From: Bob Silverman <bobs@rsa.com>
Subject: Product is a Square
Date: Fri, 10 Sep 1999 17:45:03 GMT
Newsgroups: sci.math
Keywords: finding sets of integers in intervals, whose product is a square

 A recent paper by Selfridge et.al. (to appear) discusses the
problem of finding sets of integers within a short interval whose
product is a square.

One question they did not consider is as follows: We work in Z
throughout.

Consider the set  S = {N, N+1, ...  N+k}

What is the smallest value of k,  as a function of N,  such that
we can find a subset of S whose product is a square when N must
be in the subset?

It is clear that  k >= N  is necessary when N is prime.

Problem:  Prove that  k = N  is sufficient for all N > M,  for some
value of M.

Problem:  Prove M = 5 suffices.

examples  Take N = 7.   Then  7 * 14 * 8 is a square.
If N = 6,  then  6 * 8 * 12 is a square.
If N = 3 (say),  then there is no subset of 3,4,5,6 whose product is
a square if 3 is in the subset. We must include 6 and then find an
odd power of two somewhere and there is none.
If N = 14,  then  14 * 21 * 18 * 27 is a square. We can do better
than this, though.  14 * 21 * 15 * 20 * 18 is a square, so k = 7
suffices.

Problem:  Let  M(N) be the minimum value of k that suffices as
N varies.  What is the average value of M(N)/N  as  N --> oo??

This differs from the Selfridge et.al. paper in that we require
a specific integer N,  to be part of the set whose product is a square.



--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
==============================================================================

From: John Rickard <jrr@255.255.255.192>
Subject: Re: Product is a Square
Date: 13 Sep 1999 19:06:04 +0100 (BST)
Newsgroups: sci.math

Bob Silverman <bobs@rsa.com> wrote:
: Consider the set  S = {N, N+1, ...  N+k}
:
: What is the smallest value of k,  as a function of N,  such that
: we can find a subset of S whose product is a square when N must
: be in the subset?
[...]
: Problem:  Prove that  k = N  is sufficient for all N > M,  for some
: value of M.
:
: Problem:  Prove M = 5 suffices.

Cases N <= 9 can be checked individually; for N >= 10 there is always
an m with N < 2 m^2 < 2N, and then {N, 2 m^2, 2N} is a subset whose
product is a square.

: Problem:  Let  M(N) be the minimum value of k that suffices as
: N varies.  What is the average value of M(N)/N  as  N --> oo??

The average *value* I feel sure must be 0, though I don't have a
proof; or are you after some kind of asymptotic expression as a
function of N?  I'd *guess* that M(N) is usually equal to the largest
prime factor of N, unless all the prime factors of N are small; how
does the average value of (largest prime factor of N)/N behave as
N -> oo?

-- 
John Rickard   <John.Rickard@virata.com>
==============================================================================

From: Bob Silverman <bobs@rsa.com>
Subject: Re: Product is a Square
Date: Tue, 14 Sep 1999 14:54:57 GMT
Newsgroups: sci.math

In article <iAr*d909n@news.virata.com>,
  John.Rickard@virata.com wrote:
> Bob Silverman <bobs@rsa.com> wrote:

<snip>

> Cases N <= 9 can be checked individually; for N >= 10 there is always
> an m with N < 2 m^2 < 2N, and then {N, 2 m^2, 2N} is a subset whose
> product is a square.

Yep.  This is correct.


>
> : Problem:  Let  M(N) be the minimum value of k that suffices as
> : N varies.  What is the average value of M(N)/N  as  N --> oo??
>
> The average *value* I feel sure must be 0, though I don't have a
> proof;

I agree with this. I don't have a proof either.  I expect that
M(N)  should be  N^(log 2)  from Dickman's function.  This immediately
gives an average value of 0.

Perhaps more interesting would be asking:  What is the average value of
log(M(N))/log(N)???

We need to match up the largest prime factor of N.  This should be
(except perhaps for a thin set) the right value of k.

i.e.  I can see the following happening:

Start with N.  Let  p  be its largest prime factor.  Then N+p
is divisible by p,  so we have matched 'p'.  Oops.  The largest
prime factor of N+p  is  q,  where q > p.  So we need to consider N+q.
etc..  We keep picking up additional 'large primes'.  However, I
guess that the instances where we need k  as large as a constant times
N should be rare.

There should be a 'large sieve' proof that exceptions are rare.  I am
trying to find one but I am only a beginner in sieve methods. I've
kicked Halberstam & Richert's book across the room in frustration
more than once....
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
==============================================================================

