Németh–Seberry–Shu conjecture

What Lean checks

Written asymptotic disproof and a quadratic lower bound; finite checks are not part of the proof.

Let V(p)V(p) be the number of distinct permanent values of all binary circulant matrices of prime order pp. Németh, Seberry and Shu conjectured that V(p)=O(p)V(p)=O(p) (original paper, p. 181). We prove that V(p)/p→∞V(p)/p\to\infty 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 V(p)=Ω(p2)V(p)=\Omega(p^2).

1. Binary circulants with a prescribed Fourier mode

Fix an integer kk between p/3p/3 and 2p/32p/3, put ρ=k/p\rho=k/p, and choose a real amplitude a∈[1/24,1/12]a\in[1/24,1/12]. Write ζ=exp(2πi/p)\zeta=\exp(2\pi i/p). Independently include each s∈ℤ/pℤs\in\mathbb Z/p\mathbb Z with probability ρ+2acos(2πs/p)\rho+2a\cos(2\pi s/p), which is in [1/6,5/6][1/6,5/6]. The expected unnormalized Fourier coefficients are kk at zero, papa at 1,−11,-1, and zero elsewhere by character orthogonality.

Hoeffding's inequality on the real and imaginary parts, followed by a union bound over pp frequencies, gives a realization in which all coefficients differ from their means by at most 2plogp2\sqrt{p\log p}. Indeed, at a single frequency the failure probability for complex error exceeding tt is at most 4exp(−t2/p)4\exp(-t^2/p). Add or delete elements until the support SS has size kk. The zeroth coefficient bounded the number of such edits, and each edit changes every coefficient by at most one.

Let CC be the circulant with entry Cij=𝟏{j−i∈S}C_{ij}=\mathbf 1_{\{j-i\in S\}} and let D=C/kD=C/k. The Fourier eigenvalues λℓ\lambda_\ell of DD consequently satisfy

λ0=1,λ±1=a/ρ+O(logp/p),maxℓ∉{0,1,−1}|λℓ|=O(logp/p).\lambda_0=1,\qquad \lambda_{\pm1}=a/\rho+O\!\left(\sqrt{\log p/p}\right),\qquad \max_{\ell\notin\{0,1,-1\}}|\lambda_\ell|=O\!\left(\sqrt{\log p/p}\right).

All errors are uniform in kk and aa.

2. Separation within a row sum

Put J=𝟏𝟏T/pJ=\mathbf 1\mathbf 1^T/p and B=D−JB=D-J. The matrix DD is doubly stochastic and its entries are nonnegative. We have ∥B∥max≤2/p\|B\|_{\max}\le2/p. Fourier diagonalization gives ∥B∥op=maxℓ≠0|λℓ|≤1/2\|B\|_{\mathrm{op}}=\max_{\ell\ne0}|\lambda_\ell|\le1/2 for all sufficiently large pp. The uniform permanent asymptotic of McCullagh, in the form stated by Divoux and Wang, Proposition 3.1 and Remark 2.1, gives

ppp!per(D)=(1+o(1))det(I−BTB)−1/2.\frac{p^p}{p!}\operatorname{per}(D)=(1+o(1))\det(I-B^TB)^{-1/2}.

The uniform relative error becomes an additive o(1)o(1) after taking logarithms. Since BB is real and unitarily diagonalized by Fourier modes, the eigenvalues of BTBB^TB are zero and the |λℓ|2|\lambda_\ell|^2 for ℓ≠0\ell\ne0. By Parseval,

∑ℓ≠0|λℓ|2=pk−1=ρ−1−1.\sum_{\ell\ne0}|\lambda_\ell|^2=\frac pk-1=\rho^{-1}-1.

Write h(x)=−log(1−x)−xh(x)=-\log(1-x)-x. Since h(x)=O(x2)h(x)=O(x^2) uniformly for 0≤x≤1/40\le x\le1/4, the sum of these remainders over the bulk modes is o(1)o(1): it is bounded by a constant times their maximum squared modulus times their total squared modulus. The two exceptional eigenvalues are conjugate. Consequently

log(ppp!kpper(C))=F(ρ,a)+o(1),F(ρ,a)=12(ρ−1−1)+h((a/ρ)2),\log\!\left(\frac{p^p}{p! k^p}\operatorname{per}(C)\right) =F(\rho,a)+o(1),\qquad F(\rho,a)=\tfrac12(\rho^{-1}-1)+h((a/\rho)^2),

uniformly in kk and aa.

Fix any positive integer MM and choose MM distinct increasing amplitudes in [1/24,1/12][1/24,1/12]. The function F(ρ,a)F(\rho,a) is strictly increasing in aa, since h′(x)=x/(1−x)>0h'(x)=x/(1-x)>0 for x>0x>0. For these finitely many amplitudes the adjacent gaps have a positive minimum over ρ∈[1/3,2/3]\rho\in[1/3,2/3] by continuity. For sufficiently large pp, the uniform error is smaller than half that minimum. Thus each kk gives at least MM distinct permanents.

3. Separation across row sums

The permanent counts permutations σ\sigma such that σ(i)−i∈S\sigma(i)-i\in S for all ii. Conjugation by translations partitions these permutations into orbits of size one or pp. Fixed permutations commute with translation by one, so exactly the kk translations by elements of SS are fixed. Thus per(C)≡k(modp)\operatorname{per}(C)\equiv k\pmod p, the binary case of Brualdi–Newman, Theorem 3.2. Distinct row sums in the dense interval give disjoint sets of permanents. It follows that

V(p)≥M(⌊2p/3⌋−⌈p/3⌉+1)V(p)\ge M\bigl(\lfloor2p/3\rfloor-\lceil p/3\rceil+1\bigr)

for every sufficiently large prime pp depending on MM. Since MM was arbitrary, V(p)/p→∞V(p)/p\to\infty. This contradicts the conjecture. ▫\square