Let $Log(n) = \sum_{i=1}^r \alpha_i \cdot e_i$, where $n = \prod_{i=1}^r p_i^{\alpha_i}$ and $p_i$ is the $i$-th prime, $\alpha_i \ge 0$, $e_i$ is the $i$-th standard basis vector. For example $6 = 2\cdot3$, hence: $$Log(6) = (1,1,0,0,0,\cdots)$$ $$Log(15) = (0,1,1,0,0,\cdots)$$ $$Log(7) = (0,0,0,1,0,\cdots)$$ Consider the $\mathbb{Q}$-vector space generated by the vectors: $$Log(1),Log(2),\cdots,Log(n)$$ It is not difficult to see that the dimension of this vector space is $\Pi(n)$, where $\Pi$ is the prime counting function.

I am interested if one can get some result of number theoretic interest by looking at these vectors. Is there some reference for literature which pursues this line of thought? For example, let $1 < a_1,a_2,\cdots,a_k \le n$ be a basis for $1,\cdots,n$ (where I mean that $Log(a_1),Log(a_2),\cdots,Log(a_k)$ is a basis for the above vector space), $n\ge 2 , k = \Pi(n)$, then it seems like (I have no proof for this just some intuition), that $$ a_1 \cdot a_2 \cdots a_k \equiv 0 \mod p_1\cdots p_k$$ where $p_i$ denotes the $i$-th prime number. Furthermore I conjecture, that if $2 \le m \le n$ and $1 < a_1,\cdots,a_k \le m $ is a basis for $1,\cdots,m$ and $\Pi(m)=k,\Pi(n)=l$ then there seems to exist a basis $1<b_1,\cdots,b_l\le n$ of $1\cdots,n$ such that: $$\frac{a_1\cdots a_k}{p_1 \cdots p_k} = \frac{b_1 \cdots b_l}{p_1 \cdots p_l}$$

Examples: $m=5,n=7$ then: $$\frac{3\cdot 4 \cdot 5}{2 \cdot 3 \cdot 5} = \frac{3 \cdot 4 \cdot 5 \cdot 7}{2 \cdot 3 \cdot 5 \cdot 7}$$

So my questions are:

a) Is this line of thought already pursued? If so what is the reference? ( Namely using results of linear algebra or geomtric number theory to prove number theoretic results.) b) Are the above conjectures true, if so how to prove them?

Thanks for your help.

I think I found an exact "formula" for the prime counting function using Euler characteristic:

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

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

For this to be true I need to prove a more general conjecture, which it would be nice if someone knows how to do this:

$$0 = \sum rank(A) \cdot (-1)^{|A|}$$

where $A$ runs through all subsets of some vectors $v_1,\cdots,v_n$. Since this is similar to Euler characteristic, it would be nice if someone knows how to prove this, since the prime counting formula would follow from this.

Edit: For the general case this is not true, but computations for small $n$ suggest, that the prime counting formula is correct.

  • 1
    $\begingroup$ You should look into the quadratic sieve, which does indeed use linear algebra as a tool in finding factorizations, along lines similar to your description. $\endgroup$ – Greg Martin Mar 21 '19 at 17:46
  • $\begingroup$ @GregMartin: Thanks for your comment. I will have a look. $\endgroup$ – user6671 Mar 21 '19 at 18:00
  • 1
    $\begingroup$ Related questions from same user: math.stackexchange.com/questions/3156680/… also mathoverflow.net/questions/325667/… $\endgroup$ – Gerry Myerson Mar 21 '19 at 21:30

I don't know of such a reference, but I think I can give you a short proof for your intuition and conjecture, hope that helps:

One basis for $1,...,n$ is given by $e_1,\ldots, e_k$, where $k = \Pi(n)$. Now assume we have any basis $v_1, \ldots , v_k$ and fix an $1 \leq i \leq k$. Then there exists a $j$ such that $v_j$ has a non-zero entry at position $i$, as otherwise $e_i$ can not be written as a linear combination of the $v$. Writing $v_j = Log(a_j)$, this means that $p_i \mid a_j$, giving you the desired result.

About your conjecture: Take $b_i' = p_i$ for all $i$. Then the number on the right hand side will be $1$. Next, set the $b_i$ by multiplying $b_1$ with a factor to satisfy the equality. Due to the fact that $k \leq l$, $b_i$ will still stay in the same space, and the conjecture is shown.

Unfortunately, I can't comment on the formula for $\Pi(n)$, as I currently can't remember the definition of the rank of a set.

| cite | improve this answer | |
  • $\begingroup$ It is about the rank of the matrix defined by a set of vectors. Maybe this helps? Thanks for your answer! $\endgroup$ – user6671 Mar 21 '19 at 13:45

Your Answer

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