Please see PDF version
J
P,,zl, f,
GRO~ RATES FOR MONOTONE SUBSEQUENCES'
A. DEL YUNCO AND J. MICHAEL STEELE
ABSTRACT. The growth rate of the largest monotone subsequence of a uniformly distributed sequence is obtained. For a. = na mod 1 with a algebraic irrational the exponent of growth is found to be precisely the same as for a random sequence.
1. Introduction. A well known result of Erdds and Szekeres [11 states that any sequence of n real numbers contains a monotone subsequence with at least n 1/2 elements. More recently, Haminersley [21 proved that if 1, = 1,,(al, a2, . . , an) 'S the order of the largest increasing subsequence of a,, a21 ... a., and the a, are chosen independently with the uniform distribution on [0, 11, then
lim n 1/21, = C,
n~m
where C denotes a constant and the convergence is in probability. This result was strengthened by Kesten [4] to provide almost sure convergence, and Logan and Shepp [61 proved that C > 2. Our objective here is to provide results like (1) for sequences which are uniformly distributed in [0, 11, but which are not random. Of particular interest to us is the sequence a,
na mod 1 where a is an algebraic irrational.
2. Uniformly distributed sequences. We will denote by l[,,b)(x) the indicator function of the interval [a, b) and will say a sequence (an) is uniformly distributed in [0, 11 provided for all 0 ~~ a < b Q 1,
n
lim n` lla,b).(ai) = b a.
n~oa
The best one can say about the growth rate of 1,, for a general uniformly distributed sequence is the following:
THEOREm 1. If (aJ is uniformly disiributed, then
lim n 11n = 0. (2)
n~oo
PROOF. Let A and n be positive integer's and for 0 Q i ~ A 1 and
Received by the editors July 25, 1977 and, in revised form, September 16, 1977.
AMS (MOS) subject classifications (1970), Primary 10K05, 10K30.
Key words and phrases. Monotone subsequence, uniform distribution, algebraic irrationals discrepancy.
'Supported by Contract #67 8473.
179
180 A. DEL TUNCO AND J. M. STEELE
0 < j < A 1 let
S~i k: 1 < k < n, iA ak < (i + I)A
jnA ` + 1 < k < (j + 1)nA
By IS,,l we denote the cardinality of Sij and we set g(n) = maxillSiji. If n tends to infinity along the subsequence n = ^yA, ^y = 1, 2, . . . , then g(n)ln is easily seen to converge to A ` by the uniform distribution of (a,,).
Next let S {il < i2 < . . . < i,} be any subsequence of 1, 2.... , n
such that a,, <, % <, . . <, ai,. We note that S intersects at most 2A 1 of
the Sj. (One can identify a,, a2, . . . , a, with its graph in { 1, 2, . . . , n} X
[0, 11 and view the Sij as "boxes.") This observation yields the inequality
ISI <, 2Ag(n), and since 4 <, ISI we have Sm,,_,Jjn <, 21A provided the
limit is taken along the subsequence n = kA.
For kA < n < (k + I)A we note that
1(al, a2,. . . , a,,) < 1(al, a2, aAk) + l(aAk+h a,,)
1(ai, a2, aAk) + A.
This proves
117 m (lkA + A) 2
n *oo n k >oo leA . A
which completes the proof of (1), since A was an arbitrary positive integer.
3. Restilts concerning (na). To show that 1,, o(n) is best possible we do
not have to go out of the class of sequences a,, na mod 1.
THEoREm 2. Let Cn be a sequence of real numbers ' such that C,, > 0 as
n > oc; then there is a transcendental a such that for a,, = na mod 1 we have
n 11n > C,, for infinitely many n. (3)
PROOF. The proof depends on an elementary lower estimate for 1,, in terms
of the denominators qk of the convergents pkIqk of a. First we assume
n= qk,i and that fqka} >O, where {x} x [x+ 1]. Forj= Sqk the
2
sequence ja with S =.1, 2, . . ., [qk,lIqk] can be viewed as making small positive steps, so we have the lower bound
1
n > min(l/ {qka}, qk,lIqk). (4)
By the standard theory pf,continued fractions (e.g., [3, p. 9]) we have 1{aqkll}l < lIqk11, So (4)implies 1. > qk+11qk. Since C,, >Owe can choose qk which go to infinity as rapidly as we like such that 1 / qk > C, for t = qk , 1. In particular, we may require qk to grow rapidly enough to insure that a is transcendental. Finally, we note that if the condition {qka} > 0 is not met by infinitely many k, we need only replace a by 1 a. This will then complete the proof.
There is a more precise result which can be proved if a is algebraic. To state it succinctly, we let 1,,' denote the order of the largest monotone
i
1
MONOTONE SUBSEQUENCES 181
(increasing or decreasing) subsequence of a,, a2.... 1 aw
THEOREM 3. If a,, = na mod 1 where a is an algebraic irrational, then
lim (log 1,J/ (log n) = 1/2. (5)
PROOF. We must obtain quantitative versions of the estimates used in Theorem 1. To begin, for 0 <, i ~<, n 1 and 0 < j n 1 we let
Sy = {a,,: iln < ak < (i + 1)1n,jn + 1 k < (j + 1)n} and observe that
m~X ISJ < max {1 + 2nDj (6)
1,1 0 ~j< n 1 where
(j+ 1)n
DJ = sup n 1[0,)1(a
n k) X
0
Also, if S = {ai,, a '2' . . . , ai,} is any monotone subsequence of
(a,, a21 aA, we know S intersects at most 2n 1 of the S#. Thus, we
have
n <, In'2 < 2n max ISUI, (7)
1,1
where the first inequality follows from the ErMs Szekeres theorem mentioned in the introduction.
Since the sets {(jn + 1)a, (jn + 2)a, . . . , (j + 1)na}j = 0, 1, . . . , n 1, are translates of (a, 2 a, . . . , na}, we have
max lYn' = 0 (D,,' (8)
OQjQn 1
By the Thue Siegel Roth theorem [5, pp. 122 124] we know that Dn = Dn'
0 (n for all e > 0. This fact, with (7) and (8), yields
lim (log 1,,2) / (log n) = 1. (9)
n~00
For the final step choose n so that n 2 < j < (n + 1)2 and note In'2 < lj' < 1n2 + 2n. By the bounds onj and the limit in (9), one completes the proof with a brief computation.
There are two corollaries of the proof of Theorem 3.
COROLLARY. 1. If a is an irrational for which D,, = 0 (n '+') for all c > 0, then (5) holds. In particular, this is the case if a is of finite type 1.
COROLLARY 2. For all a except a set of measure 0, one has (5).
The proof of Corollary 2 depends only on the fact that D,, = 0 (n for all e > 0 and almost every a. (For more precise results on D, see Niederreiter [71).
ACKNOWLEDGEMENT. We wish to thank Professors H. Kesten and H. Niederreiter for their comments on an earlier draft of this paper.
182 A. DEL JUNCO AND J. M. STEELE
REFERENCES
1. P. Erd~s and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463 470.
2. J. M. Hammersley, A few seedlings of research, Proc. Sixth Berkeley Sympos. Math. Statist. and Probability, Univ. of California Press, Berkeley, Calif., 1972.
3. A. Ya. Khinchin, Confinuedfractions, Univ. of Chicago, Chicago, Ill., 1964.
4. H. Kesten, Comment to "Subadditive ergodic theory" by J. F. C. Kingman, Ann. Probability 1 (1973), 903.
5. L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Wiley, Toronto, 1974.
6. B. F. Logan and L. A. Shepp, A variational problem for random Young tableaux, Advances in Math. 26 (1977), 206 222.
7. H. Niederreiter, Metric theorems on the distributions of sequences, Proc. Sympos. Pure Math., vol. 24, Arner. Math. Soc., Providence, R. L, 1973, pp. 195 212.
DEPARTMENT OF MATHEMATICS, 0mo STATE UNIVERsiTY, CoLumBus, Owo 43210
DEPARTMENT OF MATHEMATICS, UNIVERSITY OF BRITISH COLUMBIA, VANCOUVER V6T W5, B. C., CANADA
1