AFTD Auto-Formalizing Theoretical Domains

odd_squarefree_indicator_mul_of_coprime

theoremverified

For any positive integers $m$ and $n$ that are coprime, the odd square-free indicator satisfies $\mu^*(m n) = \mu^*(m) \mu^*(n)$.

Statement

theorem odd_squarefree_indicator_mul_of_coprime (m n : ℕ) (hm : 0 < m) (hn : 0 < n)
    (hcop : m.Coprime n) :
    odd_squarefree_indicator (m * n) = odd_squarefree_indicator m * odd_squarefree_indicator n
Source
arXiv:2611.05898, An Asymptotic for E. P. Stein Numbers, Proposition 4.2
Verified
09 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • 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…

Read back from the Lean

For all natural numbers $m$ and $n$, if $0 < m$, $0 < n$, and $m$ and $n$ are coprime, then the odd squarefree indicator of $m * n$ equals the product of the odd squarefree indicator of $m$ and the odd squarefree indicator of $n$ (in $\mathbb{Z}$).

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 first establishes an auxiliary characterization: for coprime positive integers m and n and any prime p, p² divides m n if and only if p² divides m or p² divides n. Using this lemma, it shows that m n has no odd prime square factors if and only if both m and n have no odd prime square factors. Finally, unfolding the definition of the odd square-free indicator and performing a case analysis on whether m and n satisfy this condition shows that the indicator identity holds in all cases (1 = 1 * 1 when both satisfy it, and 0 on both sides otherwise).

  1. If a prime square p² divides m n and p divides m, then p² divides m.

    Because p ∣ p² and p² ∣ m n, transitivity gives p ∣ m n. Since p is prime, p ∣ m or p ∣ n. In the case p ∣ m, p cannot also divide n, because any common factor would divide gcd(m, n) = 1, which is impossible for a prime. Hence p is coprime to n, so p² is also coprime to n. Since p² divides m n and is coprime to n, it must divide m.

    lines 4–17

    uses dvd_pow_self, dvd_trans, Nat.dvd_gcd

      constructor
      · intro h
        have hp_dvd_sq : p ∣ p ^ 2 := dvd_pow_self p (by decide)
        have hp_dvd_mn : p ∣ m * n := dvd_trans hp_dvd_sq h
        rcases hp.dvd_mul.mp hp_dvd_mn with hpm | hpn
        · left
          have hpn_not : ¬ p ∣ n := by
            intro hpn
            have : p ∣ m.gcd n := Nat.dvd_gcd hpm hpn
            rw [hcop.gcd_eq_one] at this
            exact hp.not_dvd_one this
          have hcop_pn : p.Coprime n := hp.coprime_iff_not_dvd.mpr hpn_not
          have hcop_p2n : (p ^ 2).Coprime n := hcop_pn.pow_left 2
          exact hcop_p2n.dvd_of_dvd_mul_right h
  2. If a prime square p² divides m n and p divides n, then p² divides n.

    Symmetrically, if p ∣ n, then p cannot divide m because gcd(m, n) = 1. Therefore p² is coprime to m. Since p² divides m n and is coprime to m, it must divide n. This completes the forward direction p² ∣ m n → p² ∣ m ∨ p² ∣ n.

    lines 18–26

    uses Nat.dvd_gcd

        · right
          have hpm_not : ¬ p ∣ m := by
            intro hpm
            have : p ∣ m.gcd n := Nat.dvd_gcd hpm hpn
            rw [hcop.gcd_eq_one] at this
            exact hp.not_dvd_one this
          have hcop_pm : p.Coprime m := hp.coprime_iff_not_dvd.mpr hpm_not
          have hcop_p2m : (p ^ 2).Coprime m := hcop_pm.pow_left 2
          exact hcop_p2m.dvd_of_dvd_mul_left h
  3. Conversely, if p² divides m or p² divides n, then p² divides m n.

    If p² divides m, it divides m n by multiplying on the right by n. If p² divides n, it divides m n by multiplying on the left by m. This completes the equivalence p² ∣ m n ↔ p² ∣ m ∨ p² ∣ n for prime p and coprime m, n.

    lines 27–29

    uses dvd_mul_of_dvd_left, dvd_mul_of_dvd_right

      · rintro (hm | hn)
        · exact dvd_mul_of_dvd_left hm n
        · exact dvd_mul_of_dvd_right hn m
  4. The product m n has no odd prime square divisor if and only if neither m nor n has an odd prime square divisor.

    To establish the equivalence (hiff), the forward direction assumes m n has no odd prime square factor; if p² were to divide m (or n), the helper lemma would imply p² ∣ m n via Or.inl (or Or.inr), yielding a contradiction. Conversely, if neither m nor n has an odd prime square factor and p² ∣ m n for an odd prime p, the helper lemma yields p² ∣ m or p² ∣ n, contradicting the respective assumption.

    lines 35–49

    uses odd_squarefree_indicator_mul_of_coprime_prime_sq_dvd_mul_iff, Or.inl, Or.inr

      have hiff : (∀ p : ℕ, Nat.Prime p → p ≠ 2 → ¬ (p ^ 2 ∣ m * n)) ↔
          (∀ p : ℕ, Nat.Prime p → p ≠ 2 → ¬ (p ^ 2 ∣ m)) ∧
          (∀ p : ℕ, Nat.Prime p → p ≠ 2 → ¬ (p ^ 2 ∣ n)) := by
        constructor
        · intro h
          constructor
          · intro p hp hp2 hp_sq
            exact h p hp hp2 ((odd_squarefree_indicator_mul_of_coprime_prime_sq_dvd_mul_iff hp hcop).mpr (Or.inl hp_sq))
          · intro p hp hp2 hp_sq
            exact h p hp hp2 ((odd_squarefree_indicator_mul_of_coprime_prime_sq_dvd_mul_iff hp hcop).mpr (Or.inr hp_sq))
        · rintro ⟨hm_cond, hn_cond⟩ p hp hp2 hp_sq
          rw [odd_squarefree_indicator_mul_of_coprime_prime_sq_dvd_mul_iff hp hcop] at hp_sq
          rcases hp_sq with hpm | hpn
          · exact hm_cond p hp hp2 hpm
          · exact hn_cond p hp hp2 hpn
  5. When both m and n have no odd prime square divisor, both sides of the theorem evaluate to 1.

    Unfolding the definition of odd_squarefree_indicator, the indicator is 1 if the number has no odd prime square factor and 0 otherwise. When both m and n satisfy this property, the equivalence hiff implies m n also satisfies it. Rewriting with if_pos reduces all three indicator expressions to 1, giving 1 = 1 * 1 = 1.

    lines 50–54

    uses if_pos, mul_one

      unfold odd_squarefree_indicator
      by_cases hm_cond : ∀ p : ℕ, Nat.Prime p → p ≠ 2 → ¬ (p ^ 2 ∣ m)
      · by_cases hn_cond : ∀ p : ℕ, Nat.Prime p → p ≠ 2 → ¬ (p ^ 2 ∣ n)
        · have hmn : ∀ p : ℕ, Nat.Prime p → p ≠ 2 → ¬ (p ^ 2 ∣ m * n) := hiff.mpr ⟨hm_cond, hn_cond⟩
          rw [if_pos hmn, if_pos hm_cond, if_pos hn_cond, mul_one]
  6. When m has no odd prime square divisor but n has one, both sides evaluate to 0.

    If n fails the condition, the equivalence hiff implies m n also fails it. Rewriting with if_neg evaluates the indicators of m n and n to 0, and the right-hand side simplifies to 1 * 0 = 0 via mul_zero.

    lines 55–56

    uses if_neg, mul_zero

        · have hmn : ¬ ∀ p : ℕ, Nat.Prime p → p ≠ 2 → ¬ (p ^ 2 ∣ m * n) := fun h => hn_cond (hiff.mp h).2
          rw [if_neg hmn, if_neg hn_cond, mul_zero]
  7. When m has an odd prime square divisor, both sides evaluate to 0.

    If m fails the condition, m n also fails it by hiff. Using if_neg, the indicators of m n and m evaluate to 0, and the right-hand side simplifies to 0 * ... = 0 via zero_mul, closing the final case.

    lines 57–58

    uses if_neg, zero_mul

      · have hmn : ¬ ∀ p : ℕ, Nat.Prime p → p ≠ 2 → ¬ (p ^ 2 ∣ m * n) := fun h => hm_cond (hiff.mp h).1
        rw [if_neg hmn, if_neg hm_cond, zero_mul]
