# Primes approximated by eigenvalues?

Consider the matrix starting: $$\displaystyle T = -\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 either the recurrence:

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

or:

$$\displaystyle T(n,k) = -a(GCD(n,k))$$

where $a$ is the Dirichlet inverse of the Euler totient function.

Does the largest eigenvalue of the matrix T(n,k) approximate the previous prime number sequence?

The signs of the eigenvalues appear to agree with the Möbius function.

As a Mathematica program this is:

Clear[b, t, n, k, i, j]
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}]];
nn = 42;
b = Range[1, nn]*0;
Do[m = Table[Table[t[n, k], {k, 1, j}], {n, 1, j}];
b[[j]] = RankedMax[Eigenvalues[m], 1], {j, 1, nn}]
Round[b]
Table[NextPrime[i, -1], {i, 2, 43}]


with the largest eigenvalues, rounded:

{-1, 1, 3, 3, 5, 5, 7, 7, 7, 8, 11, 11, 13, 13, 13, 13, 17, 17, 19, 19, 19, 19, 23, 23, 23, 23, 23, 23, 29, 29, 31, 31, 31, 31, 31, 31, 37, 37, 37, 37, 41, 41}

and the previous prime sequence:

{-2, 2, 3, 3, 5, 5, 7, 7, 7, 7, 11, 11, 13, 13, 13, 13, 17, 17, 19, 19, 19, 19, 23, 23, 23, 23, 23, 23, 29, 29, 31, 31, 31, 31, 31, 31, 37, 37, 37, 37, 41, 41}

as output.

Also, do the largest eigenvalues of this matrix approximate infinitely long sequences of consecutive prime numbers as the size of the matrix goes to infinity?

Again as a Mathematica program for a $200$ times $200$ matrix this is:

Clear[b, t, n, k, i, j]
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}]];
nn = 200;
m = Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}];
N[Sort[Eigenvalues[m], Less]]


which outputs a long list of eigenvalues of which the last few are:

{..., 157.4, 163.302, 167.281, 173.217, 179.157, 181.163, 191.074, 193.065, 197.038, 199.026}

Rounding these gives us:

{..., 157, 163, 167, 173, 179, 181, 191, 193, 197, 199}

which are equal to the 37:th to 46:th primes.

Table[Prime[i], {i, 37, 46}]


{157, 163, 167, 173, 179, 181, 191, 193, 197, 199}

Edit 1.8.2013: A more precise approximation of the primes by eigenvalues is given by this Mathematica program:

