3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ And I see 32 such degree 3 polynomials one of whose roots is a root of unity (20 if 0*x^3 doesn't count). \$\endgroup\$ – David Hammen Jun 1 '14 at 10:28
  • \$\begingroup\$ @DavidHammen Yes I get the same numbers as you do. (Ignoring the leading coefficient being zero, because I think by definition of an nth order polynomial, the nth coefficient is non-zero.) \$\endgroup\$ – Martin Ender Jun 1 '14 at 10:38
  • \$\begingroup\$ I was off on my count. I count four first order polynomials that match the criteria: 1*x+1, 1*x-1, -1*x+1, and -1*x-1. All of these are also second degree polynomials (with a leading coefficient of zero), plus 12 more with a leading coefficient of +1 or -1, making 16 second order polynomials that match the criteria. \$\endgroup\$ – David Hammen Jun 1 '14 at 10:45
  • \$\begingroup\$ Do you agree with my degree two list (just added to the question)? \$\endgroup\$ – user9206 Jun 1 '14 at 11:02
  • 1
    \$\begingroup\$ Hm, I still get different results for larger n. In particular, 36, 276, 790 and 2267 for n = 4, 6, 7, 8. I might still be doing something wrong though. \$\endgroup\$ – Martin Ender Jun 1 '14 at 12:38
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I suppose I can't ask you if you get the same numbers as me then? :) \$\endgroup\$ – user9206 Jun 2 '14 at 12:31
  • \$\begingroup\$ @Lembik, not quite. \$\endgroup\$ – Peter Taylor Jun 2 '14 at 13:04
  • \$\begingroup\$ Hm interesting, I get the same number as you for n = 4. I'd be really interested how your series continues, if you can get to speed up the performance. ;) \$\endgroup\$ – Martin Ender Jun 2 '14 at 13:08
  • \$\begingroup\$ I added a full list for degree 4 to the question. I would be very interested to know which extra polynomial you have. \$\endgroup\$ – user9206 Jun 2 '14 at 16:49
  • \$\begingroup\$ @Lembik, on the assumption that x^4+x^3x^2-1 in your list should be x^4+x^3-x^2-1, the one you're missing is x^4-x^2+1, the 12th cyclotomic polynomial. \$\endgroup\$ – Peter Taylor Jun 2 '14 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy