Conference rusure::math

First remark: the sequence defined in .1 cannot loop, as it is strictly
increasing: (m/n) + (1/(m*n)) > (m/n). The last pair in the example given in
.1 is (1157,442), not (1156,442).


Let us call "seed" the first term of the sequence of rationals defined in .1.


To the first question stated in .1:

		Does the sequence defined in .1 converge
		to sqrt(7) for all seeds?

I answer "no", as the proposition enunciated in .0 is equally true for sqrt(3)
(!), for instance, instead of sqrt(7): so build such a sequence for sqrt(3);
the built sequence is admissible for sqrt(7) also, as sqrt(3) < sqrt(7), but
it cannot converge to sqrt(7), as it never passes sqrt(3).


I have no answer for the second question in .1:
		
		What criteria determine convergence of the
		sequence defined in .1 to what value?

Does anyone have an idea?
Mihai.

>I answer "no", as the proposition enunciated in .0 is equally true for sqrt(3)
>(!), for instance, instead of sqrt(7)...

I don't think so; 1/1 < sqrt(3) but 1/1 + 1/(1*1) isn't.

There's a famous 19th century theorem by Liouville that limits how "good" a
rational approximation to an algebraic number can be; it says that for any
number x which is the root of an n-th degree irreducible equation and any
rational approximation p/q to x, 

	abs(x - p/q) > c/q^n    for some c > 0 which depends only on x

for square roots, n = 2, so from the structure of this you could certainly
surmise that there is some maximal fixed d, 0 < d < 1, such that 

	m/n < sqrt(3) ==> m/n + d/(mn) < sqrt(3)

But I haven't the foggiest idea of what d is, just as I haven't the foggiest
idea of how to prove the result in .0 from Liouville's theorem...

You're right, I gave a slightly wrong counterexample, though a type .0
proposition is true for sqrt(3) if you restrict it to  m > 1  and  n > 1 .

Consider also the .0 proposition for 2 instead of sqrt(3) or sqrt(7).
It works for all integer m and n, so this *is* a good reason for not all
seeds breeding sequences convergent to sqrt(7).

Mihai.

The conjecture about m/n<sqrt(7) implying that adding 1/mn is still < sqrt(7),
is that a "famous unproved conjecture" or is there a published proof ?

/Eric

Does everybody wishes to know?...

Well, the answer is that the problem 1889.0 was published by Radu Gologan at
the beginning of the '80s (or late '70s) in the Romanian mathematical magazine
for high-school students, "Gazeta Matematica (seria B)". Knowing that they
would publish only elementary problems could help you to solve it in an
elementary way - I can produce my elementary solution any time. But I don't
know how far it can be generalized, and then I am puzzled by the limits of the
sequences defined in .1 by John, and do Liouville-type results help here?

Mihai.

For those who have been patient and merciful enough to read 1889.7, there
were some typing errors:

------------------------------------------------------------------------
**Correction of 6.3:**
Replace                                /             By
------------------------------------------------------------------------
                 p-1                   /            p-1                 
        v(n+p) = Sum (a(i) * v(i))     /   v(n+p) = Sum (a(i) * v(n+i)) 
                 i=0                   /            i=0                 
------------------------------------------------------------------------
------------------------------------------------------------------------
**Correction of 6.5:**
Replace                                /             By
------------------------------------------------------------------------
Then    Fq(1, 1) = (0, 1)              /   Then    F2(1, 1) = (0, 1)   
        Fq(0, 1) = (1, 0)              /           F2(0, 1) = (1, 0)   
        Fq(1, 0) = (0, 0)              /           F2(1, 0) = (0, 0)   
        Fq(0, 0) = (1, 0)              /           F2(0, 0) = (1, 0)   
------------------------------------------------------------------------

Sorry!
Mihai.

I'm still enough confused about .7 to not know whether it answer my question
asking if the sqrt(7)  thing is a known provable thing.

I would very much like to see non-elementary proofs of 1889.0. I have mine,
and it is elementary, I have even a slight generalization for it (regarding
other numbers than sqrt(7)), but I realize that I do not know all the numbers
which can replace sqrt(7) in 1889.0.

Also, consider the sequence defined in 1889.1: it is convergent, but what is
its limit? It is not clear to me that it is sqrt(7)...

This problem (1889.0) seems to be rather deep, it seems to be close to a lot
of fundamental ideas.

Mihai.

let v7 mean sqrt(7) to save me typing.

v7 = 2 + 1/x.

x = 1/(v7-2).  Multiplying top and bottom by v7+2:

x = (v7+2)/3.

Since v7 is between 2 and 3, v7+2 is therefore between 4 and 5.  So x is
between 4/3 and 5/3, so:

x = 1 + 1/y.

y = 1/(x-1) = 1/((v7+2)/3 - 1) = 3/(v7-1).   [ I multiplied top and bot by 3 ].

Multiplying top and bottom by v7+1:

y = 3(v7+1)/6 = (v7+1)/2.

Since v7 is between 2 and 3, v7+1 is between 3 and 4.  So y is between 3/2
and 4/2, so:

y = 1 + 1/z.

z = 1/(y-1) = 1/((v7+1)/2)-1) = 2/(v7+1-2) = 2/(v7-1) = 2(v7+1)/6 = (v7+1)/3.

Gee, at end of the alphabet, let's wrap to a...

z is between (2+1)/3 and (3+1)/3 or 1 and 4/3.

z = 1 + 1/a.

a = 1/(z-1) = 1/((v7+1/3)-1) = 3/(v7-2) = 3(v7+2)/3 = v7+2.

Taking this all together,

v7 = 2+	1
	------------
	1 +	1
		-------------------
		1 +	1
			---------------
			1 +	1
				----------------
				v7 + 2

This means that the continued fraction denominators are this repeating pattern:

	v7 = [2 1 1 1 4 1 1 1 4 1 1 1 4 1 1 1 ....]

which is sort of interesting because of several things.  First, that what
looked "irrational" becomes just as regular as a repeating decimal when viewed
in this form.  Even transcendental numbers, such as e, confess to regularity.
e = [2 1 2 1 1 4 1 1 6 1 1 8 1 1 10 1 1 12 1 ....] although others, such
as pi don't.  (Does that make pi more transcendental than e ??)

Anyway, the other interesting thing about this continued fraction for 7 is
all the 1's.  Or, if not the 1's themselves, perhaps the fact that the
length before repetition is 4 denominators.  (Is length of repetition
related to length of repetition in decimal representation of 1/7 ?)

Does this representation of v7 help with the original puzzle ?  I thought
maybe it would if we could message the continued fraction into a form where
1/(AxB) is continually added on, but I don't see it yet...

/Eric

                <<< RUSURE::NOTES1:[NOTES$LIBRARY]MATH.NOTE;7 >>>
                            -< Mathematics at DEC >-
================================================================================
Note 1889.13     How close to sqrt(7) can a rational number be?         13 of 13
EVTSG8::ESANU "Au temps pour moi"                   118 lines   6-SEP-1994 08:23
               -< re. .12: pi is not more transcendental than e >-
--------------------------------------------------------------------------------
Sorry for answering so late. I have also been working on your
interesting questions, Eric:

> This means that the continued fraction denominators are this repeating pattern:
>
>	v7 = [2 1 1 1 4 1 1 1 4 1 1 1 4 1 1 1 ....]
>
> which is sort of interesting because of several things.  First, that what
> looked "irrational" becomes just as regular as a repeating decimal when viewed
> in this form.  Even transcendental numbers, such as e, confess to regularity.
> e = [2 1 2 1 1 4 1 1 6 1 1 8 1 1 10 1 1 12 1 ....] although others, such
<<<< Q1 and Q2
> as pi don't.  (Does that make pi more transcendental than e ??)
> 
> Anyway, the other interesting thing about this continued fraction for 7 is
> all the 1's.  Or, if not the 1's themselves, perhaps the fact that the
<<<< Q3
> length before repetition is 4 denominators.  (Is length of repetition
> related to length of repetition in decimal representation of 1/7 ?)

<<<< Q4
> Does this representation of v7 help with the original puzzle ? 

(here v7 = sqrt(7))

