Proper-parent certificate inequality (13): 32N∑D∘+32N(n−∣S∣)K+32kK∑u(∣Ru∣+∣Tu∣)≥nNK (Erdős 624)
ProvedErdos624.proper_parent_certificate_ineqby Ethan Cheung · Oct 24, 2026 · Mathlib 0df444a (Lean v4.33.1)
combinatoricserdos-problems
Throughout, U is a finite set of inputs, C a finite set of colours with ∣C∣=n=2k, and g0,g1:P(U)→C are two arbitrary maps (a pair); write L(A)={g0(A),g1(A)} for the list of colours at the input A. Let k≥3 and let V⊆U be a pool with N=∣V∣≥k+5; write K=(kN). Let S⊆C∖L(∅). For each u∈S fix a deletion set Ru⊆U and a parity certificate wu:U→F2 for the proper minimal witnesses of u surviving the deletion: for every A⊆V∖Ru with 0<∣A∣<k, u∈L(A) and u∈/L(B) for all B⊊A, we have ∑x∈Awu(x)=1. Put Tu={x∈V∖Ru:wu(x)=0}. For a k-set Y let J∘(Y)=⋃A⊊YL(A), D∘(Y)=n−∣J∘(Y)∣, Jodd∘(Y)=⋃A⊊Y,∣A∣ oddL(A) and Q∘(Y)=n−∣Jodd∘(Y)∣. Then (no coverage assumption is needed)
32NY∈(kV)∑D∘(Y)+32N(n−∣S∣)K+32kKu∈S∑(∣Ru∣+∣Tu∣)≥nNK.(13)
Context: Erdős Problem 624 asks whether H(n)−log2n→∞, where H(n) is the least m such that some f:P(X)→X with ∣X∣=n satisfies f[P(Y)]=X for all ∣Y∣≥m. By an earlier track-amplification result it suffices to find common holes for fixed numbers of tracks; this is an auxiliary finite inequality from Sol's Round 10 analysis of the two-track case. It does not settle Erdős Problem 624, PAIR or Step 17.
Preamble
import Mathlib
open Finset
Formal statement
namespace Erdos624
theorem proper_parent_certificate_ineq {U : Type*} [Fintype U] [DecidableEq U]
{C : Type*} [Fintype C] [DecidableEq C] (k : ℕ) (hk : 3 ≤ k) (hC : Fintype.card C = 2 ^ k)
(g0 g1 : Finset U → C) (V : Finset U) (hV : k + 5 ≤ #V) (S : Finset C)
(hS : ∀ u ∈ S, u ∉ ({g0 ∅, g1 ∅} : Finset C))
(R : C → Finset U) (w : C → U → ZMod 2)
(hw : ∀ u ∈ S, ∀ A ⊆ V \ R u, 0 < #A → #A < k → u ∈ ({g0 A, g1 A} : Finset C) →
(∀ B ⊂ A, u ∉ ({g0 B, g1 B} : Finset C)) → ∑ x ∈ A, w u x = 1) :
2 ^ k * #V * #(powersetCard k V) ≤
32 * #V * ∑ Y ∈ powersetCard k V, (2 ^ k - #((Y.powerset.filter (fun A => A ≠ Y)).biUnion
(fun A => ({g0 A, g1 A} : Finset C)))) +
32 * #V * (2 ^ k - #S) * #(powersetCard k V) +
32 * k * #(powersetCard k V) *
∑ u ∈ S, (#(R u) + #((V \ R u).filter (fun x => w u x = 0))) := by sorry
end Erdos624
Source
Erdős Problem 624 (https://www.erdosproblems.com/624); Round 10 reports (consolidated report §'parity transport', §'many holes one level below'; Step 17 report 'resilient relations below the top layer', eqs. (9)-(26)); derived from GPT 6.1 Sol's analysis, relayed by Ethan Cheung; proof reconstructed, hand-checked and Lean-verified by Grok Bot for Ethan Cheung (Oct 24 2026). Auxiliary result only; does NOT settle PAIR / Step 17 / #624.
View graph