/- 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 38

References:

    100 open problems

    [La79] Lovász, László. "On the Shannon capacity of a graph." IEEE Transactions on Information theory 25.1 (1979): 1-7.

    [Po20] Polak, Sven. "New methods in coding theory: Error-correcting codes and the Shannon capacity." arXiv preprint arXiv:2005.02945 (2020).

    [IRCR26] Itty, Nathaniel and Rosin, Christopher D. and Carstensen, Chase and Reichman, Daniel. "Improved lower bounds for the Shannon capacity of odd cycles." arXiv:2607.21517 (2026).

    [Ga26] Gao, Yu. "A recursive construction improving the lower bound on the Shannon capacity of $C_7$." arXiv:2607.27869 (2026).

    [BPZ26] Buys, Pjotr and Polak, Sven and Zuiddam, Jeroen. "Lean-verified lower bounds for the Shannon capacity of odd cycles." arXiv:2607.29681 (2026). Lean formalisation: https://github.com/spectra-research/shannon-capacity-lean

@[expose] public sectionopen Filter Setopen scoped Pointwisenamespace Green38

$A - A$ intersects ${-1, 0, 1}^n$ only at $0$.

def IntersectsOnlyAtZero {n : ℕ} (A : Finset (𝔽₇ n)) : Prop := ∀ a ∈ A - A, (∀ i, a i ∈ ({-1, 0, 1} : Finset (ZMod 7))) → a = 0

The set of cardinalities of all subsets A where A - A intersects {-1, 0, 1}^n only at 0.

def ValidCardinalities (n : ℕ) : Set ℕ := { (A.card) | (A : Finset (𝔽₇ n)) (_ : IntersectsOnlyAtZero A) }

{0, 2, 4} is a valid independent set in C_7, giving cardinality 3.

@[category test, AMS 5] theorem green_38.test_n1_lower : 3 ∈ ValidCardinalities 1 := ⊢ 3 ∈ ValidCardinalities 1 refine ⟨{![0], ![2], ![4]}, ?_, ⊢ {![0], ![2], ![4]}.card = 3 All goals completed! 🐙⟩ a:𝔽₇ 1ha:a ∈ {![0], ![2], ![4]} - {![0], ![2], ![4]}⊢ (∀ (i : Fin 1), a i ∈ {-1, 0, 1}) → a = 0 a:𝔽₇ 1ha:a ∈ {![0], ![2], ![4]} - {![0], ![2], ![4]}⊢ a 0 = -1 ∨ a 0 = 0 ∨ a 0 = 1 → a = 0 -- a is a difference of elements from {0, 2, 4}, check all cases ⊢ Function.uncurry (fun x1 x2 ↦ x1 - x2) (![0], ![4]) 0 = -1 ∨ Function.uncurry (fun x1 x2 ↦ x1 - x2) (![0], ![4]) 0 = 0 ∨ Function.uncurry (fun x1 x2 ↦ x1 - x2) (![0], ![4]) 0 = 1 → Function.uncurry (fun x1 x2 ↦ x1 - x2) (![0], ![4]) = 0a:𝔽₇ 1a✝:List.Mem a (List.foldr (fun x IH ↦ if ∀ y ∈ IH, (fun x1 x2 ↦ x1 ≠ x2) x y then x :: IH else IH) [] (List.map (Function.uncurry fun x1 x2 ↦ x1 - x2) ((List.map (Prod.mk ![0]) []).append (List.map (Prod.mk ![2]) (List.insert ![0] (List.insert ![2] [![4]])) ++ (List.map (Prod.mk ![4]) (List.insert ![0] (List.insert ![2] [![4]])) ++ [])))))⊢ a 0 = -1 ∨ a 0 = 0 ∨ a 0 = 1 → a = 0 ⊢ Function.uncurry (fun x1 x2 ↦ x1 - x2) (![0], ![4]) 0 = -1 ∨ Function.uncurry (fun x1 x2 ↦ x1 - x2) (![0], ![4]) 0 = 0 ∨ Function.uncurry (fun x1 x2 ↦ x1 - x2) (![0], ![4]) 0 = 1 → Function.uncurry (fun x1 x2 ↦ x1 - x2) (![0], ![4]) = 0 ⊢ 4 = 1 ∨ 4 = 0 ∨ -4 = 1 → 4 = 0 All goals completed! 🐙 a:𝔽₇ 1a✝:List.Mem a (List.foldr (fun x IH ↦ if ∀ y ∈ IH, (fun x1 x2 ↦ x1 ≠ x2) x y then x :: IH else IH) [] (List.map (Function.uncurry fun x1 x2 ↦ x1 - x2) ((List.map (Prod.mk ![0]) []).append (List.map (Prod.mk ![2]) (List.insert ![0] (List.insert ![2] [![4]])) ++ (List.map (Prod.mk ![4]) (List.insert ![0] (List.insert ![2] [![4]])) ++ [])))))⊢ a 0 = -1 ∨ a 0 = 0 ∨ a 0 = 1 → a = 0 a:𝔽₇ 1⊢ List.Mem a (List.foldr (fun x IH ↦ if ∀ y ∈ IH, (fun x1 x2 ↦ x1 ≠ x2) x y then x :: IH else IH) [] (List.map (Function.uncurry fun x1 x2 ↦ x1 - x2) ((List.map (Prod.mk ![0]) []).append (List.map (Prod.mk ![2]) (List.insert ![0] (List.insert ![2] [![4]])) ++ (List.map (Prod.mk ![4]) (List.insert ![0] (List.insert ![2] [![4]])) ++ []))))) → a 0 = -1 ∨ a 0 = 0 ∨ a 0 = 1 → a = 0 use a:𝔽₇ 1⊢ a = Function.uncurry (fun x1 x2 ↦ x1 - x2) (![2], ![4]) ∨ a ∈ List.foldr (fun x IH ↦ if ∀ y ∈ IH, (fun x1 x2 ↦ x1 ≠ x2) x y then x :: IH else IH) [] (List.map (Function.uncurry fun x1 x2 ↦ x1 - x2) ((List.map (Prod.mk ![2]) []).append (List.map (Prod.mk ![4]) (List.insert ![0] (List.insert ![2] [![4]])) ++ []))) → a 0 = -1 ∨ a 0 = 0 ∨ a 0 = 1 → a = 0 All goals completed! 🐙 ∘ List.mem_cons.1

