22
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Using the symmetry d goes to $n_N$/d, you can improve the lower bound by dividing the exponent by 2, as well as getting an upper bound by averaging over the interval $(k, N_n^{1/2})$. With examples like 715/714, it may be that you can't remove log k from the exponent. $\endgroup$ – The Masked Avenger Apr 8 '15 at 15:59
  • $\begingroup$ $k$ is used in either the definition of $N$ and the minimum, but I think the meaning is different $\endgroup$ – user40023 Apr 10 '15 at 8:58
  • $\begingroup$ Ah, yes, this was a typo - fixed it. $\endgroup$ – Kurisuto Asutora Apr 13 '15 at 8:01
  • 1
    $\begingroup$ I think this is a very interesting question, and don't believe it is known. Note that it implies your other question on logarithms of ratios of square-free numbers, which also is unknown I think. Finally, it may be worth pointing out that the kind of bound you are asking for is best possible -- random products of the first $k$ primes will cluster, and then use pigeonhole to find two near each other. $\endgroup$ – Lucia Apr 20 '15 at 5:10
  • $\begingroup$ Hi Lucia, thanks for your remark. Yes, I also think that this is very interesting. The problem arises in my work when trying to control the mean value of certain Dirichlet series (or, more precisely, of the mean value of the squared absolute value of certain finite Euler products), but I think it is of some interest on its own right. $\endgroup$ – Kurisuto Asutora Apr 21 '15 at 11:47
8
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Instead of trying to calculate the size of the minimal gap, I have now spent some time trying to prove that at least a certain fixed proportion (say 1 percent) of all the $2^k-1$ expressions $n_{\ell+1}/n_\ell - 1$ is greater than $c^{-k}$ for some fixed $c$, but couldn't even prove this. This would be very natural, since, as you say, one may expect the whole system to show a somewhat "random" behavior. Still I couldn't find a way to rule out the possibility that these numbers cluster in an extremely strong way. $\endgroup$ – Kurisuto Asutora Nov 26 '15 at 18:58
  • $\begingroup$ Hm, that might be doable though nontrivial (not that I have a specific approach in mind). What kind of application might such a result have? $\endgroup$ – Noam D. Elkies Nov 26 '15 at 19:12
  • $\begingroup$ Such a result would be a keystone in calculating moments of finite Euler products. The particular application I have in mind is in the context of Soundararajan's "resonance method" for establishing extreme values of the Riemann zeta function (and maybe other L-functions). In arxiv.org/abs/1409.6035 there is a "long resonator", namely a Euler product of the form $\prod_{1 \leq m \leq k} (1 + p_m^{i t})$ over the first $m$ primes. Then quite a large amount of technical work is necessary to show that this Euler product can be replaced by a Dirichlet polynomial which has a certain $\endgroup$ – Kurisuto Asutora Nov 27 '15 at 11:52
  • $\begingroup$ sparsity property. However, if one could show the lower bound $\approx 3^{-k}$, which you mention above, then the whole complicated procedure would be unnecessary, as the Euler product itself would already have the desired sparsity property. To get an idea why these ratios are important, try to calculate $\int_0^T \Big|\prod_{1 \leq m \leq k} (1 + p_m^{it})\Big|^2~dt$, where $k \approx c \log T$. Then you have to work with the ratios mentioned in the question above. The same issue appears in a slightly different form in a (quite amazing) recent paper, see arxiv.org/abs/1507.05840. $\endgroup$ – Kurisuto Asutora Nov 27 '15 at 11:53
  • $\begingroup$ @NoamD.Elkies : I saw your heuristic argument, but do you have a proof for $\delta_k \ll k \log k / 2^k$ ? $\endgroup$ – Basj Jan 15 '16 at 15:28
2
$\begingroup$

(New part at the bottom):

