🔢 mathematics

Distribution of integers with digit restrictions via Markov chains

This paper introduces a new Markov chain-based technique to study the distribution of integers with digit and sum-of-digits restrictions in arithmetic progressions, providing a necessary and sufficient condition for uniform distribution in missing-digit sets and extending these results to the broader class of multiplicatively invariant sets.

Original authors: Vicente Saavedra-Araya

Published 2026-02-11

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Vicente Saavedra-Araya

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

Imagine you have a giant bucket of LEGO bricks, but you are only allowed to use certain colors—say, only red and blue ones—to build towers. If you follow this rule, you aren't building "every possible tower"; you are building a very specific, restricted subset of all possible towers.

In mathematics, this paper is about integers with "digit restrictions." Instead of LEGO colors, we use digits (0–9). Instead of building towers, we are looking at numbers. If you decide you will only ever use the digits 1, 3, and 7 to write numbers, you have created a "restricted set" of integers.

The author, Vicente Saavedra-Araya, asks a fascinating question: If we look at these "special" numbers, how do they spread out across the number line?

1. The "Uniformity" Question: Are they fair players?

Imagine you are playing a game of darts. If you are a "fair player," your darts should land in every section of the board (the "residue classes") with roughly the same frequency.

If we take our "red and blue LEGO" numbers and ask, "Are these numbers equally likely to be even or odd?" or "Are they equally likely to end in a 1, 2, or 3 when divided by 5?", we are asking if they are uniformly distributed.

For a long time, mathematicians knew some rules for this, but they were mostly "sufficient conditions"—meaning, "If these specific things happen, the numbers will be fair." This paper provides the "necessary and sufficient" conditions. It’s like moving from saying, "If you wear a helmet, you are safe," to saying, "You are safe if, and only if, you wear a helmet and don't walk into a moving bus." It provides the complete, perfect rulebook.

2. The Secret Weapon: The "Markov Chain"

How do you prove something about an infinite sequence of numbers? You can't count them all!

The author uses a tool called a Markov Chain. Think of a Markov Chain like a board game where your next move only depends on where you are standing right now.

To study these numbers, the author treats the process of "adding a new digit" to a number like "taking a step on a game board."

The "state" you are in is your current remainder (e.g., "I am currently at a number that, when divided by 7, leaves a remainder of 3").
The "move" you make is adding a new digit.
By studying the "rules of the game" (the transition matrix), the author can prove that, eventually, the "player" (the number) will visit every single square on the board with equal frequency.

3. The "Fractal" Connection: The Shape of Numbers

The paper also touches on something called Multiplicatively Invariant Sets. This is a fancy way of saying sets of numbers that stay "the same kind of set" even if you chop off the first or last digit.

These sets behave like fractals—patterns that look similar whether you zoom in or zoom out. The author investigates a deep mystery: if you take one of these fractal-like sets of numbers and look only at an arithmetic progression (like every 10th number: 10, 20, 30...), does the "shape" (the dimension) of the set stay the same, or does it shrink?

The author finds that for most "well-behaved" sets (which they call transitive sofic subshifts), the shape stays the same. But if the set is "messy" or "broken," the shape can change.

Summary in a Nutshell

If you restrict the digits you use to write numbers, you create a "mathematical fractal." This paper uses the logic of "step-by-step games" (Markov Chains) to prove exactly how these restricted numbers distribute themselves among different groups. It provides the ultimate "rulebook" for when these numbers act fairly and how they maintain their complex, fractal-like structure even when you look at them through a narrow lens.

Technical Summary: Distribution of Integers with Digit Restrictions via Markov Chains

Author: Vicente Saavedra-Araya
Subject Area: Number Theory, Symbolic Dynamics, and Ergodic Theory

1. The Problem

The paper investigates the distribution of specific subsets of integers within residue classes (arithmetic progressions). Specifically, it focuses on sets of integers defined by restrictions on their digits in a given base $g \geq 2$ .

