On the Monotonicity of Higher-Fold Representation Functions

Resumen Técnico: Sobre la monotonicidad de las funciones de representación de orden superior

Planteamiento del problema
El artículo investiga las propiedades de monotonicidad de la función de representación de orden $h$ ordenada $R_{A,h}(n)$, definida como el número de soluciones ordenadas a $n = a_1 + \dots + a_h$ con $a_i \in A$, donde $A \subseteq \mathbb{N}$. La cuestión central es si $R_{A,h}(n)$ puede ser estrictamente creciente para un conjunto $A$ cuyo complemento $\mathbb{N} \setminus A$ es infinito (un conjunto co-infinito).

Históricamente, Erdős, Sárközy y Sós demostraron que para $h=2$, la monotonicidad estricta implica que $A$ es cofinito (es decir, que su complemento es finito). Para $h \ge 3$, Dombi conjeturó que si $\mathbb{N} \setminus A$ es infinito, $R_{A,h}(n)$ no puede ser eventualmente estrictamente creciente. Esta conjetura fue refutada por Shallit, quien utilizó la teoría de autómatas para construir un conjunto co-infinito $A$ donde $R_{A,3}(n)$ es estrictamente creciente. Específicamente, Shallit utilizó el conjunto $B = \{0\} \cup \{m \ge 1 : \text{la expansión en base 4 de } m \text{ comienza con 1 o 2}\}$. Si bien Shallit estableció la monotonicidad estricta para $R_{B,h}(n)$ para un $h \ge 3$ fijo, la tasa de crecimiento precisa de la diferencia $R_{B,h}(n+1) - R_{B,h}(n)$ seguía siendo una cuestión cuantitativa abierta. Además, Dombi planteó un problema sobre la existencia de tales conjuntos con densidad asintótica $\alpha \neq 1/2$ (o específicamente $\alpha \neq 1$).

Metodología
Los autores emplean una combinación de funciones generatrices, relaciones de recurrencia derivadas de la estructura autosimilar del conjunto $B$ y argumentos de convolución para establecer cotas en la función de diferencia $\Delta_h(n) = R_{B,h}(n+1) - R_{B,h}(n)$.

1. Análisis de recurrencia para el conjunto $B$:
   El conjunto $B$ está definido por su secuencia indicadora $c_n$, la cual satisface una ecuación funcional en la función generatriz $C(x) = \sum c_n x^n$:
   $$C(x) = (1+x+x^2+x^3)C(x^4) - x^3$$
   Al elevar al cuadrado y al cubo esta ecuación, los autores derivan relaciones de recurrencia para las diferencias de las funciones de representación de dos pliegues ($\beta_n$) y tres pliegues ($\alpha_n$).

• Lema 2.1 y 2.2: Estos lemas establecen fórmulas recursivas para $\beta_n$ y $\alpha_n$ basadas en valores en índices $n/4$.
• Cotas en $\beta_n$: El Lema 3.1 demuestra que la diferencia para la función de dos pliegues está acotada: $-1 \le \beta_n \le 2$.
• Cotas en $\alpha_n$: Utilizando las cotas en $\beta_n$ y las relaciones de recurrencia, el Lema 3.2 establece una cota inferior lineal $\alpha_n \ge n/5 + 4$ para $n \ge 78$, mientras que el Lema 3.3 proporciona una cota superior lineal $\alpha_n \le 3n + 2$.

2. Elevación por convolución (Convolution Lift):
   Para extender los resultados de $h=3$ a un $h \ge 3$ arbitrario, los autores utilizan la identidad de convolución:
   $$R_{p+q}(n) = \sum_{u=0}^n R_p(n-u)R_q(u)$$
   Esto conduce a una relación para las diferencias:
   $$\Delta_{p+q}(n) = \sum_{u=0}^n \Delta_p(n-u)R_q(u) + R_p(0)R_q(n+1)$$
   Al establecer $p=3$ y $q=h-3$, el comportamiento de $\Delta_h(n)$ es controlado por el comportamiento conocido de $\Delta_3(n)$ (es decir, $\alpha_n$) y el crecimiento de $R_{h-3}(n)$.

3. Construcción del conjunto $C$:
   Para abordar el problema de la densidad de Dombi, los autores construyen un conjunto $C = \mathbb{N} \setminus \{2^j : j \ge 10\}$. Analizan la función generatriz $G_C(x) = (1-x)^{-1} - D(x)$, donde $D(x)$ corresponde a las potencias de 2 eliminadas. La escasez del conjunto eliminado permite una estimación explícita de la diferencia $R_{C,h}(n+1) - R_{C,h}(n)$.

Contribuciones clave y resultados

1. Orden de crecimiento polinomial (Teorema 1.1):
   El artículo demuestra que para el conjunto $B$, la diferencia $R_{B,h}(n+1) - R_{B,h}(n)$ crece polinomialmente con orden $n^{h-2}$. Específicamente, para cada entero $h \ge 3$, existen constantes $c_h, C_h > 0$ tales 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, a pesar de que $B$ tiene un complemento infinito con grandes brechas, su función de representación se comporta asintóticamente como la del conjunto completo $\mathbb{N}$ (donde la diferencia es $\binom{n+h-1}{h-2} \asymp n^{h-2}$).

2. Monotonicidad estricta para un $h \ge 3$ arbitrario:
   Los autores prueban rigurosamente que $R_{B,h}(n+1) > R_{B,h}(n)$ para todo $n \ge 0$ y todo $h \ge 3$, mejorando el resultado de Shallit, el cual se centraba en la existencia de tales conjuntos sin cuantificar la tasa de crecimiento para todo $h$.

3. Resolución del problema de densidad de Dombi (Teorema 1.2):
   El artículo construye un conjunto co-infinito $C = \mathbb{N} \setminus \{2^j : j \ge 10\}$ tal que:

• La densidad asintótica existe y es igual a 1: $\lim_{n \to \infty} C(n)/n = 1$.
• La función de representación $R_{C,h}(n)$ es estrictamente creciente para cada entero $h \ge 3$.
  Esto responde al problema de Dombi al proporcionar un conjunto con densidad 1 (distinto de los ejemplos de densidad 1/2 conocidos anteriormente) que mantiene la monotonicidad estricta.

Significado
El artículo refina la comprensión de las funciones de representación aditiva en conjuntos co-infinitos. Demuestra que la obstrucción a la monotonicidad encontrada en el caso $h=2$ no persiste para $h \ge 3$, incluso cuando el conjunto tiene un complemento infinito "grande". Al establecer el orden de crecimiento polinomial preciso de la función de diferencia, los autores muestran que el conjunto $B$ retiene la "suavidad" del conjunto completo de los enteros en términos de crecimiento de la representación. Además, la construcción del conjunto $C$ expande el panorama conocido de tales conjuntos, mostrando que la monotonicidad estricta es compatible con la densidad asintótica 1, reduciendo así la brecha entre los comportamientos cofinitos y co-infinitos en la teoría de números aditiva.

Los autores concluyen planteando problemas abiertos respecto a la existencia de tales conjuntos para densidades arbitrarias prescritas $d \in [0, 1)$ y para conjuntos con densidades específicas de liminf y limsup, sugiriendo que la caracterización completa de las condiciones de monotonicidad para las funciones de representación sigue siendo un área de investigación activa.