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:


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)  ])
  • 1
    $\begingroup$ 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)}. $$ $\endgroup$ Mar 23, 2019 at 9:48
  • $\begingroup$ @DietrichBurde: Thanks for your comment. How does that relate to the question? $\endgroup$
    – user276611
    Mar 23, 2019 at 9:49
  • $\begingroup$ It relates to the title! $\endgroup$ Mar 23, 2019 at 12:09
  • $\begingroup$ thanks :) for your comment $\endgroup$
    – user276611
    Mar 23, 2019 at 12:10
  • 1
    $\begingroup$ 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! $\endgroup$ Mar 24, 2019 at 13:33

2 Answers 2


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})$$

  • $\begingroup$ Thanks for your answer. I will have a look at it in detail. $\endgroup$
    – user276611
    Mar 23, 2019 at 13:07
  • $\begingroup$ @stackExchangeUser See my edit, with the "of size $<n$" you obtain the formula at the bottom of my answer $\endgroup$
    – reuns
    Mar 23, 2019 at 14:21
  • $\begingroup$ 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. $\endgroup$
    – user276611
    Mar 24, 2019 at 13:13
  • $\begingroup$ 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\}$ $\endgroup$
    – reuns
    Mar 24, 2019 at 13:15
  • $\begingroup$ 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? $\endgroup$
    – 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy