# An explicit "formula" for the prime counting function?

It is known that $$\log(p_1),\cdots,\log(p_n)$$ are linearly independet over $$\mathbb{Q}$$, where $$p_i$$ denotes the $$i$$-th prime. For a number $$1 \le k \le n$$ let $$Log(k)$$ denote the vector with respect to this basis for the numbers $$1,\cdots,n$$. For a subset $$A$$ of $$1,\cdots,n$$ let $$rank(A)$$ denote the rank of the matrix build by numbers $$k$$ in $$A$$ of vectors $$Log(k)$$. Through experimentation I found the following explicit "formula" for prime-pi function:

$$\Pi(n)= (-1)^{n+1} \sum rank(A) \cdot (-1)^{|A|}$$

where $$A$$ runs through the subsets of $$1\cdots n$$ of size $$< n$$.

But I have no proof for this. The formula above has some similarity with the inclusion-exclusion principle:

$$\left| \bigcup_{i=1}^n A_i\right| = \sum_{\emptyset\neq J\subseteq\{1,\ldots,n\}}(-1)^{|J|-1} \left |\bigcap_{j\in J} A_j\right|$$

But how does one define the sets $$A_i$$?

The formula has also similarity with Euler characteristic.

For a set of (possibly repeating) vectors, define:

$$\chi(v_1,\cdots,v_n) = \sum_{A} rank(A) \cdot (-1)^{|A|}$$

where $$A$$ runs through the subsets (with repetion) of $$v_1,\cdots,v_n$$.

It is not difficult to show, that if those vectors are linearly independent then $$\chi=0$$

My conjecture is that if $$\chi(v_1,\cdots,v_n)=0$$ then $$\chi(v_1,\cdots,v_n,w)=0$$ for any vector $$w$$. This would prove the prime-counting formula.

If you can think of a proof, that would be great.

Related-but-not duplicate question: https://mathoverflow.net/questions/325880/is-this-line-of-thought-using-linear-algebra-to-get-number-theoretic-results-a

Here is some sage code to play around with:

MAXN=100

def Log(a,N=MAXN):
return vector([valuation(a,p) for p in primes(N)])

def findsubsets(S,m):
return Set(S).subsets(m)

def getMatrixA(someSubset,N=MAXN):
return matrix([Log(xx,N=N) for xx in someSubset ])

def eulerCharPrimePi(n,N=MAXN):
return (-1)^(n+1)*sum([ getMatrixA(x).rank()*(-1)^k if k < n else 0 for k in range(0,n+1) for x in findsubsets(range(1,n+1),k)  ])

• Actually, there is an explicit formula for $\pi(n)$ by Riemann. It is given by the Gram series $$G(x)=1+\sum_{k=1}^{\infty}\frac{(\log (x))^k}{(kk!\zeta(k+1)}.$$ Mar 23, 2019 at 9:48
• @DietrichBurde: Thanks for your comment. How does that relate to the question?
– user276611
Mar 23, 2019 at 9:49
• It relates to the title! Mar 23, 2019 at 12:09
• thanks :) for your comment
– user276611
Mar 23, 2019 at 12:10
• Dietrich did not tell the whole story; the Riemann function, which is represented by the Gram series, is only an approximation of $\pi(x)$. However, by successively adding corrections that involve the nontrivial zeroes of $\zeta$, you eventually get the prime counting function itself! Mar 24, 2019 at 13:33

Can you detail your sage code ? For the remaining part of your question

$$\pi(n) = \dim_\Bbb{Q}( \log(1)\Bbb{Q}+\ldots+\log(n)\Bbb{Q})$$ where $$\dim_\Bbb{Q}$$ is the dimension as a $$\Bbb{Q}$$-vector space.