Here is a long comment: A more general question was answered by Tijdeman: 1) On integers with many small prime factors (Compositio, 26 (3), 1973, 319-330. http://archive.numdam.org/article/CM_1973__26_3_319_0.pdf

But sees also 2) Tijdeman On the maximal distance between integers composed of small primes, Compositio 28 (2), 1974, 159-162. http://archive.numdam.org/article/CM_1974__28_2_159_0.pdf He studies gaps between S-units, i.e. integers multplicatively generated by (any) $k$ prime factors. Your sequence of square-free integers generated by the first $k$ primes is a subset of Tijdeman's sequences, hence a lower bound for Tijdeman sequences gives a lower bound for your problem.

Using linear forms in logarithms, (Baker theory), Tjdeman proves (Corollary on page 321): There exists an effectively computable constant $C=C(k)$ such that
$$n_{i+1}-n_i > \frac{n_i}{(\log n_i)^{C(k)}}, \text{ for } n_i \geq 3.$$ Dividing by $n_i$ gives that $\frac{n_{i+1}}{n_i} > 1+ \frac{1}{(\log n_i)^{C(k)}}\geq 1+ \frac{1}{(2k\log k)^{C(k)}}$, (where the $2$ can certainly be improved with some care on the estimate on the largest $n_i$).

Therefore $$ \min_{1 \leq \ell_1 < \ell_2 \leq N} ~ \frac{n_{\ell_2}}{n_{\ell_1}} > 1+ \frac{1}{(2k\log k)^{C(k)}}.$$

If this bound is of any use for you seems to depend on $C(k)$. It seems unlikely that the effectively computable $C(k)$ has been computed, with any useful value.

EDIT: In a series of papers R.R. Hall, P. Erdös, H. Maier and G. Tenenbaum studied questions of the "propinquity" of divisors. Maybe the following is useful: MR0554398, Erdős, P.; Hall, R. R. The propinquity of divisors. Bull. London Math. Soc. 11 (1979), no. 3, 304–307.

Theorem 1 (or short excerpt of MR entry): Let $\epsilon>0$ be fixed, and let $$\eta(x)=\exp(−(1+\epsilon)(\log 3)(2\log \log x)^{1/2}(\log \log \log \log x)^{1/2}),$$ $$\theta (x,d)=\eta(x)(\log d)^{1−\log 3}$$. Then the number of integers $n$ not exceeding $x$, and having divisors $d,d′$ with $$d<d′<d(1+\theta(x,d))$$ is $o(x)$.

The sequence of the product of the first $k$ prime factors is of course a quite thin sequence, but it should not behave too irregularly, and maybe ideas of the proof can be used.

If one makes the above function above slightly larger, then MR0739628 Maier, H.; Tenenbaum, G. On the set of divisors of an integer. Invent. Math. 76 (1984), no. 1, 121–128 shows that almost all $n$ do have such (multiplicatively) close divisors.

