Finding A Few Good q's

[rich burge]

Suppose {x_i|i=1..n} is a collection of n real numbers. Say that an
integer q is "good" when there are n integers
p_i such that:

max { q^(1/n)*abs(q*x_i-p_i) } < 1

Finding a few such good q's is easy. I will present here a method for
the case n=4. To begin, note that if any of the x_i are greater than
1 then x_i can be replaced by frac(x_i) without altering the problem
in any significant
way. For any (5x5) matrix M define the function size(M) to be the sum
of the squares of all it's entries.

Let A be the (5x5) identity matrix and D be the (1x5) vector
[1,x_1,x_2,x_3,x_4]. We can now iteratively build on
A so that after each iteration the 5th column of A gives better and
better simultaneous approximations to the x_i
of the form x_i=A[i+1,5]/A[1,5]. It also will turn out that good q's
are produced quite frequently.

To accomplish this proceed as follows:

Step 1: Form the following 4 matricies:

B[1]=[-(D[2]\D[1]),1,0,0,0;-(D[3]\D[1]),0,1,0,0;-(D[4]\D[1]),0,0,1,0;-
(D[5]\D[1]),0,0,0,1;1,0,0,0,0];

B[2]=[1,-(D[1]\D[2]),0,0,0;0,-(D[3]\D[2]),1,0,0;0,-(D[4]\D[2]),
0,1,0;0,-(D[5]\D[2]),0,0,1;0,1,0,0,0];

B[3]=[1,0,-(D[1]\D[3]),0,0;0,1,-(D[2]\D[3]),0,0;0,0,-(D[4]\D[3]),
1,0;0,0,-(D[5]\D[3]),0,1;0,0,1,0,0];

B[4]=[1,0,0,-(D[1]\D[4]),0;0,1,0,-(D[2]\D[4]),0;0,0,1,-(D[3]\D[4]),
0;0,0,0,-(D[5]\D[4]),1;0,0,0,1,0];

Step 2: Find some k so that size(B[k]*A^(-1)) is minimal.

Step 3: Set A=A*B[k]^(-1) and D=D*B[k]~ (here M~ is the transpose of
M)

Step 4: Using q=A[1,5] and p_i=A[1_i,5] compute max {q^(1/4)*abs(q*x_i-
p_i)} and output the result

Step 5: If "a few good q's" have been found, stop, otherwise goto step
1.

For example, if x_1=sqrt(2), x_2=sqrt(3), x_3=sqrt(5) and x_4=sqrt(7)
then the first 10000 iterations produce 4506
good q's.

Rich

[Gerry Myerson]

In article
<11d65461-5705-4d1e...@n16g2000prc.googlegroups.com>,
rich burge <r3...@aol.com> wrote:

> Suppose {x_i|i=1..n} is a collection of n real numbers. Say that an
> integer q is "good" when there are n integers
> p_i such that:
>
> max { q^(1/n)*abs(q*x_i-p_i) } < 1
>
> Finding a few such good q's is easy. I will present here a method for
> the case n=4.

And how does your method compare to what is already
in the literature for this venerable problem?

--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)

[rich burge]

On Feb 9, 2:17 pm, Gerry Myerson <ge...@maths.mq.edi.ai.i2u4email>
wrote:
> In article
> <11d65461-5705-4d1e-9828-55b47b851...@n16g2000prc.googlegroups.com>,

>  rich burge <r3...@aol.com> wrote:
>
> > Suppose {x_i|i=1..n} is a collection of n real numbers.  Say that an
> > integer q is "good" when there are n integers
> > p_i such that:
>
> > max { q^(1/n)*abs(q*x_i-p_i) } < 1
>
> > Finding a few such good q's is easy. I will present here a method for
> > the case n=4.  
>
> And how does your method compare to what is already
> in the literature for this venerable problem?

I do not really know.

The closest algorithm I know of is found in "A New Multidimensional
Continued Fraction Algorithm" by Tamura and Yasutomi recently
published in Mathematics of Computation. This one is different
essentially because a different size() function is used. Apparently
Lagarias has a method of finding all good q's based on latice
reduction. Just has a method of finding good q's but I am not sure
how it works. This is a simple Jacobi Perron algorithm, properly
tweaked. Not a big thing, I guess.

Rich