-------------------------------------------------------------------
Q1. Even pi has some very regular expressions, as soon as we accept
non-regular continued fractions:

	     4  1**2 2**2 3**2 4**2
	pi = -  ---- ---- ---- ----
	     1+  3  + 5  + 7  + 9  +...


-------------------------------------------------------------------
Q2. So is pi 'more' transcendental than e?

The set of the numbers which have a periodic decimal representation
(starting after a finite number of decimals) is enumerable (it is Q,
the set of the rational numbers).

The set of the numbers which are the limit of a periodic regular
continued fraction (starting after a finite number of partial
quotients) is also enumerable.

Why is it so? Because it is the union of an enumerable set of (disjoint)
enumerable sets:
                            -------------
Let x = [a(1),a(2),...,a(m),b(1),...,b(n)] be the continued fraction
convergent to x and the barred part represent its periodic sequence of
partial quotients.

Then our set is =  U  {all sequences of digits of length m} x
                m,n in N
		     x {all sequences of digits of length n} =

                = U  (S(9)^m x S(9)^n)
                m,n in N

where S(9) = {0,1,2,3,4,5,6,7,8,9}

which is an enumerable set of finite sets, so it is enumerable.

Another proof of the enumarability of this set: it is also known since
Lagrange that this set here above (the set of the numbers which are
the limit of a periodic regular continued fraction, starting after a
finite number of partial quotients) is the set of the quadratic surds,
i.e. the numbers of the form

	A + sqrt(B)
        -----------
            C

(A,B,C integers,  B >= 0,  C <> 0).


Conclusion: this set being enumerable and dense in R, its
complementary has the power of the continuum and is dense in R, same
situation as Q and R\Q or algebraic numbers and transcendental
numbers. So, at a first glance, this confers to pi a kind of 'more
transcendental' flavour than e has, but even pi is part of a 'regular'
enumerable set (see 1 above)! So, finally, *in this sense*, really
every number is 'more transcendental' than any other number...


-------------------------------------------------------------------
Q3. Link between the periodicity of the decimal representation of 1/7
and the periodicity of the representation of sqrt(7) as regular
continued fraction.

I haven't succeeded in finding one... except the following loose one:

- the periodicity of the decimal representation of 1/q (q positive
integer) <= q

- the periodicity of the regular continued fraction convergent to
sqrt(q) <= card {(a,b) / a,b integers, a**2 + b**2 <= q**2}

(the number of points of integer coordinates in the origin-centered
disk of radius q).

Notation used: '<=' for 'less or equal'

Does anyone know better?


-------------------------------------------------------------------
Q4. Well, these ideas might help (I really don't know!). The original
puzzle does also have an *elementary* solution.

Mihai.


-------------------------------------------------------------------
REFERENCES:

* G.H. Hardy, E.M. Wright, An introduction to the Theory of Numbers,
Oxford University Press        << The Holy Writ! >>

* Claude Brezinski, History of Continued Fractions and Pade'
Approximants, Springer-Verlag, 12 SCM

Wording the base note a bit differently:

	For all m/n (integer m,n) less than sqrt(7), it is always more
	than 1/(mn) less.

Question:

	What's the best m/n we can find ?  That is, find m,n (integers)
	that are best fits to this equation:

		m/n + 1/(mn) = sqrt(7).

As I ask this, I'm not sure if a qualifier is needed.  For example, perhaps
it's relatively easy to find m/n *larger* than sqrt(7) but by less than
1/(mn) ?  If not, then no qualifier is needed.  If so, then we need to say:

	FOR M/N LESS THAN SQRT(7) and m,n (integers), what m,n best fits...

/Eric

Eric, could you please reword your rewording? Pay attention to:

>	What's the best m/n we can find ?  That is, find m,n (integers)
>	that are best fits to this equation:
>
>		m/n + 1/(mn) = sqrt(7).

LHS is rational, while RHS is irrational...

Mihai.

re .15
    
>LHS is rational, while RHS is irrational...
    
    I'm sure Eric knows that. That's why he asks for "best fits" and not
    solutions.
    
    I guess what he's getting at, to give an example, is that given
    m,n < 1000, any m/n will differ from sqrt(7) by at least 1E-6, so he
    wants to know how to find the m and n that get as close as possible to
    sqrt(7). Presumably brute force is not the answer.
    
    I thought there was a sizable body of theory around nearest rational
    approximants (but I don't know any of it).

re. .14, re. .16:


The best rational approximants to any real number are the partial quotients
of its expansion as a continued fraction. Clear and complete presentations
of the subject are made in the following classical books:

[1] G.H. Hardy, E.M. Wright, An Introduction  to the Theory of Numbers,
Oxford University Press

[2] Ivan Niven, herbert S. Zuckerman, Hugh L. Montgomery, An Introduction 
to the Theory of Numbers, John Wiley & Sons, inc.



Beware: The sequence m(k+1)/n(k+1), defined by

	m(0)/n(0) < sqrt(7)

	m(1)/n(1) = m(0)/n(0) + 1/(m(0)*n(0)) < sqrt(7)

	...

	m(k+1)/n(k+1) = m(k)/n(k) + 1/(m(k)*n(k)) < sqrt(7)

might well *not* converge to sqrt(7).

I even suspect some of these sequences to have a transcendental limit, as
some of them converge extremely rapidly. my feeling is based on the
following grounds (see the Liouville-type results in 6.6, note 1889.7):

iv) The slowest convergent sequences of rationals have rational limits.

iii) On the third place are the rational approximants to quadratic surds.

