Expanding a combinatorial argument involving permutation coefficients

Question

I have spent more time thinking than I would like to admit because of the following sentence: "Choose $t = c_6X^{1/e}$ and we obtain Theorem 2.". What obvious argument am I missing that allows us to obtain Theorem 2?

The sentence, Theorem 2, and supporting background come from the first four pages of a paper of P. Erdős and J. Selfridge, found at https://www.math-inst.hu/~p_erdos/1971-24.pdf (Some problems on the prime factors of consecutive integers II). I will interpret some of it here, hopefully enough to explain the situation.

"permutation coefficients" in the question title refers to numbers of the form $W=W(n,k)=\prod_{1\leq i \leq k}(n+i)$, and the paper deals with the number $v(n,k)$ of distinct prime factors of $W$, and related quantities. Let $f_0(n)$ be the largest positive integer $k$ such that $v(n,k) \geq k$, and let $f_1(n)$ be the smallest $k$ such that for $1 \leq j \leq k$ we have $v(n,j) \geq j$, and also $v(n,k+1)=k$. It takes a little effort to show $f_0(n) \geq f_1(n)$, and more to show strict inequality occurs for an infinite number of $n$, with the smallest occurring above $n=5000$. $f_1$ is provided for completeness; it will be enough for answering this question to restrict attention to $f_0(n)$.

After some observations and a nice (but also telegraphic) proof of an upper bound for $f_0(n)$, we come to theorem 2, which states: for infinitely many $n$, $$ f_0(n) \lt c_6n^{1/e} \textrm{ and } f_1(n) \lt c_7n^{1/e}. $$ Here the symbols $c_6$ and $c_7$ refer to absolute constants independent of $n$ or anything else except the mind of the proof composer/interpreter. I interpret some of the proof below.

It is enough to consider the proposition for $n$ sufficiently large, so choose $X$ big, and consider for a sufficiently small constant $c_8$ the set $L$ of prime numbers in the interval $(c_8X^{1/e}, X)$. Where the authors write $u(m,X)$ I will write $u(m)$, which counts the number of (distinct) prime factors $m$ has that come from $L$. Then it is noted that in total, there are more instances of these prime factors among $m \in [1,X]$ than the numbers in that interval. To wit: $$ \sum_{1 \leq m \leq X} u(m) = \sum_{p \in L} \lfloor X/p \rfloor \gt X \sum_{ p \in L } 1/p - \pi(X) \gt X. $$ From this they observe that there is an integer $m \in (c_8X^{1/e}, X - c_8X^{1/e})$ such that the following inequality holds for all $t$ with $1\leq t \leq X -m$: $$\sum_{1\leq i \leq t} u(m+i) \geq t.$$

"Choose $t = c_6X^{1/e}$ and we obtain Theorem 2.". Really? How so?

I think what is provided is too abbreviated, and in an answer below I provide what I think is a reasonable expansion. However, it seems too long, and I wonder if there is something simpler and more direct. There is a little more that follows but it does not especially enlighten me. In particular I can't determine which of $c_6$ and $c_8$ is larger in general, although I suspect $c_6$ is smaller.

Gerhard "Not A Student Of Erdős" Paseman, 2017.09.07.

Answer 1

The simplest explanation is that it is a mistake. One can however complete the proof as follows:

If $X$ is large enough then $u(m) \in \{ 0,1,2 \}$ for all $m$ since $e < 3$. Thus the number of distinct primes in $L$ dividing $m$ is at least $u(m)$, unless $u(m) = 2$ and $m$ has only one prime factor in $L$, in which case $m = p^2 q$.

Let us count pairs of integers $(p,q)$ where $p > R := c_{8} X^{\frac{1}{e}}$ and $m < p^2 q \leq m+t$. This it at most $$ \sum_{q \leq X R^{-2}} \mathrm{number \ of \ squares \ in \ } ]mq^{-1},(m+t)q^{-1} ] \\ \leq \sum_{q \leq X R^{-2}} \left( \frac{t}{\sqrt{qm}} + O(1) \right) \\ \ll \frac{t}{\sqrt{R}} \sqrt{X R^{-2}} + X R^{-2} \\ \ll t X^{-\alpha} +X^{\frac{1}{e} - 2 \alpha} $$ where $\alpha = \frac{3-e}{2e} >0$.

