Engineering / Mathematics — Fields, Series and Factorisation
Formal Power Series
Formal power series, their arithmetic, invertibility criterion, and use as generating functions.
Executive summary
A formal power series is an infinite coefficient sequence with polynomial-style arithmetic and no convergence requirement. Formal means the variable is never substituted.
The ring of power series is a local ring in which a series is invertible exactly when its constant term is.
Learning objectives
- Define formal power series and their operations.
- State and apply the invertibility criterion.
- Use series as generating functions.
01Definition and arithmetic
Formal power series
An element of R[[X]] is a sequence (a₀, a₁, a₂, ...) written Σ aᵢX^i, with addition coefficientwise and multiplication by convolution:
(fg)_n = Σ_{i+j=n} aᵢ bⱼ.
Polynomials embed as the series with finitely many non-zero coefficients, so R[X] ⊂ R[[X]]. The inclusion is strict and the larger ring has properties the smaller one lacks.
02Invertibility
Invertibility criterion
f ∈ R[[X]] is invertible if and only if its constant term a₀ is a unit of R.
The inverse is constructed coefficient by coefficient. Setting b₀ = a₀⁻¹, each subsequent coefficient is determined by the requirement that the convolution vanish, giving a recurrence solvable because a₀ is invertible.
b_n = −a₀⁻¹ Σ_{i=1}^{n} aᵢ b_{n−i}Over a field, F[[X]] is therefore a local ring whose unique maximal ideal is generated by X, and every non-zero element is a power of X times a unit.
03Generating functions
A sequence is encoded as the coefficients of a series, and operations on sequences become operations on series.
| Sequence operation | Series operation |
|---|---|
| Shift | Multiply by X |
| Convolution | Multiplication |
| Partial sums | Divide by 1 − X |
| Linear recurrence | Rational function |
Rationality and linear recurrences
A sequence satisfies a linear recurrence with constant coefficients if and only if its generating function is a rational function.
The denominator is the reversed characteristic polynomial of the recurrence.
This equivalence is the reason power series appear in this collection. Linearly generated sequences are exactly those with rational generating functions, and finding the minimal recurrence is finding the denominator of least degree — which is rational function reconstruction.
04Frequently asked questions
Why is convergence irrelevant?
Because each coefficient of a sum or product is computed from finitely many input coefficients. The series is a bookkeeping device for the whole sequence, not a function to be evaluated.
Is F[[X]] a Euclidean domain?
Yes, with the order of vanishing as the size function. Every element is X^k times a unit, so division with remainder is available and the ring is a PID with the single prime X.
What is the relation to Taylor series?
A Taylor series is a formal power series that additionally converges on some interval. The formal theory discards the analytic condition and keeps only the algebra, which is all that combinatorial and algebraic applications need.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 378-380.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.