2-ADIC BEHAVIOR OF NUMBERS OF DOMINO TILINGS

HENRY COHN DEPARTMENT OF MATHEMATICS, HARVARD UNIVERSITY CAMBRIDGE, MA 02138, USA

                                             cohn@math.harvard.edu

Dedicated to my grandparents Garnette Cohn (1907–1998) and Lee Cohn (1908–1998)

Abstract. We study the 2-adic behavior of the number of domino tilings of a 2n × 2n square as n varies. It was previously known that this number was of the form 2^{n}f(n)^{2}, where f(n) is an odd, positive integer. We show that the function f is uniformly continuous under the 2-adic metric, and thus extends to a function on all of ℤ. The extension satisfies the functional equation f(−1 − n) = ±f(n), where the sign is positive iff n ≡ 0, 3 (mod 4).

Kasteleyn [K], and Temperley and Fisher [TF], proved that the number of tilings of a 2n×2n square with 1 × 2 dominos is

∏_{i=1}^{n} ∏_{j=1}^{n} (4 cos^{2} \frac{πi}{2n + 1} + 4 cos^{2} \frac{πj}{2n + 1}) .

Although it is by no means obvious at first glance, this number is always a perfect square or twice a perfect square (see [L]). Furthermore, it is divisible by 2^{n} but no higher power of 2. This fact about 2-divisibility was independently proved by several people (see [JSZ], or see [P] for a combinatorial proof), but there seems to have been little further investigation of the 2-adic properties of these numbers, except for [JS].

Write the number of tilings as 2^{n}f(n)^{2}, where f(n) is an odd, positive integer. In this paper, we study the 2-adic properties of the function f. In particular, we will prove the following theorem, which was conjectured by James Propp:

Theorem 1. The function f is uniformly continuous under the 2-adic metric, and its unique extension to a function from ℤ_{2} to ℤ_{2} satisfies the functional equation

f(−1 − n) = \begin{cases}f(n) & if n ≡ 0, 3 (mod 4), and \\ −f(n) & if n ≡ 1, 2 (mod 4). \end{cases}

John and Sachs [JS] have independently investigated the 2-adic behavior of f, and explicitly determined it modulo 2^{6}. Their methods, as well as ours, can be used to write formulas for f modulo any power of 2, but no closed form is known.

The proof of Theorem 1 will not make any use of sophisticated 2-adic machinery. The only non-trivial fact we will require is that the 2-adic absolute value extends uniquely to each finite extension of ℚ. For this fact, as well as basic definitions and concepts, the book [G] by Gouvêa is an excellent reference.

It is helpful to keep in mind this more elementary description of what it means for f to be uniformly continuous 2-adically: for every k, there exists an ℓ such that if n ≡ m (mod 2^{ℓ}), then f(n) ≡ f(m) (mod 2^{k}). In particular, we will see that for our function f, the condition n ≡ m (mod 2) implies that f(n) ≡ f(m) (mod 2), and n ≡ m (mod 4) implies that f(n) ≡ f(m) (mod 4).

Date: Submitted December 17, 1998; accepted February 18, 1999.

1991 Mathematics Subject Classification. 05A15, 11A07.

The author was supported by an NSF Graduate Research Fellowship.

As a warm-up in using 2-adic methods, and for the sake of completeness, we will prove that that number of tilings of a 2n × 2n square really is of the form 2^{n}f(n)^{2}, assuming Kasteleyn’s theorem. To do so, we will make use of the fact that the 2-adic metric extends to every finite extension of ℚ, in particular the cyclotomic extensions, which contain the cosines that appear in Kasteleyn’s product formula. We can straightforwardly determine the 2-adic valuation of each factor, and thus of the entire product.

Let ζ be a primitive (2n + 1)-st root of unity, and define

α_{i,j} = ζ^{i} + ζ^{−i} + ζ^{j} + ζ^{−j}.

Then the number of domino tilings of a 2n × 2n square is

∏_{i=1}^{n} ∏_{j=1}^{n}(4 + α_{i,j}). (1)