Thus the number of distinct prime factors of $\prod_{j=1}^{t} (m+j)$ in $L$ is at least $t - O(t X^{-\alpha} +X^{\frac{1}{e} - 2 \alpha})$. By choosing $t$ of size $X^{\frac{1}{e}}$, one thus gets $\geq t - O(t X^{-\alpha})$ distinct prime factors $>t$. By adding the $\pi(t)$ primes $\leq t$, we get $\geq t$ distinct prime factors (for $X$ large enough).

EDIT: As pointed out Gerhard Paseman below, I answered a different question ... The original question can be answered as follows :

Let $\omega_{>k}(n)$ be the number of distinct prime factors $>k$ of $n$. We first note that $$ \nu(n,k) = \pi(k) + \sum_{i=1}^k \omega_{>k}(n+i). $$ Let $c >0$ be large enough so that $$ \sum_{X<n \leq 2X + X^{\frac{4}{5}}} \omega_{>R}(n) \leq \left( 1 - \frac{3e}{\log X} \right) X $$ holds for large $X$ with $R = c X^{\frac{1}{e}}$ (indeed the inequality holds with $3e$ replaced by $e \log c + O(1)$). We first show that for any $X$ large enough the following holds:

$(*)$ there exists a $n \in [X,2X]$ such that for each $k \in [R, X^{\frac{4}{5}}]$, one has $\nu(n,k) < k$.

Indeed, assume the contrary for some $X$. Then starting with $n_0 =X$, we get a $k_0 \in [R, X^{\frac{4}{5}}]$ such that $\nu(n_0,k_0) \geq k_0$, and then with $n_1 = n_0 + k_0$ some $k_1$ such that $\nu(n_1,k_1) \geq k_1$, .... and so on until $n_{J+1} = n_J + k_J > 2X$ for some $J$. We then have $$ \sum_{n_j < n \leq n_{j+1}} \omega_{>R}(n) \geq \sum_{n_j < n \leq n_{j+1}} \omega_{>k_j}(n) \geq k_j - \pi(k_j) \geq \left( 1 - \frac{2}{\log R} \right) k_j. $$ Summing over $j$, this yields $$ \sum_{X<n \leq 2X + X^{\frac{4}{5}}} \omega_{>R}(n) \geq \left( 1 - \frac{2}{\log R} \right) X,$$ which contradicts our choice of $c$ for $X$ large enough.

Thus for any $X$ large enough one can take $n \in [X,2X]$ as in $(*)$. One has $\nu(n,k) < k$ for $k \in [R, X^{\frac{4}{5}}]$. But for $k > X^{\frac{4}{5}}$, a direct count using Brun-Titschmarsh inequality yields $\nu(n,k) \leq c k + o(k)$ with $c = 2 \log \frac{4}{3} < 1$, hence $\nu(n,k) < k$ when $X$ is large enough. Thus $f_0(n) < R \leq c n^{\frac{1}{e}}$.

Answer 2

I think the combinatorial argument could be more useful if made more clear. I want to make sure I am using it correctly; consider this answer an extension of the question and asking for other uses of this argument in the literature.

What I call $u(m)$ (and the authors call $u(m,X)$) is a nice counting function. For sufficiently large positive integers $m \leq X$, $u(m)$ takes on the values $0,1,$ and $2$. One chooses the exponent $1/e$ to get the summatory function $\sum_{1\leq m \leq X} u(m)$ up to a value close to and above $X$, and indeed $c_8$ does not need to be much smaller than $1/e$ to accomplish this, so one can make the argument with an explicit choice. One can also define $L$ so that the sum is within a small constant times $X^{1/e}$ from $X$. (We can also vary $X$; this will be crucial later.)

