betaFeedback

WorksMathematics

Boxes with cyclic tiling groups have one layer or size 2 × 2 × 4

Abstract

Kuperberg asked how a box's dimensions determine its tiling group. We prove Conlon's conjecture that this group is cyclic exactly when one side has length one or the box has dimensions 2×2×42\times2\times4 in some order. For every box, we also show that the minimum number of generators of its tiling group equals the largest multiplicity of a cyclotomic factor of prime-power index in MacMahon's volume polynomial. This polynomial counts stacks by the number of cubes they contain. It also determines the Smith factors over Q[q,q−1]\mathbb{Q}[q,q^{-1}] of the box's weighted Carlitz matrix, which presents the tiling group at q=1q=1. Each cyclotomic factor of multiplicity ee occurs in exactly the last ee Smith factors, once in each.

Which boxes have a cyclic tiling group

Stack unit cubes in a corner of an a×b×ca \times b \times c box so that column heights weakly decrease away from that corner in both horizontal directions. This boxed plane partition projects to a hexagon tiled by diamonds called lozenges (Figure 1). The matrix KK of possible tile placements presents a finite abelian group G(a,b,c)G(a,b,c), the tiling group, with one generator for each row and one relation for each column (Figure 2). Its order is ∣det⁡K∣|\det K|, the number of possible stacks in that box [14 p. 265]. In 1998 Kuperberg asked which group of that order occurs for each box [8 Question 2].

Column heights, seven cubes, and one lozenge tiling

Figure 1. One of the 105 stacks in the 2×2×42 \times2 \times4 box. Its four columns have heights 4, 2, 1, 0. Viewed along a body diagonal, each visible unit square, whether the face of a cube or part of the box’s floor or walls, projects to a lozenge. Together these lozenges tile the hexagon on the right, with the floor and walls shown in pale colors. The dotted segment in the bottom lozenge is its short diagonal. It determines that tile uniquely because the two unit equilateral triangles with this common side form the lozenge.

Figure 2. The marked diagonals of each tiling select one 1 in every row and column of KK. Triangle A shares a lozenge with xx in the empty box and with yy in the full box. In column A these two lozenges give a circled 1 in row xx and a boxed 1 in row yy. Adding those row labels gives the group relation x+y=0x+y=0.

Theorem 1 (Conlon’s conjecture on cyclic tiling groups). For positive integers a,b,ca,b,c, the group G(a,b,c)G(a,b,c) is cyclic if and only if some side has length one or (a,b,c)(a,b,c) is a permutation of (2,2,4)(2,2,4). The exceptional group G(2,2,4)G(2,2,4) is isomorphic to Z/105Z\mathbb{Z}/105\mathbb{Z}.

Theorem 1 tells us when one generator suffices. How many generators does an arbitrary box need? Give each stack of vv cubes weight qvq^v and sum over all stacks to obtain MacMahon’s volume polynomial M(q)M(q) [11 §429]. Write e(d)e(d) for the multiplicity in M(q)M(q) of Φd(q)\Phi_d(q), the cyclotomic polynomial whose roots are the primitive ddth roots of unity.

Theorem 2 (Minimum number of generators). The tiling group G(a,b,c)G(a,b,c) needs exactly max⁡p,je(pj)\max_{p,j} e(p^j) generators, where pp runs over the primes and jj over the positive integers.

Kuperberg observed that the tiling group of a one-layer box is cyclic [8 Question 2]. In 2002 he proposed two conjectures that together would determine the group for every box [9 §5.1, Conjectures 11–12]. Conlon found the exceptional 2×2×42 \times2 \times4 box by computer and conjectured that it was the only exceptional case [3 §7]. MacMahon’s count of the stacks [11 §429] gives the group order 105=3⋅5⋅7105 = 3 \cdot5 \cdot7, so by Cauchy’s theorem there are elements of orders 33, 55, and 77. Since these elements commute and their orders are pairwise coprime, their product has order 105105 and generates the group. § 6 rules out the remaining boxes by a gcd calculation when the shortest side is two and by a bound on element orders when it is larger. § 2 illustrates Theorem 2 on two boxes with twenty stacks, and § 7 proves it.

From the picture to the group

The three orientations of a lozenge correspond to squares parallel to the floor or to either wall. Projection gives a bijection between stacks in an a×b×ca \times b \times c box and lozenge tilings of the equiangular hexagon with successive side lengths aa, bb, cc, aa, bb, cc [9 §5.1, Fig. 10].

Marking the short diagonal of every lozenge records the whole tiling. To list the possible marks, divide the hexagon into unit triangles. In the orientation of Figure 1 and Figure 2, the right-pointing triangles (▹\triangleright) index the rows of a matrix KK and the left-pointing ones (◃\triangleleft) its columns. Put 1 for a shared side, the short diagonal of a possible tile, and 0 otherwise. A choice gives a tiling exactly when its tiles cover each triangle once, selecting one 1 per row and column [14 p. 261]. The Kasteleyn–Percus formula counts these tilings by ∣det⁡K∣|\det K| [14 p. 265].

The generators of G(a,b,c)G(a,b,c) are indexed by the rows of KK. For each column, set the sum of the generators at its 1’s equal to zero. In the one-cube box (Figure 2), column AA gives y=−xy=-x, and then column BB gives z=−y=xz=-y=x. Substituting in column CC leaves one generator xx with the single relation 2x=02x=0.

With mm triangles of each orientation, this construction gives the quotient G=Zm/KZmG=\mathbb{Z}^{m}/K\mathbb{Z}^{m}, the integer cokernel of KK. Its order is the lattice index ∣det⁡K∣|\det K|. Kuperberg also asked how its elements could be interpreted in terms of the tilings [14 p. 265, Problem 5].

Does the stack count determine cyclicity?

Both boxes in Figure 3 have twenty stacks, and only the flat box’s tiling group is cyclic. Each colored line traces the boundary of a layer halfway up its cubes, continuing along the box walls where needed. Adding a unit cube interchanges two consecutive steps in its layer’s path and leaves its endpoints fixed. The (63)=20\binom{6}{3}=20 shortest paths between opposite floor corners give all the flat stacks. In the pictured 2×2×22 \times2 \times2 box, three unit cubes form an L and a fourth sits above its corner. Figure 4 shows all twenty stacks in this box.