The largest subset $A \subset \mathbb{F}_7^n$ for which $A - A$ intersects ${-1, 0, 1}^n$ only at $0$.

noncomputable def LargestAdmissibleCardinality : ℕ → ℝ := fun n ↦ (sSup (ValidCardinalities n) : ℕ)

The lower bound constant $C_1 \approx 3.2578$ from [Po20].

noncomputable def C₁ : ℝ := (367 : ℝ) ^ (5⁻¹ : ℝ)

The upper bound constant $C_2 \approx 3.3177$ from [La79].

noncomputable def C₂ : ℝ := (7 * Real.cos (Real.pi / 7)) / (1 + Real.cos (Real.pi / 7))def green_38.lower.answer : ℕ → ℝ := fun n : ℕ ↦ (134753 : ℝ) ^ (n / 10)

Can we improve the lower bound? The answer sequence must be eventually nonnegative, since =O compares norms.

Yes. Itty, Rosin, Carstensen and Reichman [IRCR26] found a valid set of size $134753$ in $\mathbb{F}_7^{10}$ (an independent set in the tenth strong power of $C_7$). Taking products gives valid sets of size $134753^{\lfloor n/10 \rfloor}$ in $\mathbb{F}_7^n$, see green_38.variants.lower_itty_rosin_carstensen_reichman, so the growth rate is at least $134753^{1/10} > 3.258020 > C_1$ (note $134753 > 367^2 = 134689$). Gao [Ga26] and then Buys, Polak and Zuiddam [BPZ26] improved the rate further, to $3.258789\ldots$ and $3.2588\ldots$ respectively; the latter is formalised in Lean. The exact growth rate remains open.

@[category research solved, question value, AMS 5 11] theorem green_38.lower : (∀ᶠ n in atTop, 0 ≤ green_38.lower.answer n) ∧ green_38.lower.answer ≤ᶠ[atTop] LargestAdmissibleCardinality ∧ ∃ c > C₁, (fun n ↦ c ^ n) =O[atTop] green_38.lower.answer := ⊢ (∀ᶠ (n : ℕ) in atTop, 0 ≤ lower.answer n) ∧ lower.answer ≤ᶠ[atTop] LargestAdmissibleCardinality ∧ ∃ c > C₁, (fun n ↦ c ^ n) =O[atTop] lower.answer All goals completed! 🐙def green_38.upper.answer : ℕ → ℝ := sorry

