# On sets of coprime integers in intervals

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.

• Check out the papers by Ahlswede and Khachatrian in Acta Arithmetica. (Maximal sets of numbers not containing $k+1$ pairwise coprime integers. ..) – Lucia Jan 3 at 3:12
• @Lucia, thanks for the references. As I understand it, most of their (A and Kh) results apply either to the case k=2 (but among subsets of odd numbers in some cases) or to arbitrary k but always using the interval I with m=0, in which case for me L for [1,n] and K both equal 1+pi(n). I do not see how to translate their results to nonzero m, nor further to apply them to determine when L > K could happen. Do you see an application? Gerhard "Maybe I Need New Glasses?" Paseman, 2019.01.02. – Gerhard Paseman Jan 3 at 7:42
• Here is a related question which maybe you can answer, using terminology from their papers. Given n sufficiently large, let F be (m,n] intersect with their E(n,k,s). How big must m be to keep F from having k distinct coprimes? Gerhard "Feels This Is Also Original" Paseman, 2019.01.02. – Gerhard Paseman Jan 3 at 7:58
• An attempt at answering the first question is: let N be a large primorial divided by (say) 30. Let there be an interval of length greater than 5p where p is the largest prime factor of N, such that every number in the interval is not coprime to N. If we can arrange L for this interval to be $\pi(p)$, then K is at most L-3. Gerhard "Still Trying To Arrange Thoughts" Paseman, 2019.01.03. – Gerhard Paseman Jan 4 at 2:06