# An improved upper bound for the three dimensional dimer problem

AN IMPROVED UPPER BOUND FOR THE THREE DIMENSIONAL DIMER PROBLEM
Mihai Ciucu

Mathematical Sciences Research Institute Berkeley, California 94720 April, 1997
Abstract. Let be even and denote by ( ) the number of domino tilings of a cube of side
n

. The three dimensional dimer problem is to determine the limit 3 := limn!1 (log ( )) 3 (which is known to exist). The best previously known upper bound was found by Minc and is 1 12 log 6! = 0 54827 . In this paper we improve this bound to 0.463107.
` f n =n = : :::

n

f n

The dimer problem, which in dimension three is one of the classical unsolved problems in solid-state chemistry, is the following. De ne an brick to be a d-dimensional (d 2) rectangular parallelepiped with sides of integer lengths; we will always assume its volume to be even. A brick of volume 2 is called a dimer. The problem is to determine the number f (a1 ; : : : ; ad) of dimer tilings of the brick with sides of lengths a1 ; : : : ; ad. It is remarkable that for d = 2 this number can be expressed in closed form, as was shown independently by Fisher, Kasteleyn and Temperley (see 14] and 6]). In contrast, for d 3 no such formulas are known. Moreover, the number of dimer tilings of a brick of dimension at least three is not known even asymptotically. More precisely, Hammersley proved 4] that the sequence 1=(a1 ad ) log f (a1 ; : : : ; ad ) approaches a nite limit `d as ai ! 1, i = 1; : : : ; d. However, the exact value of `d is not known for d 3. The most important case for applications is the case d = 3 5] 7]. Various upper and lower bounds for `3 have been proved starting as far back as six decades ago, when Fowler and Rushbrooke 3] showed (assuming, based on physical and heuristic arguments, that the limit de ning `d exists) that 1 0 `3 2 log 3 = 0:54931::: This upper bound was improved by Minc 8] to 1=12 log 6! = 0:54827:::, which represents the best upper bound previously known.

1. Introduction

On the other hand, since `d is clearly a nondecreasing function of d, one obtains that a lower bound for `3 is given by `2 , which was determined by Fisher, Kasteleyn and Temperley to be

`2 = 1=

X
r
0

(?1)r =(2r + 1)2 = 0:29156:::

This lower bound has been improved several times, rst by Fisher 1] to 0.30187, then by Hammersley 5] to 0.418347 and nally by Priezzhev 11] to 0.419989. A conjecture due to Schrijver and Valiant 13] on lower bounds for permanents would imply, as noted by Minc 9], that `3 0:440075. Nagle 10] obtained the heuristic estimate of 0.446 for the actual value of `3. The main purpose of this paper is to prove the following result. Theorem1.1. `3 0:463107: Our proof employs the transfer matrix method to encode the dimer tilings of a (toroidal) brick as closed walks in a certain graph. Using the transfer matrix theorem we obtain a family of upper bounds for `3 expressed in terms of the largest eigenvalues of our graphs. The problem is then reduced to determining (or nding a good upper bound for) the largest eigenvalue of a certain nonnegative symmetric matrix of order 216. To this end, we take advantage of a certain group G of permutation matrices which commute with our matrix. It turns out that the eigenvalue we need to estimate is the same as the largest eigenvalue of the action of our matrix on the subspace of G-invariants. This is given by a sparse nonnegative matrix A of order 222. Finally, we use an elementary way to obtain upper bounds for the largest eigenvalue of A in terms of the trace of even powers of A. The bound in Theorem 1.1 is obtained by computing the 16-th power of A. We also show that knowledge of the exact value of the largest eigenvalue of A could improve the upper bound by at most lowering the last digit from 7 to 5. From the above outline of our proof it might seem that the success of our approach is conditioned by the progress in computational power that occurred since the previous upper bounds have been found. However, it turns out that one can derive by our method the already improved upper bound of 0.519093, and the largest computation involved in the process is nding the trace of the fourth power of a sparse matrix of order 22. Our approach to this problem seems not to have been considered before. In contrast to Minc's method, which used a general inequality for permanents to deduce an upper bound for `3 , our setup allows one to take advantage of the speci c problem at hand. It is probably this fact that accounts for the signi cant improvement in the upper bound. Let ft (k; l; n) be the number of dimer tilings of the toroidal brick T (k; l; n) of sides k; l and n. Clearly, f (k; l; n) ft(k; l; n), and therefore

