1.5 Polynomials
1.5.1 Definition
(a) An FPS \(a\in K\left[ \left[ x\right] \right] \) is said to be a polynomial if all but finitely many \(n\in \mathbb {N}\) satisfy \(\left[ x^{n}\right] a=0\) (that is, if all but finitely many coefficients of \(a\) are \(0\)).
(b) We let \(K\left[ x\right] \) be the set of all polynomials \(a\in K\left[ \left[ x\right] \right] \). This set \(K\left[ x\right] \) is a subring of \(K\left[ \left[ x\right] \right] \) (according to Theorem 1.148 below), and is called the univariate polynomial ring over \(K\).
- FPS.IsPolynomial f = {n : ℕ | (PowerSeries.coeff n) f ≠ 0}.Finite
- FPS.polynomialSubalgebra = { carrier := {f : PowerSeries K | FPS.IsPolynomial f}, mul_mem' := ⋯, one_mem' := ⋯, add_mem' := ⋯, zero_mem' := ⋯, algebraMap_mem' := ⋯ }
An FPS \(f\in K\left[\left[x\right]\right]\) is a polynomial if and only if there exists an \(N\in \mathbb {N}\) such that \(\left[x^{n}\right]f=0\) for all \(n\geq N\).
\(\Longrightarrow \): If the set of nonzero-coefficient indices is finite, it is bounded above by some \(N\), so all coefficients beyond \(N\) vanish.
\(\Longleftarrow \): If all coefficients beyond \(N\) vanish, then the set of nonzero-coefficient indices is contained in \(\{ 0,1,\ldots ,N-1\} \), which is finite.
An FPS \(f\in K\left[\left[x\right]\right]\) is a polynomial (in the sense of Definition 1.134) if and only if \(f\) equals the image of some element of \(K[x]\) under the canonical embedding \(K[x]\hookrightarrow K\left[\left[x\right]\right]\).
The image of any polynomial \(p\in K[X]\) under the canonical embedding \(K[X]\hookrightarrow K\left[\left[x\right]\right]\) is a polynomial in the FPS sense.
The set of indices with nonzero coefficients is contained in the support of \(p\), which is a finite set.
Converting between polynomial FPSs and polynomials
- FPS.toPolynomial f hf = (fun (N : ℕ) => (PowerSeries.trunc N) f) ⋯.choose
Let \(f\in K\left[\left[x\right]\right]\) be a polynomial FPS. Then the coercion of \(\operatorname {toPolynomial}(f)\) back into \(K\left[\left[x\right]\right]\) equals \(f\):
where \(\iota \colon K[X]\hookrightarrow K\left[\left[x\right]\right]\) is the canonical embedding.
By the degree bound, all coefficients of \(f\) beyond the bound are zero, so truncation and coercion recover every coefficient of \(f\).
For any polynomial \(p\in K[X]\), we have \(\operatorname {toPolynomial}(\iota (p))=p\), where \(\iota \) is the canonical embedding.
By Lemma 1.139, both sides have the same image under \(\iota \), and \(\iota \) is injective.
1.5.2 Polynomials form a subring of power series
The zero power series \(\underline{0}\) is a polynomial.
All coefficients of \(\underline{0}\) are \(0\), so the set of nonzero-coefficient indices is empty, hence finite.
The unity \(\underline{1}\) is a polynomial.
The unity \(\underline{1}\) equals the image of \(1\in K[X]\) under the canonical embedding.
The sum of two polynomial power series is a polynomial.
If \(f\) and \(g\) are polynomials, then the set of indices where \((f+g)\) has a nonzero coefficient is contained in the union of the corresponding sets for \(f\) and \(g\). A finite union of finite sets is finite.
The negation of a polynomial power series is a polynomial.
Negation does not change which coefficients are nonzero.
The difference of two polynomial power series is a polynomial.
The product of two polynomial power series is a polynomial.
Let \(a,b\in K\left[ x\right] \). Since \(a\) is a polynomial, there exists a finite subset \(I\) of \(\mathbb {N}\) such that \(\left[ x^{i}\right] a=0\) for all \(i\in \mathbb {N}\setminus I\). Similarly, there exists a finite subset \(J\) of \(\mathbb {N}\) such that \(\left[ x^{j}\right] b=0\) for all \(j\in \mathbb {N}\setminus J\).
Let \(S=\left\{ i+j\ \mid \ i\in I\text{ and }j\in J\right\} \). This set \(S\) is again finite (since \(I\) and \(J\) are finite), and we have
because for each \(i\in \left\{ 0,1,\ldots ,n\right\} \), letting \(j=n-i\), we cannot have both \(i\in I\) and \(j\in J\) (otherwise \(n=i+j\in S\), contradicting \(n\notin S\)), so at least one of \(\left[ x^{i}\right] a\) and \(\left[ x^{j}\right] b\) is \(0\), making each summand \(0\). Thus, all but finitely many \(n\in \mathbb {N}\) satisfy \(\left[ x^{n}\right] \left( ab\right) =0\), so \(ab\in K\left[ x\right] \).
Scalar multiplication of a polynomial power series by an element of \(K\) is a polynomial.
If \(\left[x^{n}\right]f=0\), then \(\left[x^{n}\right](cf)=c\cdot \left[x^{n}\right]f=0\). So the nonzero-coefficient set of \(cf\) is contained in that of \(f\), which is finite.
The set \(K\left[ x\right] \) is a subring of \(K\left[ \left[ x\right] \right] \) (that is, it is closed under addition, subtraction and multiplication, and contains the zero \(\underline{0}\) and the unity \(\underline{1}\)) and is a \(K\)-submodule of \(K\left[ \left[ x\right] \right] \) (that is, it is closed under addition and scaling by elements of \(K\)).
- FPS.polynomialSubalgebra = { carrier := {f : PowerSeries K | FPS.IsPolynomial f}, mul_mem' := ⋯, one_mem' := ⋯, add_mem' := ⋯, zero_mem' := ⋯, algebraMap_mem' := ⋯ }
The polynomial \(x\in K\left[\left[x\right]\right]\) is a polynomial.
The only nonzero coefficient of \(x\) is the coefficient of \(x^1\), which is \(1\). Thus the set of nonzero-coefficient indices is contained in \(\{ 1\} \), which is finite.
For any \(c\in K\), the constant FPS \(\underline{c}\) is a polynomial.
The only possibly nonzero coefficient of \(\underline{c}\) is the coefficient of \(x^0\). Thus the set of nonzero-coefficient indices is contained in \(\{ 0\} \), which is finite.
1.5.3 Reminders on rings and \(K\)-algebras
The notion of a ring (also known as a noncommutative ring) is defined in the exact same way as we defined the notion of a commutative ring in Definition 1.42, except that the “Commutativity of multiplication” axiom is removed.
A \(K\)-algebra is a set \(A\) equipped with four maps
and two elements \(\overrightarrow {0}\in A\) and \(\overrightarrow {1}\in A\) satisfying the following properties:
The set \(A\), equipped with the maps \(\oplus \), \(\ominus \) and \(\odot \) and the two elements \(\overrightarrow {0}\) and \(\overrightarrow {1}\), is a (noncommutative) ring.
The set \(A\), equipped with the maps \(\oplus \), \(\ominus \) and \(\rightharpoonup \) and the element \(\overrightarrow {0}\), is a \(K\)-module.
We have
\begin{equation} \lambda \rightharpoonup \left( a\odot b\right) =\left( \lambda \rightharpoonup a\right) \odot b=a\odot \left( \lambda \rightharpoonup b\right) \label{eq.def.alg.Kalg.scaleinv}\end{equation}14for all \(\lambda \in K\) and \(a,b\in A\).
(Thus, in a nutshell, a \(K\)-algebra is a set \(A\) that is simultaneously a ring and a \(K\)-module, with the property that the ring \(A\) and the \(K\)-module \(A\) have the same addition, the same subtraction and the same zero, and satisfy the additional compatibility property (14).)
1.5.4 Evaluation aka substitution into polynomials
Let \(f\in K\left[ x\right] \) be a polynomial. Let \(A\) be any \(K\)-algebra. Let \(a\in A\) be any element. We then define an element \(f\left[ a\right] \in A\) as follows:
Write \(f\) in the form \(f=\sum _{n\in \mathbb {N}}f_{n}x^{n}\) with \(f_{0},f_{1},f_{2},\ldots \in K\). (That is, \(f_{n}=\left[ x^{n}\right] f\) for each \(n\in \mathbb {N}\).) Then, set
(This sum is essentially finite, since \(f\) is a polynomial.)
The element \(f\left[ a\right] \) is also denoted by \(f\circ a\) or by \(f\left( a\right) \), and is called the value of \(f\) at \(a\) (or the evaluation of \(f\) at \(a\), or the result of substituting \(a\) for \(x\) in \(f\)).
- FPS.polyEval f a = (Polynomial.aeval a) f
The evaluation \(f\left[a\right]\) can be computed as \(f\left[a\right]=\sum _{n}f_{n}\cdot a^{n}\), where the sum ranges over all \(n\) in the support of \(f\).
Immediate from the definitions.
The evaluation \(f\left[a\right]\) equals \(\sum _{n\in \operatorname {supp}(f)}f_{n}\cdot a^{n}\), making the finiteness of the sum explicit.
This follows from the definition by restricting the sum to the support.
The evaluation \(f\left[a\right]\) equals \(\sum _{n=0}^{\deg f}f_{n}\cdot a^{n}\), where the sum is taken up to the degree of \(f\).
Since all coefficients beyond the degree of \(f\) are zero, extending or restricting the sum to this range does not change the result.
Let \(A\) be a \(K\)-algebra. Let \(a\in A\). Then:
(a) Any \(f,g\in K\left[ x\right] \) satisfy
(b) Any \(\lambda \in K\) and \(f\in K\left[ x\right] \) satisfy
(c) Any \(\lambda \in K\) satisfies \(\underline{\lambda }\left[ a\right] =\lambda \cdot 1_{A}\), where \(1_{A}\) is the unity of the ring \(A\).
(d) We have \(x\left[ a\right] =a\).
(e) We have \(x^{i}\left[ a\right] =a^{i}\) for each \(i\in \mathbb {N}\).
(f) Any \(f,g\in K\left[ x\right] \) satisfy \(f\left[ g\left[ a\right] \right] =\left( f\left[ g\right] \right) \left[ a\right] \).
1.5.5 Special evaluation results
For any polynomial \(f\in K[x]\), we have \(f[x]=f\).
The evaluation map at \(x\) is the identity on \(K[x]\).
For any polynomial \(f\in K[x]\) and any \(K\)-algebra \(A\), we have \(f[0]=\left[x^{0}\right]f\) (the constant term of \(f\), coerced into \(A\)).
Setting \(a=0\): all terms \(f_{n}\cdot 0^{n}\) for \(n\geq 1\) vanish, leaving only \(f_{0}\cdot 0^{0}=f_{0}\cdot 1=f_{0}\).
For any polynomial \(f\in K[x]\) and any \(K\)-algebra \(A\), we have \(f[1]=\left[x^{0}\right]f+\left[x^{1}\right]f+\left[x^{2}\right]f+\cdots \) (the sum of all coefficients of \(f\), coerced into \(A\)).
Setting \(a=1\): each term \(f_{n}\cdot 1^{n}=f_{n}\), so \(f[1]=\sum _{n}f_{n}\).