Conjectura
Beta.Proofs cannot be submitted yet. The corpus is open to read, and we are looking for researchers to maintain a subject area.Maintaining a field →
← problemsCB007openMathematics/ Combinatorics

The Erdős–Turán conjecture on additive bases

Maintainer — open

If every number is a sum of two members of a set, must some number have many such representations?

Motivation

Erdős and Turán, 1941. Erdős offered $500.

The intuition is that a set thin enough to be an efficient basis cannot be uniformly efficient — but nobody can rule out a set where every number has, say, between 1 and 100 representations.

Erdős and Turán, 1941. $500 prize.

Lean API
import Mathlib.Data.Finset.Card
import Mathlib.SetTheory.Cardinal.Finite

namespace Conjectura.CB007

/-- If every large natural has at least one representation as a sum of two members of
a set, must the number of representations be unbounded? Erdős offered $500. Open since
1941. -/
def goal : Prop :=
  ∀ (A : Set ℕ),
    (∀ n : ℕ, ∃ a ∈ A, ∃ b ∈ A, a + b = n) →
      ∀ C : ℕ, ∃ n : ℕ, C < Nat.card {p : ℕ × ℕ // p.1 ∈ A ∧ p.2 ∈ A ∧ p.1 + p.2 = n}

end Conjectura.CB007
Definition2
Related work0
    For your AI
    Download as .md
    I am proving a theorem in Lean 4 and submitting it to Conjectura.
    
    ## Problem CB007 — The Erdős–Turán conjecture on additive bases
    
    If every number is a sum of two members of a set, must some number have many such representations?
    
    ## Environment (fixed — do not assume anything newer)
    
    - Lean toolchain: `leanprover/lean4:v4.33.0-rc1`
    - Mathlib: `v4.33.0-rc1`
    
    If a lemma you want does not exist in that Mathlib, prove it inline instead of
    importing something newer.
    
    ## The exact statement I must prove
    
    ```lean
    theorem solution : ∀ (A : Set ℕ), (∀ n : ℕ, ∃ a ∈ A, ∃ b ∈ A, a + b = n) →
        ∀ C : ℕ, ∃ n : ℕ, C < Nat.card {p : ℕ × ℕ // p.1 ∈ A ∧ p.2 ∈ A ∧ p.1 + p.2 = n} := by
      sorry
    ```
    
    ## The file I submit
    
    ```lean
    import Conjectura.Problems.CB007.Statement
    
    namespace Submission
    
    theorem solution : Conjectura.CB007.goal := by
      sorry
    
    end Submission
    
    ```
    
    ## The Lean definitions of every term in this problem
    
    These are the actual definitions your proof will be checked against. Do not
    substitute your own version of any of them.
    
    ### Set
    
    abbrev
    
    ```lean
    Set
    ```
    Defined in Mathlib.
    
    ### card
    
    theorem
    
    ```lean
    Nat.card
    ```
    Defined in Mathlib.
    
    ## Rules — submissions violating these are rejected automatically
    
    1. **Do not change the name or type of `solution`.** It must satisfy the
       statement above exactly.
    2. **Do not redefine or shadow anything from the problem's Statement module.**
       Declaring your own `goal`, or redefining a name it depends on, produces a
       proof of a *different* statement and is rejected. This is the single most
       common rejection.
    3. **No `sorry`** anywhere, including in helper lemmas. It surfaces as the
       axiom `sorryAx` and is detected transitively through imports.
    4. **No `native_decide`** — it surfaces as `Lean.ofReduceBool` and is not
       accepted, because it trusts compiled code rather than the kernel.
    5. Only these axioms are permitted: `propext`, `Classical.choice`,
       `Quot.sound`.
    6. Follow Mathlib style: hypotheses left of the colon, explicit types,
       `snake_case` theorem names, `UpperCamelCase` types.
    
    ## What I want from you
    
    Here is my argument in informal mathematics:
    
    > [PASTE YOUR PROOF SKETCH HERE]
    
    Turn it into Lean 4 that compiles under the environment above and satisfies the
    statement exactly. Where you are unsure a lemma exists in this Mathlib version,
    say so explicitly rather than guessing a name.

    Submissions are not open yet

    Conjectura is in beta. You can read every statement, every definition and the Lean behind them, and download the exact files the checker uses — but proofs are not being accepted yet.

    The reason is a deliberate order of operations. Accepting a proof means running a stranger’s code and standing behind a verdict, and no statement here yet carries a researcher’s name. A machine-checked answer to a question nobody has vouched for is worth very little, so the vouching comes first.

    The English write-ups are also switched off during the beta. Nothing on this page is generated by a model.

    Discussion

    • Nothing yet.

    Sign in to take part.