🔢 mathematics

Panmagic permutations and N-ary groups

This paper investigates panmagic permutations, which correspond to maximal non-attacking queen configurations on a toroidal chessboard, by analyzing their algebraic structure as special cosets of the dihedral group and exploring their cycle decomposition through connections to classical number theory concepts such as multiplicative orders and quadratic residues.

Original authors: Sergiy Koshkin, Jaeho Lee

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sergiy Koshkin, Jaeho Lee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a giant, magical chessboard that wraps around itself like a donut (a torus). On this board, you want to place $n$ queens so that none of them can attack each other. In a normal chessboard, queens attack in straight lines and diagonals. But on this "donut" board, the diagonals wrap around the edges, creating a complex web of attack paths.

This paper is about finding specific arrangements of these queens and discovering that these arrangements follow hidden, beautiful mathematical rules. The authors, Sergiy Koshkin and Jaeho Lee, treat these arrangements not just as pictures on a board, but as permutations (rearrangements of numbers) and study how they behave when you "multiply" them together.

Here is the breakdown of their discovery in simple terms:

1. The Magic Squares and the Queens

First, the authors look at Panmagic Squares. You might know a "Magic Square" as a grid where every row, column, and diagonal adds up to the same number. A "Panmagic" square is even cooler: every diagonal, even the ones that wrap around the edges of the grid, adds up to that same number.

If you take a solution to the "Donut Chessboard" problem (placing non-attacking queens) and turn it into a grid of 1s and 0s (where 1 is a queen and 0 is empty), you get a Panmagic Permutation Matrix. The authors focus on a specific, simpler type of these solutions called Affine Panmagic Permutations. These can be described by simple math formulas, like $y = ax + b$, but using "clock arithmetic" (modular arithmetic).

2. The "Magic" Multiplication Rule

The most surprising discovery in the paper is about what happens when you multiply these permutations together.

The Old Rule: Usually, if you multiply two numbers (or matrices) from a special set, you might get something outside that set.
The New Rule: The authors found that for these specific panmagic permutations, if you multiply three (or more) of them together, the result stays inside the set.
- Think of it like a club with a weird entry rule: You can't get in by bringing just one friend (multiplying two), but if you bring a group of three friends, the whole group is welcome.
- This is called N-ary multiplication (where N is the number of items you multiply at once).

3. The "Dihedral" Dance Floor

To understand why this happens, the authors introduce a group of symmetries called the Dihedral Group ( $D_n$ ).

The Analogy: Imagine a regular polygon (like a pentagon). You can rotate it or flip it over, and it looks the same. The set of all these rotations and flips is the Dihedral Group.
The authors show that the panmagic permutations are essentially "cosets" of this group.
Coset Analogy: Imagine the Dihedral Group is a dance floor. The panmagic permutations are a specific group of dancers standing in a circle around that dance floor.
- If you take three dancers from that circle and "multiply" them (perform a specific dance move sequence), they land back in the circle.
- If you take two, they might land on the dance floor itself (the Dihedral Group), but not back in the circle.
- This explains why you need three (or more) to stay in the set.

4. The Prime Number Connection

The paper reveals that this "magic" only works perfectly when the size of the board ( $n$ ) is a prime number (like 5, 7, 11, 13) and isn't divisible by 2 or 3.

The "4k+1" Secret: They found a special connection to a famous type of prime number: those that can be written as $4k + 1$ (like 5, 13, 17).
The Cycle: When you look at how these permutations move numbers around (their "cycle structure"), the authors found that for these special primes, the movement is incredibly uniform. Every number (except one) moves in a perfect loop of the same length.
The Analogy: Imagine a carousel. For most board sizes, the horses move in messy, different-sized circles. But for these special "4k+1" primes, every horse moves in a perfect circle of the exact same size, except for one horse that stays still in the center.

5. The "Post" Cover

The authors use a concept from advanced algebra called the Post Coset Theorem (named after mathematician Emil Post).

The Analogy: Think of the panmagic permutations as a specific type of "shadow" cast by a larger, more complex group of numbers (the Affine Group).
The theorem says that any time you see a set of objects that behaves like this "N-ary multiplication" rule, it is essentially a shadow (a coset) of a normal subgroup.
The authors identified exactly which "shadow" these panmagic permutations are. They are shadows of the Dihedral Group, cast by the larger Affine Group.

Summary of the Findings

Existence: These special "panmagic" arrangements only exist on boards of certain sizes (prime numbers not divisible by 2 or 3).
Structure: They form a specific mathematical structure where multiplying three (or more) of them keeps you in the group, but multiplying two does not.
Classification: The authors proved that for prime-sized boards, these permutations are perfectly described by simple linear formulas (Affine permutations).
Pattern: For a specific subset of these primes ( $4k+1$ ), the permutations have a beautiful, uniform cycle structure where everything moves in identical loops.

What the paper does NOT claim:
The authors do not claim this has any immediate use in cryptography, computer science, or physics right now. They are purely exploring the algebraic and number-theoretic beauty of these mathematical objects. They suggest that understanding these patterns might help solve other hard problems in the future, but they stop short of applying it to real-world technology. They also note that while they solved the puzzle for "simple" (affine) permutations, the "complex" (non-affine) ones remain a mystery.

Technical Summary: Panmagic Permutations and N-ary Groups

