Erdős Problem #757

Problem 757 (Round 2)

1) ROUND-2 OBJECTIVE

I pursue (C) obstruction/correction. The Round-1 writeup isolated the right local obstruction --- repeated distances collapse to $3$-term arithmetic progressions --- but it did not exploit the full hypergraph structure now available in the literature. The most promising Round-2 step is therefore to replace the Round-1 qualitative picture by a sharp quantitative framework: the A.P.-hypergraph reformulation, the best presently verified lower bound $c_*\ge 9/17$, and the explicit upper bound $c_*\le 4/7$.

2) Round-1 FOUNDATION USED

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

• Lemma 4.1 (Round 1). In a $(4,5)$-set, two disjoint pairs cannot determine the same distance.
• Corollary 4.2 (Round 1). For $S\subseteq A$, the subset $S$ is Sidon if and only if $S$ contains no nontrivial $3$-term arithmetic progression.

These are exactly the ingredients needed to pass from additive combinatorics to a $3$-uniform hypergraph independence problem.

3) NEW INSIGHT / TOOL (ROUND-2)

The new ingredient is the A.P.-hypergraph of a $(4,5)$-set. For a finite $A\subset\mathbb R$, define $H(A)$ to be the $3$-uniform hypergraph with vertex set $A$ and edge set \[ E(H(A)):=\left\{\{x-d,x,x+d\}\subseteq A: d\neq 0\right\}. \] By Round-1 Corollary 4.2, the size of the largest Sidon subset of $A$ is precisely the independence number of $H(A)$.

Round 2 adds three structural facts.

1. (i) $H(A)$ is linear: distinct edges intersect in at most one vertex.
2. (ii) Distinct edges of $H(A)$ have distinct midpoints; consequently $|E(H(A))|\le |A|-2$.
3. (iii) (Gyárfás--Lehel) If $A$ is a $(4,5)$-set, then $H(A)$ is $F_7$-free, where $F_7$ is the $7$-vertex $3$-uniform hypergraph with edges \[ \{0,1,2\},\ \{0,3,4\},\ \{0,5,6\},\ \{1,3,5\},\ \{2,4,6\}. \] Then the Henning--Yeo transversal theorem for $3$-uniform linear $F_7$-free hypergraphs gives the improved lower bound $c_*\ge 9/17$.

A second new ingredient is an explicit $14$-point $(4,5)$-set with largest Sidon subset of size $8$, which gives the improved upper bound $c_*\le 4/7$.

4) ATTACK PLAN (ROUND-2)

The exact gap after Round 1 was quantitative:

• Round 1 reduced the problem to finding a large $3$-term-A.P.-free subset.
• What remained was a numerical lower bound on the largest independent set in the associated hypergraph, and a better construction for the upper bound.

I therefore prove the hypergraph translation cleanly, verify the linearity and midpoint-counting properties directly from the Round-1 lemmas, and then import the two external facts that Round 1 did not use:

1. the Gyárfás--Lehel $F_7$-freeness theorem, and
2. the Henning--Yeo bound $17\tau(H)\le 5|V(H)|+3|E(H)|$ for $3$-uniform linear $F_7$-free hypergraphs.

This closes the main Round-1 quantitative gap.

5) WORK (ROUND-2)

For a $(4,5)$-set $A$, let $h(A)$ denote the maximum size of a Sidon subset of $A$. For each $n\ge 1$, let \[ \sigma(n):=\min\{h(A): A\subset\mathbb R,\ |A|=n,\ A\text{ is a }(4,5)\text{-set}\}, \] and let \[ c_*:=\inf_{n\ge 1}\frac{\sigma(n)}{n}. \]

Proposition 5.1.

For every $(4,5)$-set $A\subset\mathbb R$, \[ h(A)=\alpha(H(A)), \] where $\alpha$ denotes the independence number.

Proof. By Round-1 Corollary 4.2, a subset $S\subseteq A$ is Sidon if and only if it contains no nontrivial $3$-term arithmetic progression. But the edges of $H(A)$ are exactly the nontrivial $3$-term arithmetic progressions contained in $A$. Hence $S$ is Sidon if and only if $S$ is an independent set of $H(A)$. Taking the maximum over all $S\subseteq A$ yields $h(A)=\alpha(H(A))$. $\square$

