Erdős Problem #773

Erdős Problem #773

1) ROUND-2 OBJECTIVE

Path (C): obstruction/correction. The main Round-1 gap is that the hypergraph extraction argument only produced a weak Sidon subset of the squares, not necessarily a genuine Sidon subset in the standard sense (where equal sums with repeated summands are also forbidden). The goal in this round is to repair that gap, while keeping the Round-1 framework. The new ingredient is a conversion theorem: every weak Sidon set of size $m$ contains a genuine Sidon subset of size at least $(m+1)/2$. This turns the Round-1 weak-Sidon extraction into a correct standard-Sidon lower bound.

2) Round-1 FOUNDATION USED

I use the following Round-1 results without reproving them.

1. The Landau upper bound: \[ f(N) \ll \frac{N}{(\log N)^{1/4}}, \] for the maximum size $f(N)$ of a Sidon subset of $\{1^2,2^2,\dots,N^2\}$.

2. The extraction lemma from Round-1: every $B(2k)$-sequence of length $n$ (in the Round-1 sense: every integer has at most $k$ representations as $a_i+a_j$ with $i<j$) contains a weak Sidon subsequence of size \[ \gg k^{-1/3} n^{2/3}. \]

3. The divisor-function input from Round-1: for every $\varepsilon>0$, the first $N$ squares form a $B(2k)$-sequence with $k\le N^{3\varepsilon}$ for all sufficiently large $N$.

3) NEW INSIGHT / TOOL (ROUND-2)

The genuinely new ingredient is the following strengthening.

Theorem 3.1. Let $A$ be a weak Sidon set of size $m$. Then $A$ contains a genuine Sidon subset of size at least \[ \left\lceil \frac{m+1}{2}\right\rceil. \]

This is exactly the missing bridge between the Round-1 weak-Sidon extraction and the actual statement of Problem #773.

4) ATTACK PLAN (ROUND-2)

The exact Round-1 gap is the weak-vs-standard Sidon distinction. To close it, I proceed as follows.

1. For a weak Sidon set $A$, build the 3-uniform hypergraph $H(A)$ whose edges are the 3-term arithmetic progressions in $A$.
2. Prove that for subsets of a weak Sidon set, being genuinely Sidon is equivalent to containing no 3-term arithmetic progression.
3. Prove that $H(A)$ has at most $|A|-2$ edges by an injective midpoint map.
4. Apply the Chvátal--McDiarmid--Tuza transversal bound \[ \tau(H) \le \frac{|V(H)|+|E(H)|}{4} \] for 3-uniform hypergraphs.
5. Convert the resulting large independent set in $H(A)$ into a large genuine Sidon subset of $A$, and then apply this to the Round-1 weak Sidon subset of the squares.

5) WORK (ROUND-2)

I first isolate the precise weak-Sidon-to-Sidon conversion.

Definition. A finite set $A\subset\mathbb R$ is weak Sidon if all sums $x+y$ with $x,y\in A$ and $x<y$ are distinct. It is Sidon if all sums $x+y$ with $x,y\in A$ and $x\le y$ are distinct.

Lemma 5.1. Let $A$ be a weak Sidon set, and let $S\subseteq A$. Then $S$ is Sidon if and only if $S$ contains no 3-term arithmetic progression.

Proof. If $x<y<z$ in $S$ satisfy $x+z=2y$, then the two pair-sums $x+z$ and $y+y$ are equal, so $S$ is not Sidon.

Conversely, assume that $S$ is not Sidon. Then there are two distinct unordered pairs $\{u,v\}\neq\{x,y\}$, with $u\le v$ and $x\le y$, such that \[ u+v=x+y. \] If the four elements $u,v,x,y$ were all distinct, then after relabeling them as $a<b<c<d$, the equality would force \[ a+d=b+c, \] which is an equality of two sums of distinct pairs, contradicting the weak Sidon property inherited from $A$. Hence at most three distinct elements occur.

They cannot be only two distinct elements, because the unordered pairs are different. Thus there are exactly three distinct elements, say $a<b<c$. The only possible equality of two distinct unordered pairs is \[ a+c=b+b, \] so $a,b,c$ form a 3-term arithmetic progression. Therefore $S$ fails to be Sidon if and only if it contains a 3-term arithmetic progression. $\square$

Now define $H(A)$ to be the 3-uniform hypergraph with vertex set $A$ and edge set equal to the collection of 3-term arithmetic progressions in $A$.

