A carpet with two dimensions

Every set on this ladder so far has been self-similar: built from copies of itself scaled by the same factor in every direction. For such a set the box dimension and the Hausdorff dimension agree, and that agreement is a theorem rather than a coincidence.

Change one thing. Contract horizontally by a quarter and vertically by a half, so the copies are rectangles rather than small squares, and the two numbers come apart.

Both numbers are correct. They answer different questions, and on a set of this shape the questions have different answers.

What a self-affine set is #

Take the unit square, divide it into $n$ columns and $m$ rows with $n > m$, and choose a set of cells. The map sends the whole square onto each chosen cell, contracting horizontally by $1/n$ and vertically by $1/m$. Iterate, and what is left is the carpet.

The construction is exactly the one that produces the Sierpiński carpet — and, at a different grid, the Cantor set’s two-dimensional cousin — with one difference: there the grid was three by three and the contractions were equal, and here they are not. A map that contracts differently in different directions is affine rather than a similarity, and the word for the resulting set is self-affine.

At depth $k$ the carpet is $N^k$ rectangles, each $n^{-k}$ wide and $m^{-k}$ tall. Since $n > m$, those are wider than they are tall in the sense that matters — $n^{-k}$ is the smaller number, so the rectangles are narrow and comparatively tall.

That aspect ratio is the whole story. It grows without bound: at depth $k$ the pieces are $(n/m)^k$ times taller than they are wide, so however far the construction is taken the pieces never become square.

Why a grid gives the larger answer #

A grid of squares of side $\varepsilon$ has to resolve the set at one scale in both directions at once. Take $\varepsilon = n^{-k}$, the width of a piece. Each piece is then one square wide and $(n/m)^k$ squares tall, so covering it takes $(n/m)^k$ squares — the grid pays for the piece’s height even though the piece is a single thin sliver.

Hausdorff’s definition may use covers of any shape and size. It can cover a whole column of pieces with one set, and the diameter it pays is the column’s height rather than the sum of the pieces’ heights. Wherever the pieces stack up in a column, grouping them is cheaper, and grouping is available to Hausdorff and not to the grid.

So the two numbers differ exactly when the pieces are distributed unevenly among the rows: a row with many cells offers many pieces to group, a row with few offers few, and the grid cannot exploit the difference.

The gap is a measure of how unevenly the rows are loaded, and it closes to nothing when they are loaded equally.

The two formulas #

Both dimensions have closed forms, found independently by Bedford and by McMullen in 1984.

Write $N$ for the number of chosen cells, $t_j$ for how many are in row $j$, and $r$ for the number of rows that hold any at all. Then

$$\dim_B = \frac{\log r}{\log m} + \frac{\log(N/r)}{\log n}, \qquad \dim_H = \frac{1}{\log m}\,\log\!\Big(\sum_j t_j^{\log m/\log n}\Big).$$

Both are computed in the figures, and the box one is checked against an actual count of occupied squares — a million of them at depth five — which agrees to four decimal places.

The shapes of the two formulas say what each is doing.

The box formula is a sum of two terms with different bases. The first counts the rows in the coarser scale $m$ and the second counts the average number of cells per occupied row in the finer scale $n$. That separation is exactly the grid’s inability to trade one direction against the other: it resolves vertically at one rate and horizontally at another, and the two contributions add.

The Hausdorff formula has the row counts inside a sum, raised to a power. That power, $\log m/\log n$, is below one, so the sum is concave in the row counts, in the sense that a chord lies below the curve — and a concave function of a distribution is largest when the distribution is even. Which is the previous section’s observation, arriving as a fact about concavity: the two dimensions agree exactly when the $t_j$ are equal, and the gap grows with their spread.

So the gap is a Jensen inequality. A concave function’s value at an average exceeds the average of its values, and that single fact is the whole of why the Hausdorff dimension is the smaller of the two here.

What the counted value confirms and what it cannot #

The counting in the figures is a real measurement and it confirms one of the two formulas.

At depth $k$ with a grid of side $n^{-k}$, the count of occupied squares is computed by building the carpet’s rectangles and marking every square they meet. At $k = 5$ that is a hundred thousand squares for the default carpet and the reported dimension is $1.6610$ against the formula’s $1.6610$.

