🔢 mathematics

Adjacent comparison bounds and extremal sets for Ruzsa numbers

Motivado por uma conjectura de 2024, este artigo estabelece que a diferença entre números de Ruzsa consecutivos é limitada por 144, fornece limites não triviais para o tamanho de conjuntos extremais e calcula valores exatos desses números para todos os módulos até 100.

Autores originais: Yuchen Ding, Huixi Li, Junfeng Li, Wei Niu, Xiamiao Zhao

Publicado 2026-06-10

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Yuchen Ding, Huixi Li, Junfeng Li, Wei Niu, Xiamiao Zhao

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 que você está organizando uma festa enorme em uma sala circular com $m$ assentos numerados. Você convida um grupo de convidados (um subconjunto $A$ ) para ficarem em assentos específicos. A regra da festa é simples: cada um dos assentos da sala deve ser "coberto" por pelo menos um par de convidados que estão sentados lado a lado (ou do outro lado da sala) cujos números de assento somam o número daquele assento.

No entanto, há um detalhe: você não quer que nenhum assento fique lotado demais. Se muitos pares de convidados reivindicarem o mesmo número de assento, vira um caos.

O Número de Ruzsa ( $R_m$ ) é o "limite de multidão". Ele pergunta: Qual é o menor número $r$ tal que podemos organizar nossos convidados de modo que cada assento seja coberto pelo menos uma vez, mas nenhum assento seja reivindicado por mais de $r$ pares?

O artigo de Ding, Li, Li, Niu e Zhao é uma história de detetive sobre como encontrar esse limite de multidão perfeito para diferentes tamanhos de sala ( $m$ ) e entender como o limite muda quando você adiciona apenas um assento a mais na sala.

Aqui está um detalhamento de suas descobertas usando analogias do cotidiano:

1. A Regra do "Bom Vizinho" (Comparação Adjacente)

Por muito tempo, os matemáticos se perguntaram: se você tem uma sala com $m$ assentos e uma sala com $m+1$ assentos, quão diferentes podem ser os limites de multidão?

O Palpite Antigo: Alguns pensavam que o limite nunca saltaria mais do que 1. (ex: se uma sala de 36 assentos precisa de um limite de 6, uma sala de 37 assentos precisaria de 5, 6 ou 7).
O Choque de Realidade: Os autores encontraram uma falha nos dados antigos. Para uma sala de 36 assentos, o limite é 6. Mas para uma sala de 37 assentos, o limite cai para 4. Isso é um salto de 2, quebrando a regra do "nunca mais de 1".
A Nova Descoberta: Embora a regra do "salto de 1" não seja perfeita, os autores provaram que o salto nunca pode ser grande demais. Eles mostraram que a diferença entre o limite de multidão de uma sala $m$ $m$ e uma sala $m+1$ $m + 1$ nunca é superior a 144.
- Analogia: Imagine que você está subindo uma escada onde a altura do degrau muda. Você não pode pular do chão para o telhado em um único passo, mas também não pode dar um passo de 1.000 pés de altura. Os autores provaram que a altura do degrau é limitada a 144 pés.

2. O Tamanho da "Festa Perfeita" (Conjuntos Extremais)

O artigo também analisa o tamanho da lista de convidados ( $|A|$ ).

O Equilíbrio: Se você tiver poucos convidados, não conseguirá cobrir todos os assentos. Se tiver convidados demais, criará caos demais (um $R_m$ alto).
A Descoberta: Os autores calcularam exatamente quantos convidados são necessários para salas de até tamanho 100. Eles descobriram que, para salas grandes, o "ponto ideal" para o tamanho da lista de convidados é aproximadamente a raiz quadrada do número de assentos.
O Limite: Eles provaram que, para qualquer sala grande, o número de convidados necessários para manter o caos sob controle (especificamente abaixo do limite de 192) nunca excederá aproximadamente $\sqrt{191 \times \text{assentos}}$ .

3. O "Número Mágico" 6

Uma das descobertas mais surpreendentes é um padrão nos dados.

A Observação: Quando a sala fica grande o suficiente (especificamente, 40 assentos ou mais), o "limite de multidão" ( $R_m$ ) parece se estabilizar no número 6.
A Conjectura: Os autores suspeitam que, para qualquer sala com 40 ou mais assentos, você sempre poderá organizar os convidados de modo que nenhum assento seja reivindicado mais de 6 vezes. Eles verificaram isso para cada tamanho de sala até 100.
- Analogia: É como descobrir que, não importa o quão grande sua cidade se torne, você sempre precisará de apenas 6 semáforos em qualquer cruzamento para manter o tráfego fluindo suavemente, desde que a cidade seja grande o suficiente.

