A Sequential View of Self-Similar Measures; or, What the Ghosts of Mahler and Cantor

Can Teach Us About Dimension

Michael Coons and James Evans School of Mathematical and Physical Sciences The University of Newcastle Callaghan, NSW 2308 Australia

                Michael.Coons@newcastle.edu.au
                   James.Evans10@uon.edu.au

Abstract We show that a missing q-ary digit set F ⊆ [0, 1] has a corresponding naturally associated countable binary q-automatic sequence f. Using this correspondence, we show that the Hausdorff dimension of F is equal to the base-q logarithm of the Mahler eigenvalue of f. In addition, we demonstrate that the standard mass distribution ν_{F} supported on F is equal to the ghost measure μ_{f} of f.

1 Introduction

This story starts with an uncountable set and a countable sequence, their respective dimension and asymptotical behavior, and describes the setting in which these objects and properties—and their generalizations—coalesce.

The uncountable set is the ubiquitous standard middle-thirds Cantor set, C, the selfaffine set that is the unique attractor of the iterated function system S_{C} := {S_{1}, S_{2}}, where the functions S_{1}, S_{2} : [0, 1] → [0, 1] are the affine contractions

S_{1}(x) = \frac{x}{3} and S_{2}(x) = \frac{2 + x}{3}.

The standard construction of C is via the production of “level sets” E_{k}, for k ≥ 0, where E_{k} := S_{C}^{k}([0, 1]), S_{C}(E) := S_{1}(E) ∪ S_{2}(E) for any set E, and S_{C}^{k} denotes k-fold composition of S_{C} with itself; see Figure 1. Each level set E_{k} has Lebesgue measure λ(E_{k}) = (2/3)^{k}, so that C has λ-measure zero. Nonetheless, C has some size; it has Hausdorff dimension log_{3}(2), where log_{3}(·) denotes the ternary logarithm. Further, one can construct a natural mass distribution ν_{C}, called the Cantor measure, supported on C by repeated subdivision, at each level spreading the mass equally among the subintervals of E_{k} and taking k to infinity. In this way, the λ-singular continuous measure ν_{C} is the (weak) limit of λ-absolutely continuous measures. We thus arrive to the paradigmatic example of a fractal set C and a related mass distribution ν_{C}. Much of the theories of fractal geometry and discrete dynamical systems have been developed pursuing generalizations of this example; see Falconer’s definitive monograph Fractal Geometry [14] for details and discussions.

0  \frac{1}{3}  \frac{2}{3}  ^{1} E_{0} E_{1} E_{2} E_{3} E_{4} C

Figure 1: Iterated construction of the Cantor set C, where E_{k} = S_{C}^{k}([0, 1]).

Transitioning from the uncountable to the countable, we consider the 3-automatic binary sequence that is the infinite fixed point ϱ_{c}^{∞}(1) of the substitution ϱ_{c} defined by

ϱ_{c} : \begin{cases}1 ↦ 101 \\ 0 ↦ 000 . \end{cases}

We define the Cantor sequence {c(n)}_{n≥0} as the nth entry of ϱ_{c}^{∞}(1). The construction of ϱ_{c}^{∞}(1) is reminiscent of the construction of the Cantor set C, the iterate ϱ_{c}^{k}(1) playing the part of the level set E_{k}; see Figure 2. It is easy to see that c(n) = 1 precisely when the ternary expansion of the integer n contains no ones, so that analogy to the Cantor set is clear. See Allouche and Shallit [3] for details on automatic sequences.

Using the definition, since c is 3-automatic, its generating function is a Mahler function, and one obtains immediately that the generating function of the Cantor sequence can be written as an infinite product,

M_{c}(z) := ∑_{n≥0} c(n)z^{n} = ∏_{j≥0} (1 + z^{2·3^{j}}) .

A result of Bell and Coons [9] provides, as z → 1^{−}, the asymptotics

M_{c}(z) ≍ \frac{1}{(1 − z)^{log_{3}(2)}} (1 + o(1)).

