Take the 2-minute tour ×
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.

Jeffrey O. Shallit formulated this recurrence for me: $\displaystyle T(n,1)=1, k>1: T(n,k) = \sum\limits_{i=1}^{k-1} T(n-i,k-1)-\sum\limits_{i=1}^{k-1} T(n-i,k)$

which is the lower triangular array equal to 1 if k divides n, 0 otherwise.

By changing the recurrence so that it takes values from either the vertical or horizontal direction:

$\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)$

we get this array 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}$

Do the series $\displaystyle \sum\limits_{k=1}^{\infty}\frac{T(n,k)}{k}$ $\;$ converge to the Mangoldt function $\Lambda(n)$?

http://mathworld.wolfram.com/MangoldtFunction.html

Edit 14.7.2011, added Mathematica program:

Clear[t]; 
nn = 100; 
mm = 15; 
t[n_, 1] = 1; 
t[1, k_] = 1; 
t[n_, k_] := 
t[n, k] = 
If[n < k, 
If[And[n > 1, k > 1], Sum[-t[k - i, n], {i, 1, n - 1}], 0], 
If[And[n > 1, k > 1], Sum[-t[n - i, k], {i, 1, k - 1}], 0]]; 
a = Table[Table[t[n, k], {k, 1, mm}], {n, 1, nn}]; 
b = Range[1, nn]; 
c = a/b; 
MatrixForm[c]; 
d = N[Table[Total[c[[All, i]]], {i, 1, mm}]] 
d[[1]] = 0; 
mangoldt = Exp[d] 
mangoldtexponentiated = Round[Exp[d]]

that outputs the sequence: $1, 2, 3, 2, 5, 1, 7, 2, 3, 1, 11, 1, 13, 1, 1...$ which is the Mangoldt function exponentiated.


Edit 9.2.2014:

Just for memory:

$$\varphi (n) = n\lim\limits_ {s \rightarrow 1}\zeta (s)\sum\limits_ {d | n}\mu (d) (e^{1/d})^{(s - 1)}$$

$$a(n) = \lim\limits_{s \rightarrow 1} \zeta(s)\sum\limits_{d|n} \mu(d)(e^{d})^{(s-1)}$$

$$\Lambda(n) =\sum\limits_{k=1}^{\infty} \frac{a(GCD(n,k))}{k}$$

$$\Lambda(n)=\lim\limits_{s \rightarrow 1} \zeta(s)\sum\limits_{d|n} \frac{\mu(d)}{d^{(s-1)}}$$

$$\text{Fourier Transform of } \Lambda(n) \sim \sum\limits_{n=1}^{n=k} \frac{1}{n} \zeta(1/2+i \cdot t)\sum\limits_{d|n} \frac{\mu(d)}{d^{(1/2+i \cdot t-1)}}$$


Edit 3.3.2014:

Just for memory: Mathematica:

nn = 12;
mm = nn;
MatrixForm[
 Chop[N[Total[
    Transpose[
     Table[Table[
       If[Mod[n1, k1] == 0, 
        Table[(Table[
             Sum[Exp[-a*b/n*2*Pi*I], {b, 1, n}], {a, 1, mm}]), {n, 1, 
            nn}][[n1/k1]]*MoebiusMu[n1/k1], 0], {k1, 1, nn}], {n1, 1, 
       nn}]]]]]]
share|improve this question
2  
Having solved this, I'm wondering how you ever came up with the conjecture without already seeing the connection? –  joriki Jul 16 '11 at 8:00
    
@joriki: Using the If GCD=1 then 1 else 0 pattern as input to the upper triangular half of a square array satisfying the first recurrence in the question above: Seqfan , we get the Euler totient - 1 where k divides n. As the GCD pattern is symmetric it is natural to ask if the array will be symmetric if the recurrence is allowed to run in both row and column direction. Putting the mod function around recurrence. "Recurrence modulo 2", we get a pattern of zeros and ones. By then setting $T(1,1)=0$ we get prime row sums equal to 2. –  Mats Granvik Jul 16 '11 at 11:53
    
I was asking not so much about how you came up with the recursion, but about how you came up with the conjecture for the series. Why were you interested in summing it with $1/k$ if you didn't already see how this would give a nice result? –  joriki Jul 16 '11 at 12:00
    
@joriki: By then removing the modulo function around the recurrence and letting $T(1,1)=0$ remain, we get row sums equal to zero for all rows in the lower triangular part of the this square array with recurrences running in row and column direction. Not otherwise familiar with Dirichlet characters, but knowing that dividing rows with $n$ is a common thing to do and because row sums equal 0 in lower triangular part and as square array is symmetric we can divide columns with k instead. Then looking at the sign of the row sums we get negative signs for $n=6,12,18,20,24,28,30...$. (more) –  Mats Granvik Jul 16 '11 at 12:06
    
