Existence of $K$-multimagic squares and magic squares of $k$th powers with distinct entries

Basic Information

• Paper ID: 2411.01091
• Title: Existence of $K$-multimagic squares and magic squares of $k$th powers with distinct entries
• Author: Daniel Flores (Purdue University)
• Classification: math.NT (Number Theory), math.CO (Combinatorics)
• Publication Date: January 1, 2025 (arXiv v2)
• Paper Link: https://arxiv.org/abs/2411.01091

Abstract

This paper proves that when $N > 2K(K+1)$, there exist $N$-order $K$-multimagic squares consisting of $N^2$ distinct integers. This improves upon the author's previous result which only required $N+1$ distinct integers. Furthermore, the paper presents a direct method proving the existence of $N \times N$ magic squares composed of distinct $k$th powers when the following conditions are satisfied: $N > \begin{cases}2^{k+1} & \text{if } 2 \leq k \leq 4 \\ 2\lceil k(\log k + 4.20032)\rceil & \text{if } k \geq 5\end{cases}$ This improves upon recent results by Rome and Yamagishi.

Research Background and Motivation

Problem Definition

1. $K$-multimagic square problem: An $N \times N$ matrix $Z = (z_{i,j})$ is called a $K$-multimagic square (MMS(K,N)) if for all $1 \leq k \leq K$, the matrix $Z^{\circ k} := (z_{i,j}^k)$ is a magic square (i.e., the sums of each row, column, and both main diagonals are equal).
2. Importance of distinct elements: Traditionally, magic squares containing repeated elements are considered trivial, making the search for magic squares composed of completely distinct elements more meaningful.

Research Motivation

1. Theoretical refinement: Although the author's previous work 5 proved that when $N > 2K(K+1)$ there exist $K$-multimagic squares containing at least $N+1$ distinct integers, this does not guarantee that all $N^2$ elements are distinct.
2. Method improvement: Rome and Yamagishi, when handling magic squares of distinct $k$th powers, needed to increase the lower bound from $\Delta = 12$ to $\Delta = 20$ to ensure element distinctness. This paper aims to improve upon this result.
3. Technical challenges: The main difficulty lies in finding sufficiently large divisible submatrices to handle coefficient matrix families with specific repeated elements.

Core Contributions

1. Improved existence theorem: Proves that when $N > 2K(K+1)$, there exist $K$-multimagic squares consisting of $N^2$ completely distinct integers, with the lower bound remaining unchanged.
2. Prime version: Through the Green-Tao theorem, proves the existence of $K$-multimagic squares composed of $N^2$ distinct primes.
3. Improved results for $k$th power magic squares: Provides improved existence conditions for magic squares composed of distinct $k$th powers.
4. Technical innovation: Introduces the concept of "matrix dominating functions," effectively resolving technical difficulties encountered by Rome and Yamagishi.

Methodology Details

Core Technical Framework

Matrix Dominating Functions

Definition 1.2: A matrix $C \in \mathbb{C}^{r \times s}$ is said to dominate a function $f: \mathbb{N} \to \mathbb{R}_+$ if for all $J \subset \{1,\ldots,s\}$, $\text{rank}(C_J) \geq \min\{f(|J|), r\}$ where $C_J = [c_j]_{j \in J}$.

Divisible Matrices

Definition 1.1: A matrix $C \in \mathbb{R}^{r \times rn}$ is divisible if there exist disjoint sets $J_l \subset \{1,2,\ldots,rn\}$ (each of size $r$) such that $\text{rank}(C_{J_l}) = r \quad \text{for all } 1 \leq l \leq n$

Main Technical Approach

1. Counting Solutions with Distinct Elements

For the diagonal system $\sum_{1 \leq j \leq s} c_{i,j}x_j^k = 0$ $(1 \leq i \leq r)$, let $S_k^*(P;C)$ denote the solution set with distinct elements. Then: $\#\bigcap_{1 \leq k \leq K} S_k^*(P;C) = \#\bigcap_{1 \leq k \leq K} S_k(P;C) + O\left(\sum_{1 \leq i < j \leq s} \#\bigcap_{1 \leq k \leq K} S_k(P;C^{(i,j)})\right)$

2. Key Lemma

Lemma 2.2: Let $K \geq 2$ and $C \in \mathbb{Z}^{r \times s}$ satisfy $s > rK(K+1) + 2$. If $C$ dominates the function $F(x) = \max\left\{\frac{x - r\{s/r\}}{\lfloor s/r \rfloor}, \frac{x - r\{(s-1)/r\}}{\lfloor (s-1)/r \rfloor}, \frac{x - r\{(s-2)/r\}}{\lfloor (s-2)/r \rfloor}\right\}$ then the asymptotic formula holds: $\#\bigcap_{1 \leq k \leq K} S_k^*(P;C) = P^{s - \frac{rK(K+1)}{2}}(\sigma_K(C) + o(1))$

Matrix Construction for Magic Square Systems