ϱ_{c}^{0}(1) = 1
ϱ_{c}^{1}(1) = 101
ϱ_{c}^{2}(1) = 101000101
ϱ_{c}^{3}(1) = 101000101000000000101000101
⋮
ϱ_{c}^{∞}(1) = 101000101000000000101000101000000000000000000000000000101000 ⋯

Figure 2: Iterated construction of the Cantor sequence c

Here, the number 2 in the quantity log_{3}(2) is the Mahler eigenvalue λ_{c} of M_{c}(z) (details and definitions are provided in the next section) obtained from the Mahler-type functional equation satisfied by M_{c}(z),

M_{c}(z) − (1 + z^{2})M_{c}(z^{3}) = 0.

Note that the divergent behavior of M_{c}(z) is governed by the Hausdorff dimension of C; that is, dim_{H} C = log_{3}(2). This relationship, generalized, is our first result.

Theorem 1. Let q ≥ 2 be an integer, A ⊆ {0, …, q − 1} containing 0 and F be the subset of [0, 1] consisting of numbers that can be represented in base-q using only q-ary digits from A. Then, with F there is a naturally associated q-automatic binary sequence f such that

dim_{H} F = log_{q}(|A|) = log_{q}(λ_{f}),  (1)

where λ_{f} is the Mahler eigenvalue of the generating function M_{f}(z) of f and log_{q}(·) denotes the base-q logarithm.

Remark 2. We note that the new contribution of Theorem 1 concerns the connection to the Mahler eigenvalue. In particular, the second equality of (1) is new—the first follows directly from Falconer [14, Thm. 9.3].

Returning to our motivating example, analogous to the Cantor measure ν_{C}, we may construct a mass distribution μ_{c} associated with the sequence c, called the ghost^{1} measure. This construction was introduced by Baake and Coons [5]. Here, for each n, we take the sequence c up to 3^{n} − 1 (a kind of ‘fundamental region’) and reinterpret its (renormalized) values as the weights of a pure point probability measure μ_{c,n} on the torus 𝕋 = [0, 1) with support supp(μ_{c,n}) = \{\frac{j}{3^{n}} : 0 ≤ j < 3^{n}, c(j) = 1\}. That is,

1The term ghost measure was introduced by the second author [13], inspired by the phrase “the ghost of departed quantities” as appearing in Berkeley’s critique of calculus. Evans [13] writes, “The terms of the sequence are (usually) much smaller than the sum of the terms, so the individual pure points of the μ_{n} are driven to zero by the averaging as n tends to infinity. The measure μ is the ghost of the departed pure points of the μ_{n}.”

μ_{c,n} := 2^{−n} ∑_{j=0}^{3^{n}−1} c(j) δ_{j/3^{n}},

where δ_{x} denotes the unit Dirac measure at x. The ghost measure μ_{c} is the (weak) limit of the sequence (μ_{c,n})_{n≥0} as n → ∞. With the obvious generalization in notation, we state our second result.

Theorem 3. With the notation above and assumptions of Theorem 1, the standard mass distribution ν_{F} supported on F is equal to the ghost measure μ_{f}.

In particular, the Cantor measure ν_{C} is equal to the ghost measure μ_{c}. In this way, Theorem 3 provides an alternative construction of standard mass distributions supported on fractals, and does so in a way that takes the countable to the uncountable. Remark 4. Self-similar sets—attractors of affine contractions—have been used by many authors to model physical phenomena; see Mandelbrot [18] for a detailed history and references. The study of self-similar sets was put into a rigorous general framework by Hutchinson [15] and the study of self-similar measures and their Fourier transforms was studied in detail by Strichartz [20, 21]; see also Makarov [16, 17]. See Baake and Moody [7] for the generalization to compact families of contractions.

2 Hausdorff dimension and the Mahler eigenvalue

In this section, we prove Theorem 1.

