🔢 mathematics

Restricted partition functions and additive complements

Este artigo responde positivamente a uma questão de 2016 de Dai e Chen ao construir conjuntos infinitos de inteiros positivos que produzem uma função de partição restrita com crescimento polinomial, garantindo ao mesmo tempo que todo inteiro positivo tenha pelo menos uma representação.

Autores originais: Yuchen Ding

Publicado 2026-06-17

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Yuchen Ding

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ê tem uma caixa de ferramentas gigante e infinita cheia de blocos de construção especiais. Cada bloco tem um tamanho específico, determinado por um número em uma lista chamada Conjunto A. Você também tem um livro de regras especial chamado Conjunto M que diz quantos de cada bloco você tem permissão para usar.

O matemático neste artigo, Yuchen Ding, está fazendo uma pergunta muito específica: Podemos projetar essas duas listas (A e M) de modo que possamos construir todos os números inteiros positivos (1, 2, 3, etc.), mas sem que o número de maneiras de construí-los saia do controle?

Aqui está uma decomposição dos conceitos usando analogias do cotidiano:

1. Os Blocos de Construção (Partições Restritas)

Pense no número $n$ (como 100) como uma torre que você deseja construir.

Conjunto A é sua lista de tamanhos de blocos disponíveis (ex: 1, 4, 16, 256...).
Conjunto M é seu livro de regras para "múltiplos". Ele diz: "Você pode usar 0, 1 ou 2 do bloco de tamanho 4, mas talvez 0, 5 ou 10 do bloco de tamanho 16".
O Objetivo: Você quer ser capaz de construir qualquer número $n$ usando essas regras.
O Problema: Se você tiver muitas maneiras de construir o mesmo número, a matemática fica confusa. O autor quer provar que o número de maneiras de construir qualquer torre ( $p$ ) cresce lentamente — especificamente, com "crescimento polinomial".

A Analogia: Imagine que você está assando biscoitos.

Se você tiver 100 receitas diferentes para um biscoito de gotas de chocolate, é muito trabalho para acompanhar.
"Crescimento polinomial" significa que, à medida que você tenta assar lotes cada vez maiores de biscoitos, o número de novas receitas únicas que você descobre não explode instantaneamente para os milhões. Ele cresce em um ritmo gerenciável e previsível.

2. O Problema do "Gap" (Lacuna)

Antes deste artigo, os matemáticos sabiam como criar listas onde era possível construir todos os números, mas o "gap" entre os tamanhos dos blocos não era tão grande.

A Pergunta: Podemos criar uma lista onde os blocos ficam massivamente maiores muito rapidamente? Imagine uma lista onde o primeiro bloco é de tamanho 1, o próximo é 100, o próximo é 10.000 e o próximo é 1.000.000.
O espaço entre esses números é tão amplo que a matemática geralmente entra em colapso, tornando impossível construir todos os números ou fazendo com que o número de receitas exploda.

3. A Solução: O "Par Perfeito"

Ding prova que a resposta é SIM. Você pode criar esses gaps massivos e ainda assim construir todos os números com um número gerenciável de receitas.

Ele faz isso introduzindo um truque inteligente envolvendo Complementos Aditivos.

A Metáfora: Imagine dois times, Time B e Time S.
- O Time B tem membros que são potências de 2 (1, 2, 4, 8, 16...).
- O Time S é um grupo especial de números que preenche os "buracos" deixados pelo Time B.
- Juntos, se você pegar um membro do Time B e um do Time S e somar seus "valores", você pode formar todos os números na linha numérica. Eles são "complementos".

Ding usa um resultado famoso do matemático Ruzsa para encontrar um Time S que seja apenas esparso o suficiente para ser interessante, mas denso o suficiente para preencher os buracos.

4. Como a Construção Funciona

Ding cria suas duas listas mágicas, A e M, baseadas nesses times:

Conjunto A (Os Blocos): Ele pega os números do Time B e os transforma em potências de 2 (ex: $2^1, 2^2, 2^4, 2^8...$ ). Isso cria os "gaps massivos" exigidos pela questão.
Conjunto M (As Regras): Ele cria regras baseadas no Time S. As regras permitem que você combine pequenas partes do Time S para formar os coeficientes (a parte do "quantos").