4. Como Eles Fizeram (A Busca pelo Certificado)

Os autores não apenas adivinharam; eles realizaram uma busca computacional massiva.

O Processo: Eles atuaram como arquitetos digitais. Para cada tamanho de sala, tentaram construir uma lista de convidados que funcionasse.
O "Certificado": Se eles encontrassem uma lista onde cada assento fosse coberto e nenhum assento tivesse mais de 6 pares, essa lista tornava-se um "certificado" provando que o limite é 6.
A Busca: Eles usaram supercomputadores para testar milhões de combinações. Para salas menores, eles provaram que era impossível fazer isso com um limite de 5, confirmando que 6 era, de fato, o mínimo.

5. Questões Abertas (A Festa Inacabada)

O artigo termina fazendo novas perguntas, como:

O Problema do Espaço Vazio: Se você tem uma sala enorme, é possível ter um enorme espaço vazio entre os convidados? (Eles provaram que o espaço não pode ser maior que metade do tamanho da sala).
O Problema Par/Ímpar: Os convidados tendem a sentar em assentos de números pares ou ímpares? (Eles descobriram que, para salas grandes, a mistura é quase perfeitamente equilibrada).
O Proble de "Exatamente Dois": É possível organizar os convidados de modo que nenhum assento seja reivindicado por exatamente dois pares? (Eles provaram que, se a lista de convidados for pequena o suficiente, você deve ter alguns assentos reivindicados por exatamente dois pares).

Resumo

Em suma, este artigo é um mergulho profundo na matemática de empacotamento e cobertura. Ele responde à pergunta: "Quão eficientemente podemos cobrir um círculo com somas de pares?"

Eles corrigiram um pequeno erro em cálculos anteriores.
Provaram que o "limite de multidão" não flutua drasticamente entre os tamanhos das salas.
Descobriram que, para salas grandes, o limite se estabiliza em 6.
Forneceram uma tabela massiva de soluções exatas para salas de até tamanho 100, servindo como referência para futuros matemáticos.

O trabalho é puramente teórico — trata-se da estrutura de números e padrões, não de aplicações físicas como tráfego ou biologia, embora a lógica de "cobertura eficiente" seja um conceito fundamental em muitos campos.

Resumo Técnico: Limites de Comparação Adjacente e Conjuntos Extremais para Números de Ruzsa

