A circle method approach to K-multimagic squares

Basic Information

• Paper ID: 2406.08161
• Title: A circle method approach to K-multimagic squares
• Author: Daniel Flores
• Classification: math.NT (Number Theory), math.CO (Combinatorics)
• Publication Date: June 2024, updated version January 2025
• Paper Link: https://arxiv.org/abs/2406.08161

Abstract

This paper investigates $K$-multimagic squares, which are $N \times N$ magic squares that remain magic after raising each element to the $k$-th power for all $2 \leqslant k \leqslant K$. Given $K \geqslant 2$, the author addresses the problem of determining the minimum integer $N_2(K)$ such that there exists a nontrivial $K$-multimagic square of order $N_2(K)$. Previous results showed $N_2(K) \leqslant (4K-2)^K$ for large $K$. This paper establishes the bound $N_2(K) \leqslant 2K(K+1)+1$ using the Hardy-Littlewood circle method. Through Granville's argument, the paper also derives the existence of infinitely many nontrivial prime-valued $K$-multimagic squares of order $2K(K+1)+1$.

Research Background and Motivation

1. Problem Definition: The core problem addressed is determining the minimum order of $K$-multimagic squares. A $K$-multimagic square is an $N \times N$ matrix where each row, column, and main diagonal has equal sums after raising each element to the $k$-th power for $1 \leqslant k \leqslant K$.
2. Problem Significance:
   • Magic squares have a history spanning thousands of years and represent a classical problem in mathematics
   • Martin Gardner's 1996 generalization of the 3×3 distinct perfect squares magic square problem remains unsolved
   • Multimagic squares represent an important extension of magic square theory with profound number-theoretic significance
3. Limitations of Existing Methods:
   • Previous construction methods primarily relied on normal multimagic squares (elements being 1, 2, ..., $N^2$)
   • The known upper bound $(4K-2)^K$ exhibits potential exponential growth for large $K$
   • Lack of systematic analytical methods for handling the general case
4. Research Motivation:
   • Need for more precise asymptotic bounds
   • The Hardy-Littlewood circle method provides a powerful tool for handling such additive problems
   • Aim to improve bounds from potential exponential growth to polynomial growth

Core Contributions

1. Main Theoretical Result: Proves $N_2(K) \leqslant 2K(K+1)+1$, which represents a significant improvement over the previous bound $(4K-2)^K$, particularly for $K \geqslant 4$.
2. Methodological Innovation: First application of the Hardy-Littlewood circle method to multimagic square problems, establishing a general framework for handling diagonal systems of different degrees.
3. Technical Breakthroughs:
   • Relaxes the condition of matrix height non-singularity by introducing the concept of matrix "dominating functions"
   • Establishes rank condition analysis applicable to coefficient matrices of multimagic squares
4. Prime-Valued Results: Using Granville's argument and the Green-Tao theorem, proves the existence of infinitely many prime-valued $K$-multimagic squares.

Detailed Methodology

Task Definition

Given $K \geqslant 2$ and $N$, find an $N \times N$ matrix $Z = (z_{i,j})$ such that for all $1 \leqslant k \leqslant K$, the matrix $Z^{\circ k} := (z_{i,j}^k)$ is magic. Nontrivial means using more than $N$ distinct integers.

Model Architecture

1. Diagonal System Framework

The $K$-multimagic square problem is transformed into solving a diagonal system: $\sum_{1 \leqslant j \leqslant s} c_{i,j} x_j^k = 0 \quad (1 \leqslant i \leqslant r, 1 \leqslant k \leqslant K)$

where $C = (c_{i,j})$ is the coefficient matrix, and $R_K(P;C)$ denotes the number of solutions satisfying $\max_j |x_j| \leqslant P$.

2. Circle Method Application

Define the exponential generating function: $f_K(\alpha;C) = \prod_{1 \leqslant j \leqslant s} \sum_{|x| \leqslant P} e\left(\sum_{1 \leqslant k \leqslant K} (\alpha_k \cdot c_j) x^k\right)$

By orthogonality: $R_K(P;C) = \int_{[0,1)^{r \times K}} f_K(\alpha;C) d\alpha$

3. Major Arc and Minor Arc Decomposition

• Major Arc $M(Q)$: Region where $|\alpha_{i,k} - a_{i,k}/q| \leqslant QP^{-k}$
• Minor Arc $m(Q)$: Complementary region
• Establish asymptotic formula: $R_K(P;C) = S_K(Q;C)J_K(Q,P;C) + o(P^{s-\frac{rK(K+1)}{2}})$

Technical Innovations

1. Matrix Dominating Condition

