Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site lanl.ARPA
Path: utzoo!linus!philabs!cmcl2!lanl!ttw
From: ttw@lanl.ARPA
Newsgroups: net.math
Subject: Re: Sequence of Irrational Numbers
Message-ID: <26100@lanl.ARPA>
Date: Mon, 20-May-85 12:24:54 EDT
Article-I.D.: lanl.26100
Posted: Mon May 20 12:24:54 1985
Date-Received: Tue, 21-May-85 04:43:37 EDT
References: <229@ihnet.UUCP>
Sender: newsreader@lanl.ARPA
Distribution: net
Organization: Los Alamos National Laboratory
Lines: 64

> <>
> 	Consider a sequence of real numbers between 0 and 1,
> defined recursively:  A[i] = A[i-1]+X mod 1;  A[0] = 0.
> In other words, each term is the fractional part of the sum
> of the previous term and a constant (X).
> For example, when X = pi, the sequence begins:
> 0.0, 0.14159, 0.28318, 0.42477, 0.56637, 0.70796,
> 0.84955, 0.99114, 0.13274, 0.27433 ...
> When X is rational (P/Q), the sequence is periodic, cycling every Q terms.
> The sequence is more interesting when X is irrational (as above).
> Each value occurs only once.  To show this, assume A[i] and A[i+k] are equal.
> This implies k*X = l (k and l integers).  Since k is not 0,
> X must be l/k (rational), contradicting the assumption.
> Does every real [0-1) appear in the sequence?
> Clearly not.  You cannot map a countable set onto a continuum of values.
> Note that A[] contains no rationals, except A[0] = 0.
> 
> 	Now for your homework assignment.
> Given irrational X, and the sequence A[] described above.
> 1.  Prove, for every Y between 0 and 1, and for every epsilon > 0,
> there exists A[i], such that Y-epsilon < A[i] < Y+epsilon.
> In other words, arbitrarily small intervals always contain values from this 
> sequence.
> 2.  If your proof is not constructive, design an algorithm for finding
> a specific A[i] satisfying Y-epsilon < A[i] < Y+epsilon.
> Example: find an A[i] between 0.499999999 and 0.500000001 (X = pi).
> I want a time-bounded algorithm; stepping through the sequence
> looking for a value that lies within the interval doesn't count.
> 3.  Design an algorithm to determine whether a given value (y)
> is in the sequence A[i].
> Example: is sqrt(2)-1 in A[] (X = pi).
> 4.  Find an algorithm implementing the inverse function.
> Given a Y in A[i], find the index.
> Example: what is the inverse of 10*pi-31 (X = pi).
> Again, time-bounded, not waltzing through A[]
> looking for Y.
> 
> 	I don't know the answers to any of these questions.
> I feel part 1 is true, and provable, and I will work on it.
> I am rather pessimistic about 2, 3, and 4.
> Any thoughts?
> -- 
> 
> Karl Dahlke    ihnp4!ihnet!eklhad

      The answer to your question 1 is "yes."  The fractional parts of the
multiples of an irrational number are dense. References are
 
John H. Halton,"The distribution of the sequence {n 'XI'} (n=0,1,2,...)"
,Proc. Camb. Phil. Soc. 61,(1965),665-670.
 
L. Kuipers and H. Niederreiter, "Uniform Distribution of Sequences," Wiley,
New York, 1974.
 
J. Schoiszengeier, "On the discrepancy of (n 'alpha')," Acta. Arith.,44,
(1984),241-279.
 
     I think that the answer to 2, 3, and 4 can be obtained from the
continued fraction structure of the irrational. As only rational operations
are performed it would seem that two irrationals could not appear unless
one had a linear rational relation to the other. Thus sqrt(2) and its
relatives would not appear in the sequence generated by pi.
     For more information, see Cassels book on diophantine approximation
(I forgot the title.)