AFTD Auto-Formalizing Theoretical Domains

int_crescent_point_bound

theoremverified

For every integer n ≥ 3, every index j in Fin n, and every coordinate index i in Fin 3, the absolute value of the i-th coordinate of int_crescent_point n j is at most 2 * (n - 1) * (4 * n^2 + 1)^(n - 1).

Statement

theorem int_crescent_point_bound (n : ℕ) (hn : 3 ≤ n) (j : Fin n) (i : Fin 3) :
    |int_crescent_point n j i| ≤ 2 * ((n : ℤ) - 1) * (4 * (n : ℤ)^2 + 1) ^ (n - 1)
Source
arXiv:2610.38368 Section 3
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • int_crescent_pointFor a natural number n and an index j in Fin n, int_crescent_point n j is the integer vector of type Fin 3 → ℤ whose coordinate 0 is…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • int_crescent_gaussianFor a natural number n and an index j in Fin n, int_crescent_gaussian n j is the Gaussian integer of type GaussianInt given by the integer…

Read back from the Lean

For every natural number $n \ge 3$, every index $j \in \{0, \dots, n-1\}$ (as j : Fin n), and every coordinate index $i \in \{0, 1, 2\}$ (as i : Fin 3), the absolute value of the $i$-th coordinate of int_crescent_point n j is at most $2(n - 1)(4n^2 + 1)^{n - 1}$ (evaluated 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 theorem bounds each coordinate of int_crescent_point n j by 2*(n-1)*(4n^2+1)^(n-1). For the first two coordinates (the real and imaginary parts of a Gaussian integer z), their squares are bounded by norm(z) = (4n^2+1)^(2(n-1)), which gives an absolute value bound of (4n^2+1)^(n-1) ≤ 2*(n-1)*(4n^2+1)^(n-1). For the third coordinate 2*j*(4n^2+1)^(n-1), the bound follows directly from j ≤ n - 1.

  1. The norm of w = (4n^2 - 1) + 4ni is B^2, where B = 4n^2 + 1

    By definition, the norm is (4n^2 - 1)^2 + (4n)^2, which expands algebraically to (4n^2 + 1)^2 = B^2.

    lines 6–11

    uses norm_def

      dsimp [int_crescent_gaussian]
      set B : ℤ := 4 * (n : ℤ)^2 + 1
      set w : GaussianInt := ⟨4 * (n : ℤ)^2 - 1, 4 * (n : ℤ)⟩
      have hw : norm w = B^2 := by
        simp [norm_def, w, B]
        ring
  2. The norm of int_crescent_gaussian n j equals ((4n^2 + 1)^(n-1))^2

    We write the scalar multiplication as multiplication by B^(n-1-j). By multiplicativity of the norm, the norm of the product is (B^(n-1-j))^2 * (norm w)^j = B^(2(n-1-j)) * B^(2j) = B^(2(n-1)).

    lines 12–28

    uses zsmul_eq_mul, norm_mul, norm_intCast, normMonoidHom.map_pow, pow_mul, pow_add

      rw [zsmul_eq_mul (w ^ (j : ℕ)) (B ^ (n - 1 - (j : ℕ)))]
      rw [norm_mul, norm_intCast]
      have hpow : norm (w ^ (j : ℕ)) = (norm w) ^ (j : ℕ) := normMonoidHom.map_pow w (j : ℕ)
      rw [hpow, hw]
      have h1 : (B ^ (j : ℕ))^2 = (B^2) ^ (j : ℕ) := by
        rw [← pow_mul, ← pow_mul]
        congr 1
        ring
      rw [← h1]
      have h3 : B ^ (n - 1 - (j : ℕ)) * B ^ (j : ℕ) = B ^ (n - 1) := by
        rw [← pow_add]
        congr 1
        have := j.isLt
        omega
      calc B ^ (n - 1 - (j : ℕ)) * B ^ (n - 1 - (j : ℕ)) * (B ^ (j : ℕ)) ^ 2
        _ = (B ^ (n - 1 - (j : ℕ)) * B ^ (j : ℕ))^2 := by ring
        _ = (B ^ (n - 1))^2 := by rw [h3]
  3. Establish the norm equation for int_crescent_gaussian and non-negativity of B^(n-1)

    We recall that norm(z) = re(z)^2 + im(z)^2, and note that B^(n-1) is non-negative.

    lines 33–38

    uses int_crescent_point_bound_norm, Zsqrtd.norm_def

      have hnorm := int_crescent_point_bound_norm n j
      have hnorm_eq : Zsqrtd.norm (int_crescent_gaussian n j) =
          (int_crescent_gaussian n j).re^2 + (int_crescent_gaussian n j).im^2 := by
        simp [Zsqrtd.norm_def]
        ring
      have hB_nonneg : 0 ≤ (4 * (n : ℤ)^2 + 1) ^ (n - 1) := by positivity
  4. B^(n-1) ≤ 2(n-1)B^(n-1) for n ≥ 3

    Since n ≥ 3, 1 ≤ 2(n-1). Multiplying both sides by the non-negative B^(n-1) yields the bound.

    lines 39–44

    uses mul_le_mul_of_nonneg_right

      have h_bound : (4 * (n : ℤ)^2 + 1) ^ (n - 1) ≤ 2 * ((n : ℤ) - 1) * (4 * (n : ℤ)^2 + 1) ^ (n - 1) := by
        calc (4 * (n : ℤ)^2 + 1) ^ (n - 1)
          _ = 1 * (4 * (n : ℤ)^2 + 1) ^ (n - 1) := by ring
          _ ≤ 2 * ((n : ℤ) - 1) * (4 * (n : ℤ)^2 + 1) ^ (n - 1) := by
            apply mul_le_mul_of_nonneg_right _ hB_nonneg
            omega
  5. The bound holds for the real part (i = 0)

    The first coordinate is the real part. Since re(z)^2 ≤ re(z)^2 + im(z)^2 = norm(z) = (B^(n-1))^2, taking square roots gives |re(z)| ≤ B^(n-1) ≤ 2(n-1)B^(n-1).

    lines 45–55

    uses sq_nonneg, sq_le_sq.mp, abs_of_nonneg

      fin_cases i
      · -- i = 0
        change |(int_crescent_gaussian n j).re| ≤ _
        have hre_sq : (int_crescent_gaussian n j).re^2 ≤ ((4 * (n : ℤ)^2 + 1) ^ (n - 1))^2 := by
          rw [← hnorm, hnorm_eq]
          have : 0 ≤ (int_crescent_gaussian n j).im^2 := sq_nonneg _
          linarith
        have h_abs : |(int_crescent_gaussian n j).re| ≤ (4 * (n : ℤ)^2 + 1) ^ (n - 1) := by
          have := sq_le_sq.mp hre_sq
          rwa [abs_of_nonneg hB_nonneg] at this
        exact h_abs.trans h_bound
  6. The bound holds for the imaginary part (i = 1)

    The second coordinate is the imaginary part. Similarly, im(z)^2 ≤ norm(z) = (B^(n-1))^2, so |im(z)| ≤ B^(n-1) ≤ 2(n-1)B^(n-1).

    lines 56–65

    uses sq_nonneg, sq_le_sq.mp, abs_of_nonneg

      · -- i = 1
        change |(int_crescent_gaussian n j).im| ≤ _
        have him_sq : (int_crescent_gaussian n j).im^2 ≤ ((4 * (n : ℤ)^2 + 1) ^ (n - 1))^2 := by
          rw [← hnorm, hnorm_eq]
          have : 0 ≤ (int_crescent_gaussian n j).re^2 := sq_nonneg _
          linarith
        have h_abs : |(int_crescent_gaussian n j).im| ≤ (4 * (n : ℤ)^2 + 1) ^ (n - 1) := by
          have := sq_le_sq.mp him_sq
          rwa [abs_of_nonneg hB_nonneg] at this
        exact h_abs.trans h_bound
  7. The bound holds for the third coordinate (i = 2)

    The third coordinate is 2 * j * B^(n-1). Since 0 ≤ j ≤ n - 1, this coordinate is non-negative and bounded by 2 * (n - 1) * B^(n-1).

    lines 66–73

    uses abs_of_nonneg

      · -- i = 2
        change |2 * (j : ℤ) * (4 * (n : ℤ)^2 + 1) ^ (n - 1)| ≤ _
        have hj : (j : ℤ) ≤ (n : ℤ) - 1 := by
          have := j.isLt
          omega
        have hterm0 : 0 ≤ 2 * (j : ℤ) * (4 * (n : ℤ)^2 + 1) ^ (n - 1) := by positivity
        rw [abs_of_nonneg hterm0]
        nlinarith
norm_mul
Gaussian integer norm of a product is the product of the norms
norm_intCast
Gaussian integer norm of an integer cast is its square
pow_mul
Power of a power rule: (a^m)^n = a^(m*n)
pow_add
Multiplication of powers with the same base: a^m * a^n = a^(m+n)
norm_def
Definition of norm for quadratic integers (for d = -1, a^2 + b^2)
normMonoidHom.map_pow
The norm homomorphism preserves powers
int_crescent_point_bound_norm
The norm of the crescent Gaussian integer is ((4*n^2 + 1)^(n-1))^2
Zsqrtd.norm_def
Definition of norm in Zsqrtd
mul_le_mul_of_nonneg_right
Multiplying an inequality by a non-negative number preserves the inequality
sq_nonneg
Squares of real/integer numbers are non-negative
abs_of_nonneg
If a is non-negative, |a| = a
sq_le_sq.mp
If x^2 ≤ y^2, then |x| ≤ |y|

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

open scoped GaussianIntopen Zsqrtdtheorem int_crescent_point_bound_norm (n : ℕ) (j : Fin n) :    norm (int_crescent_gaussian n j) = ((4 * (n : ℤ)^2 + 1) ^ (n - 1))^2 := by  dsimp [int_crescent_gaussian]  set B : ℤ := 4 * (n : ℤ)^2 + 1  set w : GaussianInt := ⟨4 * (n : ℤ)^2 - 1, 4 * (n : ℤ)⟩  have hw : norm w = B^2 := by    simp [norm_def, w, B]    ring  rw [zsmul_eq_mul (w ^ (j : ℕ)) (B ^ (n - 1 - (j : ℕ)))]  rw [norm_mul, norm_intCast]  have hpow : norm (w ^ (j : ℕ)) = (norm w) ^ (j : ℕ) := normMonoidHom.map_pow w (j : ℕ)  rw [hpow, hw]  have h1 : (B ^ (j : ℕ))^2 = (B^2) ^ (j : ℕ) := by    rw [← pow_mul, ← pow_mul]    congr 1    ring  rw [← h1]  have h3 : B ^ (n - 1 - (j : ℕ)) * B ^ (j : ℕ) = B ^ (n - 1) := by    rw [← pow_add]    congr 1    have := j.isLt    omega  calc B ^ (n - 1 - (j : ℕ)) * B ^ (n - 1 - (j : ℕ)) * (B ^ (j : ℕ)) ^ 2    _ = (B ^ (n - 1 - (j : ℕ)) * B ^ (j : ℕ))^2 := by ring    _ = (B ^ (n - 1))^2 := by rw [h3]/-- Every coordinate of int_crescent_point n j has absolute value at most 2*(n - 1)*(4*n^2 + 1)^(n - 1). -/theorem int_crescent_point_bound (n : ℕ) (hn : 3 ≤ n) (j : Fin n) (i : Fin 3) :    |int_crescent_point n j i| ≤ 2 * ((n : ℤ) - 1) * (4 * (n : ℤ)^2 + 1) ^ (n - 1) := by  have hnorm := int_crescent_point_bound_norm n j  have hnorm_eq : Zsqrtd.norm (int_crescent_gaussian n j) =      (int_crescent_gaussian n j).re^2 + (int_crescent_gaussian n j).im^2 := by    simp [Zsqrtd.norm_def]    ring  have hB_nonneg : 0 ≤ (4 * (n : ℤ)^2 + 1) ^ (n - 1) := by positivity  have h_bound : (4 * (n : ℤ)^2 + 1) ^ (n - 1) ≤ 2 * ((n : ℤ) - 1) * (4 * (n : ℤ)^2 + 1) ^ (n - 1) := by    calc (4 * (n : ℤ)^2 + 1) ^ (n - 1)      _ = 1 * (4 * (n : ℤ)^2 + 1) ^ (n - 1) := by ring      _ ≤ 2 * ((n : ℤ) - 1) * (4 * (n : ℤ)^2 + 1) ^ (n - 1) := by        apply mul_le_mul_of_nonneg_right _ hB_nonneg        omega  fin_cases i  · -- i = 0    change |(int_crescent_gaussian n j).re| ≤ _    have hre_sq : (int_crescent_gaussian n j).re^2 ≤ ((4 * (n : ℤ)^2 + 1) ^ (n - 1))^2 := by      rw [← hnorm, hnorm_eq]      have : 0 ≤ (int_crescent_gaussian n j).im^2 := sq_nonneg _      linarith    have h_abs : |(int_crescent_gaussian n j).re| ≤ (4 * (n : ℤ)^2 + 1) ^ (n - 1) := by      have := sq_le_sq.mp hre_sq      rwa [abs_of_nonneg hB_nonneg] at this    exact h_abs.trans h_bound  · -- i = 1    change |(int_crescent_gaussian n j).im| ≤ _    have him_sq : (int_crescent_gaussian n j).im^2 ≤ ((4 * (n : ℤ)^2 + 1) ^ (n - 1))^2 := by      rw [← hnorm, hnorm_eq]      have : 0 ≤ (int_crescent_gaussian n j).re^2 := sq_nonneg _      linarith    have h_abs : |(int_crescent_gaussian n j).im| ≤ (4 * (n : ℤ)^2 + 1) ^ (n - 1) := by      have := sq_le_sq.mp him_sq      rwa [abs_of_nonneg hB_nonneg] at this    exact h_abs.trans h_bound  · -- i = 2    change |2 * (j : ℤ) * (4 * (n : ℤ)^2 + 1) ^ (n - 1)| ≤ _    have hj : (j : ℤ) ≤ (n : ℤ) - 1 := by      have := j.isLt      omega    have hterm0 : 0 ≤ 2 * (j : ℤ) * (4 * (n : ℤ)^2 + 1) ^ (n - 1) := by positivity    rw [abs_of_nonneg hterm0]    nlinarith
See it in the graphDiscuss this resultChallenge it