🔢 mathematics

Solution of Erd\H{o}s problem $\# 443$

Este artigo resolve o problema nº 443 de Erdős ao provar que o tamanho da interseção entre os conjuntos de produtos $\{k(m-k)\}$ e $\{l(n-l)\}$ é limitado por $(mn)^{o(1)}$ , mas ainda pode ser arbitrariamente grande.

Autores originais: Stijn Cambie

Publicado 2026-07-29

📖 4 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Stijn Cambie

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine um mundo onde os números não são apenas dígitos frios e duros, mas sim jogadores em um grande jogo invisível de esconde-esconde. Este é o reino da teoria dos números, um ramo da matemática que trata os números inteiros como personagens únicos com identidades secretas. Neste jogo, frequentemente olhamos para "conjuntos" — que são apenas palavras sofisticadas para coleções de números — criados ao seguir uma regra específica. Por exemplo, se você pegar um número, multiplicá-lo por seu parceiro (o número que soma um determinado total) e listar todos os resultados, você obtém um padrão único. Os matemáticos adoram perguntar: "Se eu criar dois padrões diferentes usando regras diferentes, quantos números eles terão em comum?" É como perguntar quantos termos aparecem tanto em um dicionário de poesia antiga quanto em um dicionário de gírias modernas. A questão pode parecer um enigma para um clube de matemática, mas nos ajuda a entender a arquitetura oculta dos números, revelando se os padrões são raros, comuns ou completamente imprevisíveis.

O artigo sobre o qual você está prestes a ouvir aborda um enigma específico proposto pelo lendário matemático Paul Erdős. Ele se perguntou sobre duas coleções especiais de números. A primeira coleção é feita pegando um número $m$ , escolhendo um número menor $k$ (de 1 até metade de $m$ ) e calculando o produto $k(m-k)$ . A segunda coleção faz exatamente a mesma coisa, mas com um número $n$ diferente. A grande questão era: À medida que esses números se tornam enormes, quantos "amigos comuns" (números que aparecem em ambas as listas) eles podem compartilhar? Erdős supôs que, embora o número de amigos compartilhados possa crescer, ele cresceria muito lentamente — tão lentamente que, para qualquer margem de erro minúscula que você escolher, a contagem seria eventualmente menor do que uma fórmula matemática específica envolvendo o tamanho dos números. Ele também perguntou se esse número de amigos compartilhados poderia crescer sem nunca parar ou se atingiria um teto.

O autor deste artigo, Stijn Cambie, atua como um detetive resolvendo este mistério de décadas. Ele confirma que o número de amigos compartilhados é, de fato, ilimitado, o que significa que pode tornar-se tão grande quanto você desejar se escolher os números $m$ e $n$ certos. Para provar isso, ele usa um truque inteligente: ele mostra que encontrar um número compartilhado é o mesmo que encontrar uma maneira de decompor uma diferença de quadrados específica em duas partes menores. Isso transforma o problema em contar os "divisores" (os blocos de construção) de um número. Como sabemos que alguns números possuem um número enorme de divisores, Cambie prova que sempre podemos encontrar pares de $m$ e $n$ que criem uma quantidade massiva de amigos compartilhados.

No entanto, o artigo também estabelece um limite de velocidade estrito para esse crescimento. Cambie demonstra que, embora o número de amigos compartilhados possa tornar-se enorme, ele cresce incrivelmente devagar — tão devagar que se encaixa na suposição da "margem minúscula" de Erdős. Ele mostra que a contagem é limitada por uma função que é essencialmente "quase constante" em relação ao tamanho dos números envolvidos. Em termos simples, mesmo que você escolha os melhores números possíveis para maximizar a sobreposição, o número de amigos compartilhados nunca explodirá; ele sempre permanecerá uma fração minúscula do total de números envolvidos.

Curiosamente, o artigo revela uma reviravolta na história: este problema não foi, na verdade, uma descoberta nova. O autor observa que um matemático chamado Norbert Hegyvári resolveu este exato problema 40 anos antes, mas sua prova só foi publicada recentemente. Portanto, embora este artigo forneça uma explicação nova e clara e confirme a resposta, o status de "resolvido" do problema pertence, na verdade, a esse trabalho anterior, há muito tempo oculto. O artigo não apenas supõe; ele fornece uma prova matemática, mostrando exatamente como o número de amigos compartilhados se comporta e confirmando que ele é tanto ilimitado quanto surpreendentemente pequeno em relação ao tamanho dos números utilizados.

