pgroup_coordinate_invariant_orderhom_card_mod
For prime p and a p-subgroup of the coordinate-permutation group, the number of monotone maps from the n-fold product of the finite chain Fin m to a finite poset is congruent modulo p to the number of those maps invariant under the group.
Statement
theorem pgroup_coordinate_invariant_orderhom_card_mod (p n m : ℕ) (hp : p.Prime) (G : Subgroup (Equiv.Perm (Fin n))) (hG : IsPGroup p G) (T : Type*) [Fintype T] [PartialOrder T] : letI : MulAction G (Fin n → Fin m) := coord_perm_mul_action G; Nat.ModEq p (Nat.card ((Fin n → Fin m) →o T)) (Nat.card {f : (Fin n → Fin m) →o T // ∀ (g : G) (x : Fin n → Fin m), f (g • x) = f x})
- Source
- arXiv:2611.13887, Lemma 4 applied in Lemma 9
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- coord_perm_mul_actionA subgroup of the symmetric group on n elements acts on functions from Fin n to any type by permuting coordinates: (g • x) i = x (g⁻¹ i).
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- pgroup_coordinate_orbit_orderhom_card_modLet p be prime, G a p-subgroup of the permutations of Fin n acting by coordinate permutations on the n-fold product of the finite chain…
The proof, explained
The theorem is proved by applying the fixed-point congruence for p-groups acting on finite sets. The coordinate-permutation action of G on Fin n → Fin m is monotone, which induces an action on the finite space of order homomorphisms (Fin n → Fin m) →o T by (g • f)(x) = f (g⁻¹ • x). By the fixed-point theorem for p-groups, the cardinality of this space is congruent modulo p to the cardinality of its fixed-point set. Finally, an order homomorphism is shown to be a fixed point under this action if and only if it is coordinate-invariant, f (g • x) = f x for all g and x.
The coordinate permutation action of G on Fin n → Fin m is set up, satisfying (g • x) i = x (g⁻¹ i).
We equip the function space Fin n → Fin m with the coordinate permutation action coord_perm_mul_action G, register the primality of p as a Fact typeclass instance, and record the pointwise formula hsmul stating that for every g ∈ G, x : Fin n → Fin m, and index i : Fin n, (g • x) i = x (g⁻¹ i), which holds by definition.
letI : MulAction G (Fin n → Fin m) := coord_perm_mul_action G haveI : Fact p.Prime := ⟨hp⟩ have hsmul : ∀ (g : G) (x : Fin n → Fin m) (i : Fin n), (g • x) i = x (g.1⁻¹ i) := fun _ _ _ => rfl
Each element of G acts monotonically on the poset Fin n → Fin m.
We prove that for every g ∈ G, the map x ↦ g • x preserves the pointwise partial order. Given x ≤ y and an index i, we need x (g⁻¹ i) ≤ y (g⁻¹ i), which is immediate from evaluating the hypothesis x ≤ y at g⁻¹ i.
have hmono : ∀ g : G, Monotone (fun x : Fin n → Fin m => g • x) := by intro g x y h i show x (g.1⁻¹ i) ≤ y (g.1⁻¹ i) exact h _
The group G acts on the space of order homomorphisms (Fin n → Fin m) →o T via (g • f)(x) = f (g⁻¹ • x).
We construct the group action MulAction G ((Fin n → Fin m) →o T). For each g and f, the function x ↦ f (g⁻¹ • x) is monotone because x ↦ g⁻¹ • x is monotone and f is monotone. The identity acts trivially because 1⁻¹ • x = x. Multiplication compatibility holds because ((g * h)⁻¹ • x) = (h⁻¹ * g⁻¹) • x = h⁻¹ • (g⁻¹ • x), verified by mul_inv_rev and mul_smul.
uses
mul_inv_rev,mul_smulletI act : MulAction G ((Fin n → Fin m) →o T) := { smul := fun g f => ⟨fun x => f (g⁻¹ • x), fun x y h => f.monotone (hmono g⁻¹ h)⟩ one_smul := fun f => by ext x show f ((1 : G)⁻¹ • x) = f x simp mul_smul := fun g h f => by ext x show f ((g * h)⁻¹ • x) = f (h⁻¹ • (g⁻¹ • x)) rw [mul_inv_rev, mul_smul] }The space of order homomorphisms (Fin n → Fin m) →o T is finite.
The space of order homomorphisms injects into the function space (Fin n → Fin m) → T via the coercion DFunLike.coe, which is injective by DFunLike.coe_injective. Since Fin n → Fin m and T are both finite, the function space is finite, and Finite.of_injective transfers finiteness to the order homomorphisms.
uses
Finite.of_injective,DFunLike.coe_injectivehave hfin : Finite ((Fin n → Fin m) →o T) := Finite.of_injective (fun f : (Fin n → Fin m) →o T => (f : (Fin n → Fin m) → T)) DFunLike.coe_injective
The number of order homomorphisms is congruent modulo p to the number of fixed points under the G-action.
We apply the orbit-stabilizer fixed-point theorem for p-groups (card_modEq_card_fixedPoints) to the finite G-set (Fin n → Fin m) →o T. By transitivity (key.trans), the remaining goal is to show that the number of fixed points equals the number of coordinate-invariant order homomorphisms.
uses
card_modEq_card_fixedPointshave key := hG.card_modEq_card_fixedPoints ((Fin n → Fin m) →o T) refine key.trans ?_
It suffices to show that an order homomorphism is a fixed point if and only if it is coordinate-invariant.
Unfolding modular congruence reduces the goal to proving that the cardinality of the fixed-point set equals the cardinality of the subtype of invariant maps. By Nat.card_congr and Equiv.subtypeEquivRight, it suffices to prove that the two membership predicates are logically equivalent for every f.
uses
Nat.card_congr,Equiv.subtypeEquivRightunfold Nat.ModEq congr 1 apply Nat.card_congr refine Equiv.subtypeEquivRight ?_
An order homomorphism f is fixed by G if and only if f (g • x) = f x for all g ∈ G and all x.
By MulAction.mem_fixedPoints, f is a fixed point if and only if g' • f = f for all g' ∈ G. In the forward direction, evaluating this at g' = g⁻¹ and applying it to x via DFunLike.congr_fun yields f ((g⁻¹)⁻¹ • x) = f x, which simplifies to f (g • x) = f x. In the reverse direction, assuming f is invariant under all g • x, we compute (g • f) x = f (g⁻¹ • x) = f x by applying invariance with g⁻¹, showing g • f = f for all g.
uses
MulAction.mem_fixedPoints,DFunLike.congr_funintro f rw [MulAction.mem_fixedPoints] constructor · intro h g x have := DFunLike.congr_fun (h g⁻¹) x change f (g⁻¹⁻¹ • x) = f x at this simpa using this · intro h g ext x exact h g⁻¹ x
mul_inv_rev- In any group or division monoid, the inverse of a product is the product of the inverses in reverse order: $(a * b)⁻¹ = b⁻¹ * a⁻¹$.
mul_smul- In a group action, multiplying group elements before acting agrees with successive actions: $(x * y) • b = x • y • b$.
Finite.of_injective- If a type injects into a finite type, then it is finite.
DFunLike.coe_injective- Two morphisms that agree as functions on all inputs are equal; that is, the coercion to a function is injective.
card_modEq_card_fixedPoints- When a p-group acts on a finite set, the cardinality of the set is congruent modulo p to the cardinality of its fixed-point set.
Nat.card_congr- Equivalent types (types connected by a bijection) have the same cardinality.
Equiv.subtypeEquivRight- Subtypes defined by logically equivalent predicates on the same underlying type are in natural bijection.
MulAction.mem_fixedPoints- An element belongs to the fixed points of a group action if and only if it is fixed by every element of the group.
DFunLike.congr_fun- If two morphisms are equal, then their values agree on any argument.
- The definition of the induced action on order homomorphisms uses the inverse $g^{-1}$ in $(g • f)(x) = f(g^{-1} • x)$ to ensure a left action (so that $(g * h) • f = g • (h • f)$); the equivalence between fixed points under this action and coordinate-invariant functions accounts for this inversion.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open scoped Classicaltheorem pgroup_coordinate_invariant_orderhom_card_mod (p n m : ℕ) (hp : p.Prime) (G : Subgroup (Equiv.Perm (Fin n))) (hG : IsPGroup p G) (T : Type*) [Fintype T] [PartialOrder T] : letI : MulAction G (Fin n → Fin m) := coord_perm_mul_action G; Nat.ModEq p (Nat.card ((Fin n → Fin m) →o T)) (Nat.card {f : (Fin n → Fin m) →o T // ∀ (g : G) (x : Fin n → Fin m), f (g • x) = f x}) := by letI : MulAction G (Fin n → Fin m) := coord_perm_mul_action G haveI : Fact p.Prime := ⟨hp⟩ have hsmul : ∀ (g : G) (x : Fin n → Fin m) (i : Fin n), (g • x) i = x (g.1⁻¹ i) := fun _ _ _ => rfl have hmono : ∀ g : G, Monotone (fun x : Fin n → Fin m => g • x) := by intro g x y h i show x (g.1⁻¹ i) ≤ y (g.1⁻¹ i) exact h _ letI act : MulAction G ((Fin n → Fin m) →o T) := { smul := fun g f => ⟨fun x => f (g⁻¹ • x), fun x y h => f.monotone (hmono g⁻¹ h)⟩ one_smul := fun f => by ext x show f ((1 : G)⁻¹ • x) = f x simp mul_smul := fun g h f => by ext x show f ((g * h)⁻¹ • x) = f (h⁻¹ • (g⁻¹ • x)) rw [mul_inv_rev, mul_smul] } have hfin : Finite ((Fin n → Fin m) →o T) := Finite.of_injective (fun f : (Fin n → Fin m) →o T => (f : (Fin n → Fin m) → T)) DFunLike.coe_injective have key := hG.card_modEq_card_fixedPoints ((Fin n → Fin m) →o T) refine key.trans ?_ unfold Nat.ModEq congr 1 apply Nat.card_congr refine Equiv.subtypeEquivRight ?_ intro f rw [MulAction.mem_fixedPoints] constructor · intro h g x have := DFunLike.congr_fun (h g⁻¹) x change f (g⁻¹⁻¹ • x) = f x at this simpa using this · intro h g ext x exact h g⁻¹ x