moebius_odd_squarefree_identity_two_pow
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$.
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.
uses
mem_filter,Nat.mem_divisors,mem_singletonhave 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
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.
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$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`).
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⟩
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$.
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.
- The hypothesis that $k^2 \mid 2^a$ is superfluous for identifying the divisors: any odd divisor of $2^a$ must already be $1$ purely by prime factorization and parity.
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.
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