stein_param_inj_on
The map sending (d, u, v) to d^2 * (u^4 + 4 * v^4) is injective on stein_param_set.
Statement
theorem stein_param_inj_on : Set.InjOn (fun (d, u, v) => d^2 * (u^4 + 4 * v^4)) stein_param_set
- Source
- arXiv:2611.05898, Theorem 2.2
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- stein_param_setThe set of triples (d, u, v) of positive natural numbers such that u is odd, mu_star d holds, and d * (u^2 - 2 * v^2)^2 ≤ 4 * u * v…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - mu_starA natural number d satisfies mu_star if for every prime number p with p ≠ 2, p^2 does not divide d.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Read back from the Lean
The function mapping each triple of natural numbers $(d, u, v)$ to $d^2(u^4 + 4v^4)$ is injective on stein_param_set. That is, if two triples $(d_1, u_1, v_1)$ and $(d_2, u_2, v_2)$ both belong to stein_param_set and satisfy $d_1^2(u_1^4 + 4v_1^4) = d_2^2(u_2^4 + 4v_2^4)$, then $(d_1, u_1, v_1) = (d_2, u_2, v_2)$.
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
To prove that the map (d, u, v) ↦ N = d^2*(u^4 + 4*v^4) is injective on stein_param_set, the proof shows that the parameters (d, u, v) are uniquely determined by N. First, the identity N = (2*d*u*v)^2 + (d*|u^2 - 2*v^2|)^2 together with the parameter inequality implies that ⌊√N⌋ = 2*d*u*v, which in turn determines both p = d*|u^2 - 2*v^2| and A = d*(u^2 + 2*v^2). The sum and difference A ± p yield the set {2*d*u^2, 4*d*v^2}. A parity argument shows that the signs of u^2 - 2*v^2 cannot differ between two preimages. Finally, when the signs agree, d1*u1^2 = d2*u2^2, and because u is odd while d has no odd square prime factors, this forces d1 = d2, u1 = u2, and v1 = v2.
For all natural numbers d, u, v, d^2*(u^4 + 4*v^4) = (2*d*u*v)^2 + (d * |u^2 - 2*v^2|)^2 automation
The equality is proved by casting to the integers, expanding both sides as polynomials, and using the fact that |u^2 - 2*v^2|^2 = (u^2 - 2*v^2)^2.
uses
Int.natCast_inj.mp,sq_absprivate lemma sp_n_eq (d u v : ℕ) : d^2 * (u^4 + 4*v^4) = (2*d*u*v)^2 + (d * (((u:ℤ)^2 - 2*(v:ℤ)^2).natAbs))^2 := by apply Int.natCast_inj.mp push_cast nlinarith [sq_abs ((u:ℤ)^2 - 2*(v:ℤ)^2)]
For all natural numbers d, u, v, (d*(u^2 + 2*v^2))^2 = d^2*(u^4 + 4*v^4) + (2*d*u*v)^2 automation
Both sides expand to d^2*(u^4 + 4*u^2*v^2 + 4*v^4), which is verified by polynomial ring simplification.
private lemma sp_A_sq (d u v : ℕ) : (d*(u^2+2*v^2))^2 = d^2 * (u^4 + 4*v^4) + (2*d*u*v)^2 := by ring
For natural numbers a and b, if a^2 = b^2, then a = b
Applying the integer square root function to both sides of a^2 = b^2 and simplifying using ⌊√(n^2)⌋ = n yields a = b.
uses
congrArg,Nat.sqrt_eq'private lemma sp_sq_inj {a b : ℕ} (h : a^2 = b^2) : a = b := by have h2 := congrArg Nat.sqrt h rwa [Nat.sqrt_eq', Nat.sqrt_eq'] at h2
If d > 0 and d*(u^2 - 2*v^2)^2 ≤ 4*u*v, then ⌊√(d^2*(u^4 + 4*v^4))⌋ = 2*d*u*v
Setting m = 2*d*u*v and p = d*|u^2 - 2*v^2|, the algebraic identity gives N = m^2 + p^2, so m^2 ≤ N. Multiplying the assumed inequality by d gives p^2 ≤ 2*m, from which N = m^2 + p^2 < (m + 1)^2. By definition of the integer square root, m^2 ≤ N < (m + 1)^2 implies ⌊√N⌋ = m.
uses
sp_n_eq,eq_comm,Nat.eq_sqrt,pow_two,Nat.le_add_right,sq_abs,mul_le_mul_of_nonneg_left,le_of_lt,Nat.cast_le.mpprivate lemma sp_sqrt (d u v : ℕ) (hd : 0 < d) (hineq : (d:ℤ) * ((u:ℤ)^2 - 2*(v:ℤ)^2)^2 ≤ 4*(u:ℤ)*(v:ℤ)) : Nat.sqrt (d^2 * (u^4 + 4*v^4)) = 2*d*u*v := by set p : ℕ := d * (((u:ℤ)^2 - 2*(v:ℤ)^2).natAbs) set m : ℕ := 2*d*u*v have hn : d^2 * (u^4 + 4*v^4) = m^2 + p^2 := by simpa [m, p] using sp_n_eq d u v rw [eq_comm, Nat.eq_sqrt] constructor · rw [hn]; simp only [pow_two]; exact Nat.le_add_right _ _ · have hp2 : p^2 ≤ 2*m := by have hcast : ((p:ℤ))^2 = (d:ℤ)^2 * ((u:ℤ)^2 - 2*(v:ℤ)^2)^2 := by simp only [p] push_cast nlinarith [sq_abs ((u:ℤ)^2 - 2*(v:ℤ)^2)] have hdz : (0:ℤ) < d := by exact_mod_cast hd have hmul : (d:ℤ) * ((d:ℤ) * ((u:ℤ)^2 - 2*(v:ℤ)^2)^2) ≤ (d:ℤ) * (4*(u:ℤ)*(v:ℤ)) := mul_le_mul_of_nonneg_left hineq (le_of_lt hdz) have : ((p^2:ℕ):ℤ) ≤ ((2*m:ℕ):ℤ) := by push_cast nlinarith [hcast, hmul] exact Nat.cast_le.mp this have hm1 : (m+1)*(m+1) = m^2 + 2*m + 1 := by ring rw [hn, hm1] omega
For A = d*(u^2 + 2*v^2) and p = d*|u^2 - 2*v^2|, either (A + p = 2*d*u^2 and A - p = 4*d*v^2) or (A + p = 4*d*v^2 and A - p = 2*d*u^2)
Case split on the sign of u^2 - 2*v^2 in ℤ. If u^2 - 2*v^2 ≥ 0, its absolute value is u^2 - 2*v^2, so adding it to u^2 + 2*v^2 gives 2*u^2 and subtracting it gives 4*v^2. If u^2 - 2*v^2 < 0, its absolute value is 2*v^2 - u^2, giving the reversed values 4*v^2 and 2*u^2 upon addition and subtraction. Multiplying by d distributes over both relations.
uses
le_or_gt,Int.natAbs_of_nonneg,Int.natCast_inj.mp,sq_nonneg,Nat.cast_sub,Nat.mul_add,Nat.mul_sub_left_distrib,Int.natAbs_neg,neg_subprivate lemma sp_split (d u v : ℕ) : (d*(u^2+2*v^2) + d*(((u:ℤ)^2 - 2*(v:ℤ)^2).natAbs) = 2*(d*u^2) ∧ d*(u^2+2*v^2) - d*(((u:ℤ)^2 - 2*(v:ℤ)^2).natAbs) = 4*(d*v^2)) ∨ (d*(u^2+2*v^2) + d*(((u:ℤ)^2 - 2*(v:ℤ)^2).natAbs) = 4*(d*v^2) ∧ d*(u^2+2*v^2) - d*(((u:ℤ)^2 - 2*(v:ℤ)^2).natAbs) = 2*(d*u^2)) := by set S : ℤ := (u:ℤ)^2 - 2*(v:ℤ)^2 with hS set q : ℕ := S.natAbs with hq rcases le_or_gt (0:ℤ) S with h | h case inl => left have hqz : (q:ℤ) = (u:ℤ)^2 - 2*(v:ℤ)^2 := by rw [hq, hS]; exact Int.natAbs_of_nonneg h have h1 : (u^2+2*v^2) + q = 2*u^2 := by apply Int.natCast_inj.mp push_cast rw [hqz]; ring have hle : q ≤ u^2 + 2*v^2 := by have : (q:ℤ) ≤ ((u^2+2*v^2 : ℕ):ℤ) := by push_cast; rw [hqz]; nlinarith [sq_nonneg (v:ℤ)] exact_mod_cast this have h2 : (u^2+2*v^2) - q = 4*v^2 := by apply Int.natCast_inj.mp rw [Nat.cast_sub hle] push_cast rw [hqz]; ring constructor · rw [← Nat.mul_add, h1]; ring · rw [← Nat.mul_sub_left_distrib, h2]; ring case inr => right have hqz : (q:ℤ) = 2*(v:ℤ)^2 - (u:ℤ)^2 := by rw [hq, hS, ← Int.natAbs_neg, neg_sub] exact Int.natAbs_of_nonneg (by linarith) have h1 : (u^2+2*v^2) + q = 4*v^2 := by apply Int.natCast_inj.mp push_cast rw [hqz]; ring have hle : q ≤ u^2 + 2*v^2 := by have : (q:ℤ) ≤ ((u^2+2*v^2 : ℕ):ℤ) := by push_cast; rw [hqz]; nlinarith [sq_nonneg (u:ℤ)] exact_mod_cast this have h2 : (u^2+2*v^2) - q = 2*u^2 := by apply Int.natCast_inj.mp rw [Nat.cast_sub hle] push_cast rw [hqz]; ring constructor · rw [← Nat.mul_add, h1]; ring · rw [← Nat.mul_sub_left_distrib, h2]; ring
If d1 * a^2 = d2 * b^2 with a, b odd and neither d1 nor d2 divisible by the square of any odd prime, then d1 = d2
Divide a and b by g = gcd(a, b) to obtain coprime odd quotients a' and b' satisfying d1 * a'^2 = d2 * b'^2. By coprimality of the squares, b'^2 ∣ d1 and a'^2 ∣ d2. If b' > 1, any prime factor p of b' must be odd (since b' is odd), so p^2 ∣ d1, contradicting that d1 has no odd square prime factors. Thus b' = 1, and symmetrically a' = 1, which reduces the relation to d1 = d2.
uses
Nat.gcd_dvd_left,Nat.gcd_dvd_right,Nat.pos_of_dvd_of_pos,mul_comm,Nat.div_mul_cancel,Nat.coprime_div_gcd_div_gcd,Nat.div_dvd_of_dvd,pow_pos,dvd_mul_left,Nat.exists_prime_and_dvd,Nat.not_even_iff_odd,dvd_trans,pow_dvd_pow_of_dvdprivate lemma sp_mu_star_eq {d1 d2 a b : ℕ} (hd1 : mu_star d1) (hd2 : mu_star d2) (ha : Odd a) (hb : Odd b) (h : d1 * a^2 = d2 * b^2) : d1 = d2 := by have ha0 : 0 < a := ha.pos set g := Nat.gcd a b with hg have hga : g ∣ a := Nat.gcd_dvd_left a b have hgb : g ∣ b := Nat.gcd_dvd_right a b have hg0 : 0 < g := Nat.pos_of_dvd_of_pos hga ha0 set a' := a / g set b' := b / g have haeq : a = g * a' := by rw [mul_comm, Nat.div_mul_cancel hga] have hbeq : b = g * b' := by rw [mul_comm, Nat.div_mul_cancel hgb] have hcop : a'.Coprime b' := Nat.coprime_div_gcd_div_gcd hg0 have ha' : Odd a' := ha.of_dvd_nat (Nat.div_dvd_of_dvd hga) have hb' : Odd b' := hb.of_dvd_nat (Nat.div_dvd_of_dvd hgb) have h2 : d1 * a'^2 = d2 * b'^2 := by have hh : d1 * (g*a')^2 = d2*(g*b')^2 := by rw [← haeq, ← hbeq]; exact h have hg2 : (0:ℕ) < g^2 := pow_pos hg0 2 nlinarith [hh, hg2] have hb'2dvd : b'^2 ∣ d1 := by have hcop' : (b'^2).Coprime (a'^2) := hcop.symm.pow 2 2 apply hcop'.dvd_of_dvd_mul_left rw [mul_comm (a'^2) d1, h2] exact dvd_mul_left (b'^2) d2 have ha'2dvd : a'^2 ∣ d2 := by have hcop' : (a'^2).Coprime (b'^2) := hcop.pow 2 2 apply hcop'.dvd_of_dvd_mul_left rw [mul_comm (b'^2) d2, ← h2] exact dvd_mul_left (a'^2) d1 have hb'1 : b' = 1 := by by_contra hne obtain ⟨p, hp, hpdvd⟩ := Nat.exists_prime_and_dvd hne have hp2 : p ≠ 2 := by intro hp2eq rw [hp2eq] at hpdvd have hev : Even b' := by obtain ⟨k,hk⟩ := hpdvd; exact ⟨k, by rw [hk]; ring⟩ exact (Nat.not_even_iff_odd).mpr hb' hev have : p^2 ∣ d1 := dvd_trans (pow_dvd_pow_of_dvd hpdvd 2) hb'2dvd exact hd1 p hp hp2 this have ha'1 : a' = 1 := by by_contra hne obtain ⟨p, hp, hpdvd⟩ := Nat.exists_prime_and_dvd hne have hp2 : p ≠ 2 := by intro hp2eq rw [hp2eq] at hpdvd have hev : Even a' := by obtain ⟨k,hk⟩ := hpdvd; exact ⟨k, by rw [hk]; ring⟩ exact (Nat.not_even_iff_odd).mpr ha' hev have : p^2 ∣ d2 := dvd_trans (pow_dvd_pow_of_dvd hpdvd 2) ha'2dvd exact hd2 p hp hp2 this rw [hb'1, ha'1] at h2 simpa using h2
There exist no positive d1, d2 and odd u1, u2 satisfying d1*u1^2 = 2*(d2*v2^2) and 2*(d1*v1^2) = d2*u2^2
Multiplying the two equations gives d1*d2*(u1*u2)^2 = d1*d2*(2*v1*v2)^2. Cancelling the non-zero product d1*d2 gives (u1*u2)^2 = (2*v1*v2)^2. But since u1 and u2 are odd, (u1*u2)^2 is odd, whereas (2*v1*v2)^2 is even, a contradiction.
uses
mul_left_cancel₀,Int.natCast_inj.mp,Nat.not_even_iff_oddprivate lemma sp_parity (d1 d2 u1 u2 v1 v2 : ℕ) (hd1 : 0 < d1) (hd2 : 0 < d2) (hu1 : Odd u1) (hu2 : Odd u2) (e1 : d1*u1^2 = 2*(d2*v2^2)) (e2 : 2*(d1*v1^2) = d2*u2^2) : False := by have h1 : (d1:ℤ)*(u1:ℤ)^2 = 2*(d2:ℤ)*(v2:ℤ)^2 := by have hh : ((d1*u1^2 : ℕ):ℤ) = ((2*(d2*v2^2) : ℕ):ℤ) := by rw [e1] push_cast at hh ⊢ linarith have h2 : 2*(d1:ℤ)*(v1:ℤ)^2 = (d2:ℤ)*(u2:ℤ)^2 := by have hh : ((2*(d1*v1^2) : ℕ):ℤ) = ((d2*u2^2 : ℕ):ℤ) := by rw [e2] push_cast at hh ⊢ linarith have hmul : ((d1:ℤ)*(u1:ℤ)^2) * ((d2:ℤ)*(u2:ℤ)^2) = (2*(d2:ℤ)*(v2:ℤ)^2) * (2*(d1:ℤ)*(v1:ℤ)^2) := by rw [h1, h2] have key : ((u1:ℤ)*u2)^2 = (2*((v1:ℤ))*v2)^2 := by have hcancel : ((d1:ℤ))*((d2:ℤ))*(((u1:ℤ))*u2)^2 = ((d1:ℤ))*((d2:ℤ))*(2*((v1:ℤ))*v2)^2 := by linear_combination hmul exact mul_left_cancel₀ (by positivity) hcancel have keyN : (u1*u2)^2 = (2*(v1*v2))^2 := by apply Int.natCast_inj.mp push_cast linarith [key] have hodd : Odd ((u1*u2)^2) := (hu1.mul hu2).pow have heven : Even ((2*(v1*v2))^2) := ⟨2*(v1*v2)^2, by ring⟩ rw [← keyN] at heven exact (Nat.not_even_iff_odd).mpr hodd heven
If two parameter triples produce the same value N, then their invariants m = 2*d*u*v, p = d*|u^2 - 2*v^2|, and A = d*(u^2 + 2*v^2) coincide, and hence their sums A + p and differences A - p agree
From the parameter conditions, ⌊√N⌋ recovers m = 2*d*u*v via sp_sqrt, so m1 = m2. Since N = m^2 + p^2, we obtain p1^2 = N - m1^2 = N - m2^2 = p2^2, so p1 = p2 by injectivity of squaring. Similarly, A^2 = N + m^2 gives A1 = A2. Consequently, the sums A1 + p1 = A2 + p2 and differences A1 - p1 = A2 - p2 match.
uses
stein_param_set,Set.mem_setOf_eq,sp_sqrt,sp_n_eq,sp_sq_inj,sp_A_sq/-- The parameterization map is injective on stein_param_set. -/ theorem stein_param_inj_on : Set.InjOn (fun (d, u, v) => d^2 * (u^4 + 4 * v^4)) stein_param_set := by rintro ⟨d1,u1,v1⟩ h1 ⟨d2,u2,v2⟩ h2 heq simp only [stein_param_set, Set.mem_setOf_eq] at h1 h2 obtain ⟨hd1, hu1, hv1, ho1, hmu1, hin1⟩ := h1 obtain ⟨hd2, hu2, hv2, ho2, hmu2, hin2⟩ := h2 simp only at heq have hm1 := sp_sqrt d1 u1 v1 hd1 hin1 have hm2 := sp_sqrt d2 u2 v2 hd2 hin2 have hmeq : 2*d1*u1*v1 = 2*d2*u2*v2 := by rw [← hm1, ← hm2, heq] have hpeq : (d1 * (((u1:ℤ)^2 - 2*(v1:ℤ)^2).natAbs))^2 = (d2 * (((u2:ℤ)^2 - 2*(v2:ℤ)^2).natAbs))^2 := by have a1 := sp_n_eq d1 u1 v1 have a2 := sp_n_eq d2 u2 v2 rw [a1] at heq rw [a2] at heq rw [hmeq] at heq linarith have hpq : d1 * (((u1:ℤ)^2 - 2*(v1:ℤ)^2).natAbs) = d2 * (((u2:ℤ)^2 - 2*(v2:ℤ)^2).natAbs) := sp_sq_inj hpeq have hqeq : d1*(u1^2+2*v1^2) = d2*(u2^2+2*v2^2) := by apply sp_sq_inj rw [sp_A_sq d1 u1 v1, sp_A_sq d2 u2 v2, heq, hmeq] have hsum : d1*(u1^2+2*v1^2) + d1*(((u1:ℤ)^2-2*(v1:ℤ)^2).natAbs) = d2*(u2^2+2*v2^2) + d2*(((u2:ℤ)^2-2*(v2:ℤ)^2).natAbs) := by rw [hqeq, hpq] have hdiff : d1*(u1^2+2*v1^2) - d1*(((u1:ℤ)^2-2*(v1:ℤ)^2).natAbs) = d2*(u2^2+2*v2^2) - d2*(((u2:ℤ)^2-2*(v2:ℤ)^2).natAbs) := by rw [hqeq, hpq]
If d1 * u1^2 = d2 * u2^2, then (d1, u1, v1) = (d2, u2, v2)
Since u1, u2 are odd and d1, d2 satisfy mu_star, sp_mu_star_eq gives d1 = d2. Cancelling d1 > 0 yields u1^2 = u2^2, so u1 = u2 by sp_sq_inj. Finally, substituting d1 = d2 and u1 = u2 into 2*d1*u1*v1 = 2*d2*u2*v2 and cancelling 2*d1*u1 > 0 forces v1 = v2.
uses
sp_mu_star_eq,Nat.mul_left_cancel,sp_sq_injhave key : d1*u1^2 = d2*u2^2 → (d1,u1,v1) = (d2,u2,v2) := by intro e1 have hd : d1 = d2 := sp_mu_star_eq hmu1 hmu2 ho1 ho2 e1 have hu : u1^2 = u2^2 := by rw [← hd] at e1; exact Nat.mul_left_cancel hd1 e1 have hu' : u1 = u2 := sp_sq_inj hu have hv : v1 = v2 := by rw [hd, hu'] at hmeq exact Nat.mul_left_cancel (by positivity) hmeq rw [hd, hu', hv]
The map (d, u, v) ↦ d^2*(u^4 + 4*v^4) is injective on stein_param_set
Applying sp_split to both triples yields four cases. When the signs of u^2 - 2*v^2 match for both triples, the equations equate 2*d1*u1^2 with 2*d2*u2^2, so d1*u1^2 = d2*u2^2, which implies equality of the triples by the previous step. When the signs differ, the equations equate d1*u1^2 with 2*d2*v2^2 and d2*u2^2 with 2*d1*v1^2, which is impossible by sp_parity.
uses
sp_split,sp_parity,not_falsercases sp_split d1 u1 v1 with ⟨h1a, h1b⟩ | ⟨h1a, h1b⟩ <;> rcases sp_split d2 u2 v2 with ⟨h2a, h2b⟩ | ⟨h2a, h2b⟩ · exact key (by omega) · have e1 : d1*u1^2 = 2*(d2*v2^2) := by omega have e2 : 2*(d1*v1^2) = d2*u2^2 := by omega exact absurd (sp_parity d1 d2 u1 u2 v1 v2 hd1 hd2 ho1 ho2 e1 e2) (not_false) · have e1 : d2*u2^2 = 2*(d1*v1^2) := by omega have e2 : 2*(d2*v2^2) = d1*u1^2 := by omega exact absurd (sp_parity d2 d1 u2 u1 v2 v1 hd2 hd1 ho2 ho1 e1 e2) (not_false) · exact key (by omega)
Int.natCast_inj.mp- If two natural numbers have equal integer casts, they are equal
sq_abs- In an ordered ring, the square of the absolute value of an element equals its square: |a|^2 = a^2
congrArg- Functions preserve equality: if x = y then f(x) = f(y)
Nat.sqrt_eq'- The integer square root of n^2 is n
sp_n_eq- For natural numbers d, u, v, d^2*(u^4 + 4*v^4) = (2*d*u*v)^2 + (d * |u^2 - 2*v^2|)^2
eq_comm- Equality is symmetric: a = b ↔ b = a
Nat.eq_sqrt- a = ⌊√n⌋ if and only if a^2 ≤ n < (a + 1)^2
pow_two- a^2 = a * a in any monoid
Nat.le_add_right- For natural numbers n and k, n ≤ n + k
mul_le_mul_of_nonneg_left- If b ≤ c and 0 ≤ a, then a * b ≤ a * c
le_of_lt- If a < b, then a ≤ b
Nat.cast_le.mp- If the integer cast of m is ≤ the integer cast of n, then m ≤ n
le_or_gt- In a linear order, either a ≤ b or b < a
Int.natAbs_of_nonneg- If an integer a ≥ 0, its natural absolute value casts back to a
sq_nonneg- In an ordered semiring, squares are non-negative: 0 ≤ a^2
Nat.cast_sub- For m ≤ n in ℕ, the integer cast of n - m is the difference of their integer casts
Nat.mul_add- Multiplication distributes over addition on the left: n * (m + k) = n * m + n * k
Nat.mul_sub_left_distrib- Multiplication distributes over natural subtraction on the left: n * (m - k) = n * m - n * k
Int.natAbs_neg- The absolute value of -a equals the absolute value of a
neg_sub- -(a - b) = b - a in a subtraction group
Nat.gcd_dvd_left- The greatest common divisor gcd(m, n) divides m
Nat.gcd_dvd_right- The greatest common divisor gcd(m, n) divides n
Nat.pos_of_dvd_of_pos- If m divides n and n > 0, then m > 0
mul_comm- Multiplication is commutative: a * b = b * a
Nat.div_mul_cancel- If n divides m, then (m / n) * n = m
Nat.coprime_div_gcd_div_gcd- Dividing two numbers by their positive gcd yields coprime numbers
Nat.div_dvd_of_dvd- If n divides m, then m / n divides m
pow_pos- If a > 0, then a^n > 0 for all n
dvd_mul_left- For any elements a and b, a divides b * a
Nat.exists_prime_and_dvd- Every natural number n ≠ 1 has a prime divisor
Nat.not_even_iff_odd- A natural number is not even if and only if it is odd
dvd_trans- Divisibility is transitive: if a ∣ b and b ∣ c then a ∣ c
pow_dvd_pow_of_dvd- If a ∣ b, then a^n ∣ b^n for any natural number n
mul_left_cancel₀- If a ≠ 0 and a * b = a * c in a domain, then b = c
stein_param_set- The set of parameter triples (d, u, v) with d, u, v > 0, u odd, d having no odd square prime factors, and d*(u^2 - 2*v^2)^2 ≤ 4*u*v
Set.mem_setOf_eq- An element x belongs to the set defined by predicate p iff p(x) holds
sp_sqrt- Under d > 0 and d*(u^2 - 2*v^2)^2 ≤ 4*u*v, the integer square root ⌊√(d^2*(u^4 + 4*v^4))⌋ equals 2*d*u*v
sp_sq_inj- If a^2 = b^2 for natural numbers a and b, then a = b
sp_A_sq- For natural numbers d, u, v, (d*(u^2 + 2*v^2))^2 = d^2*(u^4 + 4*v^4) + (2*d*u*v)^2
sp_mu_star_eq- If d1 * a^2 = d2 * b^2 with a, b odd and neither d1 nor d2 having odd square prime factors, then d1 = d2
Nat.mul_left_cancel- If n > 0 and n * m = n * k in ℕ, then m = k
sp_split- For A = d*(u^2 + 2*v^2) and p = d*|u^2 - 2*v^2|, either (A + p = 2*d*u^2 and A - p = 4*d*v^2) or (A + p = 4*d*v^2 and A - p = 2*d*u^2)
sp_parity- No positive d1, d2 and odd u1, u2 can satisfy d1*u1^2 = 2*(d2*v2^2) and 2*(d1*v1^2) = d2*u2^2
not_false- The proposition False is not true (¬False)
- In Step 5, subtracting natural numbers in Lean requires establishing q ≤ u^2 + 2*v^2 beforehand so that integer casting commutes with natural subtraction (via Nat.cast_sub).
- In Step 10, the linear arithmetic tactic omega automates solving for the combinations 2*d*u^2 and 4*d*v^2 from the sums and differences.
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.
private lemma sp_n_eq (d u v : ℕ) : d^2 * (u^4 + 4*v^4) = (2*d*u*v)^2 + (d * (((u:ℤ)^2 - 2*(v:ℤ)^2).natAbs))^2 := by apply Int.natCast_inj.mp push_cast nlinarith [sq_abs ((u:ℤ)^2 - 2*(v:ℤ)^2)]private lemma sp_A_sq (d u v : ℕ) : (d*(u^2+2*v^2))^2 = d^2 * (u^4 + 4*v^4) + (2*d*u*v)^2 := by ringprivate lemma sp_sq_inj {a b : ℕ} (h : a^2 = b^2) : a = b := by have h2 := congrArg Nat.sqrt h rwa [Nat.sqrt_eq', Nat.sqrt_eq'] at h2private lemma sp_sqrt (d u v : ℕ) (hd : 0 < d) (hineq : (d:ℤ) * ((u:ℤ)^2 - 2*(v:ℤ)^2)^2 ≤ 4*(u:ℤ)*(v:ℤ)) : Nat.sqrt (d^2 * (u^4 + 4*v^4)) = 2*d*u*v := by set p : ℕ := d * (((u:ℤ)^2 - 2*(v:ℤ)^2).natAbs) set m : ℕ := 2*d*u*v have hn : d^2 * (u^4 + 4*v^4) = m^2 + p^2 := by simpa [m, p] using sp_n_eq d u v rw [eq_comm, Nat.eq_sqrt] constructor · rw [hn]; simp only [pow_two]; exact Nat.le_add_right _ _ · have hp2 : p^2 ≤ 2*m := by have hcast : ((p:ℤ))^2 = (d:ℤ)^2 * ((u:ℤ)^2 - 2*(v:ℤ)^2)^2 := by simp only [p] push_cast nlinarith [sq_abs ((u:ℤ)^2 - 2*(v:ℤ)^2)] have hdz : (0:ℤ) < d := by exact_mod_cast hd have hmul : (d:ℤ) * ((d:ℤ) * ((u:ℤ)^2 - 2*(v:ℤ)^2)^2) ≤ (d:ℤ) * (4*(u:ℤ)*(v:ℤ)) := mul_le_mul_of_nonneg_left hineq (le_of_lt hdz) have : ((p^2:ℕ):ℤ) ≤ ((2*m:ℕ):ℤ) := by push_cast nlinarith [hcast, hmul] exact Nat.cast_le.mp this have hm1 : (m+1)*(m+1) = m^2 + 2*m + 1 := by ring rw [hn, hm1] omegaprivate lemma sp_split (d u v : ℕ) : (d*(u^2+2*v^2) + d*(((u:ℤ)^2 - 2*(v:ℤ)^2).natAbs) = 2*(d*u^2) ∧ d*(u^2+2*v^2) - d*(((u:ℤ)^2 - 2*(v:ℤ)^2).natAbs) = 4*(d*v^2)) ∨ (d*(u^2+2*v^2) + d*(((u:ℤ)^2 - 2*(v:ℤ)^2).natAbs) = 4*(d*v^2) ∧ d*(u^2+2*v^2) - d*(((u:ℤ)^2 - 2*(v:ℤ)^2).natAbs) = 2*(d*u^2)) := by set S : ℤ := (u:ℤ)^2 - 2*(v:ℤ)^2 with hS set q : ℕ := S.natAbs with hq rcases le_or_gt (0:ℤ) S with h | h case inl => left have hqz : (q:ℤ) = (u:ℤ)^2 - 2*(v:ℤ)^2 := by rw [hq, hS]; exact Int.natAbs_of_nonneg h have h1 : (u^2+2*v^2) + q = 2*u^2 := by apply Int.natCast_inj.mp push_cast rw [hqz]; ring have hle : q ≤ u^2 + 2*v^2 := by have : (q:ℤ) ≤ ((u^2+2*v^2 : ℕ):ℤ) := by push_cast; rw [hqz]; nlinarith [sq_nonneg (v:ℤ)] exact_mod_cast this have h2 : (u^2+2*v^2) - q = 4*v^2 := by apply Int.natCast_inj.mp rw [Nat.cast_sub hle] push_cast rw [hqz]; ring constructor · rw [← Nat.mul_add, h1]; ring · rw [← Nat.mul_sub_left_distrib, h2]; ring case inr => right have hqz : (q:ℤ) = 2*(v:ℤ)^2 - (u:ℤ)^2 := by rw [hq, hS, ← Int.natAbs_neg, neg_sub] exact Int.natAbs_of_nonneg (by linarith) have h1 : (u^2+2*v^2) + q = 4*v^2 := by apply Int.natCast_inj.mp push_cast rw [hqz]; ring have hle : q ≤ u^2 + 2*v^2 := by have : (q:ℤ) ≤ ((u^2+2*v^2 : ℕ):ℤ) := by push_cast; rw [hqz]; nlinarith [sq_nonneg (u:ℤ)] exact_mod_cast this have h2 : (u^2+2*v^2) - q = 2*u^2 := by apply Int.natCast_inj.mp rw [Nat.cast_sub hle] push_cast rw [hqz]; ring constructor · rw [← Nat.mul_add, h1]; ring · rw [← Nat.mul_sub_left_distrib, h2]; ringprivate lemma sp_mu_star_eq {d1 d2 a b : ℕ} (hd1 : mu_star d1) (hd2 : mu_star d2) (ha : Odd a) (hb : Odd b) (h : d1 * a^2 = d2 * b^2) : d1 = d2 := by have ha0 : 0 < a := ha.pos set g := Nat.gcd a b with hg have hga : g ∣ a := Nat.gcd_dvd_left a b have hgb : g ∣ b := Nat.gcd_dvd_right a b have hg0 : 0 < g := Nat.pos_of_dvd_of_pos hga ha0 set a' := a / g set b' := b / g have haeq : a = g * a' := by rw [mul_comm, Nat.div_mul_cancel hga] have hbeq : b = g * b' := by rw [mul_comm, Nat.div_mul_cancel hgb] have hcop : a'.Coprime b' := Nat.coprime_div_gcd_div_gcd hg0 have ha' : Odd a' := ha.of_dvd_nat (Nat.div_dvd_of_dvd hga) have hb' : Odd b' := hb.of_dvd_nat (Nat.div_dvd_of_dvd hgb) have h2 : d1 * a'^2 = d2 * b'^2 := by have hh : d1 * (g*a')^2 = d2*(g*b')^2 := by rw [← haeq, ← hbeq]; exact h have hg2 : (0:ℕ) < g^2 := pow_pos hg0 2 nlinarith [hh, hg2] have hb'2dvd : b'^2 ∣ d1 := by have hcop' : (b'^2).Coprime (a'^2) := hcop.symm.pow 2 2 apply hcop'.dvd_of_dvd_mul_left rw [mul_comm (a'^2) d1, h2] exact dvd_mul_left (b'^2) d2 have ha'2dvd : a'^2 ∣ d2 := by have hcop' : (a'^2).Coprime (b'^2) := hcop.pow 2 2 apply hcop'.dvd_of_dvd_mul_left rw [mul_comm (b'^2) d2, ← h2] exact dvd_mul_left (a'^2) d1 have hb'1 : b' = 1 := by by_contra hne obtain ⟨p, hp, hpdvd⟩ := Nat.exists_prime_and_dvd hne have hp2 : p ≠ 2 := by intro hp2eq rw [hp2eq] at hpdvd have hev : Even b' := by obtain ⟨k,hk⟩ := hpdvd; exact ⟨k, by rw [hk]; ring⟩ exact (Nat.not_even_iff_odd).mpr hb' hev have : p^2 ∣ d1 := dvd_trans (pow_dvd_pow_of_dvd hpdvd 2) hb'2dvd exact hd1 p hp hp2 this have ha'1 : a' = 1 := by by_contra hne obtain ⟨p, hp, hpdvd⟩ := Nat.exists_prime_and_dvd hne have hp2 : p ≠ 2 := by intro hp2eq rw [hp2eq] at hpdvd have hev : Even a' := by obtain ⟨k,hk⟩ := hpdvd; exact ⟨k, by rw [hk]; ring⟩ exact (Nat.not_even_iff_odd).mpr ha' hev have : p^2 ∣ d2 := dvd_trans (pow_dvd_pow_of_dvd hpdvd 2) ha'2dvd exact hd2 p hp hp2 this rw [hb'1, ha'1] at h2 simpa using h2private lemma sp_parity (d1 d2 u1 u2 v1 v2 : ℕ) (hd1 : 0 < d1) (hd2 : 0 < d2) (hu1 : Odd u1) (hu2 : Odd u2) (e1 : d1*u1^2 = 2*(d2*v2^2)) (e2 : 2*(d1*v1^2) = d2*u2^2) : False := by have h1 : (d1:ℤ)*(u1:ℤ)^2 = 2*(d2:ℤ)*(v2:ℤ)^2 := by have hh : ((d1*u1^2 : ℕ):ℤ) = ((2*(d2*v2^2) : ℕ):ℤ) := by rw [e1] push_cast at hh ⊢ linarith have h2 : 2*(d1:ℤ)*(v1:ℤ)^2 = (d2:ℤ)*(u2:ℤ)^2 := by have hh : ((2*(d1*v1^2) : ℕ):ℤ) = ((d2*u2^2 : ℕ):ℤ) := by rw [e2] push_cast at hh ⊢ linarith have hmul : ((d1:ℤ)*(u1:ℤ)^2) * ((d2:ℤ)*(u2:ℤ)^2) = (2*(d2:ℤ)*(v2:ℤ)^2) * (2*(d1:ℤ)*(v1:ℤ)^2) := by rw [h1, h2] have key : ((u1:ℤ)*u2)^2 = (2*((v1:ℤ))*v2)^2 := by have hcancel : ((d1:ℤ))*((d2:ℤ))*(((u1:ℤ))*u2)^2 = ((d1:ℤ))*((d2:ℤ))*(2*((v1:ℤ))*v2)^2 := by linear_combination hmul exact mul_left_cancel₀ (by positivity) hcancel have keyN : (u1*u2)^2 = (2*(v1*v2))^2 := by apply Int.natCast_inj.mp push_cast linarith [key] have hodd : Odd ((u1*u2)^2) := (hu1.mul hu2).pow have heven : Even ((2*(v1*v2))^2) := ⟨2*(v1*v2)^2, by ring⟩ rw [← keyN] at heven exact (Nat.not_even_iff_odd).mpr hodd heven/-- The parameterization map is injective on stein_param_set. -/theorem stein_param_inj_on : Set.InjOn (fun (d, u, v) => d^2 * (u^4 + 4 * v^4)) stein_param_set := by rintro ⟨d1,u1,v1⟩ h1 ⟨d2,u2,v2⟩ h2 heq simp only [stein_param_set, Set.mem_setOf_eq] at h1 h2 obtain ⟨hd1, hu1, hv1, ho1, hmu1, hin1⟩ := h1 obtain ⟨hd2, hu2, hv2, ho2, hmu2, hin2⟩ := h2 simp only at heq have hm1 := sp_sqrt d1 u1 v1 hd1 hin1 have hm2 := sp_sqrt d2 u2 v2 hd2 hin2 have hmeq : 2*d1*u1*v1 = 2*d2*u2*v2 := by rw [← hm1, ← hm2, heq] have hpeq : (d1 * (((u1:ℤ)^2 - 2*(v1:ℤ)^2).natAbs))^2 = (d2 * (((u2:ℤ)^2 - 2*(v2:ℤ)^2).natAbs))^2 := by have a1 := sp_n_eq d1 u1 v1 have a2 := sp_n_eq d2 u2 v2 rw [a1] at heq rw [a2] at heq rw [hmeq] at heq linarith have hpq : d1 * (((u1:ℤ)^2 - 2*(v1:ℤ)^2).natAbs) = d2 * (((u2:ℤ)^2 - 2*(v2:ℤ)^2).natAbs) := sp_sq_inj hpeq have hqeq : d1*(u1^2+2*v1^2) = d2*(u2^2+2*v2^2) := by apply sp_sq_inj rw [sp_A_sq d1 u1 v1, sp_A_sq d2 u2 v2, heq, hmeq] have hsum : d1*(u1^2+2*v1^2) + d1*(((u1:ℤ)^2-2*(v1:ℤ)^2).natAbs) = d2*(u2^2+2*v2^2) + d2*(((u2:ℤ)^2-2*(v2:ℤ)^2).natAbs) := by rw [hqeq, hpq] have hdiff : d1*(u1^2+2*v1^2) - d1*(((u1:ℤ)^2-2*(v1:ℤ)^2).natAbs) = d2*(u2^2+2*v2^2) - d2*(((u2:ℤ)^2-2*(v2:ℤ)^2).natAbs) := by rw [hqeq, hpq] have key : d1*u1^2 = d2*u2^2 → (d1,u1,v1) = (d2,u2,v2) := by intro e1 have hd : d1 = d2 := sp_mu_star_eq hmu1 hmu2 ho1 ho2 e1 have hu : u1^2 = u2^2 := by rw [← hd] at e1; exact Nat.mul_left_cancel hd1 e1 have hu' : u1 = u2 := sp_sq_inj hu have hv : v1 = v2 := by rw [hd, hu'] at hmeq exact Nat.mul_left_cancel (by positivity) hmeq rw [hd, hu', hv] rcases sp_split d1 u1 v1 with ⟨h1a, h1b⟩ | ⟨h1a, h1b⟩ <;> rcases sp_split d2 u2 v2 with ⟨h2a, h2b⟩ | ⟨h2a, h2b⟩ · exact key (by omega) · have e1 : d1*u1^2 = 2*(d2*v2^2) := by omega have e2 : 2*(d1*v1^2) = d2*u2^2 := by omega exact absurd (sp_parity d1 d2 u1 u2 v1 v2 hd1 hd2 ho1 ho2 e1 e2) (not_false) · have e1 : d2*u2^2 = 2*(d1*v1^2) := by omega have e2 : 2*(d2*v2^2) = d1*u1^2 := by omega exact absurd (sp_parity d2 d1 u2 u1 v2 v1 hd2 hd1 ho2 ho1 e1 e2) (not_false) · exact key (by omega)