The entropy-rate dimension formula for self-similar measures

The explanation

Start with a number line and two moves. One move shrinks everything toward 0 by a factor of 3. The other shrinks by 3 and then shifts right by 2/3. Flip a fair coin again and again, and stack the chosen moves one inside the next. The point you land on is random. Its chances pile up on a fine dust of points called the Cantor set. That pile of chance is a self-similar measure [chance spread so it repeats, scaled down, inside each piece].

How spread out is that dust? Mathematicians answer with the Hausdorff dimension [a fullness score: a point scores 0, a line segment 1]. Here the answer is a ratio. Each coin flip adds 1 bit [the information in one fair coin flip] of information. Each move zooms in by a factor of 3, which is about 1.585 bits of zoom. Divide 1 by 1.585 and you get about 0.631. That is the dimension of the Cantor measure.

Now change the moves. Use three of them, each picked with chance 1/3. All three shrink by 3. The first adds nothing, the second adds 1, and the third adds 4/3. Each step now carries about 1.585 bits of information, the same as its zoom. The simple ratio says the dimension is 1. But two different routes can give the same map. "Add 1, then add 1" and "add 4/3, then add nothing" both send x to x/9 + 4/3. Such a collision is an exact overlap [two different move sequences of equal length giving the same map].

Collisions waste information, so the paper counts maps instead of routesSource 1. With two steps there are 9 routes but only 8 different maps. The information per step falls to about 1.474 bits. The ratio falls to about 0.93. With fourteen steps, 4,782,969 routes give only 832,040 different maps. The ratio falls to about 0.854. The limit of this per-step information is the random-walk entropy rate [long-run information per step, counting distinct maps].

The paper proves a single formula for every such system on the lineSource 2. The dimension equals the entropy rate divided by the average zoom per step. The average zoom is called the Lyapunov exponent. If that ratio is above 1, the dimension is 1. The shrink factors may differ from move to move and may flip direction. Moves may repeat and routes may collide. This was the entropy-rate dimension conjecture, stated as Conjecture 3 in a survey by Péter VarjúSource 3.

The paper first proves, in a short section, that the dimension can never exceed the ratioSource 4. The hard part is showing it never falls below. When the pieces are kept apart, the answer has long been known. Moran in 1946 and Hutchinson in 1981 found the dust's dimension in that case. They assumed the open set condition [a rule keeping pieces apart]. In 2014 Michael Hochman showed that a drop in dimension forces maps to crowd together extremely fast. His work gives the formula under a mild separation condition. Later papers proved formulas without it in special cases. Rapaport did so in 2022 for algebraic shrink factors, assuming no exact overlaps. Rapaport and Varjú did so in 2024 for rational shifts with one common positive shrink factor. Our three-move example falls in that last case.

The obstacle is maps that come extremely close without ever being equalSource 5. In 2021 Baker, and separately Bárány and Käenmäki, built examples of this. Their pieces never collide but approach each other arbitrarily fast. So having no exact overlaps gives no floor on how close two maps can get. A proof for all systems must work without any such floor. Its key estimate finds hidden information at arbitrarily fine scales, however close the maps sitSource 6.

Return to the three moves. The theorem says their dimension is exactly the limit of the falling ratio, so at most about 0.854. Swap the shift 4/3 for any real number t. Whenever no routes collide, the dimension is now given by the simple ratio, for every choice of chances. For equal chances, earlier work on this three-map family left a small exceptional set of parameters. The paper also derives the matching formula for the dust itself, not just the measure on itSource 7. The result is about dimension onlySource 8. It says nothing about whether the measure has a density. The proof gives no explicit bound on the fine scales it usesSource 9.

How certain is this? A computer proof checker called Lean has a formal proof of the main formula. Lean also proves two consequences without exact overlapsSource 10. One covers a common positive shrink factor. The other is the formula for the dust. Whether the measure has a density lies outside these statements. No specialist review has been published.

What it doesn't show. This does not say whether the measure has a density. It also gives no explicit bound on the fine scales the proof uses.