Swinnerton-Dyer polynomial

also: swinnerton dyer, recombination

The product over every sign choice of x minus a sum of distinct square roots. These are irreducible over Z and split into factors of degree at most two modulo every prime, which makes them the worst case for factorization: recombination has to test every subset of the mod-p factors before concluding there is nothing to find.

The product over every sign choice of $x$ minus a sum of distinct square roots:

SD_{k} (x) = ε \in {\pm 1}^{k} \prod (x - \sum_{i = 1}^{k} ε_{i} p_{i})

Expanding leaves integer coefficients and degree $2^{k}$ . For $p_{1}, p_{2} = 2, 3$ it is $x^{4} - 10 x^{2} + 1$ .

These polynomials are irreducible over $Z$ and yet factor into pieces of degree at most two modulo every prime. The Galois group is $(Z /2)^{k}$ , which has no element of order greater than two, so no Frobenius element can act as a long cycle and no residue degree can exceed two.

Degree 8, modulo 11. Four quadratics, and the polynomial is irreducible over Z.

> factormod x^8 - 40*x^6 + 352*x^4 - 960*x^2 + 576, 11
1 * (x^2 + 4*x + 2)^1 * (x^2 + 7*x + 2)^1
  * (x^2 + 2*x + 10)^1 * (x^2 + 9*x + 10)^1

That makes them the worst case for the Zassenhaus approach, and the reason it is worth naming them. No prime gives a useful head start, so recombination has to test every subset of the mod- $p$ factors before concluding that none combine. At degree 16 that is 8 pieces and 256 subsets, and the count doubles with every square root added. They are also what motivated the van Hoeij algorithm, which replaces the subset search with lattice reduction and is polynomial where this is exponential.