1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Check out the papers by Ahlswede and Khachatrian in Acta Arithmetica. (Maximal sets of numbers not containing $k+1$ pairwise coprime integers. ..) $\endgroup$ – Lucia Jan 3 at 3:12
  • $\begingroup$ @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. $\endgroup$ – Gerhard Paseman Jan 3 at 7:42
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Jan 3 at 7:58
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Jan 4 at 2:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.