Semi magic squares and moment conditions reveal new permutation thresholds
Moments of Magic Squares: Line-Sum Conditions, a Permutation Threshold, and Random Energies
Discrete Mathematics
Summary
Magic squares are grids of numbers where the sums of rows, columns, and diagonals are equal. The authors studied patterns in these squares using moments, which are like weighted sums. They found the minimum number of moment conditions needed to guarantee a grid is semi-magic, a threshold linked to classical number theory problems. They also analyzed the behavior of random arrangements mathematically and used computers to understand these thresholds for squares up to size 40.
What this means in practice
- •For mathematical software developers: Develop precise algorithms to test when number grids satisfy partial magic square conditions by checking moment-based sum identities.
- •For combinatorial optimization teams: Use the derived bounds on permutation thresholds to better understand constraints in assignment and layout problems involving symmetric sum conditions.
Authors
Kyle Elliott Mathewson
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_jj^m$ for all $m\ge1$, 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\ge14$. We define the permutation threshold $k^*(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 $γ_j$, the degree-$k$ conditions state that $\sum_jγ_jt^j$ is divisible by $(t-1)^{k+1}$, linking $k^*(n)$ to the Prouhet--Tarry--Escott problem. While Schur's bound on real zeros gives $k^*(n)\le\sqrt{2(n-1)\log(n^4/4)}$, we prove the converse realisability bound $k^*(n)\ge(\sqrt2-o(1))\sqrt n$ (and $k^*(n)\ge(\sqrt6-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^*(n)=n-1$ for $3\le n\le13$, $k^*(n)=n-2$ for $14\le n\le17$, and $k^*(n)\le n-3$ for $n\ge18$, and determine $k^*(n)$ for $18\le n\le40$ 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$.