Erdős Problem #787

Problem 787

1) ROUND-2 OBJECTIVE

Path (C): correct the quantitative landscape and isolate a genuine obstruction. The most important Round-2 issue here is that Round 1 stated the upper-bound side incorrectly. The best current upper bound is not Choi's historical $n^{2/5+o(1)}$ bound, but Ruzsa's much smaller stretched-exponential construction. This changes the shape of the open problem in a mathematically substantive way.

2) Round-1 FOUNDATION USED

I use the following Round-1 work as fixed:

1. the graph reformulation of $g(n)$ as an extremal independence problem;
2. the proved lower bound \[ g(n) \ge H_{\lfloor n/2 \rfloor} \gg \log n; \]
3. the small-$n$ computations, which were sanity checks only.

3) NEW INSIGHT / TOOL (ROUND-2)

The new ingredient is a correction of the upper-bound literature. The current 2026 problem page and the 2016 Tao--Vu discussion of sum-avoiding sets both record that examples are known with \[ g(n) \le \exp\!\left(O(\sqrt{\log n})\right). \] Thus the true present gap is \[ (\log n)^{1+1/68+o(1)} \ll g(n) \ll \exp\!\left(O(\sqrt{\log n})\right), \] not a polylogarithmic lower bound versus a polynomial upper bound.

A sharp obstruction follows immediately: no proof strategy can possibly show a fixed positive-power lower bound $g(n) \ge n^\delta$ for any constant $\delta>0$.

4) ATTACK PLAN (ROUND-2)

The exact Round-1 gap was a wrong statement of the best known upper bound. I will:

1. replace the outdated upper bound by the correct Ruzsa upper bound;
2. deduce a rigorous obstruction theorem ruling out every fixed positive-power lower bound;
3. restate the open problem in its corrected asymptotic regime.

5) WORK (ROUND-2)

Let $g(n)$ be as in the problem statement.

Corrected current bounds.

The current literature record gives \[ (\log n)^{1+1/68+o(1)} \ll g(n) \ll \exp\!\left(O(\sqrt{\log n})\right). \] Here the lower bound is due to Sanders and Beker, while the upper bound is due to Ruzsa. In particular, the Round-1 sentence claiming that the best upper bound was $n^{2/5+o(1)}$ was false: that is only a historical bound of Choi and is far from the current state of the art.

Proposition 787.1 (polynomial lower bounds are impossible).

For every fixed $\delta>0$, one has \[ g(n) < n^{\delta} \] for all sufficiently large $n$.

Proof.

By the corrected upper bound there is a constant $C>0$ such that \[ g(n) \le \exp\!\left(C\sqrt{\log n}\right) \] for all large $n$. But \[ \exp\!\left(C\sqrt{\log n}\right) = \exp\!\left(\frac{C}{\sqrt{\log n}} \log n\right) = n^{C/\sqrt{\log n}}. \] Since $C/\sqrt{\log n} \to 0$, for any fixed $\delta>0$ we eventually have $C/\sqrt{\log n} < \delta$, and hence \[ g(n) \le n^{C/\sqrt{\log n}} < n^{\delta}. \] This proves the claim. $\square$

Consequences.

The live problem is therefore to narrow the gap between a super-logarithmic lower bound and a stretched-exponential upper bound. Any argument aiming for $g(n)$ of polynomial order is ruled out by Proposition 787.1.

6) ADVERSARIAL VERIFICATION

1. The only nontrivial deduction here is Proposition 787.1, and it is a direct asymptotic comparison: $\exp(C\sqrt{\log n}) = n^{o(1)}$.
2. There is no clash with the Round-1 lower bound, because \[ (\log n)^{1+1/68+o(1)} = o\!\left(\exp\!\left(C\sqrt{\log n}\right)\right). \]
3. The correction is essential: replacing $n^{2/5+o(1)}$ by $\exp(O(\sqrt{\log n}))$ changes the entire plausible range of conjectures.
4. Choi's bound is not being denied; it is simply superseded by Ruzsa's stronger construction.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The strict advance is the correction of a concrete Round-1 error. The correct current state is \[ (\log n)^{1+1/68+o(1)} \ll g(n) \ll \exp\!\left(O(\sqrt{\log n})\right), \] and therefore $g(n)=n^{o(1)}$ on the upper-bound side. This rules out an entire class of proof strategies, namely any attempt to prove a fixed positive-power lower bound.

8) COMPLETION ESTIMATE

COMPLETION: 45%

9) REFERENCES

References

• [Ruzsa787] I. Z. Ruzsa, Sum-Avoiding Subsets, Ramanujan J. 9 $2005$, 77--82.
• [Sanders787] T. Sanders, The Erdős--Moser sum-free set problem, Canad. J. Math. 73 $2021$, 63--107.
• [Beker787] A. Beker, The Erdős--Moser sum-free set problem via improved bounds for $k$-configurations, arXiv:2501.10203 $2025$.
• [TaoVu787] T. Tao and V. Vu, Sum-avoiding sets in groups, Discrete Analysis 2016:15; see also the editorial introduction for the summary of the known integer-case bounds.
• [Bloom787] T. F. Bloom, Erdős Problem #787, updated January 2026, https://www.erdosproblems.com/787.

Erdős Problem #787: independent continuation

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

1) OBJECTIVE

For a finite real set $A$, seek a large subset $B$ for which $x+y\notin A$ whenever $x,y\in B$ are distinct. The supplied file updates general bounds but does not exploit extra information about the particular input set. Here is a quantitative result for sets of small additive energy.

2) ENERGY CERTIFICATE

