Three arrows in and three out

Two arrows in and two out counted the ways to put an arrow on every edge of a graph so that every point has as many arrows in as out — the Eulerian orientations, so called because an Eulerian circuit, walked once round, hands every edge such an arrow. On the square grid, where every point has four edges, that is two in and two out, and the count is the residual entropy of ice: water molecules sit at the points of a lattice, each hydrogen sits closer to one of the two oxygens its bond joins, and every oxygen must have exactly two hydrogens close to it. Linus Pauling estimated in 1935 that there are about 1.5 arrangements per molecule, and Elliott Lieb found in 1967 that on the square grid the exact number is $(4/3)^{3/2} = 1.5396$.

That essay ended on the case it could not settle: three dimensions. Real ice is three-dimensional, its oxygens on a lattice with four neighbours each, and the simplest three-dimensional grid of all — the cubic grid, six neighbours per point — has the same question with three in and three out. Nobody knows the answer for either. What can be done is to count exactly on pieces of the grid that wrap round on themselves, and to see where the counts point.

Pauling’s count #

The estimate is quick enough to do in one’s head, and every later number in this essay is measured against it. The cubic grid has three edges per point — each point has six, and each edge is shared by two points — so $n$ points carry $3n$ edges and $2^{3n} = 8^n$ arrangements of arrows altogether. At a single point, the six arrows can be arranged in $2^6 = 64$ ways, and exactly $\binom{6}{3} = 20$ of them have three arrows in.

If each point were balanced independently, with probability $20/64$, the number of arrangements with every point balanced would be $8^n \times (20/64)^n = 2.5^n$: Pauling’s estimate, 2.5 per point. The same reasoning on the square grid gives $4^n \times (6/16)^n = 1.5^n$, the number Pauling gave for ice. The points are not independent — every edge is shared by two of them, and its arrow is in for one exactly when it is out for the other — so the estimate is not obviously right in either direction.

It turns out to be right in one direction. Alexander Schrijver proved in 1983 that for every graph in which every point has even degree, the number of Eulerian orientations is at least $\prod_v \binom{d_v}{d_v/2}/2^{d_v/2}$ — exactly Pauling’s product. So 2.5 per point is a lower bound for the cubic grid, and 1.5 for the square grid, where Lieb’s exact 1.5396 sits just above it. The question for three dimensions is how far above 2.5 the truth lies.

Counting on a prism #

Exact counts come from a transfer matrix. Slice the grid into horizontal layers. A layer of a prism is an $a \times b$ grid of points, wrapped round as a torus so that every point has four horizontal neighbours, and the layers are stacked one above the next, each point joined to the point directly above it. Record, as the state between two layers, the direction of each of the $ab$ vertical edges joining them: $2^{ab}$ possible states. Given the state below a layer and the state above it, every point of the layer knows two of its six arrows, and the number of ways to orient the $2ab$ horizontal edges so that every point ends up with three in is a definite number. That number, for every pair of states, is an entry of the transfer matrix $T$.

For a 3 × 3 cross-section the states number $2^9 = 512$ and each layer has 18 horizontal edges, so filling in the matrix means checking $2^{18} = 262{,}144$ orientations of a layer and, for each, the states that fit it. The number of balanced arrangements of a prism $M$ layers tall with its top glued to its bottom is then the trace of $T^M$, and for a very long prism the count grows like $\lambda^M$, where $\lambda$ is the largest eigenvalue of $T$. Divided among the $ab$ points of a layer, the count per point of the infinite prism is $\lambda^{1/ab}$.

The hero shows the three cross-sections that can be handled this way. A 2 × 2 cross-section gives 2.7937 per point, 2 × 3 gives 2.6815, and 3 × 3 gives 2.5871. All three are above Pauling’s 2.5, as Schrijver’s theorem says they must be, and they fall as the cross-section widens. The next cross-section, 3 × 4, would need a matrix with $2^{12} = 4{,}096$ rows built from $2^{24}$ layer orientations, and 4 × 4 would need $2^{16}$ rows; with a cleverer transfer, row by row within each layer, those sizes are within reach of a large computation, but not of a figure.

Exact counts on small boxes #

The same matrix gives exact counts for closed boxes: prisms glued top to bottom as well as round the sides, so that every point has six neighbours and the grid has no edge at all.