Definição do Problema
Seja $m$ um número inteiro positivo e $\mathbb{Z}_m$ o anel de classes de resíduos módulo $m$ . Para um subconjunto $A \subset \mathbb{Z}_m$ , seja $\sigma_A(n)$ o número de pares ordenados $(a, a') \in A^2$ tais que $a + a' \equiv n \pmod m$ . O número de Ruzsa $R_m$ é definido como o menor inteiro $r$ tal que exista um subconjunto $A \subset \mathbb{Z}_m$ satisfazendo $1 \le \sigma_A(n) \le r$ para todo $n \in \mathbb{Z}_m$ . Este conceito é motivado pela conjectura de Erdős-Turán sobre bases aditivas. Trabalhos anteriores estabeleceram que $R_m$ é limitado por uma constante absoluta, com limites superiores melhorados ao longo do tempo de $C$ (Ruzsa) para $768$ (Tang e Chen), $5120$ (Tang e Chen) e, finalmente, $288$ (Chen). Mais recentemente, Ding e Zhao (2024) melhoraram o limite superior para $R_m \le 192$ e conjecturaram que $|R_{m+1} - R_m| \le 1$ para todo $m$ .

Metodologia
Os autores empregam uma combinação de lemas de comparação combinatórios, desigualdades analíticas envolvendo funções de representação e verificação computacional extensiva.

Lemas de Comparação: O artigo introduz um novo lema de comparação (Lema 3.2) estabelecendo que $R_m \le 4R_{m+1}$ e $R_{m+1} \le 4R_m$ . Isso é alcançado construindo bases aditivas em $\mathbb{Z}_{m+1}$ a partir de bases em $\mathbb{Z}_m$ (e vice-versa) usando translações de conjuntos e uniões, então limitando as contagens de representação dos novos conjuntos.
Limites Analíticos: Para estimar o tamanho de conjuntos extremais $A$ (onde $1 \le \sigma_A(n) \le R_m$ ), os autores utilizam a desigualdade de Lev-Sárközy (Lema 2.1). Ao analisar o desvio de média quadrática de $\sigma_A(n)$ em relação a uma constante $c$ , eles derivam desigualdades quadráticas relacionando a cardinalidade $|A|$ com $m$ e $R_m$ .
Verificação Computacional: Os autores realizam uma busca baseada em certificados para determinar os valores exatos de $R_m$ $R_{m}$ para $m$ $m$ até 100.
- Para $m \le 45$ , eles verificam a exatidão provando a não existência de conjuntos com limites de representação inferiores aos $R_m$ reivindicados.
- Para $m > 45$ , eles dependem de uma prova de limite inferior ( $R_m \ge 6$ ) e buscam conjuntos satisfazendo $\max \sigma_A(n) \le 6$ .
- A busca utiliza um procedimento de otimização heurística envolvendo translação de conjuntos, substituição de elementos e tentativas orçamentadas para minimizar defeitos de representação.

Contribuições Principais e Resultados

Limite de Comparação Adjacente (Teorema 1.1): Os autores provam que, para qualquer número inteiro positivo $m$ , $|R_{m+1} - R_m| \le 144$ . Isso melhora o limite trivial de $186$ (derivado de $192 - 6$) usando o novo lema de comparação e o limite superior conhecido de $R_m \le 192$ .
Valores Exatos e Contraexemplos: O artigo fornece uma tabela de valores exatos para $R_m$ $R_{m}$ para todos os $2 \le m \le 100$ $2 \leq m \leq 100$ .
- O cálculo revela que $R_{37} = 4$ e $R_{39} = 5$ .
- Especificamente, $R_{36} = 6$ e $R_{37} = 4$ , o que serve como um contraexemplo para a conjectura original de Ding-Zhao ( $|R_{m+1} - R_m| \le 1$ ) para $m=36$ .
- Os autores propõem uma conjectura revisada: $|R_{m+1} - R_m| \le 1$ ocorre para todo $m$ suficientemente grande.
- Eles conjecturam ainda que $R_m = 6$ para todo $m \ge 40$ (Conjectura 2.3).
Limites no Tamanho do Conjunto Extremal (Teorema 1.2): Para um $m$ suficientemente grande e um conjunto $A$ que atinge o número de Ruzsa, os autores derivam limites não triviais para $|A|^2$ . Seja $s = \lfloor R_m/2 \rfloor$ . O tamanho satisfaz:
$\left( s + \frac{1}{2} - \sqrt{\left(s+\frac{1}{2}\right)^2 - 4s - \epsilon} \right)m \le |A|^2 \le \left( s + \frac{1}{2} + \sqrt{\left(s+\frac{1}{2}\right)^2 - 4s + \epsilon} \right)m$
Como corolário, se $R_m = 6$ , então $|A| \le \sqrt{191m}$ .
Propriedades Estruturais: O artigo investiga propriedades dos conjuntos $A_m$ $A_{m}$ (subconjuntos que atingem $R_m$ $R_{m}$ ).
- Paridade: A Proposição 5.5 fornece limites na proporção de elementos pares em $A$ quando $m$ é par. Se $R_m = 6$ , a proporção de elementos pares é limitada dentro de $\approx 0,14$ de $1/2$ .
- Progressões Aritméticas: O artigo define $L_m$ como o comprimento máximo de uma progressão aritmética contida em qualquer $A \in A_m$ . Nota-se que $L_m \le R_m$ .
- Cardinalidade de $A_m$ : A Proposição 5.6 estabelece limites assintóticos para o número de tais conjuntos, $|A_m|$ , mostrando que $\frac{1}{2}\log m - C \le \log |A_m| \le \sqrt{191m} \log(\dots)$ .

Significância
O artigo refina a compreensão do comportamento dos números de Ruzsa, abordando especificamente a estabilidade de $R_m$ sob mudanças de módulo adjacentes. Ao refutar a conjectura estrita $|R_{m+1} - R_m| \le 1$ para pequenos valores de $m$ , enquanto fornece evidências fortes para sua validade assintótica, os autores esclarecem a interação entre estrutura algébrica (propriedades do módulo) e aleatoriedade combinatória. A provisão de valores exatos até $m=100$ estende substancialmente as tabelas anteriores, e os limites derivados para o tamanho dos conjuntos extremais oferecem novas restrições para pesquisas futuras sobre bases aditivas em grupos cíclicos. O trabalho também propõe vários problemas abertos relativos à distribuição dos valores de representação, a estrutura dos conjuntos extremais e o crescimento do número de tais conjuntos.