Seventeen-packet obstruction: three rank- colours cannot see 17 packets with exact pair-union kernels at capacity 2 (Erdős 624)
ProvedErdos624.seventeen_packet_contradictionSetting: 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). Theorem. Assume for all . Let be three distinct nonbottom covering colours with valid labels of global rank (stated as ). There do not exist 17 pairwise disjoint nonempty packets such that for all colours and distinct : ; ; and every with is or one of the three pair unions (together: the kernel condition (K) ).
This is the deterministic core of Sol's 'A Triple-Colour Ramsey Obstruction' (the probabilistic construction of the packets under a joint-balance hypothesis is not formalized here). In that note the packets have a common size with ; here only is needed.
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 seventeen_packet_contradiction {U : Type*} [Fintype U] [DecidableEq U] {C : Type*} [DecidableEq C]
{W : Type*} [AddCommGroup W] [Module (ZMod 2) W]
(L : Finset U → Finset C) (hb : ∀ A, #(L A) ≤ 2) (k : ℕ)
(c : Fin 3 → C) (hc : Function.Injective c) (hu : ∀ i, c i ∉ L ∅)
(hcov : ∀ i, ∀ Y : Finset U, #Y = k → ∃ A ⊆ Y, c i ∈ L A)
(p : Fin 3 → U → W)
(hvalid : ∀ i, ∀ F : Finset U, 0 < #F → #F ≤ k → c i ∈ L F → (∀ F' ⊂ F, c i ∉ L F') →
∑ x ∈ F, p i x = 0)
(hglob : ∀ i,
k ≤ Module.finrank (ZMod 2) (Submodule.span (ZMod 2) (Set.range (p i))) + 2)
(P : Fin 17 → Finset U) (hdisj : ∀ j l, j ≠ l → Disjoint (P j) (P l))
(hne : ∀ j, (P j).Nonempty)
(hsize : ∀ j l m, j ≠ l → j ≠ m → l ≠ m → #(P j ∪ P l ∪ P m) ≤ k)
(hpair : ∀ i j l, j ≠ l → ∑ x ∈ P j ∪ P l, p i x = 0)
(hker : ∀ i j l m, j ≠ l → j ≠ m → l ≠ m → ∀ G ⊆ P j ∪ P l ∪ P m,
∑ x ∈ G, p i x = 0 → G = ∅ ∨ G = P j ∪ P l ∨ G = P j ∪ P m ∨ G = P l ∪ P m) :
False := by sorry
end Erdos624