Erdős Problem #1193

Erdős Problem 1193: the literal statement has a counterexample

1. Statement and outcome

For $A\subset\mathbb N$, write $r_A(n)=(1_A*1_A)(n)$, counting ordered representations $n=a+b$ with $a,b\in A$. Given an everywhere positive non-decreasing function $g$, must $\{n:r_A(n)=g(n)\}$ have lower density zero, or upper density bounded by an absolute constant less than one? Both conclusions are false for the recorded statement. The counterexample below also allows $A$ to be a proper subset of $\mathbb N$.

2. A cofinite counterexample

Fix an integer $h\ge2$ and take \[ A=\{h,h+1,h+2,\ldots\},\qquad g(n)=\max\{1,n-2h+1\}. \] The definition works whether the convention for $\mathbb N$ includes zero or starts at one. The function $g$ is positive and non-decreasing. If $n<2h$, there are no representations, whereas for $n\ge2h$ the first summand can be any integer in $[h,n-h]$. The second summand is then uniquely determined and also belongs to $A$. Hence \[ r_A(n)=\max\{0,n-2h+1\},\qquad \{n:r_A(n)=g(n)\}=\{n:n\ge2h\}. \] In particular, for integer $N\ge2h$, the number of positive integers at most $N$ in the equality set is $N-2h+1$. Dividing by $N$ and taking the limit gives density one. Thus the lower density need not vanish, and no proposed universal upper bound $c<1$ can hold.

3. Assessment and attribution

This resolves exactly the stated universal assertions. Requiring $A$ to be proper, infinite, or cofinite does not repair them, since the same example meets all three conditions. Conditions such as sparsity or a prescribed slower growth for $g$ would define different questions and are not silently imposed here. The elementary $A=\mathbb N$ counterexample is already recorded on the problem page; the cofinite version above explains why a proper-subset convention does not avoid it. This is a reconstruction of the known resolution, with no novelty or local formal-verification claim. Source: https://www.erdosproblems.com/1193.

Completion rate estimate: 100%.