Numeration 2017
Argiletum in Madonna dei MontiRome, June 5 – 9, 2017
Contributions to Numeration Systems, Ergodic Theory,
Number Theory and Combinatorics

Department of Mathematics and Physics
Conference Chairs: Vilmos Komornik and Marco Pedicini
Conference Organisers: Valerio Talamanca, Corrado Falcolini,
Anna Chiara Lai, Roberto Maieli

Acknowledgements

This conference was made possible through the generous support of••••

Istituto Nazionale di Alta Matematica “Francesco Severi”, Gruppo GNSAGA;
Department of Mathematics and Physics, Roma Tre University;
Laboratory Ypatia of Mathematical Sciences;
MIUR-PRIN2011 Metodi Logici per il Trattamento delle Informazioni.

Special thanks to the Department of Architecture which hosted the Conference at
the Argiletum.

v

Contents

Expansions of quadratic numbers in a p-adic continued fraction. . . . . . . . .
Umberto Zannier

1

Around discretized rotation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Shigeki Akiyama

3

A Numeration System and a Gray Code Given by a Variant of the Towerof Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Benoı̂t Rittaud

5

Substitutions, coding prescriptions and Numeration . . . . . . . . . . . . . . . . . . .
Paul Surer

11

On the sum of digits of the factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Carlo Sanna

13

On the semi-random Lüroth map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Marta Maggioni

17

k-regular Sequences & Mellin–Perron Summation for Analyzing
Fluctuations in Pascal’s Rhombus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Daniel Krenn (based on a joint work with C. Heuberger and H. Prodinger)

19High precision computing for continued fractions and mod 2 normal
numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Geon Ho Choe

23

Limits of families of canonical number systems . . . . . . . . . . . . . . . . . . . . . . .
Dávid Bóka and Péter Burcsi
An upper bound on prolongation of periods of continued fractions byMöbius transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Hana Dlouhá and Štěpán Starosta

29

31

vii

viii

Contents

The Thompson groups, graph polynomials, and knot theory. . . . . . . . . . . . .
Valeriano Aiello and Roberto Conti

33

Finiteness in real cubic fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Zuzana Masáková and Magdaléna Tinková

39

Nearly linear recursive sequences, especially SRS . . . . . . . . . . . . . . . . . . . . . .
Attila Pethő

43

Order statistics of the values of words with respect to the generalised
multinomial measure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Ligia L. Cristea and Helmut Prodinger

45

Discrepancy bounds for β -adic Halton sequences . . . . . . . . . . . . . . . . . . . . . .
Jörg Thuswaldner

47

Algebraic structure and numeration systems for circular words . . . . . . . . . .
Isabelle Dubois

49

A constrained Diophantine equation on symmetric numbers in different
bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Stefano Arnone, Corrado Falcolini, Francesco Moauro, and Matteo Siccardi

51

On the structure of periodic elements of simultaneous systems . . . . . . . . . . .
Gabor Nagy

59

Numbers, systems, applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Attila Kovács

61

Interactions between digits in Fibonacci Numeration . . . . . . . . . . . . . . . . . . .
Anne Bertrand Mathis

65

Bernoulli convolutions, Garsia entropy and local dimension . . . . . . . . . . . . .
Kevin G. Hare

69

Bases with two expansions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Vilmos Komornik and Derong Kong75

A shrinking hole for β -transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Niels Langeveld

77

Expansions in non-integer bases in control problems . . . . . . . . . . . . . . . . . . .
Paola Loreti

81

Periodic representations in algebraic non-integer base . . . . . . . . . . . . . . . . .
Tomáš Vávra

83

Self-similar manipulators, Fibonacci sequence and number systems . . . . . .
Anna Chiara Lai

85

Contents

ix

Digit frequencies and self-affine sets with non-empty interior . . . . . . . . . . . .
Simon Baker

91

Essentially nonnormal numbers for random Cantor series expansions . . . .
Bill Mance and Roman Nikiforov

93

Computing with generalized number systems using the computer algebra
system SYGNM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Tamás Krutki, Bence Németh and Attila Kovács
Examining the number system property with probabilistic algorithms . . . .
Péter Hudoba and Attila Kovács

95
97

Normal Subsequences of Automatic Sequences . . . . . . . . . . . . . . . . . . . . . . . . 101
Clemens Müllner
Totally Real Algebraic Numbers, Bogomolov Property, and Dynamical
Zeta Function of the β -shift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Jean-Louis Verger-Gaugry
On the Hausdorff dimension faithfulness of expansions with infinite
alphabet and properties of non-normal numbers . . . . . . . . . . . . . . . . . . . . . . 105
Roman Nikiforov
On Weyl’s theorem on Uniform Distribution and Ergodic Theorems . . . . . . 107
Radhakrishnan Nair and Entesar Nasr
Fractals and space-filling curves viewed by a new numerical computation
system using infinities and infinitesimals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Fabio Caldarola
On relations between systems of numerations and fractal properties ofsubsets of non-normal numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Iryna Harko
On Littlewood and Newman polynomial multiples of Borwein polynomials 129
Paulius Drungilas, Jonas Šiurys, Jonas Jankauskas
An introduction to p-adic systems: A new kind of number system . . . . . . . . 131
Mario Weitzer
Salem numbers as unusual Mahler measures . . . . . . . . . . . . . . . . . . . . . . . . . 133
Artūras Dubickas
On multiplicative independent bases for canonical number systems incyclotomic number fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
Manfred Madritsch

xContents

Topology of a class of p2-crystallographic replication tiles . . . . . . . . . . . . . . 137
Benoı̂t Loridant and Shu-qin Zhang

List of Participants

Aiello Valeriano
Roma Tre University, Italy
Akiyama Shigeki
Tsukuba University, Japan
Andrianaivo Louis Nantenaina
Roma Tre University, Italy
Baker Simon
Mathematics Institute, University of Warwick, UK
Bertrand Mathis Anne
University of Poitiers, France
Burcsi Péter
ELTE – Eötvös Loránd University, Budapest, Hungary
Caldarola Fabio
Dep. of Mathematics and Computer Science, University of Calabria, Italy
Choe Geon
Korea Advanced Institute of Science and Technology, Republic of Korea
Cristea Ligia Loretta
University of Graz, Institute for Mathematics and Scientific Computing, Austria
Dajani Karma
Utrecht University, NetherlandsDávid Bóka
ELTE – Eötvös Loránd University, Budapest, Hungary
Davidoff Giuliana
Mount Holyoke College,

xi

xii

Dlouhá Hana
Czech Technical University in Prague, Czech RepublicDrungilas Paulius
Vilnius University, Lithuania
Dubickas Arturas
Vilnius University, Lithuania
Dubois Isabelle
Universitè de Lorraine, France
Falcolini Corrado
Dipartimento di Architettura, Roma Tre University, Italy
Frougny Christiane
IRIF, FranceHare Kevin
University of Waterloo, Canada
Harko Iryna
Dragomanov National Pedagogical University, Kyiv, Ukraine
Hudoba Péter
Eötvös Loránd University, Budapest, Hungary
Jankauskas Jonas
Mathematik und Statistik, Montanuniversität Leoben, Austria
Komornik Vilmos
Strasbourg University, France
Kong Derong
Leiden University, Netherlands
Kovács Attila
Eötvös Loránd University, Budapest, Hungary
Krenn Daniel
Alpen-Adria-Universitàat Klagenfurt, Austria
Krutki TamásEötvös Loránd University, Budapest, Hungary
Kwon DoYong
Chonnam National University, Republic of Korea
Lai Anna Chiara
Sapienza Università di Roma, Italy
Langeveld Niels
University of Leiden, Netherlands

List of ParticipantsList of Participants

Loreti Paola
Sapienza Università di Roma, Italy
Loridant Benoı̂t
Chair of Mathematics and Statistics, University of Leoben, Austria
Madritsch Manfred
Universitè de Lorraine, France
Maggioni Marta
MI-University of Leiden, Netherlands
Müllner Clemens
TU Wien, Austria
Murru Nadir
University of Turin, Italy
Nagy Gabor
ELTE Eötvös Loránd University, Budapest, Hungary
Nair Radhakrishnan
University of Liverpool, UK
Nikiforov Roman
Dragomanov National University, Kyiv, Ukraine
Pawelec Krzysztof
Pennsylvania State University, USA
Pedicini Marco
Roma Tre University, Italy
Pelantova Edita
Czech Technical University in Prague, Czech Republic
Pethő Attila
University of Debrecen, Hungary
Rittaud Benoı̂t
Université Paris-13, Sorbonne Paris Cité, LAGA, CNRS, UMR 7539, F-93430
Villetaneuse, France.
Sanna Carlo
Università degli Studi di Torino, Italy
Steiner Wolfgang
CNRS, Univ. Paris 7, France
Surer PaulBOKU Vienna, Austria
Talamanca Valerio
Roma Tre University, Italy

xiii

xiv

List of Participants

Thuswaldner Jörg
University of Leoben, Austria
Tinkovà Magdalàna
Department of Mathematics FNSPE, Czech Technical University in Prague, Czech
RepublicVávra Tomáš
Department of Algebra, Charles University, Praha, Czech Republic
Verger-Gaugry Jean-Louis
Univ. Savoie Mont Blanc, CNRS, LAMA, France
Weitzer MarioGraz University of Technology, Austria
Zannier Umberto
SNS, Pisa, Italy
Zhang Shuqin
Chair of Mathematics and Statistics, University of Leoben, Austria

Expansions of quadratic numbers in a p-adic
continued fraction.
Umberto Zannier

Abstract It goes back to Lagrange that a real quadratic irrational always has a periodic continued fraction. Starting from several decades ago, some authors have proposed expansion in p-adic continued fractions. Here the expansion depends on thechosen system of residues mod p, and results are different. We shall adopt the simplest definition, due to Ruban. It turns out that not all expansions of quadratic numbers are periodic; but it was not known how to decide whether the expansion for agiven quadratic number is or is not periodic. In recent work with L. Capuano and F.
Veneziano, we have achieved a completely general algorithm in this sense. This algorithm depends on deep theorems in transcendence and diophantine analysis, and,somewhat surprisingly, depends on the “real” value of the “p-adic” continued fraction.

Umberto Zannier
Scuola Normale Superiore e-mail: umberto.zannier@sns.it

1

Around discretized rotation
Shigeki Akiyama

Abstract Discretized rotation is modeled by a simple integer sequence (an ) definedby
0 ≤ an+2 + λ an+1 + an < 1with a fixed constant λ ∈ (−2, 2). By an analogy with rotation, we expect that all orbits are bounded, i.e., periodic. This is a notorious conjecture on which we still know
very little. From dynamical point of view, this problem is difficult by eigenvalues ofmodulus one, which makes the problem not at all expanding nor hyperbolic. We met
this problem in the context of shift radix system, the parameter space for finitenessproperty of number systems.
With many colleagues for many years, we investigated this problem and foundinteresting directions to explore: beta expansion, self-inducing system, domain exchange, substitution, and nearly recursive sequences. In this talk, I wish to summarize several ideas and developments on this topic and present interesting remaining
questions that you can join us from today.

Shigeki Akiyama
Tsukuba University, Japan e-mail: akiyama@math.tsukuba.ac.jp

3

A Numeration System and a Gray Code Given by
a Variant of the Tower of Hanoi
Benoı̂t Rittaud

The tower of Hanoi game was introduced by Édouard Lucas ([Lucas1892], p. 55-59).
In this game, n disks of increasing diameters from 1 to n are stacked onto the left post
A of a set of three (the other ones being the central one, B and the right one, C). Eachstep consists in moving a disk (only one at a time) from one post to another, until the
initial tower at the left post has been rebuilt on the right post. Each movement has tosatisfy the golden rule: a disk cannot be stacked onto a disk of smaller diameter.
It is a classical exercise to show that the successive states are naturally coded in thebinary numeration system as well as in the standard binary Gray code. Several variants of this game exist, and one may wonder whether these variants are also linked toother numeration systems. We show here in which way the answer is yes for a specific variant. What is interesting and makes the question more than a simple exercise
is that the involved numeration systems are of a particular kind, different from theusual ones derived from a greedy algorithm and a fixed increasing sequence of integers. The usefulness of these numeration systems may outweight the single study ofthe tower of Hanoi game.

1 Recursive and iterative solutions
The easiest way to present an optimal solution to the game is probably the recursive
approach, summed up by the following figure. Roughly speaking, to solve the gamewith n disks, an optimal recursive algorithm solves first the game with (n − 1) disks,
then moves once the biggest disk, then solves again the game with (n − 1) disks.
An elementary induction shows that the number of states seen by this algorithm
is 2n . Let us label them by the set of increasing integers from 0 to 2n − 1. Again, an
Benoı̂t Rittaud
Université Paris-13, Sorbonne Paris Cité, LAGA, CNRS, UMR 7539, F-93430 Villetaneuse, France.
e-mail: rittaud@math.univ-paris13.fr

5

6

Benoı̂t Rittaud

induction shows that, at the k-th state, the disk to be moved is given by the index of
the leftmost changing digit when computing the successor of k in base 2. We will callthis the digit property.

Knowing the disk which is to be moved is not equivalent to know where to put it,a question that needs some more investigation and would be of no real interest for us,
so we will not consider it here.
Now, consider the linear variant (the terminology is from [Hinz2014]), in which
direct moves between the left and the right posts are forbidden. Again, elementary
considerations provides a recursive optimal solution, by which we can prove that the
number of states is 3n , and that the base 3 numeration system also satisfies the digit
property. Hence, since in this case knowing the disk to be moved is enough to know
on which post it has to go, we get an iterative algorithm for the linear variant.
Since the number of all possible states allowed by the golden rule is also 3n (thenumber of possible partition of {1, . . . , n} in three subsets), we get that the linear
game visits the set of all allowed states. Therefore, the standard and linear games are
extremal: the first one provides the shortest path from the initial to the final state, thesecond one the (or a) longest path (without redundancy). Therefore, to no other kindof restriction in the moves can correspond a numeration system in some other integer
base.

2 The clockwise-cyclic case
The clockwise-cyclic variant, introduced in [Atkinson1981], consists in allowing only
moves from A to B, from B to C and from C to A. Atkinson wrote his paper in thecontext of teaching. In the standard game, he wrote, it is quite easy to find an iterative solution. The clockwise-cyclic variant was designed to provide a situation easily
solved by a recursive procedure, but not by iteration. He computed the explicit number of steps needed by the optimal recursivealgorithm for this cyclic variant, and√found that its complexity is O((1 + 3)n ). Some years after, [Gedeon1996] made

A Numeration System and a Gray code from the Tower of Hanoi

7a step further by presenting an iterative algorithm and by mentioning a ternary tree
structure associated to it (see figure).

Our aim is to go further in the study, by providing an explicit numeration systemthat corresponds to the clockwise-cyclic variant and satisfying the digit property.
Denote by ∆n the set {1, . . . , n}, where each integer stands for the disk of equivalent diameter. Any state of the game with n disks can be written as an ordered partitionof ∆n into three subsets. Hence, the recursive algorithm to solve the clockwise-cyclic
game with n disks can be presented in the following way, in which each arrow corresponds either to a single move or to the recursive application of the algorithm:(∆n , ∅, ∅) −→ (n, ∅, ∆n−1 ) −→ (∅, n, ∆n−1 ) −→ (∅, {∆n−2 , n}, n − 1) −→(n − 1, {∆n−2 , n}, ∅) −→ (∆n−1 , n, ∅) −→ (∆n−1 , ∅, n) −→ (∅, ∅, ∆n ).
The number rn of moves therefore satisfies rn = 2rn−1 + 2rn−2 + 3 with r1 = 2 andr2 = 7, so the number of states sn = rn + 1 is given by:
sn = 2sn−1 + 2sn−2 (for n ≥ 2).
√
The roots of the polynomial X 2 − 2X −√2 being 1 ± 3, we recover the result of[Atkinson1981] about the run-time O((1 + 3)n ) of the algorithm.
The sequence (sn )n defines naturally a numeration system of integers, and we
could expect that it satisfies the digit property, as the sequence (2n )n does for the
standard game and the sequence (3n )n does for the linear variant.
The greedy algorithm for the sequence (sn )n defines a codage of integers givenby the set of finite words on the alphabet {0, 1, 2} recognized by the language that
excludes the factor 22. The set of states of the clockwise-cyclic game is in one-to-one
correspondence with the set of integers whose expansion in this numeration system
is made of n letters (allowing leading 0s). The point is that such a numeration systemdoes not satisfy the digit property (see the states 12 and 20 in the next figure).
s1 = 3s2 = 88Benoı̂t Rittaud

Hence we need something different. First, to avoid ambiguity in the notation, wechoose A := {a, b, c} for the alphabet instead of {0, 1, 2}, and we consider only thewords that do not contain bb as a factor. With the help of the alphabetic order onwords of length n, we define a unique codage of integers between 0 and sn − 1 bywords of length exactly n, whose tree structure is the one given by [Gedeon1996].
Therefore we get an alternative way of labelling the states of the cyclic game. Let us
call it the CCH numeration system (for clockwise-cyclic Hanoi).
Theorem 1. The CCH numeration system satisfies the digit property.
Proof. The partition of the set of states in the clockwise-cyclic game given by therecursive presentation above corresponds inductively to the following partition of theset An of words of length n without bb as a factor (NB: here, An∗ stands for An \{an }):∗ } ∪ {ban−1 } ∪ {baW, W ∈ A ∗ }∪An = {an } ∪ {aW, W ∈ An−1n−2n−2∗ } ∪ {can−1 } ∪ {cW, W ∈ A ∗ }.
{bca } ∪ {bcW, W ∈ An−2
n−1

The result follows by induction.
Since the forbidden factor is bb instead of cc (i.e. 11 instead of 22), there is a big
difference between the classical greedy algorithm and the CCH numeration system,
as it appears in the way we get the value of an integer knowing its CCH expansion.
Theorem 2. Let (bn )n and (cn )n be the sequences defined by:
b0 = 1b1 = 3bn = 2bn−1 + 2bn−2 for n ≥ 2;

c0 = 2c1 = 5cn = 2cn−1 + 2cn−2 for n ≥ 2.

Let mn−1 . . . m0 be a finite word on the alphabet A = {a, b, c} with no factor equal
to bb. For any i ∈ {0, . . . , n − 1}, put
0 if mi = a;bi if mi = b and mi+1 6= b;ji :=ci if mi = c and mi+1 6= b;bi if mi = c and mi+1 = b.
The integer that corresponds to the word mn−1 . . . m0 is ∑i ji .
Theorem 2 is easily proved by induction and the partition An in the proof of Theorem 1. It is also easy to derive from Theorem 2 an algorithm that expands any nonnegative integer in the CCH numeration system.
In a sense, the cyclic tower of Hanoi game is the simplest nontrivial case amonga new kind of numeration systems that could be investigated. With only two letters,
we may consider a kind of “negative-Fibonacci-Zeckendorf” numeration system inwhich the forbidden factor is 00 instead of 11, but the impossibility of leading zeroes
makes it not very natural, at least for the usual purpose of numeration systems.

A Numeration System and a Gray code from the Tower of Hanoi

9

3 Gray codes
The standard Gray code is a binary codage such that the codage of any two consecutive integers differ by exactly one digit. Let wn . . . w0 ∈ {0, 1}n the binary expansionof length n + 1 of some integer k. The corresponding Gray code of k, g(wn . . . w0 ), canbe recursively defined by g(0) = 0, g(1) = 1 and, for n ≥ 1:

w0 if w2 w1 ∈ {00, 11};g(wn . . . w0 ) = g(wn . . . w1 )w, where w =1 − w0 if w2 w1 ∈ {01, 10}.
When n = 1, a leading 0 is added to make this definition sensible.
Such a Gray code is linked to the tower of Hanoi by the same digit property as
the usual binary numeration system is. To prove it, it is easier to start from a moreclassical definition of the binary Gray code: the code with n letters being given, write
the sequence twice: first in increasing order then in decreasing order. Add a leading
0 (resp. a leading 1) to each element of the first part (resp. of the second part): hereis the Gray code for words of length n + 1. This latter definition (equivalent to thefirst one, as can be easily proved) is closer to the recursive solution we met in section
1. It provides therefore a simpler way to prove that such a Gray code satisfies thedigit property. Nevertheless, it appears that the one we gave first is easier to extend
to the CCH case, so we will stick to it. From a tower of Hanoi standpoint, looking
at wn . . . w0 as wn (wn−1 . . . w0 ) consists in forgetting the largest disk n to work withthe others; looking at wn . . . w0 as (wn . . . w1 )w0 instead corresponds to the idea that
we are interested in the “lower tower” {2, . . . , n}, the smallest disk of radius 1 being
moved apart each time it is necessary to allow a move of one of the other disks.
For the linear variant, a Gray code (in base 3) g(wn . . . w0 ) can be defined by g(0) =0, g(1) = 1, g(2) = 2 and, for n ≥ 1, by: w0 if w1 = 0;g(wn . . . w1 )w, where w = w0 − 1 if w1 = 1;
w0 + 1 if w1 = 2,
where w0 ± 1 is to be understood mod 3. It is easy to see that such a Gray codesatisfies the digit property for the linear variant.
Now, it is natural to ask for a Gray code with the digit property in the case of theclockwise-cyclic game. Here is the result.
Theorem 3. In the CCH numeration system, define g(0) = 0, g(1) = 1, g(2) = 2 and,for n ≥ 1, let g(wn . . . w0 ) be

w0 if w2 w1 ∈ {00, 02, 12, 21};g(wn . . . w1 )w, where w =2 − w0 if w2 w1 ∈ {01, 10, 20, 22},
where a leading 0 is added if n = 2. Then, g is a Gray code that satisfies the digit
property for the clockwise-cyclic variant.

10

Benoı̂t Rittaud

It is easy to see that the condition w2 w1 ∈ {00, 02, 12, 21} is satisfied iff the integerthat corresponds to wn . . . w2 w1 is even.
Also, it is a trivial consequence of Theorem 3 that all the digits 1 of wn . . . w0 areat the same place as those of g(wn . . . w0 ).

4 Other restrictions, and the Abu Dhabi variant
There are other possible variants of the game based on constraints on the moves frompost to post. In particular, we could have considered the counterclockwise-cyclic gameas well (which is not isomorphic to the clockwise-cyclic game, since we asked thetower to go from A to C), and also some others. It is proved in [Hinz2014] Theorem
8.4 that the set of all constraints for which the game is solvable correspond to the setof digraphs of vertices A, B and C which are strongly connected. What precedes could
be reproduced in these other cases, the point being that the order of the corresponding linear recurring sequences (sn )n is bigger — up to 6. Hence, a general study ofnumeration systems with the same kind of “Markov property” as in Theorem 2 would
be probably of better interest than the study of these specific variants of the game.
Incidentally, let us notice another kind of variant, found by some pupils during
a workshop in Abu Dhabi in March 2017 (“MATh.en.JEANS”). In this variant, thesuccessive moves of any disk has to follow the periodic pattern
A −→ C −→ B −→ C −→ A −→ · · · .
It is an interesting exercise to show that the number of steps in this variant is (3n −1)/2, and that the corresponding numeration system is made of all words of lengthn in {0, 1, 2} upper-bounded (in the lexicographical order) by 1n . (The question of a“nice” Gray code seems a little bit more difficult.) One may wonder if other patternsof the same kind could give rise to more complex situations.

References[Atkinson1981] Atkinson, M.D.: The Cyclic Tower of Hanoi. Inform. Process. Lett. 31, 118-119(1981).
[Gedeon1996] Gedeon, T.D.: The Cyclic Towers of Hanoi: An Iterative Solution Produced byTransformation. Comput. J. 39, 353-356 (1996).
[Hinz2014] Hinz, A.M., Klavžar S., Milutinović, U., Petr, C.: The Tower of Hanoi — Myths andMaths. Springer, Basel (2013).
[Lucas1892] Lucas, É.: Récréations mathématiques vol. 3, Blanchard, Paris (1892).

Substitutions, coding prescriptions andNumeration
Paul Surer

Denote by A a finite set (alphabet) and by A ∗ the set of finite words over A . Fora word X ∈ A ∗ we write |X| for the length of X. Consider a substitution σ , i.e. amorphism σ : A → A ∗ and its extension to A ∗ via concatenation.
A coding prescription (with respect to σ ) is a function c with domain A 2 thatassigns to each pair of letters a finite set of integers with the following properties:
1. for all k ∈ c(xx) we have |k| < |σ (x)| (for all x ∈ A );2. c(xx) is a complete set of representatives modulo |σ (x)| (for all x ∈ A );3. c(ab) = {k ∈ c(aa) : k ≤ 0} ∪ {k ∈ c(bb) : k ≥ 0} (for all ab ∈ A 2 ).
The notion of coding prescription was introduced in [4] in order to code substitution dynamical systems as shifts of finite type. In the actual presentation we want toconcentrate on combinatorial aspects of coding prescriptions.
In particular, we will show how to compose coding prescriptions with respect togiven substitutions σ and σ 0 over the same alphabet in order to obtain a coding prescription for the composition σ 0 ◦ σ or for powers σ n . This will yield a way to represent integers quite analogously as the Dumont-Thomas numeration for natural integers (see [2, 3]). The set of representable numbers may consist of all (positive andnegative) integers, it may have gaps, and it can consist of 0 only. This depends on theactual coding prescription. For a special one, that assigns to each ab ∈ A 2 a set of
non-negative integers, we retrieve exactly the results from [3].
For primitive substitutions we can also base a numeration system for real numbers
on our setting where the domain can have various characteristics. Again, this depends
on the coding prescription. For the special choice from above we obtain the DumontThomas numeration for real numbers. Other choices of σ and c yield, for example,
symmetric beta-expansions (cf [1]). We will outline several effects by examples.

Paul Surer
BOKU Vienna, Austria e-mail: paul@surer.at

11

12

Paul Surer

References
1. S. A KIYAMA AND K. S CHEICHER, Symmetric shift radix systems and finite expansions, Math.
Pannon., 18 (2007), pp. 101–124.
2. V. B ERTH É AND A. S IEGEL, Tilings associated with beta-numeration and substitutions, Integers,
5 (2005), pp. A2, 46 pp. (electronic).
3. J.-M. D UMONT AND A. T HOMAS, Systemes de numeration et fonctions fractales relatifs aux
substitutions, Theoret. Comput. Sci., 65 (1989), pp. 153–169.
4. P. S URER, Coding of substitution dynamical systems as shifts of finite type., Ergodic Theory Dyn.
Syst., 36 (2016), pp. 944–972.

On the sum of digits of the factorial
Carlo Sanna

Abstract For integers b ≥ 2 and m, let sb (m) be the sum of the digits of m when
written in base b. We prove that sb (n!) > Cb log n log log log n for all integers n >ee , where Cb is a positive constant depending only on b. This improves by a factor
log log log n a previous lower bound for sb (n!) given by Luca. We also prove that thesame inequality holds with n! replaced by the least common multiple of 1, 2, . . . , n.

1 Introduction
For integers b ≥ 2 and m, let sb (m) be the sum of the digits of m when written in baseb. Given a sequence of integers (an )n≥1 with some combinatorial or number-theoretic
meaning, proving a lower bound for sb (an ) is usually a challenging task, which has
attracted the attention of several researchers.
For example, if (Fn )n≥1 is the sequence of Fibonacci numbers, defined as usual by
F1 = F2 = 1 and Fn+2 = Fn+1 + Fn for all positive integers n, a result of Stewart [11]implies that
log n
,
(1)
sb (Fn ) 
log log n
for all integers n ≥ 3, where the implied constant depends on b (see also [4] for amore general result).
Moreover, if for each positive integer n we write
 
1
2n
(2)
Cn =
n+1 n
for the nth Catalan number, then Luca and Shparlinski [8] showed that
Carlo Sanna
Università degli Studi di Torino, Italy, e-mail: carlo.sanna.dev@gmail.com

13

14

Carlo Sannapsb (Cn ) > ε(n) log n,(3)for almost all positive integers n (in the sense of the natural density), where ε(n) is
any function tending to zero as n → +∞. Furthermore, Luca and Young [9] provedthat
s2 (Cn )  log log n,(4)holds for all integers n ≥ 3 such that Cn is odd.
If p(n) denotes the partition function of n, Luca [6] gave the lower boundsb (p(n)) >log n,7 log log n(5)

for almost all positive integers n.
Cilleruelo, Luca, Rué, and Zumalacárregui [2] proved a general result, which inparticular implies thatlog nsb (Bn ) >,(6)60 log b
for almost all positive integers n, where Bn is the nth Bell number.
Also, lower bounds for the sum of digits of the Apéry numbers [7], the numeratorsof Bernoulli numbers [1], and a wide class of binomial sums [3], have been proved.
It is worth mentioning that all the previous results are much weaker than what is
expected to be the order of sb over such sequences of integers. Indeed, unless theterms of the sequence (an )n≥1 have small sb (an ) for trivial reasons (e.g., because the
an ’s are powers of b), then it seems plausible to conjecture that the digits of an in baseb behave like uniformly distributed random variables in {0, 1, . . . , b − 1}. Therefore,
it should be true thatsb (an )  log an ,(7)
for almost all positive integers n, or at least for infinitely many n, where the implied
constant depends on b. However, it can the easily checked that all the previous lower
bounds are instead of the formsb (an )  log log an ,(8)or worse.
Regarding the sum of digits of the factorial, Luca [5] showed thatsb (n!)  log n,(9)for all positive integers n, with an implied constant depending on b.
In a recent paper [10], we improved Luca’s result by proving thatsb (n!)  log n log log log n,
for all integers n > ee , where the implied constant depends on b.

(10)

On the sum of digits of the factorial

15

The main ingredients of our proof are the following: First, a folklore result, whichsays that if a positive integer N is divisible by bm −1, for some positive integer m, thensb (N) ≥ m. Second, an asymptotic formula, as x → +∞, for the largest positive integerm such that ϕ(m) ≤ x, where ϕ is Euler’s totient function. Third, some important
divisibility properties of the cyclotomic polynomials Φd (X) evaluated at b.
Employing those tools, we constructed an integer m  log n log log log n, with aparticular factorization, such that bm − 1 can be written as a product of many “almost”
pairwise coprime positive integers not exceeding n. This guarantees that bm − 1 divides n! and yields the desired conclusion. Our proof also works with n! replaced by
the least common multiple of 1, 2, . . . , n.

References
1. A. Bérczes and F. Luca, On the sum of digits of numerators of Bernoulli numbers, Canad. Math.
Bull. 56 (2013), no. 4, 723–728.
2. J. Cilleruelo, F. Luca, J. Rué, and A. Zumalacárregui, On the sum of digits of some sequences ofintegers, Cent. Eur. J. Math. 11 (2013), no. 1, 188–195.
3. A. Knopfmacher and F. Luca, Digit sums of binomial sums, J. Number Theory 132 (2012), no. 2,
324–331.
4. F. Luca, Distinct digits in base b expansions of linear recurrence sequences, Quaest. Math. 23(2000), no. 4, 389–404.
5. F. Luca, The number of non-zero digits of n!, Canad. Math. Bull. 45 (2002), no. 1, 115–118.
6. F. Luca, On the number of nonzero digits of the partition function, Arch. Math. (Basel) 98(2012), no. 3, 235–240.
7. F. Luca and I. E. Shparlinski, On the g-ary expansions of Apéry, Motzkin, Schröder and othercombinatorial numbers, Ann. Comb. 14 (2010), no. 4, 507–524.
8. F. Luca and I. E. Shparlinski, On the g-ary expansions of middle binomial coefficients andCatalan numbers, Rocky Mountain J. Math. 41 (2011), no. 4, 1291–1301.
9. F. Luca and P. T. Young, On the binary expansion of the odd Catalan numbers, Proceedings ofthe Fourteenth International Conference on Fibonacci Numbers and their Applications, Aportaciones Mat. Investig., vol. 20, pp. 185–190.
10. C. Sanna, On the sum of digits of the factorial, J. Number Theory 147 (2015), 836–841.
11. C. L. Stewart, On the representation of an integer in two different bases, J. Reine Angew. Math.
319 (1980), 63–72.

On the semi-random Lüroth map
Marta Maggioni

Abstract We present the semi-random Lüroth map T as an open random systemgiven by different ensembles of Lüroth maps. The state space is the unit interval with afixed hole, namely the subinterval [0, 1/a) is removed from [0, 1], for an integer a ≥ 2.
We translate this open random system [1/a, 1] → [0, 1] to a closed one [1/a, 1] →[1/a, 1] by choosing either the standard Lüroth map or the alternating one, in sucha way that, for each point of the domain, each of its iterates still lies in [1/a, 1]. We
then prove the existence of an absolutely continuous invariant measure on [1/a, 1] forthe closed semi-random system. For a = 2m we show the semi-random Lüroth map
T has a Markov partition, which allows us to use the theory of the Perron-Frobenius
operator in matrix form to get an explicit formula for the density.

References
1. J. Barrionuevo, R. M. Burton, K. Dajani, and C. Kraaikamp. Ergodic properties of generalized
Luroth series. Tu Delft Report, 94-105:1-16, 1994.
2. A. Boyarsky and G. Haddad. All invariant densities of piecewise linear Markov maps are piecewise constant. Adv. in Appl. Math., 2(3):284-289, 1981.
3. N. Byott, M. Holland, and Y. Zhang. On the mixing properties of piecewise expanding maps
under composition with permutations. ArXiv e-prints, 2012.
4. N. Friedman and A. Boyarsky. Matrices and eigenfunctions induced by Markov maps. Linear
Algebra Appl., 38:141-147, 1981.
5. G. Froyland and O. Stancevic. Escape rates and Perron-Frobenius operators: open and closed
dynamical systems. Discrete Contin. Dyn. Syst. Ser. B, 14(2):457-472, 2010.
6. T. Inoue. Invariant measures for position dependent random maps with continuous randomparameters. Studia Math., 208(1):11-29, 2012.
7. C.C.C.J. Kalle, T. Kempton, and E. Verbitskiy. The random continued fraction transformation.
ArXiv e-prints, 2015.

Marta Maggioni
University of Leiden, the Netherlands e-mail: marta.maggioni.mail@gmail.com

17

k-regular Sequences & Mellin–Perron
Summation for Analyzing Fluctuations inPascal’s Rhombus
Daniel Krenn (based on a joint work with C. Heuberger and H. Prodinger)

Abstract We focus on the asymptotic behavior of k-regular sequences, in particularon the example of the number of ones in Pascal’s rhombus. A combination of Dirchlet
series together with Mellin–Perron summation of orders one and two, and asymptotic
results on k-regular sequences is used to analyze the fluctuation of the main term in
the asymptotics of the sequence.

1 Introduction, Result and MoreA k-regular sequence f (n), n ∈ N0 , can be represented as follows: Suppose, for somed ∈ N, we have d × d-matrices M0 , . . . , Mk−1 and two d-dimensional vectors u and v.
Then the sequence satisfies the k-linear representationf (n) = uT Mn0 Mn1 . . . Mn`−1 v,
where n = (n`−1 . . . n1 n0 )k , the standard k-ary expansion of n.
Pascal’s rhombus is the array with entries ri, j , where r0, j = 0 for all j, r1,0 = 1 andr1, j = 0 for all j 6= 0, andri, j = ri−1, j−1 + ri−1, j + ri−1, j+1 + ri−2, j
for i > 1, see [3]. In the proposed talk, we will focus on the odd entries of this rhombus. A visualization is given in Figure 1.
The number of odd entries in a row of Pascal’s rhombus equals one componentof a certain system of recurrence relations, and it can be modelled by a 2-regularsequence.

