Every-face hidden-generation bound (G): on each -face few colours with have (Erdős 624)
ProvedErdos624.every_face_hidden_generationLet be a finite set, with , and a finite set of nonbottom colours () each attained inside every -subset of . For let be the span of the indicator vectors of the actual minimal witnesses of with (, for ), and for a -set let be the span of those with , and (written as the kernel of restriction to ). Put and .
Theorem. For every with and integers ,
(Both conditions are stated without subtraction: and .)
Source: 'The Larger-Deficit Case and a Rare-Pair Barrier', boxed (G). With , , this gives , i.e. (G) after adding the colours with . This is a necessary condition for a hypothetical full cover, not a contradiction.
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 every_face_hidden_generation {U : Type*} [Fintype U] [DecidableEq U] {C : Type*} [DecidableEq C]
(L : Finset U → Finset C) (b k d H : ℕ) (hb : ∀ A, #(L A) ≤ b)
(S : Finset C) (hu : ∀ u ∈ S, u ∉ L ∅)
(hcov : ∀ u ∈ S, ∀ Y : Finset U, #Y = k → ∃ A ⊆ Y, u ∈ L A)
(Y : Finset U) (hY : #Y = k) (hH : H < d) :
#(S.filter (fun u =>
Fintype.card U + d + 1 ≤
Module.finrank (ZMod 2) (Submodule.span (ZMod 2) {f : U → ZMod 2 | ∃ F : Finset U, 0 < #F ∧
#F ≤ k ∧ u ∈ L F ∧ (∀ F' ⊂ F, u ∉ L F') ∧ f = fun x => if x ∈ F then 1 else 0}) + k ∧
Module.finrank (ZMod 2) (↥((Submodule.span (ZMod 2) {f : U → ZMod 2 | ∃ F : Finset U, 0 < #F ∧
#F ≤ k ∧ u ∈ L F ∧ (∀ F' ⊂ F, u ∉ L F') ∧ f = fun x => if x ∈ F then 1 else 0}) ⊓
LinearMap.ker (LinearMap.funLeft (ZMod 2) (ZMod 2) (fun x : {x // x ∉ Y} => x.1)) : Submodule (ZMod 2) (U → ZMod 2))) ≤
Module.finrank (ZMod 2) (Submodule.span (ZMod 2) {f : U → ZMod 2 | ∃ F : Finset U, F ⊆ Y ∧
0 < #F ∧ #F ≤ k ∧ u ∈ L F ∧ (∀ F' ⊂ F, u ∉ L F') ∧
f = fun x => if x ∈ F then 1 else 0}) + H)) * (d - H) + #S ≤ b * (2 ^ k - 1) := by sorry
end Erdos624