Erdős #43 — Sidon-pair size bound (disproved)

Statement

Let $A,B\subset\{1,\ldots,N\}$ be two Sidon sets (all pairwise sums $a+b$, $a\le b$, distinct within each set) such that $(A-A)\cap(B-B)=\{0\}$ (their nonzero difference sets are disjoint). Writing $f(N)$ for the maximum possible size of a single Sidon set in $\{1,\ldots,N\}$:

1. First question ($100). Is it true that $\binom{|A|}{2}+\binom{|B|}{2}\le\binom{f(N)}{2}+O(1)$? 2. Second question (equal-size refinement). If $|A|=|B|$, can this be improved to $\binom{|A|}{2}+\binom{|B|}{2}\le(1-c+o(1))\binom{f(N)}{2}$ for some constant $c>0$?

(erdosproblems.com/43, statement verbatim; origin [Er82f, p.114], [Er95, p.5].)

Facts

- Prize \$100 (first question only); status DISPROVED — erdosproblems.com's banner: "This has been solved in the negative" (erdosproblems.com/43, fetched 2026-07-02). - Falsifiable: yes, by construction — both questions ask for a universal bound over all $N$/all valid $(A,B)$, so a single infinite family (or, as it turned out, even single small finite instances) of counterexamples settles them negatively. - Erdős himself noted the *asymptotic* inequality $\binom{|A|}{2}+\binom{|B|}{2}\le(1+o(1))\frac{N}{2}\sim\binom{f(N)}{2}$ already holds (since $f(N)\sim N^{1/2}$, Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets), and in [Er82f] flagged that the sharp $+O(1)$ error term "perhaps... is too optimistic" — i.e. Erdős himself suspected the strong form might be false (erdosproblems.com/43). - Both questions are now fully resolved, both negatively, via two independent routes: - Question 1: a negative answer follows directly from the resolution of the sibling problem erdos/42 — that construction shows one can take $|A|=f(N)$ (a maximum Sidon set) together with an accompanying Sidon $B$, disjoint-difference from $A$, with $|B|\to\infty$ as $N\to\infty$, which breaks the $+O(1)$ bound (erdosproblems.com/43, remarks; erdosproblems.com/42). - Question 2: Kevin Barreto gave an explicit infinite family of counterexamples using a Bose–Chowla mod-$(q^2-1)$ Sidon set split by parity (forum thread, posted 03 Dec 2025, refined with a full proof 19 Dec 2025); independently verified computationally by BrittB (Zenodo DOI 10.5281/zenodo.18227962, posted 20 Jan 2026, confirms a counterexample at $N=35$ with $\binom{|A|}2+\binom{|B|}2=30>21$). - Terence Tao supplied the matching unconditional upper bound $|A|=|B|\le\frac1{\sqrt2}\sqrt N+O(1)$ (i.e. $c=0$ is the best possible constant, matching Barreto's negative answer exactly) via a Cauchy–Schwarz / convolution argument (forum thread, posted 03 Dec 2025); this pins the true constant precisely, closing the problem. - Small explicit counterexamples were found even before the asymptotic construction: BorisAlexeev/Pietro Monticone (running Harmonic's Aristotle system in "informal mode") found $A=\{1,2,10,22,24\}$, $B=\{3,8,14,18,21\}$ at $N=24$, verified in Lean, with $\binom{|A|}2+\binom{|B|}2=20>\binom{f(24)}2=15$ (forum thread, posted 04 Dec 2025); an even smaller hand example is $N=8$, $A=\{1,2,5\}$, $B=\{1,3,8\}$ (Kevin Barreto, forum thread). - Formalized in Lean 4: the Erdős–Turán upper bound on maximum Sidon-set size and the Bose–Chowla construction were both formalized by Harmonic's Aristotle system (Kevin Barreto, forum thread, comment "Now formalised in Lean 4"); erdosproblems.com marks #43 "Formalised statement? Yes". - Related problems: Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — sharp $N^{1/2}$ Sidon-set asymptotics, supplies $f(N)\sim\sqrt N$ used throughout; erdos/42 (forward reference, not yet a local page) — "does every Sidon set $A\subset\{1,\ldots,N\}$ admit a disjoint-difference companion Sidon set $B$ of any prescribed size $M$?", solved (status "SOLVED (LEAN)"), proved for all $M$ by GPT-5.5 Pro (prompted by Harjas Sandhu) after Daniil Sedov (using ChatGPT/Codex) handled $M=1,2,3$; its construction is the direct engine behind #43's first-question disproof (erdosproblems.com/42).

Solution

Answer: both questions are FALSE. No universal bound of either form holds; Erdős's own suspicion that the sharp $+O(1)$ form was "too optimistic" is vindicated, and even the weaker constant-factor form ($c>0$) fails — Tao's matching upper bound shows the true threshold constant is exactly $c=0$.

**The transferable idea — split a single near-optimal additive-combinatorial object into complementary residue classes to get *two* simultaneously-extremal, difference-disjoint objects, for free.**

1. Start from one classical near-optimal Sidon set, not two. The whole difficulty of the problem looks like "build two large Sidon sets with no shared nonzero difference" — a search over pairs. Barreto's construction instead starts from a *single* classical extremal object: the Bose–Chowla Sidon set — for any odd prime power $q$, a set $S\subset\{1,\ldots,q^2-2\}$ of size $q$ that is Sidon *modulo* $M:=q^2-1$ (a strictly stronger, group-theoretic Sidon property; a set Sidon mod $M$ is automatically Sidon in $\mathbb{Z}$).

2. Partition the one object by a group-compatible invariant (parity), not by search. Split $S$ into $S_{\text{even}}=S\cap2\mathbb Z$ and $S_{\text{odd}}=S\cap(2\mathbb Z+1)$, of sizes $a,b$ with $a+b=q$. Because $M=q^2-1$ is even, every difference *within* $S_{\text{even}}$ (or within $S_{\text{odd}}$) is itself an even residue mod $M$, while a difference *between* an even and an odd element of $S$ is odd. This means the two "directed-difference" multisets from $S_{\text{even}}$ and from $S_{\text{odd}}$ are automatically disjoint from each other (they don't even need to be checked — parity forces it) *and* automatically Sidon (they're subsets of the single Sidon-mod-$M$ set $S$, so the ambient Sidon-uniqueness Lemma 1 transfers to each piece individually). Rescaling ($x\mapsto x/2$ or $(x-1)/2$) folds both pieces into the same interval $\{1,\ldots,N\}$, $N=M/2$, producing $A$ (from $S_{\text{even}}$) and $B$ (from $S_{\text{odd}}$) with $(A-A)\cap(B-B)=\{0\}$ *by construction*, no extra combinatorial argument required.

3. A counting/pigeonhole bound then forces both halves to be near-equal, near-maximal, simultaneously. Because all directed differences of $S_{\text{even}}$ and $S_{\text{odd}}$ land in the $N-1$ nonzero even residues mod $M$ and are pairwise distinct across *and* within both pieces, $a(a-1)+b(b-1)\le N-1$. Algebra converts this into $(a-b)^2\le2q-3$, i.e. $a,b=q/2-O(\sqrt q)$ — the split is forced to be almost perfectly balanced. Taking $m=\min(a,b)=q/2-O(\sqrt q)$ and truncating both pieces to size $m$ gives $|A|=|B|=m$ with $\binom{|A|}2+\binom{|B|}2=m(m-1)=q^2/4+O(q^{3/2})=(1/2+o(1))N$ — which, since $\binom{f(N)}2=(1/2+o(1))N$ too, gives $\binom{|A|}2+\binom{|B|}2\ge(1-o(1))\binom{f(N)}2$: the pair simultaneously nearly saturates the single-Sidon-set extremal bound *twice over*, refuting any $c>0$ gap.

4. Why this beats "search for two good sets." The naive approach treats "find $A$ and find $B$ with disjoint differences" as two coupled extremal problems needing a joint construction. The parity-split trick instead reduces it to one already-solved extremal problem (Bose–Chowla) plus a free algebraic partition of its output — the disjointness and the Sidon property of each half are inherited automatically from the ambient object's own uniqueness property (Lemma 1: in a Sidon set/group, $s_1-s_2=s_3-s_4\Rightarrow\{s_1,s_2\}=\{s_3,s_4\}$), rather than engineered by search. This is the reusable move: when asked for $k$ simultaneously-extremal, mutually "orthogonal" combinatorial objects, look for a single ambient extremal object plus a group-compatible partition (parity, residue class, coset) under which orthogonality is a free consequence of the ambient object's own extremal/uniqueness property, instead of attacking the $k$-fold coupled problem directly.

5. The matching upper bound (Tao) closes the gap with a routine but sharp Fourier/convolution estimate. From $(A-A)\cap(B-B)=\{0\}$ one gets the pointwise bound $1_A*1_{-A}(n)+1_B*1_{-B}(n)\le(|A|^2+|B|^2)1_{n=0}+1$; convolving against $1_{[1,H]}*1_{-[1,H]}$ and applying Cauchy–Schwarz with $H\asymp\sqrt N$ yields $|A|^2+|B|^2\le N+O(\sqrt N)$, i.e. $|A|=|B|\le\frac1{\sqrt2}\sqrt N+O(1)$ — exactly matching Barreto's lower construction up to lower-order terms, and showing the disproof is tight (Tao, forum thread; generalized by Thomas Bloom to $m$ mutually-difference-disjoint Sidon sets, giving $\sum|A_i|^2\le N+O(m^{1/2}N^{3/4})$).

6. The first question's disproof is a different, even more direct mechanism: it doesn't need a clever simultaneous construction at all — it follows immediately once #42 is solved (any Sidon set $A$ admits a disjoint-difference companion Sidon set $B$ of *arbitrary* prescribed size $M$), by taking $A=$ a maximum Sidon set ($|A|=f(N)$) and letting $M\to\infty$ with $N$. That problem (#42) was itself resolved by an AI-driven proof pipeline: Daniil Sedov (using ChatGPT/Codex) settled small cases $M=1,2,3$, and GPT-5.5 Pro (prompted by Harjas Sandhu) then closed the general-$M$ case, giving explicit growth $|B|\gg(\log\log N/\log\log\log N)^{1/2}$ (erdosproblems.com/42). This is itself a transferable pattern worth noting for the wider knowledge base: a hard-looking finite-companion-existence lemma, needed as an ingredient for a separate disproof, was cracked by iterative small-case-then-general-case AI-assisted proof search rather than by a single closed-form combinatorial trick.

Bottom line for downstream use: the "parity-split-of-a-single-extremal-object" technique = (i) find one classical extremal construction with a strong internal uniqueness property (Sidon mod $M$, a difference set, etc.), (ii) partition its ground set by a group-compatible invariant under which the extremal object's own uniqueness property automatically forces disjointness/orthogonality between the parts, (iii) a simple pigeonhole/counting argument on the invariant's fiber sizes shows the partition must be near-balanced, giving *two* (or $k$) simultaneously near-extremal, mutually orthogonal objects "for free." Any open problem of the shape "can $k$ extremal combinatorial objects coexist with pairwise disjointness/orthogonality constraints, all close to individually-optimal" is a candidate for this move before attempting a fresh joint construction.

Related

- Erdős #30 — sharp $N^{1/2}$ asymptotics for Sidon sets — sharp $N^{1/2}$ Sidon-set asymptotics; supplies $f(N)\sim\sqrt N$ used to convert both of #43's binomial-coefficient bounds into the linear-size bounds actually proved/disproved here. Still open. - erdos/42 (forward reference) — "does every Sidon set admit a disjoint-difference companion Sidon set of any prescribed size $M$?" — solved ("SOLVED (LEAN)"), the direct engine of #43's first-question disproof; resolved via an AI-assisted small-case-then-general-case proof pipeline (Sedov, then GPT-5.5 Pro/Sandhu). - Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — $B_3$ (triple-sum) set density liminf; same broader Sidon/$B_h$-set cluster, uses the same Bose–Chowla-family finite-field constructions, still open. - Singer finite-field perfect difference set construction / wiki/problems/singer-perfect-difference-sets.md — the sibling finite-field extremal construction (Singer 1938) from which Bose–Chowla's mod-$(q^2-1)$ Sidon set is the direct generalization; both are instances of "arithmetize a combinatorial extremal structure via finite-field multiplicative-group structure." - concept/bose-chowla-construction — the classical $q\to$ Sidon-set-of-size-$q$-mod-$(q^2-1)$ construction that is the raw material for the parity-split trick; worth its own concept page given its reuse across #30, #41, and #43. - concept/parity-split-extremal-partition — the transferable technique described in the Solution above: partitioning one extremal object by a group-compatible invariant to get multiple mutually-orthogonal near-extremal objects for free. - concept/ai-assisted-proof-pipeline — the small-case-then-general-case AI proof-search pattern (Sedov/ChatGPT-Codex → GPT-5.5 Pro) that resolved #42, and the "informal mode" Aristotle search (Alexeev/Monticone) that found small #43 counterexamples and formalized the Erdős–Turán bound + Bose–Chowla construction in Lean 4 — both concretely documented instances of AI systems resolving numbered Erdős problems in 2025–2026, directly relevant to the cyberplaybook "verified-memory moat" question of whether AI-assisted derivation cracks walls recombination alone cannot.