A Better Lower Bound for the Number of Magic Squares of Order 4𝒌

Benjawan  Tiamkaew; Boonyisa  Saethao; Boorapa Singha

Authors

Benjawan Tiamkaew Department of Mathematics and Statistics, Faculty of Science and Technology, Chiang Mai Rajabhat University, Thailand
Boonyisa Saethao Department of Mathematics and Statistics, Faculty of Science and Technology, Chiang Mai Rajabhat University, Thailand
Boorapa Singha Department of Mathematics and Statistics, Faculty of Science and Technology, Chiang Mai Rajabhat University, Thailand

Keywords:

magic square, square matrix, enumerating magic squares

Abstract

Background and Objectives: Magic squares of order n are n x n arrays filled with distinct positive integers 1,2,3,..., $n^{2}$ arranged in such a way that the sums of the integers in each row, column and each of the main diagonals are the same. This number is called the magic constant or magic sum which is equal to $\frac{n(n^{2}+1)}{2}$ . Magic squares have a long history, the earliest recorded information about magic squares comes from China around 2200 BC and is called "Lo Shu". Magic squares were first mentioned in the western world in the works of Theon of Smyrna and were also used to help calculate horoscopes by a 9th-century Arab astrologer. Next, the work of Greek mathematician Moschopoulos in 1300 helped popularize knowledge about magic squares. Today, over 700 years later, teachers still use this knowledge in the classroom to solve problems and practice addition. The mathematical study of magic squares generally involves their construction, classification and enumeration. Although completely general methods for creating all the magic squares of all orders do not exist, there are studies on algorithms that can be used to construct magic squares in some orders. For example, the De la Loubère method (or Siamese method) is a simple algorithm for creating magic squares of any odd order by placing numbers sequentially, moving diagonally up and to the right, wrapping around the grid, and dropping down one cell when hitting a filled cell or boundary, this technique was observed by the French diplomat Simon de la Loubère in Siam (Thailand) in the late 17th century. The Strachey method constructs magic squares of singly even order n = 4m+2 by combining four smaller identical magic squares of order 2m+1 together to form one magic square of order 4m+2 . Then 0,

$0,\frac{n^{2}}{4},\frac{n^{2}}{2},\frac{3n^{2}}{4}$

is added to each square and finally certain squares are swapped from the top subsquare to the bottom subsquare. Let M (2k, k) represent the set of 2k x 2k matrices in which every element is either 0 or 1, with the sums of each row and column equal to k and let $M_{4k}$ be the set of magic squares of order 4k. In 2022, Oboudi showed that each matrix $E\in M(2k,k)$ can be used to construct a magic square in $M_{4k}$ . The author also showed that the number of magic squares of order 4k is at least $\frac{\binom{2k}{k}^{2}}{2}$ . To prove this result, Oboudi demonstrated a comparison of the cardinality of three sets by showing that $|M_{4k}|$ . $|M_{4k}|\geq|M(2k,k)|\geq|H|\geq\frac{\binom{2k}{k}^{2}}{2}$ , where H represents the set of some bipartite graphs that are defined in a specific way. However, comparing the cardinality of the three sets above causes the obtained lower bound $\frac{\binom{2k}{k}^{2}}{2}$ to possibly deviate from the true value of $|M_{4k}|$ . . To reduce this error, in this paper we use a new procedure that is simpler than Oboudi's technique and can obtain a lower bound of $|M_{4k}|$ . that is closer to the true value.

Methodology: From Oboudi's inequality $|M_{4k}|\geq|M(2k,k)|\geq|H|\geq\frac{\binom{2k}{k}^{2}}{2}$ , in this study we will only consider the condition $|M_{4k}|\geq|M(2k,k)|$ and aim at counting the number of matrices in . This procedure will not compare the number of elements in the set $M(2k,k)$ with other sets. Therefore, it reduces the potential for error. We will begin by considering the condition $|M_{4k}|\geq|M(2k,k)|$ again. Some details of such a condition that have not been discussed in Oboudi's work will be presented in this study. We will present two algorithms for constructing matrices in $M(2k,k)$ and prove their correctness. Then we will show that the output matrices from both algorithms will always be different. After that, we will present formulas to count the number of matrices obtained from both algorithms, one of which is the lower bound that Oboudi has presented in 2022. Then we combine the number of matrices obtained from the two algorithms to find a new lower bound for the number of magic squares of order 4k.

Main Results: We have presented the conditions under which the inequality $|M_{4k}|\geq|M(2k,k)|$ is true. After that, two algorithms for constructing matrices in $M(2k,k)$ are presented. Both algorithms produce different matrices. To obtain a new lower bound for the number of magic squares of order 4k , formulas for counting matrices obtained from both algorithms are investigated. The first is $\frac{\binom{2k}{k}^{2}}{2}$ , which is the lower bound of Oboudi, and the second is $\binom{2k}{k}\cdot\sum_{t=1}^{k-t}((k!)^{k-t}\prod_{i=0}^{k-t-1}P(2k-t-i,k))$ . After combining the two formulas together, a modified lower bound for the number of magic squares of order 4k is introduced, which is

$\binom{2k}{k}\cdot\sum_{t=1}^{k-t}((k!)^{k-t}\prod_{i=0}^{k-t-1}P(2k-t-i,k))$

Conclusions: This research is a study of a lower bound for the number of magic squares of order 4k using the concept from Oboudi's work. The result obtained from this study is a lower bound that are closer to the true value of $|M_{4k}|$ than the original values. The new lower bound is obtained by two algorithms of constructing matrices in M(2k,k). We found that the matrices obtained from the two algorithms are different and there are exactly $\frac{\binom{2k}{k}^{2}}{2}$ matrices obtained from the first algorithm. This number is equal to the lower bound that Oboudi studied in 2022, but here we use a simpler proof. Moreover, we proved that the second algorithm can construct at least $\binom{2k}{k}\cdot\sum_{t=1}^{k-t}((k!)^{k-t}\prod_{i=0}^{k-t-1}P(2k-t-i,k))$ matrices. Finally, when the number of matrices obtained by the two constructions are combined, a new and better lower bound for the number of magic squares of order 4k is obtained.

References

Beck, M., & Van Herick, A. (2011). Enumeration of 4×4 magic squares. Mathematics of computation, 80(273), 617-621.

Benjamin, A. T., & Brown, E. J. (2014). Challenging magic squares for magicians. The College Mathematics Journal, 45(2), 92-100. doi.org/10.4169/college.math.j.45.2.092

Das, M. K. (1991). On concentric magic squares and magic squares of order 4n+2. International Journal of Mathematical Education in Science and Technology, 22(2), 187-201. doi. 10.1080/0020739910220203

Kato, G., & Minato, S. I. (2020). Enumeration of associative magic squares of order 7. Journal of Information Processing, 28, 903-910. doi.org/10.2197/ipsjjip.28.903

Kraitchik, M. (1942). Mathematical Recreations. New York: Norton.

Oboudi, M. R. (2022). Constructing and Enumerating of Magic Squares. Bol. Soc. Paran. Mat, 40, 1-4. doi.org/10.5269/bspm.46836

Singha, B. (2020). The Number of a Type of 3×3 Magic Squares and Its Construction Algorithm. Burapha Science Journal, 25(2), 636-646.

Triantafyllou, S. A. (2022, October). Magic squares in order 4k+2. In 2022 30th National Conference with International Participation (TELECOM) (pp. 1-4). IEEE. doi:10.1109/telecom56127.2022.10017312