Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The multiplicity inequality

Proved
SubnormalCover.lcm_le_indexMultiplicity_mul_sigma

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

combinatoricsgroup-theory

Let G1,…,GkG_1,\dots,G_kG1​,…,Gk​ (k≥1k\ge 1k≥1) and HHH be finite-index subgroups of a group GGG, with every GiG_iGi​ subnormal and HHH normal in GGG, and let a1,…,ak∈Ga_1,\dots,a_k\in Ga1​,…,ak​∈G be such that ⋃iaiGi\bigcup_{i} a_iG_i⋃i​ai​Gi​ coincides with a union of left cosets of HHH. Write h=[G:H]h=[G:H]h=[G:H], ni=[G:Gi]n_i=[G:G_i]ni​=[G:Gi​], g=(n1,…,nk)g=(n_1,\dots,n_k)g=(n1​,…,nk​), L=[n1,…,nk]L=[n_1,\dots,n_k]L=[n1​,…,nk​], and let MMM be any upper bound for the multiplicities ∣{i:ni=n}∣|\{i : n_i=n\}|∣{i:ni​=n}∣. Then case (a) of Sun's Theorem 3.2, eq. (3.8), states g(h,g)≤M∑d∣L/g1d\dfrac{g}{(h,g)}\le M\sum_{d\mid L/g}\dfrac1d(h,g)g​≤M∑d∣L/g​d1​. Formalization note. Multiplying (3.8) by (h,g)⋅(L/g)(h,g)\cdot(L/g)(h,g)⋅(L/g) and using ∑d∣m1/d=σ(m)/m\sum_{d\mid m}1/d=\sigma(m)/m∑d∣m​1/d=σ(m)/m together with g⋅(L/g)=Lg\cdot(L/g)=Lg⋅(L/g)=L gives the equivalent denominator-free form stated here, L≤M (h,g) ∑d∣L/gdL\le M\,(h,g)\,\sum_{d\mid L/g}dL≤M(h,g)∑d∣L/g​d; the hypotheses 0<k0<k0<k and [G:Gi]≠0[G:G_i]\neq 0[G:Gi​]=0 are not cosmetic, since the gcd over an empty index set is 000 (which would truncate the natural-number division and make the claim false) and an infinite index would collapse both sides to 000.

Preamble
import Mathlib
import Definitions.Def_SubnormalCover_uniformCover

open Pointwise
Formal statement
namespace SubnormalCover

theorem lcm_le_indexMultiplicity_mul_sigma {G : Type*} [Group G] {k : ℕ} (hk : 0 < k)
    (K : Fin k → Subgroup G) (a : Fin k → G) (H : Subgroup G) [H.Normal]
    (hHfin : H.index ≠ 0) (hKfin : ∀ i, (K i).index ≠ 0) (hsn : ∀ i, (K i).IsSubnormal)
    (hunion : ∀ x ∈ ⋃ i, (a i) • (K i : Set G), ∀ y ∈ H,
      x * y ∈ ⋃ i, (a i) • (K i : Set G))
    (M : ℕ) (hM : ∀ m, indexMultiplicity K m ≤ M) :
    coverLcm K ≤
      M * Nat.gcd H.index (Finset.univ.gcd fun i => (K i).index) *
        ∑ d ∈ (coverLcm K / Finset.univ.gcd fun i => (K i).index).divisors, d := by
  sorry

end SubnormalCover
Source
Z.-W. Sun, On the Herzog-Schönheim conjecture for uniform covers of groups, J. Algebra 273 (2004) 153-175, https://doi.org/10.1016/S0021-8693(03)00526-X, Theorem 3.2, eq. (3.8), case (a)
Read-back

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

Setting. Let GGG be an arbitrary type carrying a group structure (no finiteness, commutativity or other assumption on GGG), and let kkk be a natural number with 0<k0 < k0<k (so the index type Fin k={0,1,…,k−1}\mathrm{Fin}\,k = \{0,1,\dots,k-1\}Fink={0,1,…,k−1} is nonempty). We are given:

  • a family of subgroups K0,…,Kk−1≤GK_0,\dots,K_{k-1} \le GK0​,…,Kk−1​≤G (indexed by Fin k\mathrm{Fin}\,kFink; the KiK_iKi​ are not assumed pairwise distinct, so the same subgroup may be repeated);
  • a family of group elements a0,…,ak−1∈Ga_0,\dots,a_{k-1} \in Ga0​,…,ak−1​∈G;
  • a further subgroup H≤GH \le GH≤G which is assumed normal in GGG (supplied as an instance hypothesis);
  • (hHfin)(hHfin)(hHfin) the hypothesis [G:H]≠0[G:H] \ne 0[G:H]=0, and (hKfin)(hKfin)(hKfin) the hypothesis that [G:Ki]≠0[G:K_i] \ne 0[G:Ki​]=0 for every iii. Here [G:S][G:S][G:S] denotes Mathlib's Subgroup.index, defined as the cardinality #(G/S)\#(G/S)#(G/S) of the set of left cosets of SSS, with the convention that this cardinality is 000 when G/SG/SG/S is infinite; thus "≠0\ne 0=0" is exactly the statement "SSS has finite index". In particular [G:H]≥1[G:H]\ge 1[G:H]≥1 and [G:Ki]≥1[G:K_i]\ge 1[G:Ki​]≥1 for all iii;
  • (hsn)(hsn)(hsn) the hypothesis that every KiK_iKi​ is subnormal in GGG, in Mathlib's inductive sense: ⊤=G\top = G⊤=G is subnormal, and if S≤TS \le TS≤T, TTT is subnormal and SSS is normal as a subgroup of TTT, then SSS is subnormal — equivalently there is a finite chain Ki=S0⊴S1⊴⋯⊴Sn=GK_i = S_0 \trianglelefteq S_1 \trianglelefteq \cdots \trianglelefteq S_n = GKi​=S0​⊴S1​⊴⋯⊴Sn​=G, each term normal in the next;
  • (hunion)(hunion)(hunion) a closure hypothesis on the union of the left cosets: writing U=⋃iaiKi⊆GU = \bigcup_{i} a_i K_i \subseteq GU=⋃i​ai​Ki​⊆G (with aiKia_i K_iai​Ki​ the pointwise left translate {aig:g∈Ki}\{a_i g : g \in K_i\}{ai​g:g∈Ki​}), for every x∈Ux \in Ux∈U and every y∈Hy \in Hy∈H we have xy∈Ux y \in Uxy∈U. That is, UUU is stable under right multiplication by HHH; nothing else relates HHH to the KiK_iKi​, and nothing asserts that UUU is all of GGG or that the cosets are disjoint — the elements aia_iai​ occur nowhere else in the statement;
  • a natural number MMM together with (hM)(hM)(hM): for every natural number mmm (ranging over all of N\mathbb{N}N, including m=0m = 0m=0 and values not attained by any index), the multiplicity #{i∈Fin k:[G:Ki]=m}\#\{i \in \mathrm{Fin}\,k : [G:K_i] = m\}#{i∈Fink:[G:Ki​]=m} is ≤M\le M≤M. Since k≥1k \ge 1k≥1, taking m=[G:K0]m = [G:K_0]m=[G:K0​] forces M≥1M \ge 1M≥1; for m=0m=0m=0 the multiplicity is 000 by (hKfin)(hKfin)(hKfin), so that instance is vacuous.

