A commutative-aggregate map and any second map have a common hole (Erdős 624)
ProvedErdos624.one_structured_map_common_holeLet be a finite set with elements. For a map and write . For let be the set of -subsets .
Let be a finite commutative monoid, and arbitrary, and let (a commutative-aggregate map). Write .
Theorem. Let and with , and . Then for every map there are a -set and a point with and .
Context: Erdős Problem 624 asks whether , where is the least such that some () satisfies for all . By an earlier track-amplification result it would suffice to show that, for large , any two maps with have a common hole: a -set and a point missed by both maps on . These results do not settle Problem 624.
Formalization Note. Counting form with natural numbers (truncated subtraction is harmless since ); is an arbitrary Fintype with Fintype.card U = 2 ^ k.
import Mathlib import Definitions.Def_Erdos624_defs open Finset
namespace Erdos624
theorem one_structured_map_common_hole {U : Type*} [Fintype U] [DecidableEq U] {M : Type*} [CommMonoid M] [Fintype M]
(k t d : ℕ) (hk : 3 ≤ k) (hU : Fintype.card U = 2 ^ k) (v : U → M) (ψ : M → U)
(h7 : Fintype.card M < (2 ^ k - 2 * t * (d - 1)).choose t)
(hd : 2 * t * d ≤ k - 2) (hb : 64 * (2 ^ (2 * t) - 1) ^ d ≤ (2 ^ (2 * t)) ^ d)
(g : Finset U → U) :
∃ Y : Finset U, #Y = k ∧ ∃ u : U,
u ∉ Y.powerset.image (fun A => ψ (∏ x ∈ A, v x)) ∧ u ∉ Y.powerset.image g := by sorry
end Erdos624