Engineering / Mathematics — Rings and Polynomial Rings
Polynomials versus Polynomial Functions
The distinction between a formal polynomial and the function it induces, and why the two differ over finite rings.
Executive summary
A polynomial is a formal expression, a sequence of coefficients. The function it induces evaluates that expression at ring elements. Over infinite fields the two determine each other; over finite ones they do not.
Failing to keep them apart produces genuine errors in finite field computation.
Learning objectives
- Define polynomials formally as coefficient sequences.
- Exhibit distinct polynomials inducing the same function.
- State when the two notions coincide.
01The formal definition
Polynomial
A polynomial over R is a sequence of coefficients (a₀, a₁, ...) from R, all but finitely many zero, written a₀ + a₁X + a₂X² + ...
Two polynomials are equal exactly when all their coefficients agree.
X is not a variable to be substituted; it is a placeholder marking coefficient position. Addition is coefficientwise and multiplication is convolution of coefficient sequences.
Under this definition the degree is well defined as the largest index with a non-zero coefficient, and the zero polynomial is conventionally assigned degree −∞ so that the degree rules hold without exception.
02The induced function
Evaluating a polynomial at an element gives a function from R to R. Distinct polynomials may induce the same function.
| Setting | Do polynomials determine functions? | Do functions determine polynomials? |
|---|---|---|
| Infinite field | Yes | Yes |
| Finite field F_q | Yes | No; X^q − X induces zero |
| Z_n composite | Yes | No |
The failure direction is always the same: a polynomial always determines a function, but many polynomials can share one. Over an infinite field the root bound forces uniqueness, since a difference vanishing everywhere would have infinitely many roots.
03Why the distinction matters
Degree is a formal notion
Algorithms bounding cost by degree operate on the formal object. A polynomial of degree 1000 over F_2 is not cheap merely because it induces one of only four possible functions.
Reduction is not evaluation
Working in F_q[X]/(X^q − X) identifies polynomials inducing the same function, which is a different ring from F_q[X].
Interpolation needs enough points
Recovering a polynomial of degree k requires k+1 evaluation points; fewer determine the function on those points only.
Factorisation is formal
Factoring X^p − X over F_p yields the product of all linear factors — a meaningful statement about the polynomial, invisible from the function.
04Frequently asked questions
Why define polynomials formally rather than as functions?
Because degree, factorisation and division with remainder are properties of the coefficient sequence, not of the induced function. Over finite fields the functional view discards exactly the information the algorithms need.
How many functions does a finite field admit?
Every function from F_q to itself is induced by some polynomial, and there are q^q of them. Since polynomials of degree below q already realise all of these and there are q^q such, the correspondence is a bijection once degree is capped below q.
Does the distinction matter over the integers?
Less so, since Z is infinite and the root bound forces distinct polynomials to induce distinct functions. It reappears immediately on reducing modulo n.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 220-222.
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.