Swinnerton-Dyer polynomial

Template:Short description 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 (x+\sum _{p\in P}(\pm )\sqrt{p})$$ 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

• Template:Cite book
• Template:Citation
• Template:Mathworld
• Template:Oeis