Low maximal pattern complexity of infinite
permutations
Theoretical Computer Science 412 (2011) pp.2911-2921

S. V. Avgustinovich∗, A. Frid∗, T. Kamae†, P. Salimov‡
August 13, 2013

Abstract
An infinite permutation α is a linear ordering of N. We study properties of infinite permutations analogous to those of infinite words andshowing some resemblance and some diﬀerence between permutations
and words. In this paper, we define maximal pattern complexity p∗α (n)for infinite permutations and show that this complexity function is ultimately constant if and only if the permutation is ultimately periodic;
otherwise its maximal pattern complexity is at least n, and the valuep∗α (n) ≡ n is reached on a large family of permutations constructedwith the use of Sturmian words. We also conjecture that there are noother infinite permutations of maximal pattern complexity equal to n.

1

Infinite permutations

Let S be a finite or countable ordered set: we shall consider S equal either
to N, or to some finite subset of N, where N = {0, 1, 2, · · · }. Let AS be
the set of all sequences of pairwise distinct reals defined on S. Define anequivalence relation ∼ on AS as follows: let a, b ∈ AS , where a = {as }s∈Sand b = {bs }s∈S ; then a ∼ b if and only if for all s, r ∈ S the inequalities
as < ar and bs < br hold or do not hold simultaneously. An equivalence classfrom AS / ∼ is called an (S-)permutation. If an S-permutation α is realized
by a sequence of reals a, we denote it by α = a. In particular, a {1, . . . , n}permutation always has a representative with all values in {1, . . . , n}, i. e.,can be identified with a usual permutation from Sn .
In equivalent terms, a permutation can be considered as a linear orderingof S which may diﬀer from the “natural” one. That is, for i, j ∈ S, thenatural order between them corresponds to i < j or i > j, while the ordering∗Sobolev Institute of Mathematics SB RAS Koptyug av., 4, 630090 Novosibirsk, Russia
Satakedai 5-9-6, 565-0855, Japan‡Novosibirsk State University, 2 Pirogova st., 630090 Novosibirsk, Russia†1

we intend to define corresponds to αi < αj or αi > αj . We shall also use
the symbols γij ∈ {<, >} meaning the relations between αi and αj , so that
we by definition have αi γij αj for all i 6= j.
We are interested in properties of infinite permutations analogous tothose of infinite words, for example, periodicity and complexity. A permutation α = {αs }s∈S is called t-periodic if for all i and j such thati, j, i + t, j + t ∈ S we have γij = γi+t,j+t . An N-permutation is called ultimately t-periodic if these equalities hold provided that i, j > n0 for some n0 .
This definition is analogous to that for words: an infinite word w = w1 w2 · · ·on an alphabet Σ is t-periodic if wi = wi+t for all i and is ultimately tperiodic if wi = wi+t for all i ≥ n0 for some n0 .
In the previous paper by Fon-Der-Flaass and Frid [4], all periodic N-permutations have been characterized; in particular, it has been shown that
there exists an infinite number of distinct t-periodic permutations for eacht ≥ 2. For example, for each n the permutation with a representative
sequence−1, 2n − 2, 1, 2n, 3, 2n + 2, . . .
is 2-periodic, and all such permutations are distinct. So, the situation withperiodicity diﬀers from that for words, since the number of distinct t-periodic
words on a finite alphabet of cardinality q is clearly finite (and is equal toq t ).
A set T = {0, m1 , . . . , mk−1 } of cardinality k, where 0 = m0 < m1 <· · · < mk−1 , is called a (k-)window. It is natural to define T -factors of an infinite permutation α as projections of α to T +n, n ∈ N, considered as permutations on T . Such a projection is denoted by αT +n = αn αn+m1 · · · αn+mk−1 .
We call the number of distinct T -factors of α the T -complexity of α and denote it by pα (T ).
In particular, if T = {0, 1, 2, . . . , k − 1}, then T -factors of α are called
just factors of α and are analogous to factors (or subwords) of infinite words.
They are denoted by α[i..i+k) = αi αi+1 · · · αi+k−1 , and their number is called
the factor complexity fα (n) of α. This function is analogous to the subword
complexity fw (n) of infinite words which is equal to the number of diﬀerent
words w[i..i+n) of length n occurring in an infinite word w (see [3] for asurvey). However, not all the properties of these two functions are similar[4]. Consider in particular the following classical lemma.
Theorem 1 An infinite word w is ultimately periodic if and only if fw (n) =C for some constant C and all suﬃciently large n. If w is not ultimatelyperiodic, then fw (n) is strictly growing and fits fw (n) ≥ n + 1.
Only the first statement of Theorem 1 has an analogue for permutations;as for the second one, the situation with permutations is completely diﬀerent.
Theorem 2 [4] Let α be an N-permutation; then fα (n) ≤ C if and only
if α is ultimately periodic. At the same time, for each unbounded growing2

