Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Herzog-Schönheim conjecture for pyramidal groups

Proved
BFFPyramidal.herzog_schonheim_pyramidal

by burkh4rt · Sep 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricscoset-partitionsgroup-theoryherzog-schonheim

Herzog-Schönheim for pyramidal groups. Let GGG be a pyramidal group and suppose the cosets aiKia_iK_iai​Ki​, 1≤i≤t1 \le i \le t1≤i≤t, partition GGG with t>1t > 1t>1. Then two of the indices coincide:

∃ i≠j,[G:Ki]=[G:Kj].\exists\, i \ne j, \qquad [G : K_i] = [G : K_j].∃i=j,[G:Ki​]=[G:Kj​].

Herzog and Schönheim conjectured this for arbitrary groups; it remains open in general, and is open even for finite solvable groups. It is a consequence of the multiplicity bound of Berger-Felzenbaum-Fraenkel, since that bound is always at least 222.

Formalization note. The conclusion is stated for the indices (K i).index, matching the conjecture as usually stated; for a finite group equality of indices is equivalent to equality of orders. The indices i,ji, ji,j range over the index type Fin t, and i≠ji \ne ji=j refers to distinct indices, so the two cosets are distinct parts of the partition even if the subgroups happen to be equal.

Preamble
import Mathlib
import Definitions.Def_BFFPyramidal_pyramidal
import Definitions.Def_BFFPyramidal_cosetPartition
Formal statement
namespace BFFPyramidal

theorem herzog_schonheim_pyramidal {G : Type*} [Group G] [Finite G] (hG : IsPyramidal G)
    {t : ℕ} (ht : 1 < t) (K : Fin t → Subgroup G) (a : Fin t → G)
    (hpart : IsCosetPartition K a) :
    ∃ i j : Fin t, i ≠ j ∧ (K i).index = (K j).index := by
  sorry

end BFFPyramidal
Source
Berger--Felzenbaum--Fraenkel 1987, Remark on the multiplicity of a partition of a group into cosets, Fund. Math. 128 (1987) 139-144, https://doi.org/10.4064/fm-128-3-139-144, p. 140 (statement of the conjecture) and p. 139 (the Theorem, which implies it for pyramidal groups); original problem: Herzog-Schönheim, Research problem No. 9, Canad. Math. Bull. 17 (1974) 150
Read-back

What the Lean code literally says, in plain math · claude-opus-5

Read-back: BFFPyramidal.herzog_schonheim_pyramidal

Shape of the statement. The declaration asserts a single implication, universally quantified over four objects and three typeclass/propositional hypotheses. In order, the binders are:

  1. GGG — a type, implicit (inferred from later arguments), at an arbitrary universe level;
  2. a instance-implicit assumption that GGG carries a group structure;
  3. a instance-implicit assumption that GGG is finite (mere finiteness of the underlying type, no chosen enumeration);
  4. hGh_GhG​ — an explicit hypothesis that GGG is pyramidal in the sense unfolded below;
  5. ttt — a natural number, implicit;
  6. hth_tht​ — an explicit hypothesis 1<t1 < t1<t, i.e. t≥2t \ge 2t≥2 (strict inequality on 111; t=0t = 0t=0 and t=1t = 1t=1 are excluded);
  7. KKK — an explicit function assigning to each i∈{0,1,…,t−1}i \in \{0, 1, \dots, t-1\}i∈{0,1,…,t−1} a subgroup Ki≤GK_i \le GKi​≤G;
  8. aaa — an explicit function assigning to each i∈{0,…,t−1}i \in \{0,\dots,t-1\}i∈{0,…,t−1} an element ai∈Ga_i \in Gai​∈G;
  9. hparth_{\mathrm{part}}hpart​ — an explicit hypothesis that the family (K,a)(K, a)(K,a) is a coset partition of GGG, unfolded below.

The conclusion is

