AFTD Auto-Formalizing Theoretical Domains

pgroup_coordinate_invariant_orderhom_card_mod

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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.

  1. 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.

    lines 4–7

      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
  2. 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.

    lines 8–11

      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 _
  3. 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.

    lines 12–21

    uses mul_inv_rev, mul_smul

      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] }
  4. 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.

    lines 22–24

    uses Finite.of_injective, DFunLike.coe_injective

      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
  5. 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.

    lines 25–26

    uses card_modEq_card_fixedPoints

      have key := hG.card_modEq_card_fixedPoints ((Fin n → Fin m) →o T)
      refine key.trans ?_
  6. 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.

    lines 27–30

    uses Nat.card_congr, Equiv.subtypeEquivRight

      unfold Nat.ModEq
      congr 1
      apply Nat.card_congr
      refine Equiv.subtypeEquivRight ?_
  7. 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.

    lines 31–40

    uses MulAction.mem_fixedPoints, DFunLike.congr_fun

      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
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.

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

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
See it in the graphDiscuss this resultChallenge it