To this end, let q ≥ 2 be an integer, A ⊆ {0, …, q − 1} containing 0 and F be the subset of [0, 1] consisting of numbers that can be represented in base-q using only q-ary digits form A. We enumerate the set A as

0 = a_{1} < a_{2} < ⋯ < a_{m−1} < a_{m} ≤ q − 1.

Then F is the unique attractor of the iterated function system S = {S_{1}, …, S_{m}}, where the functions S_{i} are given by

S_{i}(x) = \frac{x + a_{i}}{q} .  (2)

Moreover, we have [14, Thm. 9.3]

dim_{H} F = log_{q}(m).  (3)

We associate with F the q-automatic binary sequence f, which is the infinite fixed point ϱ_{f}^{∞}(1) of the substitution ϱ_{f} defined by

ϱ_{f} : \begin{cases}1 ↦ 10^{a_{2}−(a_{1}+1)}1 ⋯ 0^{a_{k}−(a_{k−1}+1)}1 ⋯ 0^{a_{m}−(a_{m−1}+1)}10^{q−1−(a_{m})} , \\ 0 ↦ 0^{q} , \end{cases}

where 0^{j} indicates a string of zeros of length j with the convention that the string 0^{0} is equal to the empty string. The power series generating function M_{f}(z) := ∑_{n≥0} f(n) z^{n} of f has an infinite product representation, easily read off from the substitution; indeed, M_{f}(z) = ∏_{j≥0} p_{f}(z^{q^{j}}), where

p_{f}(z) = ∑_{k=1}^{m} z^{a_{k}} = 1 + z^{a_{2}} + z^{a_{3}} + ⋯ + z^{a_{m−1}} + z^{a_{m}},

and where we have used the fact that a_{1} = 0. This product representation shows that M_{f}(z) is a Mahler function.

In general, for an integer q ≥ 2, a power series M(z) ∈ ℤ[[z]] is called a q-Mahler function (or a just a Mahler function when q is understood) provided there is an integer d ≥ 1 and polynomials p_{0}(z), …, p_{d}(z) ∈ ℤ[z] with p_{0}(z)p_{d}(z) ≠ 0 such that M(z) satisfies the functional equation

p_{0}(z)M(z) + p_{1}(z)M(z^{q}) + ⋯ + p_{d}(z)M(z^{q^{d}}) = 0.  (4)

We call the integer q, the base of the Mahler function; the minimal integer d for which such an equation exists is called the degree of M(z). So in the case of the sequence f above, the function M_{f}(z) is a degree-one q-Mahler function. The leading asymptotic behavior of Mahler functions, as z → 1^{−}, is governed by a number called the Mahler eigenvalue. This concept was introduced by Bell and Coons [9] in order to produce a quick transcendence test for Mahler functions. Our focus here is on its connection to the Hausdorff dimension of a related fractal, the self-affine set F.

To formalize this notion, suppose that M(z) satisfies (4), set p_{i} := p_{i}(1), and form the characteristic polynomial of M(z),

χ_{M}(λ) := p_{0}λ^{d} + p_{1}λ^{d−1} + ⋯ + p_{d−1}λ + p_{d}.

Bell and Coons [9] showed that if χ_{M}(λ) has d distinct zeros, then there exists an eigenvalue λ_{f} with χ_{M}(λ_{M}) = 0, which is naturally associated with M(z). We call λ_{M} the Mahler eigenvalue of M(z). This natural association is best seen through the asymptotics. For example, in the case of degree-one q-Mahler functions, if M(z) = ∏_{j≥0} p(z^{q^{j}}) for some polynomial p(z) ∈ ℤ[z] with p(0) = 1 and p(1) ≠ 0, we have that λ_{M} = p(1) and, as z → 1^{−},

M(z) ≍ \frac{1}{(1 − z)^{log_{q} p(1)}} (1 + o(1)).  (5)

With the above concepts and definitions in hand, it is immediate that

λ_{f} := λ_{M_{f}} = p_{f}(1) = m,

