How many $\mathbb{Q}$-bases of $\langle\log(1),\dotsc,\log(n)\rangle$ can be built from the set of vectors $\log(1),\cdots,\log(n)$?

Question

How many $\mathbb{Q}$-bases of $\langle\log(1),\dotsc,\log(n)\rangle$ can be built from the set of vectors $\log(1),\dotsc,\log(n)$?

Data for $n=1,2,3,\dotsc$ computed with Sage:

$$1, 1, 1, 2, 2, 5, 5, 7, 11, 25, 25, 38, 38, 84, 150, 178, 178, 235, 235$$

Context: The real numbers $\log(p_1),\dotsc,\log(p_r)$, where $p_i$ is the $i$th prime, are known to be linearly independent over the rationals $\mathbb{Q}$.

Example:

[{}] -> For n = 1 , we have 1 = a(1) bases; We count {} as a basis for V_0 = {0}
[{2}] -> For n = 2, we have 1 = a(2) basis, which is {2};
[{2, 3}] -> for n = 3, we have 1 = a(3) basis, which is {2,3};
[{2, 3}, {3, 4}] -> for n = 4 we have 2 = a(4) bases, which are {2,3},{3,4}
[{2, 3, 5}, {3, 4, 5}] -> a(5) = 2;
[{2, 3, 5}, {2, 5, 6}, {3, 4, 5}, {3, 5, 6}, {4, 5, 6}] -> a(6) = 5;
[{2, 3, 5, 7}, {2, 5, 6, 7}, {3, 4, 5, 7}, {3, 5, 6, 7}, {4, 5, 6, 7}] -> a(7) = 5.

Answer 1

My comments on Greg Martin's answer got complicated enough, I thought it was worth it to write a new one. The idea for the upper bound and the lower bound are both essentially the same as his. First let's check the asymptotic \begin{align*} \prod_{p\leq n} \left\lfloor \frac{n}{p} \right\rfloor = \prod_{m=2}^{\infty} \prod_{p \leq n/m} \frac{m}{m-1} &\approx \prod_{m=2}^{\infty}\left( \frac{m}{m-1}\right)^{ (n/m) / \log (n/m)} \\ &\approx \prod_{m=2}^{\infty}\left( \frac{m}{m-1}\right)^{ (n/m) / \log n} = \left( \prod_{m=2}^{\infty} \left(\frac{m}{m-1}\right)^{1/m} \right)^{n / \log n}. \end{align*}

Here the $\approx$ denote an error of $e^{ o ( n/\log n)}$ and for the last one it is helpful to note that $\prod_{m=2}^{\infty} \left( \frac{m}{m-1 }\right)^{1/m}$ is convergent because the logarithms of the terms decline like $1/m^2$.

Let $C = \prod_{m=2}^{\infty} \left(\frac{m}{m-1}\right)^{1/m}$. Then we will show the answer is $C^{ n/\log n + o (n/\log n)}$. Here $C = 2.2001\dots$ is some explicitly computable number.

For the upper bound, note that is possible to order a basis such that the $i$th entry is divisible by the $i$th prime. This is because, if we form the $\pi(n) \times \pi(n)$ matrix whose $(i,j)$ entry is the $j$th p-adic valuation of the $i$th basis entry, to form a basis the determinant of this matrix must be nonzero, hence some permutation of the columns must have nonzero diagonal entries. It follows that the number of bases is at most the number of tuples whose $i$th entry is divisible by the $i$th prime, which is $\prod_{p\leq n} \lfloor \frac{n}{p} \rfloor = C^{n/\log n+ o(n/\log n)}$.

For the lower bound, note that if we take the first $\pi(\sqrt{n})$ vectors to be the first $\pi(\sqrt{n})$ primes, and for the remaining vectors we take the $i$th vector an arbitrary multiple of the $i$th prime, then because each multiple of the later primes will be the multiple of something $<\sqrt{n}$, these will always form a basis, and no such basis will be equal to a number of permutations of another. So we have a lower bound of $\prod_{\sqrt{n} < p\leq n} \lfloor \frac{n}{p} \rfloor = C^{n/\log n+ o(n/\log n)}/ \prod_{p \leq \sqrt{n} } \lfloor \frac{n}{p} \rfloor$ but $ \prod_{p \leq \sqrt{n} } \lfloor \frac{n}{p} \rfloor \leq \prod_{p \leq \sqrt{n} } n \approx e^{2 \sqrt{n}}$, so this is again a lower-order term.

In fact it is so small that, even under GRH, our error term comes mainly from the error term in the prime number theorem rather than the combinatorial aspect.

Answer 2

Note: Will Sawin's answer refines mine significantly!

We can say at least that the answer is roughly some exponential function of $n/\log n$.

Lower bound: Form a subset of $\log 1,\dots,\log n$ by including $2$ and $3$; all the primes $p\in(\frac n3,n]$; and either $p$ or $2p$ or $3p$ for each prime $p \in [5,\frac n2]$. All such subsets are bases for $\langle \log 1,\dots,\log n \rangle$, and there are $3^{\pi(n/3)-2}$ such subsets, which is $\gg C^{n/\log n}$ for any $C<3^{1/3}$.

Upper bound: any basis for $\langle \log 1,\dots,\log n \rangle$ must contain a multiple of every prime less than $n$. The number of multiples of any such $p$ is at most $\frac np$. Thus the total number of bases is at most $$ \prod_{p\le n} \frac np = \exp\bigg( \sum_{p\le n} (\log n-\log p) \bigg) = \exp\big( \pi(n)\log n - \theta(n) \big) = \exp\bigg( O\bigg( \frac n{\log n} \bigg) \bigg); $$ indeed, one can show that the third expression is $\ll D^{n/\log n}$ for any $D>e$.