Figure 3. Both boxes have twenty stacks. G(3,3,1)G(3, 3, 1) needs one generator and G(2,2,2)G(2, 2, 2) needs two. The colored paths trace the layers on the dotted grid. The lower right records the coefficient parities in mx+nymx+ny, so 2x+y2x+y gives (even, odd). Adding xx changes only the parity of mm, and adding yy only that of nn.

Figure 4. The twenty stacks in the 2×2×22 \times2 \times2 box, arranged by number of cubes. The darker faces belong to the cubes and the pale faces belong to the box. Setting q=1q=1 counts all twenty stacks.

Kuperberg’s path matrix presents the same group as the triangle matrix KK [9 Corollary 7 and Theorem 14]. Its rows index path starts (generators) and its columns index path ends (relations). Each entry counts paths between its endpoints by rising or falling steps to the right. The flat box gives 20x=020x = 0. In the two-layer box, two of four steps rise for a level finish (six choices), and one or three rise for a change of height (four choices).

The upper path start gives xx and the lower gives yy. In mx+nymx + ny, both relations preserve the parities of m,nm,n because their coefficients are even. All four pairs occur at 0,x,y,x+y0,x,y,x+y. Multiples of any gg give only the parities of 00 or gg, so two generators are necessary.

What the volume polynomial remembers

A cyclic group contains an element of order ∣G∣|G|. To rule this out for every box with shortest side at least three, we bound the orders of its elements using the volume polynomial. Figure 4 sorts the twenty stacks in the 2×2×22 \times2 \times2 box by volume. A rule that always adds or removes one unit cube sends all twelve even-volume stacks into the eight odd-volume stacks. Such a rule cannot realize addition by a group element, which is a bijection.

The four stacks in the middle column contribute 4q44q^{4}. Reading across the figure gives the volume polynomial

M(q)=1+q+3q2+3q3+4q4+3q5+3q6+q7+q8=A2B.M(q) = 1 + q + 3q^{2} + 3q^{3} + 4q^{4} + 3q^{5} + 3q^{6} + q^{7} + q^{8} = A^{2}B.

where A=1+q2=Φ4(q)A = 1 + q^{2} = \Phi_{4}(q) and B=1+q+q2+q3+q4=Φ5(q)B = 1 + q + q^{2} + q^{3} + q^{4} = \Phi_{5}(q). The factor Φ4\Phi_{4} has prime-power index 4=224 = 2^{2} and occurs twice, so by Theorem 2 the group needs exactly two generators. For the flat 3×3×13 \times3 \times1 box, MacMahon’s product gives M(q)=Φ2(q)Φ4(q)Φ5(q)Φ6(q)M(q) = \Phi_{2}(q)\Phi_{4}(q)\Phi_{5}(q)\Phi_{6}(q). Each factor of prime-power index occurs once, so one generator suffices. Both polynomials give 2020 at q=1q=1.

The map mx+ny↦(m mod 2,(m+n) mod 10)mx + ny \mapsto(m \mathbin{\bmod} 2,(m+n) \mathbin{\bmod} 10) respects both relations for the 2×2×22 \times2 \times2 box in Figure 3 and takes all twenty values. Since the group has order twenty, this gives G(2,2,2)≅Z/2Z⊕Z/10ZG(2,2,2) \cong\mathbb{Z}/2\mathbb{Z} \oplus\mathbb{Z}/10\mathbb{Z}. To see these summand orders in the volume polynomial, number the four steps of each path in Figure 3 from 00 to 33. Give a rise weight 11 and a fall at position rr weight qrq^{r}, and multiply the weights along the path. Choosing qruq^{r}u in ∏r=03(1+qru)\prod_{r=0}^{3}(1+q^{r}u) records a fall at rr, so the coefficient eke_{k} of uku^{k} counts paths with kk falls by weight. From the upper start xx to the lower endpoint BB there are three falls, giving e3e_{3} in the upper-right entry. At q=1q=1 every path has weight one.

C(q)=(e2e3e1e2),C(1)=(6446).C(q)=\begin{pmatrix}e_{2} & e_{3}\\e_{1} & e_{2}\end{pmatrix}, \qquad C(1)=\begin{pmatrix}6 & 4\\4 & 6\end{pmatrix}.

The determinant of C(q)C(q) is M(q)M(q) times a power of qq. Allow rational coefficients and powers of qq of either sign. Invertible row and column operations then give a diagonal matrix with each entry dividing the next. These entries are the Smith factors, determined up to nonzero rational constants and powers of qq.

The first Smith factor divides the second, so its square divides A2BA^{2}B. Since AA and BB are distinct irreducibles, the only possibilities are (1,A2B)(1,A^{2}B) and (A,AB)(A,AB). At q=iq=i, where A=0A=0, the first has rank one and the second has rank zero. The row and column operations remain invertible at ii, so we can read the rank from C(i)C(i).

At this value the product defining the entries becomes (1+u)(1+iu)(1−u)(1−iu)=1−u4(1+u)(1+iu)(1-u)(1-iu)=1-u^{4}. All three middle coefficients vanish, so C(i)=0C(i)=0. This selects (A,AB)(A,AB), giving the summand orders 22 and 1010 at q=1q=1.

The rule for every box

For the general box, fix the lengths aa, bb, cc, put N=b+cN=b+c, and let eke_k be the coefficient of xkx^k in ∏j=0N−1(1+qjx)\prod_{j=0}^{N-1}(1+q^jx), with ek=0e_k=0 outside 0≤k≤N0\leq k\leq N. The weighted Carlitz matrix and MacMahon’s volume formula [11 §429] are

C=(eb−i+j)0≤i,j<a,M(q)=∏i=1b∏j=1c1−qa+i+j−11−qi+j−1.C=(e_{b-i+j})_{0\leq i,j<a},\qquad M(q)=\prod_{i=1}^{b}\prod_{j=1}^{c}\frac{1-q^{a+i+j-1}}{1-q^{i+j-1}}.

Kuperberg relates CC, the dual Jacobi–Trudi matrix of the rectangle (ab)(a^b), to the weighted tiling matrix by invertible row and column operations and adjoining identity blocks. He asks about a diagonal form with squarefree entries over the integral Laurent ring [9 Theorem 14 and Conjectures 11–12]. For ordinary boxes we determine the factors over the rational Laurent ring. If an irreducible factor occurs ee times in the volume polynomial, it goes in ee different diagonal entries. Since each entry divides the next, these must be the last ee.

Theorem 3. Let Φd\Phi_d denote the dd-th cyclotomic polynomial and put e(d)=ord⁡ΦdM(q)e(d)=\operatorname{ord}_{\Phi_d}M(q). In increasing divisibility order, the Smith factors of CC over Q[q,q−1]\mathbb{Q}[q,q^{-1}], up to units, are

sj(q)=∏d:e(d)≥a−j+1Φd(q),1≤j≤a.s_j(q)=\prod_{d:e(d)\geq a-j+1}\Phi_d(q),\qquad1\leq j\leq a.

For the 2×2×22\times2\times2 box, A=Φ4A=\Phi_4 occurs twice and B=Φ5B=\Phi_5 occurs once. For arbitrary boxes, the operations used over the rational Laurent ring can introduce integer denominators. To draw conclusions about the tiling group at q=1q=1, § 5 therefore proves divisibility for the determinants of square submatrices before setting q=1q=1.

The rank test at q=iq=i suggests how to prove the weighted theorem. At a primitive dd-th root of unity the determinant vanishes to order e(d)e(d). Each diagonal entry that vanishes uses at least one of those e(d)e(d) factors and lowers the rank by one. We will find e(d)e(d) independent vectors sent to zero, forcing all e(d)e(d) copies into different entries.

The two intervals of exponents

Write the aa coordinates of a vector as the coefficients of a polynomial f(x)f(x) of degree <a<a. Put g(x)=∏j=0N−1(1−qjx)g(x)=\prod_{j=0}^{N-1}(1-q^jx). Multiplying ff by gg and taking the coefficients of xb,…,xb+a−1x^b,\ldots,x^{b+a-1} gives CTC^{\mathsf{T}} up to row and column signs. Indeed, coefficient ii in this block applied to xjx^j is (−1)b+i−jeb+i−j(-1)^{b+i-j}e_{b+i-j}. The coefficient map sends a vector to zero precisely when these middle coefficients vanish. Its product gfgf can then have nonzero terms only in the two outside intervals. Transposition and the signs preserve rank. Thus at any nonzero specialization of qq to a field, the nullity of CC is the dimension of the polynomials supported on

E={0,…,b−1}∪{a+b,…,a+b+c−1}(1)E=\{0,\ldots,b-1\}\cup\{a+b,\ldots,a+b+c-1\} \tag*{(1)}

that are divisible by gg. Division recovers ff, since gg has degree NN and max⁡E=a+N−1\max E=a+N-1. For the 2×2×22 \times2 \times2 box the allowed exponents are 0,1,4,50,1,4,5. At q=iq=i we have g(x)=1−x4g(x)=1-x^4, so both 1−x41-x^4 and x−x5x-x^5 have the prescribed zeros and allowed support. They are independent. At a primitive fifth root, gg divides 1−x51-x^5, which again has allowed support. These give the two missing ranks at a fourth root and the one missing rank at a fifth root, exactly the multiplicities we saw in the volume polynomial. Figure 5 shows how to find the multiples before doing any division.

Allowed powers and supported products for roots of orders 4 and 5

Figure 5. A line joins two allowed powers whose exponents agree modulo the order of the root. Their differences on the right are the supported products P(x)=g(x)f(x)P(x)=g(x)f(x). At the pale positions the coefficients of PP must vanish.

The same support gives a short determinant calculation. Put L={0,…,N−1}L=\{0,\ldots,N-1\}. Use as columns the monomials xkx^k, k∈Ek\in E in increasing order, followed by g,xg,…,xa−1gg,xg,\ldots,x^{a-1}g, in the monomial basis through degree a+N−1a+N-1. Expanding along the monomial columns gives (−1)aNdet⁡C(-1)^{aN}\det C. Alternatively, use as coordinate basis the monomials from LL followed by the same multiples of gg. The change of basis has determinant (−1)aNq(a2)(-1)^{aN}q^{\binom{a}{2}}. In these coordinates the only determinant left is that of the remainders of xkx^k, k∈Ek\in E, modulo gg. Over Q(q)\mathbb{Q}(q), evaluation at q−iq^{-i}, 0≤i<N0\leq i<N, computes this last determinant as a quotient of Vandermonde determinants, one on (q−k)k∈E(q^{-k})_{k\in E} and the other on (q−k)k∈L(q^{-k})_{k\in L}. Pairs within each interval cancel. The cross pairs give M(q)M(q), and the powers of qq give

det⁡C=qa(b2)M(q).(2)\det C=q^{a\binom{b}{2}}M(q). \tag*{(2)}

Indeed, the cross differences in the numerator and denominator have lengths a+b+j−ia+b+j-i and b+j−ib+j-i for 0≤i<b0\leq i<b, 0≤j<c0\leq j<c. Shifting the last cc exponents of LL by aa contributes the monomial q−a∑j=bN−1jq^{-a\sum_{j=b}^{N-1}j} to the Vandermonde quotient.

Fix d≥1d\geq1, write N=md+vN=md+v, 0≤v<d0\leq v<d, and let nrn_r be the number of elements of EE congruent to rr mod dd. Every difference of distinct exponents contributes one factor Φd\Phi_d precisely when its two exponents agree modulo dd. Among the exponents in LL, vv residue classes have size m+1m+1 and the others have size mm. Hence

e(d)=∑r=0d−1(nr2)−d(m2)−mv=∑r=0d−1(nr−m2).(3)e(d)=\sum_{r=0}^{d-1}\binom{n_r}{2}-d\binom{m}{2}-mv=\sum_{r=0}^{d-1}\binom{n_r-m}{2}. \tag*{(3)}

The second identity uses ∑r(nr−m)=v\sum_r(n_r-m)=v and the polynomial convention (x2)=x(x−1)/2\binom{x}{2}=x(x-1)/2, also at x=−1x=-1.

Finding all the missing ranks