Problem Statement
The paper investigates the algebraic structure of panmagic permutations, defined as permutations whose associated permutation matrices are panmagic squares (matrices where all rows, columns, main diagonals, and broken diagonals sum to the same magic constant). These permutations correspond to solutions of the modular $n$ -queens problem on a toroidal chessboard. While the existence of such permutations is known to be restricted to dimensions $n$ where $2, 3 \nmid n$ (Polya dimensions), their algebraic properties under multiplication have remained underexplored. Specifically, the paper addresses the closure properties of sets of panmagic permutations under $N$ -ary multiplication (multiplying $N$ elements at a time) and seeks to characterize these sets within the framework of group theory and number theory.

Methodology
The authors adopt a group-theoretic approach, shifting focus from the matrices themselves to the permutations they encode.

Affine Permutations: The study restricts attention to affine panmagic permutations, which can be expressed by linear formulas of modular arithmetic, $\sigma(i) \equiv ai + b \pmod n$ . These form the general affine group $Aff(\mathbb{Z}_n)$ .
Dihedral Group Connection: The authors identify the dihedral group $D_n$ (generated by a flip $\phi$ and a cyclic shift $\kappa$ ) as a normal subgroup within $Aff(\mathbb{Z}_n)$ . They utilize the fact that $D_n$ preserves the panmagic property under multiplication.
Coset Analysis: The paper analyzes cosets of $D_n$ within $Aff(\mathbb{Z}_n)$ . By examining the slopes $a$ of the affine permutations, the authors determine which cosets consist entirely of panmagic permutations.
N-ary Group Theory: The authors apply the theory of $N$ -ary groups (generalizations of binary groups to operations involving $N$ elements), specifically utilizing Emil Post's 1940 Post coset theorem. This theorem states that $N$ -ary groups are essentially cosets of normal subgroups where the quotient group is cyclic of order $N-1$ .
Number Theoretic Tools: The analysis relies heavily on properties of primitive roots, multiplicative orders, and quadratic residues in $\mathbb{Z}_p$ for prime dimensions $p$ .

Key Contributions and Results

Characterization of Affine Panmagic Permutations:
The paper establishes that for a prime dimension $p$ , an affine permutation $\pi_{a,b}$ is panmagic if and only if its slope $a$ satisfies $a, a \pm 1 \in \mathbb{Z}_p^\times$ (i.e., $a$ and its neighbors are units). This leads to a dichotomy: in prime dimensions, every affine permutation is either panmagic or dihedral.
Closure under N-ary Multiplication:
The authors prove that sets of panmagic permutations form cosets of the dihedral group $D_p$ within the affine group $Aff(\mathbb{Z}_p)$ .
- Theorem 4: For a prime $p \ge 5$ , the cosets $C_i = \pi_r^i D_p$ (where $r$ is a primitive root) consist of panmagic permutations. These cosets are closed under $N$ -ary multiplication where $N = \frac{p+1}{2}$ .
- Theorem 5: The paper generalizes this to specific cosets $\pi_a D_p$ , showing they are strictly $N$ -ary (closed under $N$ -ary multiplication but not fewer) where $N = \text{ord}_p(a^2) + 1$ .
Connection to $4k+1$ Primes:
A significant result links the algebraic structure to classical number theory. The paper proves that strictly ternary (3-ary) panmagic cosets exist if and only if the dimension $p$ is of the form $4k+1$ . This condition is equivalent to $-1$ being a quadratic residue modulo $p$ .
Cycle Structure:
The authors analyze the disjoint cycle decomposition of these permutations. They find that permutations in a panmagic coset $\pi_a D_p$ have at most two cycle types.
- If the strict arity $N$ is odd, all permutations in the coset share the same cycle type (one fixed point and cycles of length $2(N-1)$ ).
- If $N$ is even, there are two cycle types with lengths $N-1$ and $2(N-1)$ .
- Consequently, strictly ternary panmagic cosets (where $N=3$ ) contain permutations with a single fixed point and only 4-cycles.
Post Coset Theorem Application:
The paper demonstrates that the sets of panmagic permutations are concrete realizations of Post cosets. The dihedral group $D_p$ acts as the "Post associate" (the normal subgroup), and the group generated by the coset and $D_p$ (either a subgroup of $Aff(\mathbb{Z}_p)$ or $Aff(\mathbb{Z}_p)$ itself) serves as the "Post cover."

Significance and Claims
The paper claims that treating panmagic squares as permutations encoded by modular arithmetic reveals algebraic patterns obscured in matrix representations.

Algebraic Unification: It provides a unified explanation for the closure properties observed in specific cases (like $5 \times 5$ and $7 \times 7$ ) by generalizing them to all prime dimensions using $N$ -ary group theory.
Demystifying Symmetry: The appearance of the dihedral group $D_5$ in Thompson's earlier work on $5 \times 5$ panmagic squares is explained as a specific instance of the general Post coset structure for $p=5$ .
Educational Value: The authors suggest that panmagic permutations serve as an accessible setting for undergraduate students to grasp non-trivial concepts in group theory (normal subgroups, cosets, $N$ -ary groups) and number theory (primitive roots, quadratic residues).
Limitations and Scope: The authors modestly note that their results focus on affine panmagic permutations in prime dimensions. They acknowledge that non-affine panmagic permutations exist for $n \ge 13$ and that the results for composite dimensions are more complex, requiring different approaches as the dichotomy between panmagic and dihedral permutations fails in those cases. The paper does not claim to solve the general counting problem for all panmagic permutations, noting it remains a hard problem.