2. A family of upper bounds
`3
n!1 n3 2

lim 1 log ft (n)

(2.1)

(here ft (n) stands for ft(n; n; n), and n is even). In fact, it follows from the results in 4] that equality holds in (2.1), but this will not be needed in our proof. De ne a weighted directed graph S as follows. Take the set of vertices of S to be the set of k by l 0-1 matrices. For two such matrices s and t, de ne the weight of the edge from s to t to be zero unless the supports of s and t are disjoint. If the supports are disjoint, consider a k l toroidal brick (i.e., a toroidal chessboard) and remove from it the unit squares corresponding to nonzero entries of s and t; de ne the weight of the edge from s to t to be the number of dimer coverings of the leftover part. Let (i) l , i = 1; : : : ; 2kl , be the eigenvalues of the adjacency matrix M of S . Since this k is a nonnegative matrix, by the Perron-Frobenius theorem its largest eigenvalue is real and positive. Denote it by k l . Note also that it follows from the de nition that M is symmetric, and hence all its eigenvalues are real.
Proposition 2.1.

ft (k; l; n) =

X
2kl

i=1

i n k l :
( )

Proof. Let T be a dimer tiling of the toroidal brick T (k; l; n). Regard our brick as a stack of n horizontal layers, each consisting of a k l toroidal array of unit cubes. In each such layer, write 1's in the unit cubes covered by a dimer extending into the next layer above (for the top layer, dimers extending into the bottom layer); write zeroes in the remaining unit cubes. In this way, our tiling is associated a closed walk C on n steps in the graph S . By the de nition of S , the weight of C (i.e., the product of the weights of its steps) is equal to the number of tilings of T (k; l; n) whose associated closed walk is C . Therefore, ft (k; l; n) is just the total weight of closed walks on n steps in S (if e1 e2 en is a closed walk, then ei ei+1 en e1 ei?1 is in general a di erent closed walk). Since by the transfer matrix theorem (see e.g. 12]) this is just the trace of M n, the statement of the Proposition follows.
Lemma 2.2. If l and n are even, we have

kn log

1

k n

n log 2 + kl log

1

1

k l:

Proof. Since all eigenvalues are real and l and n are even, we obtain using Proposition 2.1 that
3

( k n )l

X
2kn

= ft (k; n; l) = ft (k; l; n) =
i n k l i=1 2kl ( k l )n :
( )

i=1

i l k n
( )

X
2kl

The desired inequality follows by taking the logarithms of the extreme terms above and dividing through by kln. Proposition 2.3. For even k and l, we have 1 `3 kl log k l : Proof. Let n be even and set k = l = n in Proposition 2.1. Since all the eigenvalues are

real, we obtain

ft (n) =

X
2n

2

Taking the logarithm on both sides and dividing through by n3 we deduce 1 log f (n) 1 log 2 + 1 log : Setting l = k; k = n in Lemma 2.2 one obtains 1 1 1 log n n n log 2 + kn log k n : 2 n By (2.2), (2.3) and Lemma 2.2 it follows that

i=1

i n n n
( )

2 n ( n n )n :
2

n3

t

n

n2

n n

(2.2) (2.3)

n3 log ft (n) n log 2 + n2 log
2 1

1

1

1

n n k n k l:

n log 2 + kn log n log 2 + kl log
4

3

1

Since this is true for all even n, the statement of the Proposition follows from (2.1).

Remark 2.4. In fact, the arguments in 2] imply that

Therefore, since by 4] equality holds in (2.1), we obtain that `3 is the limit of the upper bounds of Proposition 2.3, as k; l ! 1. One can expect, in view of Remark 2.4, that as the values of k and l in Proposition 2.3 increase, the upper bounds get closer to the actual value of `3 . For k = 2, l = 4 we obtain the already improved bound of 0.518971 (it is interesting that the slightly weaker bound of 0.519093 can be obtained without using the computer; see Section 5). For k = 2, l = 6, only the relatively small improvement to 0.513456 is obtained. However, k = l = 4 yields the bound in Theorem 1.1. Consider the graph S de ned in the previous section. Denote its incidence matrix by M. Let s and t be two vertices of S (i.e., two k by l matrices with entries 0 or 1) and suppose the (s; t) entry of M is nonzero. By the de nition of S , this means that the supports of s and t are disjoint, and moreover, the board obtained from a k by l toroidal chessboard by removing the squares corresponding to the nonzero entries of s and t has at least one dimer covering. This clearly implies that the numbers of 1's in s and t have the same parity. Therefore, M is the direct sum of the incidence matrix of the subgraph of S consisting of vertices with an even number of 1's and the incidence matrix corresponding to vertices with an odd number of 1's; denote these two matrices by A and B , respectively. Let F be the set of vertices of S involving an even number of 1's. Regard A as a linear transformation on the vector space V with basis F . Let G be a group of symmetries of a k by l toroidal chessboard. The group G acts in a natural way by permutations on F . Extend this linearly to an action on V . Lemma 3.1. The matrix A commutes with the action of G on V . Proof. It su ces to check that for each vector s 2 F we have g A(s) = A(g s), for all g 2 G. This follows from the fact that g is a symmetry of the toroidal board. The following result is quite possibly known, but we were not able to nd it in the literature. Lemma 3.2. If N is a nonnegative matrix that commutes with a group of permutation matrices G, then the largest eigenvalue of N is the same as the largest eigenvalue of N acting on the subspace of G-invariants. The elegant argument given below is due to Phil Hanlon. Our original formulation of Lemma 3.2 assumed that G is abelian, and the proof used character theory (this weaker version su ces to prove Theorem 1.1, but a considerable amount of computational time can be saved using the stronger version).
5