Let ζ\zeta be a primitive dd-th root of unity. At q=ζq=\zeta one full period of factors in gg gives 1−xd1-x^d. Thus

g(x)=(1−xd)mH(x),H(x)=∏j=0v−1(1−ζjx),H∣1−xd.g(x)=(1-x^d)^mH(x),\qquad H(x)=\prod_{j=0}^{v-1}(1-\zeta^jx),\qquad H\mid1-x^d.

This gives two ways to construct a multiple of gg with support in EE. We can impose m+1m+1 full periods of zeros, or impose mm full periods and then the vv remaining zeros.

The two rows of Figure 5 show why we use both constructions. At d=4d=4, one full period gives the two multiples 1−x41-x^4 and x(1−x4)x(1-x^4). A second full period would require the factor (1−x4)2(1-x^4)^2, whose degree 88 exceeds the largest allowed exponent 55. At d=5d=5, counting four root conditions on four coefficients gives only the lower bound zero. Completing the period gives the supported multiple 1−x51-x^5.

Lemma 4. With t+=max⁡(t,0)t_+=\max(t,0), the nullity at q=ζq=\zeta is at least

max⁡{∑r(nr−m−1)+,∑r(nr−m)+−v}.\max\left\{\sum_r(n_r-m-1)_+,\sum_r(n_r-m)_+-v\right\}.

Proof. Write a supported polynomial uniquely as P(x)=∑r=0d−1xrfr(xd)P(x)=\sum_{r=0}^{d-1}x^rf_r(x^d). The coefficients of frf_r have nrn_r degrees of freedom. Requiring (u−1)h∣fr(u)(u-1)^h\mid f_r(u) imposes at most hh linear conditions, namely zero remainder modulo (u−1)h(u-1)^h. The resulting space has dimension at least ∑r(nr−h)+\sum_r(n_r-h)_+, and every PP in it is divisible by (1−xd)h(1-x^d)^h. Choosing h=m+1h=m+1 gives the first bound. Choosing h=mh=m, divide by (1−xd)m(1-x^d)^m and require zero remainder modulo HH. This imposes at most vv further conditions and gives the second bound.

The shape of the box now enters. Each of the two intervals in (1) contributes either the floor or the ceiling of its length divided by dd to nrn_r. Write b=Bd+βb=Bd+\beta, c=Dd+γc=Dd+\gamma, with 0≤β,γ<d0\le\beta,\gamma<d.

If β+γ<d\beta+\gamma<d, then m=B+Dm=B+D and every nr−mn_r-m is 00, 11, or 22. In (3) only the 22’s contribute. Their number is exactly the first lower bound in Lemma 4.

If β+γ≥d\beta+\gamma\ge d, then m=B+D+1m=B+D+1 and every nr−mn_r-m is −1-1, 00, or 11. Only the −1-1’s contribute to (3). Their number is ∑r(nr−m)+−v\sum_r(n_r-m)_+-v, since ∑r(nr−m)=v\sum_r(n_r-m)=v. This is the second lower bound. These arguments also cover d>Nd>N and v=0v=0.

We have found at least e(d)e(d) dimensions of kernel. In Smith form the nullity at ζ\zeta counts the invariant factors divisible by Φd\Phi_d. Their valuations sum to e(d)e(d) by (2), so there are exactly e(d)e(d) of them, each of valuation one. Divisibility puts them in the last e(d)e(d) positions. All nonunit irreducibles of the determinant are cyclotomic, which proves Theorem 3.

There are exactly min⁡(a,b,c)\min(a,b,c) nonunit rational Laurent factors. For a≤b≤ca\le b\le c, at a primitive (b+c)(b+c)-th root the product defining the elementary functions has only its constant and top coefficients, and every matrix entry is intermediate. Thus the entire matrix vanishes. Permuting the box sides preserves MM, so the number max⁡de(d)\max_d e(d) has the same value in every orientation. This also gives the count proposed in [3 §9] for an integral Laurent Smith form if it exists, since primitivity of the determinant precludes additional nonunit constant factors.

Consequences for the integer matrix

Let G=coker⁡C(1)G=\operatorname{coker} C(1), the quotient of Za\mathbb{Z}^a by the image of the integer Carltiz matrix. Its order is M(1)M(1). For 0≤k≤a0\le k\le a put

Dk(q)=∏d≥2Φd(q)(e(d)−a+k)+.D_k(q)=\prod_{d\ge2}\Phi_d(q)^{(e(d)-a+k)_+}.

Over Q[q,q−1]\mathbb{Q}[q,q^{-1}] the product of the first kk Smith factors divides every kk-rowed minor. That product is Dk(q)D_k(q). Its coprimality to qq lets us remove powers of qq over Q[q]\mathbb{Q}[q]. Division by the monic polynomial Dk(q)D_k(q) then proves divisibility of the actual minors in Z[q]\mathbb{Z}[q]. This makes specialization legitimate even if rational row operations would introduce denominators.

Corollary 5. Every kk-rowed minor of C(1)C(1) is divisible by Dk(1)D_k(1). In particular, the exponent of GG divides

∏d≥2e(d)>0Φd(1)\prod_{\substack{d\ge2\\ e(d)>0}} \Phi_d(1)

which divides lcm⁡(1,…,a+b+c−1)\operatorname{lcm}(1,\ldots,a+b+c-1).

Proof. The exponent of GG, the largest order of one of its elements, is its last integer Smith factor. This is M(1)M(1) divided by the gcd of the cofactors, with gcd 1 in size one. For the 2×2×22 \times2 \times2 box the diagonal cofactors are 6 and the off-diagonal cofactors are −4-4. Their gcd is 2, so the largest element order is 20/2=1020/2=10. In general Da−1(1)D_{a-1}(1) divides the cofactor gcd. Dividing M(1)M(1) by Da−1(1)D_{a-1}(1) gives the stated product. All indices dd occurring are at most max⁡E=a+b+c−1\max E=a+b+c-1. For d≥2d\ge2, Φd(1)=p\Phi_d(1)=p if dd is a positive power of a prime pp, and is 1 otherwise. This gives both the lcm bound and ord⁡p∣G∣=∑j≥1e(pj)\operatorname{ord}_p|G|=\sum_{j\ge1}e(p^j).

