AP07_2-3.vp


1 Introduction

Sequences of the form � �� �j j� �� for � � 1, now known as
Beatty sequences, were first studied in the context of the
famous problem of covering the set of positive integers by
disjoint sequences [1]. Further results in the direction of
so-called disjoint covering systems are due to [2], [3], [4] and
others. Other aspects of Beatty sequences were then studied,
such as their generation using graphs [5], their relation to
generating functions [6], [7], their substitution invariance [8],
[9], etc. A good source of references on Beatty sequences and
other related problems can be found in [10], [11].

In [12] the authors study the self-matching properties of
the Beatty sequence � �� �j j� �� for � � 	

1
2

5 1( ), the golden
ratio. Their study is rather technical; they have used for their
proof the Zeckendorf representation of integers as a sum of
distinct Fibonacci numbers. The authors also state an open
question whether the results obtained can be generalized to
other irrationals than �. In our paper we answer this question
in the affirmative. We show that Beatty sequences � �� �j j� ��
for quadratic Pisot units � have a similar self-matching prop-
erty, and for our proof we use a simpler method, based on the
cut-and-project scheme.

It is interesting to note that Beatty sequences, Fibonacci
numbers and the cut-and-project scheme have attracted the
attention of physicists in recent years because of their applica-
tions for mathematical description of non-crystallographic
solids with long-range order, so-called quasicrystals, discov-
ered in 1982 [13]. The first observed quasicrystals revealed
crystallographically forbidden rotational symmetry of order
5. This necessitates, for an algebraic description of the mathe-
matical model of such a structure, the use of the quadratic
field �(�). Such a model is self-similar with the scaling fac -
tor �	1. Later, the existence was observed of quasicrystals
with 8 and 12-fold rotational symmetries, corresponding to
mathematical models with selfsimilar factors �	 � 
1 1 2 and

� 	 � 
1 2 3. Note that all �, �, and � are quadratic Pisot units,
i.e. they belong to the class of numbers for which the result of
Bunder and Tognetti is generalized here.

2 Quadratic Pisot units and the
cut-and-project scheme
The self-matching properties of the Beatty sequence

� �� �j j� �� are best displayed on the graph of � �j� against
� �j � �� 1 2 3, , ,� . An important role is played by the Fibo-

nacci numbers,
F F F F Fk k k0 1 1 10 1� � � 

 	, , , for k 
 1 .

The result of [12] states that

� � � �( )j F j Fi i
 � 
 	� � 1, (1)

with the exception of isolated mismatches of frequency �i,
namely at points of the form � �j kF k Fi i� 

1 � , k � �.

Our aim is to show a very simple proof of these results that
is valid for all quadratic units � �( , )0 1 . Every such unit is a so-
lution of the quadratic equation

x mx m2 1
 � �, �,

or
x mx m2 1	 � 	 �, �, m 
 3.

The considerations will differ slightly in the two cases.

a) Let � �( , )0 1 satisfy � �2 1
 �m for m � �. The algebraic

conjugate �� of �, i.e. the other root �� of the equation, sat-
isfies �� ��1. We define the generalized Fibonacci se-
quence

G G G mG G nn n n0 1 2 10 1 0� � � 
 
 
, , , (2)

It is easy to show by induction that for i � �, we have

( )	 � 	
 	1
1

1
i i

i iG G� � and ( )	 � � � 	



	1
1

1
i i

i iG G� � . (3)

b) Let � �( , )0 1 satisfy � �2 1	 � 	m for m � �, m 
 3. The

algebraic conjugate �� of � satisfies �� �1. We define
G G G mG G nn n n0 1 2 10 1 0� � � 	 
 
, , , (4)

In this case, we have for i � �

©  Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 21

Acta Polytechnica Vol. 47 No. 2–3/2007

Self-Matching Properties of Beatty
Sequences

Z. Masáková, E. Pelantová

We study the selfmatching properties of Beatty sequences, in particular of the graph of the function � �j� against j for every quadratic unit
� �( , )0 1 . We show that translation in the argument by an element Gi of a generalized Fibonacci sequence almost always causes the
translation of the value of the function by Gi�1. More precisely, for fixed i � �, we have � � � �� �( )j G j Gi i
 � 
 	1, where j Ui� . We
