AFTD Auto-Formalizing Theoretical Domains

pgroup_coordinate_orbit_orderhom_card_mod

theoremverifiedformalization

Let 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 Fin m, and T a finite partially ordered set. The number of monotone maps from that product to T is congruent modulo p to the number of monotone maps from its orbit quotient, ordered by comparison of representatives, to T.

Statement

theorem pgroup_coordinate_orbit_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; letI : Preorder (MulAction.orbitRel.Quotient G (Fin n → Fin m)) := quotient_poset_preorder n (Fin m) G; Nat.ModEq p (Nat.card ((Fin n → Fin m) →o T)) (Nat.card (MulAction.orbitRel.Quotient G (Fin n → Fin m) →o T))
Formalizes
arXiv:2611.13887, Lemma 9; finite target poset
Verified
12 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • 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).
  • quotient_poset_preorderThe preorder on the quotient poset of orbits of P^n under a subgroup G of S_n acting by coordinate permutations, where orbit Gx is less…
  • coordinate_orbit_invariant_orderhom_isoFor a subgroup of coordinate permutations of the n-fold product of the finite chain Fin m and a partially ordered set T, the pointwise…
  • pgroup_coordinate_invariant_orderhom_card_modFor 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…
  • 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…

Read back from the Lean

Let $p$, $n$, and $m$ be natural numbers with $p$ prime. Let $G$ be a subgroup of the permutation group $\operatorname{Equiv.Perm}(\operatorname{Fin} n)$ which is a $p$-group (every element has order a power of $p$). Let $T$ be a finite partially ordered type. Consider the action of $G$ on functions $\operatorname{Fin} n \to \operatorname{Fin} m$ by permuting coordinates (via coord_perm_mul_action), and endow the orbit quotient $(\operatorname{Fin} n \to \operatorname{Fin} m) / G$ with the preorder (via quotient_poset_preorder) where an orbit $a \le b$ if and only if there exist representatives $x \in a$ and $y \in b$ such that $x \le y$ pointwise. Then the cardinality of the type of order-preserving maps $(\operatorname{Fin} n \to \operatorname{Fin} m) \to T$ (with the pointwise partial order on $\operatorname{Fin} n \to \operatorname{Fin} m$) is congruent modulo $p$ to the cardinality of the type of order-preserving maps from the orbit quotient $(\operatorname{Fin} n \to \operatorname{Fin} m) / G$ to $T$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The strategy is to reduce the count of monotone maps modulo p to the count of G-invariant monotone maps, and then identify those with monotone maps on the orbit space. First, a general p-group congruence shows that the number of monotone maps is congruent modulo p to the number of G-invariant monotone maps. Second, an order isomorphism identifies G-invariant monotone maps with monotone maps out of the orbit quotient poset, so their cardinalities are equal. Combining these two relations by transitivity yields the theorem.

  1. The coordinate permutation action of G on Fin n → Fin m and the induced preorder on the orbit quotient are fixed.

    We activate the action of G by coordinate permutations on the product Fin n → Fin m and the preorder on the orbit quotient (Fin n → Fin m) / G in the local context.

    lines 4–5

      letI : MulAction G (Fin n → Fin m) := coord_perm_mul_action G
      letI : Preorder (MulAction.orbitRel.Quotient G (Fin n → Fin m)) := quotient_poset_preorder n (Fin m) G
  2. There is an order isomorphism e between the G-invariant monotone maps from Fin n → Fin m to T and the monotone maps from the orbit quotient (Fin n → Fin m) / G to T.

    By coordinate_orbit_invariant_orderhom_iso, any G-invariant monotone map factors uniquely through the orbit quotient to yield a monotone map, establishing an order isomorphism e between the two posets.

    line 6

    uses coordinate_orbit_invariant_orderhom_iso

      obtain ⟨e⟩ := coordinate_orbit_invariant_orderhom_iso n m G T
  3. The number of monotone maps from Fin n → Fin m to T is congruent modulo p to the number of monotone maps from the orbit quotient to T.

    By pgroup_coordinate_invariant_orderhom_card_mod, the total number of monotone maps is congruent modulo p to the number of G-invariant monotone maps. Since the order isomorphism e provides a bijection to the monotone maps on the orbit quotient, their cardinalities are equal by Nat.card_congr. The result follows by transitivity of modular congruence.

    lines 7–8

    uses pgroup_coordinate_invariant_orderhom_card_mod, Nat.card_congr

      exact (pgroup_coordinate_invariant_orderhom_card_mod p n m hp G hG T).trans
        (by rw [Nat.card_congr e.toEquiv])
coordinate_orbit_invariant_orderhom_iso
There is an order isomorphism between the poset of G-invariant monotone maps from Fin n → Fin m to T and the poset of monotone maps from the orbit quotient (Fin n → Fin m) / G to T.
pgroup_coordinate_invariant_orderhom_card_mod
For a p-group G acting by coordinate permutations on Fin n → Fin m, the number of monotone maps to T is congruent modulo p to the number of G-invariant monotone maps to T.
Nat.card_congr
A bijection between two types implies that their cardinalities are equal.

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_orbit_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; letI : Preorder (MulAction.orbitRel.Quotient G (Fin n → Fin m)) := quotient_poset_preorder n (Fin m) G; Nat.ModEq p (Nat.card ((Fin n → Fin m) →o T)) (Nat.card (MulAction.orbitRel.Quotient G (Fin n → Fin m) →o T)) := by  letI : MulAction G (Fin n → Fin m) := coord_perm_mul_action G  letI : Preorder (MulAction.orbitRel.Quotient G (Fin n → Fin m)) := quotient_poset_preorder n (Fin m) G  obtain ⟨e⟩ := coordinate_orbit_invariant_orderhom_iso n m G T  exact (pgroup_coordinate_invariant_orderhom_card_mod p n m hp G hG T).trans    (by rw [Nat.card_congr e.toEquiv])
See it in the graphDiscuss this resultChallenge it