AFTD Auto-Formalizing Theoretical Domains

hyperbinary_eval_cube_root_of_unity

theoremverifiedformalization

For every non-negative integer m, evaluating the hyperbinary length polynomial H_m(z) at the primitive cube root of unity ω = (-1 + √(-3))/2 gives an element of {0, ±1, ±ω, ±ω²}.

Statement

theorem hyperbinary_eval_cube_root_of_unity (m : ℕ) :
    Polynomial.aeval eisensteinOmega (hyperbinaryLengthPoly m) ∈
      ({0, 1, -1, eisensteinOmega, -eisensteinOmega, eisensteinOmega ^ 2, -eisensteinOmega ^ 2} : Set ℂ)
Formalizes
scout/2611-01243-halving-partitions-and-hyperbinary-expansions.md:1200
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • eisensteinOmegaThe primitive cube root of unity ω = (-1 + √(-3))/2 in the complex numbers.
  • hyperbinaryLengthPolyThe hyperbinary length polynomial H_m(z) satisfies H_0(z) = 1, H_{2m+1}(z) = z H_m(z), and H_{2m}(z) = H_m(z) + z^2 H_{m-1}(z) for m ≥ 1.

Read back from the Lean

For every natural number $m$, evaluating the polynomial hyperbinaryLengthPoly m at the Eisenstein root of unity $\omega = \frac{-1 + i\sqrt{3}}{2}$ yields an element of the set $\{0, 1, -1, \omega, -\omega, \omega^2, -\omega^2\} \subset \mathbb{C}$.

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 states that evaluating the hyperbinary length polynomial H_m(z) at the primitive cube root of unity ω gives a value in S = {0, ±1, ±ω, ±ω²}. The proof strengthens the statement to an inductive invariant on consecutive pairs (H_m(ω), H_{m+1}(ω)), defining a notion of valid pair whose components lie in S. By strong induction on m, using the polynomial recurrence relations for odd and even indices, each valid pair transforms into another valid pair, completing the proof since the first coordinate of any valid pair belongs to S.

  1. The first component x of any valid pair (x, y) belongs to S

    By definition, a pair (x, y) is valid if x = 0 with y ∈ S, y = 0 with x ∈ S, y = ω x with x ∈ S, or y = -ω² x with x ∈ S. In the first case x = 0 ∈ S, and in all other three cases x ∈ S by assumption.

    lines 13–17

      rcases h with ⟨rfl, _⟩ | ⟨_, hx⟩ | ⟨hx, _⟩ | ⟨hx, _⟩
      · simp [hyperbinary_eval_cube_root_of_unity_S]
      · exact hx
      · exact hx
      · exact hx
  2. The primitive cube root of unity ω satisfies ω² + ω + 1 = 0

    Expanding ω = (-1 + I√3)/2 and squaring, we use I² = -1 and (√3)² = 3. Ring arithmetic then simplifies ω² + ω + 1 directly to 0.

    lines 21–30

    uses Complex.I_sq, Real.sq_sqrt

      have hI : Complex.I ^ 2 = -1 := Complex.I_sq
      have h3 : (Real.sqrt 3 : ℂ) ^ 2 = 3 := by
        norm_cast
        exact Real.sq_sqrt (by norm_num)
      dsimp [eisensteinOmega]
      have h_div : ((-1 + Complex.I * (Real.sqrt 3 : ℂ)) / 2) ^ 2 = (-1 + Complex.I * Real.sqrt 3) ^ 2 / 4 := by ring
      rw [h_div]
      have : (-1 + Complex.I * (Real.sqrt 3 : ℂ)) ^ 2 = 1 - 2 * Complex.I * Real.sqrt 3 + Complex.I ^ 2 * (Real.sqrt 3 : ℂ) ^ 2 := by ring
      rw [this, hI, h3]
      ring
  3. The cube of ω is 1, so ω³ = 1

    Multiplying the identity ω² + ω + 1 = 0 by ω - 1 gives ω³ - 1 = 0, so ω³ = 1.

    lines 33–34

    uses hyperbinary_eval_cube_root_of_unity_omega_sq_add_omega_add_one

      have h := hyperbinary_eval_cube_root_of_unity_omega_sq_add_omega_add_one
      linear_combination (eisensteinOmega - 1) * h
  4. The set S is closed under negation: if z ∈ S, then -z ∈ S

    The set S consists of 0, ±1, ±ω, and ±ω². Case analysis on which element z is shows that in every case, -z also belongs to S.

    lines 39–47

    uses Set.mem_insert_iff, Set.mem_singleton_iff

      simp only [hyperbinary_eval_cube_root_of_unity_S, Set.mem_insert_iff, Set.mem_singleton_iff] at hz ⊢
      rcases hz with rfl | rfl | rfl | rfl | rfl | rfl | rfl
      · left; ring
      · right; right; left; ring
      · right; left; ring
      · right; right; right; right; left; ring
      · right; right; right; left; ring
      · right; right; right; right; right; right; ring
      · right; right; right; right; right; left; ring
  5. The set S is closed under multiplication by ω: if z ∈ S, then ω z ∈ S

    Case analysis on z ∈ S: 0 is fixed, the triple {1, ω, ω²} is permuted cyclically using ω³ = 1, and {-1, -ω, -ω²} is likewise permuted cyclically. Hence ω z ∈ S in all cases.

    lines 52–65

    uses hyperbinary_eval_cube_root_of_unity_omega_cube, Set.mem_insert_iff, Set.mem_singleton_iff

      have h3 := hyperbinary_eval_cube_root_of_unity_omega_cube
      simp only [hyperbinary_eval_cube_root_of_unity_S, Set.mem_insert_iff, Set.mem_singleton_iff] at hz ⊢
      rcases hz with rfl | rfl | rfl | rfl | rfl | rfl | rfl
      · left; ring
      · right; right; right; left; ring
      · right; right; right; right; left; ring
      · right; right; right; right; right; left; ring
      · right; right; right; right; right; right; ring
      · right; left
        calc eisensteinOmega * eisensteinOmega ^ 2 = eisensteinOmega ^ 3 := by ring
        _ = 1 := h3
      · right; right; left
        calc eisensteinOmega * -eisensteinOmega ^ 2 = -eisensteinOmega ^ 3 := by ring
        _ = -1 := by rw [h3]
  6. The set S is closed under multiplication by ω²: if z ∈ S, then ω² z ∈ S

    Writing ω² z as ω(ω z), the result follows by applying closure under multiplication by ω twice.

    lines 70–72

    uses hyperbinary_eval_cube_root_of_unity_mem_S_omega_mul

      have : eisensteinOmega ^ 2 * z = eisensteinOmega * (eisensteinOmega * z) := by ring
      rw [this]
      exact hyperbinary_eval_cube_root_of_unity_mem_S_omega_mul _ (hyperbinary_eval_cube_root_of_unity_mem_S_omega_mul _ hz)
  7. If (x, y) is a valid pair, then (ω x, y + ω² x) is a valid pair

    We split into the four definitions of a valid pair. Since S is closed under multiplication by ω, the first component ω x always belongs to S. Using ω² + ω + 1 = 0, the second component simplifies in each case to 0, ω(ω x), -ω²(ω x), or an element of S when the first is 0, satisfying one of the four valid pair clauses.

    lines 77–88

    uses hyperbinary_eval_cube_root_of_unity_omega_sq_add_omega_add_one, hyperbinary_eval_cube_root_of_unity_mem_S_omega_mul

      have h_rel := hyperbinary_eval_cube_root_of_unity_omega_sq_add_omega_add_one
      rcases h with ⟨rfl, hy⟩ | ⟨rfl, hx⟩ | ⟨hx, rfl⟩ | ⟨hx, rfl⟩
      · left
        refine ⟨by ring, by simp [hy]⟩
      · right; right; left
        refine ⟨hyperbinary_eval_cube_root_of_unity_mem_S_omega_mul x hx, ?_⟩
        ring
      · right; right; right
        refine ⟨hyperbinary_eval_cube_root_of_unity_mem_S_omega_mul x hx, ?_⟩
        linear_combination eisensteinOmega * x * h_rel
      · right; left
        refine ⟨by ring, hyperbinary_eval_cube_root_of_unity_mem_S_omega_mul x hx⟩
  8. If (x, y) is a valid pair, then (y + ω² x, ω y) is a valid pair

    We check each of the four forms of a valid pair (x, y). In each case, simplifying the transformed pair using ω³ = 1, ω² + ω + 1 = 0, and the closure of S under negation and multiplication by ω and ω² shows that the new pair is valid.

    lines 93–113

    uses hyperbinary_eval_cube_root_of_unity_omega_cube, hyperbinary_eval_cube_root_of_unity_omega_sq_add_omega_add_one, hyperbinary_eval_cube_root_of_unity_mem_S_omega_sq_mul, hyperbinary_eval_cube_root_of_unity_mem_S_neg

      have h_cube := hyperbinary_eval_cube_root_of_unity_omega_cube
      have h_rel := hyperbinary_eval_cube_root_of_unity_omega_sq_add_omega_add_one
      rcases h with ⟨rfl, hy⟩ | ⟨rfl, hx⟩ | ⟨hx, rfl⟩ | ⟨hx, rfl⟩
      · right; right; left
        refine ⟨by simpa using hy, by ring⟩
      · right; left
        refine ⟨by ring, by simpa using hyperbinary_eval_cube_root_of_unity_mem_S_omega_sq_mul x hx⟩
      · right; right; right
        have h_neg_x : -x ∈ hyperbinary_eval_cube_root_of_unity_S := hyperbinary_eval_cube_root_of_unity_mem_S_neg x hx
        refine ⟨?_, ?_⟩
        · have : eisensteinOmega * x + eisensteinOmega ^ 2 * x = -x := by
            linear_combination x * h_rel
          rw [this]
          exact h_neg_x
        · linear_combination eisensteinOmega ^ 2 * x * h_rel
      · left
        refine ⟨by ring, ?_⟩
        have : eisensteinOmega * (-eisensteinOmega ^ 2 * x) = -x := by
          linear_combination -x * h_cube
        rw [this]
        exact hyperbinary_eval_cube_root_of_unity_mem_S_neg x hx
  9. H_0(ω) = 1

    By definition, the 0-th hyperbinary length polynomial is 1, so evaluating it at ω gives 1.

    lines 120–122

    uses hyperbinaryLengthPoly.eq_1

      dsimp [hyperbinary_eval_cube_root_of_unity_H]
      rw [hyperbinaryLengthPoly.eq_1]
      simp
  10. For any k, H_{2k+1}(ω) = ω · H_k(ω)

    Since 2k + 1 is odd, the polynomial recurrence yields H_{2k+1}(X) = X · H_k(X). Evaluating at X = ω gives H_{2k+1}(ω) = ω H_k(ω).

    lines 126–133

    uses hyperbinaryLengthPoly.eq_2

      dsimp [hyperbinary_eval_cube_root_of_unity_H]
      have h_succ : 2 * k + 1 = (2 * k).succ := rfl
      rw [h_succ, hyperbinaryLengthPoly.eq_2]
      have h_mod : (2 * k + 1) % 2 = 1 := by omega
      have h_div : (2 * k + 1) / 2 = k := by omega
      simp only [h_mod, ↓reduceDIte]
      rw [h_div]
      simp
  11. For any k, H_{2k+2}(ω) = H_{k+1}(ω) + ω² · H_k(ω)

    Since 2k + 2 is even, the polynomial recurrence yields H_{2k+2}(X) = H_{k+1}(X) + X² H_k(X). Evaluating at X = ω gives H_{2k+2}(ω) = H_{k+1}(ω) + ω² H_k(ω).

    lines 138–145

    uses hyperbinaryLengthPoly.eq_2

      dsimp [hyperbinary_eval_cube_root_of_unity_H]
      have h_succ : 2 * k + 2 = (2 * k + 1).succ := rfl
      rw [h_succ, hyperbinaryLengthPoly.eq_2]
      have h_mod : ¬((2 * k + 1 + 1) % 2 = 1) := by omega
      have h_div1 : (2 * k + 1 + 1) / 2 = k + 1 := by omega
      simp only [h_mod, ↓reduceDIte]
      rw [h_div1]
      simp
  12. H_1(ω) = ω

    Writing 1 = 2 · 0 + 1, the odd recurrence gives H_1(ω) = ω H_0(ω) = ω · 1 = ω.

    lines 149–150

    uses hyperbinary_eval_cube_root_of_unity_H_odd, hyperbinary_eval_cube_root_of_unity_H_zero, mul_one

      have : 1 = 2 * 0 + 1 := rfl
      rw [this, hyperbinary_eval_cube_root_of_unity_H_odd, hyperbinary_eval_cube_root_of_unity_H_zero, mul_one]
  13. For every m, the pair (H_m(ω), H_{m+1}(ω)) is a valid pair

    We proceed by strong induction on m. For m = 0, (H_0(ω), H_1(ω)) = (1, ω) is a valid pair since 1 ∈ S and ω = ω · 1. For m + 1, if m + 1 is odd we write m + 1 = 2k + 1, so (H_{m+1}(ω), H_{m+2}(ω)) = (ω H_k(ω), H_{k+1}(ω) + ω² H_k(ω)), which is valid by the odd step lemma applied to the induction hypothesis on k. If m + 1 is even we write m + 1 = 2k + 2, and the even step lemma similarly shows validity.

    lines 155–184

    uses Nat.strong_induction_on, hyperbinary_eval_cube_root_of_unity_H_zero, hyperbinary_eval_cube_root_of_unity_H_one, hyperbinary_eval_cube_root_of_unity_H_odd, hyperbinary_eval_cube_root_of_unity_H_even, hyperbinary_eval_cube_root_of_unity_valid_pair_step_odd, hyperbinary_eval_cube_root_of_unity_valid_pair_step_even

      induction' m using Nat.strong_induction_on with m ih
      rcases m with _ | m
      · rw [hyperbinary_eval_cube_root_of_unity_H_zero, hyperbinary_eval_cube_root_of_unity_H_one]
        right; right; left
        refine ⟨by simp [hyperbinary_eval_cube_root_of_unity_S], by ring⟩
      · by_cases hm : m.succ % 2 = 1
        · obtain ⟨k, hk_lt, hk_eq⟩ : ∃ k, k < m.succ ∧ m.succ = 2 * k + 1 := by
            refine ⟨m.succ / 2, ?_, ?_⟩ <;> omega
          have ih_k := ih k hk_lt
          have h1 : hyperbinary_eval_cube_root_of_unity_H m.succ =
              eisensteinOmega * hyperbinary_eval_cube_root_of_unity_H k := by
            rw [hk_eq, hyperbinary_eval_cube_root_of_unity_H_odd]
          have h2 : hyperbinary_eval_cube_root_of_unity_H (m.succ + 1) =
              hyperbinary_eval_cube_root_of_unity_H (k + 1) + eisensteinOmega ^ 2 * hyperbinary_eval_cube_root_of_unity_H k := by
            have : m.succ + 1 = 2 * k + 2 := by omega
            rw [this, hyperbinary_eval_cube_root_of_unity_H_even]
          rw [h1, h2]
          exact hyperbinary_eval_cube_root_of_unity_valid_pair_step_odd ih_k
        · obtain ⟨k, hk_lt, hk_eq⟩ : ∃ k, k < m.succ ∧ m.succ = 2 * k + 2 := by
            refine ⟨m.succ / 2 - 1, ?_, ?_⟩ <;> omega
          have ih_k := ih k hk_lt
          have h1 : hyperbinary_eval_cube_root_of_unity_H m.succ =
              hyperbinary_eval_cube_root_of_unity_H (k + 1) + eisensteinOmega ^ 2 * hyperbinary_eval_cube_root_of_unity_H k := by
            rw [hk_eq, hyperbinary_eval_cube_root_of_unity_H_even]
          have h2 : hyperbinary_eval_cube_root_of_unity_H (m.succ + 1) =
              eisensteinOmega * hyperbinary_eval_cube_root_of_unity_H (k + 1) := by
            have : m.succ + 1 = 2 * (k + 1) + 1 := by omega
            rw [this, hyperbinary_eval_cube_root_of_unity_H_odd]
          rw [h1, h2]
          exact hyperbinary_eval_cube_root_of_unity_valid_pair_step_even ih_k
  14. For every m, evaluating H_m at ω produces an element of S = {0, ±1, ±ω, ±ω²}

    By the pair validity lemma, (H_m(ω), H_{m+1}(ω)) is a valid pair. Since the first component of any valid pair belongs to S, H_m(ω) ∈ S.

    lines 190–192

    uses hyperbinary_eval_cube_root_of_unity_H_pair_valid, hyperbinary_eval_cube_root_of_unity_valid_pair_fst_mem

      have h := hyperbinary_eval_cube_root_of_unity_H_pair_valid m
      have h_fst := hyperbinary_eval_cube_root_of_unity_valid_pair_fst_mem h
      exact h_fst