lim f (n) = nlim kl log k l : !1 n!1 n3 t

1

1

3. Estimation of

4 4

Proof. By the Perron-Frobenius theorem we know that the eigenvalue of largest absolute value is real and positive, and among the eigenvectors of this eigenvalue there is one with nonnegative coordinates; denote it by v. De ne X g v: (3.1) v = 1
0

Since N commutes with G, v0 is also an eigenvalue for , and it is clear that v0 is Ginvariant. Moreover, since the coordinates of g v are a permutation of the coordinates of v, it follows from (3.1) that for any coordinate of v that is strictly positive, the corresponding coordinate of v0 is also strictly positive, so in particular v0 is nonzero. Let O1 ; O2 ; : : : ; Op be the orbits of the action of G on F . For 1 i p de ne X v = 1 g e;
i

jGj g2G

where ei is some xed element of Oi , i = 1; : : : ; p. Since the subspace V G of G-invariants P is the image of the projection : V ! V , = (1=jGj) g2G g, the vectors vi form a basis for V G . Since by Lemma 3.1 A commutes with G, V G is invariant under A. The matrix of the restriction of A to V G is given by

jGj g2G

i

0 1 X A 1 Avi = jGj A @ g ei g2G X 1
1 X = jGj g g2G = =
n X m=1 0 p X

= jGj

g2G

g Aei

n X

1 aim jGj

X

m=1

aim em

!

j =1 m2Oj

@X

1 aim A vj ;

g2G

g em
(3.2)

where n is the order of the matrix A. Therefore, by Lemma 3.2, in order to estimate the largest eigenvalue of AP su ces to it estimate the largest eigenvalue of the matrix AG whose (i; j ) entry equals m aim , the sum running over the elements of the orbit Oj . Let k = l = 4. It is easy to see that there exists a group of symmetries of the 4 4 toroidal chessboard isomorphic to the semidirect product of C4 C4 with D8 , where C4
6

is the cyclic group of order 4 and D8 is the dihedral group of order 8 (the three factors correspond to shifting the toroidal board vertically and horizontally, and to the symmetry group of a square). However, the full symmetry group is in fact three times larger than this. Indeed, the 4 4 toroidal chessboard is, quite remarkably, isomorphic to the four-dimensional hypercube (this useful observation is due to the referee). Therefore, its symmetry group is isomorphic to the semidirect product of (C2 )4 with the symmetric group S4 (the rst four factors correspond to re ections across hyperplanes parallel to the coordinate hyperplanes, while the last one corresponds to permuting the four coordinate axes). Choose G to be this group. The family F consists of 215 vectors. It turns out that the action of G on these vectors has 222 orbits, so the matrix AG whose largest eigenvalue we need to estimate is of order 222. Exact calculation of the eigenvalues of a matrix of this size is beyond the capabilities of (at least most) present-day computers. To resolve this we employ the following simple result. Lemma 3.3. Let C be a nonnegative matrix and let be its largest eigenvalue. If all eigenvalues of C are real, then for all i 1 we have (a) tr(C 2i )1=2i 2 (b) tr(C 2i+2 )=tr(C 2i ): Proof. Let 1 ; : : : ; q be the eigenvalues of C . Since they are real, we have tr(C 2i ) =
q X j =1

( j )2i

2

i:

To obtain (b), notice that since is the largest eigenvalue, one has tr(C 2i+2 ) =
q X q X j =1 j =1

( j )2i+2
2

( j )2i

