Numeration 201822-25 May 2018
Paris
FranceTable of contents

Invited talks (Edita Pelantová, Robert F. Tichy)

3

Establishing and maintaining databases of self-affine tiles, Bandt Christoph [etal.]1

On the beta-expansion of integers of Z[beta]; connections with self similartilings, Bertrand-Mathis Anne
3

Integer multipliers of real polynomials without nonnegative roots, Brunotte
Horst
4

On the magic of some families of fractal dendrites, Cristea Ligia Loretta

5

Multiplicative dependence of shifted algebraic numbers, Dubickas Arturas

7

Representations of palindromes in the Fibonacci word, Frid Anna

9

Random homogeneous beta-expansions and self-similar measures, Hare Kathryn [etal.]13

Totally positive quadratic integers and numeration, Hejda Tomas [et al.]14

Toolset for supporting the number system research, Hudoba Peter [et al.]19

Characterization of rational matrices that admit finite digit representations, Jankauskas
Jonas [et al.]221Unique expansions on fat Sierpinski gaskets, Kong Derong [et al.]23

Multi-base Representations and their Minimal Hamming Weight, Krenn Daniel [etal.]24Infinite families of number systems, Krásenský Jakub [et al.]26

Ito alpha-continued fractions and matching, Langeveld Niels [et al.]29

The sum-of-digits function of linearly recurrent number systems and almost
primes, Madritsch Manfred
31

Constructing invariant densities for random systems, Maggioni Marta [et al.] 33

Some complexity results in the theory of normal numbers, Airey Dylan [etal.]36

Mobius Orthogonality for automatic sequences and beyond, Müllner Clemens [etal.]41

Rotation number of contracted rotations, Nogueira Arnaldo

42

On Schneider’s Continued Fraction Map on a Complete Non-Archimedean
Field., Nair Radhakrishnan
44

Essentially non-normal numbers for Cantor series expansions, Nikiforov Roman [et al.]50

Number systems over orders, Pethő Attila

52

Fundamental Domains for Rational Function Based Digit Systems of Formal
Laurent Series over Finite Fields, Rodriguez Alfonso David [et al.]56

Open maps: small and large holes, Sidorov Nikita

57

The level of distribution of the Thue–Morse sequence, Spiegelhofer Lukas

58

2

Some negative results related to Poissonian pair correlation problems, Stockinger
Wolfgang [et al.]62

Symmetric and congruent Rauzy fractals, Surer Paul [et al.]66

Digital questions in finite fields, Swaenepoel Cathy

68

Some news on rational self-affine tiles, Thuswaldner Jörg

69

Indecomposable integers and universal quadratic forms, Tinková Magdaléna [etal.]70

Lenticular Poles of the Dynamical zeta Function of the beta-shift for Simple
Parry Numbers Close to One, Dutykh Denys [et al.]72

An Effective Criterion for Periodicity of l-adic Continued Fractions, Capuano
Laura [et al.]73

Periodic representations in Salem bases, Vávra Tomáš

75Topology of a class of self-affine tiles in Rˆ3, Zhang Shuqin [et al.]76

Author Index

77

3Invited talks
On spectra of numbers
Edita Pelantová
Czech Technical University in Prague
For a given base β ∈ C of modulus > 1 and a finite alphabet A ⊂ C, we consider the setA

X (β) =

n
nX
k=0

o
ak β k : n ∈ N, a0 , a1 , . . . , an ∈ A ,called (β, A)-spectrum.
We begin with the classical case where the base β is real and the alphabet A is subsetof Z. We review recent results on topological properties of the spectra. If β is a Pisot number, we discuss also geometrical properties of spectra and properties of symbolic sequences
associated to X A (β). Then we concentrate on (β, A)-spectra where β or A are complex.
We motivate the study of complex spectra by questions comming from modeling of quasicrystals and from on-line algorithms for arithmetics in the complex field. We provide alist of results for complex spectra. It is modest and wide open to further research.

Normality, Computability and Discrepancy
Robert F. Tichy
Graz University of Technology
We give a survey on recent developments in the theory of normal numbers. In particular algorithms for the construction of absolutely normal numbers are established andanalyzed. This includes normality with respect to classical radix system as well as withrespect to Pisot numeration systems and continued fraction expansions. It seems that
there is a tradeoff between the computational complexity of the algorithms and the speedof convergence to normality (measured by the discrepancy of the corresponding lacunary
sequences). In paricular, constructions of Sierpinski, Turing, Schmidt and Levin are investigated in detail. Furthermore, various probabilistic limit laws for discrepancies of relatedsequences are established. This explains the statistical nature of normality and lacunarity.

4

Establishing and maintaining databases of self-affine tiles
Christoph Bandt (Greifswald, Germany), Dmitry Mekhontsev (Novosibirsk, Russia)

Self-affine graph-directed constructions (graph-IFS for short) include Rauzy-type tiles
obtained from substitutions as well as Penrose-type tiles obtained from cut-and-projectschemes. A projection approach based on mappings was implemented on computer by
the second author to find large lists of new examples. Sometimes, especially in the fractalcase, such lists become so extensive that careful visual inspection is impossible. Thus thecomputer must eliminate equivalent datasets and determine properties of the examples
which can be used to select the most interesting specimen. We describe algorithms forthe search as well as for the management of the database. The package is available athttps://ifstile.com.
Our setup is a graph-IFS given by an expanding integer matrix M and integer translations in high-dimensional space. Tiles, or fractal attractors, are studied in a twodimensional invariant subspace of M. Moreover, there can be a discrete symmetry group S
which commutes with M, the simplest symmetry being s− (x) = −x. Our figure shows a few
modifications which are obtained from the Rauzy substitution matrix M with appropriate
choice of translations and adding s− to some of the contraction maps.

Figure 1: Simple modifications of the Rauzy tile.
The search for new examples is performed by a random walk on the parameter spaceof integer translations and discrete symmetries, while the given M and graph structureof the IFS remain fixed. The main algorithmic ingredient is a check for the open set
condition of the graph-IFS which corresponds to the Arnoux-Ito coincidence property inthe substitution approach. In contrast to the algorithms described in the monograph ofSiegel and Thuswaldner (2010), we use only one automaton which we call the neighbor
graph of the IFS. It describes in a canonical way the dynamical boundary of the given
graph-IFS as a new graph-IFS.

1

sciencesconf.org:numeration2018:195961

To eliminate equivalent datasets from our list, we calculate various properties for eachnew dataset. Parameters of the neighbor graph, like number of vertices and edges, can betaken as invariants. The boundary dimension(s) and certain moments of the equidistribution on the tiles form other invariants. Topological properties can be calculated fromthe neighbor graph. The list of data sets can be sorted with respect to any property, andexamples with desired properties can be selected.
In the talk, mathematical background will be given, and experiments with Rauzy-type
fractals will be demonstrated.

2

sciencesconf.org:numeration2018:195961

Anne Bertrand Mathis
Université de Poitiersanne.bertrand@math.univ-poitiers.fr

On the βexpansion of integers of Z [β].Connection
with the selfsimilar tilingsLetbe an unimodular Pisot number of degree d and let Z [β] be the set βd−1u1 β+ ... + ud ; u1 , ..., ud ∈ Z . The βexpansions of the numbers of Z [β]are finite or ultimately periodic.
It is wellknown that if the β expansion of 1 is finite:
1) Every number of Z [β] admits a finite β−expansion (we say that βverifies the property F ).
2) 0 is an interior point (in Rd−1 ) of the fundamental tile of the Rauzy’s
selfsimilar tiling.
We prove that if the β expansion of 1 is a1 ...ah b1 ...bk b1 ...bk ... where h+k =d (i.e. β do not has complementary values) then
1) Every numbers of Z [β] admits either a finite expansion or an expansion
ending by b1 ...bk b1 ...bk ... (we says that β verifies the property F ? ).
2) 0 is an interior point (in Rd−1 ) of the union of two tiles disjoints inmeasure: the fundamental tile and another tile related to b1 ...bk .
Looking at expansions in negative base −β we say that β verifies theproperty F − if all numbers of Z [β] admits a finite −β expansion. We say thatβ verifies the property F −? if there exists a periodic sequence c1 ...cl c1 ...cl ...
such that all numbers of Z [β] admits either a finite −β expansion or an
expansion ending by c1 ...cl c1 ...cl ....
Now consider the periodic -β tiling and the selfsimilar −β tiling of Rd−1 ,who are simultaneously simple or multiple. We prove that
1) If β verifies the property F − then the autosimilar −β tiling is simple
and 0 is an interior point of the fundamental tile of Rd−1 .
2) If β verifies the property F −? then the autosimilar −β tiling is simple
and 0 is an interior point of the union of two tiles of Rd−1 : the fundamental
tile and another tile related to c1 ...cl c1 ...cl .....
Examples: the −β tilings associated with quadratic unimodular numbers
or with Tribonacci number are simple and it is also the case for those of Pisot
number for wich the property F − has been proved.

3

sciencesconf.org:numeration2018:198132

INTEGER MULTIPLIERS OF REAL POLYNOMIALS WITHOUTNONNEGATIVE ROOTSHORST BRUNOTTE

For a polynomial f with real coefficients and positive leading coefficient the quantities
δ(f ) = inf {deg(g) : g ∈ R[X], gf ∈ R>0 [X]}and

δ0 (f ) = inf {deg(g) : g ∈ R[X] \ {0} , gf ∈ R≥0 [X]}have been introduced by J.-P. Borel [1]. It was shown by E. Meissner [4] and A. Durand(see [1, Théorème 2]) that δ(f ) is finite if and only if f does not have a real nonnegative root;
furthermore, δ0 (f ) is finite if and only if f does not have a positive root. Moreover, given apolynomial f ∈ R[X] with positive leading coeffient, but without a real nonnegative root, a monicpolynomial t ∈ R[X] with the properties
tf ∈ R≥0 [X]anddeg(g) = δ0 (f )can effectively be computed; such a polynomial t is sometimes called a δ0 -multiplier of f . The
analogous statement holds for f with positive leading coeffient and without a real positive root.
We refer the reader to [3, 2] where also some more historical comments on theses quantities andtheir relations to algebraic number theory and distribution theory are given.
Having in mind these results, we here consider the set
F = {f ∈ R[X] : f monic and f does not have a root in [0, ∞)} ,and for f ∈ F we ask for the quantities
andTrivially, we haveϕ(f ) = inf {deg(t) : t ∈ Z[X], t monic and tf ∈ R>0 [X]}ϕ0 (f ) = inf {deg(t) : t ∈ Z[X], t monic and tf ∈ R≥0 [X]} .

δ0 (f ) ≤ ϕ0 (f )and
δ(f ) ≤ ϕ(f ) .
We show that monic polynomials s, t ∈ Z[X] with the properties
tf ∈ R≥0 [X]andsf ∈ R>0 [X]

can effectively be computed thereby giving upper bounds for the constants ϕ0 (f ) and ϕ(f ).
References[1] J.-P. Borel, Polynômes à coefficients positifs multiples d’un polynôme donné, in Cinquante ans de polynômes(Paris, 1988), vol. 1415 of Lecture Notes in Math., Springer, Berlin, 1990, pp. 97–115.
[2] H. Brunotte, On expanding real polynomials with a given factor, Publ. Math. Debrecen, 83 (2013), pp. 161–
178.
, Polynomials with nonnegative coefficients and a given factor, Periodica Math. Hung., 66 (2013), pp. 61–[3]72.
[4] E. Meissner, Über positive Darstellungen von Polynomen, Math. Ann., 70 (1911), pp. 223–235.
Haus-Endt-Straße 88, D-40593 Düsseldorf, GERMANY
E-mail address: brunoth@web.de4

sciencesconf.org:numeration2018:195871

On the magic of some families of fractal dendrites
Ligia L. Cristea
Institute for Mathematics and Scientific Computing,
University of Graz, Austria(FWF-project P27050-N26)
Abstract
An n × n pattern is obtained by dividing the unit square into n × n
congruent smaller sub-squares and colouring some of them in black (whichmeans that they will be cut out), and the rest in white.
Sierpiński carpets are planar fractals that originate from the “classical”
Sierpiński carpet. They are constructed in the following way: one starts withthe unit square, divides it into n × n congruent smaller sub-squares and cuts
out m of them, corresponding to a given n×n pattern (also called the generator of the Sierpiński carpet). This construction step is then repeated withall the remaining sub-squares ad infinitum. The resulting object is a selfsimilar fractal of Hausdorff and box-counting dimension log(n2 −m)/ log(n),called a Sierpiński carpet.
By using special patterns, which we called “labyrinth patterns”, wecreate and study a special class of carpets, called labyrinth fractals [1].
Labyrinth fractals are dendrites, i.e., connected and locally connected compact hausdorff spaces that contain no simple curves. Under certain conditions on the patterns one obtains objects with some “magic” properties.
First, we study the self-similar case. Already in this “simplest” case oneneeds results from several areas of mathematics (topology, combinatorics,
linear algebra, curves theory, graph theory) to establish the main results. An
important role is played here by the path matrix of a pattern or a labyrinth
set. This is in fact the matrix of a subsitution and is, for an important classof labyrinth patterns, primitive [2].
As a next step, we introduce and study mixed labyrinth fractals [3],which are not self-similar. It is interesting to see here which properties are
inherited from the self-similar case, and which are not.
The results obtained show how by an appropriate choice of the labyrinth
patterns, one can obtain . . . almost anything [4].

5sciencesconf.org:numeration2018:194330

In very recent research [5] we study an even more general class, calledsupermixed labyrinth fractals, and solve a conjecture on mixed labyrinth
fractals. Every time we pass to a more general class, it was necessary to
introduce new objects and tools and use new techniques for our proofs.
Wild labyrinth fractals are a further generalisation . . .
It is worth mentioning that some of our results on labyrinth fractals havealready been used by physicists in their research and construction of prototypes. Moreover, we are aware that these objects are suitable as future
models for certain crystals, as other recent research in physics shows.
The results stem from joint work with Bertran Steinsky and GuntherLeobacher.

References[1] L. L. Cristea, B. Steinsky, Curves of Infinite Length in 4 × 4-Labyrinth
Fractals, Geometriae Dedicata, Vol. 141, Issue 1 (2009), 1–17
[2] L. L. Cristea, B. Steinsky, Curves of Infinite Length in LabyrinthFractals, Proceedings of the Edinburgh Mathematical Society Volume
54, Issue 02 (2011), 329–344[3] L. L. Cristea, B. Steinsky, Mixed labyrinth fractals, Topol. Appl.(2017),
http://dx.doi.org/10.1016/jtopol2017.06.022[4] L. L. Cristea, G. Leobacher, On the length of arcs in labyrinth fractals,
Monatshefte für Mathematik (2017), doi:10.1007/s00605-017-1056-8[5] L. L. Cristea, G. Leobacher, Supermixed labyrinth fractals, manuscript
submitted for publication (2018)6

sciencesconf.org:numeration2018:194330

MULTIPLICATIVE DEPENDENCE OF SHIFTEDALGEBRAIC NUMBERS
ARTŪRAS DUBICKAS

Given n ≥ 2 non-zero complex numbers z1 , z2 , . . . , zn , we say thatthey are multiplicatively dependent if there exists a non-zero integer
vector (k1 , k2 , . . . , kn ) ∈ Zn for which
z1k1 z2k2 · · · znkn = 1.
Otherwise (if there is no such non-zero integer vector (k1 , k2 , . . . , kn )),we say that the numbers z1 , z2 , . . . , zn are multiplicatively independent.
Let α1 , α2 , . . . , αn be n pairwise distinct algebraic numbers. In [1],we show that the numbers
α1 + t, α2 + t, . . . , αn + t
are multiplicatively independent for all sufficiently large positive integers t. More generally,
Theorem 1. Let α1 , α2 , . . . , αn be pairwise distinct algebraic numbers,
and let d = [Q(α1 , α2 , . . . , αn ) : Q]. Then, there is a positive constant
C = C(n, α1 , α2 , . . . , αn ) such that, for any algebraic integer t of degree
1/(nd+1)

at most |t|, where |t| ≥ C (here |t| is the largest modulus of the
conjugates of t over Q), the algebraic numbers α1 + t, α2 + t, . . . , αn + t
are multiplicatively independent.
A more general approach, with rational functions instead of translations αi + t, has been considered in [2].
In [1], for a pair (a, b) of distinct integers a < b, we also study how
many pairs (a + t, b + t) are multiplicatively dependent when t runs
through the set integers Z. Assuming the ABC conjecture, we showthat there exists a constant C0 such that for any pair (a, b) ∈ Z2 , a < b,there are at most C0 values of t ∈ Z for which the pairs (a + t, b + t) are
multiplicatively dependent. (Without ABC, the bound on the numberof such t ∈ Z depends on the number of distinct prime divisors of b−a.)2010 Mathematics Subject Classification. 11N25, 11R04, 11D61.
Key words and phrases. Multiplicative dependence, multiplicative independence,
Pillai’s equation, ABC conjecture.

7

sciencesconf.org:numeration2018:195668

For a pair (a, b) ∈ Z2 with difference b − a = 30, we show that there
are 13 values of t ∈ Z for which the pairs (a+t, b+t) are multiplicatively
dependent, namely,(−15, 15), (−1, 29), (−29, 1), (1, 31), (−31, −1), (−5, 25), (−25, 5),(−3, 27), (−27, 3), (2, 32), (−32, −2), (6, 36), (−36, −6).

We conjecture that 13 is the largest number of such translations forany such pair (a, b) ∈ Z2 , a < b, and that the number 13 is attained
only when the difference b − a equals 30. This was proved for all pairs(a, b) with difference at most 1010 .
This research was funded by the European Social Fund according to
the activity Improvement of researchers qualification by implementing
world-class R&D projects of Measure No. 09.3.3-LMT-K-712-01-0037.
References[1] A. Dubickas and M. Sha, Multiplicative dependence and independence ofthe translations of algebraic numbers, Revista Matematica Iberoamericana,(to appear).
[2] A. Ostafe, M. Sha, I. E. Shparlinski and U. Zannier, On multiplicative dependence of values of rational functions, preprint at arXiv:1706.05874,
2017, 26 pp.
Institute of Mathematics, Department of Mathematics and Informatics, Vilnius University, Naugarduko 24, LT-03225 Vilnius, Lithuania
E-mail address: arturas.dubickas@mif.vu.lt

8

sciencesconf.org:numeration2018:195668

Representations of palindromes in the Fibonacci
word
Anna E. Frid

Abstract
We continue our study of palindromes in Sturmian words in termsof Ostrowski representations of their ends. In the previous preprint,
we used the link between them to prove that every Sturmian wordwith an unbounded directive sequence contains a factor which cannot
be decomposed to a concatenation of a given number of palindromes.
However, for the case of bounded directive sequence, the only existing proof of this property is still the non-constructive one dated 2013.
So, in this study we start considering in detail palindromes in the
Fibonacci word in terms of the (Lekkerkerker-)Zeckendorf representations of their ends. In particular, we prove an upper bound for thenumber of palindromes necessary to construct the Fibonacci prefix oflength n and conjecture which prefixes are the shortest with a given
number of palindromes.

The palindromic length of a finite word u is the minimal number Q of
palindromes P1 , . . . , PQ such that u = P1 · · · PQ .
Conjecture 1. In every infinite word which is not ultimately periodic, thepalindromic length of factors is unbounded.
The conjecture was stated in 2013 by Puzynina, Zamboni and the author[5] and was proved in the same paper for the case when the infinite word is
k-power-free for some k. To prove the conjecture at least for Sturmian words
which are not k-power-free, in the previous paper [4] the author managed
to express an occurrence of a palindrome in a characteristic Sturmian wordin terms of the Ostrowski representations of its ends. The first result of thisabstract is a new, simplified and updated, version of the respective theorem,
which we will formulate after introducing the notation.
As usual, we use in this paper the classical construction of characteristic
Sturmian words related to a directive sequence (d0 , d1 , . . . , dn , . . .), where9

sciencesconf.org:numeration2018:196004

di ≥ 1. Given a directive sequence, the standard sequence (sn ) of words on
the binary alphabet {a, b} is defined as follows:
s−1 = b, s0 = a, sn+1 = sdnn sn−1 for all n ≥ 0.

(1)

