/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Green's Open Problem 25

References:

    [Gr24] Green, Ben. "100 open problems." (2024).

    [ESS89] Erdős, Pál, András Sárközy, and V. T. Sós. "On a conjecture of Roth and some related problems I." Irregularities of partitions. Berlin, Heidelberg: Springer Berlin Heidelberg, 1989. 47-59.

    [Ru04] Ruzsa, Imre Z. "A problem on restricted sumsets." CONTEMPORARY MATHEMATICS 342 (2004): 245-248.

@[expose] public sectionopen Asymptotics Filter Finsetnamespace Green25

For which values of $k$ is the following true: whenever we partition $[N] = A_1 \cup \dots \cup A_k$, $\left|\bigcup^k_{i=1} (A_i \hat{+} A_i)\right| \geq \frac{1}{10} N$?

def Property25 (k N : ℕ) : Prop := 1 ≤ k ∧ k ≤ N ∧ ∀ P : Finpartition (Icc 1 N), #P.parts = k → 10 * #(P.parts.biUnion Finset.restrictedSumset) ≥ N

The best-known lower bound [ESS89].

noncomputable def bestLower (N : ℕ) : ℝ := Real.log (Real.log N)

The best-known upper bound [ESS89].

noncomputable def bestUpper (N : ℕ) : ℝ := (N : ℝ) / Real.log Ndef green_25.answer : Set (ℕ → ℕ) := sorry

For which values of $k$ is the following true: whenever we partition $[N] = A_1 \cup \dots \cup A_k$, $\left|\bigcup^k_{i=1} (A_i \hat{+} A_i)\right| \geq \frac{1}{10} N$?

@[category research open, question value, AMS 5 11] theorem green_25 : {k : ℕ → ℕ | ∀ᶠ N in atTop, Property25 (k N) N} = green_25.answer := ⊢ {k | ∀ᶠ (N : ℕ) in atTop, Property25 (k N) N} = green_25.answer All goals completed! 🐙def green_25.upper.answer : ℕ → ℕ := sorry

We conjecture that the best-known upper bound can be lowered.

@[category research open, question value, AMS 5 11] theorem green_25.upper : -- Ensure k is a valid partition size (∀ᶠ N in atTop, 1 ≤ green_25.upper.answer N ∧ green_25.upper.answer N ≤ N) ∧ (fun N => (green_25.upper.answer N : ℝ)) =o[atTop] bestUpper ∧ ¬ ∀ᶠ N in atTop, Property25 (green_25.upper.answer N) N := ⊢ (∀ᶠ (N : ℕ) in atTop, 1 ≤ upper.answer N ∧ upper.answer N ≤ N) ∧ (fun N ↦ ↑(upper.answer N)) =o[atTop] bestUpper ∧ ¬∀ᶠ (N : ℕ) in atTop, Property25 (upper.answer N) N All goals completed! 🐙def green_25.lower.answer : ℕ → ℝ := sorry

We conjecture that the best-known lower bound can be raised.

@[category research open, question value, AMS 5 11] theorem green_25.lower : (bestLower =o[atTop] green_25.lower.answer) ∧ (∀ᶠ N in atTop, 1 ≤ green_25.lower.answer N ∧ green_25.lower.answer N ≤ N) ∧ ∀ k : ℕ → ℕ, (∀ᶠ N in atTop, 1 ≤ k N ∧ k N ≤ N) ∧ ((fun N => (k N : ℝ)) ≪ green_25.lower.answer) → ∀ᶠ N in atTop, Property25 (k N) N := ⊢ bestLower =o[atTop] lower.answer ∧ (∀ᶠ (N : ℕ) in atTop, 1 ≤ lower.answer N ∧ lower.answer N ≤ ↑N) ∧ ∀ (k : ℕ → ℕ), (∀ᶠ (N : ℕ) in atTop, 1 ≤ k N ∧ k N ≤ N) ∧ (fun N ↦ ↑(k N)) =O[atTop] lower.answer → ∀ᶠ (N : ℕ) in atTop, Property25 (k N) N All goals completed! 🐙

For $k \ll \log \log N$, this is true [Gr24].

NOTE: [ESS89] derive a precise constant for which this is true, but $\ll$ would imply that it works for any constant. We thus prefer a little-o statement.

@[category research solved, AMS 5 11] theorem green_25.variants.lower_ess89 : ∀ k : ℕ → ℕ, (∀ᶠ N in atTop, 1 ≤ k N ∧ k N ≤ N) ∧ -- Ensure Property25 is not False due to non-existent partitions (fun N => (k N : ℝ)) =o[atTop] bestLower → ∀ᶠ N in atTop, Property25 (k N) N := ⊢ ∀ (k : ℕ → ℕ), (∀ᶠ (N : ℕ) in atTop, 1 ≤ k N ∧ k N ≤ N) ∧ (fun N ↦ ↑(k N)) =o[atTop] bestLower → ∀ᶠ (N : ℕ) in atTop, Property25 (k N) N All goals completed! 🐙

For $k \gg N / \log N$, it need not be true [Gr24].

We formalize by enforcing a $N / \log N$ growth rate on $k(N)$. This avoids cases like $k(N) = N$ or $N-1$, which produce trivial counter examples with singletons and thus empty restricted sumsets.

@[category research solved, AMS 5 11] theorem green_25.variants.upper_ess89 : ∃ k : ℕ → ℕ, (∀ᶠ N in atTop, 1 ≤ k N ∧ k N ≤ N) ∧ (fun N => (k N : ℝ)) =Θ[atTop] bestUpper ∧ ¬ ∀ᶠ N in atTop, Property25 (k N) N := ⊢ ∃ k, (∀ᶠ (N : ℕ) in atTop, 1 ≤ k N ∧ k N ≤ N) ∧ (fun N ↦ ↑(k N)) =Θ[atTop] bestUpper ∧ ¬∀ᶠ (N : ℕ) in atTop, Property25 (k N) N All goals completed! 🐙

For $k(N) = \lceil N^{23/40} \rceil$, it need not be true: for all sufficiently large $N$ there is a partition of $[N]$ into $\lceil N^{23/40} \rceil$ parts with $\left|\bigcup^k_{i=1} (A_i \hat{+} A_i)\right| < \frac{1}{10} N$. In particular, the best-known upper bound $N / \log N$ can be lowered.

@[category research solved, AMS 5 11, formal_proof using lean4 at "https://github.com/KitaKen1/green-25-upper-bound/blob/3a54a688dfc4d7b9c8990bbaeb1a124c075454e4/lean/Green25UpperFC.lean#L3043-L3051"] theorem green_25.variants.upper_pow_23_40 : let k : ℕ → ℕ := fun N => Nat.ceil ((N : ℝ) ^ (23 / 40 : ℝ)) (∀ᶠ N in atTop, 1 ≤ k N ∧ k N ≤ N) ∧ (fun N => (k N : ℝ)) =o[atTop] bestUpper ∧ ∀ᶠ N in atTop, ¬ Property25 (k N) N := ⊢ let k := fun N ↦ ⌈↑N ^ (23 / 40)⌉₊; (∀ᶠ (N : ℕ) in atTop, 1 ≤ k N ∧ k N ≤ N) ∧ (fun N ↦ ↑(k N)) =o[atTop] bestUpper ∧ ∀ᶠ (N : ℕ) in atTop, ¬Property25 (k N) N All goals completed! 🐙end Green25