ii) On the second place are, generally, rational sequences convergent to
algebraic numbers.

i) The quickest convergent rational sequences have transcendental limits.



Perhaps in the best position to solve the problem .0 are 15 years old kids
who have not yet heard about continued fractions...

Mihai.

As I calculated in .12, the continued fraction for v7 (square root of 7)
is

v7 = [2 1 1 1 4 1 1 1 4 1 1 1 4 1 1 1 ....]

Suppose we lop off everything after the first 4.  That approximation gives:

v7 ~ 2+1/(1+1/(1+1/(1+1/4))) = 2 + 9/14 = 37/14

As reminded by Mihai in .17, 37/14 is a "best" approximation, which means
that no fraction with the same or smaller denominator can be any closer
than v7.

	(by the way, my DCL says 37/14 * 37/14 = 6.98469)

However, it's not clear to me that this approximation is best when measured
according to see what happens when 1/mn is added on.

What I'm worried about is, suppose C/D is closer to v7 than a/b.  But if C and
D are larger integers than a/b, then 1/CD is much smaller than 1/ab.  Hence
isn't it possible that

	a/b + 1/ab is closer to v7 than C/D + 1/CD, even though

	C/D is closer to v7 than a/b ?


If so, then the continued fraction might not give us the best approximation
I'm looking for.

Perhaps another way to ask what I'm looking for:

	What is the limit of a/b + 1/ab for integers a,b as a/b approaches
	v7 from below ?

If you tell me the limit is v7, then give some support to your claim by
finding a,b such that

	a/b + 1/ab + c = v7

where a,b are integers and c is a positive real number less than
1E-20.  (reciprocal of 10 to the 20th power)

/Eric

re .18
    
>However, it's not clear to me that this approximation is best when measured
>according to see what happens when 1/mn is added on.
    
    Yes. I overlooked that when I posted .16. I don't know the answer to
    your question.

Let  k,m,n  be positive integers. The following
proposition is true for:

(i)    p = 4 * k  and  k, m, n > 0
(ii)   p = 4 * k + 3  and  k, m, n > 0
(iii)  p = 4 * k + 3  and  k = 0;  m, n > 1

	    m
	If  - < sqrt(p)
	    n
	           m     1
	then also  - + ----- < sqrt(p)
	           n   m * n

Mihai.

Let S be the set of x > 0 such that:

	m               m     1
	- < x  implies  - + ----- < x, for any m and n positive integers.
	n               n   m * n

The numbers 1 and (3+sqrt(5))/2 are the two smallest elements of S.
The proof is long, tedious, and left to the reader.

(3+sqrt(5))/2 = 2.6180...

Hmmm.  If (3+v5)/2 is the smallest S, then (1+v5)/2 has a counterexample.

In other words, we can find

	m/n < (1+v5)/2

such that

	m/n + 1/(mn) >= (1+v5)/2

