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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.