AFTD Auto-Formalizing Theoretical Domains

stein_param_inj_on

theoremverified

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 LinearOrder is a TotalPreorder.
  • 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 than LinearOrder — 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.

  1. 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.

    lines 1–7

    uses Int.natCast_inj.mp, sq_abs

    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)]
    
  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.

    lines 8–11

    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
    
  3. 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.

    lines 12–15

    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
    
  4. 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.

    lines 16–41

    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.mp

    private 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
    
  5. 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.

    lines 42–89

    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_sub

    private 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
    
  6. 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.

    lines 90–140

    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_dvd

    private 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
    
  7. 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.

    lines 141–167

    uses mul_left_cancel₀, Int.natCast_inj.mp, Nat.not_even_iff_odd

    private 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
    
  8. 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.

    lines 168–195

    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]
  9. 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.

    lines 196–204

    uses sp_mu_star_eq, Nat.mul_left_cancel, sp_sq_inj

      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]
  10. 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.

    lines 205–214

    uses sp_split, sp_parity, not_false

      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)
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)

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

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)
See it in the graphDiscuss this resultChallenge it