Proof of the cyclicity classification

Proof of Theorem 1. Order the sides a≤b≤ca\le b\le c. Permuting them gives stably equivalent presentations of the same tiling group [14 Problem 5]. If a=1a=1, the Carlitz matrix has a single entry and the group is cyclic.

If a=2a=2, the group is cyclic exactly when the entries of the two-by-two Carlitz matrix have gcd 1, since their gcd is its first Smith factor. Put U=(b+cb)U=\binom{b+c}{b}. The diagonal entries are UU, and the other two are Ub/(c+1)Ub/(c+1) and Uc/(b+1)Uc/(b+1). Their gcd is at least U/((b+1)(c+1))U/((b+1)(c+1)), because multiplication by (b+1)(c+1)(b+1)(c+1) makes all three entries integer multiples of UU. The lower bound increases with either bb or cc for b,c≥2b,c\ge2 and equals 20/1620/16 at b=c=3b=c=3. For b=2b=2 it is (c+2)/6>1(c+2)/6>1 whenever c≥5c\ge5. Finally at b=2b=2, c=2,3,4c=2,3,4 the gcds are respectively 2, 5, 1. Only the last box gives a cyclic group. Its matrix (1520615)\begin{pmatrix}15 & 20\\6 & 15\end{pmatrix} has determinant 105. The map (x,y)↦5y−9x mod 105(x,y)\mapsto5y-9x\mathbin{\bmod}105 sends both columns to zero and the class of (1,2)(1,2) to 1, giving an explicit isomorphism with Z/105Z\mathbb{Z}/105\mathbb{Z}.

Suppose now that a≥3a\ge3. A finite abelian group is cyclic exactly when its exponent equals its order. We show that the order outgrows an upper bound for the exponent.

Write t=a+b−1t=a+b-1 and L(t)=lcm⁡(1,…,t)L(t)=\operatorname{lcm}(1,\ldots,t). Each active power pjp^j divides a numerator index in the symmetric version of MacMahon’s formula having height cc. These indices range from c+1c+1 to c+tc+t. The number of active levels is at most the largest active jj, so Corollary 5 gives

exp⁡(G)∣lcm⁡(c+1,…,c+t)∣L(t)(c+tt).\exp(G)\mid\operatorname{lcm}(c+1,\ldots,c+t)\mid L(t)\binom{c+t}{t}.

For the second divisibility, every power of a prime beyond tt that divides some c+ic+i contributes to the valuation of the binomial, and the smaller powers are covered by L(t)L(t). In the product for ∣G∣|G|, the cells of the first row and last column together give one factor 1+c/k1+c/k for every 1≤k≤t1\le k\le t. Thus

F(a,b,c)=∣G∣(c+tt)=∏i=2a∏j=1b−1(1+ci+j−1).F(a,b,c)=\frac{|G|}{\binom{c+t}{t}}=\prod_{i=2}^{a}\prod_{j=1}^{b-1}\left(1+\frac{c}{i+j-1}\right).

It suffices that F(a,b,c)>L(t)F(a,b,c)>L(t), and FF increases with cc.

For b≥7b\ge7 it suffices to compare F(a,b,b)F(a,b,b) with the upper bound 4t−14^{t-1} for L(t)L(t). Start at (3,7,7)(3,7,7), increase bb along (3,b,b)(3,b,b), and then increase aa at fixed bb. Each step adds one to t=a+b−1t=a+b-1, multiplying the comparison bound by four.

To prove L(n)≤4n−1L(n)\le4^{n-1} by induction, observe that L(2m)/L(m)L(2m)/L(m) divides (2mm)\binom{2m}{m}, and L(2m+1)/L(m+1)L(2m+1)/L(m+1) divides (2m+1m)\binom{2m+1}{m}. Any prime power missing from the smaller lcm gives a factor in the binomial, and at most one power per prime is missing. Both binomials are at most 4m4^m, using the two equal central coefficients in the odd row. For Fb=F(3,b,b)F_b=F(3,b,b), multiplying its two rows gives

Fb=2(2b+1)(2bb)2(b+1)3(b+2),Fb+1Fb=4(2b+3)(2b+1)(b+1)(b+2)2(b+3)>4(b≥2).F_b=\frac{2(2b+1)\binom{2b}{b}^2}{(b+1)^3(b+2)},\qquad\frac{F_{b+1}}{F_b}=\frac{4(2b+3)(2b+1)(b+1)}{(b+2)^2(b+3)}>4\qquad(b\ge2).

The last inequality reduces to 3b3+5b2−5b−9>03b^3+5b^2-5b-9>0. Since F7=306735/4>48F_7=306735/4>4^8, we have Fb>4b+1F_b>4^{b+1}. Each new row up to a≤ba\le b increases F(a,b,b)F(a,b,b) by a factor of at least (3/2)b−1>4(3/2)^{b-1}>4. Therefore F(a,b,c)>4a+b−2≥L(t)F(a,b,c)>4^{a+b-2}\ge L(t).

For 4≤b≤64\le b\le6 the first pair of columns below covers a=3a=3. The second covers every 4≤a≤b4\le a\le b, by monotonicity of FF and L(t)≤L(2b−1)L(t)\le L(2b-1).

bbF(3,b,b)F(3,b,b)L(b+2)L(b+2)F(4,b,b)F(4,b,b)L(2b−1)L(2b-1)
4588/5588/5603528/53528/5420
5924420130682520
656628/756628/78402024451/72024451/727720

Table 1.

For a=b=3a=b=3 and c≥6c\ge6, F(3,3,6)=90>60=L(5)F(3,3,6)=90>60=L(5). For c=3,4,5c=3,4,5 the respective group orders are 980, 4116, 14112, while lcm⁡(c+1,…,c+5)\operatorname{lcm}(c+1,\ldots,c+5) is 840, 2520, 2520. This proves noncyclicity for every box with minimum side at least three and completes the classification.

Another prediction in Conlon’s §7 concerns the number of generators for an n×n×nn\times n\times n box. It requires nn generators exactly when nn is a power of two, including n=1n=1. Indeed this happens when some prime divides every entry. The entries comprise all interior binomial coefficients of row 2n2n. If 2n=phu2n=p^hu, p∤up\nmid u, then (1+X)2n=(1+Xph)u(1+X)^{2n}=(1+X^{p^h})^u in Fp[X]\mathbb{F}_p[X]. All interior coefficients vanish when u=1u=1, while for u>1u>1 the coefficient at php^h is u≠0u\ne0. Hence 2n2n must be a prime power, and the prime must be 2.

The ordinary group at a prime

The four coefficient-parity pairs in Figure 3 form G/2GG/2G for the 2×2×22\times2\times2 box. Both relations vanish modulo 2, leaving the images of x,yx,y as a basis over F2\mathbb{F}_2. For any box and prime pp, reducing the generators and relations modulo pp gives G/pGG/pG, with one dimension for each nontrivial cyclic summand of the pp-primary subgroup GpG_p.

Call j≥1j\ge1 active if e(pj)>0e(p^j)>0, and let tpt_p count the active indices. Corollary 5 gives ∣Gp∣|G_p| and ptpGp=0p^{t_p}G_p=0. Since C(1)C(1) is square, its nullity modulo pp equals dim⁡Fp(G/pG)\dim_{\mathbb{F}_p}(G/pG). We compute it using Han’s theorem on relations between three powers of linear forms.

Theorem 6. For every pp the dimension of G/pGG/pG over Fp\mathbb{F}_p is max⁡j≥1e(pj)\max_{j\ge1}e(p^j), with empty maximum zero. If tp≤2t_p\le2, list the positive multiplicities e(pj)e(p^j) and pad the list with zeros to obtain two numbers u≤vu\le v. Then

Gp≅(Z/p)v−u⊕(Z/p2)u.G_p\cong(\mathbb{Z}/p)^{v-u}\oplus(\mathbb{Z}/p^2)^u.

This gives the complete pp-primary group for every p3>a+b+c−1p^3>a+b+c-1, and also for smaller primes having at most two active indices.

Deduction of Theorem 2. Write GG as a direct sum of cyclic groups of orders 1<n1∣⋯∣nr1<n_1\mid\cdots\mid n_r. One generator from each summand suffices. Any generating set of GG maps to a spanning set of G/pGG/pG. A prime pp dividing n1n_1 divides every nin_i, giving G/pG≅FpG/pG\cong\mathbb{F}_p. The minimum for GG is therefore max⁡pdim⁡Fp(G/pG)=max⁡p,je(pj)\max_p\dim_{\mathbb{F}_p}(G/pG)=\max_{p,j}e(p^j) by Theorem 6.

To prove Theorem 6, we first express e(d)e(d) in terms of the side lengths modulo dd. Let x,y,zx,y,z be the least nonnegative residues of a,b,ca,b,c mod dd and S=x+y+zS=x+y+z. For d≥2d\ge2,

e(d)=max⁡{0,min⁡(x,y,z,d−x,d−y,d−z,S−d,2d−S)}.(4)e(d)=\max\{0,\min(x,y,z,d-x,d-y,d-z,S-d,2d-S)\}. \tag*{(4)}

Indeed, with F(h)=∑i=0h−1⌊i/d⌋F(h)=\sum_{i=0}^{h-1}\lfloor i/d\rfloor, the factorial form of the product in (2) gives

F(a+b+c)+F(a)+F(b)+F(c)−F(a+b)−F(a+c)−F(b+c).F(a+b+c)+F(a)+F(b)+F(c)-F(a+b)-F(a+c)-F(b+c).

The identity F(h+d)=F(h)+hF(h+d)=F(h)+h permits reduction of each side length modulo dd. Since F(h)=∑l≥1(h−ld)+F(h)=\sum_{l\ge1}(h-ld)_+, the expression becomes

(S−d)++(S−2d)+−(x+y−d)+−(x+z−d)+−(y+z−d)+.(S-d)_+ +(S-2d)_+-(x+y-d)_+-(x+z-d)_+-(y+z-d)_+.

It vanishes for S≤dS\le d and S≥2dS\ge2d. In the remaining range order x≤y≤zx\le y\le z and put w=S−dw=S-d. The expression is w−(w−x)+−(w−y)+−(w−z)+w-(w-x)_+-(w-y)_+-(w-z)_+. As ww crosses x,y,zx,y,z, this takes the successive forms w,x,d−z,2d−Sw,x,d-z,2d-S, giving (4).

For example, take a cubical box of side 2h+12^h+1 with h≥2h\ge2. In (4) the only active powers of 22 are 22 and 2h+12^{h+1}, with multiplicities 11 and 2h−32^h-3. At the intermediate powers all three residues are 11 and their sum is less than dd. At higher powers even the original three sides sum to less than dd. Theorem 6 thus gives

G2≅(Z/2)2h−4⊕Z/4.G_2\cong(\mathbb{Z}/2)^{2^{h}-4}\oplus\mathbb{Z}/4.

In particular the 9×9×99\times9\times9 box has four summands of order 22 and one of order 44.

Proof of Theorem 6. Put T=a+b+cT=a+b+c, A=a+bA=a+b, B=a+cB=a+c, W=b+cW=b+c, and work over the algebraic closure kk of Fp\mathbb{F}_p, which preserves the nullity. In k[X,Y]/(XA,YB)k[X,Y]/(X^A,Y^B), multiply by (X+Y)W(X+Y)^W from degree a−1a-1 to degree T−1T-1. The source monomials have XX-exponents 0,…,a−10,\ldots,a-1 and the target monomials have XX-exponents b,…,b+a−1b,\ldots,b+a-1. Thus the matrix is C(1)TC(1)^T. This use of multiplication in characteristic pp is related to the weak Lefschetz interpretation of prime divisibility of the box count in Li and Zanello [10 Theorem 4.2].

Let α≤β\alpha\le\beta be the degrees of a homogeneous free basis for the relations between XA,YB,(X+Y)WX^A,Y^B,(X+Y)^W in k[X,Y]k[X,Y]. The relation module is free of rank two by the graded syzygy theorem in two variables. Its degrees satisfy α+β=2T\alpha+\beta=2T because the Hilbert-series numerator 1−tA−tB−tW+tα+tβ1-t^A-t^B-t^W+t^\alpha+t^\beta of the finite-dimensional quotient has a double zero at t=1t=1. The third coefficient of a relation of degree T−1T-1 runs through precisely the kernel of our map. That coefficient determines the whole relation, since the least degree of a relation on XA,YBX^A,Y^B alone is A+B>T−1A+B>T-1. It follows that