The word sn is called also the standard word of order n. The infinite word
w = limn→∞ sn is called a characteristic Sturmian word associated with asequence (di ).
Note that to get all possible Sturmian words, we also need to allow
d0 = 0, but due to the symmetry between a and b, we can restrict ourselvesto the case of d1 > 0.
Denote the length of sn by qn ; then, clearly,
q−1 = q0 = 1, qn+1 = dn qn + qn−1 for all n ≥ 0.
In the Ostrowski numeration system [7] associated with the sequence (di ), a
non-negative integer N < qj+1 is represented as∑N=
k i qi ,(2)0≤i≤nwhere 0 ≤ ki ≤ di for i ≥ 0, and for i ≥ 1, if ki = di , then ki−1 = 0. Such a
representation of N is unique up to leading zeros; we use the notation N =kn · · · k1 k0 [o]. Everywhere in the text, we will not distinguish representations
which diﬀer only by leading zeros.
In many cases, including∑ ours, it is reasonable to consider more general
legal decompositions N = 0≤i≤n ki qi , where 0 ≤ ki ≤ di for i ≥ 0 (but thesecond restriction from the definition of the Ostrowski representation is not
imposed). A number can admit several legal representations, including theOstrowski one. A legal representation of N is denoted by N = kn · · · k1 k0(without [o] at the end, reserved for the Ostrowski version).
kn−1
Proposition 1. [4] For all k0 , . . . , kn such that ki ≤ di , the word sknn sn−1
· · · sk00
is a prefix of w.

The following statement is an updated and simplified version of Theorem
2 from [4].
Theorem 1. Let w be a characteristic Sturmian word corresponding to thedirective sequence (dn ), and w(i..j] = w[i + 1] . . . w[j] be a palindrome. Denote the Ostrowski representation of i as i = xn · · · xm · · · x0 [o]; note that it

10

sciencesconf.org:numeration2018:196004

may start with several leading zeros. Then there exist a legal representationof j given by
j = xn · · · xm+1 ym · (dm−1 − xm−1 ) · · · (d0 − x0 ),where 0 ≤ m ≤ n and xm < ym ≤ dm .
As a classical example, consider the directive sequence (1, 1, 1, . . .). It
corresponds to the famous Fibonacci word defined by its prefixes s0 = a,s1 = s0 s−1 = ab, s2 = s1 s0 = aba, s3 = s2 s1 = abaab, etc.:
w = abaababaabaababaababa · · · .
The lengths qi = |si | are Fibonacci numbers, and the respective numeration
system is the Fibonacci, or Zeckendorf, one [6, 8]: it corresponds to thegreedy decomposition of a number N to a sum of Fibonacci numbers Fn ,starting from F0 = 1, F1 = 2.
Consider the palindrome w(12..13] = w[13] = b in the Fibonacci word.
The Ostrowski representation of 12 is 12 = 10101[o]. Taking m = 1 andapplying the procedure from the previous theorem, we increase the second-to
last symbol of the representation from 0 to 1 (this is the only possible option
in the Fibonacci case) and invert the last symbol. So, get the representation
10110 = 13 = 100000[o].
For the palindrome w(5, 14] = abaabaaba, we take the Ostrowski representation of 5 with a leading zero: 5 = 1000[o] = 01000[o]. Now we add 1 tothe first zero of this long representation and invert everything which follows.
It gives the representation 10111 = 100001[o] = 14.
The following statement is partially obtained by a computer case study.
Proposition 2. The smallest lengths of prefixes of the Fibonacci word notdecomposable as a concatenation of K palindromes, K = 1, . . . , 6, are, in
the Ostrowski representation, respectively 10 = 2, 10001 = 9, 100001010,
100100010001, 100010001000010, 100100100100100101.
Note that the same result had been already known to Bucci and Richomme in 2016 [2]. However, more data we got with this Ostrowski technique allows to prove by induction at least one infinite statement on thepalindromic length of prefixes of the Fibonacci word.
Proposition 3. For every k ≥ 3, all prefixes of the Fibonacci word of length
smaller than (100)2k−1 101 can be decomposed as a concatenation of at most
2k palindromes.

11sciencesconf.org:numeration2018:196004

The result would be complete if we manage to prove the following conjecture.
Conjecture 2. For every k ≥ 1, the prefix of the Fibonacci word of length(100)2k−1 101 cannot be decomposed as a concatenation of at most 2k palindromes.
We proved that 2k + 1 palindromes are enough for this word, so, itremains just to prove that this is the minimal possible value.
The analogous conjecture for the odd number 2k + 1 of palindromes willprobably mention the critical length (100)2k 010 starting from some k.

References[1] J. Berstel. An exercise on Fibonacci representations. Theor. Inform.
Appl. 35 (2002) 491–498.
[2] M. Bucci,
G. Richomme.
arXiv:1606.05660, 2016.

Greedypalindromic

lengths,[3] C. Epifanio, C. Frougny, A. Gabriele, F. Mignosi, J. Shallit. Sturmian
graphs and integer representations over numeration systems. DiscreteAppl. Math. 160 (2012) 536–547.
[4] A. Frid, Sturmian numeration systems and decompositions to palindromes. https://arxiv.org/abs/1710.11553.
[5] A. Frid, S. Puzynina, L. Zamboni. On palindromic factorization ofwords. Advances in Appl. Math. 50 (2013) 737–748.
[6] C. G. Lekkerkerker. Voorstelling van natuurlijke getallen door een som
van getallen van Fibonacci. Simon Stevin 29 (1952) 190–195.
[7] A. Ostrowski. Bemerkungen zur Theorie der diophantischen Approximationen. Hamb. Abh. 1 (1921) 77–98.
[8] E. Zeckendorf. Représentation des nombres naturels par une somme denombres de Fibonacci ou de nombres de Lucas. Bull. Soc. R. Sci. Liège
41 (1972) 179–182.

12

sciencesconf.org:numeration2018:196004

RANDOM HOMOGENEOUS BETA-EXPANSIONS AND
SELF-SIMILAR MEASURESKEVIN G. HAREThis talk will discuss joint work with Kathryn Hare and Sascha Troscheit. Letβ ∈ (1, 2) and consider the expansion∞Xx=
aj β −jj=1

where aj ∈ {0, 1}. Then a1 a2 a3 · · · is a beta-expansion for x. Beta-expansions, andtheir associated self-similar measures are well studied within the literature.
In this talk we consider a variation of the classical beta-expansion, one that is
random homogeneous. As a simple example, let S1 and S2 be finite sets. Consider
the set K of all x such that
∞
X
(i)
x=
aj β −jj=1(i)where aj ∈ Sbi

where the bi are choosen randomly from {1, 2}. We see that if
aj = 1 for all j then K would be the set of allowable beta expansions with digit set
S1 . Similarly if aj = 2 for all j, then K would be based on digit set S2 . As we arechoosing aj randomly, this is a hybrid between the two types of beta-expansions.
Then we investigate various almost sure properties of K.

13

sciencesconf.org:numeration2018:195836

TOTALLY POSITIVE QUADRATIC INTEGERS
AND NUMERATION
TOMÁŠ HEJDA AND VÍTĚZSLAV KALA√
Abstract. Let K = Q( D) be a real quadratic field. We obtain a presen+tation of the additive semigroup OK(+) of totally positive integers in K; its
generators (indecomposable integers) and relations
can be nicely described in√terms of the periodic continued fraction for D. We also characterize all
uniquely decomposable integers in K. In these results, we make use of an
integer numeration system we construct on OK .

1. Introduction+
The additive semigroup of totally positive integers OK
in a totally real number
field K has long played a fundamental role in algebraic number theory, even thoughmore attention has perhaps been paid to the multiplicative structure of the ring
OK , for example, to its units and unique factorization into primes. Most prominent
purely additive objects are the indecomposable elements, i.e., totally positive inte+
gers α ∈ OK
that cannot be decomposed into a sum α = β + γ of totally positive+
integers β, γ ∈ OK.
√
In the real quadratic case K = Q( D), indecomposables can√ be nicely characterized in terms of continued fraction (semi-)convergents to D. This stands incontrast to the situation of a general totally real field K, where it is much harder todescribe indecomposables: Brunotte [Bru83] proved an upper bound on their normin terms of the regulator, but otherwise their structure remains quite mysterious.
The goal of this work is to study the structure of the whole additive semigroup+
OK(+). This is an interesting problem in itself, but it seems also necessary forcertain applications (such as the recent progress in the study of universal quadratic
forms and lattices over K by Kim, Blomer, Yatsyna, and the second author [BK15,
BK17, Kal16, KY17, Kim00]).
+
In particular, as indecomposable elements are precisely the generators of OK(+),
we need to determine the relations between them. While the description of indecomposables in terms of the continued fraction is fairly straightforward, it is a priori
not clear at all if the same will be the case for relations, as there could be some“random” or “accidental” ones. Perhaps surprisingly, it turns out that this is not+
the case and that the presentation of the semigroup OK(+) (given in Theorem 1)
is quite elegant. A key tool in the proof of the presentation is the fact that eachtotally positive integer can be uniquely written as a Z+ -linear combination of twoconsecutive indecomposables (Proposition 2).

2010 Mathematics Subject Classification. 11R11, 11A55, 20M05.
Key words and phrases. Real quadratic number field, semigroup of totally positive integers,
continued fraction, additively indecomposable integer.
Both authors acknowledge support by Czech Science Foundation (GAČR) grant 17-04703Y.

14

sciencesconf.org:numeration2018:195997

