No exact on average additive complements of squares

1. Problem Statement and Context

The paper addresses fundamental questions in additive number theory regarding additive complements.

• Definitions:

  • Let $S_r = \{1^r, 2^r, 3^r, \dots\}$ be the set of $r$-th powers ($r \ge 2$).
  • A subset $W \subset \mathbb{N}$ is an additive complement of $S_r$ if every sufficiently large integer $n$ can be written as $n = w + s$ where $w \in W$ and $s \in S_r$.
  • Let $f_r(n)$ denote the number of such representations: $f_r(n) = \#\{(w, m^r) \in W \times S_r : n = w + m^r\}$.
  • Let $W(N) = |W \cap [1, N]|$.

• Historical Background:

  • Erdős (1950s): Established that for squares ($r=2$), $\liminf_{N\to\infty} W(N)/\sqrt{N} \ge 1$. He asked if this limit is strictly greater than 1.
  • Moser & Others: Improved the lower bound to $1.06$, and eventually to $4/\pi$ (by Cilleruelo, Habsieger, and Balasubramanian-Ramana).
  • Ben Green's Problem (2017): Does there exist an additive complement $W$ of squares such that $W(N) \sim \frac{4}{\pi}\sqrt{N}$ (i.e., achieving the theoretical lower bound asymptotically)?
  • Ruzsa's Problem (2001) / Cilleruelo's Conjecture (1993): Does there exist an exact on average additive complement? This means a set $W$ where the average number of representations is exactly 1:
    $$\sum_{n \le N} f_r(n) \sim N \quad \text{as } N \to \infty.$$
  • Previous Results: For $r=2$, Chen and Fang (2017) and Ding et al. (2023) proved that $\sum_{n \le N} f_2(n) - N \gg N^{1/4}\log N$ and later $\gg N^{1/2}$. However, for $r \ge 3$, previous methods failed to even prove that the sum diverges to infinity.

• The Core Question: Can the sum of representations $\sum_{n \le N} f_r(n)$ be arbitrarily close to $N$ (i.e., is the "excess" sum small), or is there a significant lower bound on the deviation $\sum f_r(n) - N$?

2. Methodology

The authors employ a combination of combinatorial counting, Abel summation, and analytic number theory techniques.

A. Proof of Theorem 1 (General $r$-th Powers)

The proof for general $r$ relies on a partitioning argument and the Abel summation formula.

1. Partitioning: The interval $[1, N]$ is divided into $K$ sub-intervals of length $N/2K$. Let $W_k$ and $S_k$ be the intersections of $W$ and $S_r$ with the $k$-th interval.
2. Difference Sets: The authors analyze the number of differences $w - s$ where $w \in W_k$ and $s \in S_k$. They show that the total number of such pairs is large.
3. Collision Argument: If the sum of representations were close to $N$, the number of "collisions" (pairs $(w, s)$ and $(w', s')$ such that $w+s = w'+s'$ with distinct pairs) would be small.
4. Abel Summation: By applying Abel summation to the counts of elements in the intervals, they derive a lower bound on the number of pairs with the same difference.
5. Contradiction: They show that if the sum $\sum f_r(n)$ were too close to $N$, the number of such collisions would be insufficient to account for the density of the sets, leading to a contradiction. This forces the sum to deviate from $N$ by at least $N^{1-1/r}$.

B. Proof of Theorem 2 (Squares, $r=2$)

For the specific case of squares, the authors achieve a stronger result by exploiting the multiplicative structure of squares.

1. Ford's Multiplicative Table Theorem: They utilize a deep result by Ford regarding the number of distinct integers $n \le x$ representable as $n = m_1 m_2$ with $m_i \le \sqrt{x}$. This count involves a specific power of $\log N$ and $\log \log N$.
2. Case Analysis:
   • Case I: If the density of $W$ in the first interval is high, the result follows trivially.
   • Case II: If the density is low in the first interval, the mass must be distributed elsewhere.
