Erdős problem #757 — wave 7k

Date: 2026-08-12 (UTC; original report accessed 2026-07-27)

Claim labels

• (a) elementary-rigorous: proved below from definitions.
• (b) rigorous-modulo-named-theorem: the deduction is complete, conditional only on the explicitly named published theorem.
• (c) plausible/structural-unverified: heuristic only. No result below rests on a claim of this type.
• (d) computational-only: finite exhaustive exact-arithmetic calculation, reproducible by the standalone checker.

Step 0: authoritative live-page gate

I read the live problem page and its full discussion thread through the Bright Data browser path, not through datacenter curl. The page loaded successfully.

Verbatim live statement

Let $A\subset \mathbb{R}$ be a set of size $n$ such that every subset $B\subseteq A$ with $\lvert B\rvert =4$ has $\lvert B-B\rvert\geq 11$. Find the best constant $c>0$ such that $A$ must always contain a Sidon set of size $\geq cn$.

This is copied verbatim from the live page's LaTeX view.

Gate status

• Page status: OPEN.
• Claimed proofs: 0.
• “Currently working on this problem”: None.
• “Interested in collaborating”: None.
• The page says it was last edited 10 April 2026.

Therefore the mandatory stop condition did not trigger.

Live-page known results

The page states:

1. A four-element Sidon set has \(\lvert B-B\rvert=13\), so the hypothesis

permits at most one “missing” difference. Equivalently, every four points determine at least five distinct (positive) distances.

1. Without loss of generality one may assume \(A\subset\mathbb N\).
2. Erdős and Sós proved \(c\geq 1/2\).
3. Gyárfás and Lehel proved

\[ \frac12+\frac{1}{141\cdot 76}\leq c\leq\frac35, \] with the upper construction based on the first \(n\) Fibonacci numbers.

1. Ma and Tang improved this to

\[ \frac9{17}\leq c\leq\frac47. \]

All seven live comments

The discussion thread contains seven comments/replies and no proof claim:

1. Yongxi Lin asks whether positivity of \(A\) matters.
2. Thomas Bloom replies that translation removes the issue and that one may

even assume \(A\subset\mathbb N\).

1. Quanyu Tang records the precise Gyárfás–Lehel bound and announces

arXiv:2602.23282 with the \(9/17\) and \(4/7\) bounds. The comment says AI was used exploratorily and the arguments were subsequently human-checked.

1. Terence Tao notes that this is constant 5b in the optimization-constant

database.

1. Nat Sothanaphan posts “Congrats.”
2. Nat Sothanaphan posts that a standard GPT check found no issue.
3. Quanyu Tang replies “Thanks!”

The site itself warns that comments are user-supplied and unverified. Nothing in them indicates a current worker, claimed proof, solution, or falsification.

Live sources:

• Problem #757
• Full discussion thread
• Live LaTeX view

Primary-source literature audit

I searched by the problem number, exact title, \((4,5)\)-set terminology, the current rational bounds, and citations to the recent preprint.

1. Erdős (1997). Publisher metadata verifies P. Erdős, “Some old and new

problems in various branches of combinatorics,” Discrete Mathematics 165/166 (1997), 227–231, DOI 10.1016/S0012-365X(96)00173-200173-2). The full text was not openly exposed by the publisher in this run. Ma–Tang explicitly locate this problem on p. 231. There is also a different, much older Erdős paper with nearly the same title; I did not conflate it with this source.

1. Gyárfás–Lehel (1995). The publisher abstract verifies the definition,

the linear-size Sidon-subset problem, a lower bound \((1/2+\varepsilon)n\), and an upper bound \(3n/5+1\): 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, DOI 10.1006/jctb.1995.1028. The exact displayed \(\varepsilon=1/(141\cdot76)\) was checked against both the authoritative live page and the Ma–Tang source.

1. Henning–Yeo (2021). The publisher abstract explicitly states that a

3-uniform linear hypergraph avoiding the affine-plane-minus-two-vertices configuration satisfies \[ 17\tau(H)\leq 5n_H+3m_H. \] See M. A. Henning and A. Yeo, “Affine Planes and Transversals in 3-Uniform Linear Hypergraphs,” Graphs and Combinatorics 37 (2021), 867–890, DOI 10.1007/s00373-021-02285-x.

1. Ma–Tang (2026). I downloaded and read the current v2 TeX source, not

only its abstract: J. Ma and Q. Tang, “Largest Sidon subsets in weak Sidon sets,” arXiv:2602.23282v2, updated 6 March 2026. It proves the limit/infimum characterization, records the AP-hypergraph reduction and the \(F_7\)-free input, applies the Henning–Yeo theorem, and gives the 14-point block \[ A_{14}=\{0,136,200,243,246,249,272,286,298,323,400,528,596,1056\} \] with \(h(A_{14})=8\). Their independent code repository is ep757-45set-base-block-verification.

