Date: Fri, 31 Oct 1997 11:54:35 -0600 (CST)
From: Richard Blecksmith <richard>
To: rusin
Subject: Harvey's question

Hi, Dave

The question Harvey asked was:  In the equation

           3 x^2 + 5 y^2 = 2^(2n+1)

do  x  and  y  go to infinity with  n?  It now passes elementary
congruence tests mod 3 and 5.

Richard

==============================================================================
Date: Fri, 31 Oct 1997 17:10:00 -0600 (CST)
From: Dave Rusin <rusin>
To: richard
Subject: Re:  Harvey's question
Cc: blau, rusin

>The question Harvey asked was:  In the equation
>
>           3 x^2 + 5 y^2 = 2^(2n+1)
>
>do  x  and  y  go to infinity with  n? 

Still don't know for sure, but here are the details justifying
previous thoughts.

For a fixed  N, let us find all pairs (x,y) with
	(3x)^2 + 15 y^2 = 3* 2^N.
The left side is the norm of  z = (3x) + y alpha   in the ring  Z[beta],
where  alpha^2 = -15  and  beta=(1+alpha)/2. The left side may also be 
written  z * zbar  (where bar=complex conjugation). 

The equality of ideals
	(z) (z)bar = P^2 (Q Qbar)^N
[where  P = (3, alpha)  and  Q = (2, beta)  are prime ideals]
forces  (z) = P Q^i Qbar^j  for some  i+j=N.  (Since the ideal on the
left is principal, and the class group of  Z[beta] has order 2, we
conclude  i+j  must be odd, i.e.,  N  is odd!) If, say, i >= j, we may
pull out  Q^j Qbar^j = (2)^j ,  P*Qbar = ( 1+beta ), and Q^2 = (beta)
to write  (z) = (1+beta)(2)^j (beta)^k  for some  j  and  k  with 2k+2j=N-1.
Since this ring has only two units, it follows that
	z = (+-) { 1+beta }* 2^j * beta^k
for some k  and  j  as before. (If instead  i <= j, we get the complex
conjugate of this number.) In particular, up to reflections there are
(N-1)/2 solutions (we must take  j > 0 to keep  Re(z)  and  Im(z)/alpha  
integral; then  Re(z) = 0 mod 3 is automatic.)

OK, now we know all solutions. Which ones have the smallest  x, y?

From our initial definition of  z, the logarithm of  z  becomes
	(N-1)/2 * log(2) + log(6)/2 + i * arctan( sqrt(5/3)*y/x )
so the question of whether we can have  y  very large or small (relative to  x)
is equivalent to asking how small this imaginary part of the log is 
(modulo pi/2). 

On the other hand, from our characterization of the solutions  z, the 
logarithm may be written
	log(1+beta) + j log(2) + k log(beta)
so that imaginary part is (1/2i) times
	log((1+beta)/(1+beta:bar)) + k log(beta/beta:bar)

Combining these paragraphs, we see we need an estimate of the minimum value of
	mu + k nu + l pi/2
where mu and nu (and pi/2 !) are logarithms of algebraic numbers, and
k and l are integers, with  k < (N-1)/2. 

Call this minimum  f(N), that is, we can find  k  and  l  with
	mu + k nu + l pi/2 = f(N), and so
	arctan( sqrt(5/3)*(y/x) ) = f(N).
Then for this  k  and with  j=(N-1)/2 - k, we have
	z = {1+beta}*2^j*beta^k
close to one of the axes, say, the positive  x-axis; indeed, then the ratio
	r = sqrt(5/3)* y/x = tan ( f(N) ) 
is about  f(N), assuming  f(N)  is fairly small. We can then return to 
the original equation of the ellipse and compute  x  and  y  in terms of  r; 
I get
	y = r sqrt( 2^N/5/(1+r^2) )
Since  r  will be small this is about
	y ~~  f(N) * 2^(N/2) /sqrt(5).

So now the original question: how small can  y  get? Well, it's clear we 
need to know the size of  f(N).  In order for there to be solutions (x,y) 
for infinitely many  N  with  y  bounded, we must have  f(N) = O( 1/ 2^(N/2) ).
This seems exorbitant. On the other hand, it should be possible as
with continued fractions to show  f(N) = O(1/N); I couldn't quite get that
to work because  mu <> 0. 

Based on the experience with  pi, I suspect one could prove a result like
	There exist  r, c  such that  f(N) >= c / N^r  for all N.
Then we would have  y >= C * 2^(N/2) / N^r, and in particular, y must
grow with  N.

This certainly sounds like one of those transcendental number results
but I don't know that field very well.

dave

==============================================================================
Date: Mon, 3 Nov 1997 10:36:11 -0600 (CST)
From: Dave Rusin <rusin>
To: blau, richard
Subject:  Re:  Harvey's question

The transcendental number theory fact I wanted appears to be proven.
Here is the result (Theorem 3.1 of Baker's Transcendental Number
Theory, trimmed for this application):

Let alpha1 and alpha2 be nonzero algebraic numbers and let  b1, b2, b3 be
integers at most  B  in magnitude (for some  B >= 2 ).  Then there is
a constant  C  for which
	| b1 log alpha1 + b2 log alpha2 + b3 pi/2 | > B ^ (-C)
whenever the lefthand side does not vanish.

(The exponent  C  is effectively computable).

Therefore (unless I'm badly misreading this theorem), the conclusion
I drew in  my previous letter is substantiated:

>Based on the experience with  pi, I suspect one could prove a result like
>        There exist  r, c  such that  f(N) >= c / N^r  for all N.
>Then we would have  y >= C * 2^(N/2) / N^r, and in particular, y must
>grow with  N.

dave

==============================================================================
Date: Fri, 31 Oct 1997 14:10:05 -0600 (CST)
From: Dave Rusin <rusin>
To: kubo@abel.math.harvard.edu
Subject: Constraints on quality of rational approximations.

Tal,

Some time ago you posted to sci.math a reference to results of this form:
	 |Pi - m/n| < c/n^42  => no solutions for some  c.
I would like to know if there are general statements limiting the 
quality of rational approximations.

A colleague has asked if the solutions to
	3 x^2 + 5 y^2 = 2^n
[n must be odd else no solutions] must have  x  and  y  both grow with  n.
Factoring in the ring  Z[beta], beta=(1+sqrt(-15))/2,  convinced me the
rate of growth of  x  and  y  is limited by the minimum absolute values of
expressions
	k*theta - l*(pi/2) + phi
where  theta  and  phi  are respectively the arguments, or logs, of the complex
algebraic numbers  beta  and  (1+beta),  if I've done the arithmetic right.
If the value of  k  is restricted to be at most  N, say, how small can
the expression be?

Clearly this is analogous to minimizing the magnitude of
	n*Pi - m*1
so one is led to ask if a similar result is true, namely, that for some
numbers  c  and  r  there are no solutions to
	| k*theta - l*(pi/2) + phi | < c/N^r

References would be appreciated. I'm sort of dimly aware of what transcendental
number theory has accomplished but I'm hardly a resource person in this area.

dave