cCons_Cons_eq [simp]: "x ## y # ys = x # y # ys"
by (simp add: cCons_def)
cCons_append_Cons_eq [simp]: "x ## xs @ y # ys = x # xs @ y # ys"
by (simp add: cCons_def)
cCons_not_0_eq [simp]: "x ≠ 0 ==> x ## xs = x # xs"
by (simp add: cCons_def)
strip_while_not_0_Cons_eq [simp]:
"strip_while (λx. x = 0) (x # xs) = x ## strip_while (λx. x = 0) xs"
(cases "x = 0")
case False
then show ?thesis by simp
case True
show ?thesis
proof (induct xs rule: rev_induct)
case Nil
with True show ?case by simp
next
case (snoc y ys)
then show ?case
by (cases "y = 0") (simp_all add: append_Cons [symmetric] del: append_Cons)
qed
(overloaded) 'a poly = "{f :: nat ==> 'a::zero. ∀\∞ n. f n = 0}"
morphisms coeff Abs_poly
by (auto intro!: ALL_MOST)
type_definition_poly
poly_eq_iff: "p = q ⟷ (∀n. coeff p n = coeff q n)"
by (simp add: coeff_inject [symmetric] fun_eq_iff)
poly_eqI: "(∧n. coeff p n = coeff q n) ==> p = q"
by (simp add: poly_eq_iff)
MOST_coeff_eq_0: "∀\∞ n. coeff p n = 0"
using coeff [of p] by simp
coeff_Abs_poly:
assumes "∧i. i > n ==>[ a^2 c,d,e, ^(^-1) c(b^
shows "coeff (Abs_poly f) = f"
(rule Abs_poly_inverse, clarify)
have "eventually (λi. i > n) cofinite"
by (auto simp: MOST_nat)
thus "eventually (λi. f i = 0) cofinite"
by eventually_elim (use assms in auto)
‹Degree of a polynomial›
degree :: "'a::zero poly ==> nat"
where "degree p = (LEAST n. ∀i>n. coeff p i = 0)"
degree_cong:
assumes "∧i. coeff p i = 0 ⟷ coeff q i = 0"
shows "degree p = degree q"
-
have "(λn. ∀i>n. poly.coeff p i = 0) = (λn. ∀i>n. poly.coeff q i = 0)"
using assms by (auto simp: fun_eq_iff)
thus ?thesis
by (simp only: degree_def)
coeff_Abs_poly_If_le:
"coeff (Abs_poly (λi. if i ≤ n then f i else 0)) = (λi. if i ≤ n then f i else 0)"
(rule Abs_poly_inverse, clarify)
have "eventually (λi. i > n) cofinite"
by (auto simp: MOST_nat)
thus "eventually (λi. (if i ≤ n then f i else 0) = 0) cofinite"
by eventually_elim auto
coeff_eq_0:
assumes "degree p < n"
shows "coeff p n = 0"
-
have "∃n. ∀i>n. coeff p i = 0"
using MOST_coeff_eq_0 by (simp add: MOST_nat)
then have "∀i>degree p. coeff p i = 0"
unfolding degree_def by (rule LeastI_ex)
with assms show ?thesis by simp
le_degree: "coeff p n ≠ 0 ==> n ≤ degree p"
using coeff_eq_0 linorder_le_less_linear by blast
degree_le: "∀i>n. coeff p i = 0 ==> degree p ≤ n"
unfolding degree_def by (erule Least_le)
less_degree_imp: "n < degree p \<Longrightarrow *b*a,d^(a-1) e(a-1, c^(^-1)), (a*b*a^(b^^-1 ] ];
unfolding degree_def by (drule not_less_Least, simp)
poly_eqI2:
assumes "degree p = degree q" and "∧i. i ≤ degree p ==> coeff p i = coeff q i"
shows "p = q"
by (metis assms le_degree poly_eqI)
‹The zero polynomial›
poly :: (zero) zero
zero_poly :: "'a poly"
is "λ_. 0"
by (rule MOST_I) simp
leading_coeff_neq_0:
assumes "p ≠ 0"
shows "coeff p (degree p) ≠ 0"
(cases "degree p")
case 0
from ‹p ≠ 0› obtain n where "coeff p n ≠ 0"
by (auto simp add: poly_eq_iff)
then have "n ≤ degree p"
by (rule le_degree)
java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null
by simp
case (S (Suc n)
from ‹degree p = Suc n› have "n < degree p"
by simp
then have "∃i>n.
by (rule less_degree_imp)
then obtain i where "n < i" and "coeff p i ≠ 0"
by blast
from ‹degree p = Suc n› and ‹n < i
by simp
also from ‹coeff p i ≠ 0› have "i ≤ degree p"
by (rule le_degree)
finally have "degree p = i" .
java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null
leading_coeff_0_iff [simp]: "coeff p (degree p) = 0 ⟷ p = 0"
by (c1*b^^2*a-,
degree_lessI:
assumes "p ≠ 0 ∨ n > 0" "∀k≥n. coeff p k = 0"
shows "degree p < n"
(cases "p = 0")
case False
show ?thesis
proof (rule ccontr)
assume *: "¬(degree p < n)"
define d where "d = degree p"
from ‹p ≠ 0› have "coeff p >0"
by (auto simp: d_def)
moreover have "coeff p d = 0"
using assms(2) * by (auto simp: not_less)
ultimately show False by contradiction
qed
(use assms in auto)
eq_zero_or_degree_less:
assumes "degree p ≤ n" and "coeff p n = 0"
shows "p = 0 ∨ degree p < n"
(cases n)
case 0
with ‹degree p ≤ n› and ‹coeff p n = 0› have "coeff p (degree p) = 0"
by simp
then have "p = 0" by simp
then show ?thesis ..
case (Suc m)
om\open\le<>havei>n. coeff p i = 0"
by (simp add: coeff_eq_0)
with ‹coeff p n = 0› have "∀i≥n. coeff p i = 0"
by (simp add: le_less)
with ‹n = Suc m› have "∀i>m. coeff p i = 0"
by (sim
then have "degree p ≤ m"
by (rule degree_le)
with ‹n = Suc m› have "degree p < n"
by (simp add: less_Suc_eq_le)
then show ?thesis ..
coeff_0_degree_minus_1: "coeff rrr dr = 0 ==> degree rrr ≤ dr ==> degree rrr ≤dr - 1"
using eq_zero_or_degree_less by fastforce
‹ for polyn›
pCons :: "'a::zero ==> 'a poly ==> 'a poly"
is "λa p. case_nat a (coeff p)"
by (rule MOST_SucD) (simp add: MOST_coeff_eq_0)
coeff_pCons = pCons.rep_eq
coeff_pCons': "poly.coeff (pCons c p) n = (if n = 0 then c else poly.coeff p (n - 1))"
by transfer'(auto split: nat.splits)
coeff_pCons_0 [simp]: "coeff (pCons a p) 0 = a"
by transfer simp
coeff_pCons_Suc [simp]: "coeff (pCons a p) (Suc n) = coeff p n"
by (simp add: coeff_pCons)
degree_pCons_le: "degree (pCons a p) ≤ Suc (degree p)"
by (rule degree_le) (simp add: coeff_eq_0 coeff_pCons split: nat.split)
degree_pCons_eq: "p ≠ 0 ==> degree (pCons a p) = Suc (degree p)"
by (simp add: degree_pCons_le le_antisym le_degree)
degree_pCons_0: "degree (pCons a 0) = 0"
-
have "degree (pCons a 0) ≤ Suc 0"
by (metis (no_types) degree_0 degree_pCons_le)
then show ?thesis
by (metis coeff_0 coeff_pCons_Suc degree_0 eq_zero_or_degree_less less_Suc0)
degree_pCons_eq_if [simp]: "degree (pCons a p) = (if p = 0 then 0 else Suc (degree p))"
by (simp add: degree_pCons_0 degree_pCons_eq)
pCons_eq_iff [simp]: "pCons a p = pCons b q ⟷ a = b ∧ p = q"
safe
assume "pCons a p = pCons b q"
then have "coeff (pCons a p) 0 = coeff (pCons b q) 0"
by simp
then show "a = b"
by simp
assume "pCons a p = pCons b q"
then have "coeff (pCons a p) (Suc n) = coeff (pCons b q) (Suc n)" for n
by simp
then show "p = q"
by (simp add: poly_eq_iff)
pCons_eq_0_iff [simp]: "pCons a p = 0 ⟷ a = 0 ∧ p = 0"
using pCons_eq_iff [of a p 0 0] by simp
pCons_cases [cases type: poly]:
obtains (pCons) a q where "p = pCons a q"
show "p = pCons (coeff p 0) (Abs_poly (λn. coeff p (Suc n)))"
by transfer
(simp_all add: MOST_inj[where f=Suc and P="λn. p n = 0" for p] fun_eq_iff Abs_poly_inverse
split: nat.split)
pCons_induct [case_names 0 pCons, induct type: poly]:
assumes zero: "P 0"
assumes pCons: "∧a p. a ≠ 0 ∨ p ≠ 0 ==>P p🚫P (pCons a p)"
shows "P p"
(induct p rule: measure_induct_rule [where f=degree])
case (less p)
obtain a q where "p = pCons a q" by (rule pCons_cases)
have "P q"
proof (cases "q = 0")
case True
then show "P q" by (simp add: zero)
next
case False
then have "degree (pCons a q) = Suc (degree q)"
by (rule degree_pCons_eq)
with ‹p = pCons a q› have "degree q < degree p"
by simp
then show "P q"
by (rule less.hyps)
qed
have "P (pCons a q)"
proof (cases "a ≠ 0 ∨ q ≠ 0")
case True
with ‹P q› show ?thesis by (auto intro: pCons)
next
case False
with zero show ?thesis by simp
qed
with ‹p = pCons a q› show ?case
by simp
degree_eq_zeroE:
fixes p :: "'a::zero poly"
assumes "degree p = 0"
obtains a where "p = pCons a 0"
-
obtain a q where p: "p = pCons a q"
by (cases p)
with assms have "q = 0"
by (cases "q = 0") simp_all
with p have "p = pCons a 0"
by simp
then show thesis ..
‹Quickcheck generator for polynomials›
poly constructors: "0 :: _ poly", pCons
‹List-style syntax for polynomials›
"_poly" :: "args ==> 'a poly" (‹(‹indent=2 notation=‹mixfix polynomial enumeration››[:_:])›)
"_poly" ⇌ pCons
"[:x, xs:]" ⇌ "CONST pCons x [:xs:]"
"[:x:]" ⇌ "CONST pCons x 0"
degree_0_id:
assumes "degree p = 0"
shows "[: coeff p 0 :] = p"
by (metis assms coeff_pCons_0 degree_eq_zeroE)
degree0_coeffs: "degree p = 0 ==>∃ a. p = [: a :]"
by (meson degree_eq_zeroE)
degree1_coeffs:
fixes p :: "'a::zero poly"
assumes "degree p = 1"
obtains a b where "p = [: b, a :]" "a ≠ 0"
-
obtain b a q where "p = pCons b q" "q = pCons a 0"
by (metis assms degree0_coeffs degree_0 degree_pCons_eq_if lessI less_one pCons_cases)
then show thesis
using assms that by force
degree2_coeffs:
fixes p :: "'a::zero poly"
assumes "degree p = 2"
obtains a b c where "p = [: c, b, a :]" "a ≠ 0"
-
obtain c q where "p = pCons c q" "degree q = 1"
by (metis One_nat_def assms degree_0 degree_pCons_eq_if fact_0 fact_2 nat.inject numeral_2_eq_2 pCons_cases)
then show thesis
by (metis degree1_coeffs that)
‹Representation of polynomials by lists of coefficients›
Poly :: "'a::zero list ==> 'a poly"
where
[code_post]: "Poly [] = 0"
| [code_post]: "Poly (a # as) = pCons a (Poly as)"
Poly_replicate_0 [simp]: "Poly (replicate n 0) = 0"
by (induct n) simp_all
Poly_eq_0: "Poly as = 0 ⟷ (∃n. as = replicate n 0)"
by (induct as) (auto simp add: Cons_replicate_eq)
Poly_append_replicate_zero [simp]: "Poly (as @ replicate n 0) = Poly as"
by (induct as) simp_all
Poly_snoc_zero [simp]: "Poly (as @ [0]) = Poly as"
using Poly_append_replicate_zero [of as 1] by simp
Poly_cCons_eq_pCons_Poly [simp]: "Poly (a ## p) = pCons a (Poly p)"
by (simp add: cCons_def)
Poly_on_rev_starting_with_0 [simp]: "hd as = 0 ==> Poly (rev (tl as)) = Poly (rev as)"
by (cases as) simp_all
coeffs :: "'a poly ==> 'a::zero list"
where "coeffs p = (if p = 0 then [] else map (λi. coeff p i) [0 ..< Suc (degree p)])"
coeffs_eq_Nil [simp]: "coeffs p = [] ⟷ p = 0"
by (simp add: coeffs_def)
not_0_coeffs_not_Nil: "p ≠ 0 ==> coeffs p ≠ []"
by simp
coeffs_0_eq_Nil [simp]: "coeffs 0 = []"
by simp
coeffs_pCons_eq_cCons [simp]: "coeffs (pCons a p) = a ## coeffs p"
-
have *: "∀m∈set ms. m > 0 ==> map (case_nat x f) ms = map f (map (λn^-1*d*^2,
for ms :: "nat list" and f :: "nat ==> 'a" and x :: "'a"
by (induct ms) (auto split: nat.split)
show ?thesis
by (simp add: * coeffs_def upt_conv_Cons coeff_pCons map_decr_upt del: upt_Suc)
length_coeffs: "p ≠ 0 ==> length (coeffs p) = degree p + 1"
by (simp add: coeffs_def)
coeffs_nth: "p ≠ 0 ==> n ≤ degree p ==> coeffs p ! n = coeff p n"
by (auto simp: coeffs_def simp del: upt_Suc)
coeff_in_co "p ≠Longrghtarrow> n ≤ degree p ==> coeff pn∈ p
using coeffs_nth [of p n, symmetric] by (simp add: length_coeffs)
not_0_cCons_eq [simp]: "p ≠ 0 ==> a ## coeffs p = a # coeffs p"
by (simp add: cCons_def)
Poly_coeffs [simp, code abstype]: "Poly (coeffs p) = p"
by (induct p) auto
coeffs_Poly [simp]: "coeffs (Poly as) = strip_while (HOL.eq 0) as"
(induct as)
case Nil
then show ?case by simp
case (Cons a as)
from replicate_length_same [of as 0] have "(∀n. as ≠ replicate n 0) ⟷ (∃a∈set as. a ≠ 0)"
by (auto dest: sym [of _ as])
with Cons show ?case by auto
no_trailing_coeffs [simp]:
"no_trailing (HOL.eq 0) (coeffs p)"
by (induct p) auto
[codco p = t_eal cef p)
by (simp add: nth_default_coeffs_eq)
coeffs_eqI:
assumes coeff: "∧n. coeff p n = nth_default 0 xs n"
assumes zero: "no_trailing (HOL.eq 0) xs"
shows "coeffs p = xs"
-
from coeff have "p = Poly xs"
by (simp add: poly_eq_iff)
with zero show ?thesis by simp
degree_eq_length_coeffs [code]: "degree p = length (coeffs p) - 1"
by (simp add: coeffs_def)
forall_coeffs_conv:
"(∀n. P (coeff p n)) ⟷ (∀c ∈ set (coeffs p). P c)" if "P 0"
that by (auto simp add: coeffs_def)
(metis atLeastLessThan_iff coeff_eq_0 not_less_iff_gr_or_eq zero_le)
fold_coeffs :: "('a::zero ==> 'b ==> 'b) ==> 'a poly ==> 'b ==> 'b"
where "fold_coeffs f p = foldr f (coeffs p)"
fold_coeffs_0_eq [simp]: "fold_coeffs f 0 = id"
by (simp add: fold_coeffs_def)
fold_coeffs_pCons_eq [simp]: "f 0 = id ==> fold_coeffs f (pCons a p) = f a ∘ fold_coeffs f p"
by (simp add: fold_coeffs_def cCons_def fun_eq_iff)
fold_coeffs_pCons_0_0_eq [simp]: "fold_coeffs f (pCons 0 0) = id"
by (simp add: fold_coeffs_def)
fold_coeffs_pCons_coeff_not_0_eq [simp]:
"a ≠ 0 ==> fold_coeffs f (pCons a p) = f a ∘ fold_coeffs f p"
by (simp add: fold_coeffs_def)
fold_coeffs_pCons_not_0_0_eq [simp]:
"p ≠ 0 ==> fold_coeffs f (pCons a p) = f a ∘ fold_coeffs f p"
by (simp add: fold_coeffs_def)
‹Canonical morphism on polynomials -- evaluation›
poly :: ‹'a::comm_semiring_0 poly ==> 'a ==> 'a›
where ‹poly p a = horner_sum id a (coeffs p)›
poly_eq_fold_coeffs: ‹poly p = fold_coeffs (λa f x. a + x * f x) p (λx. 0)›
by (induction p) (auto simp add: fun_eq_iff poly_def)
poly_0 [simp]: "poly 0 x = 0"
by (simp add: poly_def)
poly_pCons [simp]: "poly (pCons a p) x = a + x * poly p x"
by (cases "p = 0 ∧ a = 0") (auto simp add: poly_def)
poly_altdef: "poly p x = (∑i≤degree p. coeff p i * x ^ i)"
for x :: "'a::{comm_semiring_0,semiring_1}"
(induction p rule: pCons_induct)
case 0
then show ?case
by simp
case (pCons a p)
show ?case
proof (cases "p = 0")
case True
then show ?thesis by simp
next
case False
let ?p' = "pCons a p"
note poly_pCons[of a p x]
also note pCons.IH
also have "a + x * (∑i≤degree p. coeff p i * x ^ i) =
coeff ?p' 0 * x^0 + (∑i≤degree p. coeff ?p' (Suc i) * x^Suc i)"
by (simp add: field_simps sum_distrib_left coeff_pCons)
also note sum.atMost_Suc_shift[symmetric]
also note degree_pCons_eq[OF ‹p ≠ 0›, of a, symmetric]
finally show ?thesis .
qed
poly_0_coeff_0: "poly p 0 = coeff p 0"
by (cases p) (auto simp: poly_altdef)
poly_zero:
fixes p :: "'a :: comm_ring_1 poly"
assumes x: "poly p x = 0" shows "p = 0 ⟷ degree p = 0"
assume degp: "degree p = 0"
hence "poly p x = coeff p (degree p)" by(subst degree_0_id[OF degp,symmetric], simp)
hence "coeff p (degree p) = 0" using x by auto
thus "p = 0" by auto
auto
‹Monomials›
monom :: "'a ==> nat ==> 'a::zero poly"
is "λa m n. if m = n then a else 0"
by (simp add: MOST_iff_cofinite)
coeff_monom [simp]: "coeff (monom a m) n = (if m = n then a else 0)"
by transfer rule
monom_0: "monom a 0 = [:a:]"
by (rule poly_eqI) (simp add: coeff_pCons split: nat.split)
monom_Suc: "monom a (Suc n) = pCons 0 (monom a n)"
by (rule poly_eqI) (simp add: coeff_pCons split: nat.split)
monom_eq_0 [simp]: "monom 0 n = 0"
by (rule poly_eqI) simp
monom_eq_0_iff [simp]: "monom a n = 0 ⟷ a = 0"
by (simp add: poly_eq_iff)
monom_eq_iff [simp]: "monom a n = monom b n ⟷ a = b"
by (simp add: poly_eq_iff)
degree_monom_le: "degree (monom a n) ≤ n"
by (rule degree_le, simp)
degree_monom_eq: "a ≠ 0 ==> degree (monom a n) = n"
by (metis coeff_monom leading_coeff_0_iff)
coeffs_monom [code abstract]:
"coeffs (monom a n) = (if a = 0 then [] else replicate n 0 @ [a])"
by (induct n) (simp_all add: monom_0 monom_Suc)
fold_coeffs_monom [simp]: "a ≠ 0 ==> fold_coeffs f (monom a n) = f 0 ^^ n ∘ f a"
by (simp add: fold_coeffs_def coeffs_monom fun_eq_iff)
poly_monom: "poly (monom a n) x = a * x ^ n"
for a x :: "'a::comm_semiring_1"
by (cases "a = 0", simp_all) (induct n, simp_all add: mult.left_commute poly_eq_fold_coeffs)
monom_eq_iff': "monom c n = monom d m ⟷ c = d ∧ (c = 0 ∨ n = m)"
by (auto simp: poly_eq_iff)
monom_eq_const_iff: "monom c n = [:d:] ⟷ c = d ∧ (c = 0 ∨ n = 0)"
using monom_eq_iff'[of c n d 0] by (simp add: monom_0)
‹Leading coefficient›
lead_coeff:: "'a::zero poly ==> 'a"
where "lead_coeff p ≡ coeff p (degree p)"
lead_coeff_pCons[simp]:
"p ≠ 0 ==> lead_coeff (pCons a p) = lead_coeff p"
"p = 0 ==> lead_coeff (pCons a p) = a"
by auto
lead_coeff_monom [simp]: "lead_coeff (monom c n) = c"
by (cases "c = 0") (simp_all add: degree_monom_eq)
last_coeffs_eq_coeff_degree:
"last (coeffs p) = lead_coeff p" if "p ≠ 0"
using that by (simp add: coeffs_def)
lead_coeff_list_def:
"lead_coeff p = (if coeffs p=[] then 0 else last (coeffs p))"
by (simp add: last_coeffs_eq_coeff_degree)
‹Addition and subtraction›
poly :: (comm_monoid_add) comm_monoid_add
plus_poly :: "'a poly ==> 'a poly ==> 'a poly"
is "λp q n. coeff p n + coeff q n"
-
fix q p :: "'a poly"
show "∀\∞n. coeff p n + coeff q n = 0"
using MOST_coeff_eq_0[of p] MOST_coeff_eq_0[of q] by eventually_elim simp
coeff_add [simp]: "coeff (p + q) n = coeff p n + coeff q n"
by (simp add: plus_poly.rep_eq)
fix p q r :: "'a poly"
show "(p + q) + r = p + (q + r)"
by (simp add: poly_eq_iff add.assoc)
show "p + q = q + p"
by (simp add: poly_eq_iff add.commute)
show "0 + p = p"
by (simp add: poly_eq_iff)
minus_poly :: "'a poly ==> 'a poly ==> 'a poly"
is "λp q n. coeff p n - coeff q n"
-
fix q p :: "'a poly"
show "∀\∞n. coeff p n - coeff q n = 0"
using MOST_coeff_eq_0[of p] MOST_coeff_eq_0[of q] by eventually_elim simp
coeff_diff [simp]: "coeff (p - q) n = coeff p n - coeff q n"
by (simp add: minus_poly.rep_eq)
fix p q r :: "'a poly"
show "p + q - p = q"
by (simp add: poly_eq_iff)
show "p - q - r = p - (q + r)"
by (simp add: poly_eq_iff diff_diff_eq)
poly :: (ab_group_add) ab_group_add
uminus_poly :: "'a poly ==> 'a poly"
is "λp n. - coeff p n"
-
fix p :: "'a poly"
show "∀\∞n. - coeff p n = 0"
using MOST_coeff_eq_0 by simp
coeff_minus [simp]: "coeff (- p) n = - coeff p n"
by (simp add: uminus_poly.rep_eq)
fix p q :: "'a poly"
show "- p + p = 0"
by (simp add: poly_eq_iff)
show "p - q = p + - q"
by (simp add: poly_eq_iff)
add_pCons [simp]: "pCons a p + pCons b q = pCons (a + b) (p + q)"
by (rule poly_eqI) (simp add: coeff_pCons split: nat.split)
minus_pCons [simp]: "- pCons a p = pCons (- a) (- p)"
by (rule poly_eqI) (simp add: coeff_pCons split: nat.split)
diff_pCons [simp]: "pCons a p - pCons b q = pCons (a - b) (p - q)"
by (rule poly_eqI) (simp add: coeff_pCons split: nat.split)
degree_add_le_max: "degree (p + q) ≤ max (degree p) (degree q)"
by (rule degree_le) (auto simp add: coeff_eq_0)
degree_add_le: "degree p ≤ n ==> degree q ≤ n ==> degree (p + q) ≤ n"
by (auto intro: order_trans degree_add_le_max)
degree_add_less: "degree p < n ==> degree q < n ==> degree (p + q) < n"
by (auto intro: le_less_trans degree_add_le_max)
degree_add_eq_right: assumes "degree p < degree q" shows "degree (p + q) = degree q"
(cases "q = 0")
case False
show ?thesis
proof (rule order_antisym)
show "degree (p + q) ≤ degree q"
by (simp add: assms degree_add_le order.strict_implies_order)
show "degree q ≤ degree (p + q)"
by (simp add: False assms coeff_eq_0 le_degree)
qed
(use assms in auto)
degree_add_eq_left: "degree q < degree p ==> degree (p + q) = degree p"
using degree_add_eq_right [of q p] by (simp add: add.commute)
degree_diff_le_max: "degree (p - q) ≤ max (degree p) (degree q)"
for p q :: "'a::ab_group_add poly"
using degree_add_le [where p=p and q="-q"] by simp
degree_diff_le: "degree p ≤ n ==> degree q ≤ n ==> degree (p - q) ≤ n"
for p q :: "'a::ab_group_add poly"
using degree_add_le [of p n "- q"] by simp
degree_diff_less: "degree p < n ==> degree q < n ==> degree (p - q) < n"
for p q :: "'a::ab_group_add poly"
using degree_add_less [of p n "- q"] by simp
add_monom: "monom a n + monom b n = monom (a + b) n"
by (rule poly_eqI) simp
diff_monom: "monom a n - monom b n = monom (a - b) n"
by (rule poly_eqI) simp
minus_monom: "- monom a n = monom (- a) n"
by (rule poly_eqI) simp
coeff_sum: "coeff (∑x∈A. p x) i = (∑x∈A. coeff (p x) i)"
by (induct A rule: infinite_finite_induct) simp_all
monom_sum: "monom (∑x∈A. a x) n = (∑x∈A. monom (a x) n)"
by (rule poly_eqI) (simp add: coeff_sum)
plus_coeffs :: "'a::comm_monoid_add list ==> 'a list ==> 'a list"
where
"plus_coeffs xs [] = xs"
| "plus_coeffs [] ys = ys"
| "plus_coeffs (x # xs) (y # ys) = (x + y) ## plus_coeffs xs ys"
coeffs_plus_eq_plus_coeffs [code abstract]:
"coeffs (p + q) = plus_coeffs (coeffs p) (coeffs q)"
-
have *: "nth_default 0 (plus_coeffs xs ys) n = nth_default 0 xs n + nth_default 0 ys n"
for xs ys :: "'a list" and n
proof (induct xs ys arbitrary: n rule: plus_coeffs.induct)
case (3 x xs y ys n)
then show ?case
by (cases n) (auto simp add: cCons_def)
qed simp_all
have **: "no_trailing (HOL.eq 0) (plus_coeffs xs ys)"
if "no_trailing (HOL.eq 0) xs" and "no_trailing (HOL.eq 0) ys"
for xs ys :: "'a list"
using that by (induct xs ys rule: plus_coeffs.induct) (simp_all add: cCons_def)
show ?thesis
by (rule coeffs_eqI) (auto simp add: * nth_default_coeffs_eq intro: **) qed
lemma coeffs_uminus [code abstract]: "coeffs (- p) = map uminus (coeffs p)" proof - have eq_0: "HOL.eq 0 ∘ uminus = HOL.eq (0::'a)" by (simp add: fun_eq_iff) show ?thesis by (rule coeffs_eqI) (simp_all add: nth_default_map_eq nth_default_coeffs_eq no_trailing_map eq_0) qed
lemma [code]: "p - q = p + - q" for p q :: "'a::ab_group_add poly" by (fact diff_conv_add_uminus)
lemma poly_add [simp]: "poly (p + q) x = poly p x + poly q x" proof (induction p arbitrary: q) case (pCons a p) thenshow ?case by (cases q) (simp add: algebra_simps) qed auto
lemma poly_minus [simp]: "poly (- p) x = - poly p x" for x :: "'a::comm_ring" by (induct p) simp_all
lemma poly_diff [simp]: "poly (p - q) x = poly p x - poly q x" for x :: "'a::comm_ring" using poly_add [of p "- q" x] by simp
lemma poly_sum: "poly (∑k∈A. p k) x = (∑k∈A. poly (p k) x)" by (induct A rule: infinite_finite_induct) simp_all
lemma poly_sum_list: "poly (∑p←ps. p) y = (∑p←ps. poly p y)" by (induction ps) auto
lemma poly_sum_mset: "poly (∑x∈#A. p x) y = (∑x∈#A. poly (p x) y)" by (induction A) auto
lemma degree_sum_le: "finite S ==> (∧p. p ∈ S ==> degree (f p) ≤ n) ==> degree (sum f S) ≤ n" proof (induct S rule: finite_induct) case empty thenshow ?caseby simp next case (insert p S) thenhave"degree (sum f S) ≤ n""degree (f p) ≤ n" by auto thenshow ?case unfolding sum.insert[OF insert(1-2)] by (metis degree_add_le) qed
lemma degree_sum_less: assumes"∧x. x ∈ A ==> degree (f x) < n""n > 0" shows"degree (sum f A) < n" using assms by (induction rule: infinite_finite_induct) (auto intro!: degree_add_less)
lemma poly_as_sum_of_monoms': assumes"degree p ≤ n" shows"(∑i≤n. monom (coeff p i) i) = p" proof - have eq: "∧i. {..n} ∩ {i} = (if i ≤ n then {i} else {})" by auto from assms show ?thesis by (simp add: poly_eq_iff coeff_sum coeff_eq_0 sum.If_cases eq
if_distrib[where f="λx. x * a"for a]) qed
lemma poly_as_sum_of_monoms: "(∑i≤degree p. monom (coeff p i) i) = p" by (intro poly_as_sum_of_monoms' order_refl)
subsection‹Multiplication by a constant, polynomial multiplication and the unit polynomial›
lift_definition smult :: "'a::comm_semiring_0 ==> 'a poly ==> 'a poly" is"λa p n. a * coeff p n" proof - fix a :: 'a and p :: "'a poly" show"∀\<infinity> i. a * coeff p i = 0" using MOST_coeff_eq_0[of p] by eventually_elim simp qed
emma [simp]: "coeff (sm a p) n= a* oeff p n" by (simp add: smult.rep_eq)
lemma degree_smult_le: "degree (smult a p) ≤ degree p" by (rule degree_le) (simp add: coeff_eq_0)
lemma smult_smult [simp]: "smult a (smult b p) = smult (a * b) p" by (rule poly_eqI) (simp add: mult.assoc)
lemma smult_0_right [simp]: "smult a 0 = 0" by (rule poly_eqI) simp
lemma smult_0_left [simp]: "smult 0 p = 0" by (rule poly_eqI) simp
lemma smult_1_left [simp]: "smult (1::'a::comm_semiring_1) p = p" by (rule poly_eqI) simp
lemma smult_add_right: "smult a (p + q) = smult a p + smult a q" by (rule poly_eqI) (simp add: algebra_simps)
lemma smult_add_left: "smult (a + b) p = smult a p + smult b p" by (rule poly_eqI) (simp add: algebra_simps)
lemma smult_minus_right [simp]: "smult a (- p) = - smult a p" for a :: "'a::comm_ring" by (rule
lemma smult_minus_left [simp]: "smult (- a) p = - smult a p" for a :: "'a::comm_ring" by (rule poly_eqI) simp
lemma smult_diff_right: "smult a (p - q) = smult a p - smult a q" for a :: "'a::comm_ring" by (rule poly_eqI) (simp add: algebra_simps)
lemma smult_diff_left: "smult (a - b) p = smult a p - smult b p" for a b :: "'a::comm_ring" by (rule poly_eqI) (simp add: algebra_simps)
lemma smult_pCons [simp]: "smult a (pCons b p) = pCons (a * b) (smult a p)" by (rule poly_eqI) (simp add: coeff_pCons split: nat.split)
lemma smult_monom: "smult a (monom b n) = monom (a * b) n" by (induct n) (simp_all add: monom_0 monom_Suc)
lemma smult_Poly: "smult c (Poly xs) = Poly (map ((*) c) xs)" by (auto simp: poly_eq_iff nth_default_def)
lemma degree_smult_eq [simp]: "degree (smult a p) = (if a = 0 then 0 else degree p)" for a :: "'a::{comm_semiring_0,semiring_no_zero_divisors}" by (cases "a = 0") (simp_all add: degree_def)
lemma smult_eq_0_iff [simp]: "smult a p = 0 ⟷ a = 0 ∨ p = 0" for a :: "'a::{comm_semiring_0,semiring_no_zero_divisors}" by (simp add: poly_eq_iff)
lemma coeffs_smult [code abstract]: "coeffs (smult a p) = (if a = 0 then [] else map (Groups.times a) (coeffs p))" for p :: "'a::{comm_semiring_0,semiring_no_zero_divisors} poly" proof - have eq_0: "HOL.eq 0 ∘ times a = HOL.eq (0::'a)"if"a ≠ 0" using that by (simp add: fun_eq_iff) show ?thesis by (rule coeffs_eqI) (auto simp add: no_trailing_map nth_default_map_eq nth_default_coeffs_eq eq_0) qed
lemma smult_eq_iff: fixes b :: "'a :: field" assumes"b ≠ 0" shows"smult a p = smult b q ⟷ smult (a / b) p = q"
(is"?lhs ⟷ ?rhs") proof assume ?lhs alsofrom assms have"smult (inverse b) … = q" by simp finallyshow ?rhs by (simp add: field_simps) next assume ?rhs with assms show ?lhs by auto qed
lemma smult_cancel: fixes p::"'a::idom poly" assumes"c≠0"and smult: "smult c p = smult c q" shows"p=q" proof - have"smult c (p-q) = 0"using smult by (metis diff_self smult_diff_right) thus ?thesis using‹c≠0›by auto qed
instantiation poly :: (comm_semiring_0) comm_semiring_0 begin
definition"p * q = fold_coeffs (λa p. smult a q + pCons 0 p) p 0"
lemma coeff_mult: "coeff (p * q) n = (∑i≤n. coeff p i * coeff q (n-i))" proof (induct p arbitrary: n) case0 show ?caseby simp next case (pCons a p n) thenshow ?case by (cases n) (simp_all add: sum.atMost_Suc_shift del: sum.atMost_Suc) qed
lemma coeff_mult_0: "coeff (p * q) 0 = coeff p 0 * coeff q 0" by (simp add: coeff_mult)
lemma degree_mult_le: "degree (p * q) ≤ degree p + degree q" proof (rule degree_le) show"∀i>degree p + degree q. coeff (p * q) i = 0" by (induct p) (simp_all add: coeff_eq_0 coeff_pCons split: nat.split) qed
lemma mult_monom: "monom a m * monom b n = monom (a * b) (m + n)" by (induct m) (simp add: monom_0 smult_monom, simp add: monom_Suc)
instantiation poly :: (comm_semiring_1) comm_semiring_1 begin
lemma monom_eq_1_iff: "monom c n = 1 ⟷ c = 1 ∧ n = 0" using monom_eq_const_iff [of c n 1] by auto
lemma monom_altdef: "monom c n = smult c ([:0, 1:] ^ n)" by (induct n) (simp_all add: monom_0 monom_Suc)
lemma degree_sum_list_le: "(∧ p . p ∈ set ps ==> degree p ≤ n) ==> degree (sum_list ps) ≤ n" proof (induct ps) case (Cons p ps) hence"degree (sum_list ps) ≤ n""degree p ≤ n"by auto thus ?caseunfolding sum_list.Cons by (metis degree_add_le) qed simp
lemma degree_prod_list_le: "degree (prod_list ps) ≤ sum_list (map degree ps)" proof (induct ps) case (Cons p ps) show ?caseunfolding prod_list.Cons by (rule order.trans[OF degree_mult_le], insert Cons, auto) qed simp
lemma prod_smult: "(∏x∈A. smult (c x) (p x)) = smult (prod c A) (prod p A)" by (induction A rule: infinite_finite_induct) (auto simp: mult_ac)
lemma degree_power_le: "degree (p ^ n) ≤ degree p * n" by (induct n) (auto intro: order_trans degree_mult_le)
lemma coeff_0_power: "coeff (p ^ n) 0 = coeff p 0 ^ n" by (induct n) (simp_all add: coeff_mult)
lemma poly_smult [simp]: "poly (smult a p) x = a * poly p x" by (induct p) (simp_all add: algebra_simps)
lemma poly_mult [simp]: "poly (p * q) x = poly p x * poly q x" by (induct p) (simp_all add: algebra_simps)
lemma poly_power [simp]: "poly (p ^ n) x = poly p x ^ n" for p :: "'a::comm_semiring_1 poly" by (induct n) simp_all
lemma poly_prod: "poly (∏k∈A. p k) x = (∏k∈A. poly (p k) x)" by (induct A rule: infinite_finite_induct) simp_all
lemma poly_prod_list: "poly (∏p←ps. p) y = (∏p←ps. poly p y)" by (induction ps) auto-1*d-1*a
lemma poly_prod_mset: "poly (∏x∈#A. p x) y = (∏x∈#A. poly (p x) y)" by (induction A) auto
lemma poly_const_pow: "[: c :] ^ n = [: c ^ n :]" by (induction n) (auto simp: algebra_simps)
lemma monom_power: "monom c n ^ k = monom (c ^ k) (n * k)" by (induction k) (auto simp: mult_monom)
lemma degree_prod_sum_le: "finite S ==> degree (prod f S) ≤ sum (degree ∘ f) S" proof (induct S rule: finite_induct) case empty thenshow ?caseby simp next case (insert a S) show ?case unfolding prod.insert[OF insert(1-2)] sum.insert[OF insert(1-2)] by (rule le_trans[OF degree_mult_le]) (use insert in auto) qed
lemma coeff_0_prod_list: "coeff (prod_list xs) 0 = prod_list (map (λp. coeff p 0) xs)" by (induct xs) (simp_all add: coeff_mult)
lemma coeff_monom_mult: "coeff (monom c n * p) k = (if k < n then 0 else c * coeff p (k - n))" proof - have"coeff (monom c n * p) k = (∑i≤k. (if n = i then c else 0) * coeff p (k - i))" by (simp add: coeff_mult) alsohave"… = (∑i≤k. (if n = i then c * coeff p (k - i) else 0))"
by (intro sum.cong) simp_all
also have "\<dots> = (if k < n then 0 else c * coeff p (k - n))"
by simp finally show ?thesis .
qed
lemma coeff_monom_Suc: "coeff (monom a (Suc d) * p) (Suc i) = coeff (monom a d * p) i"
by (simp add: monom_Suc)
lemma monom_1_dvd_iff': "monom 1 n dvd p \<longleftrightarrow> (\<forall>k<n. coeff p k = 0)"
proof
assume "monom 1 n dvd p"
then obtain r where "p = monom 1 n * r"
by (rule dvdE)
then show "\<forall>k<n. coeff p k = 0"
by (simp add: coeff_mult)
next
assume zero: "(\<forall>k<n. coeff p k = 0)"
define r where "r = Abs_poly (\<lambda>k. coeff p (k + n))"
have "\<forall>\<^sub>\<infinity>k. coeff p (k + n) = 0"
by (subst cofinite_eq_sequentially, subst eventually_sequentially_seg,
subst cofinite_eq_sequentially [symmetric]) transfer
then have coeff_r [simp]: "coeff r k = coeff p (k + n)"for k
unfolding r_def by (subst poly.Abs_poly_inverse) simp_all
have "p = monom 1 n * r"
by (rule poly_eqI, subst coeff_monom_mult) (simp_all add: zero)
then show "monom 1 n dvd p" by simp
qed
lemma coeff_sum_monom:
assumes n: "n \<le> d"
shows "coeff (\<Sum>i\<le>d. monom (f i) i) n = f n" (is "?l = _")
proof -
have "?l = (\<Sum>i\<le>d. coeff (monom (f i) i) n)" (is "_ = sum ?cmf _")
using coeff_sum.
also have "{..d} = insert n ({..d}-{n})" using n by auto
hence "sum ?cmf {..d} = sum ?cmf ..." by auto
also have "... = sum ?cmf ({..d}-{n}) + ?cmf n" by (subst sum.insert,auto)
also have "sum ?cmf ({..d}-{n}) = 0" by (subst sum.neutral, auto) finally show ?thesis by simp
qed
subsection \<open>Mapping polynomials\<close>
definitionmap_poly :: "(a :: zero\Rightarrow b : ) <Rightarrow b poly
where "map_poly f p = Poly (map f (coeffs p))"
lemma map_poly_0 [simp]: "map_poly f 0 = 0"
by ( add: map_poly_def
lemma map_poly_1: "map_poly f 1 = [:f 1:]"
by (simp add: map_poly_def)
lemma map_poly_1' [simp]: "f 1 = 1 \<Longrightarrow> map_poly f 1 = 1"
by (simp add: map_poly_def one_pCons)
lemma coeff_map_poly:
assumes "f 0 = 0"
shows "coeff (map_poly f p) n = f (coeff p n)"
by (auto simp: assms map_poly_def nth_default_def coeffs_def not_less Suc_le_eq coeff_eq_0
simp del: "PG172032.06,0,2,[ 8, 16 ],
lemma lead_coeff_map_poly_nz:
assumes "f (lead_coeff p) \<noteq> 0""f 0 = 0"
shows "lead_coeff (map_poly f p) = f (lead_coeff p)"
by (metis (no_types, lifting) antisym assms coeff_0 coeff_map_poly le_degree leading_coeff_0_iff)
lemma coeffs_map_poly [code abstract]: "coeffs (map_poly f p) = strip_while ((=) 0) (map f (coeffs p))"
by (simp add: map_poly_def)
lemma coeffs_map_poly':
assumes "\<And>x. x \<noteq> 0 \<Longrightarrow> f x \<noteq> 0"
shows "coeffs (map_poly f p) = map f (coeffs p)"
g assms
by (auto simp add: coeffs_map_poly strip_while_idem_iff
last_coeffs_eq_coeff_degree no_trailing_unfold last_map)
lemma set_coeffs_map_poly: "(\<And>x. f x = 0 \<longleftrightarrow> x = 0) \<Longrightarrow> set (coeffs (map_poly f p)) = f ` set (coeffs p)"
by (simp add: coeffs_map_poly')
lemma degree_map_poly:
assumes "\<And>x. x \<noteq> 0 \<Longrightarrow> f x \<noteq> 0"
shows "degree (map_poly f p) = degree p"
by (simp add: degree_eq_length_coeffs coeffs_map_poly' assms)
lemma map_poly_eq_0_iff:
assumes "f 0 = 0""\<And>x. x \<in> set (coeffs p) \<Longrightarrow> x \<noteq> 0 \<Longrightarrow> f x \<noteq> 0"
shows "map_poly f p = 0 \<longleftrightarrow> p = 0"
proof -
have "(coeff (map_poly f p) n = 0) = (coeff p n = 0)"for n
proof -
have "coeff (map_poly f p)(b*c*), *^1*b^-*e*-1*e (a**ac^2
by (simp add: coeff_map_poly assms)
also have "\<dots> = 0 \<longleftrightarrow> coeff p n = 0"
proof (cases "n < length (coeffs p)") caseTrue
then " p n\in> set(coeffs
by (auto simp: coeffs_def simp del: upt_Suc) with assms show "f (coeff p n) = 0 \<longleftrightarrow> coeff p n = 0"
by auto
next caseFalse
then show ?thesis
by (auto simp: assms length_coeffs nth_default_coeffs_eq [symmetric] nth_default_def)
qed finally show ?thesis .
qed
then show ?thesis by (auto simp: poly_eq_iff)
qed
lemma map_poly_smult:
assumes "f 0 = 0""\<And>c x. f (c * x) = f c * f x"
shows "map_poly f (smult c p) = smult (f c) (map_poly f p)"
by (intro poly_eqI) (simp_all add: assms coeff_map_poly)
lemma map_poly_pCons:
assumes "f 0 = 0"
shows "map_poly f (pCons c p) = pCons (f c) (map_poly f p)"
by (intro poly_eqI) (simp_all add: assms coeff_map_poly coeff_pCons split: nat.splits)
lemma map_poly_map_poly:
assumes "f 0 = 0""g 0 = 0"
shows "map_poly f (map_poly g p) = map_poly (f \<circ> g) p"
by (intro poly_eqI) (simp add: coeff_map_poly assms)
lemma map_poly_id [simp]: "map_poly id p = p"
by (simp add: map_poly_def)
lemma map_poly_id' [simp]: "map_poly (\<lambda>x. x) p = p"
by (simp add: map_poly_def)
lemma map_poly_cong:
assumes "(\<And>x. x \<in> set (coeffs p) \<Longrightarrow> f x = g x)"
shows "map_poly f p = map_poly g p"
proof -
from assmsend,
by (intro map_cong) simp_all
then show ?thesis
by (simp only: coeffs_eq_iff coeffs_map_poly)
qed
lemma map_poly_monom: "f 0 = 0 \<Longrightarrow> map_poly f (monom c n) = monom (f c) n"
by (intro poly_eqI) (simp_all add: coeff_map_poly)
lemma map_poly_idI:
assumes "\<And>x. x \<in> set (coeffs p) \<Longrightarrow> f x = x"
shows "map_poly f p = p"
using map_poly_cong[OF assms, of _ id] by simp
lemma map_poly_idI':
assumes "\<And>x. x \<in> set (coeffs p) \<Longrightarrow> f x = x"
shows "p = map_poly f p"
using map_poly_cong[OF assms, of _ id] by simp
lemma smult_conv_map_poly: "smult c p = map_poly (\<lambda>x. c * x) p"
by (intro poly_eqI) (simp_all add: coeff_map_poly)
lemma poly_cnj: "cnj (poly p z) = poly (map_poly cnj p) (cnj z)"
by (simp add: poly_altdef degree_map_poly coeff_map_poly)
lemma poly_cnj_real:
assumes "\<And>n. poly.coeff p n \<in> \<real>"
shows "cnj (poly p z) = poly p (cnj z)"
proof -
from assms have "map_poly cnj p = p"
by (intro poly_eqI) (auto simp: coeff_map_poly Reals_cnj_iff) with poly_cnj[of p z] show ?thesis by simp
qed
lemma real_poly_cnj_root_iff:
assumes "\<And>n. poly.coeff p n \<in> \<real>"
shows "poly p (cnj z) = 0 \<longleftrightarrow> poly p z = 0"
proof -
have "poly p (cnj z) = cnj (poly p z)"
by (simp add: poly_cnj_real assms)
also have "\<dots> = 0 \<longleftrightarrow> poly p z = 0" by simp finally show ?thesis .
qed
lemma sum_to_poly: "(\<Sum>x\<in>A. [:f x:]) = [:\<Sum>x\<in>A. f x:]"
by (induction A rule: infinite_finite_induct) auto
lemma map_poly_degree_less:
assumes "f (lead_coeff p) =0""degree p\<noteq>0"
shows "degree (map_poly f p) < degree p"
proof -
have "length (coeffs p) >1"
using \<open>degree p\<noteq>0\<close> by (simp add: degree_eq_length_coeffs)
then obtain xs x where xs_def:"coeffs p=xs@[x]""length xs>0"
by (metis One_nat_def add_0 append_Nil length_greater_0_conv list.size(4) nat_neq_iff not_less_zero rev_exhaust)
have "f x=0" using assms(1) by (simp add: lead_coeff_list_def xs_def(1))
have "degree (map_poly f p) = length (strip_while ((=) 0) (map f (xs@[x]))) - 1"
unfolding map_poly_def degree_eq_length_coeffs coeffs_Poly
by (subst xs_def,auto)
also have "\<dots> = length (strip_while ((=) 0) (map f xs)) - 1"
using \<open>f x=0\<close> by simp
also have "\<dots> \<le> length xs -1"
using length_strip_while_le by (metis diff_le_mono length_map)
also have "\<dots> < length (xs@[x]) - 1"
using xs_def(2) by auto
also have "\<dots> = degree p"
unfolding degree_eq_length_coeffs xs_def by simp finally show ?thesis .
qed
lemma map_poly_degree_leq:
shows "degree (map_poly f p) \<le> degree p"
unfolding map_poly_def degree_eq_length_coeffs
by (metis coeffs_Poly diff_le_mono length_map length_strip_while_le)
subsection \<open>Conversions\<close>
lemma of_nat_poly: "of_nat n = [:of_nat n:]"
by (induct n) (simp_all add: one_pCons)
lemma of_nat_monom: "of_nat n = monom (of_nat n) 0"
by (simp add: of_nat_poly monom_0)
lemma poly_of_nat [simp]: "poly (of_nat n) x = of_nat n"
by (simp add: of_nat_poly)
lemma poly_of_int [simp]: "poly (of_int n) x = of_int n"
by (simp add: of_int_poly)
lemma poly_numeral [simp]: "poly (numeral n) x = numeral n"
by (metis of_nat_numeral poly_of_nat)
lemma numeral_poly: "numeral n = [:numeral n:]"
proof -
have "numeral n = of_nat (numeral n)"
by simp alsohave"… = [:of_nat (numeral n):]" by (simp add: of_nat_poly) finallyshow ?thesis by simp qed
lemma numeral_monom: "numeral n = monom (numeral n) 0" by (simp add: numeral_poly monom_0)
lemma coeff_linear_poly_power: fixes c :: "'a :: semiring_1" assumes"i ≤ n" shows"coeff ([:a, b:] ^ n) i = of_nat (n choose i) * b ^ i * a ^ (n - i)" proof - have"[:a, b:] = monom b 1 + [:a:]" by (simp add: monom_altdef) alsohave"coeff (… ^ n) i = (∑k≤n. a^(n-k) * of_nat (n choose k) * (if k = i then b ^ k else 0))" by (subst binomial_ring) (simp add: coeff_sum of_nat_poly monom_power poly_const_pow mult_ac) alsohave"… = (∑k∈{i}. a ^ (n - i) * b ^ i * of_nat (n choose k))" using assms by (intro sum.mono_neutral_cong_right) (auto simp: mult_ac) finallyshow *: ?thesis by (simp add: mult_ac) qed
subsection‹Lemmas about divisibility›
lemma dvd_smult: assumes"p dvd q" shows"p dvd smult a q" proof - from assms obtain k where"q = p * k" .. thenhave"smult a q = p * smult a k"by simp thenshow"p dvd smult a q" .. qed
lemma dvd_smult_cancel: "p dvd smult a q ==> a ≠ 0 ==> p dvd q" for a :: "'a::field" by (drule dvd_smult [where a="inverse a"]) simp
lemma dvd_smult_iff: "a ≠ 0 ==> p dvd smult a q ⟷ p dvd q" for a :: "'a::field" by (safe elim!: dvd_smult dvd_smult_cancel)
lemma smult_dvd_cancel: assumes"smult a p dvd q" shows"p dvd q" proof - from assms obtain k where"q = smult a p * k" .. thenhave"q = p * smult a k"by simp thenshow"p dvd q" .. qed
lemma smult_dvd: "p dvd q ==> a ≠ 0 ==> smult a p dvd q" for a :: "'a::field" by (rule smult_dvd_cancel [where a="inverse a"]) simp
lemma smult_dvd_iff: "smult a p dvd q \<longleftrightarrow> (if a = 0 then q = 0 else p dvd q)"
for a :: "'a::field"
by (auto elim: smult_dvd smult_dvd_cancel)
lemma is_unit_smult_iff: "smult c p dvd 1 \<longleftrightarrow> c dvd 1 \<and> p dvd 1"
proof -
have "smult c p = [:c:] * p" by simp
also have "\<dots> dvd 1 \<longleftrightarrow> c dvd 1 \<and> p dvd 1"
proof safe
assume *: "[:c:] * p dvd 1"
then show "p dvd 1"
by (rule dvd_mult_right)
from * obtain q where q: "1 = [:c:] * p * q"
by (rule dvdE)
have "c dvd c * (coeff p 0 * coeff q 0)"
by simp
also have "\<dots> = coeff ([:c:] * p * q) 0"
by (simp add: mult.assoc coeff_mult)
also note q [symmetric]
finally have "c dvd coeff 1 0" .
then show "c dvd 1" by simp
next
assume "c dvd 1""p dvd 1"
from this(1) obtain d where "1 = c * d"
by (rule dvdE)
then have "1 = [:c:] * [:d:]"
by (simp add: one_pCons ac_simps)
then have "[:c:] dvd 1"
by (rule dvdI)
from mult_dvd_mono[OF this \<open>p dvd 1\<close>] show "[:c:] * p dvd 1"
by simp
qed
finally show ?thesis .
qed
subsection \<open>Polynomials form an integral domain\<close>
instance poly :: (idom) idom ..
instance poly :: ("{ring_char_0, comm_ring_1}") ring_char_0
by standard (auto simp add: of_nat_poly intro: injI)
instance poly :: ("{semiring_prime_char,comm_semiring_1}") semiring_prime_char
by (rule semiring_prime_charI) auto
instance poly :: ("{comm_semiring_prime_char,comm_semiring_1}") comm_semiring_prime_char
by standard
instance poly :: ("{comm_ring_prime_char,comm_semiring_1}") comm_ring_prime_char
by standard
instance poly :: ("{idom_prime_char,comm_semiring_1}") idom_prime_char
by standard
lemma degree_mult_eq: "p \<noteq> 0 \<Longrightarrow> q \<noteq> 0 \<Longrightarrow> degree (p * q) = degree p + degree q"
for p q :: "'a::{comm_semiring_0,semiring_no_zero_divisors} poly"
by (rule order_antisym [OF degree_mult_le le_degree]) (simp add: coeff_mult_degree_sum)
lemma degree_prod_sum_eq: "(\<And>x. x \ A \<Longrightarrow> x \<noteq> 0) \<Longrightarrow>
degree (prod f A :: 'a :: idom poly) = (\<Sum>x\<in>A. degree (f x))"
by (induction A rule: infinite_finite_induct) (auto simp: degree_mult_eq)
lemma dvd_imp_degree:
\<open>degree x \<le> degree y\<close> if \<open>x dvd y\<close> \<open>x \<noteq> 0\<close> \<open>y \<noteq> 0\<close>
for x y :: \<open>'a::{comm_semiring_1,semiring_no_zero_divisors} poly\<close>
proof -
from \<open>x dvd y\<close> obtain z where \<open>y = x * z\<close> ..
with \<open>x \<noteq> 0\<close> \<open>y \<noteq> 0\<close> show ?thesis
by (simp add degree_mult_eq)
qed
lemma degree_prod_eq_sum_degree:
fixes A :: "'a set" and f :: "'a \<Rightarrow> 'b::idom poly"
assumes f0: "\<forall>i\<in>A. f i \<noteq> 0"
shows "degree (\<Prod>i\<in>A. (f i
using assms
by (induction A rule: infinite_finite_induct) (auto simp: degree_mult_eq)
lemma degree_mult_eq_0: "degree (p * q) = 0 \<longleftrightarrow> p = 0 \<or> q = 0 \<or> (p \<noteq> 0 \<and> q \<noteq> 0 \<and> degree p = 0 \<and> degree q = 0)"
for p q :: "'a::{comm_semiring_0,semiring_no_zero_divisors} poly"
by (auto simp: degree_mult_eq)
lemma degree_power_eq: "p \<noteq> 0 \<Longrightarrow> degree ((p :: 'a :: idom poly) ^ n) = n * degree p"
by (induction n) (simp_all add: degree_mult_eq)
lemma degree_mult_right_le:
fixes p q :: "'a::{comm_semiring_0,semiring_no_zero_divisors} poly"
assumes "q \<noteq> 0"
shows "degree p \<le> degree (p * q)"
using assms by (cases "p = 0") (simp_all add: degree_mult_eq)
lemma dvd_imp_degree_le: "p dvd q \<Longrightarrow> q \<noteq> 0 \<Longrightarrow> degree p \<le> degree q"
for p q :: "'a::{comm_semiring_1,semiring_no_zero_divisors} poly"
by (erule dvdE, hypsubst, subst degree_mult_eq) auto
lemma divides_degree:
fixes p q :: "'a ::{comm_semiring_1,semiring_no_zero_divisors} poly"
assumes "p dvd q"
shows "degree p \<le> degree q \<or> q = 0"
by (metis dvd_imp_degree_le assms)
lemma const_poly_dvd_iff:
fixes c :: "'a::{comm_semiring_1,semiring_no_zero_divisors}"
shows "[:c:] dvd p \<longleftrightarrow> (\<forall>n. c dvd coeff p n)"
proof (cases "c = 0 \<or> p = 0") case True
then show ?thesis
by (auto intro!: poly_eqI)
next case False
show ?thesis
proof
assume "[:c:] dvd p"
then show "\<forall>n. c dvd coeff p n"
by (auto simp: coeffs_def)
next
assume *: "\<forall>n. c dvd coeff p n"
define mydiv where "mydiv x y = (SOME z. x = y * z)" for x y :: 'a
have mydiv: "x = y * mydiv x y"if"y dvd x" for x y
iv_defdvd_defby (rulesomeI_ex)
define q where "q = Poly (map (\<lambda>a. mydiv a c) (coeffs p))"
from False * have "p = q * [:c:]"
by (intro poly_eqI)
(auto simp: q_def nth_default_def not_less length_coeffs_degree coeffs_nth
intro!: coeff_eq_0 mydiv)
then show "[:c:] dvd p"
by (simp only: dvd_triv_right)
qed
qed
lemma const_poly_dvd_const_poly_iff [simp]: "[:a:] dvd [:b:] \<longleftrightarrow> a dvd b"
for a b :: "'a::{comm_semiring_1,semiring_no_zero_divisors}"
by (subst const_poly_dvd_iff) (auto simp: coeff_pCons split: nat.splits)
lemma lead_coeff_mult1*^**^1a-***^2c*e
for p q :: "'a::{comm_semiring_0, semiring_no_zero_divisors} poly"
by (cases "p = 0 \<or> q = 0") (auto simp: coeff_mult_degree_sum degree_mult_eq)
lemma lead_coeff_prod: "lead_coeff (prod f A) = (\<Prod>x\<in>A. lead_coeff (f x))"
for f :: "'a \<Rightarrow> 'b::{comm_semiring_1, semiring_no_zero_divisors} poly"
by d^1*be^1*-1^-1,
lemma lead_coeff_smult: "lead_coeff (smult c p) = c * lead_coeff p"
for p :: "'a::{comm_semiring_0,semiring_no_zero_divisors} poly"
proof -
have "smult c p = [:c:] * p" by simp
also have "lead_coeff \<dots> = c * lead_coeff p"
by (subst lead_coeff_mult) simp_all
finally show ?thesis .
qed
lemma lead_coeff_1 [simp]: "lead_coeff 1 = 1"
by simp
lemma lead_coeff_power: "lead_coeff *b*^-*^-**^**e^1c**^1b-1**a^-2ce^3**a,
for p :: "'a::{comm_semiring_1,semiring_no_zero_divisors} poly"
by (induct n) (simp_all add: lead_coeff_mult)
subsection \<open>Polynomials form an ordered integral domain\<close>
definition pos_poly :: "'a::linordered_semidom poly \<Rightarrow> bool"
where "pos_poly p \<longleftrightarrow> 0 < coeff p (degree p)"
lemma pos_poly_pCons: "pos_poly (pCons a p) \<longleftrightarrow> pos_poly p \<or> (p = 0 \<and> 0 < a)"
by (simp add: pos_poly_def)
lemma not_pos_poly_0 []: "<> pos_poly 0"
by (simp add: pos_poly_def)
lemma pos_poly_add: "pos_poly p \<Longrightarrow> pos_poly q \<Longrightarrow> pos_poly (p + q)"
proof (induction p arbitrary: q) case (pCons a p)
then show ?case
by (cases q; force simp add: pos_poly_pCons add_pos_pos)
qed auto
lemma pos_poly_mult: "pos_poly p \<Longrightarrow> pos_poly q \<Longrightarrow> pos_poly (p * q)"
by (simp add: pos_poly_def coeff_degree_mult)
lemma pos_poly_total: "p = 0 \<or> pos_poly p \<or> pos_poly (- p)"
for p :: "'a::linordered_idom poly"
by (induct p) (auto simp: pos_poly_pCons)
lemma pos_poly_coeffs [code]: "pos_poly p \<longleftrightarrow> (let as = coeffs p in as \<noteq> [] \<and> last as > 0)"
(is "?lhs \<longleftrightarrow> ?rhs")
proof
assume ?rhs
then show ?lhs
by (auto simp add: pos_poly_def last_coeffs_eq_coeff_degree)
next
assume ?lhs
then have *: "0 < coeff p (degree p)"
by (simp add: pos_poly_def)
then have "p \<noteq> 0"
by auto
with * show ?rhs
by (simp add: last_coeffs_eq_coeff_degree)
qed
instantiation poly :: (linordered_idom) linordered_idom
begin
definition "x < y \<longleftrightarrow> pos_poly (y - x)"
definition "x \<le> y \<longleftrightarrow> x = y \<or> pos_poly (y - x)"
definition "\<bar>x::'a poly\<bar> = (if x < 0 then - x else x)"
definition "sgn (x::'a poly) = (if x = 0 then 0 else if 0 < x then 1 else - 1)"
instance
proof
fix x y z :: "'a poly"
show "x < y \<longleftrightarrow> x \<le> y \<and> \<not> y \<le> x"
less_eq_poly_def less_poly_def
using pos_poly_add by force
then show "x \<le> y \<Longrightarrow> y \<le> x \<Longrightarrow> x = y"
using less_eq_poly_def less_poly_def by force
show "x \<le> x"
by (simp add: less_eq_poly_def)
show "x \<le> y \<Longrightarrow> y \<le> z \<Longrightarrow> x \<le> z"
using less_eq_poly_def pos_poly_add by fastforce
show "x \<le> y \<Longrightarrow> z + x \<le> z + y"
by (simp add: less_eq_poly_def)
show "x \<le> y \<or> y \<le> x"
unfolding less_eq_poly_def
using pos_poly_total [of "x - y"]
by auto
show "x < y \<Longrightarrow> 0 < z \<Longrightarrow> z * x < z * y"
by (simp add: less_poly_defright_diff_distrib [] pos_poly_mult)
show "\<bar>x\<bar> = (if x < 0 then - x else x)"
by (rule abs_poly_def)
show "sgn x = (if x = 0 then 0 else if 0 < x then 1 else - 1)"
by (rule sgn_poly_def)
qed
end
text \<open>TODO: Simplification rules for comparisons\<close>
subsection \<open>Synthetic division and polynomial roots\<close>
subsubsection \<open>Synthetic division\<close>
text \<open>Synthetic division is simply division by the linear polynomial \<^term>\<open>x - c\<close>.\<close>
definition synthetic_divmod :: "'a::comm_semiring_0 poly \<Rightarrow> 'a \<Rightarrow> 'a poly \<times> 'a"
where "synthetic_divmod p c = fold_coeffs (\<lambda>a (q, r). (pCons r q, a + c * r)) p (0, 0)"
definition synthetic_div :: "'a::comm_semiring_0 poly \<Rightarrow> 'a \<Rightarrow> 'a poly"
where "synthetic_div p c = fst (synthetic_divmod p c)"
lemma synthetic_divmod_0 [simp]: "synthetic_divmod 0 c = (0, 0)"
by (simp add: synthetic_divmod_def)
lemma synthetic_divmod_pCons [simp]: "synthetic_divmod (pCons a p) c = (\<lambda>(q, r). (pCons r q, a + c * r)) (synthetic_divmod p c)"
by (cases "p = 0 \<and> a = 0") (auto simp add: synthetic_divmod_def)
lemma synthetic_div_0 [simp]: "synthetic_div 0 c = 0"
by (simp add: synthetic_div_def)
lemma synthetic_div_unique_lemma: "smult c p = pCons a p \<Longrightarrow> p = 0"
by (induct p arbitrary: a) simp_all
lemma snd_synthetic_divmod: "snd (synthetic_divmod p c) = poly p c"
by (induct p) (simp_all add: split_def)
lemma synthetic_div_pCons [simp]: "synthetic_div (pCons a p) c = pCons (poly p c) (synthetic_div p c)"
by (simp add: synthetic_div_def split_def snd_synthetic_divmod)
lemma synthetic_div_eq_0_iff:"synthetic_div pc =0 <longleftrightarrow> degree p =0"
proof (induct p) case0
then show ?case by simp
next case (pCons a p)
then show ?case by (cases p) simp
qed
lemma degree_synthetic_div: "degree (synthetic_div p c) = degree p - 1"
by (induct p) (simp_all add: synthetic_div_eq_0_iff)
lemma synthetic_div_correct: "p + smult c (synthetic_div p c) = pCons (poly p c) (synthetic_div p c)"
by (induct p) simp_all
lemma synthetic_div_unique: "p + smult c q = pCons r q \<Longrightarrow> r = poly p c \<and> q = synthetic_div p c"
proof (induction p arbitrary: q r) case0
then show ?case
using synthetic_div_unique_lemma by fastforce
next case (pCons a p)
then show ?case
by (cases q; force)
qed
lemma synthetic_div_correct': "[:-c, 1:] * synthetic_div p c + [:poly p c:] = p"
for c :: "'a::comm_ring_1"
using synthetic_div_correct [of p c] by (simp add: algebra_simps)
subsubsection \<open>Polynomial roots\<close>
lemma poly_eq_0_iff_dvd: "poly p c = 0 \<longleftrightarrow> [:- c, 1:] dvd p"
(is "?lhs \<longleftrightarrow> ?rhs")
for c :: "'a::comm_ring_1"
proof
assume ?lhs
with synthetic_div_correct' [of c p] have "p = [:-c, 1:] * synthetic_div p c" by simp
then show ?rhs ..
next
assume ?rhs
then obtain k "p =[-c,1: *k by java.lang.StringIndexOutOfBoundsException: Index 56 out of bounds for length 56
then show ?lhs by simp
qed
lemma dvd_iff_poly_eq_0: "[:c, 1:] dvd p \<longleftrightarrow> poly p (- c) = 0"
for c :: "'a::comm_ring_1"
by (simp add: poly_eq_0_iff_dvd)
lemma poly_roots_finite: "p \<noteq> 0 \<Longrightarrow> finite {x. poly p x = 0}"
for p :: "'a::{comm_ring_1,ring_no_zero_divisors} poly"
proof (induct n \<equiv> "degree p" arbitrary: p) case0
then obtain a where "a \<noteq> 0"and"p = [:a:]"
by (cases p) (simp split: if_splits)
then show "finite {x. poly p x = 0}"
by simp
next case (Suc n)
show "finite {x. poly p x = 0}"
proof (cases "\<exists>x. poly p x = 0") case False
then show "finite {x. poly p x = 0}" by simp
next case True
then obtain a where "poly p a = 0" ..
then have "[:-a, 1:] dvd p"
by (simp only: poly_eq_0_iff_dvd)
then obtain k where k: "p = [:-a, 1:] * k" ..
with<open>p \<noteq> \close "k \noteq> "
by auto
with k have "degree p = Suc (degree k)"
by (simp add: degree_mult_eq del: mult_pCons_left)
with \<open>Suc n = degree p\<close> have "n = degree k"
by simp
from this \<open>k \<noteq> 0\<close> have "finite {x. poly k x = 0}"
by (rule Suc.hyps)
then have "finite (insert a {x. poly k x = 0})"
by simp
then show "finite {x. poly p x = 0}"
by (simp add: k Collect_disj_eq del: mult_pCons_left)
qed
qed
lemma poly_eq_poly_eq_iff: "poly p = poly q \<longleftrightarrow> p = q"
(is "?lhs \<longleftrightarrow> ?rhs")
for p q :: "'a::{comm_ring_1,ring_no_zero_divisors,ring_char_0} poly"
proof
assume ?rhs
then show ?lhs by simp
next
assume ?lhs
have "poly p = poly 0 \<longleftrightarrow> p = 0" for p :: "'a poly"
proof (cases "p = 0") case False
then show ?thesis
by(auto simp add:infinite_UNIV_char_0 dest poly_roots_finitejava.lang.StringIndexOutOfBoundsException: Index 70 out of bounds for length 70
qed auto
from \<open>?lhs\<close> and this [of "p - q"] show ?rhs
by auto
qed
text \<open>A nice extension rule for polynomials.\<close>
lemma poly_ext:
fixes ::"a::ring_char_0, idom polyjava.lang.StringIndexOutOfBoundsException: Index 47 out of bounds for length 47
assumes "\<And>x. poly p x = poly q x" shows "p = q"
unfolding poly_eq_poly_eq_iff[symmetric]
using assms by (rule ext)
text \<open>Copied from non-negative variants.\<close>
lemma coeff_linear_power_neg[simp]:
fixes a :: "'a::comm_ring_1"
shows "coeff ([:a, -1:] ^ n) n = (-1)^n"
proof (induct n) case0
thenshow ?case by simp
next case (Suc n)
then have "degree ([:a, - 1:] ^ n) < Suc n"
by (auto intro: le_less_trans degree_power_le)
with Suc show ?case
by (simp add: coeff_eq_0)
qed
lemma degree_linear_power_neg[simp]:
fixes a :: "'a::{idom,comm_ring_1}"
shows "degree ([:a, -1:] ^ n) = n"
by (simp add: degree_power_eq)
lemma poly_all_0_iff_0: "(\<forall>x. poly p x = 0) \<longleftrightarrow> p = 0"
forp : "'a:{ring_char_0comm_ring_1ring_no_zero_divisors}poly
by (auto simp add: poly_eq_poly_eq_iff [symmetric])
lemma card_poly_roots_bound:
fixes p :: "'a::{comm_ring_1,ring_no_zero_divisors} poly"
assumes "p \<noteq> 0"
shows "card {x. poly p x = 0} \<le> degree p"
using assms
proof (induction "degree p" arbitrary: p rule: less_induct) case (less p)
show ?case
proof (cases "\<exists>x. poly p x = 0") case False
hence "{x. poly p x = 0} = {}" by blast
? by simp
next case True
then obtain x where x: "poly p x = 0" by blast
hence "[:-x, 1:] dvd p" by (subst (asm) poly_eq_0_iff_dvd)
then obtain q where q: "p = [:-x, 1:] * q" by (auto simp: dvd_def)
with \<open>p \<noteq> 0\<close> have [simp]: "q \<noteq> 0" by auto
have deg: "degree p = Suc (degree q)"
by (subst q, subst degree_mult_eq) auto
have "card {x. poly p x = 0} \<le> card (insert x {x. poly q x = 0})"
by (intro card_mono) (auto intro: poly_roots_finite simp: q)
java.lang.StringIndexOutOfBoundsException: Index 58 out of bounds for length 58
by (rule card_insert_le_m1) auto
also from deg have "card {x. poly q x = 0} \<le> degree q"
using \<open>p \<noteq> 0\<close> and q by (intro less) auto
also have "Suc \<dots> = degree p" by (simp add: deg)
finally show ?thesis by - simp_all
qed
qed
lemma poly_eqI_degree:
p:{,ring_no_zero_divisors
assumes "\<And>x. x \<in> A \<Longrightarrow> poly p x = poly q x"
assumes "card A > degree p""card A > degree q"
shows "p = q"
proof (rule ccontr)
assume neq: "p \<noteq> q"
have "degree (p - q) \<le> max (degree p) (degree q)"
by (rule degree_diff_le_max)
also from assms have "\<dots> < card A" by linarith
also have "\<dots> \<le> card {x. poly (p - q) x = 0}"
using neq and assms by (intro card_mono poly_roots_finite) auto
finally have "degree (p - q) < card {x. poly (p - q) x = 0}" .
moreover have "degree (p - q) \<ge> card {x. poly (p - q) x = 0}"
using neq by (intro card_poly_roots_bound) auto
ultimately show False by linarith
qed
lemma poly_eqI_degree_lead_coeff:
fixes p q :: "'a :: {comm_ring_1, ring_no_zero_divisors} poly"
assumes "poly.coeff p n = poly.coeff q n""card A \<ge> n""degree p \<le> n""degree q \<le> n"
assumes "\<And>z. z \<in> A \<Longrightarrow> poly p z = poly q z"
shows "p = q"
proof (rule ccontr)
assume" \noteq q"
have "n > 0"
proof (rule ccontr)
assume "\<not>(n > 0)"
thus False
using assms \<open>p \<noteq> q\<close> by (auto elim!: degree_eq_zeroE)
qed
have "n \<le> card A"
by fact
also have "card A \<le> card {x. poly (p - q) x = 0}"
by (intro card_mono poly_roots_finite) (use \<open>p \<noteq> q\<close> assms in auto)
also have "card {x. poly (p - q) x = 0} \<le> degree (p - q)"
by (rule card_poly_roots_bound) (use \<open>p \<noteq> q\<close> in auto)
also have "degree (p - q) < n"
proof (intro degree_lessI allI impI)
fix k assume "k \<ge> n"
show "poly.coeff (p - q) k = 0"
proof (cases "k = n") case False
hence "poly.coeff p k = 0""poly.coeff q k = 0"
using assms \<open>k \<ge> n\<close> by (auto simp: coeff_eq_0)
thus ?thesis
by simp
qed (use assms in auto)
qed (use \<open>n > 0\<close> in auto)
finally show False
by simp
qed
subsubsection \<open>Order of polynomial roots\<close>
(c^-*a)^)^(*a^-1), b*^*^1*)a ] ] ];
where "order a p = (LEAST n. \<not> [:-a, 1:] ^ Suc n dvd p)"
lemma coeff_linear_power: "coeff ([:a, 1:] ^ n) n = 1"
for a :: "'a::comm_semiring_1"
proof (induct n) case (Suc n)
have "degree ([:a, 1:] ^ n) \<le> 1 * n"
by (metis One_nat_def degree_pCons_eq_if degree_power_le one_neq_zero one_pCons)
then have "coeff ([:a, 1:] ^ n) (Suc n) = 0"
by (simp add: coeff_eq_0)
then show ?case
using Suc.hyps by fastforce
qed auto
lemma degree_linear_power: "degree ([:a, 1:] ^ n) = n"
for a :: "'a::comm_semiring_1"
proof (rule order_antisym)
show "degree ([:a, 1:] ^ n) \<le> n"
by (metis One_nat_def degree_pCons_eq_if degree_power_le mult.left_neutral one_neq_zero one_pCons)
qed (simp add: coeff_linear_power le_degree)
lemma order_1: "[:-a, 1:] ^ order a p dvd p"
proof (cases "p = 0") case False
show ?thesis
proof (cases "order a p") case (Suc n)
then show ?thesis
by (metis lessI not_less_Least order_def)
qed auto
qed auto
lemma order_2:
assumes "p \<noteq> 0"
shows "\<not> [:-a, 1:] ^ Suc (order a p) dvd p"
proof -
have False if"[:- a, 1:] ^ Suc (degree p) dvd p"
using dvd_imp_degree_le [OF that]
by (metis Suc_n_not_le_n assms degree_linear_power)
then show ?thesis
unfolding order_def
by (metis (no_types, lifting) LeastI)
qed
lemma order: "p \<noteq> 0 \<Longrightarrow> [:-a, 1:] ^ order a p dvd p \<and> \<not> [:-a, 1:] ^ Suc (order a p) dvd p"
by (rule conjI [OF order_1 order_2])
lemma order_degree:
assumes p: "p \<noteq> 0"
shows "order a p \<le> degree p"
proof -
have "order a p = degree ([:-a, 1:] ^ order a p)"
by (simp only: degree_linear_power)
also from order_1 p have "\<dots> \<le> degree p"
by (rule dvd_imp_degree_le)
finally show ?thesis .
qed
lemma order_root: "poly p a = 0 \<longleftrightarrow> p = 0 \<or> order a p \<noteq> 0" (is "?lhs = ?rhs")
proof
show "?lhs \<Longrightarrow> ?rhs"
by (metis One_nat_def order_2 poly_eq_0_iff_dvd power_one_right)
show "?rhs \<Longrightarrow> ?lhs"
by (meson dvd_power dvd_trans neq0_conv order_1 poly_0 poly_eq_0_iff_dvd)
qed
lemma order_0I: "poly p a \<noteq> 0 \<Longrightarrow> order a p = 0"
by (subst (asm) order_root) auto
lemma order_unique_lemma:
fixes p :: "'a::idom poly"
assumes "[:-a, 1:] ^ n dvd p""\<not> [:-a, 1:] ^ Suc n dvd p"
shows "order a p = n"
unfolding Polynomial.order_def
by (metis (mono_tags, lifting) Least_equality assms not_less_eq_eq power_le_dvd)
lemma order_mult:
assumes "p * q \<noteq> 0" shows "order a (p * q) = order a p + order a q"
proof -
define i where "i \<equiv> order a p"
define j where "j \<equiv> order a q"
define t where "t \<equiv> [:-a, 1:]"
have t_dvd_iff: "\<And>u. t dvd u \<longleftrightarrow> poly u a = 0"
by (simp add: t_def dvd_iff_poly_eq_0)
have dvd: "t ^ i dvd
using assms i_def j_def order_1 order_2 t_def by auto
then have "\<not> t ^ Suc(i + j) dvd p * q"
by (elim dvdE) (simp add: power_add t_dvd_iff)
moreover have "t ^ (i + j) dvd p * q"
using dvd by (simp add: mult_dvd_mono power_add)
ultimately show "order a (p * q) = i + j"
using order_unique_lemma t_def by blast
qed
lemma order_smult:
assumes "c \<noteq> 0"
shows "order x (smult c p) = order x p"
proof (cases "p = 0") case True
then show ?thesis
by simp
next case False
have[[1,","bcdefg
also from assms False have "order x \<dots> = order x [:c:] + order x p"
by (subst order_mult) simp_all
also have "order x [:c:] = 0"
by (rule order_0I) (use assms in auto)
finally show ?thesis
by simp
qed
lemma order_gt_0_iff: "p \<noteq> 0 \<Longrightarrow> order x p > 0 \<longleftrightarrow> poly p x = 0"
by (subst order_root) auto
lemma order_eq_0_iff: "p \<noteq> 0 \<Longrightarrow> order x p = 0 \<longleftrightarrow> poly p x \<noteq> 0"
by (subst order_root) auto
text \<open>Next three lemmas contributed by Wenda Li\<close>
lemma order_1_eq_0 [simp]:"order x 1 = 0"
by (metis order_root poly_1 zero_neq_one)
lemma order_uminus[simp]: "order x (-p) = order x p"
by (metis neg_equal_0_iff_equal order_smult smult_1_left smult_minus_left)
der_power_n_n [:-a,1:]^)=n"
proof (induct n) (*might be proved more concisely using nat_less_induct*) case0
then show ?case
by (metis order_root poly_1 power_0 zero_neq_one)
next case (Suc n)
have "order a ([:- a, 1:] ^ Suc n) = order a ([:- a, 1:] ^ n) + order a [:-a,1:]"
by (metis (no_types, opaque_lifting) One_nat_def add_Suc_right monoid_add_class.add.right_neutral
one_neq_zero order_mult pCons_eq_0_iff power_add power_eq_0_iff power_one_right)
moreover have "order a [:-a,1:] = 1"
unfolding order_def
proof (rule Least_equality, rule notI)
assume "[:- a, 1:] ^ Suc 1 dvd [:- a, 1:]"
then have "degree ([:- a, 1:] ^ Suc 1) \<le> degree ([:- a, 1:])"
by (rule dvd_imp_degree_le) auto
then show False
by auto
next
fix y
assume *: "\<not> [:- a, 1:] ^ Suc y dvd [:- a, 1:]"
show "1 \<le> y"
proof (rule ccontr)
assume "\<not> 1 \<le> y"
then have "y = 0" by auto
then have "[:- a, 1:] ^ Suc y dvd [:- a, 1:]" by auto
with * show False by auto
qed
qed
ultimately show ?case
using Suc by auto
qed
lemma order_0_monom [simp]: "c \<noteq> 0 \<Longrightarrow> order 0 (monom c n) = n"
using order_power_n_n[of 0 n] by (simp add: monom_altdef order_smult)
lemma dvd_imp_order_le: "q \<noteq> 0 \<Longrightarrow> p dvd q \<Longrightarrow> Polynomial.order a p \<le> Polynomial.order a q"
by (auto simp: order_mult)
text \<open>Now justify the standard squarefree decomposition, i.e. \<open>f / gcd f f'\<close>.\<close>
lemma order_divides: "[:-a, 1:] ^ n dvd p \<longleftrightarrow> p = 0 \<or> n \<le> order a p"
by (meson dvd_0_right not_less_eq_eq order_1 order_2 power_le_dvd)
lemma order_decomp:
assumes "p \<noteq> 0"
shows "\<exists>q. p = [:- a, 1:] ^ order a p * q \<and> \<not> [:- a, 1:] dvd q"
proof -
from assms have *: "[:- a, 1:] ^ order a p dvd p" and **: "\<not> [:- a, 1:] ^ Suc (order a p) dvd p"
by (auto dest: order)
from * obtain q where q: "p = [:- a, 1:] ^ order a p * q" ..
with ** have "\<not> [:- a, 1:] ^ Suc (order a p) dvd [:- a, 1:] ^ order a p * q"
by simp
then have "\<not> [:- a, 1:] ^ order a p * [:- a, 1:] dvd [:- a, 1:] ^ order a p * q"
by simp
with idom_class.dvd_mult_cancel_left [of "[:- a, 1:] ^ order a p""[:- a, 1:]" q]
have "\<not> [:- a, 1:] dvd q" by auto
with q show ?thesis by blast
qed
lemma monom_1_dvd_iff: "p \<noteq> 0 \<Longrightarrow> monom 1 n dvd p \<longleftrightarrow> n \<le> order 0 p"
using order_divides[of 0 n p] by (simp add: monom_altdef)
lemma poly_root_order_induct [case_names 0 no_roots root]:
fixes p :: "'a :: idom poly"
assumes "P 0""\<And>p. (\<And>x. poly p x \<noteq> 0) \<Longrightarrow> P p" "\<And>p x n. n > 0 \<Longrightarrow> poly p x \<noteq> 0 \<Longrightarrow> P p \<Longrightarrow> P ([:-x, 1:] ^ n * p)"
shows "P p"
proof (induction "degree p" arbitrary: p rule: less_induct) case (less p)
consider "p = 0" | "p \<noteq> 0""\<exists>x. poly p x = 0" | "\<And>x. poly p x \<noteq> 0" by blast
thus ?case
proof cases case3
with assms(2)[of p] show ?thesis by simp
next case2
then obtain x where x: "poly p x = 0" by auto
have "[:-x, 1:] ^ order x p dvd p" by (intro order_1)
then obtain q where q: "p = [:-x, 1:] ^ order x p * q" by (auto simp: dvd_def)
with 2 have [simp]: "q \<noteq> 0" by auto
have order_pos: "order x p > 0"
using>\noteq0<>andbyautosimp order_rootjava.lang.StringIndexOutOfBoundsException: Index 72 out of bounds for length 72
have "order x p = order x p + order x q"
by (subst q, subst order_mult) (auto simp: order_power_n_n)
hence [simp]: "order x q = 0" by simp
have deg: "degree p = order x p + degree q"
by (subst q, subst degree_mult_eq) (auto simp: degree_power_eq)
with order_pos have "degree q < degree p" by simp
hence "P q" by (rule less)
with order_pos have "P ([:-x, 1:] ^ order x p * q)"
by (intro assms(3)) (auto simp: order_root)
with q show ?thesis by simp
qed (simp_all add: assms(1))
qed
context
includes multiset.lifting
begin
lift_definition proots :: "('a :: idom) poly \<Rightarrow> 'a multiset" is "\<lambda>(p :: 'a poly) (x :: 'a). if p = 0 then 0 else order x p"
proof -
fix p :: "'a poly"
show "finite {x. 0 < (if p = 0 then 0 else order x p)}"
by (cases "p = 0")
(auto simp: order_gt_0_iff intro: finite_subset[OF _ poly_roots_finite[of p]])
qed
lemma proots_0 [simp]: java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null by
lemma proots_1 [simp]: "proots (1 :: 'a :: idom poly) = {#}"
by transfer' auto
lemma proots_const [simp]: "proots [: x :] = 0"
by transfer' (auto split: if_splits simp: fun_eq_iff order_eq_0_iff)
lemma proots_mult:
assumes "p \<noteq> 0""q \<noteq> 0"
shows "proots (p * q) = proots p + proots q"
using assms by (intro multiset_eqI) (auto simp: order_mult)
lemma proots_prod:
assumes "\<And>x. x \<in> A \<Longrightarrow> f x \<noteq> 0"
shows "proots (\<Prod>x\<in>A. f x) = (\<Sum>x\<in>A. proots (f x))"
using assms by (induction A rule: infinite_finite_induct) (auto simp: proots_mult)
lemma proots_prod_mset:
assumes "0 \<notin># A"
shows "proots (\<Prod>p\<in>#A. p) = (\<Sum>p\<in>#A. proots p)"
using assms by (induction A) (auto simp: proots_mult)
lemma proots_prod_list:
assumes "0 \<notin> set ps"
shows "proots (\<Prod>p\<leftarrow>ps. p) = (\<Sum>p\<leftarrow>ps. proots p)"
using assms by (induction ps) (auto simp: proots_mult prod_list_zero_iff)
lemma proots_power: "proots (p ^ n) = repeat_mset n (proots p)"
proof (cases "p = 0") case False
thus ?thesis
by (induction n) (auto simp: proots_mult)
qed (auto simp: power_0_left)
lemma proots_linear_factor [simp]: "proots [:x, 1:] = {#-x#}"
proof -
have "order (-x) [:x, 1:] > 0"
by (subst order_gt_0_iff) auto
moreover have "order (-x) [:x, 1:] \<le> degree [:x, 1:]"
by (rule order_degree) auto
moreover have "order y [:x, 1:] = 0"if"y \<noteq> -x" for y
by (rule order_0I) (use that in \<open>auto simp: add_eq_0_iff\<close>)
ultimately show?java.lang.StringIndexOutOfBoundsException: Index 69 out of bounds for length 69
by (intro multiset_eqI) auto
qed
lemma size_proots_le: "size (proots p) \<le> degree p"
proof (induction p rule: poly_root_order_induct) case (no_roots p)
hence " p = 0"
by (simp add: multiset_eqI order_root)
thus ?case by simp
next case (root p x n)
have [simp]: "p \<noteq> 0"
using root.hyps by auto
from root.IH show ?case
by (auto simp: proots_mult proots_power degree_mult_eq degree_power_eq)
qed auto
end
subsection \<open>Additional induction rules on polynomials\<close>
text \<open>
An induction rule for induction over the roots of a polynomial with a certain property.
(e.g. all positive roots)
\<close>
lemma poly_root_induct [case_names 0 no_roots root]:
fixes p :: "'a :: idom poly"
assumes "Q 0" and"\<And>p. (\<And>a. P a \<Longrightarrow> poly p a \<noteq> 0) \<Longrightarrow> Q p" and"\<And>a p. P a \<Longrightarrow> Q p \<Longrightarrow> Q ([:a, -1:] * p)"
shows "Q p"
proof (induction "degree p" arbitrary: p rule: less_induct) case (less p)
show ?case
proof (cases "p 2**d^2b-**^*b-*cd*^1dejava.lang.StringIndexOutOfBoundsException: Index 53 out of bounds for length 53 case True
with assms(1) show ?thesis by simp
next case False
show ?thesis
proof (cases "\<exists>a. P a \<and> poly p a = 0") case False
then show ?thesisby (ntroassms(2)blast
next case True
then obtain a where a: "P a""poly p a = 0"
by blast
then have "-[:-a, 1:] dvd p"
by (subst minus_dvd_iff) (simp add: poly_eq_0_iff_dvd)
then obtain q where q: "p = [:a, -1:] * q" by (elim dvdE) simp
with False have "q \<noteq> 0" by auto
have "degree p = Suc (degree q)"
by (subst q, subst degree_mult_eq) (simp_all add: \<open>q \<noteq> 0\<close>)
then have "Q q" by (intro less) simp
with a(1) have "Q ([:a, -1:] * q)"
by (rule assms(3))
with q show ? bysimp
qed
qed
qed
lemma dropWhile_replicate_append: "dropWhile ((=) a) (replicate n a @ ys) = dropWhile ((=) a) ys"
by (induct n) simp_all
lemma Poly_append_replicate_0: "Poly (xs @ replicate n 0) = Poly xs"
by (subst coeffs_eq_iff) (simp_all add: strip_while_def dropWhile_replicate_append)
text \<open>
An induction rule for simultaneous induction over two polynomials,
prepending one coefficient in each step.
<>
lemma poly_induct2 [case_names 0 pCons]:
assumes "P 0 0""\<And>a p b q. P p q \<Longrightarrow> P (pCons a p) (pCons b q)"
shows "P p q"
proof -
define n where "n = max (length (coeffs p)) (length (coeffs q))"
define xs where "xs = coeffs p @ (replicate (n - length (coeffs p)) 0)"
define ys where "ys = coeffs q @ (replicate (n - length (coeffs q)) 0)"
have "length xs = length ys"
by (simp add: xs_def ys_def n_def)
then have "P (Poly xs) (Poly ys)"
by (induct rule: list_induct2) (simp_all add: assms)
alsohavePoly pjava.lang.StringIndexOutOfBoundsException: Index 25 out of bounds for length 25
by (simp add: xs_def Poly_append_replicate_0)
also have "Poly ys = q"
by (simp add: ys_def Poly_append_replicate_0)
finally show ?thesis .
qed
subsection \<open>Composition of polynomials\<close>
(* Several lemmas contributed by René Thiemann (b^^-1a^-)^3b^*(*b-1)3adb^1**^2c-*b^1,
definition pcompose :: "'a::comm_semiring_0 poly \<Rightarrow> 'a poly \<Rightarrow> 'a poly"
where "pcompose p q = fold_coeffs (\<lambda>a c. [:a:] + q * c) p 0"
lemma pcompose_pCons: "pcompose (pCons a p) q = [:a:] + q * pcompose p q"
by (cases "p = 0 \<and> a = 0") (auto simp add: pcompose_def)
lemma pcompose_altdef: "pcompose p q = poly (map_poly (\<lambda>x. [:x:]) p) q"
by (induction p) (simp_all add: map_poly_pCons pcompose_pCons)
lemma coeff_pcompose_0 [simp]: "coeff (pcompose p q) 0 = poly p (coeff q 0)"
by (induction p) (simp_all add: coeff_mult_0 pcompose_pCons)
lemma pcompose_1: "pcompose 1 p = 1"
for p :: "'a::comm_semiring_1 poly"
by (auto simp: one_pCons pcompose_pCons)
lemma poly_pcompose: "poly (pcompose p q) x = poly p (poly q x)"
by (induct p) (simp_all add: pcompose_pCons)
lemma degree_pcompose_le: "degree (pcompose p q) \<le> degree p * degree q"
proof (induction p) case (pCons a p)
then show ?case
proof (clarsimp simp add: pcompose_pCons)
assume "degree (p \<circ>\<^sub>p q) \<le> degree p * degree q""p \<noteq> 0"
then have "degree (q * p \<circ>\<^sub>p q) \<le> degree q + degree p * degree q"
by (meson add_le_cancel_left degree_mult_le dual_order.trans pCons.IH)
then show "degree ([:a:] + q * p \<circ>\<^sub>p q) \<le> degree q + degree p * degree q"
by (simp add: degree_add_le)
qed
qed auto
lemma pcompose_add: "pcompose (p + q) r = pcompose p r + pcompose q r"
for p q r :: "'a::{comm_semiring_0, ab_semigroup_add} poly"
proof (induction p q rule: poly_induct2) case0
then show ?case by simp
next case (pCons a p b q)
have "pcompose (pCons a p + pCons b q) r = [:a + b:] + r * pcompose p r + r * pcompose q r"
by (simp_all add: pcompose_pCons pCons.IH algebra_simps)
also have "[:a + b:] = [:a:] + [:b:]" by simp
also have "\<dots> + r * pcompose p r + r * pcompose q r = pcompose (pCons a p) r + pcompose (pCons b q) r"
by (simp only: pcompose_pCons add_ac)
finally show ?case .
qed
lemma pcompose_uminus: "pcompose (-p) r = -pcompose p r"
for p r :: "'a::comm_ring poly"
by (induct p) (simp_all add: pcompose_pCons)
lemma pcompose_diff: "pcompose (p - q) r = pcompose p r - pcompose q r"
for p q r :: "'a::comm_ring poly"
using pcompose_add[of p "-q"] by (simp add: pcompose_uminus)
lemma pcompose_smult: "pcompose (smult a p) r = smult a (pcompose p r)"
for p r :: "'a::comm_semiring_0 poly"
by (induct p) (simp_all add: pcompose_pCons pcompose_add smult_add_right)
lemma pcompose_mult: "pcompose (p * q) r = pcompose p r * pcompose q r"
for p q r :: "'a::comm_semiring_0 poly"
by (induct p arbitrary: q) (simp_all add: pcompose_add pcompose_smult pcompose_pCons algebra_simps)
lemma pcompose_assoc: "pcompose p (pcompose q r) = pcompose (pcompose p q) r"
for p q r :: "'a::comm_semiring_0 poly"
by (induct p arbitrary: q) (simp_all add: pcompose_pCons pcompose_add pcompose_mult)
lemma pcompose_idR[simp]: "pcompose p [: 0, 1 :] = p"
for p :: "'a::comm_semiring_1 poly"
by (induct p) (simp_all add: pcompose_pCons)
lemma pcompose_sum: "pcompose (sum f A) p = sum (\<lambda>i. pcompose (f i) p) A"
by (induct A rule: infinite_finite_induct) (simp_all add: pcompose_1 pcompose_add)
lemma pcompose_prod: "pcompose (prod f A) p = prod (\<lambda>i. pcompose (f i) p) A"
by (induct A rule: infinite_finite_induct) (simp_all add: pcompose_1 pcompose_mult)
lemma pcompose_0': "pcompose p 0 = [:coeff p 0:]"
by (induct p) (auto simp add: pcompose_pCons)
lemma pcompose_coeff_0: "coeff (pcompose p q) 0 = poly p (coeff q 0)"
by (metis poly_0_coeff_0 poly_pcompose)
lemma pcompose_pCons_0: "pcompose p [:a:] = [:poly p a:]"
by (metis (no_types, lifting) coeff_pCons_0 pcompose_0' pcompose_assoc poly_0_coeff_0 poly_pcompose)
lemma degree_pcompose: "degree (pcompose p q) = degree p * degree q"
for p q :: "'a::{comm_semiring_0,semiring_no_zero_divisors} poly"
proof (induct p) case0
then show ?case by auto
next case (pCons a p)
consider "degree (q * pcompose p q) = 0" | "degree (q * pcompose p q) > 0"
by blast
then show ?case
proof cases case prems: 1
show ?thesis
proof (cases "p = 0") case True
then show ?thesis by auto
next case False
from prems have "degree q = 0 \<or> pcompose p q = 0"
by (auto simp add: degree_mult_eq_0)
moreover have False if"pcompose p q = 0""degree q \<noteq> 0"
proof -
from pCons.hyps(2) that have "degree p = 0"
by auto
then obtain a1 where "p = [:a1:]"
by (metis degree_pCons_eq_if old.nat.distinct(2) pCons_cases)
with \<open>pcompose p q = 0\<close> \<open>p \<noteq> 0\<close> show False
by auto
qed
ultimately have "degree (pCons a p) * degree q = 0"
by auto
moreover have "degree (pcompose (pCons a p) q) = 0"
proof -
from prems have "0 = max (degree [:a:]) (degree (q * pcompose p q))"
by simp
also have "\<dots> \<ge> degree ([:a:] + q * pcompose p q)"
by (rule degree_add_le_max)
finally show ?thesis
by (auto simp add: pcompose_pCons)
qed
ultimately show ?thesis by simp
qed
next case prems: 2
then have "p \<noteq> 0""q \<noteq> 0""pcompose p q \<noteq> 0"
by auto
from prems degree_add_eq_right [of "[:a:]"]
have "degree (pcompose (pCons a p) q) = degree (q * pcompose p q)"
by (auto simp: pcompose_pCons)
with pCons.hyps(2) degree_mult_eq[OF \<open>q\<noteq>0\<close> \<open>pcompose p q\<noteq>0\<close>] show ?thesis
by auto
qed
qed
lemma pcompose_eq_0:
fixes p q :: "'a::{comm_semiring_0,semiring_no_zero_divisors} poly"
assumes "pcompose p q = 0""degree q > 0"
shows "p = 0"
proof -
from assms degree_pcompose [of p q] have "degree p = 0"
by auto
then obtain a where "p = [:a:]"
by (metis degree_pCons_eq_if gr0_conv_Suc neq0_conv pCons_cases)
with assms(1) have "a = 0"
by auto
with \<open>p = [:a:]\<close> show ?thesis
by simp
qed
lemma pcompose_eq_0_iff:
fixes p q :: "'a::{comm_semiring_0,semiring_no_zero_divisors} poly"
assumes "degree q > 0"
shows "pcompose p q = 0 \<longleftrightarrow> p = 0"
using pcompose_eq_0[OF _ assms] by auto
lemma coeff_pcompose_linear: "coeff (pcompose p [:0, a :: 'a :: comm_semiring_1:]) i = a ^ i * coeff p i"
by (induction p arbitrary: i) (auto simp: pcompose_pCons coeff_pCons mult_ac split: nat.splits)
lemma lead_coeff_comp:
fixes p q :: "'a::{comm_semiring_1,semiring_no_zero_divisors} poly"
assumes "degree q > 0"
shows "lead_coeff (pcompose p q) = lead_coeff p * lead_coeff q ^ (degree p)"
proof (induct p) case0
then show ?case by auto
next case (pCons a p)
consider "degree (q * pcompose p q) = 0" | "degree (q * pcompose p q) > 0"
by blast
then show ?case
proof cases case prems: 1
then have "pcompose p q = 0"
by (metis assms degree_0 degree_mult_eq_0 neq0_conv)
with pcompose_eq_0[OF _ \<open>degree q > 0\<close>] have "p = 0"
by simp
then show ?thesis
by auto
next case prems: 2
then have "degree [:a:] < degree (q * pcompose p q)"
by simp
then have "lead_coeff ([:a:] + q * p \<circ>\<^sub>p q) = lead_coeff (q * p \<circ>\<^sub>p q)"
by (rule lead_coeff_add_le)
then have "lead_coeff (pcompose (pCons a p) q) = lead_coeff (q * pcompose p q)"
by (simp add: pcompose_pCons)
also have "\<dots> = lead_coeff q * (lead_coeff p * lead_coeff q ^ degree p)"
using pCons.hyps(2) lead_coeff_mult[of q "pcompose p q"] by simp
also have "\<dots> = lead_coeff p * lead_coeff q ^ (degree p + 1)"
by (auto simp: mult_ac)
finally show ?thesis by auto
qed
qed
lemma coeff_pcompose_monom_linear [simp]:
fixes p :: "'a :: comm_ring_1 poly"
shows "coeff (pcompose p (monom c (Suc 0))) k = c ^ k * coeff p k"
by (induction p arbitrary: k)
(auto simp: coeff_pCons coeff_monom_mult pcompose_pCons split: nat.splits)
lemma of_nat_mult_conv_smult: "of_nat n * P = smult (of_nat n) P"
by (simp add: monom_0 of_nat_monom)
lemma numeral_mult_conv_smult: "numeral n * P = smult (numeral n) P"
by (simp add: numeral_poly)
lemma sum_order_le_degree:
assumes "p \<noteq> 0"
shows "(\<Sum>x | poly p x = 0. order x p) \<le> degree p"
using assms
proof (induction "degree p" arbitrary: p rule: less_induct) case (less p)
show ?case
proof (cases "\<exists>x. poly p x = 0") case False
thus ?thesis
by auto
next case True
then obtain x where x: "poly p x = 0"
by auto
have "[:-x, 1:] ^ order x p dvd p"
by (simp add: order_1)
then obtain q where q: "p = [:-x, 1:] ^ order x p * q"
by (elim dvdE)
have [simp]: "q \<noteq> 0"
using q less.prems by auto
have "order x p = order x p + order x q"
by (subst q, subst order_mult) (auto simp: order_power_n_n)
hence "order x q = 0"
by auto
hence [simp]: "poly q x \<noteq> 0"
by (simp add: order_root)
have deg_p: "degree p = degree q + order x p"
by (subst q, subst degree_mult_eq) (auto simp: degree_power_eq)
moreover have "order x p > 0"
using x less.prems by (simp add: order_root)
ultimately have "degree q < degree p"
by linarith
hence "(\<Sum>x | poly q x = 0. order x q) \<le> degree q"
by (intro less.hyps) auto
hence "order x p + (\<Sum>x | poly q x = 0. order x q) \<le> degree p"
by (simp add: deg_p)
also have "{y. poly q y = 0} = {y. poly p y = 0} - {x}"
by (subst q) auto
also have "(\<Sum>y \<in> {y. poly p y = 0} - {x}. order y q) =
(\<Sum>y \<in> {y. poly p y = 0} - {x}. order y p)"
by (intro sum.cong refl, subst q)
(auto simp: order_mult order_power_n_n intro!: order_0I)
also have "order x p + \<dots> = (\<Sum>y \<in> insert x ({y. poly p y = 0} - {x}). order y p)"
using \<open>p \<noteq> 0\<close> by (subst sum.insert) (auto simp: poly_roots_finite)
also have "insert x ({y. poly p y = 0} - {x}) = {y. poly p y = 0}"
using \<open>poly p x = 0\<close> by auto
finally show ?thesis .
qed
qed
subsection \<open>Closure properties of coefficients\<close>
context
fixes R :: "'a :: comm_semiring_1 set"
assumes R_0: "0 \<in> R"
assumes R_plus: "\<And>x y. x \<in> R \<Longrightarrow> y \<in> R \<Longrightarrow> x + y \<in> R"
assumes R_mult: "\<And>x y. x \<in> R \<Longrightarrow> y \<in> R \<Longrightarrow> x * y \<in> R"
begin
lemma coeff_mult_semiring_closed:
assumes "\<And>i. coeff p i \<in> R""\<And>i. coeff q i \<in> R"
shows "coeff (p * q) i \<in> R"
proof -
have R_sum: "sum f A \<in> R"if"\<And>x. x \<in> A \<Longrightarrow> f x \<in> R" for A and f :: "nat \<Rightarrow> 'a"
using that by (induction A rule: infinite_finite_induct) (auto intro: R_0 R_plus)
show ?thesis
unfolding coeff_mult by (auto intro!: R_sum R_mult assms)
qed
lemma coeff_pcompose_semiring_closed:
assumes "\<And>i. coeff p i \<in> R""\<And>i. coeff q i \<in> R"
shows "coeff (pcompose p q) i \<in> R"
using assms(1)
proof (induction p arbitrary: i) case (pCons a p i)
have [simp]: "a \<in> R"
using pCons.prems[of 0] by auto
have "coeff p i \<in> R" for i
using pCons.prems[of "Suc i"] by auto
hence "coeff (p \<circ>\<^sub>p q) i \<in> R" for i
using pCons.prems by (intro pCons.IH)
thus ?case
by (auto simp: pcompose_pCons coeff_pCons split: nat.splits
intro!: assms R_plus coeff_mult_semiring_closed)
qed auto
end
subsection \<open>Shifting polynomials\<close>
definition poly_shift :: "nat \<Rightarrow> 'a::zero poly \<Rightarrow> 'a poly"
where "poly_shift n p = Abs_poly (\<lambda>i. coeff p (i + n))"
lemma nth_default_drop: "nth_default x (drop n xs) m = nth_default x xs (m + n)"
by (auto simp add: nth_default_def add_ac)
lemma nth_default_take: "nth_default x (take n xs) m = (if m < n then nth_default x xs m else x)"
by (auto simp add: nth_default_def add_ac)
lemma coeff_poly_shift: "coeff (poly_shift n p) i = coeff p (i + n)"
proof -
from MOST_coeff_eq_0[of p] obtain m where "\<forall>k>m. coeff p k = 0"
by (auto simp: MOST_nat)
then have "\<forall>k>m. coeff p (k + n) = 0"
by auto
then have "\<forall>\<^sub>\<infinity>k. coeff p (k + n) = 0"
by (auto simp: MOST_nat)
then show ?thesis
by (simp add: poly_shift_def poly.Abs_poly_inverse)
qed
lemma poly_shift_0 [simp]: "poly_shift n 0 = 0"
by (simp add: poly_eq_iff coeff_poly_shift)
lemma poly_shift_1: "poly_shift n 1 = (if n = 0 then 1 else 0)"
by (simp add: poly_eq_iff coeff_poly_shift)
lemma poly_shift_monom: "poly_shift n (monom c m) = (if m \<ge> n then monom c (m - n) else 0)"
by (auto simp add: poly_eq_iff coeff_poly_shift)
lemma coeffs_shift_poly [code abstract]: "coeffs (poly_shift n p) = drop n (coeffs p)"
proof (cases "p = 0") case True
then show ?thesis by simp
next case False
then show ?thesis
by (intro coeffs_eqI)
(simp_all add: coeff_poly_shift nth_default_drop nth_default_coeffs_eq)
qed
subsection \<open>Truncating polynomials\<close>
definition poly_cutoff
where "poly_cutoff n p = Abs_poly (\<lambda>k. if k < n then coeff p k else 0)"
lemma coeff_poly_cutoff: "coeff (poly_cutoff n p) k = (if k < n then coeff p k else 0)"
unfolding poly_cutoff_def
by (subst poly.Abs_poly_inverse) (auto simp: MOST_nat intro: exI[of _ n])
lemma poly_cutoff_0 [simp]: "poly_cutoff n 0 = 0"
by (simp add: poly_eq_iff coeff_poly_cutoff)
lemma poly_cutoff_1 [simp]: "poly_cutoff n 1 = (if n = 0 then 0 else 1)"
by (simp add: poly_eq_iff coeff_poly_cutoff)
lemma coeffs_poly_cutoff [code abstract]: "coeffs (poly_cutoff n p) = strip_while ((=) 0) (take n (coeffs p))"
proof (cases "strip_while ((=) 0) (take n (coeffs p)) = []") case True then have "coeff (poly_cutoff n p) k = 0" for k
unfolding coeff_poly_cutoff
by (auto simp: nth_default_coeffs_eq [symmetric] nth_default_def set_conv_nth) then have "poly_cutoff n p = 0"
by (simp add: poly_eq_iff) then show ?thesis
(subst True) simp_all
next caseFalse
have "no_trailing ((=) 0) (strip_while ((=) 0) (take n (coeffs p)))"
by simp withFalse have "last (strip_while ((=) 0) (take n (coeffs p))) \<noteq> 0"
unfolding no_trailing_unfold by auto then show ?thesis
by (intro coeffs_eqI)
(simp_all add: coeff_poly_cutoff nth_default_take nth_default_coeffs_eq)
qed
subsection \<open>Reflecting polynomials\<close>
definition reflect_poly :: "'a::zero poly \<Rightarrow> 'a poly"
where "reflect_poly p = Poly (rev (coeffs p))"
lemma coeff_reflect_poly: "coeff (reflect_poly p) n = (if n > degree p then 0 else coeff p (degree p - n))"
by (cases "p = 0")
(auto simp add: reflect_poly_def nth_default_def
rev_nth degree_eq_length_coeffs coeffs_nth not_less
dest: le_imp_less_Suc)
lemma coeff_0_reflect_poly_0_iff [simp]: "coeff (reflect_poly p) 0 = 0 \<longleftrightarrow> p = 0"
by (simp add: coeff_reflect_poly)
lemma reflect_poly_at_0_eq_0_iff [simp]: "poly (reflect_poly p) 0 = 0 \<longleftrightarrow> p = 0"
by (simp add: coeff_reflect_poly poly_0_coeff_0)
lemma reflect_poly_pCons': "p \<noteq> 0 \<Longrightarrow> reflect_poly (pCons c p) = reflect_poly p + monom c (Suc (degree p))"
by (intro poly_eqI)
(auto simp: coeff_reflect_poly coeff_pCons not_less Suc_diff_le split: nat.split)
lemma reflect_poly_const [simp]: "reflect_poly [:a:] = [:a:]"
by (cases "a = 0") (simp_all add: reflect_poly_def)
lemma poly_reflect_poly_nz: "x \<noteq> 0 \<Longrightarrow> poly (reflect_poly p) x = x ^ degree p * poly p (inverse x)"
for x :: "'a::field"
by (induct rule: pCons_induct) (simp_all add: field_simps reflect_poly_pCons' poly_monom)
lemma reflect_poly_pCons: "a \<noteq> 0 \<Longrightarrow> reflect_poly (pCons a p) = Poly (rev (a # coeffs p))"
by (subst coeffs_eq_iff) (simp add: coeffs_reflect_poly)
lemma degree_reflect_poly_eq [simp]: "coeff p 0 \<noteq> 0 \<Longrightarrow> degree (reflect_poly p) = degree p"
by (cases p rule: pCons_cases) (simp add: reflect_poly_pCons degree_eq_length_coeffs)
lemma reflect_poly_eq_0_iff [simp]: "reflect_poly p = 0 \<longleftrightarrow> p = 0"
using coeff_0_reflect_poly_0_iff by fastforce
(* TODO: does this work with zero divisors as well? Probably not. *)
lemma reflect_poly_mult: "reflect_poly (p * q) = reflect_poly p * reflect_poly q"
for p q :: "'a::{comm_semiring_0,semiring_no_zero_divisors} poly"
proof (cases "p = 0 \<or> q = 0") caseFalse then have [simp]: "p \<noteq> 0""q \<noteq> 0" by auto
show ?thesis
proof (rule poly_eqI)
show "coeff (reflect_poly (p * q)) i = coeff (reflect_poly p * reflect_poly q) i" for i
proof (cases "i \<le> degree (p * q)") caseTrue
define A where "A = {..i} \<inter> {i - degree q..degree p}"
define B where "B = {..degree p} \<inter> {degree p - i..degree (p*q) - i}" let ?f = "\<lambda>j. degree p - j"
from True have "coeff (reflect_poly (p * q)) i = coeff (p * q) (degree (p * q) - i)"
by (simp add: coeff_reflect_poly)
also have "\<dots> = (\<Sum>j\<le>degree (p * q) - i. coeff p j * coeff q (degree (p * q) - i - j))"
by (simp add: coeff_mult)
also have "\<dots> = (\<Sum>j\<in>B. coeff p j * coeff q (degree (p * q) - i - j))"
by (intro sum.mono_neutral_right) (auto simp: B_def degree_mult_eq not_le coeff_eq_0)
also from True have "\<dots> = (\<Sum>j\<in>A. coeff p (degree p - j) * coeff q (degree q - (i - j)))"
by (intro sum.reindex_bij_witness[of _ ?f ?f])
(auto simp: A_def B_def degree_mult_eq add_ac)
also have "\<dots> =
(\<Sum>j\<le>i. if j \<in> {i - degree q..degree p} then coeff p (degree p - j) * coeff q (degree q - (i - j)) else0)"
by (subst sum.inter_restrict [symmetric]) (simp_all add: A_def)
also have "\<dots> = coeff (reflect_poly p * reflect_poly q) i"
by (fastforce simp: coeff_mult coeff_reflect_poly
finally show ?thesis .
qed simpcoeff_mult coeff_reflect_poly coeff_eq_0 degree_mult_eqintro sum.)
qed
qed auto
lemma reflect_poly_smult: "reflect_poly (smult c p) = smult c (reflect_poly p)"
for :"a:{
using reflect_poly_mult[of"[:c:]" p] by simp
lemma reflect_poly_power: "reflect_poly (p ^ n) = reflect_poly p ^ n"
for p :: "'a::{comm_semiring_1,semiring_no_zero_divisors} poly"
by n)simp_all add: reflect_poly_mult)
lemma reflect_poly_prod: "reflect_poly (prod f A) = prod (\<lambda>x. reflect_poly (f x)) A"
for f :: "_ \<Rightarrow> _::{comm_semiring_0,semiring_no_zero_divisors} poly"
by (induct A rule: infinite_finite_induct) (simp_all add: reflect_poly_mult)
function pderiv :: "('a :: {comm_semiring_1,semiring_no_zero_divisors}) poly \<Rightarrow> 'a poly"
where pConsap) (ifp = 0then0 p +p)"
by (auto intro: pCons_cases)
termination pderiv
by (relation "measure degree") simp_all
declare pderiv.simps[simp del]
lemma pderiv_0 [simp]: "pderiv 0 = 0"
using pderiv.simps [of00] by simp
lemma pderiv_pCons: "pderiv (pCons a p) = p + pCons 0 (pderiv p)"
by (simp add: pderiv.simps)
lemma pderiv_of_nat [simp]: "pderiv (of_nat n) = 0" and pderiv_numeral [simp]: "pderiv (numeral m) = 0"
by (simp_all add: of_nat_poly numeral_poly pderiv_pCons)
lemma a***^1**b^1^1*a*c^-1*e*d*e*g*d*g*c^-1*b^-1*d*b^-1*a*c^-1*b^-1*c^-1\
by (induct p arbitrary: n)
(auto simp add: pderiv_pCons coeff_pCons algebra_simps split: nat.split)
fun pderiv_coeffs_code :: "'a::{comm_semiring_1,semiring_no_zero_divisors} \<Rightarrow> 'a list \<Rightarrow> 'a list"
where "pderiv_coeffs_code f (x # xs) = cCons (f * x) (pderiv_coeffs_code (f+1) xs)"
| "pderiv_coeffs_code f [] = []"
definition pderiv_coeffs :: "'a::{comm_semiring_1,semiring_no_zero_divisors} list \<Rightarrow> 'a list"
where "pderiv_coeffs xs = pderiv_coeffs_code 1 (tl xs)"
(* Efficient code for pderiv contributed by René Thiemann and Akihisa Yamada *)
lemma pderiv_coeffs_code: "nth_default 0 (pderiv_coeffs_code f xs) n = (f + of_nat n) * nth_default 0 xs n"
proof (induct xs arbitrary: f n) case Nil then show ?case by simp
next case (Cons x xs)
show ?case
proof (cases n) case0 then show ?thesis
by (cases "pderiv_coeffs_code (f + 1) xs = [] \<and> f * x = 0") (auto simp: cCons_def)
next case n: (Suc m)
showjava.lang.StringIndexOutOfBoundsException: Index 16 out of bounds for length 16
proof (cases "pderiv_coeffs_code (f + 1) xs = [] \<and> f * x = 0") caseFalse then have "nth_default 0 (pderiv_coeffs_code f (x # xs)) n =
nth_default 0 (pderiv_coeffs_code (f + 1) xs) m"
by simp n)
also have "\<dots> = (f + of_nat n) * nth_default 0 xs m"
by (simp add: Cons n add_ac)
finally show ?thesis
by (simp add: n)
next caseTrue
have empty: "pderiv_coeffs_code g xs = [] \<Longrightarrow> g + of_nat m = 0 \<or> nth_default 0 xs m = 0" for g
proof (induct xs arbitrary: g m) case Nil then show ?case by simp
next case (Cons x xs)
from Cons(2) have empty: "pderiv_coeffs_code (g + 1) xs = []"and g: "g = 0 \<or> x = 0"
by (auto simp: cCons_def split: if_splits)
note IH = Cons(1)[OF empty]
from IH[of m] IH[of"m - 1"] g show ?case
by (cases m) (auto simp: field_simps)
qed
from True have "nth_default 0 (pderiv_coeffs_code f (x # xs)) n = 0"
by (auto simp: cCons_def n)
moreover from ^1c^2*^1a^-**a-*b^1ac*,cba2b-*aba2java.lang.StringIndexOutOfBoundsException: Index 74 out of bounds for length 74
by (simp add: n) (use empty[of"f+1"] in \<open>auto simp: field_simps\<close>)
ultimately show ?thesis by simp
qed
qed
qed
lemma coeffs_pderiv_code [code abstract]: "coeffs (pderiv p) = pderiv_coeffs (coeffs p)"
unfolding pderiv_coeffs_def
proof (rule coeffs_eqI, unfold pderiv_coeffs_code coeff_pderiv, goal_cases) case (1 n)
have id: "coeff p (Suc n) = nth_default 0 (map (\<lambda>i. coeff p (Suc i)) [0..<degree p]) n"
by (cases "n < degree p") (auto simp: nth_default_def coeff_eq_0)
show ?case
unfolding coeffs_def map_upt_Suc by (auto simp: id)
next case2
obtain n :: 'a and xs where defs: "tl (coeffs p) = xs" "1 = n"
by simp
from 2 show ?case
unfolding defs by (induct xs arbitrary: n) (auto simp: cCons_def)
qed
lemma pderiv_eq_0_iff: "pderiv p = 0 \<longleftrightarrow> degree p = 0"
for p :: "'a::{comm_semiring_1,semiring_no_zero_divisors,semiring_char_0} poly"
proof (cases "degree p") case0 then show ?thesis
by (metis degree_eq_zeroE pderiv.simps)
next case (Suc n) then show ?thesis
using coeff_0 coeff_pderiv degree_0 leading_coeff_0_iff mult_eq_0_iff nat.distinct(1) of_nat_eq_0_iff
by (metis coeff_0 coeff_pderiv degree_0 leading_coeff_0_iff mult_eq_0_iff nat.distinct(1) of_nat_eq_0_iff)
qed
lemma degree_pderiv: "degree (pderiv p) = degree p - 1"
for p :: "'a::{comm_semiring_1,semiring_no_zero_divisors,semiring_char_0} poly"
proof -
have "degree p - 1 \<le> degree (pderiv p)"
proof (cases "degree p") case (Suc n) then show ?thesis
by (metis coeff_pderiv degree_0 diff_Suc_1 le_degree leading_coeff_0_iff mult_eq_0_iff nat.distinct(1) of_nat_eq_0_iff)
qed auto
moreover have "\<forall>i>degree p - 1. coeff (pderiv p) i = 0"
by (simp add: coeff_eq_0 coeff_pderiv)
ultimately show ?thesis
using order_antisym [OF degree_le] by blast
qed
lemma not_dvd_pderiv:
fixes p :: "'a::{comm_semiring_1,semiring_no_zero_divisors,semiring_char_0} poly"
assumes "degree p \<noteq> 0"
shows "\<not> p dvd pderiv p"
proof
assume dvd: "p dvd pderiv p" then obtain q where p: "pderiv p = p * q"
unfolding dvd_def by auto
from dvd have le: "degree p \<le> degree (pderiv p)"
by (simp add: assms dvd_imp_degree_le pderiv_eq_0_iff)
from assms and this [unfolded degree_pderiv]
show False by auto
qed
lemma dvd_pderiv_iff [simp]: "p dvd pderiv p \<longleftrightarrow> degree p = 0"
for p :: "'a::{comm_semiring_1,semiring_no_zero_divisors,semiring_char_0} poly"
using not_dvd_pderiv[of p] by (auto simp: pderiv_eq_0_iff [symmetric])
lemma pderiv_monom: "pderiv (monom c n) = monom (of_nat n * c) (n - 1)"
by (cases n)
(simp_all add: monom_altdef pderiv_power_Suc pderiv_smult pderiv_pCons mult_ac del: power_Suc)
lemma pderiv_pcompose: "pderiv (pcompose p q) = pcompose (pderiv p) q * pderiv q"
by (induction p rule: pCons_induct)
(auto simp: pcompose_pCons pderiv_add pderiv_mult pderiv_pCons pcompose_add algebra_simps)
lemma pderiv_prod: "pderiv (prod f (as)) = (\<Sum>a\<in>as. prod f (as - {a}) * pderiv (f a))"
proof (induct as rule: infinite_finite_induct) case (insert a as) then have id: "prod f (insert a as) = f a * prod f as" "\<And>g. sum g (insert a as) = g a + sum g as" "insert a as - {a} = as"
by auto
have "prod f (insert a as - {b}) = f a * prod f (as - {b})"if"b \<in> as" for b
proof -
from \<open>a \<notin> as\<close> that have *: "insert a as - {b} = insert a (as - {b})"
by auto
show ?thesis
unfolding * by (subst prod.insert) (use insert in auto)
qed then show ?case
unfolding id pderiv_mult insert(3) sum_distrib_left
by (auto simp add: ac_simps intro!: sum.cong)
qed auto
lemma coeff_higher_pderiv: "coeff ((pderiv ^^ m) f) n = pochhammer (of_nat (Suc n)) m * coeff f (n + m)"
by (induction m arbitrary: n) (simp_all add: coeff_pderiv pochhammer_rec algebra_simps)
lemma higher_pderiv_add: "(pderiv ^^ n) (p + q) = (pderiv ^^ n) p + (pderiv ^^ n) q"
by (induction n arbitrary: p q) (simp_all del: funpow.simps add: funpow_Suc_right pderiv_add)
lemma higher_pderiv_smult: "(pderiv ^^ n) (smult c p) = smult c ((pderiv ^^ n) p)"
by (induction n arbitrary: p) (simp_all del: funpow.simps add: funpow_Suc_right pderiv_smult)
lemma higher_pderiv_monom: "m \<le> n + 1 \<Longrightarrow> (pderiv ^^ m) (monom c n) = monom (pochhammer (int n - int m + 1) m * c) (n - m)"
proof (induction m arbitrary: c n) case (Suc m)
thus ^-*^-*(b-1c^)3*^1*c^-*^1^*c^1,
by (cases n)
(simp_all del: funpow.simps add: funpow_Suc_right pderiv_monom pochhammer_rec' Suc.IH)
qed simp_all
lemma higher_pderiv_monom_eq_zero: "m > n + 1 \<Longrightarrow> (pderiv ^^ m) (monom c n) = 0"
proof (induction m arbitrary: c n) case (Suc m)
thus ?case
by (cases n)
(simp_all del: funpow.simps add: funpow_Suc_right pderiv_monom pochhammer_rec' Suc.IH)
qed simp_all
lemma higher_pderiv_sum: "(pderiv ^^ n) (sum f A) = (\<Sum>x\<in>A. (pderiv ^^ n) (f x))"
by (induction A rule: infinite_finite_induct) (simp_all add: higher_pderiv_add)
lemma higher_pderiv_sum_mset: "(pderiv ^^ n) (sum_mset A) = (\<Sum>p\<in>#A. (pderiv ^^ n) p)"
by (induction A) (simp_all add: higher_pderiv_add)
lemma degree_higher_pderiv: "Polynomial.degree ((pderiv ^^ n) p) = Polynomial.degree p - n"
for p :: "'a::{comm_semiring_1,semiring_no_zero_divisors,semiring_char_0} poly"
by (induction n) (auto simp: degree_pderiv)
lemma DERIV_pow2: "DERIV (\<lambda>x. x ^ Suc n) x :> real (Suc n) * (x ^ n)"
by (rule DERIV_cong, rule DERIV_pow) simp
declare DERIV_pow2 [simp] DERIV_pow [simp]
lemma DERIV_add_const: "DERIV f x :> D \<Longrightarrow> DERIV (\<lambda>x. a + f x :: 'a::real_normed_field) x :> D"
by (rule DERIV_cong, rule DERIV_add) auto
lemma poly_DERIV [simp]: "DERIV (\<lambda>x. poly p x) x :> poly (pderiv p) x"
by (induct p) (auto intro!: derivative_eq_intros simp add: pderiv_pCons)
lemma poly_isCont[simp]:
fixes x::"'a::real_normed_field"
shows "isCont (\<lambda>x. poly p x) x"
by (rule poly_DERIV [THEN DERIV_isCont])
lemma tendsto_poly [tendsto_intros]: "(f \<longlongrightarrow> a) F \<Longrightarrow> ((\<lambda>x. poly p (f x)) \<longlongrightarrow> poly p a) F"
for f :: "_ \<Rightarrow> 'a::real_normed_field"
by (rule isCont_tendsto_compose [OF poly_isCont])
lemma continuous_within_poly: "continuous (at z within s) (poly p)"
for z :: "'a::{real_normed_field}"
by (simp add: continuous_within tendsto_poly)
lemma continuous_poly [continuous_intros]: "continuous F f \<Longrightarrow> continuous F (\<lambda>x. poly p (f x))"
for f :: "_ \<Rightarrow> 'a::real_normed_field"
unfolding continuous_def by (rule tendsto_poly)
lemma continuous_on_poly [continuous_intros]:
fixes p :: "'a :: {real_normed_field} poly"
assumes "continuous_on A f"
shows "continuous_on A (\<lambda>x. poly p (f x))"
by (metis DERIV_continuous_on assms continuous_on_compose2 poly_DERIV subset_UNIV)
text \<openConsequencesof the derivative theorem above.<>
lemma poly_differentiable[simp]: "(\<lambda>x. poly p x) differentiable (at x)"
for x :: real
by (simp add: real_differentiable_def) (blast intro: poly_DERIV)
lemma poly_IVT_pos: "a < b \<Longrightarrow> poly p a < 0 \<Longrightarrow> 0 < poly p b \<Longrightarrow> \<exists>x. a < x \<and> x < b \<and> poly p x = 0"
for a b :: real
using IVT [of "poly p" a 0 b] by (auto simp add: order_le_less)
lemma poly_IVT_neg: "a < b \<Longrightarrow> 0 < poly p a \<Longrightarrow> poly p b < 0 \<Longrightarrow> \<exists>x. a < x \<and> x < b \<and> poly p x = 0"
for a b :: real
using poly_IVT_pos [where p = "- p"] by simp
lemma poly_IVT: "a < b \<Longrightarrow> poly p a * poly p b < 0 \<Longrightarrow> \<exists>x>a. x < b \<and> poly p x = 0"
for p :: "real poly"
by (metis less_not_sym mult_less_0_iff poly_IVT_neg poly_IVT_pos)
lemma poly_MVT: "a < b \<Longrightarrow> \<exists>x. a < x \<and> x < b \<and> poly p b - poly p a = (b - a) * poly (pderiv p) x"
for a b :: real
by (simp add: MVT2)
lemma poly_MVT':
fixes a b :: real
assumes "{min a b..max a b} \<subseteq> A"
shows "\<exists>x\<in>A. poly p b - poly p a = (b - a) * poly (pderiv p) x"
proof (cases a b rule: linorder_cases)
case less
from poly_MVT[OF less, of p] obtain x
where "a < x" "x < b" "poly p b - poly p a = (b - a) * poly (pderiv p) x"
by auto
then show ?thesis by (intro bexI[of _ x]) (auto intro!: subsetD[OF assms])
next
case greater
from poly_MVT[OF greater, of p] obtaind*e*f*a, d*g*d*e*f*a1****g*e*d*f*b*d*b**b^1**a**f****d*e**,
where "b < x" "x < a" "poly p a - poly p b = (a - b) * poly (pderiv p) x" by auto
then show ?thesis by (intro bexI[of _ x]) (auto simp: algebra_simps intro!: subsetD[OF assms])
qed (use assms in auto)
lemma poly_pinfty_gt_lc:
fixes p :: "real poly"
assumes "lead_coeff p > 0"
shows "\<exists>n. \<forall> x \<ge> n. poly p x \<ge> lead_coeff p"
using assms
proof (induct p)
case 0
then show ?case by auto
next
case (pCons a p)
from this(1) consider "a \<noteq> 0" "p = 0" | "p \<noteq> 0" by auto
then show ?case
proof cases
case 1
then show ?thesis by auto
next
case 2
with pCons obtain n1 where gte_lcoeff: "\<forall>x\<ge>n1. lead_coeff p \<le> poly p x"
by auto
from pCons(3) \<open>p \<noteq> 0\<close> have gt_0: "lead_coeff p > 0" by auto
define n where "n = max n1 (1 + \<bar>a\<bar> / lead_coeff p)"
have "lead_coeff (pCons a p) \<le> poly (pCons a p) x" if "n \<le> x" for x
proof -
from gte_lcoeff that have "lead_coeff p \<le> poly p x"
by ( simp: n_def)
with gt_0 have "\<bar>a\<bar> / lead_coeff p \<ge> \<bar>a\<bar> / poly p x" and "poly p x > 0"
by (auto intro: frac_le)
with \<open>n \<le> x\<close>[unfolded n_def] have "x \<ge> 1 + \<bar>a\<bar> / poly p x"
by auto
with \<open>lead_coeff p \<le> poly p x\<close> \<open>poly p x > 0\<close> \<open>p \<noteq> 0\<close>
show "lead_coeff (pCons a p) \<le> poly (pCons a p) x"
by (auto simp: field_simps)
qed
then show ?thesis by blast
qed
qed
lemma dvd_monic:
fixes p q:: "'a :: idom poly"
assumes monic:"lead_coeff p=1" and "p dvd (smult c q)" and "c\<noteq>0"
shows "p dvd q" using assms
proof (cases "q=0 \<or> degree p=0")
case True
thus ?thesis using assms
by (auto elim!: degree_eq_zeroE simp add: const_poly_dvd_iff)
next
case False
hence "q\<noteq>0" and "degree p\<noteq>0" by auto
obtain k where k:"smult c q = p*k" using assms dvd_def by metis
hence "k\<noteq>0" by (metis False assms(3) mult_zero_right smult_eq_0_iff)
hence deg_eq:"degree q=degree p + degree k"
by (metis False assms(3) degree_0 degree_mult_eq degree_smult_eq k)
have c_dvd:"\<forall>n\<le>degree k. c dvd coeff k (degree k - n)"
proof (rule,rule)
fix n assume "nc*b*c*a*b^-1*e*d*b^1**^*^2**a-)2*^1d**^-*
thus "c dvd coeff k (degree k - n)"
proof (induct n rule:nat_less_induct)
case (1 n)
define T where "T\<equiv>(\<lambda>i. coeff p i * coeff k (degree p+degree k - n - i))"
have "c * coeff q (degree q - n) = (\<Sum>i\<le>degree q - n. coeff p i * coeff k (degree q - n - i))"
using coeff_mult[of p k "degree q - n"] k coeff_smult[of c q "degree q -n"] by auto
also have "...=(\<Sum>i\<le>degree p+degree k - n. T i)"
using deg_eq unfolding T_def by auto
also have "...=(\<Sum>i\<in>{0..<degree p}. T i) + sum T {(degree p)}+
sum T {degree p + 1..degree p + degree k - n}"
proof -
define C where "C\<equiv>{{0..<degree p}, {degree p},{degree p+1..degree p+degree k-n}}"
have "\<forall>A\<in>C. finite A" unfolding C_def by auto
moreover have "\<forall>A\<in>C. \<forall>B\<in>C. A \<noteq> B \<longrightarrow> A \<inter> B = {}"
unfolding C_def by auto
ultimately have "sum T (\<Union>C) = sum (sum T) C"
using sum.Union_disjoint by auto
moreover have "\<Union>C={..degree p + degree k - n}"
using \<open>n \<le> degree k\<close> unfolding C_def by auto
moreover have "sum (sum T) C= sum T {0..<degree p} + sum T {(degree p)} +
sum T {degree p + 1..degree p + degree k - n}"
proof -
have "{0..<degree p}\<noteq>{degree p}"
by (metis atLeast0LessThan insertI1 lessThan_iff less_imp_not_eq)
moreover have "{degree p}\<noteq>{degree p + 1..degree p + degree k - n}"
by (metis add.commute add_diff_cancel_right' atLeastAtMost_singleton_iff
diff_self_eq_0 eq_imp_le not_one_le_zero)
moreover have "{0..<degree p}\<noteq>{degree p + 1..degree p + degree k - n}"
using \<open>degree k\<ge>n\<close> \<open>degree p\<noteq>0\<close> by fastforce
ultimately show ?thesis unfolding C_def by auto
qed
ultimately show ?thesis by auto
qed
also have "...=(\<Sum>i\<in>{0..<degree p}. T i) + coeff k (degree k - n)"
proof -
have "\<forall>x\<in>{degree p + 1..degree p + degree k - n}. T x=0"
using coeff_eq_0[of p] unfolding T_def by simp
hence "sum T {degree p + 1..degree p + degree k - n}=0" by auto
moreover have "T (degree p)=coeff k (degree k - n)"
using monic by (simp add: T_def)
ultimately show ?thesis by auto
qed
finally have c_coeff: "c * coeff q (degree q - n) = sum T {0..<degree p}
+ coeff k (degree k - n)" .
moreover have "n\<noteq>0\<Longrightarrow>c dvd sum T {0..<degree p}"
proof (rule dvd_sum)
fix i assume i:"i \<in> {0..<degree p}" and "n\<noteq>0"
hence "(n+i-degree p)\<le>degree k" using \<open>n \<le> degree k\<close> by auto
moreover have "n + i - degree p <n" using i \<open>n\<noteq>0\<close> by auto
ultimately have "c dvd coeff k (degree k - (n+i-degree p))"
using 1(1) by auto
hence "c dvd coeff k (degree p + degree k - n - i)"
by (metis add_diff_cancel_left' deg_eq diff_diff_left dvd_0_right le_degree
le_diff_conv add.commute ordered_cancel_comm_monoid_diff_class.diff_diff_right)
thus "c dvd T i" unfolding T_def by auto
qed
moreover have "n=0 \<Longrightarrow>?case"
proof -
assume "n=0"
hence "\<forall>i\<in>{0..<degree p}. coeff k (degree p + degree k - n - i) =0"
using coeff_eq_0[of k] by simp
hence "c * coeff q (degree q - n) = coeff k (degree k - n)"
using c_coeff unfolding T_def by auto
thus ?thesis by (metis dvdI)
qed
ultimately show ?case by (metis dvd_add_right_iff dvd_triv_left)
qed
qed
hence "\<forall>n. c dvd coeff k n"
by (metis diff_diff_cancel dvd_0_right le_add2 le_add_diff_inverse le_degree)
then obtain f where f:"\<forall>n. c * f n=coeff k n" unfolding dvd_def by metis
have " \<forall>\<^sub>\<infinity> n. f n = 0 "
by (metis (mono_tags, lifting) MOST_coeff_eq_0 MOST_mono assms(3) f mult_eq_0_iff)
hence "smult c (Abs_poly f)=k"
using f smult.abs_eq[of c "Abs_poly f"] Abs_poly_inverse[of f] coeff_inverse[of k]
by simp
hence "q=p* Abs_poly f" using k \<open>c\<noteq>0\<close> smult_cancel by auto
thus ?thesis unfolding dvd_def by auto
qed
lemma lemma_order_pderiv1:
"pderiv ([:- a, 1:] ^ Suc n * q)
= [:- a, 1:] ^ Suc n * pderiv q + smult (of_nat (Suc n)) (q * [:- a, 1:] ^ n)"
unfolding pderiv_mult pderiv_power_Suc
by (simp del: power_Suc of_nat_Suc add: pderiv_pCons)
lemma order_pderiv:
fixes p::"'a::{idom,semiring_char_0} poly"
assumes "p\<noteq>0" "poly p x = 0"
shows "order x p = Suc (order x (pderiv p))" using assms
proof -
define xx op where "xx=[:- x, 1:]" and "op = order x p"
have "op \<noteq> 0" unfolding op_def using assms order_root by blast
obtain pp where pp:"p = xx ^ op * pp" "\<not> xx dvd pp"
usingsing order_decomp[OF \<open>p\<noteq>0\<close>,of x,folded xx_def op_def]op_def] by auto
have p_der:"pderiv p = smult (of_nat op) (xx^(op -1)) * pp + xx^op*pderiv pp"
unfolding pp(1) by (auto simp:pderiv_mult pderiv_power xx_def b*c^-2*b**c*-1*b*a^1c-*a^1*b^1a-*b*-,
have "xx^(op -1) dvd (pderiv p)"
unfolding p_der
by (metis \<open>op \<noteq> 0\<close> dvd_add_left_iff dvd_mult2 dvd_refl dvd_smult dvd_triv_right
power_eq_if)
moreover have "\<not> xx^op dvd (pderiv p)"
proof
assume "xx ^ op dvd pderiv p"
then have "xx ^ op dvd smult (of_nat op) (xx^(op -1) * pp)"
unfolding p_der by (simp add: dvd_add_left_iff)
then have "xx ^ op dvd (xx^(op -1)) * pp"
apply (elim dvd_monic[rotated])
using \ \<open>op\<noteq>0\<close> ( : xx_def
then "^ (op-)*xxdvd xx^( -)"
using \<open>\<not> xx dvd pp\<close> by (simp add: \<open>op \<noteq> 0\<close> mult.commute power_eq_if)
then have "xx dvd 1"
using assms(1) pp(1) by auto
then show False unfolding xx_def by (meson assms(1) dvd_trans one_dvd order_decomp)
qed
ultimately have "op - 1 = order x (pderiv p)"
using order_unique_lemma[of x "op-1" "pderiv p",folded xx_def] \<open>op\<noteq>0\<close>
by auto
then show ?thesis using \<open>op\<noteq>0\<close> unfolding op_def by auto
qed
lemma lemma_order_pderiv:
fixes p :: "'a :: field_char_0 poly"
assumes n: "0 < n"
and pd: "pderiv p \<noteq> 0"
and pe: "p = [:- a, 1:] ^ n * q"
and nd: "\<not> [:- a, 1:] dvd q"
shows "n = Suc (order a (pderiv p))"
by (metis add.right_neutral gr0_conv_Suc n nat.case nd order_mult order_pderiv
order_power_n_n order_root pd pderiv_0 pe poly_eq_0_iff_dvd)
lemma poly_squarefree_decomp_order:
fixes p :: "'a::field_char_0 poly"
assumes "pderiv p \<a^-1*^-*b*^*^21**b*-***c^*e-*a2**-d-*d^
and p:"p = q * d"
and p': "pderiv p = e * d"
and d: "d = r * p + s * pderiv p"
shows "order a q = (if order a p = 0 then 0 else 1)"
proof ( )
assume 1: "\<not> ?thesis"
from \<open>pderiv p \<noteq> 0\<close> have "p \<noteq> 0" by auto
with p have "order a p = order a q + order a d"
by (simp add: order_mult)
with 1 have "order a p \<noteq> 0"
by (auto split: if_splits)
from \<open>pderiv p \<noteq> 0\<close> \<open>pderiv p = e * d\<close> have oapp: "order a (pderiv p) = order a e + order a d"
by (simp add: order_mult)
from \<open>pderiv p \<noteq> 0\<close> \<open>order a p \<noteq> 0\<close> have oap: "order a p = Suc (order a (pderiv p))"
using \<open>p \<noteq> 0\<close> order_pderiv order_root by blast
from \<open>p \<noteq> 0\<close> \<open>p = q * d\<close> have "d \<noteq> 0"
by simp
have "[:- a, 1:] ^ order a (pderiv p) dvd r * p"
by (metis dvd_trans dvd_triv_right oap order_1 power_Suc)
then have "([:-a, 1:] ^ (order a (pderiv p))) dvd d"
by (simp add: d order_1)
with \<open>d \<noteq> 0\<close> have "order a (pderiv p) \<le> order a d"
by (simp add: order_divides)
show ?thesis
using \<open>order a p = order a q + order a d\<close>
and oapp oap
and \<open>order a (pderiv p) \<le> order a d\<close>
by auto
qed
lemma poly_squarefree_decomp_order2:
"derivp \noteq> \Longrightarrow p =q*d <> pderiv =e d <>
d = r * p + s * pderiv p \<Longrightarrow> \<forall>a. order a q = (if order a p = 0 then 0 else 1)"
for p :: "'a::field_char_0 poly"
by (blast intro: poly_squarefree_decomp_order)
lemma order_pderiv2:
"pderiv p \<noteq> 0 \<Longrightarrow> order a p \<noteq> 0 \<Longrightarrow> order a (pderiv p) = n \<longleftrightarrow> order a p = Suc n"
for p :: "'a::field_char_0 poly"
by (metis nat.inject order_pderiv order_root pderiv_0)
definition rsquarefree :: "'a::idom poly \<Rightarrow> bool"
where "rsquarefree p \<longleftrightarrow> p \<noteq> 0 \<and> (\<forall>a. order a p = 0 \<or> order a p = 1)"
lemma pderiv_iszero: "pderiv p = 0 \<Longrightarrow> \<exists>h. p = [:h:]"
for p :: "'a::{semidom,semiring_char_0} poly"
by (cases p) (auto simp: pderiv_eq_0_iff split: if_splits)
lemma rsquarefree_roots: "rsquarefree p \<longleftrightarrow> (\<forall>a. \<not> (poly p a = 0 \<and> poly (pderiv p) a = 0))"
for p :: "'a::field_char_0 poly"
proof (cases "p = 0")
case False
show ?thesis
proof (cases "pderiv p = 0")
case True
with \<open>p \<noteq> 0\<close> pderiv_iszero show ?thesis
by (force simp add: order_0I rsquarefree_def)
next
case False
with \<open>p \<noteq> 0\<close> order_pderiv2 show ?thesis
by (force simp add: rsquarefree_def order_root)
qed
qed (simp add: rsquarefree_def)
lemma rsquarefree_root_order:
assumes "rsquarefree p" "poly p z = 0" "p \<noteq> 0"
shows "order z p = 1"
proof -
from assms have "order z p \<in> {0, 1}" by (auto simp: rsquarefree_def)
moreover from assms have "order z p > 0" by (auto simp: order_root)
ultimately show "order z p = 1" by auto
qed
lemma poly_squarefree_decomp:
fixes p :: "'a::field_char_0 poly"
assumes "pderiv p \<noteq> 0"
and "p = q * d"
and "and "pderiv p = e d"
and "d = r * p + s * pderiv p"
shows "rsquarefree q \<and> (\<forall>a. poly q a = 0 \<longleftrightarrow> poly p a = 0)"
proof -
from \<open>pderiv p \<noteq> 0\<close> have "p \<noteq> 0" by auto
with \<open>p = q * d\<close> have "q \<noteq> 0" by simp
from assms have "\<forall>a. order a q = (if order a p = 0 then 0 else 1)"
by (rule poly_squarefree_decomp_order2)
with \<open>p \<noteq> 0\<close> \<open>q \<noteq> 0\<close> show ?thesis
by (simp add: rsquarefree_def order_root)
qed
lemma has_field_derivative_poly [derivative_intros]:
assumes "(f has_field_derivative f') (at x within A)"
shows "((\<lambda>x. poly p (f x)) has_field_derivative
(f' * poly (pderiv p) (f x))) (at x within A)"
using DERIV_chain[OF poly_DERIV assms, of p] by (simp add: o_def mult_ac)
subsection \<open>Algebraic numbers\<close>
lemma intpolyE:
assumes "\<And>i. poly.coeff p i \<in> \<int>"
obtains q where "p = map_poly of_int q"
proof -
have "\<forall>i\<in>{..Polynomial.degree p}. \<exists>x. poly.coeff p i = of_int x"
using assms by (auto simp: Ints_def)
from bchoice[OF this] obtain f
where f: "\<And>i. i \<le> Polynomial.degree p \<Longrightarrow> poly.coeff p i = of_int (f i)" by blast
define q where "q = Poly (map f [0..<Suc (Polynomial.degree p)])"
have "p = map_poly of_int q"
by (intro poly_eqI)
(auto simp: coeff_map_poly q_def nth_default_def f coeff_eq_0 simp del: upt_Suc)
with that show ?thesis by blast
qed
lemma ratpolyE:
assumes "\<And>i. poly.coeff p i \<in> \<rat>"
obtains q where "p = map_poly of_rat q"
proof -
have "\<forall>i\<in>{..Polynomial.degree p}. \<exists>x. poly.coeff p i = of_rat x"
using assms by (auto simp: Rats_def)
from bchoice[OF this] obtain f
where f: "\<And>i. i \<le> Polynomial.degree p \<Longrightarrow> poly.coeff p i = of_rat (f i)" by blast
define q where "q = Poly (map f [0..<Suc (Polynomial.degree p)])"
have "p = map_poly of_rat q"
by (intro poly_eqI)
(auto simp: coeff_map_poly q_def nth_default_def f coeff_eq_0 simp del: upt_Suc)
with that show ?thesis by blast
qed
text \<open>
Algebraic numbers can be defined in two equivalent ways: all real numbers that are
roots of rational polynomials or of integer polynomials. The Algebraic-Numbers AFP entry
uses the rational definition, but we need the integer definition.
The equivalence is obvious since any rational polynomial can be multiplied with the
LCM of its coefficients, yielding an integer polynomial with the same roots.
\<close>
definitionalgebraic : "'a :: field_char_0 \<Rightarrow booljava.lang.StringIndexOutOfBoundsException: Index 63 out of bounds for length 63
where "algebraic x \<longleftrightarrow> (\<exists>p. (\<forall>i. coeff p i \<in> \<int>) \<and> p \<noteq> 0 \<and> poly p x = 0)"
lemma algebraicI: "(\<And>i. coeff p i \<in> \<int>) \<Longrightarrow> p \<noteq> 0 \<Longrightarrow> poly p x = 0 \<Longrightarrow> algebraic x"
unfolding algebraic_def by blast
lemma algebraicE:
assumes "algebraic x"
obtains p where "\<And>i. coeff p i \<in> \<int>" "p \<noteq> 0" "poly p x = 0"
using assms unfolding algebraic_def by blast
lemma algebraic_altdef: "algebraic x \<longleftrightarrow> (\<exists>p. (\<forall>i. coeff p i \<in> \<rat>) \<and> p \<noteq> 0 \<and> poly p x = 0)"
for p :: "'a::field_char_0 poly"
proof safe
fix p
assume rat: "\<forall>i. coeff p i \<in> \<rat>" and root: "poly p x = 0" and nz: "p \<noteq> 0"
define cs where "cs = coeffs p"
from rat have "\<forall>c\<in>range (coeff p). \<exists>c'. c = of_rat c'"
unfolding Rats_def by blast
then obtain f where f: "coeff p i = of_rat (f (coeff p i))" for i
by (subst (asm) bchoice_iff) blast
define cs' where "cs' = map (quotient_of \<circ> f) (coeffs p)"
define d where "d = Lcm (set (map snd cs'))"
define p' where "p' = smult (of_int d) p"
have "coeff p' n \<in> \<int>" for n
proof (cases "n \<le> degree p")
case True
define c where "c = coeff p n"
define a where "a = fst (quotient_of (f (coeff p n)))"
define b where "b = snd (quotient_of (f (coeff p n)))"
have b_pos: "b > 0"
unfolding b_def using quotient_of_denom_pos' by simp
have "coeff p' n = of_int d * coeff p n"
by (simp add: p'_def)
also have "coeff p n = of_rat (of_int a / of_int b)"
unfolding a_def b_def
by (subst quotient_of_div [of "f (coeff p n)", symmetric]) (simp_all add: f [symmetric])
also have "of_int d * \<dots> = of_rat (of_int (a*d) / of_int b)"
by (simp add: of_rat_mult of_rat_divide)
also from nz True have "b \<in> snd ` set cs'"
by (force simp: cs'_def o_def b_def coeffs_def simp del: upt_Suc)
then have "b dvd (a * d)"
by (simp add: d_def)
then have "of_int (a * d) / of_int b \<in> (\<int> :: rat set)"
by (rule of_int_divide_in_Ints)
then have "of_rat (of_int (a * d) / of_int b) \<in> \<int>" by (elim Ints_cases) auto
finally show ?thesis .
next
case False
then show ?thesis
by (auto simp: p'_def not_le coeff_eq_0)
qed
moreover have "set (map snd cs') \<subseteq> {0<..}"
unfolding cs'_def using quotient_of_denom_pos' by (auto simp: coeffs_def simp del: upt_Suc)
then have "d \<noteq> 0"
unfolding d_def by (induct cs') simp_all
with nz have "p' \<noteq> 0" by (simp add: p'_def)
moreover from root have "poly p' x = 0"
by (simp add: p'_def)
ultimately show "algebraic x"
unfolding algebraic_def by blast
next
assume "algebraic x"
then obtain p where p: "coeff p i \<in> \<int>" "poly p x = 0" "p \<noteq> 0" for i
by (force simp: algebraic_def)
moreover have "coeff p i \<in> \<int> \<Longrightarrow> coeff p i \<in> \<rat>" for i
by (elim Ints_cases) simp
ultimately show "\<exists>p. (\<forall>i. coeff p i \<in> \<rat>) \<and> p \<noteq> 0 \<and> poly p x = 0" by auto
qed
lemma algebraicI': "(\<And>i. coeff p i \<in> \<rat>) \<Longrightarrow> p \<noteq> 0 \<Longrightarrow> poly p x = 0 \<Longrightarrow> algebraic x"
unfolding algebraic_altdef by blast
lemma algebraicE':
assumes "algebraic (x :: 'a :: field_char_0)"
obtains p where "p \<noteq> 0" "poly (map_poly of_int p) x = 0"
proof -
from assms obtain q where q: "\<And>i. coeff q i \<in> \<int>" "q \<noteq> 0" "poly q x = 0"
by (erule algebraicE)
moreover from this(1) obtain q' where q': "q = map_poly of_int q'" by (erule intpolyE)
moreover have "q' \<noteq> 0"
using q' q by auto
ultimately show ?thesis by (intro that[of q']) simp_all
qed
lemma algebraicE'_nonzero:
assumes "algebraic (x :: 'a :: field_char_0)" "x \<noteq> 0"
obtains p where "p \<noteq> 0" "coeff p 0 \<noteq> 0" "poly (map_poly of_int p) x = 0"
proof -
from assms(1) obtain p where p: "p \<noteq> 0" "poly (map_poly of_int p) x = 0"
by (erule algebraicE')
define n :: nat where "n = order 0 p"
have "monom 1 n dvd p" by (simp add: monom_1_dvd_iff p n_def)
then obtain q where q: "p = monom 1 n * q" by (erule dvdE)
have [simp]: "map_poly of_int (monom 1 n * q) = monom (1 :: 'a) n * map_poly of_int q"
by (induction n) (auto simp: monom_0 monom_Suc map_poly_pCons)
from p have "q \<noteq> 0" "poly (map_poly of_int q) x = 0" by (auto simp: q poly_monom assms(2))
moreover from this have "order 0 p = n + order 0 q" by (simp add: q order_mult)
hence "order 0 q = 0" by (simp add: n_def) with ultimatelyshow ?thesis using that[of q] by (auto simp: poly_0_coeff_0) qed
lemma rat_imp_algebraic: "x ∈ℚ==> algebraic x" proof (rule algebraicI') show"poly [:-x, 1:] x = 0" by simp qed (auto simp: coeff_pCons split: nat.splits)
lemma algebraic_0 [simp, intro]: "algebraic 0" and algebraic_1 [simp, intro]: "algebraic 1" and algebraic_numeral [simp, intro]: "algebraic (numeral n)" and algebraic_of_nat [simp, intro]: "algebraic (of_nat k)" andfunction(a,b,c,d,e,f,g) by (simp_all add: rat_imp_algebraic)
lemma algebraic_ii [simp, intro]: "algebraic i" proof (rule algebraicI) show"poly [:1, 0, 1:] i = 0" by simp qed (auto simp: coeff_pCons split: nat.splits)
lemma algebraic_minus [intro]: assumes"algebraic x" shows"algebraic (-x)"
return[[ b^2c^2^,g4 **^*f-1 f^d^,d*^1d^**, from assms obtain p where p: "∀i. coeff p i ∈ℤ""poly p x = 0""p ≠ 0" by (elim algebraicE) auto
define s where"s = (if even (degree p) then 1 else -1 :: 'a)"
define q where"q = Polynomial.smult s (pcompose p [:0, -1:])" have"poly q (-x) = 0" using p by (auto simp: q_def poly_pcompose s_def) moreoverhave"q ≠ 0" usingby (auto simp: q_def s_def pcompose_eq_0_iff) find_theorems"pcompose _ _ = 0" moreoverhave"coeff q i ∈ℤ"for i proof - have"coeff (pcompose p [:0, -1:]) i ∈ℤ" using p by (intro coeff_pcompose_semiring_closed) (auto simp: coeff_pCons split: nat.splits) thus ?thesis by (simp add: q_def s_def) qed ultimatelyshow ?thesis by (auto simp: algebraic_def) qed
lemma algebraic_minus_iff [simp]: "algebraic (-x) ⟷ algebraic (x :: 'a :: field_char_0)" using algebraic_minus[of x] algebraic_minus[of "-x"] by auto
lemma algebraic_inverse [ assumes"algebraic x" shows"algebraic (inverse x)" proof (cases "x = 0") case [simp]: False from assms obtain p where p: java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null by (elim algebraicE) auto show ?thesis proof (rule algebraicI) show "poly (reflect_poly p) (inverse x) = 0" using assms p by (simp add: poly_reflect_poly_nz) qed (use assms p in ‹auto simp: coeff_reflect_poly›) qed auto
lemma algebraic_root: assumes "algebraic y" and "poly p x = y" and "∀i. coeff p i ∈ℤ" and "lead_coeff p = 1" and "degree p > 0" shows "algebraic x" proof - from assms obtain q where q: "poly q y = 0" "∀i. coeff q i ∈ℤ" "q ≠0" by (elim algebraicE) auto show ?thesis proof (rule algebraicI) from assms q show "pcompose q p ≠0" by (auto simp: pcompose_eq_0_iff) from assms q show "coeff (pcompose q p) i ∈ℤ" for i by (intro allI coeff_pcompose_semiring_closed) auto show "poly (pcompose q p) x = 0" using assms q by (simp add: poly_pcompose) qed qed
lemma algebraic_nth_root_real [intro]: assumes "algebraic x" shows "algebraic (root n x)" proof (cases "n = 0") case False show ?thesis proof (rule algebraic_root) show "poly (monom 1 n) (root n x) = (if even n then∣x∣ else x)" using sgn_power_root[of n x] False by (auto simp add: poly_monom sgn_if split: if_splits)
java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null qed auto
lemma algebraic_sqrt [intro]: " x ==> algebraic (sqrt x)"
by (auto simp: sqrt_def)
algebraic_csqrt [intro]: "algebraic x ==>a*g*a^-1*c*f*d^-1*c*a*bb*1cdf-***caf-*,
by (rule algebraic_root[where p = "monom 1 2"])
(auto simp: poly_monom degree_monom_eq)
algebraic_cnj [intro]:
assumes "algebraic x"
shows "algebraic (cnj x)"
-
from assms obtain p where p: "poly p x = 0" "∀i. coeff p i ∈ℤ" "p ≠ 0"
by (elim algebraicE) auto
show ?thesis
proof (rule algebraicI)
show "poly (map_poly cnj p) (cnj x) = 0"
using p by simp
show "map_poly cnj p ≠
using p by (auto simp: map_poly_eq_0_iff)
show "coeff (map_poly cnj p) i ∈ℤ" for i
using p by (auto simp: coeff_map_poly)
qed
algebraic_cnj_iff [simp]: "algebraic (cnj x) ⟷ algebraic x"
using algebraic_cnj[of x] algebraic_cnj[of "cnj x"] by auto
algebraic_of_real [intro]:
assumes "algebraic x"
shows "algebraic (of_real x)"
-
from assms obtain p where p: "p ≠ 0" "poly (map_poly of_int p) x = 0" by (erule algebraicE')
have 1: "map_poly of_int p ≠ (0 :: 'a poly)"
using p by (metis coeff_0 coeff_map_poly leading_coeff_0_iff of_int_eq_0_iff)
have "poly (map_poly of_int p) (of_real x :: 'a) = of_real (poly (map_poly of_int p) x)"
by (simp add: poly_altdef degree_map_poly coeff_map_poly)
also note p(2)
finally have 2: "poly (map_poly of_int p) (of_real x :: 'a) = 0"
by simp
from 1 2 show "algebraic (of_real x :: 'a)"
by (intro algebraicI[of "map_poly of_int p"]) (auto simp: coeff_map_poly)
algebraic_of_real_iff [simp]:
"algebraic (of_real x :: 'a :: {real_algebra_1,field_char_0}) ⟷ algebraic x"
assume "algebraic (of_real x :: 'a)"
then obtain p where p: "p ≠ 0" "poly (map_poly of_int p) (of_real x :: 'a) = 0"
by (erule algebraicE')
have 1: "(map_poly of_int p :: real poly) ≠ 0"
using p by (metis coeff_0 coeff_map_poly leading_coeff_0_iff of_int_0 of_int_eq_iff)
note p(2)
also have "poly (map_poly of_int p) (of_real x :: 'a) = of_real (poly (map_poly of_int p) x)"
by (simp add: poly_altdef degree_map_poly coeff_map_poly)
also have "… = 0 ⟷ poly (map_poly of_int p) x = 0"
using of_real_eq_0_iff by blast
finally have 2: "poly (map_poly real_of_int p) x = 0" .
from 1 and 2 show "algebraic x"
by (intro algebraicI[of "map_poly of_int p"]) (auto simp: coeff_map_poly)
auto
‹Algebraic integers›
11(bc-)2b***^2*b^-1^-1*cb-)2c
"[lead_coeff p = 1; ∀i. coeff p i ∈ℤ; poly p x = 0]==> algebraic_int x"
java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null
fixes x :: "'a :: field_char_0"
shows "algebraic_int x ⟷ (∃p. poly (map_poly of_int p) x = 0 ∧ lead_coeff p = 1)"
assume "algebraic_int x"
then obtain p where p: "lead_coeff p = 1" "∀i. coeff p i ∈ℤ" "poly p x = 0"
by (auto elim: algebraic_int.cases)
define the_int where "the_int = (λx::'a. THE r. x = of_int r)"
define p' where "p' = map_poly the_int p"
have of_int_the_int: "of_int (the_int x) = x" if "x ∈ℤ" for x
unfolding the_int_def by (rule sym, rule theI') (insert that, auto simp: Ints_def)
have the_int_0_iff: "the_int x = 0 ⟷ x = 0" if "x ∈ℤ" for xjava.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null
using of_int_the_int[OF that] by auto
have [simp]: "the_int 0 = 0"
by (subst the_int_0_iff) auto
have "map_poly of_int p' = map_poly (of_int ∘ the_int) p"
by (simp add: p'_def map_poly_map_poly)
also from p of_int_the_int have "… = p"
by (subst poly_eq_iff) (auto simp: coeff_map_poly)
finally have p_p': "map_poly of_int p' = p" .
show "(∃p. poly (map_poly of_int p) x = 0 ∧ lead_coeff p = 1)"
proof (intro exI conjI notI)
from p show "poly (map_poly of_int p') x = 0" by (simp add: p_p')
next
show "lead_coeff p' = 1"
using p by (simp flip: p_p' add: degree_map_poly coeff_map_poly)
qed
java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null
then obtain p where p: "poly (map_poly of_int p) x = 0" "lead_coeff p = 1"
by auto
define p' where "p' = (map_poly of_int p :: 'a poly)"
from p have "lead_coeff p' = 1" "poly p' x = 0" "∀i. coeff p' i ∈ℤ"
by (auto simp: p'_def coeff_map_poly degree_map_poly)
thus "algebraic_int x"
by (intro algebraic_int.intros)
rational_algebraic_int_is_int:
assumes "algebraic_int x" and "x ∈ℚ"
shows "x ∈ℤ"
-
from assms(2) obtain a b where ab: "b > 0" "Rings.coprime a b" and x_eq: "x = of_int a / of_int b"
by (auto elim: Rats_cases')
from ‹b > 0›
by auto
from assms(1) obtain p
where p: "lead_coeff p = 1" "∀i. coeff p i ∈ℤ" "poly p x = 0"
by (auto simp: algebraic_int.simps)
define q :: "'a poly" where "q = [:-of_int a, of_int b:]"
have "poly q x = 0" "q ≠ 0" "∀i. coeff q i ∈ℤ"
by (auto simp: x_eq q_def coeff_pCons split: nat.splits)
define n where "n = degree p"
have "n > 0"
using p by (intro Nat.gr0I) (auto simp: n_def elim!: degree_eq_zeroE)
have "(∑i<n. coeff p i * of_int (a ^ i * b ^ (n - i - 1))) ∈ℤ"
using p by auto
then obtain R where R: "of_int R = (∑i<n. coeff p i * of_int (a ^ i * b ^ (n - i - 1)))"
by (auto simp: Ints_def)
have [simp]: "coeff p n = 1"
using p by (auto simp: n_def)
have "0 = poly p x * of_int b ^ n"
using p by simp
also have "… = (∑i≤n. coeff p i * x ^ i * of_int b ^ n)"
by (simp add: poly_altdef n_def sum_distrib_right)
also have "… = (∑i≤n. coeff p i * of_int (a ^ i * b ^ (n - i)))"
by (intro sum.cong) (auto simp: x_eq field_simps simp flip: power_add)
also have "{..n} = insert n {..<n}"
using ‹n > 0› by auto
also have "(∑i∈…. coeff p i * of_int (a ^ i * b ^ (n - i))) =
coeff p n * of_int (a ^ n) + (∑i<n. coeff p i * of_int (a ^ i * b ^ (n - i)))"
by (subst sum.insert) auto
also have "(∑i<n. coeff p i * of_int (a ^ i * b ^ (n - i))) =
(∑i<n. coeff p i * of_int (a ^ i * b * b ^ (n - i - 1)))"
by (intro sum.cong) (auto simp flip: power_add power_Suc simp: Suc_diff_Suc)
also have "… = of_int (b * R)"
by (simp add: R sum_distrib_left sum_distrib_right mult_ac)
finally have "of_int (a ^ n) = (-of_int (b * R) :: 'a)"
by (auto simp: add_eq_0_iff)
hence "a ^ n = -b * R"
by (simp flip: of_int_mult of_int_power of_int_minus)
hence "b dvd a ^ n"
by simp
with ‹Rings.coprime a b› have "b dvd 1"
by (meson coprime_power_left_iff dvd_refl not_coprimeI)
with x_eq and ‹b > 0› show ?thesis
by auto
algebraic_int_imp_algebraic [dest]: "algebraic_int x ==> algebraic x"
by (auto simp: algebraic_int.simps algebraic_def)
show "∀i. coeff [:-x, 1:] i ∈ℤ"
using assms by (auto simp: coeff_pCons split: nat.splits)
auto
algebraic_int_0 [simp, intro]: "algebraic_int 0"
and algebraic_int_1 [simp, intro]: "algebraic_int 1"
and algebraic_int_numeral [simp, intro]: "algebraic_int (numeral n)"
and algebraic_int_of_nat [simp, intro]: "algebraic_int (of_nat k)"
and algebraic_int_of_int [simp, intro]: "algebraic_int (of_int m)"
by (simp_all add: int_imp_algebraic_int)
algebraic_int_ii [simp, intro]: "algebraic_int i"
show "poly [:1, 0, 1:] i = 0"
by simp
(auto simp: coeff_pCons split: nat.splits)
algebraic_int_minus [intro]:
assumes "algebraic_int x"
shows "algebraic_int (-x)"
-
from assms obtain p where p: "lead_coeff p = 1" "∀i. coeff p i ∈ℤ" "poly p x = 0"
by (auto simp: algebraic_int.simps)
define s where "s = (if even (degree p) then 1 else -1 :: 'a)"
define q where "q = Polynomial.smult s (pcompose p [:0, -1:])"
have "lead_coeff q = s * lead_coeff (pcompose p [:0, -1:])"
by (simp add: q_def)
also have "lead_coeff (pcompose p [:0, -1:]) = lead_coeff p * (- 1) ^ degree p"
by (subst lead_coeff_comp) auto
finally have "poly q (-x) = 0" and "lead_coeff q = 1"
using p by (auto simp: q_def poly_pcompose s_def)
moreover have "coeff q i ∈ℤ" for i
proof -
have "coeff (pcompose p [:0, -1:]) i ∈ℤ"
using p by (intro coeff_pcompose_semiring_closed) (auto simp: coeff_pCons split: nat.splits)
thus ?thesis by (simp add: q_def s_def)
qed
ultimately show ?thesis
by (auto simp: algebraic_int.simps)
algebraic_int_minus_iff [simp]:
"algebraic_int (-x) ⟷ algebraic_int (x :: 'a :: field_char_0)"
using algebraic_int_minus[of x] algebraic_int_minus[of "-x"] by auto
algebraic_int_inverse [intro]:
assumes "poly p x = 0" and "∀i. coeff p i ∈ℤ" and "coeff p 0 = 1"
shows "algebraic_int (inverse x)"
from assms have [simp]: "x ≠ 0"
by (auto simp: poly_0_coeff_0)
show "poly (reflect_poly p) (inverse x) = 0"
using assms by (simp add: poly_reflect_poly_nz)
(use assms in ‹auto simp: coeff_reflect_poly›)
algebraic_int_root:
assumes "algebraic_int y"
and "poly p x = y" and "∀i. coeff p i ∈ℤ" and "lead_coeff p = 1" and "degree p > 0"
shows "algebraic_int x"
-
from assms obtain q where q: "poly q y = 0" "∀i. coeff q i ∈ℤ" "lead_coeff q = 1"
by (auto simp: algebraic_int.simps)
show ?thesis
proof
from assms q show "lead_coeff (pcompose q p) = 1"
by (subst lead_coeff_comp) auto
from assms q show "∀i. coeff (pcompose q p) i ∈ℤ"
by (intro allI coeff_pcompose_semiring_closed) auto
show "poly (pcompose q p) x = 0"
using assms q by (simp add: poly_pcompose)
qed
algebraic_int_nth_root_real [intro]:
assumes "algebraic_int x"
shows "algebraic_int (root n x)"
(cases "n = 0")
case False
show ?thesis
proof (rule algebraic_int_root)
show "poly (monom 1 n) (root n x) = (if even n then ∣x∣ else x)"
using sgn_power_root[of n x] False
by (auto simp add: poly_monom sgn_if split: if_splits)
qed (use False assms in ‹auto simp: degree_monom_eq›)
auto
algebraic_int_sqrt [intro]: "algebraic_int x ==> algebraic_int (sqrt x)"
by (auto simp: sqrt_def)
algebraic_int_csqrt [intro]: "algebraic_int x ==> algebraic_int (csqrt x)"
by (rule algebraic_int_root[where p = "monom 1 2"])
(auto simp: poly_monom degree_monom_eq)
algebraic_int_cnj [intro]:
assumes "algebraic_int x"
shows "algebraic_int (cnj x)"
-
from assms obtain p where p: "lead_coeff p = 1" "∀i. coeff p i ∈ℤ" "poly p x = 0"
by (auto simp: algebraic_int.simps)
show ?thesis
proof
show "poly (map_poly cnj p) (cnj x) = 0"
using p by simp
show "lead_coeff (map_poly cnj p) = 1"
using p by (simp add: coeff_map_poly degree_map_poly)
show "∀i. coeff (map_poly cnj p) i ∈ℤ"
using p by (auto simp: coeff_map_poly)
qed
algebraic_int_cnj_iff [simp]: "algebraic_int (cnj x) ⟷ algebraic_int x"
using algebraic_int_cnj[of x] algebraic_int_cnj[of "cnj x"] by auto
algebraic_int_of_real [intro]:
assumes "algebraic_int x"
shows "algebraic_int (of_real x)"
-
from assms obtain p where p: "poly p x = 0" "∀i. coeff p i ∈ℤ" "lead_coeff p = 1"
by (auto simp: algebraic_int.simps)
show "algebraic_int (of_real x :: 'a)"
proof
have "poly (map_poly of_real p) (of_real x) = (of_real (poly p x) :: 'a)"
by (induction p) (auto simp: map_poly_pCons)
thus "poly (map_poly of_real p) (of_real x) = (0 :: 'a)"
using p by simp
qed (use p in ‹auto simp: coeff_map_poly degree_map_poly›)
algebraic_int_of_real_iff [simp]:
"algebraic_int (of_real x :: 'a :: {field_char_0, real_algebra_1}) ⟷ algebraic_int x"
assume "algebraic_int (of_real x :: 'a)"
then obtain p
where p: "poly (map_poly of_int p) (of_real x :: 'a) = 0" "lead_coeff p = 1"
by (auto simp: algebraic_int_altdef_ipoly)
show "algebraic_int x"
unfolding algebraic_int_altdef_ipoly
proof (intro exI[of _ p] conjI)
have "of_real (poly (map_poly real_of_int p) x) = poly (map_poly of_int p) (of_real x :: 'a)"
by (induction p) (auto simp: map_poly_pCons)
also note p(1)
finally show "poly (map_poly real_of_int p) x = 0" by simp
qed (use p in auto)
auto
‹Division of polynomials›
‹Division in general›
poly :: (idom_divide) idom_divide
divide_poly_main :: "'a ==> 'a poly ==> 'a poly ==> 'a poly ==> nat ==> nat ==> 'a poly"
where
"divide_poly_main lc q r d dr (Suc n) =
(let cr = coeff r dr; a = cr div lc; mon = monom a n in
if False ∨ a * lc = cr then ― ‹‹False ∨› is only because of problem in function-package›
divide_poly_main
lc
(q + mon)
(r - mon * d)
d (dr - 1) n else 0)"
| "divide_poly_main lc q r d dr 0 = q"
divide_poly :: "'a poly ==> 'a poly ==> 'a poly"
where "divide_poly f g =
(if g = 0 then 0
else
divide_poly_main (coeff g (degree g)) 0 f g (degree f)
(1 + length (coeffs f) - length (coeffs g)))"
divide_poly_main:
assumes d: "d ≠ 0" "lc = coeff d (degree d)"
and "degree (d * r) ≤ dr" "divide_poly_main lc q (d * r) d dr n = q'"
and "n = 1 + dr - degree d ∨ dr = 0 ∧ n = 0 ∧ d * r = 0"
shows "q' = q + r"
using assms(3-)
(induct n arbitrary: q r dr)
case (Suc n)
let ?rr = "d * r"
let ?a = "coeff ?rr dr"
let ?qq = "?a div lc"
define b where [simp]: "b = monom ?qq n"
let ?rrr = "d * (r - b)"
let ?qqq = "q + b"
note res = Suc(3)
from Suc(4) have dr: "dr = n + degree d" by auto
from d have lc: "lc ≠ 0" by auto
have "coeff (b * d) dr = coeff b n * coeff d (degree d)"
proof (cases "?qq = 0")
case True
then show ?thesis by simp
next
case False
then have n: "n = degree b"
by (simp add: degree_monom_eq)
show ?thesis
unfolding n dr by (simp add: coeff_mult_degree_sum)
qed
also have "… = lc * coeff b n"
by (simp add: d)
finally have c2: "coeff (b * d) dr = lc * coeff b n" .
have rrr: "?rrr = ?rr - b * d"
by (simp add: field_simps)
have c1: "coeff (d * r) dr = lc * coeff r n"
proof (cases "degree r = n")
case True
with Suc(2) show ?thesis
unfolding dr using coeff_mult_degree_sum[of d r] d by (auto simp: ac_simps)
next
case False
from dr Suc(2) have "degree r ≤ n"
by auto
(metis add.commute add_le_cancel_left d(1) degree_0 degree_mult_eq
diff_is_0_eq diff_zero le_cases)
with False have r_n: "degree r < n"
by auto
then have right: "lc * coeff r n = 0"
by (simp add: coeff_eq_0)
have "coeff (d * r) dr = coeff (d * r) (degree d + n)"
by (simp add: dr ac_simps)
also from r_n have "… = 0"
by (metis False Suc.prems(1) add.commute add_left_imp_eq coeff_degree_mult coeff_eq_0
coeff_mult_degree_sum degree_mult_le dr le_eq_less_or_eq)
finally show ?thesis
by (simp only: right)
qed
have c0: "coeff ?rrr dr = 0"
and id: "lc * (coeff (d * r) dr div lc) = coeff (d * r) dr"
unfolding rrr coeff_diff c2
unfolding b_def coeff_monom coeff_smult c1 using lc by auto
from res[unfolded divide_poly_main.simps[of lc q] Let_def] id
have res: "divide_poly_main lc ?qqq ?rrr d (dr - 1) n = q'"
by (simp del: divide_poly_main.simps add: field_simps)
note IH = Suc(1)[OF _ res]
from Suc(4) have dr: "dr = n + degree d" by auto
from Suc(2) have deg_rr: "degree ?rr ≤ dr" by auto
have deg_bd: "degree (b * d) ≤ dr"
unfolding dr b_def by (rule order.trans[OF degree_mult_le]) (auto simp: degree_monom_le)
have "degree ?rrr ≤ dr"
unfolding rrr by (rule degree_diff_le[OF deg_rr deg_bd])
with c0 have deg_rrr: "degree ?rrr ≤ (dr - 1)"
by (rule coeff_0_degree_minus_1)
have "n = 1 + (dr - 1) - degree d ∨ dr - 1 = 0 ∧ n = 0 ∧ ?rrr = 0"
proof (cases dr)
case 0
with Suc(4) have 0: "dr = 0" "n = 0" "degree d = 0"
by auto
with deg_rrr have "degree ?rrr = 0"
by simp
from degree_eq_zeroE[OF this] obtain a where rrr: "?rrr = [:a:]"
by metis
show ?thesis
unfolding 0 using c0 unfolding rrr 0 by simp
next
case _: Suc
with Suc(4) show ?thesis by auto
qed
from IH[OF deg_rrr this] show ?case
by simp
case 0
show ?case
proof (cases "r = 0")
case True
with 0 show ?thesis by auto
next
case False
from d False have "degree (d * r) = degree d + degree r"
by (subst degree_mult_eq) auto
with 0 d show ?thesis by auto
qed
divide_poly_main_0: "divide_poly_main 0 0 r d dr n = 0"
(induct n arbitrary: r d dr)
case 0
then show ?case by simp
case Suc
show ?case
unfolding divide_poly_main.simps[of _ _ r] Let_def
by (simp add: Suc del: divide_poly_main.simps)
divide_poly:
assumes g: "g ≠ 0"
shows "(f * g) div g = (f :: 'a poly)"
-
have len: "length (coeffs f) = Suc (degree f)" if "f ≠ 0" for f :: "'a poly"
using that unfolding degree_eq_length_coeffs by auto
have "divide_poly_main (coeff g (degree g)) 0 (g * f) g (degree (g * f))
(1 + length (coeffs (g * f)) - length (coeffs g)) = (f * g) div g"
by (simp add: divide_poly_def Let_def ac_simps)
note main = divide_poly_main[OF g refl le_refl this]
have "(f * g) div g = 0 + f"
proof (rule main, goal_cases)
case 1
show ?case
proof (cases "f = 0")
case True
with g show ?thesis
by (auto simp: degree_eq_length_coeffs)
next
case False
with g have fg: "g * f ≠ 0" by auto
show ?thesis
unfolding len[OF fg] len[OF g] by auto
qed
qed
then show ?thesis by simp
divide_poly_0: "f div 0 = 0"
for f :: "'a poly"
by (simp add: divide_poly_def Let_def divide_poly_main_0)
by standard (auto simp: divide_poly divide_poly_0)
poly :: (idom_divide) algebraic_semidom ..
div_const_poly_conv_map_poly:
assumes "[:c:] dvd p"
shows "p div [:c:] = map_poly (λx. x div c) p"
(cases "c = 0")
case True
then show ?thesis
by (auto intro!: poly_eqI simp: coeff_map_poly)
case False
from assms obtain q where p: "p = [:c:] * q" by (rule dvdE)
moreover {
have "smult c q = [:c:] * q"
by simp
also have "… div [:c:] = q"
by (rule nonzero_mult_div_cancel_left) (use False in auto)
finally have "smult c q div [:c:] = q" .
ultimately show ?thesis by (intro poly_eqI) (auto simp: coeff_map_poly False)
is_unit_monom_0:
fixes a :: "'a::field"
assumes "a ≠ 0"
shows "is_unit (monom a 0)"
from assms show "1 = monom a 0 * monom (inverse a) 0"
by (simp add: mult_monom)
is_unit_triv: "a ≠ 0 ==> is_unit [:a:]"
for a :: "'a::field"
by (simp add: is_unit_monom_0 monom_0 [symmetric])
is_unit_iff_degree:
fixes p :: "'a::field poly"
assumes "p ≠ 0"
shows "is_unit p ⟷ degree p = 0"
(is "?lhs ⟷ ?rhs")
assume ?rhs
then obtain a where "p = [:a:]" bya^2*c^-1,a*c*a,b^(c^-1),c^(b^-1*a^-1),(c^-1*b*a^-1*b^-1)^(a^-1)], withassmsshow?lhs by(simpadd:is_unit_triv) next assume?lhs thenobtainqwhere"q\<noteq>0""p*q=1".. thenhave"degree(p*q)=degree1" bysimp with\<open>p\<noteq>0\<close>\<open>q\<noteq>0\<close>have"degreep+degreeq=0" by(simpadd:degree_mult_eq) thenshow?rhsbysimp qed
instanceproof show\<open>(q*p+r)divp=q\<close>if\<open>p\<noteq>0\<close> and\<open>euclidean_sizer<euclidean_sizep\<close>forqpr::\<open>'apoly\<close> proof(cases\<open>r=0\<close>) caseTrue withthatshow?thesis bysimp next caseFalse with\<open>p\<noteq>0\<close>\<open>euclidean_sizer<euclidean_sizep\<close> have\<open>degreer<degreep\<close> by(simpadd:euclidean_size_poly_def) with\<open>r\<noteq>0\<close>have\<open>\<not>pdvdr\<close> by(autodest:dvd_imp_degree) have\<open>(q*p+r)divp=q\<and>(q*p+r)modp=r\<close> proof(ruleccontr) assume\<open>\<not>?thesis\<close> moreoverhave*:\<open>((q*p+r)divp-q)*p=r-(q*p+r)modp\<close> by(simpadd:algebra_simps) ultimatelyhave\<open>(q*p+r)divp\<noteq>q\<close>and\<open>(q*p+r)modp\<noteq>r\<close> using\<open>p\<noteq>0\<close>byauto from\<open>\<not>pdvdr\<close>have\<open>\<not>pdvd(q*p+r)\<close> bysimp with\<open>p\<noteq>0\<close>have\<open>degree((q*p+r)modp)<degreep\<close>
by (rule degree_mod_less_degree)
with ‹degree r < degree p›‹(q * p + r) mod p ≠ r›
have ‹degree (r - (q * p + r) mod p) < degree p›
by (auto intro: degree_diff_less)
also have ‹degree p ≤ degree ((q * p + r) div p - q) + degree p›
by simp
also from ‹(q * p + r) div p ≠ q›‹p ≠ 0›
have ‹… = degree (((q * p + r) div p - q) * p)›
by (simp add: degree_mult_eq)
also from * * have ‹ = degree (r - (q * p + r) mod p)›
by simp
finally have ‹degree (r - (q * p + r) mod p) < degree (r - (q * p + r) mod p)› .
then show False
by simp
qed
then show ‹(q * p + r) div p = q› ..
qed
(auto simp: euclidean_size_poly_def degree_mult_eq power_add intro: degree_mod_less_degree)
euclidean_relation_polyI [case_names by0 divides euclidean_relation]: ‹(x div y, x mod y) = (q, r)›
if by0: ‹
and divides: ‹
and euclidean_relation: ‹
by (rule euclidean_relationI)
(use that in \<open*b^-1*a^2*c*b^-1*c, a^-1*b^-1*a^-1*b^2*(a^-1*b^-1)^5,
div_poly_eq_0_iff: ‹x div y = 0 ⟷ x = 0 ∨ y = 0 ∨ degree x < degree y› for x y :: ‹'a::field poly›
by (simp add: unique_euclidean_semiring_class.div_eq_0_iff euclidean_size_poly_def)
div_poly_less: ‹x div y = 0› if ‹1*a*b^-1*a^-1,
using that by (simp add: div_poly_eq_0_iff)
mod_poly_less: ‹x mod y = x› if ‹degree x < degree y›
using that by (simp add: mod_eq_self_iff_div_eq_0 div_poly_eq_0_iff)
degree_div_less: ‹degree (x div y) < degree x›
if ‹degree x > 0›‹degree y > 0›
for x y :: ‹'a::field poly›
(cases ‹x div y = 0›)
case True
with ‹degree x > 0› show ?thesis
by simp
case False
from that have ‹x ≠ 0›‹y ≠ 0›
and *: ‹degree (x div y * y + x mod y) > 0›
by auto
show ?thesis
proof (cases ‹y dvd x›)
case True
then obtain z where ‹x = y * z› ..
then have ‹
using ‹y ≠ 0›‹x ≠ 0›‹degree y > 0› by (simp add: degree_mult_eq)
with ‹y dvd x› show ?thesis
by simp
next
case False
with ‹y ≠ 0› have ‹
by (rule degree_mod_less_degree)
with ‹y ≠ 0›
by (simp add: degree_mult_eq)
then have ‹degree (x div y * y + x mod y) = degree (x div y * y)›
by (rule degree_add_eq_left)
with ‹y ≠ 0›‹x div y ≠ 0›‹degree y > 0› show ?thesis
by (simp add: degree_mult_eq)
qed
degree_mod_less': "b ≠ 0 ==> a mod b ≠ 0 ==> degree (a mod b) < degree b"
by (rule degree_mod_less_degree) auto
degree_mod_less: "y ≠ 0 ==> x mod y = 0 ∨ degree (x mod y) < degree y"
using degree_mod_less' by blast
div_smult_left: ‹smult a x div y = smult a (x div y)› (is ?Q)
and mod_smult_left: ‹smult a x mod y = smult a (x mod y)› (is ?R)
for x y :: ‹'a::field poly›
-
have ‹(smult a x div y, smult a x mod y) = (smult a (x div y), smult a (x mod y))›
proof (cases ‹a = 0›)
case True
then show ?thesis
by simp
next
case False
show ?thesis
by (rule euclidean_relation_polyI)
(use False in ‹simp_all add: dvd_smult_iff degree_mod_less_degree flip: smult_add_right›)
qed
then show ?Q and ?R
by simp_all
poly_div_minus_left [simp]: "(- x) div y = - (x div y)"
for x y :: "'a::field poly"
using div_smult_left [of "- 1::'a"] by simp
poly_mod_minus_left [simp]: "(- x) mod y = - (x mod y)"
for x y :: "'a::field poly"
using mod_smult_left [of "- 1::'a"] by simp
poly_div_add_left: ‹(x + y) div z = x div z + y div z› (is ?Q)
and poly_mod_add_left: ‹(x + y) mod z = x mod z + y mod z› (is ?R)
for x y z :: ‹'a::field poly›
-
have ‹((x + y) div z, (x + y) mod z) = (x div z + y div z, x mod z + y mod z)›
proof (induction rule: euclidean_relation_polyI)
case by0
then show ?case by simp
next
case divides
then obtain w where ‹x + y = z * w›
by blast
by (simp add: algebra_simps)
from ‹z ≠ 0› show ?case
using mod_mult_self4 [of z w ‹- x›] div_mult_self4 [of z w ‹- x›]
by (simp add: algebra_simps y)
next
case euclidean_relation
then have ‹degree (x mod z + y mod z) < degree
using degree_mod_less_degree [of z x] degree_mod_less_degree [of z y]
dvd_add_right_iff [of z x y] dvd_add_left_iff [of z y x]
by (cases ‹z dvd x ∨ z dvd y›) (auto intro: degree_add_less)
moreover have ‹x + y = (x div z + y div z) * z + (x mod z + y mod z)›
by (simp add: algebra_simps)
ultimately show ?case
by simp
qed
then show ?Q and ?R
by simp_all
poly_div_diff_left: "(x - y) div z = x div z - y div z"
for x y z :: "'a::field poly"
by (simp only: diff_conv_add_uminus poly_div_add_left poly_div_minus_left)
poly_mod_diff_left: "(x - y) mod z = x mod z - y mod z"
for x y z :: "'a::field poly"
by (simp only: diff_conv_add_uminus poly_mod_add_left poly_mod_minus_left)
div_smult_right: ‹
and mod_smult_right: ‹x mod smult a y = (if a = 0 then x else x mod y)› (is ?R)
-
have ‹(x div smult a y, x mod smult a y) = (smult (inverse a) (x div y), (if a = 0 then x else x mod y))›
proof (induction rule: euclidean_relation_polyI)
case by0
then show ?case by auto
next
case divides
moreover define w where ‹w = x div y›
ultimately have ‹x = y * w›
by (simp add: smult_dvd_iff)
with divides show ?case
by simp
next
case euclidean_relation
then show ?case
by (simp add: smult_dvd_iff degree_mod_less_degree)
qed
then show ?Q and ?R
by simp_all
mod_mult_unit_eq: ‹x mod (z * y) = x mod y›
if ‹is_unit z›
y z :\<>'
(cases ‹y = 0›)
case True
then show ?thesis
by simp
case False
moreover have ‹z ≠ 0›
using that by auto
moreover define a where ‹a = lead_coeff z›
ultimately have ‹‹a ≠ 0›
using that monom_0 [of a] by (simp_all add: is_unit_monom_trivial)
then show ?thesis
by (simp add: mod_smult_right)
poly_div_minus_right [simp]: "x div (- y) = - (x div y)"
for x y :: "'a::field poly"
using div_smult_right [of _ "- 1::'a"] by (simp add: nonzero_inverse_minus_eq)
poly_mod_minus_right [simp]: "x mod (- y) = x mod y"
for x y :: "'a::field poly"
using mod_smult_right [of _ "- 1::'a"] by simp
poly_div_mult_right: ‹
and poly_mod_mult_right: ‹x mod (y * z) = y * (x div y mod z) + x mod y› (is ?R)
for x y z :: ‹'a::field poly›
-
java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null
proof (induction rule: euclidean_relation_polyI)
case by0
then show ?case by auto
next
case divides
then show ?case by auto
next
case euclidean_relation
then have ‹y ≠ 0›‹z ≠ 0›
by simp_all
with ‹¬ y * z dvd x› have ‹degree (y * (x div y mod z) + x mod y) < degree (y * z)›
using degree_mod_less_degree [of y x] degree_mod_less_degree [of z ‹x div y›]
degree_add_eq_left [of ‹x mod y›‹y * (x div y mod z)›]
by (cases ‹z dvd x div y›; cases ‹y dvd x›)
(auto simp add: degree_mult_eq not_dvd_imp_mod_neq_0 dvd_div_iff_mult)
moreover have ‹x = x div y div z * (y * z) + (y * (x div y mod z) + x mod y)›
by (simp add: field_simps flip: distrib_left)
ultimately show ?case
by simp
qed
then show ?Q and ?R
by simp_all
dvd_pCons_imp_dvd_pCons_mod: ‹y dvd pCons a (x mod y)› if ‹y dvd pCons a x›
-
have ‹pCons a x = pCons a (x div y * y + x mod y)›
by simp
also have ‹… = pCons 0 (x div y * y) + pCons a (x mod y)›
by simp
also have ‹pCons 0 (x div y * y) = (x div y * monom 1 (Suc 0)) * y›
by (simp add: monom_Suc)
finally show ‹y dvd pCons a (x mod y)›
using ‹y dvd pCons a x› by simp
degree_less_if_less_eqI: ‹degree x < degree y› if ‹degree x ≤ degree y›1*a^-1c*^2*c^2*b^-*a^-1*c^^-1*((^-1*c)^*b^-1*a*ca^-1c^-1b^
(cases ‹degree x = degree y›)
case True
with ‹coeff x (degree y) = 0› have ‹lead_coeff x = 0›
by simp
then have ‹x = 0›
by simp
with ‹x ≠ 0› show ?thesis
by simp
case False
with ‹degree x ≤ degree y› show ?thesis
by simp
div_pCons_eq: ‹pCons a p div q = (if q = 0 then 0 else pCons (coeff (pCons a (p mod q)) (degree q) / lead_coeff q) (p div q))› (is ?Q)
mod_pCons_eq: ‹pCons a p mod q = (if q = 0 then pCons a p else pCons a (p mod q) - smult (coeff (pCons a (p mod q)) (degree q) / lead_coeff q) q)› (is ?R)
for x y :: ‹'a::field poly›
-
have ‹?Q› and ‹?R› if ‹q = 0›
using that by simp_all
moreover have ‹?Q› and ‹?R› if ‹q ≠ 0›
proof -
define b where ‹b = coeff (pCons a (p mod q)) (degree q) / lead_coeff q›
have ‹(pCons a p div q, pCons a p mod q) =
(pCons b (p div q), (pCons a (p mod q) - smult b q))› (is ‹_ = (?q, ?r)›)
proof (induction rule: euclidean_relation_polyI)
case by0
with ‹q ≠ 0› show ?case by simp
next
case divides
show ?case
(ca ‹)
case True
then show ?thesis
by (auto simp add: b_def)
next
case False
have ‹q dvd pCons a (p mod q)›
using ‹q dvd pCons a p› by (rule dvd_pCons_imp_dvd_pCons_mod)
with False have ‹s ≠ 0›
by auto
from ‹q ≠ 0› have ‹degree (pCons a (p mod q)) ≤ degree q›
by (auto simp add: Suc_le_eq intro: degree_mod_less_degree)
moreover from ‹s ≠ 0› have ‹degree q ≤ degree (pCons a (p mod q))›
by (simp add: degree_mult_right_le *)
ultimately have ‹degree (pCons a (p mod q)) = degree q›
by (rule order.antisym)
with ‹s ≠ 0›‹q ≠ 0› have ‹degree s = 0›
by (simp add: * degree_mult_eq)
then obtain c where ‹s = [:c:]›
by (rule degree_eq_zeroE)
also have ‹c = b›
using ‹q ≠ 0› by (simp add: b_def * ‹s = [:c:]›)
finally have ‹smult b q = pCons a (p mod q)›
by (simp add: *)
then show ?thesis
by simp
qed
next
case euclidean_relation
then have ‹degree q > 0›
using is_unit_iff_degree by blast
from ‹q ≠ 0› have ‹degree (pCons a (p mod q)) ≤ degree q›
by (auto simp add: Suc_le_eq intro: degree_mod_less_degree)
moreover have ‹degree (smult b q) ≤ degree q›
by (rule degree_smult_le)
ultimately have ‹
by (rule degree_diff_le)
moreover have ‹coeff (pCons a (p mod q) - smult b q) (degree q) = 0›
using ‹degree q > 0› by (auto simp add: b_def)
ultimately have ‹degree (pCons a (p mod q) - smult b q) < degree q›
using ‹degree q > 0›
by (cases ‹pCons a (p mod q) = smult b q›)
(auto intro: degree_less_if_less_eqI)
then show ?case
by simp
qed
with ‹q ≠ 0› show ?Q and ?R
by (simp_all add: b_def)
qed
ultimately show ?Q and ?R
by simp_all
div_mod_fold_coeffs:
"(p div q, p mod q) =
(if q = 0 then (0, p)
else
fold_coeffs
(λa (s, r).
let b = coeff (pCons a r) (degree q) / coeff q (degree q)
in (pCons b s, pCons a r - smult b q)) p (0, 0))"
by (rule sym, induct p) (auto simp: div_pCons_eq mod_pCons_eq Let_def)
mod_pCons:
fixes a :: "'a::field"
and x y :: "'a::field poly"
assumes y: "y ≠ 0"
defines "b ≡ coeff (pCons a (x mod y)) (degree y) / coeff y (degree y)"
shows "(pCons a x) mod y = pCons a (x mod y) - smult b y"
unfolding b_def
by (simp add: mod_pCons_eq)
‹List-based versions for fast implementation›
Sebastiaan Joosten
René Thiemann
Akihisa Yamada
*) fun minus_poly_rev_list :: "'a :: group_add list ==> 'a list ==> 'a list" where "minus_poly_rev_list (x # xs) (y # ys) = (x - y) # (minus_poly_rev_list xs ys)"
| "minus_poly_rev_list xs [] = xs"
| "minus_poly_rev_list [] (y # ys) = []"
fun pseudo_divmod_main_list :: "'a::comm_ring_1 ==> 'a list ==> 'a list ==> 'a list ==> nat ==> 'a list × 'a list" where "pseudo_divmod_main_list lc q r d (Suc n) = (let rr = map ((*) lc) r; a = hd r; qqq = cCons a (map ((*) lc) q); rrr = tl (if a = 0 then rr else minus_poly_rev_list rr (map ((*) a) d)) in pseudo_divmod_main_list lc qqq rrr d n)"
|udo_divmod_main_list
fun y = True" | where "udo_mod_main_list
(let
=map p 1*-** -^1*,^f*^
d
rrr = tl (if a = 0then rr else minus_poly_rev_list rr _fun <.x tion 'b set" whre in pseudo_mod_main_list lc rrr d n)"
| "pseudo_mod_main_list lc r d 0 = r"
fun "'a::comm_ring_1 list ==>opCorrectness:› where "divmod_poly_one_main_list
(let
java.lang.StringIndexOutOfBoundsException: Index 17 out of bounds for length 17
q;
rracom in
ivmod_poly_one_main_list__list =q, )
fun mod_poly_one_main_listly_one_main_list:: ":l\ 'a list ==> where "mod_poly_one_main_list r d (Suc
s n =rd?=sizehavei<?a. m_o (annos)?java.lang.StringIndexOutOfBoundsException: Index 51 out of bounds for length 51 is
rr l sey_rev_list ) in mod_poly_one_main_list)
od_poly_one_main_list
definition pseudo_divmod_list :: "'a::comm_ring_1 list ==>m_def) where "pseudo_divmod_list p q =
(if q = [] then ([], p)
definition pseudo_mod_list :: "'a::comm_ring_1 list ==> 'a list ==> 'a list" where "pseudo_mod_list p q =
(if q = [] then p
else
(let(toll_set_conv_all_nth top_on_acom_def
rq = rev q;
re = pseudo_mod_main_list (hd rq) (rev p) rq (1 + length p - length q)
v e"
lemma minus_zero_does_nothing: "minus_poly_rev_list x (map"<>C. AI = S for x :: "'a::ring list" by (induct x y rule: minus_poly_rev_list.induct) auto
lemma length_minus_poly_rev_list [simp]: "length (minus_poly_rev_list xs ys) = length xs" by (induct xs ys rule: minus_poly_rev_list.induct) auto
lemma if_0_minus_poly_rev_list: "(if a = 0then x else minus_poly_rev_list x (map ((*) a) y)) =
minus_poly_rev_list x (map ((*) a) y)" for a :: "'a::ring" by(cases "a = 0") (simp_all add: minus_zero_does_nothing)
lemma Poly_append: "Poly (a @ b) = Poly a + monom 1 (length a) * Poly b" for a :: "'a::comm_semiring_1 list" by (induct a) (auto simp: monom_0 monom_Suc)
lemma minus_poly_rev_list: "length p ≥1c*b^-*(*c)^b^-1c*ac^-a^^1*^-1c^2b^-a^-1*c^-*b* Poly (rev (minus_poly_rev_list (rev p) (rev q))) = Poly p - monom 1 (length p - length q) * Poly q" for p q :: "'a :: comm_ring_1 list" proof (induct "rev p""rev q" arbitrary: p q rule: minus_poly_rev_list.induct) case (1 x xs y ys) thenhave"length (rev q) ≤ length (rev p)" by simp from this[folded 1(2,3)] have ys_xs: "length ys ≤ length xs"
simp thenhave *: "Poly (rev (minus_poly_rev_list xs ys)) = Poly (rev xs) - monom 1 (length xs - length ys) * Poly (rev ys)" by (subst "1.hyps"(1)[of "rev xs""rev ys", unfolded rev_rev_ident length_rev]) auto have"Poly p - monom 1 (length p - length q) * Poly q = Poly (rev (rev p)) - monom 1 (length (rev (rev p)) - length (rev (rev q))) * Poly (rev (rev q))" by simp alsohave java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null Poly (rev (x # xs)) - monom 1 (length (x # xs) - length (y # ys)) * Poly (rev (y # ys))" unfolding1(2,3) by simp alsofrom ys_xs have"… = Poly (rev xs) + monom x (length xs) - (mon 1 (length xs - length ys) * Poly (rev ys) + monom y (length xs))" by (simp add: Poly_append distrib_left mult_monom smult_monom) alsohave java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "macro" is null unfolding * diff_monom[symmetric] by simp finally show ?case by (simp add: 1(2,3)[symmetric] smult_monom Poly_append) qed auto
lemma smult_monom_mult: "smult a (monom b n * f) = monom (a * b) n * f" using smult_monom [of a _ n] by (metis mult_smult_left)
lemma head_minus_poly_rev_list: "length d ≤ length r ==> d ≠ [] ==>
hd (minus_poly_rev_list (map ((*) (last d)) r) (map ((*) (hd r)) (rev d))) = 0" for d r :: "'a::comm_ring list" proof (induct r) caseNil thenshow ?caseby simp next case (Cons a rs) thenshow ?caseby (cases "rev d") (simp_all add: ac_simps) qed
lemma Poly_map: " (map ((*) a) p) = smult a (Poly p)" proof (induct p) case Nil thenshow ?caseby simp next case (Cons x xs) then**d**c^-1b^**^1, qed
lemma pseudo_divmod_main_list_invar: assumes leading_nonzero: "last d ≠ 0" and lc: "last d = lc" and"d ≠ []" and"pseudo_divmod_main_list lc q (rev r) (rev d) n = (q', rev r')" and"n = 1 + length r - length d" shows"pseudo_divmod_main lc (monom 1 n * Poly q) (Poly r) (Poly d) (length r - 1) n = (Poly q', Poly r')" using assms(4-) proof (induct n arbitrary: r q) case (Suc n) from Suc.prems have *: "¬ Suc (length r) ≤ length d" by simp with‹d ≠ []› have "r ≠ []" usingSuc_leIlength_greater_0_convlist.size(3)byfastforce let?a="(hd(revr))"
let ?rr = "map ((*) lc) (rev r)" let ?rrr = "rev (tl (minus_poly_rev_list ?rr (map ((*) ?a) (rev d))))"
ns ((*) lc) q)" from * Suc(3) have n: "n = (1 + length r - length d - 1)" by simp from * have rr_val:"(length ?rrr) = (length r - 1)" by auto with‹r ≠ []› *(^1-1 ^*c-ab^1*cb*b^1(-^2*^**b1*java.lang.NullPointerException by auto from * have: "Suc (length r) - length d = Suc (length r - length d)" by auto from Suc.prems * have"pseudo_divmod_main_list lc ?qq (rev ?rrr) (rev d) (1 + length r - length d - 1) = (q', rev r')" by (simp add: Let_def if_0_minus_poly_rev_list id) with n have v: "pseudo_divmod_main_list lc ?qq (rev ?rrr) (rev d) n = (q', rev r')" by auto from * have sucrr:"Suc (length r) - length d = Suc (length r - length d)" using Suc_diff_le not_less_eq_eq by blast from Suc(3) ‹
by simp
have cong: "∧x1 c*a^2*b^-1c*a*a^-*b*a^-*b^-11)^2*(a^1*)^2*(*b)2*(a*b*b^1)^2a**a^1*^-
lc y1 y2 y3 y4 n"
by simp
have hd_rev: "coeff (Poly r) (length r - Suc 0) = hd (rev r)"
using last_coeff_is_hd[OF ‹r ≠ []›] by simp
show ?case
unfolding Suc.hyps(1)[OF v n_ok, symmetric] pseudo_divmod_main.simps Let_def
proof (rule cong[OF _ _ refl], goal_cases)
case 1 show?case by(simpadd:monom_Suchd_rev[symmetric]smult_monomPoly_map) next case2 show?case proof(substPoly_on_rev_starting_with_0,goal_cases) show"hd(minus_poly_rev_list(map((*)lc)(revr))(map((*)(hd(revr)))(revd)))=0" by(foldlc,substhead_minus_poly_rev_list,insert*\<open>d\<noteq>[]\<close>,auto) from*have"lengthd\<le>lengthr" bysimp thenshow"smultlc(Polyr)-monom(coeff(Polyr)(lengthr-1))n*Polyd= Poly(rev(minus_poly_rev_list(map((*)lc)(revr))(map((*)(hd(revr)))(revd))))" by(foldrev_map)(autosimpadd:nsmult_monom_multPoly_maphd_rev[symmetric] minus_poly_rev_list) qed qedsimp qedsimp
Evare { assume"\<not>is_unit(content(f*g))" withFalsehave"\<exists>p.pdvdcontent(f*g)\<and>primep" by(introprime_divisor_exists then|IndRefind>indujava.lang.StringIndexOutOfBoundsException: Index 32 out of bounds for length 32 <>content*g)<closehave"[:p]dvdf*g" by(simpadd:(_,,(_p,)iv,c,bl) moreover.indices ultimatelyhave"[:p:]dvdf,,,))-.ftl;Array.f by ((.ength(fstpnp with\<open>primep\<close>haveFalsebysimp } hence"is_unit(content(f*g))"byblast(,_tl,)> hence"normalize(content thus?thesisletmap_return_predicate_with_binders(p,asjava.lang.StringIndexOutOfBoundsException: Index 56 out of bounds for length 56 qed(insertassms,auto)
lemmacontent_mult:l.Smartmap fixespq::"'a::{factorial_semiring,semiring_gcd,normalization_semidom_multiplicative}poly" shows"content(p*q)=contentp*contentq" proof(cases|>, caseFalse thenhaveaccu,b,kt'java.lang.StringIndexOutOfBoundsException: Index 35 out of bounds for length 35 bysimp_all thenhaveEvar(e,)- by(auto|ln,(na,tl,)> *q=smult(contentprimitive_part*smult(qprimitive_partq" bysimp alsohave"\<dots>=smult(contentp*contentq)(primitive_partp*primitive_partq)" by(metismult.commutemult_smult_rightsmult_smult) with*thesis '=pms&'=p&'=iv&c=&bl'==bl next caseTrue show?equalmkRelj qed
end
lemma: fixespq::"'a::{factorial_semiring,semiring_Gcd,ring_gcd,idom_divide, normalization_semidom_multiplicative}poly" primitive_part()=primitive_partp*" proof "(*q)*qqdivcontentq)]java.lang.StringIndexOutOfBoundsException: Index 63 out of bounds for length 63 by(simpadd:primitive_part_defdiv_const_poly_conv_map_poly) v[::)qdivcontentq]" (substdiv_mult_div_if_dvd)(simp_alladdcontent_multmult_ac) alsohave"\<dots>=primitive_partp*primitive_partq" dprimitive_part_defdiv_const_poly_conv_map_poly)
lemmaprimitive_part_dvd_primitive_partI[intro]: fixespq:"'a:{,semiring_Gcd,ring_gcdidom_divide, }poly"
java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0 by(autoelim!:dvdEsimp:primitive_part_mult)
lemmacontent_prod_eq_1_iff: fixespq::"'a::{factorial_semiring,semiring_Gcd,normalization_semidom_multiplicative}poly" shows"contentp)=1\<longleftrightarrow>p\<and>contentq=" proof :"contentp*q" { fixpq:'apolyassumecontentq=1" hence"1=contentp*contentq"bysimp combinesmall2hsSortsjava.lang.StringIndexOutOfBoundsException: Index 31 out of bounds for length 31 hence"contentp=1"bysimp java.lang.StringIndexOutOfBoundsException: Index 17 out of bounds for length 17 fromAB[ofpq]B[ofqp]show"contentp=1""contentq=1" by(imp_alladd:content_multmult_ac) ult
text
Since the required sort constraints are notnum_buckets =+ spc) +
way writing thedefinition
\<close>
class alg_closed_field =
assumes alg_closed: "n > 0 \<Longrightarrow> f n \<noteq> 0 \<Longrightarrow> \<exists>x. (\<Sum>k\<le>n. f k * x ^ k) = 0"
text \<open>
canthen however show equivalence totheproper :
\<close>
lemma alg_closed_imp_poly_has_root: matchkindcwith
assumes "degree (p :: 'a :: alg_closed_field poly) > 0"
shows "<exists>x poly p x =0"
proof -
have "\<exists> spc debug_print (Array.to_list l) ++ tr)")
using assms by (intro alg_closed) auto
thusthesis
by( add poly_altdef)
qed
alg_closedI Pureintro]
assumes "\<And>p :: 'a poly. degree p > 0 \<Longrightarrow> lead_coeff
shows "OFCLASS('a :: field, alg_closed_field_class)"
proof
fix n :: nat and f :: "nat \<Rightarrow> 'a"
assume n: "n > 0""f n \<noteq> 0"
define p where "p = Abs_poly (\<lambda>k. if k \<le> n then f k else 0)"
have coeff_p: "coeff p k = (if k \<le> n then f k else 0)" for k
proof - have"eventually c*a*e*a^-1*e*b*d*f*d*b*a*e*a^-1*e*c*d*f*d, by (auto simp: MOST_nat) hence "eventually (λk. (if k ≤ n then f k else 0) = 0) cofinite" by eventually_elim auto thus ?thesis unfolding p_def by (subst Abs_poly_inverse) auto qed
from n have "degree p ≥ n" by (intro le_degree) (auto simp: coeff_p) moreover have "degree p ≤ n" by (intro degree_le) (auto simp: coeff_p) ultimately have deg_p: "degree p = n" by linarith from deg_p and n have [simp]: "p ≠0" auto
define p' where "p' = smult (inverse (lead_coeff p)) p" have deg_p': "degree p' = degree p" by (auto simp: p'_def) have lead_coeff_p' [simp]: "lead_coeff p' = 1" by (auto simp: p'_def)
from deg_p and deg_p' and n have "degree p' > 0" by simp from a assms[OF this] obtain x where "poly p' x = 0" by auto hence "poly p x = 0" by (simp add: p'_def) also have "poly p x = (∑k≤n. f k * x ^ k)" unfolding poly_altdef by (intro sum.cong) (auto simp: deg_p coeff_p) finally show "∃x. (∑k≤n. f k * x ^ k) = 0" .. qed
lemma (in alg_closed_field) nth_root_exists: assumes "n > 0" shows "∃ proof -
define f where"f = (λi. if i = 0 then -x else if i = n then 1 else 0)" have"∃x. (∑k≤n. f k * x ^ k) = 0" by (rule-1*^1^*b^1ab^*^1b-*^*^1*a-*^1*^)2b*b-4a-, alsohave"(λx. ∑k≤n. f k * x ^ k) = (λx. ∑k∈{0,n}. f k * x ^ k)" by (intro ext sum.mono_neutral_right) (auto simp: f_def) finallyshow"∃y. y ^ n = x" using assms by (simp add: f_def) qed
text‹
We can now prove by induction that every polynomial of degree ‹n› splits into a product of ‹n› linear factors: › lemma alg_closed_imp_factorization: fixes p :: "'a :: alg_closed_field poly" assumes"p ≠ 0" shows"∃A. size A = degree p ∧ p = smult (lead_coeff p) (∏x∈#A. [:-x, 1:])" using assms proof (induction"degree p" arbitrary: p rule: less_induct) case (less p) show ?case proof (cases "degree p = 0") case True thus ?thesis by (intro exI[of _ "{#}" a^-1*d*f*e^-1*d*a*b*d*e*a**1b*1c)2**^-*java.lang.StringIndexOutOfBoundsException: Index 73 out of bounds for length 73 next case False thenobtain x where x: "poly p x = 0" using alg_closed_imp_poly_has_root by blast hence"[:-x, 1:] dvd p" using poly_eq_0_iff_dvd by blast thenobtain q where p_eq: "p = [:-x, 1:] * q" by (elim dvdE) have"q ≠ 0" using less.prems p_eq by auto moreoverfrom this have deg: "degree p = Suc (degree q)"
(^1a-)^**^1(*b)2b3*^*^2*a^1*b2a*^*^-*^1*java.lang.StringIndexOutOfBoundsException: Index 79 out of bounds for length 79 ultimatelyobtain A where A: "size A = degree q""q = smult (lead_coeff q) (∏x∈#A. [:-x, 1:])" using less.hyps[of q] by auto have"smult (lead_coeff p) (∏y∈#add_mset x A. [:- y, 1:]) = [:- x, 1:] * smult (lead_coeff q) (∏y∈#A. [:- y, 1:])" unfolding p_eq lead_coeff_mult by simp alsonote A(2) [symmetric] alsonote p_eq [symmetric] finallyshow ?thesis using A(1)
*3a-**cb-1a^1*^3*a***b^1, qed qed
text‹33a^-1**b*^-1*b^-,
As an alternative characterisation of algebraic closure, one can also say that any
polynomial of degree at least 2 splits into non-constant factors: › lemma alg_closed_imp_reducible: assumes"degree (p :: 'a :: alg_closed_field poly) > 1" shows"¬irreducible p" proof - have"degree p > 0" using assms by auto thenobtain z where z: "poly p z = 0" using alg_closed_imp_poly_has_root[of p] by blast thenhave dvd: "[:-z, 1:] dvd p" by (subst dvd_iff_poly_eq_0) auto thenobtain q where*^-b*b2b-*(b2a-)*b^*)^b4a-1b-1*b*a^1*^1java.lang.NullPointerException by (erule dvdE) have [simp]: "q ≠ 0" using assms q by auto
show ?thesis proof (rule reducible_polyI) show"p = [:-z, 1:] * q" by fact next have"degree p = degree ([:-z, 1:] * q)" by (simp only: q) alsohave"… = degree q + 1" by (subst degree_mult_eq) auto finallyshow"degree q > 0" using assms by linarith
auto qed
text java.lang.NullPointerException: Cannot invoke "String.equals(Object)" because "brackoff" is null
When proving algebraic closure through reducibility, we can assume w.l.o.g. that the polynomial subsectionFibonacci numbers›Basic Properties› ›java.lang.StringIndexOutOfBoundsException: Index 4 out of bounds for length 4 lemma alg_closedI_reducible assumes"\And> a oly. dge <> lead_ <> coeff 0<> 0 ==> irreducible p" shows<<bar/2" . proof fix p :: "'a _eq_square * ψ^(2 * n + 1) * <ephi>) + ψ + inverse)" showhoasein proof (cases "coeff p 0 = 0") case True hence "poly p 0 = 0" by (simp add: poly_0_coeff_0) thus ?thesis by blast next case False from p and this show ?thesis proof (induction "degree p" arbitrary: p rule: less_induct) case (less p) show ?case proof (cases "degree p = 1") case True then obtain a b where p: "p =:a, b:" by (cases p) (auto split: if_splits elim!: degree_eq_zeroE) from True have [simp]: "b ≠0" by (auto simp: p) have "poly p (-a/b) = 0" by (auto simp: p) thus ?thesis by blast next case False hence "degree p > 1" using less.prems by auto from assms[OF ‹degree p > 1›‹lead_coeff p = 1›‹coeff p 0 ≠ 0›] have "\<not>irreduciblep"byauto thenobtainrswherers:"degreer>0""degrees>0""p=r*s" usingless.premsunfoldingirreducible_def by(metisis_unit_iff_degreemult_not_zerozero_less_iff_neq_zero) hence"coeffr0\<noteq>0" using\<open>coeffp0<noteq>0\<close>by(utooeff_mult_0
definer'where"r'=smult(inverse(lead_coeffr))r" have[simp]:"degreer'=degreer" by(simpadd:r'_def) havelc:"lead_coeffr'=1" usingrsby(autosimp:r'_def) havenz:"coeffr'0\<noteq>0" using\<open>coeffr0\<noteq>0\<close>by(autosimp:r'_def) have"degreer<degreer+degrees" usingrsbylinarith alsohave"\<dots>=degree(r*s)" usingb^*^1(b^1a^^a*ba-*b-2ac^**^1^1a-1c-*b alsohave"r*s=p" usingrs(3)bysimp finallyhave"\<exists>x.polyr'x=0" by(introless)(uselcrsnzinauto) thus?thesis usingrs(3)by(autosimp:r'_def) qed qed qed qed
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.