Let us look at the sequence of bipartite graphs $G_n = (V_n, E_n)$ where $V_n = A_n \cup B_n$ defined in this quesiton: Why is this bipartite graph a partial cube, if it is? .
The shortest path distance $d_n(u,v) := d(u,v)$ is given by:
$$d(u,v) = \Omega\left( \frac{uv}{\gcd(u,v)^2}\right)$$
where $\Omega(k) = \sum_{p|k} v_p(k)$ counts the primes dividing $k$ with multiplicities.
One formulation of the Riemann hypothesis is given via the Liouville function
$$\lambda(v) = (-1)^{\Omega(v)} = (-1)^{d(1,v)}$$
and is formulated like this: $\forall \epsilon > 0 $ we have:
$$\lim_{n \rightarrow \infty} \frac{\sum_{v=1}^n \lambda(v) }{n^{1/2+\epsilon}} = 0$$
But using the shortest distance function, this requirement can be formulated as:
$$\lim_{n \rightarrow \infty} \frac{\sum_{v \in V_n} (-1)^{d(v_0,v)} }{|V_n|^{1/2+\epsilon}} = 0, v_0 := 1$$
This point of view, I hope, it allows one to see the Riemann hypothesis for a sequence of graphs:
$$G_1 \subset G_2 \subset \cdots G_n \subset \cdots$$
each containing $v_0 \in V_n \forall n \in \mathbb{N}$. Then the sequence of graphs above satisfies R.H. iff $\forall \epsilon > 0 $ we have:
$$\lim_{n \rightarrow \infty} \frac{\sum_{v \in V_n} (-1)^{d_n(v_0,v)} }{|V_n|^{1/2+\epsilon}} = 0$$
where $d:=d_n$ is the shortest path distance in $G_n$.
My question is, if "easy" graphs can be constructed, where one can show that R.H. holds for these graphs.
Notice also, that in this graph theoretic formulation maybe one can use insights from Ising model to apply in this setting where the spin $\sigma_v$ is given by:
$$\sigma_v = (-1)^{d(v_0,v)}$$
Thanks for your help.
Edit Here is one example of "easy" graphs:
Example $G_n = (V_n,E_n)$ where $V_n = \{1,\cdots,n\}$, $x \equiv y \iff |x-y|=1$, $v_0 = 1$. Then $d(u,v) = |u-v|$ and $(-1)^{d(1,v)} = (-1)^{|v-1|}$. The graph is bipartite : $V_n = A_n \cup B_n$ where $A_n = \{ v | v \equiv 0 \mod(2) \}$ and $B_n = \{v | v \equiv 1 \mod(2) \}$. Hence $\sum_{v \in V_n} (-1)^{d(v_0,v)}= \sum_{v \in A_n} (-1)^{|v-1|} + \sum_{v \in B_n} (-1)^{|v-1|} = -|A_n|+|B_n| = \frac{1 \pm 1}{2} = +1,$ if $n$ is odd, or $=0$ if $n$ is even.
It follows that $\forall \epsilon > 0$: $$\lim_{n \rightarrow \infty} \frac{\sum_{v \in V_n} (-1)^{d(v_0,v)} }{|V_n|^{1/2+\epsilon}} = $$ $$\lim_{n \rightarrow \infty} \frac{ (1 \pm 1)/2 }{n^{1/2+\epsilon}} = 0$$
and the Riemann Hypothesis is satisfied for these graphs.
Third edit:
The following formulation is - by Landau's thesis - equivalent to the prime number theorem:
$$\lim_{n \rightarrow \infty} \frac{\sum_{v=1}^n \lambda(v)}{n} = 0$$
Using the analogy from above, we can define for a sequence of graphs with a node $v_0$ to satisfy the prime number theorem:
$$\lim_{n \rightarrow \infty} \frac{\sum_{v \in V_n} (-1)^{d_n(v_0,v)} }{|V_n|} = 0$$
Notice also, that in this graph theoretic formulation maybe one can use insights from Ising model to apply in this setting where the spin $\sigma_v$ is given by:
$$\sigma_v = (-1)^{d(v_0,v)}$$
In the Ising model, the quantity from the prime number theorem:
$$\frac{\sum_{v \in V_n} (-1)^{d_n(v_0,v)} }{|V_n|}$$
is called the "average magnetization".
Hence the prime number theorem says "that the natural numbers have zero average magnetization" (in the Ising model) which is kind of funny to think about.
My question would be for the Ising model:
How is the quantity (for $\epsilon > 0$) $$\frac{\sum_{v} \sigma_v }{N^{1/2+\epsilon}}$$ called in the Ising model - if it has a name?
Last edit before bounty: The prime number theorem for the graph is equivalent to:
$$0 = \lim_{n \rightarrow \infty} \frac{\sum_{v=1}^n (-1)^{d_s(1,v)}}{|V_n|}$$
which is equivalent to:
$$\lim_{n \rightarrow \infty} \frac{\deg_n(1)}{|V_n|} = \lim_{n \rightarrow \infty} \frac{\sum_{d_s(v,1)\neq 1} (-1)^{d_s(1,v)}}{|V_n|}$$
For the kernels $k(a,b) = \sum_{p|\gcd(a,b)} v_p(a)v_p(b)$ or $k(a,b) = \gcd(a,b)$, the number of neighbors of $1$, which is equal to $\deg_n(1)$, is given by:
$$\deg_n(1) = \pi(n)$$
the prime counting function.
For the kernel $k(a,b) = \min(a,b)$ we get the path graph and the only neighbor of $1$ for $n\ge 2$ is $2$, so:
$$\deg_n(1) = 1$$
in this case. We call the neighbors of $1$ with the name neighbor-primes. In the case of $k(a,b) = \min(a,b)$ we have only one neighbor-prime, hence the prime number theorem is very easy to prove and reads like this:
$$\frac{\deg_n(1)}{|V_n|} \approx \frac{1}{n}$$
for large $n$, whereas in the difficult case of the "real" prime number theorem we have an infinite number of neighbor-primes (when $n$ goes to infinity), which I suspect makes it more difficult to prove it.
It reads like this:
$$\frac{\deg_n(1)}{|V_n|} = \frac{\pi(n)}{n}\approx \frac{1}{\log(n)}$$
My question for the bounty:
Can you find an undirected connected graph on the natural numbers, which is between those two graphs? It could have a finite number of neighbor-primes or an infinite number or neighbor-primes and the prime number theorem should be proven in this case (If you can even prove the R.H. for your constructed graph, that would also be very cool).Thanks for your help!
