On the Monotonicity of Higher-Fold Representation Functions

Technical Summary: On the Monotonicity of Higher-Fold Representation Functions

Problem Statement
The paper investigates the monotonicity properties of the ordered $h$-fold representation function $R_{A,h}(n)$, defined as the number of ordered solutions to $n = a_1 + \dots + a_h$ with $a_i \in A$, where $A \subseteq \mathbb{N}$. The central question concerns whether $R_{A,h}(n)$ can be strictly increasing for a set $A$ whose complement $\mathbb{N} \setminus A$ is infinite (a co-infinite set).

Historically, Erdős, Sárközy, and Sós proved that for $h=2$, strict monotonicity implies $A$ is cofinite (i.e., the complement is finite). For $h \ge 3$, Dombi conjectured that if $\mathbb{N} \setminus A$ is infinite, $R_{A,h}(n)$ cannot be eventually strictly increasing. This conjecture was disproven by Shallit, who used automata theory to construct a co-infinite set $A$ where $R_{A,3}(n)$ is strictly increasing. Specifically, Shallit utilized the set $B = \{0\} \cup \{m \ge 1 : \text{the base-4 expansion of } m \text{ begins with 1 or 2}\}$. While Shallit established strict monotonicity for $R_{B,h}(n)$ for fixed $h \ge 3$, the precise growth rate of the difference $R_{B,h}(n+1) - R_{B,h}(n)$ remained an open quantitative question. Furthermore, Dombi posed a problem regarding the existence of such sets with asymptotic density $\alpha \neq 1/2$ (or specifically $\alpha \neq 1$).

Methodology
The authors employ a combination of generating functions, recurrence relations derived from the self-similar structure of the set $B$, and convolution arguments to establish bounds on the difference function $\Delta_h(n) = R_{B,h}(n+1) - R_{B,h}(n)$.

1. Recurrence Analysis for Set $B$:
   The set $B$ is defined by its indicator sequence $c_n$, which satisfies a functional equation in the generating function $C(x) = \sum c_n x^n$:
   $$C(x) = (1+x+x^2+x^3)C(x^4) - x^3$$
   By squaring and cubing this equation, the authors derive recurrence relations for the differences of the two-fold ($\beta_n$) and three-fold ($\alpha_n$) representation functions.

   • Lemma 2.1 & 2.2: These lemmas establish recursive formulas for $\beta_n$ and $\alpha_n$ based on values at indices $n/4$.
   • Bounds on $\beta_n$: Lemma 3.1 proves that the difference for the two-fold function is bounded: $-1 \le \beta_n \le 2$.
   • Bounds on $\alpha_n$: Using the bounds on $\beta_n$ and the recurrence relations, Lemma 3.2 establishes a linear lower bound $\alpha_n \ge n/5 + 4$ for $n \ge 78$, while Lemma 3.3 provides a linear upper bound $\alpha_n \le 3n + 2$.

2. Convolution Lift:
   To extend results from $h=3$ to arbitrary $h \ge 3$, the authors utilize the convolution identity:
   $$R_{p+q}(n) = \sum_{u=0}^n R_p(n-u)R_q(u)$$
   This leads to a relation for the differences:
   $$\Delta_{p+q}(n) = \sum_{u=0}^n \Delta_p(n-u)R_q(u) + R_p(0)R_q(n+1)$$
   By setting $p=3$ and $q=h-3$, the behavior of $\Delta_h(n)$ is controlled by the known behavior of $\Delta_3(n)$ (i.e., $\alpha_n$) and the growth of $R_{h-3}(n)$.

3. Construction of Set $C$:
   To address Dombi's problem regarding asymptotic density, the authors construct a set $C = \mathbb{N} \setminus \{2^j : j \ge 10\}$. They analyze the generating function $G_C(x) = (1-x)^{-1} - D(x)$, where $D(x)$ corresponds to the removed powers of 2. The sparsity of the removed set allows for an explicit estimation of the difference $R_{C,h}(n+1) - R_{C,h}(n)$.

Key Contributions and Results

1. Polynomial Order of Growth (Theorem 1.1):
   The paper proves that for the set $B$, the difference $R_{B,h}(n+1) - R_{B,h}(n)$ grows polynomially with order $n^{h-2}$. Specifically, for every integer $h \ge 3$, there exist constants $c_h, C_h > 0$ such that for all $n \ge 1$:
   $$c_h n^{h-2} \le R_{B,h}(n+1) - R_{B,h}(n) \le C_h n^{h-2}$$
   This result confirms that despite $B$ having an infinite complement with large gaps, its representation function behaves asymptotically like the full set $\mathbb{N}$ (where the difference is $\binom{n+h-1}{h-2} \asymp n^{h-2}$).

2. Strict Monotonicity for Arbitrary $h \ge 3$:
   The authors rigorously prove that $R_{B,h}(n+1) > R_{B,h}(n)$ for all $n \ge 0$ and all $h \ge 3$, improving upon Shallit's result which focused on the existence of such sets without quantifying the growth rate for all $h$.

3. Resolution of Dombi's Density Problem (Theorem 1.2):
   The paper constructs a co-infinite set $C = \mathbb{N} \setminus \{2^j : j \ge 10\}$ such that:

   • The asymptotic density exists and equals 1: $\lim_{n \to \infty} C(n)/n = 1$.
   • The representation function $R_{C,h}(n)$ is strictly increasing for every integer $h \ge 3$.
     This answers Dombi's problem by providing a set with density 1 (distinct from the density 1/2 examples previously known) that maintains strict monotonicity.

Significance
The paper refines the understanding of additive representation functions in co-infinite sets. It demonstrates that the obstruction to monotonicity found in the $h=2$ case does not persist for $h \ge 3$, even when the set has a "large" infinite complement. By establishing the precise polynomial order of the difference function, the authors show that the set $B$ retains the "smoothness" of the full set of integers in terms of representation growth. Furthermore, the construction of set $C$ expands the known landscape of such sets, showing that strict monotonicity is compatible with asymptotic density 1, thereby narrowing the gap between cofinite and co-infinite behaviors in additive number theory.

The authors conclude by posing open problems regarding the existence of such sets for arbitrary prescribed densities $d \in [0, 1)$ and for sets with specific liminf and limsup densities, suggesting that the full characterization of monotonicity conditions for representation functions remains an active area of research.