Erdős Problem #763

Erdős Problem #763: bounded error in an additive convolution

Statement and outcome

Can $A\subseteq\mathbb N$ and $c>0$ satisfy \[ S(N):=\sum_{j\leq N}1_A^{*2}(j)=cN+O(1)? \] Here the convolution counts ordered representations, with repetitions allowed. The answer is no. We prove the bounded-error assertion itself; stronger quantitative error estimates require further work and are not claimed. Attempt status: solved.

Generating functions

Suppose instead that $S(N)=cN+E_N$, where $|E_N|\leq M$ for every $N\geq0$, enlarging $M$ to include any initial exceptions. Write \[ F(z)=\sum_{a\in A}z^a,\qquad E(z)=\sum_{N\geq0}E_Nz^N. \] For $|z|<1$, absolute convergence and the cumulative-sum identity give \[ F(z)^2=\frac{cz}{1-z}+(1-z)E(z). \tag{1} \] This is valid whether the convention for $\mathbb N$ includes zero. In particular, for real $s\uparrow1$, \[ F(s)^2=\frac{cs}{1-s}+O(1),\qquad (1-s)^{1/2}F(s)^{2/2}\longrightarrow\sqrt c. \tag{2} \]

Fix a positive integer $m$, and put $H_m(z)=1+z+\cdots+z^{m-1}$. All integrals below are with respect to normalized angular measure $d\theta/(2\pi)$, with $z=re^{i\theta}$ and $0<r<1$. Let \[ J=\int |F(z)H_m(z)|^2,\qquad W=\int|H_m(z)|^2=\sum_{j=0}^{m-1}r^{2j}. \] The coefficient $b_\ell$ of $F H_m$ is a nonnegative integer. Thus $b_\ell^2\geq b_\ell$, and Parseval gives \[ J=\sum_\ell b_\ell^2r^{2\ell} \geq\sum_\ell b_\ell r^{2\ell}=W F(r^2). \tag{3} \]

The left side of the integrated absolute-value version of $1$, after multiplication by $|H_m|^2$, is exactly $J$. Consequently it is at least $W F(r^2)$.

The error gains a square root in the averaging length

Since $|H_m(z)|\leq m$, the main term in $1$ contributes at most \[ cm^2\int\frac{d\theta/(2\pi)}{|1-re^{i\theta}|} =O_c\left(m^2\log\frac{2}{1-r}\right). \tag{5} \] For completeness, $|1-re^{i\theta}|^2=(1-r)^2+4r\sin^2(\theta/2)$; for $r\geq1/2$, integrating separately over $|\theta|\leq1-r$ and its complement proves $5$.

By Cauchy--Schwarz and Parseval, \[ \int |E(z)|\,|(1-z)H_m(z)^2| \leq\left(\frac{M^2}{1-r^2}\right)^{1/2} \left(\int|(1-z)H_m(z)^2|^2\right)^{1/2} \leq\frac{M\sqrt{2m}}{\sqrt{1-r^2}}. \tag{6} \] Indeed, \[ (1-z)H_m(z)^2=(1-z^m)H_m(z) =\sum_{j=0}^{m-1}z^j-\sum_{j=m}^{2m-1}z^j, \] so its squared coefficient norm is $2m$. Combining $1$, the lower estimate, $5$ and $6$ yields \[ W F(r^2)^{2/2} \leq O_c\left(m^2\log\frac{2}{1-r}\right) +\frac{M\sqrt{2m}}{\sqrt{1-r^2}}. \] Multiply by $\sqrt{1-r^2}$ and let $r\uparrow1$, keeping $m$ fixed. Equation $2$, $W\to m$, and the vanishing of the logarithmic term imply \[ m\sqrt c\leq M\sqrt{2m}. \] Choosing an integer $m>2M^2/c$ is a contradiction. Thus no bounded-error example exists.

Attribution and scope

This is an elementary bounded-error specialization of the classical generating-function method underlying P. Erdős and W. H. J. Fuchs, On a problem of additive number theory, J. London Math. Soc. 31 $1956$, 67--73, https://doi.org/10.1112/jlms/s1-31.1.67. Their stronger error theorem is historical context, not an input to the proof above.

Statement checked at https://www.erdosproblems.com/763 on 24 September 2026. No novelty or local Lean verification is claimed.

COMPLETION ESTIMATE

COMPLETION: 100%