From: hrubin@odds.stat.purdue.edu (Herman Rubin)
Subject: Re: Product is a Square
Date: 14 Sep 1999 14:45:24 -0500
Newsgroups: sci.math

In article <7rlnjr$l0v$1@nnrp1.deja.com>, Bob Silverman  <bobs@rsa.com> wrote:
>In article <iAr*d909n@news.virata.com>,
>  John.Rickard@virata.com wrote:
>> Bob Silverman <bobs@rsa.com> wrote:

><snip>

>> Cases N <= 9 can be checked individually; for N >= 10 there is always
>> an m with N < 2 m^2 < 2N, and then {N, 2 m^2, 2N} is a subset whose
>> product is a square.

>Yep.  This is correct.



>> : Problem:  Let  M(N) be the minimum value of k that suffices as
>> : N varies.  What is the average value of M(N)/N  as  N --> oo??

>> The average *value* I feel sure must be 0, though I don't have a
>> proof;

>I agree with this. I don't have a proof either.  I expect that
>M(N)  should be  N^(log 2)  from Dickman's function.  This immediately
>gives an average value of 0.

>Perhaps more interesting would be asking:  What is the average value of
>log(M(N))/log(N)???

>We need to match up the largest prime factor of N.  This should be
>(except perhaps for a thin set) the right value of k.

>i.e.  I can see the following happening:

>Start with N.  Let  p  be its largest prime factor.  Then N+p
>is divisible by p,  so we have matched 'p'.  Oops.  The largest
>prime factor of N+p  is  q,  where q > p.  So we need to consider N+q.
>etc..  We keep picking up additional 'large primes'.  However, I
>guess that the instances where we need k  as large as a constant times
>N should be rare.

Even this might not be enough.  Consider the case N = 10.  Then 
p = 5, and N+p = 15.  So we now need a factor of 3 and one of 2.  
The smallest available number with an odd power of 3 is 12, which
does not add any complications, and the next one is 21, which is
already larger than 20.  Now we need an odd power of 2, and the
only ones less than 20 are 14 and 18.  We cannot use 14, as we
will need another 7, but 18 is fine, so M(10) = 8, as
10 x 15 x 12 x 18 = 180^2.

Are cases like this even more common than the ones bringing in
higher primes?  Or do they often bring in the higher primes
themselves?  In this case, it was avoided, but for larger
numbers, would it be?

>There should be a 'large sieve' proof that exceptions are rare.  I am
>trying to find one but I am only a beginner in sieve methods. I've
>kicked Halberstam & Richert's book across the room in frustration
>more than once....


-- 
This address is for information only.  I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
hrubin@stat.purdue.edu         Phone: (765)494-6054   FAX: (765)494-0558
==============================================================================

From: "Malcolm Harper" <pirround@NOSPAMhotmail.com>
Subject: Re: Product is a Square
Date: Thu, 16 Sep 1999 02:36:51 GMT
Newsgroups: sci.math

John Rickard <jrr@255.255.255.192> wrote in message
news:iAr*d909n@news.virata.com...
> Bob Silverman <bobs@rsa.com> wrote:
> : Consider the set  S = {N, N+1, ...  N+k}
> :
> : What is the smallest value of k,  as a function of N,  such that
> : we can find a subset of S whose product is a square when N must
> : be in the subset?
> [...]
> : Problem:  Prove that  k = N  is sufficient for all N > M,  for some
> : value of M.
> :
> : Problem:  Prove M = 5 suffices.
>
> Cases N <= 9 can be checked individually; for N >= 10 there is always
> an m with N < 2 m^2 < 2N, and then {N, 2 m^2, 2N} is a subset whose
> product is a square.
>
> : Problem:  Let  M(N) be the minimum value of k that suffices as
> : N varies.  What is the average value of M(N)/N  as  N --> oo??
>
> The average *value* I feel sure must be 0, though I don't have a
> proof; or are you after some kind of asymptotic expression as a
> function of N?  I'd *guess* that M(N) is usually equal to the largest
> prime factor of N, unless all the prime factors of N are small; how
> does the average value of (largest prime factor of N)/N behave as
> N -> oo?

Thm (Sum(N <= X, M(N)/N ))/X << 1/log X as X --> infinity.

Proof:
Divide the set { N <= X } into S1, S2 and S3:
S1 := { N<=X : p|N implies p is not in P } where
P  := { primes p : X^t1 < p <= X^t2 }
S2 := { N<=X^t3 }
S3 := { N : X^t3 < N <= X and p|N for some p in P }.