A Magia: Como o Time B e o Time S são complementos perfeitos, você sempre pode decompor qualquer número em uma soma que se encaixe nessas regras específicas. Como o Time S é cuidadosamente escolhido, o número de maneiras de fazer isso não explode; ele permanece dentro de um limite "polinomial" (uma taxa de crescimento gerenciável).

5. Por Que Isso Importa (De Acordo com o Artigo)

Este artigo responde a uma pergunta feita por Dai e Chen em 2016.

A Pergunta: "Existem dois conjuntos infinitos onde os blocos ficam infinitamente distantes uns dos outros, mas ainda assim podemos construir todos os números com um número gerenciável de combinações?"
A Resposta: Sim. Ding construiu um exemplo específico onde os gaps entre os blocos crescem tão rápido que a razão de seus logaritmos tende ao infinito, mas o sistema ainda funciona perfeitamente.

Uma Nota sobre o Ingrediente "IA"

O autor, Yuchen Ding, declara abertamente que usou uma ferramenta de IA (ChatGPT) durante o processo de pesquisa.

O que a IA fez: Ela sugeriu olhar para conjuntos envolvendo potências de 2 e o direcionou para um teorema específico de Ruzsa sobre "sequências lacunares" (sequências com grandes intervalos).
O que o Autor fez: O autor verificou a matemática, checou a lógica, reorganizou a prova e escreveu o artigo final. Ele assume total responsabilidade pela precisão do trabalho.

Resumo

Yuchen Ding resolveu um quebra-cabeça sobre construção de números. Ele mostrou que você pode ter um conjunto de blocos de construção que estão espaçados de forma incrivelmente distante (como uma escada com degraus que ficam cada vez mais longe uns dos outros) e um conjunto de regras para usá-los, de tal forma que:

Você pode construir todos os números inteiros.
O número de maneiras de construí-los não sai do controle.

É como provar que você pode ter uma escada com degraus espaçados por uma milha, mas ainda assim pode subí-la suavemente sem cair, usando um conjunto específico e gerenciável de técnicas de escalada.

Resumo Técnico: Funções de Partição Restritas e Complementos Aditivos

Enunciado do Problema
O artigo aborda uma questão específica na teoria aditiva dos números referente a funções de partição restritas. Seja $\mathbb{N}$ o conjunto dos inteiros positivos e $\mathbb{N}_0 = \mathbb{N} \cup \{0\}$ . Para subconjuntos $A, M \subseteq \mathbb{N}$ , a função de partição restrita $p(n, A, M)$ conta o número de representações de um inteiro $n$ na forma:
$n = \sum_{a \in A} m_a a$
onde $m_a \in M \cup \{0\}$ para todo $a \in A$ , e apenas finitos $m_a$ são não nulos. A função $p$ é dita ter crescimento polinomial se existirem constantes $c > 0$ e $n_0$ tais que $p(n, A, M) \leq n^c$ para todo $n \geq n_0$ .

O problema central, proposto por Dai e Chen em 2016 (Questão 1), questiona se existem dois conjuntos infinitos $A = \{a_n\}_{n=1}^\infty$ e $M$ de inteiros positivos tais que:

O conjunto $A$ é extremamente esparso, satisfazendo $\lim_{n\to\infty} \frac{\log a_{n+1} - \log a_n}{\log n} = +\infty$ .
$p(n, A, M) > 0$ para todo $n$ suficientemente grande (ou seja, todo inteiro grande é representável).
A função de partição $p(n, A, M)$ exibe crescimento polinomial.

Trabalhos anteriores de Alon (2012) e Dai e Chen (2016) haviam estabelecido a existência de tais conjuntos com crescimento polinomial sob condições de esparsidade menos rigorosas ou com limites de expoentes específicos (por exemplo, $p(n) < n^{2+o(1)}$ ), mas o caso da esparsidade super-logarítmica permanecia em aberto.

