Please see PDF version
Monotone subsequences in the sequence
of fractional parts of multiples of an irrational*)
By David W. Boyd and J. Michael Steele at Vancouver
1. Introduction
Hammersley [7] showed that if X,, X2,... is a sequence of independent identically distributed random variables whose common distribution is continuous, and if 1,', (1j) denotes the length of the longest increasing (decreasing) subsequence of X,, X2 X, then there is a constant c such that c and c in probability, as n oo.
2 2
n n
Kesten [8] showed that in fact there is almost sure convergence. Logan and Shepp [11] proved that c > 2, and recently Vergik"and Kerov [13] have announced that c = 2.
If ot is an irrational then the sequence {oc}, {2 a},. . . of fractional parts of multiples of a is uniformly distributed in the unit interval. Franklin [5] calls such a sequence a "Weyl sequence" and applies various tests to determine its quality as a pseudo random sequence. In this spirit, it is reasonable to investigate 1,', (cc) and l, , (a), the lengths of the longest increasing and decreasing subsequences of {oc},. . ., {na}. We will be particularly interested
in the behaviour of and Q.
n 2 n 2
Some work along these lines was done by del Junco and Steele in [2]. Using discrepancy
log 1,+, i log l, , 1
estimates, they were able to show that and for almost all a, and
log n 2 log n 2
in particular for algebraic irrationals.
Here we shall be able to obtain more precise results by establishing the exact connection between 1,', (1j) and the continued fraction expansion of 0C. We will find piecewise linear functions of n, A' and A whose vertices are explicitly determined by a, which satisfy A + 2 < In' A + and A 2 < l, , < A . The results are precise enough to show, for example,
n n n n
This work was supported in part by grants from the National Research Council of Canada.
0075 4102/79/0306 0005$02.00
Copyright by Walter de Gruyter & Co.
50 Boyd and Steele, Sequence of multiples of an irrational
L
111+ or 1J tends to a limit. In fact n 2 is the correct order of
that there is no ot for which 1 l
n 2 n 2
magnitude of /,+, and l, precisely when Y has bounded partial quotients. For example, if
5 + 1 then
2
1,', 2
lim. inf 1 = 1.337481
n 2 5 4
1+ 1
5 = 1.495349 ...
lim sup "i
2
n
lim inf
This example gives the minimum value attainable for the difference lim sup
2
n n This last result invites comparison with a result of del Junco and Steele concerning the van der Corput sequence, to the effect that
lim inf 2 2
2
n
lim. sup
2 2 n
An interesting contrast to the result for random sequences is that
(1) 1,', (a) l, , (a) ~~ frn, for all a.
l.+ l. 1+ l
.In fact lim. sup = 2 for all ot, and lim. inf " n = 1 if a has unbounded partial
n n
quotients. The lower inequality is essentially the familiar result of Erdbs and Szekeres [4],
but the upper inequality is peculiar to the sequence {n a}. Although it is an easy consequence of
our formulas for A+ and A , a more direct proof would be desirable. Note that, by contrast
n n
+ 4
with (1), for random sequences 1n 4.
The result (1), as well as aspects of the structure of the longest monotone subsequences,
1
5 2 + 1
2, 100,000, using
was suggested by a computation of 1,', and 1n for ot = 2 2 and e for n ~~
the algorithm of Fredman [6]. Only the values of n for which 1n+ > 1~ 1 or l, , > l, , 1 were printed, and these values suggested the connection with continued fractions.
The pattern of the proof is as follows. We first show that 1,', is the solution to a certain integer programming problem. We then define A' n to be the solution of the corresponding linear programming problem, so that obviously A,+ >= 1n+. Since there are only two more constraints than variables, we are able to explicitly find A+, and the structure of the extremurn
n
shows that A' 2 < l.+. Finally, we analyse the asymptotic behaviour of Since obviously
2
n
l, , (a) = 1,+, (1 ot), the results for l, , follow automatically.
Boyd and Steele, Sequence of multiples qf an irrational
2. One sided diophantine approximation
51
If a is an irrational, we will denote its continued fraction expansion by a ~ [aO; (11 ~ 612,...], so that if a = a. + ao with ao = [a], ao = {oc}, then for n = 1, 2....
a,=[ and an =
7n 1 1 { ani 1 1
If we write Pn = [ao; a,,. a.] for the principal convergents, then [10], pp. 1 8,
qn
(2)
1
OC. i
(3) q.oc pn 1)n (qn+l + an+, qn) 1, q_ 1 = 0, qO
(4) qn+l=a,,+lqn+qn l,forn=0,1,... .
We shall write an= lqna Pni, so that an = 1 lqnal 1 for n > 1, where, as usual,
11 x 11 = min Qx}, 1 {x}). Then (2), (3) and (4) imply
(5)
(6)
an = (qn+ 1 + an+ 1 qn) 1,
Un+l=an+lo~n3 n=051'.
We define the intermediate convergents P`k by
(7)
(8)
'1n,k
Pn,k =kPn+l+Pn5 0
qn,k=kqn+l+qng 0
Note that qn,0 = q, and q.,.,,, = qn + 2. Defining Un,k = J qn,ka Pn,k 1, (3) and (6) imply that
(9) Un,k=Un kun+l, for 0:!s~k::s~an+2.
The sequence qn is characterized by the following well known result:
Lemma 1. For n ~t 2, q,, is the smallest integer q > q,, such that qa < q,, a
Proof. See [10], p. 10 or [1], p. 2.
We define {q+} to be the sequence of even ordered denominators q2, and q2,,k n
(1 :f ~ k:!~ a2,n 12 1) arranged in increasing order qO < qo,l < ... n
the corresponding sequence of odd ordered denominators. The following is an analogue of Lemma 1 which we have been unable to find explicitly stated in the standard literature:
Lemma 2. (i) For n ~~ 1, q+ is the smallest integer q > q+ 1 such that {qa} < {q+ 1 a}.
n n n
(ii) For n ~t 1, q is the smallest integer q > q 1 such that {qj 1 a} < {qoc}.
n n n
Proof. By (9), {q+ a} forms a decreasing sequence. Let q satisfy q > q+ 1 = q2,n, and
n n k
{qa} < {q+ 1 a}. Write q = qn + r. Then, in order for {q+ 1 a + ra} < {q+ 1 oc}, we must have
n n n
(10) {q(x} {q+ la} + {ra} 1 = {q+ 1(x} lirall.
n n
Thus ilroc~i < {q+_1a} = {q2.,ka} < {q2.0C} = liq2.OCII. By Lemma 1, this means that r> q2,n+l
so that q> q2m,k+ q2,+1 =q2,,k+l = qn+.
1
1
52 Boyd and Steele, Sequence of'niultiples of an irrational
To prove (ii), apply (i) to 1 oc.
Remark. The q,' are the denominators in the semi regular continued fraction
+1 1 1 * * ' 2 for all n ~~i 1.
defined by oc = bo bl b2 b3 , with b,,
The easiest way to see this is to show that these denominators satisfy Lemma 2.
It also follows from a result of Tietze [12], p. 163.
3. An integer programming problem
It is clear that lJ, (a) = l,' (1 oc) so we will limit ourselves in this section to l.+
Lemma 3. Let Y and n be fixed. Let q+ be defined as in the previous section, and let
m
M sati~ft qM' =< n < q+ Then 1,+ (a) is the solution to the following:
m
m
(11) 1n+ = max Y, r.,
m=l
where the ri are integers for which
m
(12a) rmq+ < n,
M
m=l
m
(12b) r. {q+ a} < 1,
m
m=l
(12c) r, ~~: 0,. . ., rm > 0.
Proof. Suppose 0 < {nl a} < . . < {n, a} < 1 is an increasing sequence of length 1 with
1:!~ nj < ... < n,:~ n. If we write d, = nj, dk = nk nk 1 for k = 2,. . ., 1, then we obtain
{dkcc} = {nkoC} {nk 1 a}, and we have
1 1
(13) Y {dkoc}:~ 1 and Y_ dk:~ n.
k=l k=l
By definition, 1n+ is the maximum value of 1 under these constraints.
We claim that, in (13), it is no restriction to choose dk from among the q+. For, if
m
q + < dk < q++,, then {dkoc} > {q+a}, byLemma 2, so if dkisreplacedbyq+, both inequalities
m m m m
in (13) continue to hold. But then, collecting terms in qm' and {qm' OC}, (13) reduces to (12).
4. A linear programming problem
Let A' (a) denote the solution to the problem defined by (11) and (12), where rm and n
n
are no longer required to be integers. Define A (oc) = A' (1 ot). Then obviously A+ > ln'
n n =
and An ~: 1J. Now that real coefficients are to be allowed, we find that the intermediate denominators q2m,k which appear in q are no longer needed:
Lemma 4. Let K satisfy q2K:: :~ n < q2K+ 2. Then
K
A' = max
n 1, Xk,
k=l
Boyd and Steele, Sequence of'multiples of an irrational 53
where (xl XK) satisfies
K
(14a) Xk q2k n,
K
(14b) 1 X072k 1
k=l
(14c) X, o'. XK > 0.
Proof. By(8)and(9), q2.,k (1c) q2m + cq2,,,+ 2 andU2m,k = (1 C) U2. + C(T2m + 2
where c= k . Thus, in (12a), we may replace any q,t of the form q2,,,k by a convex
a2m+2
combination of q2,n and q2m+2, and in (12b), replace {q2m,koc}=U2m,k by the same combination of 92 and G2m+21 without affecting the inequalities.
Theorem 1. Define P (1 {oc}) ` and fl q a m ', m = 0, 1'. . . . Then, for any given
oc, A+ and A are the following piecewise linear functions of n:
n n
(15) q2k + 1 + na2k + 1 , if fi2k ~~ n < fi2k + 2 ~ k = 09 1 y 5
n {n, if 0:~ n < PO,
(16) An q2k + nU2k, if 132k 1 :5 n < fl2k+l 5 k = 0,11 1
{n, if 0
Proof. We begin with (15). The constraint region (14) has K+ 2) possible vertices. ( K Apart from (0,. . ., 0), either K 1 or K 2 of the Xk must be 0. If all x& but xi are 0, which we call a vertex of type I, then (14a), (14b) give
(17) x, = min (a2i', nq2i').
If all Xk but xi and xj are zero, called a vertex of type 11, then xi, xj must solve the equations
(18a) Xi% + XjU2j = 1
(18b) x,q2i + xq2j = n
so that
(19a) xi = % 1 P2i n
P2i P2i'
n P2i
(19b) Xj = U2i fi2J P2i'
Assuming i0 is seen to be
2 i 2i
P2 i:!~ n:~, P2P Among the vertices of types 1 and 11, we seek to maximize A X1 + + XK. Let us denote the right member of (17) by fi (n) and by gi,j (n) the value of A= xi + xj given by (19). Then
(20) A+ = max (m~x fi (n), Tax gi,j (n)),
& E'.1
where the maximum over i,j is restricted to those which satisfy P2 i:!~ n.5 fl2j
Journal ffir Mathernatilc, Band 306 8
54 Boyd and Steele, Sequence of multiples of an irrational
Define vi to be the point 02i, a2i'), i = 0,1,. and v (0,0). Then the graph offi(n) is the line segment v 1 vi followed by the horizontal line from vi to 00. The graph of gi,j (n) is the line segment from vi to vj. Let us denote the right member of (15) byf (n). Then, in fact, the graph of f (n) is the polygonal line v 1 vo v, . To see this, observe that
M2k) = q2k+1 + PW72k+1 = q2k+1 + q2kC2k 1 U2k+1 q2k+1 + q2ky 2k+1 = '72k' , by (5) and (6).
Also M2k+ 2 q2k+ 1 + 16+ 2G2k+ 1 = U2 k 1 1 2, by a similar calculation. The function f is
thus continuous, increasing and concave, since the slope U2k + 1 decreases with k. Thus, the
graphs of fi (n) and gi,j (n) lie strictly below the graph of f (n), except for fo (n) and gi,i + 1 (n),
i = 0, 1,. . . which coincide with f (n) on the intervals [0, PO], [P2 i, fi2 i + 2] respectively.
This shows that A+ =f (n).
To prove (16), one uses A (a)A+ (1 oo. The two cases oc > 1 and oc < 1 need to be
n n 2 2
distinguished. If a > note that P P,.
2
Corollary 1. For all oc, A + 2 < ln' < A + and A 2 < In A
n n n n
Proof. Clearly A+ > 1n+. On the other hand, by the proof of Theorem 1, if (xl,. . ., X0
n =
satisfies (14) and has A+ = X1 + "' + XK, then (Xl, XK) need only have two non zero
n
components. Thus
K K
ln
+ [Xk] >
1 Y_ Xk 2=A+ 2.
k=l U1
The proof for An follows by the standard symmetry.
5. The asymptotic behaviour of I.+ and I, ,
Theorem 2. The sequence ~n oscillates between local maxima ofsize attained
1
n 2 (q2kU2 j2
1
at n and local minima of size 2 (q2k + 1 U2k + 1) 2 attained at n P2k + 1. In a self explanatory
notation,
A +
n
(21 a) loc max
n 2 (q2kU2 j2
2
(21 b) loc min 2(q2k+1U2k+l)
2 n
In the same notation,
(22 a) loc max
n 2 (q2k+1a2k+l) 7
1
(2.2b) loc min 2(q2ka2k )2.
n
Boyd and Steele, Sequence of multiples of an irrational 55
Proof. By (15), if fl2k:~n:~5P2k+2 we have
A+
2 2
=q2k+ln + (72k+l n
2 n
which, as a function of n, decreases to a minimum of 2(q2k+1a2k+ 1)2 at n=fi2k+l, and attains a local maximum at n = P2k equal to
1 1 1 1 1 1
2 2 2 2 2 2
q2k+1q2k a2k+72k+1q2ka2k = O"2A2k (q2k+l+(X2k+,q2k)= 1
(q2k92k )2
using (5) and (6). This proves (21), and (22) follows as usual.
Corollary 2. Let A = lim. inf q2kU2k and B = lim inf q2k+ 1 U2k+ 1. Then
1+ 1 1+ 1
2 2
lim sup A lim inf " L =2B
2
n n
l, , 1 l
2 2
lim sup B litn inf ", =2A
n 2 n 2
Proof. A direct consequence of (21) and (22).
Remarks. The quantity qkUk=qkilqkall appears naturally in the theory of rational approximation, as does the quantity v(a) = lim inf qkI iqkOCI 1 [1], p. 11. The set of values v (a) is called the Lagrange spectrum. By a theorem of Hurwitz, the largest value of v (0c) is
1
5 2 . The proof of Corollary 4, below, is modelled on Davenport's proof of the theorem of Hurwitz, as given in [1 ], p. 11.
aa'+ b
Two real numbers a, a' are said to be equivalent if a = ca'+ d , where a, b, c, d are
integers with ad b c = + 1. A necessary and sufficient condition for a and oc' to be equivalent is that their continued fraction expansions can be shifted so as to coincide beyond some point [1], p. 9.
Using (5), we have the following convenient representation:
(23) (qkUk) 1=ak+1+0Ck+l+ qk 1 = [ak+l; ak+ 2,. + [0; ak, ak 1 aj.
qk
1
Thus, for example, if a =,r = 5 2+1 1,. . . ], then
2
2 2
D; 1, t. 1 + EO; 1, 11 + + 5 2
(qkak) 2 2
in 1+ l
Thus firn sup lim sup 5~'= 1.495349 while lim inf Iiin inf 1.337481
n 2 n 2 n 2 n 2
56 Boyd and Steele, Sequence of multiples of an irrational
This is an extreme example as the following shows:
111+ 4+
Corollary 3. Let a = lim sup 1 and b = lim inf 1 . Then 0 < b and a < oo if and only if
nf J
{an} is a bounded sequence. There is no a for which a b, and in fact the minimum values of
1 1
a 5 2 2 5 2 + 1
and a b are and 54 attained only for a and numbers equivalent to it.
b 2 1 2
5 4
Proof. The first statement is obvious since, by (23)
(24) ak+l <(qkak) 1< ak+l+2.
To prove the second statement, let Ak = qkak. Then the following inequality may be derived from (2), (4) and (5), [1], p. 12:
2 2
(25) a., 1 Ak+2AMk 1 +Ak+,) < 1.
Suppose that an infinite set of a. satisfy a 2. To be specific, consider the case where
a2k> 2 for an infinite set of k. Then (25) implies, for these k, that
42
A2k l+2A2k l(A2k 2+ A2k) < 1
and
A2 2k+2A2k(A2k+l+ A2k 1) < 1.
Thus
(26) 4 B 2 + 4AB < 1,
(27) A 2 + 4AB < 1.
We may rewrite (26) and (27) as
(28) B < (4AB) 1 1,
A =
(29) A < (4AB) 1 1.
4B=
Taking the geometric mean of (28) and (29), we find that (4 A B) 1 > so (4AB)
2
1 1
a 2 ~3~7 5 1
t inite which implies tha W =(4AB) > ~2 ) > 2 A similar proof applies if an infi number of a2,k+l are > 2. Thus, only if all but a finite number of a are equal to 1 we will have
1
a 51
= ' and this is in fact attained by such a as we saw above. b 2
Boyd and Steele, Sequence of multiples of an irrational 57
Furthermore a _~ 1 for all a. So, if a is not equivalent to c then
2 2
_)') + (( 2 _(2
a b=a )' a b ~ a 2 2 )12 1835 ,
3 3 3 3
while for numbers equivalent to T, we have
2
a b = 5 4 1578 .
5
+ A
An 21 2
Example. We see from (21), (22) and (24) that loc max 1 ~ a2 k + 1 and loc max a2k
2 2
n n
so the upper extremes of In 1 are governed by the partial quotients of odd order, while
2
n
those of are governed by the partial quotients of even order. The following is thus an
2
n instructive example:
oc = tan (2 [0; 1, 1, 4, 1, 8, 1, 12, 1, 16,. . .
with a2k~l and a2k+l=4k if k~1. This is obtained from Lambert's expansion of
tan ~ 1 ~ in a semi regular continued fraction [12], p. 353 by the use ot i_ ~range's ~2 ) transformation [12], p. 159. Using (23), we have A = 0, B= 1 so that
1+ 1+
lim sup " = oo, lim inf "i = 2,
n 2 n 2
4 4
lim sup i = 1 , lim inf 1 = o.
n 2 n 2
In fact, one can be more precise about By making the obvious estimates in
2
n
q2k+1=4kq2k+q2k 1, q2k=q2k l+q2k 2,
one has 4 k k! < q2k+l < 8 k (k + 1)!, so q2k + 2 =_ q2k + 1 =_ (ck)k (compare the discussion for e given in [10], p. 78). If P2k:~ n < fl2k+ 2, then
q2k(q2k+l+OC2k+,q2k):~n
log n so n ~ (c k)' and hence k = log log n Hence
1 ( log n
)2 =
loc max =(4k _log _log n
58 Boyd and Steele, Sequence qf multiples of'an irrational
The metric theory of continued fractions gives us similarly precise information for almost all oc. The following result is sufficient for our purposes:
Lemma 5 (E. Borel and F. Bernstein [9], p. 63). Let 0 (k) be an increasingfunction ofk.
110
If )7, 0 (k) oo then for almost all a, ak k 0 (k) fir infinitely many k. On the other hand, if
k=l
.0
1 0 (k) ' < cc, then for almost all a, ak:~ 0 (k) except for a finite set Qf k. k=l
Corollary 4.` Let /;, denote either /,', or Ij. For almost all oc, and any e > 0, there are constants C> 0 and D < oo so that for all n,
(30) Cn 2 (log n) 2 < lj' Dn 2 (log n)
On the other hand
2
lJ+ :~ Cn (log n) 2 and lJ+ ~: Dn 2 (log n)
holdfor infinitely many n.
Proof. For almost all oc, qk ~ C' for a universal constant c [9], p. 66. Thus P2k:~ n
+ 2' and thus,
implies that n > clk so k < C2 log n. By Lemma 5, for almost all a, a,: !~ C3 k' by (21 a) and (24),
7
2 i1,+. n =
The remainder of the proof is similar.
1
Remark. Of course (log n) 1+2 can be replaced by 0 (log n) for any increasing 0 for which 3~', 0 (k) 2 < 00 .
Corollary 5. For all ot, n..5 1,+, 1n :~ 2 n, and lim sup 2. If oc has unboundedpartial
n
+ 1.
quotients, then lim inf ln n = 1. For all a,
(31) lim inf 2 = 1.894427 ,
n 5 2
which is attained only for ot = 5 2+1 and equivalent numbers.
2
Proof. The fact that 1,+, Ij, n is a result of ErMs and Szekeres [4]. By Theorem 1,
if n. 5 then
A+ A =g(n) = (q. + na,) (q,+, + na.+,).
n n
By (5) and (6), g (p.) = 2 fl. and g (p. + 1) = 2 P. + 1. Thus g (n) 2 n is quadratic in n and
vanishes at n + 1 and hence satisfies g (n) < 2 n for P. < n < P,, + Hence
1,+, 1n n n
C, ln A+ An
Since A+ A = 2 n for n it follows that lim sup lim sup n 2.
n n n n
Boyd and Steele, Sequence of multiples of an irrational 59
g (n) 1
On the other hand has a minimum at n = (fini fini ' J 2 Using q,,1am + qnl~7m+1 1, n we have
A,+ 2
1
loc min n 1 +2(A Am+l)
where A qmu,,,. Thus
',+, In 2
1
(32) lim inf 1 + litn inf 2 (A. Am + 1)
which is 1 if {a,,,} is unbounded. Let c,,, = Am Am + 1. Then (25) becomes
2 2
(33) am + 1 AM < 1 2 cm 1 2 c,,,.
Thus
2 2 2 2cm 2cm)(1 2c. 2cm+,).
(34) am+, am+2CM < (1
Let c = lim. inf c., which is clearly at most by (3 3). If am ~~ 2 for infinitely many m, then
4
+ 1.
(34) shows that 4 c2 <= (1 4 ffl, SO C:~ 1 . Thus lim inf 1n < 1 + 2 < 1 + 2 ' from
6 n 6 2 5 2
(32). It is easy to check that equality holds in (31) for any a equivalent to r.
Added in proof. With respect to Lemma 2 we remark that J. L. Nicolas states that
result without proof in: R6partition Modulo 1, Lecture notes in Mathematics 475, New
York 1975, p. 115.
References
[1] J. W. S. Cassels, An Introduction to Diophantine Approximation, Cambridge Tracts in Mathematics and Mathematical Physics 45, London 1957.
12] A. del Junco and J. M. Steele, Growth rates for monotone subsequences, Proc. Amer. Math. Soc. (to appear).
[3] A. del Junco, Hammersley's law for the van der Corput sequence: an instance of probability theory for pseudo random sequences, Ann. of Prob. (to appear).
[4] P. Erdbs and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463 470.
[5] J. N. Franklin, Deterministic simulation of random processes, Math. Comp. 17 (1963), 28 59.
[6] M. L. Fredman, On computing the length of longest increasing sub*sequences, Discrete Math. 11 (1975),
~ 29 35.
[7] J. M. Hammersley, A few seedlings of research, Proc. Sixth Berkeley Symp. Math. Stat. and Prob. 1 (1972), 345 394.
[8] H. Kesten, Comment to "Subadditive ergodic theory" by J. F. C. Kingman, Arm. of Prob. 1 (1973), 903.
[9] A. Khinchin, Continued fractions, Chicago 1964.
[10] S. Lang, Introduction to Diophantine Approximations, Reading 1966.
[11] B. F. Logan and L. A. Shepp, A variational problem for random Young tableaux, Advances in Math. 26 (1977), 206 222.
[12] 0. Perron, Die Lehre von den Kettenbrilchen, Stuttgart 1954.
13] A. M. Vergik and S. V. Kerov, Asymptoties of the Plancherel measure of the symmetric group and the limiting form of Young tables, Soviet Math. Dokl. 18 (1977), 527 531.
Department of Mathematics, The University of British Columbia, Vancouver, Canada V6T 1W5
Eingegangen 6. April 1978