Clear[nn, n, k, d, kolumn];
a[n_] := If[n < 1, 0, Sum[d MoebiusMu@d, {d, Divisors[n]}]]
Do[nn = j;
A3 = Range[nn]*0;
Do[
kolumn = i;
A1 = Table[Table[a[GCD[n, k]], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A1];
A1[[All, kolumn]];
MatrixForm[
Table[Table[
If[Mod[n, k] == 0, MoebiusMu[n/k]*A1[[All, kolumn]][[k]],
0], {k, 1, nn}], {n, 1, nn}]];
a1 = Table[
Total[Table[
If[Mod[n, k] == 0, MoebiusMu[n/k]*A1[[All, kolumn]][[k]],
0], {k, 1, nn}]], {n, 1, nn}];
a2 = Sign[a1]*Exp[Abs[a1]];
A2 = Table[
Table[If[Mod[n, k] == 0, a2[[n/k]], 0], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A2];
a3 = Table[
Total[Table[If[Mod[n, k] == 0, a2[[n/k]], 0], {k, 1, nn}]], {n,
1, nn}];
A3[[i]] = a3;
, {i, 1, nn}]
MatrixForm[A3];
Print[N[Log[-Min[Eigenvalues[A3]]], 12]]
(*Print[N[Sign[Eigenvalues[A3]]Log[Abs[Eigenvalues[A3]]],12]]*)
, {j, 1, 24}]


which outputs:

{1.00000000000+3.14159265359 I, 1.71614308398, 2.89852243027, 2.94293185770, 4.98292271242, 4.98305676486, 6.99755465240, 6.99756090303, 6.99756737456, 6.99756777041, 10.9999546191, 10.9999546211, 12.9999938562, 12.9999938562, 12.9999938562, 12.9999938562, 16.9999998874, 16.9999998874, 18.9999999847, 18.9999999847, 18.9999999847, 18.9999999847, 22.9999999997, 22.9999999997}

Rounding these values we get:

{1, 2, 3, 3, 5, 5, 7, 7, 7, 7, 11, 11, 13, 13, 13, 13, 17, 17, 19, 19, 19, 19, 23, 23}

The program above basically uses the Riemann zeta function product that converges to the Dirichlet inverse of the Euler totient function with exponentiated divisors, analogously to the Riemann zeta function product that converges to the von Mangoldt function. I will explain more later, bedtime here now.

This latter matrix starts:

$$A_3 = \left( \begin{array}{cccccc} e & e & e & e & e & e \\ e & e-e^2 & e & e-e^2 & e & e-e^2 \\ e & e & e-e^3 & e & e & e-e^3 \\ e & e-e^2 & e & e-e^2 & e & e-e^2 \\ e & e & e & e & e-e^5 & e \\ e & e-e^2 & e-e^3 & e-e^2 & e & e-e^2-e^3+e^6 \end{array} \right)$$

and is defined by taking the Möbius transform of each column of the first matrix $T$, exponentiating the divisors, multiplying with the Möbius function and then taking the inverse Möbius transform.

$$\displaystyle T = \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}$$

Example: For the 6-th column with the entries: {1,-1,-2,-1,1,2,...} by Möbius inversion we get: {1,-2,-3,0,0,6} which is equal to the divisors of $6$ times the elementwise multiplication of the Möbius function of the divisors of $6$: {1,-2,-3,0,0,6}={1,2,3,0,0,6} times {1,-1,-1,0,-1,1}. By then exponentiating the divisors we have: {e^1,e^2,e^3,0,0,e^6} times {1,-1,-1,0,-1,1}. The Inverse Möbius transform (=summing over the divisors) then gives: {e-e^2, e-e^3, e-e^2, e, e-e^2-e^3+e^6}

The claim is that the most negative eigenvalue of $A_3$ approximates the previous prime number sequence.

Of course this could be explained more clearly by starting with the exponentiated divisors, its matrix inverse and the row sums thereof, I believe.

Using the same algorithm as above and exponentiating and correspondingly logarithmating the terms in the eigenvalue sequence arbitrary many times, it appear that they - the logarithms of the eigenvalues - converge to the Möbius function times the natural numbers.

Example, double exponentiating of divisors and double logarithms of eigenvalues of a 12 times 12 matrix: {-11.0000000000,10.0000000000,-7.00000000000,6.00171666577,-5.00000000000,-3.03392765715,-2.13750865340,1.00344457743,0,0,0,0}

Example, double exponentiating of divisors and double logarithms of eigenvalues of a 13 times 13 matrix: {-13.0000000000,-11.0000000000,10.0000000000,-7.00000000000,6.00171666577,-5.00000000000,-3.03392765715,-2.13750865340,1.00344457743,0,0,0,0}

which appears to converge to: {1, -2, -3, 0, -5, 6, -7, 0, 0, 10, -11, 0, -13, 14, 15, 0, -17, 0, -19, 0, 21, 22, -23, 0, 0, 26, 0, 0, -29, -30, -31, 0}

Or as a Mathematica line:

Range[32]*MoebiusMu[Range[32]]


Link to Pastebin with Mathematica program

Clear[n, k, a1, A1, a2, nn]
nn = 8;
b1 = Expand[
Table[Limit[
Zeta[s]*Total[
MoebiusMu[Divisors[n]]*Exp[Exp[Exp[Divisors[n]]]]^(s - 1)],
s -> 1], {n, 1, nn}]];
b1[[1]] = Exp[Exp[Exp[0]]];
A1 = Table[Table[b1[[GCD[n, k]]], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A1]
a2 = Eigenvalues[A1];
N[Table[Sign[a2[[i]]] If[a2[[i]] == 0, 0, Log[Log[Abs[a2[[i]]]]]], {i,
1, nn}], nn]


Output: {-7.0000000, 6.0000000, -5.0000000, -3.0000000, -2.1375087, 1.0034446, 0, 0}

which are:

$$\text{sign}(Eigenvalues(A_1))\log(\log(abs(Eigenvalues(A_1))))$$ of: $$A_1(n,k) = b_1(GCD(n,k))$$ where: $$b_1(n) = \lim_{s\to 1} \, \zeta (s) \sum\limits_{d|n}\mu (d(n)) (\exp(\exp (\exp (d(n)))))^{s-1}$$

So in terms of this limit with the zeta function, there is one logarithm less than the number of exponentials.

As already mentioned above, the sequence that begins to emerge is found in the oeis:

{1, -2, -3, 0, -5, 6, -7, 0, 0, 10, -11, 0, -13, 14, 15, 0, -17, 0, -19, 0, 21, 22, -23, 0, 0, 26, 0, 0, -29, -30, -31, 0}

I believe this tendency becomes clearer with infinitely many exponentials of the divisors and equally many, minus one, logarithms of the eigenvalues. So something like:

$$\text{sign}(Eigenvalues(A_1))\log(\log(\log(\log(\log(\log(\log(abs(Eigenvalues(A_1)))))))))$$ of: $$A_1(n,k) = b_1(GCD(n,k))$$ where: $$b_1(n) = \lim_{s\to 1} \, \zeta (s) \sum\limits_{d|n}\mu (d(n)) (\exp(\exp(\exp(\exp(\exp(\exp(\exp (\exp (d(n))))))))))^{s-1}$$

Edit 22.8.2013: Simplifying further to a infinite matrix

$$A_1 = \left( \begin{array}{cccccccccccc} e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} \\ e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 \\ e^{e^{e^e}} & e^{e^{e^e}} & 0 & e^{e^{e^e}} & e^{e^{e^e}} & 0 & e^{e^{e^e}} & e^{e^{e^e}} & 0 & e^{e^{e^e}} & e^{e^{e^e}} & 0 \\ e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 \\ e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & 0 & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & 0 & e^{e^{e^e}} & e^{e^{e^e}} \\ e^{e^{e^e}} & 0 & 0 & 0 & e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 & 0 & 0 & e^{e^{e^e}} & 0 \\ e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & 0 & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} \\ e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 \\ e^{e^{e^e}} & e^{e^{e^e}} & 0 & e^{e^{e^e}} & e^{e^{e^e}} & 0 & e^{e^{e^e}} & e^{e^{e^e}} & 0 & e^{e^{e^e}} & e^{e^{e^e}} & 0 \\ e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 & 0 & 0 & e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 \\ e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & e^{e^{e^e}} & 0 & e^{e^{e^e}} \\ e^{e^{e^e}} & 0 & 0 & 0 & e^{e^{e^e}} & 0 & e^{e^{e^e}} & 0 & 0 & 0 & e^{e^{e^e}} & 0 \end{array} \right)$$