Targeted searches found no later primary paper improving the Ma–Tang interval. This is a search result, not a proof that no such paper exists. The live page and the current optimization-constant database also still display \([9/17,4/7]\).

Setup

For a finite set \(A\), let \(h(A)\) be the largest size of a Sidon subset, where “Sidon” means that all sums \(x+y\), \(x\leq y\), are distinct. Define

Ma–Tang prove

For sorted \(A=\{a_0<\cdots<a_{n-1}\}\), its AP hypergraph \(H(A)\) has vertex set \(A\) and an edge \(\{a_i,a_j,a_k\}\) exactly when \(a_i+a_k=2a_j\).

An exact elementary characterization

Lemma 1 — four-gap characterization (a)

A finite real set \(A\) is a \((4,5)\)-set if and only if:

1. \(A\) is weak Sidon (all sums of two distinct elements are distinct), and
2. its AP hypergraph \(H(A)\) is linear (two edges meet in at most one vertex).

Proof

Take a sorted quadruple \(x_0<x_1<x_2<x_3\) and put

Its six positive distances are

Apart from impossible comparisons with a strictly larger positive sum, the only possible equalities are

The first four say, respectively, that one of the four triples in the quadruple is a three-term AP. The last equality \(p=r\) is exactly

a weak-Sidon violation; it also forces \(p+q=q+r\), so the quadruple then has at most four distinct distances.

Thus weak Sidonicity rules out \(p=r\). Subject to that, at least five distances occur exactly when the quadruple contains at most one AP triple. Two distinct triples inside one quadruple share two vertices, so “at most one AP triple in every quadruple” is exactly linearity of \(H(A)\). This proves both directions. \(\square\)

Lemma 2 — Sidon subsets are independent sets (a)

If \(A\) is weak Sidon, then \(S\subseteq A\) is Sidon if and only if \(S\) contains no three-term AP. Hence

Indeed, an AP \(x-d,x,x+d\) gives \((x-d)+(x+d)=x+x\). Conversely, a repeated Sidon sum cannot use four distinct elements because \(A\) is weak Sidon; with three distinct values it must have the form \(u+w=2v\).

Lemma 3 — the midpoint bound (a)

For a weak Sidon set of size \(n\geq2\), distinct AP edges have distinct midpoints. Otherwise two different endpoint pairs have the same sum \(2a_j\). The minimum and maximum elements cannot be midpoints, so

These lemmas are proved here rather than imported. The additional fact that \(H(A)\) is \(F_7\)-free is the named Gyárfás–Lehel result used by Ma–Tang, where

A finite-size sharpening hidden in the current proof

Henning–Yeo, applied exactly as in Ma–Tang, gives (b)

Using the full midpoint bound \(m\leq n-2\), without discarding its constant term, gives

Since \(\tau\) is integral and \(h(A)=\alpha(H)=n-\tau(H)\),

Ma–Tang relax \(8n-6\) to \(8n\) because they need the asymptotic constant. Retaining \(-6\) is decisive for the small cases below.

The exceptional \(n=5\) improvement (a)

Equation (1) gives only \(f(5)\geq3\), but in fact \(f(5)\geq4\).

A linear 3-graph on five vertices has at most two edges. To see this, two edges must intersect once and together use all five vertices, say \(\{x,a,b\}\) and \(\{x,c,d\}\). A third edge containing \(x\) cannot take another vertex without meeting one old edge twice; a third edge not containing \(x\) can take at most one of \(\{a,b\}\) and at most one of \(\{c,d\}\), so it cannot have three vertices.

Each 3-edge is contained in exactly two of the five 4-subsets. Two edges therefore cover at most four 4-subsets, leaving a 4-subset with no AP. Lemma 2 makes that subset Sidon.

Explicit 12-point block found in this run

The capped construction search found

I do not claim priority for the mere existence of a 12-point \(h=7\) block: Ma–Tang's AI-usage declaration says their exploration first found a 12-point example before the published 14-point block, but their paper and verification repository do not give that earlier block's coordinates. The set above is an explicit, independently checkable instance produced in this run.

Its complete AP edge list, in zero-based indices, is

The dependency-free checker verifies (d):

• all \(\binom{12}{4}=495\) quadruples have at least five distinct distances;
• the minimum attained number is exactly five;
• all 66 sums of distinct pairs are different;
• the AP list above is complete and linear;
• every subset of size \(8,9,10,11,\) or \(12\) is non-Sidon

(794 subsets in total);

• the seven-set

\[ \{0,97,161,227,374,534,547\} \] is Sidon.

Consequently

The discovery model used ordered integer variables \(0=a_0<\cdots<a_{11}\leq 5000\), exact AP indicator variables, an all-different constraint on sums of distinct pairs, at most one AP in every 4-set, and at least one AP in every 8-set. It required ten AP edges. The successful capped run took under 40 seconds wall time. The result does not depend on that solver: the standalone verification is an exhaustive exact-integer calculation using only Python's standard library.