∃ i, ∃ j∈{0,…,t−1},i≠j ∧ [G:Ki]=[G:Kj].\exists\, i,\ \exists\, j \in \{0,\dots,t-1\},\qquad i \ne j \ \wedge\ [G : K_i] = [G : K_j].∃i, ∃j∈{0,…,t−1},i=j ∧ [G:Ki​]=[G:Kj​].

Both iii and jjj are existentially quantified over the same index set {0,…,t−1}\{0,\dots,t-1\}{0,…,t−1} (of size exactly ttt), the two quantifiers being nested in that order with the conjunction in their common scope. Here [G:Ki][G : K_i][G:Ki​] denotes the index of KiK_iKi​ in GGG, defined as the cardinality of the left-coset space G/KiG / K_iG/Ki​ as a natural number (with the convention that it is 000 when that space is infinite — irrelevant here, since GGG is assumed finite, so every index is a positive natural number dividing ∣G∣|G|∣G∣). The asserted relation between the two indices is equality of natural numbers, not inequality or distinctness: the claim is that among the ttt indices [G:K0],…,[G:Kt−1][G:K_0], \dots, [G:K_{t-1}][G:K0​],…,[G:Kt−1​] there are two positions i≠ji \ne ji=j carrying the same index value. Nothing is asserted about the subgroups Ki,KjK_i, K_jKi​,Kj​ themselves being distinct, about the cosets aiKi,ajKja_iK_i, a_jK_jai​Ki​,aj​Kj​ being distinct, or about which value the common index takes; in particular the conclusion is satisfied outright if Ki=KjK_i = K_jKi​=Kj​ for some i≠ji \ne ji=j.

Unfolding "coset partition" (hparth_{\mathrm{part}}hpart​). The hypothesis IsCosetPartition K a\mathrm{IsCosetPartition}\,K\,aIsCosetPartitionKa states literally:

∀x∈G, ∃! i∈{0,…,t−1},ai−1x∈Ki.\forall x \in G,\ \exists!\, i \in \{0,\dots,t-1\},\qquad a_i^{-1} x \in K_i.∀x∈G, ∃!i∈{0,…,t−1},ai−1​x∈Ki​.

The condition ai−1x∈Kia_i^{-1}x \in K_iai−1​x∈Ki​ is equivalent to x∈aiKix \in a_i K_ix∈ai​Ki​, so this says: every element of GGG lies in the left coset aiKia_iK_iai​Ki​ for exactly one index iii. The uniqueness is over indices, not over cosets: if two indices i≠ji \ne ji=j gave the same coset aiKi=ajKja_iK_i = a_jK_jai​Ki​=aj​Kj​, the hypothesis would fail. Consequently the ttt cosets are pairwise disjoint, cover GGG, and are pairwise distinct as sets; since t≥2t \ge 2t≥2, at least two of them exist and each is nonempty, so ∣G∣≥2|G| \ge 2∣G∣≥2 and ∑i∣Ki∣=∣G∣\sum_{i} |K_i| = |G|∑i​∣Ki​∣=∣G∣, i.e. ∑i[G:Ki]−1=1\sum_i [G:K_i]^{-1} = 1∑i​[G:Ki​]−1=1. (These are consequences, not extra hypotheses.) Note in particular that the hypothesis is unsatisfiable when GGG is the trivial group: then every KiK_iKi​ is the whole group and every index iii satisfies ai−1x∈Kia_i^{-1}x \in K_iai−1​x∈Ki​, contradicting uniqueness for t≥2t \ge 2t≥2. No hypothesis asserts that the KiK_iKi​ are proper, nontrivial, normal, distinct, or of index >1> 1>1; index 111 for some KiK_iKi​ is excluded only indirectly, via the uniqueness clause together with t≥2t \ge 2t≥2.

Unfolding "pyramidal" (hGh_GhG​). IsPyramidal G\mathrm{IsPyramidal}\,GIsPyramidalG (defined only for a type with a group structure and a finiteness instance) states literally:

∃ n∈N, ∃ c:N→{subgroups of G},c0=⊤ ∧ cn=⊥ ∧ ∀k<n, (ck+1≤ck ∧ relIndex(ck+1,ck)=minFac ∣ck∣).\exists\, n \in \mathbb{N},\ \exists\, c : \mathbb{N} \to \{\text{subgroups of } G\},\qquad c_0 = \top \ \wedge\ c_n = \bot \ \wedge\ \forall k < n,\ \big(c_{k+1} \le c_k \ \wedge\ \mathrm{relIndex}(c_{k+1}, c_k) = \mathrm{minFac}\,|c_k|\big).∃n∈N, ∃c:N→{subgroups of G},c0​=⊤ ∧ cn​=⊥ ∧ ∀k<n, (ck+1​≤ck​ ∧ relIndex(ck+1​,ck​)=minFac∣ck​∣).

Here ⊤\top⊤ is GGG itself and ⊥\bot⊥ is the trivial subgroup; ccc is a total function on all of N\mathbb{N}N, so its values at indices >n> n>n are completely unconstrained (junk values are permitted there), and the step condition is imposed exactly for k=0,1,…,n−1k = 0, 1, \dots, n-1k=0,1,…,n−1 (strict k<nk < nk<n). relIndex(ck+1,ck)\mathrm{relIndex}(c_{k+1}, c_k)relIndex(ck+1​,ck​) is the index of ck+1⊓ckc_{k+1} \sqcap c_kck+1​⊓ck​ inside ckc_kck​, which under the accompanying containment ck+1≤ckc_{k+1} \le c_kck+1​≤ck​ equals the ordinary relative index [ck:ck+1][c_k : c_{k+1}][ck​:ck+1​]. ∣ck∣|c_k|∣ck​∣ denotes the order of the subgroup ckc_kck​ (the cardinality of its underlying set, as a natural number), and minFac m\mathrm{minFac}\,mminFacm is the least prime factor of mmm, with the total-function conventions minFac 0=2\mathrm{minFac}\,0 = 2minFac0=2 and minFac 1=1\mathrm{minFac}\,1 = 1minFac1=1. Because minFac 1=1\mathrm{minFac}\,1 = 1minFac1=1, the descent need not be strict: once the chain reaches ⊥\bot⊥ (order 111) it may repeat ⊥\bot⊥ with relative index 111, so nnn is not determined by GGG. Degenerately, n=0n = 0n=0 imposes no step conditions and requires only c0=⊤c_0 = \topc0​=⊤ and c0=⊥c_0 = \botc0​=⊥, so the trivial group is pyramidal; more generally the existential over nnn and ccc makes this a purely existential condition on GGG. Solvability, normality of the steps, and supersolvability appear nowhere in the definition.

Truncation and arithmetic conventions. The statement itself contains no natural-number subtraction and no natural-number division; the only truncating conventions in play are those of minFac\mathrm{minFac}minFac at 000 and 111 inside the pyramidal hypothesis and the "000 when infinite" convention for indices (inert under the finiteness instance). The auxiliary quantity modulus K=∣G∣ / gcd⁡i∣Ki∣\mathrm{modulus}\,K = |G| \,/\, \gcd_i |K_i|modulusK=∣G∣/gcdi​∣Ki​∣ defined in the same imported file (a truncating natural-number division) is not used in this statement.

Degenerate and boundary situations covered. The index type {0,…,t−1}\{0,\dots,t-1\}{0,…,t−1} is nonempty and has at least two elements by hth_tht​, so the conclusion's requirement i≠ji \ne ji=j is not automatically unsatisfiable. The trivial group is admitted by hGh_GhG​ but excluded by hparth_{\mathrm{part}}hpart​ as noted. Nothing prevents KKK from being a constant family together with a suitable aaa (e.g. KiK_iKi​ all equal to a fixed subgroup of index ttt and aaa enumerating coset representatives), in which case the conclusion is immediate.

Proof status. The proof body is sorry: the declaration is stated and admitted, with no proof supplied.

Human review
  • Endorsed by Shuze Chen · Sep 13, 2026

  • Endorsed by burkh4rt · Sep 13, 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 paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me