equal to $$(\exp(\exp(\exp(\exp(\exp(\exp(\exp(\exp(1))))))))))$$ if GCD(n,k)=1 and 0 otherwise, and taking equally many logarithms of the eigenvalues:

$$\text{sign}(Eigenvalues(A_1))\log(\log(\log(\log(\log(\log(\log(\log(abs(Eigenvalues(A_1))))))))))$$

we get the (rounded) eigenvalues:

{1.00000,-1.00000,-1.00000,-1.00000,-1.00000,1.00000,-1.00000,1.00000,-1.00000,1.00000,-1.00000,-1.00000,-1.00000,-1.00000,1.00000,1.00000,1.00000,-1.00000,1.00000,-1.00000,0,0,0,0,0,0,0,0,0,0,0,0}

which appears to be a rearrangement of the Möbius function:

{1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, 0, 1, 1, -1, 0, 0, 1, 0, 0, -1, -1, -1, 0}

Mathematica:

Do[
nn = ii;
A1 = Table[
Table[If[GCD[n, k] == 1, Exp[Exp[Exp[Exp[1]]]], 0], {k, 1,
nn}], {n, 1, nn}];
a2 = Eigenvalues[A1];
Print[N[Table[
Sign[a2[[i]]] If[a2[[i]] == 0, 0,
Log[Log[Log[Log[Abs[a2[[i]]]]]]]], {i, 1, nn}], 6]], {ii, 1, 32}]
MatrixForm[A1]


Mussardos paper:

http://lanl.arxiv.org/pdf/cond-mat/9712010.pdf

http://people.sissa.it/~mussardo/Professional_web/Quantum_Mechanics_and_Number_Theory.html

The eigenvalues can be arbitrary. Here the zeta zeros as input, and as output the zeta zeros as eigenvalues:

(*Mathematica 8 program start*)(*The Mobius function times "n" \
approximately as the eigenvalues of a matrix*)Clear[nn, n, k, d, \
kolumn]
a[n_] := If[n < 1, 0, Sum[Im[ZetaZero[d]], {d, Divisors[n]}]]
Do[nn = j;
A3 = Range[nn]*0;
Do[kolumn = i;
A1 = Table[Table[a[GCD[n, k]], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A1];
A1[[All, kolumn]];
MatrixForm[
Table[Table[
If[Mod[n, k] == 0, MoebiusMu[n/k]*A1[[All, kolumn]][[k]],
0], {k, 1, nn}], {n, 1, nn}]];
a1 = Table[
Total[Table[
If[Mod[n, k] == 0, MoebiusMu[n/k]*A1[[All, kolumn]][[k]],
0], {k, 1, nn}]], {n, 1, nn}];
a2 = Sign[a1]*Exp[Abs[a1]];
A2 = Table[
Table[If[Mod[n, k] == 0, a2[[n/k]], 0], {k, 1, nn}], {n, 1, nn}];
MatrixForm[A2];
a3 = Table[
Total[Table[If[Mod[n, k] == 0, a2[[n/k]], 0], {k, 1, nn}]], {n,
1, nn}];
A3[[i]] = a3;, {i, 1, nn}] MatrixForm[A3];
(*Print[N[Log[Log[-Min[Eigenvalues[A3]]]],12]]*)
Print[N[Sign[Eigenvalues[A3]] Log[Abs[Eigenvalues[A3]]], 12]], {j, 1,
10}]
(*program end*)

-
What is $n$ and $k$ in your example for $T(n,k)$? Both $7$? – draks ... Jun 9 '12 at 13:07
draks, yes n = k = 7 in the example of this matrix. It is of course a infinite greatest common divisor like matrix. – Mats Granvik Jun 9 '12 at 13:11
What about the $1$ and $8$ among your rounded eigenvalues? Are there other counter examples? – draks ... Jun 9 '12 at 13:15
For small matrices eigenvalues are not accurate approximations. They get better for large matrices. – Mats Granvik Jun 9 '12 at 13:18
Just genuinely I have this trouble to accept that a prime (that is an integer) can be approximated. I know the arguments for that type of thought, but dive deep in debates with the analytical number people on this matter. (However can freely accept talking about approximation of a prime counting function, sure). – al-Hwarizmi Aug 2 '13 at 8:17

This is not an answer, but too long for a comment.
Are you aware, that the L-D-U-decomposition gives triangular matrices, whose entries are constant for any dimension? That means the matrices of finite sizes can be seen as simply truncated versions of the infinite matrix, and for the matrices with size going to infinity should then approximate the primes by its eigenvalues arbitrarily exact.
Also because T is symmetric, the L and U-factors are transposed of each other.
Here is the top lft of the L-matrix (the left column is the row-index): $$\small \small \begin{array} {rr} \begin{array} {r} 1 \\ 2 \\3\\4 \\5 \\6 \\7 \\8 \\9 \\10 \\11 \\12 \\ \end{array} & \begin{bmatrix} 1 & . & . & . & . & . & . & . & . & . & . & . \\ 1 & 1 & . & . & . & . & . & . & . & . & . & . \\ 1 & 0 & 1 & . & . & . & . & . & . & . & . & . \\ 1 & 1 & 0 & 1 & . & . & . & . & . & . & . & . \\ 1 & 0 & 0 & 0 & 1 & . & . & . & . & . & . & . \\ 1 & 1 & 1 & 0 & 0 & 1 & . & . & . & . & . & . \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & . & . & . & . & . \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & . & . & . & . \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & . & . & . \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & . & . \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & . \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \end{array}$$

and the diagonal-matrix D $$\small \small \operatorname{diag} (D)=\begin{bmatrix} -1 & 2 & 3 & 0 & 5 & -6 & 7 & 0 & 0 & -10 & 11 & 0 \end{bmatrix}$$

It is nice to see the rows in L at the prime row-indexes, in general they seem to be indicators of the primefactors of the row-index and the D is not perfectly clear to me: the sign giving the number of different primefactors?). If we had the true patterns then this would allow to generate the L and the D matrices directly; the construction of the T by the recursive procedure is much time-consuming!

[update] With a bit improved heuristic the pattern of the entries in D seems to be
$\qquad \qquad \small D_1 = -1$
$\qquad \qquad \small D_k = 0 \qquad \text{if k is not squarefree}$
$\qquad \qquad \small D_k = -k \dot (-1)^{w(k)} \qquad \text{if k is squarefree}$
where $w(k)$ is the number of distinct primefactors. Using the Moebius-function we can write $$D_k = -k \cdot \operatorname{Moebius}(k)$$

The entries in L seem to be: for a row r at a column c we have 1 if $c=r$ or if (c is squarefree and is a divisor of r).

A routine in Pari/GP without recursive call which produces quickly the matrix of size mxm:

{make_T(m)=local(M);M=matrix(m,m);
for(c=1,m,M[1,c]=M[c,1]=-1);
for(r=2,m, for(c=2,r, M[r,c]=M[c,r]= - sum(i=1,c-1,M[r-i,c])));
return(M);}

-
4, 8, 9, and 12 each have a square factor, and at each index in the D matrix are a zero. Does that pattern hold? Indices 16, 20, 24...? – adam W Aug 20 '13 at 3:51
I've extended the matrix by a non-recursive computation to 64x64. It seems that we have for squarefree $k$ the entry $D_k = -k \cdot (-1)^ {n(k)}$ where $n(k)$ is the number of different prime factors of k . – Gottfried Helms Aug 20 '13 at 6:25
@adamW: I think I've got the pattern in L as well as in the diagonal D. See my updated answer. – Gottfried Helms Aug 20 '13 at 9:18
@GottfriedHelms Thank you for your answer. What do you think yourself, have you proven the result? I am not able to tell. – Mats Granvik Jan 6 '14 at 15:13
@Mats: No, I've nothing proved. Just heuristic. Only suggestive and in a sense "logical"... But I think it should be easily provable when using this path shown by the heuristic (however, I'm not good in proving and also lazy...;-) . – Gottfried Helms Jan 6 '14 at 17:03