AFTD Auto-Formalizing Theoretical Domains

moebius_odd_squarefree_identity_two_pow

theoremverified

For any natural number $a$, the sum of the Möbius function $\mu(k)$ over all divisors $k$ of $2^a$ such that $k^2$ divides $2^a$ and $k$ is odd is equal to $1$.

Statement

open Finset in
theorem moebius_odd_squarefree_identity_two_pow (a : ℕ) :
    (∑ k ∈ (Nat.divisors (2 ^ a)).filter (fun k => k ^ 2 ∣ 2 ^ a ∧ Odd k), ArithmeticFunction.moebius k) = 1
Source
arXiv:2611.05898, An Asymptotic for E. P. Stein Numbers, Proposition 4.2
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For every natural number $a$, the sum of the Möbius function $\mu(k)$ over all divisors $k$ of $2^a$ satisfying $k^2 \mid 2^a$ and $k$ is odd equals $1$.

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 proof works by showing that the index set of the sum is the singleton $\{1\}$, after which the sum collapses to $\mu(1) = 1$. To show the index set is $\{1\}$, it observes that every divisor of $2^a$ has the form $2^j$ for some $j \le a$; any such power with $j \ge 1$ is even, so the only odd divisor is $2^0 = 1$. Conversely, $1$ trivially satisfies all the conditions, and the sum over $\{1\}$ simplifies directly to $1$.

  1. To show that the index set $\{k \in \operatorname{divisors}(2^a) \mid k^2 \mid 2^a \text{ and } k \text{ is odd}\}$ equals the singleton $\{1\}$, it suffices to prove that the membership conditions are satisfied if and only if $k = 1$.

    By set extensionality (`ext k`), two sets are equal if they contain the same elements. Rewriting set membership using `mem_filter`, `Nat.mem_divisors`, and `mem_singleton` simplifies membership in the index set to $(k \mid 2^a \wedge 2^a \neq 0) \wedge k^2 \mid 2^a \wedge \operatorname{Odd}(k)$, which must be shown equivalent to $k = 1$. A split into forward and reverse implications (`constructor`) sets up the two directions.

    lines 5–8

    uses mem_filter, Nat.mem_divisors, mem_singleton

      have h_set : (Nat.divisors (2 ^ a)).filter (fun k => k ^ 2 ∣ 2 ^ a ∧ Odd k) = {1} := by
        ext k
        simp only [mem_filter, Nat.mem_divisors, mem_singleton]
        constructor
  2. Any odd divisor $k$ of $2^a$ is equal to $1$.

    Assume $k \mid 2^a$ and $k$ is odd (the condition $k^2 \mid 2^a$ is ignored). Since $2$ is prime (`Nat.prime_two`), any divisor $k$ of $2^a$ is of the form $2^j$ for some $j \le a$ (`Nat.dvd_prime_pow`). We split on $j$: if $j = 0$, then $k = 2^0 = 1$. If $j = j' + 1$, then $k = 2^{j'+1} = 2 \cdot 2^{j'}$ (`pow_succ'`), which is even (`even_two_mul`). Since $k$ is odd, it cannot be even (`Nat.not_even_iff_odd.mpr`), which is a contradiction.

    lines 9–18

    uses Nat.dvd_prime_pow, Nat.prime_two, pow_succ', even_two_mul, Nat.not_even_iff_odd.mpr

        · rintro ⟨⟨hk_dvd, _⟩, _, hk_odd⟩
          obtain ⟨j, _, rfl⟩ := (Nat.dvd_prime_pow Nat.prime_two).mp hk_dvd
          cases j with
          | zero => rfl
          | succ j =>
            exfalso
            have heven : Even (2 ^ (j + 1)) := by
              rw [pow_succ']
              exact even_two_mul (2 ^ j)
            exact Nat.not_even_iff_odd.mpr hk_odd heven
  3. $1$ satisfies all the membership conditions for the index set.

    When $k = 1$, we must verify that $1 \mid 2^a$, $2^a \neq 0$, $1^2 \mid 2^a$, and $1$ is odd. The number $1$ divides any number (`one_dvd`), powers of $2$ are nonzero since $2 \neq 0$ (`pow_ne_zero`, `two_ne_zero`), $1^2 = 1$ divides $2^a$, and $1$ is odd (`odd_one`).

    lines 19–20

    uses one_dvd, pow_ne_zero, two_ne_zero, odd_one

        · rintro rfl
          exact ⟨⟨one_dvd _, pow_ne_zero a two_ne_zero⟩, one_dvd _, odd_one⟩
  4. The sum over the index set equals $1$. automation

    Rewriting the index set with the identity established above reduces the sum to $\sum_{k \in \{1\}} \mu(k)$. Simplification evaluates this singleton sum to $\mu(1) = 1$.

    lines 21–22

      rw [h_set]
      simp
mem_filter
An element $x$ belongs to the filtered finset $\{y \in s \mid p(y)\}$ if and only if $x \in s$ and $p(x)$ holds.
Nat.mem_divisors
A natural number $n$ belongs to the divisors of $m$ if and only if $n \mid m$ and $m \neq 0$.
mem_singleton
An element $x$ belongs to the singleton set $\{a\}$ if and only if $x = a$.
Nat.dvd_prime_pow
For a prime $p$, a natural number divides $p^m$ if and only if it equals $p^k$ for some $k \le m$.
Nat.prime_two
The number $2$ is prime.
pow_succ'
In a monoid, $a^{n+1} = a \cdot a^n$.
even_two_mul
For any element $a$ in a semiring, $2 \cdot a$ is even.
Nat.not_even_iff_odd.mpr
If a natural number is odd, then it is not even.
one_dvd
The element $1$ divides any element in a monoid.
pow_ne_zero
In a monoid with zero and no nonzero zero-divisors, any power of a nonzero element is nonzero.
two_ne_zero
$2 \neq 0$.
odd_one
The number $1$ is odd.

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 2 is equal to 1. -/theorem moebius_odd_squarefree_identity_two_pow (a : ℕ) :    (∑ k ∈ (Nat.divisors (2 ^ a)).filter (fun k => k ^ 2 ∣ 2 ^ a ∧ Odd k), ArithmeticFunction.moebius k) = 1 := by  have h_set : (Nat.divisors (2 ^ a)).filter (fun k => k ^ 2 ∣ 2 ^ a ∧ Odd k) = {1} := by    ext k    simp only [mem_filter, Nat.mem_divisors, mem_singleton]    constructor    · rintro ⟨⟨hk_dvd, _⟩, _, hk_odd⟩      obtain ⟨j, _, rfl⟩ := (Nat.dvd_prime_pow Nat.prime_two).mp hk_dvd      cases j with      | zero => rfl      | succ j =>        exfalso        have heven : Even (2 ^ (j + 1)) := by          rw [pow_succ']          exact even_two_mul (2 ^ j)        exact Nat.not_even_iff_odd.mpr hk_odd heven    · rintro rfl      exact ⟨⟨one_dvd _, pow_ne_zero a two_ne_zero⟩, one_dvd _, odd_one⟩  rw [h_set]  simp
See it in the graphDiscuss this resultChallenge it