Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Multiplicity of a coset partition of a pyramidal group

Proved
BFFPyramidal.multiplicity_bound

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

combinatoricscoset-partitionsgroup-theoryherzog-schonheim

Main theorem (Berger-Felzenbaum-Fraenkel). Let GGG be a pyramidal group and suppose the cosets aiKia_iK_iai​Ki​, 1≤i≤t1 \le i \le t1≤i≤t, with Ki≤GK_i \le GKi​≤G and ai∈Ga_i \in Gai​∈G, partition GGG. If t>1t > 1t>1, then at least

x  =  ⌊P(l) φ(l)l⌋+1x \;=\; \left\lfloor \frac{P(l)\,\varphi(l)}{l} \right\rfloor + 1x=⌊lP(l)φ(l)​⌋+1

of the subgroups KiK_iKi​ have the same order, where

l  =  ∣G∣gcd⁡ ⁣(∣K1∣,…,∣Kt∣),l \;=\; \frac{|G|}{\gcd\!\left(|K_1|,\dots,|K_t|\right)},l=gcd(∣K1​∣,…,∣Kt​∣)∣G∣​,

PPP is the greatest prime factor and φ\varphiφ is Euler's totient function.

Since x≥2x \ge 2x≥2 for l≥2l \ge 2l≥2, this proves the conjectures of Herzog-Schönheim and of Burshtein for pyramidal groups; the authors had previously established the Herzog-Schönheim conjecture for finite nilpotent groups, which form a subclass.

Formalization note. The conclusion is stated as the existence of an order mmm such that the number of indices iii with ∣Ki∣=m|K_i| = m∣Ki​∣=m is at least xxx; counting indices (not distinct subgroups) is the faithful reading, since several KiK_iKi​ may coincide. The floor is natural-number division. The hypothesis t>1t > 1t>1 is necessary: for t=1t = 1t=1 the partition is GGG itself, l=1l = 1l=1, and the bound degenerates.

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

theorem multiplicity_bound {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) :
    ∃ m : ℕ, (maxPrimeFac (modulus K) * Nat.totient (modulus K)) / modulus K + 1
      ≤ (Finset.univ.filter fun i => Nat.card (K i) = m).card := 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. 139, THEOREM with eqs. (3)-(4)
Read-back

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

Read-back: BFFPyramidal.multiplicity_bound

Shape of the declaration. The statement quantifies, in this order, over: a type GGG in an arbitrary universe (implicit, inferred from later arguments); an instance-implicit group structure on GGG; an instance-implicit witness that GGG is finite; an explicit hypothesis hGhGhG asserting GGG is pyramidal in the custom sense unfolded below; an implicit natural number ttt; an explicit hypothesis 1<t1 < t1<t (strict, so t≥2t \ge 2t≥2; t=0t = 0t=0 and t=1t = 1t=1 are excluded); an explicit family of subgroups Ki≤GK_i \le GKi​≤G indexed by i∈{0,1,…,t−1}i \in \{0,1,\dots,t-1\}i∈{0,1,…,t−1}; an explicit family of group elements ai∈Ga_i \in Gai​∈G indexed by the same finite index set; and an explicit hypothesis hparthparthpart that the left cosets aiKia_i K_iai​Ki​ partition GGG. The conclusion is an existential over a natural number mmm.

Unfolding "pyramidal" (hGhGhG). The hypothesis says: there exist a natural number nnn and a function c:N→{subgroups of G}c : \mathbb{N} \to \{\text{subgroups of } G\}c:N→{subgroups of G} — a total function on all of N\mathbb{N}N, so its values at indices >n> n>n are unconstrained — such that

c0=G (the top subgroup),cn={1} (the trivial subgroup),c_0 = G \ (\text{the top subgroup}), \qquad c_n = \{1\} \ (\text{the trivial subgroup}),c0​=G (the top subgroup),cn​={1} (the trivial subgroup),

and for every kkk with k<nk < nk<n (strictly), both

ck+1≤ckand[ ck:ck+1∩ck ]=minFac⁡(∣ck∣),c_{k+1} \le c_k \qquad \text{and} \qquad \big[\,c_k : c_{k+1} \cap c_k\,\big] = \operatorname{minFac}\big(|c_k|\big),ck+1​≤ck​and[ck​:ck+1​∩ck​]=minFac(∣ck​∣),

where the index used is Mathlib's relative index of ck+1c_{k+1}ck+1​ in ckc_kck​ (the index of ck+1∩ckc_{k+1} \cap c_kck+1​∩ck​ in ckc_kck​, which under the stated containment is the ordinary index [ck:ck+1][c_k : c_{k+1}][ck​:ck+1​]), ∣ck∣|c_k|∣ck​∣ is the cardinality of the subgroup ckc_kck​ as a type, and minFac⁡(x)\operatorname{minFac}(x)minFac(x) is the least prime factor of xxx with the conventions minFac⁡(0)=2\operatorname{minFac}(0) = 2minFac(0)=2 and minFac⁡(1)=1\operatorname{minFac}(1) = 1minFac(1)=1. Descent is not required to be strict; in particular n=0n = 0n=0 is allowed, in which case the two boundary conditions force G=c0={1}G = c_0 = \{1\}G=c0​={1} and there are no step conditions, so the trivial group is pyramidal. No normality, solvability, or supersolvability is asserted or assumed.

