# Counting Spanning Trees with Roots of Unity

In a paper by Kenyon, Propp and Wilson, the number of spanning trees in a certain graph in the hexagonal lattice is:

$$\prod_{a,b,c} (3 - a-b-c)^{1/6}$$

where $a^{3n}=1, (a/b)^n=1,abc=1$ and $a,b,c$ are distinct.

In between the lines, the paper says this product is an integer.

I tried to program it Mathematica

Product[
(3 - e[k/(3 n)] - e[(k + 3 l)/(3 n)] - e[(-2 k - 3 l)/(3 n)])^(1/6)
, {k, 1, 3 n}, {l, 1, n - 1}];


The result is a real number but not an integer.

In mathematical terms I wrote:

$$\prod_{k=1}^{3n} \prod_{l=1}^{n-1} (3-\omega^k- \omega^{k+3l}- \omega^{-2k-3l})$$ where $\omega = e^{2\pi i /3n} = \cos \frac{2\pi}{3n} + i \sin \frac{2\pi}{3n}$ but this number has significant figures pas the decimal point.

How do I (correctly) parameterize the product in $a,b,c$ ?

• it looks like we need $k \neq l, 2l \mod n$ and $l \neq 0 \mod n$.
• the Galois action seems to be $(a,b,c) \mapsto (\omega a , \omega b, \omega^{-2} c)$. Shouldn't the sum be Galois invariant even if $a,b,c$ are not always distinct?
• people who'd had not trouble with it, can you share your code?
-
Incidentally, if you are not convinced that it is an integer, it definitely is. It is a product of algebraic integers which is fixed under the action of the appropriate Galois group. –  Qiaochu Yuan Jul 27 '12 at 14:35
Which integer is it? I am using Mathematica, but I'm not getting an integer. Something's wrong. –  john mangual Jul 27 '12 at 14:44
The $\mathbb{Z}/3n\mathbb{Z}$ Galois group shifts the variables: $a \mapsto \omega a, b \mapsto \omega b, c \mapsto \omega^{-2}c$. –  john mangual Jul 27 '12 at 14:50
Your expression is missing the requirement that $c$ be distinct from $a$ and $b$. –  joriki Jul 27 '12 at 15:17
I get $1, 1, 3, 26, 620, 40071, 6957314, 3228498000, 3990904966161, 13112285327130880, \ldots$. It doesn't seem to be in the OEIS yet. –  Robert Israel Jul 27 '12 at 17:58
show 1 more comment

In Maple:

F := proc(n)

local P,w,i,j,k;

P:= 1;

for i from 0 to 3*n-1 do

for j from 0 to 3*n-1 do

if (i - j) mod 3 <> 0 then next end if;

k:= (-i - j) mod (3*n);

if nops({i,j,k}) <> 3 then next end if;

P:= P * (3-w^i - w^j - w^k);


end do end do;

P:=simplify(P,{numtheory:-cyclotomic(3*n,w)=0});

simplify(P^(1/6))

end proc;

-

In Mathematica... it might look something like this

P = 1;
Do[
Do[
If[Mod[i - j, 3] != 0, k = Mod[-i - j , 3 n],];
If[Mod[i - j, 3] != 0 && Length[DeleteDuplicates[{i, j, k}]] < 3, ,
P = P*(3 - w^i - w^j - w^k )]
, {j, 0, 3 n - 1}]
, {i, 0, 3 n - 1}]
PolynomialMod[P, w^(3 n) - 1]
Replace[%, w -> E^(2 Pi I / 3/n)]

-