The author explores two primary phenomena:

Uniform Distribution: Under what conditions do these sets visit different congruence classes with equal frequency? This includes studying the joint distribution of an integer $n$ and its sum-of-digits function $S_g(n)$ modulo various integers.
Transversality (Fractal Dimension): How do these sets interact with arithmetic progressions from a fractal geometry perspective? Specifically, the paper addresses an open question by Glasscock, Moreira, and Richter: if $A$ is a "multiplicatively invariant" set (an integer analogue to fractal sets), is the mass dimension of its intersection with an arithmetic progression $P$ either $0$ or equal to the dimension of $A$ itself?

2. Methodology: The Markov Chain Approach

The core innovation of this paper is a new technique that replaces traditional Fourier analysis—the standard tool for such problems—with the theory of Markov chains and symbolic dynamics.

Multiplicative Invariance & Subshifts: The author utilizes the fact that multiplicatively invariant sets can be represented by subshifts (sets of infinite sequences of digits). By studying the "language" (the set of finite words) of these subshifts, the problem of integer distribution is transformed into a problem of word distribution.
Construction of Markov Chains: For a given base $g$ , modulus $a$ , and $g$ -additive functions $f$ , the author constructs a Markov chain where the state space $S$ is the product of the residue classes $\mathbb{Z}_a$ and the set of follower sets $V$ of the subshift (using the Fischer cover of the subshift).
Transition Matrices: The transition matrix $M_i$ is designed to capture how adding a block of digits affects both the residue of the integer and the "state" (follower set) of the digit sequence. If the subshift is "regular" (the graph is $k$ -regular), the resulting matrix is doubly stochastic, ensuring a uniform invariant distribution.
Convergence: The author applies classical results on the irreducibility and aperiodicity of Markov chains to prove that the distribution of these integers converges to a uniform limit.

3. Key Contributions and Results

A. Necessary and Sufficient Conditions for Uniform Distribution

Theorem A & Corollary A: The paper provides a definitive answer for "missing digits" sets. It establishes that a set $C_{g,D}$ is uniformly distributed modulo $a$ (where $\gcd(g, a)=1$ ) if and only if $\gcd(a, d_2-d_1, \dots, d_t-d_1) = 1$ . This extends previous work (Erdős, Mauduit, Sárközy) which only provided sufficient conditions.
Gelfond’s Theorem Extension: The author revisits Gelfond’s theorem regarding the joint distribution of $n \pmod a$ and $S_g(n) \pmod{a'}$ , providing a new, equivalent condition that removes the restrictive assumption $\gcd(g-1, a') = 1$ .

B. Addressing the Open Question on Transversality

Negative Answer (General Case): The author proves that for general transitive or sofic subshifts, the mass dimension of the intersection with an arithmetic progression can be strictly between $0$ and $\dim_M(A)$ .
Positive Answer (Transitive Sofic Case): The author proves that if the set is represented by a transitive sofic subshift, the answer to the open question is affirmative: $\dim_M(A \cap P)$ is indeed either $0$ or $\dim_M(A)$ .
Conjecture: Based on the results, the author proposes that the property holds if and only if the subshift is entropy minimal.

C. Generalization to Digit Combinations

The method is shown to work for more complex restrictions, such as forbidding specific combinations of digits (e.g., "no two 1s can be separated by an even number of 0s"), which are modeled as Shift of Finite Type (SFT) or sofic shifts.

4. Significance

This paper is significant for several reasons:

Methodological Shift: It demonstrates that problems in additive number theory can be solved elegantly using the tools of symbolic dynamics and Markov chains, offering a more direct combinatorial path than Fourier-analytic methods.
Completeness: It moves the field from "sufficient conditions" to "necessary and sufficient conditions" for many classical problems regarding digit restrictions.
Bridging Fields: It creates a rigorous link between the arithmetic properties of integers and the topological/dynamical properties of subshifts, providing a partial resolution to a major open question in the study of integer fractals.