Documentation

Mathlib.RingTheory.PowerSeries.Basic

Formal power series (in one variable) #

This file defines (univariate) formal power series and develops the basic properties of these objects.

A formal power series is to a polynomial like an infinite sum is to a finite sum.

Formal power series in one variable are defined from multivariate power series as PowerSeries R := MvPowerSeries Unit R.

The file sets up the (semi)ring structure on univariate power series.

We provide the natural inclusion from polynomials to formal power series.

Additional results can be found in:

Implementation notes #

Because of its definition, PowerSeries R := MvPowerSeries Unit R. a lot of proofs and properties from the multivariate case can be ported to the single variable case. However, it means that formal power series are indexed by Unit →₀ ℕ, which is of course canonically isomorphic to . We then build some glue to treat formal power series as if they were indexed by . Occasionally this leads to proofs that are uglier than expected.

def PowerSeries (R : Type u_1) :
Type u_1

Formal power series over a coefficient type R

Equations
Instances For

    R⟦X⟧ is notation for PowerSeries R, the semiring of formal power series in one variable over a semiring R.

    Equations
    Instances For
      Equations
      • PowerSeries.instInhabited = id inferInstance
      instance PowerSeries.instZero {R : Type u_1} [Zero R] :
      Equations
      • PowerSeries.instZero = id inferInstance
      Equations
      • PowerSeries.instAddMonoid = id inferInstance
      Equations
      • PowerSeries.instAddGroup = id inferInstance
      Equations
      • PowerSeries.instAddCommMonoid = id inferInstance
      Equations
      • PowerSeries.instAddCommGroup = id inferInstance
      Equations
      • PowerSeries.instSemiring = id inferInstance
      Equations
      • PowerSeries.instCommSemiring = id inferInstance
      instance PowerSeries.instRing {R : Type u_1} [Ring R] :
      Equations
      • PowerSeries.instRing = id inferInstance
      Equations
      • PowerSeries.instCommRing = id inferInstance
      Equations
      • =
      instance PowerSeries.instModule {R : Type u_1} {A : Type u_2} [Semiring R] [AddCommMonoid A] [Module R A] :
      Equations
      • PowerSeries.instModule = id inferInstance
      instance PowerSeries.instIsScalarTower {R : Type u_1} {A : Type u_2} {S : Type u_3} [Semiring R] [Semiring S] [AddCommMonoid A] [Module R A] [Module S A] [SMul R S] [IsScalarTower R S A] :
      Equations
      • =
      instance PowerSeries.instAlgebra {R : Type u_1} {A : Type u_2} [Semiring A] [CommSemiring R] [Algebra R A] :
      Equations
      • PowerSeries.instAlgebra = id inferInstance
      def PowerSeries.coeff (R : Type u_1) [Semiring R] (n : ) :

      The nth coefficient of a formal power series.

      Equations
      Instances For

        The nth monomial with coefficient a as formal power series.

        Equations
        Instances For
          theorem PowerSeries.coeff_def {R : Type u_1} [Semiring R] {s : Unit →₀ } {n : } (h : s () = n) :
          theorem PowerSeries.ext {R : Type u_1} [Semiring R] {φ : PowerSeries R} {ψ : PowerSeries R} (h : ∀ (n : ), (PowerSeries.coeff R n) φ = (PowerSeries.coeff R n) ψ) :
          φ = ψ

          Two formal power series are equal if all their coefficients are equal.

          theorem PowerSeries.ext_iff {R : Type u_1} [Semiring R] {φ : PowerSeries R} {ψ : PowerSeries R} :
          φ = ψ ∀ (n : ), (PowerSeries.coeff R n) φ = (PowerSeries.coeff R n) ψ

          Two formal power series are equal if all their coefficients are equal.

          def PowerSeries.mk {R : Type u_2} (f : R) :

          Constructor for formal power series.

          Equations
          Instances For
            @[simp]
            theorem PowerSeries.coeff_mk {R : Type u_1} [Semiring R] (n : ) (f : R) :
            theorem PowerSeries.coeff_monomial {R : Type u_1} [Semiring R] (m : ) (n : ) (a : R) :
            (PowerSeries.coeff R m) ((PowerSeries.monomial R n) a) = if m = n then a else 0
            theorem PowerSeries.monomial_eq_mk {R : Type u_1} [Semiring R] (n : ) (a : R) :
            (PowerSeries.monomial R n) a = PowerSeries.mk fun (m : ) => if m = n then a else 0
            @[simp]
            theorem PowerSeries.coeff_monomial_same {R : Type u_1} [Semiring R] (n : ) (a : R) :
            @[simp]
            theorem PowerSeries.coeff_comp_monomial {R : Type u_1} [Semiring R] (n : ) :
            PowerSeries.coeff R n ∘ₗ PowerSeries.monomial R n = LinearMap.id

            The constant coefficient of a formal power series.

            Equations
            Instances For

              The constant formal power series.

              Equations
              Instances For
                def PowerSeries.X {R : Type u_1} [Semiring R] :

                The variable of the formal power series ring.

                Equations
                Instances For
                  theorem PowerSeries.commute_X {R : Type u_1} [Semiring R] (φ : PowerSeries R) :
                  Commute φ PowerSeries.X
                  theorem PowerSeries.coeff_C {R : Type u_1} [Semiring R] (n : ) (a : R) :
                  (PowerSeries.coeff R n) ((PowerSeries.C R) a) = if n = 0 then a else 0
                  @[simp]
                  theorem PowerSeries.coeff_zero_C {R : Type u_1} [Semiring R] (a : R) :
                  theorem PowerSeries.coeff_ne_zero_C {R : Type u_1} [Semiring R] {a : R} {n : } (h : n 0) :
                  @[simp]
                  theorem PowerSeries.coeff_succ_C {R : Type u_1} [Semiring R] {a : R} {n : } :
                  (PowerSeries.coeff R (n + 1)) ((PowerSeries.C R) a) = 0
                  theorem PowerSeries.X_eq {R : Type u_1} [Semiring R] :
                  PowerSeries.X = (PowerSeries.monomial R 1) 1
                  theorem PowerSeries.coeff_X {R : Type u_1} [Semiring R] (n : ) :
                  (PowerSeries.coeff R n) PowerSeries.X = if n = 1 then 1 else 0
                  @[simp]
                  theorem PowerSeries.coeff_zero_X {R : Type u_1} [Semiring R] :
                  (PowerSeries.coeff R 0) PowerSeries.X = 0
                  @[simp]
                  theorem PowerSeries.coeff_one_X {R : Type u_1} [Semiring R] :
                  (PowerSeries.coeff R 1) PowerSeries.X = 1
                  @[simp]
                  theorem PowerSeries.X_ne_zero {R : Type u_1} [Semiring R] [Nontrivial R] :
                  PowerSeries.X 0
                  theorem PowerSeries.X_pow_eq {R : Type u_1} [Semiring R] (n : ) :
                  PowerSeries.X ^ n = (PowerSeries.monomial R n) 1
                  theorem PowerSeries.coeff_X_pow {R : Type u_1} [Semiring R] (m : ) (n : ) :
                  (PowerSeries.coeff R m) (PowerSeries.X ^ n) = if m = n then 1 else 0
                  @[simp]
                  theorem PowerSeries.coeff_X_pow_self {R : Type u_1} [Semiring R] (n : ) :
                  (PowerSeries.coeff R n) (PowerSeries.X ^ n) = 1
                  @[simp]
                  theorem PowerSeries.coeff_one {R : Type u_1} [Semiring R] (n : ) :
                  (PowerSeries.coeff R n) 1 = if n = 0 then 1 else 0
                  theorem PowerSeries.coeff_mul {R : Type u_1} [Semiring R] (n : ) (φ : PowerSeries R) (ψ : PowerSeries R) :
                  (PowerSeries.coeff R n) (φ * ψ) = pFinset.antidiagonal n, (PowerSeries.coeff R p.1) φ * (PowerSeries.coeff R p.2) ψ
                  @[simp]
                  theorem PowerSeries.coeff_mul_C {R : Type u_1} [Semiring R] (n : ) (φ : PowerSeries R) (a : R) :
                  @[simp]
                  theorem PowerSeries.coeff_C_mul {R : Type u_1} [Semiring R] (n : ) (φ : PowerSeries R) (a : R) :
                  @[simp]
                  theorem PowerSeries.coeff_smul {R : Type u_1} [Semiring R] {S : Type u_2} [Semiring S] [Module R S] (n : ) (φ : PowerSeries S) (a : R) :
                  (PowerSeries.coeff S n) (a φ) = a (PowerSeries.coeff S n) φ
                  @[simp]
                  theorem PowerSeries.constantCoeff_smul {R : Type u_1} [Semiring R] {S : Type u_2} [Semiring S] [Module R S] (φ : PowerSeries S) (a : R) :
                  theorem PowerSeries.smul_eq_C_mul {R : Type u_1} [Semiring R] (f : PowerSeries R) (a : R) :
                  a f = (PowerSeries.C R) a * f
                  @[simp]
                  theorem PowerSeries.coeff_succ_mul_X {R : Type u_1} [Semiring R] (n : ) (φ : PowerSeries R) :
                  (PowerSeries.coeff R (n + 1)) (φ * PowerSeries.X) = (PowerSeries.coeff R n) φ
                  @[simp]
                  theorem PowerSeries.coeff_succ_X_mul {R : Type u_1} [Semiring R] (n : ) (φ : PowerSeries R) :
                  (PowerSeries.coeff R (n + 1)) (PowerSeries.X * φ) = (PowerSeries.coeff R n) φ
                  @[simp]
                  @[simp]
                  theorem PowerSeries.constantCoeff_X {R : Type u_1} [Semiring R] :
                  (PowerSeries.constantCoeff R) PowerSeries.X = 0
                  @[simp]
                  theorem PowerSeries.coeff_zero_mul_X {R : Type u_1} [Semiring R] (φ : PowerSeries R) :
                  (PowerSeries.coeff R 0) (φ * PowerSeries.X) = 0
                  theorem PowerSeries.coeff_zero_X_mul {R : Type u_1} [Semiring R] (φ : PowerSeries R) :
                  (PowerSeries.coeff R 0) (PowerSeries.X * φ) = 0
                  theorem PowerSeries.coeff_C_mul_X_pow {R : Type u_1} [Semiring R] (x : R) (k : ) (n : ) :
                  (PowerSeries.coeff R n) ((PowerSeries.C R) x * PowerSeries.X ^ k) = if n = k then x else 0
                  @[simp]
                  theorem PowerSeries.coeff_mul_X_pow {R : Type u_1} [Semiring R] (p : PowerSeries R) (n : ) (d : ) :
                  (PowerSeries.coeff R (d + n)) (p * PowerSeries.X ^ n) = (PowerSeries.coeff R d) p
                  @[simp]
                  theorem PowerSeries.coeff_X_pow_mul {R : Type u_1} [Semiring R] (p : PowerSeries R) (n : ) (d : ) :
                  (PowerSeries.coeff R (d + n)) (PowerSeries.X ^ n * p) = (PowerSeries.coeff R d) p
                  theorem PowerSeries.coeff_mul_X_pow' {R : Type u_1} [Semiring R] (p : PowerSeries R) (n : ) (d : ) :
                  (PowerSeries.coeff R d) (p * PowerSeries.X ^ n) = if n d then (PowerSeries.coeff R (d - n)) p else 0
                  theorem PowerSeries.coeff_X_pow_mul' {R : Type u_1} [Semiring R] (p : PowerSeries R) (n : ) (d : ) :
                  (PowerSeries.coeff R d) (PowerSeries.X ^ n * p) = if n d then (PowerSeries.coeff R (d - n)) p else 0

                  If a formal power series is invertible, then so is its constant coefficient.

                  theorem PowerSeries.eq_shift_mul_X_add_const {R : Type u_1} [Semiring R] (φ : PowerSeries R) :
                  φ = (PowerSeries.mk fun (p : ) => (PowerSeries.coeff R (p + 1)) φ) * PowerSeries.X + (PowerSeries.C R) ((PowerSeries.constantCoeff R) φ)

                  Split off the constant coefficient.

                  theorem PowerSeries.eq_X_mul_shift_add_const {R : Type u_1} [Semiring R] (φ : PowerSeries R) :
                  φ = (PowerSeries.X * PowerSeries.mk fun (p : ) => (PowerSeries.coeff R (p + 1)) φ) + (PowerSeries.C R) ((PowerSeries.constantCoeff R) φ)

                  Split off the constant coefficient.

                  def PowerSeries.map {R : Type u_1} [Semiring R] {S : Type u_2} [Semiring S] (f : R →+* S) :

                  The map between formal power series induced by a map on the coefficients.

                  Equations
                  Instances For
                    @[simp]
                    theorem PowerSeries.map_id {R : Type u_1} [Semiring R] :
                    theorem PowerSeries.map_comp {R : Type u_1} [Semiring R] {S : Type u_2} {T : Type u_3} [Semiring S] [Semiring T] (f : R →+* S) (g : S →+* T) :
                    @[simp]
                    theorem PowerSeries.coeff_map {R : Type u_1} [Semiring R] {S : Type u_2} [Semiring S] (f : R →+* S) (n : ) (φ : PowerSeries R) :
                    @[simp]
                    theorem PowerSeries.map_C {R : Type u_1} [Semiring R] {S : Type u_2} [Semiring S] (f : R →+* S) (r : R) :
                    @[simp]
                    theorem PowerSeries.map_X {R : Type u_1} [Semiring R] {S : Type u_2} [Semiring S] (f : R →+* S) :
                    (PowerSeries.map f) PowerSeries.X = PowerSeries.X
                    theorem PowerSeries.X_pow_dvd_iff {R : Type u_1} [Semiring R] {n : } {φ : PowerSeries R} :
                    PowerSeries.X ^ n φ m < n, (PowerSeries.coeff R m) φ = 0
                    theorem PowerSeries.X_dvd_iff {R : Type u_1} [Semiring R] {φ : PowerSeries R} :
                    PowerSeries.X φ (PowerSeries.constantCoeff R) φ = 0
                    noncomputable def PowerSeries.rescale {R : Type u_1} [CommSemiring R] (a : R) :

                    The ring homomorphism taking a power series f(X) to f(aX).

                    Equations
                    Instances For
                      @[simp]
                      theorem PowerSeries.coeff_rescale {R : Type u_1} [CommSemiring R] (f : PowerSeries R) (a : R) (n : ) :
                      theorem PowerSeries.rescale_mk {R : Type u_1} [CommSemiring R] (f : R) (a : R) :
                      theorem PowerSeries.coeff_prod {R : Type u_2} [CommSemiring R] {ι : Type u_3} [DecidableEq ι] (f : ιPowerSeries R) (d : ) (s : Finset ι) :
                      (PowerSeries.coeff R d) (js, f j) = ls.finsuppAntidiag d, is, (PowerSeries.coeff R (l i)) (f i)

                      Coefficients of a product of power series

                      theorem PowerSeries.coeff_pow {R : Type u_2} [CommSemiring R] (k : ) (n : ) (φ : PowerSeries R) :
                      (PowerSeries.coeff R n) (φ ^ k) = l(Finset.range k).finsuppAntidiag n, iFinset.range k, (PowerSeries.coeff R (l i)) φ

                      The n-th coefficient of the k-th power of a power series.

                      First coefficient of the product of two power series.

                      theorem PowerSeries.coeff_one_pow {R : Type u_2} [CommSemiring R] (n : ) (φ : PowerSeries R) (hC : (PowerSeries.constantCoeff R) φ = 1) :
                      (PowerSeries.coeff R 1) (φ ^ n) = n * (PowerSeries.coeff R 1) φ

                      First coefficient of the n-th power of a power series with constant coefficient 1.

                      @[simp]
                      theorem PowerSeries.rescale_X {A : Type u_2} [CommRing A] (a : A) :
                      (PowerSeries.rescale a) PowerSeries.X = (PowerSeries.C A) a * PowerSeries.X
                      theorem PowerSeries.rescale_neg_one_X {A : Type u_2} [CommRing A] :
                      (PowerSeries.rescale (-1)) PowerSeries.X = -PowerSeries.X
                      noncomputable def PowerSeries.evalNegHom {A : Type u_2} [CommRing A] :

                      The ring homomorphism taking a power series f(X) to f(-X).

                      Equations
                      Instances For
                        @[simp]
                        theorem PowerSeries.evalNegHom_X {A : Type u_2} [CommRing A] :
                        PowerSeries.evalNegHom PowerSeries.X = -PowerSeries.X
                        theorem PowerSeries.eq_zero_or_eq_zero_of_mul_eq_zero {R : Type u_1} [Ring R] [NoZeroDivisors R] (φ : PowerSeries R) (ψ : PowerSeries R) (h : φ * ψ = 0) :
                        φ = 0 ψ = 0
                        Equations
                        • =
                        theorem PowerSeries.span_X_isPrime {R : Type u_1} [CommRing R] [IsDomain R] :
                        (Ideal.span {PowerSeries.X}).IsPrime

                        The ideal spanned by the variable in the power series ring over an integral domain is a prime ideal.

                        theorem PowerSeries.X_prime {R : Type u_1} [CommRing R] [IsDomain R] :
                        Prime PowerSeries.X

                        The variable of the power series ring over an integral domain is prime.

                        theorem PowerSeries.X_irreducible {R : Type u_1} [CommRing R] [IsDomain R] :
                        Irreducible PowerSeries.X

                        The variable of the power series ring over an integral domain is irreducible.

                        theorem PowerSeries.algebraMap_apply {R : Type u_1} {A : Type u_2} [CommSemiring R] [Semiring A] [Algebra R A] {r : R} :

                        The natural inclusion from polynomials into formal power series.

                        Equations
                        Instances For

                          The natural inclusion from polynomials into formal power series.

                          Equations
                          • Polynomial.coeToPowerSeries = { coe := Polynomial.ToPowerSeries }
                          theorem Polynomial.coe_def {R : Type u_2} [CommSemiring R] (φ : Polynomial R) :
                          φ = PowerSeries.mk φ.coeff
                          @[simp]
                          theorem Polynomial.coeff_coe {R : Type u_2} [CommSemiring R] (φ : Polynomial R) (n : ) :
                          (PowerSeries.coeff R n) φ = φ.coeff n
                          @[simp]
                          theorem Polynomial.coe_monomial {R : Type u_2} [CommSemiring R] (n : ) (a : R) :
                          @[simp]
                          theorem Polynomial.coe_zero {R : Type u_2} [CommSemiring R] :
                          0 = 0
                          @[simp]
                          theorem Polynomial.coe_one {R : Type u_2} [CommSemiring R] :
                          1 = 1
                          @[simp]
                          theorem Polynomial.coe_add {R : Type u_2} [CommSemiring R] (φ : Polynomial R) (ψ : Polynomial R) :
                          (φ + ψ) = φ + ψ
                          @[simp]
                          theorem Polynomial.coe_mul {R : Type u_2} [CommSemiring R] (φ : Polynomial R) (ψ : Polynomial R) :
                          (φ * ψ) = φ * ψ
                          @[simp]
                          theorem Polynomial.coe_C {R : Type u_2} [CommSemiring R] (a : R) :
                          (Polynomial.C a) = (PowerSeries.C R) a
                          @[simp]
                          theorem Polynomial.coe_X {R : Type u_2} [CommSemiring R] :
                          Polynomial.X = PowerSeries.X
                          @[simp]
                          theorem Polynomial.constantCoeff_coe {R : Type u_2} [CommSemiring R] (φ : Polynomial R) :
                          (PowerSeries.constantCoeff R) φ = φ.coeff 0
                          @[simp]
                          theorem Polynomial.coe_inj {R : Type u_2} [CommSemiring R] {φ : Polynomial R} {ψ : Polynomial R} :
                          φ = ψ φ = ψ
                          @[simp]
                          theorem Polynomial.coe_eq_zero_iff {R : Type u_2} [CommSemiring R] {φ : Polynomial R} :
                          φ = 0 φ = 0
                          @[simp]
                          theorem Polynomial.coe_eq_one_iff {R : Type u_2} [CommSemiring R] {φ : Polynomial R} :
                          φ = 1 φ = 1

                          The coercion from polynomials to power series as a ring homomorphism.

                          Equations
                          • Polynomial.coeToPowerSeries.ringHom = { toFun := Coe.coe, map_one' := , map_mul' := , map_zero' := , map_add' := }
                          Instances For
                            @[simp]
                            theorem Polynomial.coeToPowerSeries.ringHom_apply {R : Type u_2} [CommSemiring R] (φ : Polynomial R) :
                            Polynomial.coeToPowerSeries.ringHom φ = φ
                            @[simp]
                            theorem Polynomial.coe_pow {R : Type u_2} [CommSemiring R] (φ : Polynomial R) (n : ) :
                            (φ ^ n) = φ ^ n
                            theorem Polynomial.eval₂_C_X_eq_coe {R : Type u_2} [CommSemiring R] (φ : Polynomial R) :
                            Polynomial.eval₂ (PowerSeries.C R) PowerSeries.X φ = φ

                            The coercion from polynomials to power series as an algebra homomorphism.

                            Equations
                            Instances For
                              Equations
                              Equations
                              @[instance 100]
                              Equations
                              • PowerSeries.algebraPolynomial' = (Polynomial.coeToPowerSeries.ringHom.comp (algebraMap R (Polynomial A))).toAlgebra