Erdős problem #789 — wave w015

Date: 2026-07-28 UTC

Claim labels

• [a] elementary-rigorous: proved below without an external theorem.
• [b] rigorous-modulo-named-theorem: the deduction is rigorous assuming the

cited theorem.

• [c] plausible/structural-unverified: explicitly not claimed as a theorem.
• [d] computational-only: an exact finite or symbolic computation, with the

complete independent verifier in runs/erdos789_wavew015_reverify.py.

0. Mandatory live-page check

[d: live-page observation] I fetched <https://www.erdosproblems.com/789> through the Bright Data browser on 2026-07-28 and also captured a full-page screenshot. The rendered page said OPEN.

The current statement, copied verbatim from the page's LaTeX view, is:

Let $h(n)$ be maximal such that if $A\subseteq \mathbb{Z}$ with $\lvert A\rvert=n$ then there is $B\subseteq A$ with $\lvert B\rvert \geq h(n)$ such that if $a_1+\cdots+a_r=b_1+\cdots+b_s$ with $a_i,b_i\in B$ then $r=s$.

Estimate $h(n)$.

The page's listed known results, also copied verbatim, are:

Erd\H{o}s \cite{Er62c} proved $h(n) \ll n^{5/6}$. Straus \cite{St66} proved $h(n) \ll n^{1/2}$. Erd\H{o}s noted the bound $h(n)\gg n^{1/3}$, taking \[ > B=\{ a: \{ \alpha a\} \in n^{-1/3}+\tfrac{1}{2} > (-n^{-2/3},n^{-2/3})\} > \] for a random $\alpha\in [0,1]$. \cite{Er62c} and Choi \cite{Ch74b} improved this to $h(n) \gg (n\log n)^{1/3}$.

See also [186] and [874].

The status panel showed:

| live-page field | value | |---|---:| | comments | 0 | | claimed proofs | 0 | | interested in collaborating | None | | currently working on this problem | None | | formalised statement? | Yes |

Thus no stop condition applied.

1. Convention audit: these are distinct-element subset sums

The displayed statement is terse about repetition. The cited results determine the intended convention.

[a] If repetitions were allowed, any two distinct positive integers $x,y$ would give

with different numbers of terms. Taking $A$ positive would force $h(n)\leq 1$, contradicting the live page's lower bound $h(n)\gg(n\log n)^{1/3}$. Hence “sums formed from the elements” must mean sums of distinct elements, i.e. nonempty subset sums.

[d] This is independently confirmed by the Lean formalisation linked from the live page: it quantifies over nonempty finite subsets $S,T\subseteq B$.

[b: Deshouillers--Freiman 1999, definition] The primary paper “On an additive problem of Erdős and Straus, 2” explicitly says “pairwise distinct elements” and calls such a set admissible. All work below uses this standard subset-sum meaning.

There is one small but important formulation difference. Choi's 1974 abstract speaks of nonzero integers, whereas the authoritative live statement and its linked Lean formulation allow $0$. The exact table below is for the live-page formulation, so its use of zero is intentional.

2. Literature check

Sources actually verified

1. [d: bibliographic verification] S. L. G. Choi,

“On an extremal problem in number theory,” Journal of Number Theory 6 (1974), 105–111, DOI 10.1016/0022-314X(74)90048-190048-1), exists. The publisher abstract defines the same arbitrary-$n$-element-set function $h(n)$ (for nonzero integers) and says the paper refines Erdős's lower bound. I do not infer a formula hidden by the publisher's broken math rendering; the live page is the source used for $(n\log n)^{1/3}\ll h(n)$.

1. [d: primary-source verification] Erdős's 1973 survey

Problems and results in combinatorial number theory states the arbitrary-set definition, attributes the square-root upper bound to Straus, and announces Choi's $(n\log n)^{1/3}$ lower bound.

1. [b: Deshouillers--Freiman 1999, Theorem 1] J.-M. Deshouillers and

G. A. Freiman, “On an additive problem of Erdős and Straus, 2”, Astérisque 258 (1999), 141–148, prove that for all sufficiently large $N$, every admissible $C\subseteq[1,N]$ satisfies \[ |C|\leq 2\sqrt{N+\tfrac14}-1. \] Their introduction states that this proves Erdős's conjecture that a terminal interval is extremal in $[1,N]$. Their earlier paper is J.-M. Deshouillers and G. A. Freiman, “On an additive problem of Erdős and Straus, 1,” Israel J. Math. 92 (1995), 33–43, DOI 10.1007/BF02762069, whose abstract gives the preceding $(2+o(1))\sqrt N$ bound.

1. [b: immediate consequence of item 3] Taking the ambient $n$-element

set to be $[1,n]$ gives the sharpened known obstruction \[ h(n)\leq \left\lfloor 2\sqrt{n+\tfrac14}-1\right\rfloor \qquad(n\geq N_0). \] This improves the constant in the page's $h(n)\ll\sqrt n$ statement but does not improve its exponent.

Search miss

