Briefly,

Question: Is it "good enough" to use least prime factor in choosing a maximal set of coprime integers in an interval?

The post title comes from a 1993 paper of Erdos and Sarkozy. They define some functions and show their asymptotic growth without showing explicit bounds. To restate their theorem 7, given natural number $k \gt 1$ and positive real number $\epsilon$, there is a real number $\alpha_k$ depending only on $k$ and numbers $n_0$ and $C$ (and both $n_0$ and $C$ depend on $k$ and on $\epsilon$) so that: for any $n \gt n_0$, for any integer $m$ and any subset $A$ of (integers of) the interval $[m+1,m+n]$ with $\mid A \mid \gt n*(\alpha_k + \epsilon)$, there are at least $Cn^k$ many ways to pick $k$ members of $A$ which are mutually coprime.

While the order of growth $n^k$ is nailed down, the numbers $C$ and $n_0$ and $\alpha_k$ are not made explicit (although it becomes clear how $\alpha_k$ should tend to 1 with $k$). Part of my goal is to make some other results like these with explicit values. In particular, in another post (link forthcoming ( here it is : A generalization of Landau's function)) I made the claim that the generalized Landau function $g(n,k)$ is like $(n/k)^k$ for $n$ greater than $k^5$. I expect something stronger than this holds, but I do not have a proof of this claim, and while Theorem 7 points in the direction of this claim, the theorem is not explicit enough to confirm or refute this claim.

I now introduce my setup to rephrase the above question more precisely.

If we pick the subset $A$ of all even numbers out of the interval $I=[m+1,m+n]$, it is clear that we can't get even two coprime numbers from $A$, much less $k$ mutually coprime numbers. So for $k \gt 2$, $\alpha_k$ should be larger than 1/2. If $B_{k-1}$ is that subset of $I$ with all members having some prime factor strictly less than the $k$th prime, it is also clear that we can't pick $k$ mutually coprime numbers from this subset. (We can vary this by choosing the set of numbers in $I$ having a prime factor coming from some chosen set of $k-1$ many primes.) So $\alpha_k$ has to grow like $1 - \prod (1 - 1/p)$ with the product being over the first $k$ primes $p$. One can look at the complement of $B_{k-1}$ in the interval and do some analysis and show that, for $n$ sufficiently large, there are sets of $k$ coprime integers in the complement. Because of the estimates used, the 1993 paper can't say much if $n \lt 2^k$.

Indeed, we should be able to do better with $n$ smaller than $2^k$. Let's collect least prime factors of numbers in an interval. Using $LPF$ for least prime factor, define $L(m,n)=\{ LPF(m+i) : 1 \leq i \leq n \}$; I abuse notation and have $L$ stand for the number of elements of $L(m,n)$. Indeed, any set of $k$ mutually coprime numbers have among them $k$ distinct $LPF$ values, so if we can pick $k$ coprimes from the interval, then $k \leq L$. So, given $k$, if we pick $n$ so that for every $m$ we look at $L(m,n)$ and find that $L \geq k$ for all these $m$, we have a nice $n$ for $k$ many coprimes in an interval of length $n$, and we can work on an explicit formula and get our bound, right?

Not so fast. It is possible that for a given $m,n$, we cannot pick $L$ coprimes from the interval. I have not constructed an example, but I imagine that we can pick $m$ and $n$ so that all even numbers in $I$ have an odd prime factor which is at most $n$. (This follows from work of Westzynthius and earlier on prime gaps.). If $L(m,n)$ contains all primes less than $n$, then any maximal set of coprime must avoid either an even number or it must avoid all numbers which have $LPF=p$, an odd prime that divides the even representative. So we may not have $L$ many coprimes.

So first question: Is there an interval $[m+1,m+n]$ of integers with $L(m,n)$ of size $L$ but with no subset of $L$ mutually coprime integers in this interval? If so, what is $n$?

I believe the answer is yes, but I have not worked it out. Note that one estimate of the size of $n$ involves summing prime reciprocals for odd primes, and that the answer thus is no if $n \lt 23$. The answer is probably still no for $n \lt 50$, but I am unsure of this.

However, a yes answer backed up with detail about $m$ and $n$ is not a deal breaker for me. I am willing to make a construction where I start with $n$ large enough (so that $L \geq 2k$ for example) to get what I need. In fact, what I really need is (with minimum having $m$ taken over all integers) $K(n) = \min_m \{ $ the size of the largest subset of mutually coprime integers from $I \}$. Let us define in parallel $L(n) = \min_m \mid L(m,n) \mid$ .

Next question : How do the growth rates of $L(n)$ and $K(n)$ compare with $n$? In particular, is $2*K(n) \gt L(n)$ for every $n$?

One can prove (as is done in the above post asking about Landau's function; there $C(k)$ is a function of Jacobsthal) that $L(n)=K(n)=$ function related to $C(K(n))$ for $n$ at most 22. I tried there to build a set using $L(m,n)$; a problem arises in that an element poorly chosen later may not be coprime to an earlier chosen element. Another problem is that it is not clear what the set $L(m,n)$ looks like in general. Westzynthius gives explicitly that there are $m$ where max $L(m,n)$ is less than any fraction of $n$ for $n$ sufficiently large (so pick a fraction $\epsilon$, then there are $n$ large such that the Max is less than $\epsilon n$). In particular, there are intervals of consecutive numbers with every number having a significant smooth factor, I.e. every number is a multiple of some number with several distinct prime factors less than $n$.

However, if $L(n)$ does not grow much faster than $K(n)$, then if we want $k$ coprimes, we pick $n$ with $L(n)$ not much larger than (say) $2*k$, do our construction using $LPF$, and get the $k$ coprimes, and do this in a small enough interval. Then we can use the results to give asymptotics to the generalized Landau function.

So finally, Question: Is there any literature on (or approaching) $L(n)$ and its relation to $K(n)$?

This feels like a decent and original academic research topic to me. If it is, and a student wants to work on it (or an advisor wants to suggest it to a student), I would like to know about it and share some further ideas. Please let me know of this happens.

Gerhard "To Start 2019 Off Right" Paseman, 2019.01.01.