Lower bound for the size of a union of cosets
ProvedBFFPyramidal.lemma_IVLemma IV. Let be a pyramidal group, let be subgroups of and arbitrary elements. Then
where is the divisor closure and the totient measure.
The cosets are not assumed disjoint: this is a general lower bound on the size of a union of cosets in a pyramidal group, sensitive to the orders of the subgroups rather than merely to their number. It is the step that makes the multiplicity bound possible, since the conclusion of the main theorem counts subgroups of equal order.
Formalization note. The union is a Set G and its size is Set.ncard. is the image of the order function over all indices, so repeated orders are collapsed — is a set, not a multiset. The bound holds for every choice of coset representatives, including , where both sides are .
import Mathlib import Definitions.Def_BFFPyramidal_pyramidal import Definitions.Def_BFFPyramidal_arithmetic open Pointwise
namespace BFFPyramidal
theorem lemma_IV {G : Type*} [Group G] [Finite G] (hG : IsPyramidal G)
{t : ℕ} (K : Fin t → Subgroup G) (a : Fin t → G) :
muMeasure (divisorClosure (Finset.image (fun i => Nat.card (K i)) Finset.univ))
≤ (⋃ i, (a i) • (K i : Set G)).ncard := by
sorry
end BFFPyramidal
Read-back
What the Lean code literally says, in plain math · claude-opus-5
Read-back of BFFPyramidal.lemma_IV.
The declaration asserts the following. Let be a type (implicit argument, so the reader supplies it silently), equipped with two instance assumptions: a group structure on , and the assumption that is finite. One explicit hypothesis is assumed about : that is pyramidal in the sense of the accompanying definition, which unfolds to the existence of a natural number and a function (a total function on all of , constrained only where stated) such that (the top subgroup), (the trivial subgroup), and for every index with both and
where denotes the least prime factor of (with the usual Lean conventions , ) and is the cardinality of the subgroup . Since the containment is asserted, the relative index appearing here coincides with the ordinary index . Descent need not be strict: for with the condition reads , which holds, so the trivial subgroup may repeat and is not pinned down. Note that for the two endpoint conditions force and simultaneously, i.e. trivial, and then the step conditions are vacuous.
Then, quantified universally after that hypothesis: for every natural number (an implicit argument, inferred from the following data), every family of subgroups indexed by the finite type of elements, and every family of group elements , the conclusion is the inequality
Unfolding each piece: is the order of the subgroup as a natural number (a positive number, since is finite, so ; exactly when is trivial). The collection is a finite set of naturals obtained as the image of the index type, so repeated orders are collapsed to a single element: if two indices give subgroups of the same order, that order is counted once. is the divisor closure, defined as the union over of the set of divisors of ; that is, , again as a finite set with duplicates collapsed, so a divisor common to several of the orders appears only once. (The definition uses Lean's divisor function, for which the divisors of form the empty set; this boundary case cannot arise here because subgroup orders are positive.) Finally , the sum of Euler's totient over the elements of the finite set , with . So the left-hand side is
the sum being over each such divisor exactly once.
The right-hand side is the cardinality (as a natural number, via the "ncard" of a set) of the set-theoretic union, over all in the -element index type, of the left cosets , where is viewed as a subset of and the scalar action is pointwise left translation. Because is finite this union is finite and its cardinality is its ordinary number of elements; the union is taken as a set, so overlapping cosets are counted once.
The inequality is non-strict () and is between natural numbers; no subtraction or division occurs, so no truncation issues arise. No hypothesis is imposed on the families and : the subgroups need not be distinct, need not be proper, need not be pairwise non-conjugate, the cosets need not be disjoint, and they need not cover ; nor is assumed positive.
Degenerate cases included by the quantifiers: when the index type is empty, the image set is empty, , , and the union is empty with cardinality , so the claim reads and holds trivially. When the left side is by Gauss's identity and the right side is , so equality holds. If every is the trivial subgroup, the left side is and the right side is the number of distinct elements among the , which is whenever . itself is permitted to be the trivial group.
The pyramidality hypothesis does not appear anywhere in the conclusion; it constrains only the ambient group . The finiteness instance on is what makes the subgroup orders and the union's cardinality meaningful as stated. The proof is not supplied: the body of the declaration is sorry, so the artifact asserts this statement without establishing it.
Confirmed by the mission captain (proposal self-audit).