To determine the divisibility by 2, we look at this number as an element of ℚ_{2}(ζ). Because 2n + 1 is odd, the extension ℚ_{2}(ζ)/ℚ_{2} is unramified, so 2 remains prime in ℚ_{2}(ζ). We will use | · |_{2} to denote the unique extension of the 2-adic absolute value to ℚ_{2}(ζ).

Lemma 2. For 1 ≤ i, j ≤ n, we have

|4 + α_{i,j}|_{2} = \begin{cases}1 & if i ≠ j, and \\ 1/2 & if i = j. \end{cases}

Proof. The number 4 + α_{i,j} is an algebraic integer, so its 2-adic absolute value is at most 1. To determine how much smaller it is, first notice that

α_{i,j} = (ζ^{i} + ζ^{j})(ζ^{i+j} + 1)ζ^{−i}ζ^{−j}.

In order for 4 + α_{i,j} to reduce to 0 modulo 2, we must have

ζ^{i} ≡ ζ^{±j} (mod 2).

However, this is impossible unless i ≡ ±j (mod 2n + 1), because ζ has order 2n + 1 in the residue field. Since 1 ≤ i, j ≤ n, the only possibility is i = j.

In that case, 4 + α_{i,i} = 2(2 + ζ^{i} + ζ^{−i}). In order to have |4 + α_{i,i}|_{2} < 1/2, the second factor would need to reduce to 0. However, that could happen only if ζ^{i} ≡ ζ^{−i} (mod 2), which is impossible.

By Lemma 2, the product (1) is divisible by 2^{n} but not 2^{n+1}. The product of the terms with i = j, divided by 2^{n}, is

∏_{i=1}^{n}(2 + ζ^{i} + ζ^{−i}), (2)

which equals 1, as we can prove by writing

∏_{i=1}^{n}(2 + ζ^{i} + ζ^{−i}) = ∏_{i=1}^{n}(1 + ζ^{i})(1 + ζ^{−i}) = ∏_{i=1}^{n}(1 + ζ^{i})(1 + ζ^{2n+1−i}) = ∏_{i=1}^{2n}(1 + ζ^{i}) = 1;

the last equality follows from substituting z = −1 in

z^{2n+1} − 1 = ∏_{i=0}^{2n}(z − ζ^{i}).

Thus, the odd factor of the number of tilings of a 2n × 2n square is

f(n)^{2} = ∏_{1≤i<j≤n}(4 + α_{i,j})^{2}.

We are interested in the square root of this quantity, not the whole odd factor. The positive square root is

f(n) = ∏_{1≤i<j≤n}(4 + α_{i,j})

(notice that every factor is positive). It is clearly an integer, since it is an algebraic integer and is invariant under every automorphism of ℚ(ζ)/ℚ. Thus, we have shown that the number of tilings is of the form 2^{n}f(n)^{2}, where f(n) an odd integer.

In determining the 2-adic behavior of f, it seems simplest to start by examining it modulo 4. In that case, we have the formula

f(n) ≡ ∏_{1≤i<j≤n} α_{i,j} (mod 4),

and the product appearing in it can actually be evaluated explicitly.

Lemma 3. We have

∏_{1≤i<j≤n} α_{i,j} = \begin{cases}1 & if n ≡ 0, 1, 3 (mod 4), and \\ −1 & if n ≡ 2 (mod 4). \end{cases}

Proof. In this proof, we will write ζ^{∗} to indicate an unspecified power of ζ. Because the product in question is real and the only real power of ζ is 1, we will in several cases be able to see that factors of ζ^{∗} equal 1 without having to count the ζ’s.

Start by observing that

∏_{1≤i<j≤n} α_{i,j} = ∏_{i=1}^{n−1} ∏_{j=i+1}^{n}(ζ^{i+j} + 1)(ζ^{i−j} + 1)ζ^{−i}

= ζ^{∗} ∏_{i=1}^{n−1} ∏_{j=i+1}^{n}(ζ^{i+j} + 1)(ζ^{2n+1+i−j} + 1)

= ζ^{∗} ∏_{i=1}^{n−1} ∏_{s=2i+1}^{2n}(ζ^{s} + 1).