$\endgroup$
  • $\begingroup$ As you write, the problem is that $C=C(k)$ depends on k here. Tijdeman's result is obtained using Baker's theorem on linear forms of logarithms, which does not seem to be suited for sub-asymptotic applications. (Or applications where, in our notation, N increases automatically as k does). By the way, there are explicit versions of Baker's result, which might lead to an explicit quantitative form of Tijdeman's result. See for example MR1817252 and MR2009829 on MathSciNet. $\endgroup$ – Kurisuto Asutora Jan 14 '16 at 9:45
  • $\begingroup$ As $C(k)$ is not explicit in terms of $k$, it seems that (please correct me if I'm wrong) your last lower bound says nothing more than "There exists a positive function $f$ such that $\min \frac{n_{\ell_2}}{n_{\ell_1}} > 1 + f(k)$". I'm afraid it proves no asymptotic at all. $\endgroup$ – Basj Jan 15 '16 at 16:09
1
$\begingroup$

Here is some (unverified) computational data, which I encourage others to extend.

I look at the squarefree p-smooth numbers (being $2^k$ in number for $p$ being the $k$th prime) and compared successive ratios. To reduce print out and operation cycles, I replaced the comparison $$\frac{x+a}{x} \gt \frac{y+b}{y}$$ with $$ay \gt xb$$, and whenever I got a better fraction I printed out in order $p : y+b, y, (y+b)/y, b, a$ . Here is the output up to p=71:

5 : 3 2 1.5 1 1
5 : 6 5 1.2 1 1
7 : 7 6 1.16667 1 1
7 : 15 14 1.07143 1 1
11 : 22 21 1.04762 1 1
13 : 66 65 1.01538 1 1
13 : 78 77 1.01299 1 1
17 : 715 714 1.0014 1 1
29 : 2002 2001 1.0005 1 1
29 : 2262 2261 1.00044 1 1
31 : 7163 7161 1.00028 2 1
31 : 12122 12121 1.00008 1 2
41 : 50065 50061 1.00008 4 1
41 : 82621 82615 1.00007 6 4
41 : 101270 101269 1.00001 1 6
43 : 958341 958334 1.00001 7 1
47 : 310247 310245 1.00001 2 7
47 : 487578 487577 1 1 2
47 : 2162095 2162094 1 1 1
53 : 21894574 21894565 1 9 1
61 : 66965190 66965177 1 13 9
61 : 1669770410 1669770141 1 269 13
67 : 118885413 118885403 1 10 269
67 : 4432525097 4432524801 1 296 10
71 : 62296466 62296465 1 1 296
71 : 6768250181 6768250086 1 95 1
71 : 16487003968153872 16487003736740238 1 231413634 95

I find the last line a rather startling indicator as to the problem difficulty. I suspect that it will be impossible to remove $\log$ from the exponent, and harder to prove that you cannot remove it.

EDIT: Unfortunately, the last values for $y$ have more decimal digits than the square root of the primorial for 71, leading me to suspect machine error. Even without that line though, the fact that there are many near-optimal ratios with difference larger than 1 presents some challenge. END EDIT.

Gerhard "Let's Do It Right Away" Paseman, 2015.04.28

$\endgroup$
  • $\begingroup$ Returning to the millions range, my program reports further improvements, one of them being 221669902,1 for $y,b$. Gerhard "Paging Experts On Stormer's Theorem" Paseman, 2015.04.28 $\endgroup$ – Gerhard Paseman Apr 28 '15 at 19:26
  • $\begingroup$ Hi Gerhard, thanks for your contribution. I have to confess that I don't know which claim is supported by your computations. Yes, in the last line you certainly get a ration which is very small. (Two 17-digit numbers differing by a 9-digit number). On the other hand, the quotient in the second displayed formula in the question is the quotient of the first 20 primes (71 is the 20-th prime), which is a 27-digit number, compared to the same number minus one, which means a difference only in the last digit. $\endgroup$ – Kurisuto Asutora May 1 '15 at 10:57
  • $\begingroup$ @KurisutoAsutora, my intent is to support the claim that the infimum is not far from exp(-ck log k), instead of the exp (-ck) you suggest might occur. I doubt the data supports either conclusion, but the fact is that the infimum does not occur as a ratio of consecutive smooth numbers for some small k, and this is likely to make a lower bound proof harder. Even if you focus on those cases for which the infimum does occur at consecutive smooth numbers, I don't know how many there are of such cases. Gerhard "Sorry For The Machine Error" Paseman, 2015.05.04 $\endgroup$ – Gerhard Paseman May 4 '15 at 17:03
  • $\begingroup$ Yes, I understand. $\endgroup$ – Kurisuto Asutora May 8 '15 at 7:40
1
$\begingroup$

Let $P_k$ be the product of the $k$ first prime numbers, and for any integer $n$, we denote by $(d_i)_{1 \leq i \leq \tau(n)}$ the increasing sequence of its divisors.

The set $\{n_1, ... n_N \}$ of square-free positive integers which are generated by the first $k$ primes that you are considering is nothing else than the set of the divisors of $P_k$. Thus we can use this notation:

$$\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) = \min_{d_i | P_k,\ 1 \leq i < 2^k} \left(\frac{d_{i+1}}{d_i} - 1\right).$$

We have, for $ \epsilon > 0$,