t1, t2 and t3 are some convenient parameters. They can be
taken as t1 = 1/10, t2 = 1/5 and t3 = 9/10.  The sum we wish
to bound, sum( N <= X, M(N)/N ) does not exceed
#S1 + #S2 + sum( N in S3, M(N)/N ).

Strategy:
1.  Use a sieve to bound #S1.
2.  Bound #S2.
3.  For N in S3, bound M(N)/N using the existence of p and
Rickard's approach.

Specifically for such t1, t2 a standard upper bound sieve
will yield #S1 << X/log X as X --> infinity.
#S2 <= X^t3.
For N in S3, N>X^t3, p<=X^t2 implies that for X large
enough, there is an integer m with
N < p(p+1)m^2 < (p+1)N/p hence
M(N)/N <= 1/p so
sum(N in S3, M(N)/N) <= X^(1-t1).

sum(N <= X, M(N)/N) << X/log X + X^(9/10)
hence the average << 1/log X as X --> infinity.

Notes:
1.  As Silverman notes in his original post, for N=p prime
M(p)/p = 1 so
sum(N <= X, M(N)/N) >= pi(X) >> X/log X and the average is
>> 1/log X so the result is in some sense best possible.

2.  t1, t2 and t3 are somewhat arbitrary.  For the sieve
result we should choose 0 < t1 < t2 < 1/4 - epsilon.
For the existence of m^2 we need
2*(X^t2) * (X^t2 + 1) <= X^(t3/2) for which
4*t2 + epsilon <= t3 suffices as X gets large.

3.  Choosing p prime simplifies the sieve, the primality of
p is not used elsewhere.

4.[Q]  Is there an external motivation for this question?
i.e. does it have a larger context?

Malcolm
To respond via email, remove the NOSPAM from my address.



==============================================================================

From: Bob Silverman <bobs@rsa.com>
Subject: Re: Product is a Square
Date: Thu, 16 Sep 1999 14:06:31 GMT
Newsgroups: sci.math

In article <7JYD3.462$j6.7111@carnaval.risq.qc.ca>,
  "Malcolm Harper" <pirround@NOSPAMhotmail.com> wrote:
>
> John Rickard <jrr@255.255.255.192> wrote in message
> news:iAr*d909n@news.virata.com...
> > Bob Silverman <bobs@rsa.com> wrote:
> > : Consider the set  S = {N, N+1, ...  N+k}
> > :
> > : What is the smallest value of k,  as a function of N,  such that
> > : we can find a subset of S whose product is a square when N must
> > : be in the subset?

<snip>

>
> Thm (Sum(N <= X, M(N)/N ))/X << 1/log X as X --> infinity.
>
> Proof:
> Divide the set { N <= X } into S1, S2 and S3:
> S1 := { N<=X : p|N implies p is not in P } where
> P  := { primes p : X^t1 < p <= X^t2 }
> S2 := { N<=X^t3 }
> S3 := { N : X^t3 < N <= X and p|N for some p in P }.
>
> t1, t2 and t3 are some convenient parameters. They can be
> taken as t1 = 1/10, t2 = 1/5 and t3 = 9/10.

You clearly know more about sieve methods than I.

A couple of questions.

(1) Doesn't the fundamental lemma of the sieve imply that t1 can
only be taken as high as (say) epsilon here,  for suitably small
epsilon?  How do we know that 1/10  (or any other value) is suitably
small? Indeed,  I had thought that the fundamental lemma implied
we could only take t1 as high as  O((log N) ^k) except under certain
circumstances (which I clearly still learning). What allows us to
take the bound on the sieve as high as N^1/10??

(2) Why partition into 3 parts (small, medium, large)  as opposed to
just (small, not small)???


> The sum we wish
> to bound, sum( N <= X, M(N)/N ) does not exceed
> #S1 + #S2 + sum( N in S3, M(N)/N ).
>
> Strategy:
> 1.  Use a sieve to bound #S1.
> 2.  Bound #S2.
> 3.  For N in S3, bound M(N)/N using the existence of p and
> Rickard's approach.
>
> Specifically for such t1, t2 a standard upper bound sieve
> will yield #S1 << X/log X as X --> infinity.

Could you explain this a bit further?  I am not even sure that
for a given N, we can take k = largest prime factor of N.  This is
what I was trying to show using sieve methods, but failed.


> #S2 <= X^t3.
> For N in S3, N>X^t3, p<=X^t2 implies that for X large
> enough, there is an integer m with
> N < p(p+1)m^2 < (p+1)N/p hence
> M(N)/N <= 1/p

I'm having a stupidity attack here.  What bound on M(N) are you using
here?  Where does the last 'hence ....' come from.  The last line
seems to come from nowhere...



 so