Proposition 5.2.

If $A$ is a $(4,5)$-set, then $H(A)$ is linear.

Proof. Suppose two distinct edges of $H(A)$ intersect in at least two vertices. Since every edge has size $3$, the two edges then share exactly two vertices. Let the shared vertices be $x<y$, and put $d:=y-x>0$.

Any nontrivial $3$-term arithmetic progression containing both $x$ and $y$ has third point equal to one of \[ x-d,\qquad \frac{x+y}{2},\qquad y+d. \] Since the two edges are distinct, their union is obtained by choosing two distinct points from this three-element set. After translating by $-x$ and scaling by $d$, the resulting four-point set is one of \[ \{-1,0,1,2\},\qquad \{-1,0,\tfrac12,1\},\qquad \{0,\tfrac12,1,2\}. \] In the first case the positive distances are $\{1,2,3\}$, and in each of the other two cases the positive distances are $\{\tfrac12,1,\tfrac32,2\}$. Thus in every case the $4$-point union has at most four distinct positive distances, so its difference set has size at most \[ 1+2\cdot 4=9, \] contradicting the $(4,5)$-condition $|B-B|\ge 11$ for every $4$-subset $B\subseteq A$.

Therefore two distinct edges cannot intersect in two vertices, so $H(A)$ is linear. $\square$

Proposition 5.3.

If $A$ is a $(4,5)$-set and $|A|\ge 2$, then distinct edges of $H(A)$ have distinct midpoints. Consequently, \[ |E(H(A))|\le |A|-2. \]

Proof. Suppose two distinct edges have the same midpoint $u\in A$. Then for some distinct positive $d,e$, \[ \{u-d,u,u+d\},\ \{u-e,u,u+e\}\in E(H(A)). \] Without loss of generality $0<d<e$. Consider the $4$-set \[ B=\{u-e,u-d,u+d,u+e\}. \] Its six pairwise distances are \[ e-d,\ e+d,\ 2e,\ 2d,\ e+d,\ e-d. \] Thus among the positive distances there are at most four distinct values, namely \[ e-d,\ 2d,\ e+d,\ 2e. \] Hence \[ |B-B|\le 1+2\cdot 4=9, \] contradicting the $(4,5)$-condition $|B-B|\ge 11$. Therefore distinct edges have distinct midpoints.

Now the midpoint of any nontrivial $3$-term progression lies strictly between its two endpoints, so it cannot be the minimum or maximum element of $A$. Thus the midpoint map $E(H(A))\to A$ is injective and lands in $A\setminus\{\min A,\max A\}$. Therefore \[ |E(H(A))|\le |A|-2. \] $\square$

External theorem used.

Gyárfás and Lehel proved that if $A$ is a $(4,5)$-set, then $H(A)$ contains no copy of $F_7$.

External theorem used.

(Henning--Yeo.) If $H$ is a $3$-uniform linear hypergraph with no subhypergraph isomorphic to $F_7$, then \[ 17\tau(H)\le 5|V(H)|+3|E(H)|, \] where $\tau(H)$ is the transversal number.

Theorem 5.4.

For every $(4,5)$-set $A$ of size $n$, \[ h(A)\ge \frac{9}{17}n. \] Consequently, \[ c_*\ge \frac{9}{17}. \]

Proof. If $n=1$, then $h(A)=1\ge 9/17$, so there is nothing to prove. Assume $n\ge 2$, and let $H:=H(A)$. By Proposition 5.1, $h(A)=\alpha(H)$. By Proposition 5.2, $H$ is linear; by the Gyárfás--Lehel theorem, $H$ is $F_7$-free; and by Proposition 5.3, \[ |E(H)|\le |V(H)|-2=n-2. \] Applying the Henning--Yeo theorem gives \[ 17\tau(H)\le 5n+3(n-2)=8n-6<8n. \] Hence $\tau(H)\le 8n/17$. Since $\alpha(H)+\tau(H)=|V(H)|=n$ for every hypergraph, \[ h(A)=\alpha(H)\ge n-\frac{8n}{17}=\frac{9n}{17}. \] Taking the minimum over all $(4,5)$-sets $A$ of size $n$ yields $\sigma(n)\ge 9n/17$ for every $n$, and hence $c_*\ge 9/17$. $\square$

