An official website of the United States government
Abstract Magic squares have been extremely useful and popular in combinatorics and statistics. One generalization of magic squares ismagic rectangleswhich are useful for designing experiments in statistics. A necessary and sufficient condition for the existence of magic rectangles restricts the number of rows and columns to be either both odd or both even. In this paper, we generalize magic rectangles to even by oddnearly magic rectangles. We also prove necessary and sufficient conditions for the existence of a nearly magic rectangle, and construct one for each parameter set for which they exist.
more »
« less
This content will become publicly available on September 1, 2026
A circle method approach to K‐multimagic squares
Abstract In this paper, we investigate‐multimagic squaresof order . These are magic squares that remain magic after raising each element to the th power for all . Given , we consider the problem of establishing the smallest integer for which there existnontrivial‐multimagic squares of order . Previous results on multimagic squares show that for large . We use the Hardy–Littlewood circle method to improve this to The intricate structure of the coefficient matrix poses significant technical challenges for the circle method. We overcome these obstacles by generalizing the class of Diophantine systems amenable to the circle method and demonstrating that the multimagic square system belongs to this class for all .
more »
« less
- Award ID(s):
- 2001549
- PAR ID:
- 10638942
- Publisher / Repository:
- Wiley
- Date Published:
- Journal Name:
- Journal of the London Mathematical Society
- Volume:
- 112
- Issue:
- 3
- ISSN:
- 0024-6107
- Page Range / eLocation ID:
- article no. e70290, 27pp
- Subject(s) / Keyword(s):
- Hardy-Littlewood method additive forms in differing degrees magic squares multimagic squares
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract A transversal in an latin square is a collection of entries not repeating any row, column, or symbol. Kwan showed that almost every latin square has transversals as . Using a loose variant of the circle method we sharpen this to . Our method works for all latin squares satisfying a certain quasirandomness condition, which includes both random latin squares with high probability as well as multiplication tables of quasirandom groups.more » « less
-
We study the problem of decomposing a polynomial p into a sum of r squares by minimizing a quadratically penalized objective fp(u)=‖‖∑ri=1u2i−p‖‖2. This objective is nonconvex and is equivalent to the rank-r Burer-Monteiro factorization of a semidefinite program (SDP) encoding the sum of squares decomposition. We show that for all univariate polynomials p, if r≥2 then fp(u) has no spurious second-order critical points, showing that all local optima are also global optima. This is in contrast to previous work showing that for general SDPs, in addition to genericity conditions, r has to be roughly the square root of the number of constraints (the degree of p) for there to be no spurious second-order critical points. Our proof uses tools from computational algebraic geometry and can be interpreted as constructing a certificate using the first- and second-order necessary conditions. We also show that by choosing a norm based on sampling equally-spaced points on the circle, the gradient ∇fp can be computed in nearly linear time using fast Fourier transforms. Experimentally we demonstrate that this method has very fast convergence using first-order optimization algorithms such as L-BFGS, with near-linear scaling to million-degree polynomials.more » « less
-
Abstract This paper introduces several means to expedite a known Voronoi heuristic method for solving a continuousp‐center location problem, which is to cover a polygon withpcircles such that no circle's center lies outside the polygon, no circle's center drops inside a polygonal hole, and the radius of the largest circle is as small as possible. A key step in the Voronoi heuristic is the repeated task of determining the constrained minimum covering circle (CMCC), but the best‐known method for this task is brute‐force and inefficient. This paper develops an improved method by exploiting the convexity of a related subproblem and employing an optimized search procedure. The algorithmic enhancements help to drastically reduce the effort required for finding the CMCC, and in turn, significantly expedite the solution of thep‐center problem. On a realistic‐scale test case, the proposed algorithm ran 400× faster than the literature benchmark.more » « less
-
Abstract We develop a version of the Kloosterman circle method with a bump function that is used to provide asymptotics for weighted representation numbers of nonsingular integral quadratic forms. Unlike many applications of the Kloosterman circle method, we explicitly state some constants in the error terms that depend on the quadratic form. This version of the Kloosterman circle method uses Gauss sums, Kloosterman sums, Salié sums, and a principle of nonstationary phase. We briefly discuss a potential application of this version of the Kloosterman circle method to a proof of a strong asymptotic local–global principle for certain Kleinian sphere packings.more » « less
