In mathematics, a sparse polynomial (also lacunary polynomial or fewnomial) is a

polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...

that has far fewer terms than its degree and number of

variables Variable may refer to: Computer science * Variable (computer science), a symbolic name associated with a value and whose associated value may be changed Mathematics * Variable (mathematics), a symbol that represents a quantity in a mathemat ...

would suggest. For example,

x^ + 3x^3 + 1

is a sparse polynomial, as it is a

trinomial In elementary algebra, a trinomial is a polynomial consisting of three terms or monomials. Examples of trinomial expressions # 3x + 5y + 8z with x, y, z variables # 3t + 9s^2 + 3y^3 with t, s, y variables # 3ts + 9t + 5s with t, s variables # a ...

with a degree of

10

. The motivation for studying sparse polynomials is to concentrate on the structure of a polynomial's monomials instead of its degree, as one can see, for instance, by comparing

Bernstein–Kushnirenko theorem The Bernstein–Kushnirenko theorem (or Bernstein–Khovanskii–Kushnirenko (BKK) theorem), proven by David Bernstein and in 1975, is a theorem in algebra. It states that the number of non-zero complex solutions of a system of Laurent polynomia ...

with Bezout's theorem. Research on sparse polynomials has also included work on

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

s whose running time grows as a function of the number of terms rather than on the degree, for problems including polynomial multiplication, division,

root-finding algorithms In numerical analysis, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function is a number such that . As, generally, the zeros of a function cannot be computed exactly nor e ...

, and

polynomial greatest common divisor In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common d ...

s. Sparse polynomials have also been used in pure mathematics, especially in the study of

Galois group In mathematics, in the area of abstract algebra known as Galois theory, the Galois group of a certain type of field extension is a specific group associated with the field extension. The study of field extensions and their relationship to the pol ...

s, because it has been easier to determine the Galois groups of certain families of sparse polynomials than it is for other polynomials. The

algebraic varieties Algebraic varieties are the central objects of study in algebraic geometry, a sub-field of mathematics. Classically, an algebraic variety is defined as the set of solutions of a system of polynomial equations over the real or complex numbers. ...

determined by sparse polynomials have a simple structure, which is also reflected in the structure of the solutions of certain related differential equations. Additionally, a sparse positivstellensatz exists for univariate sparse polynomials. It states that the non-negativity of a polynomial can be certified by SOS polynomials whose degree only depends on the number of monomials of the polynomial. Sparse polynomials often come up in sum or difference of powers equations. The

sum of two cubes In mathematics, the sum of two cubes is a cubed number added to another cubed number. Factorization Every sum of cubes may be factored according to the identity a^3 + b^3 = (a + b)(a^2 - ab + b^2) in elementary algebra. Binomial numbers g ...

states that

(x + y)(x^2 - xy + y^2) = x^3 + y^3

. Here

x^3 + y^3

is a sparse polynomial, since out of the

16

possible terms, only

2

appear. Other examples include the identities

(x - y) \sum_^ x^k y^ = x^N - y^N

and also

(x + y) \sum_^(-1)^k x^k y^ = x^ + y^,

where the product of two polynomials give a spearse polynomial. The Bring–Jerrard normal form of a quintic,

x^5 + px + q,

is also a sparse polynomial.

References

Polynomials {{polynomial-stub

See also

References