Erd\H{o}s's diameter conjecture for separated distances fails in high dimensions

Os autores refutam a conjectura de Erdős sobre diâmetros em espaços de alta dimensão, demonstrando que existem conjuntos de pontos com distâncias mútuas separadas por pelo menos 1 cujo diâmetro é significativamente menor do que o limite proposto, utilizando uma construção formalizada em Lean 4.

O essencial

Imagine que você tem um grupo de amigos e quer organizá-los em uma sala de dança (o "espaço"). Existe uma regra muito estrita: a distância entre qualquer par de amigos deve ser única. Não pode haver dois pares de amigos que estejam exatamente à mesma distância um do outro, nem mesmo com uma diferença de um milímetro. Se o par A e B estão a 1 metro, o par C e D não pode estar a 1 metro, nem a 1,0001 metros. Eles precisam estar "separados" por pelo menos 1 unidade de distância.

Agora, o famoso matemático Paul Erdős fez uma pergunta sobre isso há muito tempo:

"Se eu tiver muitos amigos (digamos, $n$ pessoas) e seguir essa regra de distâncias únicas, o quanto a sala de dança precisa ser grande? Ou seja, qual é a distância máxima entre os dois amigos mais afastados (o 'diâmetro' do grupo)?"

Erdős conjecturou que, não importa o quão grande fosse o número de pessoas, a sala precisaria ser enorme. Ele achava que a distância máxima teria que crescer muito rápido, algo como o quadrado do número de pessoas ($n^2$). Ele provou que isso era verdade se a dança fosse em uma linha reta (1 dimensão), mas achava que valia para qualquer espaço, mesmo em dimensões muito altas (como em um universo de 100 dimensões).

O que este artigo descobriu?

O autor deste artigo, Boon Suan Ho, disse: "Erdős estava errado para espaços de alta dimensão."

Ele construiu um exemplo matemático (uma "dança" em um espaço de muitas dimensões) onde:

1. Todas as distâncias entre os pares são únicas e separadas por pelo menos 1.
2. Mas, ao contrário do que Erdős pensava, o grupo não precisa ocupar uma sala gigantesca. Eles podem ficar todos bem mais juntos do que o esperado.

A Analogia da "Escada Mágica"

Para entender como isso é possível, imagine que você está construindo uma escada para chegar ao topo de uma montanha (o "diâmetro" do grupo).

• A visão de Erdős: Ele achava que, para ter degraus únicos e separados, você precisaria de uma escada extremamente longa e íngreme. Cada degrau teria que subir um pouco mais que o anterior, e a soma total seria gigantesca.
• A descoberta de Ho: Ele mostrou que, se você tiver um "elevador" com muitas dimensões (muitos eixos para se mover), você pode criar uma escada onde os degraus são únicos, mas a subida total é muito mais suave e curta.

Como eles fizeram isso? (A Receita Secreta)

O autor usou uma ferramenta matemática antiga chamada Conjuntos Diferenciais de Singer (pense neles como um "mapa de segredos" que garante que todas as distâncias sejam únicas).

1. O Mapa: Ele escolheu um número especial de pontos baseado em números primos.
2. A Música: Ele colocou esses pontos em um espaço multidimensional (como se fossem notas musicais em várias oitavas ao mesmo tempo).
3. O Truque: Ele ajustou o "peso" de cada nota (distância) de uma forma muito específica. Imagine que você está afinando um piano. Ele afinou as notas de modo que a diferença entre a nota mais aguda e a segunda mais aguda fosse a menor possível, mas ainda assim maior que 1.
4. O Resultado: Ao "esticar" toda a música para garantir que a menor diferença fosse pelo menos 1, ele descobriu que a música inteira cabia em um espaço muito menor do que Erdős previu.

O Veredito Final

O artigo prova que, em dimensões muito altas (como um espaço com milhares de dimensões), é possível ter um grupo de pessoas com distâncias únicas e separadas, mas que ocupam um espaço cerca de 11% menor do que a conjectura de Erdős previa.

É como se Erdős tivesse dito: "Para encaixar 100 pessoas com distâncias únicas, você precisa de um estádio de futebol."
E o autor respondeu: "Não, em um universo multidimensional, elas cabem perfeitamente em uma quadra de basquete."

Por que isso importa?

Isso mostra que a nossa intuição sobre como as coisas se organizam no espaço (geometria) muda drasticamente quando olhamos para dimensões muito altas. O que funciona em 1 ou 2 dimensões (como no chão ou em um papel) não necessariamente funciona em 100 dimensões.

Curiosidade Extra: O autor menciona que usou Inteligência Artificial (GPT-5.4 Pro e Harmonic Aristotle) para descobrir essa construção e provar a matemática no computador, mas ele mesmo verificou tudo manualmente para garantir que estava correto. É um exemplo moderno de como humanos e máquinas podem colaborar para resolver problemas antigos.

Resumo técnico

Resumo Técnico do Artigo

1. O Problema e a Conjectura

O artigo aborda uma questão clássica proposta por Paul Erdős sobre a geometria de conjuntos de pontos no espaço euclidiano.

• A Pergunta: Dado um conjunto $C$ de $n$ pontos em um espaço euclidiano (de dimensão arbitrária) tal que todas as $\binom{n}{2}$ distâncias pareadas são mutuamente separadas por pelo menos 1 (ou seja, $||x-y| - |x'-y'|| \ge 1$ para pares distintos), qual é o limite inferior para o diâmetro do conjunto (a maior distância entre dois pontos)?
• A Conjectura de Erdős: Erdős conjecturou que, independentemente da dimensão do espaço, o diâmetro deve ser pelo menos $(1 + o(1))n^2$. Ele provou isso para a dimensão 1.
• O Objetivo: O autor visa determinar se essa cota inferior é válida para dimensões arbitrárias ou se ela falha em dimensões suficientemente altas.

