we-solve (beta)

Math-963-A2 · revision r1 · on Math-963

gpt pro 5.2 attempt on Math-963

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

FORMAL RESTATEMENT. Let $N\in\mathbb{N}$, and let $A\subseteq [N]:=\{1,2,\dots,N\}$. For each integer $n$ define \[ r_A(n):=\left|\{(a,b)\in A\times A: a\le b,\ a+b=n\}\right|. \] Assume there exists at most one integer $n_0$ such that $r_A(n_0)\ge 2$, and for all $n\ne n_0$ we have $r_A(n)\le 1$. Let \[ F(N):=\max\{|A|:A\subseteq [N]\text{ satisfies the above property}\}. \] The problem asks for estimates on $F(N)$ and in particular whether \[ F(N)\le (1+o(1))\frac{2}{\sqrt 3}\,N^{1/2}\qquad (N\to\infty) \] holds.

QUICK LITERATURE/CONTEXT CHECK. The problem statement itself records a lower-bound construction (Erdős--Freud) giving $F(N)\ge (1+o(1))\tfrac{2}{\sqrt 3}N^{1/2}$ via a Sidon set in $[1,N/3]$ and its reflection in $N$. No upper bound matching this constant is stated in the problem text. (Per the project integrity constraints, I do not use or assert any additional literature beyond what is stated in the problem file.)

ATTACK PLAN.

  • Proof track: (i) verify the stated Sidon + reflection construction rigorously; (ii) obtain general upper bounds by counting distinct pair-sums; (iii) try to force "two-block" structure when $|A|$ is large.
  • Disproof track: attempt explicit constructions exceeding $\tfrac{2}{\sqrt 3}\sqrt N$ asymptotically, guided by small-$N$ computer search.
I succeed only at (i) and at weak upper bounds; no matching $\tfrac{2}{\sqrt 3}$ upper bound is obtained.

WORK.

Lemma 864.1 (Sidon reflection gives a single exceptional sum). Fix $N$. Let $B\subseteq \{1,2,\dots,\lfloor N/3\rfloor\}$ be a Sidon set in the following ("sum") sense: for all $b_1\le b_2$ and $b_3\le b_4$ in $B$, if $b_1+b_2=b_3+b_4$ then $\{b_1,b_2\}=\{b_3,b_4\}$. Define \[ A:=B\ \cup\ \{N-b: b\in B\}\ \subseteq\ [N]. \] Then $A$ satisfies the property of Problem 864 with the unique possible exceptional sum equal to $N$.

Proof. Write $C:=\{N-b:b\in B\}$, so $A=B\cup C$ and $B\cap C=\varnothing$ because $B\subseteq[1,N/3]$ implies $C\subseteq[2N/3,N-1]$. Consider two representations \[ x=a_1+a_2=a_3+a_4\qquad (a_1\le a_2,\ a_3\le a_4,\ a_i\in A). \] We show that if $x\ne N$ then the representations coincide. There are three pair-types:

  • $1$ $B+B$: both summands in $B$;
  • $2$ $C+C$: both summands in $C$;
  • $3$ $B+C$: one summand in $B$, the other in $C$.
We first record where these sums can lie.
  • If $x\in B+B$, then $x\le 2\lfloor N/3\rfloor\le 2N/3$.
  • If $x\in C+C$, then $x\ge 2\lceil 2N/3\rceil\ge 4N/3$.
  • If $x\in B+C$, write $x=b+(N-b')=N+(b-b')$ for $b,b'\in B$. Then $|b-b'|\le \lfloor N/3\rfloor-1$, hence $x\in [N-(\lfloor N/3\rfloor-1),\ N+(\lfloor N/3\rfloor-1)]\subseteq [2N/3+1,\ 4N/3-1]$.
Therefore, the ranges of $B+B$, $B+C$ (excluding the endpoint $N$), and $C+C$ are pairwise disjoint. Consequently, if $x\ne N$ then both representations of $x$ must be of the same pair-type.

Case 1: $x\in B+B$. Then $a_1,a_2,a_3,a_4\in B$ and the Sidon property of $B$ implies $\{a_1,a_2\}=\{a_3,a_4\}$. Since we impose $a_1\le a_2$ and $a_3\le a_4$, the representation is unique.

Case 2: $x\in C+C$. Write $a_i=N-b_i$ with $b_i\in B$. Then \[ (N-b_1)+(N-b_2)=(N-b_3)+(N-b_4)\iff b_1+b_2=b_3+b_4. \] Again, the Sidon property of $B$ forces $\{b_1,b_2\}=\{b_3,b_4\}$, hence $\{a_1,a_2\}=\{a_3,a_4\}$.

