Skip to main content
2 of 2
deleted 1 character in body
Gerhard Paseman
  • 13k
  • 3
  • 32
  • 63

Expanding a combinatorial argument involving permutation coefficients

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.

Gerhard Paseman
  • 13k
  • 3
  • 32
  • 63