Find number of polynomials with a root which is a root of unity

Question

Write a program which takes an integer argument and outputs the number of degree n monic polynomials with coefficients that are -1,1 or 0 which have a root which is a root of unity. To make it a little cleaner, only count polynomials with leading coefficient of 1.

You can use any language you like as long as it is freely available and the interpreter/compiler is open source. You can use the standard libraries of the language you choose but no tools specifically designed to solve this problem.

Your score is simply the length of your code.

Tests

For n = 1,2,3,4,5,6,7,8 the output should be 2,6,12,36,94, 276,790.

Degree two polynomials with a root which is a root of unity.

x^2-1,x^2-x, x^2+x, x^2-x+1, x^2+1, x^2+x+1

---

There was a bug in my numbers above and so I have just copied Peter Taylor's until I find out how to fix it.

Answer 1

GolfScript (111 107 chars)

~3\?:k,{2k*+3base{(}%:P,.*,{,{!}%-1+P{.,2$,>!{\[.0={*}+2$%\2$0={*}+%\]zip{{-}*}%\}*\0:x;{x|:x},.}do;,(},},,

Note: I disagree with some of the given test cases: I get

input   output
   1         2
   2         6
   3        12
   4        36
   5        94
   6       276
   7       790
   8      2270
   9      6412
  10     18334

Theory

Every algebraic number \$a\$ over a field \$F\$ has a minimal polynomial which is a factor of any polynomial \$P\$ in \$F[x]\$ for which \$P(a) = 0\$. For every integer \$n\$, the primitive \$n^\textrm{th}\$ roots of unity (those which are not roots of unity for any smaller \$n\$) share a minimal polynomial, the \$n^\textrm{th}\$ cyclotomic polynomial, whose degree is \$\varphi(n)\$.

So for input \$k\$ we can get an exact result by enumerating the possible functions and for each one looking for a non-trivial GCD with a cyclotomic polynomial of degree no greater than \$k\$.

There are two ways of doing that check: either by looping over the cyclotomic polynomials (or safe products thereof - e.g. \$x^n - 1\$ rather than the \$n^\textrm{th}\$ cyclotomic polynomial), or by multiplying them together and doing one GCD. My current approach is to take a very loose bound \$N = (k+1)^2\$ on the largest number whose totient is \$k\$ and then loop over \$x^i - 1\$. This is much faster than doing a single GCD with a massive polynomial, which can get some truly enormous intermediate values in the GCD, and I've managed to golf it ever so slightly more as well.

For speedier results at the cost of some characters, the bound can be improved moderately. Let \$M(n) = \max \{i : \varphi(i) = n\}\$. This has one major problem, which is that it's not well defined for odd \$n\$ greater than \$1\$ or for all even \$n\$. It also has the minor problem that it's not monotone. We need to use bound \$B(n) = \max \{i : \varphi(i) \le n\} = \max \{M(j) : j \le n\}\$.

H. Gupta defines \$A(n) = n \prod_{(p-1) \mid n} \frac{p}{p-1}\$ where \$p\$ prime and proves that \$M(n) \le A(n)\$. The bound is tight for \$n=1, 2, 8\$. Note that this is also not a monotone function: e.g. \$A(14) < A(12)\$.

We can modify the definition of \$A(n)\$ to get a looser bound which is monotone. First observe that since \$2 - 1\$ divides any integer, we can say that \$A(n) = 2n \prod_{(p-1) \mid n} \frac{p}{p-1}\$ where the \$p\$ must be odd primes. Then the number of multiplicands of the \$\prod\$ is bounded above by \$\log_3 (n+1)\$, and each multiplicand is bounded above by \$\frac32\$, so we get \$A(n) \le 2^{1 - \log_3 (n+1)} n(n+1)\$, and since this is monotone increasing for positive \$n\$ we also have \$B(n) \le 2^{1 - \log_3 (n+1)} n(n+1)\$. This bound overestimates by a factor of about \$2.5\$ at \$n=96\$, which isn't too shabby.

To use this bound, replace .* with ..(*2*2@3base,(?/). This is what I did to get the output for n=6 and n=7 in a reasonable amount of time.

More efficient calculation

;10,{
    )..).(*2*2@3base,(?/),{
        ):N,{!}%-1+
        N,0-{
            .N\%!{
                ~${
                    1$,\:Q,-),{
                        ;.0=\
                        [.0={*}+Q%]zip
                        {{-}*}%(;\
                    }%\
                }:^~;
            }{;}if
        }/
    }/]

    (\{,(1$)<},
    3@?:k,{
        2k*+3base{(}%[`{\^0-!*}+1$?]
    },
    ,p;
}/

prints the values for \$1\$ to \$10\$, taking about 8 minutes to get to \$8\$ and 125 minutes to get to \$10\$ on my computer. It applies the theory above more directly: it computes the actual cyclotomic polynomials (filtering to only include relevant ones), and then rather than doing GCD it suffices to do a division. Thus we replace a loop per (candidate, cyclotomic) tuple with a loop per cyclotomic, and makes the remaining division per (candidate, cyclotomic) work with smaller polynomials. It also has a quick-accept which speeds up testing for the successful candidates. I'm not sure whether it's possible to golf it to beat the GCD version, even ditching some of these optimisations.