> sum(N in S3, M(N)/N) <= X^(1-t1).

This is clear.

>
> sum(N <= X, M(N)/N) << X/log X + X^(9/10)
> hence the average << 1/log X as X --> infinity.

Yep.

>
> Notes:
> 1.  As Silverman notes in his original post, for N=p prime
> M(p)/p = 1 so
> sum(N <= X, M(N)/N) >= pi(X) >> X/log X and the average is
> >> 1/log X so the result is in some sense best possible.

This is clear.

Thanks for the help.
>
> 2.  t1, t2 and t3 are somewhat arbitrary.  For the sieve
> result we should choose 0 < t1 < t2 < 1/4 - epsilon.

Why '1/4'?


> For the existence of m^2 we need
> 2*(X^t2) * (X^t2 + 1) <= X^(t3/2) for which
> 4*t2 + epsilon <= t3 suffices as X gets large.
>
> 3.  Choosing p prime simplifies the sieve, the primality of
> p is not used elsewhere.
>
> 4.[Q]  Is there an external motivation for this question?
> i.e. does it have a larger context?

Somewhat.  It arises from the study of highly composite integers
lying in short intervals.

Can you suggest a better book than Halberstam and Richert??
I am trying to self-teach and this is not a good text.
[The generic Serge Lang comment applies]
It looks like a terrific reference, however.

--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"


Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
==============================================================================

From: "Malcolm Harper" <pirround@NOSPAMhotmail.com>
Subject: Re: Product is a Square
Date: Fri, 17 Sep 1999 07:23:39 GMT
Newsgroups: sci.math

I'm afraid you are right and I am wrong.  Sorry.  The lower bound in the sum
cannot exceed (log X)^k.  I think the rest is OK.  Replacing X^t1 by log X
everywhere would then yield a bound << log log X / log X on the average.
Still going to zero, but not nearly so nice.

Bob Silverman <bobs@rsa.com> wrote in message
news:7rqtgt$c0j$1@nnrp1.deja.com...
> In article <7JYD3.462$j6.7111@carnaval.risq.qc.ca>,
>   "Malcolm Harper" <pirround@NOSPAMhotmail.com> wrote:
> > > Bob Silverman <bobs@rsa.com> wrote:
> > > : Consider the set  S = {N, N+1, ...  N+k}
> > > :
> > > : What is the smallest value of k,  as a function of N,  such that
> > > : we can find a subset of S whose product is a square when N must
> > > : be in the subset?

Then define M(N) equal the smallest such k and the goal is to show that the
average of M(N)/N,
sum( N <= X, M(N)/N ) /X --> 0 as X gets large.
>
> <snip>
>
> >
> > Thm (Sum(N <= X, M(N)/N ))/X << 1/log X as X --> infinity.

Change this to  << log log X / log X

> > Proof:
> > Divide the set { N <= X } into S1, S2 and S3:
> > S1 := { N<=X : p|N implies p is not in P } where
> > P  := { primes p : X^t1 < p <= X^t2 }
> > S2 := { N<=X^t3 }
> > S3 := { N : X^t3 < N <= X and p|N for some p in P }.
> >
> > t1, t2 and t3 are some convenient parameters. They can be
> > taken as t1 = 1/10, t2 = 1/5 and t3 = 9/10.

Replace X^t1 by log X, so we are sieving the set {N <= X} by primes p
log X < p <= X^t2

> You clearly know more about sieve methods than I.

Apparently not as much as I hoped.

> A couple of questions.
>
> (1) Doesn't the fundamental lemma of the sieve imply that t1 can
> only be taken as high as (say) epsilon here,  for suitably small
> epsilon?  How do we know that 1/10  (or any other value) is suitably
> small? Indeed,  I had thought that the fundamental lemma implied
> we could only take t1 as high as  O((log N) ^k) except under certain
> circumstances (which I clearly still learning). What allows us to
> take the bound on the sieve as high as N^1/10??

Nothing, we can't.  (Although it might give us the bound #S1 << X   :-)

> (2) Why partition into 3 parts (small, medium, large)  as opposed to
> just (small, not small)???
>
>
> > The sum we wish
> > to bound, sum( N <= X, M(N)/N ) does not exceed
> > #S1 + #S2 + sum( N in S3, M(N)/N ).
> >
> > Strategy:
> > 1.  Use a sieve to bound #S1.
> > 2.  Bound #S2.
> > 3.  For N in S3, bound M(N)/N using the existence of p and
> > Rickard's approach.

This is essentially the answer to your question (2).  If d|N and d is not
too large with respect to N then there is an m^2 with

d*(N/d) < d(d+1)m^2 < (d+1)*(N/d)