Theorem 5.5.

There exists a $(4,5)$-set \[ A_{\mathrm{base}}=\{0,136,200,243,246,249,272,286,298,323,400,528,596,1056\} \] of size $14$ such that $h(A_{\mathrm{base}})=8$. Consequently, \[ c_*\le \frac{8}{14}=\frac47. \]

Proof. The assertions that $A_{\mathrm{base}}$ is a $(4,5)$-set and that its largest Sidon subset has size $8$ were verified by exhaustive exact computation in Ma--Tang. Therefore $\sigma(14)\le 8$, and by the definition of $c_*$ as an infimum of the ratios $\sigma(n)/n$, we obtain $c_*\le 8/14=4/7$. $\square$

Round-2 conclusion for Problem 757.

Combining Theorems 5.4 and 5.5 gives the strongest explicit interval reached in this round: \[ \frac{9}{17}\le c_*\le \frac47. \] This is a strict improvement over the Round-1 state $\tfrac12<c_*<\tfrac35$.

6) ADVERSARIAL VERIFICATION

• Does Proposition 5.1 use anything stronger than Round 1? No. It is exactly Round-1 Corollary 4.2 rewritten hypergraphically.
• Could Proposition 5.2 fail when two $3$-term progressions share two vertices? No. The proof reduces the union to one of three affine normal forms, and each normal form has at most four distinct positive distances on its four vertices.
• Is the midpoint-counting argument valid for all edges? Yes. The midpoint of a nontrivial progression is never an extreme point of $A$, so the midpoint map lands in $A\setminus\{\min A,\max A\}$.
• Does the upper bound really follow from one finite example? Yes. Since $c_*=\inf_n \sigma(n)/n$, one example with $\sigma(14)\le 8$ immediately implies $c_*\le 8/14$.
• Is anything claimed beyond the cited external theorems? No. The only imported ingredients are the $F_7$-freeness theorem of Gyárfás--Lehel, the Henning--Yeo transversal bound, and the explicit $14$-point construction of Ma--Tang.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED). Round 2 upgrades the Round-1 qualitative reduction to the presently strongest quantitative statement I could verify: \[ \frac{9}{17}\le c_*\le \frac47. \] The lower bound is now derived by a clean hypergraph argument using Round-1's "Sidon $\Leftrightarrow$ $3$AP-free" reformulation, while the upper bound comes from an explicit $14$-point example.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 55%

9) REFERENCES

• J. Ma and Q. Tang, Largest Sidon subsets in weak Sidon sets, arXiv:2602.23282, 2026.
• A. Gyárfás and J. Lehel, Linear sets with five distinct differences among any four elements, J. Combin. Theory Ser. B 64 $1995$, 108--118.
• M. A. Henning and A. Yeo, Affine Planes and Transversals in 3-Uniform Linear Hypergraphs, Graphs Combin. 37 $2021$, 867--890.

10) OUTPUT FORMAT

Here the Erdős problem number is $x=757$.

Erdős Problem #757: independent continuation

Date: 23 September 2026. Source versions read in full: 757.tex in gpt_pro_5.4.

1) OBJECTIVE AND FINITE CHECK

A weak $(4,5)$ set of real numbers has at least five distinct positive distances on every four-element subset. The source reduces its strong $(3,3)$ subsets to sets containing no three-term arithmetic progression, and supplies \[ A=\{0,136,200,243,246,249,272,286,298,323,400,528,596,1056\}. \] I checked all $\binom{14}{4}=1001$ four-element subsets using integer arithmetic. Every one has at least five distances. There are exactly twelve arithmetic-progression triples. Enumerating all $2^{14}$ subsets gives maximum progression-free size eight. These checks are reproduced in verification/root_checks.py.

2) REPLICATION WITHOUT CREATING EXTRA RELATIONS

