AFTD Auto-Formalizing Theoretical Domains

moebius_odd_squarefree_identity_odd_prime_pow

theoremverified

For any prime natural number $p$ with $p \neq 2$ and any natural number $a$, the sum of the Möbius function $\mu(k)$ over all divisors $k$ of $p^a$ such that $k^2$ divides $p^a$ and $k$ is odd equals $\mu^*(p^a)$.

Statement

open Finset in
theorem moebius_odd_squarefree_identity_odd_prime_pow (p a : ℕ) (hp : p.Prime) (hp2 : p ≠ 2) :
    (∑ k ∈ (Nat.divisors (p ^ a)).filter (fun k => k ^ 2 ∣ p ^ a ∧ Odd k), ArithmeticFunction.moebius k) =
      odd_squarefree_indicator (p ^ a)
Source
arXiv:2611.05898, An Asymptotic for E. P. Stein Numbers, Proposition 4.2
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • odd_squarefree_indicatorThe integer-valued odd square-free indicator $\mu^*(d) \in \mathbb{Z}$, for a natural number $d$, is defined to be $1$ if for every prime…
  • 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.

Read back from the Lean

For all natural numbers $p$ and $a$, if $p$ is prime and $p \ne 2$, then the sum of the Möbius function $\mu(k)$ over all divisors $k$ of $p^a$ satisfying $k^2 \mid p^a$ and $k$ is odd is equal to $\text{odd\_squarefree\_indicator}(p^a)$.

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

