perm_order_eq_prod_and_sum_prime_power_parts_le
Let k ≥ 1. If q is the order of some permutation of k elements and S(q) is the set of maximal prime-power divisors of q, then q = ∏_{s∈S(q)} s and ∑_{s∈S(q)} s ≤ k.
Statement
theorem perm_order_eq_prod_and_sum_prime_power_parts_le (k : ℕ) (hk : 1 ≤ k) (q : ℕ)
(hq : ∃ σ : Equiv.Perm (Fin k), orderOf σ = q) :
q = ∏ s ∈ nat_prime_power_parts q, s ∧ ∑ s ∈ nat_prime_power_parts q, s ≤ k- Formalizes
- arXiv:2610.11098 (An improved lower bound for separating words by permutation automata), Lemma 2.3.
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- nat_prime_power_partsS(q): the set of maximal prime-power divisors of q, i.e. p^(v_p(q)) for each prime p dividing q.
- nat_prime_power_parts_oneS(1) = ∅.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - supportThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…
The proof, explained
The theorem establishes that for the order q of any permutation σ of k elements, q is the product of its maximal prime-power divisors, and their sum is at most k. The product formula follows from the uniqueness and injectivity of prime factorizations. The sum inequality is established by cycle induction on permutations to bound the sum of prime-power parts by the size of the permutation's support. For a single cycle, the order equals the support size and exceeds the sum of its prime-power divisors; for disjoint products, the order is the least common multiple whose prime powers embed into the union of the components. Finally, since the support of any permutation on k elements has size at most k, the sum is bounded by k.
For finite sets A and B of natural numbers, the sum over their union is bounded by the sum over A plus the sum over B.
By inclusion-exclusion (Finset.sum_union_inter), the sum over A ∪ B plus the sum over A ∩ B equals the sum over A plus the sum over B. Since all elements are non-negative, omega concludes the inequality.
uses
Finset.sum_union_interhave := Finset.sum_union_inter (f := fun (x:ℕ) => x) (s₁ := A) (s₂ := B) omega
If a finite set S is contained in A ∪ B, then the sum over S is bounded by the sum over A plus the sum over B.
Since S ⊆ A ∪ B and all terms are non-negative (Nat.zero_le), the sum over S is at most the sum over A ∪ B by Finset.sum_le_sum_of_subset_of_nonneg. Combining this with the union bound perm_order_eq_prod_and_sum_prime_power_parts_le_sum_union_le_nat gives the result.
uses
Finset.sum_le_sum_of_subset_of_nonneg,Nat.zero_le,perm_order_eq_prod_and_sum_prime_power_parts_le_sum_union_le_nathave h1 : ∑ s ∈ S, s ≤ ∑ s ∈ A ∪ B, s := Finset.sum_le_sum_of_subset_of_nonneg hsub (fun _ _ _ => Nat.zero_le _) have h2 : ∑ s ∈ A ∪ B, s ≤ ∑ s ∈ A, s + ∑ s ∈ B, s := perm_order_eq_prod_and_sum_prime_power_parts_le_sum_union_le_nat A B exact h1.trans h2
For non-zero a and b, any element of the prime-power parts of lcm(a, b) has exponent equal to the maximum of its valuations in a and b.
An element of S(lcm(a, b)) has the form p^(v_p(lcm(a, b))) for a prime factor p (Finset.mem_image.mp, Nat.mem_primeFactors). By Nat.factorization_lcm, the valuation in lcm(a, b) is max(v_p(a), v_p(b)).
uses
Finset.mem_image.mp,Nat.mem_primeFactors,Nat.factorization_lcmintro s hs unfold nat_prime_power_parts at hs ⊢ rcases Finset.mem_image.mp hs with ⟨p, hp, rfl⟩ rw [Nat.mem_primeFactors] at hp have hlcm_fact : (a.lcm b).factorization p = max (a.factorization p) (b.factorization p) := by have hf := Nat.factorization_lcm ha hb rw [hf] rfl rw [hlcm_fact]
If v_p(b) ≤ v_p(a), the prime-power part p^(v_p(lcm(a, b))) belongs to the prime-power parts of a.
When v_p(b) ≤ v_p(a) (via le_total), max_eq_left gives max(v_p(a), v_p(b)) = v_p(a). The positive valuation implies p ∣ a (Nat.dvd_of_factorization_pos), placing the prime power in S(a) via Finset.mem_image.mpr and thus in S(a) ∪ S(b) via Finset.mem_union_left.
uses
le_total,max_eq_left,Finset.mem_union_left,Finset.mem_image.mpr,Nat.mem_primeFactors,Nat.dvd_of_factorization_posrcases le_total (b.factorization p) (a.factorization p) with hle | hle · rw [max_eq_left hle] apply Finset.mem_union_left apply Finset.mem_image.mpr refine ⟨p, ?_, rfl⟩ rw [Nat.mem_primeFactors] refine ⟨hp.1, ?_, ha⟩ have hpos : 0 < (a.lcm b).factorization p := hp.1.factorization_pos_of_dvd hp.2.2 hp.2.1 rw [hlcm_fact, max_eq_left hle] at hpos exact Nat.dvd_of_factorization_pos hpos.ne'
If v_p(a) ≤ v_p(b), the prime-power part p^(v_p(lcm(a, b))) belongs to the prime-power parts of b.
Symmetrically, when v_p(a) ≤ v_p(b), max_eq_right simplifies the exponent to v_p(b). The positive valuation implies p ∣ b (Nat.dvd_of_factorization_pos), so the prime power is in S(b) (Finset.mem_image.mpr) and in the union (Finset.mem_union_right).
uses
max_eq_right,Finset.mem_union_right,Finset.mem_image.mpr,Nat.mem_primeFactors,Nat.dvd_of_factorization_pos· rw [max_eq_right hle] apply Finset.mem_union_right apply Finset.mem_image.mpr refine ⟨p, ?_, rfl⟩ rw [Nat.mem_primeFactors] refine ⟨hp.1, ?_, hb⟩ have hpos : 0 < (a.lcm b).factorization p := hp.1.factorization_pos_of_dvd hp.2.2 hp.2.1 rw [hlcm_fact, max_eq_right hle] at hpos exact Nat.dvd_of_factorization_pos hpos.ne'
The map sending a prime factor p of q to p^(v_p(q)) is injective on the prime factors of q.
If p^(v_p(q)) = p'^(v_p'(q)), then since v_p(q) > 0, p divides p'^(v_p'(q)) by dvd_pow_self. Being prime, p must divide p', which forces p = p'.
uses
Nat.mem_primeFactors,dvd_pow_selfintro p hp p' hp' h dsimp at h simp only [Finset.mem_coe, Nat.mem_primeFactors] at hp hp' have ha : q.factorization p ≠ 0 := by have := hp.1.factorization_pos_of_dvd hp.2.2 hp.2.1 omega have hdvd : p ∣ p' ^ q.factorization p' := by rw [← h] exact dvd_pow_self p ha have hprime_dvd := hp.1.dvd_of_dvd_pow hdvd exact (hp'.1.eq_one_or_self_of_dvd p hprime_dvd).resolve_left hp.1.ne_one
Every non-zero natural number q equals the product of its prime-power parts.
By injectivity of the prime-power map (perm_order_eq_prod_and_sum_prime_power_parts_le_injOn), Finset.prod_image rewrites the product over S(q) as the product of p^(v_p(q)) over all prime factors, which equals q by Nat.prod_primeFactors_pow_factorization.
uses
perm_order_eq_prod_and_sum_prime_power_parts_le_injOn,Finset.prod_image,Nat.prod_primeFactors_pow_factorizationunfold nat_prime_power_parts rw [Finset.prod_image (perm_order_eq_prod_and_sum_prime_power_parts_le_injOn q)] exact Nat.prod_primeFactors_pow_factorization hq
Every prime-power part of q is at least 2.
Each s ∈ S(q) is p^(v_p(q)) for a prime p dividing q (Finset.mem_image.mp, Nat.mem_primeFactors). Since p ≥ 2 and v_p(q) ≥ 1, we have 2 ≤ p ≤ p^(v_p(q)) by Nat.le_self_pow.
uses
Finset.mem_image.mp,Nat.mem_primeFactors,Nat.le_self_powunfold nat_prime_power_parts at hs rcases Finset.mem_image.mp hs with ⟨p, hp, rfl⟩ rw [Nat.mem_primeFactors] at hp have hpos : 0 < q.factorization p := hp.1.factorization_pos_of_dvd hp.2.2 hp.2.1 have hp2 : 2 ≤ p := hp.1.two_le calc 2 ≤ p := hp2 _ ≤ p ^ q.factorization p := Nat.le_self_pow hpos.ne' _
For any finite set s of integers each at least 2, the sum is bounded by the product in the base case and when inserting into an empty set.
We proceed by induction on s (Finset.induction_on). For s = ∅, the sum is 0 and the product is 1, so 0 ≤ 1. When inserting a into an empty set, the sum and product are both a, so a ≤ a holds trivially.
uses
Finset.induction_on,Finset.sum_insert,Finset.prod_insert,Finset.mem_insert_self,Finset.mem_insert_of_memclassical induction s using Finset.induction_on with | empty => simp | insert a s has ih => simp only [Finset.sum_insert has, Finset.prod_insert has] have ha : 2 ≤ a := h a (Finset.mem_insert_self a s) have hs : ∀ x ∈ s, 2 ≤ x := fun x hx => h x (Finset.mem_insert_of_mem hx) have ih' := ih hs rcases s.eq_empty_or_nonempty with rfl | hne · simp
For a non-empty finite set s of integers each at least 2, inserting a ≥ 2 preserves the inequality sum ≤ prod. automation
Choosing an element y ∈ s with y ≥ 2, y divides the product (Finset.dvd_prod_of_mem), so the product is at least 2 (Nat.le_of_dvd, Finset.prod_pos). Combined with a ≥ 2 and the induction hypothesis, nlinarith closes a + ∑ x ≤ a * ∏ x.
uses
Finset.dvd_prod_of_mem,Finset.prod_pos,Nat.le_of_dvd· have hprod : 2 ≤ ∏ x ∈ s, x := by obtain ⟨y, hy⟩ := hne have hy2 : 2 ≤ y := hs y hy have hdiv : y ∣ ∏ x ∈ s, x := Finset.dvd_prod_of_mem (fun x => x) hy have hpos : 0 < ∏ x ∈ s, x := by apply Finset.prod_pos intro x hx have := hs x hx omega exact Nat.le_of_dvd hpos hdiv |>.trans' hy2 nlinarith
For any non-zero natural number c, the sum of its prime-power parts is at most c.
Since all prime-power parts of c are at least 2 (perm_order_eq_prod_and_sum_prime_power_parts_le_two_le), their sum is bounded by their product (perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_prod). By perm_order_eq_prod_and_sum_prime_power_parts_le_prod, this product equals c.
uses
perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_prod,perm_order_eq_prod_and_sum_prime_power_parts_le_two_le,perm_order_eq_prod_and_sum_prime_power_parts_le_prodhave := perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_prod (nat_prime_power_parts c) (fun _ hx => perm_order_eq_prod_and_sum_prime_power_parts_le_two_le hx) rw [← perm_order_eq_prod_and_sum_prime_power_parts_le_prod c hc] at this exact this
For the identity permutation, the sum of the prime-power parts of its order is at most the cardinality of its support.
We apply cycle induction (Equiv.Perm.cycle_induction_on). For σ = 1, orderOf 1 = 1 (orderOf_one), its set of prime-power parts is empty (nat_prime_power_parts_one), so the sum is 0 (Finset.sum_empty). The support is empty (Equiv.Perm.support_one), having cardinality 0 (Finset.card_empty), so 0 ≤ 0.
uses
Equiv.Perm.cycle_induction_on,orderOf_one,nat_prime_power_parts_one,Finset.sum_empty,Equiv.Perm.support_one,Finset.card_emptyrefine Equiv.Perm.cycle_induction_on (fun σ => ∑ s ∈ nat_prime_power_parts (orderOf σ), s ≤ σ.support.card) σ ?_ ?_ ?_ · rw [orderOf_one, nat_prime_power_parts_one, Finset.sum_empty, Equiv.Perm.support_one, Finset.card_empty]
For a single cycle τ, the sum of the prime-power parts of its order is at most the size of its support.
The order of a cycle is non-zero (orderOf_pos), and the sum of its prime-power parts is at most its order by perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_self. For a cycle, its order equals the size of its support.
uses
orderOf_pos,perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_self· intro τ hτ have hord : orderOf τ ≠ 0 := (orderOf_pos τ).ne' have := perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_self (orderOf τ) hord rw [← hτ.orderOf] exact this
The bound extends from a cycle τ and a disjoint permutation π to their product τ * π.
The order of τ * π is lcm(orderOf τ, orderOf π). Its prime-power parts are contained in the union of those of τ and π (perm_order_eq_prod_and_sum_prime_power_parts_le_lcm_subset), so the sum is at most the sum of the two parts (perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_sum_union_le). Disjointness gives |supp(τ * π)| = |supp(τ)| + |supp(π)| (Finset.card_union_of_disjoint), and the induction hypotheses finish the bound.
uses
orderOf_pos,perm_order_eq_prod_and_sum_prime_power_parts_le_lcm_subset,perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_sum_union_le,Finset.card_union_of_disjoint· intro τ π hd hτ ihτ ihπ have hτ_pos : orderOf τ ≠ 0 := (orderOf_pos τ).ne' have hπ_pos : orderOf π ≠ 0 := (orderOf_pos π).ne' rw [hd.orderOf] have hsub := perm_order_eq_prod_and_sum_prime_power_parts_le_lcm_subset (orderOf τ) (orderOf π) hτ_pos hπ_pos have hsum := perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_sum_union_le _ _ _ hsub have hsupp : (τ * π).support.card = τ.support.card + π.support.card := by rw [hd.support_mul, Finset.card_union_of_disjoint hd.disjoint_support] rw [hsupp] omega
For any permutation σ of k elements with order q, q equals the product of its prime-power parts and their sum is at most k.
Since orderOf σ ≠ 0 (orderOf_pos), the product equality follows from perm_order_eq_prod_and_sum_prime_power_parts_le_prod. The sum of the prime-power parts is bounded by |supp(σ)| (perm_order_eq_prod_and_sum_prime_power_parts_le_support), which is at most the total number of elements k (Fintype.card_fin).
uses
orderOf_pos,perm_order_eq_prod_and_sum_prime_power_parts_le_prod,perm_order_eq_prod_and_sum_prime_power_parts_le_support,Fintype.card_finrcases hq with ⟨σ, rfl⟩ have hq0 : orderOf σ ≠ 0 := (orderOf_pos σ).ne' refine ⟨perm_order_eq_prod_and_sum_prime_power_parts_le_prod (orderOf σ) hq0, ?_⟩ have hle := perm_order_eq_prod_and_sum_prime_power_parts_le_support σ have hcard : σ.support.card ≤ k := by have := σ.support.card_le_univ rwa [Fintype.card_fin] at this exact hle.trans hcard
Finset.sum_union_inter- For any two finite sets, the sum over their union plus the sum over their intersection equals the sum of the sums over each set.
Finset.sum_le_sum_of_subset_of_nonneg- If s ⊆ t and f is non-negative outside s, then the sum of f over s is at most that over t.
Nat.zero_le- Every natural number is greater than or equal to zero.
perm_order_eq_prod_and_sum_prime_power_parts_le_sum_union_le_nat- For finite sets of natural numbers A and B, the sum over their union is bounded by the sum over A plus the sum over B.
Finset.mem_image.mp- If an element belongs to the image of a set under f, then it is the image of some element in that set.
Finset.mem_image.mpr- If an element is the image of some element in a set under f, then it belongs to the image of that set.
Nat.mem_primeFactors- A number p is in the prime factors of n if and only if p is prime, p divides n, and n ≠ 0.
Nat.factorization_lcm- For non-zero natural numbers a and b, the prime factorization of their least common multiple is the pointwise maximum of their factorizations.
le_total- In any linear order, for any two elements a and b, either a ≤ b or b ≤ a.
max_eq_left- If b ≤ a, then max a b = a.
max_eq_right- If a ≤ b, then max a b = b.
Finset.mem_union_left- If an element belongs to s, then it belongs to s ∪ t.
Finset.mem_union_right- If an element belongs to t, then it belongs to s ∪ t.
Nat.dvd_of_factorization_pos- If the exponent of p in the prime factorization of n is non-zero, then p divides n.
dvd_pow_self- Any non-zero power of a is divisible by a.
perm_order_eq_prod_and_sum_prime_power_parts_le_injOn- The map sending each prime factor p to p raised to its multiplicity is injective.
Finset.prod_image- If g is injective on s, then the product of f over the image of s under g equals the product of f ∘ g over s.
Nat.prod_primeFactors_pow_factorization- Every non-zero natural number equals the product over its prime factors of p raised to its multiplicity.
Nat.le_self_pow- For any non-zero exponent n, a ≤ a^n.
Finset.induction_on- To prove a statement for all finite sets, it suffices to prove it for the empty set and show it is preserved by inserting an element.
Finset.sum_insert- Inserting an element a into a set s adds f(a) to the sum of f over s.
Finset.prod_insert- Inserting an element a into a set s multiplies the product of f over s by f(a).
Finset.mem_insert_self- An element belongs to the set obtained by inserting it into s.
Finset.mem_insert_of_mem- An element in s remains in the set after inserting another element into s.
Finset.dvd_prod_of_mem- Any element of a finite set divides the product of the set's elements.
Finset.prod_pos- A product of strictly positive natural numbers over a finite set is strictly positive.
Nat.le_of_dvd- If m divides a strictly positive natural number n, then m ≤ n.
perm_order_eq_prod_and_sum_prime_power_parts_le_two_le- Every prime-power part of a natural number q is at least 2.
perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_prod- For any finite set of natural numbers each at least 2, their sum is at most their product.
perm_order_eq_prod_and_sum_prime_power_parts_le_prod- Every non-zero natural number equals the product of its prime-power parts.
perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_self- For any non-zero natural number c, the sum of its prime-power parts is at most c.
Equiv.Perm.cycle_induction_on- To prove a property for all permutations, it suffices to check the identity, cycles, and products of a cycle with a disjoint permutation.
orderOf_one- The order of the identity permutation is 1.
nat_prime_power_parts_one- The set of prime-power parts of 1 is empty.
Finset.sum_empty- The sum over the empty set is 0.
Equiv.Perm.support_one- The support of the identity permutation is empty.
Finset.card_empty- The cardinality of the empty set is 0.
orderOf_pos- The order of an element in a finite group is strictly positive.
perm_order_eq_prod_and_sum_prime_power_parts_le_lcm_subset- The prime-power parts of lcm(a, b) are contained in the union of the prime-power parts of a and b.
perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_sum_union_le- If S is a subset of A ∪ B, the sum over S is at most the sum over A plus the sum over B.
Finset.card_union_of_disjoint- The cardinality of the union of disjoint finite sets is the sum of their cardinalities.
perm_order_eq_prod_and_sum_prime_power_parts_le_support- The sum of the prime-power parts of the order of a permutation is at most the size of its support.
Fintype.card_fin- The cardinality of the type Fin n is n.
- In step 10, the step establishing the inequality a + P ≤ aP for a ≥ 2 and P ≥ 2 relies on nonlinear arithmetic automation (nlinarith).
- In lemma 9 (steps 12-14), induction on the permutation cycle decomposition is handled by Mathlib's cycle induction principle Equiv.Perm.cycle_induction_on.
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.
lemma perm_order_eq_prod_and_sum_prime_power_parts_le_sum_union_le_nat (A B : Finset ℕ) : ∑ s ∈ A ∪ B, s ≤ ∑ s ∈ A, s + ∑ s ∈ B, s := by have := Finset.sum_union_inter (f := fun (x:ℕ) => x) (s₁ := A) (s₂ := B) omegalemma perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_sum_union_le (A B S : Finset ℕ) (hsub : S ⊆ A ∪ B) : ∑ s ∈ S, s ≤ ∑ s ∈ A, s + ∑ s ∈ B, s := by have h1 : ∑ s ∈ S, s ≤ ∑ s ∈ A ∪ B, s := Finset.sum_le_sum_of_subset_of_nonneg hsub (fun _ _ _ => Nat.zero_le _) have h2 : ∑ s ∈ A ∪ B, s ≤ ∑ s ∈ A, s + ∑ s ∈ B, s := perm_order_eq_prod_and_sum_prime_power_parts_le_sum_union_le_nat A B exact h1.trans h2lemma perm_order_eq_prod_and_sum_prime_power_parts_le_lcm_subset (a b : ℕ) (ha : a ≠ 0) (hb : b ≠ 0) : nat_prime_power_parts (a.lcm b) ⊆ nat_prime_power_parts a ∪ nat_prime_power_parts b := by intro s hs unfold nat_prime_power_parts at hs ⊢ rcases Finset.mem_image.mp hs with ⟨p, hp, rfl⟩ rw [Nat.mem_primeFactors] at hp have hlcm_fact : (a.lcm b).factorization p = max (a.factorization p) (b.factorization p) := by have hf := Nat.factorization_lcm ha hb rw [hf] rfl rw [hlcm_fact] rcases le_total (b.factorization p) (a.factorization p) with hle | hle · rw [max_eq_left hle] apply Finset.mem_union_left apply Finset.mem_image.mpr refine ⟨p, ?_, rfl⟩ rw [Nat.mem_primeFactors] refine ⟨hp.1, ?_, ha⟩ have hpos : 0 < (a.lcm b).factorization p := hp.1.factorization_pos_of_dvd hp.2.2 hp.2.1 rw [hlcm_fact, max_eq_left hle] at hpos exact Nat.dvd_of_factorization_pos hpos.ne' · rw [max_eq_right hle] apply Finset.mem_union_right apply Finset.mem_image.mpr refine ⟨p, ?_, rfl⟩ rw [Nat.mem_primeFactors] refine ⟨hp.1, ?_, hb⟩ have hpos : 0 < (a.lcm b).factorization p := hp.1.factorization_pos_of_dvd hp.2.2 hp.2.1 rw [hlcm_fact, max_eq_right hle] at hpos exact Nat.dvd_of_factorization_pos hpos.ne'lemma perm_order_eq_prod_and_sum_prime_power_parts_le_injOn (q : ℕ) : Set.InjOn (fun p => p ^ q.factorization p) q.primeFactors := by intro p hp p' hp' h dsimp at h simp only [Finset.mem_coe, Nat.mem_primeFactors] at hp hp' have ha : q.factorization p ≠ 0 := by have := hp.1.factorization_pos_of_dvd hp.2.2 hp.2.1 omega have hdvd : p ∣ p' ^ q.factorization p' := by rw [← h] exact dvd_pow_self p ha have hprime_dvd := hp.1.dvd_of_dvd_pow hdvd exact (hp'.1.eq_one_or_self_of_dvd p hprime_dvd).resolve_left hp.1.ne_onelemma perm_order_eq_prod_and_sum_prime_power_parts_le_prod (q : ℕ) (hq : q ≠ 0) : q = ∏ s ∈ nat_prime_power_parts q, s := by unfold nat_prime_power_parts rw [Finset.prod_image (perm_order_eq_prod_and_sum_prime_power_parts_le_injOn q)] exact Nat.prod_primeFactors_pow_factorization hqlemma perm_order_eq_prod_and_sum_prime_power_parts_le_two_le {q s : ℕ} (hs : s ∈ nat_prime_power_parts q) : 2 ≤ s := by unfold nat_prime_power_parts at hs rcases Finset.mem_image.mp hs with ⟨p, hp, rfl⟩ rw [Nat.mem_primeFactors] at hp have hpos : 0 < q.factorization p := hp.1.factorization_pos_of_dvd hp.2.2 hp.2.1 have hp2 : 2 ≤ p := hp.1.two_le calc 2 ≤ p := hp2 _ ≤ p ^ q.factorization p := Nat.le_self_pow hpos.ne' _lemma perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_prod (s : Finset ℕ) (h : ∀ x ∈ s, 2 ≤ x) : ∑ x ∈ s, x ≤ ∏ x ∈ s, x := by classical induction s using Finset.induction_on with | empty => simp | insert a s has ih => simp only [Finset.sum_insert has, Finset.prod_insert has] have ha : 2 ≤ a := h a (Finset.mem_insert_self a s) have hs : ∀ x ∈ s, 2 ≤ x := fun x hx => h x (Finset.mem_insert_of_mem hx) have ih' := ih hs rcases s.eq_empty_or_nonempty with rfl | hne · simp · have hprod : 2 ≤ ∏ x ∈ s, x := by obtain ⟨y, hy⟩ := hne have hy2 : 2 ≤ y := hs y hy have hdiv : y ∣ ∏ x ∈ s, x := Finset.dvd_prod_of_mem (fun x => x) hy have hpos : 0 < ∏ x ∈ s, x := by apply Finset.prod_pos intro x hx have := hs x hx omega exact Nat.le_of_dvd hpos hdiv |>.trans' hy2 nlinarithlemma perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_self (c : ℕ) (hc : c ≠ 0) : ∑ s ∈ nat_prime_power_parts c, s ≤ c := by have := perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_prod (nat_prime_power_parts c) (fun _ hx => perm_order_eq_prod_and_sum_prime_power_parts_le_two_le hx) rw [← perm_order_eq_prod_and_sum_prime_power_parts_le_prod c hc] at this exact thislemma perm_order_eq_prod_and_sum_prime_power_parts_le_support {α : Type*} [DecidableEq α] [Fintype α] (σ : Equiv.Perm α) : ∑ s ∈ nat_prime_power_parts (orderOf σ), s ≤ σ.support.card := by refine Equiv.Perm.cycle_induction_on (fun σ => ∑ s ∈ nat_prime_power_parts (orderOf σ), s ≤ σ.support.card) σ ?_ ?_ ?_ · rw [orderOf_one, nat_prime_power_parts_one, Finset.sum_empty, Equiv.Perm.support_one, Finset.card_empty] · intro τ hτ have hord : orderOf τ ≠ 0 := (orderOf_pos τ).ne' have := perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_self (orderOf τ) hord rw [← hτ.orderOf] exact this · intro τ π hd hτ ihτ ihπ have hτ_pos : orderOf τ ≠ 0 := (orderOf_pos τ).ne' have hπ_pos : orderOf π ≠ 0 := (orderOf_pos π).ne' rw [hd.orderOf] have hsub := perm_order_eq_prod_and_sum_prime_power_parts_le_lcm_subset (orderOf τ) (orderOf π) hτ_pos hπ_pos have hsum := perm_order_eq_prod_and_sum_prime_power_parts_le_sum_le_sum_union_le _ _ _ hsub have hsupp : (τ * π).support.card = τ.support.card + π.support.card := by rw [hd.support_mul, Finset.card_union_of_disjoint hd.disjoint_support] rw [hsupp] omegatheorem perm_order_eq_prod_and_sum_prime_power_parts_le (k : ℕ) (hk : 1 ≤ k) (q : ℕ) (hq : ∃ σ : Equiv.Perm (Fin k), orderOf σ = q) : q = ∏ s ∈ nat_prime_power_parts q, s ∧ ∑ s ∈ nat_prime_power_parts q, s ≤ k := by rcases hq with ⟨σ, rfl⟩ have hq0 : orderOf σ ≠ 0 := (orderOf_pos σ).ne' refine ⟨perm_order_eq_prod_and_sum_prime_power_parts_le_prod (orderOf σ) hq0, ?_⟩ have hle := perm_order_eq_prod_and_sum_prime_power_parts_le_support σ have hcard : σ.support.card ≤ k := by have := σ.support.card_le_univ rwa [Fintype.card_fin] at this exact hle.trans hcard