Daniel Krenn
Alpen-Adria-Universität Klagenfurt, Austria, e-mail: daniel.krenn@aau.at

19

20

Daniel Krenn

Fig. 1: Pascal’s rhombus modulo 2.

We have the following asymptotic result.
Theorem 1 (Heuberger–K–Prodinger 2016). Let an be the number of odd entries in
the first n rows. Then we getan = nκ Φa (log2 n) + O(n log2 n)√
with κ = 2 − log2 ( 17 − 3) = 1.8325063835804 . . . and a continuous and 1-periodic
function Φa (u).
The Fourier coefficients of the fluctuation Φa (u) can be computed as well.
The proof of this result is based on the following ideas: As mentioned, the numberof ones in the a certain row, i.e., the first order differences of the an , form a 2-regularsequence. This 2-linear representation is translated to a system of functional equationsof Dirichlet series. Experiments show that the Mellin–Perron summation formula offirst order gives the asymptotic behavior and the Fourier coefficients, however, dueto (frequently recognized) convergence issues of this first order formula, it is notpossible to use it. Instead we use an approach based on the second order Mellin–
Perron summation formula, cf. [4] and [5], and show that we still get the results on the
an despite using the same system of Dirichlet series as with the first order approach.

k-regular Sequences & Mellin–Perron Summation

21

In order to make this work, a pseudo-Tauberian argument [2] and, to avoid a circularargumentation, an asymptotic statement based on [1] are needed.
Although the focus lies on this particular example of Pascal’s rhombus, the method
seems to cover many other questions that can be modelled by k-regular sequences; inthe talk we draw our attention to these generalizations.

References
1. Philippe Dumas, Joint spectral radius, dilation equations, and asymptotic behavior of radixrational sequences, Linear Algebra Appl. 438 (2013), no. 5, 2107–2126.
2. Philippe Flajolet, Peter Grabner, Peter Kirschenhofer, Helmut Prodinger, and Robert F. Tichy,
Mellin transforms and asymptotics: digital sums, Theoret. Comput. Sci. 123 (1994), 291–314.
MR 94m:11090
3. John Goldwasser, William Klostermeyer, Michael Mays, and George Trapp, The density of onesin Pascal’s rhombus, Discrete Math. 204 (1999), no. 1-3, 231–236. MR 1691871
4. Peter J. Grabner and Clemens Heuberger, On the number of optimal base 2 representations ofintegers, Des. Codes Cryptogr. 40 (2006), no. 1, 25–39. MR 2226281 (2007f:11008)
5. Peter J. Grabner and Hsien-Kuei Hwang, Digital sums and divide-and-conquer recurrences:
Fourier expansions and absolute convergence, Constr. Approx. 21 (2005), 149–179.

High precision computing for continued fractions
and mod 2 normal numbers
Geon Ho Choe

Abstract Optimal number of significant digits in numerical simulations for somenumber theoretical examples including continued fractions and mod 2 normal numbers is investigated in terms of divergence speed and the Lyapunov exponent of theassociated discrete time dynamical system.

1 Discrete dynamical system associated with number theoretic
examplesHow can we be sure that the compute continued fraction expansion of a given irrational number obtained numerically is correct up to a given level with reasonableamount of theoretical justification? This question belongs to a more broad and fundamental problem of executing rigorous simulation of discrete time dynamical systems
arising from number theoretic problems on a computer.
A discrete dynamical system is a repeated iteration T n , n ≥ 1, of a mapping (or atransformation) T : X → X defined on a probability measure space (X, µ) equippedwith a T -invariant probability measure µ, i.e., µ(T −1 A) = µ(A). In this talk we consider the case when X is the unit interval and T is piecewise differentiable. For example, T x = 2x (mod 1) or T x = 1/x (mod 1) with corresponding invariant measuresdµ = ρ(x)dx. A loop in a computer code is an iteration of the identical instruction.
When a discrete time dynamical system is modeled as a loop in a numerical code,
there is loss of accuracy in each application of the numerically defined instruction
contained in a computer code.
Some theoretical concepts cannot be rigorously simulated numerically except
when there is no need for high precision arithmetic. One such example is approximation of invariant measures including strange attractors in chaos theory based on theGeon Ho Choe
Korea Advanced Institute of Science & Technology, e-mail: ghchoe@kaist.ac.kr

23

24

Geon Ho Choen−1
Birkhoff Ergodic TheoremR which states that the time average limn→∞ (1/n) ∑k=0
f (T k (x)equals the space average X f (x)dµ for an ergodic transformation T , i.e., if f (T x) =f (x) almost everywhere then f is constant almost everywhere. For more information
consult [Bos],[P],[W]. Some software allows us to do practically unlimited precise
computation that is indispensable for high precision numerical simulations without
much technical coding requirements. Some previously unthinkable numerical experiments can be done on a personal computer.
When we try to iterate a mapping T : [0, 1] → [0, 1] with very many significant
digits, it takes a lot of time to execute a program. In this talk we present a method
to determine the number of digits sufficient for a rigorous simulation. If we take too
many significant digits, then the computation would take too long. With small numberof digits, the truncation error will ruin everything very soon. The optimal number ofsignificant digits will be given in terms of Lyapunov exponent of T .

Definition 1. If T : [0, 1] → [0, 1] is piecewise continuously differentiable and if
ρ(x)dx is an ergodic T -invariant probability measure, then we define the Lyapunov
exponent λ byZ 1

λ=log |T 0 (x)| ρ(x) dx

0where the logarithmic base equals 10.
Suppose that we take D significant decimal digits in floating point computation in
specifying a point x0 . For example,√ we may let x0 = 0.414 with D = 3 or x0 = 0.4142
with D = 4 in specifying x0 = 2 − 1 as an input. (In fact, D is large in the numericalsimulation.) The number D is the magnification level of a microscope that focuses on
the point x0 .) After k iterations of T , we lose about k × λ decimal digits from originalD digits in x0 .
Specify D significant decimal digits for x0 : |x0 − x̃0 | ≈ 10−D . If λ is the Lyapunov
exponent, then the Birkhoff Ergodic Theorem implies that, for sufficiently large k,
λ≈

k−1
1 k−1
1
log |T 0 (T j x0 )| ≈ log ∏ |T 0 (T j x0 )|
∑
k j=0
k
j=0

and
k−1

10kλ ≈ ∏ |T 0 (T j x0 )| = |(T k )0 (x0 )| .
j=0

By the chain rule, |T k x0 − T k x̃0 | ≈ 10kλ |x0 − x̃0 | ≈ 10kλ −D .
Having some precision after k iterations in an orbit of x̃0 is equivalent to kλ − D ≤0, and hence we should not iterate T numerically more than about D/λ times.
Definition 2. Define the divergence speed
Vn (x) = min{ j ≥ 1 : |T j x − T j xe| ≥ 10−1 }where |x̃ − x| = 10−n . Since

High precision computing for continued fractions and mod 2 normal numbers

25|T Vn x − T Vn x̃| ≈ 10Vn λ |x − x̃| = 10Vn λ −n ,we have Vn λ − n ≈ 0, solimnn→∞ Vn (x)= λ.

Example 1. For T x = 10x (mod 1) with λ = log10 10 = 1, we have Vn (x) = n − 1 for
0 ≤ x ≤ 1 − 10−n .
Example 2. An irrational translation mod 1 has the Lyapunov exponent equal to 0,
and hence λ = 0, and Vn = +∞ for n ≥ 2. See [CS],[KS] for related results.

2 Optimal number of significant digits
Each time when T is applied, we lose λ significant decimal digits on average. If westart with D significant decimal digits for x, then we may iterate T up to approximately
VD ≈ D/λ times with at least one decimal significant digit remaining in T VD x. Takea starting point of an orbit, say x0 , and let x̃0 denote its approximation such that|x0 − x̃0 | ≈ 10−D . For every j ∈ N, 1 ≤ j . D/λ , there corresponds an integer k ≈D − j × h such thatT n x̃0 = 0. a1 . . . . . . . . . ak ak+1 . . . . . . . . . aD
{z
}|
|
{z
}
significant

meaninglesswhere the last j ×λ digits have no information for the true theoretical orbit point T j x0 .
So, if j ≈ D/λ , then T j x̃0 loses any amount of precision. We don’t have to worry
about the truncation errors of the size 10−D , which are negligible in comparison with
10−k . In simulations with irrational translations mod 1 we don’t need many significant
digits. For the details, consult [C3]. For a related result, see [C2],[CKb].

3 Accuracy in continued fraction expansions
Consider the continued fraction map T x = {1/x}. Since x0 = [k, k, k, . . .] is a fixed
point of T , it is obvious that the average of log |T 0 | along the orbit of x0 is equal tolog |T 0 (x0 )|. Take1x0 = [k, k, k, . . . ] =
.
1
k+
1
k+
k +···√
Then x0 = (−k + k2 + 4)/2. Since log |T 0 (x0 )| = −2 log x0 , if we are given D decimal significant digits we lose all the significant digits after approximately D/(−2 log x0 )iterations of T . The number of correct partial quotients in the continued fractions

26

