Németh–Seberry–Shu conjecture: a quadratic lower bound

Candidate extension; not externally reviewed. The manuscript and fourth-moment refinement give simpler proofs of weaker bounds. This note uses the same cited analytic inputs, extracting a sharper error bound. It concerns all row sums collectively, not the fixed-sparse-row-sum conjecture of Resta and Sburlati.

Claim. For some absolute c>0c>0 and all sufficiently large primes pp, the number V(p)V(p) of distinct permanent values of binary circulants of order pp satisfies V(p)≥cp2V(p)\ge cp^2. For every integer kk with p/3≤k≤2p/3p/3\le k\le2p/3, the row sum kk contributes at least c′pc'p distinct values, for an absolute c′>0c'>0.

1. Tune the first Fourier coefficient to bounded error

Use the Bernoulli model and fourth-moment event in the preceding note, with a∈[1/24,1/12]a\in[1/24,1/12], ρ=k/p\rho=k/p, and ζ=e2πi/p\zeta=e^{2\pi i/p}. The three bounds there fail with total probability at most 3/83/8. Also partition the unit circle into twelve fixed half-open sectors of equal width. Each contains p/12+O(1)p/12+O(1) of the points ζs\zeta^s. In each sector the expected selected and unselected counts are each at least one sixth its size, since the Bernoulli parameters lie in [1/6,5/6][1/6,5/6]. By Hoeffding's inequality and a union bound, with probability 1−o(1)1-o(1) all sectors have both counts at least one twelfth their size. The estimates are uniform in k,ak,a, so a realization satisfying both events exists.

Repair the cardinality to kk by O(p)O(\sqrt p) edits. The first Fourier coefficient is now within O(p)O(\sqrt p) of papa. Let zz be papa minus this coefficient. If r=|z|≥4r=|z|\ge4, add an unselected root from the sector containing the direction of zz, and remove a selected root from its antipodal sector. The Fourier increment δ\delta has length at most two and projection at least 2cos(π/6)=32\cos(\pi/6)=\sqrt3 on the direction of zz. Hence |z−δ|2≤r2−2r3+4≤(r−1)2(r≥4). |z-\delta|^2\le r^2-2r\sqrt3+4\le (r-1)^2 \qquad(r\ge4). Thus at most O(p)O(\sqrt p) swaps reduce the remaining error to less than four. There are always candidates: each sector started with ≫p\gg p roots of each type, and the cardinality repair and all swaps together change at most O(p)O(\sqrt p) membership choices. This argument preserves kk.

Divide the Fourier coefficients by kk to obtain the eigenvalues of D=Cp(S)/kD=C_p(S)/k. The resulting profile satisfies λ1=a/ρ+O(p−1),λ−1=λ1¯,∑ℓ∉{0,1,−1}|λℓ|4=O(p−1). \lambda_1=a/\rho+O(p^{-1}),\qquad \lambda_{-1}=\overline{\lambda_1}, \qquad \sum_{\ell\notin\{0,1,-1\}}|\lambda_\ell|^4=O(p^{-1}). The bulk estimate follows just as in the preceding note: the original unnormalized fourth sum is O(p3)O(p^3), all edits contribute O(p)O(\sqrt p) to each coefficient, and (x+y)4≤8(x4+y4)(x+y)^4\le8(x^4+y^4). In particular the maximum bulk modulus is O(p−1/4)O(p^{-1/4}). Thus B=D−JpB=D-J_p obeys the same uniform entry and operator bounds as before. Exact Parseval and the log determinant formula from the preceding note give logdet(I−BTB)−1/2=F(ρ,a)+O(p−1),F(ρ,a)=12(1/ρ−1)+h((a/ρ)2),h(x)=−log(1−x)−x. \log\det(I-B^TB)^{-1/2}=F(\rho,a)+O(p^{-1}),\quad F(\rho,a)=\tfrac12(1/\rho-1)+h((a/\rho)^2),\quad h(x)=-\log(1-x)-x .

