Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Challenge 2: the scaled excluded-minor statement S(r,B)S(r,B)S(r,B)

Definition
TenChallenges_Challenge_02

by utkuokur · Nov 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

excluded-minorsmatroidsrepresentabilityten-challenges

The scaled form of Challenge 2. For natural numbers rrr and BBB, the statement S(r,B)S(r,B)S(r,B) says:

for every prime p and every m≥1 with pm≤r, the class of GF(pm)-representable matroids has at most B excluded minors up to isomorphism.\text{for every prime } p \text{ and every } m\ge 1 \text{ with } p^m\le r,\ \text{the class of } \mathrm{GF}(p^m)\text{-representable matroids has at most } B \text{ excluded minors up to isomorphism.}for every prime p and every m≥1 with pm≤r, the class of GF(pm)-representable matroids has at most B excluded minors up to isomorphism.

"At most BBB excluded minors up to isomorphism" is the predicate ExcludedMinorsAtMost(p,m,B)\mathrm{ExcludedMinorsAtMost}(p,m,B)ExcludedMinorsAtMost(p,m,B) of the companion definition. The statement is monotone: S(r,B)S(r,B)S(r,B) implies S(r′,B′)S(r',B')S(r′,B′) for r′≤rr'\le rr′≤r and B′≥BB'\ge BB′≥B, and it is vacuous for r≤1r\le 1r≤1. Known rungs are S(2,1)S(2,1)S(2,1) (Tutte), S(3,4)S(3,4)S(3,4) (Bixby, Seymour) and S(4,7)S(4,7)S(4,7) (Geelen, Gerards, Kapoor).

Formalization Note. The primality of ppp enters as the instance argument [Fact p.Prime], as required by GaloisField p m.

Definition code
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
Source
Ten Challenges repository, file Challenges/challenge_02.lean (commit ff14a56), https://github.com/TenChallenges/ten-challenges/blob/main/Challenges/challenge_02.lean; V. Bajpai, N. Bowler, J. Carmesin, U. Okur, 10 Scalable Challenges in Combinatorics, AI4Math @ CICM 2026, challenge 2.
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 rrr and BBB).

The definition asserts: for all natural numbers ppp and mmm, and for every proof that ppp is prime (a typeclass hypothesis Fact p.Prime bound inside the universal quantifier, so in effect: for every prime ppp and every natural mmm),

0<m   and   pm≤r⟹ExcludedMinorsAtMost(p,m,B),0 < m \;\text{ and }\; p^{m} \le r \quad\Longrightarrow\quad \mathrm{ExcludedMinorsAtMost}(p, m, B),0<m and pm≤r⟹ExcludedMinorsAtMost(p,m,B),

where ExcludedMinorsAtMost(p,m,B)\mathrm{ExcludedMinorsAtMost}(p, m, B)ExcludedMinorsAtMost(p,m,B) is the bundle definition from item TenChallenges_MatroidRepresentability, which unfolds as follows.

Matroids. A matroid MMM on a type γ\gammaγ is Mathlib's Matroid γ: a ground set E(M)⊆γE(M) \subseteq \gammaE(M)⊆γ (possibly infinite or empty) with "base" and "independent" predicates on subsets of γ\gammaγ 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 X⊆E(M)X \subseteq E(M)X⊆E(M) extends to a maximal independent subset of XXX, and bases lie in E(M)E(M)E(M); hence independent sets lie in E(M)E(M)E(M) and ∅\emptyset∅ is independent.