= 2 tr(C 2i ): Since AG is sparse, its powers can be found in a reasonable time using the computer (we are indebted to John Stembridge for writing an e cient program to this end). The traces of the rst 16 powers of AG were found in about 24 minutes of CPU time. The traces of the 14-th and 16-th powers are

t14 = 1126977601503291741399637139638752100045480750 t16 = 3075161475953781009986362817937907270093976213987550:
7

Applying Lemma 3.3 to AG , we obtain that the largest eigenvalue A of A satis es 1651:87

The matrix B corresponding to the vertices of S with an odd number of 1's can be analized in a completely analogous way. Its G-invariant part B G turns out to have order 181. The trace of the square of B G is found with the computer to be Lemma 3.3(a) with i = 1 implies therefore that
B

t 1=2 = t16
14

A

(t16 )1=16 = 1651:93 : : :

(3.3)

t02 = 2199876:

2199876 < 1484 < A : Thus 4 4 = A . Theorem 1.1 follows then from the upper bound in (3.3) and Proposition 2.3. From the lower bound in (3.3) it follows that (1=16) log 4 4 > 0:463104, and therefore the precise knowledge of 4 4 could bring only a very slight improvement on the bound from Theorem 1.1. The ideas in Section 2 can be generalized without di culty to the case of a d-dimensional brick. The only limitation is that the number of vertices in the corresponding graph Sd increases very fast with d, and therefore the size of the matrices whose largest eigenvalues we need to estimate quickly go beyond the capabilities of (at least today's) computers. However, we do obtain an improvement on the upper bound for `4 at a very small expense of computation time (in fact, as we will discuss below, this could almost be worked out by hand). We also indicate how this bound could be improved further by performing a longer computer calculation. Finally, we point out another feasible computer calculation that would quite likely improve the best known upper bound for `5 . However, since from the perspective of applications almost all attention seems to be concentrated on the threedimensional case, we did not carry out these computations. In analogy to Section 2, de ne the graph S = Sd to have its vertex set consisting of (d ? 1)-dimensional arrays of 0's and 1's, the dimensions of the array being a1 ; : : : ; ad?1 . De ne the edge-weights of S in analogy to the de nition in Section 2. Let a denote the vector (a1 ; : : : ; ad?1 ). Let a be the largest eigenvalue of the incidence matrix of S . The following result can be proved using arguments similar to the ones in Section 2. Proposition 4.1. For even a1 ; : : : ; ad?1 , we have 1 log : `
d

p

4. Higher dimensions and other dimer enumeration problems

Let d=4 and choose a1 = a2 = a3 = 2. The incidence matrix M of S is again (as in Section 3) the direct sum of two sparse matrices A and B ; both have order 128. Given
8

a1

a

the manageable size, one can use the computer to nd the rst few powers of A and B , and then deduce by Lemma 3.3 a good upper bound for 2;2;2 . Using Proposition 4.1, this yields

`4 0:662561;
which is slightly better than the best previously known upper bound of 1=16 log 8! = 0:662788:::, due to Minc 8]. (Note that if we exploit the fact that the natural action of the symmetry group of the cube commutes with A and B , the computation is reduced to the degree that it can almost be done by hand; see Section 5). We note that the case a1 = a2 = 2, a3 = 4 is also within reach: choosing G to be the symmetry group of the 2 2 4 toroidal brick, the matrix AG has order 1324. The case d = 5, a1 = a2 = a3 = a4 = 2 reduces to a calculation of smaller size. Finally, we mention that our method also applies to other dimer enumeration problems in three (or higher) dimensions that should be of comparable interest, e.g. for toroidal quotients of the body centered cubic lattice or face centered cubic lattice. Indeed, these lattices satisfy the three crucial properties required for the ideas in Section 2 to go through: (1) if g(a; b; c) is the number of dimer coverings of a toroidal quotient of sizes a; b and c then g is symmetric in a; b; c (2) the dimer coverings can be interpreted as closed walks in a certain weighted directed graph S and (3) the adjacency matrix of S is symmetric. As promised, we argue in this section that the case d = 3, k = 2, l = 4 can be worked out with minimal (conceivably even no) computer assistance. The matrix M has in this case order 28 , so the direct summands A and B both have order 128. Figure 5.1 illustrates the vertices of the graph S which give rise to A. Each such vertex, by de nition a 2 by 4 0-1 matrix (with an even number of 1's), is identi ed with a (toroidal) 2 4 chessboard whose unit squares corresponding to 1's in the matrix are shaded. Choose G to be the group generated by the shift one unit to the right and by the re ection in the horizontal and vertical symmetry axes of the board (so G is isomorphic to C4 C2 C2 ). The action of G on the vertices of A turns out to have the 22 orbits indicated in Figure 5.1. By (3.2), the largest eigenvalue of A is the same as the largest eigenvalue of the matrix AG of order 22 whose (i; j ) entry is obtained as follows: choose some element x in the i-th orbit and add up the weights of the edges of S from x to y, as y runs over the j -th orbit. This can be done by inspection from Figure 5.1. For example, let us nd the (6; 14) entry of our matrix AG . To this end, let x be the top element of orbit 6. Only the second, third, sixth and seventh elements of orbit 14 have their shaded squares in positions disjoint from the positions of the shaded squares of x. Moreover, by superimposing x and any of these four elements of orbit 14, the unshaded part of the resulting (toroidal) board has always two distinct dimer coverings. Therefore, AG (6; 14) = 8. Similarly, one obtains AG (6; 15) = 0 and AG (6; 21) = 4.
9

5. Concluding remarks

1 2 3

6

8

10

12

14

15

16

4

7

9

11

13

5

17

18

19

20

21

22

Most of the entries of AG turn out to be zero. This makes it very easy to compute its square, and therefore the trace of its second and fourth powers. The values of these traces are (5.1) The matrix B can be handled in a completely analogous way. As in Section 3, it turns out that the largest eigenvalue of B is strictly less than the largest eigenvalue of A. Thus,
10

Figure 5.1

t2 = 4462 t4 = 16369814:

by (5.1) and Lemma 3.3 one obtains for `3 the upper bounds of 0.52521 (from t2 ) and 0.519093 (from t4 ). We conclude with some comments on the case k = 4, l = 6. This would most likely improve on the upper bound in Theorem 1.1. However, unless one could nd some additional reductions besides the ones discussed in Section 3, the size of the data one needs to handle surpasses the limits of today's computers. Indeed, the matrix A has in this case order 223 , while the largest group G we can choose is the symmetry group of a 4 by 6 toroidal chessboard, which has 96 elements.

Acknowledgments. I wish to thank John Stembridge for many useful discussions and insights. I would also like to thank Richard Stanley and Curtis Greene for stimulating conversations and for their interest in this work. I am grateful to Michael Fisher and Alistair Sinclair for indicating useful references, and to the referee for helpful suggestions and for the careful reading of the manuscript. 1] J. A. Bondy and D. J. Welsh, A note on the monomer-dimer problem, Proc. Cambridge Philos. Soc. 62 (1966), 503{505. 2] M. Ciucu, Higher dimensional Aztec diamonds and a (2d + 2)-vertex model, pre3] 4] 5] 6] 7] 8] 9] 10]
print. R. H. Fowler and G. S. Rushbrooke, An attempt to extend the statistical theory of perfect solutions, Trans. Faraday Soc. 33 (1937), 1272{1294. J. M. Hammersley, Existence theorems and Monte Carlo methods for the monomerdimer problem, \Research papers in statistics: Festschrift for J. Neyman," John Wiley, London, 1966, 125{146. J. M. Hammersley, An improved lower bound for the multidimensional dimer problem, Proc. Cambridge Philos. Soc. 64 (1968), 455{463. P. W. Kasteleyn, The statistics of dimers on a lattice, I: the number of dimer arrangements on a quadratic lattice, Physica 27 (1961), 1209{1225. H. Minc, An asymptotic solution of the multidimensional dimer problem, Linear and Multilinear Algebra 8 (1980), 235{239. H. Minc, An upper bound for the multidimensional dimer problem, Math. Proc. Cambridge Philos. Soc. 83 (1978), 461{462. H. Minc, Review of the paper \On lower bounds for permanents" by A. Schrijver and W. G. Valiant, Math. Reviews, January 1982, article 82a:15004, 63. J. F. Nagle, New series-expansion method for the dimer problem, Phys. Rev. 152 (1966), 190{197.
11

References

improved lower bound, J. Stat. Phys. (1981),829{837. 12] R. P. Stanley, \Enumerative combinatorics, Vol. I," Wadsworth and Brooks/Cole, Monterey, CA, 1986. 13] A. Schrijver and W. G. Valiant, On lower bounds for permanents, Nederl. Akad. Wetensch. Indag. Math. 42 (1980), 425{427. 14] H. N. V. Temperley and M. E. Fisher, Dimer problem in statistical mechanics|an exact result, Philos. Mag. (8) 6 (1961), 1061{1063.

11] V. B. Priezzhev, The statistics of dimers on a three-dimensional lattice. II. An

12