Primality testing via circulant matrix eigenvalue structure

This one is sole-authored, written at ExtensityAI, and posted to arXiv as 2505.00730. Before anything else: the paper carries a footnote on its first page stating that it was created with AI assistance using the Symbia Engine from the SymbolicAI framework, and the arXiv record repeats the disclosure. That belongs at the top of any description of the work rather than buried in it.

The problem

Primality testing is, practically speaking, solved. Miller-Rabin is fast and wrong with negligible probability; AKS is deterministic and polynomial. Nobody needs another test.

What is not exhausted is the supply of characterisations: statements of the form “n is prime if and only if some other object has some other structural property.” Those are worth having because they connect number theory to machinery developed elsewhere, and because the connection sometimes turns out to run in both directions. This paper adds one such bridge, between primality and the spectral structure of a specific family of matrices.

The idea

Start with the cyclic shift. Let $W_n$ be the n-by-n matrix with a 1 in position $(i,j)$ whenever $j\equiv i+1\mathrm{mod}n$, and zeros elsewhere; it rotates a vector’s entries by one. Its eigenvalues are exactly the n-th roots of unity, ${\lambda }_j=e^{2\pi ij/n}$.

Now form the composite matrix

$$C_n=W_n+W_n^2$$

Because $W_n$ and $W_n^2$ share eigenvectors, the eigenvalues of $C_n$ follow immediately: ${\mu }_j={\lambda }_j+{\lambda }_j^2$.

The main theorem is that an integer $n>2$ is prime if and only if the minimal polynomial of $C_n$ has exactly two irreducible factors over the rationals.

The reason is Galois theory rather than arithmetic. The $j=0$ eigenvalue is always ${\mu }_0=1+1=2$, contributing a linear factor $(x-2)$. That accounts for one factor for every n. What happens to the rest depends entirely on the subfield structure of the cyclotomic field $\mathbb{Q}({\zeta }_n)$, the rationals extended by a primitive n-th root of unity ${\zeta }_n$.

If n is prime, every ${\lambda }_j$ for j from 1 to $n-1$ is a primitive n-th root of unity, and the Galois group, isomorphic to the units mod n, acts transitively on them. Since each ${\mu }_j$ is a polynomial in ${\lambda }_j$, the whole set forms a single Galois orbit and shares one irreducible minimal polynomial of degree $n-1$. Two factors, exactly.

If n is composite, say $n=ab$, then $\mathbb{Q}({\zeta }_n)$ contains the proper subfields $\mathbb{Q}({\zeta }_a)$ and $\mathbb{Q}({\zeta }_b)$. Eigenvalues indexed by multiples of a land inside $\mathbb{Q}({\zeta }_b)$ and cannot be conjugate to those associated with primitive n-th roots. They form separate orbits, each contributing its own factor, so the count is at least three. The paper sharpens this into a lower bound: one factor for the linear term, plus at least one more for each distinct prime dividing n. Repeated prime factors do not each buy a separate factor, which is why a prime power such as 125 lands at three rather than higher.

Composite structure, in other words, shows up as fragmentation of the spectrum into orbits. Primality is the case where no fragmentation is available.

Why it matters, and what it does not

It is a genuine if-and-only-if, and the experiments back it: across the ranges tested, the number of irreducible factors separates primes from composites with no exceptions and no borderline cases.

The algorithm is a different matter, and the paper is direct about it. Computing eigenvalues is $O(n)$, determining the Galois orbits costs up to $O(n\cdot \phi (n))$, where $\phi (n)$ counts the integers below n coprime to it, and for prime n that works out quadratic in the value of n. Measured against the input’s bit-length, the only measure that matters at cryptographic sizes, the running time is exponential. The paper says so in as many words.

There is a structural caveat a reader should catch too. The practical algorithm applies the orbit computation only below $10^6$; above that it falls back to factorising n and checking whether the factorisation is a single prime to the first power. Factorisation is strictly harder than primality testing, so on large inputs the fast path is not the theorem doing the work. The benchmark table shows the method competitive around $n\approx 10^6$ and beaten by Miller-Rabin by $n\approx 10^{10}$. That is the honest summary, and it is the one the paper’s own conclusion gives.

The contribution is the characterisation, not the speed.

Where it applies

Two places, neither of them cryptography.

The first is teaching. The criterion is visual in a way divisibility arguments are not. The eigenvalues of C_97 trace one connected curve in the complex plane; those of C_90 show visible clustering and discontinuities that correspond to its divisors. Minimal-polynomial coefficients behave the same way, smooth and extended for primes, jagged and compressed for composites. A student can see the subfield lattice instead of being told about it.

The second is as a test case for machine-assisted mathematics. The result is self-contained, the algebra is long enough to get quietly wrong by hand, and every step is symbolically checkable. That makes it a reasonable place to run an AI-assisted workflow and then be specific about what came out, which is why the disclosure on the paper is a feature of the experiment rather than a blemish on it.