Your claim is that $$\pi(n) = (-1)^{n+1}f(n)$$ where $$f(n) = \sum_{e \in \{0,1\}^n} (-1)^{\sum_m e_m} \dim_\Bbb{Q}(\sum_{m=1}^n e_m\log(m)\Bbb{Q})$$ But for $$p$$ prime $$f(p) = f(p-1)+\sum_{e \in \{0,1\}^{p-1}} (-1)^{1+\sum_m e_m} \dim_\Bbb{Q}( \log(p)\Bbb{Q}+\sum_{m=1}^{p-1} e_m \log(m)\Bbb{Q})$$ $$= f(p-1)-\sum_{e \in \{0,1\}^{p-1}} (-1)^{\sum_m e_m}(1+ \dim_\Bbb{Q}(\sum_{m=1}^{p-1} e_m \log(m)\Bbb{Q}))$$ $$= f(p-1)-\sum_{e \in \{0,1\}^{p-1}} (-1)^{\sum_m e_m} - f(p-1)$$ $$= -\sum_{e \in \{0,1\}^{p-2}} (-1)^{\sum_m e_m} +\sum_{e \in \{0,1\}^{p-2}} (-1)^{\sum_m e_m} = 0$$

Since there is always a prime in $$(n/2,n]$$ the same $$f(n)=0$$ holds by permuting $$\log n$$ with $$\log p$$ the largest prime $$\le n$$. Thus my guess is that you meant $$\pi(n) =(-1)^{n+1} f(n)+ \dim_\Bbb{Q}( \log(1)\Bbb{Q}+\ldots+\log(n)\Bbb{Q}))$$ $$= (-1)^{n+1}\sum_{e \in \{0,1\}^n - (1,\ldots,1)} (-1)^{\sum_m e_m} \dim_\Bbb{Q}(\sum_{m=1}^n e_m\log(m)\Bbb{Q})$$

• Thanks for your answer. I will have a look at it in detail.
– user276611
Mar 23, 2019 at 13:07
• @stackExchangeUser See my edit, with the "of size $<n$" you obtain the formula at the bottom of my answer Mar 23, 2019 at 14:21
• I updated the SAGE code and found a simple proof of the formula, which maybe you might want to have a look at. Thanks for your help.
– user276611
Mar 24, 2019 at 13:13
• Right it works too when replacing $\log(p)$ by $\log(1)$, but my argument still works when replacing $\{1,\ldots,n\}$ by $\{2,\ldots,n\}$ Mar 24, 2019 at 13:15
• I did also some experiment with the numbers not ranging from $1,\cdots,n$ but ranging from $a,\cdots,b$ where $a<b$ and in this case it seems that $\chi = 0$. Does your argument allow one to consider also this case?
– user276611
Mar 24, 2019 at 13:19

I found a very simple proof of the formula:

1. Let $$v_1=0$$ then $$\chi(v_1,v_2,\cdots,v_n)=0$$.

Proof: The idea is to divide the subsets in those containing $$v_1=0$$ and those not containing $$v_1=0$$.

$$\chi(v_1,\cdots,v_n) = \sum_{ A \subset \{1,\cdots,n\}} rank(A) \cdot (-1)^{|A|} =$$

$$\sum_{ A \subset \{2,\cdots,n\}} rank(A) \cdot (-1)^{|A|}+\sum_{ A \subset \{2,\cdots,n\}} rank(A \cup v_1) \cdot (-1)^{|A|+1} =$$

$$\sum_{ A \subset \{2,\cdots,n\}} rank(A) \cdot (-1)^{|A|}- rank(A ) \cdot (-1)^{|A|} =0$$

1. Corollary: $$\chi(Log(1),Log(2),\cdots,Log(n)) = 0$$

Proof: Since $$Log(1)=0$$ this follows from 1.

1. Corollary: $$\Pi(n) = (-1)^{n+1} \sum_{ A \subset \{1,\cdots,n\}, |A| < n } rank(A) \cdot (-1)^{|A|}$$ Proof: Since $$\Pi(n) = rank(1,\cdots,n)$$ the formula follows from 2.