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$ – Dietrich Burde Mar 23 at 9:48
  • $\begingroup$ @DietrichBurde: Thanks for your comment. How does that relate to the question? $\endgroup$ – orgesleka Mar 23 at 9:49
  • $\begingroup$ It relates to the title! $\endgroup$ – Dietrich Burde Mar 23 at 12:09
  • $\begingroup$ thanks :) for your comment $\endgroup$ – orgesleka Mar 23 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$ – J. M. is a poor mathematician Mar 24 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})$$

  • $\begingroup$ Thanks for your answer. I will have a look at it in detail. $\endgroup$ – orgesleka Mar 23 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 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$ – orgesleka Mar 24 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 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$ – orgesleka Mar 24 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

Not the answer you're looking for? Browse other questions tagged or ask your own question.