(To prove the last line, check that i + j and 2n + 1 + i − j together run over the same range as s.) In the factors where i > n/2, replace ζ^{s} + 1 with ζ^{s}(ζ^{2n+1−s} + 1). Now for every i, it is easy to check that

∏_{s=2i+1}^{2n}(ζ^{s} + 1) ∏_{s=2(n−i)+1}^{2n}(ζ^{2n+1−s} + 1) = ∏_{s=1}^{2n}(ζ^{s} + 1) = 1.

When n is odd, pairing i with n − i in this way takes care of every factor except for a power of ζ, which must be real and hence 1. Thus, the whole product is 1 when n is odd, as desired.

In the case when n is even, the pairing between i and n − i leaves the i = n/2 factor unpaired. The product is thus

ζ^{∗} ∏_{s=n+1}^{2n}(ζ^{s} + 1). (3)

Notice that

( ∏_{s=n+1}^{2n}(1 + ζ^{s}))^{2} = ∏_{s=n+1}^{2n} ζ^{s}(1 + ζ^{2n+1−s}) ∏_{s=n+1}^{2n}(1 + ζ^{s})

= ∏_{s=n+1}^{2n} ζ^{s}
= ζ^{∗}.

Hence, since every power of ζ has a square root among the powers of ζ (because 2n + 1 is odd),

∏_{s=n+1}^{2n}(ζ^{s} + 1) = ±ζ^{∗}.

Substituting this result into (3) shows that the product we are trying to evaluate must equal ±1, since the ζ^{∗} factor must be real and therefore 1. All that remains is to determine the sign.

Since

∏_{s=n+1}^{2n}(1 + ζ^{s})

and

∏_{t=1}^{n}(1 + ζ^{t})

are reciprocals, it is enough to answer the question for the second one (which is notationally slightly simpler). We know that it is plus or minus a power of ζ, and need to determine which. Since ζ = ζ^{−2n}, we have

∏_{t=1}^{n}(1 + ζ^{t}) = ∏_{t=1}^{n}(1 + ζ^{−2nt}) = ζ^{∗} ∏_{t=1}^{n}(ζ^{nt} + ζ^{−nt}).

The product

∏_{t=1}^{n}(ζ^{nt} + ζ^{−nt})

is real, so it must be ±1; to determine which, we just need to determine its sign. For that, we write

ζ^{nt} + ζ^{−nt} = 2 cos (tπ − \frac{tπ}{2n + 1}) ,

which is negative iff t is odd (assuming 1 ≤ t ≤ n). Thus, the sign of the product is negative iff there are an odd number of odd numbers from 1 to n, i.e., iff n ≡ 2 (mod 4) (since n is even).

Therefore, the whole product is −1 iff n ≡ 2 (mod 4), and is 1 otherwise.

Now that we have dealt with the behavior of f modulo 4, we can simplify the problem considerably by working with f^{2} rather than f. Recall that proving uniform continuity is equivalent to showing that for every k, there exists an ℓ such that if n ≡ m (mod 2^{ℓ}), then f(n) ≡ f(m) (mod 2^{k}). If we can find an ℓ such that n ≡ m (mod 2^{ℓ}) implies that f(n)^{2} ≡ f(m)^{2} (mod 2^{2k}), then it follows that f(n) ≡ ±f(m) (mod 2^{k}), and our knowledge of f modulo 4 pins down the sign as +1. The same reasoning applies to the functional equation, so if we can show that f^{2} is uniformly continuous 2-adically and satisfies f(−1 − n)^{2} = f(n)^{2}, then we will have proved Theorem 1.

We begin by using (1) to write

2^{n}f(n)^{2} = ( ∏_{i,j=1}^{n} α_{i,j}) ∏_{i,j=1}^{n} (1 + \frac{4}{α_{i,j}} )

= ( ∏_{i,j=1}^{n} α_{i,j}) ∑_{k≥0} 4^{k}E_{k}(n),

where E_{k}(n) is the k-th elementary symmetric polynomial in the 1/α_{i,j}’s (where 1 ≤ i, j ≤ n). We can evaluate the product

