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 pseudorandom 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.

00754102/79/03060005$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. Onesided 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 =

7n1 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+qnl,forn=0,1,... .

We shall write an= lqnaPni, 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=Unkun+l, for 0:!s~k::s~an+2.

The sequence qn is characterized by the following wellknown 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 evenordered 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 oddordered 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 semiregular 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 132k1 :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 P2in

P2i P2i'

nP2i

(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 + q2ky2k+1 = '72k' , by (5) and (6).

Also M2k+ 2 q2k+ 1 + 16+ 2G2k+ 1 = U2k 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 nonzero

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, ak1 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+2AMk1 +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

A2kl+2A2kl(A2k2+ A2k) < 1

and

A2 2k+2A2k(A2k+l+ A2k1) < 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 51

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

ab=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 semiregular 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+q2k1, q2k=q2kl+q2k2,

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 2cm2cm)(12c.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 pseudorandom sequences, Ann. of Prob. (to appear).

[4] P. Erdbs and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463470.

[5] J. N. Franklin, Deterministic simulation of random processes, Math. Comp. 17 (1963), 2859.

[6] M. L. Fredman, On computing the length of longest increasing sub*sequences, Discrete Math. 11 (1975),

~ 2935.

[7] J. M. Hammersley, A few seedlings of research, Proc. Sixth Berkeley Symp. Math. Stat. and Prob. 1 (1972), 345394.

[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), 206222.

[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), 527531.

Department of Mathematics, The University of British Columbia, Vancouver, Canada V6T 1W5

Eingegangen 6. April 1978