Complex.I_sq
The square of the imaginary unit I is -1.
Real.sq_sqrt
The square of the square root of a non-negative real number is the number itself.
hyperbinary_eval_cube_root_of_unity_omega_sq_add_omega_add_one
The primitive cube root of unity ω satisfies ω² + ω + 1 = 0.
Set.mem_insert_iff
An element belongs to insert a s if and only if it equals a or belongs to s.
Set.mem_singleton_iff
An element belongs to the singleton set {b} if and only if it equals b.
hyperbinary_eval_cube_root_of_unity_omega_cube
The cube root of unity ω satisfies ω³ = 1.
hyperbinary_eval_cube_root_of_unity_mem_S_omega_mul
Multiplying any element of S by ω yields an element of S.
hyperbinary_eval_cube_root_of_unity_mem_S_omega_sq_mul
Multiplying any element of S by ω² yields an element of S.
hyperbinary_eval_cube_root_of_unity_mem_S_neg
The negation of any element of S belongs to S.
hyperbinaryLengthPoly.eq_1
The 0-th hyperbinary length polynomial is the constant polynomial 1.
hyperbinaryLengthPoly.eq_2
Recurrence for the (m+1)-st hyperbinary polynomial: X · H_{(m+1)/2} if m+1 is odd, and H_{(m+1)/2} + X² · H_{(m+1)/2 - 1} if m+1 is even.
hyperbinary_eval_cube_root_of_unity_H_odd
Evaluating H at an odd index 2k + 1 gives ω times H(k).
hyperbinary_eval_cube_root_of_unity_H_zero
Evaluating H at 0 gives 1.
mul_one
Multiplying any element by 1 on the right leaves it unchanged.
Nat.strong_induction_on
The principle of strong induction on natural numbers.
hyperbinary_eval_cube_root_of_unity_H_one
Evaluating H at 1 gives ω.
hyperbinary_eval_cube_root_of_unity_H_even
Evaluating H at an even index 2k + 2 gives H(k+1) + ω² H(k).
hyperbinary_eval_cube_root_of_unity_valid_pair_step_odd
If (x, y) is a valid pair, then (ω x, y + ω² x) is also a valid pair.
hyperbinary_eval_cube_root_of_unity_valid_pair_step_even
If (x, y) is a valid pair, then (y + ω² x, ω y) is also a valid pair.
hyperbinary_eval_cube_root_of_unity_H_pair_valid
For all m, the consecutive evaluations (H(m), H(m+1)) form a valid pair.
hyperbinary_eval_cube_root_of_unity_valid_pair_fst_mem
The first component of any valid pair belongs to the set S.

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