For an odd prime power $p^a$, every divisor is of the form $p^i$. The condition that $k$ is square-free forces $k$ to be either $1$ or $p$, because any higher power $p^i$ ($i \ge 2$) satisfies $\mu(p^i) = 0$, so the sum reduces to $S \subseteq \{1, p\}$. The divisor $1$ is always in $S$ with $\mu(1) = 1$, while $p$ is in $S$ if and only if $p^2 \mid p^a$ (that is, $a \ge 2$), contributing $\mu(p) = -1$. Therefore, the sum evaluates to $1 - 1 = 0$ when $a \ge 2$ and to $1$ when $a < 2$, which matches the odd square-free indicator $\mu^*(p^a)$.

  1. Define the divisor set $T$ and its subset $S$.

    We let $T$ be the index set of the sum, namely the set of odd divisors $k$ of $p^a$ such that $k^2 \mid p^a$, and define $S \subseteq T$ as the subset of elements equal to $1$ or $p$.

    lines 6–8

      classical
      set T : Finset ℕ := (Nat.divisors (p ^ a)).filter (fun k => k ^ 2 ∣ p ^ a ∧ Odd k) with hTdef
      set S : Finset ℕ := T.filter (fun k => k = 1 ∨ k = p) with hSdef
  2. The odd square-free indicator $\mu^*(p^a)$ equals $0$ if $a \ge 2$, and $1$ if $a < 2$.

    By definition, $\mu^*(p^a) = 1$ if no square of an odd prime divides $p^a$, and $0$ otherwise. Any prime dividing $p^a$ must divide $p$, so $p$ is the only candidate prime. Its square $p^2$ divides $p^a$ if and only if $a \ge 2$. Therefore, no odd prime square divides $p^a$ precisely when $a < 2$, so the indicator evaluates to $0$ for $a \ge 2$ and $1$ for $a < 2$.

    lines 10–30

    uses pow_dvd_pow, dvd_trans, dvd_pow_self, Nat.prime_dvd_prime_iff_eq, Nat.le_of_dvd, pow_pos, Nat.pow_le_pow_right, if_congr, if_pos, if_neg

      have hind : odd_squarefree_indicator (p ^ a) = if 2 ≤ a then 0 else 1 := by
        have hcond : (∀ q : ℕ, q.Prime → q ≠ 2 → ¬ q ^ 2 ∣ p ^ a) ↔ a < 2 := by
          constructor
          · intro h
            by_contra hge
            push Not at hge
            exact h p hp hp2 (pow_dvd_pow p hge)
          · intro ha q hq hq2 hqdvd
            have hq_dvd : q ∣ p ^ a := dvd_trans (dvd_pow_self q (by norm_num)) hqdvd
            have hqp : q ∣ p := hq.dvd_of_dvd_pow hq_dvd
            have hqeqp : q = p := (Nat.prime_dvd_prime_iff_eq hq hp).1 hqp
            rw [hqeqp] at hqdvd
            have h2 : p ^ 2 ≤ p ^ a := Nat.le_of_dvd (pow_pos hp.pos a) hqdvd
            have ha1 : a ≤ 1 := by omega
            have hle : p ^ a ≤ p := by simpa using Nat.pow_le_pow_right hp.pos ha1
            nlinarith [hp.two_le]
        unfold odd_squarefree_indicator
        rw [if_congr hcond rfl rfl]
        by_cases h : a < 2
        · rw [if_pos h, if_neg (by omega)]
        · rw [if_neg h, if_pos (by omega)]
  3. The sum of $\mu(k)$ over $T$ equals the sum of $\mu(k)$ over $S$.

    Every divisor $k \in T$ of $p^a$ is of the form $p^i$ with $i \le a$. If $k \in T \setminus S$, then $k \neq 1$ and $k \neq p$, which forces $i \ge 2$. Thus $p^2 \mid k$, so $k$ is not square-free. By the vanishing property of the Möbius function, $\mu(k) = 0$ for all such elements. Removing them from the sum over $T$ leaves only the sum over $S$.

    lines 32–56

    uses Finset.sum_subset, Finset.mem_filter, Or.inl, Or.inr, Nat.mem_divisors, Nat.dvd_prime_pow, pow_zero, pow_one, pow_dvd_pow, Nat.squarefree_iff_prime_squarefree, pow_two, ArithmeticFunction.moebius_eq_zero_of_not_squarefree

      have hST : ∑ k ∈ S, ArithmeticFunction.moebius k = ∑ k ∈ T, ArithmeticFunction.moebius k := by
        refine Finset.sum_subset ?_ ?_
        · intro x hx
          rw [hSdef, Finset.mem_filter] at hx
          exact hx.1
        · intro x hxT hxS
          have hxS' : ¬ (x = 1 ∨ x = p) := by
            intro h
            apply hxS
            rw [hSdef, Finset.mem_filter]
            exact ⟨hxT, h⟩
          have hx1 : x ≠ 1 := fun h => hxS' (Or.inl h)
          have hxp : x ≠ p := fun h => hxS' (Or.inr h)
          rw [hTdef, Finset.mem_filter, Nat.mem_divisors] at hxT
          obtain ⟨⟨hxdvd, -⟩, -⟩ := hxT
          obtain ⟨i, hi, hxi⟩ := (Nat.dvd_prime_pow hp).1 hxdvd
          have hi0 : i ≠ 0 := by rintro rfl; rw [pow_zero] at hxi; exact hx1 hxi
          have hi1 : i ≠ 1 := by rintro rfl; rw [pow_one] at hxi; exact hxp hxi
          have hi2 : 2 ≤ i := by omega
          have hpdvdx : p ^ 2 ∣ x := by rw [hxi]; exact pow_dvd_pow p hi2
          have hnsq : ¬ Squarefree x := by
            rw [Nat.squarefree_iff_prime_squarefree]
            intro hsq
            exact hsq p hp (by simpa [pow_two] using hpdvdx)
          exact ArithmeticFunction.moebius_eq_zero_of_not_squarefree hnsq
  4. The set $S$ is a subset of $\{1, p\}$, contains $1$, and contains $p$ if and only if $a \ge 2$.

    By definition, any element of $S$ equals $1$ or $p$, so $S \subseteq \{1, p\}$. Since $1 \mid p^a$, $1^2 \mid p^a$, and $1$ is odd, $1$ always belongs to $S$. Since $p$ is an odd prime dividing $p^a$, it belongs to $S$ if and only if its square $p^2$ divides $p^a$, which holds precisely when $a \ge 2$.

    lines 58–80

    uses Finset.mem_filter, Nat.mem_divisors, one_dvd, pow_pos, odd_one, Or.inl, Nat.le_of_dvd, Nat.pow_le_pow_right, dvd_pow_self, pow_dvd_pow, Or.inr

      have hS_le : S ⊆ ({1, p} : Finset ℕ) := by
        intro x hx
        rw [hSdef, Finset.mem_filter] at hx
        obtain ⟨-, hx1p⟩ := hx
        rcases hx1p with rfl | rfl
        · simp
        · simp
      have h1S : (1:ℕ) ∈ S := by
        rw [hSdef, hTdef, Finset.mem_filter, Finset.mem_filter, Nat.mem_divisors]
        exact ⟨⟨⟨one_dvd _, (pow_pos hp.pos a).ne'⟩, ⟨by simp, odd_one⟩⟩, Or.inl rfl⟩
      have hpS : p ∈ S ↔ 2 ≤ a := by
        constructor
        · intro hpS'
          rw [hSdef, hTdef, Finset.mem_filter, Finset.mem_filter, Nat.mem_divisors] at hpS'
          obtain ⟨⟨⟨-, -⟩, ⟨hpdvd, -⟩⟩, -⟩ := hpS'
          have h2 : p ^ 2 ≤ p ^ a := Nat.le_of_dvd (pow_pos hp.pos a) hpdvd
          by_contra hlt
          have ha1 : a ≤ 1 := by omega
          have hle : p ^ a ≤ p := by simpa using Nat.pow_le_pow_right hp.pos ha1
          nlinarith [hp.two_le]
        · intro h2a
          rw [hSdef, hTdef, Finset.mem_filter, Finset.mem_filter, Nat.mem_divisors]
          exact ⟨⟨⟨dvd_pow_self p (by omega), (pow_pos hp.pos a).ne'⟩, ⟨pow_dvd_pow p h2a, hp.odd_of_ne_two hp2⟩⟩, Or.inr rfl⟩
  5. The sum of $\mu(k)$ over $S$ equals $0$ if $a \ge 2$, and $1$ if $a < 2$.

    We sum $\mu(x)$ over $S \subseteq \{1, p\}$. The element $1$ is always in $S$ and contributes $\mu(1) = 1$. When $a \ge 2$, $p \in S$ also contributes $\mu(p) = -1$, yielding $1 + (-1) = 0$. When $a < 2$, $p \notin S$, leaving only $\mu(1) = 1$. In both cases, the sum equals `if 2 ≤ a then 0 else 1`.

    lines 81–98

    uses Finset.sum_congr, if_pos, Finset.sum_subset, Finset.sum_pair, Ne.symm, ArithmeticFunction.moebius_apply_one, ArithmeticFunction.moebius_apply_prime, if_neg

      have hsum_S : ∑ x ∈ S, ArithmeticFunction.moebius x = (if 2 ≤ a then 0 else 1) := by
        have hcongr : ∑ x ∈ S, ArithmeticFunction.moebius x = ∑ x ∈ S, (if x ∈ S then ArithmeticFunction.moebius x else 0) := by
          apply Finset.sum_congr rfl
          intro x hx
          rw [if_pos hx]
        have hsub := Finset.sum_subset (s₁ := S) (s₂ := ({1,p} : Finset ℕ)) hS_le
          (f := fun x => if x ∈ S then ArithmeticFunction.moebius x else 0)
          (by intro x hx hxS; simp [hxS])
        have hpair : ∑ x ∈ ({1,p} : Finset ℕ), (if x ∈ S then ArithmeticFunction.moebius x else 0)
            = (if 1 ∈ S then ArithmeticFunction.moebius 1 else 0) + (if p ∈ S then ArithmeticFunction.moebius p else 0) := by
          rw [Finset.sum_pair (Ne.symm hp.ne_one)]
        rw [hcongr, hsub, hpair]
        rw [if_pos h1S, ArithmeticFunction.moebius_apply_one]
        by_cases h : 2 ≤ a
        · rw [if_pos (hpS.mpr h), ArithmeticFunction.moebius_apply_prime hp, if_pos h]
          ring
        · rw [if_neg (fun hc => h (hpS.mp hc)), if_neg h]
          ring
  6. The sum over $T$ equals the odd square-free indicator $\mu^*(p^a)$.

    The sum over $T$ reduces to the sum over $S$, which evaluates to `if 2 ≤ a then 0 else 1`, matching the value of $\mu^*(p^a)$.

    line 99

      rw [← hST, hsum_S, hind]
