Sparse polynomial

In mathematics, a sparse polynomial (also lacunary polynomial or fewnomial) is a <a href="/facts/Polynomial/Lzak8VVx">polynomial</a> that has far fewer terms than its <a href="/facts/Degree_of_a_polynomial/Bf8vEIhf">degree</a> and number of <a href="/facts/Variable_(mathematics)/VbQlrvKz">variables</a> would suggest. For example, 
 
 
 
 
 x
 
 10
 
 
 +
 3
 
 x
 
 3
 
 
 +
 1
 
 
 {\displaystyle x^{10}+3x^{3}+1}
 
 is a sparse polynomial, as it is a <a href="/facts/Trinomial/nVXhBpbH">trinomial</a> with a <a href="/facts/Degree_of_a_polynomial/Bf8vEIhf">degree</a> of 
 
 
 
 10
 
 
 {\displaystyle 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 <a href="/facts/Bernstein%25E2%2580%2593Kushnirenko_theorem/J1LY5q3k">Bernstein–Kushnirenko theorem</a> with <a href="/facts/Bezout%2527s_theorem/QxstoGnv">Bezout's theorem</a>. Research on sparse polynomials has also included work on <a href="/facts/Algorithm/fnl5NmRt">algorithms</a> whose running time grows as a function of the number of terms rather than on the degree, for problems including <a href="/facts/Polynomial_multiplication/Lzak8VVx">polynomial multiplication</a>, <a href="/facts/Polynomial_division/MgJlJ2G7">division</a>, <a href="/facts/Root-finding_algorithms/IxTDkhBq">root-finding algorithms</a>, and <a href="/facts/Polynomial_greatest_common_divisor/4c3dUbJr">polynomial greatest common divisors</a>. Sparse polynomials have also been used in pure mathematics, especially in the study of <a href="/facts/Galois_group/A0p35p5c">Galois groups</a>, because it has been easier to determine the Galois groups of certain families of sparse polynomials than it is for other polynomials. 
The <a href="/facts/Algebraic_variety/Vk7f97vn">algebraic varieties</a> determined by sparse polynomials have a simple structure, which is also reflected in the structure of the solutions of certain related <a href="/facts/Differential_equation/9MGbE3Ca">differential equations</a>. Additionally, a sparse <a href="/facts/Positivstellensatz/WIl2Mv9s">positivstellensatz</a> exists for univariate sparse polynomials. It states that the non-negativity of a polynomial can be certified by <a href="/facts/Polynomial_SOS/mwf3SeW4">SOS polynomials</a> 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 <a href="/facts/Sum_of_two_cubes/9E1yDERW">sum of two cubes</a> states that 
 
 
 
 (
 x
 +
 y
 )
 (
 
 x
 
 2
 
 
 −
 x
 y
 +
 
 y
 
 2
 
 
 )
 =
 
 x
 
 3
 
 
 +
 
 y
 
 3
 
 
 
 
 {\displaystyle (x+y)(x^{2}-xy+y^{2})=x^{3}+y^{3}}
 
. Here 
 
 
 
 
 x
 
 3
 
 
 +
 
 y
 
 3
 
 
 
 
 {\displaystyle x^{3}+y^{3}}
 
 is a sparse polynomial, since out of the 
 
 
 
 16
 
 
 {\displaystyle 16}
 
 possible terms, only 
 
 
 
 2
 
 
 {\displaystyle 2}
 
 appear.
Other examples include the identities 
 
 
 
 (
 x
 −
 y
 )
 
 ∑
 
 k
 =
 0
 
 
 N
 −
 1
 
 
 
 x
 
 k
 
 
 
 y
 
 N
 −
 1
 −
 k
 
 
 =
 
 x
 
 N
 
 
 −
 
 y
 
 N
 
 
 
 
 {\displaystyle (x-y)\sum _{k=0}^{N-1}x^{k}y^{N-1-k}=x^{N}-y^{N}}
 
 and also 
 
 
 
 (
 x
 +
 y
 )
 
 ∑
 
 k
 =
 0
 
 
 2
 n
 
 
 (
 −
 1
 
 )
 
 k
 
 
 
 x
 
 k
 
 
 
 y
 
 2
 n
 −
 k
 
 
 =
 
 x
 
 2
 n
 +
 1
 
 
 +
 
 y
 
 2
 n
 +
 1
 
 
 ,
 
 
 {\displaystyle (x+y)\sum _{k=0}^{2n}(-1)^{k}x^{k}y^{2n-k}=x^{2n+1}+y^{2n+1},}
 
 where the product of two polynomials give a spearse polynomial. The <a href="/facts/Bring_radical/uAgB4rHe">Bring–Jerrard normal form</a> of a quintic, 
 
 
 
 
 x
 
 5
 
 
 +
 p
 x
 +
 q
 ,
 
 
 {\displaystyle x^{5}+px+q,}
 
 is also a sparse polynomial.

Sparse polynomial open-in-new

Sparse polynomial