By Lemma 5.1, the genuine Sidon subsets of $A$ are exactly the independent sets of $H(A)$. Therefore the largest genuine Sidon subset of $A$ has size \[ \alpha(H(A)). \]

Lemma 5.2. If $A=\{a_1<a_2<\cdots<a_m\}$ is weak Sidon, then \[ |E(H(A))|\le m-2. \]

Proof. Every edge $\{x,y,z\}$ of $H(A)$ has a unique midpoint $y$, with $x<y<z$ and $x+z=2y$. Thus the midpoint belongs to $\{a_2,\dots,a_{m-1}\}$.

I claim that distinct edges have distinct midpoints. Indeed, if \[ x<y<z, \qquad x'<y<z' \] are two distinct 3-term arithmetic progressions with the same midpoint $y$, then \[ x+z=2y=x'+z'. \] Since the two unordered pairs $\{x,z\}$ and $\{x',z'\}$ are distinct, this contradicts the weak Sidon property of $A$. Hence the midpoint map is injective from $E(H(A))$ into $\{a_2,\dots,a_{m-1}\}$, so $|E(H(A))|\le m-2$. $\square$

I now use the classical theorem of Chvátal and McDiarmid, independently proved by Tuza: if $H$ is a 3-uniform hypergraph with $n_H$ vertices and $m_H$ edges, then \[ \tau(H)\le \frac{n_H+m_H}{4}. \] Since $\alpha(H)+\tau(H)=|V(H)|$ for every finite hypergraph, Lemma 5.2 yields the conversion theorem.

Proof of Theorem 3.1. Let $m=|A|$, and let $H=H(A)$. Then $|V(H)|=m$, and by Lemma 5.2, \[ |E(H)|\le m-2. \] Hence \[ \tau(H)\le \frac{|V(H)|+|E(H)|}{4}\le \frac{m+(m-2)}{4}=\frac{m-1}{2}. \] Therefore \[ \alpha(H)=m-\tau(H)\ge m-\frac{m-1}{2}=\frac{m+1}{2}. \] Since independent sets of $H$ are exactly Sidon subsets of $A$ by Lemma 5.1, the conclusion follows. $\square$

This immediately strengthens the Round-1 extraction lemma.

Corollary 5.3. Every $B(2k)$-sequence of length $n$ contains a genuine Sidon subsequence of size \[ \gg k^{-1/3}n^{2/3}. \]

Proof. By the Round-1 extraction lemma, there is a weak Sidon subsequence of size \[ M\gg k^{-1/3}n^{2/3}. \] Applying Theorem 3.1 to that weak Sidon subsequence gives a genuine Sidon subsequence of size at least $(M+1)/2\gg k^{-1/3}n^{2/3}$. $\square$

Applying this to the first $N$ squares and using the Round-1 divisor-function estimate with $k\le N^{3\varepsilon}$, I obtain: \[ f(N)\gg_\varepsilon N^{2/3-\varepsilon} \qquad (\forall\,\varepsilon>0). \] This is now a correct standard-Sidon lower bound, not merely a weak-Sidon lower bound.

6) ADVERSARIAL VERIFICATION

The only serious logical vulnerability in Round-1 was the weak-vs-standard Sidon confusion. I check that the present repair really closes it.

1. Could Lemma 5.1 fail because a non-Sidon configuration uses four distinct elements? No. In a weak Sidon set, four distinct elements giving equal sums would already violate weak Sidonicity.

2. Could distinct 3-term progressions share a midpoint without violating weak Sidonicity? No. Shared midpoint $y$ gives two distinct representations of $2y$ as a sum of distinct pairs.

3. Does the Chvátal--McDiarmid--Tuza bound apply to disconnected hypergraphs? Yes; it is stated for all 3-uniform hypergraphs.

4. Did I recover the known sharp lower bound $f(N)\gg N^{2/3}$? No. This round only repairs the Round-1 proof to a correct bound $f(N)\gg_\varepsilon N^{2/3-\varepsilon}$. The stronger bound $f(N)\gg N^{2/3}$ remains the theorem of Lefmann and Thiele.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED)

The Round-1 lower bound has been repaired gap-free: the hypergraph extraction plus Theorem 3.1 now gives a genuine Sidon subset of the first $N$ squares of size $\gg_\varepsilon N^{2/3-\varepsilon}$. The overall problem remains open; the current best-known bounds are still \[ N^{2/3}\ll f(N)\ll \frac{N}{(\log N)^{1/4}}. \]

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 60%

9) REFERENCES

[1] T. F. Bloom, Erdős Problem #773, erdosproblems.com/773, accessed 2026-03-07.

