Challenge 2: the scaled excluded-minor statement
DefinitionTenChallenges_Challenge_02The scaled form of Challenge 2. For natural numbers and , the statement says:
"At most excluded minors up to isomorphism" is the predicate of the companion definition. The statement is monotone: implies for and , and it is vacuous for . Known rungs are (Tutte), (Bixby, Seymour) and (Geelen, Gerards, Kapoor).
Formalization Note. The primality of enters as the instance argument [Fact p.Prime], as required by GaloisField p m.
import Definitions.Def_TenChallenges_MatroidRepresentability namespace TenChallenges /-- For every prime power `pᵐ ≤ r`, the excluded minors for `GF(pᵐ)`-representability number at most `B` up to isomorphism. -/ def statement_02 (r B : ℕ) : Prop := ∀ (p m : ℕ) [Fact p.Prime], 0 < m → p ^ m ≤ r → ExcludedMinorsAtMost p m B end TenChallenges
Read-back
What the Lean code literally says, in plain math · claude-fable-5-1
Read-back of TenChallenges.statement_02 r B (a proposition depending on two natural numbers and ).
The definition asserts: for all natural numbers and , and for every proof that is prime (a typeclass hypothesis Fact p.Prime bound inside the universal quantifier, so in effect: for every prime and every natural ),
where is the bundle definition from item TenChallenges_MatroidRepresentability, which unfolds as follows.
Matroids. A matroid on a type is Mathlib's Matroid γ: a ground set (possibly infinite or empty) with "base" and "independent" predicates on subsets of such that a set is independent iff it lies in some base, some base exists, bases satisfy the exchange axiom, every independent subset of any extends to a maximal independent subset of , and bases lie in ; hence independent sets lie in and is independent.
-representability ( for a matroid on ): there exist a type in the lowest universe, an additive commutative group structure on , a vector-space structure on over (Mathlib's GaloisField p m, the splitting field of over ; for the field with elements), and a function defined on all of , such that for every subset (not only subsets of ),
where linear independence of the family indexed by the elements of means that is injective on finitely supported coefficient functions (repeated vectors or a zero vector make the family dependent; the empty family is independent). Since independent sets lie in , this forces for all . No bound on .
Excluded minor ( for ): , and for every matroid on the same type with , holds. Here is Mathlib's strict minor relation: and not , where means for some sets (not required disjoint or inside ), with the restriction of to and the contraction (ground set ). Mathlib documents as equivalent to " is a minor of and ". If has no strict minors (e.g. ), the second clause is vacuous.
Isomorphism (, a bundle definition): there is a bijection such that for every , is independent in iff is independent in .
: there exists a finite set of matroids on the type (ground sets arbitrary subsets of ) with such that for every type in the lowest universe and every matroid on with finite, if is an excluded minor for -representability (as unfolded above, with minors taken among matroids on ), then some satisfies . Members of need not be excluded minors, finite, or pairwise non-isomorphic; forces and then asserts that no finite excluded minor exists; infinite excluded minors are unconstrained.
Edge cases of itself: the hypothesis excludes (so always has elements here). For no pair with prime, , exists, so holds vacuously for every . For the single number must serve simultaneously as the bound for every prime power with (e.g. for : ). The hypotheses mention only ; nothing depends on otherwise.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.