This \(7/12\) ratio does not improve the current asymptotic upper bound \(4/7\); its value here is that it closes the lone gap in the explicit finite-order table.

Exact 15-point extension found in the update

Adjoin 1057 to Ma--Tang's 14-point block:

The updated dependency-free checker verifies directly from the live definitions (d):

• all \(\binom{15}{4}=1365\) quadruples have \(|B-B|\ge11\): the exact

histogram is 144 quadruples with 11 signed differences and 1221 with 13;

• all 105 sums of distinct pairs are different;
• the AP hypergraph has the same twelve edges as the 14-point block, so 1057

lies in no AP and the hypergraph remains linear;

• every one of the \(2^{15}=32768\) subsets passes through the direct Sidon

predicate; there are 143 Sidon nine-subsets and none of size at least ten;

• in particular, all \(\binom{15}{10}=3003\) ten-subsets are non-Sidon, while

\[ \{0,136,200,243,246,298,323,528,1057\} \] is Sidon.

Thus \(h(A_{15})=9\). On the other hand, (1) gives (b)

Therefore

An independent second checker evaluates the literal \(|B-B|\) predicate and the critical 10- and 9-subset layers via both the sum definition and the positive-distance formulation.

The 2026-08-12 live discussion still had seven comments and none mentioned this finite extension. The current Ma--Tang v2 TeX and companion repository contain the 14-point block but no 1057, f(15), or 15-point construction. This targeted miss is evidence about novelty, not a proof of priority.

Exact table through \(n=15\)

Here are explicit extremal sets used by the checker:

n= 1: {0}
n= 2: {0,97}
n= 3: {0,97,194}
n= 4: {0,97,161,194}
n= 5: {0,97,161,194,227}
n= 6: {0,97,161,194,227,322}
n= 7: {0,97,161,194,227,322,374}
n= 8: {0,97,161,194,227,322,454,547}
n= 9: {0,97,161,194,227,322,374,454,534}
n=10: {200,243,246,249,272,286,298,323,400,528}
n=11: {0,97,161,194,227,322,374,454,521,534,547}
n=12: {0,97,161,194,227,322,374,454,521,534,547,720}
n=13: {0,136,200,243,246,249,272,286,298,323,400,528,596}
n=14: {0,136,200,243,246,249,272,286,298,323,400,528,596,1056}
n=15: {0,136,200,243,246,249,272,286,298,323,400,528,596,1056,1057}

The \(n=10,13,14\) sets are subsets of the Ma–Tang 14-point block, the 15-point set is its new one-point extension, and the rest are subsets of the new 12-point block. The checker tests every construction directly.

Combining (1), the elementary \(n=5\) argument, and the exact construction checks gives:

Thus (b)+(d)

The lower half is rigorous modulo the named Gyárfás–Lehel \(F_7\)-freeness and Henning–Yeo transversal theorem (except the elementary \(n=5\) patch); the matching upper half is finite exhaustive computation.

Four scattered exact values beyond 15

The same lower bound and explicit separated unions give (a)+(b)+(d)

This does not require knowing \(f(16)\).

The elementary construction is as follows. For finite blocks \(X,Y\) with minimum zero, write \(D_X=\max X,D_Y=\max Y\), and let \(\delta_Y\) be the smallest positive gap of \(Y\). If

then \(qD_Y\ge q\delta_Y>D_X\), and the three pair-sum ranges are contained in

They are disjoint. Mixed sums are unique because

whose two sides cannot have the same nonzero magnitude. The same separation excludes mixed APs. Therefore the AP hypergraph is a disjoint union and the result is a \((4,5)\)-set. Any Sidon subset restricts to Sidon subsets of the two blocks, while the separated union of maximum witnesses is Sidon, so

Here are the four explicit integer sets, all using \(q=1000\):

n=17, A14+A3, t=195057:
{0,136,200,243,246,249,272,286,298,323,400,528,596,1056,
 195057,292057,389057}

n=24, A12+A12, t=720721:
{0,97,161,194,227,322,374,454,521,534,547,720,
 720721,817721,881721,914721,947721,1042721,1094721,1174721,
 1241721,1254721,1267721,1440721}

n=26, A14+A12, t=721057:
{0,136,200,243,246,249,272,286,298,323,400,528,596,1056,
 721057,818057,882057,915057,948057,1043057,1095057,1175057,
 1242057,1255057,1268057,1441057}

n=28, A14+A14, t=1057057:
{0,136,200,243,246,249,272,286,298,323,400,528,596,1056,
 1057057,1193057,1257057,1300057,1303057,1306057,1329057,
 1343057,1355057,1380057,1457057,1585057,1653057,2113057}