dim⁡kker⁡C(1)=(T−α)++(T−β)+=(β−α)/2.\dim_k\ker C(1)=(T-\alpha)_++(T-\beta)_+=(\beta-\alpha)/2.

Han’s theorem computes this degree gap by a distance. We use the statement in Brenner and Kaid [1 Theorem 2.3], which attributes the formula to Han [4] and also gives Monsky’s proof reference [13 Corollary 23]. Put v=(W,B,A)\mathbf{v}=(W,B,A) and let O\mathcal{O} be the triples of integers with odd sum. Write dist⁡1\operatorname{dist}_1 for the sum-of-absolute-values distance to a set. The coordinates of v\mathbf{v} satisfy the strict triangle inequalities. If ss is the least integer for which dist⁡1(psv,O)<1\operatorname{dist}_1(p^s\mathbf{v},\mathcal{O})<1, the gap is

β−α=p−s(1−dist⁡1(psv,O)).\beta-\alpha=p^{-s}(1-\operatorname{dist}_1(p^s\mathbf{v},\mathcal{O})).

It is zero when there is no such ss. Coordinate permutations preserve the formula. The sum of the coordinates of v\mathbf{v} is even, so only s<0s<0 can qualify. For any d≥2d \ge2 we claim that

(d−dist⁡1(v,dO))+=2e(d).\left(d-\operatorname{dist}_{1}(\mathbf{v},dO)\right)_{+}=2e(d).

Reducing the sides modulo dd changes v/d\mathbf{v}/d by an integer triple with even sum. We can therefore use v′=(y+z,x+z,x+y)\mathbf{v}'=(y+z,x+z,x+y). If an odd center dhd\mathbf{h} lies at distance <d<d, each of 2x,2y,2z2x,2y,2z must be within dd of an odd multiple of dd. Indeed each is the sum of two coordinates of v′\mathbf{v}' minus the third. In [0,2d)[0,2d) the required odd multiple can only be dd. The three equations on h\mathbf{h} force h=(1,1,1)\mathbf{h}=(1,1,1). To compute the distance to this center, take the largest absolute signed coordinate sum, allowing all signs. Up to a common sign the four sums are 2x−d2x-d, 2y−d2y-d, 2z−d2z-d, 2S−3d2S-3d. Taking the positive part of dd minus their maximum absolute value gives twice the minimum in (4) when positive, and zero otherwise.

Han’s least ss therefore chooses the largest active power D=p−sD=p^{-s}. It also gives the largest e(d)e(d) among the active powers. In fact, if d,D=ldd,D=ld are both active and l>1l>1, take their closest odd centers dh,DHd\mathbf{h},D\mathbf{H}. The triangle inequality gives ∥h−lH∥1<l+1\lVert\mathbf{h}-l\mathbf{H}\rVert_{1}<l+1. This integer has parity 1−l1-l, so it is at most l−1l-1. Hence

D−∥v−DH∥1≥d−∥v−dh∥1.D-\lVert\mathbf{v}-D\mathbf{H}\rVert_{1}\ge d-\lVert\mathbf{v}-d\mathbf{h}\rVert_{1}.

This proves the rank formula, also when no level is active. If at most two levels occur, the vv nontrivial cyclic pp-power factors have orders pp or p2p^{2}, and the base-pp logarithm of the group order is u+vu+v. Thus exactly uu of those factors have order p2p^{2}.

The first determinantal ideal over the integers

For the entries themselves one can strengthen the divisibility in Corollary 5 to an equality of ideals before specializing. The reason is that their indices run through a consecutive interval. Write Bk(q)=(Nk)qB_k(q)=\binom{N}{k}_q for the Gaussian binomial coefficient. Up to a power of qq, ek=Bke_k=B_k for 0≤k≤N0\le k\le N. Ekedahl’s full-interior-row result, published by Mirmohades [12 Theorem 3.1], gives the ideal (ΦN)(\Phi_N) when the indices are 1,…,N−11,\ldots,N-1, N≥2N\ge2. Hazi’s proof of Theorem 3.8 treats initial intervals in the two-colored setting [5]. Joris, Oestreicher and Steinig studied the gcd of consecutive ordinary binomial coefficients [7]. Here we use any nonempty consecutive interval I⊆{0,…,N}I\subseteq\{0,\ldots,N\} in the polynomial ring.

Lemma 7. The Bk(q)B_k(q) for k∈Ik\in I generate their monic polynomial gcd as an ideal in Z[q]\mathbb{Z}[q].

Proof. Let gIg_I be their monic gcd in Q[q]\mathbb{Q}[q]. The factorial formula for Gaussian binomials gives