function g(n), there exists a N-permutation α with fα (n) ≤ g(n) for alln ≥ N0 which is not ultimately periodic.
The supporting example of a permutation with low complexity can be defined by the inequalities α2n < α2n+2 < α2n+1 < α2n+3 for all n ≥ 0, andα2nk < α2k+1 < α2nk +2 for some sequence {nk }∞k=0 which grows suﬃcientlyfast.
In this paper we study the properties of another complexity function,
namely, maximal pattern complexityp∗α (n) = max pα (T ).
#T =n

The analogous function p∗w (n) for infinite words was defined in 2002 byKamae and Zamboni [6] where the following statement was proved:
Theorem 3 [6] An infinite word w is not ultimately periodic if and only ifp∗w (n) ≥ 2n for some n.
Infinite words of maximal pattern complexity 2n include rotation words [6]and also some words built by other techniques [7]. The classification of allwords of maximal pattern complexity 2n is an open problem [5].
In this paper, we prove analogous results for infinite permutations andstate a conjecture that in the case of permutations, lowest maximal patterncomplexity is achieved only in the “Sturmian” case.

2Lowest complexity

First of all, we prove a lower bound for the maximal pattern complexity ofa non-periodic infinite permutation.
Theorem 4 An infinite permutation α is not ultimately periodic if and only
if p∗α (n) ≥ n for any n.
Proof. Clearly, if a permutation is ultimately periodic, its maximal patterncomplexity is ultimately constant, and thus the “if” part of the proof isobvious. Now suppose that p∗α (l) < l for some l; we shall prove that α isultimately periodic.
Since p∗α (1) = 1 (there is exactly one permutation of length one), and thefunction p∗ is non-decreasing, we see that p∗α (l) < l implies that p∗α (n + 1) =p∗α (n) for some n ≤ l. Consider an n-window T = (0, m1 , . . . , mn−1 ) suchthat pα (T ) = p∗α (n); the equality p∗α (n + 1) = pα (T ) means that for each
T 0 = (0, m1 , . . . , mn−1 , mn ) with mn > mn−1 we have pα (T ) = p∗α (T 0 ),3that is, each T -permutation which occurs in α can be extended to a T 0 permutation which occurs in α by a unique way. Clearly, there exist twoequal factors of length 2mn−1 in α: say,α[k..k+2mn−1 ) = α[k+t..k+t+2mn−1 ) .
We shall prove that α is ultimately t-periodic, namely, that γij = γi+t,j+t
for all i, j with k ≤ i < j. The proof will use the induction on the pairi, j starting by the pairs i, j with k ≤ i < j < k + 2mn−1 , for which ourstatement holds since α[k..k+2mn−1 ) = α[k+t..k+t+2mn−1 ) .
Now for the induction step: for some M ≥ 2mn−1 , suppose that γij =γi+t,j+t for all k ≤ i < j < k + M , that is, α[k..k+M ) = α[k+t..k+t+M ) . We
are going to prove that γi,k+M = γi+t,k+t+M for all i ∈ {k, . . . , k + M − 1},and thus α[k..k+M +1) = α[k+t..k+t+M +1) .
Indeed, condider the case i ∈ {k, . . . , k + M − mn−1 − 1} first. Then
αT +i is a T -factor of α[k..k+M ) and αT +i+t is a T -factor of α[k+t..k+t+M )standing at the same position. So, these T -factors of α are equal, anddue to the choice of T , so are their extensions αT 0 +i and αT 0 +i+t , where
T 0 = (0, m1 , . . . , mn−1 , M − i). In particular, the first and last elements of
αT 0 +i and αT 0 +i+t are in the same relationship: γi,k+M = γi+t,k+t+M , which
is what we needed.
Now if i ∈ {k + M − mn−1 , . . . , k + M − 1}, we consider αT +i−mn−1
which is a T -factor of α[k..k+M ) with the last element αi , and αT +i+t−mn−1
which is a T -factor of α[k+t..k+t+M ) with the last element αi+t . They areequal, and so are their extensions αT 0 +i−mn−1 and αT 0 +i+t−mn−1 , where
T 0 = (0, m1 , . . . , mn−1 , M − i + mn−1 ). In particular, the next to last
and the last elements of these T -permutations are in the same relationship: γi,k+M = γi+t,k+t+M for all i ∈ {k, . . . , k + M − 1}; together with theinduction hypothesis it means that α[k..k+M +1) = α[k+t..k+t+M +1) . Repeating the induction step we get that γij = γi+t,j+t for all k ≤ i < j, that is,
the permutation α is ultimately t-periodic.
23

