Even-packet capacity: packets whose zero-sum subsets are even packet unions bound the colours by (Erdős 624)
ProvedErdos624.even_packet_capacitySetting: 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). Each colour has its own valid label into one -space. Theorem. Assume , every is nonbottom and covering with (stated as ). Let be pairwise disjoint nonempty packets with such that for every : for , and every zero-sum is a union of an even number of packets. Then .
This is the deterministic capacity core of Sol's 'Bias-Free Colour Bounds' (and of 'Bias-Free Bounds on Colour-Dependent Dense Pools'): there, packets with these properties are constructed probabilistically for colours, which this theorem shows is impossible. The probabilistic construction is not formalized.
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 even_packet_capacity {U : Type*} [Fintype U] [DecidableEq U] {C : Type*} [DecidableEq C]
{W : Type*} [AddCommGroup W] [Module (ZMod 2) W]
(L : Finset U → Finset C) (b k d : ℕ) (hb : ∀ A, #(L A) ≤ b)
(S : Finset C) (p : C → U → W) (hu : ∀ u ∈ S, u ∉ L ∅)
(hcov : ∀ u ∈ S, ∀ Y : Finset U, #Y = k → ∃ A ⊆ Y, u ∈ L A)
(hvalid : ∀ u ∈ S, ∀ F : Finset U, 0 < #F → #F ≤ k → u ∈ L F → (∀ F' ⊂ F, u ∉ L F') →
∑ x ∈ F, p u x = 0)
(hglob : ∀ u ∈ S,
k ≤ Module.finrank (ZMod 2) (Submodule.span (ZMod 2) (Set.range (p u))) + d)
(P : Fin (d + 1) → Finset U) (hdisj : ∀ j l, j ≠ l → Disjoint (P j) (P l))
(hne : ∀ j, (P j).Nonempty) (hk : #(Finset.univ.biUnion P) ≤ k)
(hpair : ∀ u ∈ S, ∀ j, j ≠ 0 → ∑ x ∈ P 0 ∪ P j, p u x = 0)
(hzs : ∀ u ∈ S, ∀ G ⊆ Finset.univ.biUnion P, ∑ x ∈ G, p u x = 0 →
∃ I : Finset (Fin (d + 1)), Even #I ∧ G = I.biUnion P) :
#S ≤ b * (2 ^ d - 1) := by sorry
end Erdos624