3
$\begingroup$

I want to observe the distribution of the cyclotomic coefficients for x^n-1. To do this, I created the following user function:

cyclotomicCoefficientList[n_] := 
Module[{},
       coeffi = CoefficientList[Cyclotomic[n, x], x]; 
       max = Max[coeffi]; min = Min[coeffi];  
       list = DeleteCases[Table[  Row[{i, Style[" \[RightTeeArrow] ", Bold],
              Count[coeffi, i]}], {i, max, min, -1}], Row[{_Integer, _, 0}]]; 
       Multicolumn[list, If[Length[list] < 8, Length[list], 6], 
                   Frame -> All, FrameStyle -> Directive[Gray, Thin],                  
                   ItemStyle -> 12, ItemSize -> All, 
                   Spacings -> {1, 0.75}, Alignment -> {Center, Center}]  ]

With this function I observe the distribution of the cyclotomic coefficients for x^n-1 to the value of n=3*5*7*11*13*17=255255.

However, for a larger number n=3*5*7*11*13*17*19=4849845, it took a lot of computation time for a general PC, and still no results were obtained.

Of course, this execution was done without outputting the symbol (;).

For this reason, I have looked at the usage of CPU and RAM for my PC.

(As a reference, my PC's CPU is i7-2.6 and RAM is 16G.)

As a result, my CPU usage was 16% and memory was only 4G.

Is there any way to get more of my PC resources and get the results of this run?

For example, you might want to use Mathematica functions in parallel computing.

Is there a way to optimize my defined function?

I want to find the n value that the coefficient is ±2017.

$\endgroup$
4
$\begingroup$

I trust you realize that for $n=3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 = 4849845$, the cyclotomic polynomial will be a polynomial of order $\phi(4849845) = 1658880$ where $\phi$ is the Euler totient function. I don't have the patience to figure out whether Mathematica can compute this in a reasonable amount of time. So, here is an alternative, which is quite slow, but should produce an answer in under 2 hours.

The idea is to use a recurrence relation to determine the coefficients. One such recurrence (valid only for squarefree n) is:

$$\Phi _n(x)=\sum _ {j=0}^{\phi (n)} a_{n,j} x^j$$

where

$$a_{n,j} = - \frac{\mu(n)}{j} \sum_{m=0}^{j-1} a_{n,m} \mu(gcd(n, j-m)) \phi(gcd(n, j-m))$$

This can be coded up as follows:

ccycle[n_,max_:Automatic]:=Module[{gcd,vec, tot=EulerPhi[n]},
    gcd=GCD[n,Range[tot]];
    vec=-MoebiusMu[n]MoebiusMu[gcd]EulerPhi[gcd];
    m=If[max===Automatic,tot,max];
    fc[vec, If[max===Automatic, tot, max]+1]
]

fc = Compile[{{v,_Integer,1},{max,_Integer}},
    Module[{res = ConstantArray[0, max]},
        res[[1]]=1;
        Do[
            res[[i]] = v[[i-1;;1;;-1]] . res[[;;i-1]]/(i-1),
            {i,2,max}
        ];
        res
    ]
];

Note the second argument of ccycle. It is there to check how the function scales when computing parts of the full cyclotomic polynomial. Now, let's check ccycle vs the built-in Cyclotomic:

r1 = ccycle[3 5 7];
r2 = CoefficientList[Cyclotomic[3 5 7, x], x];
r1 === r2

True

r1 = ccycle[3 5 7 11];
r2 = CoefficientList[Cyclotomic[3 5 7 11, x], x];
r1 === r2

True

r1 = ccycle[3 5 7 11 13 17];
r2 = CoefficientList[Cyclotomic[3 5 7 11 13 17, x], x];
r1 === r2

True

Finally, let's see how computing the desired cyclotomic coefficients scales:

ccycle[3 5 7 11 13 17 19, 100]; //MaxMemoryUsed //AbsoluteTiming
ccycle[3 5 7 11 13 17 19, 200]; //MaxMemoryUsed //AbsoluteTiming
ccycle[3 5 7 11 13 17 19, 400]; //MaxMemoryUsed //AbsoluteTiming
ccycle[3 5 7 11 13 17 19, 800]; //MaxMemoryUsed //AbsoluteTiming
ccycle[3 5 7 11 13 17 19, 1600]; //MaxMemoryUsed //AbsoluteTiming
ccycle[3 5 7 11 13 17 19, 3200]; //MaxMemoryUsed //AbsoluteTiming
ccycle[3 5 7 11 13 17 19, 6400]; //MaxMemoryUsed //AbsoluteTiming
ccycle[3 5 7 11 13 17 19, 12800]; //MaxMemoryUsed //AbsoluteTiming

{3.00648, 159239128}

{3.40589, 159239128}

{3.93661, 159239128}

{5.24564, 159239128}

{7.64084, 159239128}

{12.9667, 159239128}

{23.0814, 159239128}

{44.5148, 159239128}

Computing the $\mu \times \phi$ vector takes about 3 seconds. Subtracting this from the times, it seems that the computation scales linearly with the number of terms of the cyclotomic polynomial being returned. Hence, I estimate that computing the full coefficient list will take under 2 hours. Also note that maximum memory used doesn't change. So, there shouldn't be any memory issues with this approach.

$\endgroup$
  • $\begingroup$ Thanks for the detailed answers and advice. I am going to calculate the total coefficient. Even if it takes 2 hours ... I will check whether there are 2017 in coefficient. Thank you again. $\endgroup$ – user21427 Jun 15 '17 at 5:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.