Sturmian Words and the Permutation that Orders Fractional Parts

Kevin O’Bryant University of California, San Diego kobryant@math.ucsd.edu http://www.math.ucsd.edu/∼kobryant

November 12, 2002

Abstract A Sturmian word is a map W : ℕ → {0, 1} for which the set of {0, 1}-vectors F_{n}(W) := {(W (i), W (i + 1), …, W (i + n − 1))^{T} : i ∈ ℕ} has cardinality exactly n + 1 for each positive integer n. Our main result is that the volume of the simplex whose n + 1 vertices are the n + 1 points in F_{n}(W) does not depend on W. Our proof of this motivates studying algebraic properties of the permutation π_{α,n} (where α is any irrational and n is any positive integer) that orders the fractional parts {α}, {2α}, …, {nα}, i.e., 0 < {π_{α,n}(1)α} < {π_{α,n}(2)α} < ⋯ < {π_{α,n}(n)α} < 1. We give a formula for the sign of π_{α,n}, and prove that for every irrational α there are infinitely many n such that the order of π_{α,n} (as an element of the symmetric group S_{n}) is less than n.

1 Introduction

A binary word is a map from the nonnegative integers into {0, 1}. The factors of W are the column vectors (W (i), W (i + 1), …, W (i + n − 1))^{T}, where i ≥ 0 and n ≥ 1. In particular, the set of factors of length n of a binary word W is defined by

F_{n}(W) := {(W (i), W (i + 1), …, W (i + n − 1))^{T} : i ≥ 0} .

Obviously, |F_{n}(W)| ≤ 2^{n} for any binary word W. It is known [Lot02, Theorem 1.3.13] that if |F_{n}(W)| < n+1 for any n, then W is eventually periodic. If |F_{n}(W)| = n + 1 for every n—the most simple non-periodic case—then W is called a Sturmian word. Sturmian words arise in many fields, including computer graphics, game theory, signal analysis, diophantine approximation, automata, and quasi-crystallography. The new book of Lothaire [Lot02] provides an excellent introduction to combinatorics on words; the second chapter is devoted to Sturmian words.

Throughout this paper, W is always a Sturmian word, n is always a positive integer, and α is always an irrational between 0 and 1. A typical example of a Sturmian word is given by c_{α}(i) := ⌊(i + 2)α⌋−⌊(i + 1)α⌋, the so-called characteristic word with slope α. By routine manipulation, one finds that c_{α}(i) = 1 if and only if i + 1 ∈ {⌊kα⌋ : k ∈ ℤ^{+}}. The integer sequences (⌊kα + β⌋)_{k=1}^{∞} are called Beatty sequences. The study of Beatty sequences is intimately related to the study of Sturmian words, and the interested reader can locate most of the literature through the bibliographies of [Sto76], [Bro93], and [Tij00].

In this paper, we consider the n + 1 factors in F_{n}(W) to be the vertices of a simplex in ℝ^{n}. Our main result is

Theorem 1.1. If W is a Sturmian word, then the volume of the simplex F_{n}(W) is \frac{1}{n!}.

The remarkable aspect of Theorem 1.1 is that the volume of the simplex F_{n}(W) is independent of W. The key to the proof of Theorem 1.1 is to study F_{n}(W) for all Sturmian words W simultaneously. The primary tool is the representation theory of finite groups.

Sturmian words are examples of one-dimensional quasicrystals, at least with respect to some of the ‘working definitions’ currently in use. In contrast to the study of crystals, group theory has not been found very useful in the study of quasicrystals. According to M. Senechal [Sen95], “The one-dimensional case suggests that symmetry may be a relatively unimportant feature of aperiodic crystals.” Thus, the prominent role of symmetric groups in the proof of Theorem 1.1 comes as a surprise.

The proof of Theorem 1.1 reveals a deep connection between the simplex F_{n}(c_{α}) and algebraic properties of the permutation π_{α,n} of 1, 2, …, n that orders the fractional parts {α}, {2α}, …, {nα}, i.e.,

0 < {π_{α,n}(1)α} < {π_{α,n}(2)α} < ⋯ < {π_{α,n}(n)α} < 1.

The definition of π_{α,n} has a combinatorial flavor, and accordingly some attention has been given to its combinatorial qualities. Using the geometric theory of continued fractions, Sós [Sós57] gives a formula for π_{α,n} in terms of n, π_{α,n}(n), and π_{α,n}(1) (see Lemma 3.1.1). Boyd & Steele [BS79] reduce the problem of finding the longest increasing subsequence in π_{α,n} to a linear programming problem, which they then solve explicitly. Schoißengeier [Sch84] used Dedekind eta sums to study π_{α,n} and give his formula for the star-discrepancy of nα-sequences.

Here, motivated by the appearance of π_{α,n} in our study of the simplex F_{n}(W), we initiate the study of algebraic properties of π_{α,n}. If σ is an element of a group (with identity element id), we let ord(σ) be the least positive integer t such that σ^{t} = id, or ∞ if no such integer exists. We use this notation with permutations, matrices, and congruence classes (the class will always be relatively prime to the modulus). For any permutation σ, let sgn(σ) be the sign of σ, i.e., sgn(σ) = 1 if σ is an even permutation and sgn(σ) = −1 if σ is an odd permutation. Our main results concerning π_{α,n} are stated in Theorems 1.2 and 1.3.

Theorem 1.2. For every irrational α, there are infinitely many positive integers n such that ord(π_{α,n}) < n.

Theorem 1.3. For every irrational α and positive integer n,

sgn(π_{α,2n}) = sgn(π_{α,2n+1}) = ∏_{ℓ=1}^{n}(−1)^{⌊2ℓα⌋}.

In particular, although π_{α,n} is “quasi-random” in the sense of [Coo02], it is highly structured in an algebraic sense.

Sections 2 and 3 are logically independent and may be read in either order. In Section 2, we consider Sturmian words and the simplex F_{n}(W). Section 3 is devoted to proving Theorems 1.2 and 1.3. Section 4 is a list of questions raised by the results of Sections 2 and 3 that we have been unable to answer. A Mathematica notebook containing code for generating the functions and examples in this paper is available from the author.

2 Sturmian Words

2.1 Introduction to Sturmian Words

An excellent introduction to the theory of Sturmian words is given in [Lot02, Chapter 2]. We restate the results needed in this paper in this subsection.

If α ∈ (0, 1) is irrational and β is any real number, then the words s_{α,β} and s′_{α,β} defined by

s_{α,β}(i) := ⌊(i + 1)α + β⌋ − ⌊iα + β⌋
s′_{α,β}(i) := ⌈(i + 1)α + β⌉ − ⌈iα + β⌉

are Sturmian, and every Sturmian word arises in this way [Lot02, Theorem 2.3.13]. The irrational number α is called the slope of the word, and the word c_{α} := s_{α,α} is called the characteristic word of slope α. It is easily shown [Lot02, Proposition 2.1.18] that F_{n}(W) depends only on the slope of W, and so it is consistent to write F_{n}(α) in place of F_{n}(W). In fact, we shall use the equation F_{n}(α) = F_{n}(s_{α,β}) for all β. It is often easier to think in terms of ‘where the 1s are’; elementary manipulation reveals that

c_{α}(i) = \begin{cases}1 & i + 1 ∈ \{⌊\frac{k}{α}⌋ : k ≥ 1\} \\ 0 & otherwise. \end{cases}

The n + 1 elements of F_{n}(α) are n-dimensional vectors, naturally defining a simplex in ℝ^{n}. Whenever a family of simplices arises, there are several questions that must be asked. Can the simplex F_{n}(α) be degenerate? If F_{n}(α) is not degenerate, can one express its volume as a function of n and α? Under what conditions on α, β, n is F_{n}(α) ≅ F_{n}(β)?

The first and second questions are answered by Theorem 1.1, which we prove in Subsection 2.5 below. Computer calculation suggests a simple answer to the third question, which we state as a conjecture in Section 4.

Example: The characteristic word with slope e^{−1} ≈ 0.368 begins

(c_{e^{−1}}(0), c_{e^{−1}}(1), c_{e^{−1}}(2), …) = (0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, …).

Note that

c_{e^{−1}}(i) = \begin{cases}1 & i + 1 ∈ \{⌊ne⌋ : n ≥ 1\} = \{2, 5, 8, 10, … \} \\ 0 & otherwise. \end{cases}

The set of factors of c_{e^{−1}} of length 6, arranged in anti-lexicographic order, is

F_{6}(c_{e^{−1}}) = F_{6}(e^{−1}) = \{(\begin{matrix}1 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \end{matrix}) , (\begin{matrix}1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \end{matrix}) , (\begin{matrix}1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{matrix}) , (\begin{matrix}0 \\ 1 \\ 0 \\ 1 \\ 0 \\ 0 \end{matrix}) , (\begin{matrix}0 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \end{matrix}) , (\begin{matrix}0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 0 \end{matrix}) , (\begin{matrix}0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 1 \end{matrix})\} .

□

2.2 Definitions

To analyze a simplex, one first orders the vertices (we order them anti-lexicographically). Then, one translates the simplex so that one vertex is at the origin (we move the last factor to 0). Finally, one writes the coordinates of the other vertices as the columns of a matrix. If this matrix is non-singular, then the simplex is not degenerate. In fact, the volume of the simplex is the absolute value of the determinant divided by n!. We are thus led to define the matrix M_{n}(α), whose j-th column is v⃗_{j}−v⃗_{n+1}, where F_{n}(α) = {v⃗_{1}, v⃗_{2}, …, v⃗_{n+1}} ordered anti-lexicographically.

Example:

M_{6}(e^{−1}) = (\begin{matrix}1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & −1 & −1 & −1 & −1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & −1 & −1 & −1 & −1 \end{matrix}) .

□

When a list of vectors is enclosed by parentheses, it denotes a matrix whose first column is the first vector, second column the second vector, and so on. For example,

M_{n}(α) := (v⃗_{1} − v⃗_{n+1}, v⃗_{2} − v⃗_{n+1}, … v⃗_{n} − v⃗_{n+1}) .

We also define V_{k} to be the n × n matrix all of whose entries are 0, save the k-th column, which is e⃗_{k−1} − 2e⃗_{k} + e⃗_{k+1}.

We shall make frequent use of Knuth’s notation:

[[Q]] = \begin{cases}1 & Q is true; \\ 0 & Q is false. \end{cases}

We denote the symmetric group on the symbols 1, 2, …, n by S_{n}. We use several notations for permutations interchangeably. We use standard cycle notation when convenient, and frequently use one-line notation for permutations, i.e.,

σ = [σ(1), …, σ(n)].

Thus, if a list of distinct numbers is surrounded by parentheses then it is a permutation in cycle notation, and if the numbers 1, 2, …, n are in any order and surrounded by brackets then it is a permutation in one-line notation. We multiply permutations from right to left. Also, set P_{σ} = (p_{ij}), with p_{ij} = [[j = σ(i)]]. This is the familiar representation of S_{n} as permutation matrices.

One permutation we have already defined is π_{α,n}. For notational convenience we set π_{α,n}(0) := 0 and π_{α,n}(n + 1) := n + 1. Also, set P_{j} := {jα} for 0 ≤ j ≤ n, and set P_{n+1} := 1. Thus

0 = P_{π_{α,n}(0)} < P_{π_{α,n}(1)} < P_{π_{α,n}(2)} < ⋯ < P_{π_{α,n}(n)} < P_{π_{α,n}(n+1)} = 1.

We write e⃗_{i} (1 ≤ i ≤ n) be the n-dimensional column vector with every component 0 except the i-th component, which is 1. We set e⃗_{n+1} = 0, the n-dimensional 0 vector. We denote the identity matrix as I := (e⃗_{1}, e⃗_{2}, …, e⃗_{n}). Let δ⃗_{i} := e⃗_{i+1} − e⃗_{i} (1 ≤ i ≤ n). In particular, δ⃗_{n} = −e⃗_{n}.

We will also use the notation h(v⃗) for the Hamming weight of the {0, 1}-vector v⃗, i.e., the number of 1’s.

Set

D(σ) := {1} ∪ {k: σ^{−1}(k − 1) > σ^{−1}(k)}.

In other words, D(σ) consists of those k for which k − 1 does not occur before k in [σ(1), σ(2), …, σ(n)]. For example, D([1, 3, 5, 4, 2, 6]) = {1, 3, 5}.

Set

w_{1}^{σ} := ∑_{i∈D(σ)} e⃗_{i}

and for 1 ≤ j ≤ n, set

w_{j+1}^{σ} := w_{j}^{σ} + δ⃗_{σ(j)}.

We now define two matrices: the n × (n + 1) matrix

L_{σ} := (w_{1}^{σ}, w_{2}^{σ}, …, w_{n}^{σ}, w_{n+1}^{σ}),

and the square n × n matrix

M_{σ} := (w_{1}^{σ} − w_{n+1}^{σ}, w_{2}^{σ} − w_{n+1}^{σ}, …, w_{n}^{σ} − w_{n+1}^{σ}).

Proposition 2.3.1 below shows that M_{n}(α) = M_{π_{α,n}}, justifying our definitions.

Example: Set n = 5 and σ = [5, 2, 3, 1, 4] = (1, 5, 4)(2)(3). We find that D(σ) = {1, 2, 5}, and so w_{1}^{σ} = e⃗_{1} + e⃗_{2} + e⃗_{5}. By definition w_{2}^{σ} = w_{1}^{σ} + δ⃗_{σ(1)} = w_{1}^{σ} + e⃗_{6} − e⃗_{5} = e⃗_{1} + e⃗_{2}, and so on. Thus

L_{σ} = (\begin{matrix}1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 \end{matrix}) and M_{σ} = (\begin{matrix}1 & 1 & 1 & 1 & 0 \\ 0 & 0 & −1 & −1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & −1 & −1 & −1 & −1 \end{matrix}) .

Note that the first column of M_{σ} is e⃗_{1}; that this is always the case is proven in Lemma 2.4.2. Further, the second column of M_{σ} is e⃗_{1} + δ⃗_{σ(1)}, the third is e⃗_{1} + δ⃗_{σ(1)} + δ⃗_{σ(2)}, and so forth. This pattern holds in general and is proved in Lemma 2.4.3 below. It is not immediate from the definitions that L_{σ} is always a {0, 1}-matrix or that M_{σ} is a {−1, 0, 1}-matrix; we prove this in Lemma 2.4.4.

In Lemma 2.4.5 we prove that if σ ≠ τ then M_{σ} ≠ M_{τ}. The proof relies on reconstructing σ and L_{σ} from M_{σ}. This reconstruction proceeds as follows. The ‘−1’ entries of M_{σ} are in the second and fifth rows; this gives w_{6}^{σ} = e⃗_{2} + e⃗_{5}, which is the last column of L_{σ}. In fact, the j-th column of L_{σ} is the j-th column of M_{σ} plus e⃗_{2} + e⃗_{5}. Once we know the columns of L_{σ} := (w_{1}^{σ}, w_{2}^{σ}, …, w_{6}^{σ}), we can use the definition of w_{j+1}^{σ} to find σ(j). For example, δ⃗_{σ(4)} = w_{5}^{σ} − w_{4}^{σ} = e⃗_{2} − e⃗_{1} = δ⃗_{1}, and so σ(4) = 1.

Lemma 2.4.6 generalizes the observation that

M_{[1,2,4,3,5]} = M_{(4,3)} = (\begin{matrix}1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & −1 & 0 \\ 0 & 0 & 0 & 1 & 1 \end{matrix}) = I + V_{4}.

With ϕ = \frac{\sqrt{5}−1}{2}, we compute that π_{ϕ,5} = [5, 2, 4, 1, 3] = (1, 5, 3, 4)(2), and one may directly verify that M_{π_{ϕ,5}} = M_{ϕ}(5). This is no accident, by Proposition 2.3.1 below M_{α}(n) = M_{π_{α,n}} for all α and n. The equation

M_{(4,3)}M_{π_{ϕ,5}} = M_{(4,3)(1,5,3,4)(2)} = M_{(1,5,4)(2)(3)},

which is the same as

(\begin{matrix}1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & −1 & 0 \\ 0 & 0 & 0 & 1 & 1 \end{matrix}) (\begin{matrix}1 & 1 & 1 & 1 & 0 \\ 0 & 0 & −1 & −1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & −1 & −1 \\ 0 & −1 & −1 & 0 & 0 \end{matrix}) = (\begin{matrix}1 & 1 & 1 & 1 & 0 \\ 0 & 0 & −1 & −1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & −1 & −1 & −1 & −1 \end{matrix}) ,

is an example of the isomorphism of Proposition 2.4.1. □

2.3 The Matrices M_{n}(α) and M_{π_{α,n}}

Proposition 2.3.1. M_{n}(α) = M_{π_{α,n}}.

Proof. For brevity, we write π in place of π_{α,n}. First observe that w_{1}^{π}, w_{2}^{π}, …, w_{n+1}^{π} are in anti-lexicographic order by definition, and so for 1 ≤ i < j ≤ n + 1 we have w_{i}^{π} ≠ w_{j}^{π}. We know from [Lot02, Proposition 2.1.18] that F_{n}(α) = F_{n}(s_{α,β}) for every β, and from [Lot02, Theorem 2.1.13] that |F_{n}(α)| = n + 1. Thus, it suffices to show that w_{j}^{π} ∈ F_{n}(s_{α,β}) for some β. In fact, we shall show that

(s_{α,β_{j}}(1), s_{α,β_{j}}(2), …, s_{α,β_{j}}(n)) = w_{j}^{π}

with β_{j} := −P_{1} − P_{π(j)}.

Using the identities ⌊x⌋ = x − {x} and {x − y} = {x} − {y} + [[{x} < {y}]], we have

s_{α,β_{j}}(i) = ⌊(i + 1)α − P_{1} − P_{π(j)}⌋ − ⌊iα − P_{1} − P_{π(j)}⌋
= α − P_{i} + P_{i−1} − [[P_{i} < P_{π(j)}]] + [[P_{i−1} < P_{π(j)}]]
= [[P_{i} < P_{i−1}]] − [[P_{i} < P_{π(j)}]] + [[P_{i−1} < P_{π(j)}]].  (1)

The last equality follows from the knowledge that s_{α,β_{j}}(i) ∈ ℤ, and consequently if P_{i} < P_{i−1} then α − P_{i} + P_{i−1} > α > 0 must in fact be 1, and if P_{i} > P_{i−1} then α − P_{i} + P_{i−1} < α < 1 must in fact be 0.

We first consider j = 1. We have P_{1} > P_{0}, P_{1} ≥ P_{π(1)}, and P_{0} < P_{π(1)}, whence s_{α,β_{1}}(1) = 1 = [[1 ∈ D(π)]]. For 2 ≤ i ≤ n, we have P_{i} ≥ P_{π(1)} and P_{i−1} ≥ P_{π(1)}, whence

s_{α,β_{1}}(i) = [[P_{i} < P_{i−1}]] = [[π^{−1}(i) < π^{−1}(i − 1)]] = [[i ∈ D(π)]].

Therefore, (s_{α,β_{1}}(1), s_{α,β_{1}}(2), …, s_{α,β_{1}}(n)) = w_{1}^{π}.

Now suppose that 2 ≤ j ≤ n + 1. Since w_{j}^{π} is defined by w_{j}^{π} − w_{j−1}^{π} = δ⃗_{π(j−1)} = e⃗_{π(j−1)+1} − e⃗_{π(j−1)}, we need to show that s_{α,β_{j}}(i) − s_{α,β_{j−1}}(i) = [[i = π(j − 1) + 1]] − [[i = π(j − 1)]]. By Eq. (1), we have

s_{α,β_{j}}(i) − s_{α,β_{j−1}}(i) = −[[P_{i} < P_{π(j)}]] + [[P_{i−1} < P_{π(j)}]] + [[P_{i} < P_{π(j−1)}]] − [[P_{i−1} < P_{π(j−1)}]]
= ([[P_{i−1} < P_{π(j)}]] − [[P_{i−1} < P_{π(j−1)}]]) − ([[P_{i} < P_{π(j)}]] − [[P_{i} < P_{π(j−1)}]])
= [[i − 1 = π(j − 1)]] − [[i = π(j − 1)]].

We remark that in the same manner one may prove that if

1 − {π_{α,n}(j)α} ≤ {iα + β} < 1 − {π_{α,n}(j − 1)α},

then

(s_{α,β}(i), s_{α,β}(i + 1), …, s_{α,β}(i + n − 1)) = w_{j}^{π_{α,n}}.

From this it is easy to prove that F_{n}(s_{α,β}) does not depend on β and has cardinality n + 1, the two results of [Lot02] that we used. There is another fact that can be proved in this manner that we do not use explicitly but which may help the reader develop an intuitive understanding of the simplices F_{n}(W). If r, r′ are consecutive Farey fractions of order n + 1 and r < α < γ < r′, then F_{n}(α) = F_{n}(β).

2.4 A Curious Representation

Proposition 2.4.1. The map σ ↦ M_{σ} is an isomorphism.

The proof we give of this is more a verification than an explanation. We remark that there are several anti-isomorphisms involved in our choices. We have chosen to multiply permutations right-to-left rather than left-to-right. We have chosen to consider the list [a, b, c, …] as the permutation taking 1 to a, 2 to b, 3 to c, etc., rather than the permutation taking a to 1, b to 2, c to 3, etc. Finally, we have chosen to define the vectors w^{σ} to be columns rather than rows. If we were to change any two of these conventions, then we would still get an isomorphism.

We begin with some simple observations about M_{σ} before proving Proposition 2.4.1. We defined w_{j+1}^{σ} := w_{j}^{σ} + δ⃗_{σ(j)}. An easy inductive consequence of this definition is that w_{j+1}^{σ} = w_{1}^{σ} + ∑_{i=1}^{j} δ⃗_{σ(i)} for 1 ≤ j ≤ n; we use this repeatedly and without further fanfare.

Lemma 2.4.2. w_{1}^{σ} − w_{n+1}^{σ} = e⃗_{1}.

Proof. Since w_{n+1}^{σ} = w_{1}^{σ} + ∑_{i=1}^{n} δ⃗_{σ(i)}, all we need to show is that ∑_{i=1}^{n} δ⃗_{σ(i)} = −e⃗_{1}. As {1, 2, …, n} = {σ(1), σ(2), …, σ(n)}, we have

w_{n+1}^{σ} − w_{1}^{σ} = ∑_{i=1}^{n} δ⃗_{σ(i)} = ∑_{i=1}^{n} δ⃗_{i} = ∑_{i=1}^{n}(e⃗_{i+1} − e⃗_{i}) = e⃗_{n+1} − e⃗_{1} = −e⃗_{1}.

Lemma 2.4.3. The j-th column of M_{σ} is e⃗_{1} + ∑_{i=1}^{j−1} δ⃗_{σ(i)}.

Proof. The j-th column of M_{σ} is defined as w_{j}^{σ} − w_{n+1}^{σ}. If j = 1, then this lemma reduces to Lemma 2.4.2. If j > 1, then Lemma 2.4.2 gives

w_{j}^{σ} − w_{n+1}^{σ} = (w_{1}^{σ} + ∑_{i=1}^{j−1} δ⃗_{σ(i)}) − (w_{1}^{σ} − e⃗_{1}) = e⃗_{1} + ∑_{i=1}^{j−1} δ⃗_{σ(i)}.

Lemma 2.4.4. The entries of L_{σ} are 0 and 1. The entries of M_{σ} are -1, 0, and 1.

Proof. It is easily seen from Lemma 2.4.3 that M_{σ} is a {−1, 0, 1}-matrix, and this also follows from the more subtle observation that L_{σ} is a {0, 1}-matrix. To prove that L_{σ} is a {0, 1}-matrix is the same as showing that each w_{j}^{σ} (1 ≤ j ≤ n + 1) is a {0, 1}-vector. This is obvious for w_{1}^{σ} := ∑_{i∈D(σ)} e⃗_{i}. We have w_{j+1}^{σ} = w_{1}^{σ} + ∑_{i=1}^{j} δ⃗_{σ(i)}; define v⃗, c_{i} by v⃗ := ∑_{i=1}^{j} δ⃗_{σ(i)} = ∑_{i=1}^{n} c_{i}e⃗_{i}.

The i-th component of v⃗ can only be affected by δ⃗_{i−1} (which adds 1 to the i-th component) and δ⃗_{i} (which subtracts 1). It is thus clear that c_{i} is (-1), (0), (0), or (1) depending, respectively, on whether (only i), (i−1 and i), (neither i − 1 nor i), or (only i − 1) is among {σ(1), σ(2), …, σ(j)}. To show that w_{j+1}^{σ} = w_{1}^{σ} + v⃗ is a {0, 1}-vector, we need to show two things. First, if c_{i} = −1 then i ∈ D(σ) (and so the i-th component of w_{1}^{σ} is 1). Second, if c_{i} = 1 then i ∉ D(σ) (and so the i-th component of w_{1}^{σ} is 0).

If c_{i} = −1, then i is and i − 1 is not among {σ(1), …, σ(j)}. This means that σ^{−1}(i − 1) > j ≥ σ^{−1}(i), and so by the definition of D, i ∈ D(σ). If, on the other hand, c_{i} = 1, then i − 1 is and i is not among {σ(1), …, σ(j)}. This means that σ^{−1}(i − 1) ≤ j < σ^{−1}(i), and so by the definition of D, i ∉ D(σ).

Lemma 2.4.5. The map σ ↦ M_{σ} is 1-1.

Proof. Given M_{σ}, we find σ. We first note that moving from L_{σ} to σ is easy since w_{j+1}^{σ} − w_{j}^{σ} = δ⃗_{σ(j)}. Some effort is involved in finding L_{σ} from M_{σ}. We need to find w_{n+1}^{σ}.

Every row of L_{σ} contains at least one 0 (explanation below). Thus M_{σ} will contain a −1 in exactly those rows in which w_{n+1}^{σ} contains a 1, and we are done. We have w_{j+1}^{σ} = w_{j}^{σ} + δ⃗_{σ(j)} = w_{j}^{σ} + e⃗_{σ(j)+1} − e⃗_{σ(j)}. The σ(j)-th row of e⃗_{σ(j)+1} is 0, and w_{j}^{σ} , e⃗_{σ(j)} are {0, 1}-vectors, so the σ(j)-th row of w_{j+1}^{σ} is either 0 or −1. But by Lemma 2.4.4, L_{σ} is a {0, 1}-matrix, whence the σ(j)-th row of the (j + 1)-st column of L_{σ} is 0.

Recall that V_{k} is defined to be the matrix all of whose entries are 0, save the k-th column, which is e⃗_{k−1} − 2e⃗_{k} + e⃗_{k+1}.

Lemma 2.4.6. M_{(k,k−1)} = I + V_{k}, for 2 ≤ k ≤ n.

Proof. Follow the definitions. With σ = (k, k − 1), we have D(σ) = {1, k}, w_{j}^{(k,k−1)} = e⃗_{j} + e⃗_{k} for n ≥ j ≠ k, w_{k}^{(k,k−1)} = e⃗_{k−1} + e⃗_{k+1} and w_{n+1}^{(k,k−1)} = e⃗_{k}.

We have laid the necessary groundwork, and turn now to proving Proposition 2.4.1.

Proof. We have already seen in Lemma 2.4.5 that the map σ ↦ M_{σ} is 1-1; all that remains is to show that this map respects multiplication, i.e., for any σ, τ ∈ S_{n}, M_{τ} M_{σ} = M_{τσ}. Since we may write τ as a product of transpositions of the form (k, k − 1) it is sufficient to show that M_{(k,k−1)}M_{σ} = M_{(k,k−1)σ} for every k (2 ≤ k ≤ n) and σ ∈ S_{n}.

We need to split the work into two cases: σ^{−1}(k − 1) < σ^{−1}(k) and σ^{−1}(k − 1) > σ^{−1}(k). In each case we first describe the rows of M_{(k,k−1)}M_{σ} − M_{σ} using Lemma 2.4.6, and then compute the columns of M_{(k,k−1)σ} − M_{σ} from the definition. We will find that M_{(k,k−1)}M_{σ} − M_{σ} = M_{(k,k−1)σ} − M_{σ} in each case, which concludes the proof. Since the two cases are handled similarly, we present only the first case.

Suppose that σ^{−1}(k − 1) < σ^{−1}(k). By Lemma 2.4.6, M_{(k,k−1)}M_{σ} − M_{σ} = V_{k}M_{σ}. The matrix V_{k} is zero except in the (k − 1, k), (k, k), and (k + 1, k) positions (note: we sometimes refer to positions which do not exist for k = n; the reader may safely ignore this detail), where it has value 1, −2, 1, respectively. Thus V_{k}M_{σ} is zero except in the (k − 1)-st and (k + 1)-st rows (which are the same as the k-th row of M_{σ}), and the k-th row (which is −2 times the k-th row of M_{σ}).

We now describe the k-th row of L_{σ}. By the hypothesis of this case, k ∉ D(σ), so the k-th row of w_{1}^{σ} is 0. Since w_{j+1}^{σ} = w_{1}^{σ} + ∑_{i=1}^{j} δ⃗_{σ(i)}, the k-th row of w_{j}^{σ} is 0 for 1 ≤ j ≤ σ^{−1}(k − 1), is 1 for σ^{−1}(k − 1) < j ≤ σ^{−1}(k), and is 0 for σ^{−1}(k) < j ≤ n + 1. This gives the k-th row of M_{σ} as σ^{−1}(k − 1) ‘0’s followed by σ^{−1}(k) − σ^{−1}(k − 1) ‘1’s, followed by n − σ^{−1}(k) ‘0’s.

We now compute M_{(k,k−1)σ} − M_{σ}. The columns of L_{(k,k−1)σ} are given by w_{j+1}^{(k,k−1)σ} = w_{1}^{(k,k−1)σ} + ∑_{i=1}^{j} δ⃗_{(k,k−1)σ(i)} (except the first, but the first column of M_{τ} is e⃗_{1}, independent of τ). Now (k, k − 1)σ(i) = σ(i) for i ∉ {σ^{−1}(k), σ^{−1}(k−1)}, so that ∑_{i=1}^{j} δ⃗_{(k,k−1)σ(i)} = ∑_{i=1}^{j} δ⃗_{σ(i)} for j < σ^{−1}(k−1) and for j ≥ σ^{−1}(k). For σ^{−1}(k − 1) ≤ j < σ^{−1}(k),

∑_{i=1}^{j} δ⃗_{(k,k−1)σ(i)} = (∑_{i=1}^{j} δ⃗_{σ(i)}) − δ⃗_{k−1} + δ⃗_{k}.

Thus the (j + 1)-st column of M_{(k,k−1)σ} − M_{σ} is

(w_{j+1}^{(k,k−1)σ} − w_{n+1}^{(k,k−1)σ}) − (w_{j+1}^{σ} − w_{n+1}^{σ}) = ∑_{i=1}^{j} δ⃗_{(k,k−1)σ(i)} − ∑_{i=1}^{j} δ⃗_{σ(i)},

which is 0 for j < σ^{−1}(k − 1) and for j ≥ σ^{−1}(k), and −δ⃗_{k−1} + δ⃗_{k} = e⃗_{k−1} − 2e⃗_{k} + e⃗_{k+1} for σ^{−1}(k − 1) ≤ j < σ^{−1}(k). We have shown that M_{(k,k−1)}M_{σ} − M_{σ} = M_{(k,k−1)σ} − M_{σ} in the case σ^{−1}(k − 1) < σ^{−1}(k).

2.5 Proof of Theorem 1.1

Proof of Theorem 1.1. The volume of the n-dimensional simplex whose vertices have coordinates v⃗_{1}, v⃗_{2}, …, v⃗_{n+1} is \frac{1}{n!} times the absolute value of the determinant of the matrix

(v⃗_{1} − v⃗_{n+1}, v⃗_{2} − v⃗_{n+1}, …, v⃗_{n} − v⃗_{n+1}) .

In our case, this means that the volume of the simplex F_{n}(α) is \frac{1}{n!} |det(M_{n}(α))|. We will show that det(M_{n}(α)) = ±1.

Now M_{n}(α) = M_{π_{α,n}} by Proposition 2.3.1, and for any integer t we have (M_{π_{α,n}})^{t} = M_{π_{α,n}^{t}} by Proposition 2.4.1. Since π_{α,n} ∈ S_{n}, a finite group, there is a positive integer t such that π_{α,n}^{t} is the identity permutation (which we denote by id). Thus

(det M_{n}(α))^{t} = (det M_{π_{α,n}})^{t} = det (M_{π_{α,n}}^{t}) = det (M_{π_{α,n}^{t}}) = det (M_{id}) = det I = 1.

Consequently, det M_{n}(α) is a t-th root of unity, and since the entries of M_{n}(α) are integers, det M_{n}(α) = ±1.

2.6 The Character of the Representation

We review the needed facts and definitions from the representation theory of finite groups (an excellent introduction is [Sag01]). A representation of a finite group G is a homomorphism R : G → SL_{m}(ℂ) for some m ≥ 1. The representation is said to be faithful if the homomorphism is in fact an isomorphism. Thus, Proposition 2.4.1 implies that {M_{σ}: σ ∈ S_{n}} is a faithful representation of S_{n}. The character of R is the map g ↦ tr(R(g)), with tr being the trace function. We will use Corollary 1.9.4(5) of [Sag01], which states that if two representations R_{1}, R_{2} of G have the same character, then they are similar, i.e., there is a matrix Q such that ∀g ∈ G (Q^{−1}R_{1}(g)Q = R_{2}(g)). Any such matrix Q is called an intertwining matrix for the representations R_{1}, R_{2}.

Proposition 2.6.1. The representations {P_{σ}: σ ∈ S_{n}} and {M_{σ}: σ ∈ S_{n}} are similar.

Proof. The character of {P_{σ}: σ ∈ S_{n}} is obviously given by tr(P_{σ}) = #{i: σ(i) = i}. We will show that tr(M_{σ}) = #{i: σ(i) = i} also, thereby establishing that the representations are similar.

We first note that tr(M_{σ}) = tr(L_{σ}) − h(w_{n+1}^{σ}), since every “1” in w_{n+1}^{σ} is subtracted from exactly one diagonal position when we form M_{σ} from L_{σ} by subtracting w_{n+1}^{σ} from each column. We show below that

tr(L_{σ}) = h(w_{1}^{σ}) − 1 + #{i: σ(i) = i},  (2)

so by Lemma 2.4.2 we have

tr(M_{σ}) = h(w_{1}^{σ}) − 1 + #{i: σ(i) = i} − h(w_{n+1}^{σ}) = #{i: σ(i) = i},

which will conclude the proof.

Until this point we have found it convenient to think of L_{σ} in terms of its columns. That is not the natural viewpoint to take in proving Eq. (2), however. The difference between the (j +1)-st and j-th columns of L_{σ} is δ⃗_{σ(j)} = e⃗_{i+1}−e⃗_{i}; we think of this relationship as a “1” moving down from the i-th row to the (i+1)-st row. In looking at the matrix L_{σ} we see each “1” in the first column continues across to the east, occasionally moving down a row (southeast), or even ‘off’ the bottom of the matrix. We call the path a “1” takes a snake.

Example: With σ = [1, 4, 5, 8, 2, 3, 9, 6, 10, 7], we find

L_{σ} = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \end{matrix} )

The matrix L_{σ} has 3 snakes beginning in positions (1, 1), (4, 1), and (8, 1). The first snake occupies the positions (1, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 6), (4, 7), (4, 8), (4, 9), (4, 10), and (4, 11). □

Only the last snake moves off the bottom of L_{σ}; after all, n only occurs once in a permutation. The other snakes, of which there are h(w_{1}^{σ})−1, begin on or below the diagonal and end on or above the diagonal. Thus each must intersect the diagonal at least once. Moreover, each fixed point of σ will keep a snake on a diagonal for an extra row. Thus, tr(L_{σ}) = h(w_{1}^{σ}) − 1 + #{i: σ(i) = i}.

We turn now to identifying the intertwining matrices, i.e., the matrices Q such that Q^{−1}M_{σ}Q = P_{σ} for every σ ∈ S_{n}.