Introduce new concept: Matrix $C$ dominates function $f$ if and only if for all $J \subset \{1,...,s\}$: $\text{rank}(C_J) \geqslant \min\{f(|J|), r\}$

This condition is weaker than traditional height non-singularity but remains sufficiently strong.

2. Key Function $F(x)$

Define: $F(x) = \max\left\{\frac{x - \text{rem}(s,r)}{\lfloor s/r \rfloor}, \frac{x - \text{rem}(s-1,r)}{\lfloor (s-1)/r \rfloor}\right\}$

3. Main Technical Theorem

Theorem 2.2: If $K \geqslant 2$, $C \in \mathbb{Z}^{r \times s}$ satisfies $s \geqslant rK(K+1)$ and $C$ dominates function $F(x)$, then: $R_K(P;C) = P^{s-\frac{rK(K+1)}{2}}(\sigma_K(C) + o(1))$ where $\sigma_K(C) > 0$.

Experimental Setup

Magic Square Coefficient Matrix Construction

For an $N \times N$ magic square, construct a $2N \times N^2$ matrix $C^{\text{magic}}_N$, where each column corresponds to a matrix position $(i,j)$, encoding the row sum and column sum conditions of the magic square.

Key Verification Steps

1. Rank Analysis: Prove that $C^{\text{magic}}_N$ dominates function $F(x)$
2. Nonsingular Solution Existence: Utilize the existence of doubly diagonal Latin squares (DDLS)
3. Jacobian Matrix Analysis: Ensure nonsingularity of local solutions

Experimental Results

Main Results Comparison

Asymptotic Behavior Analysis

The paper proves that for $K \geqslant 2$ and $N \geqslant 2K(K+1)$: $M_{K,N}(P) \sim cP^{N(N-K(K+1))}$ where $c > 0$ is a constant.

Prime-Valued Results

Corollary 1.3: Given $K \geqslant 2$, for each $N \geqslant 2K(K+1)$, there exist infinitely many nontrivial prime-valued $K$-multimagic squares.

Related Work

Historical Development

• Classical Constructions: Specific constructions by Wroblewski, Trump, Fengchu and others
• General Theory: $(4K-2)^K$ bound by Zhang, Chen, Li
• Circle Method Applications: Work by Brandes, Parsell on additive equations

Technical Connections

The paper's methods relate to:

1. Vinogradov's Mean Value Theorem: Used for minor arc estimates
2. Additive Combinatorics: Diagonal equations of different degrees
3. Algebraic Geometry: Rank analysis of Jacobian matrices

Conclusions and Discussion

Main Conclusions

1. Establishes a quadratic upper bound $N_2(K) \leqslant 2K(K+1)+1$ for the minimum order of $K$-multimagic squares
2. Proves the infinite existence of prime-valued multimagic squares
3. Provides a new circle method framework for handling additive problems of different degrees

Limitations

1. Constants: The constant 2 in the bound may not be optimal
2. Lower Bounds: No corresponding lower bound estimates provided
3. Computational Complexity: The method is primarily an existence proof without direct construction algorithms

Future Directions

1. Higher-Dimensional Generalization: Extension to $d$-dimensional hypercubes, with expected bound $N_d(K) \ll_d K^2$
2. Optimal Constants: Determine optimal constant factors
3. Construction Algorithms: Develop practical construction methods

In-Depth Evaluation

Strengths

1. Theoretical Breakthrough: Improves from potentially exponential bounds to quadratic bounds, representing a qualitative leap
2. Methodological Innovation: Successfully adapts the circle method to handle mixed-degree problems with high technical difficulty
3. Completeness: Comprehensive theoretical system from existence to prime-valued results
4. Rigor: Rigorous mathematical proofs with meticulous technical treatment

Weaknesses

1. Practicality: For small $K$ values, new bounds are not always superior
2. Constructivity: The method is non-constructive, unable to directly generate specific magic squares
3. Complexity: Proof techniques are complex with high comprehension threshold

Impact

1. Theoretical Value: Provides new analytical tools for multimagic square theory
2. Methodological Significance: New application of circle method in combinatorial number theory
3. Future Research: Opens new directions for related problem investigations

Applicable Scenarios

The method applies to:

1. Existence problems for multimagic squares with large parameter $K$
2. Other types of additive combinatorial problems
3. Asymptotic counting research of combinatorial structures

References

The paper cites 23 important references covering:

• Recent advances in Vinogradov's mean value theorem (Bourgain, Demeter, Guth)
• Circle method applications to additive problems (Brandes, Parsell, Wooley)
• Construction theory of multimagic squares (Boyer, Trump, Zhang, et al.)
• Prime distribution theory (Granville, Green-Tao)