The 2 × 2 × 2 box has 9,600 balanced arrangements, the 2 × 2 × 3 box 443,520, the 2 × 3 × 3 box 120,083,840, and the 3 × 3 × 3 box exactly 440,105,291,264. Two boxes that are the same shape turned round — 2 × 2 × 3 and 2 × 3 × 2 — give the same count, as they must, which is a check on the matrices: the count of one is a trace over layers stacked in one direction and the count of the other a trace over layers stacked in another. Per point the counts are 3.146, 2.955, 2.811 and 2.699, larger than the prisms’ values because a small box is full of short loops round its glued directions, and each short loop is an extra way for arrows to balance.

That shrinking is visible directly along a single prism.

One layer, glued to itself, gives 3.485 per point; two layers 2.811; three 2.699; six 2.629. The infinite prism’s 2.5871 is the limit, and the excess falls roughly in proportion to one over the number of layers, because a closed box’s count is a sum over every eigenvalue of the transfer matrix, not only the largest. The length of the prism is the easy direction. The width is the hard one, and it is the width that decides how far the hero’s numbers are from the answer for the whole grid.

How far a narrow prism is from the whole grid #

The square grid is where the overshoot of a narrow cross-section can be measured, because there the answer is known. The same transfer matrix, with layers that are rings of $L$ points instead of tori, gives the count per point on infinite strips of the square grid.

A strip of width 2 overcounts by 12.5 per cent, a strip of width 3 by 3.1 per cent, and a strip of width 9 by 0.33 per cent, with odd and even widths alternating in how much they overshoot. In the plane, then, a cross-section of three points is already within a few per cent of the truth. The cube’s cross-sections are two-dimensional, so a 3 × 3 cross-section is the analogue of a strip of width 3 in both directions at once, and if its overshoot is of the same kind, the cubic grid’s value is a few per cent below 2.587 — somewhere above Schrijver’s 2.5 and below the 3 × 3 prism.

That is an argument from analogy, not a bound. Nothing proves that the prisms’ values decrease to the grid’s value as the cross-section grows, or that a 3 × 3 cross-section overshoots by a few per cent rather than more. In the plane, strips approach Lieb’s value from above at every width computed, and the cubic prisms here fall as their cross-section widens, which is consistent with the same behaviour; but the exact location of the cubic grid’s value is, on present knowledge, an open question with 2.5 below it and 2.587 very probably above.

Why the square grid could be solved and the cube cannot #

Lieb’s solution of square ice is one of the great exact results of statistical mechanics, and the reason it works explains why the cube resists. The square grid’s transfer matrix, for a strip of any width, has a hidden structure: it commutes with a whole family of other matrices, and its eigenvectors can be written down by an ansatz due to Hans Bethe, as superpositions of plane waves whose wave numbers satisfy a finite set of equations. Taking the width to infinity, those equations become an integral equation that can be solved, and the solution gives $(4/3)^{3/2}$. The same structure underlies the alternating-sign matrices, which are square ice with fixed walls, and the exact count $1, 2, 7, 42, 429, 7436, \ldots$ of them.

The cubic grid’s transfer matrix has no such structure known. Its states are patterns on a two-dimensional cross-section, not on a line, and the Bethe ansatz has no analogue for them. This is the general situation in statistical mechanics: many models are exactly solvable in two dimensions, through precisely this kind of hidden commuting family, and almost none in three. The three-dimensional Ising model, the most famous unsolved problem in the subject, fails for the same reason.

The same wall in every exactly solved model #

Square ice is one of three counting problems on the square grid that were solved exactly in the twenty years after 1944, and all three stop at the same wall. The first was Lars Onsager’s solution of the two-dimensional Ising model in 1944. The second was the count of domino tilings, found in 1961 by Pieter Kasteleyn and by Harold Temperley and Michael Fisher, through a determinant whose signs make it count: the number of tilings of a large square grows like $e^{G/\pi}$ per square, with $G$ Catalan’s constant. The third was Lieb’s ice. Each solution found a hidden algebraic structure in the two-dimensional problem — a Pfaffian for the dominoes, a commuting family of transfer matrices for ice and for Ising — and in each case nobody has found the corresponding structure in three dimensions.