Resumo Técnico: Solução do Problema #443 de Erdős

Enunciado do Problema
Este artigo aborda o Problema #443 proposto por Erdős e Graham em seu trabalho de 1980 [1]. O problema refere-se a dois conjuntos de inteiros gerados pelas formas quadráticas $k(m-k)$ e $\ell(n-\ell)$ , onde $1 \le k \le m/2$ e $1 \le \ell \le n/2$ . Especificamente, seja $S(m) = \{k(m-k) : 1 \le k \le m/2\}$ e $S(n) = \{\ell(n-\ell) : 1 \le \ell \le n/2\}$ . As questões centrais são:

É possível estimar o número de inteiros comuns, denotado por $f(n, m) = \#(S(m) \cap S(n))$ ?
Esse número é ilimitado conforme $m$ e $n$ variam?
O número de elementos comuns é estritamente menor que $(mn)^\epsilon$ para todo $\epsilon > 0$ quando $mn$ é suficientemente grande?

Metodologia e Derivação
O autor, Stijn Cambie, adota a notação $f(n, m)$ e assume, sem perda de generalidade, que $m > n$ . O núcleo da metodologia envolve transformar a condição de interseção em uma diferença de quadrados.

Ao observar que $k(2m-k) = m^2 - (m-k)^2$ , o autor define $c = m-k$ . A condição para um inteiro estar em ambos os conjuntos, $k(2m-k) = \ell(2n-\ell)$ , é reescrita como:
$m^2 - c^2 = n^2 - d^2$
onde $d = n-\ell$ . Reorganizando os termos, obtém-se:
$m^2 - n^2 = c^2 - d^2 = (c-d)(c+d)$
Esta transformação demonstra que o número de soluções é limitado por metade do número de divisores do inteiro $m^2 - n^2$ , denotado por $\tau(m^2 - n^2)$ . A restrição de que $c-d$ deve ser um divisor limitado por $\sqrt{m^2 - n^2}$ é utilizada para estabelecer este limite.

Resultados Principais

Limite Superior: O artigo estabelece que $f(n, m) \le \lfloor \tau(m^2 - n^2) / 2 \rfloor$ . Ao invocar o resultado bem conhecido sobre a função divisor $\tau(x)$ , que afirma que $\tau(x) \le 2^{(1+o(1))\frac{\log x}{\log \log x}} = x^{o(1)}$ , o autor confirma que $f(n, m) = (mn)^{o(1)}$ . Isso afirma a conjectura de que o número de inteiros comuns é menor que $(mn)^\epsilon$ para qualquer $\epsilon > 0$ quando $mn$ é suficientemente grande.
Ilimitabilidade: Para abordar se o número de inteiros comuns é ilimitado, o autor considera o caso específico onde $m = n+1$ . Neste cenário, $m^2 - n^2 = 2n+1$ . O número de soluções é mostrado como sendo relacionado a $\lfloor \tau(2n+1)/2 \rfloor - 1$ . Como $\tau(x)$ é ilimitada (atingindo valores grandes para números altamente compostos), $f(2n+2, 2n)$ é ilimitada. A construção mapeia explicitamente fatorações de $2n+1 = pq$ (com $p \ge q \ge 2$ ) para soluções inteiras válidas para $c$ e $d$ .

Significância e Alegações
O artigo afirma fornecer uma solução completa para o Problema #443 de Erdős, confirmando tanto a taxa de crescimento subpolinomial quanto sua natureza ilimitada.

O autor inclui uma observação específica sobre o histórico da solução: Norbert Hegyvári [2] resolveu este problema independentemente 40 anos antes da publicação desta nota. No entanto, a prova de Hegyvári só foi publicada recentemente, após a submissão desta nota. O artigo posiciona-se como uma verificação e solução independente do problema, ao mesmo tempo em que reconhece o trabalho prévio e tardio de Hegyvári.

Referências Citadas no Artigo

[1] P. Erdős e R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, 1980.
[2] N. Hegyvári, (Solução do problema, publicada recentemente).
[3] Resultado padrão sobre a função divisor $\tau(x)$ .

Mais como este