In algebra, the Swinnerton-Dyer polynomials are a family of polynomials, introduced by Peter Swinnerton-Dyer, that serve as examples where polynomial factorization algorithms have worst-case runtime.
They have the property of being reducible modulo every prime, while being irreducible over the rational numbers.
They are a standard counterexample in number theory.
Given a finite set
{\displaystyle P}
of prime numbers, the Swinnerton-Dyer polynomial associated to
{\displaystyle P}
is the polynomial:
f
( x ) = ∏
∑
where the product extends over all
choices of sign in the enclosed sum.
The polynomial
has degree
and integer coefficients, which alternate in sign.
is reducible modulo
for all primes
, into linear and quadratic factors, but irreducible over
The Galois group of
The first few Swinnerton-Dyer polynomials are:
{\displaystyle f_{\{2\}}(x)=x^{2}-2=(x-{\sqrt {2}})(x+{\sqrt {2}})}
{\displaystyle f_{\{2,3\}}(x)=x^{4}-10x^{2}+1=(x-{\sqrt {2}}-{\sqrt {3}})(x-{\sqrt {2}}+{\sqrt {3}})(x+{\sqrt {2}}-{\sqrt {3}})(x+{\sqrt {2}}+{\sqrt {3}})}