Erdős problem #790 — wave w015

Date: 2026-07-28 UTC

This report does not solve either asymptotic question. It gives an exact, unbounded computer-assisted determination of \(l(n)\) for \(n\leq 10\), and matching one-unit bounds for \(11\leq n\leq14\).

Claim labels

• [a] elementary-rigorous: proved below from elementary facts.
• [b] rigorous-modulo-named-theorem: uses the explicitly named published

theorem.

• [c] plausible/structural-unverified: a literature-search miss, proposed

reduction, or diagnosis rather than a theorem.

• [d] computational-only: an exact finite or symbolic computation,

independently recomputed by runs/erdos790_wavew015_reverify.py.

0. Mandatory live-page audit

[d: direct page observation] Before doing mathematics I fetched the live page through the Bright Data browser on 2026-07-28. I then followed its comment link and fetched the full discussion thread. The rendered page showed:

| live field | value | |---|---| | status | OPEN | | claimed proofs | 0 | | currently working | None | | interested in collaborating | None | | all other reaction/formalisation-worker rows | None | | comments | 1 | | last edit | 23 January 2026 |

The sole comment, by StijnC at 12:45 on 30 October 2025, points out that the Choi--Komlós--Szemerédi paper contains polylogarithmic improvements to both older bounds. The comment itself says the site was updated to incorporate this. It does not claim a proof and does not announce a current worker. Thus neither mandatory stop condition applied.

The source-copy limit permits only a short verbatim excerpt. The first part of the current statement is:

“Let \(l(n)\) be maximal such that if \(A\subset\mathbb Z\) with \(|A|=n\) then there exists a sum-free \(B\subseteq A\) with \(|B|\ge l(n)\)”

Here is an exact symbolic transcription of the complete live question. A finite \(B\subset\mathbb Z\) is called sum-free here when

for every choice of pairwise distinct \(b_1,\ldots,b_r\in B\). (A one-term right side cannot cause a violation because all terms are distinct, so the checker starts with two summands.) Define

The page asks for an estimate of \(l(n)\), and specifically whether

The live page lists these known results.

• [b] Erdős observed \(l(n)\geq\sqrt{n/2}\).
• [b] Choi improved this to \(l(n)>(1+c)\sqrt n\) for some absolute

\(c>0\).

• [b] Choi, Komlós and Szemerédi proved

\[ \sqrt{\frac{n\log n}{\log\log n}}\ll l(n) \ll \frac{n}{\log n}. \tag{3} \]

• [c: conjecture] They suggested \(l(n)\geq n^{1-o(1)}\).
• The page also links problem #876, concerning infinite sets with the same

arbitrary-length distinct-summand condition.

1. Primary-source literature check

I checked the following primary sources rather than relying on similarly titled work about the usual three-term equation \(x+y=z\).

1. [b] P. Erdős,

Extremal problems in number theory, Proc. Sympos. Pure Math. VIII (1965), 181--189. On p. 188 he defines the arbitrary-length distinct-summand function (there called \(g(n)\)) for finite sets of real numbers, proves the \(\sqrt{n/2}\) lower bound, and writes that “complicated arguments” give \(g(n)=o(n)\). The downloaded 11-page PDF had SHA-256 b2dc8978ca143027e8d5940211a71aaf69cde9f2d771499dad881d9fb27878ea.

1. [b] P. Erdős,

Problems and results on combinatorial number theory, in A Survey of Combinatorial Theory (1973), 117--138. On p. 130 he again gives the arbitrary-length definition, records Choi's \((1+c)\sqrt n\) improvement, and says he had difficulty reconstructing his claimed \(o(n)\) proof. The downloaded 22-page PDF had SHA-256 da5a584aa60527424b7deded98398f8ab359758a3a62ea5bf60e1f2f7d803a71.

1. [b] S. L. G. Choi, J. Komlós and E. Szemerédi,