noncomputable def hyperbinary_eval_cube_root_of_unity_S : Set ℂ :=  {0, 1, -1, eisensteinOmega, -eisensteinOmega, eisensteinOmega ^ 2, -eisensteinOmega ^ 2}def hyperbinary_eval_cube_root_of_unity_ValidPair (x y : ℂ) : Prop :=  (x = 0 ∧ y ∈ hyperbinary_eval_cube_root_of_unity_S) ∨  (y = 0 ∧ x ∈ hyperbinary_eval_cube_root_of_unity_S) ∨  (x ∈ hyperbinary_eval_cube_root_of_unity_S ∧ y = eisensteinOmega * x) ∨  (x ∈ hyperbinary_eval_cube_root_of_unity_S ∧ y = -eisensteinOmega ^ 2 * x)lemma hyperbinary_eval_cube_root_of_unity_valid_pair_fst_mem {x y : ℂ}    (h : hyperbinary_eval_cube_root_of_unity_ValidPair x y) :    x ∈ hyperbinary_eval_cube_root_of_unity_S := by  rcases h with ⟨rfl, _⟩ | ⟨_, hx⟩ | ⟨hx, _⟩ | ⟨hx, _⟩  · simp [hyperbinary_eval_cube_root_of_unity_S]  · exact hx  · exact hx  · exact hxlemma hyperbinary_eval_cube_root_of_unity_omega_sq_add_omega_add_one :    eisensteinOmega ^ 2 + eisensteinOmega + 1 = 0 := by  have hI : Complex.I ^ 2 = -1 := Complex.I_sq  have h3 : (Real.sqrt 3 : ℂ) ^ 2 = 3 := by    norm_cast    exact Real.sq_sqrt (by norm_num)  dsimp [eisensteinOmega]  have h_div : ((-1 + Complex.I * (Real.sqrt 3 : ℂ)) / 2) ^ 2 = (-1 + Complex.I * Real.sqrt 3) ^ 2 / 4 := by ring  rw [h_div]  have : (-1 + Complex.I * (Real.sqrt 3 : ℂ)) ^ 2 = 1 - 2 * Complex.I * Real.sqrt 3 + Complex.I ^ 2 * (Real.sqrt 3 : ℂ) ^ 2 := by ring  rw [this, hI, h3]  ringlemma hyperbinary_eval_cube_root_of_unity_omega_cube : eisensteinOmega ^ 3 = 1 := by  have h := hyperbinary_eval_cube_root_of_unity_omega_sq_add_omega_add_one  linear_combination (eisensteinOmega - 1) * hlemma hyperbinary_eval_cube_root_of_unity_mem_S_neg (z : ℂ)    (hz : z ∈ hyperbinary_eval_cube_root_of_unity_S) :    -z ∈ hyperbinary_eval_cube_root_of_unity_S := by  simp only [hyperbinary_eval_cube_root_of_unity_S, Set.mem_insert_iff, Set.mem_singleton_iff] at hz ⊢  rcases hz with rfl | rfl | rfl | rfl | rfl | rfl | rfl  · left; ring  · right; right; left; ring  · right; left; ring  · right; right; right; right; left; ring  · right; right; right; left; ring  · right; right; right; right; right; right; ring  · right; right; right; right; right; left; ringlemma hyperbinary_eval_cube_root_of_unity_mem_S_omega_mul (z : ℂ)    (hz : z ∈ hyperbinary_eval_cube_root_of_unity_S) :    eisensteinOmega * z ∈ hyperbinary_eval_cube_root_of_unity_S := by  have h3 := hyperbinary_eval_cube_root_of_unity_omega_cube  simp only [hyperbinary_eval_cube_root_of_unity_S, Set.mem_insert_iff, Set.mem_singleton_iff] at hz ⊢  rcases hz with rfl | rfl | rfl | rfl | rfl | rfl | rfl  · left; ring  · right; right; right; left; ring  · right; right; right; right; left; ring  · right; right; right; right; right; left; ring  · right; right; right; right; right; right; ring  · right; left    calc eisensteinOmega * eisensteinOmega ^ 2 = eisensteinOmega ^ 3 := by ring    _ = 1 := h3  · right; right; left    calc eisensteinOmega * -eisensteinOmega ^ 2 = -eisensteinOmega ^ 3 := by ring    _ = -1 := by rw [h3]lemma hyperbinary_eval_cube_root_of_unity_mem_S_omega_sq_mul (z : ℂ)    (hz : z ∈ hyperbinary_eval_cube_root_of_unity_S) :    eisensteinOmega ^ 2 * z ∈ hyperbinary_eval_cube_root_of_unity_S := by  have : eisensteinOmega ^ 2 * z = eisensteinOmega * (eisensteinOmega * z) := by ring  rw [this]  exact hyperbinary_eval_cube_root_of_unity_mem_S_omega_mul _ (hyperbinary_eval_cube_root_of_unity_mem_S_omega_mul _ hz)lemma hyperbinary_eval_cube_root_of_unity_valid_pair_step_odd {x y : ℂ}    (h : hyperbinary_eval_cube_root_of_unity_ValidPair x y) :    hyperbinary_eval_cube_root_of_unity_ValidPair (eisensteinOmega * x) (y + eisensteinOmega ^ 2 * x) := by  have h_rel := hyperbinary_eval_cube_root_of_unity_omega_sq_add_omega_add_one  rcases h with ⟨rfl, hy⟩ | ⟨rfl, hx⟩ | ⟨hx, rfl⟩ | ⟨hx, rfl⟩  · left    refine ⟨by ring, by simp [hy]⟩  · right; right; left    refine ⟨hyperbinary_eval_cube_root_of_unity_mem_S_omega_mul x hx, ?_⟩    ring  · right; right; right    refine ⟨hyperbinary_eval_cube_root_of_unity_mem_S_omega_mul x hx, ?_⟩    linear_combination eisensteinOmega * x * h_rel  · right; left    refine ⟨by ring, hyperbinary_eval_cube_root_of_unity_mem_S_omega_mul x hx⟩lemma hyperbinary_eval_cube_root_of_unity_valid_pair_step_even {x y : ℂ}    (h : hyperbinary_eval_cube_root_of_unity_ValidPair x y) :    hyperbinary_eval_cube_root_of_unity_ValidPair (y + eisensteinOmega ^ 2 * x) (eisensteinOmega * y) := by  have h_cube := hyperbinary_eval_cube_root_of_unity_omega_cube  have h_rel := hyperbinary_eval_cube_root_of_unity_omega_sq_add_omega_add_one  rcases h with ⟨rfl, hy⟩ | ⟨rfl, hx⟩ | ⟨hx, rfl⟩ | ⟨hx, rfl⟩  · right; right; left    refine ⟨by simpa using hy, by ring⟩  · right; left    refine ⟨by ring, by simpa using hyperbinary_eval_cube_root_of_unity_mem_S_omega_sq_mul x hx⟩  · right; right; right    have h_neg_x : -x ∈ hyperbinary_eval_cube_root_of_unity_S := hyperbinary_eval_cube_root_of_unity_mem_S_neg x hx    refine ⟨?_, ?_⟩    · have : eisensteinOmega * x + eisensteinOmega ^ 2 * x = -x := by        linear_combination x * h_rel      rw [this]      exact h_neg_x    · linear_combination eisensteinOmega ^ 2 * x * h_rel  · left    refine ⟨by ring, ?_⟩    have : eisensteinOmega * (-eisensteinOmega ^ 2 * x) = -x := by      linear_combination -x * h_cube    rw [this]    exact hyperbinary_eval_cube_root_of_unity_mem_S_neg x hxnoncomputable def hyperbinary_eval_cube_root_of_unity_H (m : ℕ) : ℂ :=  Polynomial.aeval eisensteinOmega (hyperbinaryLengthPoly m)lemma hyperbinary_eval_cube_root_of_unity_H_zero :    hyperbinary_eval_cube_root_of_unity_H 0 = 1 := by  dsimp [hyperbinary_eval_cube_root_of_unity_H]  rw [hyperbinaryLengthPoly.eq_1]  simplemma hyperbinary_eval_cube_root_of_unity_H_odd (k : ℕ) :    hyperbinary_eval_cube_root_of_unity_H (2 * k + 1) = eisensteinOmega * hyperbinary_eval_cube_root_of_unity_H k := by  dsimp [hyperbinary_eval_cube_root_of_unity_H]  have h_succ : 2 * k + 1 = (2 * k).succ := rfl  rw [h_succ, hyperbinaryLengthPoly.eq_2]  have h_mod : (2 * k + 1) % 2 = 1 := by omega  have h_div : (2 * k + 1) / 2 = k := by omega  simp only [h_mod, ↓reduceDIte]  rw [h_div]  simplemma hyperbinary_eval_cube_root_of_unity_H_even (k : ℕ) :    hyperbinary_eval_cube_root_of_unity_H (2 * k + 2) =      hyperbinary_eval_cube_root_of_unity_H (k + 1) + eisensteinOmega ^ 2 * hyperbinary_eval_cube_root_of_unity_H k := by  dsimp [hyperbinary_eval_cube_root_of_unity_H]  have h_succ : 2 * k + 2 = (2 * k + 1).succ := rfl  rw [h_succ, hyperbinaryLengthPoly.eq_2]  have h_mod : ¬((2 * k + 1 + 1) % 2 = 1) := by omega  have h_div1 : (2 * k + 1 + 1) / 2 = k + 1 := by omega  simp only [h_mod, ↓reduceDIte]  rw [h_div1]  simplemma hyperbinary_eval_cube_root_of_unity_H_one :    hyperbinary_eval_cube_root_of_unity_H 1 = eisensteinOmega := by  have : 1 = 2 * 0 + 1 := rfl  rw [this, hyperbinary_eval_cube_root_of_unity_H_odd, hyperbinary_eval_cube_root_of_unity_H_zero, mul_one]lemma hyperbinary_eval_cube_root_of_unity_H_pair_valid (m : ℕ) :    hyperbinary_eval_cube_root_of_unity_ValidPair      (hyperbinary_eval_cube_root_of_unity_H m) (hyperbinary_eval_cube_root_of_unity_H (m + 1)) := by  induction' m using Nat.strong_induction_on with m ih  rcases m with _ | m  · rw [hyperbinary_eval_cube_root_of_unity_H_zero, hyperbinary_eval_cube_root_of_unity_H_one]    right; right; left    refine ⟨by simp [hyperbinary_eval_cube_root_of_unity_S], by ring⟩  · by_cases hm : m.succ % 2 = 1    · obtain ⟨k, hk_lt, hk_eq⟩ : ∃ k, k < m.succ ∧ m.succ = 2 * k + 1 := by        refine ⟨m.succ / 2, ?_, ?_⟩ <;> omega      have ih_k := ih k hk_lt      have h1 : hyperbinary_eval_cube_root_of_unity_H m.succ =          eisensteinOmega * hyperbinary_eval_cube_root_of_unity_H k := by        rw [hk_eq, hyperbinary_eval_cube_root_of_unity_H_odd]      have h2 : hyperbinary_eval_cube_root_of_unity_H (m.succ + 1) =          hyperbinary_eval_cube_root_of_unity_H (k + 1) + eisensteinOmega ^ 2 * hyperbinary_eval_cube_root_of_unity_H k := by        have : m.succ + 1 = 2 * k + 2 := by omega        rw [this, hyperbinary_eval_cube_root_of_unity_H_even]      rw [h1, h2]      exact hyperbinary_eval_cube_root_of_unity_valid_pair_step_odd ih_k    · obtain ⟨k, hk_lt, hk_eq⟩ : ∃ k, k < m.succ ∧ m.succ = 2 * k + 2 := by        refine ⟨m.succ / 2 - 1, ?_, ?_⟩ <;> omega      have ih_k := ih k hk_lt      have h1 : hyperbinary_eval_cube_root_of_unity_H m.succ =          hyperbinary_eval_cube_root_of_unity_H (k + 1) + eisensteinOmega ^ 2 * hyperbinary_eval_cube_root_of_unity_H k := by        rw [hk_eq, hyperbinary_eval_cube_root_of_unity_H_even]      have h2 : hyperbinary_eval_cube_root_of_unity_H (m.succ + 1) =          eisensteinOmega * hyperbinary_eval_cube_root_of_unity_H (k + 1) := by        have : m.succ + 1 = 2 * (k + 1) + 1 := by omega        rw [this, hyperbinary_eval_cube_root_of_unity_H_odd]      rw [h1, h2]      exact hyperbinary_eval_cube_root_of_unity_valid_pair_step_even ih_k/-- Evaluating H_m at the cube root of unity ω yields one of {0, ±1, ±ω, ±ω²}. -/theorem hyperbinary_eval_cube_root_of_unity (m : ℕ) :    Polynomial.aeval eisensteinOmega (hyperbinaryLengthPoly m) ∈      ({0, 1, -1, eisensteinOmega, -eisensteinOmega, eisensteinOmega ^ 2, -eisensteinOmega ^ 2} : Set ℂ) := by  have h := hyperbinary_eval_cube_root_of_unity_H_pair_valid m  have h_fst := hyperbinary_eval_cube_root_of_unity_valid_pair_fst_mem h  exact h_fst
See it in the graphDiscuss this resultChallenge it