∏_{i,j=1}^{n} α_{i,j}

by combining Lemma 3 with the equation

∏_{t=1}^{n}(ζ^{t} + ζ^{−t}) = (−1)^{⌊ \frac{n+1}{2} ⌋},

which can be proved using the techniques of Lemma 3: it is easily checked that the product squares to 1, and its sign is established by writing

ζ^{t} + ζ^{−t} = 2 cos \frac{2tπ}{2n + 1},

which is positive for 1 ≤ t < (2n + 1)/4 and negative for (2n + 1)/4 < t ≤ n. This shows that

∏_{i,j=1}^{n} α_{i,j} = (−1)^{⌊ \frac{n+1}{2} ⌋}2^{n},

so we conclude that

f(n)^{2} = (−1)^{⌊ \frac{n+1}{2} ⌋} ∑_{k≥0} 4^{k}E_{k}(n). (4)

The function n ↦ (−1)^{⌊ \frac{n+1}{2} ⌋} is uniformly continuous 2-adically and invariant under interchanging n with −1 − n, so to prove these properties for f^{2} we need only prove them for the sum on the right of (4).

Because α_{i,j} has 2-adic valuation at most 1, that of E_{k}(n) is at least −k, and hence 2^{k}E_{k}(n) is a 2-adic integer (in the field ℚ_{2}(ζ)). Thus, to determine f(n)^{2} modulo 2^{k} we need only look at the first k + 1 terms of the sum (4).

Define

S_{k}(n) = ∑_{i,j=1}^{n} \frac{1}{α_{i,j}^{k}} .

We will prove the following proposition about S_{k}.

Proposition 4. For each k, S_{k}(n) is a polynomial over ℚ in n and (−1)^{n}. Furthermore,

S_{k}(n) = S_{k}(−1 − n).

We will call a polynomial in n and (−1)^{n} a quasi-polynomial. Notice that every quasi-polynomial over ℚ is uniformly continuous 2-adically.

In fact, S_{k} is actually a polynomial of degree 2k. However, we will not need to know that. The only use we will make of the fact that S_{k} is a quasi-polynomial is in proving uniform continuity, so we will prove only this weaker claim.

Given Proposition 4, the same must hold for E_{k}, because the E_{k}’s and S_{k}’s are related by the Newton identities

kE_{k} = ∑_{i=1}^{k}(−1)^{i−1}S_{i}E_{k−i}.

It now follows from (4) that f^{2} is indeed uniformly continuous and satisfies the functional equation. Thus, we have reduced Theorem 1 to Proposition 4.

Define

T_{k}(n) = ∑_{i,j=0}^{2n} \frac{1}{α_{i,j}^{k}} ,

and

R_{k}(n) = ∑_{i=0}^{2n} \frac{1}{α_{i,0}^{k}} .

Because α_{i,j} = α_{−i,j} = α_{i,−j} = α_{−i,−j}, we have

T_{k}(n) = 4S_{k}(n) + 2R_{k}(n) − \frac{1}{α_{0,0}^{k}} .

To prove Proposition 4, it suffices to prove that T_{k} and R_{k} are quasi-polynomials over ℚ, and that T_{k}(−1 − n) = T_{k}(n) and R_{k}(−1 − n) = R_{k}(n).

We can simplify further by reducing T_{k} to a single sum, as follows. It is convenient to write everything in terms of roots of unity, so that

T_{k}(n) = ∑_{ζ,ξ} \frac{1}{(ζ + 1/ζ + ξ + 1/ξ)^{k}} ,

where ζ and ξ range over all (2n + 1)-st roots of unity. (This notation supersedes our old use of ζ.) Then we claim that

T_{k}(n) = (∑_{ζ} \frac{1}{(ζ + 1/ζ)^{k}} )^{2} .

To see this, write the right hand side as

(∑_{ζ} \frac{1}{(ζ + 1/ζ)^{k}} ) (∑_{ξ} \frac{1}{(ξ + 1/ξ)^{k}} ) = ∑_{ζ,ξ} \frac{1}{(ζξ + 1/(ζξ) + ζ/ξ + 1/(ζ/ξ))^{k}} ,