since there are m terms in the polynomial p_{f}(z) each with coefficient equal to one. The validity of Theorem 1 is now readily apparent by combining this equality with (3).

Remark 5. Note that (5) implies that as z → 1^{−} the function (1 − z)^{log_{q} p(1)}M(z) potentially oscillates between two positive real numbers. In fact, this is the case—see, e.g., Brent, Coons and Zudilin [10], Bell and Coons [9] and Coons [11]—though little is known about the consequences and properties of this oscillation. In the light of Theorem 1, it seems a reasonable question to ask if this oscillation has a relation to certain fractals or their properties.

3 Fractal mass distributions are ghost measures

In this section, we start by describing both the standard mass distribution ν_{F} supported on the attractor F of an iterated function system S of rational affine contractions and the ghost measure μ_{f} of the associated automatic sequence f. We then prove Theorem 3, that ν_{F} = μ_{f}, by showing that the Fourier–Stieltjes coefficients ν̂_{F}(n) and μ̂_{f}(n) are equal for every integer n. Details and results showing this equivalence can be found in Rudin [19, Thm. 1.3.6]; see also Baake and Grimm [6, Ch. 8] for a more recent discussion on Fourier analysis and measures focussing on those important to the study of aperiodic order.

Let S = {S_{1}, …, S_{m}} be an iterated function system satisfying (2) and define, for any set E ⊆ [0, 1], the function

S(E) := ⋃_{i=1}^{m} S_{i}(E).

In particular, we have that F := lim_{k→∞} S^{k}([0, 1]), where, as before, S^{k} indicates k-fold function composition of S with itself. Analogous to the construction of the Cantor set in Figure 1, we let E_{k} := S^{k}([0, 1]) be the level sets in the construction of F. Each of the level sets E_{k} is a union of m^{k} intervals of length q^{−k}. We divide the unit mass of the interval equally among each of these intervals and construct a mass distribution ν_{F} supported on the attractor F as the limit of the mass distributions ν_{F,k} supported on the level sets E_{k}. Initially, we have that ν_{F,0} = λ |_{[0,1]} is Lebesgue measure restricted to the interval [0, 1], and for k ≥ 1, we have

ν_{F,k} = \frac{q}{m} · ν_{F,k−1} |_{E_{k}}.  (6)

Each measure ν_{F,k} is absolutely continuous with respect to Lebesgue measure. The measure ν_{F} is the (weak) limit of the ν_{F,k} as k → ∞. For example, Figure 3 contains the graph of the distribution function of ν_{C} over the interval [0, 1], known as the devil’s staircase—there are uncountably many steps, one at each element of the Cantor set C.

Turning now to the ghost measure of the related sequence f, for each k, analogous to the construction of μ_{c} in the Introduction, we take the sequence f up to q^{k} − 1 and reinterpret its (renormalized) values as the weights of a pure point probability measure μ_{f,k} on the torus 𝕋 = [0, 1) with support supp(μ_{f,k}) = {j/q^{k} : 0 ≤ j < q^{k}, f(j) = 1}. That is,

μ_{f,k} := m^{−k} ∑_{j=0}^{q^{k}−1} f(j) δ_{j/q^{k}},

Figure 3: The devil’s staircase: the distribution function of ν_{C} = μ_{c}.

where δ_{x} denotes the unit Dirac measure at x. The measures μ_{f,k} are the mass distributions associated with the finite sequences ϱ_{f}^{k}(1), analogous to the mass distributions ν_{F,k} associated with the level sets E_{k}. The ghost measure μ_{f} is the (weak) limit of the sequence (μ_{f,k})_{k≥0} as k → ∞.

With this terminology in hand, we are now ready to prove Theorem 3.

Proof of Theorem 3. As stated at the beginning of this section, to show that ν_{F} = μ_{f}, it is enough (equivalent, actually) to show that their Fourier–Stieltjes coefficients are equal [19, Thm. 1.3.6]; that is, for every integer n, ν̂_{F}(n) = μ̂_{f}(n).

