# Möbius function from random number sequence

Consider some arbitrary number sequence like the decimal expansion of $\pi$ = {3, 1, 4, 1, 5, 9, 2}. Prepend the sequence with the number $1$ so that you get {1, 3, 1, 4, 1, 5, 9, 2}.

Then plug it into the first column in a matrix that has the following recurrence definition:

\begin{align} T(n,1) &= (n-1)\text{th digit of }\pi, \\ T(n,2) &= T(n,1) - T(n-1,2), \\ \text{for } k>2, T(n,k) &= \sum\limits_{i=1}^{k-1} T(n-i,k-1)-\sum\limits_{i=1}^{k-1} T(n-i,k) \end{align}

That table looks like this:

$$\displaystyle \left( \begin{array}{cccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 3 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & -2 & 3 & 0 & 0 & 0 & 0 & 0 \\ 4 & 6 & -2 & 3 & 0 & 0 & 0 & 0 \\ 1 & -5 & 3 & -2 & 3 & 0 & 0 & 0 \\ 5 & 10 & 0 & 3 & -2 & 3 & 0 & 0 \\ 9 & -1 & 2 & -3 & 3 & -2 & 3 & 0 \\ 2 & 3 & 7 & 7 & -3 & 3 & -2 & 3 \end{array} \right)$$

Then calculate the matrix inverse of the matrix above:

$$\displaystyle \left( \begin{array}{cccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & \frac{1}{3} & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & \frac{2}{9} & \frac{1}{3} & 0 & 0 & 0 & 0 & 0 \\ 0 & -\frac{14}{27} & \frac{2}{9} & \frac{1}{3} & 0 & 0 & 0 & 0 \\ -1 & -\frac{1}{81} & -\frac{5}{27} & \frac{2}{9} & \frac{1}{3} & 0 & 0 & 0 \\ 1 & -\frac{146}{243} & -\frac{28}{81} & -\frac{5}{27} & \frac{2}{9} & \frac{1}{3} & 0 & 0 \\ -1 & -\frac{688}{729} & -\frac{11}{243} & -\frac{1}{81} & -\frac{5}{27} & \frac{2}{9} & \frac{1}{3} & 0 \\ 0 & \frac{694}{2187} & -\frac{850}{729} & -\frac{92}{243} & -\frac{1}{81} & -\frac{5}{27} & \frac{2}{9} & \frac{1}{3} \end{array} \right)$$

Why then is there the Möbius function sequence in the first column?

I have checked this for random sequences in programs like this:

(*Mathematica*)
Clear[t, n, k, a, b];
nn = 8;
a = Flatten[{1, RealDigits[N[Pi, nn - 1]][[1]]}]
Length[a]
t[n_, 1] := t[n, 1] = a[[n]];
t[n_, k_] :=
t[n, k] =
If[And[n > 1, k > 1],
If[k == 2, t[n, k - 1] - t[n - 1, k],
Sum[t[n - i, k - 1], {i, 1, k - 1}] -
Sum[t[n - i, k], {i, 1, k - 1}]], 0];
A = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A]
MatrixForm[Inverse[A]]


for up to 100 times 100 matrices and I always get the Möbius function in the first column.

I believe it has something do with the fact that the divisibility matrix equal to 1 if k divides n and 0 otherwise:

$$\displaystyle \left( \begin{array}{cccccccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \end{array} \right)$$

satisfies the recurrence, that (edit 21.7.2014) Jeffrey Shallit formulated for me:

\begin{align} T(n,1) &= 1, \\ \text{for } 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) \end{align}

and also the recurrence:

\begin{align} T(n,1) &=1, \\ T(n,2) &= T(n,1)-T(n-1,2),\\ \text{for } k>2, T(n,k) &= \sum\limits_{i=1}^{k-1} T(n-i,k-1) -\sum\limits_{i=1}^{k-1} T(n-i,k) \end{align} which is the same as the first recurrence in the beginning of the question except that the first column here is equal to 1,1,1...

Edit 28.3.2014:

(*Mathematica Mats Granvik 28.3.2014*)
Clear[A, t, n, k, a, nn];
nn = 8;
a = Table[StringJoin[{"x", ToString[n]}], {n, 1, nn}]
Length[a]
t[n_, 1] := t[n, 1] = a[[n]];
t[n_, k_] :=
t[n, k] =
If[And[n > 1, k > 1],
If[k == 2, t[n, k - 1] - t[n - 1, k],
Sum[t[n - i, k - 1], {i, 1, k - 1}] -
Sum[t[n - i, k], {i, 1, k - 1}]], 0];
A = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A]
MatrixForm[a[[1]]*Inverse[A]]


Outputs: 1,-1,-1,0,-1,1,-1,0,...

Edit 7.4.2013:

Input: {"x0", "x1", "x2", "x3", "x4", "x5", "x6", "x7", "x8", "x9", "x10"}

Mathematica program:

