Proper odd-palette inequality (11): (Erdős 624)
ProvedErdos624.proper_odd_palette_aloncombinatoricserdos-problems
Throughout, is a finite set of inputs, a finite set of colours with , and are two arbitrary maps (a pair); write for the list of colours at the input . For a -set define the proper odd palette and . Let and with . Then
Context: Erdős Problem 624 asks whether , where is the least such that some with satisfies for all . 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_odd_palette_alon {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) :
2 ^ k * #(powersetCard k V) ≤
32 * ∑ Y ∈ powersetCard k V,
(2 ^ k - #((Y.powerset.filter (fun A => A ≠ Y ∧ #A % 2 = 1)).biUnion
(fun A => ({g0 A, g1 A} : Finset C)))) := 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.