Geon Ho Choeof x0 obtained from numerical computation is denoted by Nk . Let Ck be the maximal number of iterations of T that produces the correct partial quotients of x0 .
If |ex0 − x0 | ≈ 10−D , then T Ck −1 x̃0 ∈ Ik = (1/(k + 1), 1/k) and T Ck x̃0 6∈ Ik . Sincej
T x0 = x0 ,|T n x̃0 − x0 | |T n x̃0 − T n x0 | n−1 0 j≈≈ ∏ |T (T x0 )| ≈ |T 0 (x0 )|n ,|x̃0 − x0 ||x̃0 − x0 |
j=0
hence
log |T n x̃0 − x0 | + D ≈ n log |T 0 (x0 )| = n(−2 log x0 ) .
Since T Ck −1 xe0 ∈ Ik ,1
1|} .
|T Ck −1 xe0 − x0 | ≤ max{ |x0 − |, |x0 −k
k+1
An approximate upper bound Uk for Nk is given by
Uk =1
D + log max{ |x0 − 1k |, |x0 − k+1|}+1 .
−2 log x0

Similarly, an approximate lower bound Lk for Nk is given by
Lk =

1
|}
D + log min{ |x0 − 1k |, |x0 − k+1.
−2 log x0

For more details and related results, see [A],[C1],[C3],[CKc]. For a general introduction to continued fractions, consult [DK],[KN],[RS].

4 Mod 2 normal numbers−k
Let X = [0, 1) with Lebesgue measure µ. Define T x = 2x (mod 1). Let x = ∑∞k=1 ak 2 ,1
k−1
ak ∈ {0, 1}, be the binary representation of x. Then ak = 1E (T x) where E = [ 2 , 1).
The normal number theorem states that almost every x is normal, i.e., (1/n) ∑nk=1 ak
converges to 21 .

Definition 3. Define dn (x) ∈ {0, 1} by dn (x) ≡ ∑nk=1 ak (mod 2). Then x is called a
mod 2 normal number if
1 N
1
(1)
lim
∑ dn (x) = 2 .
N→∞ N
n=1
Later we will see that almost every x ∈ [0, 1] is mod 2 normal. In general, if T :X → X is a transformation and 1E is the characteristic function of E ⊂ X. Definedn (x) ∈ {0, 1} by

High precision computing for continued fractions and mod 2 normal numbers

27ndn (x) ≡ ∑ 1E (T k−1 x)(mod 2) .

k=1

Then x is called a mod 2 normal number with respect to E if
1 N
1dn (x) = .
∑
N→∞ N
2
n=1

(2)

lim

(This type of problem was first studied by [W] for irrational translations modulo 1.)
Put en (x) = exp(πidn (x)) = 1 − 2 dn (x) ∈ {±1}. Then Eq. (2) is equivalent to
1 N∑ en (x) = 0
N→∞ N
n=1

(3)

lim

and Eq. (1) is a special case of Eq. (2) for T x = 2x (mod 1) and E = [ 21 , 1).
Theorem 1. (i) For any interval E 6= ( 16 , 56 ) a.e. x ∈ [0, 1) is mod 2 normal with respect
to E.
(ii) For E = ( 61 , 65 ) a.e. x ∈ [0, 1) is not mod 2 normal with respect to E. Moreprecisely, for E = ( 16 , 65 )
1 N
2
dn =
∑
N→∞ N
3
n=1
lim

a.e. x ∈ ( 13 , 23 ) ,1
1 N
dn = a.e. x ∈ (0, 31 ) ∪ ( 32 , 1) .
∑
N→∞ N
3
n=1
lim

For the proof and numerical simulations see [C3],[CHN].
Example 3 (Mod 2 uniform distribution). For θ irrational, T x = x + θ (mod 1) withrespect to E = (0, θ ).
Example 4 (Mod 2 uniform distribution). T x = 2x (mod 1) with respect to E = (0, 12 )Example 5 (Failure of mod 2 uniformity). For 0 < θ < 1/2 irrational, T x = x + θ(mod 1) with respect to E = (0, 2θ ). Thenexp(πi1E (x)) = q(x)q(T x) is satisfied byR
q = exp(πi1F ), F = (θ , 2θ ). Note that q dµ = 1 − 2θ .
Example 6 (Failure of mod 2 uniformity). T x = 2x (mod 1) with respect to E = ( 61 , 56 )Then exp(πi1E (x)) = q(x)q(T x) is satisfied by q = exp(πi1F ), F = ( 31 , 23 ). Note thatR
q dµ = 13 .
√Example 7 (Failure of mod 2 uniformity). Take β = 5+1
2 , T x = β x (mod 1), E =(1 − β1 , 1). Then exp(πi1E (x)) = q(x)q(T x) with q = exp(πi1F ), F = (0, β1 ). Notethat q dµ = − √15 .
R

28Geon Ho Choe

References[A] Y. Ahn, Generalized Gauss transformations, Applied Mathematics and Computation 142(2003), 113–122.
[B] G.D. Birkhoff, Proof of the ergodic theorem, Proceedings of the National Academy of Sciences
USA 17 (1931), 656–660.
[C1] G. Choe, Generalized continued fractions, Applied Mathematics and Computation 109 (2000),
287–299.
[C2] G. Choe, A universal law of logarithm of the recurrence time, Nonlinearity 16 (2003), 883–
896.
[C3] G. Choe, Computational Ergodic Theory, Springer, Heidelberg, 2005.
[CHN] G. Choe, T. Hamachi and H. Nakada, Mod 2 normal numbers and skew products, Studia
Mathematica 165 (2004), 53–60.
[CKb] G. Choe and B.J. Kim, High precision numerical estimation of the largest Lyapunov exponent, Communications in Nonlinear Science and Numerical Simulation 15 (2010), 1378–1384.
[CKc] G. Choe and C. Kim, The Khintchine constants for generalized continued fractions, Applied
Mathematics and Computation 144 (2003), 397–411.
[CS] G. Choe and B.K. Seo, Recurrence speed of multiples of an irrational number, Proceedings of
the Japan Academy Series A, Mathematical Sciences 77 (2001), 134–137.
[DK] K. Dajani and C. Kraaikamp, Ergodic Theory of Numbers, Mathematical Association ofAmerica, Washington, D.C., 2002.
[KS] D.H. Kim and B.K. Seo, The waiting time for irrational rotations, Nonlinearity 16 (2003),
1861–1868.
[KN] L. Kuipers and H. Niederreiter, Uniform Distribution of Sequences, John Wiley & Sons, New
York, 1974.
[P] K. Petersen, Ergodic Theory, Cambridge University Press, Cambridge, 1983.
[RS] A.M. Rockett and P. Szüsz, Continued Fractions, World Scientific, Singapore, 1992.
[V] W.A. Veech, Strict ergodicity in zero dimensional dynamical systems and Kronecker–Weyl theorem mod 2, Transactions of the American Mathematical Society 140 (1969), 1–33.
[W] P. Walters, An Introduction to Ergodic Theory, 2nd ed., Springer-Verlag, New York, 1982.

Limits of families of canonical number systems
Dávid Bóka and Péter Burcsi

Abstract We consider expansion structure and expansion length in numeration systems obtained from polynomial families with canonical digits sets. We examine how
the length of the expansion of constant polynomials changes as we increase the degree. In some special cases we prove that the expansion length is quadratic in the
degree, and introduce a limiting numeration system which captures some aspects ofthe complete family. We also pose some open questions about the period structure ofsome families of polynomials.

Dávid Bóka
ELTE – Eötvös Loránd University, Budapest, e-mail: bdavid1001@gmail.com
Péter Burcsi
ELTE – Eötvös Loránd University, Budapest, e-mail: bupe@inf.elte.hu

29An upper bound on prolongation of periods ofcontinued fractions by Möbius transformation
Hana Dlouhá and Štěpán Starosta

A number x has an 
eventuallyperiodic continued fraction if and only if x is quadraticabirrational. Let M =∈ Z2,2 . Möbius transformation (also called fractional linear
cd
transformation) determined by the matrix M is the function hM given by hM (x) =ax+bcx+d . We study the relation of the periods of the continued fraction of a quadratic
number x and of hM (x) for a given M.
Raney in [?] constructed transducers representing Möbius transformations. Using
these transducers, we construct an upper bound on the period of the continued fraction of hM (x) that depends only on the period of the continued fraction of the number
x and on the determinant of the matrix M. More precisely, let n = | det M| and πn (x)be the period of the continued fraction of hM (x) divided by the period of the continued fraction of x. Furthermore, set ξ (e, f ) to be the number of steps of Euclidean
algorithm of coprime positive integers e and f (until we reach the remainder 1). If n
is prime, we show for all quadratic irrational x the following estimate:5
if n = 2,



n−1


2

2 + 2 (ξ (i, n) + 3) if n ≡ 3 ( mod 4),∑
πn (x) ≤
(1)
i=1


n−1

2




1 + 2 ∑ (ξ (i, n) + 3) if n ≡ 1 ( mod 4).
i=1

Hana Dlouhá
Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague,
Prague, Czech Republic e-mail: hanka.dlouha@seznam.cz
Štěpán Starosta
Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic
e-mail: stepan.starosta@fit.cvut.cz

31

32

Hana Dlouhá and Štěpán Starosta

For n composite, we show a generalization of this formula. We exhibit computational
evidence that this upper bound is sharp for some small prime determinants and forother small determinants it is not greater than 2 max(πn (x)).
x

Acknowledgements This work was supported by the Grant Agency of the Czech Technical University in Prague, grant No. SGS17/193/OHK4/3T/14 and by the Czech Science Foundation grant
GAČR 13-03538S.

The Thompson groups, graph polynomials, andknot theory.
Valeriano Aiello and Roberto Conti

Abstract We describe some results and problems arising from the graphical description of the elements of the Thompson groups in terms of planar rooted binary trees
and a recent connection with knot theory discovered by Jones.

1 Introduction
In the 1960s Richard Thompson introduced the groups F ⊂ T ⊂ V , which ever since
their debut have received a great deal of attention. Among other things, we remarkthat it is still unknown whether F is amenable or not. For our purposes, it is important
to stress that their elements admit a nice pictorial description in terms of pair of planarrooted binary trees. By using this description and Vaughan Jones’s recent work, many
invariants of geometric nature, either coming from graph or knot theory, give rise topositive-definite functions on some of these groups. One thus gets many unitary representations that may shed further light on some analytical aspects. Two notable examples coming from graph theory are given by the Tutte polynomial and the chromatic
polynomial. In the process of giving an elementary proof of the positive definitenessof the chromatic polynomial, we came across a family of matrices satisfying a somewhat curious set of conditions, namely symmetric real matrices A = (ai j ) of arbitrary
size, with entries 0 ≤ ai j ≤ 1, and such that for every i, j, k it holds ai j + aik − 1 ≤ a jk .
Many of these matrices can be shown to be positive-semidefinite and counterexamples
are not known. Along similar lines, it can also be shown that several specializations ofValeriano AielloDepartment of Mathematics and Physics, Roma Tre University, Largo S. Leonardo Murialdo 1,00146 Roma, Italy, e-mail: valerianoaiello@gmail.com
Roberto Conti
Department of Basic and Applied Sciences for Engineering, Sapienza University of Rome, Via A.
Scarpa 16, I-00161 Roma, Italy. e-mail: roberto.conti@sbai.uniroma1.it

33

34

Valeriano Aiello and Roberto Conti

the HOMFLY polynomial, a celebrated link invariant, yields a positive-definite func→tion on the oriented Thompson group F , a notable subgroup of the Thompson groupF.

2 Preliminaries
For brevity, we will focus only on the Thompson group F, however, many of theissues make sense for the other groups too. The Thompson group F can be describedin many different ways. Here we will recall just one of them. Let T be the set ofrooted planar binary trees. Given a tree T ∈ T we will denote by ∂ T the set of its
leaves. The Thompson group F can be defined as.
F = {(T+ , T− ) ∈ T × T | |∂ T+ | = |∂ T− |}/ ∼where ∼ is the equivalence relation generated by the addition of opposite carets, theinterested reader is referred to [5, 4]. Given two elements (T+1 , T−1 ), (T+2 , T−2 ) ∈ F, in order to compute their product we pick two representatives (T+01 , T−01 ) ∼ (T+1 , T−1 ), (T+02 , T−02 ) ∼(T+2 , T−2 ) such that T−01 = T+02 and then.
(T+1 , T−1 ) · (T+2 , T−2 ) = (T+01 , T−02 ) .
It can be shown that (T, T ) is the unit for any T ∈ T and (T+ , T− )−1 = (T− , T+ ). We
mention that F is finitely presented as
F = hx0 , x1 | x2 x1 = x1 x3 , x3 x1 = x1 x4 i,.
where xn = x01−n x1 x0n−1 for n ≥ 2.
Jones introduced in [7] a graph Γ (T+ , T− ) associated with a representative (T+ , T− )of an element of F, e.g.

The chromatic polynomial of G is the polynomial Chr(G,t) such that, for any
Q ∈ N, Chr(G, Q) is the number of proper colourings of the vertices of G with Q
colours. Moreover, if e ∈ E(G), it satisfies the following condition0
if e is a loop
Chr(G, Q) =Chr(G − e, Q) − Chr(G/e, Q) otherwise.

The Thompson groups, graph polynomials, and knot theory.

35

Jones defined a function on F by Q−1 (Q − 1)−n+1 Chr(Γ (T+ , T− ), Q) for T± withn-leaves, as this expression is independent of the choice of the representative of anelement of F. Actually, this function is of positive type on F [7, Proposition 5.2.1]
according to the following definition.
Definition 1. Let G be a discrete group. A function ϕ : G → C is said of positive type(or positive definite) if the matrix (ϕ(gi g−1j ))i, j is positive semi-definite for any r ∈ N,
g1 , . . . , gr ∈ G, and a1 , . . . , ar ∈ C.
The chromatic polynomial allows us to introduce the oriented Thompson group as→

F = {g ∈ F | ChrΓ (g) (2) = 2} = {g ∈ F | Γ (g) is bipartite}
For g ∈ F, the graph Γ (T+ , T− ) admits a preferred 2-colouring, with colours + and−, starting with + on the leftmost vertex.

3 Colourings and a positive semi-definiteness problem
We examine some further combinatorial aspects of the chromatic polynomial in theabove setting.
Proposition 1. Let Ti , T j , Tk ∈ Tn . Consider the Q-colourings of Γ (Ti , T j ) and Γ (Ti , Tk ).
We denote their cardinality by Chri j and Chrik , respectively. The number of colourings that are compatible for both Γ (Ti , T j ) and Γ (Ti , Tk ) is denoted by Chri jk .Then
the following inquality holds
Chri j +Chrik −Chri jk ≤ Chrii .
In particular, it holds
Chri j +Chrik −Chrii ≤ Chr jk .
Proof. Taking into account double counting, we have the following inequality
Chri j +Chrik −Chri jk ≤ Q(Q − 1)n−1(as colourings of Γ+ (Ti )), which implies
Chri j +Chrik − Q(Q − 1)n−1 ≤ Chri jk ≤ Chr jk .
→One can recover the fact that F is a group from the above lemma. Indeed, for Q = 2,
the Chromatic polynomial takes only two values 0, 2 and, thus, given three trees
Ti , T j , Tk ∈ T with n-leaves such that Chr(Γ (Ti , T j ), Q) = 2, Chr(Γ (Ti , Tk ), Q) = 2,
the above inequality tells us that Chr(Γ (Tk , T j ), Q) = 2.
By Jones’ results the matrices (Q−1 (Q − 1)−n+1 Chr(Γ (T+i , T+j ), Q))i, j are positive
semi-definite for all choices of trees {T+i }i with n-leaves. One might wonder whether

36Valeriano Aiello and Roberto Conti

the same conclusion holds only assuming the inequalities in Proposition 1 (together
with few other natural assumptions). In particular, consider a matrix A ∈ Mr ([0, 1])such that
1. Aii = 1, for all i;
2. Ai j = A ji , for all i, j;
3. let (i, j, k) ∈ {1, · · · , r}3 be a triple with mutually distinct indices, then ai j + aik −1 ≤ a jk .
We tend to believe that for any r ∈ N a matrix A as above is always positive semidefinite. This is obviously true for r = 2 and if r = 3 it can be proved without muchtroubles. However, already for r = 4 the situation becomes much more involved andthe general argument remains elusive. We mention however that the claim can beproved in many special cases. Over the years, several conditions ensuring the positive
semi-definiteness have been examined in the literature, although we are not aware of
any result implying a complete solution to the above problem.
If we make the further assuption that A ∈ Mr ({0, 1}), then the matrix satisfies thefollowing stronger condition• let (i, j, k) ∈ {1, · · · , r}3 be a triple with mutually distinct indices. If Ai j 6= 0 and
Aik 6= 0, then A jk 6= 0.
Moreover, the above properties imply that• for any i, [A2 ]ii = ∑ j (Ai j )2 is equal to the number of 1 on the ith row (and column).
• for any i 6= j, Ai j = 0 implies [A2 ]i j = 0. In fact, [A2 ]i j = ∑k Aik Ak j . If [A2 ]i j 6= 0,
then there exists k0 6∈ {i, j} such that Ai,k0 6= 0, Ak0 , j 6= 0. However, this implies
that Ai j 6= 0.
This case corresponds precisely to 2-colourings and there are a handful of proofsof the claim in this setting. We give a quick sketch of one of them. Our aim is toshow that A can be expressed as a linear combination of orthogonal projections (withpositive coefficients). This establishes the positive semi-definiteness of A.
Consider A2 . We define the following matrices A(1) , · · · , A(r) ∈ Mr ({0, 1}) as follows. For any l ∈ 1, . . . , r, the entries of A(l) are all zero but those such that the corresponding entries in A2 are equal to l, that is1
if (A2 )i j = l(l)
Ai j =
0 otherwise.
(l)Lemma 1. If Ai j 6= 0, for some 1 ≤ l ≤ r, then for any k ∈ 1, . . . , r,Aik 6= 0 ⇔ A jk 6= 0.
Therefore, the rows i and j of A contain the same number l of non-zero entries (in thesame positions).

The Thompson groups, graph polynomials, and knot theory.

37

Proof. Suppose instead that Aik = 1 and A jk = 0. Then i, j, k are necessarily distinct
and Ai j must be 0. However, this is impossible by the assumption on A.
Next lemma shows that if a row of A(l) is nonzero then it must coincide with thecorresponding row of A.
(l)

(l)

Lemma 2. If Ai j 6= 0 and Aik 6= 0, then Aik 6= 0.
(l)Proof. Suppose instead Aik = 0. Then by the definition of A(l) we have that [A2 ]ik =(l)∑h Aih Akh 6= l. As Ai j 6= 0, we have by the Lemma 1 that the rows i, j of A have(l)exactly l entries equal to 1 (in the same positions). The hypothesis Aik = 0 meansthat the entries equal to 1 in the row k of A are in different positions with respect tothose in the row i. Therefore, there exists an index m such that Aim = 1, Akm = 0. As
i, k, m can be easily seen to be distinct, one has Aik = 0, contradicting the assumption.
(l)

As a consequence, if for some i, j one has Ai j 6= 0 then the rows i and j of A(l)coincide and contain the same number l of non-zero entries.
Lemma 3. The matrices A(k) /k are orthogonal projections.
Proof. By definition, all the matrices A(k) /k are clearly symmetric. They are also
idempotent. In fact, by the above lemma, a row (or a column) of A(k) has either all
the entries equal to 0 or has the same entries of the corresponding row in A. The
conclusion now follows by a straightforward combination of the previous results.
Theorem 1. Under the above hypotheses we have thatnA = ∑ A(k)k=0

In particular, the matrix A is positive semi-definite.
Proof. The first equation follows from the definition of A(l) . The second claim follows
from the above lemma.
Recently, Vilmos Komornik [9] gave another elegant proof of this result.

4 Further remarks
In the previous section we saw that the chromatic polynomial gives rise to functionsof positive type on the Thompson groups. We mention that many other functions(coming from graph and knot theory) admit a similar treatment. The following invariants have been studied [7, 1, 2, 3]: Chromatic polynomial, Tutte polynomial, Kauffman bracket, Jones polynomial, HOMFLY polynomial, number of Fox-colourings,

38

Valeriano Aiello and Roberto Conti

2-variable Kauffman polynomial. We briefly explain the connection with knot theory.
Jones [7] showed that links can be obtained as the closure of elements of the Thompson group F and the result does not depend on the representative up to distant unknots.
→
Moreover, for elements in F one can naturally orient the obtained link by using thedata corresponding the 2-colouring of the Γ -graph. Therefore, in the same spirit as
for the chromatic polynomial, one can use the HOMFLY polynomial P→ (α, z) to proL→

duce functions of positive type on F , the corresponding unitary representation being
associated to the category of oriented forests [3]. There are actually two possible ways
to deal with the HOMFLY, according to whether one choses the trivial *-structure or→not. In the former case one defines the HOMFLY function on F as
−n+1
1 − α −2+zP→(α, z)
P(T+ ,T− ) (α, z) = α −1
L (T+ ,T− )zand then shows that for q ∈ R \ {±1, 0} and k a positive integer, P(T+0 ,T−0 ) (qk , q − q−1 )is of positive type. The proof relies upon the statistical mechanical interpretation of
the HOMFLY polynomial discovered in [6] and the following facts→• the quantity c(L(T+ , T− )) − n is always even, where (T+ , T− ) ∈F , (T+ , T− ) is a pairof trees with n leaves and c(L(T+ , T− )) is the number of connected components of
the associated link;→• the rotation number rot( L (T+ , T− )) = n+ − n− , where n+ (resp. n− ) is the number→of vertices of Γ (T+ , T− ) labeled with colour + (resp. −) and by rot( L ) the rotation→
number of the link L .
The latter case is dealt with in [3] by using an approach developed in [8].

References
1. V. Aiello, R. Conti. Graph polynomials and link invariants as positive type functions on Thompson’s group F. arXiv:1510.04428.
2. V. Aiello, R. Conti. The Jones polynomial and functions of positive type on the oriented JonesThompson groups F and T. arXiv:1603.03946.
3. V. Aiello, R. Conti, V. F. R. Jones. The Homflypt polynomial and the oriented Thompson group.
arXiv:1609.02484.
4. J. Belk. Thompson’s group F, Ph.D. thesis, Cornell University (2004), preprint arXiv:0708.3609(2007).
5. J. W. Cannon, W. J. Floyd, W. R. Parry. Introductory notes on Richard Thompson’s groups.
Enseignement Mathématique 42, 215-256 (1996).
6. V. F. R. Jones, On knot invariants related to some statistical mechanical models, Pacific J. Math137.2 (1989): 311-334.
7. V. F. R. Jones. Some unitary representations of Thompson’s groups F and T . arXiv:1412.7740.
8. V. F. R. Jones. A no-go theorem for the continuum limit of a quantum spin chain.
arXiv:1607.08769.
9. V. Komornik, Private communication (2016).

Finiteness in real cubic fields
Zuzana Masáková and Magdaléna Tinková

Positional representation of numbers in systems with non-integer base β > 1 as defined by Rényi [11] is a suitable alternative to classical decimal or binary notation,
when encountered with the need of finite representation of numbers in an algebraic
field. A particular question is what is the most suitable choice of the base in a real
number field. One of the natural requirements is that elements with eventually periodic β -expansion form the field Q(β ). By a result of Schmidt [13], this happens
exactly for Pisot bases, i.e. such algebraic integers β > 1 that have all conjugatesinside the unit circle. It is also natural to ask that the set Fin(β ) of numbers withfinite β -expansion is closed under addition, subtraction and multiplication. This socalled finiteness property or property (F) can be reformulated by Fin(β ) = Z[β , β −1 ],and is satisfied only by Pisot numbers [6]. Moreover, not all of them. A complete
algebraic characterization of Pisot numbers with (F) is known only for the quadraticcase and cubic unit case [1]. For general degree, some sufficient conditions have been
given [6, 7]. If the base is chosen to be a unit, then Z[β , β −1 ] = Z[β ] and the (F)property is equivalent to a certain property of the corresponding Rauzy tiling. Suchgeometric interpretation is useful in describing some other arithmetic features of thenumeration system, such number of fractional digits arising in arithmetic operations.
Salem in [12] proved that every real number field can be generated by a Pisot
number β . Bertin et al. [4] provide a non-constructive proof for the fact that β can bechosen to be a Pisot unit. Requiring moreover the finiteness property, it is no longer
true that every real number field contains such Pisot unit generator. This can be seenon the case of √real quadratic fields. It turns out that existence of a Pisot unit generator
with (F) in Q( m) depends on the period-length of the continued fraction expansion
Zuzana Masáková
Department of Mathematics FNSPE, Czech Technical University in Prague
Trojanova 13, 120 00 Praha 2, Czech Republic
e-mail: zuzana.masakova@fjfi.cvut.cz· Magdaléna Tinková
Department of Mathematics FNSPE, Czech Technical University in Prague
Trojanova 13, 120 00 Praha 2, Czech Republic e-mail: tinkomag@fjfi.cvut.cz

39

40

Zuzana Masáková and Magdaléna Tinková

of the square-free integer m ∈ N. However, every quadratic field contains a generator
with property (PF), i.e. the set of finite expansions is closed at least under addition.
We focus on the question whether every cubic number field contains a generator
which is a Pisot unit with property (F). We show that this is true in case of all real
cubic fields which are not totally real. We also illustrate that in case of totally real
cubic fields the situation is more complicated. We give classes of fields which contain
unit with (F), but we also give examples of cubic totally real field where no Pisot unit
satisfies the finiteness property.
As a compensation for the number fields without a generator possessing property(F), we suggest to consider representation in negative base [8]. Analogous property(−F) can be defined by requiring Fin(−β ) = Z[β , β −1 ]. Based on the necessary conditions on β for (−F) provided in [10, 5] and the description of cubic Pisot units with(−F) given recently in [9], we show that in real quadratic and cubic number fields
not generated by a Pisot unit with (F), one always finds a Pisot unit generator withproperty (−F).
We also provide bounds L⊕ (β ) on the number of fractional digits appearing when
performing addition and subtraction of β -expansions. Such bounds were sofar given
only for a few cubic examples [3, 2].
Acknowledgements This work was supported by the Grant Agency of the Czech Technical University in Prague, grant No. SGS17/193/OHK4/3T/14.

References
1. S. Akiyama, Cubic Pisot units with finite beta expansions, in Algebraic number theory andDiophantine analysis (Graz, 1998), pages 11-26. de Gruyter, Berlin, 2000
2. P. Ambrož, Z. Masáková, E. Pelantová, Addition and multiplication of beta-expansions in generalized Tribonacci base, Discrete Math. Theor. Comput. Sci. 9 (2007), 73–88.
3. J. Bernat, Computation of L+ for several cubic Pisot numbers, Discrete Math. Theor. Comput.
Sci., 9 (2007), 175–193.
4. M.-J. Bertin, A. Decomps-Guilloux, M. Grandet-Hugot, M. Pathiaux-Delefosse, J.-P. Schreiber,
Pisot and Salem numbers, Birkhuser Verlag, Basel, 1992.
5. S. Dammak and M. Hbaib, Number systems with negative bases, Acta Math. Hungar. 142(2014), 475–483.
6. C. Frougny, B. Solomyak, Finite beta expansions, Ergodic Theory Dynam. Systems 12 (1992)
713–723.
7. M. Hollander, Linear numeration systems, finite beta expansions, and discrete spectrum of substitution dynamical systems, Ph.D. Thesis University of Washington, 1996.
8. S. Ito, T. Sadahiro, Beta-expansions with negative bases, Integers 9 (2009), A22, 239259.
9. Z. Krčmáriková, W. Steiner, T. Vávra, Finite beta-expansions with negative bases. (2017), toappear in Acta Mathematica Hungarica.
10. Z. Masáková, E. Pelantová, T. Vávra, Arithmetics in number systems with negative base, Theoret. Comp. Sci. 412 (2011), 835–845.
11. A. Rényi, Representations for real numbers and their ergodic properties, Acta Math. Acad. Sci.
Hungar, 8 (1957), 477–493.
12. R. Salem, Algebraic numbers and Fourier analysis, Heath mathematical monographs, Heath,
1963.

Finiteness in real cubic fields

41

13. K. Schmidt, On periodic expansions of Pisot numbers and Salem numbers, Bull. London Math.
Soc. 12 (1980), 269–278.

Nearly linear recursive sequences, especially SRS
Attila Pethő

My talk is based on join works with Shigeki Akiyama and Jan-Hendrik Evertse, as
well as with Jörg Thuswaldner and Mario Weitzer.
Let r = (r0 , . . . , rd−1 ) ∈ Rd , then the mapping τr : Zd 7→ Zd such thatτr (a0 , . . . , ad−1 ) = (a1 , . . . , ad−1 , −[ra])is called SRS. Equivalently we define the sequence of integers (an ) by the nearlylinear recurrence relation, in the sequel nlrs,
r0 an + · · · + rd−1 an+d−1 + an+d = en , 0 ≤ en < 1.
SRS was extensively studied recently, but only if τr is contractive or indifferent, i.e.
if the roots of the polynomial X d + pd−1 X d−1 + · · · + p0 lie inside or on the unit
circle. Then the orbits of τr are either periodic or grow polynomially. If, however, τr
is expansive no systematic investigation is known for me.
SRS is a special instance of nlrs (bn ) of complex numbers for which there exist
A0 , . . . , Ad−1 ∈ C such that
A0 bn + · · · + Ad−1 bn+d−1 + bn+d = enand the sequence (en ) is bounded.
With Akiyama and Evertse [1] we investigated nlrs. We proved a Binet-type formula for such sequences, justifying that they are growing usually exponentially. This
does not mean monotone increase, nlrs may have surprisingly large fluctuation. We
show that there exist lrs (bn ) such that lim sup bn = ∞, lim inf |bn | = 0 and bn 6= 0 for
all n. Using this result we construct nlrs of integers, for which the Skolem-MahlerAttila PethőDepartment of Computer Science, University of Debrecen, Hungary
Department of Mathematics, University of Ostrava, Czech Republik
e-mail: petho.attila@inf.unideb.hu

43

44

Attila Pethő

Lech theorem does not hold. This means that infinitely many terms of the sequence iszero, but their indices do not fit a line.
If (an ) is a nlrs and (bn ) a bounded sequence then (an + bn ) is also a nlrs. Having stronger restrictions to nlrs, for example concentrating to expansive SRS, we canobserve similar patterns as for the contractive SRS. There are expansive SRS, whichhave some bounded, thus periodic, orbits, others have only unbounded orbits. We
prove that for expanding SRS the existence of bounded orbits is algorithmically decidable.

References
1. S. Akiyama, J.-H. Evertse, On nearly linear recurrencee sequences, in C. Elsholz, P. Grabner (eds.), Number Theory - Diophantine Problems, Uniform Distribution and Applications,
Springer International Publishing, 2017.

Order statistics of the values of words withrespect to the generalised multinomial measure
Ligia L. Cristea and Helmut Prodinger

Okada, Sekiguchi and Shiota [1] introduce the multinomial measure on the unit interval, that is defined with the help of the digital expansions of the numbers in the unit
interval in a certain integer base q in the following way.

h
, for
Let q ≥ 2 be a positive integer. Denote I = I0,0 = [0, 1] and In, j = qjn , j+1
n
q
h n
i
q
−1
j = 0, 1, . . . , qn − 2, In,qn −1 = qn , 1 , for n = 1, 2, 3, . . . . Let r = (r0 , r1 , . . . , rq−1 )with 0 ≤ ri ≤ 1 and ∑q−1
k=0 rk = 1. The multinomial measure µq,r is the probability
measure on I defined byµq,r (In+1,q j+k ) = rk · µq,r (In, j )(1)for n = 0, 1, 2, . . . , j = 0, 1, . . . , qn − 1, k = 0, 1, . . . , q − 1.
We recall that the binomial measure (and generalisations thereof) is used in amethod designed by the authors Kobayashi, Muramoto, Okada, Sekiguchi and Shiota in order to study moments of higher order ∑n<N Sqd (n) of the sum-of-digits function, which for an integer q ≥ 2 and any natural number n with the q-adic expansion
n = ∑i≥0 ai qi , with ai ∈ {0, 1, . . . , q − 1}, is defined by Sq (n) := ∑i≥0 ai .
In our paper [2] we introduced the generalised multinomial measure. Here a generalisation consists, roughly speaking, in the fact that instead of dividing the unit interval into a finite number of subintervals of equal length, we divide it into infinitely(and denumerably) many intervals, such that the j-th subinterval has length pq j−1 ,where p, q > 0, and p + q = 1.
One way to define the generalised multinomial measure is the following. We consider the set W of all (finite and infinite) words over the infinite alphabet {0, 1, . . . }Ligia L. Cristea
Institute for Mathematics and Scientific Computing, University of Graz, Austria, e-mail: strublistea@gmail.com
Helmut Prodinger
Mathematics Department, Stellenbosch University, Sounth Africa, e-mail: hproding@sun.za

45

46

Ligia L. Cristea and Helmut Prodinger

and a probability measure Pr defined on the set of all words. A function value associates to every word ω ∈ W a real number value(ω) ∈ [0, 1), such that the closureof the set of all such values value(ω), is the interval [0, 1]. Then the measure of aninterval µr,q ([0, a)), with 0 ≤ a ≤ 1 can be defined in a natural way with the help of
the probability Pr , where r = (r0 , r1 , . . . ) is a sequence of real numbers (parameters)with 0 ≤ ri ≤ 1 and ∑q−1
k=0 rk = 1.
In my talk I present results on the behaviour of the average minimum value anamong n words of W chosen independently at random with respect to the generalised
multinomial measure µr,q for certain values of the parameters r j , j = 0, 1, . . . .
Furthermore, I show results for the average maximum value among n words. We
note that the final formulae obtained for the asymptotics show a certain duality.
Acknowledgements L.L. Cristea is supported by the Austrian Science Fund (FWF), stand-alone
project P27050-N26, and by the Austrian Science Fund (FWF) project F5508-N26, which is part of
the Special Research Program “Quasi-Monte Carlo Methods: Theory and Applications”.

References
1. T. Okada, T. Sekiguchi, and Y. Shiota. A Generalization of Hata-Yamaguti’s Results on the
Takagi Function II: Multinomial Case. Japan J. Indust. Appl. Math., 13:435–463, 1996.
2. L. L. Cristea, and H. Prodinger. Order statistics of the generalised multinomial measure. Monatsh.
Math., 175:333–346, 2014.

Discrepancy bounds for β -adic Halton sequencesJörg Thuswaldner

Van der Corput and Halton sequences are well-known low-discrepancy sequences.
In the 1990ies Ninomiya defined analogues of van der Corput sequences for β numeration and proved that they also form low-discrepancy sequences provided thatβ is a Pisot number. Hofer, Iacó, and Tichy define β -adic Halton sequences and showthat they are equidistributed for certain parameters β = (β1 , . . . , βs ).
In this talk we give discrepancy estimates for β -adic Halton sequences for which
the components βi are m-bonacci numbers. Our methods include dynamical and geometric properties of Rauzy fractals that allow to relate β -adic Halton sequences torotations on high dimensional tori. The discrepancies of these rotations can then be
estimated by classical methods relying on W. M. Schmidt’s Subspace Theorem.

Jörg Thuswaldner
University of Leoben, Austria e-mail: jorgthus@gmail.com

47

Algebraic structure and numeration systems forcircular words
Isabelle Dubois

We investigate some properties of finite abelian groups defined by equivalence relations on circular words. In particular, we show how the formalism of circular words
gives rise naturally to the notion of numeration systems for some finite abelian groups,
and to periodic expansions of real numbers in [0; 1[.
Our basic structure is the notion of circular words, introduced in the algebraic
context in [2] by B. Rittaud and L. Vivier.
A circular word of length ` is a finite word made of ` letters on the alphabet Z,
indexed by Z/`Z. The set of circular words of length ` is then an abelian group and we
consider an equivalence relation that defines a “carry” given by an integer polynomial.
More precisely, given a polynomial P(X) = ∑0≤i≤d ai X i ∈ Z[X], the carry equivalence≈ defined by P on circular words W = (w0 . . . w`−1 ) (where the indices are modulo `)is based on the relations:∀i mod `,W ≈ (w0 . . . (wi−d + a0 ) . . . (wi−1 + ad−1 )(wi + ad )wi+1 . . . w`−1 ).
When P has no roots of unity, the quotient group of circular words of length ` bythis carry equivalence is a finite abelian group whose structure is determined by algebraic and arithmetic tools. We can then define a numeration system on these groups,
which leads to a numerical system of the classes of finite circular words and to periodic expansions of some real numbers.
Some examples are given, in particular for a carry equivalence from a linear polynomial aX − b, or from a quadratic polynomial X 2 − pX − q generalizing the resultsof [1]. Algebraic rather than combinatorial tools are used, which allow a more systematic and general study.
This is a joint work with Benoı̂t Rittaud.
Isabelle Dubois
IECL, Université de Lorraine, Metz, France, e-mail: isabelle.dubois@univ-lorraine.fr

49

50

Isabelle Dubois

References
1. Benoı̂t R ITTAUD, “Structure of Classes of Circular Words defined by a Quadratic Equivalence”,
RIMS Kôkyûroku Bessatsu, B 46, 231-239 (2014-06).
2. Benoı̂t R ITTAUD & Laurent V IVIER, “Circular words and three applications: factors of the
Fibonacci word, F -adic numbers, and the sequence 1, 5, 16, 45, 121, 320,. . . ”, Functiones etApproximatio 47, n◦ 2, 207-231 (2012).

A constrained Diophantine equation on
symmetric numbers in different bases
Stefano Arnone, Corrado Falcolini, Francesco Moauro, and Matteo Siccardi

Abstract Any number may be written in many different ways, using different stringsin different bases. In few, very special cases, a symmetry emerges which is usuallyhidden beneath the surface: the strings “230” in base 164 and “164” in base 230
are both equal to 54284 in base 10. This talk analyzes the infinite solution set ofthe (constrained) Diophantine equation that implements such symmetry, and showsinteresting patterns emerging both from a geometrical and analytic point of view. We
will discuss these patterns and formulate a conjecture on the number of solutions of
the equation.
The relationship between numbers in different bases will be investigated.
In order to avoid ambiguities, our symbols will be numerals in base ten, e.g. in thefollowing {1, 15}16 will be used in place of what is commonly written as 1F16 . As
far as notation is concerned, N with no lower indices will be used to denote the list,
N = {nP , nP−1 , · · · , n2 , n1 , n0 }, while N with a lower index (representing a base) will
indicate the number, evaluated in that base, Nb = nP bP + nP−1 bP−1 + · · · + n1 b + n0 .
For instance, 230 = {2, 3, 0} whereas 230164 = 2 · (164)2 + 3 · (164)1 + 0 · (164)0 .
Now, “a kind of magic” may take place: {2, 3, 0} {1, 6, 4} = {1, 6, 4} {2, 3, 0},
where the equal sign refers to the equality of the two numbers represented by thedifferent lists in different bases. The above is a shorthand for
Stefano Arnone
Department of Mathematics, Natural and Computer Sciences, John Cabot University, Via della Lungara, 233, 00165 Roma (Italy), e-mail: sarnone@johncabot.edu
Corrado Falcolini
Department of Architecture, Roma Tre University, Via della Madonna dei Monti, 40, 00184 Roma
(Italy) e-mail: falco@uniroma3.it
Francesco Moauro
Physics Department, Sapienza University, P.le Aldo Moro, 1, 00185 Roma (Italy) e-mail:francesco.moauro@gmail.com
Matteo Siccardi
Department of Mathematics, Natural and Computer Sciences, John Cabot University, Via della Lungara, 233, 00165 Roma (Italy), e-mail: emme.esse@gmail.com

51

52

Stefano Arnone, Corrado Falcolini, Francesco Moauro, and Matteo Siccardi{2, 3, 0} {1, 6, 4}= 2·(1·102 +6·101 +4·100 )2 +3·(1·102 +6·101 +4·100 )1 +0·(1·102 +6·101 +4·100 )0= {5, 4, 2, 8, 4} {1, 0} = {1, 6, 4} {2, 3, 0}This phenomenon is not restricted to or peculiar of base ten. For instance,{2, 1, 1} {1, 2, 1}three = {1, 2, 1} {2, 1, 1}three ,where the reference base has been written in letters.
Generalizing the simple observation that
N {1, 0} = {1, 0} N,(1)

N being any list except {0} and {1}, we will speculate on the existence of solutions
to the following equation:
N Mb = M Nb .
(2)
For the sake of clarity and effectiveness, we expand eq. (2)
P

!k

Q
i

∑ nk ∑ b mi
k=0

i=0

Q

= ∑ mi
i=0

!i

P
k

∑ b nk

,

(3)

k=0

where b is the base and the lists N, M contain P + 1 and Q + 1 elements respectively.
All elements — mi , nk — are constrained to the range [0, b − 1] and, in order to avoid
ill-defined expressions, if one list contains one element only, the other cannot — thatis (P, Q) 6= (0, 0). Such restrictions upon the form of possible solutions will be seen
to play an important role in the following. Solving our problem amounts to finding allof the solutions to eq. (3).
Meaningful solutions of eq. (2) are lists of integers satisfying a number of constraints. Therefore, we are bound to solve a Diophantine equation with additional
constraints.
As eq. (2) is symmetric under the exchange M ↔ N, we can and will search forsolutions in M, at fixed N. We can also impose M ≥ N as a non-restrictive constraint.
An immediate consequence of the above is that the solution M = N, hereafter referred
to as the symmetric solution, satisfies eq. (2).
Another solution that is easy to find is given by the following
Theorem 1 Any M satisfies eq. (2) if N = {1, 0}
which generalizes eq. (1) to any base b. Such a solution will be hereafter referred toas the trivial solution.
Regular patterns are seen to emerge when considering simplifying assumptions.
One such well-defined set of solutions is given in the following
Theorem 2 Solutions of eq. (2) exist of the form n0 = 0, nk = Pk for k > 0, m0 = 0,
mi = Qi for i > 0, ∀P > Q > 0 and ∀b > max Pk .
k

A constrained Diophantine equation on symmetric numbers in different bases53

Due to their structure, for a given P we can read all lists M which are solutions ofeq. (3) from the first rows of a slightly modified Pascal’s triangle.
We next show that solutions exist for lists having only one non-zero element.
Theorem 3 Solutions of eq. (2) exist of the form M = {ah , 0, . . . , 0}, N = {ak , 0, . . . , 0},
Q = nh + 1, and P = nk + 1 ∀n ∈ N0 , ∀a ∈ {1, . . . , b − 1} such that ah , ak < b.
The solutions so far presented are independent of the reference base b, although
Theorems 2 and 3 do have a base-dependent constraint.
Eq. (3) can be interpreted as a constraint on two polynomials in the reference
base, b. More specifically, finding a base-independent solution is tantamount to constructing two polynomials in b which commute under composition. Block and Thielman [Block and Thielman, 1951], building on previous work by Ritt [Ritt, 1922,
Ritt, 1923], have shown what the properties of commuting polynomials are in thecase they do not have the same degree, and were able to organize them in two different classes. Translating their results into our “language” allowed us to conclude
that the only base-independent solutions with different number of elements are thoselisted above [Pakovich, 2013, Arnone et al., 2017].

1 Solutions with equal number of elements
1.1 Two elements
When M, N contain two elements each, that is P = Q = 1, it is possible to rewrite theDiophantine eq. (3) as(n1 − 1)m0 = (m1 − 1)n0 .
(4)
As before, the only dependence upon the base b comes from the constraint that theelements cannot exceed it, which implies an increase in the number of solutions as
the base grows large. The exact result is






b−1
b−2 
b−2 2
b − 1 2,+
(5)
S2 (b) = 4(b − 1)2 + ∑ ∑
ϕ(m1 ) m1
m0
m0 =m1 +1
m1 =1
gcd(m0 ,m1 )=1

where ϕ(x) is the Euler totient function.

1.2 Three elements
When M, N contain three elements each, that is P = Q = 2, the Diophantine eq. (2)takes the form

54

Stefano Arnone, Corrado Falcolini, Francesco Moauro, and Matteo Siccardi
100
90
80
70
60
N

50
40
30
20
10

Fig. 1 Solutions to eq. (4) for
any base greater than or equal
to ten.

10

20

30

40

50

60

70

80

90

100

M

N Mb = n2 (m2 b2 + m1 b + m0 )2 + n1 (m2 b2 + m1 b + m0 ) + n0
= m2 (n2 b2 + n1 b + n0 )2 + m1 (n2 b2 + n1 b + n0 ) + m0 = M Nb , (6)that is a polynomial equation of degree 7 in 3+3+1 variables, {m2 , m1 , m0 ; n2 , n1 , n0 ; b},where the dependence upon b no longer disappears.
Solutions to eq. (6), other than the symmetric ones, have been obtained, up tob = 400, via a numerical algorithm [Arnone et al., 2017].
Preliminary analysis shows that infinite families of solutions exist, which may becast into two different categories. The former contains solutions where the base can be
expressed as a (linear or quadratic) function of an integer, k, an example of which is
given by M = {k + 1, 2k + 
1, 13k − 5}, N = {k, 10k + 1, 5k}, b = 16k + 5. The latter ispexemplified by M = {4, 21 1 + 8i − 8p + 1 + 16p + 48p2 , 0}, N = {3, 3i + 1, 0},b = p − i, for an infinite sequence of ps, coming from the Pell-type structure of oneof the constraints, and a finite range for i for each p. Further investigation reveals
that another, geometric perspective may be adopted, which sheds more light on the
structure of the solution set.
Figure 2 shows the graphs of two second-degree polynomials which commute under composition at a specific, positive integer value of the independent variable b,
together with two secants to such parabolae. The secant lines go through the points(b, N(b)), (M(b), N(M(b))) and (b, M(b)), (N(b), M(N(b))) respectively. Owing to
the fact that the two polynomials commute at b, N(M(b)) equals M(N(b)), so that b
is a solution to eq. (6).
The point of intersection of the secants, I, can be shown to lie on the bisector of
the first quadrant angle; its coordinates are bounded between b − 1 and b. Computing
the coordinates of I for each of the known solutions holds the key to a better representation of the whole set. As a matter of fact, re-expressing the known families interms of the base b — as opposed to k or p — and other two parameters, and plotting
the pairs1 (b, 1 − {xI (b)}) reveals the patterns shown in fig. 3.
1 Here {x } stands for the fractional part of x , {x } = 1 − bx c.
I
IIIA constrained Diophantine equation on symmetric numbers in different bases

55

Fig. 2 A new, geometricperspective elucidating thestructure of solutions. The red
curve is N(x), whereas thegreen one is M(x).

The grey curves, corresponding to equal values of the two additional parameters,
represent the fine spectral lines of our “Diophantine atom”: for a given value of n2
these are seen to form a band, which gets smaller and smaller the larger n2 grows.
The curves in different colours correspond to equal values of the other additionalparameter: when they intersect a spectral line at a solution, they always cut throughthe mid-point of the patch.
Several solutions have been found that have not been classified yet, and the question remains as to whether a base b̄ exist such that solutions can be found for all bases
greater than b̄.

1.3 Four or more elements
When P = Q = 3, that is in the case of four elements, eq. (2) is of degree 13 in 4+4+1
variables.
No explicit solutions, except for the symmetric ones, have been found numerically. This appears to be consistent with a series of results that have been obtained onbounds for feasible solutions. Indeed, the region in the M − N plane where solutions
might be found shrinks down to a smaller and smaller size as the number of elements
increases.
The lack of non-symmetric solutions when N, M have at least four elements eachmotivated us to formulate the following

56

Stefano Arnone, Corrado Falcolini, Francesco Moauro, and Matteo Siccardi
Solutions: (n2, pn2, - n2 b , 0 ,rpn2,- =

p n2 ,+ n2 , qn2, - ( +n2) b , 0 , b)
r

r

+ n2

q n2 ,<bpn2,0=

pn2 =2n2+ , pn2, + =(4n2+3)(pn2, -pn2, - )+pn2, -2

qn2,- =0, qn2,0=

qn2 =2n2+2 , qn2, + =(4n2+3)(qn2, -qn2, - )+qn2, -2

1

1

,1

r

,1

r

1

r

1

r

r

r

1

1

r

+ n2
r

r

1-{x (b)}
I

1.0

0.8

(n2 ) = ((n2 ) = (0.6

(n2 ) = (

)

)

)

(2,3)

(2,2)
0.4

(3,3)

(3,2)
(4,2)
0.2

)

(
0

100

200

300

400

b

Fig. 3: Our “Diophantine atomic” structure.

Conjecture 1. Let ni , mi be non-negative integers,
N = {nP , nP−1 , . . . , n0 },andM = {mP , mP−1 , . . . , m0 },with mP nP 6= 0. Then, ∀ b ∈ N ∀P > 2,
N 6= M⇒

N Mb 6= M Nb .

References[Arnone et al., 2017] Arnone, S., Falcolini, C., Moauro, F. and Siccardi, M. (2017). On Numbers in
Different Bases: Symmetries and a Conjecture. Experimental Mathematics, 26, no. 2:197–209.
[Block and Thielman, 1951] Block, D. and Thielman, P. (1951). Commutative polynomials. Quarterly Journal of Mathematics Oxford Series, 2:241–243.
[Pakovich, 2013] Pakovich, A. (2013). Generalized ’second Ritt theorem’ and explicit solution of
the polynomial moment problem. Compositio Mathematica, 149:705–728.
[Ritt, 1922] Ritt, J. F. (1922). Prime and composite polynomials. Transanctions of the American
Mathematical Society, 23, no. 1:51–66.

A constrained Diophantine equation on symmetric numbers in different bases

57[Ritt, 1923] Ritt, J. F. (1923). Permutable rational functions. Transanctions of the American Mathematical Society, 25, no. 3:399–448.

On the structure of periodic elements ofsimultaneous systems
Gabor Nagy

Abstract It is well-known (see [1]) that (−N1 , −N2 , Ac ) is a simultaneous number
system if and only if 2 ≤ N1 , N2 and |N1 − N2 | = 1, where N1 , N2 are rational integers
and Ac = {0, 1, . . . , |N1 ||N2 | − 1}. The aim of this talk is to determine the structure ofperiodic elements when N1 , N2 do not fulfil the aforementioned assumption.
The case of simultaneous systems of Gaussian integers is also considered (see [2]).

References
1. K-H Indlekofer, P Racskó, and I Kátai. Number systems and fractal geometry. In Probability
theory and applications, pages 319–334. Springer, 1992.
2. Gábor Nagy. On the simultaneous number systems of gaussian integers. In Annales Univ. Sci.
Budapest, Sect. Comp, volume 35, pages 223–238, 2011.

Gabor Nagy
ELTE Eötvös Loránd University, Budapest, Hungary, e-mail: nagy@compalg.inf.elte.hu

59

Numbers, systems, applications
Attila Kovács

Abstract The lecture presents the newest results achieved in (1) constructing number
systems in the ring of integers of real quadratic fields, (2) showing how the number
system concept can be applied to kleptographing the RSA public key scheme.
Let Λ be a lattice in Rn and let M : Λ → Λ be a linear operator such that det(M) 6=
0. Let furthermore 0 ∈ D ⊆ Λ be a finite subset.
Definition 1 The triple (Λ , M, D) is called a number system (GNS) if every element
x of Λ has a unique, finite representation of the formLx = ∑ M i di ,i=0where di ∈ D and L ∈ N. L is the length of the expansion.
Here M is called the base and D is the digit set.
Theorem 2 If (Λ , M, D) is a number system then
1. D must be a full residue system modulo M,
2. M must be expansive,
3. det(In − M) 6= ±1. (unit condition)
If a system fulfills the first two conditions then it is called a radix system.
ϕ

Let ϕ : Λ → Λ , x 7→ M −1 (x−d) for the unique d ∈ D satisfying x ≡ d (mod M). Since
M −1 is contractive and D is finite, there exists a norm k.k on Λ and a constant C suchthat the orbit of every x ∈ Λ eventually enters the finite set S = {x ∈ Λ | kxk < C}
for the repeated application of ϕ. This means that the sequence x, ϕ(x), ϕ 2 (x), . . . iseventually periodic for all x ∈ Λ . Clearly, (Λ , M, D) is a number system iff for everyx ∈ Λ the orbit of x eventually reaches 0.
Attila Kovács
Eötvös Loránd University, Budapest, e-mail: attila.kovacs@inf.elte.hu

61

62

Attila Kovács

A point p is called periodic if ϕ k (p) = p for some k > 0. The orbit of a periodic
point p is a cycle. The set of all periodic points is denoted by P. The signature(l1 , l2 , . . . , lω ) of a radix system (Λ , M, D) is a finite sequence of non-negative integers
in which the periodic structure P consists of #li cycles with period lenght i (1 ≤ i ≤ω). Clearly, the signature of a number system is (1).
The following problem classes are in the mainstream of the research: for a given(Λ , M, D)• the decision problem asks if the triple form a number system or not,• the classification problem means finding all cycles (witnesses),• the parametrization problem means finding parametrized families of number systems,• the construction problem aims at constructing a digit set D to M for which(Λ , M, D) is a number system. In general, construct a digit set D to M such that(Λ , M, D) satisfies a given signature.
Regarding the decision and classification problem the algorithmic complexity
is unknown. For the practical analysis software packages were designed and implemented (please, visit the talk of Tamás Krutki of this conference), see also
[1, 22, 27, 3, 33, 37].
Families of number systems were analysed by different authors and researchgroups, especially for canonical digit sets in the {1, θ , . . . , θ n−1 } basis, where M is thecompanion of the polynomial p(x) = c0 +c1 x +· · ·+cn−1 xn−1 +xn ∈ Z[x] and f (θ ) =0, since this is the most natural generalization of the usual binary or decimal number
system concept (see [1, 2, 3, 4, 5, 7, 8, 12, 18, 19, 20, 21, 23, 24, 25, 26, 28, 32]).
The construction problem was analysed in the quadratic fields by ([6, 11, 31]), in
two dimensional simultaneous systems by [34, 35], and in general by [14, 29, 36].
There are only a few results regarding the signature analysis [13, 16, 17]. The firstpart of the talk is about number system constructions with integers in real quadratic
fields.
There are only a few application regarding the concept of generalized number
systems [9, 10].
Kleptography is the study of stealing information securely and subliminally. A
kleptographic attack is an attack which uses asymmetric cryptography to implementa cryptographic backdoor. Kleptographic attacks have been designed for RSA key
generation, the Diffie–Hellman key exchange, the Digital Signature Algorithm, andother cryptographic algorithms and protocols.
The other part of the talk is about how generalized binary number systems can beapplied in cryptography, especially in kleptography.

References
1. Kátai, I., Szabó, J., Canonical number systems for complex integers, Acta Sci. Math. (Szeged),37, (1975), 255–260.

Numbers, systems, applications

63

2. Kátai I., Kovács, B., Kanonische Zahlensysteme in der Theorie der quadratischen algebraischen
Zahlen, Acta Sci. Math. (Szeged), 42 (1980), 99–107.
3. Kátai I., Kovács, B., Canonical number systems in imaginary quadratic fields, Acta
Math. Acad. Sci. Hungar., 37, (1981), 159–164.
4. Kovács, B., Canonical number systems in algebraic number fields, Acta Math. Acad. Sci. Hungar., 37, (1981), 405–407.
5. Gilbert, W.J., Radix representations of quadratic fields, J. Math. Anal. Appl., 83, (1981), 264–274.
6. Steidl, G., On symmetric representation of Gaussian integers, BIT, 29, (1989), 563–571.
7. Grossman, E.H., Number bases in quadratic fields,√ Studia Sci. Math. Hungar., 20, (1985), 55–58.
8. Körmendi, S., Canonical number systems in Q 3 2, Acta Sci. Math., (Szeged), 50 (1986), 351–
357.
9. Pethő, A., On a polynomial transformation and its application to the construction of a publickey cryptosystem, Computational number theory (Debrecen, 1989), de Gruyter, Berlin, (1991),
31–43.
10. Vince, A., Radix representation and rep-tiling, Congressus Numerantium, 98, (1993), 199–212.
11. Kátai, I., Number systems in imaginary quadratic fields, Annales Univ. Sci. Budapest.,
Sect. Comp., 14, (1994), 91–103.
12. Thuswaldner, J.M., Elementary properties of canonical number systems in quadratic fields, in:Applications of Fibonacci Numbers, 7, G. E. Bergum et al. (eds.), Kluwer, Dordrecht (1998),
405–414.
13. Kovács, A., On expansion of Gaussian integers with non-negative digits, Mathematica Pannonica, 10/1, (1999), 177–191.
14. Kátai, I., Construction of number systems in algebraic number fields, Annales Univ. Sci. Budapest., Sect. Comp., 18, (1999), 103–107.
15. Kovács, A., On computation of attractors for invertible expanding linear operators in Zk , Publ.
Math. Debrecen, 56/1–2, (2000), 97–120.
16. Kovács, A., Canonical expansions of integers in imaginary quadratic fields, Acta Math. Hungar,
93/4, (2001), 347–357.
17. Thuswaldner, J., Attractors for invertible expanding linear operators and number systems in Z2 ,Publ. Math. Debrecen, 58, (2001), 423–440.
18. Kovács, A., Generalized binary number systems, Annales Univ. Sci. Budapest, Sect. Comp., 20,(2001), 195–206.
19. Brunotte, H., On trinomial bases of radix representations of algebraic integers, Acta
Sci. Math. (Szeged), 67, (2001), 521–527.
20. Brunotte, H., Characterization of CNS trinomials, Acta Sci. Math. (Szeged), 68, (2002), 673–
679.
21. Akiyama, S., Pethő, A., On canonical number systems, Theor. Comp. Sci., 270/(1-2), (2002),
921–933.
22. Kovács, A. On number expansions in lattices, Math. Comp. Modelling., 38, (2003), 909–915.
23. Akiyama, S., Brunotte, H., Pethő, A., Cubic CNS polynomials, notes on a conjecture ofW.J. Gilbert, J. Math. Anal. and Appl., 281, (2003), 402–415.
24. Brunotte H., On cubic CNS polynomials with three real roots, Acta Sci. Math (Szeged), 70,(2004), 495–504.
25. Akiyama, S., Rao, H., New criteria for canonical number systems Acta Arith., 111 (2004), 5–25.
26. Akiyama, S., Borbély, T., Brunotte, H., Pethő., A., Thuswaldner, J.M., On a generalization of
the radix representation a survey , in “High Primes and Misdemeanours: lectures in honour of
the 60th birthday of Hugh Cowie Williams”, Fields Institute Commucations, 41, (2004), 19–27.
27. Burcsi, P., Kovács, A., An algorithm checking a necessary condition of number system constructions, Annales Univ. Sci. Budapest, Sect. Comp. 25, (2005), 143–152.
28. Brunotte, H., Huszti, A., Pethő, A., Bases of canonical number systems in quartic algebraic
number fields, Journal de théorie des nombres de Bordeaux, 18, (2006)/3, 537–557.
29. Germán, L., Kovács, A., On number system constructions, Acta Math. Hungar., 115/(1-2),(2007), 155–167.

64

Attila Kovács

30. Burcsi, P., Kovács, A., Papp-Varga, Zs., Decision and Classification Algorithms for Generalized
Number Systems, Annales Univ. Sci. Budapest, Sect.
√ Comp., 28, (2008), 141–156.
31. Farkas, G., Kovács, A., Digital expansion in Q( 2), Annales Univ. Sci. Budapest., Sect. Comp.,
22, (2008), 83–94.
32. Burcsi, P., Kovács, A., Exhaustive search methods for CNS polynomials, Monatshefte für Mathematik, 155, (2008), 421–430.
33. Tátrai, A., Parallel implementations of Brunotte’s algorithm, Journal of Parallel and Distributed
Computing, 71/4, (2011), 565–572.
34. Kovács, A., Algorithmic construction of simultaneous number systems in the lattice of Gaussian
integers, Annales Univ. Sci. Budapest, Sect. Comp., 39/1, (2013), 279–290.
35. Kovács, A., Simultaneous number systems in the lattice of Eisenstein integers, Annales
Univ. Sci. Budapest, Sect. Comp., 41, (2013), 43–55.
36. Kovács, A., Number system constructions with block diagonal bases, RIMS KokyurokuBessatsu, B46, ‘Numeration and Substitution’, (2014), 205–213.
37. Hudoba, P., Kovács, A., Some improvements on number expansion computations, submitted.

Interactions between digits in Fibonacci
Numeration
Anne Bertrand Mathis

A positive integer m can be written in “Fibonacci base” in a unique way: let (Gn )n≥0
be the numeration sequence G1 = 1, G2 = 2, and Gn = Gn−1 + Gn−2 for n ≥ 3; thenm = εr Gr + ... + ε1 G1 where the digits εi belongs to {0, 1} and whereεi+1 εi = 0 for√
all i; we say that εr ...ε1 is the expansion of m. We set Φ = 1+2 5 so the algebraic

√
n+1 
n+1 − (−1)√1conjugate of Φ is 1−2 5 = −1
; Gn is equivalent toΦ , and Gn = 5 ΦΦn√1 (Φ)n+1 . We say that εn is the nth digit on the left and we say also that εn is “the5digit of the Φ n−1 ” (ε1 is the digit of unities, ε2 the digit of the Φ, ε3 the digits of theΦ 2 and so on) as in base ten in 645 the first digit 5 is the digit of unities, the second

digit 4 is the digit of the dozens, the third digit 6 is the digit of the hundreds.
We prove that at the time where the nth digit increases by 1 it was late with respect
to all (n − i)th digits and becomes (just after growing) early with respect to all (n −i)th digits. So the digits are interlinked with an extraordinary precision, their motion
being orchestrated by a substitution. You can imagine an helical gears with an infinite
numbers of pulleys, the letters of the substitution playing the role of the pulleys.
An alphabet is a set of letters, a word (finite or infinite) is a sequence on thisalphabet; the length of a finite word w is the number of letters that it contains and isdenoted by | w |. The classical Fibonacci word is defined as follows [6] [7] : we set
σ 0 (a) = ab and σ 0 (b) = a; the map σ 0 extends to all word on the alphabet {a, b}
by concatenation; as σ 0 (a) begin with a, σ 0k (a) is the beginning of σ 0k+1 (a) anditerating the processus we obtain a σ 0 −invariant infinite word σ ∞ (a) = abaababa...:this is the Fibonacci word. We shall use another very similar Fibonacci word adapted
to our problem: let B = {b1 , b2 , b3 , ...} be an enumerable set of letters, and let σ be
the map b1 7−→ b1 b2 , b2 7−→ b3 , b3 7−→ b1 b4 , b4 7−→ b5 and more generally b2k 7−→
b2k+1 , b2k+1 7−→ b1 b2k+2 ; the map σ extend to all finite word by concatenation andas b1 is the beginning of σ (b1 ), for all n σ n (b1 ) is the beginning of σ n+1 (b1 ); thus
Anne Bertrand Mathis
University of Poitiers UMR 7348 Departement de Mathèmatiques SP2MI BP 30179 86000 Futuroscope cedex e-mail: anne.bertrand@math.univ-poitiers.fr

65

66

Anne Bertrand Mathis

iterating the process we obtain a σ −invariant infinite word σ ∞ (b1 ) = u0 u1 ... also
called Fibonacci substitutive word. The following Lemma is clear:
Lemma 1. If we replace all the b2k+1 by a and all the b2k by b, σ becomes theclassical substitution σ 0 : a 7−→ ab and b 7−→ a; for all n ≥ 0 , | σ n (b1 ) |=| σ 0n (a) |and σ ∞ (b1 ) becomes the classical Fibonacci word σ 0∞ (a).
Transferring classical results from σ 0 to σ we obtain the: n+1

Lemma 2. For all n ≥ 0, | σ n (b1 ) |= Gn+1 and Gn = √15 Φ n+1 − (−1).
Φ n+1
For all n ≥ 1 the expansions of the | σ n (b1 ) |= Gn+1 first numbers (starting from0) are exactly those admitting at most n digits.
More, m = εr Gr + ... + ε1 G1 if and only if the beginning of the substitutive word
σ ∞ (b1 ) = u0 u1 .... is u0 ...um = (σ r (b1 ))εr (σ r−1 (b1 ))εr−1 ...(σ 1 (b1 ))ε2 (σ 0 (b1 ))ε1 .
Going from m to m + 1, the hth digit either increases by 1, or vanishes, or remains
fixed.
Theorem 1. Suppose that the expansion of an integer m is εr ...ε1 and that the termum in the sequence σ ∞ (b1 ) = u0 u1 ... is bk ; then the expansion of m + 1 is obtained
from the expansion of m as follows: the kth digit on the left εk increased from +1(or appears if they were no kth digit), the digits εk−1 , ..., ε1 becomes 0 and the digits
εk+1 , εk+2 , ... do not change.
Thus we obtain a method allowing to write the sequence of integers in Fibonaccibase; the term um point out what to do in order to obtain the expansion of m + 1 fromthe expansion of m.
Remark: it is possible to expand positive integers in all base β > 1 [3] and this substitutif phenomen can be generalised to all the bases; one even can expand numbersof Z in a base −β < −1 [4], define an associated substitution and study his effect on
the expansion of successive integers.
Look for example at the first expansions: G1 , G2 , G3 , G4 , G5 , G6 = 1, 2, 3, 5, 8, 13;
the beginning u0 ...u12 = u0 ...uG6 −1 of σ ∞ (b1 ) = u0 u1 ...u12 isb1 b2 b3 b1 b4 b1 b2 b5 b1 b2 b3 b1 b6 ;the following data (expansions smaller than G6 = 13 = σ 5 (b1 ), just below their position in the sequence (un )n≥0 and the corresponding bi ) explain how to go from m to
m + 1:
0 1 10 100 101 1000 1001 1010 10000 10001 10010 10100 10101
u0 u1 u2 u3 u4 u5 u6 u7
u8
u9
u10
u11
u12
b1 b2 b3 b1 b4 b1 b2 b5
b1
b2
b3
b1
b6
You can see that till m = 12 if the letter um is bk , this letter says: to go from the
expansion of the number m to the expansion of m + 1, add 1 to the kth digit on the left,
replace the hth digit by zero if h < k and do not change the other digits.
And the term uGn −1 is always equal to bn and point out that m + 1 = Gn = 10n−1
owns n digits.
 √ hThe kth digit grows Φ h = 1+2 5 faster than the (h + k)th digit. So

Interactions between digits in Fibonacci Numeration

67

Theorem and definition 2. Suppose that until reaching a number m the kth digit
increased xk times and the (h + k)th digit increased xh+k times; we say that the (h +k)th is late with respect to the kth digit if xh+k < Φxkh and is early if xh+k > Φxkh .(Φ is an
irrational number so there is never equality).
At the time where the nth digit increase by 1 it was late with respect to all the(n − i)th digits and becomes (just after growing) early with respect to all (n − i)th
digits.
For all k ≥ 1 and h ≥ 1, xh+k < Φxkh < 1.
Let dn the number of times where the first digit (the digit of unities) has increased
before reaching the number Gn = 10n−1 and set G0 = G−1 = 1;then for 
all n ≥
1,
−1
1
n−1
√
dn = Gn−2 (we shall consider that d0 = 0) and for n ≥ 2 dn = 5 Φ− Φ n−1.
Let n ≥ k. The number of times where the (k + 1)th digit increased in the | σ n (b0 ) |first numbers (owning at most n digits ) is dn−k .
Let m = εr Gr + ... + ε1 G1 an integer ≥ 1.
Then the number x1 (m) of times where the right digit increased between 0 and m
is x1 (m) = εr dr + ... + εk+1 dk+1 + ... + ε1 d1 = ∑ri=1 εi Gi−2
The number of times xk+1 (m) where the (k + 1)th digit increased between zero andm is xk+1 (m) = εr dr−k + ... + εk+1 d1 = ∑ri=k+1 εi Gr−k .
A calculus allows to compare x1 (m) and xk+1 (m) and to prove the Theorem 2.
Another proof can be given using the simplicity of the Rauzy tiling and remains valid
in the quadratic unimodular Pisot case.
Remark: for every base β there is a similar substitution who controls the passing
from m = 1 to m + 1; the kth digit grows β h faster than the (h + k)th digit, this allows
by example to recover Christiane Frougny’s results [1] [2] on carries.

References
1. V. Berthè, Ch. Frougny, M. Rigo, J. Sakarovitch, On the cost and complexity of the successor
function, in P.Arnoux,N.Bedaride and J. Cassaigne (eds), Proc. Words 2007, Tech. Rep., Institutde Mathèmariques de Luminy (Marseille) 2007, 43-56.
2. V. Berthè, Ch. Frougny, M. Rigo, J. Sakarovitch, On the concrete complexity of the successor
function, Part1: The carry propagation, en prèparation.
3. A. Bertrand-Mathis, Comment ècrire les nombres entiers dans une base qui n’est pas entiére, Acta
Math.Hungar. 54( 1989) n.°3-4 237-241.
4. A. Bertrand-Mathis, How to write relative numbers in a noninteger basis,Uniform Distribution
Theory 9, 2014, n°2, 125-134.
5. C.J. Lekkerkerker, Representation of natural integers as a sum of Fibonacci Numbers (Dutch)
Simon Stevin, 29 (1952) 190-195
6. M. Lothaire, Algebraic combinatorics on words,Encyclopedia of Mathematics and applications,n° 90,Cambridge University Press, Cambridge (2002).
7. M. Queffelec, Substitution dynamical systems, spectral analysis L.N.in Math.1924 Springer
Berlin (2010).
8. E. Zeckendorf, Reprèsentation des nombres naturels par une somme de nombres de Fibonacci ou
de Lucas, Bull.Soc.Roy.Sci.Liége 41 (1972),179-182.

Bernoulli convolutions, Garsia entropy and local
dimension
Kevin G. Hare

This talk will discuss joint work with Kathryn E. Hare, Kevin R. Matthews, Michael
Ka Shing Ng, Nikita Sidorov and Grant Simms. Much of this work can be found in[10, 11, 12, 13, 14].
Let β ∈ (1, 2). Consider the expansion∞

x = ∑ a jβ − jj=1where a j ∈ {0, 1}. Then a1 a2 a3 · · · is a beta-expansion for x. It is easy to see that x
1].
will have a beta-expansion if and only if x ∈ Iβ := [0, β −1
One interesting property of non-integer expansions is that it is possible to havemultiple different representations for the same value. For example, consider β thegolden ratio, β ≈ 1.618, the larger root of x2 − x − 1 = 0. Notice that1 = β1 + β12
or111= β + β3 + β4
or
1
1
1
1
1
= β + β3 + β5 + β7 + β9 + ··· .
In the case of the golden ratio, some x have only one expansion (such at x = 0), somehave countably many expansions, and some even have uncountably many expansions.
Intimately connected with beta-expansion is the idea of Bernoulli convolutions,denoted by µβ . We can think of this as a measure which has weight focused where
there are lots of beta-expansions. These were first studied by by Rényi and by Parry[20, 23]. Let us recall the basic definitions.
Let µβ denote the Bernoulli convolution parameterized by β on Iβ by

Kevin G. Hare
Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1,
e-mail: kghare@uwaterloo.ca

69

70

Kevin G. Hare

(

∞

)

µβ (E) = P (a1 , a2 , . . . ) ∈ {0, 1}N : ∑ ak β −k ∈ E
k=1

for any Borel set E ⊆ Iβ , where P is the product measure on {0, 1}N with P(a1 = 0) =P(a1 = 1) = 1/2.
An alternate way of defining µβ is as the unique measure such that:11µβ = µβ ◦ S0−1 + µβ ◦ S1−1 ,22where S j = x/β + j for j = 0, 1.
Bernoulli convolutions have been studied since the 1930s (see, e.g., [25] and references therein). An important property of µβ is the fact that it is either absolutely
continuous or purely singular.
Recall that a number β > 1 is called a Pisot number if it is an algebraic integer
whose other Galois conjugates are less than 1 in modulus. Erdős [2] showed that if β
is a Pisot number, then µβ is singular. Garsia [7] introduced a new class of algebraic
integers – now referred to as Garsia numbers – and proved that µβ is absolutely
continuous if β is a Garsia number. Solomyak [24] proved that for Lebesgue-a.e.
β ∈ (1, 2) the Bernoulli convolution is absolutely continuous.
Definition 1. Given a Bernoulli convolution µβ , by the upper local dimension of µβ
at x ∈ suppµβ , we mean the number
dimloc µβ (x) = lim sup
r→0+

log µβ ([x − r, x + r]).
log r

Replacing the lim sup by lim inf gives the lower local dimension, denoted dimloc µβ (x).
If the limit exists, we call the number the local dimension of µβ at x and denote thisby dimloc µβ (x).
It is also known that µβ is exact-dimensional (which is a special case of a general
result in [15]). Namely, there is a number α such thatlog µβ (x − r, x + r)
=α
r→0
log r

dimloc (µ) = lim

for µβ -almost every x. We will call this number α the dimension of µβ and denoteby dim(µβ ). In particular, the exact-dimensionality implies dimH (µβ ) = dim(µβ ).
Clearly, if µβ is absolutely continuous, then dim(µβ ) = 1. Whether the converse istrue for this family, remains unknown.
Garsia [8] introduced the following useful quantity Hβ , called the Garsia entropy,
associated with a Bernoulli convolution. If β is transcendental or algebraic but notsatisfying an algebraic equation with coefficients {−1, 0, 1} (i.e., it is not of heightone), then Hβ = log 2/ log β > 1.
However, if β is Pisot, then it was shown in [8, 21] that Hβ = dim(µβ ) < 1. Furthermore, Garsia also proved that if Hβ < 1, then µβ is singular.

Bernoulli convolutions, Garsia entropy and local dimension

71

Alexander and Zagier in [1] managed to evaluate Hβ for the golden ratio β =τ with an astonishing accuracy. It turned out that Hτ is close to 1 – in fact Hτ ≈0.9957. Grabner, Kirschenhofer and Tichy [9] extended this method to the multinacci
numbers, which are the positive real roots of xm = xm−1 + xm−2 + · · · + x + 1. No othervalues of Hβ correct up to at least two decimal places are known to date.
The Garsia entropy and the dimension of a Bernoulli convolution are connected by
the following result:
Theorem 1 (Hochman, 2014 [15]). If β ∈ (1, 2) is algebraic, thendim(µβ ) = min{Hβ , 1}.
Essentially, this remarkable theorem says that the topological quantity, dim(µβ ), coincides with the combinatorial one, Hβ . If β is Pisot, then this is relatively straightforward (and known since [21]); for all other algebraic β this fact is highly non-trivial.
Using this, we prove that
Theorem 2. For all algebraic β ∈ (1, 2) we have dim(µβ ) > 0.82.
We also show that:
Proposition 1. If [Q(β 1/k ) : Q(β )] = k for some k ≥ 2, then Hβ 1/k = kHβ .
Although it is possible for [Q(β 1/k ) : Q(β )] 6= k, this does not happen often.
Corollary 0.1. Let k ≥ 2 and β ∈ (1, 2) a Pisot number. Assume further that β 1/k is
not a Pisot number. Then Hβ 1/k ≥ 1 and dim(µβ 1/k ) = 1.
Using a similar technique we also show
Corollary 0.2. Let k ≥ 2, β ∈ (1, 2) and deg(β ) = r. Assume further that deg(β 1/k ) >r. Then Hβ 1/k ≥ 1 and dim(µβ 1/k ) = 1.
Further, when β is a Pisot number, these Bernoullie convolutions are know to beof finite type, (first introduced by Ngai and Wang [NW]). This allows us to study inmore detail the possible local dimensions arising from a Bernoulli convolution.
Building on earlier work (c.f., [6, 16, 18, 22]), Feng undertook a study of equicontractive, self-similar measures of finite type in [3, 4, 5]. His main results were for
Bernoulli convolutions. In particular, he proved that despite the failure of the open set
condition, the multifractal formalism still holds for the Bernoulli convolutions whose
contraction factor was the reciprocal of a simple Pisot number (meaning, a Pisot number whose minimal polynomial is of the form xn − xn−1 − · · · − x − 1). A particularlyinteresting example is when the contraction factor is the golden ratio with minimal
polynomial x2 − x − 1 (also called the golden mean).
We first give a simple formula for the value of the local dimension of µ at any “periodic” point of its support. As a corollary we get that the local dimension exists at“periodic” points. The finite type condition leads naturally to a combinatorial notion
we call a “loop class”. For a “positive” loop class we prove that the set of attainable local dimensions of the measure is a closed interval and that the set of local dimensions

72

Kevin G. Hareat periodic points in the loop class is a dense subset of this interval. Similar results
are also given for upper and lower local dimensions. Given two values ` ≤ u within
this interval, we can find an x in this positive loop class with lower local dimension
equal to ` and upper local dimension equal to u.
A consequence of our result is that the set of attainable local dimensions is theunion of a closed interval together with the local dimensions at points in finitely many
loop classes external to the essential class. We will say that a point is an essential point
if it is in the essential class. The set of essential points has full Lebesgue measure on
the support of the measure and in many interesting examples the set of essential points
is the interior of the support of the measure.
When the essential set is the interior of the support of the measure µ, then µ has
no isolated point in its set of attainable local dimensions if and only if dimloc µ(0)coincides with the local dimension of µ at an essential point. In that case, the set of
attainable local dimensions of µ is a closed interval. The Bernoulli convolution µρ ,with ρ −1 a simple Pisot number has this property.
However, we construct other examples of Bernoulli convolutions (with contraction
factor a Pisot inverse) which do have an isolated point in their set of attainable local
dimensions. As far as we are aware, these are the first examples of Bernoulli convolutions known to admit an isolated point. We also construct a Cantor-like measure offinite type, whose set of local dimensions consists of (precisely) two distinct points.
In all of these examples, the essential set is the interior of the support of the measure.
The computer was used to help obtain some of these results. In principle, the techniques could be applied to other convolutions of Bernoulli convolutions, howevereven with the simple examples given here, the problem can become computationallydifficult.

References
1. J. C. Alexander and D. Zagier, (1991) The entropy of a certain infinitely convolved Bernoulli
measure. J. London Math. Soc. (2) 44:121–134.
2. P. Erdős, (1939) On a family of symmetric Bernoulli convolutions. Amer. J. Math. 61:974–976.
3. D-J. Feng, (2003) Smoothness of the Lq -spectrum of self-similar measures with overlaps, J.
London Math. Soc. 68:102-118.
4. D-J. Feng, (2005) The limited Rademacher functions and Bernoulli convolutions asociated with
Pisot numbers, Adv. in Math. 195:24-101.
5. D-J. Feng, (2009) Lyapunov exponents for products of matrices and multifractal analysis. Part
II: General matrices, Isr. J. Math. 170:355-394.
6. D-J. Feng and E. Olivier, (2003) Multifractal analysis of the weak Gibbs measures and phasetransition-application to some Bernoulli convolutions, Ergodic Theory Dynam. Systems.
23:1751-1784.
7. A. M. Garsia, (1962) Arithmetic properties of Bernoulli convolutions, Trans. Amer. Math. Soc.
102:409–432.
8. A. M. Garsia, (1963) Entropy and singularity of infinite convolutions. Pacific J. Math. 13:1159–
1169.
9. P. J. Grabner, P. Kirschenhofer and R. F. Tichy, (2002) Combinatorial and arithmetical propertiesof linear numeration systems. Combinatorica 22:245–267.

Bernoulli convolutions, Garsia entropy and local dimension

73

10. Kathryn E. Hare, Kevin G. Hare, and Kevin R. Matthews, Local dimensions of measures offinite type on the torus, arXiv:1607.03515.
11. Kathryn E. Hare, Kevin G. Hare, and Kevin R. Matthews, (to appear) Local dimensions ofmeasures of finite type, J. Fractal Geom., arXiv:1504.00510.
12. Kathryn E. Hare, Kevin G. Hare, and Michael Ka Shing Ng, Local dimensions of measures of finite type II - measures without full support and with non-regular probabilities,
arXiv:1603.02244.
13. Kevin G. Hare and Nikita Sidorov, (2010) A lower bound for Garsia’s entropy for certain
Bernoulli convolutions, LMS J. Comput. Math. 13:130–143.
14. Kevin G. Hare and Nikita Sidorov, (to appear) A lower bound for the dimension of bernoulli
convolutions, Exp. Math., arXiv:1606.02131.
15. M. Hochman, (2014) On self-similar sets with overlaps and inverse theorems for entropy, Ann.
of Math. (2) 180:773–822.
16. T-Y. Hu, (1997) The local dimensions of Bernoulli convolution associated with the golden number, Trans. Amer. Math. Soc. 349:2917-2940.
17. K. S. Lau and S. M. Ngai, (1999) Multifractal measures and a weak separation condition, Adv.
Math. 141:45-96.
18. K. S. Lau and S. M. Ngai, (1998) Lq -spectrum of the Bernoulli convolution associated with thegolden ratio, Studia Math. 131:225-251.
19. S. M. Ngai and Y. Wang, (2001) Hausdorff dimension of self-similar sets with overlaps, J.
London Math. Soc. 63:655-672.
20. W. Parry, (1960) On the β -expansions of real numbers, Acta Math. Acad. Sci. Hungar. 11:401–
416.
21. F. Przytycki and M. Urbański, (1989) On the Hausdorff dimension of some fractal sets, Studia
Math. 93:155–186.
22. A. Porzio, (1998) On the regularity of the multifractal spectrum of Bernoulli convolutions, J.
Stats. Phys. 91:17-29.
23. A. Rényi, (1957) Representations for real numbers and their ergodic properties, Acta Math.
Acad. Sci. Hungar. 8:477–493.
24. B. Solomyak, (1995) On the random series ±λ n (an Erdős problem), Ann. of Math. (2) 142,
no. 3:611–625.
25. P. Varjú, Recent progress on Bernoulli convolutions, arXiv:1608.04210.

Bases with two expansions
Vilmos Komornik and Derong Kong

Abstract In this paper we answer several questions raised by Sidorov on the set B2of bases in which there exist numbers with exactly two expansions. In particular, we
prove that the set B2 is closed, and it contains both infinitely many isolated and accumulation points in (1, qKL ), where qKL ≈ 1.78723 is the Komornik-Loreti constant.
Consequently we show that the second smallest element of B2 is the smallest accumulation point of B2 . We also investigate the higher order derived sets of B2 . Finally,
we prove that there exists a δ > 0 such that
dimH (B2 ∩ (qKL , qKL + δ )) < 1,
where dimH denotes the Hausdorff dimension. For more details see arXiv:1705.00473.

Vilmos Komornik
Département de mathématique, Université de Strasbourg, 7 rue René Descartes, 67084 Strasbourg
Cedex, France, e-mail: komornik@math.unistra.fr
Derong Kong
Mathematical Institute, University of Leiden, PO Box 9512, 2300 RA Leiden, The Netherlands,e-mail: d.kong@math.leidenuniv.nl

75

A shrinking hole for β -transformations
Niels Langeveld

Abstract For β ∈ (1, 2] let Tβ be the expanding map on the interval [0, 1) defined byTβ (x) = β x (mod 1). In this talk we consider the set Eβ of all t ∈ [0, 1) for which thenoforward orbit Tβn (t) : n ≥ 0 avoids the hole [0,t). The set Eβ is a Lebesgue null set
of full Hausdorff dimension for all β ∈ (1, 2). Different from β = 2, we prove that forLebesgue almost every β ∈ (1, 2) the set Eβ contains both infinitely many isolated andaccumulation points. Furthermore, we characterise the set of β such that Eβ ∩ [0, δ )has isolated points for all δ > 0, the set of β for which there exists a δ > 0 such thatEβ ∩ [0, δ ) has no isolated points and the set of β for which Eβ has no isolated points.
In the last case we show that Eβ is a Cantor set satisfying
lim dimH Eβ ∩ (t − δ ,t + δ ) = dimH Kβ (t) for all t ∈ Eβ ,

δ →0

(1)

o
n
where Kβ (t) is the survivor set defined by Kβ (t) = x ∈ [0, 1) : Tβn (x) ≥ t for any n ≥ 0 .
This is joint work with Charlene Kalle, Derong Kong and Wenxia Li.

1 The main theorems
Let us also define the function ηβ : [0, 1) → [0, 1] byηβ (t) := dimH Kβ (t).

(2)

Then by the results from [4] the function ηβ is a continuous, monotone function
with ηβ (0) = 1 and ηβ (1) = 0 and such that ηβ0 (t) = 0 for Lebesgue almost everyt ∈ [0, 1). Denote by Bβ the bifurcation set of ηβ , i.e., the set of t ∈ [0, 1) where
the function ηβ is not locally constant. Since ηβ is continuous, Bβ has no isolated
University of Leiden, P.O. Box 9512, 2300 RA Leiden, The Netherlands

77

78

Niels Langeveld

points. For the doubling map Nilsson proved in [2] that the bifurcation set B2 ofthis dimension function is a Cantor set of full Hausdorff dimension. In [1] Carminati
and Tiozzo proved for the maps x 7→ kx (mod 1) (k ∈ N≥2 ) that at every bifurcation
parameter t of the function t 7→ dimH K(t) the local Hölder exponent equals the valueof the function itself. Both [2] and [1] used the fact that B2 equals the set E2 :={t ∈ [0, 1) : T2n (t) ≥ t for any n ≥ 0}, proved in [2]. Urbański proved in [4] that forany t ∈ E2 ,lim dimH E2 ∩ (t − δ ,t + δ ) = dimH K(t).
(3)
δ →0

Similar to β = 2 we define the set Eβ for β ∈ (1, 2) asnoEβ := t ∈ [0, 1) : Tβn (t) ≥ t for any n ≥ 0 .

(4)

One might expect that the behaviour of Eβ is similar to that of E2 = B2 . Some of ourresults indicate similarities between the sets E2 and Eβ . Namely, we have
Theorem 1. For any β ∈ (1, 2) the set Eβ is a Lebesgue null set of full Hausdorff
dimension.
This result is unexpected, since the symbolic dynamical system associated to the β transformation becomes more and more restricted as β → 1. Apparently this has no
significant influence on the size of Eβ . For other properties we identify a set of β ∈(1, 2) which have more similarities as β = 2. To be able to do so we define cyclicallybalanced words and Sturmian words.
For any word u ∈ {0, 1}∗ , use |u|1 to denote the number of ones. A word w is calledbalanced if for every two factors u, v of w of the same length we have |u|1 − |v|1 ≤ 1
and cyclically balanced if w2 is balanced. Let w ∈ {0, 1}∞ be a sequence. If it is nonperiodic and |u|1 − |v|1 ≤ 1 for any two factors u and v of w, then the sequenceis called Sturmian. Let α : (1, 2) → {0, 1}N denote the function assigning to β thecorresponding quasi-greedy β -expansion of 1, i.e.,α(β ) = α1 (β )α2 (β ) · · · ,where 1 = ∑n≥1 αnβ(βn ) and α(β ) does not end in an infinite string of zeros. We define
the setR := {β ∈ (1, 2) : α(β ) is cyclically balanced or Sturmian} .
As the following theorem will show this will be the set that has similarities with β = 2.
Theorem 2. For β ∈ R the following statements hold.
(i) E β is a Cantor set. Furthermore, for any t ∈ Eβ we have
lim dimH Eβ ∩ (t − δ ,t + δ ) = ηβ (t).

δ →0(ii) The survivor set Kβ (t) has the following properties.

(5)

A shrinking hole for β -transformations

79

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

Fig. 1: Left: the graph of ηβ with β the golden mean. Right: the graph of ηβ with β
the tribonacci constant.

• If t ∈ Eβ , then dimH Kβ (t) ∩ [t,t + δ ) = ηβ (t) for all δ > 0.
• If t ∈/ Eβ , then Kβ (t) ∩ [t,t + δ ) = 0/ for some δ > 0.
On the other hand, many of our results show that there are fundamental differences
between E2 and Eβ as well. For β ∈ (1, 2) the set Eβ has no isolated points if and only
if β ∈ R. Moreover, the Hausdorff dimension of R is zero. In other words, in mostcases Eβ 6= Bβ since ηβ is continuous.

80

Niels Langeveld

Let us now define
C3 = {β ∈ (1, 2) : the orbit of 1 under the map Tβ avoids [0, δ ) for some δ > 0}.
(6)
We have the following theorem
Theorem 3. Let β ∈ (1, 2). The set Eβ ∩ [0, δ ) has isolated points for all δ > 0 if andonly if β 6∈ C3 .
Note that R ⊂ C3 . In [3] it is shown that C3 is a Lebesgue null set with dimH (C3 ) = 1.
What we find is that for almost all β ∈ (1, 2) any neighbourhood of zero contains bothisolated points and non-isolated points.

References
1. C. Carminati and G. Tiozzo. The local Ho?lder exponent for the dimension of invariant subsetsof the circle. arXiv:1410:5761.
2. J. Nilsson. On numbers badly approximable by dyadic rationals. Israel J. Math., 171:93110,
2009.
3. J. Schmeling. Symbolic dynamics for ?-shifts and self-normal numbers. Ergodic Theory Dynam.
Systems, 17(3):675694, 1997.
4. M. Urban?ski. On Hausdorff dimension of invariant sets for expanding maps of a circle. Ergodic
Theory Dynam. Systems, 6(2):295309, 1986.

Expansions in non-integer bases in control
problems
Paola Loreti

In this talk we discuss some classes of expansions in non integer-bases describing
how bases can represent physical properties of the system and the alphabet can beassociated to a control acting on the system. Then we discuss a result obtained incollaboration with C. Baiocchi and V. Komornik (work in progress).

Paola Loreti
Sapienza Università di Roma, e-mail: paola.loreti@sbai.uniroma1.it

81Periodic representations in algebraic non-integer
baseTomáš Vávra

Abstract We consider (β , A )-representations of the form ∑ki=−∞ ai β i with algebraic
base β , |β | > 1, and a finite alphabet A ⊂ Q(β ).
We study the following problem: “For which bases β does there exist an alphabet
A such that each element of Q(β ) has eventually periodic (β , A )-representation?”
We show that this question can be answered in the affirmative if β has no Galois
conjugates on the unit circle. This is an extension of the result of of Baker, Masáková,Pelantová, and Vávra.
It remains to solve the problem for the bases that have a conjugate on the unit
circle. Such a class of numbers contains for example the Salem numbers for which isthe positive answer to our question conjectured by K. Schmidt. We will discuss thepossible application of our method to these cases.
This is a joint work with V. Kala.

Tomáš Vávra
Department of Algebra, Charles University, Sokolovská 83, 175 86 Praha 8, Czech Republic, e-mail:avrato@gmail.com

83Self-similar manipulators, Fibonacci sequenceand number systems
Anna Chiara Lai

Abstract We introduce a model for planar manipulators characterised by a selfsimilar morphology. We show that related control problems can be set in the framework of non-standard number systems and theory of Iterated Function Systems. We
then focus on models for snake-like manipulators based on Fibonacci sequences:reachability and local controllability are investigated. This presentation is based on
joint works with Paola Loreti and Pierluigi Vellucci.

1 Introduction
A manipulator is a robotic device composed by several rigid, possibly extensible,
links joint by rotating junctions. Robot fingers, snake-like manipulators and robot
octopus-inspired tentacles are examples of manipulators. The motion of planar manipulators is constrained on the plane, while redundant manipulators are characterisedby a number of links which is gretar than the degrees of freedom of the device. We
study a model for planar manipulators with an arbitrarily large number of links, theso-called hyper-redundant planar manipulators. This class of robotic arms is knowning an increasing interests among researchers due to their good performances inconstrained enviroments [1]. The peculiarity of the model presented here is a selfsimilarity assumption on the links, that gives access to classical methods of the theory of Iterated Function Systems for the investigation of the reachable workspace. We
then focus on the particular case of links scaling according to Fibonacci sequence.
In order to build our model, we assume links and junctions composing the manipulator to be thin, so to be respectively approximated by their middle axes andbarycentres. We also assume axes and barycentres to be coplanar and, by employing
Anna Chiara Lai
Dipartimento di Scienze di Base e Applicate per l’Ingegneria, Sapienza Università di Roma, Via
Scarpa, 16, 00181 Roma, e-mail: anna.lai@sbai.uniroma1.it

85

86

Anna Chiara Lai

the isometry between R2 and C, we use the symbols x0 , x1 , ..., xn ∈ C to denote theposition of the barycentres of the junctions. We define lk as the maximal length of thek-th link. A binary control uk ∈ {0, 1} rules the extension of the k-link in particular
we set |xk − xk−1 | = uk lk , so that if uk = 1 then the k-th link has length lk and if uk = 0
then the k-th link is unextended and the k-th and the k −1-th joints coincide. Moreovera binary control vk rules the rotation of the k-th link: if vk = 0 then the k − 1-th link
and the k-th link are collinear, if vk = 1 they form an angle π − ω, ω ∈ (0, π) is fixed.
In view of these assumptions, the position of k-th junction xk depends on the k − 1-thjunctions according to the discrete controlled dynamical system:kxk = xk−1 + uk lk e−iω ∑ j=1 v j .

(1)

A closed formula for xk is given bynnxk = ∑ uk lk e−iω ∑ j=1 v j .

(2)

k=0

We say that a sequence (lk ) in R is Linear-Contractive-Recursive (LCR) if there
exists an integer n ∈ N and a linear map F : Rn → R satisfying lk = F(lk−1 , . . . , lk−n )for every k > n and there exists L < 1 such that |F(x) − F(y)| < L||x − y||∞ , where||(x1 , . . . , xn )||∞ := max{|xk |, k = 1, . . . , n} denotes the L∞ -norm of x ∈ Rn . We areinterested in the asymptotic reachable workspace(
W := { lim xn (u, v) | u, v ∈ {0, 1} }
∞

n→∞

=

∞

∑ uk lk e−iω ∑nj=1 v j)∞| u, v ∈ {0, 1}.

k=0

Also we investigate a subset of W corresponding to the so called full-extension configurations, characterised by extension controls constantly equal to 1:(
E := { lim xn (1, v) | v ∈ {0, 1}∞ } =
n→∞

∞

n

)

∑ lk e−iω ∑ j=1 v j | u, v ∈ {0, 1}∞ .
k=0

Example 1. The geometric sequence lk = q−k for some q > 1 is LCR. Indeed lk =lk−1 q−1 for every k ∈ N. In this case the asymptotic reachable workspace W isa self-similar set [3]. Moreover note that the full-rotation configurations x(u, 1) =e−iωk−iω with digits (u ).
∑∞kk=0 uk ρ k are expansions in the complex base q := ρeExample 2. The scaled Fibonacci sequence lk = fk q−k is LCR, where fk is the k-th
Fibonacci number, q > ϕ and ϕ is the Golden Mean. We discuss this case in Section
3 below.

2 Self-similar manipulators
In [4], the properties of LCR sequences are applied to the study of a simplified version of (1) corresponding to case un ≡ 1, i.e., to the full-extension configurations. In

Self-similar manipulators, Fibonacci sequence and number systems

87

particular, a relation with fractal geometry is established: the reachable set is showed
to be a suitable projection of a self-similar set. The core idea is to build an Iterated
Function System (IFS) naturally associated to (lk ). To this end, recall that the dual of
Rn is isomorphic to Rn itself, namely every linear map F : Rn → R can be identified
with an element a ∈ Rn . In other words, there exists a = (a1 , . . . , an ) ∈ Rn such thatfor every k > n
lk = ha, (lk−1 , . . . , lk−n )i.
Now, we define the n × n matrix
a . . . an−1 an
A := 1,In−10n−1
where In−1 denotes the (n − 1)-dimensional identity matrix. By construction, for every k > nA(lk−1 , lk−2 , . . . , lk−n )T = (lk , lk−1 , . . . , lk−n+1 )T ,(3)
that is A acts on (lk ) as a shift operator with window of length n. We say that a map
F is eventually contractive if some of its iterations F k , with k sufficiently large, isa contractive map. We call a finite set of eventually contractive maps an eventuallycontractive IFS. We now consider the affine eventually contractive IFS (Fu )u∈{0,1}defined on Cn
Fu (x) := e−iωu (Ax + B)u ∈ {0, 1},(4)where B = (ln , ln−1 , . . . , l1 )T . Note that by (3)Ak B = (lk+n , . . . , lk+1 )T∀k > 0.

(5)Moreover by Hölder inequality the spectral radius of A is lower than 1 and it can beproved that this a sufficient condition to have an unique compact attractor for the IFS(Fu )u∈{0,1} .
Theorem 1 ([4]). Let F (S) := ∪u∈{0,1} Fu (S) be the Hutchinson operator associatedto (Fu )u∈{0,1} and denote by π1 the projection of a vector of Cn on its first component. Let Q∞ be the (unique) invariant set of (Fu )u∈U . Then asymptotic reachable
workspace corresponding to full extension configurations E satisfies
(
)
E =

∞

k

∑ lk e−iω ∑n=0 vn | vn ∈ {0, 1}= π1 (Q∞ )k=0

and for every bounded set S ⊂ Cn we have E = π1 (limk→∞ F k (S)).

3 Fibonacci manipulators
We assume now that the length of the links is governed by the recursive relation

88

Anna Chiara Lai

11
lk+1 = lk + 2 lk−1qqwith l0 = 1 and l1 = q1 for some q > ϕ – recall that ϕ denotes the Golden Mean.
The assumption q > ϕ ensures the convergence of the series ∑∞k=0 lk , representing the
maximal total length of the manipulator: a closed formula for (lk ) is given by
lk =

fk
.
qk

where ( fk ) is Fibonacci sequence, namely f0 = f1 := 1 and fk+2 = fk+1 + fk for all
k ≥ 0 and one has that the radius of convergence of the power series ∑k=0 fk yk is ϕ1 .
The following local controllability holds1
Theorem 2 ([6]). Let p ∈ N and q(p) be the greatest real solution of the equation∞

f pk∑ q pk = 2.

k=0

If ω = 2π dp for some coprime integers d, p ∈ N and if q ∈ (ϕ, q(p)], then the asymptotic reachable workspace()∞
fk −iω ∑k vn∞
n=0
W = ∑ uk k e| u, v ∈ {0, 1}q
k=0contains a neighborhood of the origin.
We present also a result on the quantity∞lk
L(u) = ∑ uk kq
k=0

representing the total length of manipulator corresponding to the extension control
sequence u ∈ {0, 1}∞ . We consider the set
(
)
∞
f
k
L := {L(u) | u ∈ {0, 1}∞ } = ∑ uk k | u ∈ {0, 1}∞ .
q
k=0
In order to give a complete characterisation of L we introduce the quantities:

1 We recall that a manipulator is locally controllable if its reachable workspace contains a neighbor-hood of the origin

Self-similar manipulators, Fibonacci sequence and number systems

89

∞

f j+k
k
k=0 q

S(q, j) := ∑Q(−1) := ϕ;Q( j) := greatest solution of the equation S(q, j + 1) = q f j
q1
2 + 8 f 2 ).
=( f j+2 + f j+2j2fj√
Note that Q(0) = 1 + 3.
Theorem 3 ([6, 2]). For all j ≥ 0 if q ∈ (Q( j − 1), Q( j)], then L is composed by the
disjoint union of 2 j intervals:
"
#
j−1
j−1
[
fk
fk
L =
(6)
∑ qk uk , ∑ qk uk + S(q, j) .
k=0
u ,...,u ∈{0,1} k=0
0

j−1

√
fk
In particular, if q ∈ (ϕ, 1 + 3], then L is the interval [0, ∑∞k=0 qk ].
p
fk
Moreover if q ≥ 21 (ϕ 2 + ϕ 2 + 1) then the map u 7→ xu = ∑∞k=0 qk uk is increasing
with respect to the lexicographic order and L is a totally disconnected set.

References[1] G. S. Chirikjian, and J. W. Burdick. An obstacle avoidance algorithm for hyper-redundant
manipulators. IEEE International Conference on Robotics and Automation, 1: 625–631, 1990.
[2] A. C. Lai. A note on the reachability of a Fibonacci control system. Proceedings of Workshop
on Functional Analysis and its Applications in Mathematical and Optimal Control, September
8 - 12, 2015, Nemecka Slovak Republic. ISBN 978-90-227-4030-2[3] A. C. Lai and P. Loreti. Robot’s finger and expansions in non-integer bases. Networks andHeterogeneus Media, 7 (1) 71–111, 2011.
[4] A. C. Lai and P. Loreti. Self-similar control systems and applications to zygodactyl birds foot.
Networks and Heterogeneus Media, 10 (2) 401 – 419, 2015.
[5] A. C. Lai, P. Loreti and P. Vellucci. A model for Robotic Hand based on Fibonacci sequence.
Proceedings of the 11-th International Conference on Informatics in Control, Automation andRobotics, 577–587, 2014.
[6] A. C. Lai, P. Loreti and P. Vellucci.

Digit frequencies and self-affine sets with
non-empty interior
Simon Baker

Abstract In this talk I will discuss recent results on digit frequencies in the setting of
expansions in non-integer bases, and self-affine sets with non-empty interior. Within
expansions in non-integer bases I will give details of a recent result which states
1) has a simply normal β -expansion.
that if β ∈ (1, 1.787 . . .) then every x ∈ (0, β −1
√

1
) has
Employing similar ideas I will show that if β ∈ (1, 1+2 5 ) then every x ∈ (0, β −1
a β -expansion for which the digit frequency does not exist, and a β -expansion withlimiting frequency of zeros p, where p is any real number sufficiently close to 1/2.
For a class of planar self-affine sets I will show that if the horizontal contraction lies
in a certain parameter space and the vertical contractions are sufficiently close to 1,
then every nontrivial vertical fibre contains an interval. This approach lends itself to
explicit calculation and give rise to new examples of self-affine sets with non-empty
interior. One particular strength of this approach is that it allows for different rates ofcontraction in the vertical direction.

Simon Baker
Mathematics institute, University of Warwick, Coventry, CV4 7AL, UK e-mail: simonbaker412@gmail.com

91

92

Simon Baker

Fig. 1: An example of a self-affine set where it can be shown that each vertical fibre
contains an interval.

Essentially nonnormal numbers for random
Cantor series expansions
Bill Mance and Roman Nikiforov

The set of essentially nonnormal numbers in base b, Lb , consists of those numbers
where no digital frequencies exists in their b-ary expansion. It was proven by S. Albeverio, M. Pratsiovytyi, and G. Torbin in [2] that Lb has full Hausdorff dimension.
We extend this result to a large class of Cantor series expansions and considering
numbers not only whose digital frequencies do not exist but whose block frequencies
also do not exist.
A basic sequence is a sequence of integers greater than or equal to 2. Given abasic sequence Q = (qn )∞n=1 , the Q-Cantor series expansion of a real number x is the(unique) expansion of the form
∞

En
q
q
n=1 1 2 · · · qn

x = E0 + ∑(1)where E0 = bxc and En is in {0, 1, · · · , qn − 1} for n ≥ 1 with En 6= qn − 1 infinitely often. For a basic sequence Q = (qn ), a block B = (b1 , b2 , · · · , b` ), and a natural numberj, define
1 if b1 < q j , b2 < q j+1 , · · · , b` < q j+`−1.
IQ, j (B) =0 otherwise
and let

IQ, j (B).
j=1 q j q j+1 · · · q j+`−1n

Qn (B) = ∑A real number x is Q-normal if for all blocks B such that limn→∞ Qn (B) = ∞Bill Mance
Institute of Mathematics of Polish Academy of Science, Śniadeckich 8, 00-656 Warsaw, Poland email: Bill.A.Mance@gmail.com
Roman Nikiforov
National Pedagogical Dragomanov University, Pyrogova str. 9, 01030 Kyiv, Ukraine e-mail: rnikiforov@gmail.com

93

94

Bill Mance and Roman Nikiforov

NnQ (B, x)= 1.
n→∞ Qn (B)limwhere NnQ (B, x) is the number of occurences of the block B in the sequence (Ei )ni=1
of the first n digits in the Q-Cantor series expansion of x. Motivated by this definitionQ

we say that x is Q-essentially nonnormal if the limit limn→∞ NQn n(B,x)(B) does not exist for∗
all B such that limn→∞ Qn (B) = ∞ and call this set LQ . Clearly, when qn = b for all∗ . We improve the result in [2] by not only showing that L∗ hasn, we have Lb ( LQ
Q
full Hausdorff dimension in this special case, but that its Hausdorff dimension is 1
for other classes of basic sequences. Furthermore, we will show that the Hausdorff∗ will be 1 almost surely when the bases q are i.i.d. random variables
dimension of LQ
nwhere the expecation of E[log q1 ] < ∞. Furthermore, our result will even hold if weAP of real numbers where a similar limit doesn’t exist for numbers
consider the set LQ
whose Cantor series digits are sampled along all nontrivial arithmetic progressions.
Our construction surprisingly will use a recent result of Joseph Vandehey on numbers normal with respect to the regular continued fraction expansion. In [1], he provedthat if x = [a0 ; a1 , a2 , · · · ] is the continued fraction of x and if x is continued fraction
normal, then for every pair of integers m, r with m ≥ 2 and r ≥ 0, the real number[0; ar , am+r , a2m+r , · · · ] is not normal with respect to the regular continued fraction
AP .
expansion. We will use this property to construct members of LQ

References
1. Joseph Vandehey. Continued fraction normality is not preserved along arithmetic progressions.
Arch. Math. (Basel) 106 (2016), no. 4, 363370.
2. Albeverio, Sergio; Pratsiovytyi, Mykola; Torbin, Grygoriy. Topological and fractal properties ofreal numbers which are not normal. Bull. Sci. Math. 129 (2005), no. 8, 615630.

Computing with generalized number systems
using the computer algebra system SYGNM
Tamás Krutki, Bence Németh and Attila Kovács

Abstract As computational methods become increasingly important in scientific research and education there is a high demand for all kinds of mathematical software.
Computer algebra systems aim to provide both symbolic and numerical capabilities
covering a wide range of mathematical topics. The development of some of the mostwidely used computer algebra systems has began over 30 years ago, which meansthat these systems are outdated in some aspects and do not fully take advantage of
new technologies and software engineering methods that appeared since then. A new,general purpose computer algebra system architecture and its implementation is presented which aims to fix several problems of current systems. Part of this new system
is a built-in package for computations with generalized number systems, containing functionality which is not found in other computer algebra systems. The number
systems package is efficient and well integrated into the general purpose computer
algebra environment, however it is also available as a separate C++ library. The current capabilities of the number systems package and plans for future number system
related developments are presented. Both the new computer algebra system and thegeneralized number systems library will be released as open source software.

Tamás KrutkiEötvös Loránd University, Budapest, e-mail: krtamas@inf.elte.hu
Bence Németh
Google, CA 94043, US, e-mail: nemben@gmail.com
Attila Kovács
Eötvös Loránd University, Budapest, e-mail: attila.kovacs@inf.elte.hu

95

Examining the number system property withprobabilistic algorithms
Péter Hudoba and Attila Kovács

Abstract The world of generalized number systems contains many challenging areas. In some cases the complexity of the arising problems is unknown. Researchingthese problems are important since they can be applied e.g. in cryptography. In thistalk we focus on experimenting with probabilistic methods by which we can support
the analysis of the “decision problem”. To be more precise we present two Las Vegas
type probabilistic algorithms and measurements regarding the attraction domain distributions. We implemented our solutions in the computer algebra system Sage (someparts in C++).

1 Extended abstract
Let Λ be a lattice in Rn and let M : Λ → Λ be a linear operator such that det(M) 6= 0.
Let furthermore 0 ∈ D ⊆ Λ be a finite subset. Lattices can be seen as finitely generated
free Abelian groups.
Lattices have many significant applications in pure mathematics (Lie algebras,
number theory and group theory), in applied mathematics (coding theory, cryptography) because of conjectured computational hardness of several lattice problems,and are used in various ways in the physical sciences.
In this talk we consider number expansions in lattices.
Definition 1. The triple (Λ , M, D) is called a number system (GNS) if every element
x of Λ has a unique, finite representation of the formPéter Hudoba
Eötvös Loránd University, Budapest Hungary, e-mail: peter.hudoba@inf.elte.hu
Attila Kovács
Eötvös Loránd University, Budapest Hungary e-mail: attila.kovacs@inf.elte.hu

97

98

Péter Hudoba and Attila KovácsLx = ∑ M i di ,i=0where di ∈ D and L ∈ N. L is the length of the expansion.
Here M is called the base and D is the digit set. It is easy to see that similarity
preserves the number system property, i.e., if M1 and M2 are similar via the matrix Q
then (Λ , M1 , D) is a number system if and only if (QΛ , M2 , QD) is a number systemat the same time. If we change the basis in Λ a similar integer matrix can be obtained,
hence, no loss of generality in assuming that M is integral acting on the lattice Z n .
If two elements of Λ are in the same coset of the factor group Λ /MΛ then they
are said to be congruent modulo M. The following theorem is well-known.
Theorem 1. If (Λ , M, D) is a number system then
1. D must be a full residue system modulo M,
2. M must be expansive,
3. det(In − M) 6= ±1. (unit condition)
If a system fulfills the first two conditions then it is called a radix system.
ϕ

Let ϕ : Λ → Λ , x 7→ M −1 (x − d) for the unique d ∈ D satisfying x ≡ d (mod M).
Since M −1 is contractive and D is finite, there exists a norm k.k on Λ and a constant C
such that the orbit of every x ∈ Λ eventually enters the finite set S = {x ∈ Λ | kxk < C}
for the repeated application of ϕ. This means that the sequence x, ϕ(x), ϕ 2 (x), . . . iseventually periodic for all x ∈ Λ . Clearly, (Λ , M, D) is a number system iff for everyx ∈ Λ the orbit of x eventually reaches 0.
A point p is called periodic if ϕ k (p) = p for some k > 0. The orbit of a periodic
point p is a cycle. The set of all periodic points is denoted by P.
The following problem classes are in the mainstream of the research: for a given(Λ , M, D)• the decision problem asks if the triple form a number system or not.
• the classification problem means finding all cycles (witnesses).
• the parametrization problem means finding parametrized families of number systems.
• the construction problem aims at constructing a digit set D to M for which(Λ , M, D) is a number system.
The algorithmic complexity of the decision and classification problems is still unknown. In this talk we propose two new probabilistic methods improving the running
time of determining the number system property.
• We analysed the Garsia operators (the companions of all expansive polynomials
with constant term ±2) and monitored the orbits of randomly chosen points. In
case of non-number systems in order to find a witness it was enough to calculate
the orbit of a very few number of randomly chosen points from S.

Examining the number system property with probabilistic algorithms

99• According to the conjecture of the second author ([2]) we obtained that in a nonnumber system case there were always at least one point around zero (having coordinates from {0, ±1}) that converged to a non-zero periodic point. If we combine
this observation with the previous algorithm we can find witnesses really fast withhigh probability.

References
1. Kovács, A., On computation of attractors for invertible expanding linear operators in Z k , Publ.
Math. Debrecen, 56/1–2, (2000), 97–120.
2. Kovács, A., Generalized binary number systems, Annales Univ. Sci. Budapest, Sect. Comp., 20,(2001), 195–206.
3. Burcsi, P., Kovács, A., Papp-Varga, Zs., Decision and Classification Algorithms for Generalized
Number Systems, Annales Univ. Sci. Budapest, Sect. Comp., 28, (2008), 141–156.

Normal Subsequences of Automatic Sequences
Clemens Müllner

In 2013 Drmota, Mauduit and Rivat observed that the subsequence along the squares(t(n2 ))n≥0 of the Thue-Morse sequence (t(n))n≥0 (that can be defined by t(n) =s2 (n) mod 2, where s2 (n) denotes the binary sum-of-digits function) is a normal sequence on the alphabet {0, 1}.
The purpose of this talk is to discuss this result also from a more general pointof view. The Thue-Morse sequence is a special case of an k-automatic sequence(a(n))n≥0 , that is, a sequence where the n-th element is the output of a deterministic finite state automaton, where the input is the base k expansion of n. Automatic sequence
have a sub-linear subword complexity - so they are far from being normal. Furthermore, linear subsequences of automatic sequences are again automatic sequence and,
therefore, have again sub-linear subword complexity. However, when we consider asubsequence a(φ (n)), where φ (n)/n → ∞ the situation can change completely - as(t(n2 ))n≥0 shows. Thus, we discuss the question for which subsequences - and forwhich automatic sequences - we may expect a normal sequence.
Recent results in this direction, e.g., by Lukas Spiegelhofer and the author (whoconsidered φ (n) = bnc c for the Thue-Morse sequence, where 1 < c < 3/2) and by
the author (who considered block-additive functions like the Rudin-Shapiro sequenceand φ (n) = n2 ) indicate that there might be a more general principle behind.

Clemens Müllner
TU Wien, Karlsplatz 13, 1040 Wien, Austria, e-mail: clemens.muellner@tuwien.ac.at101Totally Real Algebraic Numbers, Bogomolov
Property, and Dynamical Zeta Function of theβ -shift
Jean-Louis Verger-Gaugry√
Abstract Schinzel (1973) obtained the lower bound 12 log(1 + 5/2) = 0.24 . . . for
the Weil’s height h(α) of any totally real algebraic integer α 6= 0, 6= ±1, optimally.
This problem of minoration of the height is related to the problem of Lehmero for
Salem numbers with Mahler’s measure M(α). Bombieri and Zannier (2001) introduced the property of Bogomolov for any field F ⊂ Q, by analogy with Bogomolov’s
Conjecture: by definition F has the property of Bogomolov relative to h if and only ifh(α) = 0 or admits a lower bound > 0 for any α ∈ F. Amoroso and Zannier (2000)
proved it for K ab , where K is a number field. Bombieri and Zannier (2001) for totally p-adic fields, Habegger (2011) for Q(Etors ), where E/Q is an elliptic curve. Filiand Miner (2016), using limit equidistribution theorems of Favre and Rivera-Letelier,proved lim inf h(α) ≥ 0.12 . . . for α in the field of totally real algebraic numbers Qtr ;Pottmeyer (2016) obtained the limit infimum lim inf h(α) ≥ 4π7 2 ζ (3) by other techniques. In this work we show that the dynamical zeta function of the β -shift relative
to the arithmetical Rényi-Parry dynamical system, with β = α , α ∈ Qtr , allows toprove that the property of Bogomolov for Qtr is true, with a global explicit minoration.

Jean-Louis Verger-Gaugry
Univ. Savoie Mont Blanc, CNRS, LAMA, F- 73000 Chambéry, France e-mail: jean-louis.vergergaugry@univ-smb.fr

103

On the Hausdorff dimension faithfulness of
expansions with infinite alphabet and properties
of non-normal numbers
Roman Nikiforov

The notion of the Hausdorff dimension is well known, but in many cases it is a rather
non-trivial problem to give the exact dimension. One approach to the simplification of
the calculation of the Hausdorff dimension consists in some restrictions of admissible
coverings.
A fine covering family Φ is said to be a faithful family of coverings for the Hausdorff dimension calculation on [0, 1] if dimH (E, Φ) = dimH (E), ∀E ⊆ [0, 1].
The first phenomenon we will talk about is connected with the problem of faithfulness of the family of cylinders generated by the expansions with infinite alphabet(continued fractions, Lüroth expansion, Sylvester expansion and other).
We will also discuss properties of sets of essentially non-normal numbers definedin different systems of numeration.

Roman Nikiforov
Dragomanov National Pedagogical University, Pyrogova St. 9, 01601, Kyiv, Ukraine, e-mail: rnikiforov@gmail.com

105On Weyl’s theorem on Uniform Distribution and
Ergodic Theorems
Radhakrishnan Nair and Entesar Nasr

We say sequence a {x1 , . . . , xN } is uniformly distributed modulo one if
lim

1

N→∞ N

#{1 ≤ n ≤ N : xn ∈ I} = |I|for every interval I ⊆ [0, 1).
We also say a sequence of natural numbers (kn )n≥1 is Hartman uniform distributed(on Z) if it is uniformly distributed in residue classes modulo m, for each natural number m > 1, and for each irrational number α, the sequence ({kn α})n≥1 is uniformly
distributed modulo one. Here and henceforth, for a real number y we use {y} to denote its fractional part. Note that if (kn )n≥0 is Hartman uniformly distributed, and if
we set1 N−1 kn
F(N, z) :=(N = 1, 2, · · · )
∑z ,
N n=0
we have F(N, 1) = 1 for all N ≥ 1 and if z 6= 1 we have limN→∞ F(N, z) = 0. A list of
examples is given in the next section .
Let (X, B, µ) be a probability space and let T : X → X be a measurable map, thatis also measure-preserving. That is, given A ∈ B, we have µ(T −1 A) = µ(A), where
T −1 A denotes the set {x ∈ X : T x ∈ A}. We call (X, B, µ, T ) a dynamical system. We

Radhakrishnan Nair
Mathematical Sciences
University of Liverpool
Liverpool L69 7ZL
U.K. e-mail: nair@liv.ac.uk
Entesar Nasr
Mathematical Sciences
University of Liverpool
Liverpool L69 7ZL
U.K.e-mail: hsenasr@liv.ac.uk

107

108

Radhakrishnan Nair and Entesar Nasr

say the dynamical system is ergodic if T −1 A = A for A ∈ B means that either µ(A)or µ(X\A) is 0.
We say (kn )n≥0 is L p good universal if for each dynamical system (X, B, µ, T ) andfor each f ∈ L p (X, β , µ) the limit
1 N−1∑ f (T kn x),
N→∞ N
n=0
lim

exists µ almost everywhere.
Let ψ(x) = α0 + α1 x + α2 x2 + . . . + αk xk , with αk irrational. In the sequel call(k j ) j≥1 good if it is Hartman uniform distributed on Z and L∞ -good universal.
Theorem 1. The sequence (ψ(k j )) j≥1 is uniform distribution modulo one if (k j ) j≥1
is good.
This theorem has a number of implications.
We say a set of natural numbers S has positive Banach density B(S) if there exists a
sequence of intervals (Ik )∞k=1 in N with Ik = [ak , bk ] ∩ N and bk − ak tending to infinity
as k tends to infinity such that|S ∩ Ik |= B(S)
k→∞ |Ik |lim

0
and for any other sequence of intervals (Ik0 )∞k=1 in N such that |Ik | tends to infinity as
k tends to infinity we have

lim supk→∞| S ∩ Ik0 |≤ B(S).
| Ik0 |

We say a sequence k of positive integers is a set of intersectivity if given any set of
natural numbers S of positive Banach density B(S) there exists an integer k in k suchthat we can find s1 and s2 both in S satisfyingk = s1 − s2 .
We say a sequence of natural numbers k = (k j )∞j=1 is a sequence of Poincaré recurrence if given any measure preserving dynamical system on a probability space(X, β , µ, T ) and any set A in β of positive measure there exists an element k of k suchthatµ(A ∩ T −k A) > 0.
Theorem 2. Suppose φ is a polynomial mapping the natural numbers to themselves,
such that φ (0) = 0. Then the sequence (φ (k j )) j≥1 is Poincaré recurrent if (k j ) j≥1 is
good.
Theorem 3. Suppose φ is a polynomial mapping the natural numbers to themselves,
such that φ (0) = 0. Then the sequence (φ (k j )) j≥1 is intersective if (k j ) j≥1 is good.

Weyl’s Theorem and Ergodic Theory

109
1
p

For f ∈ L p (X, B, µ), with p ≥ 1 set k f k p = ( X | f | p dµ) .
R

Theorem 4. Suppose that φ is a polynomial mapping the natural numbers to themselves, such that φ (0) = 0 and that (k j ) j≥1 is good. Then for the dynamical system(X, B, µ, T ) and f ∈ L p (X, B, µ), for p ≥ 1. Then there exists f such that
lim

N→∞

1 N−1
∑ f (T φ (kn ) x) − f
N n=0

= 0.
p

It is natural to ask if Theorem 1.5 is true almost everywhere.
We say a set S contained in Z is Glasner if for every infinite set A contained in T
and ε > 0, some dilation nA = {nx : x ∈ A} is ε dense (that is nA intersects every
interval of length ε). This definition is motivated by the fact that in 1979 S. Glasnershowed that given an infinite set A ⊂ T there exists a natural number n such that nA
is ε dense in T. We have
Theorem 0.6 : Suppose (kn )n≥1 good. Let ψ be a polynomial of degree k ≥ 1
mapping the natural numbers to themselves. Suppose δ > 0. Then there exists
ε(ψ, δ ) > 0 such that if 0 < ε < ε(ψ, δ ) given any set X contained in T of
cardinality s with1s > ( )2k+δ
ε
has an ε dense dilation of the form ψ(kn )X, for some integer n.

1 List of known good sequences1
1. The natural numbers: The sequence (n)∞n=1 is L -good universal. This is Birkhoff’s
pointwise ergodic theorem.
p
2. Condition H: Sequences (an )∞n=1 that are both L -good universal and Hartman
uniformly distributed can be constructed as follows. Denote by [x] the integer partof a real number x. Set an = [τ(n)] (n = 1, 2, . . . ), where τ : [1, ∞) → [1, ∞) isa differentiable function whose derivative increases with its argument. Let Ωmdenote the cardinality of the set {n : an ≤ m}, and suppose, for some function
ϕ : [1, ∞) → [1, ∞) increasing to infinity as its argument does, that we set

ρ(m) =sup∑ e(zan ) ,


h
1 ,1
n : an ≤m{z}∈ ϕ(m)2where e(x) = e2πix for a real x. Suppose also, for some decreasing function ρ :[1, ∞) → [1, ∞) and some positive constant ω > 0, that

110

Radhakrishnan Nair and Entesar Nasrmρ(m) + Ω[ϕ(m)] + ϕ(m)ΩmThen if we have≤ ωρ(m).

∞∑ ρ(θ n ) < ∞n=1

for all θ > 0, we say that (an )∞n=1 satisfies condition H.
Sequences satisfying condition H are known to be both Hartman uniformly distributed and L p -good universal. Specific sequences of integers that satisfy condition H include an = [τ(n)] (n = 1, 2, . . . ) where:
I. τ(n) = nγ if γ > 1 and γ ∈/ N.
γII. τ(n) = elog n for γ ∈ (1, 32 ).
III.τ(n) = bk nk + · · · + b1 n + b0 for bk , . . . , b1 not all rational multiplies of the same
real number.
IV.Hardy fields: By a Hardy field, we mean a closed subfield (under differentiation) of the ring of germs at +∞ of continuous real-valued functions with addition and multiplication taken to be pointwise. Let H denote the union of all∞
Hardy fields. Conditions for (an )∞n=1 = ([η(n)])n=1 , where η ∈ H to satisfy
condition H are given by the hypotheses of Theorems 3.4, 3.5 and 3.8. in [?].
3. A random example: Suppose that S = (bn )∞n=1 is a strictly increasing sequenceof natural numbers. By identifying S with its characteristic function χS , we mayview it as a point in Λ = {0, 1}N , the set of maps from N to {0, 1}. We may
endow Λ with a probability measure by viewing it as a Cartesian product Λ =∏∞n=1 Xn , where, for each natural number n, we have Xn = {0, 1} and specify theprobability νn on Xn by νn ({1}) = ωn with 0 ≤ ωn ≤ 1 and νn ({0}) = 1 − ωn suchthat limn→∞ ωn n = ∞. The desired probability measure on Λ is the corresponding
product measure ν = ∏∞n=1 νn . The underlying σ -algebra A is that generated by
the cylinders{(∆n )∞
n=1 ∈ Λ : ∆ n1 = αn1 , . . . , ∆ nk = αnk }for all possible choices of n1 , . . . , nk and αn1 , . . . , αnk . Then almost every point(an )∞
n=1 in Λ , with respect to the measure ν, is Hartman uniformly distributed.
See Proposition 8.2 (i) in [?] for the details of this. Again Hartman uniformly
distributed sequences are called ergodic sequencesin this paper.
S∞
4. Block sequences: Suppose that (an )∞
=
[d
,
e
n
n ] is ordered by absolute value
n=1
n=1
for disjoint ([dn , en ])∞
with
d
=
O(e
)
as
n
tends
to infinity. Note that this
n
n−1
n=1
allows the possibility that (an )∞iszerodensity.
This
exampleis an immediate
n=1
consequence of Tempelman’s semigroup ergodic theorem. See page 218 of [T].
Being a group average ergodic theorem this pointwise limit must be invariant.
which ensures that the block sequence must be Hartman uniformly distributed.
The proof of this, which we don’t need in this paper and is hence forgone is a
simple exercise in spectral theory.
p
5. Random perturbation of good sequences: Suppose that (an )∞n=1 is an L -good universal sequence which is also Hartman uniformly distributed. Let θ = (θn )∞n=1 beWeyl’s Theorem and Ergodic Theory111

a sequence of N-valued independent, identically distributed random variables withbasic probability space (Y, A , P), and a P-complete σ -field A . Let E denote
expectation with respect to the basic probability space (Y, A , P). Assume that
there exist 0 < γ < 1 and β > 1/γ such thatγan = O(en )andβE log+ |θ1 | < ∞.

p
Then (an + θn (ω))∞
n=1 is both L -good universal and Hartman uniformly distributed [NW].

References[BeL] A. Bellow – V. Losert On sequences of zero density in ergodic theory. Conference in modern
analysis and probability (New Haven, Conn. 1982), 49–60, Contemp. Math. 26, Amer. Math.
Soc. Providence. RI. 1984.
[Bos] M. Boshernitzan – G. Kolesnik – A. Quas – M. Wierdl Ergodic averaging sequences J. Anal.
Math. 95 (2005), 63–103.
[Bou] J. Bourgain On the maximal ergodic theorem for certain subsets of the integers, Israel J. Math.
Vol. 61 no. 1, 39–72 (1988).
[N] R. Nair On uniformly distributed sequences of integers and Poin-caré recurrence II, Indag.
Math., N. S. vol 9 (1998), no. 3, 405–415.
[NW] R. NAIR and M. WEBER. On random perturbation of some intersective sets. Indag. Math.
(N.S.), 15 (3), (2004), 73–381.
[T]
A. Tempelman Ergodic Theorems for Group Actions”, Kluwer Academic Publication, (2010).
[UZ] R.Urban – J.Zienkiewicz Weak type (1,1) estimates for a class of discrete rough maximal
functions, Math. Res. Lett. 14 (2007), no. 2, 227-237.
[W] H. Weyl Über die Gleichverteiling von Zahlen mod. Eins., Mathematische Annalen 77(1),313—-352, 1916

Fractals and space-filling curves viewed by a newnumerical computation system using infinities
and infinitesimals
Fabio Caldarola

Abstract In the first part of the talk we briefly introduce a new computational system
based on infinite and infinitesimal quantities and we show how to work numericallywith it in a very handy way. Then we describe the “state of the art” giving a quick
overview of how this new computational methodology has already been successfully
applied in a number of theoretical and computational research areas: if time allows
we will choose and explain briefly some examples.
In the second part we focus on some space-filling curves and d-dimensional fractals, and we present a double level of treatment: at “finite” and at “infinite”. In the firstsetting we analyze deeply the generating sequences of the considered fractals and, inparticular, we study the characteristics of various d-dimensional generalizations; inthe second setting we use the new computational machinery to investigate their behavior at “infinity” making a precise and detailed analysis of such geometric fractal
objects, in a similar way as for ordinary finite shapes and familiar geometric entities.
Lastly, adopting the new point of view, we show as each fractal or space-filling
curve considered previously, gives rise to a large family of infinitely many self-similar
objects.

1 Introduction
In this paper we want to give, rather than a detailed treatment of the topics of thetalk, some guidelines to introduce the reader to a new computational system, to show
him some of the several possible applications in different fields and, above of all,to provide some references and a discussed bibliography for further, more complete
readings.
Fabio Caldarola
Dep. of Mathematics and Computer Science, University of Calabria, Cubo 31/B, Ponte Bucci, 87036
Rende (CS), Italy, e-mail: caldarola@mat.unical.it

113

114

Fabio Caldarola

In particular the organization of the paper is as follows: in Section 2 we will givethe rudimenta of the mentioned new numerical system recently introduced by Ya. D.
Sergeyev; in its essence, it represents an alternative to the classical view of the set of
natural numbers N (and of the larger sets Z, Q, R), and it is simple to use as we ordinarily do with N. Sergeyev’s system is based on infinite and infinitesimal quantities
like Robinson’s approach to non-standard analysis (see [1]), but it is different fromthe last, especially for the great versatility of use and its strong computational character. For detailed introduction surveys to Sergeyev’s system, which show how one
is able to work numerically with infinities and infinitesimals in a handy way as withfinite numbers, the reader can see [2, 3, 4, 5] and the book [6], written in a popular
way and easily understandable also by a high school student.
This computational methodology has already been successfully applied in a numberof theoretical and computational research areas as optimization and numerical differentiation (see [7, 8, 9, 10]), cellular automata (see [11, 12]), Euclidean and hyperbolic
geometry (see [13, 14]), percolation (see [15, 16, 17]), fractals (see [18, 19, 20, 21, 22,17]), infinite series and the Riemann zeta function (see [23, 24, 25]), the first Hilbert
problem, Turing machines and supertasks (see [26, 27, 28, 29]), numerical solutionof ordinary differential equations (see [30, 31, 32, 33]), etc.
In the talk at the conference we will focus on some space-filling curves and ddimensional fractals, referring to some works of the author ([34], [35], [18] and [36]),
but here, for problem of space, we give some details only for one of them: the ddimensional Sierpinski tetrahedron.
We want to point out that, for each of the mentioned objects of the talk and for thed-dimensional Sierpinski tetrahedron in the following, we present a double level oftreatment: at “finite” and at “infinite”. In the first setting we analyze deeply the generating sequences which approximate the considered fractals, first in dimension 2 and
3 to have viewable pictures of them, then we study accurately the characteristics ofvarious d-dimensional generalizations. In the second setting, i.e. at infinity, almost allmeasures related to such fractals (or space-filling curves) approaches 0 or +∞, andwe can not say any more by traditional analysis. For instance, these are totally indistinguishable from classical mathematics, even though they have, per se, a completely
different meaning. So, using the new computational machinery we referred above toinvestigate the behavior at “infinity”, we obtain, in each case, a whole family of values
expressed in the new system and, by defining equivalence relations between them, or
looking at their ratios written in power series in the new system, or employing othermethods, we are able to make a precise and detailed analysis of the behavior of suchgeometric fractal objects, in a similar way as for ordinary finite shapes and familiar
geometric entities.
During the discussion of the topics we will suggest various further directions of research and how it is possible to generalize the results communicated in the talk. We
in fact believe that papers using the new approach will be more and more numerous
in the next years for two main reasons: the great versatility which allows to apply the
new computational system to a really large variety of subjects, and the fact that it has
been introduced so recently that many of the possible application areas are still totally
unexplored.

Fractals and space-filling curves viewed by a new numerical computation system

115

2 The new computational system: a brief description
In this section we want to give some of the strictly indispensable notions and someexamples that allow us to work with the new computational system. The main idea
followed by Ya. D. Sergeyev in introducing his new system, is to find a way to measure infinite and infinitesimal quantities in an easy, handy and useful way for calculations and applications. Hence, in the early 2000s, he proposed a system based on
two different fundamental units of measure: the familiar natural number 1 for finite
quantities and another that had the same functions as 1, but for infinite quantities:
it is the grossone, expressed by the new numeral 1 and formally introduced by the
Infinite Unit Axiom (IUA)(see, for example, [6, 2, 37]). The new infinite number 1
has several different properties and characterizations: for instance, it represent the
number of elements in the set of natural numbers N, but it is necessary to emphasize
immediately that 1 is not equal to the Cantor’s cardinality ω, ℵ0 , ℵ1 , etc., or toother yet known entity or symbols. An important property we need for our employ ofthe new computational method in this paper, is that 1 is the last element in the set of
natural numbers of the new system, and moreover, every sequential process can nothave more than 1 steps.
As regards explicit computations, the numeral 1 allows one to express and to ordera huge variety of numerals representing different infinities and infinitesimals; for in1
3
stance, 1 ,, 2 1 , 1 − 10, 1 5.2 are examples of infinities and 1 −1 ,, 1 −10 ,31− 1 −5.2 are examples of infinitesimals.
The way to do computations inside the new system is easy and intuitive: for example,
in many simple cases it coincides with the one in the field of rational functions R[x],where 1 takes the place of the unknown variable x. Even though the variety of possible operations, expressions and computations in the new system, is much larger thanthe one in the field R[x], we remark that all they are quite intuitive and easy to use; inthe following we give some examples of computations and main relations:• 0 · 1 = 1 · 0 = 0,

1 0 = 1,• 0 · 1 −1 = 1 −1 · 0 = 0,•

1 · 1 −1 = 1,••

1 1 = 1,

0

1 −1 − 1 −1 = 0,

1 −1

1 −1 > 0,• 3 · 1 − 4 = 3 1 − 12,

0 1 = 0,= 1,

1 2 · 1 −3.4 = 1 −1.4 ,

1 − 1 = 0,12
1 −3.4

1
= 1;
1

1 −1
= 1;
1 −1
= 1 5.4 ;


 3
3 2
1 + 3 · 1 − 2 1 −2 = 1 2 − 6 1 −2 ;2
2

1 2.1 + 2 − 3 1 −3.4
+ 2 1 = 3 1 + 2 1 −1.1 − 3 1 −4.5 ;
1 1.1
3


2 1 = 23 1 ,
2 · 3 1 − 5 1 · −4 · 2 1 = −8 · 26 1 + 20 · 1 · 2 1 ;

116

•

Fabio Caldarola
2 1 − 3 + 3 · 2−2 1 · 22 1 − 2 · 2− 1 = 23 1 − 3 · 22 1 + 1 + 6 · 2− 1 − 6 · 2−3 1 ;

• 0<

1
1
1
2π
< 2 <1<−4 << 1 < 1 +3 < 1 2 −4 < 2 1 −3 1 .
3.5
1
1
6
6

We think that the previous examples are enough to give an idea sufficiently clear
of how to do basic computations in the new system. We point out that it is also
possible to use an on-line calculator called the Infinity Computer and available at[38]. For more details about the system, the way to do computations, and some
applications, the reader can see, for example, [2, 3, 4, 5, 6, 39, 40], or also several other papers and information available at the home page of Ya. D. Sergeyev,
at http://wwwinfo.deis.unical.it/yaro/
Since the conference Numeration 2017 focuses also on mathematical logic, we
conclude this section by informing that, for a formal logic point of view on the theoryof grossone, the reader can also see, for example, the paper of G. Lolli [41]. Moreover,in [42] it is possible to find a brief survey on the history of infinities and infinitesimals
in mathematics.

3 The Sierpinski d-dimensional tetrahedron
The Sierpinski gasket, also called the Sierpinski triangle and denoted by ∆ 2 , is one of
the most known and very popular fractal set; it has the exterior shape of an equilateraltriangle, and is subdivided recursively into smaller similar triangles, from which thecentral ones are removed at each step as in Fig. 1.

(a) ∆12(b) ∆22(c) ∆32

Fig. 1: The first three steps in the construction of the Sierpinski gasket ∆ 2 , startingfrom ∆0 , the regular triangle of unitary side.
The equivalent 3-dimensional object of the Sierpinski gasket is called the Sierpinski tetrahedron and denoted by ∆ 3 : the first steps in its construction are shown in Fig.
2. But clearly, it is also possible to construct, in the same way, a d-dimensional fractal
object in every dimension d > 2: this is what we will do, with some details, in theFractals and space-filling curves viewed by a new numerical computation system(a) ∆13(b) ∆23117(c) ∆33

Fig. 2: The first three steps in the construction of the 3-dimensional Sierpinski tetrahedron, starting from the regular tetrahedron ∆03 of side one.

following.
First of all we recall that the generalization of a triangle or tetrahedron to arbitrary
dimension d > 0, is what is called a d-simplex or, less commonly, a d-dimensional
tetrahedron. More precisely, a d-simplex is a d-dimensional polytope which is theconvex hull of d + 1 affinely independent points in RD , D > d + 1 and, of course, it
is called regular if all its edges have the same length.
The use of simplexes is widespread in many areas of mathematics like algebraic geometry, algebraic topology and especially in singular homology; but we advise thereader that what in literature is called the standard d-simplex is different from ourdnotion of unitary d-simplex or unitary d-tetrahedron, denoted√ by ∆0 and widely usedin the following. In fact, whilst the first has edge length 2 because it is the convex
hull of the standard basis (1, 0, . . . , 1), . . . , (0, . . . , 0, 1) of Rd+1 , that is()
d(x0 , . . . , xd ) ∈ Rd+1

∑ xi = 1 and xi > 0 for all i = 0, . . . , d ,i=0

the second is a d-tetrahedron whose edges have all unitary length. We recall that thed-volume of a regular d-simplex is equal to√d +1 d√ ·l ,(1)d! 2dwhere l is the length of its edges. Moreover, if 0 6 k 6 d, every k-dimensional face(briefly k-face) of a d-simplex is a k-simplex itself, and since any k + 1 points fromthe d + 1 vertices of a d-simplex identify uniquely a k-face, then, the number of the
k-faces of a d-simplex is given by the binomial coefficient


d +1
.
(2)
k+1

118

Fabio Caldarola

Now let d > 2 be a fixed integer; to build a fractal ∆ d which generalizes
 the Sierpinski
gasket ∆ 2 and the Sierpinski tetrahedron ∆ 3 , we define a sequence ∆nd n . Note that∆0d is yet defined and ∆1d is the union of d + 1 regular tetrahedra of side 1/2, each one
built in a corner of ∆0d . Then we can adopt two equivalent inductive constructions at
the generic step n > 2 to obtain ∆nd : the first one consists to repeat a copy of ∆1d , scaledd , insteadby ln−1 := (1/2)n−1 , in each small tetrahedron of side ln−1 constituting ∆n−1dthe second construction consists to replicate a copy of ∆n−1 , scaled by l1 = 1/2, ineach of the d + 1 tetrahedrons of side l1 composing ∆1d .
Finally, for every d > 2, the d-dimensionalTSierpinski tetrahedron ∆ d is the limit
limn→+∞ ∆nd , and note that it is also equal to n∈N ∆nd .
Now we want to attach to each of such fractal ∆ d , some sequences of real numbers
 d, kvn n which give a k-dimensional valuation of the elements of the generating se
quence ∆nd n . More precisely we pose the followingddDefinition 1. For all integers d > 2 and n > 0, let vd,
n be the d-volume of ∆ n . Mored, kover, if 0 6 k < d, let vn be the sum of the k-volumes of the k-dimensional elements(briefly k-elements) lying on the (d − 1)-dimensional boundary surface of ∆nd .
(d)

The next proposition gives a general expression
for vd,kn , but first note that, if Nn n
1
the number of tetrahedra of side ln =which make up ∆nd , then2(d)Nn = (d + 1)n ,

is

(3)

for every n > 0.
Proposition 1. For all n > 0 and d > 2, we have
√

 

d +1 nk+1 d +1


√
·
·

 k! 2k
k+1
2k
k
=
vd,
n

n+1

+d +1

 (d + 1)
2

if 1 6 k 6 d,
(4)
if k = 0.

For the proofs of the results in this and the next section we refer to [34].
For every d > 2 and 0 6 k 6 d, we pose
k
d, k
v∞
:= lim vd,
n
n→+∞

(5)

and denote by dim(∆ d ) the fractal dimension of ∆ d . For comprehensive references
about the general theory of the dimension of a fractal, the reader can see [43] or [44];in our particular case, it is simple to prove thatdim(∆ d ) =ln(d + 1)= log2 (d + 1),
ln 2

(6)

Fractals and space-filling curves viewed by a new numerical computation system

119

Table 1: The values of the limit 5 in dependence from d and k, until the dimension
d = 8 and for d = 15, 32, 63, 127. It is obvious that in the missing lines, for examplekd ∈ {16, . . . , 30} or d ∈ {32, . . . , 62}, the values of vd,∞ until k = 9, are the same asfor d = 15 and d = 31, respectively.
d dim ∆ d
2 log2 33
2
4 log2 55 log2 6
6 log2 77
3

d,1 d,2 d,3 vd,4
vd,0
∞ v∞ v∞ v∞∞+∞ +∞ 0√+∞ +∞ 3 0+∞ +∞ +∞ 00+∞ +∞ +∞ 00+∞ +∞ +∞ 00√+∞ +∞ +∞ 335
0
2

vd,5
∞
0
0
0

vd,6
∞
0
0

vd,7
∞
0

vd,8
∞ ...
- ...
- ...
- ...
- ...
- ...
- ...

+∞ +∞ +∞ +∞ 0
. . . . . . . . . . . . . .√.

0
...

0
...

0
...

0 ...
... ...

0. . .√

0
...

0
...

0 ...
... ...

...

0
... √

0
...

0 ...
... ...

8...

log2 9
...

15
...

4
...

+∞ +∞ +∞ +∞ 912 5... ... ... ... ...

31
...

5
...

+∞ +∞ +∞ +∞ +∞... ... ... ... ...

18879 3
10

63
...
127
...

6
...
7
...

+∞ +∞ +∞ +∞ +∞... ... ... ... ...
+∞ +∞ +∞ +∞ +∞... ... ... ... ...

+∞
...
+∞
...

3235501 7
30

...
+∞
...

0
...

0 ...
... ...
5957094385
0 ...
84
...
... ...

for every d > 2 (see, for example, [45]). In Table 1 there are collected some valuesd, kkdof vd,∞ and dim(∆ ). From Proposition 1, it is trivial that the sequence vn convergeskif and only if d 6 2 − 1, and converges to a nonzero value if and only if k > 2 andd = 2k − 1; in the last case the limit value is
√
 k 
k+1
2
2k −1, k
= √ ·
v∞
.
(7)
k+1
k! 2k
It is also clear that the number of occurrences of +∞ in the d-th row of Table 1 isgiven by dlog2 (1 + d)e for all d > 2 (cf. (6)), where dxe is the ceiling of x ∈ R.

4 The exact measures of the d-dimensional Sierpinski tetrahedronthrough infinite and infinitesimal computation
In the previous section we computed vnd, k for finite values of n and we obtained thatkvd,
∞ is zero, or a positive number equal to (7), or +∞: that is all what we can say
from classical analysis. It is also quite obvious that the various zeros and infinities
appearing in Table 1 have not the same meaning, because they arise from a compu-

120

Fabio Caldarola

tation of a k-dimensional volume related to a d-dimensional object where k and d
are different for each entry. For example, v2,0
∞ , representing the infinite grow of the
2,1 , representing
number of vertices of ∆n2 , has a completely different meaning from v∞
3,1
4,2
the grow of its perimeter, or from v∞ , v∞ which comes from a 2-dimensional area,or from v8,3
∞ which is related to a 3-volume in a 8-space, etc. But traditional analysis,
having got no appropriate language and notations, is not able to see these differences
and such infinite quantities are all equal, and denoted by the same symbol +∞. We
can also use the same argument for the zeros of Table 1, and hence it is clear thattraditional computing systems are inadequate to treat many phenomena occurring inmathematics, like those we are speaking about.
In this section we show as, adopting the new computing system for infinities andinfinitesimals quantities based on the grossone 1 , we can give a rich description of
the behavior at infinity of the previous constructive processes as, and maybe morethan, the one at finite.
For example, if we execute 1 steps in the construction of ∆ d , we obtain the following
values for the related k-volumes
√

 

d +1 1k+1 d +1
d, k
√
·
(8)
v1 =
2k
k! 2k k + 1
in the case 1 6 k 6 d, andvd,1 0 =d +1
d +1· (d + 1) 1 +
2
2

(9)

for k = 0 (see Proposition 1).
Definition 2. Let α and β be any quantities of the new computational system.
(i) α and β are said of the same order (in symbols ord(α) = ord(β ), or α ∼ord β ) if
their quotient is finite but not infinitesimal, that is, more precisely, if there exist
two positive real number m, M ∈ R such that 0 < m < α/β < M.
In case α, β are both infinite or infinitesimal quantities, they are also called infinities of the same order or infinitesimals of the same order, respectively.
(ii)α and β are said equivalent (in symbols α ∼eq β , or simply α ∼ β ) if their quotientis 1 up to infinitesimals. In other words, if for all ε ∈ R+ we have 1 − ε < α/β <1 + ε.
As before, in case α, β are infinite or infinitesimal quantities, they are also called
equivalent infinities or equivalent infinitesimals, respectively.
It is trivial that both the relations introduced in Definition 2 (i) and (ii) are equivalence
relations, so for example, we can ask about the equivalence class of vd,1 k , using therelation ∼ord or ∼eq .
Recall that at the beginning of the section we said that the symbols +∞ and 0 in Table
1 are not distinguishable for traditional mathematics; instead, Corollary 0.1, which isan immediate consequence of Theorem 1 (ii), states that, in the analogue new version

Fractals and space-filling curves viewed by a new numerical computation system

121

of Table 1, the elements v d,1 k are all distinct. But Theorem 1 establishes more: ourpurpose is to give information about the partition of the following setsnoV d := vd,1 k 0 6 k 6 d ,W d :=d[Vi

for all d > 2,

i=2

and

W :=

[

(10)

V d,

d>2

in equivalence classes. We denote the equivalence class of vd,1 k in W , with respect thehiihrelation ∼ord or ∼eq , by vd,1 k
and vd,1 k , respectively.
ordeq

Before to state Theorem 1, we write in the following lemma an important consequenceof the equations (8) and (9).

 !


d +1 1d, k.
Lemma 1. For all d > 2 and 0 6 k 6 d we have ord v 1 = ord
2kMoreovervt,1h ∼ord vd,1 k

if and only if

t + 1 = 2h−k · (d + 1).

(11)

The proof of the previous lemma is an easy check; now we are ready to state the main
theorem of the section.
Theorem 1.
(i) Let d > 2 and denote by νd the number of equivalence classes in the set W d withrespect the equivalence relation ∼ord . Then
if d = 2,

3


d
2
(12)
νd = 3d + 9d + 6
(−1)
d +1

+
·
if d > 3.

842
Moreover, a system of minimal representatives of the classes in W is
o
[n
RW :=
V d d even > 2 or d = 3


t +3
t, h
6h6t ,∪ v 1 t odd > 5 and h = 0 or
2

(13)

and for every v t,1 h ∈ RW , its equivalence class is
h iv t,1 hord=

2 j−h (t+1)−1, jv1j ∈ N0 , j > h .

(14)(ii) Each equivalence class in W under the relation ∼eq consists of a single element.

122

Fabio Caldarola

For the proof of the theorem the interesting reader can see [34]. We remark that atrivial consequence of part (ii) of the preceding theorem, is the following
Corollary 0.1. The elements vd,1 k are all distinct for every d > 2 and 0 6 k 6 d.
Note moreover that W is clearly a totally ordered set, but the explicit relation is not
obvious at first sight; an immediate consequence of Lemma 1 and of Theorem 1 (ii),is that(t > 2h−k · (d + 1) − 1 or
t, h
d, k
if and only if,
v1 > v1
t = 2h−k · (d + 1) − 1 and h > kwhere “>” has the obvious meaning between the elements of W .
Remark 0.1. To prove that all the elements vd,1 k of the new computational system are
effectively distinct, is not a trivial issue; for instance, when k, h > 1, it is equivalent toshow that the following system
√
√




k+1 d +1h+1 t +1


√
√
·
=
·


k+1
h+1
k! 2k
h! 2h
(15)


t
+
1
d
+
1


=
2k
2h
has no integer solutions 2 6 d < t, 1 6 k 6 d and 1 6 h 6 t. But to prove the nonexistence of such solutions of a Diophantine system as (15), is a non trivial problem; forexample, by using the most powerful computer algebra systems or scientific computational software available today, like Mathematica 11.0 by Wolfram Research Inc.,or many others, it is not possible to obtain any answer except for very small valuesof t cause the complexity of (15). Instead, as consequence of our results, we can givea full response to this problem and to similar ones arising from the other cases. In
particular, Corollary 0.1, which follows from Theorem 1 (ii), guarantees that all thenumbers in W are effectively distinct and a Diophantine systems like (15) has no nontrivial solutions.
rReferences
1. A. Robinson. Non-standard Analysis. Princeton Univ. Press, Princeton, 1996.
2. Ya.D. Sergeyev. A new applied approach for executing computations with infinite and infinitesimal quantities. Informatica, 19(4):567–596, 2008.
3. Ya.D. Sergeyev. Lagrange Lecture: Methodology of numerical computations with infinities andinfinitesimals. Rendiconti del Seminario Matematico dell’Università e del Politecnico di Torino,
68(2):95–113, 2010.
4. Ya.D. Sergeyev. Un semplice modo per trattare le grandezze infinite ed infinitesime. Matematica
nella Società e nella Cultura: Rivista della Unione Matematica Italiana, 8(1):111–147, 2015.

Fractals and space-filling curves viewed by a new numerical computation system

123

5. Ya.D. Sergeyev. Computations with grossone-based infinities. In Calude C.S. and Dinneen M.J.,
editors, Unconventional Computation and Natural Computation: Proc. of the 14th International
Conference UCNC 2015, volume LNCS 9252, pages 89–106. Springer, New York, 2015.
6. Ya.D. Sergeyev. Arithmetic of Infinity. Edizioni Orizzonti Meridionali, CS, 2003, 2nd ed. 2013.
7. S. De Cosmis and R. De Leone. The use of grossone in mathematical programming and operations research. Applied Mathematics and Computation, 218(16):8029–8038, 2012.
8. R. De Leone. Nonlinear programming and grossone: Quadratic programming and the role ofconstraint qualifications. Applied Mathematics and Computation, 218(16):submitted, submitted.
9. Ya.D. Sergeyev. Higher order numerical differentiation on the Infinity Computer. Optimization
Letters, 5(4):575–585, 2011.
10. A. Žilinskas. On strong homogeneity of two global optimization algorithms based on statistical models of multimodal objective functions. Applied Mathematics and Computation,
218(16):8131–8136, 2012.
11. L. D’Alotto. Cellular automata using infinite computations. Applied Mathematics and Computation, 218(16):8077–8082, 2012.
12. L. D’Alotto. A classification of one-dimensional cellular automata using infinite computations.
Applied Mathematics and Computation, 255:15–24, 2015.
13. M. Margenstern. An application of grossone to the study of a family of tilings of the hyperbolic
plane. Applied Mathematics and Computation, 218(16):8005–8018, 2012.
14. M. Margenstern. Fibonacci words, hyperbolic tilings and grossone. Communications in Nonlinear Science and Numerical Simulation, 21(1–3):3–11, 2015.
15. D.I. Iudin, Ya.D. Sergeyev, and M. Hayakawa. Interpretation of percolation in terms of infinity
computations. Applied Mathematics and Computation, 218(16):8099–8111, 2012.
16. D.I. Iudin, Ya.D. Sergeyev, and M. Hayakawa. Infinity computations in cellular automaton
forest-fire model. Communications in Nonlinear Science and Numerical Simulation, 20(3):861–
870, 2015.
17. M.C. Vita, S. De Bartolo, C. Fallico, and M. Veltri. Usage of infinitesimals in the Menger’s
Sponge model of porosity. Applied Mathematics and Computation, 218(16):8187–8196, 2012.
18. F. Caldarola. The sierpinski curve viewed by numerical computations with infinities and infinitesimals. submitted, 2017.
19. Ya.D. Sergeyev. Blinking fractals and their quantitative analysis using infinite and infinitesimal
numbers. Chaos, Solitons & Fractals, 33(1):50–75, 2007.
20. Ya.D. Sergeyev. Evaluating the exact infinitesimal values of area of Sierpinski’s carpet andvolume of Menger’s sponge. Chaos, Solitons & Fractals, 42(5):3042–3046, 2009.
21. Ya.D. Sergeyev. Using blinking fractals for mathematical modelling of processes of growth inbiological systems. Informatica, 22(4):559–576, 2011.
22. Ya.D. Sergeyev. The exact (up to infinitesimals) infinite perimeter of the Koch snowflake and its
finite area. Communications in Nonlinear Science and Numerical Simulation, 31(1–3):21–29,
2016.
23. Ya.D. Sergeyev. Numerical point of view on Calculus for functions assuming finite, infinite, andinfinitesimal values over finite, infinite, and infinitesimal domains. Nonlinear Analysis Series
A: Theory, Methods & Applications, 71(12):e1688–e1707, 2009.
24. Ya.D. Sergeyev. On accuracy of mathematical languages used to deal with the Riemann zetafunction and the Dirichlet eta function. p-Adic Numbers, Ultrametric Analysis and Applications,
3(2):129–148, 2011.
25. A.A. Zhigljavsky. Computing sums of conditionally convergent and divergent series using theconcept of grossone. Applied Mathematics and Computation, 218(16):8064–8076, 2012.
26. D. Rizza. Supertasks and numeral systems. In Sergeyev Ya.D., Kvasov D.E., Dell’Accio F.,
and Mukhametzhanov M.S., editors, Proc. of the 2nd Intern. Conf. “Numerical Computations:
Theory and Algorithms”, volume 1776, page 090005. AIP Publishing, New York, 2016.
27. Ya.D. Sergeyev. Counting systems and the First Hilbert problem. Nonlinear Analysis Series A:
Theory, Methods & Applications, 72(3-4):1701–1708, 2010.
28. Ya.D. Sergeyev and A. Garro. Observability of Turing machines: A refinement of the theory ofcomputation. Informatica, 21(3):425–454, 2010.

124

Fabio Caldarola

29. Ya.D. Sergeyev and A. Garro. Single-tape and multi-tape Turing machines through the lens of
the Grossone methodology. Journal of Supercomputing, 65(2):645–663, 2013.
30. P. Amodio, F. Iavernaro, F. Mazzia, M.S. Mukhametzhanov, and Ya.D. Sergeyev. A generalized
Taylor method of order three for the solution of initial value problems in standard and infinity
floating-point arithmetic. Mathematics and Computers in Simulation, 2016. in Press.
31. F. Mazzia, Ya.D. Sergeyev, F. Iavernaro, P. Amodio, and M.S. Mukhametzhanov. Numerical methods for solving ODEs on the Infinity Computer. In Sergeyev Ya.D., Kvasov D.E.,
Dell’Accio F., and Mukhametzhanov M.S., editors, Proc. of the 2nd Intern. Conf. “Numerical Computations: Theory and Algorithms”, volume 1776, page 090033. AIP Publishing, New
York, 2016.
32. Ya.D. Sergeyev. Solving ordinary differential equations by working with infinitesimals numerically on the Infinity Computer. Applied Mathematics and Computation, 219(22):10668–10681,
2013.
33. Ya.D. Sergeyev, M.S. Mukhametzhanov, F. Mazzia, F. Iavernaro, and P. Amodio. Numericalmethods for solving initial value problems on the Infinity Computer. International Journal of
Unconventional Computing, 12(1):3–23, 2016.
34. F. Caldarola. Evaluating the exact measures of the sierpinski d-dimensional tetrahedron. submitted, 2017.
35. F. Caldarola. High-dimensional vicsek fractal and p-adic numbers viewed through infinite computations. preprint, 2017.
36. F. Caldarola and Y.D. Sergeyev. Some d-dimensional fractal sponges through the lens of thegrossone theory. preprint, 2017.
37. Ya.D. Sergeyev. Numerical computations and mathematical modelling with infinite and infinitesimal numbers. Journal of Applied Mathematics and Computing, 29:177–195, 2009.
38. Ya.D. Sergeyev. http://www.theinfinitycomputer.com. 2004.
39. Ya.D. Sergeyev. Numerical computations with infinite and infinitesimal numbers: Theory andapplications. In Sorokin A. and Pardalos P.M., editors, Dynamics of Information Systems: Algorithmic Approaches, pages 1–66. Springer, New York, 2013.
40. Ya.D. Sergeyev. A few remarks on philosophical foundations of a new applied approach toInfinity. Scheria, 26-27:63–72, 2005.
41. G. Lolli. Metamathematical investigations on the theory of grossone. Applied Mathematics andComputation, 255:3–14, 2015.
42. G. Lolli. Infinitesimals and infinites in the history of mathematics: A brief survey. Applied
Mathematics and Computation, 218(16):7979–7988, 2012.
43. G. Edgar. Measure, Topology, and Fractal Geometry. Springer, New York, second edition, 2008.
44. K. Falconer. Fractal Geometry. Mathematical Foundations and Applications. John Wiley &Sons, Chichester (UK), third edition, 2014.
45. J.B. Kim and H.S. Kim. Transfer matrices of n-dimensional sierpinski tetraedron. Univ.
Beograd. Publ. Elektrotehn. Fak. Ser. Mat., 12:1–11, 2001.

On relations between systems of numerations andfractal properties of subsets of non-normal
numbers
Iryna Harko

The report is devoted to analysis of the dependence of fractal and topological properties of subsets of non-normal numbers on systems of numerations.
Till 1994 the set of numbers, which are non-normal w.r.t. s-adic expansion, wasconsidered as a ”rather small” one in the sense of Lebesgue measure as well as in thesense of the Hausdorff-Besicovitch dimension. After the proof of the superfractalityof sets of non-normal and essentially non-normal numbers for s-adic and some otherexpansions [2] and construction of such systems of representation for which the set of
essentially non-normal numbers was of full Lebesgue measure, the conjecture about
the superfractality and topological massivity of the set of essentially non-normal numbers (independently of the choice of a system of numeration) became dominating.
Probabilistic approach is shown to be very useful to prove the superfractality ofthe set of essentially non-normal numbers for Q-expansions [3], Q∞ -expansions [4]and Q∗ -expansions (under additional assumptions inf qik > 0 on the matrix Q∗ ).
i,k

We shall answer the following problems, which are well motivated by the above
arguments:
1. Is the condition inf qik > 0 necessary for the superfractality of the set of Q∗ i,kessential non-normal numbers?
2. Are there systems of numeration, for which the corresponding set of essentiallynon-normal numbers is not a superfractal?
To answer the first question we show, in particular, that there are Q∗ -expansions ofreal numbers, for which the corresponding set of essentially non-normal numbers has
zero Hausdorff-Besicovitch dimension: dimH (L(Q∗ )) = 0.
Theorem 1 ([1]). Let
Iryna Harko
Dragomanov National Pedagogical University, Pyrogova St. 9, 01601, Kyiv, Ukraine, e-mail:garko.iryna@gmail.com

125

126

Iryna Harko

Q∗ = kqik k, q2k =1
1 − q2k, q0k = q1k =, i ∈ {0, 1, 2}.
k+1
2(k + 1)

Then
dimH (L(Q∗ )) = 0.
So, we also refuted the conjecture about the superfractality of the set of essentiallynon-normal numbers independently of the choice of a system of numeration.
Moreover, we prove the existence of such Q∗ -expansions of real numbers, forwhich even the whole set D(Q∗ ) of all non-normal numbers has zero HausdorffBesicovitch dimension: dimH (D(Q∗ )) = 0.
Theorem 2 ([1]). Let Q∗ = kqik k, i ∈ {0, 1, 2, . . . , s − 1}.
Let A = {n : n = 10k , k ∈ N}, B = {n : n 6= 10k , k ∈ N, n ∈ N},
and let(1
if k ∈ B;
k+1 ,q1k = q2k = . . . = qs−1,k = 1(s−1)(k+1)
if k ∈ A.
s,(
1
1−
if k ∈ B;
k+1 ,q0k = 1 (k+1)
if k ∈ A.
s,
Then
dimH (D(Q∗ )) = 0.
We also give the sufficient conditions that the set L(Q∗ ) of essentially non-normal
numbers is of full and zero Hausdorff–Besicovitch dimension.
Theorem 3 ([1]). If all entries of a matrix Q∗ are bounded from below by somepositive constant q∗ , i.e.,
inf qik ≥ q∗ > 0,i,kthen the set L(Q∗ ) of essentially non-normal numbers is of full Hausdorff dimension,i.e.,
dimH L(Q∗ ) = 1.
Theorem 4 ([1]). Let Q∗ = kqik k, i ∈ A = {0, 1, . . . , s − 1}, and let there exists a digiti0 ∈ A, such that ∀α > 0 the condition: lim sk · qαi0 ,k = 0 is satisfied.
Then

dimH (L(Q∗ )) = 0.

k→∞References
1. Albeverio S. , Garko I. , Ibragim M., Torbin G.: Non-normal numbers: full Hausdorff dimensionality vs zero dimensionality. Bull. Sci. math. 141, 1–19 (2017)
2. Albeverio S., Pratsiovytyi M., Torbin G.: Topological and fractal properties of real numbers
which are not normal. Bull. Sci. math. 129, 615–630 (2005)

Fractal properties of subsets of non-normal numbers

127

3. Garko I., Torbin G.: On the dependence of fractal properties of the set of essentially non-normal
numbers on a system of numeration. Transactions of the Dragomanov National Pedagogical
University. Series 1: Phys.-Math. Sciences, 13, 74–81 (2012)
4. Albeverio S., Kondratiev Yu., Nikiforov R., Torbin G.: On new fractal phenomena connectedwith infinite linear IFS. Math. Nachr. (2016) doi:10.1002/mana.201500471

On Littlewood and Newman polynomial
multiples of Borwein polynomials
Paulius Drungilas, Jonas Šiurys, Jonas Jankauskas

Abstract A Newman polynomial has all the coefficients in {0, 1} and constant term 1,
whereas a Littlewood polynomial has all coefficients in {−1, 1}. We call P(X) ∈ Z[X]a Borwein polynomial if all its coefficients belong to {−1, 0, 1} and P(0) 6= 0. We exploit an algorithm developed previously by Lau and Stankov in their research on the
spectra of numbers and independently by Akiyama, Thuswaldner and Zaı̈mi in theirstudy of Height Reducing Property. The algorithm decides whether a given monic
integer polynomial with no roots on the unit circle |z| = 1 has a non-zero multiple
in Z[X] with coefficients in a finite set D ⊂ Z. Our results are as follows. For every
Borwein polynomial of degree ≤ 9 we determine whether it divides any Littlewood or
Newman polynomial. We show that every Borwein polynomial of degree ≤ 8 which
divides some Newman polynomial divides some Littlewood polynomial as well. For
every Newman polynomial of degree ≤ 11, we check whether it has a Littlewood
multiple, extending the previous results of Borwein, Hare, Mossinghoff. We find examples of polynomials whose products and squares have no Littlewood or Newman
multiples, while the original polynomials possess such multiples. Described results
were presented in the paper “On Littlewood and Newman polynomial multiples ofBorwein Polynomials” (to appear in AMS Mathematics of Computation).

P. Drungilas
Department of Mathematics and Informatics, Vilnius University, Naugarduko 24, Vilnius LT-03225,
Lithuania,e-mail: paulius.drungilas@gmail.com
J. Jankauskas
Mathematik und Statistik, Montanuniversität Leoben, Franz Josef Straße 18, A-8700 Leoben, Austria, e-mail: jonas.jankauskas@gmail.com
J. Šiurys
Department of Mathematics and Informatics, Vilnius University, Naugarduko 24, Vilnius LT-03225,
Lithuania, e-mail: jonas.siurys@mif.vu.lt

129An introduction to p-adic systems: A new kind of
number system
Mario Weitzer

In this talk a new kind of number system on the p-adic integers Z p will be introduced
which generalizes and provides a common framework for several different notions,such as positional notation systems, the 3n+1 problem, integer fibred systems, or permutation polynomials. This framework allows notions and methods of one discipline
to be translated to the other, admitting new points of views in both areas. Furthermore, it provides interesting examples of new discrete dynamical systems showing
unexpected behavior.

Mario Weitzer
Graz University of Technology, Austria e-mail: mario weitzer at@yahoo.de

131

Salem numbers as unusual Mahler measures
Artūras Dubickas

Recall that for a polynomial
f (x) = a(x − α1 ) . . . (x − αn ) ∈ C[x],where a 6= 0,

its Mahler measure is defined by M( f ) := |a| ∏nj=1 max{1, |α j |}. The polynomial f
is called reciprocal if the set of its roots {α1 , . . . , αn } is equal to {α1−1 , . . . , αn−1 }, i.e.
f (x) = ±xn f (x−1 ), and nonreciprocal otherwise. A root α > 1 of a monic irreducible
polynomial f in Z[x] of degree 2n ≥ 4 is called a Salem number if f is reciprocal andhas 2n − 2 roots on the unit circle |z| = 1.
Let L0 be the set of all possible Mahler measures of nonreciprocal (but not necessarily irreducible) polynomials in Z[x]. Various aspects of the set of Mahler measures
L := {M( f ) : f ∈ Z[x]}and of its subset of nonreciprocal measures
L0 := {M( f ) : f ∈ Z[x], f − nonreciprocal}
have been investigated in the papers of Adler and Marcus [1], Boyd [2], [3], [4],Dixon and the author [5], the author [7], Schinzel [9]. One of the problems from the
BIRS workshop “The Geometry, Algebra and Analysis of Algebraic Numbers” heldin 2015 in Banff (Canada) suggested by David Boyd 7(c) was the following:• Does L0 contain any Salem numbers?
The problem, as stated, was actually solved in [5] by Dixon and the author (see also[6]). Selecting, for instance, the nonreciprocal quartic polynomial x4 − x + 1 whose
Galois group is isomorphic to S4 and Mahler measure is equal to the productArtūras Dubickas
Department of Mathematics and Informatics, Vilnius University, Naugarduko 24, LT-03225 Vilnius,
Lithuania, e-mail: arturas.dubickas@mif.vu.lt

133

134

Artūras Dubickas|β |2 = β β 0 = 1.40126 · · · ∈ L0of two complex conjugate roots β and β 0 = β of x4 − x + 1 that are outside the unit
circle, we see that α = β β 0 must be of degree 6 over Q and, thus it is a Salem number(in this case, with minimal polynomial x6 − x4 − x3 − x2 + 1). This is true for any
totally complex nonreciprocal quartic unit β whose Galois group is doubly transitive:
each such Mahler measure M(β ) belongs to the set L0 and at the same time it is a
Salem number of degree 6.
This construction seems, however, an accidental one. So one may ask a more general question:• Are there Salem numbers of other degrees in the set L0 ?
It turns out that
Theorem 1. The set of nonreciprocal Mahler measures L0 contains infinitely many
Salem numbers of degree d = 4 and also of each degree d = 4` + 2, where ` ∈ N.
This theorem and some other related results have been proved in [8].

References
1. Adler, R.L., Marcus, B.: Topological entropy and equivalence of dynamical systems. Mem.
Amer. Math. Soc. 20 (1979), no. 219
2. Boyd, D.W.: Inverse problems for Mahler’s measure. In: Diophantine Analysis, ed. by J. Loxton and A. van der Poorten, London Math. Soc. Lecture Notes, 109, Cambridge Univ. Press,
Cambridge, 1986, pp. 147–158.
3. Boyd, D.W.: Perron units which are not Mahler measures. Ergod. Theory and Dynamical Sys.
6 485–488 (1986)
4. Boyd, D.W.: Reciprocal algebraic integers whose Mahler measures are non-reciprocal. Canad.
Math. Bull. 30 3–8 (1987)
5. Dixon, J.D., Dubickas, A.: The values of Mahler measures. Mathematika 51 131–148 (2004)
6. Dubickas, A.: Algebraic, arithmetic and geometric properties of Mahler measures. Proc. Inst.
Math. (Nat. Acad. Sc. Belarus) 13 70–74 (2005)
7. Dubickas, A.: Mahler measures in a cubic field. Czechoslovak Math. J. 56 949–956 (2006)
8. Dubickas, A.: Salem numbers as Mahler measures of nonreciprocal units. Acta Arith. 176 81–
88 (2016)
9. Schinzel, A.: On values of the Mahler measure in a quadratic field (solution of a problem ofDixon and Dubickas). Acta Arith. 113 401–408 (2004)

On multiplicative independent bases forcanonical number systems in cyclotomic number
fieldsManfred Madritsch

In the present talk we focus on number systems in the ring of integers of cyclotomic
number fields. Our goal is to show a variant of Cobham’s theorem [2] stating that the
only sets that are recognizable with respect to two multiplicative independent bases
are finite unions of arithmetic progressions.
We start with the cases of fourth and third roots of unity, which correspond to thering of Gaussian and Eisenstein integers, respectively. In the case of quadratic number
fields the polynomials giving rise to a base have been completely characterized. In
particular, the possible bases are of the form −m ± ζ3 and −m ± ζ4 with m ≥ 1 a
positive integer and ζk a primitive kth root of unity.
Moreover we clearly have that if −m + ζk is a base of a numeration system, then it
is also an integral power base of the ring of integers. Győry [3] showed that there
are only finitely many integral power bases and a conjecture of Bremner [1] andRobertson [6] states that the only possible power bases for Z[ζk ] are ζk , ηk := (1 +ζk )−1 and θk := (1 − ζk )−1 . This has been verified for several small values of k.
Let β1 , . . . , βr be the integral power bases of Z[ζk ] then a result of Kovacs andPethő [4] states that there exists Mi such that −m + βi is a base for m ≥ Mi . Our first
result state that −m + ζk , −m + ηk and −m + θk are bases of numeration systems inZ[ζk ] provided that m ≥ ϕ(k) + 1 where ϕ is Euler’s totient function.
Now we turn to the second ingredient: the multiplicative independence. We call
two bases α and β multiplicative independent if the only solution (m, n) of the equation α m = β n over the integers is the trivial solution (m, n) = (0, 0). Our second resultshows that −m + ζk and −n + ζk are multiplicative independent provided that m 6= n
and k 6= 2, 3, 4, 6. The excluded cases were already treated by Madritsch and Ziegler[5].
The last part considers the variant of Cobham’s theorem [2]. The four exponents
conjecture states that for any two pairwise Q-independent pairs of complex numbers
Manfred Madritsch
Universit de Lorraine, 54506 Vandouevre-lès-Nancy, France e-mail: manfred.madritsch@univlorraine.fr

135

136

Manfred Madritsch(x1 , x2 ) and (y1 , y2 ) at least one of the numbers
ex1 y1 ,ex1 y2 ,ex2 y1andex2 y2is transcendent. We can show that under the four exponents conjecture every subset
S ⊂ Z[ζk ] which is α- and β -recognizable for multiplicative independent α and β
has to be syndetic. In this context a subset S ⊂ Z[ζk ] ⊂ C is called syndetic if there
exists r > 0 such that for each γ ∈ Z[ζk ] the intersection S ∩ B(γ, r) is non-empty (hereB(γ, r) is the closed disk with center γ and radius r.
This is joint work with Paul Surer from the Universität für Bodenkultur and Volker
Ziegler from the University of Salzbourg.

References
1. Andrew Bremner. On power bases in cyclotomic number fields. J. Number Theory, 28(3):288–
298, 1988.
2. Alan Cobham. On the base-dependence of sets of numbers recognizable by finite automata. Math.
Systems Theory, 3:186–192, 1969.
3. K. Győry. Sur les polynômes à coefficients entiers et de discriminant donné. III. Publ. Math.
Debrecen, 23(1-2):141–165, 1976.
4. B. Kovács and A. Pethő. Number systems in integral domains, especially in orders of algebraic
number fields. Acta Sci. Math. (Szeged), 55(3-4):287–299, 1991.
5. Manfred G. Madritsch and Volker Ziegler. An infinite family of multiplicatively independentbases of number systems in cyclotomic number fields. Acta Sci. Math. (Szeged), 81(1-2):33–44,
2015.
6. Leanne Robertson. Monogeneity in cyclotomic fields. Int. J. Number Theory, 6(7):1589–1607,
2010.

Topology of a class of p2-crystallographic
replication tiles
Benoı̂t Loridant and Shu-qin Zhang

Abstract We study the topological properties of a class of planar crystallographic
replication tiles. Let M ∈ Z2×2 be an expanding matrix with characteristic polynomial
x2 + Ax + B (A, B ∈ Z, B ≥ 2) and v ∈ Z2 such that (v, Mv) are linearly independent.
Then the equation
MT +

B−1
v = T ∪ (T + v) ∪ (T + 2v) ∪ · · · ∪ (T + (B − 2)v) ∪ (−T )2(1)defines a unique nonempty compact set T satisfying T o = T . Moreover, T tiles theplane by the crystallographic group p2 generated by the π-rotation and the translations by integer vectors. Leung and Lau [2] proved in the context of self-affine lattice
tiles with collinear digit set that T ∪ (−T ) is homeomorphic to a closed disk if andonly if 2|A| < B + 3. However, this characterization does not hold anymore for T itself(see Figure 1, for instance). We prove that
The crystile T is disk-like if and only if − 2 ≤ A ≤ 1 and B ≥ 2 or A = B = 2.
To achieve this, we find that the crystallographic replication tiles as (1) are homeomorphic to the tiles defined as follows,

 



1
B−2
g(T ) = T ∪ T +∪···∪ T +∪ (−T )
(2)
0
0
where

Benoı̂t Loridant
Chair of Mathematics and Statistics, University of Leoben, Franz-Josef-Strasse 18, A-8700 Leoben,
Austria e-mail: benoit.loridant@unileoben.ac.at
Shu-qin Zhang
Chair of Mathematics and Statistics, University of Leoben, Franz-Josef-Strasse 18, A-8700 Leoben,
Austria e-mail: zhangsq ccnu@sina.com

137

138

Benoı̂t Loridant and Shu-qin Zhang    B−1 
0 −Bx2g(x, y) =
+
1 −A
y
0

(3)

is an expanding mapping on R2 . Thus to prove the result, it is sufficient to prove it for
T given by (2).
As a result of [3], we notice that the lattice tile T ` given by



 



0 −B
1
B−1
T` = T` ∪ T` +∪···∪ T` +
.
(4)
1 −A
0
0
is a translation of T ∪(−T ) for fixed A and B. For the case 2|A|−B < 3, the associatedlattice T ` is disk-like by the result of Leung and Lau [2] and a result of Akiyama
and Thuswaldner [1] on CNS tiles allow us to estimate the set of neighbors of T .
Then finding out the disk-like tiles for this case will rely on the construction of theassociated neighbor graphs for the whole class. Then using a criterion of Loridant andLuo [4], we can check the disk-likeness of a crystile. For the case 2|A| − B ≥ 3, we
use a purely topological argument to prove that the associated tiles are not disk-like.

(a) The lattice tile T `(b) The crystallographic tile T

Fig. 1: Lattice tile and Crystile for A = 2, B = 3.

References
1. S. A KIYAMA AND J. M. T HUSWALDNER, The topological structure of fractal tilings generated
by quadratic number systems, Comput. Math. Appl., 49 (2005), pp. 1439–1485.
2. K.-S. L EUNG AND K.-S. L AU, Disklikeness of planar self-affine tiles, Trans. Amer. Math. Soc.,
359 (2007), pp. 3337–3355.
3. B. L ORIDANT, Crystallographic number systems, Monatsh Math, 167 (2012), pp. 511–529.
4. B. L ORIDANT AND J. L UO, On a theorem of Bandt and Wang and its extension to p2-tiles,
Discrete Comput. Geom., 41 (2009), pp. 616–642.

Topology of a class of p2-crystallographic tiles

139

0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0
-0.2
-0.2

-0.4
-0.4

-0.2

0

0.2

0.4

0.6

0.8

1

-1

-0.8

-0.6

-0.4

-0.2

0

0.2

Fig. 2: B = 3. For A = 2 on the left, T is not disk-like and for A = −2 on the right, T
is disk-like