Swinnerton-Dyer_polynomial References

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 $P$ of prime numbers, the Swinnerton-Dyer polynomial associated to $P$ is the polynomial:

f_{P}(x)=\prod \left(x+\sum _{p\in P}(\pm ){\sqrt {p}}\right)

where the product extends over all

2^{|P|}

choices of sign in the enclosed sum. The polynomial

f_{P}(x)

has degree

2^{|P|}

and integer coefficients, which alternate in sign. If

|P|>1

, then

f_{P}(x)

is reducible modulo

p

for all primes

p

, into linear and quadratic factors, but irreducible over

\mathbb {Q}

. The Galois group of

f_{P}(x)

is

\mathbb {Z} _{2}^{|P|}

.

The first few Swinnerton-Dyer polynomials are:

{\mathcal {P}}=\{2\}:\quad f_{P}(x)=(x-{\sqrt {2}})(x+{\sqrt {2}})=x^{2}-2

{\mathcal {P}}=\{2,3\}:\quad f_{P}(x)=(x-{\sqrt {2}}-{\sqrt {3}})(x-{\sqrt {2}}+{\sqrt {3}})(x+{\sqrt {2}}-{\sqrt {3}})(x+{\sqrt {2}}+{\sqrt {3}})=x^{4}-10x^{2}+1

{\mathcal {P}}=\{2,3,5\}:\quad f_{P}(x)=x^{8}-20x^{6}+352x^{4}-960x^{2}+576.

References

von zur Gathen, Joachim; Gerhard, Jürgen (April 2013). Modern Computer Algebra (Third ed.). Cambridge University Press. ISBN 9781107039032.
Vardi, I (1991), Computational Recreations in Mathematica, Addison-Wesley, pp. 225–226
Weisstein, Eric W. "Swinnerton-Dyer Polynomial". MathWorld.
OEIS: A153731