Can we improve the best upper bound? The base c must be positive, since =O compares norms.

@[category research open, question value, AMS 5 11] theorem green_38.upper : LargestAdmissibleCardinality ≤ᶠ[atTop] green_38.upper.answer ∧ ∃ c : ℝ, 0 < c ∧ c < C₂ ∧ green_38.upper.answer =O[atTop] (fun n ↦ c ^ n) := ⊢ LargestAdmissibleCardinality ≤ᶠ[atTop] upper.answer ∧ ∃ c, 0 < c ∧ c < C₂ ∧ upper.answer =O[atTop] fun n ↦ c ^ n All goals completed! 🐙

The lower bound $(C_1 - o(1))^n \leqslant |A|$ where $C_1 = 367^{1/5} \approx 3.2578$, from a valid set of size $367$ in $\mathbb{F}_7^5$ [Po20, Section 9.1]. This was the best known bound when Green's list was written; it has since been improved, see green_38.lower.

@[category research solved, AMS 5 11] theorem green_38.variants.best_lower : ∀ ε ∈ Set.Ioo (0 : ℝ) C₁, ∀ᶠ n in atTop, (C₁ - ε) ^ n ≤ LargestAdmissibleCardinality n := ⊢ ∀ ε ∈ Ioo 0 C₁, ∀ᶠ (n : ℕ) in atTop, (C₁ - ε) ^ n ≤ LargestAdmissibleCardinality n All goals completed! 🐙

Itty, Rosin, Carstensen and Reichman [IRCR26] found a valid set of size $134753$ in $\mathbb{F}_7^{10}$. Products of copies of it, padded with zero coordinates, give $134753^{\lfloor n/10 \rfloor} \leqslant |A|$ in $\mathbb{F}_7^n$.

@[category research solved, AMS 5 11] theorem green_38.variants.lower_itty_rosin_carstensen_reichman (n : ℕ) : (134753 : ℝ) ^ (n / 10) ≤ LargestAdmissibleCardinality n := n:ℕ⊢ 134753 ^ (n / 10) ≤ LargestAdmissibleCardinality n All goals completed! 🐙

The current best upper bound is $|A| \leqslant (C_2 + o(1))^n$ where $C_2 = \frac{7 \cos(\pi/7)}{1 + \cos(\pi/7)} \approx 3.3177$ [La79, Corollary 5].

@[category research solved, AMS 5 11] theorem green_38.variants.best_upper : ∀ ε > 0, ∀ᶠ n in atTop, LargestAdmissibleCardinality n ≤ (C₂ + ε) ^ n := ⊢ ∀ ε > 0, ∀ᶠ (n : ℕ) in atTop, LargestAdmissibleCardinality n ≤ (C₂ + ε) ^ n All goals completed! 🐙

0 is a valid cardinality, since the empty set vacuously satisfies the condition.

@[category test, AMS 5 11] theorem green_38.test_zero_mem_validCardinalities {n : ℕ} : 0 ∈ ValidCardinalities n := n:ℕ⊢ 0 ∈ ValidCardinalities n n:ℕ⊢ ∃ (_ : IntersectsOnlyAtZero ∅), ∅.card = 0 All goals completed! 🐙

The set of valid cardinalities we take the supremum over is bounded above.

@[category test, AMS 5 11] theorem green_38.test_bound_above {n : ℕ} : BddAbove (ValidCardinalities n) := n:ℕ⊢ BddAbove (ValidCardinalities n) n:ℕ⊢ 7 ^ n ∈ upperBounds (ValidCardinalities n) n:ℕA:Finset (𝔽₇ n)w✝:IntersectsOnlyAtZero A⊢ A.card ≤ 7 ^ n calc A.card _ ≤ Fintype.card (𝔽₇ n) := A.card_le_univ _ = _ := n:ℕA:Finset (𝔽₇ n)w✝:IntersectsOnlyAtZero A⊢ Fintype.card (𝔽₇ n) = 7 ^ n All goals completed! 🐙end Green38