Let be the number of distinct permanent values of all binary circulant matrices of prime order . Németh, Seberry and Shu conjectured that (original paper, p. 181). We prove that along the primes. This proof uses the uniform permanent asymptotic as stated by Divoux and Wang, not an extracted convergence rate. The quadratic refinement strengthens the bound to .
1. Binary circulants with a prescribed Fourier mode
Fix an integer between and , put , and choose a real amplitude . Write . Independently include each with probability , which is in . The expected unnormalized Fourier coefficients are at zero, at , and zero elsewhere by character orthogonality.
Hoeffding's inequality on the real and imaginary parts, followed by a union bound over frequencies, gives a realization in which all coefficients differ from their means by at most . Indeed, at a single frequency the failure probability for complex error exceeding is at most . Add or delete elements until the support has size . The zeroth coefficient bounded the number of such edits, and each edit changes every coefficient by at most one.
Let be the circulant with entry and let . The Fourier eigenvalues of consequently satisfy
All errors are uniform in and .
2. Separation within a row sum
Put and . The matrix is doubly stochastic and its entries are nonnegative. We have . Fourier diagonalization gives for all sufficiently large . The uniform permanent asymptotic of McCullagh, in the form stated by Divoux and Wang, Proposition 3.1 and Remark 2.1, gives
The uniform relative error becomes an additive after taking logarithms. Since is real and unitarily diagonalized by Fourier modes, the eigenvalues of are zero and the for . By Parseval,
Write . Since uniformly for , the sum of these remainders over the bulk modes is : it is bounded by a constant times their maximum squared modulus times their total squared modulus. The two exceptional eigenvalues are conjugate. Consequently
uniformly in and .
Fix any positive integer and choose distinct increasing amplitudes in . The function is strictly increasing in , since for . For these finitely many amplitudes the adjacent gaps have a positive minimum over by continuity. For sufficiently large , the uniform error is smaller than half that minimum. Thus each gives at least distinct permanents.
3. Separation across row sums
The permanent counts permutations such that for all . Conjugation by translations partitions these permutations into orbits of size one or . Fixed permutations commute with translation by one, so exactly the translations by elements of are fixed. Thus , the binary case of Brualdi–Newman, Theorem 3.2. Distinct row sums in the dense interval give disjoint sets of permanents. It follows that
for every sufficiently large prime depending on . Since was arbitrary, . This contradicts the conjecture.