Moments of Magic Squares: Line-Sum Conditions, a Permutation Threshold, and Random Energies

Abstract

Every semi-magic square of order $n$ satisfies the axial moment identities ${\sum }_{i,j}{s}_{ij}{j}^m={\sum }_{i,j}{s}_{ij}{i}^m=M(n){\sum }_j{j}^m$ for all $m\ge 1$, where $M(n)=n(n^2+1)/2$. For real matrices the converse requires $1\le m\le n-1$, whereas for arrangements of $\{1,\dots ,n^2\}$ fewer moments suffice once $n\ge 14$. We define the permutation threshold $k^{\ast }(n)$ as the least $k$ such that every arrangement satisfying these identities for $1\le m\le k$ is semi-magic. In terms of the column-sum deviations ${\gamma }_j$, the degree-$k$ conditions state that ${\sum }_j{\gamma }_j{t}^j$ is divisible by $(t-1{)}^{k+1}$, linking $k^{\ast }(n)$ to the Prouhet--Tarry--Escott problem. While Schur's bound on real zeros gives $k^{\ast }(n)\le \sqrt{2(n-1)\log (n^4/4)}$, we prove the converse realisability bound $k^{\ast }(n)\ge (\sqrt{2}-o(1))\sqrt{n}$ (and $k^{\ast }(n)\ge (\sqrt{6}-o(1))\sqrt{n}$ when $4\mid n$) by perturbing semi-magic squares with complementary row pairs via horizontal swaps. We also show that $k^{\ast }(n)=n-1$ for $3\le n\le 13$, $k^{\ast }(n)=n-2$ for $14\le n\le 17$, and $k^{\ast }(n)\le n-3$ for $n\ge 18$, and determine $k^{\ast }(n)$ for $18\le n\le 40$ with computer assistance. Finally, at the $k=1$ level of the hierarchy, we specialise the Mantel--Hubert quadratic assignment variance formula to obtain exact means, variances, and limit laws under a uniform random arrangement for the full line-sum energy $E_{\mathrm{full}}$, for the four-term energy $E_4$ combining the first moments and the two diagonals, and for Loly's moment of inertia, and find that $|L_4|=14,639,440$ arrangements of order $4$ satisfy $E_4=0$.

arXiv comment27 pages, 3 figures, 5 tables; ancillary verification scripts and certificates in anc/