Lemma 2.10 — the ideals of of odd norm
ProvedFasterPrimeEnum.lemma_2_10number-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1prime-enumeration
Let be odd. The map is a bijection from
to the set of ideals of of norm .
It gives a standard generator for each ideal of odd norm, and so turns the ideal count into a count of representations by a binary quadratic form, which is how Proposition 2.9 is proved.
Formalization Note is Mathlib's ℤ√(-1), is the principal ideal of , and the norm of an ideal is its index.
Differences from the source:
- encoding: ideals of Z[√-1] of norm n → ideals I of ℤ√(-1) with Nat.card (ℤ√(-1) ⧸ I) = n; reason: the norm of a nonzero ideal is its index; the zero ideal has infinite index
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace FasterPrimeEnum
/-- **Lemma 2.10** — D. Harvey, *Faster enumeration of primes*, arXiv:2606.22851 (held version, sha256 7fc13f17…), p.16.
"Let n ⩾ 1 be odd. The map (a, b) ↦ ⟨a + 2b√−1⟩ is a bijection from {(a, b) ∈ Z² : a² + 4b² = n, a ⩾ 1} to the set of ideals of
Z[√−1] of norm n."
**Formalization Note.** `Z[√−1]` is Mathlib's `ℤ√(-1)`, whose element `⟨x, y⟩` is `x + y√−1`;
`⟨θ⟩` is the principal ideal `Ideal.span {θ}`. The norm of an ideal is its index
`Nat.card (ℤ√(-1) ⧸ I)`. An odd natural number is at least `1`. -/
theorem lemma_2_10 (n : ℕ) (hn : n % 2 = 1) :
Set.BijOn (fun ab : ℤ × ℤ => Ideal.span {(⟨ab.1, 2 * ab.2⟩ : ℤ√(-1))})
{ab : ℤ × ℤ | ab.1 ^ 2 + 4 * ab.2 ^ 2 = (n : ℤ) ∧ 1 ≤ ab.1}
{I : Ideal (ℤ√(-1)) | Nat.card (ℤ√(-1) ⧸ I) = n} := by sorry
end FasterPrimeEnum
Source
Harvey, Faster enumeration of primes, arXiv:2606.22851 (held version, sha256 7fc13f17…), Lemma 2.10, p.16
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.