Metodologia
O autor, Yuchen Ding, emprega uma construção baseada em complementos aditivos e expansões binárias. A estratégia central envolve:

Definição de Complementos Aditivos: Dois conjuntos $B, S \subseteq \mathbb{N}_0$ são chamados de complementos aditivos completos se $B + S = \mathbb{N}_0$ .
Construção dos Conjuntos $A$ e $M$ : O artigo constrói $A$ $A$ e $M$ $M$ baseando-se em um par de complementos aditivos $B$ $B$ e $S$ $S$ que satisfazem uma condição de contagem específica. Especificamente:
- $A = \{2^b : b \in B\}$
- $M = \{ \sum_{d \in D} 2^d : D \subset S, 0 < |D| < \infty \}$ (somas de subconjuntos finitos de potências de 2 provenientes de $S$ ).
Mapeamento Injetivo: A prova estabelece um mapeamento injetivo das representações de $n$ contadas por $p(n, A, M)$ para subconjuntos finitos do espaço produto $S \times B$ . Ao utilizar a unicidade das expansões binárias, o autor mostra que qualquer representação de $n$ corresponde a um conjunto de pares $(s, b)$ tal que $s+b \leq \log_2 n$ .
Limitação do Crescimento: O número dessas representações é limitado pelo número de pares $(s, b) \in S \times B$ com $s+b \leq N$ (onde $N \approx \log_2 n$ ). Esta contagem é mostrada ser limitada por $S(N)B(N)$ . Se $B(x)S(x) \ll x$ , a função de partição resultante cresce polinomialmente.

Contribuições Principais e Resultados
O artigo fornece uma resposta afirmativa à Questão 1 de Dai e Chen através dos seguintes resultados:

Teorema 1: Sejam $B$ e $S$ complementos aditivos completos satisfazendo a condição de contagem $B(x)S(x) \ll x$ . Se $A$ e $M$ forem definidos como acima, então $p(n, A, M) > 0$ para todo $n \in \mathbb{N}$ e $p(n, A, M)$ possui crescimento polinomial.
Corolário 1 (Resolução da Questão 1): Ao invocar um resultado de Ruzsa (1972) referente a complementos aditivos de potências de dois, o autor constrói conjuntos específicos $A$ $A$ e $M$ $M$ que satisfazem as condições do Teorema 1.
- Seja $B = \{0\} \cup \{2^k : k \geq 0\}$ .
- $S$ é um subconjunto de $\mathbb{N}$ derivado do teorema de Ruzsa tal que $S(x) \ll x / \log x$ e $B+S = \mathbb{N}_0$ (após a adição de elementos finitos).
- O conjunto $A$ resultante tem elementos $a_n = 2^{2^{n-2}}$ para $n \geq 2$ .
- Esta construção produz $\lim_{n\to\infty} \frac{\log a_{n+1} - \log a_n}{\log n} = +\infty$ , satisfazendo o requisito de esparsidade extrema.
- Como $B(x) \ll \log x$ e $S(x) \ll x / \log x$ , o produto $B(x)S(x) \ll x$ é mantido, garantindo o crescimento polinomial de $p(n, A, M)$ .

Significância
O artigo afirma responder a uma questão de 2016 de Dai e Chen de forma afirmativa. Ele demonstra que é possível construir funções de partição restritas que são sobrejetivas (representam todos os inteiros positivos) e possuem crescimento polinomial, mesmo quando o conjunto de partes permitidas $A$ é significativamente mais esparso do que exemplos conhecidos anteriormente (especificamente, satisfazendo uma condição de limite onde a lacuna logarítmica entre elementos consecutivos cresce mais rápido do que qualquer potência de $\log n$ ).

O trabalho generaliza resultados anteriores ao vincular a taxa de crescimento de funções de partição restritas diretamente às propriedades de contagem de complementos aditivos. O autor observa que a construção foi inicialmente explorada com a assistência de IA generativa (ChatGPT), que sugeriu a forma específica dos conjuntos e a conexão com o teorema de Ruzsa, embora a verificação matemática, reorganização e a prova final sejam seu trabalho independente.