Németh–Seberry–Shu conjecture: removing the logarithmic loss

This is a quantitative refinement of the candidate disproof, not a separate conjecture. It uses the same uniform O(p−1/2)O(p^{-1/2}) permanent estimate extracted in Appendix A of that manuscript from Divoux–Wang, Proposition 3.1 and its proof. External review remains outstanding.

Claim. If V(p)V(p) counts distinct permanent values of binary p×pp\times p circulants, then V(p)≥cp3/2V(p)\ge c p^{3/2} for an absolute c>0c>0 and all sufficiently large primes pp. In fact each row sum p/3≤k≤2p/3p/3\le k\le 2p/3 contributes at least c′pc'\sqrt p distinct values.

The earlier proof paid a logarithmic factor to control every Fourier error individually. Only the first conjugate pair needs a sharp individual bound. For the bulk, the sum of fourth powers suffices.

Fourier profile with a fourth-moment bound

Fix p≥5p\ge5, kk in the indicated interval, ρ=k/p\rho=k/p, and a∈[1/24,1/12]a\in[1/24,1/12]. Write ζ=e2πi/p\zeta=e^{2\pi i/p}. Choose independent Bernoulli variables XsX_s with means ρ+2acos(2πs/p)\rho+2a\cos(2\pi s/p). For each frequency ℓ\ell, put Yℓ=∑s(Xs−𝔼Xs)ζℓsY_\ell=\sum_s (X_s-\mathbb EX_s)\zeta^{\ell s}. The uncentered expected Fourier coefficients are kk at zero, papa at frequencies 1,−11,-1, and zero elsewhere.

Uniformly in ℓ\ell, 𝔼|Yℓ|2≤p\mathbb E|Y_\ell|^2\le p and 𝔼|Yℓ|4≤3p2\mathbb E|Y_\ell|^4\le3p^2. For the fourth moment expand YℓYℓ¯YℓYℓ¯Y_\ell\overline{Y_\ell}Y_\ell\overline{Y_\ell}: independence and centering eliminate every index pattern containing a singleton. There are pp patterns with one index and 3p(p−1)3p(p-1) patterns with two indices each appearing twice. Each remaining summand has modulus at most one.

By Markov and a union bound, some realization satisfies all three conditions |Y0|2≤8p,|Y1|2≤8p,∑ℓ∉{0,1,−1}|Yℓ|4≤24p3. |Y_0|^2\le 8p,\quad |Y_1|^2\le 8p,\quad \sum_{\ell\notin\{0,1,-1\}}|Y_\ell|^4\le24p^3. Indeed each failure probability is at most 1/81/8. Repair the cardinality to kk by at most 8p\sqrt{8p} additions/deletions. Every Fourier coefficient changes by at most that amount. If λℓ\lambda_\ell are the Fourier eigenvalues of the repaired circulant divided by kk, then, uniformly, λ0=1,|λ1−a/ρ|≤68/p,∑ℓ∉{0,1,−1}|λℓ|4=O(p−1). \lambda_0=1,\qquad |\lambda_1-a/\rho|\le 6\sqrt{8/p},\qquad \sum_{\ell\notin\{0,1,-1\}}|\lambda_\ell|^4=O(p^{-1}). For the last bound use (x+y)4≤8(x4+y4)(x+y)^4\le8(x^4+y^4), sum the errors from repair, and divide by k4≥(p/3)4k^4\ge(p/3)^4. Real entries give λ−1=λ1¯\lambda_{-1}=\overline{\lambda_1}. In particular every bulk eigenvalue is O(p−1/4)O(p^{-1/4}), which is enough for the required fixed spectral gap.

Separation and count

Let D=Cp(S)/kD=C_p(S)/k and B=D−JpB=D-J_p, where JpJ_p has all entries 1/p1/p. We have ∥B∥max≤2/p\|B\|_{\max}\le2/p and ∥B∥op≤1/2\|B\|_{\mathrm{op}}\le1/2 for all sufficiently large pp uniformly in the parameters. By Parseval, ∑ℓ≠0|λℓ|2=1/ρ−1\sum_{\ell\ne0}|\lambda_\ell|^2=1/\rho-1. With h(x)=−log(1−x)−xh(x)=-\log(1-x)-x, the log determinant correction is exactly logdet(I−BTB)−1/2=12(1/ρ−1)+h(|λ1|2)+12∑ℓ∉{0,1,−1}h(|λℓ|2). \log\det(I-B^TB)^{-1/2} =\tfrac12(1/\rho-1)+h(|\lambda_1|^2) +\tfrac12\sum_{\ell\notin\{0,1,-1\}}h(|\lambda_\ell|^2). The bulk sum is O(p−1)O(p^{-1}) by h(x)=O(x2)h(x)=O(x^2) uniformly on 0≤x≤1/40\le x\le1/4. The exceptional term differs from h((a/ρ)2)h((a/\rho)^2) by O(p−1/2)O(p^{-1/2}). Combining this with the uniform quantitative permanent estimate gives log(perCp(S)kpp!/pp)=F(ρ,a)+O(p−1/2),F(ρ,a)=12(1/ρ−1)+h((a/ρ)2). \log\!\left(\frac{\operatorname{per}C_p(S)}{k^p p!/p^p}\right) =F(\rho,a)+O(p^{-1/2}),\qquad F(\rho,a)=\tfrac12(1/\rho-1)+h((a/\rho)^2). Taking logs preserves the external absolute error because the determinant correction is at least one and the approximating normalized permanent is uniformly bounded away from zero for sufficiently large pp.

On the compact parameter rectangle, ∂aF\partial_a F has a strictly positive lower bound bb. Let C>0C>0 be a uniform bound on the constant in the last error term. Use amplitudes 1/24+jL/p1/24+jL/\sqrt p in [1/24,1/12][1/24,1/12] with fixed L>2C/bL>2C/b. Successive log permanents differ by at least (bL−2C)/p>0(bL-2C)/\sqrt p>0. There are ≫p\gg\sqrt p amplitudes for each kk. No simultaneous probabilistic event across amplitudes is needed: the existence argument applies separately to each amplitude, with the same bounds. By the Brualdi–Newman congruence, perCp(S)≡k(modp)\operatorname{per}C_p(S)\equiv k\pmod p, so the values for different row sums in this interval are disjoint. The ≫p\gg p row sums give the claim.

The conclusion still depends on the cited analytic input and its quantitative error. It does not resolve the fixed-sparse-row-sum conjecture of Resta and Sburlati.