AFTD Auto-Formalizing Theoretical Domains

hn_poly_three_roots

theoremverified

For every integer n ≥ 2, the cubic polynomial hn_poly n has three real roots l1 > l2 > l3 satisfying 1/2 < l1 < 2n, 0 < l2 < 1/2, and -n < l3 < 0, such that hn_poly n = (Polynomial.X - Polynomial.C l1) * (Polynomial.X - Polynomial.C l2) * (Polynomial.X - Polynomial.C l3).

Statement

theorem hn_poly_three_roots (n : ℕ) (hle : 2 ≤ n) :
    ∃ l1 l2 l3 : ℝ,
      1 / 2 < l1 ∧ l1 < 2 * (n : ℝ) ∧
      0 < l2 ∧ l2 < 1 / 2 ∧
      -(n : ℝ) < l3 ∧ l3 < 0 ∧
      l2 < l1 ∧ l3 < l2 ∧
      hn_poly n = (Polynomial.X - Polynomial.C l1) * (Polynomial.X - Polynomial.C l2) * (Polynomial.X - Polynomial.C l3)
Source
arXiv:2610.18636 Theorem 4
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • hn_polyFor every natural number n, hn_poly n is the cubic polynomial q_n(x) = x^3 - n*x^2 - (2*n^2 - n - 1)*x + (n^2 - n) over the real numbers.
Used by 1
  • hn_spectrumFor every integer n ≥ 2, there exist real numbers l1 > l2 > l3 such that 1/2 < l1 < 2n, 0 < l2 < 1/2, -n < l3 < 0, hn_poly n =…

Read back from the Lean