ArithmeticFunction.moebius_eq_zero_of_not_squarefree
If $n$ is not square-free, then $\mu(n) = 0$.
ArithmeticFunction.moebius_apply_one
The Möbius function evaluated at $1$ equals $1$.
ArithmeticFunction.moebius_apply_prime
The Möbius function evaluated at any prime $p$ equals $-1$.
Finset.mem_filter
An element $x$ is in `s.filter p` if and only if $x \in s$ and $p(x)$ holds.
Finset.sum_congr
If two finsets are equal and two functions agree on them, their sums are equal.
Finset.sum_pair
For $a \neq b$, the sum of $f$ over $\{a, b\}$ equals $f(a) + f(b)$.
Finset.sum_subset
If $s_1 \subseteq s_2$ and the summand vanishes on $s_2 \setminus s_1$, then the sum over $s_1$ equals the sum over $s_2$.
Nat.dvd_prime_pow
For a prime $p$, $i \mid p^m$ if and only if $i = p^k$ for some $k \le m$.
Nat.le_of_dvd
If $n > 0$ and $m \mid n$, then $m \le n$.
Nat.mem_divisors
A number $n$ belongs to the divisors of $m$ if and only if $n \mid m$ and $m \neq 0$.
Nat.pow_le_pow_right
For $n > 0$, exponentiation $n^i$ is monotonically increasing in $i$.
Nat.prime_dvd_prime_iff_eq
For prime numbers $p$ and $q$, $p \mid q$ if and only if $p = q$.
Nat.squarefree_iff_prime_squarefree
A natural number is square-free if and only if no square of a prime divides it.
Ne.symm
Inequality is symmetric: if $a \neq b$, then $b \neq a$.
Or.inl
From a proof of $A$, deduce $A \lor B$.
Or.inr
From a proof of $B$, deduce $A \lor B$.
dvd_pow_self
If $n \neq 0$, then $a$ divides $a^n$.
dvd_trans
Divisibility is transitive: if $a \mid b$ and $b \mid c$, then $a \mid c$.
if_congr
An if-then-else expression is invariant under replacing the condition with an equivalent proposition and the branches with equal terms.
if_neg
If condition $c$ is false, then `if c then t else e` equals $e$.
if_pos
If condition $c$ is true, then `if c then t else e` equals $t$.
odd_one
The number $1$ is odd.
one_dvd
The number $1$ divides any element.
pow_dvd_pow
If $m \le n$, then $a^m$ divides $a^n$.
pow_one
Any element raised to the first power equals itself.
pow_pos
If $a > 0$, then $a^n > 0$ for any natural number $n$.
pow_two
The square of an element $a^2$ equals $a \cdot a$.
pow_zero
Any element raised to the power $0$ equals $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