For dominoes the failure has been made precise: counting the domino tilings of a three-dimensional region is a problem of the hardest counting class, as hard as counting the solutions of an arbitrary logical formula, which is strong evidence that no determinant formula exists. For three-dimensional ice and Ising no such hardness result for the grid’s entropy is known, and no formula either; the problems are simply open. The two-dimensional solutions also come with exact descriptions of what large random configurations look like — the frozen corners of the Aztec diamond for dominoes, and analogous arctic curves for ice with fixed walls — and three-dimensional analogues of those pictures are known only by simulation.

That is the larger reason the cubic grid’s count is hard. It is not that the transfer matrices are large; the plane’s are infinitely large too, as the width grows. It is that in the plane the infinitely large matrices are tame, through structure nobody has found one dimension up.

Ice, real and imagined #

The cubic grid is not the shape of real ice. In ordinary ice the oxygens sit on a lattice in which each has four neighbours arranged at the corners of a tetrahedron, and the condition is two hydrogens in and two out at every oxygen — the same rule as square ice, on a three-dimensional lattice. Pauling’s estimate for real ice is 1.5 per molecule, and it agrees with the measured residual entropy of ice — the disorder ice retains as it is cooled towards absolute zero — to within about one per cent, which was one of the early triumphs of statistical thinking about molecules. Series expansions by John Nagle in 1966 refined it to about 1.5069, a small correction above Pauling’s value, and no exact answer exists.

The cubic grid with three in and three out is a mathematical relative of that problem rather than a physical one, chosen because its geometry is the simplest in three dimensions and its transfer matrices are the easiest to build. It shares the essential difficulty: a local rule at every point, constraints shared along every edge, and a count that is easy to estimate, easy to bound below, and impossible, so far, to compute exactly.

The other half of an Euler argument #

The connection to Euler’s bridges is closer than the language of ice suggests. Euler’s theorem says that a connected graph has a circuit using every edge once exactly when every point has even degree, and an orientation in which every point has as many arrows in as out is exactly what such a circuit leaves behind. Every Eulerian circuit of the cubic box gives an Eulerian orientation by following the walk, and the same parity argument that decides which streets a postman must walk twice decides whether any balanced orientation exists at all — on a grid where every point has even degree, it always does. The converse needs more: an Eulerian orientation of a connected graph always has at least one directed circuit that follows it, and the BEST theorem counts how many — but different orientations have very different numbers of circuits. Counting orientations is the simpler problem, and on the cubic grid even that is open.

Bracketing the cubic grid’s value #

The value for the whole grid. Every number drawn is exact for its piece of grid — a prism with a small cross-section or a box glued on all sides — and none is the cubic grid’s own value. The figures bracket it between Schrijver’s proven 2.5 and the computed 2.587 only if narrow prisms overcount, which is expected and not proved.

Larger cross-sections. The method builds the full transfer matrix from every orientation of a layer, which limits it to cross-sections of nine points. Row-by-row transfer matrices, which add one point of the cross-section at a time, and series expansions in the style of Nagle’s reach much further; the figures show the method and the first three steps of the sequence, not what a dedicated computation can do.

Doubled edges. A box with a side of 2, glued to itself, has two edges between neighbouring points in that direction. The counts are correct for that multigraph, and they are not counts for a piece of the true cubic grid, which is why the boxes with a side of 2 sit furthest above the trend.

Still open: ice in three dimensions #

What is the number of Eulerian orientations of the cubic grid per point? Above 2.5 and, on the evidence, a little below 2.587; beyond that, unknown in closed form, and the same is true of real ice, of the diamond lattice, and of every other three-dimensional grid. In the plane, Lieb’s exact answer depended on an integrable structure that three-dimensional grids do not have, and no other route to an exact answer is known. Even the qualitative question of how much the answer exceeds Pauling’s estimate — whether the excess is small, as for real ice, or substantial — has only numerical answers.

The square grid’s companion problems are open too in three dimensions: the counts with fixed walls, whose two-dimensional versions are the alternating-sign matrices with their product formula, have no known formula in a cube; and the shapes of large random arrangements, which in the plane freeze into ordered corners with a disordered middle, are understood in three dimensions only through simulation. The one thing that holds in every dimension is Schrijver’s theorem: however a grid is built, as long as every point has an even number of edges, Pauling’s simple product is never too large.