4
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Why insist on referring to the numbers $\log(n)$ as vectors? It's certainly technically accurate, but (at least for me) required a second glance to understand. $\endgroup$ – LSpice May 9 at 20:14
  • $\begingroup$ @LSpice I think the point of the "Vector" terminology is that it makes the terminology "basis" available. $\endgroup$ – Andreas Blass May 9 at 22:59
  • 2
    $\begingroup$ You should submit this sequence to oeis.org ! $\endgroup$ – Greg Martin May 10 at 0:04
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thank you for your detailed answer $\endgroup$ – orgesleka May 10 at 13:08
  • $\begingroup$ Very nice "untelescoping" the product in the first step—saves a lot of headache and error terms! In the same vein, note that $C$ can also be written as $\prod_{m=2}^\infty m^{1/m(m+1)}$, which seems faster to compute. $\endgroup$ – Greg Martin May 10 at 15:27
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ For the lower bound we can do all primes less than or equal to $\sqrt{n}$ and then an arbitrary multiple of all primes greater than $\sqrt{n}$. This gives a lower bound on the same order as the upper bound, the difference is of size $\sqrt{n}$. $\endgroup$ – Will Sawin May 10 at 0:21
  • $\begingroup$ For the upper bound, one should be careful that the numbers that are multiples of each prime $p$ are distinct. To ensure that they are, one can consider the $\pi(n) \times \pi(n)$ matrix where each column contains the tuple of $p$-adic valuations of one of the basis elements. If they form a basis, the determinant of this matrix is nonzero, hence some permutation has all nonzero entries, giving the upper bound. $\endgroup$ – Will Sawin May 10 at 0:24
  • $\begingroup$ @GredMartin Thank you for your answer and the suggestion to include this sequence to OEIS. I am in reviewing process at OEIS to include this sequence and will link your answer to this sequence. $\endgroup$ – orgesleka May 10 at 5:21
  • $\begingroup$ @WillSawin: Thanks for the comments. For the first comment, how do you get that the lower bound matches the upper bound? $\endgroup$ – Greg Martin May 10 at 8:20

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.