🔢 mathematics

Aperiodicity and subword complexity in the binary expansion of powers of three

This paper establishes that the binary expansions of powers of three exhibit increasing aperiodicity, with the number of periodicity-breaking positions growing as $\log m/\log\log m$ , and demonstrate that their low-order digits achieve full subword complexity for sufficiently large exponents.

Original authors: Ralf Stephan

Published 2026-07-17

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Ralf Stephan

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.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 Secret Life of Numbers: A Journey into Binary Patterns

Imagine you are a detective trying to find patterns in a chaotic city. In the world of mathematics, this city is the number system, and the chaos is the way numbers look when written in different languages. We usually speak "decimal," using ten digits (0 through 9), but computers speak "binary," a language made of only two digits: 0 and 1. When you take a number like 3 and multiply it by itself over and over again (3, 9, 27, 81, and so on), you get a sequence of numbers that grow huge very quickly. If you write these massive numbers in binary, they look like long, jagged strings of zeros and ones.

Mathematicians have long wondered: Do these strings of zeros and ones follow a hidden rhythm, or are they completely random? This question belongs to a field called number theory, which studies the deep, often mysterious properties of whole numbers. A key idea here is "periodicity." Think of a periodic pattern like a wallpaper design that repeats the same flower every few inches. If a number's binary code had a period, it would mean that after a certain point, the pattern of zeros and ones would start repeating itself perfectly, like a song on a loop. Another important concept is "complexity," which measures how many different small chunks of the pattern exist. If a string is simple, it has few different chunks; if it's complex, it has a huge variety of them. Understanding these patterns helps us see if numbers like powers of three are truly chaotic or if they hide a secret order that we just haven't found yet.

The Paper's Discovery: Chaos in the Binary Code

In this paper, mathematician Ralf Stephan investigates the binary expansion of powers of three ( $3^m$ ). He asks a very specific question: As these numbers get bigger and bigger, do their binary digits eventually settle into a repeating loop, or do they stay messy and unpredictable?

The paper proves two main things, both of which confirm that the binary code of $3^m$ is delightfully chaotic and refuses to be tamed by simple repetition.

First, the "No-Loop" Rule:
The author proves that for any fixed repeating pattern you might try to find (say, a pattern that repeats every 5 digits, or every 100 digits), the binary code of $3^m$ will eventually break that pattern. It's as if you are trying to force a wild animal to march in a perfect circle; no matter how long you wait, the animal will eventually step out of line. The paper shows that as the power $m$ gets larger, the number of times the binary code "breaks" this periodicity grows. Specifically, the number of these breaks grows roughly like $\frac{\log m}{\log \log m}$ .

To use an analogy: Imagine the binary digits of $3^m$ are a long line of dancers. If you try to make them dance in a repeating step (a period), the paper proves that the longer the line gets, the more dancers will inevitably mess up the step. The paper calculates that the number of "mess-ups" increases as the number gets bigger, meaning the dance never settles into a perfect, boring loop. Even if you look at a window of the dance floor that is as deep as a fixed power of the logarithm of $m$ , you won't find a perfect repeating pattern.

Second, the "Maximum Variety" Rule:
The second finding is about how many different "chunks" of the binary code exist. If you take a small slice of the binary string (say, 10 digits long), how many different combinations of 0s and 1s can you find? The paper proves that for large enough powers of three, the number of different chunks of length $n$ is at least $n + 1$ .

In everyday terms, this means the binary code is "maximally complex" at the low end. It's not just random; it's richly random. If you have a string of length $n$ , the simplest possible pattern (like a perfect loop) would only have $n$ different chunks. But $3^m$ has at least $n + 1$ . It's like a deck of cards that, no matter how you shuffle it, always manages to produce one more unique hand than the bare minimum required to be considered "not boring." This proves that the low-order digits of $3^m$ are as diverse and unpredictable as they can possibly be without being infinite.

How Sure Are We?
The author is extremely confident in these results. The paper doesn't just guess or simulate; it provides a rigorous mathematical proof. The logic relies on a powerful tool called "linear forms in logarithms," which acts like a mathematical magnifying glass to show that if the patterns were simple, the numbers would have to be impossibly small or contradictory. The paper also mentions that these proofs have been formally verified by a computer program called Lean 4, which double-checks every logical step to ensure there are no errors. So, we can be certain that the binary expansion of powers of three is aperiodic and has full subword complexity.

In short, the paper tells us that the powers of three are the ultimate rebels in the world of numbers. They refuse to fall into a predictable rhythm, and their binary code is a treasure trove of unique, non-repeating patterns that grow more complex as the numbers get larger.

Technical Summary: Aperiodicity and Subword Complexity in the Binary Expansion of Powers of Three

