Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Enumeration of $ 4 \times 4$ magic squares


Authors: Matthias Beck and Andrew van Herick
Journal: Math. Comp. 80 (2011), 617-621
MSC (2010): Primary 05A15, 05C78, 52B20, 52C35, 68R05
DOI: https://doi.org/10.1090/S0025-5718-10-02347-1
Published electronically: March 29, 2010
MathSciNet review: 2728997
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A magic square is an $ n \times n$ array of distinct positive integers whose sum along any row, column, or main diagonal is the same number. We compute the number of such squares for $ n=4$, as a function of either the magic sum or an upper bound on the entries. The previous record for both functions was the $ n=3$ case. Our methods are based on inside-out polytopes, i.e., the combination of hyperplane arrangements and Ehrhart's theory of lattice-point enumeration.


References [Enhancements On Off] (What's this?)

  • 1. Maya Ahmed, Jesús A. De Loera, and Raymond Hemmecke, Polyhedral cones of magic cubes and squares, Discrete and Computational Geometry, Algorithms Combin., vol. 25, Springer, Berlin, 2003, pp. 25-41. MR 2038468 (2004m:05016)
  • 2. Alexander Barvinok, Computing the Ehrhart polynomial of a convex lattice polytope, Discrete Comput. Geom. 12 (1994), no. 1, 35-48. MR 1280575 (95e:52015)
  • 3. Matthias Beck, Moshe Cohen, Jessica Cuomo, and Paul Gribelyuk, The number of ``magic'' squares, cubes, and hypercubes, Amer. Math. Monthly 110 (2003), no. 8, 707-717. MR 2023999 (2004k:05009)
  • 4. Matthias Beck and Sinai Robins, Computing the continuous discretely: Integer-point enumeration in polyhedra, Undergraduate Texts in Mathematics, Springer, New York, 2007. MR 2271992 (2007h:11119)
  • 5. Matthias Beck and Thomas Zaslavsky, Six little squares and how their numbers grow, Preprint, 2005.
  • 6. -, An enumerative geometry for magic and magilatin labellings, Ann. Comb. 10 (2006), no. 4, 395-413. MR 2293647 (2007m:05010)
  • 7. -, Inside-out polytopes, Adv. Math. 205 (2006), no. 1, 134-162. MR 2254310 (2007e:52017)
  • 8. Schuyler Cammann, Old Chinese magic squares, Sinologica 7 (1962), 14-53.
  • 9. -, Islamic and Indian magic squares, Parts I and II, History of Religions 8 (1969), 181-209; 271-299.
  • 10. Eugène Ehrhart, Sur les polyèdres rationnels homothétiques à $ n$ dimensions, C. R. Acad. Sci. Paris 254 (1962), 616-618. MR 0130860 (24:A714)
  • 11. -, Sur les carrés magiques, C. R. Acad. Sci. Paris Sér. A-B 277 (1973), A651-A654. MR 0332532 (48:10859)
  • 12. Komei Fukuda, Software package cdd, (2008. Electronically available at http://www. ifor.math.ethz.ch/$ \sim$fukuda/cddhome/cdd.html).
  • 13. Andrew Van Herick, Theoretical and computational methods for lattice point enumeration in inside-out polytopes, MA thesis, San Francisco State University, 2007. Available at http://math.sfsu.edu/beck/teach/masters/andrewv.pdf. Software package IOP available at http://iop.sourceforge.net/.
  • 14. Vincent Loechner, Software package polylib, (2007. Electronically available at http://icps.u-strasbg.fr/polylib/).
  • 15. Percy A. MacMahon, Combinatory Analysis, Chelsea Publishing Co., New York, 1960. MR 0141605 (25:5003)
  • 16. Richard P. Stanley, Linear homogeneous Diophantine equations and magic labelings of graphs, Duke Math. J. 40 (1973), 607-632. MR 0317970 (47:6519)
  • 17. -, Enumerative Combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997, Corrected reprint of the 1986 original. MR 1442260 (98a:05001)
  • 18. The PARI Group, Bordeaux, PARI/GP, version 2.3.4, 2008, available from http://pari.math.u-bordeaux.fr/.
  • 19. Sven Verdoolaege, Software package barvinok, (2004. Electronically available at http://freshmeat.net/projects/barvinok/).
  • 20. Guoce Xin, Constructing all magic squares of order three, Discrete Math. 308 (2008), no. 15, 3393-3398. MR 2423421 (2009e:05039)
  • 21. Claudia Zaslavsky, Africa Counts, Prindle, Weber & Schmidt, Inc., Boston, Mass., 1973. MR 0504588 (58:20993)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 05A15, 05C78, 52B20, 52C35, 68R05

Retrieve articles in all journals with MSC (2010): 05A15, 05C78, 52B20, 52C35, 68R05


Additional Information

Matthias Beck
Affiliation: Department of Mathematics, San Francisco State University, San Francisco, California 94132
Email: beck@math.sfsu.edu

Andrew van Herick
Affiliation: 531 Beloit Avenue, Kensington, California 94708
Email: avanherick@gmail.com

DOI: https://doi.org/10.1090/S0025-5718-10-02347-1
Keywords: Magic square, lattice-point counting, rational inside-out convex polytope, arrangement of hyperplanes, Ehrhart theory, rational generating function computation
Received by editor(s): August 11, 2009
Received by editor(s) in revised form: August 30, 2009
Published electronically: March 29, 2010
Additional Notes: We thank a referee and an associate editor for helpful comments on an earlier version of this paper. We are grateful to San Francisco State University’s Center for Computing and Life Sciences for graciously offering the use of their resources. This research was partially supported by the NSF (research grant DMS-0810105).
Article copyright: © Copyright 2010 American Mathematical Society

American Mathematical Society