For every natural number $n$ such that $2 \le n$, there exist real numbers $l_1, l_2, l_3$ such that: 1. $1/2 < l_1 < 2n$, 2. $0 < l_2 < 1/2$, 3. $-n < l_3 < 0$, 4. $l_2 < l_1$, 5. $l_3 < l_2$, and 6. the polynomial $\text{hn\_poly}(n)$ factors over $\mathbb{R}$ as $(X - l_1)(X - l_2)(X - l_3)$.

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 locates three distinct real roots of the cubic polynomial hn_poly n by applying the Intermediate Value Theorem to sign changes across three disjoint intervals: (-n, 0), (0, 1/2), and (1/2, 2n). Because these intervals are disjoint, the roots are strictly ordered as l3 < l2 < l1. Subtracting the monic product (X - C l1) * (X - C l2) * (X - C l3) from hn_poly n cancels the leading cubic term, leaving a polynomial of degree at most 2 with three distinct roots. By an auxiliary root-counting lemma, a nonzero polynomial cannot have more roots than its degree, which forces the difference polynomial to be identically zero and establishes the factorization.

  1. A real polynomial of degree at most 2 having three pairwise distinct roots must be the zero polynomial.

    Suppose for contradiction that p ≠ 0. The total number of roots of p counted with multiplicity is bounded by p.natDegree ≤ 2. The set s = {l1, l2, l3} consists of three distinct roots of p, so s ⊆ p.roots.toFinset by Multiset.mem_toFinset and Polynomial.mem_roots. By Finset.card_le_card, |s| ≤ |p.roots.toFinset| ≤ 2. But s has 3 distinct elements, so |s| = 3, giving 3 ≤ 2, a contradiction.

    lines 1–23

    uses Multiset.mem_toFinset, Polynomial.mem_roots, Finset.card_le_card

    lemma hn_poly_three_roots_aux_zero (p : Polynomial ℝ) (hdeg : p.natDegree ≤ 2)
        (l1 l2 l3 : ℝ) (h12 : l1 ≠ l2) (h13 : l1 ≠ l3) (h23 : l2 ≠ l3)
        (hr1 : p.IsRoot l1) (hr2 : p.IsRoot l2) (hr3 : p.IsRoot l3) : p = 0 := by
      by_contra hp
      have hcard := p.card_roots'
      have h1 : l1 ∈ p.roots.toFinset := by
        rw [Multiset.mem_toFinset]
        exact (Polynomial.mem_roots hp).mpr hr1
      have h2 : l2 ∈ p.roots.toFinset := by
        rw [Multiset.mem_toFinset]
        exact (Polynomial.mem_roots hp).mpr hr2
      have h3 : l3 ∈ p.roots.toFinset := by
        rw [Multiset.mem_toFinset]
        exact (Polynomial.mem_roots hp).mpr hr3
      let s : Finset ℝ := {l1, l2, l3}
      have hs : s ⊆ p.roots.toFinset := by
        intro x hx
        aesop
      have hscard : s.card = 3 := by
        simp [s, h12, h13, h23]
      have hle := Finset.card_le_card hs
      have hle2 := p.roots.toFinset_card_le
      omega
  2. There exists a root l3 of hn_poly n in the open interval (-n, 0).

    Cast 2 ≤ n to the real numbers, giving -n ≤ 0. Evaluating hn_poly n at -n yields -2n < 0, while evaluating at 0 yields n² - n > 0 (using Polynomial.eval_add, Polynomial.eval_sub, Polynomial.eval_mul, Polynomial.eval_pow, Polynomial.eval_X, Polynomial.eval_C). Since polynomial evaluation is continuous on [-n, 0], 0 lies between the values at the endpoints, so the Intermediate Value Theorem (intermediate_value_Ioo) yields a root l3 ∈ (-n, 0).

    lines 24–53

    uses Polynomial.eval_add, Polynomial.eval_sub, Polynomial.eval_mul, Polynomial.eval_pow, Polynomial.eval_X, Polynomial.eval_C, intermediate_value_Ioo

    /-- The polynomial q_n has three real roots in (1/2, 2n), (0, 1/2), and (-n, 0). -/
    theorem hn_poly_three_roots (n : ℕ) (hle : 2 ≤ n) :
        ∃ l1 l2 l3 : ℝ,
          1 / 2 < l1 ∧ l1 < 2 * (n : ℝ) ∧
          0 < l2 ∧ l2 < 1 / 2 ∧
          -(n : ℝ) < l3 ∧ l3 < 0 ∧
          l2 < l1 ∧ l3 < l2 ∧
          hn_poly n = (Polynomial.X - Polynomial.C l1) * (Polynomial.X - Polynomial.C l2) * (Polynomial.X - Polynomial.C l3) := by
      have hn : (2 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hle
      -- Root l3 in (-n, 0)
      have hab3 : -(n : ℝ) ≤ 0 := by linarith
      have hcont3 : ContinuousOn (fun x : ℝ => (hn_poly n).eval x) (Set.Icc (-(n : ℝ)) 0) :=
        (hn_poly n).continuous.continuousOn
      have hneg3 : (hn_poly n).eval (-(n : ℝ)) < 0 := by
        have heval : (hn_poly n).eval (-(n : ℝ)) = -2 * (n : ℝ) := by
          unfold hn_poly
          simp only [Polynomial.eval_add, Polynomial.eval_sub, Polynomial.eval_mul, Polynomial.eval_pow,
            Polynomial.eval_X, Polynomial.eval_C]
          ring
        linarith
      have hpos3 : 0 < (hn_poly n).eval 0 := by
        have heval : (hn_poly n).eval 0 = (n : ℝ) ^ 2 - (n : ℝ) := by
          unfold hn_poly
          simp only [Polynomial.eval_add, Polynomial.eval_sub, Polynomial.eval_mul, Polynomial.eval_pow,
            Polynomial.eval_X, Polynomial.eval_C]
          ring
        nlinarith
      have h0_3 : (0 : ℝ) ∈ Set.Ioo ((hn_poly n).eval (-(n : ℝ))) ((hn_poly n).eval 0) := ⟨hneg3, hpos3⟩
      rcases intermediate_value_Ioo hab3 hcont3 h0_3 with ⟨l3, hl3_mem, hl3_eval⟩
  3. There exists a root l2 of hn_poly n in the open interval (0, 1/2).

    Evaluating hn_poly n at 1/2 yields 5/8 - 3n/4, which is strictly negative since n ≥ 2. Because (hn_poly n).eval 0 > 0, 0 lies strictly between (hn_poly n).eval (1/2) and (hn_poly n).eval 0. Since the polynomial is continuous on [0, 1/2], the Intermediate Value Theorem for a decreasing interval (intermediate_value_Ioo') gives a root l2 ∈ (0, 1/2).

    lines 54–67

    uses Polynomial.eval_add, Polynomial.eval_sub, Polynomial.eval_mul, Polynomial.eval_pow, Polynomial.eval_X, Polynomial.eval_C, intermediate_value_Ioo'

      -- Root l2 in (0, 1/2)
      have hab2 : (0 : ℝ) ≤ 1 / 2 := by linarith
      have hcont2 : ContinuousOn (fun x : ℝ => (hn_poly n).eval x) (Set.Icc 0 (1 / 2)) :=
        (hn_poly n).continuous.continuousOn
      have hneg2 : (hn_poly n).eval (1 / 2) < 0 := by
        have heval : (hn_poly n).eval (1 / 2) = 5 / 8 - 3 * (n : ℝ) / 4 := by
          unfold hn_poly
          simp only [Polynomial.eval_add, Polynomial.eval_sub, Polynomial.eval_mul, Polynomial.eval_pow,
            Polynomial.eval_X, Polynomial.eval_C]
          ring
        linarith
      have h0_2 : (0 : ℝ) ∈ Set.Ioo ((hn_poly n).eval (1 / 2)) ((hn_poly n).eval 0) := ⟨hneg2, hpos3⟩
      rcases intermediate_value_Ioo' hab2 hcont2 h0_2 with ⟨l2, hl2_mem, hl2_eval⟩
  4. There exists a root l1 of hn_poly n in the open interval (1/2, 2n).

    Evaluating hn_poly n at 2n gives 3n² + n > 0. Since (hn_poly n).eval (1/2) < 0 and 1/2 ≤ 2n, 0 lies between the endpoint values. By continuity of the polynomial on [1/2, 2n], the Intermediate Value Theorem (intermediate_value_Ioo) produces a root l1 ∈ (1/2, 2n).

    lines 68–81

    uses Polynomial.eval_add, Polynomial.eval_sub, Polynomial.eval_mul, Polynomial.eval_pow, Polynomial.eval_X, Polynomial.eval_C, intermediate_value_Ioo

      -- Root l1 in (1/2, 2n)
      have hab1 : (1 : ℝ) / 2 ≤ 2 * (n : ℝ) := by linarith
      have hcont1 : ContinuousOn (fun x : ℝ => (hn_poly n).eval x) (Set.Icc (1 / 2) (2 * (n : ℝ))) :=
        (hn_poly n).continuous.continuousOn
      have hpos1 : 0 < (hn_poly n).eval (2 * (n : ℝ)) := by
        have heval : (hn_poly n).eval (2 * (n : ℝ)) = 3 * (n : ℝ) ^ 2 + (n : ℝ) := by
          unfold hn_poly
          simp only [Polynomial.eval_add, Polynomial.eval_sub, Polynomial.eval_mul, Polynomial.eval_pow,
            Polynomial.eval_X, Polynomial.eval_C]
          ring
        nlinarith
      have h0_1 : (0 : ℝ) ∈ Set.Ioo ((hn_poly n).eval (1 / 2)) ((hn_poly n).eval (2 * (n : ℝ))) := ⟨hneg2, hpos1⟩
      rcases intermediate_value_Ioo hab1 hcont1 h0_1 with ⟨l1, hl1_mem, hl1_eval⟩
  5. The roots satisfy l3 < l2 < l1, and providing them leaves only the polynomial factorization identity.

    Since -n < l3 < 0 < l2 < 1/2 < l1 < 2n, linear arithmetic immediately establishes l3 < l2 and l2 < l1. Supplying l1, l2, l3 together with their interval bounds and ordering relations satisfies all the existential conjuncts except for the factorization.

    lines 82–88

      have h21 : l2 < l1 := by linarith [hl2_mem.2, hl1_mem.1]
      have h32 : l3 < l2 := by linarith [hl3_mem.2, hl2_mem.1]
      have h31 : l3 < l1 := by linarith
    
      refine ⟨l1, l2, l3, hl1_mem.1, hl1_mem.2, hl2_mem.1, hl2_mem.2, hl3_mem.1, hl3_mem.2, h21, h32, ?_⟩
    
  6. The difference polynomial hn_poly n - Q, where Q = (X - C l1) * (X - C l2) * (X - C l3), has degree at most 2 and roots l1, l2, l3.

    Expanding Q into expanded form via map_add and map_mul shows that its leading term is X³. Since hn_poly n is also monic of degree 3, the cubic terms cancel, leaving natDegree (hn_poly n - Q) ≤ 2. Moreover, because l1, l2, l3 are roots of both hn_poly n and Q, evaluating the difference at each root gives 0, proving that l1, l2, l3 are roots of the difference by Polynomial.IsRoot.def.

    lines 89–107

    uses map_add, map_mul, Polynomial.IsRoot.def

      set Q := (Polynomial.X - Polynomial.C l1) * (Polynomial.X - Polynomial.C l2) * (Polynomial.X - Polynomial.C l3)
      have hdeg : (hn_poly n - Q).natDegree ≤ 2 := by
        have hQ : Q = Polynomial.X ^ 3 - Polynomial.C (l1 + l2 + l3) * Polynomial.X ^ 2 +
            Polynomial.C (l1 * l2 + l1 * l3 + l2 * l3) * Polynomial.X -
            Polynomial.C (l1 * l2 * l3) := by
          simp only [Q, map_add, map_mul]
          ring
        rw [hQ]
        unfold hn_poly
        ring_nf
        compute_degree!
    
      have hr1 : (hn_poly n - Q).IsRoot l1 := by
        simp [Polynomial.IsRoot.def, hl1_eval, Q]
      have hr2 : (hn_poly n - Q).IsRoot l2 := by
        simp [Polynomial.IsRoot.def, hl2_eval, Q]
      have hr3 : (hn_poly n - Q).IsRoot l3 := by
        simp [Polynomial.IsRoot.def, hl3_eval, Q]
    
  7. hn_poly n = (Polynomial.X - Polynomial.C l1) * (Polynomial.X - Polynomial.C l2) * (Polynomial.X - Polynomial.C l3).

    The difference polynomial hn_poly n - Q has degree at most 2 and three pairwise distinct roots l1, l2, l3. By the auxiliary lemma hn_poly_three_roots_aux_zero, hn_poly n - Q = 0. Applying sub_eq_zero.mp then concludes hn_poly n = Q.

    lines 108–110

    uses hn_poly_three_roots_aux_zero, sub_eq_zero.mp

      have hdiff : hn_poly n - Q = 0 :=
        hn_poly_three_roots_aux_zero (hn_poly n - Q) hdeg l1 l2 l3 (by linarith) (by linarith) (by linarith) hr1 hr2 hr3
      exact sub_eq_zero.mp hdiff
Multiset.mem_toFinset
An element belongs to the underlying finite set of a multiset if and only if it belongs to the multiset.
Polynomial.mem_roots
For a nonzero polynomial over an integral domain, an element is in its multiset of roots if and only if it is a root of the polynomial.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most the other's cardinality.
Polynomial.eval_add
Evaluating a sum of polynomials at a point equals the sum of their individual evaluations.
Polynomial.eval_sub
Evaluating a difference of polynomials at a point equals the difference of their individual evaluations.
Polynomial.eval_mul
Evaluating a product of polynomials at a point equals the product of their individual evaluations.
Polynomial.eval_pow
Evaluating a power of a polynomial at a point equals that power of the evaluation.
Polynomial.eval_X
Evaluating the indeterminate variable X at x gives x.
Polynomial.eval_C
Evaluating a constant polynomial C(a) at any point yields the constant a.
intermediate_value_Ioo
A continuous function on [a, b] attains every value strictly between f(a) and f(b) on the open interval (a, b).
intermediate_value_Ioo'
A continuous function on [a, b] attains every value strictly between f(b) and f(a) on the open interval (a, b).
map_add
A ring homomorphism preserves addition.
map_mul
A ring homomorphism preserves multiplication.
Polynomial.IsRoot.def
An element a is a root of polynomial p if and only if p evaluates to 0 at a.
hn_poly_three_roots_aux_zero
A real polynomial of degree at most 2 with three pairwise distinct roots is the zero polynomial.
sub_eq_zero.mp
If the difference of two elements is zero, then they are equal.

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 hn_poly_three_roots_aux_zero (p : Polynomial ℝ) (hdeg : p.natDegree ≤ 2)    (l1 l2 l3 : ℝ) (h12 : l1 ≠ l2) (h13 : l1 ≠ l3) (h23 : l2 ≠ l3)    (hr1 : p.IsRoot l1) (hr2 : p.IsRoot l2) (hr3 : p.IsRoot l3) : p = 0 := by  by_contra hp  have hcard := p.card_roots'  have h1 : l1 ∈ p.roots.toFinset := by    rw [Multiset.mem_toFinset]    exact (Polynomial.mem_roots hp).mpr hr1  have h2 : l2 ∈ p.roots.toFinset := by    rw [Multiset.mem_toFinset]    exact (Polynomial.mem_roots hp).mpr hr2  have h3 : l3 ∈ p.roots.toFinset := by    rw [Multiset.mem_toFinset]    exact (Polynomial.mem_roots hp).mpr hr3  let s : Finset ℝ := {l1, l2, l3}  have hs : s ⊆ p.roots.toFinset := by    intro x hx    aesop  have hscard : s.card = 3 := by    simp [s, h12, h13, h23]  have hle := Finset.card_le_card hs  have hle2 := p.roots.toFinset_card_le  omega/-- The polynomial q_n has three real roots in (1/2, 2n), (0, 1/2), and (-n, 0). -/theorem hn_poly_three_roots (n : ℕ) (hle : 2 ≤ n) :    ∃ l1 l2 l3 : ℝ,      1 / 2 < l1 ∧ l1 < 2 * (n : ℝ) ∧      0 < l2 ∧ l2 < 1 / 2 ∧      -(n : ℝ) < l3 ∧ l3 < 0 ∧      l2 < l1 ∧ l3 < l2 ∧      hn_poly n = (Polynomial.X - Polynomial.C l1) * (Polynomial.X - Polynomial.C l2) * (Polynomial.X - Polynomial.C l3) := by  have hn : (2 : ℝ) ≤ (n : ℝ) := by exact_mod_cast hle  -- Root l3 in (-n, 0)  have hab3 : -(n : ℝ) ≤ 0 := by linarith  have hcont3 : ContinuousOn (fun x : ℝ => (hn_poly n).eval x) (Set.Icc (-(n : ℝ)) 0) :=    (hn_poly n).continuous.continuousOn  have hneg3 : (hn_poly n).eval (-(n : ℝ)) < 0 := by    have heval : (hn_poly n).eval (-(n : ℝ)) = -2 * (n : ℝ) := by      unfold hn_poly      simp only [Polynomial.eval_add, Polynomial.eval_sub, Polynomial.eval_mul, Polynomial.eval_pow,        Polynomial.eval_X, Polynomial.eval_C]      ring    linarith  have hpos3 : 0 < (hn_poly n).eval 0 := by    have heval : (hn_poly n).eval 0 = (n : ℝ) ^ 2 - (n : ℝ) := by      unfold hn_poly      simp only [Polynomial.eval_add, Polynomial.eval_sub, Polynomial.eval_mul, Polynomial.eval_pow,        Polynomial.eval_X, Polynomial.eval_C]      ring    nlinarith  have h0_3 : (0 : ℝ) ∈ Set.Ioo ((hn_poly n).eval (-(n : ℝ))) ((hn_poly n).eval 0) := ⟨hneg3, hpos3⟩  rcases intermediate_value_Ioo hab3 hcont3 h0_3 with ⟨l3, hl3_mem, hl3_eval⟩  -- Root l2 in (0, 1/2)  have hab2 : (0 : ℝ) ≤ 1 / 2 := by linarith  have hcont2 : ContinuousOn (fun x : ℝ => (hn_poly n).eval x) (Set.Icc 0 (1 / 2)) :=    (hn_poly n).continuous.continuousOn  have hneg2 : (hn_poly n).eval (1 / 2) < 0 := by    have heval : (hn_poly n).eval (1 / 2) = 5 / 8 - 3 * (n : ℝ) / 4 := by      unfold hn_poly      simp only [Polynomial.eval_add, Polynomial.eval_sub, Polynomial.eval_mul, Polynomial.eval_pow,        Polynomial.eval_X, Polynomial.eval_C]      ring    linarith  have h0_2 : (0 : ℝ) ∈ Set.Ioo ((hn_poly n).eval (1 / 2)) ((hn_poly n).eval 0) := ⟨hneg2, hpos3⟩  rcases intermediate_value_Ioo' hab2 hcont2 h0_2 with ⟨l2, hl2_mem, hl2_eval⟩  -- Root l1 in (1/2, 2n)  have hab1 : (1 : ℝ) / 2 ≤ 2 * (n : ℝ) := by linarith  have hcont1 : ContinuousOn (fun x : ℝ => (hn_poly n).eval x) (Set.Icc (1 / 2) (2 * (n : ℝ))) :=    (hn_poly n).continuous.continuousOn  have hpos1 : 0 < (hn_poly n).eval (2 * (n : ℝ)) := by    have heval : (hn_poly n).eval (2 * (n : ℝ)) = 3 * (n : ℝ) ^ 2 + (n : ℝ) := by      unfold hn_poly      simp only [Polynomial.eval_add, Polynomial.eval_sub, Polynomial.eval_mul, Polynomial.eval_pow,        Polynomial.eval_X, Polynomial.eval_C]      ring    nlinarith  have h0_1 : (0 : ℝ) ∈ Set.Ioo ((hn_poly n).eval (1 / 2)) ((hn_poly n).eval (2 * (n : ℝ))) := ⟨hneg2, hpos1⟩  rcases intermediate_value_Ioo hab1 hcont1 h0_1 with ⟨l1, hl1_mem, hl1_eval⟩  have h21 : l2 < l1 := by linarith [hl2_mem.2, hl1_mem.1]  have h32 : l3 < l2 := by linarith [hl3_mem.2, hl2_mem.1]  have h31 : l3 < l1 := by linarith  refine ⟨l1, l2, l3, hl1_mem.1, hl1_mem.2, hl2_mem.1, hl2_mem.2, hl3_mem.1, hl3_mem.2, h21, h32, ?_⟩  set Q := (Polynomial.X - Polynomial.C l1) * (Polynomial.X - Polynomial.C l2) * (Polynomial.X - Polynomial.C l3)  have hdeg : (hn_poly n - Q).natDegree ≤ 2 := by    have hQ : Q = Polynomial.X ^ 3 - Polynomial.C (l1 + l2 + l3) * Polynomial.X ^ 2 +        Polynomial.C (l1 * l2 + l1 * l3 + l2 * l3) * Polynomial.X -        Polynomial.C (l1 * l2 * l3) := by      simp only [Q, map_add, map_mul]      ring    rw [hQ]    unfold hn_poly    ring_nf    compute_degree!  have hr1 : (hn_poly n - Q).IsRoot l1 := by    simp [Polynomial.IsRoot.def, hl1_eval, Q]  have hr2 : (hn_poly n - Q).IsRoot l2 := by    simp [Polynomial.IsRoot.def, hl2_eval, Q]  have hr3 : (hn_poly n - Q).IsRoot l3 := by    simp [Polynomial.IsRoot.def, hl3_eval, Q]  have hdiff : hn_poly n - Q = 0 :=    hn_poly_three_roots_aux_zero (hn_poly n - Q) hdeg l1 l2 l3 (by linarith) (by linarith) (by linarith) hr1 hr2 hr3  exact sub_eq_zero.mp hdiff
See it in the graphDiscuss this resultChallenge it