AFTD Auto-Formalizing Theoretical Domains

nat_prime_power_parts_prime_pow

theoremverified

For a prime p and k ≥ 1, S(p^k) = {p^k}.

Statement

theorem nat_prime_power_parts_prime_pow {p k : ℕ} (hp : p.Prime) (hk : k ≠ 0) :
    nat_prime_power_parts (p ^ k) = {p ^ k}
Source
Sanity lemma for nat_prime_power_parts (arXiv:2610.11098 (An improved lower bound for separating words by permutation automata)).
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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.

The proof, explained

By definition, the prime power parts of a number are obtained by raising each of its prime factors to its full multiplicity. Since p is prime and k ≥ 1, the only prime factor of p^k is p, with multiplicity k. Thus the set of prime power parts reduces to the singleton {p^k}.

  1. By definition, the prime power parts of p^k is the image of the prime factors of p^k under the map q ↦ q ^ ((p^k).factorization q).

    Unfold the definition of `nat_prime_power_parts`.

    line 3

      unfold nat_prime_power_parts
  2. The domain of prime factors reduces to the singleton {p}.

    Because p is prime and k ≠ 0, the only prime factor of p^k is p. Applying `Nat.primeFactors_prime_pow` replaces (p ^ k).primeFactors with {p}.

    line 4

    uses Nat.primeFactors_prime_pow

      rw [Nat.primeFactors_prime_pow hk hp]
  3. The prime power parts of p^k equals {p^k}.

    The image of {p} under q ↦ q ^ ((p^k).factorization q) evaluates at p to p ^ ((p^k).factorization p). By `Nat.factorization_pow`, the exponent is k * (p.factorization p), which simplifies to k * 1 = k via `hp.factorization_self`. Simplifying the singleton image closes the goal.

    line 5

    uses Nat.factorization_pow, hp.factorization_self

      simp [Nat.factorization_pow, hp.factorization_self]
Nat.primeFactors_prime_pow
For a prime p and k ≠ 0, the set of prime factors of p^k is {p}.
Nat.factorization_pow
The prime factorization of n^k is k times the prime factorization of n.
hp.factorization_self
For a prime p, the multiplicity of p in its own prime factorization is 1.

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

theorem nat_prime_power_parts_prime_pow {p k : ℕ} (hp : p.Prime) (hk : k ≠ 0) :    nat_prime_power_parts (p ^ k) = {p ^ k} := by  unfold nat_prime_power_parts  rw [Nat.primeFactors_prime_pow hk hp]  simp [Nat.factorization_pow, hp.factorization_self]
See it in the graphDiscuss this resultChallenge it