GF(pm)\mathrm{GF}(p^m)GF(pm)-representability (IsGFRepresentable(p,m,M)\mathrm{IsGFRepresentable}(p,m,M)IsGFRepresentable(p,m,M) for a matroid MMM on γ\gammaγ): there exist a type WWW in the lowest universe, an additive commutative group structure on WWW, a vector-space structure on WWW over GF(pm)\mathrm{GF}(p^m)GF(pm) (Mathlib's GaloisField p m, the splitting field of Xpm−XX^{p^m}-XXpm−X over Z/pZ\mathbb{Z}/p\mathbb{Z}Z/pZ; for m≥1m \ge 1m≥1 the field with pmp^mpm elements), and a function v:γ→Wv : \gamma \to Wv:γ→W defined on all of γ\gammaγ, such that for every subset I⊆γI \subseteq \gammaI⊆γ (not only subsets of E(M)E(M)E(M)),

I independent in M  ⟺  (v(x))x∈I linearly independent over GF(pm),I \text{ independent in } M \iff (v(x))_{x\in I} \text{ linearly independent over } \mathrm{GF}(p^m),I independent in M⟺(v(x))x∈I​ linearly independent over GF(pm),

where linear independence of the family indexed by the elements of III means that c↦∑x∈Icxv(x)c \mapsto \sum_{x \in I} c_x v(x)c↦∑x∈I​cx​v(x) 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 E(M)E(M)E(M), this forces v(x)=0v(x)=0v(x)=0 for all x∉E(M)x \notin E(M)x∈/E(M). No bound on dim⁡W\dim WdimW.

Excluded minor (IsExcludedMinorFor(P,M)\mathrm{IsExcludedMinorFor}(P, M)IsExcludedMinorFor(P,M) for P=IsGFRepresentable(p,m,⋅)P = \mathrm{IsGFRepresentable}(p,m,\cdot)P=IsGFRepresentable(p,m,⋅)): ¬P(M)\neg P(M)¬P(M), and for every matroid NNN on the same type γ\gammaγ with N<mMN <_m MN<m​M, P(N)P(N)P(N) holds. Here N<mMN <_m MN<m​M is Mathlib's strict minor relation: N≤mMN \le_m MN≤m​M and not M≤mNM \le_m NM≤m​N, where N≤mMN \le_m MN≤m​M means N=(M/C)∖DN = (M/C)\setminus DN=(M/C)∖D for some sets C,D⊆γC, D \subseteq \gammaC,D⊆γ (not required disjoint or inside E(M)E(M)E(M)), with M∖DM \setminus DM∖D the restriction of MMM to E(M)∖DE(M)\setminus DE(M)∖D and M/C=(M∗∖C)∗M/C = (M^*\setminus C)^*M/C=(M∗∖C)∗ the contraction (ground set E(M)∖CE(M) \setminus CE(M)∖C). Mathlib documents N<mMN <_m MN<m​M as equivalent to "NNN is a minor of MMM and N≠MN \ne MN=M". If MMM has no strict minors (e.g. E(M)=∅E(M)=\emptysetE(M)=∅), the second clause is vacuous.

Isomorphism (IsIso(N,M)\mathrm{IsIso}(N, M)IsIso(N,M), a bundle definition): there is a bijection e:E(N)→E(M)e : E(N) \to E(M)e:E(N)→E(M) such that for every I⊆E(N)I \subseteq E(N)I⊆E(N), III is independent in NNN iff e(I)e(I)e(I) is independent in MMM.

ExcludedMinorsAtMost(p,m,B)\mathrm{ExcludedMinorsAtMost}(p, m, B)ExcludedMinorsAtMost(p,m,B): there exists a finite set SSS of matroids on the type N\mathbb{N}N (ground sets arbitrary subsets of N\mathbb{N}N) with ∣S∣≤B|S| \le B∣S∣≤B such that for every type β\betaβ in the lowest universe and every matroid MMM on β\betaβ with E(M)E(M)E(M) finite, if MMM is an excluded minor for GF(pm)\mathrm{GF}(p^m)GF(pm)-representability (as unfolded above, with minors taken among matroids on β\betaβ), then some N∈SN \in SN∈S satisfies IsIso(N,M)\mathrm{IsIso}(N, M)IsIso(N,M). Members of SSS need not be excluded minors, finite, or pairwise non-isomorphic; B=0B=0B=0 forces S=∅S=\emptysetS=∅ and then asserts that no finite excluded minor exists; infinite excluded minors are unconstrained.

Edge cases of statement_02\mathrm{statement\_02}statement_02 itself: the hypothesis 0<m0 < m0<m excludes m=0m = 0m=0 (so GF(pm)\mathrm{GF}(p^m)GF(pm) always has pm≥2p^m \ge 2pm≥2 elements here). For r≤1r \le 1r≤1 no pair (p,m)(p, m)(p,m) with ppp prime, m≥1m \ge 1m≥1, pm≤rp^m \le rpm≤r exists, so statement_02(r,B)\mathrm{statement\_02}(r, B)statement_02(r,B) holds vacuously for every BBB. For r≥2r \ge 2r≥2 the single number BBB must serve simultaneously as the bound for every prime power pm≤rp^m \le rpm≤r with m≥1m \ge 1m≥1 (e.g. for r=4r = 4r=4: 21,31,222^1, 3^1, 2^221,31,22). The hypotheses mention only pm≤rp^m \le rpm≤r; nothing depends on rrr otherwise.

Human review
  • Endorsed by Shuze Chen · Nov 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by utkuokur · Nov 4, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me