Let $n=|A|$ and \[ r(s)=|\{(x,y)\in A^2:x+y=s\}|,\qquad E(A)=\sum_s r(s)^2. \] Form a simple graph on $A$, joining distinct $x,y$ when $x+y\in A$. Its independent sets are precisely the required subsets. If it has $M$ edges, then \[ 2M\le\sum_{s\in A}r(s)\le\sqrt{nE(A)}. \tag{1} \] The first inequality allows the diagonal pairs, and the second is Cauchy--Schwarz. Choose a uniformly random ordering of the vertices and keep each vertex appearing before all its neighbours. The retained vertices form an independent set, and a vertex of degree $d$ is kept with probability $1/(d+1)$. Therefore some independent set has size at least \[ \sum_{x\in A}\frac1{d(x)+1}\ge\frac{n^2}{n+2M} \ge\boxed{\frac{n^2}{n+\sqrt{nE(A)}}}. \tag{2} \] The middle inequality is again Cauchy--Schwarz. In particular, if $E(A)\le K n^2$, then \[ |B|\ge\frac{\sqrt n}{\sqrt K+n^{-1/2}}. \] All these bounds allow rounding up, since $|B|$ is integral.

3) SCOPE AND FAILURE IN THE WORST CASE

The proof applies to negative numbers and zero as well as positive numbers. It correctly excludes loops: the definition only forbids sums of distinct elements. It supplies a polynomial-size subset when the energy is quadratic. For energy of order $n^3$, however, $2$ may give only a constant; it therefore does not improve the universal bounds discussed in the source. A missing ingredient is a way to treat high-energy sets without sacrificing their additive structure.

7) FINAL

UNRESOLVED. This is a self-contained sufficient estimate for a restricted regime, not a new general asymptotic bound or a novelty claim about the standard graph argument. Problem statement checked against https://www.erdosproblems.com/787.

8) COMPLETION ESTIMATE

COMPLETION: 10% 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 787

1. Formal restatement

For a finite set $A\subset\mathbb{R}$, define $\varphi(A)$ to be the largest integer $m$ such that $A$ contains distinct elements $b_1,\dots,b_m$ with \[ b_i+b_j\notin A\qquad\text{for all }1\le i<j\le m. \] Let \[ g(n)\coloneqq \min\{\varphi(A): A\subset\mathbb{R},\ |A|=n\}. \] Estimate the growth of $g(n)$.

2. Quick literature/context check

The statement records the following (we list them only as context).

• A greedy algorithm gives $g(n)\gg \log n$.
• (Choi) $g(n)\ge \log_2 n$.
• (Ruzsa, unpublished) $g(n)>2\log_3 n-1$.
• (Sudakov--Szemerédi--Vu) $g(n)$ is superlogarithmic.
• Best known upper bound (Ruzsa): $g(n)<\exp(\sqrt{\log n})$.
• (Sanders) $g(n)\ge (\log n)^{1+c}$ for some $c>0$.
• (Beker) the exponent can be taken to be $1+\tfrac{1}{68}$.

3. Attack plan

1. Reinterpret the problem as an independent-set problem in a "sum graph" on $A$.
2. Prove at least logarithmic lower bounds by bounding degrees in a suitable induced sum graph (e.g., on the positive elements), then apply a standard independent-set lower bound such as Caro--Wei.
3. For upper bounds, search for constructions of $A$ with very large additive energy so that many pairwise sums stay inside $A$, shrinking $\varphi(A)$. (This is the hard direction and uses additive-combinatorial machinery in the best known results.)
4. As a computational reality check for small $n$, brute-force over $A\subset[-M,M]\cap\mathbb{Z}$ and compute $\varphi(A)$ by exhaustive search.

4. Work

4.1. A clean $\boldsymbol{\gg\log n}$ lower bound via Caro--Wei

The following argument is essentially the one recorded in the Tao--Vu survey on sum-free sets.

4.2. Small computational reality check

For small $n$ one can brute-force over $A\subset[-M,M]\cap\mathbb{Z}$ and compute $\varphi(A)$ by checking all subsets $B\subset A$. For $M=10$ this search returns the following minima for $n\le 7$: \[ g(2)=1,\quad g(3)=1,\quad g(4)=2,\quad g(5)=2,\quad g(6)=2,\quad g(7)=2. \] (These match the general lower bound $g(n)\ge H_{\lfloor n/2\rfloor}$, which is $\ge 2$ for $n\ge 4$.)

5. Verification

• Proposition Proposition (Logarithmic lower bound) is self-contained and yields the promised $\gg\log n$ growth.
• The computational check is consistent with the theorem for small $n$ (it is not a proof for general $n$).

6. FINAL

UNRESOLVED.

Fail-safe (required):

1. Strongest partial results proved here. A clean logarithmic lower bound $g(n)\ge H_{\lfloor n/2\rfloor}\sim \log n$ (Proposition Proposition (Logarithmic lower bound)).
2. First gap that blocks a full solution. We do not prove any superlogarithmic lower bound, nor do we reproduce Ruzsa-type constructions giving subpolynomial upper bounds such as $\exp(\sqrt{\log n})$.
3. What would close the problem. Either (a) a matching upper bound construction showing $g(n)\le (\log n)^{1+o(1)}$ or similar, or (b) a proof that $g(n)$ grows faster than any fixed power of $\log n$ (together with a best-possible rate).
4. Why computations didn't settle it. Brute force only accesses tiny $n$ and cannot detect the asymptotic regime where superlogarithmic behavior appears.

7. COMPLETION ESTIMATE

30%. A baseline $\log n$ lower bound is proved, but the true growth rate remains open.