On the minimum integer not coprime to numbers in an interval

Question

Consider the set of positive integers $[a,a+1,\ldots, a+k]$ (i.e. the interval $[a,a+k]$). What can we say about the smallest positive integer $N$ such that $\gcd(a+i,N)>1$ for all $0\leq i\leq k$? Can we prove that it is at least of order $k^4$ (and it would be great if we can give as explicit constants as possible)?

Answer 1

The obvious interpretation of this question is to find the a bound for the smallest $N$ as $a \ge 2$ varies. For convenience, consider the interval $[a,a+X-1]$ of length exactly $X$. I will prove that the smallest $N$ certainly grows faster than any power of $X$.

It's not hard to make the estimates in this answer perfectly explicit, but it would become a real mess, and unless one is very careful and works extra you will end up having to assume that $X$ is very large and or consider many cases explicitly. The answer, however, can certainly be made explicit if desired.

Certainly we may take the smallest $N$ to be squarefree. Let us suppose that $N = \prod_{i=1}^{n} q_i$ for distinct primes $q_i$.

Case 1 The number of primes factors is at least $n \ge \log X$. In this case, $N$ is at least the product of the first $n$ primes, and thus the product of the primes $p \le p_n > n \log n \ge X \log X$. Since $$\sum_{p \le Y} \log p \sim Y,$$ this implies that $$N \ge \exp(\log X \log \log X (1 - o(1))) = X^{\log \log X(1 - o(1))},$$ which shows that $N$ is (eventually) bigger than any power of $X$.

Case 2 The number $n$ of prime factors is bounded by $\log X$. In this case we show that $N$ will be co-prime to at least one element in the interval for $X$ large enough. Let $f(d)$ denote the number of integers in the interval $[a,a+X-1]$ which have a factor in common with $d$. Then since every $d$th integer is divisible by $d$, we get

$$ \left| f(d) - \frac{X}{d} \right| \le 1.$$

By inclusion-exclusion, we deduce that the number of integers in $[a,a+X-1]$ which are prime to $N$ is equal to:

$$f(1) - \sum f(q_i) + \sum f(q_i q_j) - \ldots $$

We want to show that this is non-zero unless $N$ is large. There are $2^n$ terms in this sum.

The "main term" gives

$$M = X \prod \left(1 - \frac{1}{q_i} \right)$$

and the error term is bounded by $2^n$, because the error in each term is bounded by $1$. We can estimate the error term as

$$2^n \le 2^{\log X} = X^{\log 2} = X^{0.69\ldots}$$

Now let's estimate $M$. It suffices to show that $M$ is bigger than the error term. We have $\log(1-x) \sim -x$.

$$\log M = \log X + \sum \log(1 - 1/q_i) \sim \log X - \sum \frac{1}{q_i},$$

On the other hand, if we denote the primes in order by $p_1, p_2, p_3, \ldots$, then

$$ \sum_{i=1}^{n} \frac{1}{q_i} \le \sum_{i=1}^{n} \frac{1}{p_i}.$$

By Merten's theorem, we have the estimate

$$\sum_{p \le Y} \frac{1}{p} \sim \log \log Y.$$

If $Y = p_n$ is the $n$th prime and $n \le \log X$, then we can take $Y \sim X \log X$, and then

$$\log \log Y = \log \log (X \log X) \sim \log \log X \ll \log X,$$

and hence $\log M \sim \log X$ and so $M > X^{1 - o(1)} > X^{\log 2}$.