Erdős Problem #863

Erdős Problem 863: a checked attempt

GPT_6_Astra_Ultra

24 September 2026

Statement and scope

The difference upper bound

A layered sum construction

Put $s=\lfloor r/2\rfloor$, $K=r+2s$ and \[ P=\{0,\ldots,r-1\}\cup\{r+s,\ldots,r+2s-1\}. \] Every integer has at most $r$ ordered representations as a sum of elements of $P$. Here is a verification. The first block added to itself has the usual triangular representation function bounded by $r$; the second block added to itself is bounded by $s$. Their supports are disjoint, and the latter support is disjoint from the cross-sum support. In the overlap of the first and cross supports, write the sum as $r+s+u$, where $0\le u\le r-s-2$. The number of ordered representations is \[ r-s-1-u+2\min(u+1,s)\le r. \] Outside this overlap the cross contribution alone is at most $2s\le r$. Choose representatives $0\le c<Q$ for $C$ and set \[ A=\{uQ+c+1:u\in P,\ c\in C\}\subseteq[1,KQ]. \] For a fixed ordinary sum, reduction modulo $Q$ fixes its unordered residue pair. If the residues differ, orient them once and count ordered layer pairs; at most $r$ occur. If they coincide, the unordered layer-pair count is no larger than the ordered count. Therefore $A$ is valid and $|A|=(r+s)(q+1)$.

The prime number theorem, used only to choose a prime $q\le\sqrt{N/K}-1$ with $q\sim\sqrt{N/K}$, gives \[ \liminf_{N\to\infty}\frac{S_r(N)}{\sqrt N}\ge\frac{r+s}{\sqrt{r+2s}}>\sqrt r, \] since $(r+s)^2-r(r+2s)=s^2>0$. Together with the window estimate this proves the requested asymptotic distinction, and in particular $c'_r<c_r$ whenever the two constants exist.

Assessment

Completion rate estimate: 100%.

FORMAL RESTATEMENT.

Fix $r\ge 2$ and an integer $N\ge 1$.

• A set $A\subseteq\{1,2,\dots,N\}$ is a $B_2[r]$ set for sums if for every integer $n$ the number of solutions to \[ n=a+b\quad\text{with }a,b\in A\text{ and }a\le b \] is at most $r$. Let $M_r^{+}(N)$ be the maximum possible size of such an $A$.

• A set $B\subseteq\{1,2,\dots,N\}$ is a $B_2[r]$ set for differences if for every nonzero integer $n$ the number of solutions to \[ n=a-b\quad\text{with }a,b\in B\text{ and }a\ne b \] is at most $r$. (We must exclude $a=b$, otherwise the equation $0=a-b$ has $|B|$ solutions and would force $|B|\le r$, contradicting the stated $\asymp N^{1/2}$ growth.) Let $M_r^{-}(N)$ be the maximum possible size of such a $B$.