First, let

	g = (1+v5)/2

so my hand doesn't get tired keeping typing the expr.  (g for golden ratio?)

Well, v5 is about 2.2 something, so

	g = 3.2/2

Try m/n = 3/2.

Question is, is 3/2 + 1/6 larger (or equal) than (to) g ?  I don't think so,
since 1/6 is .1666... which is smaller than .2...

So this m/n isn't a counterexample for g.  Can any of you find one ?

/Eric

>Question is, is 3/2 + 1/6 larger (or equal) than (to) g ?  I don't think so,
>since 1/6 is .1666... which is smaller than .2...

Question is, is 3/2 + 1/6 larger (or equal) than (to) g ?  I think so,
since 1/6 is .1666... which is greater than .2/2...

Dick

whoops, yeah, sorry, i forgot the /2 ...

/Eric

> Let S be the set of x > 0 such that:
>
>	m               m     1
>	- < x  implies  - + ----- < x, for any m and n positive integers.
>	n               n   m * n
>
> The numbers 1 and (3+sqrt(5))/2 are the two smallest elements of S.
> The proof is long, tedious, and left to the reader.

Can you give us the outline of the proof? Also, how does the set S look
like? What are its connected components, for instance?

Thank you,
Mihai.

> Can you give us the outline of the proof?

Let S be the set of x > 0 such that:

	m               m     1
	- < x  implies  - + ----- < x, for any m and n positive integers.
	n               n   m * n

The numbers 1 and (3+sqrt(5))/2 are the two smallest elements of S.


Suppose some 0 < x < 1 is in S.  Let m = 1, and let n be the smallest positive
integer such that 1/n < x.  Then m/n + 1/(m*n) = 2/n > x, so x is not in S.
To see that 2/n > x, note the following:

	if       x > 1/2, then n = 2, and 2/n = 1 > x;
	if 1/2 > x > 1/3, then n = 3, and 2/n = 2/3 > 1/2 > x;
	if 1/3 > x > 1/4, then n = 4, and 2/n = 2/4 > 1/3 > x;
	...
	if 1/(j-1) > x > 1/j for an integer j >= 3, then take m=1 and n=j,
	so that m/n + 1/(m*n) = 2/j > 1/(j-1) > x.

Claim: 1 is in S.  This is equivalent to showing that there are no integers
m and n such that m/n < 1 < m/n + 1/(m*n); proof is left to the reader.
Hint: 1-m/n > 1/n.

To show that (3+sqrt(5))/2 is the second-smallest element of S, it's
necessary to show that for any 1 < x < (3+sqrt(5))/2, it's possible to find
m and n such that m/n < x < m/n + 1/(m*n).  To show that (3+sqrt(5))/2 is
in S requires showing that there are no such m and n.  In both cases, the
fractions approximating (3+sqrt(5))/2 were taken from the partials of the
continued fraction expansion of (3+sqrt(5))/2.


> Also, what does the set S look like?  What are its connected components,
> for instance?

That's a good question.  S doesn't have any 'connected components' -- it's
just a set of isolated points.  Suppose otherwise, that all x in some range
(x0,x1) were in S.  Pick any rational m/n in this range.  Then S contains
no points in the range (m/n,m/n + 1/(m*n)) -- but we assumed S contained
(x0,x1), so we have a contradiction.

Thank you a lot. Can you find all the elements of S? (Must be tough).

Mihai.

P.S. For the record, an isolated point of a set (the set defined by the point)
*is* a connected component of that set.

The following is excerpted from .21:


>       2
>(3)	- < sqrt(p)
>	n
>
>which is true in the cases (i) and (ii), the case (iii) supposing m <> 1:
>
>(i)    p = 4 * k  and  k, m, n > 0



For n=1 and k=1, we have p=4, so the statement becomes

	2 < sqrt(4)

which of course isn't exactly right.

Probably doesn't change subsequent discussion, but this is math, right ? So
such inaccuracies are worth mentioning ?

/Eric

    re .29
    
    I didn't check .21 or .29 but, yes, a proof that has a strict inequality
    which should actually include equality as well can doubtless be used to
    prove all sorts of contradictions.