Documentation

Mathlib.RingTheory.Polynomial.Resultant.Basic

Resultant of two polynomials #

This file contains basic facts about resultant of two polynomials over commutative rings.

Main definitions #

TODO #

def Polynomial.sylvester {R : Type u_1} [Semiring R] (f g : Polynomial R) (m n : ) :
Matrix (Fin (m + n)) (Fin (m + n)) R

The Sylvester matrix of two polynomials f and g of degrees m and n respectively is a (m+n) × (m+n) matrix with the coefficients of f and g arranged in a specific way. Here, m and n are free variables, not necessarily equal to the actual degrees of the polynomials f and g.

Note that the natural definition would be a Matrix (Fin (m + n)) (Fin m ⊕ Fin n) R but we prefer having this as a square matrix to take determinants later on.

Equations
    Instances For
      @[simp]
      theorem Polynomial.sylvester_zero_left_deg {R : Type u_1} [Semiring R] (f g : Polynomial R) (m : ) :
      f.sylvester g 0 m = Matrix.diagonal fun (x : Fin (0 + m)) => f.coeff 0
      theorem Polynomial.sylvester_map_map {R : Type u_1} {S : Type u_2} [Semiring R] [Semiring S] (f g : Polynomial R) (m n : ) (φ : R →+* S) :
      (map φ f).sylvester (map φ g) m n = φ.mapMatrix (f.sylvester g m n)
      noncomputable def Polynomial.sylvesterDeriv {R : Type u_1} [Semiring R] (f : Polynomial R) :

      The Sylvester matrix for f and f.derivative, modified by dividing the bottom row by the leading coefficient of f. Important because its determinant is (up to a sign) the discriminant of f.

      Equations
        Instances For

          We can get the usual Sylvester matrix of f and f.derivative back from the modified one by multiplying the last row by the leading coefficient of f.

          def Polynomial.resultant {R : Type u_1} [CommRing R] (f g : Polynomial R) (m : := f.natDegree) (n : := g.natDegree) :
          R

          The resultant of two polynomials f and g is the determinant of the Sylvester matrix of f and g. The size arguments m and n are implemented as optParam, meaning that the default values are f.natDegree and g.natDegree respectively, but they can also be specified to be other values.

          Equations
            Instances For
              @[simp]
              theorem Polynomial.resultant_map_map {R : Type u_1} {S : Type u_2} [CommRing R] [CommRing S] (f g : Polynomial R) (m n : ) (φ : R →+* S) :
              (map φ f).resultant (map φ g) m n = φ (f.resultant g m n)
              @[simp]
              theorem Polynomial.resultant_zero_left_deg {R : Type u_1} [CommRing R] (f g : Polynomial R) (m : ) :
              f.resultant g 0 m = f.coeff 0 ^ m
              theorem Polynomial.resultant_C_zero_left {R : Type u_1} [CommRing R] (g : Polynomial R) (r : R) (m : ) :
              (C r).resultant g 0 m = r ^ m

              For polynomial f and constant a, Res(f, a) = a ^ m.

              theorem Polynomial.resultant_comm {R : Type u_1} [CommRing R] (f g : Polynomial R) (m n : ) :
              f.resultant g m n = (-1) ^ (m * n) * g.resultant f n m

              Res(f, g) = (-1)ᵐⁿ Res(g, f)

              @[simp]
              theorem Polynomial.resultant_zero_right_deg {R : Type u_1} [CommRing R] (f g : Polynomial R) (m : ) :
              f.resultant g m 0 = g.coeff 0 ^ m
              theorem Polynomial.resultant_C_zero_right {R : Type u_1} [CommRing R] (f : Polynomial R) (m : ) (r : R) :
              f.resultant (C r) m 0 = r ^ m

              Res(a, g) = a ^ deg g

              @[simp]
              theorem Polynomial.resultant_zero_right {R : Type u_1} [CommRing R] (f : Polynomial R) (m n : ) :
              f.resultant 0 m n = 0 ^ m * f.coeff 0 ^ n
              @[simp]
              theorem Polynomial.resultant_zero_left {R : Type u_1} [CommRing R] (g : Polynomial R) (m n : ) :
              resultant 0 g m n = 0 ^ n * g.coeff 0 ^ m
              theorem Polynomial.resultant_zero_zero {R : Type u_1} [CommRing R] (m n : ) :
              resultant 0 0 m n = 0 ^ (m + n)
              theorem Polynomial.resultant_add_mul_right {R : Type u_1} [CommRing R] (f g p : Polynomial R) (m n : ) (hp : p.natDegree + m n) (hf : f.natDegree m) :
              f.resultant (g + f * p) m n = f.resultant g m n

              Res(f, g + fp) = Res(f, g) if deg f + deg p ≤ deg g.

              theorem Polynomial.resultant_add_mul_left {R : Type u_1} [CommRing R] (f g p : Polynomial R) (m n : ) (hk : p.natDegree + n m) (hg : g.natDegree n) :
              (f + g * p).resultant g m n = f.resultant g m n

              Res(f + gp, g) = Res(f, g) if deg g + deg p ≤ deg f.

              theorem Polynomial.resultant_C_mul_right {R : Type u_1} [CommRing R] (f g : Polynomial R) (m n : ) (r : R) :
              f.resultant (C r * g) m n = r ^ m * f.resultant g m n

              Res(f, a • g) = a ^ {deg f} * Res(f, g).

              theorem Polynomial.resultant_C_mul_left {R : Type u_1} [CommRing R] (f g : Polynomial R) (m n : ) (r : R) :
              (C r * f).resultant g m n = r ^ n * f.resultant g m n

              Res(a • f, g) = a ^ {deg g} * Res(f, g).

              theorem Polynomial.resultant_succ_left_deg {R : Type u_1} [CommRing R] (f g : Polynomial R) (m n : ) (hf : f.natDegree m) :
              f.resultant g (m + 1) n = (-1) ^ n * g.coeff n * f.resultant g m n
              theorem Polynomial.resultant_add_left_deg {R : Type u_1} [CommRing R] (f g : Polynomial R) (m n k : ) (hf : f.natDegree m) :
              f.resultant g (m + k) n = (-1) ^ (n * k) * g.coeff n ^ k * f.resultant g m n
              theorem Polynomial.resultant_add_right_deg {R : Type u_1} [CommRing R] (f g : Polynomial R) (m n k : ) (hg : g.natDegree n) :
              f.resultant g m (n + k) = f.coeff m ^ k * f.resultant g m n
              theorem Polynomial.resultant_eq_zero_of_lt_lt {R : Type u_1} [CommRing R] (f g : Polynomial R) (m n : ) (hf : f.natDegree < m) (hg : g.natDegree < n) :
              f.resultant g m n = 0
              @[simp]
              theorem Polynomial.resultant_C_left {R : Type u_1} [CommRing R] (g : Polynomial R) (m n : ) (r : R) :
              (C r).resultant g m n = (-1) ^ (m * n) * g.coeff n ^ m * r ^ n
              @[simp]
              theorem Polynomial.resultant_C_right {R : Type u_1} [CommRing R] (f : Polynomial R) (m n : ) (r : R) :
              f.resultant (C r) m n = f.coeff m ^ n * r ^ m
              @[simp]
              theorem Polynomial.resultant_one_left {R : Type u_1} [CommRing R] (g : Polynomial R) (m n : ) :
              resultant 1 g m n = (-1) ^ (m * n) * g.coeff n ^ m
              @[simp]
              theorem Polynomial.resultant_one_right {R : Type u_1} [CommRing R] (f : Polynomial R) (m n : ) :
              f.resultant 1 m n = f.coeff m ^ n
              @[simp]
              theorem Polynomial.resultant_X_sub_C_left {R : Type u_1} [CommRing R] (g : Polynomial R) (n : ) (r : R) (hg : g.natDegree n) :
              (X - C r).resultant g 1 n = eval r g

              Res(X - r, g) = g(r)

              @[simp]
              theorem Polynomial.resultant_X_add_C_left {R : Type u_1} [CommRing R] (g : Polynomial R) (n : ) (r : R) (hg : g.natDegree n) :
              (X + C r).resultant g 1 n = eval (-r) g

              Res(X + r, g) = g(-r)

              @[simp]
              theorem Polynomial.resultant_X_sub_C_right {R : Type u_1} [CommRing R] (f : Polynomial R) (m : ) (r : R) (hf : f.natDegree m) :
              f.resultant (X - C r) m 1 = (-1) ^ m * eval r f

              Res(f, X - r) = (-1)^{deg f} * f(r)

              @[simp]
              theorem Polynomial.resultant_X_add_C_right {R : Type u_1} [CommRing R] (f : Polynomial R) (m : ) (r : R) (hf : f.natDegree m) :
              f.resultant (X + C r) m 1 = (-1) ^ m * eval (-r) f

              Res(f, X + r) = (-1)^{deg f} * f(-r)

              theorem Polynomial.resultant_eq_prod_roots_sub {K : Type u_3} [Field K] (f g : Polynomial K) (hf : f.Monic) (hg : g.Monic) (hf' : f.Splits) (hg' : g.Splits) :
              f.resultant g = (Multiset.map (fun (ij : K × K) => ij.1 - ij.2) (f.roots ×ˢ g.roots)).prod

              If f and g are monic and splits, then Res(f, g) = ∏ (α - β), where α and β runs through the roots of f and g respectively.

              theorem Polynomial.resultant_eq_prod_eval {R : Type u_1} [CommRing R] [IsDomain R] (f g : Polynomial R) (n : ) (hg : g.natDegree n) (hf : f.Splits) :
              f.resultant g f.natDegree n = f.leadingCoeff ^ n * (Multiset.map (fun (x : R) => eval x g) f.roots).prod

              If f splits with leading coeff a and degree n, then Res(f, g) = aⁿ * ∏ g(α) where α runs through the roots of f.

              theorem Polynomial.induction_of_Splits_of_injective_of_surjective {R : Type u} [CommRing R] (p : Polynomial R) (P : {R : Type u} → [inst : CommRing R] → Polynomial RProp) (Splits : ∀ (R : Type u) [inst : Field R] (p : Polynomial R), p.SplitsP p) (injective : ∀ (R S : Type u) [inst : CommRing R] [inst_1 : CommRing S] (φ : R →+* S), Function.Injective φ∀ (p : Polynomial R), P (map φ p)P p) (surjective : ∀ (R S : Type u) [inst : CommRing R] [inst_1 : CommRing S] (φ : R →+* S), Function.Surjective φ∀ (p : Polynomial S), (∀ (q : Polynomial R), P q)P p) :
              P p

              An induction principle useful to prove statements about resultants. Let P be a predicate on a polynomial. If R → S injective implies (∀ p : S[X], P p) → (∀ p : R[X], P p), and if R → S surjective implies (∀ p : R[X], P p) → (∀ p : S[X], P p), then we may reduce to the case where R is a field and p splits.

              theorem Polynomial.resultant_mul_right {R : Type u_1} [CommRing R] (f g₁ g₂ : Polynomial R) (m : ) (hm : f.natDegree m) :
              f.resultant (g₁ * g₂) m (g₁.natDegree + g₂.natDegree) = f.resultant g₁ m * f.resultant g₂ m

              Res(f, g₁ * g₂) = Res(f, g₁) * Res(f, g₂).

              theorem Polynomial.resultant_mul_left {R : Type u_1} [CommRing R] (f₁ f₂ g : Polynomial R) (n : ) (hn : g.natDegree n) :
              (f₁ * f₂).resultant g (f₁.natDegree + f₂.natDegree) n = f₁.resultant g f₁.natDegree n * f₂.resultant g f₂.natDegree n

              Res(f₁ * f₂, g) = Res(f₁, g) * Res(f₂, g).

              @[simp]
              theorem Polynomial.resultant_self {R : Type u_1} [CommRing R] (f : Polynomial R) :

              Res(f, f) = 0 unless deg f = 0. Also see resultant_self_eq_zero.

              theorem Polynomial.resultant_ne_zero {R : Type u_1} [CommRing R] [IsDomain R] (f g : Polynomial R) (H : IsCoprime f g) :
              @[simp]
              theorem Polynomial.resultant_prod_left {R : Type u_1} [CommRing R] {ι : Type u_3} (s : Finset ι) (f : ιPolynomial R) (g : Polynomial R) (n : ) (hf : is, (f i).leadingCoeff 0) (hn : g.natDegree n) :
              (∏ is, f i).resultant g (∏ is, f i).natDegree n = is, (f i).resultant g (f i).natDegree n
              @[simp]
              theorem Polynomial.resultant_prod_right {R : Type u_1} [CommRing R] {ι : Type u_3} (s : Finset ι) (f : Polynomial R) (g : ιPolynomial R) (m : ) (hm : f.natDegree m) (hg : is, (g i).leadingCoeff 0) :
              f.resultant (∏ is, g i) m = is, f.resultant (g i) m
              @[simp]
              theorem Polynomial.resultant_pow_left {R : Type u_1} [CommRing R] (f g : Polynomial R) (m n : ) (hf : f.leadingCoeff ^ m 0) (hn : g.natDegree n) :
              (f ^ m).resultant g (f ^ m).natDegree n = f.resultant g f.natDegree n ^ m
              @[simp]
              theorem Polynomial.resultant_pow_right {R : Type u_1} [CommRing R] (f g : Polynomial R) (m n : ) (hm : f.natDegree m) (hg : g.leadingCoeff ^ n 0) :
              f.resultant (g ^ n) m = f.resultant g m ^ n
              theorem Polynomial.resultant_X_sub_C_pow_left {R : Type u_1} [CommRing R] (r : R) (g : Polynomial R) (m n : ) (hn : g.natDegree n) :
              ((X - C r) ^ m).resultant g m n = eval r g ^ m
              theorem Polynomial.resultant_X_sub_C_pow_right {R : Type u_1} [CommRing R] (f : Polynomial R) (r : R) (m n : ) (hm : f.natDegree m) :
              f.resultant ((X - C r) ^ n) m n = (-1) ^ (m * n) * eval r f ^ n
              theorem Polynomial.resultant_X_pow_left {R : Type u_1} [CommRing R] (g : Polynomial R) (m n : ) (hn : g.natDegree n) :
              (X ^ m).resultant g m n = g.coeff 0 ^ m
              theorem Polynomial.resultant_X_pow_right {R : Type u_1} [CommRing R] (f : Polynomial R) (m n : ) (hm : f.natDegree m) :
              f.resultant (X ^ n) m n = (-1) ^ (m * n) * f.coeff 0 ^ n
              theorem Polynomial.resultant_taylor {R : Type u_1} [CommRing R] (f g : Polynomial R) (r : R) :
              ((taylor r) f).resultant ((taylor r) g) = f.resultant g

              Res(f(x + r), g(x + r)) = Res(f, g).

              noncomputable def Polynomial.sylvesterMap {m n : } {R : Type u_1} [CommRing R] (f g : Polynomial R) (hf : f.natDegree m) (hg : g.natDegree n) :
              (degreeLT R m) × (degreeLT R n) →ₗ[R] (degreeLT R (m + n))

              The map (p, q) ↦ f * q + g * p whose associated matrix is Syl(f, g).

              Equations
                Instances For
                  @[simp]
                  theorem Polynomial.sylvesterMap_apply_coe {m n : } {R : Type u_1} [CommRing R] (f g : Polynomial R) (hf : f.natDegree m) (hg : g.natDegree n) (pq : (degreeLT R m) × (degreeLT R n)) :
                  ((f.sylvesterMap g hf hg) pq) = f * pq.2 + g * pq.1
                  noncomputable def Polynomial.adjSylvester {m n : } {R : Type u_1} [CommRing R] (f g : Polynomial R) :
                  (degreeLT R (m + n)) →ₗ[R] (degreeLT R m) × (degreeLT R n)

                  The adjugate map of the sylvester map. It takes P to (p, q) such that f * q + g * p = Res(f, g) * P.

                  Equations
                    Instances For
                      theorem Polynomial.exists_mul_add_mul_eq_C_resultant {m n : } {R : Type u_1} [CommRing R] (f g : Polynomial R) (hf : f.natDegree m) (hg : g.natDegree n) (H : m 0 n 0) :
                      ∃ (p : Polynomial R) (q : Polynomial R), p.degree < n q.degree < m f * p + g * q = C (f.resultant g m n)

                      Note that if n = m = 0 then resultant = 1 but f and g aren't necessarily coprime.

                      noncomputable def Polynomial.discr {R : Type u_1} [CommRing R] (f : Polynomial R) :
                      R

                      The discriminant of a polynomial, defined as the determinant of f.sylvesterDeriv modified by a sign. The sign is chosen so polynomials over with all roots real have non-negative discriminant.

                      Equations
                        Instances For
                          @[deprecated Polynomial.discr (since := "2025-10-20")]
                          def Polynomial.disc {R : Type u_1} [CommRing R] (f : Polynomial R) :
                          R

                          Alias of Polynomial.discr.


                          The discriminant of a polynomial, defined as the determinant of f.sylvesterDeriv modified by a sign. The sign is chosen so polynomials over with all roots real have non-negative discriminant.

                          Equations
                            Instances For
                              @[simp]
                              theorem Polynomial.discr_C {R : Type u_1} [CommRing R] (r : R) :
                              (C r).discr = 1

                              The discriminant of a constant polynomial is 1.

                              theorem Polynomial.discr_of_degree_eq_one {R : Type u_1} [CommRing R] {f : Polynomial R} (hf : f.degree = 1) :
                              f.discr = 1

                              The discriminant of a linear polynomial is 1.

                              theorem Polynomial.discr_of_degree_eq_two {R : Type u_1} [CommRing R] {f : Polynomial R} (hf : f.degree = 2) :
                              f.discr = f.coeff 1 ^ 2 - 4 * f.coeff 0 * f.coeff 2

                              Standard formula for the discriminant of a quadratic polynomial.

                              @[deprecated Polynomial.discr_C (since := "2025-10-20")]
                              theorem Polynomial.disc_C {R : Type u_1} [CommRing R] (r : R) :
                              (C r).discr = 1

                              Alias of Polynomial.discr_C.


                              The discriminant of a constant polynomial is 1.

                              @[deprecated Polynomial.discr_of_degree_eq_one (since := "2025-10-20")]
                              theorem Polynomial.disc_of_degree_eq_one {R : Type u_1} [CommRing R] {f : Polynomial R} (hf : f.degree = 1) :
                              f.discr = 1

                              Alias of Polynomial.discr_of_degree_eq_one.


                              The discriminant of a linear polynomial is 1.

                              @[deprecated Polynomial.discr_of_degree_eq_two (since := "2025-10-20")]
                              theorem Polynomial.disc_of_degree_eq_two {R : Type u_1} [CommRing R] {f : Polynomial R} (hf : f.degree = 2) :
                              f.discr = f.coeff 1 ^ 2 - 4 * f.coeff 0 * f.coeff 2

                              Alias of Polynomial.discr_of_degree_eq_two.


                              Standard formula for the discriminant of a quadratic polynomial.

                              theorem Polynomial.resultant_deriv {R : Type u_1} [CommRing R] {f : Polynomial R} (hf : 0 < f.degree) :

                              Relation between the resultant and the discriminant.

                              (Note this is actually false when f is a constant polynomial not equal to 1, so the assumption on the degree is genuinely needed.)

                              theorem Polynomial.discr_of_degree_eq_three {R : Type u_1} [CommRing R] {f : Polynomial R} (hf : f.degree = 3) :
                              f.discr = f.coeff 2 ^ 2 * f.coeff 1 ^ 2 - 4 * f.coeff 3 * f.coeff 1 ^ 3 - 4 * f.coeff 2 ^ 3 * f.coeff 0 - 27 * f.coeff 3 ^ 2 * f.coeff 0 ^ 2 + 18 * f.coeff 3 * f.coeff 2 * f.coeff 1 * f.coeff 0

                              Standard formula for the discriminant of a cubic polynomial.

                              @[deprecated Polynomial.discr_of_degree_eq_three (since := "2025-10-20")]
                              theorem Polynomial.disc_of_degree_eq_three {R : Type u_1} [CommRing R] {f : Polynomial R} (hf : f.degree = 3) :
                              f.discr = f.coeff 2 ^ 2 * f.coeff 1 ^ 2 - 4 * f.coeff 3 * f.coeff 1 ^ 3 - 4 * f.coeff 2 ^ 3 * f.coeff 0 - 27 * f.coeff 3 ^ 2 * f.coeff 0 ^ 2 + 18 * f.coeff 3 * f.coeff 2 * f.coeff 1 * f.coeff 0

                              Alias of Polynomial.discr_of_degree_eq_three.


                              Standard formula for the discriminant of a cubic polynomial.