math.CO — Combinatorics

The Dancing Sand Theorem: the 2-part of the sandpile group of the hypercube, for every n

Contributed by Rafael Amichis Luengo

Let $K (Q_{n})$ be the sandpile group (critical group, Jacobian) of the $n$-dimensional hypercube graph $Q_{n}$. Its odd part was determined by Bai in 2003; its $2$-part has been open since then, and the latest work on it determines its $n - 1$ largest cyclic factors. We determine the whole 2-part of $K (Q_{n})$ for every $n$, by an explicit rule. The group splits over the indecomposable tilting modules $T (\lambda)$ of $\mathrm{SL}_{2}$ in characteristic $2$ that occur in $V^{\otimes n}$, with their multiplicities. The contribution of $T (\lambda)$ at the shift $i = (n - \lambda) / 2$ consists of explicit small cyclic factors and of $2^{| I |}$ large ones, where $I$ is the set of binary digits of $\lambda + 1$ below the leading one. The large ones are obtained by pooling a sequence of explicit integers — binomial valuations and carries — into a non-increasing sequence, in the manner of isotonic regression. The proof reduces each contribution, by elimination inside explicit $2$-adic lattices, to the Smith form of an explicit $2^{| I |} \times 2^{| I |}$ integer matrix, and computes that Smith form from the valuations of its entries. It needs a unique cheapest matching for an upper bound and an inductive potential for a lower bound. As consequences we recover Bai's counts and the theorems of Gao, Marx-Kuo, McDonald and Yuen on the largest factors, and we prove their Conjectures 4.14 and 5.4 and the formula for the $(n + 1)$-th factor stated in the 2019 poster of three of them. We also prove the fold law: the 2-part of the sandpile group of the folded cube $Q_{n} / \langle (1, \dots, 1) \rangle$ is $2 \cdot \operatorname{Syl}_{2} K (Q_{n})$, the group obtained by lowering every exponent by one. With the results above this gives the whole $2$-part of the sandpile group of the folded cube, and, with the known odd part, its whole sandpile group. The whole proof has been checked in the proof assistant Lean 4 with the Mathlib library, with nothing cited. This work has not been refereed by a human expert.