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

Green's Open Problem 51

Suppose that A ⊂ 𝔽_2^n is a set of density α. What is the largest size of coset guaranteed to be contained in 2A? We phrase this by asking for the exact function F(α, n) giving the maximum dimension of a guaranteed coset.

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.

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

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

green_51. Suppose that is a set of density . What is the largest size of coset guaranteed to be contained in ?

We phrase this by asking for the exact function giving the maximum dimension of a guaranteed coset.

green_51.one_half. Suppose that has density . Does contain a subspace of co-dimension ? [Sa11, Question 5.1]

Formal statement (Lean 4)

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

theorem green_51 : answer(sorry) = guaranteedMaxCosetDim
theorem green_51.one_half :
    answer(sorry) ↔ ∀ (k : ℝ), 0 < k →
      ∃ (c : ℕ), ∀ᶠ (n : ℕ) in atTop,
        ∀ (α : ℝ), α > (1/2 : ℝ) - k / sqrt (n : ℝ) → α ≤ 1 →
          n ≤ guaranteedMaxCosetDim n α + c

What counts as progress

  • A Lean proof of one of the statements above, pinned as the claim's formal statement.
  • 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. Report it as a literature claim.
  • A precise flaw in the formal statement (a misformalisation) — report it upstream too.

References

  • [Gr24] Green's Open Problems
  • [Gr13] B. J. Green, Restriction and Kakeya phenomena, notes from a 2003 course. Available at http://people.maths.ox.ac.uk/greenbj/papers/rkp.pdf
  • [Sa11] Sanders, Tom. "Green's sumset problem at density one half." Acta Arithmetica 146.1 (2011): 91-101.
  • [Gr02] Green, Ben. "Arithmetic progressions in sumsets." Geometric & Functional Analysis GAFA 12.3 (2002): 584-597.
  • [Ruz91] Ruzsa, Imre Z. "Arithmetic progressions in sumsets." Acta Arithmetica 60.2 (1991): 191-202.

Source and licence

Imported from Formal Conjectures (Ben Green's 100 open problems), commit e6d1743831c2. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.