Skip to content
Cairn Commons
X Sign in
Level A · Machine-checkable Hard Combinatorics P-erdos-789

Erdős Problem #789

Let h(n) be maximal such that if A⊆ ℤ with lvert Arvert=n then there is B⊆ A with lvert Brvert ≥ h(n) such that if a_1+⋯+a_r=b_1+⋯+b_s with a_i,b_i∈ B then r=s. Estimate h(n).

From the catalogue. Imported from The Formal Conjectures Authors (Google DeepMind and contributors) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim. A Lean proof is checked against the statement below by the Lean kernel; a curator confirms before the problem counts as resolved.

Start working on it Submit a claim Follow
Cite 
@misc{cairn-erdos-789,
  title        = {Erdős Problem #789},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/erdos-789}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-29}
}

Also: CITATION.cff · Atom feed of results

Claims
0
Verified
0
Disputed
0
Refuted
0
On the literature board
0

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

The question

Let be maximal such that if with then there is with such that if with then .

Estimate .

In this problem, a function is defined maximally by some counting property.

The problem asks to estimate . This has been interpreted here as asking for . The principal version includes answer(sorry) for an unknown function. On the other hand, the best known upper bound is and the best known lower bound is so we also provide these candidates as variants. Moreover, it suffices to show and respectively for each, so further variants are provided for those.

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.ErdosProblems.«789». answer(sorry) marks a yes/no question: a proof of the statement on the right of ↔, or of its negation, answers it.

theorem erdos_789 :
    (fun n ↦ (subsetSumThreshold n : ℝ)) =Θ[atTop] (answer(sorry) : ℕ → ℝ)

What counts as progress

  • A Lean proof of the pinned statement (or of its negation, for a yes/no question) — checked by the Lean kernel against the upstream statement; a curator confirms before the problem is marked resolved.
  • Partial results: special cases, weaker bounds, reductions — as verified claims.
  • Computations and numerical evidence with published code (reproducible).
  • Literature: the problem may have been solved or partly solved already — check erdosproblems.com/789. Report it as a literature claim.
  • A precise flaw in the formal statement (a misformalisation) — report it upstream too.

Variants

  • erdos_789.variants.sq — Let h(n) be maximal such that if A⊆ ℤ with lvert Arvert=n then there is B⊆ A with lvert Brvert ≥ h(n) such that if a_1+⋯+a_r=b_1+⋯+b_s with a_i,b_i∈ B then…
  • erdos_789.variants.sq_isBigO — By the solved variant erdos_789.variants.isBigO_sq, in order to prove erdos_789.variants.sq it suffices to show √(n)=O(h(n)).
  • erdos_789.variants.cube_root_linearithmic — Let h(n) be maximal such that if A⊆ ℤ with lvert Arvert=n then there is B⊆ A with lvert Brvert ≥ h(n) such that if a_1+⋯+a_r=b_1+⋯+b_s with a_i,b_i∈ B then…
  • erdos_789.variants.isBigO_cube_root_linearithmic — By the solved variant erdos_789.variants.cube_root_linearithmic_isBigO, in order to prove erdos_789.variants.cube_root_linarithmic it suffices to show h(n) =…

References

  • erdosproblems.com/789
  • [Str66] Straus, E. G., _On a problem in combinatorial number theory_. J. Math. Sci. (1966), 77--80.
  • [Er62c] Erdős, Pál, _Some remarks on number theory_. {III}. Mat. Lapok (1962), 28--38.
  • [Ch74b] Choi, S. L. G., _On an extremal problem in number theory_. J. Number Theory (1974), 105--111.

Source and licence

Imported from Formal Conjectures (Erdős problems), commit e6d1743831c2. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.