Swinnerton-Dyer polynomial

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: $$f_{\{2\}}(x)=x^{2}-2=(x-{\sqrt {2}})(x+{\sqrt {2}})$$ $$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}})$$ $$f_{\{2,3,5\}}(x)=x^{8}-40x^{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