Research manuscript, 20 November 2026. AI-assisted internal mathematical checks have found no flaw in the argument below. External review remains outstanding; this manuscript is not presented as peer-reviewed.
Abstract
Let count the distinct permanents of all binary circulant matrices of prime order . Nemeth, Seberry and Shu conjectured in 1979 that . We give an argument establishing and hence contradicting that conjecture. The construction uses dense binary circulants with prescribed Fourier profiles. A uniform permanent estimate of McCullagh, in the form proved by Divoux and Wang, separates permanent values within each row sum. The classical Brualdi–Newman congruence separates values belonging to different row sums. The proof does not establish the stronger conjectural fixed-row-sum asymptotic of Resta and Sburlati. The probabilistic construction also admits a deterministic, though exponential-time, specification.
1. The question and the result
For a positive integer and a set , write Thus is a binary circulant, and every row and column has sum . Define All supports are allowed: zero may belong to , no symmetry condition is imposed, and the row sum is not fixed.
Nemeth, Seberry and Shu [1, p.181] conjectured that for prime . This is Conjecture 27 in the Cheon–Wanless survey [3]. Their discussion distinguishes it from the fixed-degree conjecture of Resta and Sburlati [4].
Theorem 1. There is an absolute constant such that, for every sufficiently large prime , In particular, along the primes.
No explicit numerical starting prime is asserted. A less sharp, fully specified amplitude grid also gives These statements concern all row sums collectively, not a fixed sparse row sum.
We use natural logarithms. For a real matrix, is the largest singular value and is the maximum absolute entry. The constants in all asymptotic bounds below are independent of the support, row sum and amplitude in their stated ranges.
2. The external analytic input
Put .
Analytic input. Fix and . Uniformly over doubly stochastic matrices satisfying one has
The qualitative version of (1) is McCullagh's permanent asymptotic [5], explicitly proved with uniformity in Divoux–Wang [6, Proposition 3.1 and Remark 2.1]. The rate used here is extracted from estimates in their proof; Appendix A gives that extraction. The permanent asymptotic and its underlying analytic estimates are external results, not claimed as contributions of this manuscript. In (1) the determinant square root is the positive real one. Zero entries in are permitted.
For the qualitative conclusion , their stated uniform estimate alone suffices. Section 6 separates that conclusion from the quantitative extension, which uses the rate in (1).
3. Binary supports with controlled Fourier profiles
Lemma 2. Let be prime, let be an integer satisfying , and put . For each , there is a support of size exactly such that the eigenvalues of satisfy where .
Proof. Write . Independently select each with probability These probabilities lie in . If is the selection indicator, character orthogonality gives For each frequency, Hoeffding's inequality applied to real and imaginary parts bounds the probability that the complex error exceeds by . Taking and applying a union bound over all frequencies gives failure probability at most . Thus a realization exists for which every Fourier error is at most .
Its cardinality differs from by at most , using frequency zero. Add or delete that many elements to obtain a set with exactly elements. Every edit changes every unnormalized Fourier coefficient by at most one. All errors after repair are therefore at most . Dividing by proves (2). The Fourier eigenvalue convention may reverse all frequencies; the estimates are unchanged.
This is an existence argument for each profile. When many profiles are used later, they may be chosen separately; no simultaneous random event is required.
4. The permanent associated with a profile
Define
Lemma 3. There is an absolute constant such that, for all sufficiently large , every support supplied by Lemma 2 satisfies
Proof. A real circulant is normal and is diagonalized by the Fourier matrix. For , the constant-direction eigenvalue is zero and the other eigenvalues are , . Consequently the eigenvalues of are the squared magnitudes of those eigenvalues.
Every entry of is either or , so . By (2), for all sufficiently large . We can apply (1) with the fixed constants , .
Parseval's identity supplies the exact relation Indeed, , and . The exceptional eigenvalues are complex conjugates. It follows that For clarity, the last sum does not accumulate copies of a worst-case error. For , Since the squared magnitudes in that sum are at most , while their total is at most two by (5), their contribution is at most Take large enough that , and put . Then On , . The difference between the exceptional term in (6) and is therefore at most .
Finally, (1) changes the logarithm by . This follows directly because its determinant factor is at least one and its normalized permanent is at least one by the van der Waerden inequality. Combining these bounds with proves (4).
5. Separating different row sums
The following congruence is classical: it is the binary case of Brualdi–Newman [2, Theorem 3.2, p.161]. We include its proof.
Lemma 4. If is prime, then
Proof. The permanent counts permutations of for which for every . Translation by acts by conjugation, Every orbit has size one or . A fixed permutation commutes with translation by one, so it is a translation . Such a translation is admissible exactly when . There are fixed permutations, proving (8).
Thus distinct degrees in the interval produce disjoint sets of permanent values.
6. Counting distinct values
6.1. Qualitative disproof using only uniform asymptotics
Fix an arbitrary positive integer , and choose any distinct positive amplitudes in . For each degree in the dense interval, construct a support for each amplitude.
For , Continuity and compactness give a positive minimum separation of adjacent limiting logarithmic values, uniformly over . Even with (4) replaced by a uniform , all values within each degree are distinct for sufficiently large . Lemma 4 separates the degrees. Therefore Since is arbitrary, . This already disproves the original conjecture.
6.2. Quantitative bound
On , , (9) gives Set , and choose For sufficiently large , . Adjacent limiting logarithmic values differ by at least Each actual normalized logarithm differs from its target by at most , by Lemma 3. Hence all permanents within each degree are distinct. Lemma 4 again separates degrees, giving This proves Theorem 1.
For a grid independent of the unspecified constant , take with the same amplitudes. The ratio of adjacent target separation to the error grows like , and tends to infinity. This proves the stated corollary.
All constants in Lemmas 2 and 3 are independent of . The proof therefore permits to grow. Uniform qualitative convergence without a rate would not, by itself, justify any prescribed growing choice of .
7. A deterministic specification
This section gives a finite construction, not an efficient algorithm. Let , and take a rational amplitude from the grid with . Enumerate binary strings lexicographically and select the first whose unnormalized Fourier coefficients differ from the targets (3) by strictly less than , at every frequency. Such a string exists by the same concentration argument, since and the union failure probability is less than one.
Repair its cardinality by adding or removing the smallest available indices. The resulting error is less than , so the proof applies with enlarged absolute constants. Squared-error comparisons involve real algebraic numbers in a cyclotomic extension, and can be decided exactly. This defines a deterministic exponential-time family; no closed-form support or polynomial-time construction is claimed.
Appendix A. Extracting a uniform rate
We explain why the estimates in Divoux–Wang [6, proof of Proposition 3.8 and Section 3.3] imply the rate in (1). This appendix extracts a rate from their proof; it does not reproduce their underlying Gaussian and rook-polynomial analysis.
Fix , and choose a fixed compact interval with . If , the estimate is immediate. For an -by- matrix , define its rook polynomial by where the permanent of the empty matrix is one. The normalized rook expression in their proof is The determinant square root is the analytic branch equal to one at ; it is defined on the disk . Their coefficient estimates imply, uniformly for , with fixed constants . Their Cauchy estimate bounds the remaining coefficient sum by , after a fixed sufficiently large choice of .
Here is a sharper evaluation of (11) than its qualitative use in that paper. Put and . For large , the denominators are at least . Grouping by , the sum is at most Put . For , When , the power sum on the right is at most 22. The complete bound is thus Consequently their normalized rook approximation has uniform relative error on .
Their Gamma representation is Write and . On , and its derivative are uniformly bounded. Direct Gamma moments give Thus replacing by on costs . The probability of the complementary event is exponentially small; the stronger weighted tail estimate in their Section 3.3 bounds its contribution to by . Combining the central rook error, the Lipschitz estimate and this tail bound proves (1), with constants depending only on the fixed bounds.
Scope, provenance and review status
The analytic permanent estimate and the modular congruence are prior results. The proposed contribution is their application to a family of binary Fourier profiles, followed by uniform amplitude separation and counting across dense degrees. Literature searches checked the original paper, subsequent surveys and specialist status listings; no prior full resolution was located. Such searches cannot guarantee novelty or rule out unindexed work.
Independent AI-assisted internal checks examined the argument, rate extraction and conjecture scope. These checks are not independent human peer review. Finite exact-permanent checks are supplied separately as sanity checks, not as evidence sufficient for the asymptotic theorem. No Lean verification or external peer review is claimed.
References
- E. Nemeth, J. Seberry and M. Shu, On the distribution of the permanent of cyclic (0,1) matrices, Utilitas Mathematica 16 (1979), 171–182; conjecture on printed p.181 (PDF p.11). Original paper.
- R. A. Brualdi and M. Newman, Some Theorems on the Permanent, Journal of Research of the National Bureau of Standards 69B (1965), 159–163. Theorem 3.2. Original paper.
- G.-S. Cheon and I. M. Wanless, An update on Minc's survey of open problems involving permanents, Linear Algebra and its Applications 403 (2005), 314–342. Conjecture 27, pp.329–330. Paper.
- G. Resta and G. Sburlati, On the number of different permanents of some sparse (0,1)-circulant matrices, Linear Algebra and its Applications 375 (2003), 197–209. DOI.
- P. McCullagh, An asymptotic approximation for the permanent of a doubly stochastic matrix, Journal of Statistical Computation and Simulation 84 (2014), 404–414. arXiv:1205.5723; DOI.
- A. Divoux and S. Wang, The Maximum Number of Hamiltonian Cycles in Tournaments, arXiv:2610.23755v1 (2026). Proposition 3.1, Remark 2.1, Proposition 3.8 and Section 3.3. Paper.
The current specialist status page consulted during the novelty check was Yair Lavi, Conjecture 27. It is status evidence, not a source for the proof.