The product of the three terms is a square so

M(N) <= (d+1-d)*(N/d) = N/d and
M(N)/N <= 1/d
an improvement on the bound M(N)/N <= 1.  We want d small enough so that m^2
exists (slightly smaller than N^(1/4)) but large enough so that 1/d is
significantly smaller than 1.  Simplifying by only considering prime d=p,
the least N that we are going to treat this way must be larger than p^4 for
the greatest prime in P.  This says what P and S3 must look like.   S1 is
just the sifted set, while S2 is just defined to make the N in S3 large.

> > Specifically for such t1, t2 a standard upper bound sieve
> > will yield #S1 << X/log X as X --> infinity.
>
> Could you explain this a bit further?  I am not even sure that
> for a given N, we can take k = largest prime factor of N.  This is
> what I was trying to show using sieve methods, but failed.

The main term in the sieve will look like X*prod( log X < p <= X^t2,
(1-1/p)).  The log X gives a log log X in the numerator while the X^t2 gives
a log X in the denominator.  If we replace the upper bound X^t2 a slightly
smaller Z, log Z = log X / (A*log log X) then the sieve of Eratothenes will
yield the bound #S1 << X*((log log X)^2)/log X     (A is some large positive
constant).  The X*log log X/log X bound can be achieved by using a more
advanced sieve (Brun's sieve should do).

> > #S2 <= X^t3.
> > For N in S3, N>X^t3, p<=X^t2 implies that for X large
> > enough, there is an integer m with
> > N < p(p+1)m^2 < (p+1)N/p hence
> > M(N)/N <= 1/p
>
> I'm having a stupidity attack here.  What bound on M(N) are you using
> here?  Where does the last 'hence ....' come from.  The last line
> seems to come from nowhere...

I tried to explain a bit above.  I'm not using the "largest prime" approach,
but instead using the existence of a small, but bigger than log X, factor
d=p.  The exact condition on the size of p for the existence of m^2 is given
below.

>  so
> > sum(N in S3, M(N)/N) <= X^(1-t1).
>
> This is clear.

This will change now to sum <= X/log X upon replacing X^t1 by log X.

> > sum(N <= X, M(N)/N) << X/log X + X^(9/10)
> > hence the average << 1/log X as X --> infinity.

And this will change to sum << X*log log X / log X and average << log log
X/log X

> Yep.
>
> >
> > Notes:
> > 1.  As Silverman notes in his original post, for N=p prime
> > M(p)/p = 1 so
> > sum(N <= X, M(N)/N) >= pi(X) >> X/log X and the average is
> > >> 1/log X so the result is in some sense best possible.
>
> This is clear.

I am now wondering what the right bound is? Is it 1/log X?  I've been trying
to do some heurisitics, but I'm not very experienced at them.

> Thanks for the help.
> >
> > 2.  t1, t2 and t3 are somewhat arbitrary.  For the sieve
> > result we should choose 0 < t1 < t2 < 1/4 - epsilon.
>
> Why '1/4'?

Another error I'm afraid.  I was thinking of another context.  t2 is not
really important so long as we can take it positive.  t1 of course has
disappeared.

> > For the existence of m^2 we need
> > 2*(X^t2) * (X^t2 + 1) <= X^(t3/2) for which
> > 4*t2 + epsilon <= t3 suffices as X gets large.
> >
> > 3.  Choosing p prime simplifies the sieve, the primality of
> > p is not used elsewhere.

I've been trying to get a gain using
S3 = { N<=X : d|N for some d, log X < d <= X^t2 }
which would give the same bound for S3 and possibly a smaller bound for S1,
but I can't seem to make any headway.

> > 4.[Q]  Is there an external motivation for this question?
> > i.e. does it have a larger context?
>
> Somewhat.  It arises from the study of highly composite integers
> lying in short intervals.

Now that you point out the connection and after working on the problem, I
can see that it's related.  Thanks.

> Can you suggest a better book than Halberstam and Richert??
> I am trying to self-teach and this is not a good text.
> [The generic Serge Lang comment applies]
> It looks like a terrific reference, however.

I am not an expert on sieve theory.  I know H & R is a good reference.  One
drawback is that they use a lot of their own notation which can make
switching back and forth from their work to others more difficult.
Hooley's book _Applications of sieve methods to the theory of numbers_ is
good although out of print.  I think Davenport spends some time on sieves
(large sieve only?) in _Multiplicative Number Theory_. Ram Murty published a
set of lecture notes for a graduate course in sieve methods through CICMA
here in Montreal.  I could try to get you up a copy if you would like.

Malcolm