Sturmian permutations

A one-side infinite word w = w0 w1 w2 · · · on the alphabet {0, 1} is called
Sturmian if its subword complexity fw (n) is equal to n+1 for all n. Sturmianwords have a number of equivalent definitions [1]; we shall need two of them.
First, Sturmian words are exactly aperiodic balanced words which meansthat for each length n, the number of 1s in factors of w of length n takes
only two successive values. Second, Sturmian words are exactly irrational
mechanical words which means that there exists some irrational σ ∈ (0, 1)
and some ρ ∈ [0, 1) such that for all i we have
wi = bσ(i + 1) + ρc − bσi + ρc or
wi = dσ(i + 1) + ρe − dσi + ρe.
4

These definitions coincide if σi + ρ is never integer; if it is for some (unique)i, the sequences built by these two formulas diﬀer in at most two successive
positions. So, we distinguish lower and upper Sturmian words according to
the choice of b·c or d·e in the definition.
Now let us define a Sturmian permutation α(w, x, y) = α = a associatedwith a Sturmian word w and positive numbers x and y by its representative
sequence a, where a0 is a real number and for all i ≥ 0 we have{ai + x, if wi = 0,
ai+1 =
ai − y, if wi = 1.
Clearly, such a permutation is well-defined if and only if we never havekx 6= ly if k is the number of 0s and l is the number of 1s in some factor ofw; and in particular if x and y are rationally independent.
Note that a factor of w of length n corresponds to a factor of α of lengthn + 1, and the correspondence is one-to-one. So, we have fα (n) = n for alln. In fact, we are going to prove that the maximal pattern complexity of α
is also equal to n, and thus the lower bound in Theorem 4 is precise.
Theorem 5 For each Sturmian permutation α we have p∗α (n) ≡ n.
Proof. Let us start with the situation when x = σ and y = 1 − σ. Thiscase has been proved by M. Makarov in [9], but we give a proof here for thesake of completeness.
If we take a0 = ρ, then by the definition of the Sturmian word, ai = {σi+ρ} holds in the case that w is a lower Sturmian word, and ai = 1−{1−σi−ρ}holds in the case that w is an upper Sturmian word. In what follows, weconsider lower Sturmian words without loss of generality.
Consider a k-window T = {0, m1 , . . . , mk−1 } and the set of T -factors
αT +n = {σn + ρ}, {σ(n + m1 ) + ρ}, . . . , {σ(n + mk−1 ) + ρ} for all n. Since
the set of {σn + ρ}, n ∈ N, is dense in [0, 1], the set of T -factors is equal to
the set of all permutations t, {t + σm1 }, . . . , {t + σmk−1 } with t ∈ [0, 1]
Let us arrange the points {t + σmi } (i = 0, . . . , k − 1) on the unit circle,
that is the interval [0, 1] with the points 0 and 1 identified (recall thatm0 = 0 by definition). Then, the arrangement partitions the unit circle
into k arcs. Since the arrangements for diﬀerent t’s are diﬀerent only byrotations, the permutation defined by the points is determined by the arc
containing the point 0 = 1. Since the number of arcs is k, there are exactly
k diﬀerent permutations defined by the points {t + σmi } (i = 0, . . . , k − 1)with diﬀerent t’s. Thus, pα (T ) = k. Since the window T was chosen to bearbitrary, we have p∗α (k) = k.
Now consider the general case of arbitrary x and y. Let us keep thenotation γij for the relation between α(w, σ, 1 − σ)i and α(w, σ, 1 − σ)j , anddenote the relation between α(w, x, y)i and α(w, x, y)j by δij .
5

Recall that the weight of a binary word is the number of 1’s in it. Notethat by the definition of α, we have δi,i+n = δj,j+n if w[i..i+n) and w[j..j+n)
have the same weight. Note also that the weight of a factor of w of lengthn is either equal to bnσc or to dnσe. So, in α(w, σ, 1 − σ), words w[i..i+n)
and w[j..j+n) of the same length n but of diﬀerent weight always correspondto γi,i+n 6= γj,j+n , since (n − bnσc)σ − bnσc(1 − σ) = nσ − bnσc > 0 and(n − dnσe)σ − dnσe(1 − σ) = nσ − dnσe < 0.
Now let us fix an arbitrary k-window T = {0 = m0 , m1 , . . . , mk−1 } andtwo positions i and j such that α(w, σ, 1 − σ)T +i = α(w, σ, 1 − σ)T +j . Let us
prove that α(w, x, y)T +i = α(w, x, y)T +j . Indeed, for all p, r ∈ {0, . . . , k − 1}with p < r, we have γi+mp ,i+mr = γj+mp ,j+mr . Due to the arguments
above this means that the weight of w[i+mp ..i+mr ) is equal to the weight ofw[j+mp ..j+mr ) , and thus δi+mp ,i+mr = δj+mp ,j+mr . Since a T -permutation
is determined by the relations between pairs of its elements, these equalities for all p and r mean that α(w, x, y)T +i = α(w, x, y)T +j . So, we havepα(w,x,y) (T ) ≤ pα(w,σ,1−σ) (T ) and thus p∗α(w,x,y) (k) ≤ p∗α(w,σ,1−σ) (k) = k; atthe same time, p∗α(w,x,y) (k) ≥ k since this permutation is not ultimately
periodic. So, p∗α(w,x,y) (k) = k, and the theorem is proved.
2.

4Concluding remark

At the moment we conjecture that the described Sturmian permutations are
the only permutations of maximal pattern complexity p∗α (n) = n. We hopeto prove it is a subsequent work.

References[1] J. Berstel, P. Séébold, Sturmian words, in: M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, 2002. P. 40–97.
[2] J. A. Davis, R. C. Entringer, R. L. Graham, and G. J. Simmons, On permutations containing no long arithmetic progressions, Acta Arithmetica
34 (1977), 81-90.
[3] S. Ferenczi, Complexity of sequences and dynamical systems, Discrete
Math. 206 (1999), 145–154.
[4] D. G. Fon-Der-Flaass, A. E. Frid, On periodicity and low complexityof infinite permutations, European Journal of Combinatorics 28 (2007),2106–2114.
[5] T. Kamae, H. Rao, Bo Tan, Yu-M. Xue, Language Structure of Pattern Sturmian Word, Discrete Mathematics, Discrete Mathematics 306(2006), 1651–1668.
6

[6] T. Kamae, L. Zamboni, Sequence entropy and the maximal pattern complexity of infinite words, Ergodic Theory and Dynamical Systems 22(2002), 1191–1199.
[7] T. Kamae, L. Zamboni, Maximal pattern complexity for discrete systems, Ergodic Theory and Dynamical Systems 22 (2002), 1201–1214.
[8] M. Makarov, On permutations generated by infinite binary words,
Siberian Electronic Mathematical Reports 3 (2006) 304–311 [in Russian,English abstract].
[9] M. Makarov, On Sturmian permutations, accepted to Siberian Mathematical Journal [in Russian].
[10] G. Rote, Sequences with subword complexity 2n, Journal of Number
Theory 46 (1993), 196–213.

7