Swinnerton-Dyer polynomial explained

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)\; =\; \backslash prod\; \backslash left(x\; +\; \backslash sum\_\; (\backslash pm)\; \backslash sqrt\backslash 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 Q . The Galois group of f _{P(x)} is Z ^{|P|} _{2} .

The first few Swinnerton-Dyer polynomials are:$$\backslash mathcal\; P\; =\; \backslash :\backslash quad\; f\_P(x)\; =\; (x-\backslash sqrt\; 2)(x+\backslash sqrt\; 2)\; =\; x^2-2$$$$\backslash mathcal\; P\; =\; \backslash :\backslash quad\; f\_P(x)\; =\; (x-\backslash sqrt\; 2-\backslash sqrt\; 3)(x-\backslash sqrt\; 2+\backslash sqrt\; 3)(x+\backslash sqrt\; 2\; -\backslash sqrt\; 3)(x+\backslash sqrt\; 2+\backslash sqrt\; 3)\; =\; x^4-10x^2+1$$$$\backslash mathcal\; P\; =\; \backslash :\backslash quad\; f\_P(x)\; =\; x^8-20x^6+352x^4-960x^2+576.$$

References

• Book: Joachim . von zur Gathen . Jürgen . Gerhard . Modern Computer Algebra . Cambridge University Press . April 2013 . 9781107039032 . Third .