2. Metodologia e Construção

O autor refuta a conjectura construindo explicitamente conjuntos de pontos em dimensões altas que violam o limite proposto. A construção baseia-se em três pilares principais:

1. Conjuntos de Diferença de Singer:

   • Utiliza-se um conjunto de diferença cíclico $(m, n, 1)$ de Singer, onde $m = q^2 + q + 1$ e $n = q + 1$ (sendo $q$ uma potência de primo).
   • Existe um subconjunto $D \subset \mathbb{Z}/m\mathbb{Z}$ com tamanho $n$ tal que cada resíduo não nulo em $\mathbb{Z}/m\mathbb{Z}$ pode ser representado de forma única como $a - b$ com $a, b \in D$.
   • Isso garante que as separações cíclicas entre pares de pontos em $D$ são únicas e cobrem todos os valores de $1$a$N = \binom{n}{2}$.

2. Realização Geométrica em $\mathbb{R}^{2N}$:

   • Os pontos são mapeados para um espaço de dimensão $2N$ (onde $N = \binom{n}{2}$) utilizando um produto ponderado de polígonos regulares $m$-gonos.
   • Define-se um perfil de distâncias $d_1 < d_2 < \dots < d_N$ baseado em uma função harmônica específica.
   • As coordenadas dos pontos $v_t$ são definidas por somas de senos e cossenos ponderados por coeficientes $W_r$.

3. Perturbação de Uma Frequência e Análise Assintótica:

   • O autor define pesos $W_r$ baseados em uma série de Fourier modificada, onde os coeficientes $c_j$ são escolhidos como $c_1 = 1 - \varepsilon$ e $c_j = 1/j^2$ para $j$ ímpares $\ge 3$.
   • A função de distância resultante $G(\theta)$ é mostrada ser estritamente crescente e estritamente côncava.
   • Estratégia de Escalonamento: Como a função é côncava, as diferenças entre distâncias consecutivas ($d_{s+1} - d_s$) diminuem à medida que $s$ aumenta. O menor intervalo ocorre entre as duas maiores distâncias ($d_N - d_{N-1}$).
   • O conjunto é escalado pelo fator $\lambda = 1/(d_N - d_{N-1})$ para garantir que a menor diferença entre distâncias seja exatamente 1, satisfazendo a condição de separação.

3. Resultados Principais

O Teorema 1 do artigo estabelece que a conjectura de Erdős é falsa em geral:

• Existência de Contraexemplos: Para infinitos valores de $n$ (especificamente $n = q+1$ para potências de primas $q$), existe um conjunto $X_n \subset \mathbb{R}^{n^2-n}$ com $n$ pontos onde todas as distâncias pareadas são mutuamente separadas por pelo menos 1.
• Limite Superior do Diâmetro: O diâmetro desse conjunto é limitado por:
  $$\text{diam}(X_n) \le \left(1 - \frac{1}{\pi^2} + o(1)\right) n^2$$
• Valor da Constante: A constante $c^* = 1 - 1/\pi^2 \approx 0.89867$.
• Refutação: Como $c^* < 1$, o limite inferior $(1+o(1))n^2$ proposto por Erdős não se mantém em dimensões altas. O diâmetro real é aproximadamente 10% menor do que a conjectura previa.

4. Contribuições Chave

1. Refutação da Conjectura: Demonstra que a dependência da dimensão é crucial; a conjectura de Erdős falha quando a dimensão do espaço cresce com $n$.
2. Construção Explícita: Fornece uma construção matemática explícita baseada em teoria dos números (conjuntos de Singer) e análise harmônica, em vez de argumentos probabilísticos ou existenciais.
3. Formalização em Lean 4: O artigo destaca que a prova completa foi formalizada no assistente de prova Lean 4, garantindo a verificação rigorosa de todos os passos lógicos e analíticos.
4. Otimização Potencial: O autor nota que a constante $c^*$ pode ser ainda menor (aproximadamente 0.854) se os coeficientes da série de Fourier forem otimizados numericamente, sugerindo que o limite real pode ser ainda mais baixo.

5. Significado e Implicações

• Geometria Combinatória: O trabalho resolve um problema aberto de longa data, mostrando que o espaçamento das distâncias não impõe um limite de diâmetro tão forte quanto se pensava em dimensões altas.
• Limites de Dimensão: O resultado sugere que, embora a conjectura possa ser verdadeira para dimensões fixas (como $d=2$ ou $d=3$), ela falha assintoticamente quando a dimensão do espaço permite uma "flexibilidade" geométrica suficiente para comprimir o diâmetro.
• Métodos Híbridos: O uso de ferramentas de análise harmônica (séries de Fourier) combinadas com estruturas algébricas discretas (diferenças de Singer) abre novas vias para problemas de geometria de distâncias.
• Verificação Computacional: A formalização em Lean 4 reforça a confiabilidade dos resultados complexos de análise assintótica e cálculo de limites.

Conclusão:
O artigo de Boon Suan Ho demonstra que a conjectura de Erdős sobre o diâmetro de conjuntos com distâncias separadas é falsa em dimensões altas, estabelecendo um limite superior assintótico de aproximadamente $0.8987 n^2$, significativamente abaixo da conjectura original de $n^2$. A prova combina elegância algébrica com análise rigorosa e verificação computacional.