Jump to content

Swinnerton-Dyer polynomial

From Wikipedia, the free encyclopedia

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 of prime numbers, the Swinnerton-Dyer polynomial associated to is the polynomial: where the product extends over all choices of sign in the enclosed sum. The polynomial has degree and integer coefficients, which alternate in sign. If , then is reducible modulo for all primes , into linear and quadratic factors, but irreducible over . The Galois group of is .

The first few Swinnerton-Dyer polynomials are:

References

[edit]
  • 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.
  • OEISA153731