For ν_{F}, we note that given an integer n, applying (6) followed by a change of variable, we have

ν̂_{F,k}(n) := ∫_{0}^{1} e^{2πinx} dν_{F,k}(x) = \frac{q}{m} ∫_{0}^{1} e^{2πinx} dν_{F,k−1}(x) |_{E_{k}}

= \frac{1}{m} ∑_{j=1}^{m} ∫_{0}^{1} e^{2πin( \frac{a_{j} +y}{q} )} dν_{F,k−1}(y) = \frac{1}{m} ∑_{j=1}^{m} e^{2πina_{j}/q} ∫_{0}^{1} e^{2πi(n/q)y} dν_{F,k−1}(y)

= (\frac{1}{m} · p_{f}(e^{2πin/q})) { \atop ν_{F,k−1}}(n/q) = ∏_{ℓ=1}^{k} (\frac{1}{m} · p_{f}(e^{2πin/q^{ℓ}})) · ∫_{0}^{1} e^{2πi(n/q^{k})x} dx,

where the last equality follows by repeated application of the penultimate equality, and the fact that ν_{F,0}(x) = λ |_{[0,1]}. Taking the limit as k → ∞, we thus have

ν̂_{F}(n) = ∏_{ℓ≥1} (\frac{1}{m} · p_{f}(e^{2πin/q^{ℓ}})) ,  (7)

since lim_{k→∞} ∫_{0}^{1} e^{2πi(n/q^{k})x} dx = 1 for any integer n.

The calculation for μ_{f} is more straight-forward. Indeed, by inspecting the iterates ϱ_{f}^{k}(1), it is clear that

∑_{j=0}^{q^{k}−1} f(j) z^{j} = ∏_{ℓ=0}^{k−1} p_{f}(z^{q^{ℓ}}),

so that

μ̂_{f,k}(n) := m^{−k} ∑_{j=0}^{q^{k}−1} f(j) e^{−2πinj/q^{k}} = m^{−k} ∏_{ℓ=0}^{k−1} p_{f}(e^{−2πinq^{ℓ−k}}) = ∏_{ℓ=1}^{k} (\frac{1}{m} · p_{f}(e^{−2πin/q^{ℓ}})) .

Taking the limit as k → ∞, μ̂_{f}(n) is equal to the righthand side of (7) and so also to ν̂_{F}(n), thus μ_{f} = ν_{F}, which finishes the proof of the theorem.

4 Further comments

The idea of fractals arising from automatic sequences is by no means new. The limiting sets of automatic sequences and their relation to fractals was investigated by Barbé and von Haeseler [8]. In fact, even our paradigmatic example—the Cantor sequence—has been around for some time. It played an emphatic role in the paper of Allouche and Skordev [4]; one of the purposes of their paper was to remind the mathematical community that there is an abundance of literature connecting automatic sequences to fractals. See their paper [4] for a detailed reference list. There are even several examples given in Allouche and Shallit [3], e.g., the dragon curve is related to the regular paperfolding sequence [3, p. 155] and one can obtain von Koch’s famous snowflake via an 8-automatic sequence on three letters [3, p. 202]. As well, the notion of relating the Hausdorff dimension to properties of automatic fractals is not new; Adamczewski and Bell explored the possibility of a relationship between the Hausdorff dimension and entropy of an automatic fractal, which led them to ask several questions; see [1].

In this paper, we demonstrated how two objects, attractors of certain rational affine iterated function systems and automatic sequences, can be related and explored a few of the consequences of that relationship. As described above, the connection between fractal and automatic sequences is well-established. Our contribution is an explicit relationship of some invariants related to either object. In particular, we showed that the Hausdorff dimension of the attractor is related to the asymptotics of the generating function of the automatic sequence. The class of iterated function systems we considered has attractors that are self-affine sets, and so the relationship we describe is with a very tangible, and wellunderstood, geometric object. That said, there is no reason not to desire a generalization beyond this straight-forward class of examples. Ghost measures exist for a much larger class of sequences, e.g., for a large subset of regular sequences [12] as defined by Allouche and Shallit [2]. The ghost measures of the so-called ‘affine’ 2-regular sequences have been recently completely described by Evans [13]. The existence of such measures begs the question of further relationships between automatic and regular sequences to fractals.