For arbitrary $ X$, one can show the existence of the stated $m$ as follows. Consider for any positive integer $j$ less than $X$ the largest $s$ such that $\sum_{1 \leq i \leq r} u(j+i) \geq r$ holds for $1 \leq r \leq s$ but does not hold for $r=s+1$. Indeed, for small $j$ outside of $L$ $u(j+i)$ is $0$ for small $i$, and so for these $j$ $s$ is $0$. One can partition $[1,X]$ into disjoint intervals of the form $[j,j+s]$, and there will be at least $c_8X^{1/e}$ many of these intervals, which means (since the summatory exceeds $X$) that the excess $u$ values pile up later on in the interval. $m$ is the largest of these $j$'s and has to handle all the excess "missed out" by the smaller $j$'s, so we must have $m \in (c_8X^{1/e}, X - c_8X^{1/e})$. This is argument has less control if you replace $1/e$ by something smaller, say $1/10$. You can show the existence of $m$, but $u$ would become more bumpy and you might not prove as large a value of $s$ as here ($m$ might end up too close to $X$.)

As currently written, it is not clear if the authors expect $\sum_{1 \leq i \leq X+1-m} u(m+i) \geq X +1 -m$ to fail. Indeed, if it does not fail, then $v(m,X-m+1)$ may be larger than $ X-m+1 $ just because $W(m,X-m+1)$ might have that many prime factors bigger than $c_8X^{1/e}$ alone, and still more small prime factors. Then $f_0(m)$ would be larger than $X-m+1$, and $m$ might not be one of the infinitely many $n$ highlighted in Theorem 2. More importantly, the suggested value of $n$ of $X-t$ or $n= X - c_6X^{1/e}$ might also not satisfy $f_0(n) \lt c_6X^{1/e}$ because we found a large interval full of primes and semiprimes containing $X$. This issue as well as having to fill in details like "where is $n$?" prompts the question.

If we can guarantee that the last inequality fails for $t= X-m+1$, then I can finish the proof easily. Choose $c_6$ and $t$ as suggested, and choose $n=X-t$. Then $W(n,t)$ has fewer than $t$ factors coming from $L$ by the construction of $m$ and the guarantee. If also $c_6$ is larger than $c_8$ and $n \gt m$, then some of the factors from $L$ are repeated (so not distinct) and since we can vary $t$ between $1$ and $X-m$, we can choose $c_6$ so that there are more repeats than primes below $c_8X^{1/e}$, and now we get finally an $n$ that gets close to the goal, having $v(n, X-n) $ less than $c_6X^{1/e}$. To get the goal requires a little more tweaking of $c_6$, but we have made assumptions on $X$ and $m$, so let's address those.

So let us not choose arbitrary $X$. Let us choose $X' \geq X$ so that (now renaming $X'$ to $X$) we can assert the existence of $m \lt X$ above where the inequality in $t$ above not only works for $1 \leq t \leq X-m$ and also fails at $t=X+1-m$. This is essentially the partition argument above, except we choose $X'$ to be $m+s$ (or $m+s+1$, whichever works) and rename it to $X$. We can also tweak $c_8$ and $L$ correspondingly to get this to work.

Here is the key point: for all $n$ in $(m, X)$ now we have $\sum_{1 \leq i \leq X-n} u(n+i) \lt X-n$, and now we have the inequality pointing in the right direction (because of the failure for $m$ at $t=X+1-m$). Now we can have our pick of $n$ to get the small primes in $W(n,X-n)$ outnumbered by the repeats in $L$. Even if $m$ is too small, we can start "backing up" (by choosing $m' \lt m$ and renaming) and find a good value for $n$ less than the original $m$. There are more details to consider, but now I see a light at the end of the tunnel, and it does not look like an oncoming train.

I can understand leaving detail to the reader, but I think the reader deserves the bone of the phrase ("and let $n=X-t$"). Unless, of course, I missed something simpler.

Gerhard "Maybe Can Hitch A Ride?" Paseman, 2017.09.08.