hyperbinary_eval_cube_root_of_unity
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.
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.
rcases h with ⟨rfl, _⟩ | ⟨_, hx⟩ | ⟨hx, _⟩ | ⟨hx, _⟩ · simp [hyperbinary_eval_cube_root_of_unity_S] · exact hx · exact hx · exact hx
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.
uses
Complex.I_sq,Real.sq_sqrthave 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
The cube of ω is 1, so ω³ = 1
Multiplying the identity ω² + ω + 1 = 0 by ω - 1 gives ω³ - 1 = 0, so ω³ = 1.
uses
hyperbinary_eval_cube_root_of_unity_omega_sq_add_omega_add_onehave h := hyperbinary_eval_cube_root_of_unity_omega_sq_add_omega_add_one linear_combination (eisensteinOmega - 1) * hThe 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.
uses
Set.mem_insert_iff,Set.mem_singleton_iffsimp 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
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.
uses
hyperbinary_eval_cube_root_of_unity_omega_cube,Set.mem_insert_iff,Set.mem_singleton_iffhave 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]
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.
uses
hyperbinary_eval_cube_root_of_unity_mem_S_omega_mulhave : 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)
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.
uses
hyperbinary_eval_cube_root_of_unity_omega_sq_add_omega_add_one,hyperbinary_eval_cube_root_of_unity_mem_S_omega_mulhave 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⟩
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.
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_neghave 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
H_0(ω) = 1
By definition, the 0-th hyperbinary length polynomial is 1, so evaluating it at ω gives 1.
uses
hyperbinaryLengthPoly.eq_1dsimp [hyperbinary_eval_cube_root_of_unity_H] rw [hyperbinaryLengthPoly.eq_1] simp
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(ω).
uses
hyperbinaryLengthPoly.eq_2dsimp [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
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(ω).
uses
hyperbinaryLengthPoly.eq_2dsimp [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
H_1(ω) = ω
Writing 1 = 2 · 0 + 1, the odd recurrence gives H_1(ω) = ω H_0(ω) = ω · 1 = ω.
uses
hyperbinary_eval_cube_root_of_unity_H_odd,hyperbinary_eval_cube_root_of_unity_H_zero,mul_onehave : 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]
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.
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_eveninduction' 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
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.
uses
hyperbinary_eval_cube_root_of_unity_H_pair_valid,hyperbinary_eval_cube_root_of_unity_valid_pair_fst_memhave 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
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.
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