Nothing in the figures counts anything relevant to the Hausdorff dimension, and that is not a shortcoming of the implementation. Hausdorff dimension cannot be computed by any counting, because it is an infimum over a family of covers with no parameterisation. The number $1.5850$ is quoted from McMullen’s theorem, and the figure’s honest claim is that the other number is right.

Reading the box formula as two measurements #

The box formula’s two terms can be read off the picture, and doing so is the quickest way to see why it is a sum rather than a single logarithm.

Cover the carpet with squares of side $m^{-k}$ — the height of a piece rather than its width. At that scale each piece fits inside one square vertically and the pieces in a row have collapsed together horizontally, so what is counted is the number of distinct rows the construction reaches: $r^k$ of them. The dimension read at that scale alone is $\log r/\log m$, which is the formula’s first term.

Now refine to squares of side $n^{-k}$. Each of those coarse squares contains the pieces of one row, and the pieces within a row are separated horizontally at the finer scale, so each coarse square breaks into about $N/r$ pieces per step. The extra growth is $(N/r)^k$ over a scale change of $n^k$, which is the second term.

So the grid measures the set twice, at two scales, and adds the answers — and it has to, because the set genuinely has two scales in it. A self-similar set has one scale and one term.

That reading also explains the bases. The first term divides by $\log m$ because the vertical structure repeats at rate $m$; the second by $\log n$ because the horizontal structure repeats at rate $n$. A dimension is a logarithm of a count over a logarithm of a scale, and when there are two scales there are two of these to add.

What the aspect ratio does over time #

There is a way of seeing the whole phenomenon in one number, and it is the aspect ratio of a piece.

At depth $k$ the pieces are $n^{-k}$ by $m^{-k}$, so the ratio of height to width is $(n/m)^k$. For the default carpet that is $2^k$: at depth four the pieces are sixteen times taller than wide, at depth ten a thousand times, and it grows without bound.

A grid never catches up with that. Whatever square size is chosen, at a deep enough level the pieces are far from square, and the mismatch between the shape the grid offers and the shape the set is made of never goes away. That is the structural reason the two definitions cannot converge on such a set — it is not that the grid is coarse, it is that the grid is the wrong shape at every scale.

For a self-similar set the ratio is $1$ at every depth. The pieces are the same shape as the boxes, forever, and that is the hypothesis the agreement theorem is really about. A linear map’s effect on a circle is the same distinction one field away: a similarity takes circles to circles and a general map takes them to ellipses, and everything that goes wrong here goes wrong because the ellipse gets thinner at every step.

What the separation costs the subject #

A set with two different dimensions is not a curiosity; it is the generic situation once similarities are given up, and giving them up is unavoidable.

Attractors of maps are self-affine. The Hénon attractor is produced by a map that stretches in one direction and contracts in another, at different rates, so it is affine rather than similar and there is no reason for its two dimensions to agree. The value quoted for it is a box dimension, because that is the one a computation can produce.

The formulas above do not generalise. McMullen’s and Bedford’s results are for carpets — grids, aligned rectangles, an exact self-affine structure. For a general self-affine set the Hausdorff dimension is known only under conditions, and there is a standard expression, the affinity dimension, which is an upper bound and is achieved for almost every choice of the linear parts and not for every choice.

And “almost every” is doing real work there. Falconer’s theorem from 1988 says the Hausdorff dimension equals the affinity dimension for almost all translations of the pieces, in the sense of measure. The carpets are exactly a family where the translations are not generic — they are aligned to a grid — and the theorem says nothing about them, which is why they had to be handled separately and why they are the standard counterexample.

The relationship between those two results is worth stating carefully, because it is easy to read one as overturning the other. Falconer’s says the tidy answer holds off a set of exceptional configurations of measure zero. McMullen’s and Bedford’s describe a family that lies inside that exceptional set — and the family is not obscure, since alignment to a grid is what somebody constructs when asked for an example.

So the generic case and the constructible case are different cases, and a subject whose examples are all constructed will meet the exceptional one first. That is a recurring hazard rather than an accident of this problem: a randomly chosen object is generic by definition, and every object anybody writes down was chosen.