[2] H. Lefmann and T. Thiele, Point sets with distinct distances, Combinatorica 15 $1995$, 379--408.

[3] J. Ma and Q. Tang, Largest Sidon subsets in weak Sidon sets, arXiv:2602.23282, 2026.

[4] V. Chvátal and C. McDiarmid, Small transversals in hypergraphs, Combinatorica 12 $1992$, 19--26.

[5] Zs. Tuza, Covering all cliques of a graph, Discrete Math. 86 $1990$, 117--126.

Erdős Problem #773: independent continuation

Date: 2026-09-23. Research attempt; no claim of a new published result.

1) TARGET AND SOURCE AUDIT

Estimate the largest size $f(N)$ of a standard Sidon subset of $\{1^2,\ldots,N^2\}$, where sums allowing a repeated summand must also be distinct.

All supplied versions considered: 773.tex. The source repairs weak versus standard Sidonicity using a sharp half-size conversion theorem. I give a direct alteration proof that handles three- and four-vertex collisions together, so that the extraction step no longer depends on that conversion theorem or on an unavailable earlier round.

2) WORK

Direct standard-Sidon extraction.

Let $A$ be a set of $n$ real numbers such that every real number has at most $k\ge1$ representations as a sum of two distinct elements of $A$. Then $A$ has a standard Sidon subset of size at least \[ {3\over4}k^{-1/3}n^{2/3}-1. \tag{1} \] For each sum $s$, write $r(s)$ for its number of unordered distinct-pair representations. Distinct representations of the same sum cannot share a vertex. Thus the number of four-vertex collision configurations is at most \[ \sum_s {r(s)\choose2}\le {k-1\over2}\sum_s r(s) \le {kn^2\over4}. \] Three-vertex collisions are precisely $x+z=2y$ with $x<y<z$. Each midpoint $y$ admits at most $k$ endpoint pairs, so there are at most $kn$ such configurations.

Select each element independently with probability $p=(kn)^{-1/3}$. Delete at most one element from every surviving collision configuration. No deletion creates another collision. The expected surviving size after these deletions is at least \[ np-{kn^2\over4}p^4-knp^3 ={3\over4}k^{-1/3}n^{2/3}-1. \] Some realization attains this bound, proving $1$. The list of configurations is exhaustive: equal sums of distinct pairs either involve four distinct elements, or cancellation identifies the pair; one repeated pair gives a three-term progression; two repeated pairs force the same midpoint.

Applying the lemma to the representation bound $k\le N^{3\epsilon}$ quoted for squares in the supplied source recovers $f(N)\gg_\epsilon N^{2/3-\epsilon}$. That application is conditional on that representation estimate; the extraction lemma itself is entirely proved above. It does not improve the stronger $N^{2/3}$ literature lower bound recorded in the source.

3) ADVERSARIAL VERIFICATION

The probability satisfies $p\le1$ for $k,n\ge1$. Multiple collisions on the same vertices can only make the deletion bound less efficient, never invalidate it. Repeated summands are explicitly included. This gives a direct proof of a known-strength lower bound, not a new asymptotic exponent.

4) FINAL

UNRESOLVED. The gap to the near-linear upper bound for squares remains. Improving the generic extraction constant or removing the weak-Sidon intermediary does not determine $f(N)$.

5) SOURCES CHECKED

Full source read. Checked Ma--Tang, https://arxiv.org/abs/2602.23282v2, on 2026-09-23: its abstract establishes the exact half-size weak-Sidon conversion for all nonempty sets. The direct alteration argument above uses none of that paper's theorems.

6) COMPLETION ESTIMATE

This is a conservative subjective measure of progress toward the original question, not a probability of correctness or a claim that the remaining work is routine. COMPLETION: 12%

Problem 773: Sidon subsets of the first $N$ squares

1) Formal restatement

Let $S_N=\{1^2,2^2,\dots,N^2\}$. A set $A\subseteq\mathbb{Z}$ is Sidon (a $B_2$-set) if \[ a+b=c+d\ (a,b,c,d\in A)\quad\Longrightarrow\quad \{a,b\}=\{c,d\}. \] Equivalently, all sums $a+b$ with $a<b$ are distinct. Define \[ f(N):=\max\{|A|:A\subseteq S_N \text{ is Sidon}\}. \] The problem asks for the best possible asymptotic bounds on $f(N)$.

2) Quick literature/context check (no more than 8 lines)

