Erasure-cost lower bound: a parity certificate must delete a point of each zero-sum triple block (Erdős 624 cross-review)
ProvedErdos624.erasure_block_lower_boundcombinatoricserdos-problems
Let be pairwise disjoint finite sets of coordinates and, for each , let satisfy over (relation (Z)). Let be a set of deleted coordinates and an -valued form such that every disjoint from has . Then .
In the cross-review's construction these are the three proper minimal witnesses of a colour in each block, so every successful deletion meets all blocks: (the lower half of (EC)).
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 12 Step 17 cross-review / resilience analysis of the two-track (PAIR) case. It does not settle Erdős Problem 624, PAIR or Step 17.
Preamble
import Mathlib open Finset
Formal statement
namespace Erdos624
theorem erasure_block_lower_bound {U : Type*} [DecidableEq U] (t : ℕ) (P : Fin t → Finset U)
(hP : ∀ i j, i ≠ j → Disjoint (P i) (P j))
(E1 E2 E3 : Fin t → Finset U) (h1 : ∀ j, E1 j ⊆ P j) (h2 : ∀ j, E2 j ⊆ P j)
(h3 : ∀ j, E3 j ⊆ P j)
(hZ : ∀ j x, ((if x ∈ E1 j then 1 else 0) + (if x ∈ E2 j then 1 else 0) +
(if x ∈ E3 j then 1 else 0) : ZMod 2) = 0)
(R : Finset U) (w : U → ZMod 2)
(hw : ∀ j, (Disjoint (E1 j) R → ∑ x ∈ E1 j, w x = 1) ∧
(Disjoint (E2 j) R → ∑ x ∈ E2 j, w x = 1) ∧ (Disjoint (E3 j) R → ∑ x ∈ E3 j, w x = 1)) :
t ≤ #R := by sorry
end Erdos624
Source
Erdős Problem 624 (https://www.erdosproblems.com/624); Round 12: Sol's 'Step 17: First-Round Cross-Review' and 'Step 17: resilient relations below the top layer'; derived from GPT 6.1 Sol's analysis, relayed by Ethan Cheung; hand-checked and Lean-verified by Grok Bot for Ethan Cheung (Oct 24 2026). Auxiliary result only; does NOT settle PAIR / Step 17 / #624.