🔢 mathematics

Prescribed distinct-digit growth in countable alphabets

This paper determines the Hausdorff dimensions of exceptional sets in full-branch affine countable iterated function systems with regularly varying weights, revealing a sharp phase transition where imposing a positive linear growth rate for distinct digits collapses the dimension to a value dictated by the tail index, while sublinear growth rates preserve full Hausdorff dimension.

Original authors: Ying Wai Lee

Published 2026-02-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ying Wai Lee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A Game of Infinite Boxes

Imagine you have an infinite row of mailboxes, numbered 1, 2, 3, and so on forever. You also have an endless supply of letters. Every day, you pick a mailbox at random and drop a letter in it.

The "Digit": The number of the mailbox you chose (e.g., Box 5).
The "Distinct Count": How many different boxes have received at least one letter so far.

If you pick Box 5, then Box 5 again, then Box 10, your "distinct count" goes: 1, 1, 2.
If you keep picking new boxes, the count goes up. If you keep picking the same old boxes, the count stays flat.

The Core Question:
If you play this game for a very long time, how fast does the number of unique boxes grow? And, more importantly, how "big" is the set of people who play the game in a weird, specific way?

In mathematics, "how big" doesn't just mean "how many people." It means Hausdorff Dimension. Think of this as a measure of "complexity" or "space-filling ability."

A single point has dimension 0.
A line has dimension 1.
A full, solid interval (like the whole number line from 0 to 1) has dimension 1.

The paper asks: If we force the game to grow at a specific speed (e.g., "I want exactly 50% of my days to be new boxes"), how complex is the group of people who can do that?

The Two Main Rules of the Game

The author studies two types of "weird" growth rates:

1. The "Linear" Rule (The Fast Lane)

Imagine you demand that 30% of your days must be brand new boxes.

The Result: This is a very strict rule. To keep finding new boxes that fast, you have to avoid the "popular" boxes (the ones with high probabilities) and hunt for the rare ones.
The Surprise: The group of people who can do this is tiny. In fact, their "complexity" (dimension) drops drastically.
The Metaphor: Imagine trying to run a marathon where you must jump over a hurdle every 3 steps. Only a very specific, elite type of runner can do this. The "space" they occupy is very thin.
The Math: The size of this group depends entirely on the Tail Index (a number that describes how "heavy" the tails of the probability distribution are). If the boxes are very unevenly distributed (some are super common, most are rare), the group of "30% new box" players becomes even smaller.

2. The "Sublinear" Rule (The Slow Lane)

Imagine you demand that the number of new boxes grows, but slower than the total number of days. For example, "I want the number of new boxes to equal the square root of the days passed."

The Result: This is a much more relaxed rule. It's easy to find new boxes if you don't demand them too often.
The Surprise: The group of people who can do this is massive. Their "complexity" is full (Dimension = 1).
The Metaphor: Imagine walking through a forest and saying, "I will find a new tree every 100 steps." Almost anyone walking through that forest can do this. The group of people who can do this fills up the entire forest.
The Math: Even if you pick a very specific, slow growth rate, the set of numbers that follow this rule is just as "big" and complex as the set of all possible numbers.

The "Phase Transition" (The Tipping Point)

The most exciting discovery in the paper is a sharp phase transition.

Think of a light switch.

Position OFF (Sublinear): If your growth rate is anything slower than a straight line (like a curve that flattens out), the "size" of the group is Full (1). The system is robust; almost any weird, slow pattern is possible.
Position ON (Linear): The moment you demand a straight-line growth (e.g., "10% new boxes every day"), the size of the group snaps to a much smaller value (determined by the Tail Index).

It's like a dam. As long as the water level (growth rate) is low, the dam holds back a massive lake (Full Dimension). But the moment the water level hits a specific critical line, the dam breaks, and the water level crashes down to a tiny trickle (Low Dimension).

Why Does This Matter?

This paper connects three different worlds:

Probability: The "Infinite Urn" problem (filling boxes).
Number Theory: How numbers are written out (like continued fractions or Luroth expansions).
Fractal Geometry: Measuring the size of weird, jagged sets.

The Takeaway:
In the world of infinite numbers, slowness is freedom, but speed is a trap.

If you want to grow your collection of unique items slowly, you have infinite freedom; almost any path you take is valid and complex.
If you try to grow your collection at a steady, fast pace, you are forced into a very narrow, rigid path. The "freedom" to be different disappears, and the mathematical "size" of your group shrinks.

Summary in One Sentence

If you try to find new things at a slow, steady pace, you can do it in a million different ways (Full Dimension), but if you try to find new things at a fast, linear pace, you are forced into a very specific, tiny corner of reality (Low Dimension).

1. Problem Statement

The paper investigates the Hausdorff dimension of exceptional sets defined by the growth rate of the number of distinct symbols (digits) appearing in the first $n$ steps of a symbolic process.

Context: The study focuses on affine full-branch countable iterated function systems (IFS) on the unit interval $[0, 1)$ . In these systems, the interval is partitioned into countably many subintervals, and a map $T$ sends each subinterval affinely onto the whole interval.
The Process: This generates a sequence of digits $(d_n)_{n \in \mathbb{N}}$ taking values in a countable alphabet (identified with $\mathbb{N}$ ). Under Lebesgue measure, this digit process is independent and identically distributed (i.i.d.) with probabilities $(p_k)_{k \in \mathbb{N}}$ .
The Observable: The primary object of study is the distinct-digit count $D_n(x) = \#\{d_1(x), \dots, d_n(x)\}$ , which represents the number of unique symbols observed up to time $n$ . This is mathematically equivalent to the number of occupied boxes in an infinite-urn occupancy scheme.
The Question: While the "typical" growth of $D_n$ is well-understood (governed by the tail behavior of $p_k$ ), the paper asks: What is the Hausdorff dimension of the set of points where $D_n$ grows at a prescribed, atypical rate? Specifically, the author analyzes sets where $D_n$ grows at a positive linear rate ( $D_n \sim \theta n$ ) or a prescribed sublinear rate ( $D_n \sim f(n)$ ).

