5
$\begingroup$

An order-$n$ magic square is an $n \times n$ matrix over the numbers $\{1, ... ,n^2\}$, each appearing exactly once, whose row and column sums are all equal. Sometimes the sums of the diagonals are required to be equal too.

These objects have a rich history, and they are hugely popular in recreational math. I remember being fascinated by constructions of magic squares when I was 10. It seems natural to ask how many order-$n$ magic squares are there? An exact formula is probably too much to hope for, but it is probably possible to give some asymptotic bounds.

Has anybody asked this question before? Are there known bounds on the number of order-$n$ magic squares?

$\endgroup$
4
$\begingroup$

This has been asked before on MSE, here and here for example. According to the OEIS, not much is known. James E. Ward III wrote a paper in Mathematics Magazine where he derived an upper bound of $(n^2)!/8(2n+1)!$ (where the 8 in the denominator comes from the 8 symmetries of a magic square), but this is surely a gross overestimate. As for lower bounds, there are numerous papers giving constructions of magic squares, but I am not aware of any that make an effort to derive an interesting lower bound on the total number of magic squares.

There has been quite a bit of research on the related question of the number of $n\times n$ squares with nonnegative integer entries whose rows and columns all sum to some given number $s$. This question is more tractable to analyze than your problem, but is still very difficult, and for example I do not think that there is a known asymptotic formula for $s =n(n^2+1)/2$ (and in any case, this would yield an even worse upper bound than Ward's).

$\endgroup$
  • 2
    $\begingroup$ Actually asymptotics for $n\times n$ squares with nonnegative integer entries whose rows and columns all sum to some given number $s$ are known for $s\gt Cn/\log n$, see arxiv.org/abs/math/0703600 published in Combinatorica, 30 (2010) 655-680. Restricting the entries to distinct integers would need different techniques, I think. $\endgroup$ – Brendan McKay Nov 30 '15 at 2:06
  • 2
    $\begingroup$ I'm not sure how gross an overestimate this is. If I were to choose a random permutation of $\{1, \dots, n^2\}$, then any given row or column should have the correct sum with probability roughly proportional to $n^{-5/2}$ (the variance of a row sum is on the order of $n^5$). Make a bunch of unjustified (and untrue) independence assumptions, and the probability you get a magic square would be roughly $(n^{-5/2})^{2n}=n^{-5n}$. Ward's estimate corresponds to replacing the $5n$ by $(2+o(1))n$. $\endgroup$ – Kevin P. Costello Nov 30 '15 at 6:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.