open Finset in/-- The odd square divisor Möbius sum for powers of an odd prime equals the odd square-free indicator. -/theorem moebius_odd_squarefree_identity_odd_prime_pow (p a : ℕ) (hp : p.Prime) (hp2 : p ≠ 2) :    (∑ k ∈ (Nat.divisors (p ^ a)).filter (fun k => k ^ 2 ∣ p ^ a ∧ Odd k), ArithmeticFunction.moebius k) =      odd_squarefree_indicator (p ^ a) := by  classical  set T : Finset ℕ := (Nat.divisors (p ^ a)).filter (fun k => k ^ 2 ∣ p ^ a ∧ Odd k) with hTdef  set S : Finset ℕ := T.filter (fun k => k = 1 ∨ k = p) with hSdef  -- Indicator evaluation  have hind : odd_squarefree_indicator (p ^ a) = if 2 ≤ a then 0 else 1 := by    have hcond : (∀ q : ℕ, q.Prime → q ≠ 2 → ¬ q ^ 2 ∣ p ^ a) ↔ a < 2 := by      constructor      · intro h        by_contra hge        push Not at hge        exact h p hp hp2 (pow_dvd_pow p hge)      · intro ha q hq hq2 hqdvd        have hq_dvd : q ∣ p ^ a := dvd_trans (dvd_pow_self q (by norm_num)) hqdvd        have hqp : q ∣ p := hq.dvd_of_dvd_pow hq_dvd        have hqeqp : q = p := (Nat.prime_dvd_prime_iff_eq hq hp).1 hqp        rw [hqeqp] at hqdvd        have h2 : p ^ 2 ≤ p ^ a := Nat.le_of_dvd (pow_pos hp.pos a) hqdvd        have ha1 : a ≤ 1 := by omega        have hle : p ^ a ≤ p := by simpa using Nat.pow_le_pow_right hp.pos ha1        nlinarith [hp.two_le]    unfold odd_squarefree_indicator    rw [if_congr hcond rfl rfl]    by_cases h : a < 2    · rw [if_pos h, if_neg (by omega)]    · rw [if_neg h, if_pos (by omega)]  -- reduce sum over T to sum over S  have hST : ∑ k ∈ S, ArithmeticFunction.moebius k = ∑ k ∈ T, ArithmeticFunction.moebius k := by    refine Finset.sum_subset ?_ ?_    · intro x hx      rw [hSdef, Finset.mem_filter] at hx      exact hx.1    · intro x hxT hxS      have hxS' : ¬ (x = 1 ∨ x = p) := by        intro h        apply hxS        rw [hSdef, Finset.mem_filter]        exact ⟨hxT, h⟩      have hx1 : x ≠ 1 := fun h => hxS' (Or.inl h)      have hxp : x ≠ p := fun h => hxS' (Or.inr h)      rw [hTdef, Finset.mem_filter, Nat.mem_divisors] at hxT      obtain ⟨⟨hxdvd, -⟩, -⟩ := hxT      obtain ⟨i, hi, hxi⟩ := (Nat.dvd_prime_pow hp).1 hxdvd      have hi0 : i ≠ 0 := by rintro rfl; rw [pow_zero] at hxi; exact hx1 hxi      have hi1 : i ≠ 1 := by rintro rfl; rw [pow_one] at hxi; exact hxp hxi      have hi2 : 2 ≤ i := by omega      have hpdvdx : p ^ 2 ∣ x := by rw [hxi]; exact pow_dvd_pow p hi2      have hnsq : ¬ Squarefree x := by        rw [Nat.squarefree_iff_prime_squarefree]        intro hsq        exact hsq p hp (by simpa [pow_two] using hpdvdx)      exact ArithmeticFunction.moebius_eq_zero_of_not_squarefree hnsq  -- evaluate sum over S  have hS_le : S ⊆ ({1, p} : Finset ℕ) := by    intro x hx    rw [hSdef, Finset.mem_filter] at hx    obtain ⟨-, hx1p⟩ := hx    rcases hx1p with rfl | rfl    · simp    · simp  have h1S : (1:ℕ) ∈ S := by    rw [hSdef, hTdef, Finset.mem_filter, Finset.mem_filter, Nat.mem_divisors]    exact ⟨⟨⟨one_dvd _, (pow_pos hp.pos a).ne'⟩, ⟨by simp, odd_one⟩⟩, Or.inl rfl⟩  have hpS : p ∈ S ↔ 2 ≤ a := by    constructor    · intro hpS'      rw [hSdef, hTdef, Finset.mem_filter, Finset.mem_filter, Nat.mem_divisors] at hpS'      obtain ⟨⟨⟨-, -⟩, ⟨hpdvd, -⟩⟩, -⟩ := hpS'      have h2 : p ^ 2 ≤ p ^ a := Nat.le_of_dvd (pow_pos hp.pos a) hpdvd      by_contra hlt      have ha1 : a ≤ 1 := by omega      have hle : p ^ a ≤ p := by simpa using Nat.pow_le_pow_right hp.pos ha1      nlinarith [hp.two_le]    · intro h2a      rw [hSdef, hTdef, Finset.mem_filter, Finset.mem_filter, Nat.mem_divisors]      exact ⟨⟨⟨dvd_pow_self p (by omega), (pow_pos hp.pos a).ne'⟩, ⟨pow_dvd_pow p h2a, hp.odd_of_ne_two hp2⟩⟩, Or.inr rfl⟩  have hsum_S : ∑ x ∈ S, ArithmeticFunction.moebius x = (if 2 ≤ a then 0 else 1) := by    have hcongr : ∑ x ∈ S, ArithmeticFunction.moebius x = ∑ x ∈ S, (if x ∈ S then ArithmeticFunction.moebius x else 0) := by      apply Finset.sum_congr rfl      intro x hx      rw [if_pos hx]    have hsub := Finset.sum_subset (s₁ := S) (s₂ := ({1,p} : Finset ℕ)) hS_le      (f := fun x => if x ∈ S then ArithmeticFunction.moebius x else 0)      (by intro x hx hxS; simp [hxS])    have hpair : ∑ x ∈ ({1,p} : Finset ℕ), (if x ∈ S then ArithmeticFunction.moebius x else 0)        = (if 1 ∈ S then ArithmeticFunction.moebius 1 else 0) + (if p ∈ S then ArithmeticFunction.moebius p else 0) := by      rw [Finset.sum_pair (Ne.symm hp.ne_one)]    rw [hcongr, hsub, hpair]    rw [if_pos h1S, ArithmeticFunction.moebius_apply_one]    by_cases h : 2 ≤ a    · rw [if_pos (hpS.mpr h), ArithmeticFunction.moebius_apply_prime hp, if_pos h]      ring    · rw [if_neg (fun hc => h (hpS.mp hc)), if_neg h]      ring  rw [← hST, hsum_S, hind]
See it in the graphDiscuss this resultChallenge it