2. Methodology

The author employs a combination of probabilistic occupancy theory, regular variation theory, and fractal geometry techniques (specifically the mass distribution principle and covering arguments).

A. Probabilistic Framework

The problem is mapped to an infinite-urn model where box probabilities are $(p_k)$ . The paper assumes the probability sequence is regularly varying with a tail index $\rho \ge 1$ :
$p_k \sim k^{-\rho} L(k)$
where $L(k)$ is a slowly varying function. This generalizes pure power-law distributions.

B. Lower Bound Construction (Mass Distribution Principle)

To prove that a set has a certain Hausdorff dimension, the author constructs a specific subset of the interval and a probability measure supported on it.

Block Concatenation: The construction involves defining blocks of digits.
- For linear rates (Theorem 1), the author constructs a set where digits are chosen from disjoint dyadic alphabets in blocks, ensuring exactly $\theta n$ distinct digits appear.
- For sublinear rates (Theorem 2), the construction uses a "forced-digit" strategy. At specific times, a new, unique digit is forced (from a high-index set), while at other times, digits are chosen freely from a lower-index set. This controls the distinct count to match a prescribed function $f(n)$ .
Measure Estimation: A measure is defined on these constructed sets. The author estimates the ratio of the measure of a cylinder set to its diameter raised to a power $s$ . If this ratio is bounded, the Mass Distribution Principle implies the dimension is at least $s$ .

C. Upper Bound Construction (Hausdorff-Cantelli & Tilting)

To prove the upper bound on dimension, the author uses a covering argument.

Tilting/Change of Measure: For the linear rate case, the author introduces a "tilted" probability measure where the probabilities are raised to a power $s$ ( $q_k \propto p_k^s$ ). This allows the use of large deviation principles.
Combinatorial Bounds: Lemmas regarding the number of sequences with a high number of distinct elements are used to bound the probability of the "bad" events (where the growth rate is too high).
Convergence: By showing that the sum of the $s$ -th powers of the diameters of the covering cylinders converges for $s > 1/\rho$ , the author establishes the upper bound.

3. Key Contributions and Results

The paper establishes a sharp phase transition in the Hausdorff dimension of these exceptional sets, depending on whether the prescribed growth rate is linear or sublinear.

Theorem 1: Linear Growth Rates

Let $E_\theta = \{ x : \lim_{n \to \infty} D_n(x)/n = \theta \}$ for $0 < \theta \le 1$ .

Result: $\dim_H(E_\theta) = \frac{1}{\rho}$ .
Significance: Imposing any positive linear growth rate forces the dimension to collapse from the full dimension (1) to a value determined solely by the tail index $\rho$ $ρ$ . This value is universal for the linear scale.
- Example: In the classical Lüroth expansion (where $\rho=2$ ), the dimension of the set with linear distinct-digit growth is $1/2$ .

Theorem 2: Sublinear Growth Rates

Let $f(n)$ be an "admissible" function (unbounded, $f(n)\log f(n)/n \to 0$ , and $0 \le f(n+1)-f(n) \le 1$ ). Define $E_f = \{ x : \lim_{n \to \infty} D_n(x)/f(n) = 1 \}$ .

Result: $\dim_H(E_f) = 1$ .
Significance: For a broad class of sublinear growth rates, the exceptional sets retain full Hausdorff dimension. The dimension does not drop, regardless of the specific sublinear rate chosen (provided it satisfies the admissibility conditions).

Corollary 1: Specific Cases

Sublinear polynomial rates ( $D_n \sim c n^\beta$ for $0 < \beta < 1$ ) have full dimension.
The set where the linear rate vanishes ( $D_n/n \to 0$ ) also has full dimension.

4. Significance and Comparison

Robustness of Phase Transition: The results confirm that the "dimension dichotomy" observed in continued fractions (by Wu and Xie) is robust and extends to independent digit systems (affine IFS).
- Continued Fractions: Wu-Xie showed $\dim = 1$ for sublinear and $\dim = 1/2$ for linear growth.
- Affine IFS (This Paper): The same dichotomy holds, but the collapsed dimension is $1/\rho$ rather than a fixed $1/2$ . This highlights that the specific value of the drop is determined by the tail index of the digit distribution.
Independence vs. Dependence: A major contribution is demonstrating that this phenomenon occurs even in i.i.d. settings (unlike continued fractions where digits are dependent). This suggests the phase transition is a fundamental property of heavy-tailed occupancy schemes rather than a specific artifact of dynamical dependence.
Methodological Advancement: The paper provides a refined toolkit for analyzing distinct-value statistics in countable alphabets, combining regular variation with fractal dimension theory. The "block concatenation" and "forced-digit" constructions offer new methods for building sets with precise growth constraints.

Summary

The paper proves that in countable alphabet systems with regularly varying weights, the Hausdorff dimension of sets with prescribed distinct-digit growth undergoes a sharp phase transition:

Sublinear growth: The set is "large" (Full Dimension = 1).
Linear growth: The set is "small" (Dimension = $1/\rho$ ), where the drop is dictated entirely by the heaviness of the tail of the probability distribution.

This work unifies the study of distinct-value statistics across number theory (continued fractions) and dynamical systems (Lüroth expansions and affine IFS), showing that the underlying probabilistic structure (heavy tails) is the primary driver of these dimensional laws.