On sum-free subsequences, Trans. Amer. Math. Soc. 212 (1975), 307--313, DOI 10.1090/S0002-9947-1975-0376594-1. Its abstract and Theorem (1.1) define exactly the integer-sequence problem and prove (3). Its final paragraph sketches possible iteration of the lower-bound method but explicitly omits the messy details; I do not promote that remark to a theorem. The downloaded seven-page PDF had SHA-256 104121039ab775129afa48f02ed91e85afafdee97d0d5740d630b6cbfefcd686.

[c: documented search miss] Exact-title, exact-phrase, DOI-citation and author/title searches did not locate a post-1975 primary source improving (3) for this exact arbitrary-length, distinct-summand problem. An OpenAlex forward-citation query for the 1975 DOI returned five indexed items: three editions of the book chapter Sequences of Integers, the 1977 Abbott--Wang paper, and a 2013 paper on random sum-free subsets of abelian groups. The latter two use the ordinary pair-sum notion and do not improve (3). Modern papers such as Eberhard--Green--Manners, arXiv:1301.4579 also concern \(x+y=z\), not (SF). This paragraph reports what the searches found; it is not a theorem that no unindexed improvement exists.

2. Exact finite progress

The result

Theorem [d, exact symbolic computation plus the elementary lemma below]. For the live-page formulation,

Moreover,

Zero is permitted by the authoritative statement \(A\subset\mathbb Z\); its use in the finite upper-bound examples is intentional.

Elementary lower bound through six elements

[a] Every set of at most two distinct integers is sum-free. The set \(\{-1,0,1\}\) is not, since \(0=(-1)+1\), so \(l(3)=2\).

The following supplies the next plateau without computation.

Lemma [a]. Every four distinct real numbers contain a sum-free triple.

Proof. Choose \(d\) of maximum absolute value and, after multiplying all four numbers by \(-1\) if needed, assume \(d>0\). Suppose every triple containing \(d\) were bad. For every pair \(x,y\) among the other three numbers, one of

would hold. After scaling by \(d\), every pair among three distinct points of \([-1,1]\setminus\{1\}\) would therefore satisfy

A point \(x\in[-1,0]\) has at most one neighbour in this relation: it is \(x+1\) (with the endpoint interpretation \(0\leftrightarrow-1\)). Thus a three-clique cannot contain a nonpositive point. But for three points in \((0,1)\), the difference alternative in (6) is impossible, while the equations \(x+y=x+z=1\) force \(y=z\). This is also impossible. Hence some triple containing \(d\) is sum-free. \(\square\)

[a] By heredity, every \(n\)-element set with \(n\geq4\) contains a sum-free triple. Together with the explicit examples checked below, this gives the values for \(4\leq n\leq6\).

Exact, unbounded seven-variable obstruction

The only non-elementary lower-bound step in (4) is:

Lemma [d]. Every seven distinct integers contain a sum-free four-element subset.

This is not a search in a bounded interval. Here is the exact decision performed by the standalone verifier.

1. Sort a hypothetical counterexample as

\(a_0<a_1<\cdots<a_6\).

1. A four-index set \(Q\) is bad precisely when it satisfies at least one

of 16 homogeneous equations: \[ a_t=\sum_{i\in S\setminus\{t\}}a_i, \qquad t\in S\subseteq Q,\quad |S|\in\{3,4\}. \tag{7} \] There are \(4\cdot3=12\) supported on triples and four supported on all of \(Q\).

1. A counterexample would satisfy the conjunction of these 16-way

disjunctions for all \(\binom74=35\) choices of \(Q\). Globally there are \[ 3\binom73+4\binom74=105+140=245 \] possible equation atoms.

1. The verifier branches on an unsatisfied clause and stores selected

equations in canonical reduced row-echelon form over \(\mathbb Q\). A relation already in the row space satisfies its clause; otherwise adding every possible relation is exhaustive.

1. Order feasibility is also exact. Put

\[ a_i=x_0+d_1+\cdots+d_i,\qquad d_j>0. \] Every row in (7) has nonzero coefficient sum, so one row eliminates \(x_0\), leaving \(Hd=0\). Normalize \(\sum d_j=1\). The rational polytope \[ P=\{d\geq0:Hd=0,\ \sum d_j=1\} \] contains a point with all coordinates positive iff, for every coordinate, some vertex of \(P\) is positive there; averaging those vertices proves the reverse implication. All possible vertex supports, of size at most \(\operatorname{rank}(H)+1\), are enumerated and solved with exact fractions.

If a real ordered solution to one branch existed, this rational polyhedral test would produce a rational one; clearing denominators would produce distinct ordered integers. Thus UNSAT over these exact rational branches is uniform over all integers, not merely over a chosen coordinate box.

The clean run closed UNSAT after 825 recursive calls (715 memoized states, 110 memo hits), examined 6,367 order-feasibility row spaces, and reached rank 6. The analogous four-variable search independently closes the elementary lemma above in five states.

[a+d] Choosing any seven elements of a larger set now gives \(l(n)\geq4\) for all \(n\geq7\). This proves the lower halves of (4) and (5).

Matching explicit obstructions

[d] For each row, the verifier finds the displayed-size sum-free witness and checks directly from (SF) that every subset of the next size is bad. By heredity, this certifies the stated maximum \(g(A)\).

| \(n\) | explicit \(A\) | certified \(g(A)\) | next-size subsets checked | |---:|---|---:|---:| | 3 | \([-1,1]\) | 2 | 1 | | 4 | \([-2,1]\) | 3 | 1 | | 5 | \([-2,2]\) | 3 | 5 | | 6 | \([-3,2]\) | 3 | 15 | | 7 | \([-3,3]\) | 4 | 21 | | 8 | \([-4,3]\) | 4 | 56 | | 9 | \([-4,4]\) | 4 | 126 | | 10 | \([-5,4]\) | 4 | 252 | | 11 | \([-5,5]\) | 5 | 462 | | 12 | \([-6,5]\) | 5 | 924 | | 13 | \([-7,5]\) | 5 | 1,716 | | 14 | \(\{-8,-7,-6,-5,-3,-2,-1,0,1,2,3,4,5,7\}\) | 5 | 3,003 |

The \(n=1,2\) cases are immediate. These rows give all upper bounds in (4)--(5).

3. What remains, precisely

The next finite question is already isolated:

[d] The report proves only \(4\leq l(11)\leq5\). Encoding the negation of (8) has \(\binom{11}{5}=462\) clauses. Each clause has

relation atoms, drawn from

global atoms, and possible row-space rank rises from 6 to 10. [d: diagnostic only] A 45-second bounded CP-SAT run at \(|a_i|\leq500\) returned UNKNOWN after about 1.08 million branches; such a bounded run would not prove (8) anyway. No full \(n=11\) symbolic run was attempted because its cost cannot responsibly be put within the requested few CPU-minutes without a new pruning lemma. The exact missing finite lemma is therefore (8), not a larger integer search box.

[c] None of the finite results changes the asymptotic gap (3). To answer the first question in (2), one still needs a uniform lower-bound gain \(\omega(\sqrt n)\); to answer the second, one needs a construction with polynomially sublinear maximum. The CKS dyadic-block/representation-tree machinery supplies the logarithmic factors in (3), but the paper's omitted iteration remark is not a proved uniform \(n^{1-o(1)}\) lower bound.

4. Reproduction

Run from the repository root:

python -u runs/erdos790_wavew015_reverify.py

The verifier uses only the Python standard library. The final clean run on this VM took 61.9 seconds, including the \(n=11,\ldots,14\) construction checks. It recomputes relation equations, RREFs, rational cone feasibility, all explicit subset certificates, (4), and (5) from scratch. Its SHA-256 is bcfa78ddad59cfbf16d1854e5952c8d19de4c18e220c3b0ccbbc5027a33bcde5.

PARTIAL: exact computer-assisted table \(l(1..10)=1,2,2,3,3,3,4,4,4,4\) and \(4\leq l(n)\leq5\) for \(11\leq n\leq14\); both asymptotic questions remain open.