An explicit "formula" for the prime counting function?

Question

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)  ])

Answer 1

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

Answer 2

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

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

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

3. 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.