$$(2^k-1) \Bigg( \min_{d_i | P_k,\ 1 \leq i < 2^k} \left(\frac{d_{i+1}}{d_i} - 1\right)\Bigg)^{1+\epsilon} \leq \sum_{1 \leq i < 2^k} \left(\frac{d_{i+1}}{d_i} - 1\right)^{1+\epsilon} \leq C,$$

with an absolute constant $C$, uniformly for all $k$, by using Théorème 1 of Sur un problème extrémal en arithmétique, G. Tenenbaum, Ann. Inst. Fourier, Grenoble (1987).

i.e. it is proved that, for every $\epsilon > 0$,

$$\delta_k \ll 2^{-k(1-\epsilon)}$$

Note 1 : It doesn't give the lower bound you were looking for, but it confirms that $\delta_k$ has an upper bound of the order you expected, i.e. $e^{-c\ k}$.

Note 2 : I have applied Théorème 1 with the function $h(u) = u^{1+\epsilon}$, but the article describes (see page 3) a wider class of function that could be used.

Note 3 : For a lower bound, the best I can prove is (do you want me to post a proof for this?):

$$\delta_k \gg e^{- \frac{1}{2} k \log k}$$

$\endgroup$
  • $\begingroup$ Hi Basj, thank you. Concerning 1), a similar upper bound can be obtained by using a simple averaging argument, see Noam Elkies' comment above. Concerning 2), what would help is any result that reduces the exponent to a smaller function of k. The optimum would be to remove the $\log k$, but it would be already nice to replace $\log k$ by $\sqrt{\log k}$, for example. The constant does not really play a role, sorry. $\endgroup$ – Kurisuto Asutora Jan 18 '16 at 11:27
  • $\begingroup$ About 1), I agree with his heuristic, but I would really like to see a proof for it. 1bis) With the article mentionned here, it's possible to improve the upper bound to $\delta_k \ll 2^{-k+k^{d}}$ with $2/3 < d < 1$. About 2), I'm really not sure you can remove $\log k$: I don't see why there couldn't be a gap of $d_{i+1} - d_i = 1$ very close to $d_i \approx \sqrt{P_k}$. If this is true, you cannot do better than $c\ k \log k$ in the exponent. (I think this is what @TheMaskedAvenger suggests in the first comment.) $\endgroup$ – Basj Jan 18 '16 at 12:26
  • $\begingroup$ The proof goes as follows. Assume that $n_1 < \dots < n_N$ are ordered. By the prime number theorem $n_N \approx e^{c k \log k}$, and thus $\log n_N \approx k \log k$. We have $\sum_{\ell=1}^{N-1} \log (n_{\ell+1}/n_{\ell}) = \log (\prod_{\ell=1}^{N-1} (n_{\ell+1}/n_{\ell})) = \log (n_N / n_1) = \log (n_N) \approx k \log k$. The sum has $N-1=2^k -1$ summands, thus there exists a summand which is at most as large as $\approx (k \log k)/2^k$. Now note that $\log x \approx 1 +x$ for small $x$. That's the proof. $\endgroup$ – Kurisuto Asutora Jan 18 '16 at 14:19
  • $\begingroup$ Concerning 2), I'm definitely also not sure. The hope is that the whole structure shows a somewhat "random" appearance, and that there are no gaps which are so much smaller than the average gap. But, as I said, I'm certainly not sure. On the other hand: even if one or a few such extremely small gaps exist, shouldn't most of the gaps (or at least 1% of them) be of average size and not extremely small? $\endgroup$ – Kurisuto Asutora Jan 18 '16 at 14:24
  • $\begingroup$ @KurisutoAsutora That's right, I missed this argument... So this nearly-trivial estimate gives better than the result I cited here ;) About your last sentence, I think you're right. You could try to split $S := \sum_i d_{i+1}/d_i - 1$ in three parts. A) The indices $i$ such that $d_{i+1}/d_i - 1 \leq 2^{-k}$ only contribute to the sum with $O(1)$. B) If we can show that only very few indices $i$ are such that $d_{i+1}/d_i - 1$ is very big (this is certainly true), then their contribution to the sum $S$ would be $O(1)$ too... (continued) $\endgroup$ – Basj Jan 18 '16 at 20:14

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.