We also manage to find a basis, alphabet and forbidden strings for a numeration+
system on OK
and show some of its properties (§ 4). This numeration systemnaturally generalizes integer numeration systems (see, e.g., [Ost22, Zec72, Fro92,
GT91]) from K = Q to real quadratic fields; the price is that the base becomes abi-infinite sequence, namely it is the indecomposables that will play the role of thebasis.
One of course cannot hope to have an analogue of unique factorization in the
additive setting, but nevertheless, some elements can be uniquely decomposed asa sum of indecomposables. In Theorem 6 we characterize all such uniquely decomposable elements and obtain again a very explicit result depending only on the+continued fraction. This then yields directly Corollary 7 that OK(+) (viewed as an
abstract semigroup) completely determines D and the number field K.
2. Preliminaries
Throughout the work, we will use the following notation. √We fix a squarefree
integer D ≥ 2 and consider the real quadratic field K = Q( D) and its ring ofintegers OK ; we know that {1, ωD } forms an integral basis of OK , where(√D
if D ≡ 2, 3 (mod 4),
ωD := 1+√D
if D ≡ 1 (mod 4).
2

By ∆ we denote the discriminant of K, i.e., ∆ = 4D if D ≡ 2, 3 (mod 4) and ∆ = D
otherwise. The norm and trace from K to Q are denoted by N and Tr, respectively.
An algebraic integer α ∈ OK is totally positive iff α > 0 and α0 > 0, where α0 is
the Galois conjugate of α, we write this fact as α  0; for α, β ∈ OK we denote by+α  β the fact that α − β  0, and by OK
the set of all totally positive integers.
+
We say that α ∈ OK is indecomposable iff it can not be written as a sum of two+
totally positive integers or equivalently iff there is no algebraic integer β ∈ OK
such+that α  β. We say that α ∈ OK is uniquely decomposable iff there is a unique
way how to express it as a sum of indecomposable elements.
It will be slightly more convenient for us to work with a purely periodic continued fraction, and so let σD = [u0 , u1 , . . . , us−1 ] be the periodic continued fraction
expansion of(√√
D + b Dc
if D ≡ 2, 3 (mod 4),0
σD := ωD + b−ωD c = 1+√D  −1+√D +
if D ≡ 1 (mod 4)22(with positive integers ui ). We then have that ωD = du0 /2e, u1 , . . . , us . It is wellknown that u1 , u2 , . . . , us−1 is a palindrome and that u0 = us is even if and only if
D ≡ 2, 3 mod 4, hence du0 /2e = (us + Tr(ωD))/2.

Denote the convergents to ωD by pi /qi := du0 /2e, u1 , . . . , ui and recall that thesequences (pi ), (qi ) satisfy the recurrence(1)

Xi+2 = ui+2 Xi+1 + Xi

for i ≥ −1with the initial condition q−1 = 0, p−1 = q0 = 1, and p0 = du0 /2e. Denote0αi := pi − qi ωDand αi,r = αi + rαi+1 . Then we have the following classical facts(see, e.g., [DS82, Per13]):• The sequence (αi ) satisfies the recurrence (1).
• αi  0 if and only if i ≥ −1 is odd.

15

sciencesconf.org:numeration2018:195997

+• The indecomposable elements in OK
are αi,r with odd i ≥ −1 and 0 ≤ r ≤ui+2 − 1, together with their conjugates.
• We have that αi,ui+2 = αi+2,0 .
• The indecomposables αi,r are increasing with increasing (i, r) (in the lexicographic sense).
0
are decreasing with increasing (i, r).
• The indecomposables αi,rWe also denote ε > 1 the fundamental unit of OK ; we have that ε = αs−1 .
Furthermore, we denote ε+ > 1 the smallest totally positive unit > 1; we have thatε+ = ε if s is even and ε+ = ε2 = α2s−1 if s is odd. Furthermore, we denote γ0 = ωD1
< ui + 1
and γi = [ui , ui+1 , ui+2 , . . . ] for i ≥ 1; we have that ui < γi = ui + γi+1
for i ≥ 1.
+
3. Presentation of the semigroup OK(+)

In this section we will prove the following theorem that gives a presentation of+
the semigroup OK(+). We recall that hS | Ri is a presentation of a semigroup
G(+) iff G is generated by S and all (additive) relations between elements of S are
generated by the relations in R.
+
Theorem 1. The additive semigroup OK(+) is presented by+OK= A ∪ A0 ∪ {1} R, R0 , R0 ,where A := { αi,r : i ≥ −1 odd and 0 ≤ r ≤ ui+2 − 1 }\{1} are the indecomposable
elements > 1, A0 := { y 0 : y ∈ A }, and the relations are the following:(2)

R : αi,r−1 − 2αi,r + αi,r+1 = 0

for oddαi−2,ui −1 − (ui+1 + 2)αi,0 + αi,1 = 0

i ≥ −1 and 1 ≤ r ≤ ui+2 − 1,for oddi ≥ 1;

R : same relations as in R after applying the isomorphism (0 );00R0 : α−1,1− (u0 + 2) · 1 + α−1,1 = 0.

For convenience, we introduce an alternative notation of the indecomposables.
We define βj , j ∈ Z by the condition that · · · < β−3 < β−2 < β−1 < β0 = 1 < β1 <β2 < β3 < · · · is the increasing sequence of the indecomposables. Note that wehave βj0 = β−j for all j ∈ Z. Using this notation, we can rewrite the relations (2)in a unified way in terms of βj and certain constants vj as follows:(3)

R, R0 , R0 : βj−1 − vj βj + βj+1 = 0 for j ∈ Z.

Note that the given set of relations is minimal in the sense that none of them canbe removed.
In order to prove the previous theorem, we provide a way of expressing totally
positive integers as sums of indecomposables: A variant of this concerning sums of
powers of units was used by Kim, Blomer, and the second author [BK17, Kim00]
in the construction of universal quadratic forms.
+
Proposition 2. Let x ∈ OK
. Then there exist unique j0 , e, f ∈ Z with e ≥ 1 andf ≥ 0 such that x = eβj0 + f βj0 +1 ;+4. Numeration system on OK

The numeration system we are about to define resembles the Ostrowski numeration systems and is its generalization onto integer rings other than Z.

16

sciencesconf.org:numeration2018:195997

P+
Proposition 3. The map (lj )j∈Z 7→ j∈Z lj βj is a bijection L → OK
, where L isthe set of sequences (lj )j∈Z satisfying the following:• lj ∈ Z and only finitely many lj ’s are non-zero;• 0 ≤ lj ≤ vj − 1 for all j ∈ Z;
• for all j, J ∈ Z, j ≤ J − 1 we have that (lj , lj+1 , . . . , lJ ) 6= (vj − 1, vj+1 −2, vj+2 − 2, . . . , vJ−2 − 2, vJ−1 − 2, vJ − 1).
We will call the sequence (lj )j∈Z ∈ L the greedy expansion of x. It also satisfies
the following:+
Theorem 4.
(1) The greedy expansion of x ∈ OK
is obtained by the usual
greedy algorithm, where the seqence (β
)
is
taken
as the base.
j
j∈Z
P
+
(2) Suppose x ∈ OK
is a finite sum x = j∈Z kj βj with integers kj ≥ 0. Thenthe greedy expansion of x is obtained by repeated applying of the relations (3)on this sum at any position with kj ≥ vj as long as such a position exists;
this process is terminated.
+(3) A sequence (lj )j∈Z is the greedy expansion of x ∈ OK
if and only if (l−j )j∈Z+
0
is the greedy expansion of x ∈ OK .
+5. Uniquely decomposable elements of OK

The greedy expansions allow us to describe all uniquely decomposable elements
+
of OK
:

+
Proposition 5. A number x ∈ OK
is uniquely decomposable if and only if its
greedy expansion (lj )j∈Z is of length one or two, i.e., if there exists j0 such thatlj = 0 for all j 6= j0 , j0 + 1.

From this, we can list them explicitly:+
Theorem 6. All uniquely decomposable elements x ∈ OK
are the following:(a) αi,r with odd i ≥ −1 and 0 ≤ r ≤ ui+2 − 1;(b) eαi,0 with odd i ≥ −1 and with 2 ≤ e ≤ ui+1 + 1(c) αi,ui+2 −1 + f αi+2,0 with odd i ≥ −1 odd such that ui+2 ≥ 2 and with1 ≤ f ≤ ui+3 ;(d) eαi,0 + αi,1 with odd i ≥ −1 such that ui+2 ≥ 2 and with 1 ≤ e ≤ ui+1 ;(e) eαi,0 +f αi+2,0 with odd i ≥ −1 such that ui+2 = 1 and with 1 ≤ e ≤ ui+1 +1,
1 ≤ f ≤ ui+3 + 1, (e, f ) 6= (ui+1 + 1, ui+3 + 1);(f) Galois conjugates of all of the above.
+
Corollary 7. The additive semigroups OK, for real quadratic fields K, are pairwise
not isomorphic.

References[BK15] Valentin Blomer and Vítězslav Kala, Number fields without n-ary universal quadratic
forms, Math. Proc. Cambridge Philos. Soc. 159 (2015), no. 2, 239–252.
[BK17], On the rank of universal quadratic forms over real quadratic fields, 2017, Doc.
Math, to appear, 17 pp., arXiv:1705.03671.
[Bru83] Horst Brunotte, Zur Zerlegung totalpositiver Zahlen in Ordnungen totalreeller algebraischer Zahlkörper [On the decomposition of totally positive numbers in orders of totallyreal algebraic number fields], Arch. Math. (Basel) 41 (1983), no. 6, 502–503, (in German).
[DS82] Andreas Dress and Rudolf Scharlau, Indecomposable totally positive numbers in real
quadratic orders, J. Number Theory 14 (1982), no. 3, 292–306.

17sciencesconf.org:numeration2018:195997

[Fro92] Christiane Frougny, Representations of numbers and finite automata, Math. Systems
Theory 25 (1992), no. 1, 37–60.
[GT91] Peter J. Grabner and Robert F. Tichy, α-expansions, linear recurrences, and the sumof-digits function, Manuscripta Math. 70 (1991), no. 3, 311–324.
[Kal16] Vítězslav Kala, Universal quadratic forms and elements of small norm in real quadratic
fields, Bull. Aust. Math. Soc. 94 (2016), no. 1, 7–14.
[Kim00] Byeong Moon Kim, Universal octonary diagonal forms over some real quadratic fields,
Comment. Math. Helv. 75 (2000), no. 3, 410–414.
[KY17] Vítězslav Kala and Pavlo Yatsyna, On sums of squares in number fields, 2017, in preparation.
[Ost22] Alexander Ostrowski, Bemerkungen zur Theorie der Diophantischen Approximationen[Note on the theory of Diophantine approximation], Abh. Math. Sem. Univ. Hamburg 1(1922), no. 1, 77–98, (in German).
[Per13] Oskar Perron, Die lehre von den Kettenbrüchen [The theory of continued fractions], Firsted., B. G. Teubner Verlag, 1913, (in German).
[Zec72] Édouard Zeckendorf, Représentation des nombres naturels par une somme de nombresde Fibonacci ou de nombres de Lucas [Representation of natural numbers by a sum ofFibonacci or Lucas numbers], Bull. Soc. Roy. Sci. Liège 41 (1972), 179–182, (in French).
Charles University, Faculty of Mathematics and Physics, Department of Algebra,
Sokolovská 83, 18600 Praha 8, Czech Republic
University of Chemistry and Technology, Prague, Department of Mathematics, Studentská 6, 16000 Praha 6, Czech Republic
E-mail address: tohecz@gmail.com
Charles University, Faculty of Mathematics and Physics, Department of Algebra,
Sokolovská 83, 18600 Praha 8, Czech Republic
University of Göttingen, Mathematisches Institut, Bunsenstr. 3–5, D-37073 Göttingen, Germany
E-mail address: vita.kala@gmail.com

18

sciencesconf.org:numeration2018:195997

Toolset for supporting the number system
researchPé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, computer
experiments are able to support the theoretical research. In this talk we introduce a
new toolset that helps to analyze number systems in lattices. The toolset is able to• Analyze the expansions;• Decide the number system property;• Classify and visualize the periodic points;• Calculate correlations between system data, etc.

In this talk we present an introductory usage of the toolset.

1 Extended abstract
1.1 Introduction
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. 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
EFOP-3.6.3-VEKOP-16-2017-00001: Talent Management in Autonomous Vehicle Control Technologies - The Project is supported by the Hungarian Government and co-financed by the European
Social Fund.

19

sciencesconf.org:numeration2018:195998

L

x = ∑ M i di ,i=0where di ∈ D and L ∈ N.
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
system at the same time. If we change the basis in Λ a similar integer matrix can beobtained, hence, no loss of generality in assuming that M is integral acting on thelattice 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. 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 fulfils 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), . . .
is eventually periodic for all x ∈ Λ . Clearly, (Λ , M, D) is a number system iff forevery x ∈ Λ 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 allperiodic points is denoted by P. The signature (l1 , l2 , . . . , lω ) of a radix system is a
finite sequence of non-negative integers in which the periodic structure P consistsof #li cycles with period length i (1 ≤ i ≤ ω).
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.
The algorithmic complexity of the decision and classification problems is still
unknown.

20

sciencesconf.org:numeration2018:195998

1.2 The toolset
We implemented a python based system that contain the following:• Base features of number systems (addition, multiplication);• Procedures for the decision and the classification problems;• Visualization for structure analysis, fractions, etc.
• Different optimization algorithms, etc.

Moreover, in order to support the research we implemented a serves-side application which is able to store various data on predefined systems. The database alreadycontains more than 10 000 candidates of the following type:• Special bases (companions of expansive polynomials with constant terms ±2,±3,±5,±7) with canonical, shifted canonical, symmetric digit sets.
• Product systems.
The data server allows to read the data from the server publicly via a JSON API.
The registered users with API token can send new properties also to the databaseand store them in a flexible way. The server already stores plenty of properties, forexample• Eigenvalues, eigenvectors,• Periodic points and orbits,• Classification details.

In this talk we present an introductory usage of the toolset.

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., On number expansions in lattices, Math. and Comp. Modelling, 38, (2003), 909–
915.
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.
4. Hudoba, P., Kovács, A., Some improvements on number expansion computations, Annales Univ.
Sci. Budapest, Sect. Comp., 46, (2017), 81–96.

21

sciencesconf.org:numeration2018:195998

Characterization of rational matrices that admit
finite digit representations
J. Jankauskas and J. M. Thuswaldner

Abstract Let A be an n × n matrix with rational entries and let
Zn [A] :=∞ [

Zn + AZn + . . . + Ak−1 Zn

k=1be the minimal A-invariant Z-module containing the lattice Zn . If D ⊂ Zn [A] is a
finite set we call the pair (A, D) a digit system. We say that (A, D) has the finitenessproperty if each z ∈ Zn [A] can be written in the formz = d0 + Ad1 + . . . + Ak dk ,with k ∈ N and digits d j ∈ D for 0 ≤ j ≤ k. We prove that for a given matrix A ∈Mn (Q) there is a finite set D ⊂ Zn [A] such that (A, D) has the finiteness property
if and only if A has no eigenvalue of absolute value < 1. This result is the matrix
analogue of the height reducing property of algebraic numbers. In proving this result
we also characterize integer polynomials P ∈ Z[x] that admit digit systems having
the finiteness property in the quotient ring Z[x]/(P).

J. Jankauskas
Mathematik und Statistik, Montanuniversität Leoben, Franz Josef Straße 18, A-8700 Leoben, Austria, e-mail: jonas.jankauskas@gmail.com
J. M. Thuswaldner
Mathematik und Statistik, Montanuniversität Leoben, Franz Josef Straße 18, A-8700 Leoben, Austria, e-mail: joerg.thuswaldner@unileoben.ac.at22

sciencesconf.org:numeration2018:199353

UNIQUE EXPANSIONS ON FAT SIERPINSKI GASKETSDERONG KONG AND WENXIA LI

Abstract. Given β ∈ (1, 2), the fat Sierpinski gasket Sβ is defined by
(∞
)
X di
Sβ :=
: di ∈ {(0, 0), (1, 0), (0, 1)} for all i ≥ 1 .
βi
i=1

Let Uβ be the set of points in Sβ having a unique β-expansion with respect to the alphabet{(0, 0), (1, 0), (0, 1)}. In this paper we give a lexicographical characterization of Uβ , anddetermine the critical base βc ≈ 1.55263 such that Uβ has positive Hausdorff dimension
if and only if β > βc . We show that βc is transcendental and is defined in terms of amodified Thue-Morse sequence. When β = βc , the univoque set Uβ is uncountable but has
zero Hausdorff dimension. When β < βc , the univoque set Uβ is at most countable. This
generalizes the one dimensional result of Glendinning and Sidorov (2001) for the uniqueβ-expansions to the fat Sierpinski gaskets.

(D. Kong) Mathematical Institute, University of Leiden, PO Box 9512, 2300 RA Leiden, The
Netherlands
E-mail address: d.kong@math.leidenuniv.nl(W. Li) Department of Mathematics, Shanghai Key Laboratory of PMMP, East China Normal
University, Shanghai 200062, People’s Republic of China
E-mail address: wxli@math.ecnu.edu.cn

2010 Mathematics Subject Classification. Primary:11A63, Secondary: 37B10, 28A78.

23

sciencesconf.org:numeration2018:194134

Multi-base Representations
and their
Minimal Hamming Weight
Daniel Krenn∗

Vorapong Suppakitpaisarn†
Stephan Wagner‡

Given a finite set of bases b1 , b2 , . . . , br (integers greater than 1), a multi-base representation uses, in analogy to a standard base-b representation, all numbers in theset
B = {bα1 1 bα2 2 · · · bαr r | α1 , α2 , . . . , αr ∈ N0 }.
More precisely, a multi-base representation of a positive integer n is a representation of
the form
X
n=
dB B,
(1)
B∈B

where the digits dB are taken from a fixed finite set containing 0. Note that we obtainthe standard base-b representation if r = 1, b1 = b and D = {0, 1, . . . , b − 1}.
The Hamming weight of a representation (1) is the number of nonzero terms in thesum. The Hamming weight is a measure of how efficient a certain representation is.
The Hamming weight of single-base representations has been thoroughly studied,not only in the case of the standard set {0, 1, . . . , b − 1} of digits, but also for moregeneral types of digit sets. Both the worst case (maximum) and the average order ofmagnitude of the Hamming weight are log n. We investigate the Hamming weight ofmulti-base representations; it can be reduced—even in the worst case—by using multibase representations, albeit only by a small amount. Perhaps surprisingly, the order ofmagnitude is independent of r (provided only that r ≥ 2), the set of bases and the set of
digits: it is always log n/(log log n).
We present the following theorem:

daniel.krenn@aau.at, Alpen-Adria-Universität Klagenfurt, Austria. Daniel Krenn is supported by
the Austrian Science Fund (FWF): P 28466-N35.
†
vorapong@is.s.u-tokyo.ac.jp, The University of Tokyo, Japan.
‡
swagner@sun.ac.za, Stellenbosch University, South Africa.

∗

24

sciencesconf.org:numeration2018:195727

Theorem. Suppose that r ≥ 2, and that the multiplicatively independent bases b1 , b2 ,. . . , br and the digit set are such that every positive integer n has a representation of theform (1). There exist two positive constants K1 and K2 depending on the bases and thedigit set such that the following hold:(U) For all integers n > 2, there exists a representation of the form (1) with Hamming
weight at most K1 logloglogn n .
(L) For infinitely many positive integers n, there is no representation of the form (1)whose Hamming weight is less than K2 logloglogn n .
The upper bound (U) was shown by Dimitrov, Jullien and Miller [1] in the case that theb1 , b2 , . . . , br are distinct primes. The proof is based on an analysis of the natural greedy
algorithm and based on a results by Tijdeman [2] from Diophantine approximation. We
present a variant of this proof under the slightly more general condition that the bases b1 ,b2 , . . . , br are multiplicatively independent.
The lower bound (L) showing that the order of the Greedy algorithm is best possible—
therefore showing that the minimal Hamming weight admits the same order—is based ona counting argument. In the talk, the details will be revealed. An alternative approach
using communication complexity will also be discussed.

References[1] V. S. Dimitrov, G. A. Jullien, and W. C. Miller, An algorithm for modular exponentiation, Inform. Process. Lett. 66 (1998), no. 3, 155–159. MR MR1627991(99d:94023)[2] Robert Tijdeman, On the maximal distance between integers composed of small primes,
Compositio Math. 28 (1974), 159–162. MR 0345917

25

sciencesconf.org:numeration2018:195727

Infinite families of number systems
Jakub Krásenský and Attila Kovács

Abstract In the context of number systems in lattices, we find a broad class ofradices such that for every one of them there exists an infinite family of digit sets
where the digits get arbitrarily far away from the origin.

1 Extended abstract
The concept of number systems in lattices, pioneered by Vince [5], is a straightforward generalization of number systems in the ring of integers of a given algebraic number field. The systematic research was initiated by Kátai and continued by
Gilbert, B. Kovács and Pethő. Since every lattice can be transformed into Zd by abasis transformation, we develop our notions in the convenient setting of an integer
lattice.
Let a regular matrix (radix) L ∈ Zd×d and a finite set of digits 0 ∈ D ⊂ Zd be
given. The pair (L, D) is called a number system (GNS) in Zd if every non-zeroelement z ∈ Zd has a unique representation of the formNz = ∑ Lk ak ,k=0

where N ∈ N0 , ak ∈ D, aN 6= 0.

The necessary conditions for (L, D) being a number system is that D must be acomplete residue system modulo L, the radix L must be expansive (i.e. ρ(L−1 ) < 1)
and the “unit condition” det(L−I) 6= ±1 must be satisfied. Also, for any given (L, D)
there are algorithms to decide whether it is a GNS or not, however, with unknown
algorithmic complexity.
Jakub Krásenský
Czech Technical University in Prague, Czech Republic, e-mail: krasejak@fjfi.cvut.cz
Attila Kovács
Eötvös Loránd University, Budapest, Hungary, e-mail: attila.kovacs@inf.elte.hu

26sciencesconf.org:numeration2018:195958

The main question is giving sufficient conditions on the operator L such that there
exists at least one GNS with this radix. In special cases of quadratic number fields
this problem was examined e.g. by Steidl [4] and Kátai [2]. The following theorem
generalizes the previous result [1]:Theorem 1 (Germán, Kovács). If for L ∈ Zd×d the spectral radius of its inverse
satisfies ρ(L−1 ) < 1/2, then there always exists a digit set D such that (L, D) is a
GNS in Zd .
The suitable digit set can be found as follows: take any vector norm on Rd such thatthe induced matrix norm satisfies kL−1 k < 1/2. Then we create the so-called dense
digit set by taking the smallest representative (with respect to this norm) from eachcongruence class modulo L.
All known number system constructions use digit sets whose elements are very
close to the origin (canonical, symmetric, adjoint). We examined the following question: is it possible to create number systems with “sparse” digit sets, i.e. systems
where the digits are arbitrarily far away from the origin? We answer this question
affirmatively for a broad class of radices. Hence, it is possible to construct an infinite
number of different GNSs:
Theorem 2. Let L be a regular d × d integer matrix. Suppose further that

1. ρ(L−1 ) < 1/2, i.e. all eigenvalues of L are bigger than 2;
2. L is diagonalizable over C;
3. the characteristic polynomial of L is f k for some k ∈ N and f is irreducible
over Q;
4. either d ≥ 3 or L has real eigenvalues and d = 2.

Then we can describe a sequence of digit sets Dn such that for every n the pair(L, Dn ) is a GNS, and for any given finite subset S of the lattice, 0 ∈/ S, there exists
N ∈ N such that for n ≥ N, the set Dn doesn’t use any of the elements of S.

We also give several other sets of conditions which enable this construction of“arbitrarily sparse” alphabets, and show that the these conditions are equivalent to
the previous ones.
Jakub Krásenský aknowledges financial support by the Grant Agency of the
Czech Technical University in Prague, grant SGS17/193/OHK4/3T/14.

27

sciencesconf.org:numeration2018:195958

References
1. Germán, L., and Kovács, A., On number system constructions, Acta Mathematica Hungarica,
115/1, (2007), 155–167.
2. Kátai, I., Number systems in imaginary quadratic fields, Annales Univ. Sci. Bud., Sectio Comp.,
14, (1994), 91–103.
3. Kovács, A., On computation of attractors for invertible expanding linear operators in Z k , Publ.
Math. Debrecen, 56/1–2, (2000), 97–120.
4. Steidl, G., On symmetric radix representation of Gaussian integers, BIT, Numerical Mathematics 29/3, (1989), 563–571.
5. Vince, A., Replicating Tessellations, SIAM Journal on Discrete Mathematics 6/3, (1993), 501–
521.

28

sciencesconf.org:numeration2018:195958

Ito ↵-continued fractions and matching
Niels Langeveld
In this talk, we look at Ito ↵-continued fractions and matching. Matching tells us when the entropy as a function of ↵ is increasing constant ordecreasing. We will look at di↵erences and similarities between the caseof Ito-↵ continued fractions and other continued fraction algorithms.
1, ↵] ! [↵ 1, ↵] be defined by(S(x) bS(x) + 1 ↵c for x 6= 0,
T↵ (x) =0
for x = 0.

Let T↵ : [↵(1)

Di↵erent choices of S in formula (1) give rise to di↵erent generalizationsof the classical continued fraction algorithms:
1(N) for S(x) = |x|
one gets the ↵-continued fractions first studied by H.
Nakada [8].

(KU) for S(x) = x1 one gets the ↵-continued fractions first studied by S.
Katok and I. Ugarcovici [5].
(IT) for S(x) = x1 one gets the ↵-continued fractions first studied by S.
Ito and S. Tanaka [4].
As in cases (N) and (KU), also for Ito-Tanaka continued fractions thematching property will play a central role; a parameter ↵ 2 [0, 1] satisfies
the matching condition with matching exponents M, N if
T↵N (↵) = T↵M (↵

1).

(2)

For matching we will use the following definition:
Definition 1 (Matching). Let J ⇢ [0, 1] be an interval with non-empty
interior. We say that J is a matching interval with exponents N, M if(i) condition (2) holds for every ↵ 2 J;(ii) {↵
by1, ↵} \ P M↵ = ;, where P M↵ is the pre-matching set defined
P M↵ = {T↵j (↵), 0 < j < N } [ {T↵i (↵1), 0 < i < M };(iii) condition (2) does not hold if we decrease the both exponents by 1,
moreover J is not properly contained in any larger interval on which
condition (2) holds.
The di↵erence:= M N is called matching index.
We call matching set the set A obtained by the union of all matchingintervals; its complement will be called bifurcation set and will be denoted
by E.

29

sciencesconf.org:numeration2018:195838

Using a shadowing argument, one can show that for all ↵ 2 Q \ (0, 1)
there is a matching interval J such that ↵ 2 J in the case of (N) and (KU).
For Ito ↵ continued fractions this is not true. For some rationals we willfind that, even though 2 holds, there is no matching interval that they
are contained in. In fact, interesting behaviour can be observed aroundthese rationals. Let Qb the set of such rationals. We have the following
theorem.
Theorem 0.1. Let b 2 Qb \ (0, 12 ). Then there exists sequences of intervals (In ), (Jn ), (Kn ), (Ln ), n 2 N such that for all n 2 N we have

1. In < Jn < In+1 < Jn+1 < b and b < Kn+1 < Ln+1 < Kn < Ln
2. For all n 2 N the entropy is constant on In and Kn and is increasingon Jn and Ln .
3. for all > 0 we have that there is an n such that• (b, b) \ In 6= ;• (b, b) \ Jn 6= ;• (b, b + ) \ Kn 6= ;• (b, b + ) \ Ln 6= ;4. we can find an increasing sequence (cn )n 1 ⇢ Qb and a decreasing
sequence (dn )n 1 ⇢ Qb such that limn!1 cn = limn!1 dn = b.

In the talk we will construct such sequences explicitly. We will also
relate this to an open dynamical system.

This is joint work with Carlo Carminati, Hitoshi Nakada and Wolfgang
Steiner.

References[1] C. Carminati, S. Isola and G. Tiozzo, Continued fractions with SL(2, Z)branches: combinatorics and entropy, to appear on Trans. Amer. Math.
Soc. https://doi.org/10.1090/tran/7109[2] C. Carminati and G. Tiozzo. A canonical thickening of and the entropyof ↵-continued fraction transformations. Erdogic theory and dynamicalsystems 32 (2012), 1249-1269[3] C. Carminati and G. Tiozzo. Tuning plateaux for the entropy of ↵continued fractions. Nonlinearity 26 (2013), 1049-1070[4] S. Ito and S. Tanaka. On a family of continued-fraction transformations
and their ergodic properties. Tokyo J. Math. Vol. 4 No 1 (1981)[5] S. Katok and I. Ugarcovici, Applications of (a, b)-continued fraction transformations, J. Mod. Dyn. 4 (2010), no 4, 637-691.
[6] S. Katok and I. Ugarcovici, Applications of (a,b)-continued fraction transformations. Ergodic Theory Dynam. Systems 32 (2012), no. 2, 755–777.
[7] L. Luzzi and S. Marmi. On the entropy of Japanese continued fractions.
Discrete Contin. Dyn. Syst. 20 (2008), 673-711.
[8] H. Nakada, Metrical theory for a class of continued fraction transformations and their natural extensions. Tokyo J. Math. 4(1981),no. 2, 399-426.
[9] H. Nakada and R. Natsui. The non-monotonicity of the entropy of ↵continued fraction transformations. Nonlinearity 21 (2008), 1207-1225

30

sciencesconf.org:numeration2018:195838

THE SUM-OF-DIGITS FUNCTION OF LINEARLY RECURRENTNUMBER SYSTEMS AND ALMOST PRIMESMANFRED G. MADRITSCHThis is joint work with Jörg Thuswaldner from University of Leoben and Mario Weitzer
from Graz University of Technology.
A linear recurrent number system is a generalization of the q-adic number system. In
particular, we replace the sequence of powers of q by a linear recurrent sequence Gk+d =a1 Gk+d−1 + · + ad Gk for k ≥ 0. Under some mild conditions for every positive integer n wehave a representation of the formkXn=εj (n)Gj .
j=0

The q-adic number system corresponds to the linear recursion Gk+1 = qGk and G0 = 1.
The first example of a real generalization is due to Zeckendorf who showed that the Fibonaccisequence G0 = 1, G1 = 2, Gk+2 = Gk+1 + Gk for k ≥ 0 yields a representation for eachpositive integer. This is unique if we additionally suppose that no two consecutive ones exist
in the representation.
In the present talk we investigate the representation of primes and almost primes in linear
recurrent number systems. We start by showing the different results due to Fouvry, Mauduit
and Rivat [2–4]in the case of q-adic number systems. Then we shed some light on their main
tools and techniques. The hearth of our considerations is the following Bombieri-Vinogradov
type resultXq<xϑ−εmax maxy<x 1≤a≤qXn<y,sG (n)≡b mod dn≡b mod q

1−

1
q

X

n<y,sG (n)≡b mod d1  x(log 2x)−A ,which we establish under the assumption that a1 ≥ 30. This lower bound is due to numericalestimation.
With this tool in hand we aim for lower bounds on the sets of primes and almost primes
such thatx.
|{n ≤ x : sG (n) ≡ b mod d, n = p1 or n = p1 p2 }| log x
Finally we want to discuss further related problems like lower estimates for polynomials
instead of almost primes as have been established by Dartyge, Stoll and Tenenbaum [1, 5]
References[1] C. Dartyge and G. Tenenbaum, Congruences de sommes de chiffres de valeurs polynomiales, Bull. London
Math. Soc. 38 (2006), no. 1, 61–69. MR2201604[2] E. Fouvry and C. Mauduit, Méthodes de crible et fonctions sommes des chiffres, Acta Arith. 77 (1996),
no. 4, 339–351. MR1414514 (97j:11046)

31

sciencesconf.org:numeration2018:195887

[3], Sommes des chiffres et nombres presque premiers, Math. Ann. 305 (1996), no. 3, 571–599.
MR1397437[4] C. Mauduit and J. Rivat, Sur un problème de Gelfond: la somme des chiffres des nombres premiers, Ann.
of Math. (2) 171 (2010), no. 3, 1591–1646. MR2680394 (2011j:11137)[5] T. Stoll, Combinatorial constructions for the Zeckendorf sum of digits of polynomial values, Ramanujan J.
32 (2013), no. 2, 227–243. MR3118300
Manfred Madritsch
1. Université de Lorraine, Institut Elie Cartan de Lorraine, UMR 7502, Vandoeuvre-lès-Nancy,
F-54506, France;
2. CNRS, Institut Elie Cartan de Lorraine, UMR 7502, Vandoeuvre-lès-Nancy, F-54506, France
E-mail address: manfred.madritsch@univ-lorraine.fr

32

sciencesconf.org:numeration2018:195887

CONSTRUCTING INVARIANT DENSITIES FOR RANDOM SYSTEMSMARTA MAGGIONIThis is a joint work with Charlene Kalle. Ergodic theory is convenient for understanding the
global behaviour of series expansions of numbers in a given interval. Indeed, series expansions
can be generated by iterations of an appropriate map T , where the digits are defined byrecursive relations. Generally, most of the maps studied to generate number expansions are
Lasota-Yorke maps ([LY73]), i.e. expanding, piecewise C 2 -transformations on the interval.
These maps have been intensively studied. For instance, a number of articles have been
published on absolutely continuous invariant measures of these type of transformations. These
measures allow to obtain properties of the related series expansions, such as digits frequency.
A prime example is the binary expansions, where the map T (x) = 2x mod 1 associates witheach point x of the unit interval [0, 1) an infinite sequence of 0’s and 1’s. Another classicalexample, although more complicated, is provided by the greedy and lazy β-transformations,for a non integer β > 1. See [Rén57, Par60, Gel59, DK10, EJK90, Sid03, DdV07] for example.
The deterministic case becomes even more interesting when replaced with a random setting.
In this context, instead of a single map T , a family of maps T1 , ..., Tr is considered from which
one is selected at each iteration according to a probabilistic regime. Also random systems
are used to generate number expansions. The random β-expansions introduced in [DK03] byDajani and Kraaikamp provides an example, see Figure 1. It uses random combinations of twopiecewise linear maps with constant slope β > 1. See [DdV05, DK13, Kem14] for example.

1
β−1

1
β−1

1
β−1

1

1

2−β
β−1

2−β
β−1

0

1
β(β−1)(a) T0

1
β−1

0

1
β

(b) T1

1
β−1

0

1
β−1

(c) T

Figure 1. In (a) we see the lazy β-transformation, in (b) the greedy β2−βtransformation and in (c) we see them combined. Whether or not 1 > β−1
depends on the chosen value of β.
In [DdV07] it was shown that these maps have a unique absolutely continuous invariant
measure. In [Kem14] Kempton gave a formula for the invariant density of the random βtransformation if one chooses the maps according to the uniform Bernoulli regime, and very
recently Suzuki ([Suz17]) extended these results to include the non-uniform Bernoulli regime
as well.
Except for this specific case, not much is known about the absolutely continuous invariant
measures of general random maps. In [Pel84] Pelikan gave sufficient conditions under whicha random system, using a finite number of Lasota-Yorke maps, has absolutely continuous
invariant measures. He also discussed the possible number of ergodic components. But noexplicit expressions for invariant densities were given.
We therefore study invariant densities for any random system of piecewise linear maps thatare expanding on average. More precisely, we provide a procedure to construct an explicit

33

sciencesconf.org:numeration2018:195455

formula for the density of an absolutely continuous invariant measure. We obtain this result
by generalising the method from [Kop90], valid in the deterministic setting.
For a given random system T we construct a fundamental matrix M . We prove the existenceof a non-trivial solution for the matrix equation M γ = 0 and we relate each solution γ tothe density of an absolutely continuous invariant measure hγ of the system T . We apply theprocedure to different examples. We generalise the results from [Kem14] and [Suz17] regarding
the expression for the invariant density for the random β-transformation. Moreover, we study
a system that is not everywhere expanding, but is expanding on average, by considering arandom combination of the greedy β-transformation and the intermittent (α, β)-transformation
introduced in [DHK09], see Figure 2. Last, we study another system that has different slopes,
namely a random Lüroth map with a hole, see Figure 3.
1

β−1
α β−1
β
0

1

1
β

Figure 2. The random (α, β)-transformation.

1

1

0

11 1
54 3

1
2

(a) TL

1

1

0

11 1
54 3

1
2

(b) TA

1

0

1
3

1
2

1

(c) T

Figure 3. In (a) we see the Lüroth map and in (b) the alternating Lüroth
map. (c) shows the open random system system T consistingof random
combinations of TL and TA restricted to the interval 13 , 1 .
References[DdV05] K. Dajani and M. de Vries. Measures of maximal entropy for random β-expansions. J. Eur. Math.
Soc., 7(1):51–68, 2005.
[DdV07] K. Dajani and M. de Vries. Invariant densities for random β-expansions. J. Eur. Math. Soc., 9(1):157–
176, 2007.
[DHK09] K. Dajani, Y. Hartono, and C. Kraaikamp. Mixing properties of (α, β)-expansions. Ergodic Theory
Dynam. Systems, 29(4):1119–1140, 2009.
[DK03] K. Dajani and C. Kraaikamp. Random β-expansions. Ergodic Theory Dynam. Systems, 23(2):461–
479, 2003.
[DK10] K. Dajani and C. Kalle. A note on the greedy β-transformation with arbitrary digits. In École deThéorie Ergodique, volume 20 of Sémin. Congr., pages 83–104. Soc. Math. France, Paris, 2010.
[DK13] K. Dajani and C. Kalle. Local dimensions for the random β-transformation. New York J. Math.,
19:285–303, 2013.
P−ni and[EJK90] P. Erdös, I. Joó, and V. Komornik. Characterization of the unique expansions 1 = ∞i=1 q
related problems. Bull. Soc. Math. France, 118(3):377–390, 1990.
[Gel59] A. O. Gel0 fond. A common property of number systems. Izv. Akad. Nauk SSSR. Ser. Mat., 23:809–
814, 1959.
[Kem14] K. Kempton. On the invariant density of the random β-transformation. Acta Math. Hungar.,142(2):403–419, 2014.

34

sciencesconf.org:numeration2018:195455

[Kop90][LY73][Par60][Pel84][Rén57][Sid03][Suz17]

C. Kopf. Invariant measures for piecewise linear transformations of the interval. Appl. Math. Comput.,
39(2, part II):123–144, 1990.
A. Lasota and J. A. Yorke. On the existence of invariant measures for piecewise monotonic transformations. Trans. Amer. Math. Soc., 186:481–488 (1974), 1973.
W. Parry. On the β-expansions of real numbers. Acta Math. Acad. Sci. Hungar., 11:401–416, 1960.
S. Pelikan. Invariant densities for random maps of the interval. Trans. Amer. Math. Soc., 281(2):813–
825, 1984.
A. Rényi. Representations for real numbers and their ergodic properties. Acta Math. Acad. Sci.
Hungar, 8:477–493, 1957.
N. Sidorov. Almost every number has a continuum of β-expansions. Amer. Math. Monthly,
110(9):838–842, 2003.
S. Suzuki. Invariant density functions of random β-transformations. Ergodic Theory and Dynamical
Systems, page 1–22, 2017.

(Marta Maggioni) Mathematisch Instituut, Leiden University, Niels Bohrweg 1, 2333CA Leiden,
The Netherlands
E-mail address, Marta Maggioni: m.maggioni@math.leidenuniv.nl

35

sciencesconf.org:numeration2018:195455

SOME COMPLEXITY RESULTS IN THE THEORY OF NORMALNUMBERSD. AIREY, S. JACKSON, AND B. MANCE

For a real number r, define real functions πr and σr by πr (x) = rx and σr (x) =r + x. We let N (b) denote the set of reals x which are normal to base b. We letN ⊥ (b) = {y : ∀x ∈ N (b) σy (x) ∈ N (b)}.

Normality preserving functions. Let f be a function from R to R. We saythat f preserves b-normality if f (N (b)) ⊆ N (b)). We can make a similar definition
for preserving normality with respect to the regular continued fraction expansion,
β-expansions, Cantor series expansions, the Lüroth series expansion, etc.
Several authors have studied b-normality preserving functions. They naturally
arise in H. Furstenberg’s work on disjointness in ergodic theory[10]. V. N. Agafonov[1], T. Kamae [12], T. Kamae and B. Weiss [13], and W. Merkle and J. Reimann [18]studied b-normality preserving selection rules. The situation for continued fractions
is very different. Let [a1 , a2 , a3 , . . .] be normal with respect to the continued fraction
expansion. B. Heersink and J. Vandehey [11] recently proved that for any integersm ≥ 2, k ≥ 1, the continued fraction [ak , am+k , a2m+k , a3m+k , . . .] is never normal
with respect to the continued fraction expansion.
In 1949 D. D. Wall proved in his Ph.D. thesis [21] that for non-zero rational r thefunction πr is b-normality preserving for all b and that the function σr is b-normality
preserving for all b whenever r is rational. These results were also independently
proven by K. T. Chang in 1976 [8]. D. D. Wall’s method relies on the well known
characterization that a real number x is normal in base b if and only if the sequence(bn x) is uniformly distributed mod 1[16].
D. Doty, J. H. Lutz, and S. Nandakumar took a substantially different approachfrom D. D. Wall and strengthened his result. They proved in [9] that for every real
number x and every non-zero rational number r the b-ary expansions of x, πr (x),and σr (x) all have the same finite-state dimension and the same finite-state strong
dimension. It follows that πr and σr preserve b-normality. It should be noted that
their proof uses different methods from those used by D. D. Wall and is unlikely tobe proven using similar machinery.
G. Rauzy obtained a complete characterization of N ⊥ (b) in [19]. M. Bernay used
this characterization to prove that Σb has zero Hausdorff dimension [6]. One of themain results of this paper, stated in Corollary 3, is to obtain an exact determinationof the descriptive set theoretic complexity of N ⊥ (b).
M. Mendés France asked in [17] if the function πr preserves simple normality withrespect to the regular continued fraction for every non-zero rational r. This wasrecently settled by J. Vandehey [20] who showed that ax+b
cx+d is normal with respect
to the continued fraction when x is normal with respect to the continued fraction
expansion and integers a, b, c,and d satisfy ad − bc 6= 0. Work was also done on
the normality preserving properties of the functions πr and σr for the Cantor series36sciencesconf.org:numeration2018:195953

expansions by the first and third author in [2] and additonally with J. Vandehey in[3]. However, these functions are not well understood in this context.
Descriptive Complexity. In any topological space X, the collection of Borel
sets B(X) is the smallest σ-algebra containing the open sets. They are stratified
into levels, the Borel hierarchy, by defining Σ01 = the open sets, Π01 = ¬Σ01 ={X − A : A ∈ Σ01 } = the S
closed sets, and for α < ω1 we let Σ0α be the collectionof countable unions A = n An where each An ∈ Π0αn for some αn < α. We alsoTlet Π0α = ¬Σ0α . Alternatively, A ∈ Π0α if A = n An where An ∈ Σ0αn where
each αn < α. We also set ∆0α = Σ0α ∩ Σ0α , in particular∆01 isS
S the collection of0
clopen sets. For any topological space, B(X) = α<ω1 Σα = α<ω1 Π0α . All of
the collections ∆0α , Σ0α , Π0α are pointclasses, that is, they are closed under inverse
images of continuous functions. A basic fact (see [14]) is that for any uncountable
Polish space X, there is no collapse in the levels of the Borel hierarchy, that is,
all the various pointclasses ∆0α , Σ0α , Π0α , for α < ω1 , are all distinct. Thus, theselevels of the Borel hierarch can be used to calibrate the descriptive complexity ofa set. We say a set A ⊆ X is Σ0α (resp. Π0α ) hard if A ∈/ Π0α (resp. A ∈/ Σ0α ). This00says A is “no simpler” than a Σα set. We say A is Σα -complete if A ∈ Σ0α − Π0α ,that is, A ∈ Σ0α and A is Σ0α hard. This says A is exactly at the complexity level
Σ0α . Likewise, A is Π0α -complete if A ∈ Π0α − Σ0α .
A fundamental result of Suslin (see [14]) says that in any Polish space B(X) =∆11 = Σ11 ∩ Π11 , where Π11 = ¬Σ11 , and Σ11 is the pointclass of continuous imagesof Borel sets. Equivalently, A ∈ Σ11 iff A can be written as x ∈ a ↔ ∃y (x, y) ∈ B
where B ⊆ X × Y is Borel (for some Polish space Y ). Similarly, A ∈ Π11 iff it isof the form x ∈ A ↔ ∀y (x, y) ∈ B for a Borel B. The Σ11 sets are also called
the analytic sets, and Π11 the co-analytic sets. We also have Σ11 6= Π11 for any
uncountable Polish space.
H. Ki and T. Linton [15] proved that the set N (b) is Π03 (R)-complete. Further
work was done by V. Becher, P. A. Heiber, and T. A. Slaman [4] who settled aconjecture of A. S. Kechris by showing that the set of absolutely normal numbers
is Π03 (R)-complete. Furthermore, V. Becher and T. A. Slaman [5] proved that theset of numbers normal in at least one base is Σ04 (R)-complete.
K. Beros considered sets involving normal numbers in the difference heirarchy in[7]. Let Nk (b) be the set of numbers normal of order k in base b. He proved that(see [14] for a
for b ≥ 2 and s > r ≥ 1, the set Nr (b)\Ns (b) is D2 (Π03 )-completeSdefinition of the difference hierarchy). Additionally, the set k N2k+1 (2)\N2k+2 (2)is shown to be Dω (Π03 )-complete.
Results. We are interested in determining the exact descriptive set theoretic complexity of N ⊥ (b) and some related sets. The definition of N ⊥ (b) shows that N ⊥ (b)is Π11 , since it involves a universal quantification. It is not immediately clear if
N ⊥ (b) is a Borel set, but this in fact follows from a result of Rauzy. Specifically,
Rauzy [19] characterized N ⊥ (b) in terms of an entropy-like condition called thenoise. We recall this condition and associated notation from [19]. For any positive
integer length `, let E` denote the set of functions from b` to b. We call an E ∈ E`a block function of width `. As in [19] we set, for x ∈ R,
1 X
inf{1, |cn − E(cn+1 , . . . , cn+` )|},β` (x, N ) = inf
E∈E` Nn<N

37

sciencesconf.org:numeration2018:195953

where c0 , c1 , . . . is the (fractional part) of the base b expansion of x.
We also let for E ∈ E
1 X
βE (x, N ) =inf{1, |cn − E(cn+1 , . . . , cn+` )|}.
Nn<N

We then define the lower and upper noises β − (x), β + (x) of x by:β − (x) = lim β`− (x),
`→∞

where
β`− (x) = lim inf β` (x, N ).
N →∞The upper entropy β + (x) is defined similarly using
β + (x) = lim β`+ (x)
`→∞

where
β`+ (x) = lim sup β` (x, N ).
For a fixed E ∈ E we also let

N →∞

−
βE
(x) = lim inf βE (x, N ),+and similarly for βE
(x).

N →∞

Rauzy showed that x ∈ N (b) iff it has the maximal possible noise in that β − (x) =b−1⊥+
b . Furthermore, x ∈ N (b) iff it has minmal possible noise in that β (x) = 0.
b−1
It is therefore natural to ask for any s ∈ [0, b ], what are the complexities of thelower and upper noise sets associated to s. Specifically, we introduce the following
four sets.
Definition 1. Let s ∈ [0, b−1b ]. Let(1)
Finally, we let

A1 (s) = {x : β − (x) ≤ s},
A3 (s) = {x : β + (x) ≤ s},

A2 (s) = {x : β − (x) ≥ s}

A4 (s) = {x : β + (x) ≥ s}

L(s) = A1 (s) ∩ A2 (s) = {x : β − (x) = s}

U (s) = A3 (s) ∩ A4 (s) = {x : β + (x) = s}.
⊥Thus, N (b) = L( b−1b ), and N (b) = U (0). The Ki-Linton result shows that0b−1
N (b), and thus L( b ) is Π3 -complete for any base b. Recall also the BecherSlaman result which shows that the set of reals which are normal to some base b
forms a Σ04 -complete set.
We have the following complexity results.
0
Theorem 2. For any s ∈ [0, b−1b ), the set A1 (s) is Π4 -complete and the set A3 (s)0is Π03 -complete. For any s ∈ (0, b−1b ], the set A2 (s) is Π3 -complete, and the set0b−1
A4 (s) is Π2 -complete. For s ∈ (0, b ), the set L(s) is Π04 -complete, and the set
U (s) is Π03 -complete.

As a corollary we obtain the Ki-Linton result as well as the determination of theexact complexity of N ⊥ (b).

Corollary 3. The sets N (b) and N ⊥ (b) are both Π03 -complete.

38

sciencesconf.org:numeration2018:195953

We remark on the significance of complexity classifications such Theorem 2.
Aside from the intrinsic interest to descriptive set theory, results of this form canbe viewed as ruling out the existence of further theorems which would reduce thecomplexity of the sets. For example, Rauzy’s theorem reduces the complexity ofN ⊥ (b) from Π11 to Π03 . The fact that A3 (0) is Π03 -complete tells us that there
cannot be other theorems which result in a yet simpler characterization of N ⊥ (b).
Lastly, we wish to approximate the Hausdorff dimension of the sets Ai (s), U (s),and L(s). Put H(s) = −s log s − (1 − s) log(1 − s).

we have
Theorem 4. For s ∈ 0, b−1bdimH (A1 (s)) = 1
dimH (A2 (s)) = 1
1log(b − 1)1
H(s) +s ≤ dimH (A3 (s)) ≤H(s) + s
log b
log b
log b
dimH (A4 (s)) = 1.
Furthermore
log(b − 1)11
H(s) +s ≤ dimH (U (s)) ≤H(s) + s
log b
log b
log b
dimH (L(s)) = 1.
References
1. V. N. Agafonov, Normal sequences and finite automata, Dokl. Akad. Nauk SSSR 179 (1968),
255–256.
2. D. Airey and B. Mance, Normality preserving operations for Cantor series expansions andassociated fractals, I, to appear in Illinois J. Math.
3. D. Airey, B. Mance, and J. Vandehey, Normality preserving operations for Cantor series
expansions and associated fractals, II, New York J. Math. 21 (2015), 1311–1326.
4. V. Becher, P. A. Heiber, and T. A. Slaman, Normal numbers and the Borel hierarchy, Fund.
Math. 226 (2014), no. 1, 63–78.
5. V. Becher and T. A. Slaman, On the normality of numbers to different bases, J. Lond. Math.
Soc. (2) 90 (2014), no. 2, 472–494.
6. M. Bernay, La dimension de Hausdorff de l’ensemble des nombres r-déterministes, C. R.
Acad. Sci. Paris 280 (1975), A539–A541.
7. K. A. Beros, Normal numbers and completeness results for difference sets, J. Symb. Log. 82(2017), no. 1, 247–257.
8. K. T. Chang, A note on normal numbers, Nanta Math. 9 (1976), 70–72.
9. D. Doty, J. H. Lutz, and S. Nandakumar, Finite-state dimension and real arithmetic, Inform.
and Comput. 205 (2007), 1640–1651.
10. H. Furstenberg, Disjointness in ergodic theory, minimal sets, and a problem in Diophantine
approximation, Math. Systems Theory 1 (1967), 1–49.
11. B. Heersink and J. Vandehey, Continued fraction normality is not preserved along arithmetic
progressions, Arch. Math. (Basel) 106 (2016), no. 4, 363–370.
12. T. Kamae, Subsequences of normal sequences, Israel J. Math 16 (1973), 121–149.
13. T. Kamae and B. Weiss, Normal numbers and selection rules, Israel J. Math 21 (1975),
101–110.
14. A. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156,
Springer-Verlag, New York, 1995.
15. H. Ki and T. Linton, Normal numbers and subsets of N with given densities, Fund. Math.
144 (1994), no. 2, 163–179.
16. L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Dover, Mineola, NY, 2006,
MR0419394.

39

sciencesconf.org:numeration2018:195953

17. Ch. Mauduit, Problem session dedicated to Gérard Rauzy, Dynamical systems (Luminy–
Marseille, 1998), World Scientific Publishing, River Edge, NJ, 2000.
18. W. Merkle and J. Reimann, Selection functions that do not preserve normality, Theory Comput. Syst. 39 (2006), no. 5, 685–697.
19. G. Rauzy, Nombres normaux et processus déterministes, Acta Arith. 29 (1976), no. 3, 211–
225.
20. J. Vandehey, Non-trivial matrix actions preserve normality for continued fractions,
arXiv:1504.05121.
21. D. D. Wall, Normal numbers, Ph.D. thesis, Univ. of California, Berkeley, Berkeley, California,
1949.

40

sciencesconf.org:numeration2018:195953

MÖBIUS ORTHOGONALITY FOR AUTOMATIC
SEQUENCES AND BEYOND
CLEMENS MÜLLNER

The presented results are partly joint work with Michael Drmota andLukas Spiegelhofer.
This talk focuses on two different methods to show that fixed points
of substitutions can not correlate with the Möbius function. First we
recall the case of substitutions of fixed length. Fixed points of substitutions of fixed length correspond to automatic sequences and theauthor proved that any automatic sequence is orthogonal to the Möbius
function. This result relies on a new structural result for deterministic
finite automata and uses a method developed by Mauduit and Rivat.
In the case of non-constant length substitutions, very little is known
and we focus only on one particular case. It was recently shown by Drmota, Müllner and Spiegelhofer that the sequence (−1)sϕ (n) is asymptotically orthogonal to all bounded multiplicative functions, where sϕdenotesthe Zeckendorf sum-of-digits function. In particular we havePsϕ (n)(−1)µ(n) = o(N ), that is, this sequence is orthogonal to then<NMöbius function.
We use the Katai - Bourgain- Ziegler criterion to reduce
P - Sarnaksϕ (pn)+s
ϕ (qn). To analyze suchthe problem to estimates of n<N (−1)
sums we use the concept of quasi-additivity with respect to the Zeckendorf expansion which allows a generating function approach, which
was introduced by Kropf and Wagner for integer bases.

41

sciencesconf.org:numeration2018:195990

ROTATION NUMBER OF CONTRACTED ROTATIONS
Arnaldo Nogueira, Institut des Mathématiques de Marseille
Based on a joint work with Michel Laurant.
Let I = [0, 1) be the unit interval.
Definition 1. Let 0 < λ < 1 and δ ∈ I. We call the map defined by
f = fλ,δ : x ∈ I "→ {λx + δ},

where the symbol {.} stands for the fractional part, a contracted rotation of I.
If λ + δ > 1, f is a 2-interval piecewise contraction on the interval I (see Figure 1).
1
δ

λ+δ−1
0

1

1−δ
λ

Figure 1. A plot of fλ,δ : I → I, where λ + δ > 1
Many authors have studied the dynamics of contracted rotations, as a dynamical system
or in applications. It is known that every contracted rotation map f has a rotation numberρ = ρλ,δ , satisfying 0 ≤ ρ < 1. The goal of this article is to study the value of the rotation
number ρλ,δ according to the diophantine nature of the parameters λ and δ. Applying aclassical transcendence result due to J.H. Loxton and A.J. van der Poorten, we prove
Theorem 1. Let 0 < λ, δ < 1 be algebraic real numbers. Then, the rotation number ρλ,δis a rational number.
In view of Theorem 1, a natural problem that arises is to estimate the height of therational rotation number ρλ,δ in terms of the algebraic numbers λ and δ. We provide apartial solution for this issue when λ and δ are rational.
Theorem 2. Let λ = a/b√and δ = r/s be rational numbers with 0 < λ, δ < 1. Assume
that b > aγ , where γ = 1+2 5 denotes the golden ratio. Then, the rotation number ρλ,δ isa rational number p/q where
γ log(sb)0 ≤ p < q ≤ γ 2+ log b−γ log a .

42sciencesconf.org:numeration2018:204364

Our proofs of Theorems 1 and 2 are based on an arithmetical analysis of formulae giving
the rotation number ρλ,δ in terms of the parameters λ and δ. As far as we are aware,
it is in the works of E. J. Ding and P. C. Hemmer and Y. Bugeaud that appears thefirst complete description of the relations between the parameters λ, δ and the rotation
number ρλ,δ . For 0 < λ < 1 fixed, these papers deal with the variation of the rotation
number in the one-dimensional family of contracted rotations fλ,δ as δ runs through theinterval [0, 1). We summarize the results that we need in the following
Theorem 3. Let 0 < λ < 1 be given. Then the application δ "→ ρλ,δ is a continuous nondecreasing function sending I onto I and satisfying the following properties:(i) The rotation number ρλ,δ vanishes exactly when 0 ≤ δ ≤ 1 − λ.
p(ii) Let be a positive rational number, where 0 < p < q are relatively prime integers.
qp
Then ρλ,δ takes the value if and only if δ is located in the interval
q
!
"
! !
"
"
1−λ
p
1−λ
p
q−1
q
c λ,
≤δ≤
c λ,
+λ
−λ ,
1 − λqq
1 − λqqwhere"% $ %"!
q−2 !$#ppp(k + 1) − k
=1+
λk
c λ,
q
q
q
k=1
and the above sum equals 0 when q = 2.
(iii) For every irrational number ρ with 0 < ρ < 1, there exists one and only one real
number δ such that 0 < δ < 1 and ρλ,δ = ρ which is given by the formula
'
&
+∞
#
(1)
δ = δ(λ, ρ) = (1 − λ) 1 +([(k + 1)ρ] − [kρ]) λk .
k=1

The proof of Theorem 2 deeply relies on a tree structure, introduced by Y. Bugeaud and
J.-P. Conze which is parallel to the classical Stern-Brocot tree of rational numbers. It
enables us to handle more easily the complicated intervals occuring in Theorem 3 (ii).

43sciencesconf.org:numeration2018:204364

On Schneider’s Continued Fraction Map on aComplete Non-Archimedean Field
Speaker: R. Nair (Liverpool)
Abstract : This is joint work with A. Haddley (nee Jaššová) of the
University of Liverpool. The purpose of this talk is to calculate the entropyof T. Schneider’s continued fraction map, and to show the map has a naturalextention which is Bernoulli. Schneider’s map is the natural analogue of theGauss continued fraction map in this setting. The Gauss map is known to
π2. Schneider’s map ishave a Bernoulli natural extention with entropy 6 log(2)usually defined on the p-adic field for the rational prime p. In fact we workin a more general setting which we now describe. Let K denote a topologicalfield. By this we mean that the field K is a locally compact group under the
addition, with respect to a topology. This ensures that there is a translation
invariant Haar measure µ on K, that is unique up to scalar multiplication.
In the non-Archimedean examples that concern us, this topology will always
be discrete. For an element a ∈ K, we are now able to define its absolutevalue, asµ(aF )
,
|a| =
µ(F )
for every µ measureable F ⊆ K of finite positive µ measure. Let R≥0 denotethe set of non-negative real numbers. An absolute value is a function |.| :K → R≥0 such that (i) |a| = 0 if and only if a = 0; (ii) |ab| = |a||b| for alla, b ∈ K and (iii) |a + b| ≤ |a| + |b| for all pairs a, b ∈ K. The absolute value
just defined gives rise to a metric defined by d(a, b) = |a − b| with a, b ∈ K,
whose topology coincides with original topology on the field K.
Topological fields come in two types. The first where (iii) can be replacedby the stronger condition (iii)* |a + b| ≤ max(|a|, |b|) a, b ∈ K, called nonArchimedean fields and fields where (iii)* is not true called Archimedean
spaces. In this paper we shall concern ourselves solely with non-Archimedeanfields. Another approach to defining a non-Archimedan field is via discrete
valuations. Denote the real numbers by R. Let K ∗ = K\{0}. A map
v : K ∗ → R is a valuation if (a) v(K ∗ ) 6= {0}; (b) v(xy) = v(x) + v(y) forx, y ∈ K and (c) v(x + y) ≥ min{v(x), v(y)}. Two valuations v and cv, for44

sciencesconf.org:numeration2018:194191

c > 0 a real constant, are called equivalent. We extend v to K formally byletting v(0) = ∞. The image v(K ∗ ) is an additive subgroup of R called thevalue group of v. If the value group is isomorphic to Z, we say v is a discrete
valuation. Here Z denotes the set of integers. If v(K ∗ ) = Z, we call v anormalised discrete valuation. To our initial absolute value we associate thevaluation described as follows. Pick 0 < α < 1 and write |a| = αv(a) , i.e., letv(a) = logα |a|. Then v(a) is a valuation, an additive version of |a|.
Let v : K ∗ → R be a valuation corresponding to the absolute value|.| : K → R≥0 . ThenO = Ov := {x ∈ K : v(x) ≥ 0} = OK := {x ∈ K : |x| ≤ 1}
is a ring, called the valuation ring of v and K is its field of fractions. The
set of units in O is O× = {x ∈ K : v(x) = 0} = {x ∈ K : |x| = 1} andM = {x ∈ K : v(x) > 0} = {x ∈ K : |x| < 1} is an ideal in O. Note
O = O× ∪ M. Because M is a maximal ideal, we know k = O/M is a field,
called the residue field of v or of K. Henceforth we assume that k is a finite
field. Suppose the valuation v : K ∗ → Z is normalised and discrete. Takeπ ∈ M such that v(π) = 1. We call π a uniformiser. Then every x ∈ K canbe written uniquely as x = uπ n with u ∈ O× and n ∈ Z. In particular everyx ∈ M can be written uniquely as x = uπ n for a unit u ∈ O× and n ≥ 1.
We now consider two examples.
a) p-adic numbers : Let Q denote the rational numbers. For r = pvp uv
in Q with u and v coprime to p and each other, let |r|p = p−vp . Thendp (r, r0 ) = |r − r0 |p for r0 ∈ Q defines a metric on Q. The completion of
Q with respect to the metric dp is a field denoted Qp referred to as the padic numbers. We also use Zp to denote {x ∈ Qp : |x|p ≤ 1} – the ringof p-adic integers. It is worth keeping in mind that the metric dp has theultrametric property, namely that dp (r, r00 ) ≤ max(dp (r, r0 ), dp (r0 , r00 )) for all
r, r0 and r00 ∈ Qp . The main characteristics of the field Qp that distinguish itfrom the field R stem from the ultrametric property. It turns out that Qp isa locally compact abelian field and hence comes endowed with a translation
invariant Haar measure. In this instance K = Qp , O = Zp , M = pZ, π = p
and k = Z/pZ.
b) The field of formal Laurant series in finite characteristic : Let q bea power of a prime p and let Fq be the finite field with q elements. Denote
by Fq [X] and Fq (X) the ring of polynomials with coefficients in Fq and thequotient field of Fq [X] respectively. For each P, Q ∈ Fq [X] set |P/Q| :=q deg(P )−deg(Q) where for an element g ∈ Fp [X] we have denoted its degree bydeg(g). Let Fq ((X −1 )) denote the field of formal Laurent series i.e.

Fq ((X −1 )) = an X n + · · · + a0 + a−1 X −1 + · · · : n ∈ Z, ai ∈ Fq .

45

sciencesconf.org:numeration2018:194191

Also dq (x, y) = |x − y| for x, y ∈ Fq (X) defines a metric on Fq (X). The
metric extends to Fq ((X −1 )) by completion and by implication to its subset
L = {x ∈ Fq ((X −1 )) : |x| ≤ 1}. Note that this metric is non-Archimediansince |x + y| ≤ max(|x|, |y|). In this example K = Fq ((X −1 )), O = L,
M = XL, π = X and k = L/XL = Fq .
The only two types of non-Archimedean local fields there are are finite
exensions of the field of p-adic numbers for some rational prime p and thefield of formal Laurant series over a finite field.
Our primary object of study in this paper is the map Tv : M → M
defined by
π v(x)Tv (x) =− b(x)xv(x)where b(x) denotes the residue class to which π x belongs in k.
This gives rise to the continued fraction expansion of x ∈ M in the form
π a1
x=
π a2
b1 +
π a3
b2 +
b3 + .

..

where bn ∈ k × , an ∈ N for n = 1, 2, . . . . Here N denotes the set of natural
numbers.
The rational approximants to x ∈ M arise in a manner similar to that in
the case of the real numbers as follows. We suppose A0 = b0 , B0 = 1, A1 =b0 b1 + π a1 , B1 = b1 . Then set
An = π an An−2 + bn An−1 and Bn = π an Bn−2 + bn Bn−1
for n ≥ 2. A simple inductive argument, for n = 1, 2, . . . gives
An−1 Bn − An Bn−1 = (−1)n π a1 +...+an .
One can readily check that the map Tv : M → M preserves Haar measure
on M. By this we mean, for each Haar measurable set A contained in M
we have µ(Tv−1 (A)) = µ(A). Here Tv−1 (A) := {x ∈ M : Tv (x) ∈ A}.

In the case where K = Qp the map Tv reduces to the original Schneider’scontinued fracton map Tp , which motivates this whole investigation and isdefined as follows. For x ∈ pZp define the map Tp : pZp → pZp by v(x)

p
pa(x)
pv(x)
−
mod p =− b(x)Tp (x) =x
x
x

46

sciencesconf.org:numeration2018:194191

where v(x) is the p-adic valuation of x, a(x) ∈ N and b(x) ∈ {1, 2, . . . , p − 1}.
Then using the continued fraction algorithm for x we get the expansion,
x=

pa1
pa2
b1 +
pa3
b2 +
b3 + .

..

where bn ∈ {1, 2, . . . , p − 1}, an ∈ N for n = 1, 2, . . . .
We now define measure-theoretic entropy. Let (X, A, m) be a probability
space where X is a set, A is a σ-algebra of its subsets and m is a probability
measure. A partition of (X, A, m) is defined as a denumerable collectionof elements α = {AS 1 , A2 , . . . } of A such that Ai ∩ Aj = ∅ for all i, j ∈ Λwith i 6= j and i∈Λ Ai = X. Here Λ is a denumerable index set. Fora measure-preserving transformation T we have T −1 α = {T −1 Ai |Ai ∈ α}which is also a denumerable partition. Given partitions α = {A1 , A2 , . . . }and β = {B1 , B2 , . . . } we define the join of α and β to be the partitionα ∨ β = {Ai ∩ Bj |Ai ∈ α, Bj ∈ β}.PFor a finite partition α = {A1 , . . . , An }we define its entropy H(α) := − ni=1 m(Ai ) log m(Ai ). Let A0 ⊂ A be a
sub-σ-algebra. Then
we define the conditional entropy of α given A0 toP
be H(α|A0 ) := − ni=1 m(Ai |A0 ) log m(Ai |A0 ). Here m(A|A0 ) denotes the mconditional probability of A with respect to the σ-algebra A0 . See [?] for moredetails about conditional probability. The entropy of a measure-preserving
transformation T relative to a partition α is defined to be
!
n−1
_
1
T −i αhm (T, α) = lim H
n→∞ n
i=0
where the limit always exists. The alternative formula for hm (T, α) which isused for calculating entropy is
!
!
n
∞
_
_
hm (T, α) = lim H α| T −i α = H α| T −i α .
n→∞

i=1

i=1

We define the measure-theoretic entropy of T with respect to the measure m
to be hm (T ) = supα hm (T, α). Here the supremum is taken over all finite or
countable partitions α from A with H(α) < ∞.
Two measure-preseving transformations (X1 , β1 , m1 , T1 ) and (X2 , β2 , m2 , T2 )are said to be isomorphic if there exist sets M1 ⊆ X1 and M2 ⊆ X2 with
m1 (M1 ) = 1 and m2 (M2 ) = 1 such that T1 (M1 ) ⊆ M1 and T2 (M2 ) ⊆ M2

47

sciencesconf.org:numeration2018:194191

and such that there exists a map φ : M1 → M2 satisfying φT1 (x) = T2 φ(x)for all x ∈ M1 and m1 (φ−1 (A)) = m2 (A) for all A ∈ β2 . The importanceof measure theoretic entropy, is that two dynamical systems with different
entropies can not be isomorphic. The following is our first result.
Theorem 0.1 Let B denote the Haar σ-algebra restricted to M and let µdenote Haar measure on M. Then the measure-preserving transformation#(k)(M, B, µ, Tv ) has measure-theoretic entropy #(k× ) log(#(k)).
The measure-preserving transformation (pZp , B, µ, Tp ) is known to be ergodic [3]. Moreover, in [2] it was proved that (pZp , B, µ, Tp ) is exact. The
exactness of (pZp , B, µ, Tp ) implies other weaker properties including mixing,
which implies weak-mixing implying ergodicity, all implications being strict.
Suppose (Y, α, l) is a probability space, and let Yn = (Y, α, l) for each n ∈ Z.
Set (X, β, m) = Πn∈Z Yn i.e. the bi-infinite product probability space. For
the shift map τ ({xn }) = ({xn+1 }), the measure preserving transformation(X, β, m, τ ) is called the Bernoulli process with state space (Y, α, l). Here{xn } is a bi-infinite sequence of elements of the set Y . Any measure preserving transformation isomorphic to a Bernoulli process will be referred to as
Bernoulli. The fundamental fact about Bernoulli processes, famously provedby D. Ornstein, is that Bernoulli processes with the same entropy are isomorphic. To any measure-preserving transformation, (X, β, m, T0 ) we canassociate another called its natural extension. Originally introduced by V.
A. Rokhlin, the natural extension is defined as follows. Set
XT0 = {(x0 , x1 , x2 , . . . ) : xn = T0 (xn+1 ), xn ∈ X, n = 0, 1, 2, . . . },and let T : XT0 → XT0 be defined by
T ((x0 , x1 , . . . , )) = (T0 (x0 ), x0 , x1 , . . . , ).
The map T is 1 − 1 on XT0 . If T0 preserves a measure m, then we can definea measure m on XT0 , by defining m on the cylinder sets
C(A0 , A1 , . . . , Ak ) = {{xn } : x0 ∈ A0 , x1 ∈ A1 , . . . , xk ∈ Ak }bym(C(A0 , A1 , . . . , Ak )) = m(T0−k (A0 ) ∩ T0−k+1 (A1 ) ∩ . . . ∩ Ak ),for k ≥ 1. One can check that the transformation (XT0 , β, m, T0 ) is measurepreserving as a consequence of the measure preservation of the transformation(X, β, m, T0 ). Our second theorem is the following.

48

sciencesconf.org:numeration2018:194191

Theorem 0.2 Suppose (M, B, µ, Tv ) is as in our first theorem. Then the
dynamical system (M, B, µ, Tv ) has a natural extension that is Bernoulli.
Our two theorems above together tell us that as a dynamical system, theisomorphism class to which Tv belongs is determined solely by its residue
class field. This is irrespective of the characteristic of the underlying global
field. For instance for each rational prime p the corresponding Schneider mapplog(p), so we know these maps are mutually non-isomorphic.
has entropy p−1
Each of them is however isomorpic to the analogue of the Schneider map
on the field of formal power series with coefficient field the finite field of pelements.
As is well known, if you restrict the Gauss map to the rational numbers
you get the Euclidean algorithm. If you set p = 2 and restrict the Schneider
map to the rational numbers what you get is the Binary Euclidean algorithm.
This is another way of calculating the highest common factor of two integers,
particularly well adapted to efficient implementation on binary machines.
The algorithm was first published by Josef Stein but is also attributed toRoland Silver and John Terzian. The algorithm may however be much older.
D. Knuth cites a verbal description of the algorithm in the first-century A.D.
Chinese text “Chiu Chang Suan Shu ”. See the reference below for moredetails, including missing definitions.
References[1] A. Haddley, R. Nair: On Schneider’s continued fraction map on a complete non-rchemedian field, Indag. Math. (preprint).
[2] J Hančl, A. Jaššová, P. Lertchoosakul, R. Nair: On the metric theory of
p-adic continued fractions, Indag. Math. (N.S.) 24 (2013), no. 1, 42-56.
[ 3] J. Hirsh, L.C. Washington: p-adic continued fractions, Ramanujan J. 25(3) (2011) 389-403.

49

sciencesconf.org:numeration2018:194191

Essentially non-normal numbers for Cantor
series expansions
Dylan Airey and Bill Mance and Roman Nikiforov

Denote by Nnb (B, x) the number of times a block B occurs with its starting position
no greater than n in the b-ary expansion of x.
A real number x is normal in base b if for all k and blocks B in base b of lengthk, one has
N b (B, x)lim n= b−k .
(1)n→∞n
A number x is simply normal in base b if (1) holds for k = 1.
Borel introduced normal numbers in 1909 and proved that almost all (in the senseof Lebesgue measure) real numbers are normal in all bases. Obviously that the complement of the set of normal numbers has zero Lebesque measure. But how small isthe compliment in fractal and topological sense?
Let consider a subset of set of non-normal numbers for which limit (1) does notexist for any individual digit. Such numbers called essentially non-normal numbers.
It was proven by Albeverio, Pratsiovytyi and Torbin in 2005 that this set has full
Hausdorff dimension and is of second Baire category. This result was extended for
different system of numeration with finite alphabet (Q-expansion, Q∗ -expansion)
and with infinite alphabet (Q∞ -expansion, I-Q∞ -expansion, Lüroth series expansion). We extend and generalize this result for large class of Cantor series expansion
considering numbers for which limit (1) does not exist for any block of digits for
all k. Furthermore the result still hold for the set of essentially non-normal numbers
whose Cantor series digits are sampled along all arithmetic progressions.
Dylan AireyPrinceton University, Fine Hall, Washington Road, Princeton NJ 08544-1000, USA, e-mail:dairey@math.princeton.edu
Bill Mance
Adam Mickiewicz University in Poznan, Wieniawskiego 1, 61-712 Poznan, Poland, e-mail:william.mance@amu.edu.pl
Roman Nikiforov
Dragomanov National Pedagogical University, Pyrogova St. 9, 01601, Kyiv, Ukraine, e-mail: rnikiforov@gmail.com

50

sciencesconf.org:numeration2018:196104

The Q-Cantor series expansions, first studied by G. Cantor, are a natural generalization of the b-ary expansions.
Let Nk := Z ∩ [k, ∞). If Q ∈ NN
2 , then we say that Q is a basic sequence. Givena basic sequence Q = (qn )∞,the
Q-Cantor series expansion of a real number
n=1
x ∈ [0, 1] is the unique expansion of the form∞En
n=1 q1 q2 · · · qn

x= ∑

(2)

where En is in {0, 1, . . . , qn − 1} for n ≥ 1 with En 6= qn − 1 infinitely often.
Let B = (b1 , b2 , . . . , bk ) is a block of digits of length k. Then for block B and anatural number j define(
1, if b1 < q j , b2 < q j+1 , . . . , bk < q j+k−1 ,IQ, j (B) =0, otherwise,
and letn

IQ, j (B).
qq
j=1 j j+1 . . . q j+k−1

Qn (B) = ∑Let NnQ (B, x) denote the number of occurrences of the block B in the digits of the
Q-Cantor series expansion of x up to position n.
A real number x is essentially non-normal if for all blocks B such lim Qn (B) = ∞n→∞the limit
NnQ (B, x)limn→∞ Qn (B)does not exist.

51

sciencesconf.org:numeration2018:196104

NUMBER SYSTEMS OVER ORDERS
EXTENDED ABSTRACT
ATTILA PETHŐ AND JÖRG THUSWALDNER

In this talk, which is based on our joint paper [23] we introduce a general notionof number system defined over orders of number fields. This generalizes the wellknown number systems and canonical number systems in number fields to relativeextensions and allows for the definition of “classes” of digit sets by the use oflattice tilings. It fits in the general framework of digit systems over commutative
rings defined by Scheicher et al. [25].
Before the beginning of the 1990s canonical number systems have been definedas number systems that allow to represent elements of orders (and, in particular,
rings of integers) in number fields. After the pioneering work of Knuth [16] andPenney [21], special classes of canonical number systems have been studied by Kátai
and Szabó [15], Kátai and Kovács [13, 14], and Gilbert [11], while elements of ageneral theory are due to Kovács [17] as well as Kovács and Pethő [18, 19]. In 1991
Pethő [22] gave a more general definition of canonical number systems that reads
as follows. Let p ∈ Z[x] be a monic polynomial and let D be a complete residue
system modulo p(0). The pair (p, D) was called a number system if each a ∈ Z[x]allows a representation of the form(1)a ≡ d0 + d1 x + · · · + d`−1 x`−1

(mod p)(d0 , . . . , d`−1 ∈ D).

If such an expansion exists it is unique if we forbid “leading zeros”, i.e., if wedemand d`−1 6= 0 for a 6≡ 0 (mod p) and take the empty expansion for a ≡ 0(mod p). It can be determined algorithmically by the so-called “backward division
mapping” (see e.g. [1, Section 3] or [25, Lemma 2.5]). Choosing the digit set
D = {0, 1, . . . , |p(0)| − 1}, the pair (p, D) was called a canonical number system,
CNS for short. An overview about the early theory of number systems can befound for instance in Akiyama et al. [1] and Brunotte, Huszti, and Pethő [7].
Let p ∈ Z[x] and let D be a complete residue system modulo p(0). With thedevelopment of the theory of radix representations it became necessary to notationally distinguish an arbitrary pair (p, D) from a particular pair (p, D) for which
each a ∈ Z[x] admits a representation of the form (1). Nowadays in the literature an arbitrary pair (p, D) is called number system (or canonical number system
if D = {0, 1, . . . , |p(0)| − 1}), while the fact that each a ∈ Z[x] admits a representation of the form (1) is distinguished with the suffix with finiteness property.
Although there exist many partial results on the characterization of number systems with finiteness property with special emphasis on canonical number systems(see for instance [2, 3, 5, 6, 8, 17, 26, 27]), a complete description of this property
seems to be out of reach (although there are fairly complete results for finite field
analogs, see for instance [4, 9, 20]).

52

sciencesconf.org:numeration2018:195980

If (p, D) is a number system and a ∈ Z[x] admits a representation of the form(1), we call ` the length of the representation of a in this number system (for a ≡ 0(mod p) this length is zero by definition).
In the present talk we generalize the CNS concept in two ways. Firstly, insteadof looking at polynomials in Z[x] we consider polynomials with coefficients in someorder O of a given number field of degree k, and secondly, we consider the sets ofdigits in a more general but uniform way. Indeed, for each fundamental domain Fof the action of Zk on Rk we define a class of number systems (p, DF ) where F
associates a digit set DF with each polynomial p ∈ O[x] in a natural way. Thus foreach fundamental domain F we can define a class GF := {(p, DF ) : p ∈ O[x]} ofnumber systems whose properties will be studied.
Our main objective will be the investigation of the finiteness property for thesenumber systems. For a given pair (p, D) this property can be checked algorithmically. This makes it possible to prove a strong bound for the length of therepresentations, provided it exists.
The “dominant condition”, a condition for the finiteness property of (p, D) thatinvolves the largeness of the absolute coefficient of p, has been studied for canonicalnumber systems in several versions for instance in Kovács [17, Section 3], Akiyama
and Pethő [2, Theorem 2], Scheicher and Thuswaldner [26, Theorem 5.8], andPethő and Varga [24, Lemma 7.3]. The main difficulty of the generalization of
the dominant condition is due to the fact that in O we do not have a naturalordering, hence, we cannot adapt the methods that were used in the case of integer
polynomials. However, by exploiting tiling properties of the fundamental domain
F we are able to overcome this difficulty, and provide a general criterion for thefiniteness property that is in the spirit of the dominant condition and can be usedin the proofs of our main results. In particular, using this criterion, depending on
natural properties of F we are able to show that (p(x + m), DF ) enjoys a finitenessproperty for each given p provided that m (or |m|) is large enough. This forms
a generalization of an analogous result of Kovács [17] to this general setting. We
also give a converse of this result in showing that (p(x − m), DF ) doesn’t enjoy thefiniteness property for large m if F has certain properties.
If p ∈ Z[x] is irreducible then Z[x]/(p) is isomorphic to Z[α] for any root α of p.
Thus in this case the finiteness property of (p, D) is easily seen to be equivalent to
the fact that each γ ∈ Z[α] admits a unique expansion of the form
(2)

γ = d0 + d1 α + · · · + d`−1 α`−1with analogous conditions on d0 , . . . , d`−1 ∈ D as in (1). In this case we sometimes
write (α, D) instead of (p, D). This relates number systems to the problem of power
integral bases of orders. Recall that the order O has a power integral basis, if there
exists α ∈ O such that each γ ∈ O can be written uniquely in the form
γ = g0 + g1 α + · · · + gk−1 αk−1with g0 , . . . , gk−1 ∈ Z. In this case O is called monogenic. The definitions of
number system with finiteness property (2) and power integral bases seem similar
and indeed there is a strong relation between them. Kovács [17, Section 3] provedthat the order O has a power integral basis if and only if it contains α such that(α, {0, . . . , |NQ(α)/Q (α)| − 1}) is a CNS with finiteness property. A deep result ofGyőry [12] states that, up to translation by integers, O admits finitely many power
integral bases and they are effectively computable. Combining this result of Győry

53

sciencesconf.org:numeration2018:195980

with the above mentioned theorem of Kovács [17, Section 3], Kovács and Pethő [18]proved that if 1, α, . . . , αk−1 is a power integral basis then, up to finitely many
possible exceptions, (α − m, N0 (α − m)), m ∈ Z is a CNS with finiteness property
if and only if m > M (α), where M (α) denotes a constant. A good overview overthis circle of ideas is provided in the book of Evertse and Győry [10].
Using this theorem we generalize the results of Kovács [17] and of Kovács andPethő [18] to number systems over orders in algebraic number fields. Our result is
not only more general as the earlier ones, but sheds fresh light to the classical case of
number systems over Z too. It turns out that under general conditions in orders ofalgebraic number fields the power integral bases and the bases of number systems
with finiteness condition up to finitely many, effectively computable exceptions
coincide. Choosing for example the symmetric digit set, the conditions satisfy
and, hence, power integral bases and number systems coincide up to finitely many
exceptions. This means that CNS are quite exceptional among number systems.
References[1] S. Akiyama, T. Borbély, H. Brunotte, A. Pethő, and J. M. Thuswaldner, Generalized
radix representations and dynamical systems. I, Acta Math. Hungar., 108 (2005), pp. 207–
238.
[2] S. Akiyama and A. Pethő, On canonical number systems, Theor. Comput. Sci., 270 (2002),
pp. 921–933.
[3] S. Akiyama and H. Rao, New criteria for canonical number systems, Acta Arith., 111(2004), pp. 5–25.
[4] T. Beck, H. Brunotte, K. Scheicher, and J. M. Thuswaldner, Number systems andtilings over Laurent series, Math. Proc. Cambridge Philos. Soc., 147 (2009), pp. 9–29.
[5] H. Brunotte, Characterization of CNS trinomials, Acta Sci. Math. (Szeged), 68 (2002),
pp. 673–679.
, A unified proof of two classical theorems on CNS polynomials, Integers, 12 (2012),[6]
pp. 709–721.
[7] H. Brunotte, A. Huszti, and A. Pethő, Bases of canonical number systems in quartic
algebraic number fields, J. Théor. Nombres Bordeaux, 18 (2006), pp. 537–557.
[8] P. Burcsi and A. Kovács, Exhaustive search methods for CNS polynomials, Monatsh.
Math., 155 (2008), pp. 421–430.
[9] G. Effinger, K. Hicks, and G. L. Mullen, Integers and polynomials: comparing the close
cousins Z and Fq [x], Math. Intelligencer, 27 (2005), pp. 26–34.
[10] J.-H. Evertse and K. Győry, Discriminant equations in Diophantine number theory, vol. 32
of New Mathematical Monographs, Cambridge University Press, Cambridge, 2017.
[11] W. J. Gilbert, Radix representations of quadratic fields, J. Math. Anal. Appl., 83 (1981),
pp. 264–274.
[12] K. Győry, On polynomials with integer coefficients and given discriminant. IV, Publ. Math.
Debrecen, 25 (1978), pp. 155–167.
[13] I. Kátai and B. Kovács, Kanonische Zahlensysteme in der Theorie der quadratischen algebraischen Zahlen, Acta Sci. Math. (Szeged), 42 (1980), pp. 99–107.
, Canonical number systems in imaginary quadratic fields, Acta Math. Acad. Sci.
[14]
Hungar., 37 (1981), pp. 159–164.
[15] I. Kátai and J. Szabó, Canonical number systems for complex integers, Acta Sci. Math.
(Szeged), 37 (1975), pp. 255–260.
[16] D. E. Knuth, An imaginary number system, Comm. ACM, 3 (1960), pp. 245–247.
[17] B. Kovács, Canonical number systems in algebraic number fields, Acta Math. Hungar., 37(1981), pp. 405–407.
[18] B. Kovács and A. Pethő, Number systems in integral domains, especially in orders ofalgebraic number fields, Acta Sci. Math. (Szeged), 55 (1991), pp. 286–299.
[19], On a representation of algebraic integers, Studia Sci. Math. Hungar., 27 (1992),
pp. 169–172.

54

sciencesconf.org:numeration2018:195980

[20] V. Laohakosol and U. Pintoptang, Lengths, periods and expansions of elements writtenwith respect to a digit system over Fq [x], Finite Fields Appl., 14 (2008), pp. 142–158.
[21] W. Penney, A “binary” system for complex numbers, J. ACM, 12 (1965), pp. 247–248.
[22] A. Pethő, On a polynomial transformation and its application to the construction of apublic key cryptosystem, in Computational number theory (Debrecen, 1989), de Gruyter,
Berlin, 1991, pp. 31–43.
[23] A. Pethő and J. M. Thuswaldner, Number systems over orders, submitted.
[24] A. Pethő and P. Varga, Canonical number systems over imaginary quadratic Euclidean
domains, Colloq. Math., 146 (2017), pp. 165–186.
[25] K. Scheicher, P. Surer, J. M. Thuswaldner, and C. E. Van de Woestijne, Digit systems
over commutative rings, Int. J. Number Theory, 10 (2014), pp. 1459–1483.
[26] K. Scheicher and J. M. Thuswaldner, On the characterization of canonical number systems, Osaka J. Math., 41 (2004), pp. 327–351.
[27] M. Weitzer, Characterization algorithms for shift radix systems with finiteness property,
Int. J. Number Theory, 11 (2015), pp. 211–232.
Department of Computer Science, University of Debrecen, H-4010 Debrecen, P.O.
Box 12, HUNGARY and, University of Ostrava, Faculty of Science, Dvořákova 7, 70103
Ostrava, CZECH REPUBLIC
E-mail address: Petho.Attila@inf.unideb.hu
Chair of Mathematics and Statistics, University of Leoben, Franz-Josef-Strasse 18,
A-8700 Leoben, AUSTRIA
E-mail address: Joerg.Thuswaldner@unileoben.ac.at55

sciencesconf.org:numeration2018:195980

FUNDAMENTAL DOMAINS FOR RATIONAL FUNCTION BASED DIGITSYSTEMS OF FORMAL LAURENT SERIES OVER FINITE FIELDS

M.J.C. LOQUIAS AND A.D.C. RODRIGUEZ?
Institute of Mathematics, College of Science, University of the Philippines Diliman
Abstract. Let F be a finite field. Digit systems for the residue class ring S of the ringF((x−1 , y −1 )) of formal Laurent series in two variables over F modulo a polynomial f in F[x, y]that is monic in both x and y were studied in [1]. In particular, fundamental domains withrespect to both x-digit and y-digit representations that induce a tiling of S were examined.
More recently, digit systems with rational base P/Q, where P, Q ∈ F[x] are coprime withdeg P > deg Q ≥ 0, for the field F((x−1 )) were introduced in [2]. These new digit systems may
be viewed as for the ring S formed from the polynomial f = Qy − P , which is not necessarily
monic in y. In this contribution, we obtain fundamental domains with respect to P/Q-digit
representations given by such digit systems and investigate some of their properties.

? Presenter

References
1. T. Beck, H. Brunotte, K. Scheicher, and J.M. Thuswaldner, Number systems and tilings over Laurent series,
Math. Proc. Camb. Phil. Soc. 147 (2009) 9–29.
2. M.J.C. Loquias, M. Mkaouar, K. Scheicher, and J.M. Thuswaldner, Rational digit systems over finite fields
and Christol’s Theorem, J. Number Theory 171 (2017) 358–390.

56

sciencesconf.org:numeration2018:195738

OPEN MAPS: SMALL AND LARGE HOLESNIKITA SIDOROVLet X be a compact manifold, T : X → X piecewise continuous withpositive entropy, and µ a T -invariant probability measure on X. Let
H be an open connected subset of X which we treat as a hole. Thenthe survivor set J(H) is the set of all x ∈ X whose T -orbits avoid H.
In my talk I will concentrate on the following questions:(i) If µ(H) is suﬃciently small, is it true that the Hausdorﬀ dimension of J(H) is positive?
(ii) If µ(H) is suﬃciently close to 1, is it true that J(H) is countable?
We will see that the answers strongly depend on whether X is onedimensional. My main examples will be the doubling map and the
baker’s map.
As it turns out, in the case of the doubling map and H = (a, b),
the critical holes are closely related to balanced words and Sturmian
sequences. For the baker’s map the situation is very diﬀerent, although
the Thue-Morse sequence appears to play a significant role as well.
This talk is based on my recent papers with Paul Glendinning (Manchester) and Kevin Hare (Waterloo).

57

sciencesconf.org:numeration2018:195699

THE LEVEL OF DISTRIBUTION OF THE THUE–MORSE SEQUENCELUKAS SPIEGELHOFER
Abstract. The level of distribution of a complex valued sequence b measures how well b
behaves on arithmetic progressions nd + a. Determining whether a given number θ is a levelof distribution for b involves summing a certain error over d ≤ D, where D depends on θ; thiserror is given by comparing a finite sum of b along nd + a and the expected value of the sum.
We prove that the Thue–Morse sequence has level of distribution 1, which is essentially best
possible. More precisely, this sequence gives one of the first nontrivial examples of a sequencesatisfying an analogue of the Elliott–Halberstam conjecture in prime number theory. In
particular, this result improves on the level of distribution 2/3 obtained by Müllner and theauthor.
Moreover, we show that the subsequence of the Thue–Morse sequence indexed by bnc c,where 1 < c < 2, is simply normal. That is, each of the two symbols appears with asymptotic
frequency 1/2 in this subsequence. This result improves on the range 1 < c < 3/2 obtainedby Müllner and the author and closes the gap that appeared when Mauduit and Rivat proved(in particular) that the Thue–Morse sequence along the squares is simply normal. In the
proofs, we reduce both problems to an estimate of a certain Gowers uniformity norm of theThue–Morse sequence similar to that given by Konieczny (2017).

1. Extended abstract
Let t be the Thue–Morse sequence N → {0, 1} defined by t(n) = 0 if and only if 2 | s(n),where s(n) is the binary sum-of-digits function. The main topic of this article is the study oft along arithmetic progressions and, more generally, along Beatty sequences bnα + βc. We areparticularly interested in the error term for sparse arithmetic progressions, having large common
difference d. This is the subject of our main result.
Theorem 1.1. Assume that ε > 0. ThenX

max max1≤d≤x1−ε0≤y≤x 0≤a<dX(−1)s(n) = O(x1−η )0≤n<yn≡a mod dfor some η > 0 depending on ε.
The formulation of this theorem is an analogue of the Elliott–Halberstam conjecture.
Conjecture (Elliott–Halberstam). For all real numbers A > 0 there exists a constant C suchthat for all x ≥ 2
X
π(x)
max
π(x; d, a) −≤ Cx(log x)−A .
0≤a<d
ϕ(d)
1−ε
1≤d≤x

gcd(a,d)=1

Here ϕ denotes Euler’s totient function, π(x) is the number of primes up to x, and π(x; d, a) is
the number of such primes that are ≡ a mod d.
Our result says that the Thue–Morse sequence has level of distribution 1, while the Elliott–
Halberstam conjecture states that the primes have level of distribution 1. It is known that 1/2
is a level of distribution of the primes (the Bombieri–Vinogradov theorem).

58

sciencesconf.org:numeration2018:198052

A level of distribution 0.55711 for the sum of digits in base 2 modulo m (and also a level
0.5924 for Thue–Morse) was obtained by Fouvry and Mauduit [2]. Using sieve theory, they
applied this result to the study of s(n) mod m for positive integers n having at most two prime
factors. They also considered [1] the sum of digits in base q modulo m, where gcd(m, q − 1) = 1
and obtained the result that the level of distribution approaches 1 as the base q grows.
Later, in an important paper, Mauduit and Rivat [6] could handle the sum of digits of prime
numbers.
Theorem 1.1 seems to be one of the first examples of a sequence with level of distribution
equal to 1. More precisely, it is one of the first such examples where we have a maximum
over a inside the sum over d; therefore the formulation “analogue of the Elliott–Halberstam
conjecture”.
Our second result concerns the Thue–Morse sequence on Piatetski-Shapiro sequences bnc c.
Theorem 1.2. Let 1 < c < 2. The Thue–Morse sequence along bnc c is simply normal. Thatis, each of the letters 0 and 1 appears with asymptotic frequency 1/2 in n 7→ t(bnc c).
The two main theorems are connected. More precisely, by the same method of proof used
for Theorem 1.1, we prove a Beatty sequence analogue; this analogue can be used to prove
Theorem 1.2 using linear approximation of bnc c by bnα + βc.
Theorem 1.3. We defineA(y, z; α, β) = y ≤ m < z : t(m) = 0 and ∃n ∈ Z such that m = bnα + βc .
Let 0 < θ1 ≤ θ2 < 1. There exist η > 0 and C such thatZ 2Dz−ydα ≤ Cx1−ηmax
max A(y, z; α, β) −
y,z
β≥0
2α
D
0≤y≤z
z−y≤x

for all x and D such that x ≥ 1 and xθ1 ≤ D ≤ xθ2 .
The method of approximation of bnc c by bnα + βc for proving theorems like Theorem 1.2
has been discussed in length in the earlier articles [8] by the author and [7] by Müllner and theauthor. In those articles, we obtained the ranges 1 < c ≤ 1.42 and 1 < c < 1.5 respectively,
improving on the range 1 < c < 1.4 obtained by Mauduit and Rivat [4].
Mauduit and Rivat [5], in another major paper, showed (in particular) that the Thue–Morsesequence along n2 is simply normal.
Theorem 1.2 therefore closes the gap [1.5, 2) in the set of exponents for which we have an
asymptotic formula for Thue–Morse along bnc c.
In the present article, we restrict ourselves to giving an outline of the proof of Theorem 1.1.
1.1. Idea of proof of Theorem 1.1. As in our earlier paper with Müllner [7, Section 4.1], it
is sufficient to prove the following result.
Proposition 1.4. For real numbers N, D ≥ 1 and ξ set
S0 = S0 (N, D, ξ) =X

D≤d<2D

max
a≥0

X

0≤n<N

e




1
s(nd + a) e(nξ) ,2where e(x) = exp(2πix). Let ρ2 ≥ ρ1 > 0. There exists an η > 0 and a constant C such thatS0
≤ CN −ηND
holds for all ξ ∈ R and all real numbers N, D ≥ 1 satisfying N ρ1 ≤ D ≤ N ρ2 .

59

sciencesconf.org:numeration2018:198052

It is sufficient to prove this for D = 2ν . By Cauchy–Schwarz, followed by van der Corput’s
inequality, moreover by using a “carry propagation lemma” (e.g. [7, Lemma 3.6]) we obtain2ν N X
2
S0 (N, 2ν , ξ) R0
1≤r0 <R0
!
X
X
 1

1
e
sup
×
+ errors,sλ (n + r0 )d + a − sλ nd + a
22
ν
ν+1 a≥00≤n<N

2 ≤d<2where sλ is the “truncated sum-of-digits function” defined by sλ (n) = s(n mod 2λ ). We apply
the inequalities of Cauchy–Schwarz and van der Corput alternatingly m times, and obtain
2m+1

S0 (N, 2ν , ξ)
2ν N

(1.1)



X

1
R0 2mρ 2ν N

X

1≤r0 <R00≤d<2λ0≤ri <2ρ ,1≤i≤m

sup S1 + errors,
a≥0

where
S1 =

X

0≤n<N

1
e
2

X

ε0 ,...,εm ∈{0,1}sλ nd + a + ε0 r0 d + ε1 r1 K1 d + · · · + εm rm Km d!

and λ > ν is chosen later in the proof.
Now we choose the multiples K1 , . . . , Km in such a way that the number of digits to be taken
into account is reduced from λ to ρ := λ − (m + 1)µ, where µ and m are chosen later. For thiswe use Farey series. Let pQ (α)/qQ (α) be the element of the Farey series FQ associated to α (seee.g. [7]) and set
2µK1 = 2 q2σ





d

;
2(m−1)µ
p2µ+2σ d/2(i+1)µd
Ki = q2µ+2σ
q2σ
for 2 ≤ i < m;2(i+1)µ2(m−i)µdKm = q2µ+σ,2(m+1)µ

where σ is chosen later. Using the approximation property |qQ (α)α − pQ (α)| < 1/Q, we seethat Ki α/2iµ is close to a multiple of 2µ for 2 ≤ i ≤ m. Using this, and the discrepancy ofnα-sequences modulo 1, we cut off µ many digits at a time (2µ many in the first step) andobtainS1 = S2 + errors,
where


!
X
X
X
1
nd + aε0 r0 dS2 =esλ−(m+1)µ+ (m+1)µ +εi ri pi,22(m+1)µ
2
0≤n<N
1≤i≤m
ε0 ,...,εm ∈{0,1}andp1 = p2σ
(1.2)



d
2(m−1)µ;

p2µ+2σ d/2(i+1)µpi = p2σ2(m−i)µdpm = p2µ+σ.
2(m+1)µ60

!

for 2 ≤ i < m;sciencesconf.org:numeration2018:198052

For simplicity of argument, assume that the second summand in the floor function in thedefinition of S2 is not present, and write Se2 for the resulting expression. Using the usually
very small discrepancy of nα-sequences, and choosing m large enough, we see that the sequenceb(nd + a)/2(m+1)µ c runs through all the residue classes mod 2ρ , where ρ = λ − (m + 1)µ, in avery uniform way. Therefore
!

X
X
X
N
1
εi ri pi
+ errors.
esρ k +
Se2 = ρ
2
2
ρ
0≤k<2

ε1 ,...,εm ∈{0,1}1≤i≤m

We note the important fact that this expression is independent of the residue class a + dZ.
This allows us to remove the maximum over a inside the sum over d, and thus prove the strong
statement on the level of distribution.
Using the identity (1.1), we see that we have to treat the sum
X
X
Se2 .
Se3 =
0≤d<2λ 0≤r1 ,...,rm <2ρ

At this point, we apply the argument that for most α < 2λ the 2-valuation of p1 , . . . , pm issmall. (This is established by a technical lemma that we do not present here.) For these α, theterm ri pi mod 2ρ attains each k ∈ {0, . . . , 2ρ − 1} not too often, as ri runs. We may therefore
replace ri p1 by ri and thus obtain full sums over ri . It remains to estimate the expression



X
X
X
X
1
e
sρ n +
εi ri  .
2
ρρ0≤r1 ,...,rm <20≤n<2ε1 ,...,εm ∈{0,1}1≤i≤mUsing Cauchy–Schwarz, the absolute value can be removed at the cost of an additional variable
rm+1 . The problem is therefore reduced to proving a nontrivial estimate for the sum



X
X
X
X
1
sρ n +
εi ri  .
e2ρρ0≤r1 ,...,rm+1 <2 0≤n<2ε1 ,...,εm+1 ∈{0,1}1≤i≤m+1

This is a Gowers uniformity norm for the Thue–Morse sequence; a very similar estimate wasgiven by Konieczny [3], and we use ideas from that paper to prove our estimate. This finishes
the proof.
References[1] E. Fouvry and C. Mauduit, Méthodes de crible et fonctions sommes des chiffres, Acta Arith., 77 (1996),
pp. 339–351.
[2], Sommes des chiffres et nombres presque premiers, Math. Ann., 305 (1996), pp. 571–599.
[3] J. Konieczny, Gowers norms for the Thue-Morse and Rudin-Shapiro sequences, 2017. Preprint,
http://arxiv.org/abs/1611.09985.
[4] C. Mauduit and J. Rivat, Propriétés q-multiplicatives de la suite bnc c, c > 1, Acta Arith., 118 (2005),
pp. 187–203.
[5], La somme des chiffres des carrés, Acta Math., 203 (2009), pp. 107–148.
[6], Sur un problème de Gelfond: la somme des chiffres des nombres premiers, Ann. of Math. (2), 171(2010), pp. 1591–1646.
[7] C. Müllner and L. Spiegelhofer, Normality of the Thue–Morse sequence along Piatetski-Shapiro sequences, II, Israel J. Math., 220 (2017), pp. 691–738.
[8] L. Spiegelhofer, Piatetski-Shapiro sequences via Beatty sequences, Acta Arith., 166 (2014), pp. 201–229.
Institute of Discrete Mathematics and Geometry, Vienna University of Technology, Wiedner
Hauptstrasse 8–10, 1040 Vienna, Austria

61

sciencesconf.org:numeration2018:198052

Some negative results related to Poissonian paircorrelation problems
Gerhard Larcher, Wolfgang Stockinger
Abstract
We say that a sequence (xn )n∈N in [0, 1) has Poissonian pair correlations if
1 n
so
lim
# 1 ≤ l 6= m ≤ N : kxl − xm k ≤= 2s
N →∞ NN

for every s ≥ 0. The aim of this talk is twofold. First, we will establish
a gap theorem which allows to deduce that a sequence (xn )n∈N of real
numbers in [0, 1) having a certain weak gap structure, cannot have Poissonian pair correlations. This result covers a broad class of sequences,e.g., Kronecker sequences, the van der Corput sequence and in more general LS-sequences of points and digital (t, 1)-sequences. Additionally, thistheorem enables us to derive negative pair correlation properties for sequences of the form ({an α})n∈N , where (an )n∈N is a strictly increasing
sequence of integers with maximal order of additive energy, a notion thatplays an important role in many fields, e.g., additive combinatorics, and isstrongly connected to Poissonian pair correlation problems. These statements are not only metrical results, but hold for all possible choices ofα.
Second, we study the pair correlation statistics for sequences of theform, xn = {bn α}, n = 1, 2, 3, . . ., with an integer b ≥ 2, where we choose
α as the Stoneham number and as an infinite de Bruijn word.

1

Introduction and statement of main results

The concept of Poissonian pair correlations has its origin in quantum mechanics, where the spacings of energy levels of integrable systems were studied. Seefor example [1] and the references cited therein for detailed information on that
topic. Rudnik and Sarnak first studied this concept from a purely mathematicalpoint of view and over the years the topic has attracted wide attention, see e.g.,[7, 14, 15, 16, 17].
Let k · k denote the distance to the nearest integer. A sequence (xn )n∈Nof real numbers in [0, 1) has Poissonian pair correlations if the pair correlation
statistics
so
1 n
(1)
FN (s) := # 1 ≤ l 6= m ≤ N : kxl − xm k ≤NN62sciencesconf.org:numeration2018:195542

tends to 2s, for every s ≥ 0, as N → ∞.
Recently, Aistleitner, Larcher, Lewko and Bourgain (see [2]) could give astrong link between the concept of Poissonian pair correlations and the additiveenergy of a finite set of integers, a notion that plays an important role in manymathematical fields, e.g., in additive combinatorics. To be precise, for a finite
set A of reals the additive energy E(A) is defined as
X
E(A) :=
1,
a+b=c+dwhere the sum is extended over all quadruples (a, b, c, d) ∈ A4 . Roughly speaking, it was proved in [2] that if the first N elements of an increasing sequence ofdistinct integers (an )n∈N , have an arbitrarily small energy saving, then ({an α})n∈N
has Poissonian pair correlations for almost all α. In this paper the authors also
raised the question if ({an α})n∈N , where (an ) is an increasing sequence of distinct integers with maximal order of additive energy, can have Poissonian paircorrelations for almost all α. Jean Bourgain could show that the answer to thisquestion is negative, i.e., he proved:
Theorem A (in [2]) If E(AN ) = Ω(N 3 ), where AN denotes the first N elements of (an )n∈N , then there exists a subset of [0, 1] of positive measure such thatfor every α from this set the pair correlations of ({an α})n∈N are not Poissonian.
Recently, the result of Bourgain has been further extended, see [1, 9, 10, 11].
The result given in [10] is an easy consequence of our Theorem 1 stated below
and will be shown in Section 2. Further, see [4, 5] for (negative) results anddiscussions concerning a Khintchine type criterion which fully characterizes themetric pair correlation property in terms of the additive energy.
Due to a result by Grepstad and Larcher [6] (see also [3, 19]), we know thata sequence which satisfies that (1) tends to 2s, for every s ≥ 0, as N → ∞, isalso uniformly distributed in [0, 1), i.e., it satisfieslim

1

N →∞ N#{1 ≤ n ≤ N : xn ∈ [a, b)} = b − a

for all 0 ≤ a < b ≤ 1. Note that the other direction is not necessarily correct.
For instance the Kronecker sequence ({nα})n∈N is uniformly distributed modulo
1 for irrational α, but does not have Poissonian pair correlations for any real α;a fact that easily follows from continued fractions arguments. In earlier papers(see e.g., [2, 17]) this fact was argued to be an immediate consequence of theThree Gap Theorem [18]. The Three Gap Theorem, roughly speaking, statesthat the Kronecker sequence always has at most three distinct distances between
nearest sequence elements. Nonetheless – at least for us – it is not immediately
clear that we can deduce from this fact that ({nα})n∈N is not Poissonian for any
α. Therefore, we will prove the following very general result concerning the link
between Poissonian pair correlations and a certain gap structure of a sequence63

sciencesconf.org:numeration2018:195542

in the unit interval. In the next section, we will present some applications of
this Theorem 1.
Theorem 1 Let (xn )n∈N be a sequence in [0, 1) with the following property:
There is an s ∈ N, positive real numbers K and γ, and infinitely many N suchthat the point set x1 , . . . , xN has a subset with M ≥ γN elements, denoted by
xj1 , . . . , xjM , which are contained in a set of points with cardinality at most KN
having at most s different distances between neighbouring sequence elements, socalled gaps. Then, (xn )n∈N does not have Poissonian pair correlations.
Poissonian pair correlation is a typical property of a sequence. Random sequences, i.e., almost all sequences, have the Poissonian pair correlation property. Nevertheless, it seems to be extremely difficult to give explicit
examples of√sequences with Poissonian pair correlations. We note that ({ n})n∈N has Poissonian pair correlations, [12] (see [13] for another explicit construction). Apartfrom that – to our best knowledge – no other explicit examples are known.
Especially, until now we do not know any single explicit construction of a real
number α such that the sequence of the form ({an α})n∈N has Poissonian paircorrelations.
We recall that the sequence ({bn α})n∈N , for an integer b ≥ 2, has the Poissonian property for almost all α. Moreover we know that the sequence ({bn α})n∈N
is uniformly distributed modulo 1 if and only if α is normal in base b, see e.g., [8].
So, if we want to investigate, whether the distribution of the pair correlations
for some explicit given sequence is Poissonian, the sequence has to be uniformly
distributed modulo 1. Therefore, if we study the distribution of the spacings
between the sequence elements of ({bn α})n∈N , the only reasonable choice for α
is a b-normal number. We will present two special instances, which were suggested by Yann Bugeaud as potential candidates in personal communication.
We will consider so-called infinite de Bruijn words and Stoneham’s number. For
these instances, we also obtained negative results considering the Poissonian
pair correlation structure.

References[1] I. Aichinger, C. Aistleitner and G. Larcher, On Quasi-Energy-Spectra, Pair
Correlations of Sequences and Additive Combinatorics, Celebration of the80th birthday of Ian Sloan (J. Dick, F. Y. Kuo, H. Woźniakowski, eds.),
Springer-Verlag, to appear, 2018.
[2] C. Aistleitner, G. Larcher and M. Lewko, Additive energy and the Hausdorff
dimension of the exceptional set in metric pair correlation problems. Withan appendix by Jean Bourgain, Israel J. Math., 222 (2017) No. 1, 463-485.
[3] C. Aistleitner, T. Lachmann, and F. Pausinger, Pair correlations andequidistribution, arXiv:1612.05495, 2017. To appear in: Journal of Number Theory.

64

sciencesconf.org:numeration2018:195542

[4] C. Aistleitner, T. Lachmann, and N. Technau, There is no Khintchine
threshold for metric pair correlations, arXiv:1802.02659, 2018.
[5] T. Bloom, S. Chow, A. Gafni and A. Walker, Additive energy and the metric
Poissonian property, arXiv:1709.02634, 2017.
[6] S. Grepstad and G. Larcher, On Pair Correlation and Discrepancy, Arch.
Math. 109, 143-149, 2017.
[7] D. R. Heath-Brown, Pair correlation for fractional parts of αn2 , Math.
Proc. Cambridge Philos. Soc., 148(3):385-407, 2010.
[8] L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Wiley,
New York, 1974.
[9] T. Lachmann and N. Technau, On Exceptional Sets in the Metric Poissonian Pair Correlations problem, arXiv:1708.08599, 2017.
[10] G. Larcher, Remark on a result of Bourgain on Poissonian pair correlation,
arXiv:1711.08663, 2017.
[11] G. Larcher and W. Stockinger, Pair correlation of sequences ({an α})n∈N
with maximal order of additive energy, arXiv:1802.02901, 2018.
[12] D. El-Baz, J. Marklof and I. Vinogradov,
The two-point correlation func√tion of the fractional parts of n is Poisson, Proceedings of the American
Mathematical Society 143 (7), 2815-2828, 2015.
[13] D. El-Baz, J. Marklof and I. Vinogradov, The distribution of directions in
an affine lattice: two-point correlations and mixed moments, International
Mathematics Research Notices, vol 2015., 1371-1400, 2015.
[14] R. Nair and M. Pollicott, Pair Correlations of sequences in higher dimensions, Israel J. Math. 157, 219238, 2007.
[15] Z. Rudnick and A. Zaharescu, A metric result on the pair correlation of
fractional parts of sequences, Acta Arith., 89(3):283-293, 1999.
[16] Z. Rudnick, P. Sarnak and A. Zaharescu, The distribution of spacings between the fractional parts of n2 α, Invent. Math., 145(1):37-57, 2001.
[17] Z. Rudnick and P. Sarnak, The pair correlation function of fractional partsof polynomials, Comm. Math. Phys., 194(1):61-70, 1998.
[18] V. T. Sós, On the distribution mod 1 of the sequence nα, Ann. Univ. Sci.
Budap. Rolando Eötvös, Sect. Math., 1:127-134, 1958.
[19] S. Steinerberger, Localized Quantitative Criteria for Equidistribution, Acta
Arith., 180:183–199, 2017.

65

sciencesconf.org:numeration2018:195542

SYMMETRIC AND CONGRUENT RAUZY FRACTALSPAUL SURER

Based on a joint work with K. Scheicher and V. Sirvent
Let A = {1, 2, . . . , m} be a finite set (alphabet) and A∗ the finite words over A. We
denote by σ a morphism A∗ −→ A∗ that we require to be primitive, hence, there
exists a power n such that for each two letters i, j ∈ A the word σ n (j) contains i
at least once.
Primitivity ensures that the matrix Mσ = (|σ(j)|i )1≤,i,j≤m (where |σ(j)|i denotes the number of occurrences of i in the word σ(j)) possesses a dominant real
eigenvalue β. We are interested in unimodular Pisot substitutions, that is β is a
Pisot unit of algebraic degree d + 1 (thus, d + 1 ≤ m). In this case it is well known
that we can associate to σ a compact set Rσ ⊂ Rd of fractal shape known as Rauzy
fractal (see, for example, [2, 3]).
Given unimodular Pisot substitutions σ, τ we are interested in the following
problems:• Which conditions ensure the associated Rauzy fractals Rσ , Rτ to be congruent (that is they differ by an affine transformation only)?
• Which conditions ensure that the Rauzy fractal Rσ is central symmetric?
We discuss the questions in terms of the induced language. For a primitive substitution σ it is defined by
Lσ := {A ∈ A∗ | ∃n ≥ 1 : A is a subword of σ n (1)}.

Therefore, our discourse involves a lot of combinatorics on words. Concretely wehave the following two main results.
Theorem (cf. [5]). Let σ and τ be irreducible Pisot substitutions (i.e. d + 1 =m) over the same alphabet A. If Lσ = Lτ then the Rauzy fractals Rσ , Rτ arecongruent.
For irreducible substitutions we need additional conditions.
For a word A ∈ A∗ we denote by Ã the reversed word (or mirror-word). We
call a set L ⊂ A∗ mirror-invariant if for each A ∈ L we have Ã ∈ L. With thesenotations we can state the following theorem concerning central symmetric Rauzy
fractals.
Theorem (cf. [5]). Let σ be a Pisot substitutions over A. If Lσ is mirror-invariant
then the Rauzy fractals Rσ is central-symmetric.
Based on these two theorems we will present concrete classes of substitutions
that yield congruent or central-symmetric Rauzy fractals. For these classes we will
be able to give explicit expressions for the respective translation and the point
Key words and phrases. Substitutions; Rauzy fractals; Combinatorics on words.

66

sciencesconf.org:numeration2018:195970

of symmetry, respectively. Furthermore, we analyse whether the conditions in ourtheorems are necessary. We will see that the topic is related with up to now unsolved
problems as the Pisot conjecture (see for example [1]) and the Class P conjecturestated in [4]. The presentation will be accompanied by illustrative examples.
References[1] S. Akiyama, M. Barge, V. Berthé, J.-Y. Lee, and A. Siegel, On the Pisot substitution conjecture, in Mathematics of Aperiodic Order, vol. 309 of Progress in Mathematics, Birkhäuser,
2015, pp. 33–72.
[2] P. Arnoux and S. Ito, Pisot substitutions and Rauzy fractals, Bull. Belg. Math. Soc. Simon
Stevin, 8 (2001), pp. 181–207. Journées Montoises d’Informatique Théorique (Marne-la-Vallée,2000).
[3] V. Berthé and A. Siegel, Tilings associated with beta-numeration and substitutions, Integers,
5 (2005), pp. A2, 46 pp. (electronic).
[4] A. Hof, O. Knill, and B. Simon, Singular continuous spectrum for palindromic Schrödinger
operators., Commun. Math. Phys., 174 (1995), pp. 149–159.
[5] K. Scheicher, V. F. Sirvent, and P. Surer, Symmetric and congruent Rauzy fractals.,Indag. Math., New Ser., 27 (2016), pp. 799–820.
Institut für Mathematik, Universtiät für Bodenkultur (BOKU), Gregor-MendelStraße 33, 1180 Wien, Austria
E-mail address: paul@surer.at
URL: http://www.palovsky.com

67

sciencesconf.org:numeration2018:195970

Digital questions in finite fields
Cathy Swaenepoel
Université d’Aix-Marseille

The connection between the arithmetic properties of an integer andthe properties of its digits in a given basis produces a lot of interestingquestions and many papers have been devoted to this topic. In thecontext of finite fields, the algebraic structure permits to formulate
and study new problems of interest which might be out of reach in N.
This study was initiated by C. Dartyge and A. Sárközy.
We will devote our interest to several new questions in this spirit:(1) estimate precisely the number of elements of some special sequences of Fq whose sum of digits is fixed;(2) given subsets C and D of Fq , find conditions on |C| and |D| toensure that there exists (c, d) ∈ C × D such that the sum ofdigits of cd belongs to a predefined subset of Fp ;(3) estimate the number of elements of an interesting sequence of
Fq with preassigned digits.
We notice that the notion of digits in Fq is directly related to the notionof trace which is crucial in the study of finite fields.

68

sciencesconf.org:numeration2018:201764

SOME NEWS ON RATIONAL SELF-AFFINE TILES
J. M. THUSWALDNER

Let A be an expanding d×d integer matrix and D ⊂ Zd a complete set of residue
class representatives of Zd /AZd . Then by a classical result of Hutchinson one canuniquely define a nonempty compact set T by the set equation
AT = T + D.

The set T is called a self-affine tile. Self-affine tiles have been studied extensively
in the literature. An important result by Lagarias and Wang from 1997 states thatsuch tiles form a lattice tiling w.r.t. the lattice Zd under very general conditions.
Together with Steiner we gave a generalization of this result to self-affine tiles
defined in terms of rational matrices with irreducible characteristic polynomial. In
the proofs of this generalization we used tools from algebraic number theory. In an
ongoing work with Jankauskas and Steiner we want to get rid of the irreducibility
condition. To this end we use methods from linear algebra and harmonic analysis.

69

sciencesconf.org:numeration2018:195885

Indecomposable integers and universal quadratic
forms
Magdaléna Tinková (with M. Čech, D. Lachman, J. Svoboda and K. Zemková)Department of Algebra, Charles University,
Sokolovská 83, 175 86 Praha 8, Czech Republic
tinkova.magdalena@gmail.com

This work focuses on the ring of algebraic integers OK of totally real fields K and thesemigroup OK+ of totally positive integers. In this structure, we can define so-called
indecomposable integers, elements of OK+ which cannot be expressed as a sum of
two totally positive integers. It is also not hard to see that each element of OK+ can be
written as a sum of finitely many indecomposables. In connection to number systems,
we can express totally positive√ numbers using the indecomposable integers as a base.
In quadratic fields Q( D), there werecharacterized all indecomposable integers√√
D−1using the continued fraction of D or 2 , see [14, 5]. In the second article, theauthors also found the upper bound on the norm of indecomposables, which wasrefined in [7]. We do not have such a characterization for fields of higher degrees.
However, in [3], there was derived a bound on norms. This bound can be greatly
improved in the quadratic case [5, 10] and we will discuss some original results
related to these estimates.
The indecomposable integers are closely related to quadratic forms. By this, wemean
Q(x1 , x2 , . . . , xn ) = ∑ ai j xi x j
1≤i≤ j≤nwhere ai j ∈ OK and x1 , x2 , . . . , xn are variables. We focus on totally positive definite
forms, i.e., Q(γ1 , . . . , γn ) is totally positive for all γi ∈ OK such that our n-tuples are
not equal to zero.
Our form is called universal if it represents each element of OK+ . For example,2
x1 + x22 + x32 + x42 is universal over Z. Moreveover, in [16], there was√ proved that thesum of any number of squares is universal only over Q and Q( 5). Other results
we can see in [4, 2, 12]. The indecomposable integers play an important role in the
study of universal quadratic forms, since they are difficult to represent and we often
use them as coefficients of our forms.
√ √In biquadratic fields Q( p, q), we focus on the question whether the indecom√ √posable integers from quadratic subfields remain indecomposable in Q( p, q).
The following theorem shows one of our results, which can be improved under certain conditions.

70

sciencesconf.org:numeration2018:195724

√ √pq
Theorem 1. Let Q( p, q) be a biquadratic field, and let r = gcd(p,q)
2 . Set√p
if p ≡ 2, 3 (mod 4),
δ p = √ p−1
if
p ≡ 1 (mod 4).
2

If

√
√
r > p max{ui ; i odd, [u0 , u1 , u2 , . . . , us−1 , us ] is the continued fraction of δ p },√√ √then the indecomposable integers from Q( p) are indecomposable in Q( p, q).

We will also discuss how we can use our knowledge of indecomposable integers
in biquadratic fields for the study√ √of universal forms, in particular, we can show thateach universal form over Q( 6, 19) must have at least 6 variables.
Acknowledgement. This work was supported by Czech Science Foundation (GAČR), grant17-04703Y, by the Charles University, project GA UK No 1298218, and by the project SVV2017-260456.

References
1. M. Bhargava and J. Hanke, Universal quadratic forms and the 290 - theorem, preprint.
2. V. Blomer and V. Kala, Number fields without n-ary universal quadratic forms, Math.
Proc. Cambridge Philos. Soc., 159(2):239-252, 2015.
3. H. Brunotte, Zur Zerlegung totalpositiver Zahlen in Ordnungen totalreeller algebraischer
Zahlkrper, Arch. Math. (Basel) 41 (1983), no. 6, 502503.
4. W. K. Chan, M.-H. Kim, S. Raghavan, Ternary universal integral quadratic forms, Japan.
J. Math. 22 (1996), 263-273.
5. A. Dress and R. Scharlau, Indecomposable totally positive numbers in real quadraticorders, J. Number Theory 14 (1982), 292-306.
6. T. Hejda and V. Kala, Additive structure of totally positive quadratic integers, 12 pp.,submitted.
7. S. W. Jang and B. M. Kim, A refinement of the Dress-Scharlau theorem, J. Number Theory
158 (2016), 234-243.
8. F. Jarvis, Algebraic Number Theory, Springer, 2007.
9. V. Kala, Universal quadratic forms and elements of small norm in real quadratic fields,
Bull. Aust. Math. Soc. 94 (2016), 7-14.
10. V. Kala, Norms of indecomposable integers in real quadratic fields, J. Number Theory
166 (2016), 193-207.
11. A. Ya. Khinchin, Continued fractions, Translated from the third (1961) Russian edition,
Reprint of the 1964 translation, Dover, Mineola, NY, 1997.
12. V. Kala and J. Svoboda, Universal quadratic forms over multiquadratic fields, RamanujanJ., to appear.
13. M. Mazur & S. V. Ullom. Galois module structure of units in real biquadratic number
fields. Acta Arithmetica 111.2 (2004): 105-124. http://eudml.org/doc/278051
14. O. Perron, Die Lehre von den Kettenbrchen, B. G. Teubner, 1913.
15. A. E. Ross, On representation of integers by quadratic forms, Proc. Nat. Acad. Sci. 18(1932), 600-608.
16. C. L. Siegel, Sums of m-th powers of algebraic integers, Ann. Math. 46 (1945), 313-339.
17. K. S. Williams, Integers of biquadratic fields, Canad. Math. Bull. Vol. 13 (1970), 519-526.

71

sciencesconf.org:numeration2018:195724

Lenticular Poles of the Dynamical Zeta Function ofthe β -shift for Simple Parry Numbers Close to One
Denys Dutykh and Jean-Louis Verger-Gaugry∗
Univ. Grenoble Alpes, Univ. Savoie Mont Blanc, CNRS, LAMA,
F-73000 Chambéry, France∗ Corresponding author’s email: Jean-Louis.Verger-Gaugry@univ-smb.fr

Abstract. The distribution of the conjugates and the β −conjugates of simple PARRY’s numbers in S OLOMYAK’s fractal is revisited in the case where the base of numeration β > 1 isclose to one. We focus on the class B of polynomials of the typef (x) = −1 + x + x n + x m 1 + . . . + x m s ,s > 1,

n > 2,

with m 1 − n > n − 1 , m q+1 − m q > n − 1 , q = 1, 2, . . . , s − 1 . They are polynomials sections of PARRY Upper functions associated with the dynamical zeta functions of the β −shift,
in the R ÉNYI -PARRY dynamical system in base β . This work has two objectives: (i) to showthat there exists an asymptotic “reducibility Conjecture” for the polynomials of the class B in
the context of O DLYZKO –P OONEN’s Conjecture, which provides an asymptotics on the typeof β −conjugates, this reducibility conjecture is empirically supported by extensive M ONTE C ARLO simulations, (ii) to establish new theorems of factorization of the polynomials of theclass B , by comparison with the general theorems of S CHINZEL related to the reducibility oflacunary polynomials. In particular, in the search of reciprocal integer polynomials having asmall M AHLER measure by the PARRY Upper function we will show the existence of lenticuli
of roots, described by divergent series (asymptotic expansions à la P OINCAR É), in the region of
the cusp of S OLOMYAK’s fractal and indicate how they are related to the problem of L EHMER.

72

sciencesconf.org:numeration2018:194409

AN EFFECTIVE CRITERION FOR PERIODICITY OF `-ADIC CONTINUEDFRACTIONSFRANCESCO VENEZIANO(JOINT WORK WITH L. CAPUANO AND U. ZANNIER)

Extended abstract
The theory of real continued fractions plays a central role in real Diophantine Approximation
for many different reasons, in particular because the convergents of the simple continued fraction
expansion of a real number α give the best rational approximations to α. Motivated by the same
type of questions, several authors (see for example Mahler [Mah34], Schneider [Sch70], Ruban[Rub70], Bundschuch [Bun77], and Browkin [Bro78]) have generalized the theory of real continued
fractions to the `-adic case in various ways.
There is not a canonical way to define a continued fraction expansion in this context, as we lacka canonical `-adic analog of the integral part. The `-adic process which is the most similar to theclassical real one was mentioned for the first time in one of the earliest papers on the subject byMahler [Mah34], and then studied accurately by Ruban [Rub70], who showed that these continued
fractions enjoy nice ergodic properties.
Ruban’s continued fractions will be the subject of this talk and they have many importantdifferences with respect to the classical real ones. First of all, while some rational numbers have afinite expansion, this is not — unlike the real case — the only possible behaviour. For example, it iseasy to see that negative rational numbers cannot admit a terminating Ruban continued fraction.
It is however possible to decide when a given rational number admits a finite Ruban continued
fraction expansion and indeed our first result is the following:
Theorem 1. Let ` be a prime number and α ∈ Q be a rational number.
(i) The Ruban continued fraction expansion of α terminates if and only if all complete quotientsare non-negative; there is an algorithm to decide in a finite number of steps whether thishappens.
(ii) If the Ruban continued fraction expansion of α does not terminate, then it is periodic withall partial quotients eventually equal to ` − `−1 ; in this case, the pre-periodic part can beeffectively computed.
Disregarding the computability aspect, the last part of this result has already appeared in theliterature, due to Laohakosol and, independently, to Wang (see [Lao85] and [Wan85]), but thisdoes not seem to be the case for either of the algorithmic conclusions, which apparently do notfollow directly from the proofs in [Lao85] and [Wan85]. For completeness, we have also included
our own (short) proof of the qualitative part, which is quite different.
The conclusion of Theorem 1 depends of course on the precise algorithm defining the continued
fraction expansion. In [Bro78], Browkin modified Ruban’s definition so that every rational number
has a finite `-adic continued fraction expansion.
Another natural question arises when one considers the periodicity of Ruban continued fractions.
In the classical real case, Lagrange’s theorem states that a real number has an infinite periodic
continued fraction if and only if it is quadratic irrational. We will show that this is not true in the`-adic case and only some similarities can be recovered. For example we prove the following result:
Theorem 2. A Ruban continued fraction which is periodic represents an element of Q` which iseither a rational number or a real quadratic irrational over Q.
2010 Mathematics Subject Classification. 11J70, 11D88, 11Y16.

73

sciencesconf.org:numeration2018:193537

No full analogue of Lagrange’s theorem holds in this setting as remarked by Ooto in [Oot17], andthe problem of deciding whether a quadratic (`-adic) irrational number has a periodic continued
fraction seems still open. For Browkin’s definition, some very partial sufficient conditions were
given in a series of papers by Bedocchi [Bed93]. Moreover,√in [Bro01], Browkin wrote an algorithm
to generate the periodic continued fraction expansion of ∆ ∈ Q` \ Q for some values of ∆ and `,giving many numerical examples.
In this paper we investigate the periodicity of the `-adic Ruban continued fraction expansion ofquadratic irrational numbers, thus solving a problem posed by Laohakosol in [Lao85].
Our main result is the following:
Theorem 3. Let α ∈ Q` \ Q be a quadratic irrational over Q. Then, the Ruban continued fraction
expansion of α is periodic if and only if there exists a unique real embedding j : Q(α) → R suchthat the image of each complete quotient αn under the map j is positive.
Moreover, there is an effectively computable constant Nα such that, either ∃ n ≤ Nα such thatboth real embeddings of αn are negative, and therefore the expansion is not periodic, or ∃ n1 <n2 ≤ Nα such that αn1 = αn2 , hence the expansion is periodic.
In particular, both the preperiodic and the periodic part of a periodic expansion can be computedwith a finite algorithm.
I summarise here a simplified version of the explicit bounds that we prove.
H(α)
+ 2;
• If the expansion of a rational α is finite, then its length is at most loglog`• If the expansion of a rational α is periodic, then the length of the preperiodic part is at2
most 32`H(α);√
b+ ∆• If α = c , with b, c, ∆ integers, ∆ > 0 not a square, then the constant Nα in Theorem 3√
can be bounded by bc + 2(c ∆ + 1)3 .

It is also interesting to study how the qualitative behaviour of the expansion varies with theprime ` for fixed rational or irrational quadratic numbers. We show that finiteness of the expansion(for rational numbers) and periodicity (for irrational quadratic numbers) are "unlikely" behaviours
which occur for at most finitely many primes.
This extended abstract has been adapted from the introduction of the full paper, which isavailable on ArXiv at the address https://arxiv.org/abs/1801.06214.
References[Bed93] E. Bedocchi, ‘Fractions continues p-adiques: périodes de longueur paire’, Boll. Un. Mat. Ital. (7) 7-A(1993), 259-265.
[Bro78] J. Browkin, ‘Continued fractions in local fields. I’, Demonstratio Math. 11 (1978), no. 1, 67-82.
[Bro01] J. Browkin, ‘Continued fractions in local fields. II’, Math. Comp. 70 (2001), no. 235, 1281-1292.
[Bun77] P. Bundschuh, ‘p-adische Kettenbrüche und Irrationalität p-adischer Zahlen’, Elem. Math. 32 (1977), no.
2, 36-40.
[Lao85] V. Laohakosol, ‘A characterization of rational numbers by p-adic Ruban continued fractions’, J. Austral.
Math. Soc. Ser. A 39 (1985), no. 3, 300-305.
[Mah34] K. Mahler ‘Zur Approximation p-adischer Irrationalzahlen’, Nieuw Arch. Wisk. (2) 18 (1934), 22-34.
[Oot17] T. Ooto, ‘Transcendental p-adic continued fractions’, Math. Z. 287 (3) (2017), 1053-1064.
[Rub70] A. Ruban, ‘Certain metric properties of the p-adic numbers’, Sibirsk. Mat. Z. 11 (1970), 222-227.
[Sch70] T. Schneider, ‘Über p-adische Kettenbrüche’, Symposia Mathematica Vol. IV (INDAM, Rome, 1968/69),
Academic Press, London, 1970, 181-189.
[Wan85] L.X. Wang, ‘p-adic continued fractions I, II,’ Sci. Sinica Ser. A 28 (1985), no. 10, 1009-1017, 1018-1023.
Collegio Puteano, Scuola Normale Superiore, Piazza dei Cavalieri, 3, I-56100 PISA, Italia
E-mail address: francesco.veneziano@sns.it

74

sciencesconf.org:numeration2018:193537

PERIODIC REPRESENTATIONS IN SALEM BASES
TOMÁŠ VÁVRA

This contribution is a continuation of author’s work on periodic representations
in number systems with algebraic bases. By the results of Baker, Kala, Masáková,Pelantová, and Vávra, we know that for an algebraic base β without Galois conjugates on the unit circle there is a finite alphabet A ⊂ Z such that each elementof Q(β) admits an eventually periodic (β, A)-representation. That is, a representaP+∞tion of the form i=−k ai β −i , ai ∈ A with the digit sequence {ai } being eventuallyperiodic.
We will show that the mentioned result can be strengthened to cover all thealgebraic bases, in particular also the Salem numbers, for which this problem wasunapproachable by the previous method. Moreover, we discuss whether the representations constructed by our method satisfy the weak-greedy condition, i.e.,
whether the leading power of the representation is proportional to the modulus of
the represented number. We come to the conclusion that the weak-greedy conditionis satisfied if and only if |β| is a Pisot or a Salem number, or β is a complex Pisot
or a complex Salem number.
Furthemore, we study the decideability whether a pair (β, A) satisfies the periodicity condition. We show that the periodicity condition can be equivalently statedas a topological property of the attractor of certain iterated function system, or asa geometric property of the spectrum of β with the alphabet A.
Department of Algebra, Charles University, Sokolovská 83, 175 86 Praha 8, Czech
Republic75

sciencesconf.org:numeration2018:195884

TOPOLOGY OF A CLASS OF SELF-AFFINE TILESJÖRG THUSWALDNER AND SHU-QIN ZHANG (SPEAKER)

Abstract. Let T = T (M, D) be an integral self-affine tile (Z3 -tile) in R3
generated by an expanding matrix   

0 0 −C01
C−1
M = 1 0 −B  and the digit set D = {0 , 0 , . . . ,  0 },
0 1 −A000where 1 ≤ A ≤ B < C. To study the topological properties of a Z3 -tile,
the neighbor set plays an important role. We have the following result aboutneighbor set. For 1 ≤ A < B < C, the Z3 -tile has 14-neighbors if and only if
one of the following conditions satisfies.
(1). B ≥ 2A − 1 and C ≥ 2(B − A) + 2;
(2). B < 2A − 1 and C ≥ A + B − 2.
In particular, if A = B = 1, it has 20 neighbors for all C ≥ 2. Moreover,
we will also show when the boundaries of the self-affine tiles are topological
2-spheres.

Chair of Mathematics and Statistics, University of Leoben, Franz-Josef-Strasse 18,
A-8700 Leoben, Austria
E-mail address: joerg.thuswaldner@unileoben.ac.at
E-mail address: zhangsq ccnu@sina.com

76

sciencesconf.org:numeration2018:197576

Author Indexčech Martin, 70, 71
Airey Dylan, 36–40, 50, 51
Bandt Christoph, 1, 2
Bertrand-Mathis Anne, 3
Brunotte Horst, 4
Capuano Laura, 73, 74
Carminati Carlo, 29, 30
Cristea Ligia Loretta, 5, 6
Drmota Michael, 41
Dubickas Arturas, 7, 8
Dutykh Denys, 72
Frid Anna, 9–12
Hare Kathryn, 13Hare Kevin, 13
Hejda Tomas, 14–18
Hudoba Peter, 19–21
Jackson Stephen, 36–40
Jankauskas Jonas, 22Sidorov Nikita, 57
Sirvent Victor, 66, 67
Spiegelhofer Lukas, 41, 58–61
Steiner Wolfgang, 29, 30
Stockinger Wolfgang, 62–65
Suppakitpaisarn Vorapong, 24, 25
Surer Paul, 66, 67
Svoboda Josef, 70, 71
Swaenepoel Cathy, 68
Thuswaldner Jörg, 22, 69, 76
Tinková Magdaléna, 70, 71
Troscheit Sascha, 13
Vávra Tomáš, 75
Veneziano Francesco, 73, 74
Verger-Gaugry Jean-Louis, 72
Wagner Stephan, 24, 25
Zannier Umberto, 73, 74
Zemková Kristýna, 70, 71
Zhang Shuqin, 76

Kala Vitezslav, 14–18
Kalle Charlene, 33–35
Kong Derong, 23
Kovács Attila, 26–28
Kovacs Attila, 19–21
Krásenský Jakub, 26–28
Krenn Daniel, 24, 25
Lachman Dominik, 70, 71
Langeveld Niels, 29, 30
Larcher Gerhard, 62–65
Li Wenxia, 23
Loquias Manuel Joseph, 56
Müllner Clemens, 41
Madritsch Manfred, 31, 32
Maggioni Marta, 33–35
Mance Bill, 36–40, 50, 51
Mekhontsev Dmitry, 1, 2
Nair Radhakrishnan, 44–49
Nakada Hitoshi, 29, 30
Nikiforov Roman, 50, 51
Nogueira Arnaldo, 42, 43
Pethő Attila, 52–55
Rodriguez Alfonso David, 56
Scheicher Klaus, 66, 67

77

78