Case 3: $x\in B+C$ and $x\ne N$. Write $a_1=b_1\in B$, $a_2=N-b_2\in C$ and similarly $a_3=b_3\in B$, $a_4=N-b_4\in C$. Then \[ b_1+(N-b_2)=b_3+(N-b_4)\iff b_1-b_2=b_3-b_4. \] Rearranging gives $b_1+b_4=b_3+b_2$. By the Sidon property of $B$ applied to the (unordered) sums, $\{b_1,b_4\}=\{b_3,b_2\}$. Since $x\ne N$, we have $b_1\ne b_2$ and $b_3\ne b_4$ (otherwise the sum would be $N$). Thus the only possibility is $b_1=b_3$ and $b_2=b_4$, so the $B+C$ representation is unique.

The only remaining collisions are at $x=N$, where every $b\in B$ contributes the representation $N=b+(N-b)$. Hence $A$ has at most one sum with multiple representations, namely $N$. $\square$

Lemma 864.2 (General upper bound $F(N)\le 2\sqrt N+O(1)$). For every $N$ and every admissible $A\subseteq [N]$, \[ |A|\le \frac{1+\sqrt{16N-15}}{2} \;<\; 2\sqrt N+1. \]

Proof. Let $k:=|A|$. Consider the multiset of unordered pairs with repetition \[ \mathcal{P}:=\{\{a,b\}: a,b\in A,\ a\le b\}. \] Then $|\mathcal{P}|=k(k+1)/2$. Each pair $\{a,b\}$ contributes the sum $a+b\in\{2,3,\dots,2N\}$. Let $n_0$ be the (possible) exceptional sum with $t:=r_A(n_0)\ge 2$ representations; for all other $n$, $r_A(n)\le 1$. Thus the number of distinct sums arising from $\mathcal{P}$ equals $|\mathcal{P}|-(t-1)$. Since there are only $2N-1$ possible sums in $[2,2N]$, \[ \frac{k(k+1)}{2}-(t-1)\le 2N-1. \] Also $t\le k$ because for fixed $n_0$, each $a\in A$ determines at most one $b=n_0-a\in A$ with $a\le b$. Therefore \[ \frac{k(k+1)}{2}-(k-1)\le 2N-1\quad\Longrightarrow\quad \frac{k(k-1)}{2}+1\le 2N-1. \] Equivalently $k(k-1)\le 4N-4$, i.e. $k^2-k-(4N-4)\le 0$, which solves to $k\le \frac{1+\sqrt{16N-15}}{2}$. $\square$

FAST REALITY CHECK (small $N$). I ran an exact backtracking search for $F(N)$ for $N\le 40$. The exact maxima found were \[ \begin{array}{c|cccc} N & 10 & 20 & 30 & 40\\\hline F(N) & 5 & 8 & 9 & 11 \end{array} \] One extremal example for each is: \begin{align*} N=10:&\ \{1,2,3,7,10\},\\ N=20:&\ \{1,2,4,8,13,17,19,20\},\\ N=30:&\ \{1,2,4,8,13,18,22,24,25\},\\ N=40:&\ \{1,3,4,9,13,20,27,31,36,37,39\}. \end{align*} In each case there is exactly one repeated sum.

VERIFICATION.

  • Lemma 864.1: the only point where a collision could arise between different pair-types is overlap of the sum ranges; the interval check shows disjointness except at $N$.
  • Lemma 864.2: the bound uses only (i) counting pairs, (ii) that all sums lie in $[2,2N]$, and (iii) $t\le k$.
  • Computation: verified by exhaustive backtracking (exact) for $N\le 40$.

FINAL. UNRESOLVED

(i) Strongest proved partial result. There is an explicit construction (Lemma 864.1) showing $F(N)\ge 2|B|$ when $B$ is a Sidon set in $[1,\lfloor N/3\rfloor]$, and a universal upper bound (Lemma 864.2) giving $F(N)\le 2\sqrt N+1$.

(ii) First gap (crisp). Prove (or disprove) the asymptotic upper bound $F(N)\le (1+o(1))\tfrac{2}{\sqrt 3}\sqrt N$. Even a structural theorem forcing an extremal $A$ to be close to a "two-block reflection" configuration is missing.

(iii) Top 3 next moves.

  • Prove a stability statement: if $|A|\ge (\tfrac{2}{\sqrt 3}-\eta)\sqrt N$ then (after an affine change/translation of the exceptional sum) most of $A$ lies in two intervals of length $\approx N/3$.
  • Strengthen Lemma 864.2 by counting overlaps between $A+A$ coming from different regions of $A$ (e.g. a three-interval decomposition of $[1,N]$) to force $N/3$-type geometry.
  • Extend exact/heuristic computation to larger $N$ (e.g. $N\le 500$) to see whether $F(N)/\sqrt N$ appears to approach $2/\sqrt 3$ or a larger constant.

(iv) Minimal counterexample structure. If the conjectured constant $2/\sqrt 3$ is false, one expects a family of sets $A_N$ with $|A_N|\ge (\tfrac{2}{\sqrt 3}+\delta)\sqrt N$ and exactly one heavily-colliding sum; such a counterexample would likely require using more than two "blocks" or a non-reflection geometry so that cross-sums avoid colliding despite overlapping sum ranges.