and notice that as ζ and ξ run over all (2n + 1)-st roots of unity, so do ζξ and ζ/ξ. (This is equivalent to the fact that every (2n + 1)-st root of unity has a unique square root among such roots of unity, because that implies that the ratio ξ^{2} between ζξ and ζ/ξ does in fact run over all (2n + 1)-st roots of unity.)

We can deal with R_{k} similarly: as ξ runs over all (2n + 1)-st roots of unity, so does ξ^{2}, and hence

R_{k}(n) = ∑_{ζ} \frac{1}{(2 + ζ + 1/ζ)^{k}} = ∑_{ξ} \frac{1}{(2 + ξ^{2} + 1/ξ^{2})^{k}} = ∑_{ξ} \frac{1}{(ξ + 1/ξ)^{2k}} .

Define

U_{k}(n) = ∑_{ζ} \frac{1}{(ζ + 1/ζ)^{k}} .

Now everything comes down to proving the following proposition:

Proposition 5. The function U_{k} is a quasi-polynomial over ℚ, and satisfies

U_{k}(−1 − n) = U_{k}(n).

Proof. The proof is based on the observation that for any non-zero numbers, the power sums of their reciprocals are minus the Taylor coefficients of the logarithmic derivative of the polynomial with those numbers as roots, i.e.,

\frac{d}{dx} log ∏_{i=1}^{m}(x − r_{i}) = ∑_{i=1}^{m} \frac{1}{x − r_{i}}

= ∑_{i=1}^{m} \frac{−1/r_{i}}{1 − x/r_{i}}

= − ∑_{i=1}^{m} (\frac{1}{r_{i}} + \frac{x}{r_{i}^{2}} + \frac{x^{2}}{r_{i}^{3}} + …) .

To apply this fact to U_{k}, define

P_{n}(x) = ∏_{ζ}(x − (ζ + 1/ζ))

= ∏_{j=0}^{2n}(x − 2 cos(2πj/(2n + 1)))

= 2(cos((2n + 1) cos^{−1}(x/2)) − 1).

Then

\frac{d}{dx} log P_{n}(x) = \frac{2n + 1}{2\sqrt{1 − x^{2}/4}} \frac{sin((2n + 1) cos^{−1}(x/2))}{cos((2n + 1) cos^{−1}(x/2)) − 1}.

This function is invariant under interchanging n with −1 − n (equivalently, interchanging 2n + 1 with −(2n + 1)), so its Taylor coefficients are as well. By the observation above, the coefficient of x^{k} is −U_{k+1}(n). Straightforward calculus shows that these coefficients are polynomials over ℚ in n, sin((2n + 1)π/2), and cos((2n + 1)π/2). Using the fact that cos((2n + 1)π/2) = 0 and sin((2n + 1)π/2) = (−1)^{n} completes the proof.

Acknowledgements

I am grateful to James Propp for telling me of his conjecture, to the anonymous referee for pointing out a sign error in the original manuscript, and to Karen Acquista, Noam Elkies, Matthew Emerton, and Vis Taraz for helpful conversations.

References

[G] F. Gouvêa, p-adic Numbers: An Introduction, 2nd ed., Springer-Verlag, New York, 1997.

[JS] P. John and H. Sachs, On a strange observation in the theory of the dimer problem, preprint, 1998.

[JSZ] P. John, H. Sachs, and H. Zernitz, Problem 5. Domino covers in square chessboards, Zastosowania Matematyki (Applicationes Mathematicae) XIX 3–4 (1987), 635–641.

[K] 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.

[L] L. Lovász, Combinatorial Problems and Exercises, North-Holland Publishing Company, Amsterdam, 1979.

[P] L. Pachter, Combinatorial approaches and conjectures for 2-divisibility problems concerning domino tilings of polyominoes, Electronic Journal of Combinatorics 4 (1997), #R29.

[TF] H. N. V. Temperley and M. E. Fisher, Dimer problem in statistical mechanics—an exact result, Phil. Mag. 6 (1961), 1061–1063.