The integrated checker and a separately implemented audit verify every live quadruple, all distinct-element pair sums, the complete AP list with no mixed AP, exact component Sidon numbers, and direct full-sum witnesses. The second checker also exhausts all subsets of the 17-point union. Exact live-predicate histograms are:

The seven live comments, current Ma--Tang v2 TeX, companion checker, and targeted exact-value/coordinate searches did not mention these four finite equalities. They are straightforward consequences of published ingredients, so this is reported only as a search miss and an explicit audited corollary, not as a claim of priority.

Independent from-scratch \(n=7\) audit

As a check not using Henning–Yeo or \(F_7\)-freeness, the verifier completely enumerates the \(n=7\) obstruction (d).

If \(h(A)\leq4\), every five vertices of \(H(A)\) contain an edge. Midpoint injectivity allows at most one edge with each midpoint index \(j=1,\ldots,5\). The number of labelled choices, including “no edge” at a midpoint, is

Exact enumeration gives:

• 2,364 linear candidates;
• 48 linear candidates with independence number at most 4;
• every one of those 48 has five AP equations of exact rational rank 5;
• after normalizing \(a_0=0,a_6=1\), only four solutions are strictly

increasing.

The four normalized solutions and a forced weak-Sidon collision are:

So no seven-point \((4,5)\)-set has \(h\leq4\). This independently confirms \(f(7)\geq5\), while the displayed seven-point construction gives equality. All equation solving uses fractions.Fraction; there is no floating point.

Reproduction

Run:

python runs/erdos757_wave7k_reverify.py
python runs/erdos757_wave7k_a15_audit.py
python runs/erdos757_wave7k_concat_verify.py
python runs/erdos757_wave7k_concat_audit.py

The frozen publication bundle, including both checkers and recorded outputs, is in the verification/757/f15-exact directory of the site repository.

The four separated-union values have a second frozen bundle at verification/757/separated-values.

The standalone file is runs/erdos757_wave7k_reverify.py. It has no third-party dependencies. On this VM it completes in about 0.06 seconds and ends with:

PASS: all construction, table, arithmetic, and n=7 checks succeeded

The independent 15-point audit is runs/erdos757_wave7k_a15_audit.py. It implements the live difference-set predicate and the critical Sidon checks separately from the integrated checker.

The program recomputes rather than embeds:

1. every pair sum used in each Sidon test;
2. every distance in every four-subset, including all 1365 at order 15;
3. every largest-Sidon-subset value, including all 32768 subsets of \(A_{15}\);
4. the complete AP list of \(A_{12}\);
5. every floor and integer inequality in (1);
6. all 29,160 midpoint-labelled seven-point AP patterns; and
7. all rational ranks, normalized solutions, and weak-Sidon collisions.

What remains and the precise wall

This does not determine \(c_*\) and does not improve the current uniform interval

Finite values through 15 do not supply the missing asymptotic uniformity.

There are two concrete next targets:

1. Upper-bound target. By Ma–Tang's

\(c_*=\inf_n f(n)/n\), one finite block with \(h(A)/|A|<4/7\) improves the upper bound. Bound (1) rules out such a block at \(n=15\): the new construction attains its forced value \(h=9\), while strict asymptotic improvement would need \(h\leq8\). The first numerically possible order is \(n=16\), where a 16-point \((4,5)\)-set with \(h=9\) would give \[ c_*\leq\frac9{16}<\frac47. \] A direct integer model at \(n=16\) has 560 AP indicators, 120 distinct-pair sums, 1,820 four-set linearity constraints, and 8,008 ten-set covering constraints. A bounded-span pilot should be budgeted at roughly 1–10 core-hours; several bounds/seeds or a certificate-quality sweep would plausibly cost tens of core-hours. Such a bounded integer miss would still not prove nonexistence over all reals.

1. Lower-bound target. The exact missing lemma is a stronger transversal

inequality for ordered, arithmetically realizable AP hypergraphs, beyond the general \[ \tau(H)\leq\frac{8}{17}|V(H)|+O(1). \] To meet the existing \(4/7\) upper bound one would need, at minimum, \[ \tau(H(A))\leq\frac37|A|+o(|A|) \quad\text{or equivalently}\quad \alpha(H(A))\geq\frac47|A|-o(|A|). \] Linearity, midpoint injectivity, and \(F_7\)-freeness alone currently give only the Henning–Yeo coefficient. What is missing is an inequality that exploits the simultaneous ordered equations \(a_i+a_k=2a_j\), not merely the abstract hypergraph.

No conjectural extrapolation of the small table is used as a theorem.

PARTIAL: Exact finite table through 15, plus \(f(17)=10,f(24)=14,f(26)=15,f(28)=16\), with explicit integer blocks and dependency-free checkers; the asymptotic constant remains \(9/17\le c_*\le4/7\).