Conclusion. Put

N  =  lcm⁡([G:K0],…,[G:Kk−1]),g  =  gcd⁡([G:K0],…,[G:Kk−1]),N \;=\; \operatorname{lcm}\big([G:K_0],\dots,[G:K_{k-1}]\big), \qquad g \;=\; \gcd\big([G:K_0],\dots,[G:K_{k-1}]\big),N=lcm([G:K0​],…,[G:Kk−1​]),g=gcd([G:K0​],…,[G:Kk−1​]),

both taken as the Finset lcm/gcd over all i∈Fin ki \in \mathrm{Fin}\,ki∈Fink (the empty conventions lcm⁡∅=1\operatorname{lcm}\varnothing = 1lcm∅=1, gcd⁡∅=0\gcd\varnothing = 0gcd∅=0 are not reachable here because k≥1k \ge 1k≥1; with (hKfin)(hKfin)(hKfin) we have N≥1N \ge 1N≥1 and g≥1g \ge 1g≥1). Then the theorem asserts the single inequality

N  ≤  M⋅gcd⁡ ⁣([G:H], g)⋅ ⁣ ⁣∑d ∈ divisors(N/g) ⁣ ⁣d,N \;\le\; M \cdot \gcd\!\big([G:H],\, g\big) \cdot \!\!\sum_{d \,\in\, \mathrm{divisors}(N/g)}\!\! d ,N≤M⋅gcd([G:H],g)⋅d∈divisors(N/g)∑​d,

where all arithmetic is in N\mathbb{N}N: the product is parsed as (M⋅gcd⁡([G:H],g))⋅σ\big(M \cdot \gcd([G:H],g)\big)\cdot \sigma(M⋅gcd([G:H],g))⋅σ, the quotient N/gN/gN/g is natural-number (floor) division — here it happens to be exact, since ggg divides each [G:Ki][G:K_i][G:Ki​] and each [G:Ki][G:K_i][G:Ki​] divides NNN — and divisors(n)\mathrm{divisors}(n)divisors(n) is Mathlib's finite set of positive divisors of nnn, with divisors(0)=∅\mathrm{divisors}(0) = \varnothingdivisors(0)=∅ and divisors(1)={1}\mathrm{divisors}(1) = \{1\}divisors(1)={1}, so the sum is the classical divisor-sum σ(N/g)\sigma(N/g)σ(N/g) (and would be 000 on the unreachable input N/g=0N/g = 0N/g=0).

Degenerate situations the statement allows. If every Ki=GK_i = GKi​=G then all indices are 111, N=g=1N = g = 1N=g=1, N/g=1N/g = 1N/g=1, σ(1)=1\sigma(1) = 1σ(1)=1, gcd⁡([G:H],1)=1\gcd([G:H],1)=1gcd([G:H],1)=1, and the claim reduces to 1≤M1 \le M1≤M, which holds since M≥k≥1M \ge k \ge 1M≥k≥1. The hypothesis (hunion)(hunion)(hunion) is satisfied outright by H={1}H = \{1\}H={1} (then y=1y = 1y=1 and xy=xxy = xxy=x), a choice permitted whenever [G:{1}]=#G≠0[G:\{1\}] = \#G \ne 0[G:{1}]=#G=0, i.e. whenever GGG is finite; it is also satisfied by taking all Ki=GK_i = GKi​=G and any HHH. The subnormality hypothesis (hsn)(hsn)(hsn) and the elements aia_iai​ place no further constraint on the numerical quantities appearing in the conclusion beyond what is stated. No relation between HHH and the family (Ki)(K_i)(Ki​) other than (hunion)(hunion)(hunion) is assumed, and the case k=0k = 0k=0 is excluded by (hk)(hk)(hk).

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

  • Endorsed by burkh4rt · Sep 14, 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