• Landau's theorem on sums of two squares yields $f(N)\ll N(\log N)^{-1/4}$.
• A graph/hypergraph extraction lemma of Alon--Erdős implies $f(N)\gg_\varepsilon N^{2/3-\varepsilon}$ for every $\varepsilon>0$.
• Lefmann--Thiele improved the lower bound to $f(N)\gg N^{2/3}$.
• The true order of $f(N)$ remains open: there is still a large gap between exponents $2/3$ and $1$ (up to logs).

3) Attack plan

• Upper bound: count the number of distinct pair-sums $a+a'$ forced by the Sidon property and compare with Landau's count of integers that are sums of two squares.
• Lower bound: prove a general lemma that any $B(2k)$ sequence of length $n$ contains a Sidon subsequence of size $\gg k^{-1/3}n^{2/3}$, then apply to squares using a divisor-function bound on the number of representations $m=i^2+j^2$.

4) Work

Upper bound $\boldsymbol{f(N)\ll N(\log N)^{-1/4}}$.

Let $A\subseteq S_N$ be Sidon and let \[ \Sigma:=\{a+a': a,a'\in A,\ a<a'\}. \] Sidon implies that each unordered pair $\{a,a'\}$ gives a distinct sum, so $|\Sigma|=\binom{|A|}{2}$. Each element of $\Sigma$ is a sum of two squares, and $\Sigma\subseteq [2,2N^2]$.

Let $R(X)$ be the number of integers $m\le X$ representable as a sum of two squares. Landau proved $R(X)\ll X/\sqrt{\log X}$, so \[ \binom{|A|}{2}=|\Sigma|\le R(2N^2)\ll \frac{N^2}{\sqrt{\log N}}. \] Hence $|A|^2\ll N^2(\log N)^{-1/2}$, i.e. \[ |A|\ll \frac{N}{(\log N)^{1/4}}. \] Therefore $f(N)\ll N(\log N)^{-1/4}$.

A general extraction lemma.

Lower bound for squares.

Apply Lemma Lemma to $a_i=i^2$ for $i=1,\dots,N$ (so $n=N$). We need an upper bound on the number of representations of $m\le 2N^2$ as $m=i^2+j^2$ with $1\le i<j\le N$.

Let $r_2(m)$ denote the number of integer solutions $(x,y)\in\mathbb{Z}^2$ to $x^2+y^2=m$. A classical formula implies $r_2(m)\le 4d(m)$, where $d(m)$ is the divisor function. Hence the number of pairs $(i,j)$ with $1\le i<j\le N$ and $i^2+j^2=m$ is $O(d(m))$.

Fix $\varepsilon>0$. It is standard that $d(m)\le m^{\varepsilon}$ for all sufficiently large $m$. Since $m\le 2N^2$, for $N$ large we have $d(m)\ll_\varepsilon N^{2\varepsilon}$, and thus \[ \#\{(i,j): i^2+j^2=m,\ 1\le i<j\le N\}\le N^{3\varepsilon} \] after increasing $N$ if needed (absorbing constants). Therefore $\{1^2,\dots,N^2\}$ is a $B(2k)$-sequence with $k=N^{3\varepsilon}$, and Lemma Lemma gives a Sidon subset of size \[ \gg k^{-1/3}N^{2/3} = N^{2/3-\varepsilon}. \] So $f(N)\gg_\varepsilon N^{2/3-\varepsilon}$ for every $\varepsilon>0$. (A stronger bound $f(N)\gg N^{2/3}$ is known by Lefmann--Thiele.)

5) Verification

• Upper bound: $|\Sigma|=\binom{|A|}{2}$ is exact for Sidon; Landau's bound applies to all sums $a+a'\le 2N^2$.
• Lemma Lemma: the hypergraph edge count $\sum_m\binom{r_m}{2}$ is maximized by packing fibers to size $k$, giving $|E(H)|\le (k-1)n^2/4$.
• Divisor bound step: only needs the qualitative fact $d(m)\le m^\varepsilon$ for large $m$, hence $k=N^{O(\varepsilon)}$.

6) Final (exactly one label and one sub-label)

LABEL: UNRESOLVED.
SUBLABEL: Proved the Landau upper bound and an $N^{2/3-\varepsilon}$ lower bound (with known improvement to $N^{2/3}$); the true order of $f(N)$ is open.

7) Completion estimate

To resolve Problem 773 completely would require either substantially improving the upper bound (beyond Landau) or giving a near-linear lower bound; presently the best-known exponents remain $2/3$ (lower) and $1$ (upper, with a log saving).