English
There is a Horner-based recursion principle for polynomials: given a target type M on polynomials and data for the base case M(0) and two constructors (adding a nonzero constant, and multiplying by X when the operand is nonzero), one can define M(p) by induction on the degree of p.
Русский
Существует принцип индукции по Хорнеру для полиномов: дана матрица типа M на polynomials и данные для базового случая M(0) и два построителя (добавление ненулевого константного множителя и умножение на X, если аргумент не равен нулю); можно определить M(p) по степеням p.
LaTeX
$$$\\text{recOnHorner} : \\forall M, M0, MC, MX, \\forall p, M(p) \\text{ определяется рекурсивно by Horner steps.}$$$
Lean4
/-- An induction principle for polynomials, valued in Sort* instead of Prop. -/
@[elab_as_elim]
noncomputable def recOnHorner {M : R[X] → Sort*} (p : R[X]) (M0 : M 0)
(MC : ∀ p a, coeff p 0 = 0 → a ≠ 0 → M p → M (p + C a)) (MX : ∀ p, p ≠ 0 → M p → M (p * X)) : M p :=
letI := Classical.decEq R
if hp : p = 0 then hp ▸ M0
else by
have wf : degree (divX p) < degree p := degree_divX_lt hp
rw [← divX_mul_X_add p] at *
exact
if hcp0 : coeff p 0 = 0 then by
rw [hcp0, C_0, add_zero]
exact MX _ (fun h : divX p = 0 => by simp [h, hcp0] at hp) (recOnHorner (divX p) M0 MC MX)
else
MC _ _ (coeff_mul_X_zero _) hcp0
(if hpX0 : divX p = 0 then show M (divX p * X) by rw [hpX0, zero_mul]; exact M0
else MX (divX p) hpX0 (recOnHorner _ M0 MC MX))
termination_by p.degree
