Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Proposition 46, p. 31 — the coset complex of Theorem 45 has dimension d − 1, is good and has no empty squares

Proved
MulticlassDS.NatGap.prop46_coset_complex_good

by mikedeng1 · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

coset-complexgood-complexgroup-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1simplicial-complex

Let FFF be a finite group, d>1d > 1d>1, and H1,…,Hd≤FH_1, \dots, H_d \le FH1​,…,Hd​≤F subgroups such that

  1. (⋂j≠iHj)∖Hi≠∅\big(\bigcap_{j \neq i} H_j\big) \setminus H_i \neq \emptyset(⋂j=i​Hj​)∖Hi​=∅ for every i∈[d]i \in [d]i∈[d], and
  2. the coset complex C=CF(H1,…,Hd)C = C_F(H_1, \dots, H_d)C=CF​(H1​,…,Hd​) contains no empty square.

Then CCC has dimension d−1d - 1d−1, is good (finite, pure, properly colorable with ddd colors, and satisfies replacement), and has no empty squares.

This is the step that turns the group-theoretic construction of Theorem 45 into a good complex, from which Proposition 42 produces a ddd-dimensional pseudo-cube.

Formalization Note The hypotheses are exactly "as in Theorem 45". The dimension is d−1d - 1d−1 with natural-number subtraction, which is exact because d>1d > 1d>1; the coloring then takes values in Fin (d - 1 + 1), i.e. ddd colors.

Preamble
import Mathlib
import Definitions.Def_MulticlassDS_NatGap_Dimensions
import Definitions.Def_MulticlassDS_NatGap_Complexes
Formal statement
namespace MulticlassDS.NatGap

theorem prop46_coset_complex_good {F : Type*} [Group F] [Finite F] (d : ℕ) (hd : 1 < d)
    (Hs : Fin d → Subgroup F)
    (h1 : ∀ i : Fin d, ∃ z : F, (∀ j : Fin d, j ≠ i → z ∈ Hs j) ∧ z ∉ Hs i)
    (h2 : NoEmptySquares (cosetComplex Hs)) :
    IsGood (cosetComplex Hs) (d - 1) ∧ NoEmptySquares (cosetComplex Hs) := by sorry

end MulticlassDS.NatGap
Source
Brukhim, Carmon, Dinur, Moran, Yehudayoff, A Characterization of Multiclass Learnability, arXiv:2203.01550v1, p. 31, Proposition 46
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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