Problem Statement
This paper investigates the fine structural properties of the binary digits of integers of the form $3^m$ . While previous work established that the number of non-zero binary digits ( $s_2(3^m)$ ) and the number of "blocks" (maximal runs of identical digits) tend to infinity as $m$ increases, these results do not fully characterize the arrangement of these digits. Specifically, the paper addresses two gaps:

Aperiodicity: Do long periodic patterns (runs of period $p$ ) exist in the binary expansion of $3^m$ ? Previous results ruled out long constant runs (period $p=1$ ), but the behavior for fixed periods $p > 1$ was unknown.
Subword Complexity: Does the finite binary word formed by the low-order digits of $3^m$ exhibit "full" complexity? In the context of infinite words, the Morse–Hedlund theorem states that subword complexity $p(n) \le n$ implies eventual periodicity. The paper seeks to determine if the finite word of $3^m$ satisfies the lower bound $p_{3^m}(n) \ge n+1$ for sufficiently large $m$ , effectively proving it is not "too simple" or periodic within its length.

Methodology
The proofs rely on a combination of transcendental number theory and combinatorial word analysis:

Linear Forms in Logarithms: The core engine is the effective theorem of Baker and Wüstholz regarding linear forms in logarithms of algebraic numbers. The paper utilizes this to establish "gap principles." The logic follows: if a long periodic stretch exists in the binary expansion of $3^m$ $3^{m}$ , it forces a specific integer identity that results in a non-zero linear form $\Lambda$ $Λ$ in logarithms of 2, 3, and auxiliary integers. The Baker–Wüstholz theorem provides a lower bound on $|\Lambda|$ $∣Λ∣$ , which contradicts the smallness implied by the existence of a long periodic window.
- Novelty: The paper introduces a new period- $p$ run estimate (Lemma 2.2). While classical results use three-term linear forms to bound constant runs, this work derives a four-term linear form to bound periodic runs of arbitrary fixed period $p$ .
Combinatorial Propagation: To address subword complexity, the paper employs a finite quantitative version of the Morse–Hedlund theorem (Lemma 4.1). This lemma establishes that if a word has low subword complexity (at most $n$ distinct factors of length $n$ ), it must contain a long periodic factor. This periodic factor is then fed into the period- $p$ run estimate to derive a contradiction for large $m$ .
Formal Verification: All theorems and lemmas in the paper have been formally verified using the Lean 4 proof assistant.

Key Contributions and Results

1. Aperiodicity of Period- $p$ Runs (Theorem A)
The paper proves that for any fixed period $p \ge 1$ , the number of positions where the binary expansion of $3^m$ breaks $p$ -periodicity, denoted $B_p(3^m)$ , grows asymptotically.

Result: $B_p(3^m) \ge \frac{\log m}{\log \log m + C_p} - 2$ for a constant $C_p > 0$ .
Implication: No window of the binary expansion of $3^m$ deeper than a fixed power of $\log m$ can be $p$ -periodic. This generalizes the known result for $p=1$ (Blecksmith–Filaseta–Nicol; Bugeaud–Kaneko) to all fixed periods.

2. Full Low-Order Subword Complexity (Theorem B)
The paper establishes a lower bound on the subword complexity of the finite binary word formed by the low-order digits of $3^m$ .

Result: For every length $n \ge 1$ , the complexity function satisfies $p_{3^m}(n) \ge n + 1$ for all sufficiently large $m$ .
Threshold: The threshold $m$ is effective. It occurs when the linear growth of the number of digits $M(3^m) \approx m \log_2 3$ overtakes a bound of order $n^2 \log m$ derived from the period- $p$ run estimate.
Implication: The finite word of $3^m$ is not eventually periodic in the sense of having low complexity; it possesses "full" complexity relative to its length, satisfying the condition that prevents periodicity in infinite words.

Significance and Claims
The author claims these results strengthen the understanding of the distribution of binary digits in powers of three in two specific directions:

Extension of Known Bounds: While Stewart's theorem and subsequent work established that $3^m$ has few sparse digits and many blocks, this paper extends the aperiodicity result to any fixed period $p$ , not just constant runs.
Finite vs. Infinite Context: The paper distinguishes its contribution from studies on algebraic irrationals (which have infinite expansions). It provides the first quantitative results on digit changes and subword complexity specifically for the finite word of a single power $3^m$ .
Optimality: Theorem B is presented as the analogue of the Morse–Hedlund theorem for the finite digit word of $3^m$ , lying at the "linear-forms optimum." The paper notes that proving superlinear per-word complexity is a separate, harder question not addressed here.

The work relies on the interplay between the arithmetic properties of $3^m$ (via Baker's theory) and the combinatorial structure of its digit string, providing effective lower bounds on the "disorder" or aperiodicity inherent in these numbers.

The Secret Life of Numbers: A Journey into Binary Patterns

The Paper's Discovery: Chaos in the Binary Code

More like this