[c] Exact-title, exact-definition, DOI, and citation searches found the 1974 Choi paper and the 1995/1999 interval-extremal papers, but no primary source improving the arbitrary-ambient-set gap

This is only an honest search report, not a claim that no such paper exists. No arXiv identifier is asserted for any of the older papers.

3. Definitions and elementary reductions

Call a finite set $B$ admissible when, for all nonempty $S,T\subseteq B$,

Let

Then the live-page definition is equivalently

[a] Heredity. Every subset of an admissible set is admissible.

[a] Monotonicity. $h(n+1)\geq h(n)$. Indeed, delete one element of an arbitrary $(n+1)$-set and apply the definition of $h(n)$ to the remaining $n$-set.

[a] Two-element fact. Two distinct nonzero integers form an admissible pair. The only possible unequal-cardinality collisions among $\{x\},\{y\},\{x,y\}$ reduce to $x=0$ or $y=0$.

[a] Bad-triple characterisation. A triple of distinct integers is bad if and only if at least one of the following holds:

1. one element is $0$;
2. two elements sum to $0$;
3. one element is the sum of the other two.

This follows by listing comparisons of nonempty subsets of sizes $1,2,3$ and cancelling their intersection.

4. A uniform five-nonzero lemma

Lemma [a]. Every five distinct nonzero integers contain an admissible triple.

Proof. If four of the five have the same sign, multiply by $-1$ if necessary and write four positive ones as $p<q<r<s$. A bad all-positive triple $x<y<z$ must satisfy $x+y=z$. If all four triples were bad, then in particular $\{p,q,r\}$ and $\{p,q,s\}$ would give both $p+q=r$ and $p+q=s$, impossible.

It remains to treat a $3+2$ sign split. After a global sign change, write the positive elements as $0<a<b<c$ and the negative elements as $-u,-v$, where $0<u<v$. If $\{a,b,c\}$ is bad, then necessarily $a+b=c$.

For $0<x<y$ and $w>0$, the bad-triple characterisation says that $\{x,y,-w\}$ is bad exactly when

If there were no admissible triple, each of $u,v$ would therefore belong to

Hence $\{u,v\}=\{a,b\}$. But $\{c,-a,-b\}$ has no zero, no opposite pair, and no element equal to the sum of the other two, so it is admissible, a contradiction. ∎

[a] Consequence. Every six-element integer set has an admissible triple: discard its possible zero, leaving at least five nonzero elements, and apply the lemma. Thus $h(6)\geq3$.

5. A global exact symbolic lemma

Lemma [d]. Every six distinct positive integers contain an admissible four-element subset.

This is not a bounded search. The verifier performs the following exhaustive symbolic decision:

1. Sort hypothetical values as $0<x_1<\cdots<x_6$.
2. For each of the $\binom64=15$ quadruples, generate directly from the

definition every equation obtained by equating two nonempty subset sums of different cardinalities. After canonicalisation there are 30 possible homogeneous integer hyperplanes per quadruple.

1. Ask whether all 15 clauses (“at least one bad hyperplane holds”) can be

true simultaneously.

1. Maintain chosen equalities in exact rational reduced row-echelon form.
2. Test intersection of each equality space with the strict positive order

cone using an exact, dependency-free Fourier–Motzkin eliminator. Homogeneity lets the strict gaps be scaled to $x_1\geq1$ and $x_{i+1}-x_i\geq1$.

The complete search closes UNSAT after 57 exact backtracking states. Since it is infeasible even over the reals, there is no integer counterexample.

[d] Consequence. Any 12-element integer set has at least 11 nonzero elements, hence at least six of one sign. Multiply those six by $-1$ if necessary and apply the symbolic lemma. Therefore $h(12)\geq4$.

The verifier also independently performs the analogous five-variable hyperplane computation for the elementary lemma above, over all six sign splits. It closes UNSAT in 2, 2, 10, 8, 2, and 2 states respectively.

6. Explicit finite obstructions

For each row below, the verifier exhibits one admissible $k$-subset and checks every $(k+1)$-subset of $A$ is bad. By heredity, this proves $H(A)=k$.

| $|A|$ | explicit $A$ | $k=H(A)$ | admissible witness | bad $(k+1)$-subsets checked | label | |---:|---|---:|---|---:|---| | 2 | $\{0,1\}$ | 1 | $\{0\}$ | 1 of 1 | [d] | | 5 | $[-2,2]$ | 2 | $\{-2,-1\}$ | 10 of 10 | [d] | | 11 | $[-5,5]$ | 3 | $\{-5,-4,-3\}$ | 330 of 330 | [d] | | 19 | $\{-10\}\cup[-8,8]\cup\{10\}$ | 4 | $\{-10,-8,-7,-6\}$ | 11,628 of 11,628 | [d] | | 23 | $[-11,11]$ | 5 | $\{-11,-10,-9,-8,-7\}$ | 100,947 of 100,947 | [d] |

The first three rows can also be hand-checked, but the stated counts are the independent from-scratch computation.

7. Exact table and sharp next bracket

