AFTD Auto-Formalizing Theoretical Domains

hyperbinaryLengthPoly

def

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

Statement

noncomputable def hyperbinaryLengthPoly : ℕ → Polynomial ℤ
Defined in
scout/2611-01243-halving-partitions-and-hyperbinary-expansions.md:353
Verified
03 Nov 2026
Axioms
none listed
Used by 2
  • hyperbinaryCountMod3For nonnegative integers m and r, hyperbinaryCountMod3 m r is the sum of coefficients of the hyperbinary length polynomial H_m(z) over…
  • hyperbinary_eval_cube_root_of_unityFor every non-negative integer m, evaluating the hyperbinary length polynomial H_m(z) at the primitive cube root of unity ω = (-1 +…

Read back from the Lean

hyperbinaryLengthPoly is a function from the natural numbers $\mathbb{N}$ to the polynomial ring $\mathbb{Z}[X]$, defined by well-founded recursion on $n$: - hyperbinaryLengthPoly 0 = 1 - For any $n \in \mathbb{N}$, evaluating on $n + 1$: - If $(n + 1) \equiv 1 \pmod 2$ (i.e., $n + 1$ is odd): $$\text{hyperbinaryLengthPoly}(n + 1) = X \cdot \text{hyperbinaryLengthPoly}((n + 1) / 2)$$ - Otherwise (i.e., $n + 1$ is even): $$\text{hyperbinaryLengthPoly}(n + 1) = \text{hyperbinaryLengthPoly}((n + 1) / 2) + X^2 \cdot \text{hyperbinaryLengthPoly}((n + 1) / 2 - 1)$$ where $X$ is the indeterminate Polynomial.X, and / denotes truncated natural number division.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The hyperbinary length polynomial H_m(z). -/
noncomputable def hyperbinaryLengthPoly : ℕ → Polynomial ℤ
| 0 => 1
| n + 1 =>
  if h : (n + 1) % 2 = 1 then
    have : (n + 1) / 2 < n + 1 := Nat.div_lt_self (Nat.succ_pos n) (by decide)
    Polynomial.X * hyperbinaryLengthPoly ((n + 1) / 2)
  else
    have : (n + 1) / 2 < n + 1 := Nat.div_lt_self (Nat.succ_pos n) (by decide)
    have : (n + 1) / 2 - 1 < n + 1 := by omega
    hyperbinaryLengthPoly ((n + 1) / 2) + Polynomial.X ^ 2 * hyperbinaryLengthPoly ((n + 1) / 2 - 1)
termination_by n => n
See it in the graphDiscuss this resultChallenge it