Efficient Computation of Swinnerton-Dyer Polynomials

Question

the Swinnerton-Dyer polynomials are defined as $$SD_n(x) = \prod(x \pm \sqrt{2} \pm \sqrt{3} \pm ... \pm \sqrt{p_n})$$ where the product is taken over all possible permutations of $+$ or $-$ signs. $p_n$ is the nth prime number and the sum is taken over primes smaller or equal to $p_n$.

My idea for computation of their coefficients (which turns out to be faster than just expanding) is the following recursive procedure:

1. Compute $p(x) = SD_{n-1}(x)$
   

2. Compute $p(x+\sqrt{p_n})$ and $p(x-\sqrt{p_n})$
   

3. Expand the product $p(x+\sqrt{p_n})p(x-\sqrt{p_n})$

My question is now: Is there a more efficient way of computing $SD_n(x)$ in expanded form (Maybe even without the use of radicals in the computation)?

Answer 1

Your recursion works, and it might be not the most efficient. In as far I would be also interested in better evaluation strategies or other polynomials that can be also used to compute the reciprocal as I do at the end of this answer.

I was trying it symbolically, and do get also integer coefficients when $p_1,..,p_n$ are not only prime numbers but other rational numbers. I use the library(groebner/generic), which is a Jekejeke Prolog package for polynomials and vectors. The following Prolog program does the job:

f(L, X, Y) :-
   L =.. [vector,A,B|H],
   R =.. [vector,B|H],
   Y is f(R,X-A)*f(R,X+A).
f(vector(A), X, Y) :-
   Y is (X-A)*(X+A).

You can then invoke it as follows, and all the coffections use squares of the roots:

?- Y is f([A],X).
Y is -A^2+X^2

?- Y is f([A,B],X).
Y is A^4-2*A^2*B^2+B^4-(2*A^2+2*B^2)*X^2+X^4 

?- Y is f([A,B,C],X).
Y is A^8-4*A^6*B^2+6*A^4*B^4-4*A^2*B^6+B^8-
(4*A^6-4*A^4*B^2-4*A^2*B^4+4*B^6)*C^2+(6*A^4+4*A^2*B^2+6*B^4)*C^4-
(4*A^2+4*B^2)*C^6+C^8-(4*A^6-4*A^4*B^2-4*A^2*B^4+4*B^6-
(4*A^4-40*A^2*B^2+4*B^4)*C^2-(4*A^2+4*B^2)*C^4+4*C^6)*X^2+
(6*A^4+4*A^2*B^2+6*B^4+(4*A^2+4*B^2)*C^2+6*C^4)*X^4-
(4*A^2+4*B^2+4*C^2)*X^6+X^8 

By construction $f((x_1,..,x_n),x)$ is divisible by $x+x_1+..+x_n$, let denote the result of this divison by $g((x_1,..,x_n),x)$, a recursion for this function can be also built. So that in the end we have a way to compute ${(p+\sqrt{p_1}+..+\sqrt{p_n})}^{-1}$ as $g((\sqrt{p_1},..,\sqrt{p_n}),p) / f((\sqrt{p_1},..,\sqrt{p_n}),p)$.