how to get the coefficient of a special term in the expansion of the graph polynomial?

Question

What is the coefficient $c$ of the term $x_1^2x_2^2x_3^2\cdots x_{12}^2$ in the expansion of the following multivariable polynomial:

$(x_1-x_2)(x_1-x_3)(x_1-x_4)(x_1-x_{10})(x_2-x_3)(x_2-x_5)(x_2-x_{11})(x_3-x_6)(x_3-x_{12})(x_4-x_5)(x_4-x_6)(x_4-x_7)(x_5-x_6)(x_5-x_8)(x_6-x_9)(x_7-x_8)(x_7-x_9)(x_7-x_{10})(x_8-x_9)(x_8-x_{11})(x_9-x_{12})(x_{10}-x_{11})(x_{10}-x_{12})(x_{11}-x_{12})$

If we recognized each $x_i$ as a vertex and each factor as a edge, then we get a quadrilateral tessellation of the torus. The above polynomial is actually as the graph polynomial of the following quadrangulation of the torus:

I hope someone can give an algorithm to get the coefficient of the term $x_1^2x_2^2x_3^2\cdots x_{12}^2$ in the expansion of the above graph polynomial. Thank you very much!

Answer 1

With slightly different notations (and with the opposite sign), we look for the coefficient of $\prod a_i^2b_i^2c_i^2$ in the polynomial $F:=\prod_{i=1}^{2n} (a_{i+1}-a_i)(b_{i+1}-b_i)(c_{i+1}-c_i)\cdot \prod_{i=1}^{2n} (a_i-b_i)(b_i-c_i)(c_i-a_i)$, where indices are taken modulo $n$. We may apply this formula for all sets $A_i=\{0,1,2\}$. How does a non-zero value of $F$ occur? For each $i$, $[a_i,b_i,c_i]$ is a permutation $\pi_i$ of $0,1,2$, and $\pi_{i+1}$ is obtained from $\pi_i$ by a cyclic shift (there are two possible shifts). If we introduce $\varepsilon_i=\pm 1$ dependently on which shift is used, then $\sum \varepsilon_i$ must be divisible by 3 and the value of the polynomial is $4^{2n}\prod \varepsilon_i$. The denominator in the formula is always $4^{2n}$. So the coefficient equals $$6\sum_{3|\varepsilon_1+\dots+\varepsilon_{2n}}\varepsilon_1\cdot \ldots \cdot\varepsilon_{2n}=6\sum_{3 |m-n} (-1)^m\binom{2n} {m}, $$ 6 corresponds to the choice of $\pi_1$, $m$ denotes the number of negative $\varepsilon$'s. The sum equals $\frac13((1-1)^{2n}+w^{-n}(1-w)^{2n}+w^{-2n}(1-w^2)^{2n})=\frac23 (-3)^n$, where $w=e^{2\pi i/3}$, thus the answer is $4(-3)^n$.

Here we use the fact (somebody here on MO told how is it called but I forgot) that for a Laurent polynomial $f(z)=\sum a_j z^j$ and a positive integer $n$ we have $$\sum_{k\equiv \alpha\pmod n} a_k=\frac1n\sum_{\omega:\omega^n=1} \omega^{-\alpha}f(\omega).$$

Answer 2

Note that the problem asks essentially for the number of arrow arrangements on the edges such that at each vertex 2 arrows meet except these arrangements are counted with sign, which is $(-1)^N$ where $N$ is the number of "down" arrows plus the number of "right" arrows. For odd $m$ we immediately see from here that the answer is zero: the horizontal flip changes the parity of $N$, so each symmetric pair of arrangements cancels out.