@joriki: I am coming to that. By then letting $k$ that I divided the lower triangular part with, increase, then again by looking at the signs of row sums we notice that they are all negative for non-prime powers. So know we know that this second array appears to have something to do with prime powers. –  Mats Granvik Jul 16 '11 at 12:14
show 2 more comments

2 Answers

up vote 8 down vote accepted

Yes, they do for $n\neq1$. This can be proved in two steps:

  1. The coefficients are given by $T(n,k)=\sum_{d\mid\gcd(n,k)}\mu(d)d$, where $\mu$ is the Möbius function.
  2. $\displaystyle \sum\limits_{k=1}^{\infty}\frac1k\sum_{d|\gcd(n,k)}\mu(d)d=\Lambda(n)$ for $n\neq1$, where $\Lambda$ is the von Mangoldt function.

We can prove 1. by induction over the recursion steps. The equation holds for the initial values: $T(n,1)=T(1,k)=\sum_{d\mid1}\mu(d)d=\mu(1)=1$. Assume that it holds before the recursion step for $T(n,k)$. Since the recursion is symmetric with respect to interchange of $k$ and $n$, we can assume $n\ge k$. Then we have

$$ \begin{eqnarray} \sum_{d\mid\gcd(n,k)}\mu(d)d-T(n,k) &=& \sum_{d\mid\gcd(n,k)}\mu(d)d+\sum_{i=1}^{k-1}T(n-i,k) \\ &=& \sum_{d\mid\gcd(n,k)}\mu(d)d+\sum_{i=1}^{k-1}\sum_{d\mid\gcd(n-i,k)}\mu(d)d \\ &=& \sum_{i=0}^{k-1}\sum_{d\mid\gcd(n-i,k)}\mu(d)d \;. \end{eqnarray} $$

Every square-free divisor $d$ of $k$ occurs $k/d$ times in this sum, so its contribution sums to $(k/d)\mu(d)d=\mu(d)k$, and the sum becomes

$$\sum_{d|k}\mu(d)k=k\sum_{d|k}\mu(d)=0\;,$$

since $k\neq1$ (see here). This proves the induction claim.

To prove 2., note that the series in question is the series

$$\sum_{k=1}^{\infty}\frac1k\sum_{d|\gcd(n,k)}\mu(d)dx^k$$

evaluated at $x=1$, and this is

$$ \begin{eqnarray} \sum_{k=1}^{\infty}\frac1k\sum_{d|\gcd(n,k)}\mu(d)dx^k &=& \sum_{d|n}\mu(d)d\sum_{k=1\atop d|k}^{\infty}\frac{x^k}k \\ &=& \sum_{d|n}\mu(d)d\sum_{l=1}^{\infty}\frac{x^{ld}}{ld} \\ &=& \sum_{d|n}\mu(d)\sum_{l=1}^{\infty}\frac{(x^d)^l}l \\ &=& -\sum_{d|n}\mu(d)\log\left(1-x^d\right)\;. \end{eqnarray} $$

Since $\sum_{d|n}\mu(d)=0$ for $n\neq1$ (see above), we can rewrite this as

$$-\sum_{d|n}\mu(d)\log\left(1-x^d\right)=-\sum_{d|n}\mu(d)\log\left(\frac{1-x^d}{1-x}\right)=-\sum_{d|n}\mu(d)\log\left(\sum_{j=0}^{d-1}x^j\right)\;,$$

which evaluates to

$$-\sum_{d|n}\mu(d)\log d=\Lambda(n)$$

at $x=1$ (see here).

To make this argument rigorous, we need to invoke Abel's theorem: All the power series occurring in the proof have radius of convergence $1$ and converge at $x=1$, and hence converge at $x=1$ to the function whose Taylor series they are.

share|improve this answer
add comment

Here's your Mathematica code, tidied up slightly:

nn = 100; mm = 15;
t[n_, 1] = 1; t[1, k_] = 1;
t[n_, k_] := t[n, k] =
      With[{p = Min[n, k], q = Max[n, k]},
        -Sum[t[q - i, p], {i, p - 1}]];
a = Table[t[n, k], {n, nn}, {k, mm}];
b = Range[nn]; c = a/b;
MatrixForm[c];
d = N[Table[Apply[Plus, c[[All, i]]], {i, mm}]];
d[[1]] = 0;
mangoldt = Exp[d];
mangoldtexponentiated = Round[Exp[d]]

I suspect your two-dimensional recursion can be modified to reduce the memory required; let me think about it for a bit...

share|improve this answer
    
I think it would be more efficient to use the non-recursive expression provided in my answer -- this only involves iterating over $d$ and adding/subtracting $d$ to/from a fraction $d^{-2}$ of the entries. –  joriki Jul 16 '11 at 9:08
    
It certainly would, if you've a way to evaluate Möbius's function in your computing environment. (I know Mathematica can, but this at least can be translated to other environments...) –  J. M. Jul 16 '11 at 11:35
add comment

Your Answer

 
discard

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

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