On the Guy-Kelly Conjecture for the No-Three-In-Line Problem

Este artigo detalha a correção de um erro heurístico encontrado por Gabor Ellmann em 2004 na conjectura de Guy e Kelly sobre o problema "no-three-in-line", apresentando pela primeira vez na literatura os pormenores dessa falha e da sua consequente correção do limite superior conjecturado.

O essencial

Imagine que você tem um tabuleiro de xadrez gigante, mas em vez de casas pretas e brancas, ele é uma grade de pontos (como uma folha de papel quadriculado). O desafio é o seguinte: Quantos pontos você consegue marcar neste tabuleiro sem que três deles fiquem alinhados em uma linha reta?

Se você marcar muitos pontos, inevitavelmente três vão acabar formando uma linha (como três estrelas no céu que parecem estar no mesmo caminho). O problema matemático "No-Three-in-Line" (Nenhum-Tres-Em-Linha) tenta descobrir qual é o número máximo de pontos que podemos colocar antes que isso aconteça inevitavelmente.

Aqui está a história contada neste artigo, explicada de forma simples:

1. O Problema do "Limite de 2"

Para um tabuleiro de tamanho $n \times n$, sabemos que podemos colocar, no máximo, $2n$pontos. É como se cada linha e cada coluna do tabuleiro tivesse um "teto" de dois ocupantes. Para tabuleiros pequenos (até 64), sabemos que conseguimos atingir exatamente esse teto ($2n$).

Mas os matemáticos acham que, para tabuleiros gigantescos (infinitos), não conseguimos chegar a esse teto de $2n$. Deve haver um limite um pouco menor.

2. A Aposta Errada de Guy e Kelly

Em 1968, dois matemáticos famosos, Guy e Kelly, tentaram prever qual seria esse limite para tabuleiros gigantes. Eles usaram um método chamado "heurística" (uma espécie de "adivinhação inteligente" baseada em probabilidades).

Eles imaginaram o seguinte:

• Se você escolher pontos aleatórios, qual a chance de três deles formarem uma linha?
• Eles calcularam essa chance e tentaram ver quantos pontos você poderia colocar antes que a chance de formar uma linha se tornasse 100%.

O resultado da conta deles foi que o número máximo de pontos seria algo como **$2,08 \times n$**. Eles achavam que o limite era um pouco acima de$2n$.

3. O Erro Escondido (O "Bug" no Código)

Em 2004, um matemático chamado Gabor Ellmann olhou para a conta deles e disse: "Ei, tem um erro aqui!".

Imagine que Guy e Kelly estavam tentando calcular a quantidade de água que cabe em uma piscina. Eles fizeram a conta certa, mas, no meio do cálculo, usaram o tamanho de uma banheira de bebê em vez do tamanho da piscina. Foi um erro pequeno, mas que mudou todo o resultado final.

O erro estava em uma fórmula onde eles usaram o número $2n$(o limite antigo) em um lugar onde deveriam ter usado uma variável genérica$k \times n$(onde$k$ é o número que estamos tentando descobrir). Foi como se eles tivessem assumido a resposta antes de fazer a conta.

4. A Correção e o Novo Limite

Quando Gabor corrigiu esse pequeno detalhe matemático, a conta mudou completamente. O novo resultado não é mais $2,08 \times n$.

O novo limite correto é:
$$\frac{\pi}{\sqrt{3}} \times n \approx 1,81 \times n$$

O que isso significa na prática?
Antes, achávamos que podíamos encher o tabuleiro com cerca de 208 pontos para cada 100 de largura. Agora, sabemos que, para tabuleiros gigantes, o limite real é mais baixo: cerca de 181 pontos para cada 100 de largura.

5. Por que este artigo é importante?

O autor deste texto, Paul Voutier, está dizendo: "Gente, esse erro foi descoberto em 2004, mas ninguém publicou a explicação detalhada de onde estava o erro e como corrigi-lo. Guy (um dos autores originais) sabia do erro, mas morreu em 2020 sem ter publicado a correção oficial.

Este artigo serve como o manual de instruções oficial para corrigir a conta antiga. Ele mostra exatamente qual linha do texto original estava errada e como a matemática se conserta para nos dar o número $1,81$em vez de$2,08$.

Resumo da Ópera

• O Desafio: Colocar o máximo de pontos em uma grade sem que três fiquem alinhados.
• A Velha Teoria: Achávamos que o limite era cerca de $2,08 \times n$.
• O Problema: Havia um erro de cálculo em 1968 que ninguém tinha apontado publicamente.
• A Solução: Um erro de "troca de variáveis" foi corrigido.
• O Novo Limite: O número máximo real é cerca de $1,81 \times n$.

É como se a gente tivesse achado que cabiam 20 pessoas em um elevador, mas, ao revisar a física do cabo de aço, descobrimos que o limite de segurança real é apenas 18. A matemática ficou mais precisa, mas um pouco mais "apertada".

Resumo técnico

Aqui está um resumo técnico detalhado do artigo "ON THE GUY-KELLY CONJECTURE FOR THE NO-THREE-IN-LINE PROBLEM", de Paul M. Voutier, apresentado em português:

1. O Problema: "No-Three-in-Line"

O artigo aborda o clássico problema de geometria discreta conhecido como "No-Three-in-Line" (Nenhum Três em Linha).

