On the Monotonicity of Higher-Fold Representation Functions

Resumo Técnico: Sobre a Monotonicidade de Funções de Representação de Ordem Superior

Enunciado do Problema
O artigo investiga as propriedades de monotonicidade da função de representação ordenada de ordem $h$, $R_{A,h}(n)$, definida como o número de soluções ordenadas para $n = a_1 + \dots + a_h$, onde $a_i \in A$, sendo $A \subseteq \mathbb{N}$. A questão central é se $R_{A,h}(n)$ pode ser estritamente crescente para um conjunto $A$ cujo complemento $\mathbb{N} \setminus A$ é infinito (um conjunto co-infinito).

Historicamente, Erdős, Sárközy e Sós provaram que, para $h=2$, a monotonicidade estrita implica que $A$ é cofinito (ou seja, o complemento é finito). Para $h \ge 3$, Dombi conjecturou que, se $\mathbb{N} \setminus A$ for infinito, $R_{A,h}(n)$ não pode ser eventualmente estritamente crescente. Esta conjectura foi refutada por Shallit, que utilizou a teoria de autômatos para construir um conjunto co-infinito $A$ onde $R_{A,3}(n)$ é estritamente crescente. Especificamente, Shallit utilizou o conjunto $B = \{0\} \cup \{m \ge 1 : \text{a expansão na base 4 de } m \text{ começa com 1 ou 2}\}$. Embora Shallit tenha estabelecido a monotonicidade estrita para $R_{B,h}(n)$ para um $h \ge 3$ fixo, a taxa de crescimento precisa da diferença $R_{B,h}(n+1) - R_{B,h}(n)$ permaneceu uma questão quantitativa em aberto. Além disso, Dombi propôs um problema sobre a existência de tais conjuntos com densidade assintótica $\alpha \neq 1/2$ (ou especificamente $\alpha \neq 1$).

Metodologia
Os autores empregam uma combinação de funções geradoras, relações de recorrência derivadas da estrutura autossimilar do conjunto $B$ e argumentos de convolução para estabelecer limites na função de diferença $\Delta_h(n) = R_{B,h}(n+1) - R_{B,h}(n)$.

1. Análise de Recorrência para o Conjunto $B$:
   O conjunto $B$ é definido por sua sequência indicadora $c_n$, que satisfaz uma equação funcional em sua função geradora $C(x) = \sum c_n x^n$:
   $$C(x) = (1+x+x^2+x^3)C(x^4) - x^3$$
   Ao elevar ao quadrado e ao cubo esta equação, os autores derivam relações de recorrência para as diferenças das funções de representação de ordem dois ($\beta_n$) e ordem três ($\alpha_n$).

• Lema 2.1 & 2.2: Estes lemas estabelecem fórmulas recursivas para $\beta_n$ e $\alpha_n$ baseadas em valores nos índices $n/4$.
• Limites em $\beta_n$: O Lema 3.1 prova que a diferença para a função de ordem dois é limitada: $-1 \le \beta_n \le 2$.
• Limites em $\alpha_n$: Utilizando os limites em $\beta_n$ e as relações de recorrência, o Lema 3.2 estabelece um limite inferior linear $\alpha_n \ge n/5 + 4$ para $n \ge 78$, enquanto o Lema 3.3 fornece um limite superior linear $\alpha_n \le 3n + 2$.

2. Elevação por Convolução (Convolution Lift):
   Para estender os resultados de $h=3$ para qualquer $h \ge 3$, os autores utilizam a identidade de convolução:
   $$R_{p+q}(n) = \sum_{u=0}^n R_p(n-u)R_q(u)$$
   Isso leva a uma relação para as diferenças:
   $$\Delta_{p+q}(n) = \sum_{u=0}^n \Delta_p(n-u)R_q(u) + R_p(0)R_q(n+1)$$
   Ao definir $p=3$ e $q=h-3$, o comportamento de $\Delta_h(n)$ é controlado pelo comportamento conhecido de $\Delta_3(n)$ (ou seja, $\alpha_n$) e pelo crescimento de $R_{h-3}(n)$.

3. Construção do Conjunto $C$:
   Para abordar o problema de densidade de Dombi, os autores constroem um conjunto $C = \mathbb{N} \setminus \{2^j : j \ge 10\}$. Eles analisam a função geradora $G_C(x) = (1-x)^{-1} - D(x)$, onde $D(x)$ corresponde às potências de 2 removidas. A esparsidade do conjunto removido permite uma estimativa explícita da diferença $R_{C,h}(n+1) - R_{C,h}(n)$.

Principais Contribuições e Resultados

1. Ordem de Crescimento Polinomial (Teorema 1.1):
   O artigo prova que, para o conjunto $B$, a diferença $R_{B,h}(n+1) - R_{B,h}(n)$ cresce polinomialmente com ordem $n^{h-2}$. Especificamente, para todo inteiro $h \ge 3$, existem constantes $c_h, C_h > 0$ tais que, para todo $n \ge 1$:
   $$c_h n^{h-2} \le R_{B,h}(n+1) - R_{B,h}(n) \le C_h n^{h-2}$$
   Este resultado confirma que, apesar de $B$ possuir um complemento infinito com grandes lacunas, sua função de representação comporta-se assintoticamente como a do conjunto completo $\mathbb{N}$ (onde a diferença é $\binom{n+h-1}{h-2} \asymp n^{h-2}$).

2. Monotonicidade Estrita para Qualquer $h \ge 3$:
   Os autores provam rigorosamente que $R_{B,h}(n+1) > R_{B,h}(n)$ para todo $n \ge 0$ e para todo $h \ge 3$, melhorando o resultado de Shallit, que focava na existência de tais conjuntos sem quantificar a taxa de crescimento para todos os $h$.

3. Resolução do Problema de Densidade de Dombi (Teorema 1.2):
   O artigo constrói um conjunto co-infinito $C = \mathbb{N} \setminus \{2^j : j \ge 10\}$ tal que:

• A densidade assintótica existe e é igual a 1: $\lim_{n \to \infty} C(n)/n = 1$.
• A função de representação $R_{C,h}(n)$ é estritamente crescente para cada inteiro $h \ge 3$.
  Isso responde ao problema de Dombi ao fornecer um conjunto com densidade 1 (distinto dos exemplos de densidade 1/2 conhecidos anteriormente) que mantém a monotonicidade estrita.

Significância
O artigo refina a compreensão das funções de representação aditiva em conjuntos co-infinitos. Ele demonstra que o obstáculo à monotonicidade encontrado no caso $h=2$ não persiste para $h \ge 3$, mesmo quando o conjunto possui um complemento infinito "grande". Ao estabelecer a ordem polinomial precisa da função de diferença, os autores mostram que o conjunto $B$ retém a "suavidade" do conjunto completo dos inteiros em termos de crescimento de representação. Além disso, a construção do conjunto $C$ expande o panorama conhecido de tais conjuntos, mostrando que a monotonicidade estrita é compatível com a densidade assintótica 1, estreitando assim a lacuna entre os comportamentos cofinitos e co-infinitos na teoria aditiva dos números.

Os autores concluem propondo problemas abertos relativos à existência de tais conjuntos para densidades prescritas arbitrariamente $d \in [0, 1)$ e para conjuntos com densidades específicas de liminf e limsup, sugerindo que a caracterização completa das condições de monotonicidade para funções de representação continua sendo uma área ativa de pesquisa.