Uniform covers of a group by cosets
DefinitionSubnormalCover_uniformCoverA finite system of left cosets of a group is a uniform cover of weight when the covering function of Sun's equation (1.2) is constant, equal to . The case is a coset partition, the setting of the Herzog-Schönheim conjecture; a uniform cover need not have any disjoint subcover at all.
IsUniformCover K a w says that for every the number of indices with is exactly w. The count is Nat.card of a subtype, so no decidability hypothesis is needed, and the family is indexed by Fin k so that multiplicities stay visible — every conclusion in this mission counts indices, not distinct subgroups. A cover is trivial when every is the whole group; nontriviality is deliberately not folded into the definition and appears as the explicit hypothesis ∃ i, K i ≠ ⊤ wherever it is needed, since without it the results are false.
Also defined here: coverLcm K, the modulus , the least common multiple of the indices , whose prime divisors are exactly those of the product ; and indexMultiplicity K m, the number of indices with , of which the paper's is a uniform bound.
import Mathlib
namespace SubnormalCover
/-- A finite system of left cosets `a i • K i`, `i : Fin k`, is a **uniform cover** of `G` with
weight `w` if the covering function `w_A(x) = |{i : x ∈ a i K i}|` of Z.-W. Sun's equation (1.2)
is constant, equal to `w`.
The membership `x ∈ a i • K i` is spelled `(a i)⁻¹ * x ∈ K i`, and the count is `Nat.card` of the
subtype of such indices, so that no decidability assumption is needed.
The case `w = 1` is a **disjoint cover**, i.e. a partition of `G` into cosets; this is the setting
of the Herzog-Schönheim conjecture. A uniform cover is called **trivial** when `K i = ⊤` for every
`i`; nontriviality is expressed in the statements below as `∃ i, K i ≠ ⊤`, and is never folded
into this definition. -/
def IsUniformCover {G : Type*} [Group G] {k : ℕ} (K : Fin k → Subgroup G) (a : Fin k → G)
(w : ℕ) : Prop :=
∀ x : G, Nat.card {i : Fin k // (a i)⁻¹ * x ∈ K i} = w
/-- The **modulus** `N = [n₁, …, n_k]` of a system of cosets: the least common multiple of the
indices `n i = [G : K i]`. Its prime divisors are exactly those of the product `n₁ ⋯ n_k`, which
is the quantity named in the abstract of the source. -/
noncomputable def coverLcm {G : Type*} [Group G] {k : ℕ} (K : Fin k → Subgroup G) : ℕ :=
Finset.univ.lcm fun i => (K i).index
/-- The **multiplicity** of the value `m` among the indices, i.e. `|{i : [G : K i] = m}|`. The
quantity `M` of the source is a bound for this, uniform in `m`. -/
noncomputable def indexMultiplicity {G : Type*} [Group G] {k : ℕ} (K : Fin k → Subgroup G) (m : ℕ) : ℕ :=
(Finset.univ.filter fun i => (K i).index = m).card
end SubnormalCover
Read-back
What the Lean code literally says, in plain math · claude-opus-5
SubnormalCover.IsUniformCover
What is declared. This is a definition (a predicate, i.e. a Prop-valued function), not a theorem; nothing is proved. Its parameters are:
- an implicit type in an arbitrary universe, carrying an arbitrary group structure (the only typeclass assumption; no finiteness, no commutativity, no decidable equality, no topology);
- an implicit natural number , allowed to be ;
- an explicit family , i.e. subgroups of , indexed by the finite type of size — these are arbitrary subgroups, with no assumption of finite index, normality, subnormality, or distinctness (repetitions are allowed, and any or all may equal or );
- an explicit family of group elements, again arbitrary and possibly repeating;
- an explicit natural number .
What the predicate says. is by definition the proposition
where the condition is exactly membership of in the left coset . The cardinality is Mathlib's Nat.card of the subtype of those indices satisfying the condition; because that subtype is a subtype of a finite type of size , it is always finite, so this cardinality is the ordinary count and never takes the junk value -for-infinite. Thus the definition asserts that the covering multiplicity function is constant on all of , with the constant value being the given number — an equality of natural numbers, not an inequality, and required for every element of , with no exceptions and no ambient hypothesis that the cosets cover (that is a consequence only when ).
Degenerate cases the quantifiers allow.
- : the index type is empty, so the count is for every , and (since a group is nonempty) the predicate holds precisely when .
- with : the predicate demands that no lies in any ; taking (which lies in since ) makes this unsatisfiable, so for the predicate with is never true. Consequently the definition is satisfiable with only for , and with only for .
- Every : the count is for every , so the predicate holds exactly when . Nothing in the definition excludes this case; the accompanying comment's notions of "disjoint cover" () and "trivial cover" are not part of the formal content, and no nontriviality condition such as is imposed here.
- infinite, or the of infinite index, are all permitted; nothing constrains or .
- Right cosets are not used: the condition is left-coset membership .
SubnormalCover.coverLcm
What is declared. A definition of a natural number (marked as noncomputable, which affects only code generation, not the mathematical value); nothing is asserted or proved. Its parameters are an implicit type in an arbitrary universe with an arbitrary group structure (the only typeclass assumption — no finiteness), an implicit natural number (possibly ), and an explicit family of subgroups of indexed by the finite type of size . Note that the element family plays no role here and is absent.
Value. is the least common multiple, taken in over all indices, of the subgroup indices:
Here is Mathlib's Subgroup.index, defined as the cardinality (via Nat.card) of the coset space — the type of left cosets of in , which exists for an arbitrary, not necessarily normal, subgroup — with the standing convention that Nat.card of an infinite type is , so exactly when has infinite index in . In particular and (which is when is infinite). No FiniteIndex hypothesis is imposed.
Degenerate cases.
- : the least common multiple is taken over the empty index set, and Mathlib's finite-set of the empty family is the unit ; so when .
- If any single has infinite index, then that index is and with is , so the whole value collapses to .
- Repeated subgroups contribute nothing extra (lcm is idempotent), and subgroups equal to contribute the factor .
- The remark in the source comment about the prime divisors of this number coinciding with those of the product is commentary only; it is not part of the definition and nothing is proved about it here.
SubnormalCover.indexMultiplicity
What is declared. A definition of a natural number (marked noncomputable, presumably because the equality test on indices is decided classically; this does not change the value); nothing is asserted or proved. Its parameters are an implicit type in an arbitrary universe with an arbitrary group structure (the only typeclass assumption — no finiteness), an implicit natural number (possibly ), an explicit family of subgroups of indexed by the finite type of size , and an explicit natural number . The coset representatives do not appear.
Value. is the number of indices whose subgroup index equals :
i.e. the cardinality of the subset of the -element index set cut out by the exact equality (an equality, not a divisibility or an inequality). As above, is Subgroup.index, the Nat.card of the left-coset space , which is by convention when the index is infinite. Counting is by index position, not by distinct subgroup: if two different positions carry the same subgroup, or merely subgroups of the same index, both are counted.
Degenerate cases.
- : the index set is empty, so the value is for every .
- : the definition counts exactly those positions at which has infinite index in , since is the infinite-index convention — it does not count "nothing".
- : counts the positions with (index ).
- Values of realized by no give ; the total over all occurring is .
- The source comment's statement that a quantity bounds this uniformly in is commentary only; no bound, and no relation to any uniform-cover hypothesis, is part of this definition.
Confirmed by the mission captain (proposal self-audit).