Arithmetic properties of exceptional lattice paths
For a fixed real number ρ > 0, let L be an affine line of slope ρ ⁻¹ in R ² . We show that the closest approximation of L by a path P in Z ² is unique, except in one case, up to integral translation. We study this exceptional case. For irrational ρ, the projection of P to L yields two q...
Збережено в:
| Дата: | 2006 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2006
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/157386 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Arithmetic properties of exceptional lattice paths / W. Rump // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 3. — С. 101–118. — Бібліогр.: 16 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-157386 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1573862019-06-21T01:27:52Z Arithmetic properties of exceptional lattice paths Rump, W. For a fixed real number ρ > 0, let L be an affine line of slope ρ ⁻¹ in R ² . We show that the closest approximation of L by a path P in Z ² is unique, except in one case, up to integral translation. We study this exceptional case. For irrational ρ, the projection of P to L yields two quasicrystallographic tilings in the sense of Lunnon and Pleasants [5]. If ρ satisfies an equation x ² = mx + 1 with m ∈ Z, both quasicrystals are mapped to each other by a substitution rule. For rational ρ, we characterize the periodic parts of P by geometric and arithmetic properties, and exhibit a relationship to the hereditary algebras Hρ(K) over a field K introduced in a recent proof of a conjecture of Ro˘ıter. 2006 Article Arithmetic properties of exceptional lattice paths / W. Rump // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 3. — С. 101–118. — Бібліогр.: 16 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 05B30, 11B50; 52C35, 11A0 http://dspace.nbuv.gov.ua/handle/123456789/157386 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
For a fixed real number ρ > 0, let L be an affine
line of slope ρ
⁻¹
in R
²
. We show that the closest approximation of
L by a path P in Z
²
is unique, except in one case, up to integral
translation. We study this exceptional case. For irrational ρ, the
projection of P to L yields two quasicrystallographic tilings in the
sense of Lunnon and Pleasants [5]. If ρ satisfies an equation x
² =
mx + 1 with m ∈ Z, both quasicrystals are mapped to each other
by a substitution rule. For rational ρ, we characterize the periodic
parts of P by geometric and arithmetic properties, and exhibit
a relationship to the hereditary algebras Hρ(K) over a field K
introduced in a recent proof of a conjecture of Ro˘ıter. |
| format |
Article |
| author |
Rump, W. |
| spellingShingle |
Rump, W. Arithmetic properties of exceptional lattice paths Algebra and Discrete Mathematics |
| author_facet |
Rump, W. |
| author_sort |
Rump, W. |
| title |
Arithmetic properties of exceptional lattice paths |
| title_short |
Arithmetic properties of exceptional lattice paths |
| title_full |
Arithmetic properties of exceptional lattice paths |
| title_fullStr |
Arithmetic properties of exceptional lattice paths |
| title_full_unstemmed |
Arithmetic properties of exceptional lattice paths |
| title_sort |
arithmetic properties of exceptional lattice paths |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2006 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/157386 |
| citation_txt |
Arithmetic properties of exceptional lattice paths / W. Rump // Algebra and Discrete Mathematics. — 2006. — Vol. 5, № 3. — С. 101–118. — Бібліогр.: 16 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT rumpw arithmeticpropertiesofexceptionallatticepaths |
| first_indexed |
2025-07-14T09:49:26Z |
| last_indexed |
2025-07-14T09:49:26Z |
| _version_ |
1837615354914799616 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Number 3. (2006). pp. 101 – 118
c© Journal “Algebra and Discrete Mathematics”
Arithmetic properties of exceptional lattice paths
Wolfgang Rump
Communicated by V. V. Kirichenko
Dedicated to the memory of Vitaliy M. Usenko
Abstract. For a fixed real number ρ > 0, let L be an affine
line of slope ρ−1 in R2. We show that the closest approximation of
L by a path P in Z2 is unique, except in one case, up to integral
translation. We study this exceptional case. For irrational ρ, the
projection of P to L yields two quasicrystallographic tilings in the
sense of Lunnon and Pleasants [5]. If ρ satisfies an equation x2 =
mx + 1 with m ∈ Z, both quasicrystals are mapped to each other
by a substitution rule. For rational ρ, we characterize the periodic
parts of P by geometric and arithmetic properties, and exhibit
a relationship to the hereditary algebras Hρ(K) over a field K
introduced in a recent proof of a conjecture of Rŏıter.
Introduction
Let Z2 be the standard lattice in the real Euclidean space R2. We define
a lattice path to be a subset P := {vn | n ∈ Z} of Z2 such that each
difference vn+1 − vn is one of the unit vectors e1 =
(
1
0
)
or e2 =
(
0
1
)
.
For an affine line L in R2 of non-negative or infinite slope, let d(v, L)
denote the distance between v ∈ Z2 and L. There is always a lattice
path P = {vn | n ∈ Z} such that the approximation of L by P cannot be
improved. This means that each lattice path {v′n |n ∈ Z} with d(v′n, L) 6
d(vn, L) for all n satisfies d(v′n, L) = d(vn, L) for all n. If P is unique,
we call P the best approximation of L. Which lines L admit a best
approximation? Of course, the answer will be the same if L is replaced
by L + v with a translation vector v ∈ Z2.
2000 Mathematics Subject Classification: 05B30, 11B50; 52C35, 11A07.
Key words and phrases: Lattice path, uniform enumeration, quasicrystal.
102 Arithmetic properties of exceptional lattice paths
Our first result (Proposition 1) states that for any ρ ∈ [0,∞], there is,
up to an integral translation, exactly one line L of slope ρ−1 which does
not admit a best approximation by a lattice path. It is this exceptional
case on which we focus our attention in this paper. If L is a horizontal or
vertical line, the exception clearly occurs when L has distance 1
2
from Z2.
So let us consider the (essentially unique) exceptional line L of positive
slope ρ−1 ∈ R. Although the distance between L and Z2 can be arbitrarily
small in this case, there exists an integral translation that carries L to a
line which passes through the point O :=
(
1/2
1/2
)
.
It will be convenient to take the point O of L as a new origin, so
that Z2 is shifted to the affine lattice E with coordinates of the form
n + 1
2
, n ∈ Z. The points v ∈ E are the centers of the cells in Z2, i. e.
the translates of the closed unit square. So the set C of cells inherits
the structure of a two-dimensional lattice. Any sequence of cells in C
corresponding to a finite piece of a lattice path will be called a hook.
Let ρ be rational. Then the integral points on L form a lattice line in
Z2, and these are the only points where the infinitely many lattice paths
in E which form a closest approximation of L are ambiguous. So if we
remove the ambiguous points from these lattice paths, we get an infinite
sequence of finite pieces P which are equal up to translation. The hook
Hρ associated to P will be called rational. For any hook H, let ∂H denote
the boundary of the union
⋃
H of its cells. We show that a hook H is
rational if and only if the line that connects its extremal points intersects
∂H just in these two points (Theorem 1). If ρ = a
b with relatively prime
integers a, b > 0, the rational hook Hρ fits into a rectangle of length a
and height b.
Apart from this geometric description, we show that rational hooks
can be characterized by rather nice arithmetic properties. First, we show
that a hook H is rational if and only if its cells can be filled with posi-
tive numbers such that the row sums and the column sums are constant
(Theorem 2). All such numberings are proportional, and the minimal
row sum (column sum) is the length a (resp. the height b) of H. In the
minimal numbering, the cells with value 1 are exactly those which can be
removed so that the remaining cells make up one or two smaller rational
hooks (Theorem 4). Second, we characterize a rational hook Ha/b by the
existence of a unique enumeration of its cells from 1 to n so that the dif-
ference between two sucessive cells in the same row (column) is b (resp.
a) (Theorem 3).
If ρ is irrational, there are only two approximations of L by lattice
paths P+, P− that cannot be improved. Furthermore, these lattice paths
coincide except at one lattice point near O. The orthogonal projection
W. Rump 103
of P± to L yields two quasicrystallographic tilings X± of L in the sense
of [5], consisting of two tiles A and B. The tilings X± are of the form
Y ∗ABY respectively Y ∗BAY , where Y and Y ∗ are limits of increasing
filtrations of rational hooks. If ρ or ρ−1 is a quadratic unitary Pisot
number, i. e. a solution β > 1 of an equation
x2 = mx + d
with m ∈ N and |d| = 1, the tilings X± can be regarded as one-
dimensional cut-and-project quasicrystals, generated by a generalized
substitution rule in the sense of [7]. In the special case β ∈ {1
2
(1 +√
5), 1 +
√
2, 2 +
√
3}, the quasicrystals admit a unique quasiaddition
[1, 8]. For d = 1, we show that X+ and X− are mapped into each other
by the substitution rule A 7→ AmB, B 7→ A.
Rational hooks occurred in a quite different context. During the past
decades, representations of partially ordered sets have played a vital rôle
in the representation theory of finite dimensional algebras and orders over
a Dedekind domain. For a finite poset Ω, Nazarova and Rŏıter [9, 11]
introduced a norm ‖Ω‖ such that Ω is representation-finite if and only if
‖Ω‖ > 1
4
and tame if and only if ‖Ω‖ = 1
4
. In a recent paper [10], they
define a P-faithful poset to be a non-empty poset Ω such that ‖Ω′‖ > ‖Ω‖
holds for every proper subset Ω′. They prove that Klĕıner’s celebrated
list of critical posets [3] consists in the P-faithful posets of norm 1/4.
Zeldich [14, 15, 16] and Sapelkin [13] proved Rŏıter’s conjecture [10] which
explicitely describes the connected P-faithful posets, hence all P-faithful
posets.
In [12] we generalize Rŏıter’s norm to arbitrary vector space K-
categories over a field K and show that the above mentioned results hold
in this broader context. Relating P-faithful posets to a class of hereditary
algebras of type An, we give a rather short proof of Rŏıter’s conjecture. In
particular, we parametrize connected P-faithful posets by rational num-
bers ρ > 1. In the terminology of the present paper, the P-faithful posets
are just the posets associated to rational hooks Hρ. Thus every rational
hook Hρ corresponds to a hereditary K-algebra Hρ(K), and some of the
arithmetic properties of Hρ are reflected by the representation theory of
Hρ(K) (see [12], §7).
For irrational ρ > 0, an infinite dimensional hereditary algebra Hρ(K)
of type A∞
∞ can be defined analoguously. Then the finitely generated
indecomposable preprojective Hρ(K)-modules can be parametrized by
the positive numbers in Z + Zρ. For example, if ρ = τ := 1
2
(1 +
√
5), the
preprojective component of Hρ(K) looks as follows:
104 Arithmetic properties of exceptional lattice paths
...
...
...
...
[3 − τ 4 τ + 5 2τ + 6 · · ·
[2 − τ
→
3
→→
τ + 4
→→
2τ + 5
→→
3τ + 6
→
[2
→→
τ + 3
→→
2τ + 4
→→
3τ + 5
→→
· · ·
[1
→
τ + 2
→→
2τ + 3
→→
3τ + 4
→→
4τ + 5
→
[τ + 1
→→
2τ + 2
→→
3τ + 3
→→
4τ + 4
→→
· · ·
[τ
→
2τ + 1
→→
3τ + 2
→→
4τ + 3
→→
5τ + 4
→
[τ − 1
→
2τ
→→
3τ + 1
→→
4τ + 2
→→
5τ + 3
→→
· · ·
[2τ − 1
→→
3τ
→→
4τ + 1
→→
5τ + 2
→→
6τ + 3
→
...
...
...
...
The indecomposable projective Hρ(K)-modules, marked by a left bracket
“[”, are connected by two kinds of arrows, “ր” or “ց”, according to the
tiling of the associated quasicrystal X+. Note that the greater difference
τ between the values of two adjacent projectives corresponds to a short
tile, while the smaller difference 1 indicates a long tile of X+. The mirror-
image X−of X+ corresponds to the modified algebra H−
ρ (K), with a
projective of value 0 instead of that with value τ + 1.
1. Approximation of affine lines
Let ρ, δ be real numbers with ρ > 0. By Lρδ we denote the affine line
ρy − x = δ (1.1)
in the real vector space R2. We consider the lattice Z2 ⊂ R2 generated by
the unit vectors e1 :=
(
1
0
)
and e2 :=
(
0
1
)
. A sequence (vn)n∈Z of vectors
vn ∈ Z2 will be called a lattice path if the difference vn+1−vn of successive
vectors is either e1 or e2. Up to a shift n 7→ n + k, such a sequence is
determined by its underlying set P := {vn | n ∈ Z}. Therefore, by a
slight abuse, the subset P ⊂ Z2 will also be referred to as a lattice path.
Now let us define a minimal lattice path to be one which provides a best
approximation (in a sense to be made precise yet) of some line Lρδ.
If we regard R2 as a Euclidean space with orthonormal basis {e1, e2},
the vector
(−1
ρ
)
is orthogonal to Lρδ. Therefore, the distance d(v, Lρδ)
between any v =
(
x
y
)
∈ Z2 and Lρδ satisfies
√
1 + ρ2 · d(v, Lρδ) = |ρy − x − δ|. (1.2)
W. Rump 105
Now let v − e1, v, v + e2 be three successive vectors of a lattice path
P ⊂ Z2. If we replace v =
(
x
y
)
by v′ := v − e1 + e2 =
(
x−1
y+1
)
, we get
another lattice path P ′ with ρ(y+1)− (x−1)−δ = (ρy−x−δ)+(1+ρ).
Thus P ′ cannot approximate Lρδ better that P unless ρy − x− δ < 0. If
ρy − x − δ < 0, then d(v, Lρδ) < d(v′, Lρδ) holds if and only if v belongs
to
Pρδ :=
{(
x
y
)
∈ Z2
∣
∣
∣ |ρy − x − δ| < 1+ρ
2
}
. (1.3)
A similar statement applies when e1 and e2 are permuted. Therefore,
we define a best approximation of Lρδ to be a (necessarily unique) lattice
path P ⊂ Pρδ.
Proposition 1.. Let ρ, δ ∈ R with ρ > 0 be given. A best approximation
P of Lρδ exists if and only if
ρ−1
2
− δ 6∈ Z + ρZ. (1.4)
If the best approximation exists, it coincides with Pρδ.
Proof. By Eq. (1.3), we have
(
x
y
)
∈ Pρδ ⇔ ρy − δ − 1+ρ
2
< x < ρy − δ + 1+ρ
2
. (1.5)
So there is an open interval Iy of length 1 + ρ such that
(
x
y
)
∈ Pρδ ⇔ x ∈
Iy. Hence
(
x+1
y
)
∈ Pρδ ⇔ x + 1 ∈ Iy and
(
x
y+1
)
∈ Pρδ ⇔ x− ρ ∈ Iy. Thus
if v :=
(
x
y
)
∈ Pρδ and x + 1 6= ρy − δ + 1+ρ
2
, exactly one of the numbers
x − ρ and x + 1 belongs to Iy, i. e. either v + e1 ∈ Pρδ or v + e2 ∈ Pρδ.
This shows that Pρδ is a best approximation of Lρδ if the equation
x + 1 = ρy − δ + 1+ρ
2
(1.6)
has no solution
(
x
y
)
∈ Z2, and there is no best approximation if Eq. (1.6)
is solvable in Z2. Now the Diophantine equation (1.6) is not solvable if
and only if (1.4) holds. This completes the proof. �
Remark. By a translation
x 7→ x − x0 ; y 7→ y − y0 (1.7)
with x0, y0 ∈ Z, Eq. (1.1) becomes ρy−x = δ+(ρy0−x0). Therefore, the
problem to approximate Lρδ by a lattice path is turned into an equivalent
one if an arbitrary element of Z + ρZ is added to δ. So Proposition 1
shows that up to translation (1.7), there is just one exceptional value of
δ for which the best approximation of Lρδ does not exist, namely,
δ = ρ−1
2
. (1.8)
106 Arithmetic properties of exceptional lattice paths
Assume that (1.4) is satisfied. Then the orthogonal projection of the
lattice path Pρδ = {vn | n ∈ Z} to the line Lρδ yields a two-way infinite
sequence (v′n)n∈Z of points v′n ∈ Lρδ with
|v′n+1 − v′n| =
ρ√
1+ρ2
if vn+1 − vn = e1
1√
1+ρ2
if vn+1 − vn = e2.
So we get a one-dimensional quasicrystallographic tiling with two tiles in
the sense of [5], Definition 2. By [5], §4, two such quasicrystals X, X ′
with the same length ratio ρ of their tiles are in the same species, i. e.
every finite sequence of successive tiles in X has infinitely many copies
in X ′ which are asymptotically equally distributed. (In particular, this
property holds for X ′ = X.) The two-tile sequences (Tn)n∈Z with T ∈
{L, S} arising in this way (L = long, S = short) can also be characterized
by the property that the number of L’s in a word of length l can take
only two values [6].
2. The exceptional case
In the Euclidean space R2, the unit square Q is a fundamental domain
for the group of integral translations (1.7). The translates of the closed
unit square will be called cells of Z2.
For ρ > 0 and δ ∈ R as in Proposition 1, assume that there is no best
approximation of Lρδ. By the preceding remark, we can assume, without
loss of generality, that δ satisfies Eq. (1.8). Therefore, Eq. (1.6) takes
the simple form
x = ρy. (2.9)
For each solution v =
(
x
y
)
∈ Z2 of Eq. (2.9), there is a cell
v + e2 v + e1 + e2
v v + e1
in Z2, where v and v + e1 + e2 belong to Pρδ, while v + e1 and v + e2
are equally distant from Lρδ. So there exist approximations of Lρδ by
lattice paths that cannot be improved, but which are ambiguous at each
solution of Eq. (2.9).
If ρ is irrational, Eq. (2.9) has no integral solution except the trivial
one. Accordingly, there are two equally good approximations of Lρδ,
W. Rump 107
differing only at the origin. If the slope ρ−1 of Lρδ is the golden ratio
τ := 1+
√
5
2
, we get the example considered in [5], Fig. 4, a cut-and-project
quasicrystal of Fibonacci type, with acceptance window either [0, 1) or
(0, 1], according to the ambiguity at the origin.
In case ρ is rational, say, ρ = a
b with relatively prime integers a, b > 0,
the integral solutions of Eq. (2.9) form the lattice line Z
(
a
b
)
. So there are
infinitely many lattice paths giving approximations of Lρδ which cannot
be improved, but which are ambiguous at each v ∈ Z
(
a
b
)
. The situation
is illustrated by the following example with ρ = 8
3
.
b
b
b
b
b
b
b
b
b
b
Note that in the exceptional case (1.8), the vector
(
1/2
1/2
)
satisfies Eq.
(1.1). So it is convenient to shift the origin to
(
1/2
1/2
)
. Then the line Lρδ is
replaced by the subspace
Lρ := R
(
ρ
1
)
, (2.10)
and the lattice Z2 is changed into the affine lattice
E :=
{(
x
y
)
∈ R2
∣
∣ x + 1
2
, y + 1
2
∈ Z
}
. (2.11)
Accordingly, we set
Pρ :=
{(
x
y
)
∈ E
∣
∣
∣
(x+
1
2
y+
1
2
)
∈ Pρδ
}
=
{(
x
y
)
∈ E
∣
∣
∣ |ρy − x| < 1+ρ
2
}
. (2.12)
The elements of E are the centers v of the cells Q of Z2. Hence, via the
correspondence Q ↔ v, the set C of cells of Z2 becomes a lattice which
can be identified with E.
Proposition 2.. A vector v ∈ E belongs to Pρ if and only if Lρ intersects
the interior of the corresponding cell Q.
108 Arithmetic properties of exceptional lattice paths
Proof. Lρ intersects the interior of Q if and only if v − 1
2
e1 + 1
2
e2 and
v + 1
2
e1 − 1
2
e2 are on different sides of the line Lρ, i. e. if and only if
ρ(y + 1
2
)− (x− 1
2
) and ρ(y − 1
2
)− (x + 1
2
) have different sign. The latter
condition is equivalent to the inequality |ρy − x| < 1+ρ
2
. �
In the sequel, we consider the exceptional case (1.8) with ρ = a
b ∈ Q,
where the integers a, b > 0 are relatively prime. Then the solutions of
Eq. (2.9) coincide with the integral points n
(
a
b
)
on Lρ. At these points,
two cells of C touch the line Lρ, which causes the mentioned ambiguity
of the approximation. So Pρ consists of a sequence (Fn)n∈Z of finite
pieces Fn of a lattice path P in E, such that the translation v 7→ v +
(
a
b
)
carries Fn to Fn+1. Moreover, the Fn are separated by the integral points
n
(
a
b
)
∈ Lρ ∩ Z2, and at each n
(
a
b
)
, there are two choices to connect the
pieces Fn to a lattice path P . Up to translation, there is a unique subset
Hρ of C corresponding to Fn ⊂ E. We call Hρ a rational hook. For
example, the rational hook H8/3, together with the line L8/3, looks as
follows:
(2.13)
Remark. Proposition 2 shows that rational hooks can be obtained by
an extremely simple geometric construction. For any rational ρ > 0 with
reduced representation ρ = a
b , there is a path of a + b − 1 cells which
intersect a lattice line of slope ρ−1 properly, and these cells constitute
the rational hook Hρ.
Let us define a hook to be a finite subset H of C, consisting of a
non-empty sequence Q1, . . . , Qn of cells with the following property. If vi
denotes the center of Qi, then vi+1−vi ∈ {e1, e2} for all i ∈ {1, . . . , n−1}.
Thus a hook is just a finite version of a lattice path in C. Clearly, a hook
H is determined by the union
⋃
H of its cells. The boundary ∂H of
⋃
H
will be called the boundary of the hook H. Furthermore, we define the
interior line of H to be the open line segment which connects the lower
left corner of H with the upper right corner of H (see (2.13)). As an
immediate consequence of Proposition 2, we get
Theorem 1.. A hook H is rational if and only if its interior line does
not intersect the boundary ∂H.
Our next aim is to show that rational hooks can be obtained by an
equally simple arithmetic construction. If the cells of a hook H can be
filled with positive integers such that the row sums as well as the column
sums are constant, we call H a magic hook. For example, the rational
hook H8/3 is a magic one:
W. Rump 109
3 3 2
1 3 3 1
2 3 3
Here the row sums are 8, and the column sums are 3. In what follows,
the function which attaches a number to each cell of a magic hook will
be denoted by v.
Proposition 3.. For any pair a, b of positive integers, there is exactly
one magic hook with row sum a and column sum b.
Proof. We construct a magic hook H with row sum a and column
sum b, and show that such a hook must be unique. Let Q1, . . . , Qn be
the sequence of cells of H, ordered from the lower left to the upper right
corner of H. If a = b, there can be only one cell, and we are done.
If a > b, then n > 2, and the cells Q1 and Q2 cannot be in the same
column. Similarly, a < b implies that Q1 and Q2 cannot be in the same
row. Thus let us assume, without loss of generality, that a > b. Then
v(Q1) = b. Starting with r0 := 0, we define the sequences (ri)i∈N and
(qi)i∈N of integers recursively by the formula
a + ri = qib + ri+1, (2.14)
where 0 6 ri < b for all i. Thus a = q0b+r1. If r1 = 0, we get a hook of q0
cells in one row with v(Qi) = b for all i. Otherwise, the cells Q1, . . . , Qq0+1
are in one row, and v(Qi) = b for i 6 q0. As the row sum is a, we obtain
v(Qq0+1) = r1 > 0. Since the column sum is b, the cell Qq0+2 above Qq0+1
satisfies v(Qq0+2) = b − r1. Now Eq. (2.14) gives a + r1 = q1b + r2, that
is, (b− r1) + (q1 − 1)b + r2 = a. Therefore, the cells Qq0+2, . . . , Qq0+q1+1
are in the second row, with v(Qi) = b for i ∈ {q0 + 3, . . . , q0 + q1 + 1}.
If r2 = 0, the magic hook is finished. Otherwise, there is another cell
Qq0+q1+2 in the second row, with v(Qq0+q1+2) = r2, and the procedure
has to be continued as before.
It remains to be shown that the recursion (2.14) eventually stops. If
we add Eqs. (2.14) for i ∈ {0, . . . , i − 1}, we get
ia = (q0 + · · · + qi−1)b + ri. (2.15)
Hence ri ≡ i · a (mod b), which proves that rb = 0. �
If the numbering of a magic hook is multiplied by a fixed positive in-
teger, another magic numbering is obtained. Therefore, the magic hooks
of Proposition 3 only depend on the rational number ρ := a
b . Our next
result shows that all magic hooks are rational, and conversely, that every
rational hook admits a magic numbering.
110 Arithmetic properties of exceptional lattice paths
Theorem 2.. A hook is rational if and only if it admits a magic num-
bering.
Proof. Let ρ = a
b be a rational number with a, b > 0 relatively prime.
We show that the magic hook H ′
ρ with row sum a and column sum b, con-
structed via (2.14), coincides with the rational hook Hρ. By symmetry,
we can assume that a > b. If r1 = 0, then H ′
ρ consists of a single row of q0
cells, and H ′
ρ = Hρ. Otherwise, both H ′
ρ and Hρ start with a horizontal
sequence of q0 + 1 cells, followed by one step upwards. The line Q
(
a
b
)
contains the point
(
2ρ
2
)
, and Eq. (2.15) implies that 2ρ = q0 + q1 + r2
b .
Hence, if r2 = 0, the upward step is followed by q1 horizontal steps, and
the resulting magic hook is rational. If r2 > 0, another horizontal step
has to be added in H ′
ρ and also in Hρ, again followed by one step upwards.
︸ ︷︷ ︸
q0
︸ ︷︷ ︸
q1
︸ ︷︷ ︸
q2
In general, the equivalence of the geometric construction of Hρ and the
recursive construction of H ′
ρ via (2.14) results from Eq. (2.15), divided
by b:
i · ρ = (q0 + · · · + qi−1) + ri
b .
Note that ri
b < 1. Since
(
iρ
i
)
∈ Q
(
a
b
)
, we get H ′
ρ = Hρ. �
Corollary. Every rational hook is centrally symmetric.
Proof. If we apply a rotation with angle π to a rational hook Ha/b
with a, b > 0 relatively prime, we get another magic hook H with row
sum a and column sum b. Hence H = Ha/b. �
3. Uniform enumeration
In this section, we give a third characterization of rational hooks. Let H
be a hook with n cells. An enumeration of the cells from 1 to n defines
a bijection
f : H −→ {1, . . . , n}.
W call f a uniform enumeration if there are integers a, b > 0 such that
each pair of adjacent cells Q, Q′ satisfies f(Q′)− f(Q) = a if Q′ is below
Q and f(Q′)−f(Q) = b if Q′ is on the right of Q. The following example
W. Rump 111
displays a uniform enumeration of the rational hook H17/7.
7 14 21
4 11 18
1 8 15 22
5 12 19
2 9 16 23
6 13 20
3 10 17
Theorem 3..
(a) A hook is rational if and only if it admits a uniform enumeration.
(b) A rational hook has exactly one uniform enumeration.
(c) If Q is the lower left cell and Q′ the upper right cell of Ha/b, where
a, b > 0 are relatively prime, the uniform enumeration f of Ha/b
satisfies f(Q) = b and f(Q′) = a.
Proof. We make the affine lattice E into a partially ordered set, defin-
ing
(
x
y
)
6
(
x′
y′
)
:⇔ x 6 x′ and y > y′. (3.16)
Every hook H can also be regarded as a partially ordered set. For a
pair of cells Q, Q′ ∈ H, we write Q < Q′ if either Q and Q′ are in the
same row with Q′ on the right of Q, or they are in the same column
with Q′ below Q. If the cells of H are replaced by their centers, we
get a finite subposet Ω of E, unique up to translation. Then a magic
numbering of H is tantamount to a uniform vector v > 0 of Ω in the
sense of [12], §5. Similarly, a uniform enumeration of H is equivalent
to a uniform enumeration [12] of Ω. Therefore, part (a) and (b) of the
theorem follow by [12], Proposition 9. For te reader’s convenience, the
one-to-one correspondence between a magic numbering v and a uniform
enumeration f of H is given in Eqs. (3.17) below. For a cell Q ∈ H, we
denote the set of lower neighbours of Q by Q−.
v(Q) = f(Q) −
∑
Q′∈Q−
f(Q′) ; f(Q) =
∑
Q′6Q
v(Q′). (3.17)
To prove (c), note first that the rational hook Ha/b has a+b−1 cells. Let
Q1, . . . , Qa+b−1 be the sequence of cells of Ha/b, ordered from the lower
left to the upper right of Ha/b. If Qi and Qi+1 are in the same row, then
112 Arithmetic properties of exceptional lattice paths
f(Qi+1) = f(Qi)+b; if they are in the same column, f(Qi+1) = f(Qi)−a.
Hence
f(Qi+1) ≡ f(Qi) + b (mod a + b).
Since b is invertible modulo a+ b, and f(Qi) runs through all the residue
classes modulo a+b except 0, we infer that f(Q1)−b ≡ 0 ≡ f(Qa+b−1)+
b (mod a + b), which proves the claim. �
In the sequel, the partial ordering of a hook introduced in the above
proof will be assumed without further notice.
Corollary. Let v be a magic numbering of a hook H with at least two
rows and columns. Assume that the values of v are relatively prime. Then
there are exactly two cells Q of H with v(Q) = 1. These cells are related
by central symmetry.
Proof. By assumption, there are relatively prime integers a, b > 2
with H = Ha/b. Therefore, a cell Q of H with v(Q) = 1 must be either
minimal or maximal. (Since H has more than one cell, the sets of min-
imal respectively maximal cells are disjoint.) Let f denote the uniform
enumeration of H. By Eqs. (3.17), a minimal cell Q satisfies v(Q) = 1 if
and only if f(Q) = 1. Therefore, the corollary of Theorem 1 implies that
there are exactly two, centrally symmetric, cells Q of H which satisfy
v(Q) = 1. �
Next we give an explicit formula for the minimal magic numbering
v of a rational hook Hρ. Assume that ρ = a
b with a > b > 0 relatively
prime. For a minimal cell Q (with respect to the partial ordering of Hρ),
there is exactly one vertex
(
xQ
yQ
)
∈ Z2 strictly below the line Lρ, and this
property characterizes the minimal cells. Similarly, the maximal cells Q
have exactly one vertex strictly above Lρ (see (2.13)). If f denotes the
uniform enumeration of Hρ, we have v(Q) = f(Q) if and only if Q is
minimal. Thus, by symmetry, the minimal magic numbering is given by
the values f(Q) for minimal Q ∈ Hρ. Note that v(Q) = b if Q is neither
minimal nor maximal.
Proposition 4.. Let Ha/b be a rational hook with a, b > 0 relatively
prime, and let f be its uniform enumeration. Then
f(Q) = bxQ − ayQ (3.18)
holds for the minimal cells Q of Ha/b.
Proof. We use Eqs. (2.14) to determine the minimal cells Q1, . . . , Qb
of Ha/b, ordered from left to right. We have
xQi
= 1 +
i−2∑
j=0
qj ; yQi
= i − 1 (3.19)
W. Rump 113
for i ∈ {1, . . . , b}. For the maximal cells Q′
i below Qi (for i > 1), the
proof of Proposition 3 shows that v(Q′
i) = ri−1. Hence v(Qi) = b − ri−1,
which holds for all i ∈ {1, . . . , b}. So we get
bxQi
− ayQi
= b +
i−2∑
j=0
bqj − a(i − 1) =
= b +
i−2∑
j=0
(a + rj − rj+1) − a(i − 1) = b − ri−1 = v(Qi) = f(Qi).
�
4. Splitting of rational hooks and quasicrystals
In all what follows, for any rational hook H, we denote the minimal magic
numbering by v and the uniform enumeration by f . Let us call a cell Q
of H removable if H r {Q} is a disjoint union of (one or two) rational
hooks. The following theorem adds a converse to [12], Proposition 10,
which states that the cell Q ∈ H with f(Q) = 1 is removable. Using
Proposition 4, we give a simple geometric proof of this property.
Theorem 4. A cell Q of a rational hook H is removable if and only if
v(Q) = 1.
Proof. Assume that H = Ha/b with a, b > 0 relatively prime. If H has
only one row or column, every cell Q is removable and satisfies v(Q) = 1.
Thus let us assume, without loss of generality, that a > b > 2. The
proof of Proposition 3 shows that H is a union R1 ∪ · · · ∪ Rb of hooks
Ri, each with one row. By Eqs. (2.14), the hooks Ri with i < b consist
of qi + 1 cells, while Rb has qb cells. Therefore, each Ri consists of either
q0 + 1 or q0 + 2 cells. Since every rational hook is centrally symmetric
by the corollary of Theorem 1, a removable cell Q cannot be one of the
two ends of H and must be either maximal or minimal with respect to
the partial ordering of H, i. e. v(Q) < b. Now the right-hand side of Eq.
(3.18) can be written as a scalar product
(
b
−a
)
·
(
xQ
yQ
)
, where the vector
(
b
−a
)
is orthogonal to the line La/b. Therefore, bxQ − ayQ measures the
distance between vQ :=
(
xQ
yQ
)
and La/b. By Theorem 1, a rational hook
Hρ is characterized by the geometric property that the interior line does
not intersect ∂Hρ. If a cell Q of H is removed, this property remains
valid for the two hooks of H r {Q} if the distance between vQ and La/b
is minimal, i. e. bxQ − ayQ = ±1. By Proposition 4, the latter means
that v(Q) = 1. To prove the converse, assume that bxQ − ayQ = 1, and
114 Arithmetic properties of exceptional lattice paths
that Q′ ∈ H is removable, too. Assume, without loss of generality, that
d := bxQ′ − ayQ′ is positive. Thus H r {Q′} splits into two rational
hooks Hρ′ and Hρ′′ . Assume that Q belongs to Hρ′ . If vQ′ = d · vQ, then
vQ ∈ Lρ′ , a contradiction. Hence |vQ′ | > d · |vQ|. Since d · vQ =
(dxQ
dyQ
)
satisfies b · dxQ − a · dyQ = d, this is impossible. �
Corollary. Let H = Ha/b be a rational hook with a, b > 2 relatively
prime. There are exactly two removable cells of H. If one of these cells
is removed, we obtain two rational hooks Hp/q and Hr/s with reduced
fractions p
q > r
s . These hooks Hp/q and Hr/s are uniquely determined by
the determinantal relation ∣
∣
∣
∣
p r
q s
∣
∣
∣
∣
= 1. (4.20)
Proof. By Theorem 4 and the corollary of Theorem 3, there are two
centrally symmetric removable cells. Let Q be the minimal one. Then
bxQ−ayQ = 1 by Proposition 4. Hence Eq. (4.20) holds with p = xQ, q =
yQ, r = a−xQ, and s = b−yQ, which yields a splitting of H into Hp/q and
Hr/s. Conversely, since p + r = a and q + s = b, Eq. (4.20) is equivalent
to
∣
∣
∣
∣
p a
q b
∣
∣
∣
∣
= 1, which has exactly one solution
(
p
q
)
∈ Z2 with 0 < p < a and
0 < q < b. �
Let H be any rational hook. If we successively remove the cells Q
with f(Q) = 1, we get a unique decomposition of H into hooks of one
cell. Next we will show that this decomposition of a rational hook Hρ
with ρ > 1 can be obtained from the continued fraction expansion of
ρ. Recall first that Hρ corresponds to a finite sequence v0, . . . , vn in E,
such that the differences vi − vi−1 are either e1 or e2. Therefore, the
orthogonal projection of {v0 . . . , vn} to the interior line of Hρ yields a
sequence Wρ of n tiles L or S, corresponding to the differences e1 and e2,
respectively. We call Wρ the tiling of Hρ. Note that the restriction ρ > 1
is not essential. For the symmetric case 0 < ρ < 1, however, the “long”
tile L would be shorter than S.
By the corollary of Theorem 4, every hook Hρ with more than one
row and column has two removable cells Q such that Hρ r{Q} splits into
two rational hooks Hρ′ and Hρ′′ with ρ′ < ρ′′. Accordingly, the tiling Wρ
has two decompositions
Wρ = Wρ′′T
+Wρ′ = Wρ′T
−Wρ′′ , (4.21)
where
T+ := SL, T− := LS. (4.22)
In fact, if Q is minimal, Eq. (3.18) shows that
ρ′′ =
xQ
yQ
> ρ′ =
a − xQ
b − yQ
, (4.23)
W. Rump 115
which yields the first equation in (4.21). The other case is dual.
For any ρ > 1, there is a unique continued fraction expansion
ρ = [a0, a1, a2, . . .] := a0 +
1
a1 +
1
a2 + · · ·
(4.24)
with integers an > 1. (For rational ρ, the expansion is finite, and we
assume that the last an is > 2.) The partial quotients
[a0, . . . , an−1] =
pn
qn
(4.25)
with relatively prime pn, qn > 0 are given by the recursion (cf. [2], chap.
X)
pn+1
qn+1
=
anpn + pn−1
anqn + qn−1
(4.26)
with p−1 = q0 = 0 and p0 = q−1 = 1. Hence
∣
∣
∣
∣
pn pn−1
qn qn−1
∣
∣
∣
∣
= (−1)n (4.27)
holds for all n ∈ N.
Proposition 5.. Let ρ > 1 be a rational number with continued fraction
expansion ρ = [a0, . . . , am] and partial quotients (4.25). With wn :=
Wpn/qn
, the tiling Wρ = wm+1 of Hρ satisfies the reduction formula
wn+1 =
{
(wnT+)anwn−1 for n even
(wnT−)anwn−1 for n odd.
(4.28)
Proof. We set vn :=
(
pn
qn
)
. Assume first that n is even. Then Eq.
(4.27) implies that det(vn, ivn + vn−1) = det(vn, vn−1) = 1 for all i ∈ N.
Hence (4.28) follows by Eq. (4.26) and an iterated application of Eq.
(4.21). For odd n, we have det(ivn + vn−1, vn) = det(vn−1, vn) = 1 for all
i ∈ N. In this case, we get the same result, with T− instead of T+. �
Remark. If we introduce the improper tilings
w−1 := L−1, w0 := S−1 (4.29)
of length −1, the reduction formula (4.28) yields the correct values
w1 = Wa0
= La0−1, w2 = Wa0a1+1/a1
= La0SLa0S · · ·SLa0 , (4.30)
where in the second equation, La0 occurs a1 times.
116 Arithmetic properties of exceptional lattice paths
The composition formula (4.21) and its repetition (4.28) with the
connecting tiles T± shed some light upon the quasicrystallographic case.
Let ρ > 1 be an irrational number. The orthogonal projection of Pρ,
augmented by one of the points ±1
2
(e1 − e2) ∈ E, to the line Lρ yields
two quasicrystallographic tilings
· · ·T2T1T0T
±T0T1T2 · · · (4.31)
of Lρ with Ti ∈ {L, S}, where the connecting tiles T+ or T− arise at the
point of ambiguity. The explicit form of the tiling (4.31) can be obtained
from Proposition 5 with ρ irrational (cf. [4]). Note that each wn+1 starts
with wn, so that wn converges to T0T1T2 · · · .
If we extend the concept of hook to infinite sequences of cells, there
are infinite hooks of three types:
type ω: H has a lower left cell
type ω∗: H has an upper right cell
type ω∗ + ω: H is a two-way infinite hook.
Thus (4.31) represents a hook of type ω∗+ω with a splitting into hooks of
type ω∗ and ω, respectively. Like in the finite case (4.21), the connecting
piece is T+ or T−. For a finite hook Hρ, however, the two composites
Wρ′′T
−Wρ′ and Wρ′T
+Wρ′′ in (4.21) are equal, while there are two dif-
ferent composites in the infinite case (4.31). On the other hand, the two
pieces · · ·T2T1T0 and T0T1T2 · · · in (4.31) are congruent via reflection,
while the pieces Wρ′ and Wρ′′ in (4.21) are different. We have seen above
that for a rational ρ > 1, the infinitely many, equally good approxima-
tions of Lρ are made up from infinitely many rational hooks Hρ. The
corresponding tilings of Lρ are thus of the form
· · ·WρT
±WρT
±WρT
±Wρ · · · (4.32)
where the finite pieces Wρ of this composition are again congruent and
separated by T+ or T−.
If ρ is quadratic over Q, the continued fraction expansion (4.24) is
periodic. Assume that ρ satisfies an equation
ρ2 = mρ + 1 (4.33)
with an integer m > 1. Then ρ = m + 1
ρ , and the sequence (an) in (4.28)
is constant with an = m. In this case, the sequence (Tn) in (4.31) can be
generated by the substitution rule
L 7→ LmS; S 7→ L. (4.34)
W. Rump 117
Indeed, for a given tiling w, if we replace every L by LmS and every S
by L, we get a new tiling w′. Then a simple induction shows that the
tilings wn defined in (4.28) and (4.29) satisfy
w′
nLm = wn+1. (4.35)
Therefore, an iterated substitution (4.34) gives the infinite tiling T0T1T2 · · ·
in (4.31).
Since the tilings wn = Wpn/qn
are symmetric, the reverse tiling · · ·T2T1T0
ends with wn, for every n > 1. This implies that the two quasicrystals
(4.31) are mirror-images with respect to the substitution rule (4.34). In
fact, Eq. (4.35) yields
(· · ·wnLSwn · · · )′ = · · ·w′
nLmSLw′
n · · · = · · ·wn+1SLw′
n · · ·
(· · ·wnSLwn · · · )′ = · · ·w′
nLLmSw′
n · · · = · · ·wn+1LSw′
n · · ·
References
[1] S. Berman, R. V. Moody: The algebraic theory of quasicrystals with five-fold
symmetries, J. Phys. A: Math. Gen. 27 (1994), 115-129
[2] G. H. Hardy, E. M. Wright: An Introduction to the Theory of Numbers, Oxford
University Press (4th corr. Ed.), London 1975
[3] M. M. Kleiner: Partially ordered sets of finite type, in: D. K. Faddeev (ed.):
Investigations on Representation Theory, Zap. Naučn. Sem LOMI 28 (1972),
32-41; engl. transl.: J. Soviet Math. 3 (1975), 607-615
[4] J. M. Luck, D. Petritis: Phonon Spectra in One-Dimensional Quasicrystals, J.
Stat. Physics 42 (1986), 289-310
[5] W. F. Lunnon, P. A. B. Pleasants: Quasicrystallographic tilings, J. Math. Pures
Appl. 66 (1987), 217-263
[6] W. F. Lunnon, P. A. B. Pleasants: Characterization of two-distance sequences,
J. Austral. Math. Soc. (Series A) 53 (1992), 198-218
[7] Z. Masáková, J. Patera, E. Pelantová: Substitution rules for aperiodic sequences
of the cut and project type, J. Phys. A: Math. Gen. 33 (2000), 8867-8886
[8] Z. Masáková, J. Patera, E. Pelantová: Exceptional algebraic properties of the
three quadratic irrationalities observed in quasicrystals, Can. J. Phys. 79 (2001),
687-696
[9] L. A. Nazarova, A. V. Roiter: Representations and forms of weakly completed
partially ordered sets, in: Linear Algebra and Representation Theory, Institute
of Mathematics of the Ukrainian Acad. of Sciences (1983), 19-55 (in Russian)
[10] L. A. Nazarova, A. V. Roiter: The norm of a relation, separating functions and
representations of marked quivers, Preprint math.RT/0206052
[11] A. V. Roiter: The norm of a relation, in: V. Dlab, P. Gabriel, G. Michler
(eds.): Representation Theory I, Finite Dimensional Algebras, Springer LNM
1177 (1984), 269-271
[12] W. Rump: Hereditary algebras and Roiter’s norm, J. Algebra, in press
[13] A. I. Sapelkin: P-faithful partially ordered sets, Ukrain. Math. J. 54 (2002),
1669-1688
118 Arithmetic properties of exceptional lattice paths
[14] M. Zeldich: On characteristic forms of partially ordered sets with simply con-
nected Hasse diagram, Visn. Kyiv. Univ., Ser. Fiz.-Mat., 4 (2001), 36-44
[15] M. Zeldich: On ρ-faithful partially ordered sets, Visn. Kyiv. Univ., Ser. Fiz.-
Mat., 4 (2001), 45-51
[16] M. Zeldich: ρ-exact partially ordered sets and characteristic forms, Preprint (69
pp.), Kiev 2002 (in Russian)
Contact information
W. Rump Institut fьr Algebra und Zahlentheorie, Uni-
versitдt, Stuttgart, Pfaffenwaldring 57, D-
70550 Stuttgart, Germany
E-Mail: rump@mathematik.uni-stuttgart.de
Received by the editors: 20.04.2005
and in final form 19.11.2006.
|