AFTD Auto-Formalizing Theoretical Domains

perm_order_eq_prod_and_sum_prime_power_parts_le

theoremverifiedformalization

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • 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.

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

    lines 3–4

    uses Finset.sum_union_inter

      have := Finset.sum_union_inter (f := fun (x:ℕ) => x) (s₁ := A) (s₂ := B)
      omega
  2. 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.

    lines 8–10

    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_nat

      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 h2
  3. 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)).

    lines 14–22

    uses Finset.mem_image.mp, Nat.mem_primeFactors, Nat.factorization_lcm

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

    lines 23–32

    uses le_total, max_eq_left, Finset.mem_union_left, Finset.mem_image.mpr, Nat.mem_primeFactors, Nat.dvd_of_factorization_pos

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

    lines 33–41

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

    lines 45–55

    uses Nat.mem_primeFactors, dvd_pow_self

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

    lines 59–61

    uses perm_order_eq_prod_and_sum_prime_power_parts_le_injOn, Finset.prod_image, Nat.prod_primeFactors_pow_factorization

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

    lines 64–70

    uses Finset.mem_image.mp, Nat.mem_primeFactors, Nat.le_self_pow

      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' _
  9. 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.

    lines 74–83

    uses Finset.induction_on, Finset.sum_insert, Finset.prod_insert, Finset.mem_insert_self, Finset.mem_insert_of_mem

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

    lines 84–94

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

    lines 98–101

    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_prod

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

    lines 106–108

    uses Equiv.Perm.cycle_induction_on, orderOf_one, nat_prime_power_parts_one, Finset.sum_empty, Equiv.Perm.support_one, Finset.card_empty

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

    lines 109–113

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

    lines 114–123

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

    lines 128–135

    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_fin

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

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

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