Ordinary translated copies fail: equal internal distances in two copies violate the four-point requirement. Instead fix a positive transcendental real $t$ and form \[ B_k=\bigcup_{i=1}^k\{t^{2i}+a t^{2i+1}:a\in A\}. \] Different listed points are distinct, because a nonzero integer polynomial cannot vanish at $t$. Any equality of positive distances can be written $x-y=\pm(z-w)$. For four distinct endpoints in more than one block, comparison of the coefficients of each $t^{2i}$ forces each occupied block to occur equally often on the two sides. The only mixed possibility is two blocks each containing one point on each side; comparison of $t^{2i+1}$ then forces those points to coincide, a contradiction. For three distinct endpoints a repeated distance means $2x=y+z$. Its constant-block coefficients force all three into the same block. Therefore all nontrivial distance repetitions are internal. Four points in one block inherit the property of $A$; three in one block and one outside have at most the one distance repetition possible on three real points; every other mixed four-set has all six distances distinct. Thus $B_k$ is weak $(4,5)$.

3) EXACT INDEPENDENCE RATIO

The same coefficient argument shows that every arithmetic progression in $B_k$ lies in a single block. A progression-free subset has at most eight points in each block, and independent choices of eight-point progression-free subsets attain this bound. Consequently \[ |B_k|=14k,\qquad \alpha_{\rm AP}(B_k)=8k. \] The finite $4/7$ obstruction therefore persists at arbitrarily large sizes, rather than being an isolated fourteen-point effect.

7) FINAL

UNRESOLVED. This verifies and amplifies the supplied example. It does not close the source's gap between the general lower bound and $4/7$, nor claim a new best upper bound.

8) COMPLETION ESTIMATE

COMPLETION: 15% This is a subjective estimate of progress toward the entire stated problem, not a probability that the conjecture or an unverified proof is correct.

Problem 757

1) FORMAL RESTATEMENT

Let $A\subset\mathbb{R}$ with $|A|=n$. For a finite set $B\subset\mathbb{R}$, write \[ B-B:=\{x-y: x,y\in B\}. \] Assume that $A$ satisfies the $(4,5)$-difference condition: \[ \forall B\subseteq A\ (|B|=4\implies |B-B|\ge 11). \] Equivalently, for every $4$-set $B=\{b_1,b_2,b_3,b_4\}$, among the $6$ pairwise distances $\{|b_i-b_j|:1\le i<j\le 4\}$ at least $5$ are distinct.

A subset $S\subset\mathbb{R}$ is a Sidon set (a $B_2$-set) if all sums $s_i+s_j$ with $s_i\le s_j$ are distinct; equivalently, all nonzero differences $s_i-s_j$ with $s_i>s_j$ are distinct.

Define, for each $n$, the quantity \[ \sigma(n):=\min\Big\{\max\{|S|: S\subseteq A\ \text{Sidon}\}: A\subset\mathbb{R},\ |A|=n,\ A\ \text{satisfies }|B-B|\ge 11\ \forall B\in\binom{A}{4}\Big\}. \] The problem asks for the best constant \[ c^*:=\sup\{c>0: \forall n\ \sigma(n)\ge cn\}, \] (or, equivalently, the asymptotically best guaranteed linear fraction of a Sidon subset in every such $A$).

2) QUICK LITERATURE/CONTEXT CHECK

The statement as recorded in Erdős's problem list (and repeated in later sources) includes:

• Erdős--Sós: $c^*\ge \tfrac12$.
• Gyárfás--Lehel $1995$: improved the lower bound and exhibited an upper bound, \[\tfrac12<c^*<\tfrac35,\] with the upper bound given by taking $A$ to be the first $n$ Fibonacci numbers.

I did not locate a definitive resolution of the exact value of $c^*$.

3) ATTACK PLAN

A natural first step is to understand what the constraint $|B-B|\ge 11$ forbids. For a $4$-set, $|B-B|=1+2\cdot\#\{\text{distinct positive distances in }B\}$. Thus $|B-B|\ge 11$ means at most one of the $6$ distances repeats. The extremal obstruction to being Sidon is an equality of distances \[ |a-b|=|c-d|\quad\text{with }\{a,b\}\ne\{c,d\}. \] Under the $(4,5)$ hypothesis, such equalities are forced to have strong overlap structure. If one can reduce Sidon-ness in $A$ to forbidding only a small class of local configurations (e.g. $3$-term arithmetic progressions), then the problem becomes a structured extremal/packing question (hypergraph independent set problem) on those configurations.

4) WORK