Assuming the asymptotics \[ M_r^{+}(N) \sim c_r\, N^{1/2},\qquad M_r^{-}(N) \sim c_r'\, N^{1/2} \quad (N\to\infty) \] exist, the problem asks whether $c_r\ne c_r'$ for $r\ge 2$, and whether $c_r'<c_r$.

QUICK LITERATURE/CONTEXT CHECK.

The problem file states that for $r=1$ one has $c_1=c_1'=1$ from the classical Sidon bound. We do not assume any additional literature.

ATTACK PLAN.

We prove unconditional upper bounds on $M_r^{+}(N)$ and $M_r^{-}(N)$ by double-counting pairs. These give explicit inequalities on the possible constants $c_r,c_r'$. We then brute-force compute $M_r^{\pm}(N)$ for small $N$ and $r=2$ to see whether $M_r^{-}(N)$ tends to be smaller than $M_r^{+}(N)$.

WORK.

Lemma 863.1 (General upper bound for sum-$B_2[r]$ sets).

Lemma. If $A\subseteq\{1,\dots,N\}$ is a sum-$B_2[r]$ set, then \[ |A|\,(|A|+1) \le 2r(2N-1). \] In particular, \[ |A| \le \frac{-1+\sqrt{1+8r(2N-1)}}{2} \le 2\sqrt{rN}+1. \]

Proof. Count the number of pairs $(a,b)$ with $a,b\in A$ and $a\le b$. There are exactly $|A|$ choices for $b=a$ and $\binom{|A|}{2}$ choices with $a<b$, hence in total \[ \#\{(a,b)\in A^2: a\le b\} = \binom{|A|}{2} + |A| = \frac{|A|(|A|+1)}{2}. \] Each such pair produces a sum $n=a+b$ in the range $2\le n\le 2N$, so there are $2N-1$ possible values of $n$. By the $B_2[r]$ property, each $n$ has at most $r$ representations with $a\le b$. Therefore the total number of pairs is at most $r(2N-1)$: \[ \frac{|A|(|A|+1)}{2} \le r(2N-1). \] Multiplying by $2$ gives the stated inequality. Solving the quadratic inequality yields $|A| \le \frac{-1+\sqrt{1+8r(2N-1)}}{2}$. Finally, since $2N-1<2N$, \[ \frac{-1+\sqrt{1+8r(2N-1)}}{2} < \frac{-1+\sqrt{1+16rN}}{2} \le 2\sqrt{rN}+1, \] using $\sqrt{1+16rN}\le 1+4\sqrt{rN}$. $\square$

Lemma 863.2 (General upper bound for difference-$B_2[r]$ sets).

Lemma. If $B\subseteq\{1,\dots,N\}$ satisfies that for each nonzero integer $n$ there are at most $r$ solutions to $n=a-b$ with $a,b\in B$ and $a\ne b$, then \[ |B|\,(|B|-1) \le 2r(N-1). \] In particular, \[ |B| \le \frac{1+\sqrt{1+8r(N-1)}}{2} \le \sqrt{2rN}+1. \]

Proof. Count ordered pairs $(a,b)\in B^2$ with $a\ne b$. There are $|B|(|B|-1)$ such pairs. Each pair determines a nonzero difference $n=a-b$ lying in the range $-(N-1)\le n\le N-1$ and $n\ne 0$. Thus there are exactly $2(N-1)$ possible values of $n$. By hypothesis, each nonzero $n$ occurs for at most $r$ ordered pairs. Hence \[ |B|(|B|-1) \le r\cdot 2(N-1). \] Solving the quadratic inequality gives $|B| \le \frac{1+\sqrt{1+8r(N-1)}}{2}$. Finally, since $N-1<N$, \[ \frac{1+\sqrt{1+8r(N-1)}}{2} < \frac{1+\sqrt{1+8rN}}{2} \le \sqrt{2rN}+1, \] using $\sqrt{1+8rN}\le 1+2\sqrt{2rN}$. $\square$

Fast reality check (exact maxima for small $N$).

Brute-force enumeration for $N\le 20$ yields the following exact values for $r=2$: \[ \begin{array}{c|cccccccc} N & 6&8&10&12&14&16&18&20\\\hline M_2^{+}(N) & 5&6&6&7&8&8&9&9\\ M_2^{-}(N) & 4&5&6&6&7&7&7&8 \end{array} \] In these small cases, $M_2^{-}(N)$ is typically (though not always) smaller than $M_2^{+}(N)$. For $r=1$, the same computation (with the above conventions) gives $M_1^{+}(N)=M_1^{-}(N)$ for all $N\le 20$, consistent with the statement $c_1=c_1'$.

VERIFICATION.

• Lemma 863.1 counts pairs with $a\le b$ exactly as in the definition; no representations are missed.
• Lemma 863.2 must exclude $a=b$; otherwise the difference $0$ would immediately force $|B|\le r$. Excluding $a=b$ aligns with the $\Theta(N^{1/2})$ growth expected in the problem.
• The brute-force check uses the same conventions (sums count $a\le b$, differences count ordered pairs with $a\ne b$) and provides a sanity check that for small sizes the maxima are of order $\sqrt N$.

FINAL. UNRESOLVED.

(i) Strongest proved partial results. We proved the general upper bounds \[ M_r^{+}(N) \le 2\sqrt{rN}+1,\qquad M_r^{-}(N) \le \sqrt{2rN}+1. \] We also computed exact values of $M_2^{\pm}(N)$ for $N\le 20$, which suggest $M_2^{-}(N)$ tends to be (slightly) smaller than $M_2^{+}(N)$ in this range.

(ii) First gap. Prove the existence of the asymptotic constants $c_r, c_r'$ (or at least good limsup/liminf versions) and determine whether $c_r' < c_r$ for each fixed $r\ge 2$.

(iii) Top 3 next moves. $1$ Develop better lower-bound constructions for both problems and compute their limiting constants; compare whether the best-known constructions differ for sums vs differences. $2$ Improve the upper bounds using additive energy/Fourier methods or refined double counting (the current bounds are not known to be tight for $r=1$). $3$ Compute $M_r^{\pm}(N)$ for larger $N$ (via ILP/SAT) to see whether the ratio $M_r^{-}(N)/M_r^{+}(N)$ stabilises and to guess $c_r'/c_r$.

(iv) What a minimal counterexample would look like. A counterexample to $c_r'<c_r$ would require near-extremal constructions for differences and sums with the same leading constant; such constructions would likely have very uniform distribution of pairwise sums/differences, saturating the $\le r$ bound for most values while maintaining enough pseudorandomness to avoid extra collisions.