2. Sharpen the quantitative permanent estimate

Use the inputs in Appendix A of the manuscript, extracted from Divoux–Wang, Section 3: for ∥B∥max≤2/p\|B\|_{\max}\le2/p, ∥B∥op≤1/2\|B\|_{\mathrm{op}}\le1/2, their rook polynomial RB(s)R_B(s) differs from Δ(s)=det(I−s2BTB)−1/2\Delta(s)=\det(I-s^2B^TB)^{-1/2} by O(p−1)O(p^{-1}) uniformly on I=[3/4,5/4]I=[3/4,5/4]. If T∼Gamma(p+1,1)T\sim\operatorname{Gamma}(p+1,1) and Z=p/TZ=p/T, the normalized permanent equals 𝔼RB(Z)\mathbb E R_B(Z). The absolute contribution of RB(Z)R_B(Z) outside II is exponentially small by the cited proof. Also ℙ(Z∉I)≤e−c0p\mathbb P(Z\notin I)\le e^{-c_0p} for a constant c0>0c_0>0 and all large pp, by exponential moment bounds for Gamma variables.

The new step is to use the centered first-order term rather than bound its absolute value. On II the functions Δ,Δ′,Δ″\Delta,\Delta',\Delta'' are uniformly bounded: differentiate logΔ(s)=−12∑jlog(1−s2σj2)\log\Delta(s)=-\tfrac12\sum_j\log(1-s^2\sigma_j^2), where the singular values satisfy ∑jσj2=∥B∥F2≤4\sum_j\sigma_j^2=\|B\|_F^2\le4 and maxjσj≤1/2\max_j\sigma_j\le1/2. The denominators are uniformly bounded away from zero and the sums are bounded by constants times ∑jσj2\sum_j\sigma_j^2. Taylor's formula gives Δ(Z)=Δ(1)+Δ′(1)(Z−1)+O((Z−1)2)(Z∈I). \Delta(Z)=\Delta(1)+\Delta'(1)(Z-1)+O((Z-1)^2)\quad(Z\in I). The exact moments are 𝔼Z=1\mathbb EZ=1 and 𝔼(Z−1)2=1/(p−1)\mathbb E(Z-1)^2=1/(p-1). The first moment omitted by restricting to II has modulus at most ℙ(Z∉I)/(p−1)\sqrt{\mathbb P(Z\notin I)/(p-1)} by Cauchy–Schwarz. The omitted constant term is also exponentially small; the Taylor remainder contributes O(p−1)O(p^{-1}). It follows that ppp!per(D)=Δ(1)+O(p−1) \frac{p^p}{p!}\operatorname{per}(D)=\Delta(1)+O(p^{-1}) uniformly. As Δ(1)≥1\Delta(1)\ge1, taking logarithms retains this error order.

3. Count

For every k,ak,a in the specified ranges a suitable support therefore has log normalized permanent F(ρ,a)+O(p−1)F(\rho,a)+O(p^{-1}), uniformly. On the compact rectangle of parameters, ∂aF≥b>0\partial_a F\ge b>0. Let CC bound the error by C/pC/p. Take an amplitude grid from 1/241/24 in steps of L/pL/p up to 1/121/12, with fixed L>2C/bL>2C/b. Adjacent values of the target function differ by at least bL/pbL/p, so all corresponding permanents for a fixed kk are distinct. This gives ≫p\gg p values for each of ≫p\gg p distinct row sums. The classical congruence perCp(S)≡k(modp)\operatorname{per}C_p(S)\equiv k\pmod p ensures that values for different row sums are disjoint, proving the proposed bound.

Kocharovsky, Kocharovsky and Tarasov (2020), §7.2 also use a determinantal approximation and Fourier diagonalization for positive weighted circulants. That calculation does not count distinct permanent values of binary circulants. The literature search distinguishes the all-row-sums question from earlier fixed-degree work. Follow-up searches for a quadratic lower bound across all row sums did not locate a prior proof; this is not a priority certification.