Now take $m=2n$. We can immediately discard all arrangements that have vertical $3$-cycles because inverting such a cycle results in an admissible arrangement of the opposite parity. If we look at what is left, we see that in each column the numbers of vertical arrows converging at the 3 vertices in the column are 0,1,2 in some order and those numbers determine the arrows. The cyclic shifts of $\begin{bmatrix}0\\1\\2\end{bmatrix}$ have 2 downward arrows and, thereby, do not influence the parity, while the cyclic shifts of $\begin{bmatrix}2\\1\\0\end{bmatrix}$ have $1$ downward arrow. Now let's write those numbers and see what the horizontal arrows may be. If you see $2$ or $0$, it is clear, so the interesting part is $1$. Fix one column to start with and look at the direction of the horizontal arrows passing through $1$ in this column. Since the horizontal flip does not change the parity now, we can assume it is to the right and then just double the answer. Let's see what can be in the next column. You have two choices: either you keep $1$ in the same position and $0$ and $2$ flip (thus changing the column orientation), or you follow $1$ by $0$ (it cannot be $2$ because then you'll have too many arrows there), $2$ by $1$, and $0$ by $2$. Notice that the orientation of the horizontal arrows passing through the new $1$ is still to the right and if you choose the second option, then $1$ is shifted by a single position in the direction determined by the column orientation. Thus you have an oriented graph whose vertices are 6 rearrangements of $\begin{bmatrix}0\\1\\2\end{bmatrix}$ in which you want to count the cycles with signs. Note that the contribution to the parity of the horizontal arrows is just the sum of horizontal positions of $2$'s minus the sum of horizontal positions of $0$'s in each row, but if you sum over rows, you get $0$ because in each position (column) there is one $2$ and one $0$. Now you set up the $6$ by $6$ transition matrix for this problem (which looks something like $$ \begin{bmatrix} 0 & -1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & -1 \\ 0 & -0 & 0 & -1 & 1 & 0 \\ 0 & -1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & -1 \\ 0 & -0 & 0 & -1 & 1 & 0 \end{bmatrix} $$ ("something like" because you may enumerate the positions differently from me; my original mistake was to put all $1$'s), note that it projects everything to a 3-dimensional subspace, on which it acts as $$ \begin{bmatrix} 0 & -1 &1 \\ 1&0&-1 \\ -1&1&0 \end{bmatrix} $$ and compute the eigenvalues which are $0$, $\pm\sqrt 3i$. Thus the count (which is just the trace of the $2n$-th power of this transition matrix) is $2(-3)^n$ and we have to double it.

This is a bit sketchy, so feel free to ask questions. Alas, it does not help much with the $m\times n$ case.

Answer 3

Mathematica tells me the requested coefficient is $-36$.

---

In response to the comments, I evaluated the coefficient for larger arrays, of size $m\times n$. Denoting the absolute value of the coefficient by $C_{m,n}$ I find: $$C_{3,2}=12,\;\;C_{3,4}=36,\;\;C_{3,6}=108,\;\;C_{3,8}=324,\;\;C_{3,10}=972,$$ in agreement with the formula $C_{3,2p}=4\cdot 3^p$. Continuing to other values of $m$, I find

$$C_{2,2}=18,\;\;C_{2,4}=114,\;\;C_{2,6}=858,\;\;C_{2,8}=7074,$$ $$C_{4,2}=114,\;\;C_{4,4}=2970,\;\;C_{4,6}=98466,$$ $$C_{5,2}=180,\;\;C_{5,4}=4380,$$ $$C_{6,2}=858,\;\;C_{6,4}=98466.$$

Guess: the coefficients $C_{m,n}$ for $m$ and $n$ both even equal the number of Eulerian orientations of the torus grid graph $C_{m}\times C_n$, given by OEIS A29811:

This implies in particular that $C_{2p,2q}=C_{2q,2p}$. The value of $C_{2p,2q}$ follows from the even powers of the generating function $F_{2p}(x)$ given by $$F_2(x)=\frac{2 x \left(12 x^2-15 x+4\right)}{(1-x) (1-2 x) (1-3 x)},$$ $$F_4(x)=\frac{2 x \left(300 x^4-812 x^3+651 x^2-183 x+16\right)}{(1-x) (1-2 x) (1-5 x) \left(4 x^2-7 x+1\right)}.$$ I have not found a result for generating functions $F_{2p}(x)$ for $p>2$, is this an open problem?