UMA CONJECTURA DE 1969 SOBRE SOMAS QUE SE ANULAM SE REVELA FALSA
Pegue um relógio de seis horas e uma lista de movimentos: “avance o ponteiro 1 hora”, “avance 4 horas”, e assim por diante. Com cinco movimentos de uma hora cada, nenhum grupo deles jamais traz o ponteiro exatamente de volta ao início. Com seis movimentos, quaisquer que sejam, algum grupo sempre trará. Os matemáticos escrevem essa aritmética de relógio como C₆, e o número seis aqui é a constante de Davenport do relógio.
Agora coloque r relógios desse tipo lado a lado, e deixe cada movimento girar cada ponteiro em sua própria quantidade. A constante de Davenport desse conjunto de relógios, escrita D(C₆^r), é o menor número de movimentos que garante um grupo cujo total traz todos os ponteiros de volta ao início ao mesmo tempo — uma subsequência de soma zero, nas palavras do artigo. A constante está ligada a problemas de teoria dos grafos, geometria finita, combinatória e teoria da fatoração.
Uma fórmula de 1969
Há uma cota inferior fácil. Em cada relógio, tome cinco movimentos de uma hora que afetam apenas aquele relógio: com r relógios, isso dá 5r movimentos entre os quais nenhum grupo se anula. Portanto, são necessários pelo menos 5r + 1 movimentos. Em geral, para relógios com n horas, pelo menos r(n − 1) + 1.
Em 1969, van Emde Boas e Kruyswijk conjecturaram que essa cota fácil é sempre a resposta exata:
D(C_n^r) = r(n − 1) + 1.
Isso foi demonstrado na década de 1960 para alguns casos, como o de relógios cujo número de horas é uma potência de um número primo, ou o de no máximo dois relógios. Além disso, o valor exato permaneceu fora de alcance: ainda em 2018, nem mesmo o caso de quatro relógios de seis horas era conhecido. Mesmo assim, a conjectura tornou-se “um problema proeminente de longa data” da área, e esperava-se que fosse verdadeira.
116 movimentos que nunca se anulam
Weidong Gao (Universidade de Tianjin), Alfred Geroldinger (Universidade de Graz), Guoqing Wang (Universidade de Tiangong) e Xiangneng Zeng (Universidade Sun Yat-Sen) mostram agora que ela falha.
A equipe monta os movimentos como blocos de construção:
- uma lista de 24 movimentos em cinco relógios de seis horas, construída a partir de uma pequena tabela: qualquer grupo deles cujo total caia num pequeno conjunto de três posições sempre cai na mesma delas, uma posição diferente de zero;
- duas listas desse tipo que compartilham essas três posições, o que dá 48 movimentos sem nenhum grupo que se anule;
- uma lista separada de 20 movimentos em que também nenhum grupo se anula.
Colocadas lado a lado, elas dão 2 × 48 + 20 = 116 movimentos em 23 relógios de seis horas, e nenhum grupo deles traz todos os ponteiros de volta ao início. A conjectura dizia que 23 × 5 = 115 era a lista mais longa possível desse tipo. Portanto, para 23 relógios, a constante de Davenport é pelo menos 117, e não 116.
Cópias desse bloco podem ser empilhadas: o resultado geral é que D(C₆^r) ≥ 5r + ⌊r/23⌋ + 1, onde ⌊r/23⌋ conta quantos blocos inteiros de 23 cabem em r. A conjectura é, portanto, falsa para relógios de seis horas assim que r chega a 23, e para todo r maior. Os autores observam que o mesmo teorema também refuta um resultado conjecturado sobre recobrimentos.
O que continua em aberto
A prova não dá o verdadeiro valor de D(C₆^r), apenas uma cota que a conjectura proíbe. Ela não diz nada de novo para menos de 23 relógios, caso em que a nova cota é igual à fórmula antiga, nem para relógios com um número de horas diferente de seis. A nota tem cinco páginas, e a revisão por pares ainda está por vir.