• Definição: Seja $S_n$ o conjunto de $n^2$ pontos no plano $\mathbb{R}^2$ com coordenadas inteiras $(x, y)$, onde $1 \le x, y < n$. Seja$f_n$o tamanho máximo de um subconjunto$T \subseteq S_n$tal que **nenhuma** três pontos de$T$ sejam colineares.
• Limites Conhecidos:
  • O limite superior trivial é $f_n \le 2n$, derivado do princípio da casa dos pombos.
  • Para $n \le 64$, sabe-se que $f_n = 2n$ (com a extensão para $n=64$ sendo confirmada recentemente por Prellberg em 2026).
  • A conjectura geral é que, para $n$ suficientemente grande, $f_n < 2n$.

2. Contexto Histórico e a Conjectura Original

Em 1968, Guy e Kelly publicaram um argumento heurístico que levou à seguinte conjectura sobre o comportamento assintótico de $f_n$:
$$f_n \sim \left(\frac{2\pi^2}{3}\right)^{1/3} n \approx 1.87 n$$
No entanto, em março de 2024 (referenciando uma comunicação privada de 2004), Gabor Ellmann identificou um erro no raciocínio heurístico original de Guy e Kelly. Essa correção alterou a constante assintótica para:
$$f_n \sim \left(\frac{\pi}{\sqrt{3}}\right) n \approx 1.8138 n$$
Apesar de Guy ter mencionado essa correção em comunicações privadas e em notas de rodapé, os detalhes técnicos exatos do erro e da sua correção nunca foram publicados formalmente na literatura acadêmica até este artigo.

3. Metodologia e Análise do Erro

O objetivo principal do artigo é preencher essa lacuna na literatura, fornecendo uma derivação completa e corrigida do argumento de Guy e Kelly.

• Reconstrução do Argumento Probabilístico:

  1. Contagem de Linhas: Guy e Kelly provaram que o número de conjuntos de 3 pontos colineares em $S_n$ é $t_n \sim \frac{3}{\pi^2} n^4 \log(n)$.
  2. Probabilidade de Colinearidade: A probabilidade de três pontos escolhidos aleatoriamente serem colineares é calculada como:
     $$P(\text{colinear}) \approx \frac{18 \log(n)}{\pi^2 n^2}$$
  3. Hipótese de Independência: Assumindo que os eventos de não-colinearidade são independentes, calcula-se a probabilidade de um conjunto de $kn$ pontos não conter três pontos em linha.
  4. Estimativa de Soluções: Utilizando a aproximação de Stirling e a expansão exponencial, o número estimado de soluções para um subconjunto de tamanho $kn$ é dado por:
     $$O\left( n^{kn - \frac{3k^3 n}{\pi^2}} \cdot e^{O(n)} \right)$$

• Identificação do Erro Específico:
  O autor localiza o erro exato na página 530 de [3], na linha -4.

  • O Erro: Guy e Kelly utilizaram incorretamente $2n$(o limite trivial) em vez de$kn$(o tamanho variável do subconjunto) em suas estimativas fatoriais. Especificamente, eles estimaram$(n^2)! / (n^2 - 2n)!$e$(2n)!$em vez de$(n^2)! / (n^2 - kn)!$e$(kn)!$.
  • A Consequência Matemática: Isso resultou em um termo incorreto na exponencial. Na equação original, o termo linear em $k$ era $-2 + \dots$, quando deveria ser $-k + \dots$.
  • Correção: Ao corrigir o termo para $-k + \frac{3k^3}{\pi^2}$, a condição para que a estimativa de soluções tenda a zero (indicando que tal conjunto não existe) muda.

4. Resultados Principais

A correção do termo linear altera a condição de otimização para o expoente da função de estimativa.

• A nova condição para que a probabilidade de existência de tal conjunto tenda a zero é quando o expoente se torna negativo:
  $$-k + \frac{3k^3}{\pi^2} < 0 \implies k > \frac{\pi}{\sqrt{3}}$$
• Nova Conjectura Corrigida: O artigo estabelece formalmente que, para $n$ suficientemente grande:
  $$f_n \sim \frac{\pi}{\sqrt{3}} n$$
  Onde $\frac{\pi}{\sqrt{3}} \approx 1.813799$.

5. Significado e Contribuições

• Correção Histórica: O artigo fornece a primeira publicação detalhada e técnica da correção do erro de Guy e Kelly, esclarecendo a origem exata do equívoco (substituição de $kn$ por $2n$).
• Validação de Trabalhos Recentes: Embora o trabalho de Prellberg (2026) tenha derivado independentemente a mesma constante corrigida, o artigo de Voutier foca em explicar por que o argumento original falhou, algo que não estava explícito na literatura anterior.
• Ceticismo sobre a Heurística: O autor também nota que, embora a correção matemática seja sólida, a própria premissa da "independência" dos eventos de colinearidade (usada na derivação probabilística) tem sido questionada por outros pesquisadores (como Kaplan) e por evidências empíricas em grades simétricas. Portanto, a nova constante é uma correção da heuristic, mas a validade da heurística em si permanece um tópico de discussão.

Em suma, o artigo de Voutier é uma peça fundamental para a precisão histórica e matemática do problema "No-Three-in-Line", corrigindo uma conjectura de décadas e estabelecendo o limite assintótico correto baseado na lógica probabilística original, agora livre de erros de cálculo.