determine the set Ui of mismatches and show that it has a low frequency, namely �

i.

Keywords: Beatty sequences, Fibonacci numbers, cut-and-project scheme.



� �i i iG G� 	 	1 and � � � 	 	� �
i

i iG G 1 (5)

The proof we give here is based on the algebraic expres-
sion for one-dimensional cut-and-project sets [14]. Let V1, V2
be straight lines in �2 determined by vectors ( , )� 	1 and
( , )� 	� 1 , respectively. The projection of the square lattice �2 on
the line V1 along the direction of V2 is given by

( , ) ( ) ( )a b a b x a b x� 
 � 
 
� �
� �

1 2, for ( , )a b ��
2,

where
�

x1
1

1�
	 �� �

�	� 
( and
�

x2
1

1�
� 	

�
� �

� 	� 
( . For the de-

scription of the projection of �2 on V1 it suffices to consider
the set

� � � �� �� � 
 � �� �: ,a b a b
The integral basis of this free abelian group is ( , )1 �� , and

thus every element x of � �� �� has a unique expression in this
base. We will say that a is the rational part of x a b� 
 �� and b
is its irrational part. Since �� is a quadratic unit, � �� �� is a ring
and, moreover, it satisfies

� � � �� � � �� � �� � (6)
A cut-and-project set is the set of projections of points of

�
2 to V1, that are found in a strip of given bounded width,

parallel to the straight line V1. Formally, for a bounded inter-
val � we define

� �� �( ) , ,� 
 � � 
 �a b a b a b� � ��
Note that a b
 �� corresponds to the projection of the

point (a, b) to the straight line V1 along V2, whereas a b
 �
corresponds to the projection of the same lattice point to V2
along V1.

Among the simple properties of the cut-and-project sets
that we use here are
� � � �( ) ( )	 � 	 
1 1 , � �� �� � � �( ) ( ),

where the latter is a consequence of (6). If the interval � is of
unit length, one can derive directly from the definition a sim-
pler expression for � �( ). In particular, we have

� � � �� ��[ , ) [ , )0 1 0 1� 
 � 
 � � � 	 �a b a b b b b� � � � � , (7)
where we use that the condition 0 1� 
 �a b� is satisfied if and
only if � � � �a b b� 	 � 	� � .

Let us mention that the above properties of one-dimen-
sional cut-and-project sets, and many others, are explained in
the review article [14].

3 Self-matching property of the graph
� �j� against j
An important role in the study of the self-matching prop-

erties of the graph � �j� against j is played by the generalized
Fibonacci sequence ( )Gi i�� , defined by (2) and (4), respec-
tively. It turns out that shifting the argument j of the function

� �j� by the integer Gi results in shifting the value by Gi	1, with
the exception of isolated mismatches with low frequency. The
first proposition is an easy consequence of the expressions of
�� as an element of the ring � �� � in the integral basis 1, �,

given by (3) and (5).

Theorem 1

Let � �( , )0 1 satisfy � �2 1
 �m and let ( )Gi i�
�

0 be defined by (2). Let

i ��. Then for j �� we have

� � � �� � 
( ) ( )j G j G ji i i
 � 
 
	1
where � �
i ij( ) ,( )� 	 
0 1 1 . The frequency of integers j for which the
value 
i j( ) is non-zero is equal to

� �
�


�i

n

i ij n j n j

n
: lim

# , ( )
�

� 	 � � �



�

��

� 0

2 1
.

Proof. The first statement is trivial. For, we have

� � � � � �� �

� �


 � � � � �

� �

i i i i i

i

j j G j G j j G G

j j

( ) ( )

( )

� 
 	 	 � 	 
 	

� 	 
 	

	 	




1 1

11� � � �� i i� 	 
0 1 1, ( ) .
(8)

The frequency �i is easily determined in the proof of
Theorem 1. �

In the following theorem we determine the integers j for
which 
i j( ) is non-zero. From this, we easily derive the fre-
quency of such mismatches.

Theorem 2

With the notation of Theorem 1, we have


i
i

ij
if j U
otherwise,

( )
,

( )
�

�

	
�
�
�



0
1 1

where

� �� �U k G k G k k Gi i i
i

i� 
 � � �
	�

�
�

�
�
�




	

1

1
0

1
2

� �,
( )

.

Before starting the proof, let us mention that for i even,
the set Ui can be written simply as

� �� �U k G k G ki i i� 
 �
1 � � .
For i odd, the element corresponding to k � 0 is equal to 	Gi
instead of 0. The distinction according to the parity of i is
necessary here, since unlike the paper [12], we determine the
values of 
i j( ) for j ��, not only for.

Proof. It is convenient to distinguish two cases according to the
parity of i.

� First let i be even. It is obvious from (8), that � �
i j( ) ,� 	0 1
and

� �
 � � �i
ij j j( ) [ , ).� 	 	 �1 0if and only if (9)

Let us denote by M the set of all such j,

� �� �
� �

M j j j

j k j k

i

i

� � 	 �

� � 
 � �

�

� �

� � �

� �

[ , )

[ , ),

0

0 for some

22 ©  Czech Technical University Publishing House http://ctn.cvut.cz/ap/

Acta Polytechnica Vol. 47 No. 2–3/2007



Therefore M is formed by the irrational parts of the ele-
ments of the set

� �k j k j
G G k

i i i

i i


 � 
 � � � �

� 	 � 
 �	

� � � � �

� �

[ , ) [ , ) [ , )

( )

0 0 0 1

1

� �

� �� �	 �k k� � ,
where the last equality follows from (3) and (7). Separating
the irrational part we obtain

� �� �
� �� �

M k G m k G k G k

G k k G k U

i i i

i i i

� 
 
 �

� 
 � �

	




1

1

�

�

�

� ,

where we have used the equations � 
 � �� �2 1m and

mG G Gi i i
 �	 
1 1.

� Now let i be odd. Then from (8), � �
i j( ) ,� 	0 1 and

� �
 � � �i
ij j j( ) [ , ).� 	 � 	1 1 1if and only if (10)

Let us denote by M the set of all such j,

� �� �
� �

M j j j

j k j k

i

i

� � 	 	 � 	

� � 
 � 	 �

�

� �

� � �

� �

1 0

0

[ , )

[ , ), .for some

Therefore M is formed by the irrational parts of elements
of the set

� �k j k j i i i
i


 � 
 � 	 � 	 � � 	

� � 	

� � � � �

�

[ , ) [ , ) [ , )

( [ , )

0 0 1 0

1 0 1

� �

� � �� �) ( ) .� � 	 � 	 	 �	� � �G G k k ki i 1 1 �
Separating the irrational part we obtain

� �� �
� �� �

M k G m k G k G G k

k G G k k

k G

i i i i

i i

i

� 	 	 	 	 �

� 	 	 
 �

� 


	







1

1

1

1

�

�

�

�( )

� �� �G k k Ui i( ) ,� 	 � �1 �

where we have used the equation
� 
 � �� �2 1m , mG G Gi i i
 �	 
1 1 and � � � �	 �k k� � .

Let us recall that the Weyl theorem [15] states that num-
bers of the form � �j j� �	 , j ��, are uniformly distributed in
(0, 1) for every irrational �. Therefore the frequency of those
j �� that satisfy � �j j I� �	 �  ( , )0 1 is equal to the length of
the interval I. Therefore one can derive from (9) and (10) that
the frequency of mismatches (non-zero values 
i j( )) is equal to
�i, as stated by Theorem 1. �

If � �( , )0 1 is the quadratic unit satisfying � �2 1	 � 	m ,
then the considerations are even simpler, because expression
(5) does not depend on the parity of i. We state the result as
the following theorem.

Theorem 3
Let � �( , )0 1 satisfy � �2 1	 � 	m and let ( )Gi i�

�
0 be defined by (4).

For i ��, put

� �� �V k G k G ki i i� 	 
 �
1 1( )� � .
Then for j �� we have

� � � �� � 
( ) ( )j G j G ji i i
 � 
 
	1 ,

where


i
ij

if j V
otherwise.

( )
,

�
��

�
�

0
1

The density of the set Ui of mismatches is equal to �
i.

Proof. The proof follows the same lines as proofs of Theorems
1 and 2. �

4 Conclusions
One-dimensional cut-and-project sets can be constructed

from �2 for every choice of straight lines V1, V2, if they have ir-
rational slopes. However, in our proof of the self-matching
properties of the Beatty sequences we strongly use the alge-
braic ring structure of the set � �� �� , and its scaling invariance
with the factor �� , namely � � � �� � �� � �� � . For this, �� must nec-
essarily be a quadratic unit.

However, it is plausible that, even for other irrationals �,
some self-matching property is displayed by the graph � �j�
against j. To show that, other methods would be necessary.

5 Acknowledgments
The authors acknowledge financial support from the

Czech Science Foundation GA ČR 201/05/0169, and from the
grant LC06002 of the Ministry of Education, Youth and
Sports of the Czech Republic.

References
[1] Beatty, S.: Amer. Math. Monthly, Vol. 33 (1926), No. 2,

p. 103–105.
[2] Fraenkel, A. S.: The Bracket Function and Complemen-

tary Sets of Integers. Canad. J. Math., 21, 1969, 6–27
[3] Graham, R. L.: Covering the Positive Integers by Dis-

joint Sets of the Form � �� �n n� �
 �: , ,1 2 � . J. Combina-
torial Theory Ser. A, Vol. 15 (1973), p. 354–358.

[4] Tijdeman, R.: Exact Covers of Balanced Sequences and
Fraenkel’s Conjecture. In Algebraic Number Theory and
Diophantine Analysis (Graz, 1998), Berlin: de Gruyter
2000, p. 467–483.

[5] de Bruijn, N. G.: Updown Generation of Beatty Se-
quences. Nederl. Akad. Wetensch. Indag. Math., Vol. 51
(1989), p. 385–407.

[6] Komatsu, T.: A Certain Power Series Associated with a
Beatty Sequence. Acta Arith., Vol. 76 (1996), p. 109–129.

[7] O’Bryant, K.: A Generating Function Technique for
Beatty Sequences and Other Step Sequences. J. Number
Theory, Vol. 94 (2002), p. 299–319.

[8] Komatsu, T.: Substitution Invariant Inhomogeneous
Beatty Sequences. Tokyo Journal Math., Vol. 22 (1999),
p. 235–243.

[9] Parvaix, B.: Substitution Invariant Sturmian Bise-
quences. Thor. Nombres Bordeaux, Vol. 11 (1999),
p. 201–210.

[10] Brown, T.: Descriptions of the Characteristic Sequence
of an Irrational. Canad. Math. Bull., Vol. 36 (1993),
p. 15–21.

©  Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 23

Acta Polytechnica Vol. 47 No. 2–3/2007



[11] Stolarsky, K.: Beatty Sequences, Continued Fractions,
and Certain Shift Operators. Canad. Math. Bull., Vol. 19
(1976), p. 473–482.

[12] Bunder, M., Tognetti, K.: On the Self Matching Proper-
ties of [j�]. Discr. Math., Vol. 241 (2001), p. 139–151.

[13] Shechtman, D., Blech, I., Gratias, D., Cahn, J. W.:
Metallic Phase with Long-Range Orientational Order
and no Translation Symmetry. Phys. Rev. Lett., Vol. 53
(1984), p. 1951–1953.

[14] Gazeau, J. P., Masáková, Z., Pelantová, E.: Nested Quasi-
crystalline Discretization of the Line. In: Physics and
Number Theory (Editor: L. Nyssen), Vol. 10 of IRMA Lec-
tures in Mathematics and Theoretical Physics, Zürich, EMS
2006, p. 79–132.

[15] Weyl, H.: Über die Gleichverteilung von Zahlen mod.
Eins. Math. Ann., Vol. 77 (1916), p. 313–352.

Doc. Ing. Zuzana Masáková, Ph.D.
phone: +420 224 358 544
e-mail: masakova@km1.fjfi.cvut.cz,

Prof. Ing. Edita Pelantová, CSc.
phone: +420 224 358 544
e-mail: pelantova@km1.fjfi.cvut.cz

Doppler Institute for Mathematical Physics and Applied
Mathematics

Czech Technical University in Prague
Faculty of Nuclear Sciences and Physical Engineering
Trojanova 13
120 00 Praha 2, Czech Republic

24 ©  Czech Technical University Publishing House http://ctn.cvut.cz/ap/

Acta Polytechnica Vol. 47 No. 2–3/2007