Where the account needs care #

The grid must be aligned with the construction for the count to be exact. The counts here use grids of side $n^{-k}$, which line up with the carpet’s own divisions, so the count is exact rather than an estimate. A grid at any other size gives a count that is right only in the limit.

The two contractions must genuinely differ. With $n = m$ the map is a similarity, the two formulas collapse to the same expression, and the gap is nought whatever the cell distribution — which is the theorem the rung below relied on.

Rows and columns are not interchangeable. The formulas are stated for the direction of stronger contraction being horizontal. Transposing the carpet transposes which formula applies, and the two dimensions of a carpet and its transpose are generally different numbers.

And the Hausdorff value is quoted, not computed. Everything on this page that is measured is a box count. The Hausdorff dimension enters as a formula from a theorem, and the essay’s claim about it rests on that theorem entirely.

That last one is worth one more sentence, because it is the shape of nearly every claim about Hausdorff dimension anywhere. The rung below recorded that upper bounds are exhibitions and lower bounds are arguments; here neither half is a computation. What can be checked is that the box count matches its formula, which the figures do at a million squares, and that the two formulas stand in the relation the theory says — Hausdorff at most box, with equality exactly when the rows are evenly loaded.

Those checks catch an implementation error and not a mistaken theorem, and saying which is which is the whole of the honesty available here. A figure that printed two numbers from two formulas and checked neither would look identical.

Two people, one year, two methods #

Tim Bedford’s thesis and Curt McMullen’s paper both appeared in 1984 and both contain the Hausdorff formula, arrived at independently and by different routes — Bedford through the thermodynamic formalism, McMullen by a direct construction of the optimal measure.

The simultaneity is worth noticing because of what it says about when a result becomes available. Neither method existed in 1918 when Hausdorff wrote his definition, and the question — do the two dimensions ever differ — could have been asked at any point in between. It became answerable when the machinery for building measures on self-similar sets was in place, and once it was, two people answered it in the same year.

A question waits for its tools rather than for somebody to think of it, which is a fair description of most of the sixty-six years between the definition and this example.

What the pictures cannot show #

The carpet is drawn at depth four, which is $625$ rectangles for the default; the object is the limit, and every drawn stage is a finite union of rectangles with dimension exactly two. The gap between the two dimensions is a property of the limit and of nothing drawn.

The gap itself is invisible. Two carpets with the same box dimension and different Hausdorff dimensions would look equally fractal, and nothing about the appearance of any of the figures says which number is which. The dimensions are printed beside the drawings because there is no other way to put them on the page.

And the box count, though exact, is exact at grid sizes chosen to line up with the construction. That is a legitimate measurement and it is a favourable one — a grid at an unaligned size would give a count that is off by a bounded factor, which vanishes in the limit and does not vanish in a figure.

The ladder from here #

Rungs above: a dimension from the map’s stretching rates, which is the method that works on an attractor with no construction rule at all. The affinity dimension and Falconer’s theorem, which say what happens for a generic self-affine set. Packing dimension, which is a third notion agreeing with Hausdorff on these carpets and not on everything. Multifractal analysis, where a set is split by the local scaling rate and each piece gets its own dimension. And the dimension of a projection, where a self-affine set can drop dimension in a direction a self-similar one cannot.

Two definitions that agreed for a reason #

The habit is about what to do when two definitions of the same thing keep agreeing.

Box dimension and Hausdorff dimension agree on every set the rung below drew, and it would be reasonable to conclude from that page that they are the same notion described two ways. They are not, and the agreement was a theorem with a hypothesis in it — self-similar, with equal contractions — which the examples all satisfied because they were the examples somebody chose.

A hypothesis satisfied by every example in front of a reader is a hypothesis that reads as an assumption about the world. The way to find it is the one this rung takes: change the least conspicuous ingredient — here, that the contractions were equal — and see what stops being true.

The reward for finding it is usually larger than the counterexample. Knowing that the two dimensions differ exactly when the rows are unevenly loaded, and that the gap is a Jensen inequality, is a better understanding of both definitions than agreement on a hundred examples would have given.