[Math] Small quotients of smooth numbers

analytic-number-theorydiophantine-approximationnt.number-theoryprime numbers

Assume that $N=2^k$, and let $\{n_1, \dots, n_N\}$ denote the set of square-free positive integers which are generated by the first $k$ primes, sorted in increasing order. Question: what is a good lower bound for
$$
\min_{1 \leq \ell_1 < \ell_2 \leq N} ~ \frac{n_{\ell_2}}{n_{\ell_1}}.
$$

Remark 1: Since by assumption $n_{\ell_2} > n_{\ell_1}$ for $\ell_2 > \ell_1$, a trivial lower bound is 1.

Remark 2: By the prime number theorem, the largest number $n_N$ is of size roughly $e^{c k \log k}$ for some $c$. Thus an obvious lower bound is something like
$$
\frac{e^{c k \log k}}{e^{c k \log k} -1} \approx 1 + \frac{1}{e^{c k \log k}}.
$$
The questions is if an essential improvement of this simple lower bound is possible. In particular, it would be nice to get a lower bound of size roughly
$$
1 + \frac{1}{e^{c k}}.
$$

(All constants $c$ in these statements are generic positive numbers, their specific values are not of interest for me. Also, I don't care about small values of $k$ or $N$, but about an asymptotic result.)

Edit: It would already be very helpful to know that 1% (or any other fixed percentage) of all possible quotients of consecutive numbers $n_{\ell+1}/n_\ell$ satisfy the desired lower bound.

Best Answer

It seems unlikely that one can prove anything nontrivial, but it's still interesting to consider what ought to be true, and to experimentally compute for small $k$.

Let

$$ \delta_k = \min_{\ell_1<\ell_2} \left(\frac{n_{\ell_2}}{n_{\ell_1}} - 1\right) = \min_{\ell} \left(\frac{n_{\ell+1}}{n_\ell} - 1\right), $$ so we're asking how small $\delta_k$ can get. An easy upper bound is $\delta_k \ll k \log k \, / \, 2^k$, and one can probably save some power of $k$. The right answer is probably $\delta_k \sim C^{-k + o(k)}$ for some constant $C>2$, and it seems reasonable to guess that $C=3$. I'll explain this next, followed by computational techniques that make it feasible to determine $\delta_k$ at least for $k \leq 36$; for example $$ \delta_{28} = \delta_{29} = \delta_{30} = \frac1{1079415718589} \doteq 3^{-25.22} $$ (the numerator is $13 \cdot 53 \cdot 59 \cdot 61 \cdot 67 \cdot 73 \cdot 89 = 2 \cdot 3 \cdot 5 \cdot 11 \cdot 17 \cdot 19 \cdot 31 \cdot 43 \cdot 71 \cdot 107 - 1$), and $$ \delta_{36} = \frac{145948}{123657879146878688901} \doteq 3^{-31.29} $$ with $$ 1 + \delta_{36} = \frac {7 \cdot 13 \cdot 19 \cdot 37 \cdot 41 \cdot 47 \cdot 73 \cdot 83 \cdot 89 \cdot 97 \cdot 127 \cdot 151} {3 \cdot 17 \cdot 23 \cdot 43 \cdot 59 \cdot 61 \cdot 67 \cdot 71 \cdot 79 \cdot 101 \cdot 131 \cdot 137}. $$

For the upper bounds: Note that $\delta_k$ is essentially $\min_{\ell_1<\ell_2} (\log n_{\ell_2} - \log n_{\ell_1}).$ There are $2^k$ numbers $\log n_\ell$ between $\log n_1 = 0$ and $\log n_{2^k} = \sum_{i=1}^k \log p_i \sim k \log k$; so when we list them in order the average difference is $\log n_{2^k} \, / \, (2^k - 1) \sim k \log k \, / \, 2^k$, and so there must be some difference(s) no larger than that. To save a power of $k$, note that the variance of the $2^k$ numbers $\log n_\ell$ is $\frac14 \sum_{i=1}^k \log^2 p_i \sim (k/4) \log^2 k$, and a positive fraction of them must be within say two standard deviations of the mean, so we get an upper bound $\sim k^{1/2} \log k \, /\, 2^k$.

For the heuristics: If we had $2^k$ random numbers in an interval, we'd expect the closest pair to be about $4^{-k}$ apart. But the separations aren't independent; there are only $(3^k-1)/2$ different ratios $n_{\ell_2} / n_{\ell_1}$ (namely the values of $\prod_{i=1}^k p_i^{\alpha_i}$ with each $\alpha_i \in \{-1, 0, 1\}$ that make the product $>1$), so we expect the smallest one to have logarithm about $3^{-k}$, again up to subexponential factors.

For small $k$ we can compute $\delta_k$ exactly by listing the $2^k$ factors of $\prod_{i=1}^k p_k$, sorting them, setting $\delta=2$, comparing each $n_{\ell+1} / n_\ell$ with the current value of $\delta$, and if $n_{\ell+1} / n_\ell$ is smaller then making it the new $\delta$. This takes about $2^k$ space and $k 2^k$ time.

We can reduce each factor $2^k$ to $3^{k/2}$ by splitting $\{p_1,\ldots,p_k\}$ into two equal or nearly equal subsets $P_1,P_2$, listing for $j=1,2$ all the $3^{P_j}$ rationals of the form $\prod_{p \in P_j} p^{\alpha_p}$ with each $\alpha_p \in \{-1, 0, 1\}$, merging and sorting the two lists, and minimizing over ratios between consecutive elements of different lists. This increases the feasible range by a factor of $\log_3 4 = 1.26\!+$, and is how I computed $\delta_k$ for $k \leq 36$ (in a few hours running gp on a computer on which I could allocatemem(2^37)). We next tabulate, for each $k \leq 36$, the values of $\log_3 (1 / \delta_k)$ (which does seem reasonably close to $k$), followed by the difference between the two $n_\ell$ with the ratio closest to $1$ and the values of those two $n_\ell$. When $\delta_k = \delta_{k-1}$ we use " marks instead of repeating a row.

 1 |  0      1  2  1
 2 |  0.631  1  3  2
 3 |  1.465  1  6  5
 4 |  2.402  1  15  14
 5 |  2.771  1  22  21
 6 |  3.954  1  78  77
 7 |  5.981  1  715  714
 8 |    "    "   "   "
 9 |    "    "   "   "
10 |  7.030  1  2262  2261
11 |  8.559  1  12122  12121
12 |    "    "    "      "
13 | 10.491  1  101270  101269
14 | 10.765  7  958341  958334
15 | 13.277  1  2162095  2162094
16 | 13.385  9  21894574  21894565
17 |   "     "     "         "
18 | 14.237  269  1669770410  1669770141
19 | 15.039  296  4432525097  4432524801
20 | 16.459  95   6768250181  6768250086
21 | 17.492  1    221669903  221669902
22 | 17.989  479  183357752669  183357752190
23 | 20.727  1    7746395147  7746395146
24 | 20.899  241  2256564888159  2256564887918
25 | 22.260  31   1293752274846  1293752274815
26 | 22.260  31   1293752274846  1293752274815
27 | 23.709  8    1641739926263  1641739926255
28 | 25.220  1    1079415718590  1079415718589
29 |   "     "          "              "
30 |   "     "          "              "
31 | 28.015  3749    87225268563485259  87225268563481510
32 | 29.352  699715  70660131241710008586  70660131241709308871
33 | 30.221  208586  54759581443774708307  54759581443774499721
34 |   "       "              "                     "
35 | 31.240  4       3216928369004441  3216928369004437
36 | 31.288  145948  123657879146878834849  123657879146878688901

This seems to agree with the computations of Gerhard Paseman up to $k=20$ (except for the error already noted in the final line). I couldn't find a sequence in OEIS that matches any of it.

One could push this computation further using the data structure described in this paper by D. J. Bernstein, which reduces the space requirement from $3^{k/2}$ (or $2^k$) to the square root $3^{k/4}$ (or $2^{k/2}$) without appreciably increasing the running time. I haven't tried to implement this.

Finally, for yet larger $k$ one could probably still exhibit some values of $n_{\ell+1} / n_{\ell}$ that are reasonably close to $1$ using algorithms such as LLL to find approximate integer relations on $\{ \log p_i \mid 1 \leq i \leq k \}$ (though it would be harder to prove that one has found the minimal one). I have not tried to do this either.

Related Question