Do these series converge to the Mangoldt function?

Question

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.

Answer 1

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.

Answer 2

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...