Combine monotonicity, the lower thresholds at $n=3,6,12$, and the explicit upper witnesses at $n=2,5,11,19$.

[a+d] Exact page-formulation table:

| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | |---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:|---:| | $h(n)$ | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |

The provenance of each block is:

• [a+d] $h(1)=h(2)=1$;
• [a+d] $h(n)=2$ for $3\leq n\leq5$;
• [a+d] $h(n)=3$ for $6\leq n\leq11$;
• [d] $h(n)=4$ for $12\leq n\leq19$.

[a+d] Sharp next bracket. Monotonicity gives $h(n)\geq4$ for $n\geq19$, while the $23$-element obstruction gives $h(n)\leq5$ for $n\leq23$. Consequently

8. Reverification code and run

The complete standalone verifier is:

• runs/erdos789_wavew015_reverify.py
• Python standard library only; no SAT/SMT/LP package
• SHA-256:

dd1bf556989ebf1913bc0b9441830f539169190c82dca36d030b7b40459815c1

• deterministic, no random seed and no bounded-value assumption in either

symbolic lemma

The definition-level core used for all explicit constructions is:

def admissible(values):
    sum_cardinality = {}
    for mask in range(1, 1 << len(values)):
        total = sum(values[i] for i in range(len(values)) if mask >> i & 1)
        size = mask.bit_count()
        previous = sum_cardinality.get(total)
        if previous is not None and previous != size:
            return False
        sum_cardinality[total] = size
    return True

The symbolic core does not hard-code the bad relations; it generates them:

def bad_subset_equations(indices, variable_count):
    equations = set()
    width = len(indices)
    for left in range(1, 1 << width):
        for right in range(1, 1 << width):
            if left.bit_count() == right.bit_count():
                continue
            row = [0] * variable_count
            for local_index, variable_index in enumerate(indices):
                row[variable_index] = (
                    ((left >> local_index) & 1)
                    - ((right >> local_index) & 1)
                )
            equations.add(canonical_equation(tuple(row)))
    return tuple(sorted(equations))

The remainder of the standalone file is the exact rational RREF, Fourier–Motzkin elimination, hyperplane backtracker, construction enumerator, and assertions. Run it from the repository root with:

python runs/erdos789_wavew015_reverify.py

Final measured run: 3.00 seconds user time 2.98 seconds, peak RSS 17,152 KiB. It reported:

A_2=(0, 1): maximum admissible size 1; all 1 pairs are bad
A_5=(-2, -1, 0, 1, 2): maximum admissible size 2; all 10 triples are bad
A_11=(-5, ..., 5): maximum admissible size 3; all 330 quadruples are bad
A_19=(-10, -8, ..., 8, 10): maximum admissible size 4;
  all 11628 five-subsets are bad
A_23=(-11, ..., 11): maximum admissible size 5;
  all 100947 six-subsets are bad
five-nonzero lemma, sign splits 0,...,5: UNSAT in 2,2,10,8,2,2 states
six-positive lemma: every quadruple bad: UNSAT in 57 states
verified page-formulation table h(1..19) =
  (1,1,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,4,4)
verified bounds for 20 <= n <= 23: 4 <= h(n) <= 5

As a second, deliberately redundant check, direct bounded enumeration tested all $\binom{25}{6}=177{,}100$ positive six-sets in $[1,25]$ and found an admissible quadruple in each. This bounded check is not used to justify the global symbolic lemma.

9. Precise wall

[c] The work does not improve either asymptotic exponent. The verified literature bounds remain

For the next exact threshold, the sign-pigeonhole route isolates a concrete missing lemma:

Every ten distinct positive integers contain an admissible five-element subset.

If this lemma holds, every 20-element integer set supplies ten integers of one sign after discarding a possible zero, so $h(20)\geq5$; the verified $23$-element obstruction would then give $h(n)=5$ for $20\leq n\leq23$.

[d: negative computation report] The same exact hyperplane engine turns that lemma into 252 five-subset clauses with 95 generated candidate hyperplanes per clause. The present pure-Python proof search was terminated at the imposed 120-second single-core cap without a result. Nothing from that incomplete run is used above.

[c: cost estimate] A proof-producing, optimized C++/SMT implementation with canonical row-space memoisation is plausibly a 1–10 core-hour job on a modern 3–4 GHz CPU (roughly $0.05–$1 at ordinary commodity compute rates), but that is an engineering estimate, not a guaranteed bound. Merely enumerating a large integer box would not prove the lemma; the required output is a uniform linear-arithmetic UNSAT certificate or an elementary case proof.

Asymptotically, the precise missing ingredient is much stronger: a uniform selection lemma surpassing Choi's $(n\log n)^{1/3}$ lower scale, or an ambient construction improving the square-root interval obstruction. The Deshouillers–Freiman interval theorem cannot bridge this gap because it only sharpens the already-known $\sqrt n$ upper construction.

PARTIAL: exact page-formulation values are h(1..19)=1,1,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,4,4, with 4<=h(n)<=5 for 20<=n<=23; the asymptotic exponent gap remains open.