Unfolding "coset partition" (hparthparthpart). The hypothesis says: for every x∈Gx \in Gx∈G there is a unique index i∈{0,…,t−1}i \in \{0,\dots,t-1\}i∈{0,…,t−1} with ai−1x∈Kia_i^{-1} x \in K_iai−1​x∈Ki​, i.e. every element of GGG lies in exactly one of the ttt left cosets aiKia_i K_iai​Ki​. The indices are distinct even when the cosets coincide as sets, so uniqueness of iii forbids repeating the same coset twice; the subgroups KiK_iKi​ themselves may repeat.

Unfolding the modulus. Write

g  =  gcd⁡i∈{0,…,t−1}∣Ki∣,l  =  ⌊∣G∣g⌋,g \;=\; \gcd_{i \in \{0,\dots,t-1\}} |K_i|, \qquad l \;=\; \left\lfloor \frac{|G|}{g} \right\rfloor,g=i∈{0,…,t−1}gcd​∣Ki​∣,l=⌊g∣G∣​⌋,

where ∣G∣|G|∣G∣ and ∣Ki∣|K_i|∣Ki​∣ are the cardinalities of GGG and of each subgroup, and the gcd is taken over the whole finite index set (for t≥2t \ge 2t≥2 this set is nonempty; had ttt been 000 the empty gcd would be 000 and the division would be the junk value x/0=0x/0 = 0x/0=0). The division is truncating natural-number division; since each ∣Ki∣|K_i|∣Ki​∣ divides ∣G∣|G|∣G∣, the quotient here is in fact exact and l≥1l \ge 1l≥1. This lll is the quantity called the modulus.

Unfolding the greatest prime factor. P(m)P(m)P(m) denotes the supremum of the finite set of prime factors of mmm, taken in N\mathbb{N}N with the empty supremum equal to 000; hence P(0)=P(1)=0P(0) = P(1) = 0P(0)=P(1)=0, and otherwise P(m)P(m)P(m) is the largest prime dividing mmm.

The conclusion. There exists a natural number mmm (unconstrained: mmm need not be positive, prime, a divisor of ∣G∣|G|∣G∣, or the order of any KiK_iKi​) such that

⌊P(l)⋅φ(l)l⌋+1  ≤  #{ i∈{0,…,t−1}  :  ∣Ki∣=m },\left\lfloor \frac{P(l)\cdot \varphi(l)}{l} \right\rfloor + 1 \;\le\; \#\{\, i \in \{0,\dots,t-1\} \;:\; |K_i| = m \,\},⌊lP(l)⋅φ(l)​⌋+1≤#{i∈{0,…,t−1}:∣Ki​∣=m},

where φ\varphiφ is Euler's totient (φ(0)=0\varphi(0) = 0φ(0)=0, φ(1)=1\varphi(1) = 1φ(1)=1), the division is truncating natural-number division, the +1+1+1 is added after truncation, and the right-hand side is the number of indices iii whose subgroup KiK_iKi​ has cardinality exactly mmm. The inequality is non-strict, and its left-hand side does not depend on mmm.

Degenerate and boundary behaviour. The left-hand side is always at least 111. It equals exactly 111 whenever P(l)φ(l)<lP(l)\varphi(l) < lP(l)φ(l)<l — for instance when l=1l = 1l=1 (then P(1)=0P(1) = 0P(1)=0, φ(1)=1\varphi(1) = 1φ(1)=1, so the left side is 0+1=10 + 1 = 10+1=1), and more generally whenever the truncated quotient vanishes. In all such cases the conclusion asserts only that some natural number mmm is the order of at least one of the subgroups KiK_iKi​, which holds because the index set is nonempty (t≥2t \ge 2t≥2); choosing m=∣K0∣m = |K_0|m=∣K0​∣ suffices. Also φ(l)≤l\varphi(l) \le lφ(l)≤l for l≥1l \ge 1l≥1, so the truncated quotient never exceeds P(l)P(l)P(l), and the left-hand side is bounded above by P(l)+1P(l) + 1P(l)+1. Because GGG is finite, every ∣Ki∣≥1|K_i| \ge 1∣Ki​∣≥1, so the choice m=0m = 0m=0 always yields count 000. The auxiliary definitions divisorClosure (the divisor closure of a finite set of naturals) and muMeasure (the totient-sum measure) from the imported arithmetic file do not appear in the statement. The proof is sorry (the theorem is stated but not proved in this artifact).

Hypothesis usage as visible in the statement. The conclusion mentions only KKK, ttt, and the cardinalities of GGG and the KiK_iKi​; the elements aia_iai​ occur only inside hparthparthpart, and hGhGhG (pyramidality) constrains only GGG. Whether hGhGhG or hparthparthpart is needed for the inequality is not determined by the statement itself; both are assumed.

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