If a n x
n + a n–1 x
n–1 +…+ a 1 x + a 0 = 0 for all values x,
then it must be the case that a n = a n–1 =…= a 1 = a 0 = 0.
(To see this, write a n x
n + a n–1 x
n–1 +…+ a 1 x + a 0 =
. For a large
value of x, the term a n x
n will adopt a very large value,
and the expression inside the parentheses will adopt a
value close to 1 + 0 +…+ 0 + 0 = 1. Thus the value of
the entire polynomial expression will not be zero,
unless a n = 0. Repeating this argument shows that all
coefficients would then have to be zero.) As a consequence we have:
If two polynomials produce the same output
values for each input value x, then the two
polynomials must be identical, that is, their
coefficients match.
(The difference of these two polynomials would be a
new polynomial that always produces the zero output.)
This second statement explains why the process of
EQUATING COEFFICIENTS is valid.
The FUNDAMENTAL THEOREM OF ALGEBRA assures
us that any degree-n polynomial equation of the form
a n x
n + a n–1 x
n–1 +…+ a 1 x + a 0 = 0 has precisely n roots
(when counted with multiplicity). Some roots may be
COMPLEX NUMBERS. There exist arithmetic formulae
for finding the roots of any quadratic equation, any
CUBIC EQUATION, and any QUARTIC EQUATION. In 1824
algebraist NIELS HENRIK ABEL proved that there are no
analogous formulae for solving fifth- and higher-degree
polynomial equations.
Evaluating a degree-n polynomial typically requires
the computation of n + (n –1) +…+ 2 + 1 + 0 =
multiplications. For instance, in the expression
2x 3 + 3x
2 + 4x + 5 = 2 × x × x × x + 3 × x × x + 4 × x + 5
the multiplication sign “× “ appears 3 + 2 + 1 + 0 = 6
times. This is the formula for the nth TRIANGULAR
NUMBER. The process of performing a NESTED MULTIPLICATION reduces the number of products needed to
just n. For example, rewriting 2x
3 + 3x
2 + 4x + 5 as
x(x(2x + 3) + 4) + 5 reduces the number of multiplications present from six to three. The process of SYNTHETIC DIVISION is intimately connected with nested
multiplications.
LAGRANGE’S FORMULA shows that given any n + 1
points, drawn in the plane, each with a distinct x coordinates, there exists a polynomial function of degree n
whose graph passes through each of those points. Thus
it is always possible to “fit” a polynomial function to
any finite set of data points. This is useful for the purposes of INTERPOLATION and EXTRAPOLATION.
A polynomial may have more than one variable.
For example, 5x
2
y + 7xy
2 – y
3 is a degree-three bivariate polynomial.
See also BINOMIAL; COMPLETING THE SQUARE;
DESCARTES’S RULE OF SIGNS; DIFFERENCE OF TWO
CUBES; DIFFERENCE OF TWO SQUARES; DISCRIMINANT;
FACTOR THEOREM; FACTORIZATION; HISTORY OF EQUATIONS AND ALGEBRA (essay); MONOMIAL; REMAINDER
THEOREM; ROOT; SOLUTION BY RADICALS; TAYLOR
SERIES; TRINOMIAL.
polynomial time A computation is said to run in
polynomial time if the number of elementary steps
required to complete the computation can be expressed
as a POLYNOMIAL function of the size of the input. For
example, if a basic step is to add or multiply two single-digit numbers, then the computation of multiplying
two n-digit numbers via ordinary long multiplication
requires at most 4n
2 steps. (Multiplying each of the
pair of digits requires n
2 steps, and summing all results,
with carrying, is at most 3n
2 steps.) Thus long multiplication runs in polynomial time.
Computations that do not run in polynomial time
are said to run in exponential time. For example, the
task of listing all possible arrangements of n objects
grows as n FACTORIAL. As the factorial function will
exceed any polynomial function of n for sufficiently
large values of n, the operation of listing all possible
orders is exponential. Even with the most powerful
computers, exponential time computations generally
require an infeasible amount of time to complete. Polynomial time algorithms, however, are more practical.
See also NP COMPLETE; TRAVELING-SALESMAN
PROBLEM.
polyomino Generalizing the concept of a domino, a
polyomino is a shape made by adjoining 1×1 squares
along entire edge lengths in such a way that no corner
of one square lies at an interior point of another
n(n + 1)
———–
2
a x
a
a
x
a
a x
a
a x
n
n
n
n
n
n
n
n
1
1
1
1
1
1
1
0
+
⋅ + +
⋅
+
⋅
⎛
⎝
⎜
⎞
⎠
⎟
−
−
L
polyomino 405
n + a n–1 x
n–1 +…+ a 1 x + a 0 = 0 for all values x,
then it must be the case that a n = a n–1 =…= a 1 = a 0 = 0.
(To see this, write a n x
n + a n–1 x
n–1 +…+ a 1 x + a 0 =
. For a large
value of x, the term a n x
n will adopt a very large value,
and the expression inside the parentheses will adopt a
value close to 1 + 0 +…+ 0 + 0 = 1. Thus the value of
the entire polynomial expression will not be zero,
unless a n = 0. Repeating this argument shows that all
coefficients would then have to be zero.) As a consequence we have:
If two polynomials produce the same output
values for each input value x, then the two
polynomials must be identical, that is, their
coefficients match.
(The difference of these two polynomials would be a
new polynomial that always produces the zero output.)
This second statement explains why the process of
EQUATING COEFFICIENTS is valid.
The FUNDAMENTAL THEOREM OF ALGEBRA assures
us that any degree-n polynomial equation of the form
a n x
n + a n–1 x
n–1 +…+ a 1 x + a 0 = 0 has precisely n roots
(when counted with multiplicity). Some roots may be
COMPLEX NUMBERS. There exist arithmetic formulae
for finding the roots of any quadratic equation, any
CUBIC EQUATION, and any QUARTIC EQUATION. In 1824
algebraist NIELS HENRIK ABEL proved that there are no
analogous formulae for solving fifth- and higher-degree
polynomial equations.
Evaluating a degree-n polynomial typically requires
the computation of n + (n –1) +…+ 2 + 1 + 0 =
multiplications. For instance, in the expression
2x 3 + 3x
2 + 4x + 5 = 2 × x × x × x + 3 × x × x + 4 × x + 5
the multiplication sign “× “ appears 3 + 2 + 1 + 0 = 6
times. This is the formula for the nth TRIANGULAR
NUMBER. The process of performing a NESTED MULTIPLICATION reduces the number of products needed to
just n. For example, rewriting 2x
3 + 3x
2 + 4x + 5 as
x(x(2x + 3) + 4) + 5 reduces the number of multiplications present from six to three. The process of SYNTHETIC DIVISION is intimately connected with nested
multiplications.
LAGRANGE’S FORMULA shows that given any n + 1
points, drawn in the plane, each with a distinct x coordinates, there exists a polynomial function of degree n
whose graph passes through each of those points. Thus
it is always possible to “fit” a polynomial function to
any finite set of data points. This is useful for the purposes of INTERPOLATION and EXTRAPOLATION.
A polynomial may have more than one variable.
For example, 5x
2
y + 7xy
2 – y
3 is a degree-three bivariate polynomial.
See also BINOMIAL; COMPLETING THE SQUARE;
DESCARTES’S RULE OF SIGNS; DIFFERENCE OF TWO
CUBES; DIFFERENCE OF TWO SQUARES; DISCRIMINANT;
FACTOR THEOREM; FACTORIZATION; HISTORY OF EQUATIONS AND ALGEBRA (essay); MONOMIAL; REMAINDER
THEOREM; ROOT; SOLUTION BY RADICALS; TAYLOR
SERIES; TRINOMIAL.
polynomial time A computation is said to run in
polynomial time if the number of elementary steps
required to complete the computation can be expressed
as a POLYNOMIAL function of the size of the input. For
example, if a basic step is to add or multiply two single-digit numbers, then the computation of multiplying
two n-digit numbers via ordinary long multiplication
requires at most 4n
2 steps. (Multiplying each of the
pair of digits requires n
2 steps, and summing all results,
with carrying, is at most 3n
2 steps.) Thus long multiplication runs in polynomial time.
Computations that do not run in polynomial time
are said to run in exponential time. For example, the
task of listing all possible arrangements of n objects
grows as n FACTORIAL. As the factorial function will
exceed any polynomial function of n for sufficiently
large values of n, the operation of listing all possible
orders is exponential. Even with the most powerful
computers, exponential time computations generally
require an infeasible amount of time to complete. Polynomial time algorithms, however, are more practical.
See also NP COMPLETE; TRAVELING-SALESMAN
PROBLEM.
polyomino Generalizing the concept of a domino, a
polyomino is a shape made by adjoining 1×1 squares
along entire edge lengths in such a way that no corner
of one square lies at an interior point of another
n(n + 1)
———–
2
a x
a
a
x
a
a x
a
a x
n
n
n
n
n
n
n
n
1
1
1
1
1
1
1
0
+
⋅ + +
⋅
+
⋅
⎛
⎝
⎜
⎞
⎠
⎟
−
−
L
polyomino 405