Lemma 4.1 (no repeated distance on disjoint pairs).

Assume $A$ satisfies the $(4,5)$-difference condition. Then there do not exist four distinct $a,b,c,d\in A$ such that \[ |a-b|=|c-d|\ \text{ and }\ \{a,b\}\cap\{c,d\}=\varnothing. \] Proof. Assume (for contradiction) that $a,b,c,d$ are distinct and $|a-b|=|c-d|=:r$ with disjoint pairs. By translating and relabelling if needed, we may assume $a<b$ and $c<d$ so that $b-a=d-c=r$. Then also \[ |c-a|=c-a = (c+r)-(a+r)=d-b=|d-b|. \] Hence in the $4$-set $\{a,b,c,d\}$ the distance $r$ occurs at least twice (between $a,b$ and $c,d$) and the distance $|c-a|$ occurs at least twice (between $a,c$ and $b,d$), so there are at least two repeated distances among the $6$ pairwise distances. This contradicts the $(4,5)$-difference condition. $\square$

Corollary 4.2 (Sidon versus 3-term arithmetic progressions inside $A$).

Let $S\subseteq A$. Then $S$ fails to be Sidon if and only if $S$ contains a (nontrivial) $3$-term arithmetic progression, i.e. distinct $x,y,z\in S$ with $y-x=z-y$.

Proof. If $S$ contains a $3$-term AP $x<y<z$ with $y-x=z-y$, then the distance $y-x$ is repeated among pairs $(x,y)$ and $(y,z)$, so $S$ is not Sidon. Conversely, if $S$ is not Sidon, there exist distinct unordered pairs $\{u,v\}\ne\{u',v'\}$ in $S$ with $|u-v|=|u'-v'|$. By Lemma 4.1 these pairs cannot be disjoint, hence they share a vertex. Up to relabelling, we have distinct $x,y,z\in S$ with $|x-y|=|y-z|$, which in $\mathbb{R}$ implies $y$ is the midpoint of $x$ and $z$, i.e. $x,y,z$ form a $3$-term AP. $\square$

Interpretation.

Under the $(4,5)$-difference condition, the entire Sidon obstruction collapses to the presence of $3$-term arithmetic progressions. In other words, within such an $A$, finding a large Sidon subset is equivalent to finding a large subset free of $3$-term APs.

Small-$n$ sanity check (computational).

A brute-force search over small integer sets (restricted to a bounded range) finds examples of $(4,5)$-sets and computes the smallest possible maximum Sidon subset size among them. For instance, within a small search window one can find:

• $n=4$: example $A=\{0,1,2,5\}$ satisfies the condition; its largest Sidon subset has size $3$.
• $n=6$: example $A=\{0,1,2,5,8,15\}$ satisfies the condition; its largest Sidon subset has size $4$.

These are consistent with a linear guarantee, but of course do not address the optimal constant $c^*$.

5) OBSTRUCTIONS/CAVEATS

• Determining $c^*$ requires a sharp extremal analysis of how many $3$-term APs can be forced by the $(4,5)$ condition and how large an AP-free subset must exist in such structured sets.
• While Lemma 4.1 and Corollary 4.2 reduce the nature of the obstruction, they do not by themselves yield the best constant (currently only the interval $\tfrac12<c^*<\tfrac35$ is recorded).

6) FINAL

UNRESOLVED.

• (i) Where I got stuck: I did not obtain a new argument pinning down the exact optimal constant $c^*$, or improving the best known bounds beyond $\tfrac12<c^*<\tfrac35$.
• (ii) Partial progress: I proved that the $(4,5)$ condition forbids equal distances on disjoint pairs (Lemma 4.1) and therefore, within such sets, Sidon subsets are exactly those avoiding $3$-term APs (Cor. 4.2).
• (iii) What seems next: Model the family of $3$-term APs in $A$ as a $3$-uniform hypergraph with strong linearity-type constraints; then apply (or develop) sharp bounds on the independence number under those constraints. This is plausibly where the improvements from $1/2$ to $>1/2$ arise.
• (iv) What I believe is true: The exact value of $c^*$ is likely nontrivial; the Fibonacci example suggests the extremal configurations are highly structured rather than random.

7) COMPLETION ESTIMATE

$20\%$.