3
$\begingroup$

In the wikipedia page Uses of trigonometry under the section Number theory and in the page for the Möbius function there is an explanation for how to calculate the Möbius function from the GCD=1 pattern:

$\mu(n) = \sum\limits_{\stackrel{1\le k \le n }{ \gcd(k,\,n)=1}} e^{2\pi i \tfrac{k}{n}}$

Consider the infinite matrix starting:

$\displaystyle T(n,k) = \begin{bmatrix} +1&+1&+1&+1&+1&+1&+1 \\ +1&-1&+1&-1&+1&-1&+1 \\ +1&+1&-2&+1&+1&-2&+1 \\ +1&-1&+1&-1&+1&-1&+1 \\ +1&+1&+1&+1&-4&+1&+1 \\ +1&-1&-2&-1&+1&+2&+1 \\ +1&+1&+1&+1&+1&+1&-6 \end{bmatrix}$

defined by the recurrence:

$\displaystyle T(n,1)=1, T(1,k)=1, n>=k: -\sum\limits_{i=1}^{k-1} T(n-i,k), n<k: -\sum\limits_{i=1}^{n-1} T(k-i,n)$

Does the Möbius function $\displaystyle \mu(n)$ also equal the following:

$\displaystyle \mu(n) = \frac{1}{n} \sum\limits_{k=1}^{k=n} T(n,k) \cdot e^{i 2 \pi \frac{k}{n}}$

As a Mathematica program this is:

Clear[nn, t, n, k, a, b];
nn = 15;
t[n_, 1] = 1;
t[1, k_] = 1;
t[n_, k_] := 
  t[n, k] = 
   If[n >= k, -Sum[t[n - i, k], {i, 1, k - 1}], -Sum[
      t[k - i, n], {i, 1, n - 1}]];
MatrixForm[Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}]];
MatrixForm[
 Table[N[Total[Table[1/n*t[n, k]*Exp[I*2*Pi*k/n], {k, 1, n}]]], {n, 1,
    nn}]]

And if needed, the matrix $\displaystyle T(n,k)$ as Excel cell formulas is:

European:

=if(or(row()=1; column()=1); 1; if(row()>=column(); -sum(indirect(address(row()-column()+1; column(); 4)&":"&address(row()-1; column(); 4); 4)); -sum(indirect(address(column()-row()+1; row(); 4)&":"&address(column()-1; row(); 4); 4))))

American:

=if(or(row()=1, column()=1), 1, if(row()>=column(), -sum(indirect(address(row()-column()+1, column(), 4)&":"&address(row()-1, column(), 4), 4)), -sum(indirect(address(column()-row()+1, row(), 4)&":"&address(column()-1, row(), 4), 4))))

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.