Erdős problem #787 — wave 7l
Accessed 2026-07-27. Claim labels used below:
- (a) elementary-rigorous;
- (b) rigorous modulo the named theorem/source;
- (c) plausible/structural-unverified;
- (d) computational-only (including a finite exhaustive certificate).
0. Mandatory live-page check
I fetched the live problem page and its
discussion thread through a
Bright Data browser, not datacenter curl.
Verbatim live statement:
> Let \(g(n)\) be maximal such that given any set \(A\subset \mathbb{R}\) with
> \(\lvert A\rvert=n\) there exists some \(B\subseteq A\) of size
> \(\lvert B\rvert\geq g(n)\) such that \(b_1+b_2\not\in A\) for all
> \(b_1\neq b_2\in B\).
>
> Estimate \(g(n)\).
The page said:
- OPEN; last edited 23 January 2026.
- 0 claimed proofs.
- Currently working on this problem: None.
- Interested in collaborating: None.
- Choi observed that one may assume \(A\subset\mathbb Z\).
- Klarner proved \(g(n)\gg\log n\).
- Choi proved \(g(n)\ll n^{2/5+o(1)}\).
- The displayed current bounds are
\[ (\log n)^{1+c}\ll g(n)\ll \exp(\sqrt{\log n}) \]
for an absolute \(c>0\), attributed respectively to Sanders and Ruzsa.
- The page additionally records Beker's
\[ (\log n)^{1+1/68+o(1)}\ll g(n). \]
These are (b), page-reported claims. The stop condition was therefore not
triggered.
I also read all five comments. In summary (comments themselves are explicitly
unverified by the site):
1. qawsed objected that “estimate” is not a yes/no conjecture; the site was
subsequently edited.
2. Nat Sothanaphan discussed the ambiguity of what “solved” should mean for an
estimation problem.
3. Woett noted Choi's reduction to integer sets; the site was subsequently
edited.
4. Thomas Bloom said that the intended resolution threshold is the right order
of growth, perhaps up to lower-order terms.
5. Alfaiz pointed to the 2005 Sudakov–Szemerédi–Vu paper as the first
superlogarithmic lower bound. Its link resolves to the authors' PDF.
No comment contains a claimed proof, a current-worker marker, or a claim that
the problem has been solved or falsified.
1. Primary-source literature check
- (b) Sudakov, Szemerédi and Vu, On a question of Erdős and Moser,
Duke Math. J. 129 (2005), 129–155,
DOI 10.1215/S0012-7094-04-12915-X.
The abstract and Theorem 1.1 state a lower bound \(h(n)\log n\), where
\(h(n)\to\infty\), and the paper gives an iterated-log quantitative form.
This verifies the substance of Alfaiz's comment.
- (b) Tom Sanders, The Erdős–Moser sum-free set problem,
Canad. J. Math. 73 (2021), 63–107,
DOI 10.4153/S0008414X1900049X.
The abstract states that every finite integer set \(A\) has a qualifying
subset of size at least \(\log^{1+c}|A|\) for an absolute \(c>0\).
- (b) Adrian Beker, *The Erdős–Moser sum-free set problem via improved
bounds for \(k\)-configurations*,
Theorem 1.2 says precisely that, for every fixed \(c<1/68\) and all
sufficiently large finite \(A\subset\mathbb Z\), there is a qualifying
\(B\) of size at least \((\log|A|)^{1+c}\). Thus the endpoint notation on
the live page should be read in the usual \(1+1/68-o(1)\) sense.
- (b) Imre Ruzsa, Sum-avoiding subsets, Ramanujan J. 9 (2005), 77–82,
DOI 10.1007/s11139-005-0826-4.
The DOI, bibliographic data, and abstract exist. The full Springer text was
paywalled in this run, so I did not pretend to inspect it. The primary SSV
paper above explicitly reproduces Ruzsa's lattice-ball construction and
records its \(\exp(O(\sqrt{\log n}))\) upper bound.
- (b) S. L. G. Choi, On a Combinatorial Problem in Number Theory,
Proc. London Math. Soc. s3-23 (1971), 629–642,
The journal metadata exists, but the article was paywalled. The later
primary SSV paper records both Choi's integer reduction and his
\(n^{2/5+o(1)}\) construction.
Targeted searches for the exact problem name and “sum-avoiding” in 2025–2026
found Beker's preprint but no later primary source improving the asymptotic
bounds. This is a search miss, not a claim that no such paper can exist. I
also found no primary source tabulating the exact small values below, so I make
no novelty claim.
2. Finite formulation
For finite \(A\subset\mathbb R\), put
\[ \phi(A)=\max\{|B|:B\subseteq A,\ b+b'\notin A \text{ for all distinct }b,b'\in B\}. \]Then
\[ g(n)=\min_{\substack{A\subset\mathbb R\\|A|=n}}\phi(A). \tag{1} \]This equivalence is (a).
The concrete output of this run is the following exact table:
\[ \boxed{ \begin{array}{c|c} n&g(n)\\ \hline 1\le n\le3&1\\ 4\le n\le7&2\\ 8\le n\le13&3\\ 14\le n\le19&4 \end{array}} \tag{2} \]The bounds through \(n=13\) have short elementary proofs. The threshold at
\(n=14\) uses the complete 32,768-case certificate in §4. Accordingly, (2)
is (d), exact finite exhaustive, rather than an asymptotic theorem.
3. Universal lower bounds
3.1 The thresholds \(4\) and \(8\)
Claim 1 (a). If \(|A|\ge4\), then \(\phi(A)\ge2\).
If every distinct pair in \(A\) had its sum in \(A\), then \(A\) could have at
most one positive element: the largest positive plus another positive exceeds
the largest positive. Similarly it could have at most one negative element,
and of course at most one zero. Hence \(|A|\le3\), a contradiction.
Claim 2 (a). Four positive elements of a finite \(A\subset\mathbb R\)
contain three elements whose distinct pair sums avoid \(A\), provided they are
the four largest positive elements of \(A\).
Write those four as \(0 exceeds the largest positive element and is outside \(A\). The two sums \(x_1+x_3\) and \(x_2+x_3\), if in \(A\), would both have to equal \(x_4\); that would imply \(x_1=x_2\). Thus one of these pairs, together with \(x_4\), is a qualifying triple. Negating gives the same result for four negative elements (choose the four of greatest magnitude). Consequently, if \(\phi(A)\le2\), each sign class has size at most three and there is at most one zero. Therefore \(|A|\le7\), so (a) Lemma 3 (d, complete finite exhaustive). Every seven positive reals contain four whose distinct pair sums avoid the seven-element ambient set. Here is the elementary (a) reduction to a finite graph check. Let \(k>j\). For each possible witness \(k=2,\ldots,6\), define3.2 Seven same-sign elements
It is also nested: if \((a,b),(c,d)\in M_k\), with each pair increasingly
ordered and \(a \(b>d\). Thus every actual sum graph is the union of one nested matching on \(\{0,\ldots,k-1\}\) for each \(k=2,\ldots,6\). The numbers of such matchings are respectively The standalone verifier generates all unions from scratch and checks all vertex subsets. Its independence-number histogram is In particular every union has an independent four-set. Because the enumeration includes some mutually incompatible matching choices as well as all realizable choices, this is a safe over-enumeration. If \(A\) has at least seven positive elements, apply the lemma to its seven largest positives. A sum of two selected elements is larger than both, so if it is in \(A\), it is still among those seven. The negative case follows by negation, using the seven negatives of greatest magnitude. Hence, if \(\phi(A)\le3\), each sign class has size at most six and there is at most one zero. Therefore (d), via Lemma 3 Equations (3) and (5), together with Claim 1, supply every lower bound in (2). The following integer sets give the reverse inequalities. Interval notation means all integers in the interval. | \(n\) | claimed \(g(n)\) | witness \(A_n\) with \(\phi(A_n)=g(n)\) | |---:|---:|:---| | 1 | 1 | \(\{0\}\) | | 2 | 1 | \(\{0,1\}\) | | 3 | 1 | \(\{-1,0,1\}\) | | 4 | 2 | \(\{-1,0,1,2\}\) | | 5 | 2 | \([-2,2]_{\mathbb Z}\) | | 6 | 2 | \(\{-3,-2,-1,1,2,3\}\) | | 7 | 2 | \([-3,3]_{\mathbb Z}\) | | 8 | 3 | \([-4,3]_{\mathbb Z}\) | | 9 | 3 | \([-4,4]_{\mathbb Z}\) | | 10 | 3 | \([-5,4]_{\mathbb Z}\) | | 11 | 3 | \([-5,5]_{\mathbb Z}\) | | 12 | 3 | \(\{-7,-6,-5,-2,-1,0,1,2,3,4,5,7\}\) | | 13 | 3 | \(\{-7,-5,-4,-3,-2,-1,0,1,2,3,4,5,7\}\) | | 14 | 4 | \([-7,6]_{\mathbb Z}\) | | 15 | 4 | \([-7,7]_{\mathbb Z}\) | | 16 | 4 | \(\{-9,-8,-7,-6,-3,-2,-1,0,1,2,3,4,5,6,7,9\}\) | | 17 | 4 | \(\{-9,-8,-7,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,9\}\) | | 18 | 4 | \(\{-11,-10,-9,-7,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,11\}\) | | 19 | 4 | \(\{-11,-8,-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,11\}\) | These are (d), exact brute-force checks: for every row the verifier visits subsets in decreasing cardinality, tests every distinct pair, and returns both the exact maximum and a maximizing \(B\). It does not trust a stored list of independent subsets. Standalone file: SHA-256 at the time of this report: Run: Observed output: The full source is: This does not narrow the asymptotic gap, so it does not solve the live problem. At the finite frontier, \(n=20\) is the first value not decided here: one needs either a 20-element witness with \(\phi(A)=4\), or a universal proof that every 20-element real set has a qualifying five-set. Sign splitting alone cannot settle that value. For comparison, the direct nested-matching over-enumeration for eleven same-sign elements (the next analogous five-set lemma) has patterns. At the measured rate of this pure-Python verifier, naïve enumeration would cost roughly 60 core-years (about \$20,000 at \$0.04/core-hour), so I did not run it. Strong branch pruning or a compact independently checkable SAT certificate would be needed. Even that finite lemma would only force a five-set from \(22\) arbitrary reals by sign splitting; it would not settle \(n=20,21\), much less the asymptotic problem. The asymptotic wall remains the one visible in the primary literature: the lower-bound side needs substantially stronger quantitative control of the configuration/structure step than Sanders or Beker presently provides, while the upper-bound side needs a construction beating Ruzsa's \(\exp(O(\sqrt{\log n}))\) scale. This diagnosis is (b) as to the published bounds and (c) as to which future route will succeed. PARTIAL: Exact, from-scratch computer-certified values are \(g(n)=1,2,3,4\) on \(n=1\!-\!3,4\!-\!7,8\!-\!13,14\!-\!19\), respectively; the asymptotic problem remains open.4. Matching constructions
5. Reverification
runs/erdos787_wave7l_reverify.py1b567bd424cba6e2e47d04bbc4ecbc20b50713074f1e9cc6755cf79ec979d28a
python runs/erdos787_wave7l_reverify.py
nested-matching choice counts: (2, 4, 8, 16, 32)
patterns checked: 32768
independence-number histogram: {4: 8153, 5: 22763, 6: 1851, 7: 1}
n phi(A_n) one maximizing B
1 1 (0,)
2 1 (0,)
3 1 (-1,)
4 2 (1, 2)
5 2 (-2, -1)
6 2 (-3, -2)
7 2 (-3, -2)
8 3 (-4, -3, -2)
9 3 (-4, -3, -2)
10 3 (-5, -4, -3)
11 3 (-5, -4, -3)
12 3 (-7, -6, -5)
13 3 (-7, -5, -4)
14 4 (-7, -6, -5, -4)
15 4 (-7, -6, -5, -4)
16 4 (-9, -8, -7, -6)
17 4 (-9, -8, -7, -5)
18 4 (-11, -10, -9, -7)
19 4 (-11, -8, -7, -6)
All assertions passed.
#!/usr/bin/env python3
from collections import Counter
from functools import lru_cache
from itertools import combinations, product
CONSTRUCTIONS = {
1: (0,), 2: (0, 1), 3: (-1, 0, 1), 4: (-1, 0, 1, 2),
5: tuple(range(-2, 3)), 6: (-3, -2, -1, 1, 2, 3),
7: tuple(range(-3, 4)), 8: tuple(range(-4, 4)),
9: tuple(range(-4, 5)), 10: tuple(range(-5, 5)),
11: tuple(range(-5, 6)),
12: (-7, -6, -5, -2, -1, 0, 1, 2, 3, 4, 5, 7),
13: (-7, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 7),
14: tuple(range(-7, 7)), 15: tuple(range(-7, 8)),
16: (-9, -8, -7, -6, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 9),
17: (-9, -8, -7, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 9),
18: (-11, -10, -9, -7, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 11),
19: (-11, -8, -7, -6, -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 11),
}
def expected_g(n):
return 1 if n <= 3 else 2 if n <= 7 else 3 if n <= 13 else 4
def is_sum_avoiding(subset, ambient):
ambient = set(ambient)
return all(x + y not in ambient for x, y in combinations(subset, 2))
def exact_phi(ambient):
for size in range(len(ambient), 0, -1):
for subset in combinations(ambient, size):
if is_sum_avoiding(subset, ambient):
return size, subset
raise AssertionError
@lru_cache(maxsize=None)
def all_matchings(vertices):
vertices = tuple(vertices)
if not vertices:
return ((),)
first = vertices[0]
output = list(all_matchings(vertices[1:]))
for position, mate in enumerate(vertices[1:]):
rest = vertices[1:position + 1] + vertices[position + 2:]
for matching in all_matchings(rest):
output.append(((first, mate),) + matching)
return tuple(output)
def is_nested_matching(matching):
for edge_1, edge_2 in combinations(matching, 2):
a, b = sorted(edge_1)
c, d = sorted(edge_2)
if c < a:
a, b, c, d = c, d, a, b
if not (a < c and b > d):
return False
return True
def graph_independence_number(number_of_vertices, edges):
edges = {tuple(sorted(edge)) for edge in edges}
vertices = tuple(range(number_of_vertices))
for size in range(number_of_vertices, 0, -1):
for subset in combinations(vertices, size):
if all(tuple(sorted(edge)) not in edges
for edge in combinations(subset, 2)):
return size
raise AssertionError
def verify_seven_positive_lemma():
choices = []
for witness_index in range(2, 7):
nested = tuple(m for m in all_matchings(tuple(range(witness_index)))
if is_nested_matching(m))
choices.append(nested)
counts = tuple(map(len, choices))
assert counts == (2, 4, 8, 16, 32)
histogram = Counter()
for matchings_by_witness in product(*choices):
edges = set()
for matching in matchings_by_witness:
edges.update(tuple(sorted(edge)) for edge in matching)
alpha = graph_independence_number(7, edges)
assert alpha >= 4
histogram[alpha] += 1
assert sum(histogram.values()) == 32768
assert histogram == Counter({4: 8153, 5: 22763, 6: 1851, 7: 1})
return counts, histogram
def verify_constructions():
table = []
for n in range(1, 20):
ambient = CONSTRUCTIONS[n]
assert len(ambient) == len(set(ambient)) == n
phi, example = exact_phi(ambient)
assert phi == expected_g(n)
table.append((n, phi, example))
return table
def main():
counts, histogram = verify_seven_positive_lemma()
table = verify_constructions()
print("nested-matching choice counts:", counts)
print("patterns checked:", sum(histogram.values()))
print("independence-number histogram:", dict(sorted(histogram.items())))
print("\n n phi(A_n) one maximizing B")
for n, phi, example in table:
print(f"{n:2d} {phi:8d} {example}")
print("\nAll assertions passed.")
if __name__ == "__main__":
main()
6. Exact remaining wall