From: shallit@graceland.uwaterloo.ca (Jeffrey Shallit)
Subject: Re: pairwise relatively prime numbers in an interval
Date: 18 Aug 2000 15:42:03 GMT
Newsgroups: sci.math.research
Summary: [missing]

In article <Pine.GSO.4.21.0008150656320.1075-100000@tarski.math.usf.edu>,
Edwin Clark  <eclark@math.usf.edu> wrote:
>
>Sorry, but I goofed in stating the question. This
>is what I meant to ask:
>
>For integers x > 0 and y >=0, let F(x,y) denote the maximum cardinality 
>of a subset of { y+1, y+2, . . . ,y + x } whose elements are pairwise 
>relatively prime, and let 
>
>             F*(x) = min { F(x,y) | y >=0 }.
>
>In 1971 Erdos and Selfridge proved that for 
>every e > 0, if x is sufficiently large then
>
>            x^{1/2 - e} <  F*(x).
>
>Can anyone tell me more about lower bounds for F*(x)? 
>
>Thanks,
>
>Edwin Clark
>
>------------------------------------------------------
>                    W. Edwin Clark  
>Department of Mathematics, University of South Florida,
>4202 East Fowler Avenue, PHY 114, Tampa, FL 33620-5700
>        http://www.math.usf.edu/~eclark/
>------------------------------------------------------

I've already responded to Edwin Clark by e-mail, but here goes again:

In a paper I wrote with my student Ming-wei Wang, and recently presented at
a conference in London, Ontario, we observe the following:

	Let f(r) denote the least integer y such that every interval of
	y consecutive integers contains at least r pairwise relatively
	prime integers.

	Let C(r) be the classical Jacobsthal function, i.e., C(r) counts
	the maximum distance between two consecutive numbers relatively
	prime to n, where n is divisible by r distinct primes.

	Then f(r) = C(r-1) for r >= 1.

Iwaniec proved the upper bound C(r) = O(r^2 (log r)^2) in 1978, and no 
one has improved this bound since then.  The general consensus
seems that it is probably quite hard to improve.

Since any improvement on C would give a corresponding improvement on
f, and vice versa, we may conclude that f(r) = O(r^2 (log r)^2) and
that no one currently knows anything better for an upper bound.

There are some lower bounds known for C(r), but since I am away
from  my papers and books I cannot find them at the moment.  I believe
it is known that C(r) >  r * t(r), where t is something roughly on the
order of (log r)/(log log r), but I am probably misremembering the exact
bound.

Jeffrey Shallit, Computer Science, University of Waterloo,
Waterloo, Ontario  N2L 3G1 Canada shallit@graceland.uwaterloo.ca
URL = http://www.math.uwaterloo.ca/~shallit/