ord⁡ΦdBk=⌊Nd⌋−⌊kd⌋−⌊N−kd⌋={0,k mod d≤N mod d,1,k mod d>N mod d.\operatorname{ord}_{\Phi_d}B_k= \left\lfloor\frac{N}{d}\right\rfloor-\left\lfloor\frac{k}{d}\right\rfloor-\left\lfloor\frac{N-k}{d}\right\rfloor = \begin{cases} 0, & k\bmod d\le N\bmod d,\\ 1, & k\bmod d>N\bmod d. \end{cases}

Here d≥2d\ge2, and these are all the irreducible factors. The quotients Bk/gIB_k/g_I therefore belong to Z[q]\mathbb{Z}[q] and have constant term 1. Suppose their ideal were proper. A rational polynomial Bézout identity gives a nonzero integer in that ideal after denominators are cleared, so a maximal ideal containing it has residue characteristic p>0p>0. Its residue field is a finite extension of Fp\mathbb{F}_p. The constant terms force the image of qq to be nonzero. Denote its multiplicative order by nn. The cyclotomics vanishing there have indices d=npjd=np^j, j≥0j\ge0, with d=1d=1 omitted from consideration. This follows from Xmp−1=(Xm−1)pX^{mp}-1=(X^m-1)^p in characteristic pp and the distinct roots of Xn−1X^n-1 when p∤np\nmid n. For each such dd, call an index good if k mod d≤N mod dk \bmod d \le N \bmod d. If goodness is constant on II for every dd, any k∈Ik \in I attains all the minimum valuations. Otherwise take the largest DD on this chain for which there are both good and bad indices. Such DD exists because all indices are good for d>Nd > N. The good indices modulo DD occur in the consecutive blocks [tD,tD+(N mod D)][tD, tD + (N \bmod D)]. Since II contains both kinds of index, it contains a good endpoint of one of these blocks. That endpoint is congruent to either 00 or NN modulo every divisor of DD, so it is good for every smaller dd on the chain. At every larger level the choice of index is immaterial. Thus a single BkB_k attains the minimum at every vanishing cyclotomic. Its quotient by gIg_I is nonzero in the residue field, a contradiction.

For CC take I=[b−a+1,b+a−1]∩[0,N]I = [b - a + 1, b + a - 1] \cap[0, N] in the integers. Powers of qq are units in Z[q,q−1]\mathbb{Z}[q,q^{-1}], so the entries generate (s1(q))(s_1(q)) over the integral Laurent ring. In particular the smallest ordinary Smith factor always equals s1(1)s_1(1). The two-by-two weighted presentation also has a Smith form in each local ring at a maximal ideal, since after division by s1s_1 one entry is a unit and serves as a pivot.

Relation to earlier work. Kuperberg’s integral Laurent problem also asks that the diagonal form exist over Z[q,q−1]\mathbb{Z}[q,q^{-1}]. Theorem 3 determines it after rational coefficients are allowed. In Stanley’s Theorem 3.1 the alphabet length varies through y=qNy = q^N, with yy independent and qq in the coefficient field Q(q)\mathbb{Q}(q) [15]. Here NN is a fixed integer and the zeros in the variable qq determine the invariant factors. Chen, Guo, Jin and Liu studied the integer Carlitz matrices and used skew Schur polynomials to relate minors of Toeplitz matrices [2]. Huang and Yang’s path formula and interval decompositions [6 §§4.2, 4.4] give a representation-theoretic method for computing ranks at a fixed root of unity. The length-NN path between grades a−1a - 1 and a+N−1a + N - 1 on the tensor product with interval lengths a+b−1a + b - 1 and a+c−1a + c - 1 gives our transposed matrix up to row and column units. For k=b+i−jk = b + i - j, the exponent adjustment from their qj(N−k)Bk(q)q^{j(N-k)}B_k(q) to eke_k is (b+i2)−(j2)−Nj\binom{b+i}{2} - \binom{j}{2} - Nj.

Kuperberg’s question. In each cyclic case of Theorem 1, the group is Z/M(1)Z\mathbb{Z}/M(1)\mathbb{Z}. Choosing a side of length two for aa gives a two-row presentation. Lemma 7 gives the first integer Smith factor s1(1)s_1(1), and the determinant gives the second, M(1)/s1(1)M(1)/s_1(1). For any box, Theorem 6 determines the entire pp-primary group whenever at most two of the polynomials Φpj\Phi_{p^j}, j≥1j \ge1, divide M(q)M(q). With three or more such indices, we still know the number of cyclic pp-power summands. Corollary 5 supplies a common divisor of the minors of C(1)C(1) at each intermediate size 1<k<a1 < k < a. The exact power of pp in the gcd at each size would determine the orders of the individual summands.

Verification

Another AI model independently audited the mathematics and exposition of the 19 November 2026 draft. It found no gap in the proofs and used its own code to compute the integer Smith forms for all 364 boxes with $1 \le a \le b \le c \le 12$.

References

  1. [1]H. Brenner and A. Kaid, A note on the weak Lefschetz property of monomial complete intersections in positive characteristic. arXiv:1003.0824.arxiv.org/abs/1003.0824
  2. [2]C. Chen, A. Guo, X. Jin and G. Liu, Trivariate monomial complete intersections and plane partitions, arXiv:1108.1426.
  3. [3]N. Conlon, On plane partitions and Kasteleyn cokernels, UC Davis REU report, January 2022. Archived report.
  4. [4]C. Han, The Hilbert–Kunz function of a diagonal hypersurface, Ph.D. thesis, Brandeis University, 1991.
  5. [5]A. Hazi, Existence and rotatability of the two-colored Jones–Wenzl projector. doi:10.1112/blms.12983.
  6. [6]H.-L. Huang and Y. Yang, The Green rings of minimal Hopf quivers. doi:10.1017/S0013091515000085.
  7. [7]H. Joris, C. Oestreicher and J. Steinig, The greatest common divisor of certain sets of binomial coefficients, J. Number Theory 21 (1985), 101–119. doi:10.1016/0022-314X(85)90013-7.
  8. [8]G. Kuperberg, An exploration of the permanent-determinant method, Electron. J. Combin. 5 (1998), R46. doi:10.37236/1384.DOI
  9. [9]G. Kuperberg, Kasteleyn cokernels, Electron. J. Combin. 9 (2002), R29. doi:10.37236/1645.DOI
  10. [10]J. Li and F. Zanello, Monomial complete intersections, the weak Lefschetz property and plane partitions. arXiv:1002.4400.arxiv.org/abs/1002.4400
  11. [11]P. A. MacMahon, Combinatory Analysis, vol. II, §429, 1916, pp. 182–183. Original text.
  12. [12]D. Mirmohades, About categorification of cyclotomic integers and tensored N-complexes. arXiv:1807.02100.arxiv.org/abs/1807.02100
  13. [13]P. Monsky, Mason’s theorem and syzygy gaps, J. Algebra 303 (2006), 373–381.DOI
  14. [14]J. Propp, Enumeration of matchings: problems and progress, New Perspectives in Algebraic Combinatorics (1999), 255–291. arXiv:math/9904150.arxiv.org/abs/math/9904150
  15. [15]R. P. Stanley, The Smith normal form of a specialized Jacobi–Trudi matrix, European J. Combin. 62 (2017), 178–182. doi:10.1016/j.ejc.2016.12.008.DOI

Paper details

vlnc:W_a8ak5nem
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI Codex GPT-6.2-Astra max

View statement
Looking for related papers…
Contents