Uniform actual-generation theorem (A): and (Erdős 624)
ProvedErdos624.actual_generation_gapSetting: is a finite set of inputs, an arbitrary list map (the actual colour lists), a natural number. A colour is nonbottom if and covering if every -subset contains some with . An actual minimal witness of is with and for every . A valid label for is a map into an -vector space with for every actual minimal witness with . For , and (the dimension of the valid parity space). For let (the kernel of ) and an actual minimal witness of with . Theorem (A). If is nonbottom and covering and is a valid label with (stated as ), then for every (no size restriction)
Source: 'Actual Witness Spans and Intrinsic Kernel Diversity', boxed (A). (There the labels live on a pool ; take .)
Context: Erdős Problem 624 asks whether , where is the least such that some with satisfies for all . This is an auxiliary finite statement from Sol's Round 13 notes on the two-track (PAIR) case. It does not settle Erdős Problem 624, PAIR or Step 17; the initial near-critical population those notes start from is not established.
import Mathlib open Finset
namespace Erdos624
theorem actual_generation_gap {U : Type*} [Fintype U] [DecidableEq U] {C : Type*} [DecidableEq C]
{W : Type*} [AddCommGroup W] [Module (ZMod 2) W]
(L : Finset U → Finset C) (k d : ℕ) (u : C) (hu : u ∉ L ∅)
(hcov : ∀ Y : Finset U, #Y = k → ∃ A ⊆ Y, u ∈ L A)
(p : U → W)
(hvalid : ∀ F : Finset U, 0 < #F → #F ≤ k → u ∈ L F → (∀ F' ⊂ F, u ∉ L F') →
∑ x ∈ F, p x = 0)
(hglob : k ≤ Module.finrank (ZMod 2) (Submodule.span (ZMod 2) (Set.range p)) + d)
(T : Finset U) :
Submodule.span (ZMod 2) {f : T → ZMod 2 | ∃ F : Finset U, F ⊆ T ∧ 0 < #F ∧ #F ≤ k ∧
u ∈ L F ∧ (∀ F' ⊂ F, u ∉ L F') ∧ f = fun x : T => if x.1 ∈ F then (1 : ZMod 2) else 0} ≤
LinearMap.ker (Fintype.linearCombination (ZMod 2) (fun x : T => p x)) ∧
Module.finrank (ZMod 2) (LinearMap.ker (Fintype.linearCombination (ZMod 2) (fun x : T => p x))) + 1 ≤
Module.finrank (ZMod 2) (Submodule.span (ZMod 2) {f : T → ZMod 2 | ∃ F : Finset U, F ⊆ T ∧ 0 < #F ∧ #F ≤ k ∧
u ∈ L F ∧ (∀ F' ⊂ F, u ∉ L F') ∧ f = fun x : T => if x.1 ∈ F then (1 : ZMod 2) else 0}) + d := by sorry
end Erdos624