Proposition 2.6.2. The n × n matrix Q = (q_{ij}) satisfies Q^{−1}M_{σ}Q = P_{σ} for every σ ∈ S_{n} iff there are complex numbers a, b with (na + b)b^{n−1} ≠ 0 and q_{11} = a + b, q_{1k} = a, q_{kk} = b, q_{k,k−1} = −b (2 ≤ k ≤ n).

Proof. We first note that it is sufficient to restrict σ to a generating set of S_{n}. To see this, let S_{n} = ⟨σ_{1}, …, σ_{r}⟩. If Q satisfies Q^{−1}M_{σ}Q = P_{σ} for every σ ∈ S_{n}, then clearly Q^{−1}M_{σ_{i}}Q = P_{σ_{i}} (1 ≤ i ≤ r). In the other direction, if Q satisfies Q^{−1}M_{σ_{i}}Q = P_{σ_{i}} (1 ≤ i ≤ r) and σ = σ_{i_{1}}σ_{i_{2}} … σ_{i_{s}}, then

Q^{−1}M_{σ}Q = Q^{−1} (M_{σ_{i_{1}}} M_{σ_{i_{2}}} … M_{σ_{is}} ) Q = ∏_{j=1}^{s} (Q^{−1}M_{σ_{i_{j}}} Q)

= ∏_{j=1}^{s} P_{σ_{i_{j}}} = P_{∏_{j=1}^{s} σ_{i_{j}}} = P_{σ}.

Thus we can restrict our attention to the transpositions (k, k − 1) (2 ≤ k ≤ n). We identified M_{(k,k−1)} in Lemma 2.4.6 as M_{(k,k−1)} = I + V_{k}, where V_{k} is the matrix all of whose entries are zero, save the k-th column, which is e⃗_{k−1} − 2e⃗_{k} + e⃗_{k+1}.

We suppose that Q = (q_{ij}) satisfies M_{(k,k−1)}Q = QP_{(k,k−1)} to find linear constraints on the unknowns q_{ij}. We will find that these constraints (for 2 ≤ k ≤ n) are equivalent to q_{11} = a + b, q_{1k} = a, q_{kk} = b, q_{k,k−1} = −b (2 ≤ k ≤ n). The determinant of Q is easily seen to be (na + b)b^{n−1}, so that as long as this is nonzero, Q^{−1}M_{σ}Q = P_{σ} for every σ ∈ S_{n}.

We have M_{(k,k−1)}Q = IQ + V_{k}Q, so that M_{(k,k−1)}Q = QP_{(k,k−1)} is equivalent to V_{k}Q = Q(P_{(k,k−1)} − I). This is a convenient form since most entries in the matrices V_{k} and P_{(k,k−1)} − I are zero. The entries of the product V_{k}Q are 0 except for the (k − 1)-st, k-th, and (k + 1)-st rows which are equal to the k-th row of Q, to −2 times the k-th row of Q, and to the k-th row of Q, respectively. The entries of the product Q(P_{(k,k−1)} − I) are 0 except for the (k − 1)-st and k-th columns, which are equal to the k-th column of Q minus the (k −1)-st column of Q, and to the (k −1)-st column of Q minus the k-th column of Q, respectively. The entries which are zero in one matrix or other lead to the families of equations q_{kj} = 0 (for j ∉ {k −1, k}) and q_{jk} = q_{j,k−1} (for j ∉ {k − 1, k, k + 1}). The entries which are non-zero in both products give the six equations

(\begin{matrix}q_{k,k−1} & q_{kk} \\ −2q_{k,k−1} & −2q_{kk} \\ q_{k,k−1} & q_{kk} \end{matrix}) = (\begin{matrix}q_{k−1,k} − q_{k−1,k−1} & q_{k−1,k−1} − q_{k−1,k} \\ q_{kk} − q_{k,k−1} & q_{k,k−1} − q_{kk} \\ q_{k+1,k} − q_{k+1,k−1} & q_{k+1,k−1} − q_{k+1,k} \end{matrix}) ,

which are equivalent to q_{k−1,k−1} = q_{k−1,k} +q_{k,k}, q_{k,k−1} = −q_{kk}, and q_{k+1,k−1} = q_{k+1,k} +q_{kk}. Taking q_{nn} = b and q_{1n} = a, the result follows.

Corollary 2.6.3.

M_{σ} = (\begin{matrix}1 \\ −1 & 1 & & & & & 0 \\ & −1 & 1 \\ & & & . & . & . \\ & 0 & & & & & ... \\ & & & & & & −1 & 1 \end{matrix}) · P_{σ} · (\begin{matrix}1 \\ 1 & 1 & & & 0 \\ 1 & 1 & 1 \\ ⋮ & & & ... \\ ⋮ & 1 & & & ... \\ & … & … & … & 1 & 1 \end{matrix}) .

Proof. Set a = 0, b = 1 in Theorem 2.6.2. All that needs to be checked is that Q^{−1} is as claimed, i.e., the n × n matrix with “1”s on and below and the diagonal and “0”s above the diagonal.

We remark that, since it is easy to recover L_{σ} from M_{σ} (see the proof of Lemma 2.4.4) this Corollary gives a simple method for computing the factors of length n of a Sturmian word with slope α given only the permutation ordering {α}, …, {nα} (we don’t even need α). Also, we note that the matrix with “1”s on and below the diagonal is a summation operator, and its inverse is a difference operator. If one could prove Corollary 2.6.3 directly, this would provide a second proof of Theorem 1.1.

2.7 The Simplex F_{n}(W)

Stolarsky & Porta [personal communication] observed experimentally that M_{n}(α) has determinant ±1, and moreover that the roots of its characteristic polynomial are roots of unity. The first observation was proved in the course of the proof of Theorem 1.1 in Subsection 2.5. The second observation also follows from the fact that M_{n}(α) lies in a finite group.

We now summarize the results of this paper as they relate to M_{n}(α) and F_{n}(α).

Theorem 2.1. Let α ∈ (0, 1) be irrational, and n ≥ 1 an integer.

i. The volume of the simplex F_{n}(α) is \frac{1}{n!}.

ii. det(M_{n}(α)) = ±1.

iii. M_{n}(α) = M_{π_{α,n}} = QP_{π_{α,n}}Q^{−1} (see Theorem 2.6.2 for the definition of Q);

