Guard-free rank restoration under pool restriction (Erdős 624)
ProvedErdos624.adaptive_rank_restorationcombinatoricserdos-problems
Let be finite, with , and a family of nonempty subsets of a type such that every -subset of contains a member of . Let be a labelling into a module over , with for every . Then there exist a subfamily and a labelling such that every member of is contained in , every -subset of contains a member of , every is annihilated by , and . Thus a feasible annihilator of a covering family on can be restored, after pruning the family, to the same rank on any still-large subpool .
Context: Erdős Problem 624 asks whether . This is an auxiliary structural lemma for already feasible covering cores, taken from Sol's 2026-11-18 Perplexity note on adaptive rank restoration. It does not settle Erdős Problem 624, PAIR, Step 17, or DENSE-P.
Preamble
import Mathlib open Finset
Formal statement
namespace Erdos624
theorem adaptive_rank_restoration {U : Type*} [DecidableEq U]
{W : Type*} [AddCommGroup W] [Module (ZMod 2) W]
(P Q : Finset U) (G : Finset (Finset U)) (k : ℕ) (p : U → W)
(hQP : Q ⊆ P) (hQk : k ≤ #Q)
(hGne : ∀ A ∈ G, A.Nonempty)
(hcov : ∀ Y : Finset U, Y ⊆ P → #Y = k → ∃ A ∈ G, A ⊆ Y)
(hann : ∀ A ∈ G, ∑ x ∈ A, p x = 0) :
∃ (H : Finset (Finset U)) (p' : U → W × (U → ZMod 2)),
H ⊆ G ∧
(∀ A ∈ H, A ⊆ Q) ∧
(∀ Y : Finset U, Y ⊆ Q → #Y = k → ∃ A ∈ H, A ⊆ Y) ∧
(∀ A ∈ H, ∑ x ∈ A, p' x = 0) ∧
Module.finrank (ZMod 2) (Submodule.span (ZMod 2) (p' '' (Q : Set U))) =
Module.finrank (ZMod 2) (Submodule.span (ZMod 2) (p '' (P : Set U))) := by sorry
end Erdos624
Source
Erdős Problem 624 (https://www.erdosproblems.com/624); Round 18: derived from GPT 6.1 Sol's analysis, relayed by Ethan Cheung, in the Perplexity Computer note “Adaptive Rank Restoration Under Pool Restriction” (task d32c2107-b546-4015-be2e-c9c4e46ce7cd, captured 2026-11-18 under perplexity_2026-11-18/); hand-checked and Lean-verified by Grok Bot for Ethan Cheung (18 Nov 2026). Auxiliary finite result only; does NOT settle PAIR / Step 17 / DENSE-P / #624.