For $N \times N$ magic squares, define the coefficient matrix $C_N^{\text{magic}} \in \mathbb{Z}^{2N \times N^2}$, where:

• Rows correspond to constraints on row and column sums
• Columns correspond to the $N^2$ positions of the magic square

Lemma 3.1 proves that when $N > 4$, $C_N^{\text{magic}}$ dominates the required function $F(x)$.

Experimental Setup

Theoretical Proof Framework

This paper is primarily theoretical work without numerical experiments, establishing existence results through rigorous mathematical proofs.

Proof Strategy

1. Circle Method: Used for handling additive combinatorial problems
2. Hardy-Littlewood Method: Analyzes asymptotic behavior of exponential sums
3. Matrix Theory: Analyzes rank properties of coefficient matrices

Main Results

Theorem 1.3 (Main Result)

Existence of $K$-multimagic squares: Given $K \geq 2$, when $N > 2K(K+1)$, there exist infinitely many MMS(K,N) consisting of $N^2$ distinct integers.

Corollary 1.4

Prime version: Given $K \geq 2$, when $N > 2K(K+1)$, there exist infinitely many MMS(K,N) consisting of $N^2$ distinct primes.

Theorem 1.5

Magic squares of $k$th powers: Given $k \geq 2$, when the following conditions are satisfied, there exist infinitely many $N \times N$ magic squares composed of distinct $k$th powers: $N > \begin{cases}2^{k+1} & \text{if } 2 \leq k \leq 4 \\ 2\lceil k(\log k + 4.20032)\rceil & \text{if } k \geq 5\end{cases}$

Comparison with Known Results

Related Work

Historical Development

1. Constructive methods: Traditionally, multimagic squares have been sought through explicit construction, as in the work of Wroblewski, Trump, Fengchu, and others.
2. General results by Zhang, Chen, and Li: Proved that when $K \geq 2$, there exist $K$-multimagic squares of order $(4K-2)^K$.
3. Application of Circle Method: Bremner discussed in lectures during the 1990s the possibility of applying the circle method to this problem.

Recent Progress

Rome and Yamagishi 7 addressed the existence of magic squares of distinct $k$th powers but required larger lower bounds to ensure complete element distinctness. This paper improves upon their results through the concept of matrix dominating functions.

Technical Innovations

1. Concept of Matrix Dominating Functions

This provides an appropriate perspective for understanding the divisibility of coefficient matrices, offering deeper insight into the divisibility of submatrices.

2. Unified Treatment Framework

Through Lemma 2.2, provides a unified technical framework for handling distinctness constraints, avoiding the technical difficulties encountered by Rome and Yamagishi.

3. Improved Lower Bound Analysis

For $k$th power magic squares, improves the lower bound by approximately half compared to Rome-Yamagishi results.

Conclusions and Discussion

Main Conclusions

1. Theoretical refinement: Proves that under the same lower bound $N > 2K(K+1)$, not only do $K$-multimagic squares containing sufficiently many distinct elements exist, but versions with completely distinct elements also exist.
2. Method superiority: The matrix dominating function method is more effective than traditional divisible matrix methods when handling distinctness constraints.

Limitations

1. Optimality of lower bounds: Although improving upon existing results, significant gaps remain between theoretical lower bounds and constructive results.
2. Computational complexity: Theoretical existence results do not provide effective construction algorithms.

Future Directions

1. Further improvement of lower bounds: Seeking tighter theoretical lower bounds.
2. Constructive algorithms: Converting existence proofs into practical construction methods.
3. Other constraint conditions: Considering other types of constraints (such as consecutive integers, special sequences, etc.).

In-Depth Evaluation

Strengths

1. Theoretical rigor: Employs mature analytic number theory methods with complete and reliable proofs.
2. Technical innovation: The introduction of matrix dominating functions represents an important technical contribution.
3. Result improvements: Improves upon best-known results in multiple aspects.
4. Clear presentation: The paper is well-structured with appropriate handling of technical details.

Weaknesses

1. Theory-practice gap: Significant gap between theoretical lower bounds and known constructive results.
2. Computational feasibility: Existence proofs do not provide practical construction methods.
3. Constant optimization: Certain constants (such as 4.20032) may have room for optimization.

Impact

1. Academic value: Provides important theoretical foundations for multimagic squares and power magic squares theory.
2. Methodological contribution: The concept of matrix dominating functions may have applications in other combinatorial problems.
3. Future research: Establishes foundations for further theoretical and constructive investigations.

Application Scenarios

1. Theoretical mathematics research: Number theory, combinatorics, additive combinatorics
2. Computational mathematics: Existence analysis of large-scale magic squares
3. Cryptographic applications: Design of matrices with special structures

References

The paper cites 11 related references, primarily including:

• 5 D. Flores' previous work on $K$-multimagic squares
• 7,8 N. Rome and S. Yamagishi's recent research on power magic squares
• 6 L. Low, J. Pitman, and A. Wolff's foundational theory on diagonal congruences
• 2,3 A. Bremner's early work on squares of squares