iv. det(M_{2n}(α) = det(M_{2n+1}(α)) = ∏_{ℓ=1}^{n}(−1)^{⌊2ℓα⌋}.

v. If π_{α,n}(n) = n, then

ord(M_{n−1}(α)) = ord(M_{n}(α)) = ord(π_{α,n}(1) mod n).

vi. If π_{α,n}(1) = n, then

ord(M_{n−1}(α)) = ord(−π_{α,n}(n) mod n)

and

ord(M_{n}(α)) = ord(−π_{α,n}(n) mod gn),

where g is the smallest positive integer such that gcd (n, \frac{π_{α,n}(n)+1}{g}) = 1.

Items (i) and (ii) are proved in Subsection 2.5. Item (iii) is a combination of Theorem 2.6.2 and Proposition 2.3.1. Items (iv), (v) and (vi) are immediate consequences of Proposition 2.3.1, the facts det(M_{σ}) = sgn(σ) and ord(M_{σ}) = ord(σ), and Theorem 3.1. They are included here for the purpose of listing everything known about M_{n}(α) in one place.

3 Ordering Fractional Parts

3.1 Statement of Results

Table 1 gives the sign and multiplicative order of π_{e,n} for 2 ≤ n ≤ 136. Visually inspecting the table, one quickly notices that sgn(π_{e,2n}) = sgn(π_{e,2n+1}) for all n, and that ord(π_{e,n}) is surprisingly small for n = 70, 71, 109, 110. The first several convergents to e are 2, 3, \frac{8}{3}, \frac{11}{4}, \frac{19}{7}, \frac{87}{32}, \frac{106}{39}, \frac{193}{71}; the value 71 is the denominator of a convergent, and 110 = 71 + 39 is the sum of two denominators. Note also that for some values of n, ord(π_{e,n}) is extraordinarily large, e.g., ord(π_{e,123}) = 22383900. None of these observations are peculiar to the irrational e. Some of these observations are explained by Theorem 3.1 below, and the others remain conjectural.

As in Section 2, we make frequent use of Knuth’s notation:

[[Q]] = \begin{cases}1 & Q is true; \\ 0 & Q is false. \end{cases}

Lemma 3.1.1, giving π_{α,n} in terms of only π_{α,n}(1), π_{α,n}(n), and n, is proved by V. T. Sós in [Sós57]. Her method of proof is similar to our proof of Lemma 3.3.1 below. The lemma is also proved—in terse English—in [Sla67]. We will derive Theorem 3.1 from Sós’s Lemma.

Lemma 3.1.1 (Sós). Let α be irrational, n a positive integer, and π = π_{α,n}. Then

π(k + 1) = π(k) + π(1) [[π(k) ≤ π(n)]] − π(n) [[n < π(1) + π(k)]]

for 1 ≤ k < n.

The surprising Three-Distance Theorem is an easy corollary: If α is irrational, the n + 2 points 0, {α}, {2α}, …, {nα}, 1 divide the interval [0, 1] into n+1 subintervals which have at most 3 distinct lengths. Alessandri & Berthé [AB98] give an excellent and up-to-date survey of generalizations of the Three-Distance Theorem.

The primary goal of this section is to prove Theorem 3.1, which refines Theorem 1.2, and to prove Theorem 1.3. Corollary 3.2.1 is of independent interest.

Theorem 3.1. Let α ∉ ℚ and n ∈ ℤ^{+}.

i. If π_{α,n}(n) = n, then ord(π_{α,n−1}) = ord(π_{α,n}) = ord(π_{α,n}(1) mod n).

ii. If π_{α,n}(1) = n, then ord(π_{α,n−1}) = ord(−π_{α,n}(n) mod n), and

ord(π_{α,n}) = ord(−π_{α,n}(n) mod gn),

where g is the least positive integer such that gcd (n, \frac{π_{α,n}(n)+1}{g}) = 1.

3.2 The Multiplicative Order of the Permutation

Theorem 3.1 follows from Sós’s Lemma.

Proof of Theorem 3.1(i). Suppose that π_{α,n}(n) = n. We have

π_{α,n}(k) = \begin{cases}π_{α,n−1}(k) & 1 ≤ k ≤ n − 1; \\ k & k = n, \end{cases}

and so obviously ord(π_{α,n−1}) = ord(π_{α,n}). We show that the length of every orbit divides ord(π_{α,n}(1) mod n), and that the length of the orbit of 1 is exactly ord(π_{α,n}(1) mod n). From Sós’s Lemma (Lemma 3.1.1), we have in this case for 1 ≤ k < n the congruence π_{α,n}(k + 1) ≡ π_{α,n}(k) + π_{α,n}(1) (mod n). By induction, this gives π_{α,n}(k) ≡ kπ_{α,n}(1) (mod n) for 1 ≤ k ≤ n. Thus, the orbit of the point k is

k, kπ_{α,n}(1), kπ_{α,n}(1)^{2}, kπ_{α,n}(1)^{3}, …

The length of the orbit of k divides ord(π_{α,n}(1) mod n), and in particular the orbit of 1 has length equal to ord(π_{α,n}(1) mod n).

Proof of Theorem 3.1(ii). Suppose that π_{α,n}(1) = n. Sós’s Lemma gives

π_{α,n}(k) ≡ (1 − k)π_{α,n}(n) (mod n).

Table 1: Algebraic properties of π_{α,n} with α = e and 2 ≤ n ≤ 136

n  sgn(πα,n)  ord(πα,n)  n  sgn(πα,n)  ord(πα,n)  n  sgn(πα,n)  ord(πα,n)
2  -1  2  47  -1  44  92  1  2107
3  -1  2  48  -1  540  93  1  13244
4  -1  2  49  -1  120  94  -1  18810
5  -1  4  50  1  680  95  -1  20034
6  -1  6  51  1  1848  96  -1  3348
7  -1  6  52  -1  50  97  -1  11256
8  1  7  53  -1  90  98  -1  1702
9  1  6  54  -1  962  99  -1  188
10  -1  10  55  -1  1848  100  1  957
11  -1  10  56  -1  588  101  1  2100
12  -1  12  57  -1  276  102  -1  102
13  -1  36  58  1  165  103  -1  2052
14  -1  40  59  1  1260  104  -1  1950
15  -1  14  60  -1  1848  105  -1  1260
16  1  15  61  -1  2040  106  -1  5964
17  1  3  62  -1  62  107  -1  13860
18  1  3  63  -1  15640  108  1  54366
19  1  15  64  1  2040  109  1  10
20  1  77  65  1  424  110  -1  10
21  1  12  66  -1  966  111  -1  2310
22  -1  12  67  -1  1476  112  -1  720
23  -1  12  68  -1  56  113  -1  3738
24  1  4  69  -1  232  114  1  1938
25  1  4  70  -1  14  115  1  112
26  1  36  71  -1  14  116  -1  92820
27  1  48  72  1  6840  117  -1  11220
28  1  6  73  1  406  118  -1  5520
29  1  24  74  -1  390  119  -1  60060
30  -1  210  75  -1  780  120  -1  14280
31  -1  4  76  -1  192  121  -1  1680
32  -1  4  77  -1  228  122  1  6240
33  -1  180  78  -1  32130  123  1  22383900
34  -1  210  79  -1  390  124  -1  820820
35  -1  420  80  1  630  125  -1  215460
36  1  120  81  1  72  126  -1  9360
37  1  37  82  1  2728  127  -1  17160
38  -1  12  83  1  6138  128  1  68640
39  -1  12  84  1  152  129  1  47888
40  -1  40  85  1  6669  130  -1  7276
41  -1  1980  86  -1  31920  131  -1  508
42  -1  414  87  -1  400  132  -1  6720
43  -1  42  88  1  192  133  -1  4914
44  1  580  89  1  14616  134  -1  1560
45  1  168  90  1  18585  135  -1  11752
46  -1  1120  91  1  25080  136  1  3045

For 1 ≤ k < n we have

π_{α,n−1}(k) = π_{α,n}(k + 1) ≡ (1 − (k + 1))π_{α,n}(n) = −kπ_{α,n}(n) (mod n).

Thus for r ≥ 1 we have π_{α,n−1}^{r}(k) ≡ k(−π_{α,n}(n))^{r} (mod n). The length of the orbit of k under π_{α,n−1} divides ord(−π_{α,n}(n) mod n), and in particular the orbit of 1 has length equal to ord(−π_{α,n}(n) mod n). This proves that ord(π_{α,n−1}) = ord(−π_{α,n}(n) mod n).

For notational convenience, set x = −π_{α,n}(n). Now from

π_{α,n}(k) ≡ (1 − k)π_{α,n}(n) = (k − 1)x (mod n)

it is readily seen by induction that for R ≥ 0 we have

π_{α,n}^{R}(k) ≡ kx^{R} − (x + x^{2} + ⋯ + x^{R}) (mod n).  (3)

Let r be the least positive integer for which ∀k (π_{α,n}^{r}(k) = k), i.e., let r be the least common multiple of the length of the orbits of π_{α,n}. We must show that r = ord(x mod gn).

Define the integer γ by gγ = x − 1, and note that gcd(γ, n) = 1. We may rearrange Eq. (3), setting R = r, as

\frac{x^{r} − 1}{x − 1} ≡ (k − 1)(x^{r} − 1) (mod n),  (4)

the division being real, not modular. With k = 1, Eq. (4) becomes 0 ≡ \frac{x^{r}−1}{x−1} = \frac{x^{r}−1}{gγ} (mod n), which holds iff \frac{x^{r}−1}{g} ≡ 0 (mod n). This, in turn, holds iff there is an integer β with βn = \frac{x^{r}−1}{g}, i.e., βng = x^{r} − 1. Thus r is a multiple of ord(x mod gn), and in particular r ≥ ord(x mod gn).

We claim that ∀k (π_{α,n}^{ord(x mod gn)}(k) = k), so that r ≤ ord(x mod gn), which will conclude the proof. We have

\frac{x^{ord(x mod gn)} − 1}{x − 1} = \frac{βgn}{gγ} = \frac{βn}{γ}

and

(k − 1)(x^{ord(x mod gn)} − 1) ≡ 0 (mod n),

so that substituting r = ord(x mod gn) into Eq. (4) we write \frac{βn}{γ} ≡ 0 (mod n), which holds for all k since gcd(γ, n) = 1. Thus r ≤ ord(x mod gn).

For quadratic irrationals one can easily identify the convergents and intermediate fractions and, if the denominators have enough structure, explicitly compute ord(π_{α,n}) when n or n + 1 is such a denominator. We have for example

Corollary 3.2.1. Let ϕ = \frac{\sqrt{5}−1}{2}, and f_{n} be the n-th Fibonacci number. Then for n ≥ 2,

ord(π_{ϕ,−1+f_{2n}}) = ord(π_{ϕ,f_{2n}}) = 2

and

ord(π_{ϕ,−1+f_{2n+1}}) = ord(π_{ϕ,f_{2n+1}}) = 4.

Proof. From the continued fraction expansion of ϕ we know that π_{ϕ,f_{2n}}(f_{2n}) = f_{2n} and π_{ϕ,f_{2n}}(1) = f_{2n−1}. The identity f_{2n−1}^{2} − f_{2n}f_{2n−2} = 1 shows that ord(f_{2n−1} mod f_{2n}) = 2 for n ≥ 2, whence by Theorem 3.1(i) we have ord(π_{ϕ,−1+f_{2n}}) = ord(π_{ϕ,f_{2n}}) = 2.

The continued fraction expansion of ϕ also tells us π_{ϕ,f_{2n+1}}(1) = f_{2n+1} and π_{ϕ,f_{2n+1}}(f_{2n+1}) = f_{2n}. The identity f_{2n}^{2} − f_{2n+1}f_{2n−1} = −1 shows ord(−f_{2n} mod f_{2n+1}) = 4 for n ≥ 2, whence by Theorem 3.1(ii), ord(π_{ϕ,−1+f_{2n+1}}) = 4.

We defined g to be the least positive integer such that gcd (f_{2n+1}, \frac{f_{2n}+1}{g}) = 1. In particular, g|f_{2n} + 1, and so the identity

(−f_{2n})^{4} − 1 = f_{2n−1}(f_{2n} − 1)f_{2n+1}(f_{2n} + 1) ≡ 0 (mod gf_{2n+1})

shows that ord(−f_{2n} mod gf_{2n+1}) divides 4, and the identity (−f_{2n})^{2} − f_{2n+1}f_{2n−1} = −1 shows that

ord(−f_{2n} mod gf_{2n+1}) ≥ ord(−f_{2n} mod f_{2n+1}) = 4,

whence ord(−f_{2n} mod gf_{2n+1}) = 4 and by Theorem 3.1(ii), ord(π_{ϕ,f_{2n+1}}) = 4.

3.3 The Sign of the Permutation

Recall that a k-cycle is even exactly if k is odd. We define ρ(n, k) to be the (n − k)-cycle

ρ(n, k) := (n, n − 1, …, k + 1) = (n, n − 1)(n − 1, n − 2) ⋯ (k + 2, k + 1).

Define also

B_{α}(k) := #{q: 1 ≤ q < k, {qα} < {kα}},

which counts the integers in [1, k) that are ‘better’ denominators for approximating α from below. Clearly,

π_{α,n} = π_{α,n−1} ρ(n, B_{α}(n))

= ρ(1, B_{α}(1)) ρ(2, B_{α}(2)) … ρ(n, B_{α}(n))

= ∏_{k=1}^{n} ρ(k, B_{α}(k))

so that π_{α,n} is the product of ∑_{k=1}^{n}(k − B_{α}(k) − 1) transpositions. We will show that for k odd, B_{α}(k) ≡ 0 (mod 2), which will be used to demonstrate that sgn(π_{α,2n}) = sgn(π_{α,2n+1}).

Our proof of Lemma 3.3.1 is similar in spirit to Sós’s proof of Lemma 3.1.1.

Lemma 3.3.1. For k ≥ 3 and 0 < α < 1/2, α irrational, B_{α}(k) + B_{1−α}(k) = k − 1, and

B_{α}(k) − 2B_{α}(k − 1) + B_{α}(k − 2) = \begin{cases}1 − k, & \{kα\} ∈ [0, α); \\ k − 1, & \{kα\} ∈ [α, 2α); \\ 0, & \{kα\} ∈ [2α, 1). \end{cases}

Proof. Observe that 0 < {qα} < {kα} iff {k(1 − α)} < {q(1 − α)} < 1, so that q with 1 ≤ q < k is in either the set {q : 1 ≤ q < k, {qα} < {kα}} or in the set {q : 1 ≤ q < k, {q(1 − α)} < {k(1 − α)}}, and is not in both. Thus, B_{α}(k) + B_{1−α}(k) = k − 1.

We think of the points 0, {α}, …, {kα} as lying on a circle with circumference 1, and labeled P_{0}, P_{1}, …, P_{k}, respectively, i.e., P_{j} := \frac{1}{2π} e^{2πjα\sqrt{−1}} = \frac{1}{2π} e^{2π\{jα\}\sqrt{−1}}. “The arc \overline{P_{i}P_{j}}” refers to the half-open counterclockwise arc from P_{i} to P_{j}, containing P_{i} but not P_{j}. We say that three distinct points A, B, C are in order if B ∉ \overline{CA}. We say that A, B, C, D are in order if both A, B, C and C, D, A are in order. Essentially, if when moving counter-clockwise around the circle starting from A, we encounter first the point B, then C, then D, and finally A (again), then A, B, C, D are in order.

By rotating the circle so that P_{i} ↦ P_{i+1} (0 ≤ i ≤ k), we find that each P on the arc \overline{P_{k−2}P_{k−1}} is rotated onto a P on the arc \overline{P_{k−1}P_{k}}. Specifically, the number of P_{0}, P_{1}, …, P_{k−2} on \overline{P_{k−2}P_{k−1}} is the same as the number of P_{1}, P_{2}, …, P_{k−1} on \overline{P_{k−1}P_{k}}. Set

X := {P_{0}, P_{1}, …, P_{k−2}} and Y := {P_{1}, P_{2}, …, P_{k−1}},

so that what we have observed is

|X ∩ \overline{P_{k−2}P_{k−1}}| = |Y ∩ \overline{P_{k−1}P_{k}}| .  (5)

Also, we will use

B_{α}(k) = |Y ∩ \overline{P_{0}P_{k}}| .

Now, first, suppose that {kα} ∈ [0, α), so that the points P_{0}, P_{k}, P_{k−2}, P_{k−1} are in order on the circle. We have

X ∩ \overline{P_{k−2}P_{k−1}} = X ∩ (\overline{P_{0}P_{k−1}} \ \overline{P_{0}P_{k−2}})
= (X ∩ \overline{P_{0}P_{k−1}}) \ (X ∩ \overline{P_{0}P_{k−2}})
|X ∩ \overline{P_{k−2}P_{k−1}}| = |(X ∩ \overline{P_{0}P_{k−1}})| − |(X ∩ \overline{P_{0}P_{k−2}})|
= (B_{α}(k − 1) + 1) − (B_{α}(k − 2) + 1)
= B_{α}(k − 1) − B_{α}(k − 2),

and similarly

Y ∩ \overline{P_{k−1}P_{k}} = (Y ∩ \overline{P_{k−1}P_{0}}) ∪ (Y ∩ \overline{P_{0}P_{k}})
= (Y \ (Y ∩ \overline{P_{0}P_{k−1}})) ∪ (Y ∩ \overline{P_{0}P_{k}})
|Y ∩ \overline{P_{k−1}P_{k}}| = (|Y | − |Y ∩ \overline{P_{0}P_{k−1}}|) + |Y ∩ \overline{P_{0}P_{k}}|
= (k − 1 − B_{α}(k − 1)) + B_{α}(k)
= B_{α}(k) − B_{α}(k − 1) − (1 − k),

so that Eq. (5) becomes B_{α}(k − 1) − B_{α}(k − 2) = B_{α}(k) − B_{α}(k − 1) − (1 − k), as claimed in the statement of the theorem.

Now suppose that {kα} ∈ [α, 2α), so that the points P_{0}, P_{k−1}, P_{k}, P_{k−2} are in order. By arguing as in the above case, we find

X ∩ \overline{P_{k−2}P_{k−1}} = (X \ (X ∩ \overline{P_{0}P_{k−2}})) ∪ (X ∩ \overline{P_{0}P_{k−1}}) ,

and so |X ∩ \overline{P_{k−2}P_{k−1}}| = B_{α}(k − 1) − B_{α}(k − 2) + (k − 1). Likewise,

Y ∩ \overline{P_{k−1}P_{k}} = (Y ∩ \overline{P_{0}P_{k}}) \ (Y ∩ \overline{P_{0}P_{k−1}})

so that |Y ∩ \overline{P_{k−1}P_{k}}| = B_{α}(k)−B_{α}(k−1). Thus, in this case Eq. (5) becomes B_{α}(k−1)−B_{α}(k−2)+(k−1) = B_{α}(k) − B_{α}(k − 1), as claimed in the statement of the theorem.

Finally, suppose that {kα} ∈ [2α, 1), so that the points P_{0}, P_{k−2}, P_{k−1}, P_{k} are in order. We find

X ∩ \overline{P_{k−2}P_{k−1}} = (X ∩ \overline{P_{0}P_{k−1}}) \ (X ∩ \overline{P_{0}P_{k−2}})

and |X ∩ \overline{P_{k−2}P_{k−1}}| = B_{α}(k − 1) − B_{α}(k − 2). Also,

Y ∩ \overline{P_{k−1}P_{k}} = (Y ∩ \overline{P_{0}P_{k}}) \ (Y ∩ \overline{P_{0}P_{k−1}})

and so |Y ∩ \overline{P_{k−1}P_{k}}| = B_{α}(k)−B_{α}(k−1). As claimed, we have B_{α}(k−1)−B_{α}(k−2) = B_{α}(k)−B_{α}(k−1).

Lemma 3.3.2 makes explicit the connection between Lemma 3.3.1, arithmetic properties of B_{α}, and the permutation π_{α,n}.

Lemma 3.3.2. Let α ∈ (0, 1) be irrational and n ∈ ℤ^{+}. If k is odd, then B_{α}(k) is even. If k is even, then B_{α}(k) ≡ ⌊kα⌋ + 1 (mod 2).

Proof. By Lemma 3.3.1, B_{α}(k) + B_{1−α}(k) = k − 1. Thus for odd k, B_{α}(k) + B_{1−α}(k) is even, and so either both B_{α}(k) and B_{1−α}(k) are even or both are odd. This means that, for odd k, without loss of generality we may assume that 0 < α < \frac{1}{2}.

Reducing the recurrence relation in Lemma 3.3.1 modulo 2, under the hypothesis that k is odd, we find that B_{α}(k) ≡ B_{α}(k − 2) (mod 2). Since B_{α}(1) = 0, we see that B_{α}(k) ≡ 0 (mod 2) for all odd k.

Now suppose that k is even and 0 < α < \frac{1}{2}. The recurrence relation in Lemma 3.3.1 reduces to

B_{α}(k) + B_{α}(k − 2) ≡ [[{kα} ∈ [0, 2α)]] (mod 2).

Set β = 2α, k = 2ℓ and B′(i) = B_{α}(2i). We have

B_{α}(k) = B_{α}(2ℓ) = B′(ℓ)

≡ B′(ℓ − 1) + [[{ℓβ} ∈ [0, β)]] (mod 2)

≡ B′(1) + ∑_{i=2}^{ℓ}[[{iβ} ∈ [0, β)]] (mod 2)

= B_{α}(2) + ⌊ℓβ⌋

= 1 + ⌊2ℓα⌋ = 1 + ⌊kα⌋ ,

since ∑_{i=2}^{ℓ}[[{iβ} ∈ [0, β)]] (with β ∈ (0, 1)) counts the integers in the interval (β, ℓβ]. This proves the lemma for 0 < α < \frac{1}{2} and k even.

Now suppose that k is even and \frac{1}{2} < α < 1. By Lemma 3.3.1, B_{α}(k) = k − 1 − B_{1−α}(k) ≡ 1 + B_{1−α}(k) (mod 2). By the argument (for 0 < α < \frac{1}{2}) given above, B_{1−α}(k) ≡ 1 + ⌊k(1 − α)⌋ (mod 2). We have

B_{α}(k) ≡ ⌊k(1 − α)⌋ (mod 2)
= k − ⌊kα⌋ − {k(1 − α)} − {kα}
≡ ⌊kα⌋ + 1 (mod 2),

where we have used {k(1 − α)} + {kα} = 1 (since α is irrational).

Proof of Theorem 1.3. We have π_{α,2n+1} = π_{α,2n} ρ(2n+1, B_{α}(2n+1)). The permutation ρ(2n+1, B_{α}(2n+1)) is the product of 2n + 1 − B_{α}(2n + 1) − 1 transpositions, which is an even number by Lemma 3.3.2. Thus sgn(π_{α,2n+1}) = sgn(π_{α,2n}).

By Lemma 3.3.2, for all integers k

k − B_{α}(k) + 1 ≡ \{ \begin{matrix}0, & k odd; \\ ⌊kα⌋ , & k even. \end{matrix}

Since the sign of the permutation ρ(k, B_{α}(k)) is (−1)^{k−B_{α}(k)} and (−1)^{2n} = 1, we have

sgn(π_{α,2n}) = (−1)^{2n} sgn (∏_{k=1}^{2n} ρ(k, B_{α}(k))) = ∏_{k=1}^{2n}(−1) sgn (ρ(k, B_{α}(k)))

= ∏_{k=1}^{2n}(−1)(−1)^{k−B_{α}(k)} = ∏_{k=1}^{2n}(−1)^{k−B_{α}(k)+1} = ∏_{ℓ=1}^{n}(−1)^{⌊2ℓα⌋}.

4 Unanswered Questions

The most significant question we have been unable to answer is why the matrices formed from Sturmian words in Section 2 lie in a common representation of S_{n}. We made two choices with little motivation: we ordered the factors anti-lexicographically; and we subtracted the last factor from the others. What happens if we order the factors differently, or subtract the second factor from the others? Understanding why the structure revealed in Section 2 exists might allow us to predict other phenomena.

Lucas Wiman [personal communication] has proved that

\{M_{n−1} (\frac{c}{n}) : gcd(c, n) = 1\}

is isomorphic to the multiplicative group modulo n, and asks if this is the largest subset of {M_{n−1}(α): 0 < α < 1} that is a group.

We have shown that the volume of the simplex F_{n}(α) is independent of α. When are two such simplices actually congruent?

Conjecture: For α, β ∈ (0, 1) be irrational, F_{n}(α) ≅ F_{n}(β) (as simplices) iff F_{n}(α) = F_{n}(β) or F_{n}(α) = F_{n}(1 − β).

We have verified this conjecture for n ≤ 20 by direct computation. At least, can any such simplex be cut and reassembled (in the sense of Hilbert’s 3rd Problem: see Eves [Eve72] for the basic theory and Sydler [Syd65] for a complete characterization) into the shape of another?

While we have identified the matrix M_{n}(α), there are many interesting questions that we remain unable to answer. We don’t believe that there is a bound on ∑_{n=1}^{N} det(M_{n}(α)) = ∑_{n=1}^{N} sgn(π_{α,n}) that is independent of N, but this sum must grow very slowly. We suspect that

|∑_{n=1}^{N} sgn(π_{α,n})| ≪ log N

for almost all α. For example, with α = \frac{\sqrt{5}−1}{2} and N < e^{13} ≈ 442413,

|∑_{n=1}^{N} sgn(π_{α,n})| < 10.

In Section 3.1 we showed that ord(π_{α,n}) is regularly extremely small relative to the average order of a permutation on n symbols. For each irrational α, are there infinitely many values of n for which ord(π_{α,n}) is exceptionally large?

One might hope for an explicit formula for ord(π_{α,n}) in terms of the base-α Ostrowski expansion of n, but this seems to be extremely difficult. Are metric results more approachable? Specifically, what is the distribution of ord(π_{α,n}) and sgn(π_{α,n}) for α taken uniformly from (0, 1)?

Since ord(π_{α,n}) appears to vary wildly, it may be advantageous to consider its average behavior. Can one give an asymptotic expansion of ∑_{n=1}^{N} ord(π_{α,n})? What can be said about I(n) := ∫_{0}^{1} ord(π_{α,n}) dα? Surprisingly, although I(n) seems to be rapidly increasing, it is not monotonic, e.g., I(35) > I(36) > I(37). Is this the ‘law of small numbers,’ or are there infinitely many values of n for which I(n + 1) > I(n)? We are not aware of any non-trivial bounds, upper or lower, on I(n). Figure 1 shows I(n) for 1 ≤ n ≤ 60.

B_{α} is an interesting function in its own right. We gave a formula for B_{α}(n) (mod 2) in Lemma 3.3.2. Is it possible to give a nice formula for B_{α}(n) for other moduli? It seems likely that there are arbitrarily large integers which are not in the range of B_{α}, although we have been unable to show that it does not contain

n I(n)This picture omitted from the DVI file only! Download PS or PDF file to view picture
Figure 1: I(n) for 1 ≤ n ≤ 60

all nonnegative integers. For example, B_{(\sqrt{5}−3)/2}(k) ≠ 3, B\sqrt{2}(k) ≠ 7 and B_{e^{−1}}(k) ≠ 23 for k ≤ 10^{7}. It is perhaps noteworthy that the least k for which B_{e^{−1}}(k) = 25 is k = 22154, a reminder that B_{α} can take new, small values even at large k. From the theory of continued fractions we know that there are infinitely many k for which B_{α}(k) = 0. Is there an x ≠ 0 and irrational α for which there are infinitely many k such that B_{α}(k) = x?

Acknowledgements

I am grateful to Horacio Porta & Kenneth B. Stolarsky for bringing M_{n}(α) to my attention, and for making their conjectures and data available. I also wish to thank my thesis advisor, Kenneth B. Stolarsky, for his guidance and careful reading, and Lucas Wiman for his many probing questions and suggestions.

References

[AB98] Pascal Alessandri and Valérie Berthé. Three distance theorems and combinatorics on words. Enseign. Math. (2), 44(1-2):103–132, 1998.

[Bro93] Tom C. Brown. Descriptions of the characteristic sequence of an irrational. Canad. Math. Bull., 36(1):15–21, 1993.

[BS79] David W. Boyd and J. Michael Steele. Monotone subsequences in the sequence of fractional parts of multiples of an irrational. J. Reine Angew. Math., 306:49–59, 1979.

[Coo02] Joshua N. Cooper. Quasirandom permutations. arXiv:math.CO/0211001, 2002.

[Eve72] Howard Eves. A survey of geometry. Allyn and Bacon Inc., Boston, Mass., revised edition, 1972.

[Lot02] M. Lothaire. Algebraic Combinatorics on Words. Cambridge University Press, Cambridge, U.K., first edition, 2002. Currently available online at http://www-igm.univ-mlv.fr/~berstel/

       Lothaire/.

[Sag01] Bruce E. Sagan. The symmetric group. Springer-Verlag, New York, second edition, 2001. Representations, combinatorial algorithms, and symmetric functions.

[Sch84] Johannes Schoißengeier. On the discrepancy of (nα). Acta Arith., 44(3):241–279, 1984.

[Sen95] Marjorie Senechal. Quasicrystals and geometry. Cambridge University Press, Cambridge, 1995.

[Sla67] Noel B. Slater. Gaps and steps for the sequence nθ mod 1. Proc. Cambridge Philos. Soc., 63:1115– 1123, 1967.

[Sós57] Vera T. Sós. A lánctörtek egy geometriai interpretációja és alkalmazásai [On a geometrical theory

of continued fractions]. Mat. Lapok, 8:248–263, 1957.

[Sto76] Kenneth B. Stolarsky. Beatty sequences, continued fractions, and certain shift operators. Canad. Math. Bull., 19(4):473–482, 1976.

[Syd65] J.-P. Sydler. Conditions nécessaires et suffisantes pour l’équivalence des polyèdres de l’espace euclidien à trois dimensions. Comment. Math. Helv., 40:43–80, 1965.

[Tij00] R. Tijdeman. Exact covers of balanced sequences and Fraenkel’s conjecture. In Algebraic number theory and Diophantine analysis (Graz, 1998), pages 467–483. de Gruyter, Berlin, 2000.