Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 Mobius 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))))

share|improve this question

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.