3. Arithmetic Features: In the second subcase, they construct a set of differences based on the structure $w_i = n^* - m_i^2$. The differences between these squares involve terms like $(m_i - m)(m_i + m)$.
4. Application of Lemma 1: By mapping these differences to the multiplicative table problem, they show that the number of distinct values generated is limited by the Ford bound. This limitation forces the sum of representations to be significantly larger than $N$, introducing an extra logarithmic factor compared to the general $r$ case.

C. Proof of Theorem 3 (Equivalence of Problems)

The authors prove that Ben Green's Problem (existence of a complement with $W(N) \sim \frac{4}{\pi}\sqrt{N}$) and Ruzsa's Problem (existence of an exact on average complement) are equivalent for squares.

• They show that if an exact on average complement exists, the growth rate of $W(N)$ must be exactly $\frac{4}{\pi}\sqrt{N}$.
• Conversely, if the growth rate is exactly $\frac{4}{\pi}\sqrt{N}$, the average representation sum cannot be $N$ (it must be larger), implying no exact on average complement exists.

3. Key Contributions and Results

Theorem 1: General Lower Bound for $r$-th Powers

For any additive complement $W$ of $r$-th powers ($r \ge 2$):
$$\sum_{n \le N} f_r(n) - N \gg_r N^{1 - 1/r}$$

• Significance: This extends the known bound from $r=2$ to all $r \ge 2$. It proves that for $r \ge 3$, the sum of representations must diverge to infinity, resolving the limitation of previous methods. The implied constant depends on $r$.

Theorem 2: Improved Bound for Squares ($r=2$)

For squares, the lower bound is significantly stronger:
$$\sum_{n \le N} f_2(n) - N \gg N^{1/2} (\log N)^{\delta} (\log \log N)^{3/2}$$
where $\delta = 1 - \frac{1 + \log \log 2}{\log 2} \approx 0.086$.

• Significance: This improves upon the recent result by Ding, Sun, Wang, and Xia (which had a bound of $N^{1/2}$) by adding a polylogarithmic factor. This demonstrates that the arithmetic structure of squares imposes stricter constraints on additive complements than general $r$-th powers.

Theorem 3: Equivalence of Problems

The paper establishes that the existence of an additive complement $W$ of squares satisfying $W(N) \sim \frac{4}{\pi}\sqrt{N}$ is equivalent to the existence of an exact on average additive complement.

• Significance: This unifies two major open problems in the field. Since the authors prove (via Theorem 1 and 2) that the sum of representations always exceeds $N$ by a significant margin, it implies that no exact on average additive complement exists for squares. Consequently, Ben Green's question is answered negatively: one cannot have a complement with the "perfect" asymptotic density $\frac{4}{\pi}\sqrt{N}$ that also yields an average of exactly 1 representation.

4. Significance and Impact

1. Resolution of Cilleruelo's Conjecture (Partial): The paper provides strong evidence supporting Cilleruelo's conjecture that $\sum f_r(n) - N$ grows significantly. Specifically, it proves the conjecture for $r=2$ with a refined bound and for all $r \ge 3$ with a non-trivial lower bound.
2. Negative Answer to Existence Questions: By proving the sum of representations is strictly greater than $N$ (by a factor of $N^{1-1/r}$), the paper implies that exact on average additive complements do not exist for squares (and likely for higher powers). This answers Ruzsa's 2001 problem and Ben Green's 2017 problem in the negative.
3. Methodological Advancement: The successful application of Ford's multiplicative table results to additive complement problems opens a new avenue for research, linking additive and multiplicative number theory more deeply.
4. Optimality: The results suggest that the "best" possible additive complements (those with minimal density) still suffer from a significant "waste" in the number of representations, preventing them from being "exact" on average.

In summary, this paper settles long-standing questions about the density and representation counts of additive complements of powers, proving that perfect efficiency (exact average representation) is mathematically impossible for squares and establishing robust lower bounds for all higher powers.