5 Acknowledgments

We thank the referee for a thorough reading that improved the quality of this paper. We acknowledge the support of the Commonwealth of Australia.

References

[1] Boris Adamczewski and Jason P. Bell, An analogue of Cobham’s theorem for fractals, Trans. Amer. Math. Soc. 363 (2011), 4421–4442.

[2] Jean-Paul Allouche and Jeffrey Shallit, The ring of k-regular sequences, Theoret. Comput. Sci. 98 (1992), 163–197.

[3] Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge, 2003.

[4] Jean-Paul Allouche and Gencho Skordev, Von Koch and Thue-Morse revisited, Fractals 15 (2007), 405–409.

[5] Michael Baake and Michael Coons, A natural probability measure derived from Stern’s diatomic sequence, Acta Arith. 183 (2018), 87–99.

[6] Michael Baake and Uwe Grimm, Aperiodic Order. Volume 1: A Mathematical Invitation, Cambridge, 2013.

[7] Michael Baake and Robert V. Moody, Self-similar measures for quasicrystals, in M. Baake and R. V. Moody, eds., Directions in Mathematical Quasicrystals, CRM Monogr. Ser., Vol. 13, Amer. Math. Soc., 2000, pp. 1–42.

[8] André Barbé and Fritz von Haeseler, Limit sets of automatic sequences, Adv. Math. 175 (2003), 169–196.

[9] Jason P. Bell and Michael Coons, Transcendence tests for Mahler functions, Proc. Amer. Math. Soc. 145 (2017), 1061–1070.

[10] Richard P. Brent, Michael Coons, and Wadim Zudilin, Algebraic independence of Mahler functions via radial asymptotics, Int. Math. Res. Not. IMRN 2016, 571–603.

[11] Michael Coons, An asymptotic approach in Mahler’s method, New Zealand J. Math. 47 (2017), 27–42.

[12] Michael Coons, James Evans, and Neil Mañibo, The spectral theory of regular sequences, preprint, 2020. Available at https://arxiv.org/abs/2009.01402.

[13] James Evans, The ghost measures of affine regular sequences, Houston J. Math., to appear.

[14] Kenneth Falconer, Fractal Geometry, John Wiley & Sons, 2014.

[15] John E. Hutchinson, Fractals and self-similarity, Indiana Univ. Math. J. 30 (1981), 713–747.

[16] Konstantin A. Makarov, Asymptotics of the Fourier transform of self-affine measures, Dokl. Akad. Nauk 333 (1993), 140–143.

[17] Konstantin A. Makarov, Asymptotic expansions for Fourier transform of singular selfaffine measures, J. Math. Anal. Appl. 187 (1994), 259–286.

[18] Benoit B. Mandelbrot, Fractals: Form, Chance, and Dimension, W. H. Freeman and Co., 1977.

[19] Walter Rudin, Fourier Analysis on Groups, John Wiley & Sons, 1962.

[20] Robert S. Strichartz, Self-similar measures and their Fourier transforms I, Indiana Univ. Math. J. 39 (1990), 797–817.

[21] Robert S. Strichartz, Self-similar measures and their Fourier transforms II, Trans. Amer. Math. Soc. 336 (1993), 335–361.

2010 Mathematics Subject Classification: Primary 28A80 Secondary 11K55, 52C23. Keywords: Hausdorff dimension, iterated function system, self-affine set, automatic sequence, Mahler function.

(Concerned with sequences \underline{A088917} and \underline{A292686}.)

Received October 18 2020; revised version received January 28 2021. Published in Journal of Integer Sequences, January 28 2021.

Return to Journal of Integer Sequences home page.