dvd_pow_self
An element divides any of its positive powers (here, p ∣ p² since 2 ≠ 0).
dvd_trans
Divisibility is transitive: if a ∣ b and b ∣ c, then a ∣ c.
Nat.dvd_gcd
If k divides both m and n, then k divides their greatest common divisor gcd(m, n).
dvd_mul_of_dvd_left
If a divides b, then a divides b * c for any c.
dvd_mul_of_dvd_right
If a divides b, then a divides c * b for any c.
odd_squarefree_indicator_mul_of_coprime_prime_sq_dvd_mul_iff
For any prime p and coprime integers m and n, p² divides m * n if and only if p² divides m or p² divides n.
Or.inl
Constructs a proof of the disjunction A ∨ B from a proof of the left disjunct A.
Or.inr
Constructs a proof of the disjunction A ∨ B from a proof of the right disjunct B.
if_pos
A conditional expression if c then t else e reduces to t when the condition c is true.
if_neg
A conditional expression if c then t else e reduces to e when the condition c is false.
mul_one
Multiplying any element by 1 leaves it unchanged (a * 1 = a).
mul_zero
Multiplying any element by 0 yields 0 (a * 0 = 0).
zero_mul
Multiplying 0 by any element yields 0 (0 * a = 0).

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 odd_squarefree_indicator_mul_of_coprime_prime_sq_dvd_mul_iff    {m n p : ℕ} (hp : Nat.Prime p) (hcop : m.Coprime n) :    p ^ 2 ∣ m * n ↔ p ^ 2 ∣ m ∨ p ^ 2 ∣ n := by  constructor  · intro h    have hp_dvd_sq : p ∣ p ^ 2 := dvd_pow_self p (by decide)    have hp_dvd_mn : p ∣ m * n := dvd_trans hp_dvd_sq h    rcases hp.dvd_mul.mp hp_dvd_mn with hpm | hpn    · left      have hpn_not : ¬ p ∣ n := by        intro hpn        have : p ∣ m.gcd n := Nat.dvd_gcd hpm hpn        rw [hcop.gcd_eq_one] at this        exact hp.not_dvd_one this      have hcop_pn : p.Coprime n := hp.coprime_iff_not_dvd.mpr hpn_not      have hcop_p2n : (p ^ 2).Coprime n := hcop_pn.pow_left 2      exact hcop_p2n.dvd_of_dvd_mul_right h    · right      have hpm_not : ¬ p ∣ m := by        intro hpm        have : p ∣ m.gcd n := Nat.dvd_gcd hpm hpn        rw [hcop.gcd_eq_one] at this        exact hp.not_dvd_one this      have hcop_pm : p.Coprime m := hp.coprime_iff_not_dvd.mpr hpm_not      have hcop_p2m : (p ^ 2).Coprime m := hcop_pm.pow_left 2      exact hcop_p2m.dvd_of_dvd_mul_left h  · rintro (hm | hn)    · exact dvd_mul_of_dvd_left hm n    · exact dvd_mul_of_dvd_right hn m/-- The odd square-free indicator is multiplicative on positive coprime integers. -/theorem odd_squarefree_indicator_mul_of_coprime (m n : ℕ) (hm : 0 < m) (hn : 0 < n)    (hcop : m.Coprime n) :    odd_squarefree_indicator (m * n) = odd_squarefree_indicator m * odd_squarefree_indicator n := by  have hiff : (∀ p : ℕ, Nat.Prime p → p ≠ 2 → ¬ (p ^ 2 ∣ m * n)) ↔      (∀ p : ℕ, Nat.Prime p → p ≠ 2 → ¬ (p ^ 2 ∣ m)) ∧      (∀ p : ℕ, Nat.Prime p → p ≠ 2 → ¬ (p ^ 2 ∣ n)) := by    constructor    · intro h      constructor      · intro p hp hp2 hp_sq        exact h p hp hp2 ((odd_squarefree_indicator_mul_of_coprime_prime_sq_dvd_mul_iff hp hcop).mpr (Or.inl hp_sq))      · intro p hp hp2 hp_sq        exact h p hp hp2 ((odd_squarefree_indicator_mul_of_coprime_prime_sq_dvd_mul_iff hp hcop).mpr (Or.inr hp_sq))    · rintro ⟨hm_cond, hn_cond⟩ p hp hp2 hp_sq      rw [odd_squarefree_indicator_mul_of_coprime_prime_sq_dvd_mul_iff hp hcop] at hp_sq      rcases hp_sq with hpm | hpn      · exact hm_cond p hp hp2 hpm      · exact hn_cond p hp hp2 hpn  unfold odd_squarefree_indicator  by_cases hm_cond : ∀ p : ℕ, Nat.Prime p → p ≠ 2 → ¬ (p ^ 2 ∣ m)  · by_cases hn_cond : ∀ p : ℕ, Nat.Prime p → p ≠ 2 → ¬ (p ^ 2 ∣ n)    · have hmn : ∀ p : ℕ, Nat.Prime p → p ≠ 2 → ¬ (p ^ 2 ∣ m * n) := hiff.mpr ⟨hm_cond, hn_cond⟩      rw [if_pos hmn, if_pos hm_cond, if_pos hn_cond, mul_one]    · have hmn : ¬ ∀ p : ℕ, Nat.Prime p → p ≠ 2 → ¬ (p ^ 2 ∣ m * n) := fun h => hn_cond (hiff.mp h).2      rw [if_neg hmn, if_neg hn_cond, mul_zero]  · have hmn : ¬ ∀ p : ℕ, Nat.Prime p → p ≠ 2 → ¬ (p ^ 2 ∣ m * n) := fun h => hm_cond (hiff.mp h).1    rw [if_neg hmn, if_neg hm_cond, zero_mul]
See it in the graphDiscuss this resultChallenge it