Exact-rank quadratic correlation: a phase-compatible Clique reduction

Abstract

We give an additive-gap reduction from Clique to correlation maximization over Boolean quadratic phases of prescribed even polar rank r ≥ 4. For the bounded function obtained by averaging graph-edge characters, an (r + 1)-clique gives exact-rank optimum 2^(−r/2) binom(r + 1, 2)/|E|, while its absence decreases the optimum by at least 2^(−r/2)/|E|. The proof combines the graphic span bound with control of nonzero affine Fourier supports and a nondegenerate quadratic Gauss witness realizing every clique-edge sign simultaneously. Consequently, an exact-rank additive optimizer with running time f(r) poly(n, ε⁻¹) would give a fixed-parameter Clique algorithm, with the corresponding randomized implication for randomized optimization. Explicit examples separate exact rank from rank at most a cap and show why the rank-two gap fails. An anchored affine-restriction lemma preserves both an output-rank cap and its rank distance from a known quadratic, providing a positive structural contrast.