Deterministic Fourier profiles for the circulant permanent argument

This note derandomizes the profile construction in the quadratic candidate refinement. It does not provide an explicit threshold for the analytic permanent estimate.

Fix rational ρ=k/p∈[1/3,2/3]\rho=k/p\in[1/3,2/3] and a∈[1/24,1/12]a\in[1/24,1/12], and use the twelve sectors and random variables YℓY_\ell from that refinement. Let UjU_j be the selected count in sector jj minus its mean. The nonnegative score S=|Y0|2+|Y1|2+∑jUj2p+∑ℓ∉{0,1,−1}|Yℓ|4p3 S=\frac{|Y_0|^2+|Y_1|^2+\sum_j U_j^2}{p} +\frac{\sum_{\ell\notin\{0,1,-1\}}|Y_\ell|^4}{p^3} has expectation at most six. Indeed the first two moments contribute at most two, the sector variances total at most pp, and the previous fourth-moment bound contributes at most three. Choose the membership bits in order, each time keeping the conditional expected score nonincreasing. The two possible next conditional expectations average to the current one with the specified Bernoulli probabilities, so one of them works. The resulting assignment obeys the same required asymptotic bounds: each sector has both types in linear quantity because its discrepancy is at most 6p\sqrt{6p}, the initial cardinality and leading coefficient errors are O(p)O(\sqrt p), and the bulk fourth sum is O(p3)O(p^3).

This is a polynomial-time construction in pp and the bit length of the rational parameters, in the exact bit model. Expand SS as a degree-at-most-four polynomial, first reducing each XsjX_s^j for j≥1j\ge1 to XsX_s and then taking the product of the means for any unfixed distinct variables in a monomial. There are polynomially many terms, involving powers of a primitive pp-th root ζ\zeta and rational coefficients. Thus each conditional expectation can be computed in the cyclotomic field with polynomial-size rational coefficient lists; the products have bounded degree in the input probabilities, and a common denominator can be taken as a fixed power of the product of the rational input denominators and pp. To compare the final real field values, rewrite each as a rational polynomial in x=2cos(2π/p)x=2\cos(2\pi/p) using conjugate symmetry and the recurrence for ζj+ζ−j\zeta^j+\zeta^{-j}. The relevant xx is the largest real root of the degree-(p−1)/2(p-1)/2 minimal polynomial obtained from Φp\Phi_p by the same recurrence. Exact univariate root isolation and sign determination at that isolated root take polynomial time in degrees and coefficient bit lengths. Sector membership can be computed using the integer indices ss, without approximating angles.

For the swaps after cardinality repair, compare squared errors after each admissible addition/removal pair using the same real-field arithmetic and choose a minimizer. The sector argument guarantees a decrease of at least one in error modulus whenever that modulus is at least four; stop when the squared error is less than sixteen. Thus the number of swaps is O(p)O(\sqrt p). This yields the same profile guarantees as the probabilistic proof. In particular a grid with rational amplitudes spaced by any sufficiently large fixed integer multiple of 1/p1/p gives deterministic constructions of the quadratic number of witnesses for sufficiently large primes. The analysis does not say how large that integer or the starting prime must be.