(*Mathematica Mats Granvik 7.4.2014*)
Clear[A, t, n, k, a, nn];
nn = 11;
a = Table[StringJoin[{"x", ToString[n - 1]}], {n, 1, nn}]
Length[a]
t[n_, 1] := t[n, 1] = If[n <= 3, 1, a[[n]]];
t[n_, k_] :=
t[n, k] =
If[n >= k,
If[n <= 3, 1,
If[And[k > 1],
If[Or[k == 2, k == 3],
t[n, k - 1] - Sum[t[n - i, k], {i, 1, k - 1}],
If[k >= 4,
Sum[t[n - i, k - 1], {i, 1, k - 2}] -
Sum[t[n - i, k], {i, 1, k - 1}], 0], 0], 0, 0], 0], 0];
A = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A]
Inverse[A][[2 ;; nn, 1]]


Output; {-1, 0, -1, -1, -2, -1, -2, -2, -2, -1}

Which is the Mertens function with the first term negated.

Edit 21.7.2014:

The matrix inverse of this triangle:

$$\left( \begin{array}{cccccc} x_1 & 0 & 0 & 0 & 0 & 0 \\ x_2 & x_2 & 0 & 0 & 0 & 0 \\ x_3 & x_3-x_2 & x_2 & 0 & 0 & 0 \\ x_4 & x_2-x_3+x_4 & x_3-x_2 & x_2 & 0 & 0 \\ x_5 & -x_2+x_3-x_4+x_5 & x_4-x_3 & x_3-x_2 & x_2 & 0 \\ x_6 & x_2-x_3+x_4-x_5+x_6 & x_2-x_4+x_5 & x_4-x_3 & x_3-x_2 & x_2 \end{array} \right)$$

gives the möbius function function divided by $x_1$.

Edit 24.7.2014:

(*Program start*)
(*Mathematica Mats Granvik 24.7.2014*)
Clear[A, t, n, k, a, nn];
nn = 32;
Print["Random numbers as input:"]
a = RandomReal[7, nn]
Length[a];
t[n_, 1] := t[n, 1] = a[[n]];
t[n_, k_] :=
t[n, k] =
If[And[n > 1, k > 1],
If[k == 2, t[n, k - 1] - t[n - 1, k],
Sum[t[n - i, k - 1], {i, 1, k - 1}] -
Sum[t[n - i, k], {i, 1, k - 1}]], 0];
A = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A];
B = a[[1]]*Inverse[A];
Print["Möbius function as output:"]
MatrixForm[B];
Chop[B[[All, 1]]]
(*program end*)

-
Your observation is correct. – Hagen von Eitzen Dec 31 '12 at 13:59
Have you tried it with a non-"random" sequence? Such as all $1$? – Thomas Andrews Dec 31 '12 at 13:59
@ThomasAndrews Yes I have tried it with the all 1 sequence. That is the same as the last recurrence at the end of my writing. – Mats Granvik Dec 31 '12 at 14:02
Yeah, my point is that the "random" part of the question is misleading - it has nothing to do with whether the initial sequence is "random." – Thomas Andrews Dec 31 '12 at 14:21
My answer is wrong - you probably want to unselect it if you want to get a correct answer. I'm thinking about how I can fix it, but it is being stubborn. I suspect I'm on the right track, just stuck on a few points. – Thomas Andrews Dec 31 '12 at 17:18

(This argumen isn't working out - the "shift" issue is the problem - it doesn't quite work.)

(Actually, I'm pretty sure this answer is wrong, but something like it is almost certainly the correct approach. The problem is that the value for $(0,1,0,0,...)$ is not as simple as the shift operator I gave.

Take the vector equal to the difference of your digits, so $x=(x_i)=(1,3-1,1-4,\dots)$.

Then your matrix is a linear map of $x=(x_i)$. That is, if $A(x)$ is the matrix gotten from $x=(x_1,...,x_m)$ by starting with $T(n,1)=\sum_{i=1}^n x_i$, and computing as above, then $A(x+x')=A(x)+A(x')$ and $A(\alpha x)=\alpha A(x)$ for any constant $\alpha$.

Now, when $x=(1,0,0,...)$ you get the matrix at the bottom of your question. Let's call that matrix $B = A(1,0,...0)$.

If $x=(0,1,0,...)$ then $A(x)$ is just that same matrix with the bottom row dropped, and a top row of $0$s added. That is $MB$, where $M$ is the matrix with $1$s just below the diagonal.

(This argument is still not quite working out, but it goes somethThis all means that if $x=(x_i)$ then $A(x)=\left(\sum_{i=1}^{m} x_i M^{i-1} \right)B$

The matrix $\sum_{i=1}^m x_iM^{i-1}$ is a lower diagonal matrix, with $x_1$ in all the diagonal elements. If $x_1\neq 0$, this is invertible, and its inverse is an lower -diagonal matrix, and all the diagonals are $x_1^{-1}$.

On the other hand $B^{-1}$ is can be easily seen to have $\mu(k)$ in the left column. So $B^{-1}\left(\sum_{i=1}^m x_iM^{i-1}\right)^{-1}$ has $x_1^{-1}\mu(k)$ along the left column.

But that is precisely the inverse of your matrix, so when $x_1=1$, we are done.

-