# Theory Sturm_Rat

section ‹Separation of Roots: Sturm›
text ‹We adapt the existing theory on Sturm's theorem to work on rational numbers instead of real
numbers. The reason is that we want to implement real numbers as real algebraic numbers with the
help of Sturm's theorem to separate the roots. To this end, we just copy the definitions of
of the algorithms w.r.t. Sturm and let them be executed on rational numbers. We then
prove that corresponds to a homomorphism and therefore can transfer the existing soundness results.›
theory Sturm_Rat
imports
Sturm_Sequences.Sturm_Theorem
Algebraic_Numbers_Prelim
Berlekamp_Zassenhaus.Square_Free_Int_To_Square_Free_GFp
begin
hide_const (open) UnivPoly.coeff
lemma root_primitive_part [simp]:
fixes p :: "'a :: {semiring_gcd, semiring_no_zero_divisors} poly"
shows "poly (primitive_part p) x = 0 ⟷ poly p x = 0"
proof(cases "p = 0")
case True
then show ?thesis by auto
next
case False
have "poly p x = content p * poly (primitive_part p) x"
by (metis content_times_primitive_part poly_smult)
also have "… = 0 ⟷ poly (primitive_part p) x = 0" by (simp add: False)
finally show ?thesis by auto
qed
lemma irreducible_primitive_part:
assumes "irreducible p" and "degree p > 0"
shows "primitive_part p = p"
using irreducible_content[OF assms(1), unfolded primitive_iff_content_eq_1] assms(2)
by (auto simp: primitive_part_def abs_poly_def)
subsection ‹Interface for Separating Roots›
text ‹For a given rational polynomial, we need to know how many real roots are in a given closed interval,
and how many real roots are in an interval $(-\infty,r]$.›