Improving the Constant in the Aharonov--Regev Theorem

1 Introduction

• The constant matters because the hardness exponent and the NP ∩ coNP exponent now agree up to ε, leaving a factor n^ε on the hardness side and c on the membership side.The Aharonov–Regev proof gives c = 100, and this paper studies that constant.Source: §1 · p. 2
• Modeling certificates as samples makes the verifier’s tests linear constraints on their empirical distribution, and accepted certificates correspond, up to concentration slack, to feasible distributions below threshold.The linear-program value is the infimum of the expected cosine objective over feasible distributions.Source: §1 · pp. 2–3
• Close-side soundness and far-side completeness are dual views of the same program: close targets admit envelope certificates, while far-target completeness requires a feasible distribution with small objective.For the far side, the obstructing dual certificate is a positive-semidefinite quadratic form.Source: §1 · pp. 3–4

Phases and the phase program.

• For derivative tests of every order k ≥ 2, the close-side value is vk = 3/16; lattice certificates show no derivative test at the target, of any order, raises the close radius.Source: Phases and the phase program · p. 5
• The verifier has a finite-bit implementation using N = 100n^2⌈log2 n⌉ dual vectors, exact rational arithmetic, and tests of a trigonometric sum, its gradient, and its Hessian.It is sound for n ≥ 8 and complete for n ≥ n0(c).Source: Phases and the phase program · p. 6
• The Gaussian prover is not always optimal: on specified code-lattice deep holes it fails, while a parity certificate built from short dual vectors with odd target pairing passes every test.The coset Gaussian mass is at least half the lattice mass at these deep holes, which lie beyond 0.2735√n.Source: Phases and the phase program · p. 6
• At order-two targets, the exact prover value is governed by the spectral capacity of the odd dual coset; the Hessian constraint requires twice the capacity of the spectral-only constraint.At and above σ^2μ = 2, the Hessian-augmented infimum is −1 and is not attained.Source: §1 · p. 5, Phases and the phase program · p. 7

1.2 Organization

• The paper proceeds from Gaussian sums and concentration through verifier and phase programs, duality, close-side results, far-side analysis, and a finite-bit verifier appendix.The far-side analysis includes order-two targets, code lattices where the Gaussian prover fails, and random-lattice obstructions.Source: §1.2 · p. 7

2.1 Lattices, Gaussian sums and the coset mass function

• For dist(x,L) ≥ c√n, the coset mass function satisfies f_L(x) ≤ β(c)^n, with β(1) = 0.1786.Source: §2.1 · p. 8
• The second-moment transference identity gives E⟨w,e⟩² < ∥e∥²/2π and fixes the verifier’s spectral bound at 1/2π.Summing the directional bounds gives E∥w∥² ≤ n/2π.Source: §2.1 · p. 9
• The bound 1/2π cannot be improved in general: the identity’s loss is the primal Gaussian’s second moment in the direction e.That loss is small in directions where the lattice is stretched.Source: §2.1 · p. 9

2.2 Concentration

• Hoeffding and matrix Bernstein bounds are recorded for concentration, alongside a truncation estimate for discrete Gaussian samples.Conditioning samples on ∥w∥ ≤ √n has tail probability at most β(1)^n.Source: §2.2 · p. 10

3.1 The verifiers

• As τ, η1, and η2 tend to zero, gradient and Hessian tests raise the close radius from σ^-1/4 to σ^-1√(3/16).Without derivative tests, the exact radius at threshold τ is arccos(τ)/(2πσ).Source: §3.1 · p. 11

3.2 The prover’s program

• A certificate is modeled by its empirical distribution on the dual lattice, and verifier tests become linear constraints on that distribution.The constraints include a spectral matrix bound and, for derivative-augmented verifiers, gradient and Hessian bounds; Appendix A implements the tests in exact rational arithmetic.Source: §3.1 · p. 11, §3.2 · p. 12

3.3 Phases and the phase program

• Writing t = y + e reduces dual-vector phases to θ = ⟨w,e⟩, whose second moment is bounded by σ²∥e∥² in the soundness analysis.The soundness proposition uses the phase program to bound the target’s distance when the certificate passes the verifier tests.Source: §3.3 · p. 13

3.4 Far thresholds and the constant

• A far threshold requires distributions supported on dual vectors of norm at most n² that certify every target at distance at least c√n for all sufficiently large n.The support bound is a normalization for polynomial-bit certificates; the theorem connects achieving a threshold with coNP membership when the verifier is sound.Source: §3.4 · p. 14

4 Duality

• Finite-dimensional separation establishes strong duality for the programs over probability measures with finitely many linear or conic constraints.Source: §4 · p. 14

4.1 The phase program and envelope inequalities

• The phase program’s dual variables are envelopes: a multiplies the threshold constraint, while b1, b2, and higher bm correspond to derivative tests.For the studied orders, matching feasible distributions and envelopes establish the program values without loss of slack.Source: §4.1 · pp. 15–16

4.2 The prover’s program and quadratic certificates

• The infimum over finitely supported feasible distributions equals the full program value, for both the prover and phase programs.The exact values and constant identification are established for V(k); their proofs use phase reduction and scaling properties that general test functions need not share.Source: §4.2 · p. 17
• For the prover’s program, a dual feasible point gives a quadratic form M ⪰ 0 that bounds the cosine phase over the whole dual lattice.On the close side, derivative-test dual solutions have rank one along the target offset, and this restriction loses nothing in the close radius.Source: §4.2 · p. 17

5.1 Three envelopes

• The order-0 and order-1 inequalities hold for every real θ, with equality at ±1/4 and {0, ±1/2}, respectively; the Hessian envelope is nonnegative with equality at ±1/4 and ±3/4.Source: §5.1 · p. 18

5.2 Proof of the Hessian envelope

• An exact derivative-based monotonicity argument proves the Hessian envelope globally, with only double zeros at ±1/4 and ±3/4.Source: §5.1 · p. 18, §5.2 · p. 20

5.3 Proof of Theorem 1

• v0=1/16, v1=1/8, v2=3/16, and for every k≥3 the infimum is 3/16 but is not attained; finite rational distributions approach it.Source: §5.3 · pp. 20–21
• For sufficiently large T, the rational solution has E_P[θ²] ≤ 3/16 + ε; if E_P[cos(2πθ)] = 0 and E_P[J_a] = 0 for 1≤a≤k, then f_W(t)=0 and ∇^M f_W(t)=0 for 1≤M≤k.Source: §5.3 · p. 22, §5.5 · p. 23

5.4 Soundness of the Hessian-augmented verifier

• For k=0, soundness rejects every YES instance when the target is within r0; the same conclusion holds for k=1,2 when the respective gradient and Hessian tests are included.The soundness condition assumes tests (a), (b), threshold τ, tolerances σ and η, and distance at most rk.Source: §5.4 · p. 22

5.5 Realization by lattice certificates

• For k=0, k=1, and k≥2, the exact close-radius limits are σ^-1√(1/16), σ^-1√(1/8), and σ^-1√(3/16), respectively; no derivative order can raise them.For k≤2, the boundary radius is also attainable; for k≥3, the theorem gives the construction for radii strictly above the stated limit.Source: §5.5 · p. 24
• With all line tests, the phase-program value is exactly 2/27 for k=0 and remains 1/8 for k=1; finite tests numerically raise the Hessian-augmented value to 0.1962 for 4≤J≤6.The reported numerical value is 0.1958 for J=2 and J=3, and the corresponding Gaussian-prover constant is 0.3593 for large J.Source: §5.5 · p. 25

6 Completeness and the proof of the main theorem

• Matrix Bernstein removes the Hoeffding and net slacks in the spectral bound, while 1/2π is the lowest possible bound.The earlier proof used 3N in place of (1 + δ)N/2π.Source: §6 · p. 27
• For every n ≥ n0(c), a Gaussian-sampled certificate passes tests (b)–(e) with margin at least n^-4, establishing completeness.At n = 8, the stated failure probabilities sum to less than 0.3527.Source: §6 · p. 29
• The GapSVP coNP verifier runs the GapCVP verifier on n index-two sublattice instances and accepts when all accept.A shortest nonzero vector has an odd coordinate in some basis direction, giving the stated reduction to a distance instance.Source: §6 · p. 29
• Table 2 gives the cutoff n0(c) for the finite-bit verifier, with the Hessian-size condition binding except at c = 2.For c ≤ 0.5, the listed cutoffs are within a factor of 4 of the least n meeting the threshold-test condition.Source: Table 2 · p. 29
• The Hessian test, with v2 = 3/16, gives c = 2/(π√3) = 0.3676; this value does not depend on the parameters (Theorem 2).Source: §6 · pp. 29–30

7.1 The Gaussian prover

• For every c > c0, the dual discrete Gaussian conditioned on vectors of norm at most n² passes the verifier’s covariance, Fourier, gradient, and Hessian tests with exponentially small bounds.This holds for sufficiently large n and every target at distance at least c√n.Source: §7.1 · p. 30

7.2 The constant of the verifier family

• For k = 0, 1, and 2, the verifier-family constant is characterized by the far-certification threshold divided by the corresponding close radius.The proof establishes this relation by deriving far-certifiability from an accepting certificate and constructing certificates from far-certifiability.Source: §7.2 · pp. 30–31

7.3 Targets of order two

• At order-two targets, the exact-Hessian program has infimum 1 − 2 min(1, σ²µ/2), while the spectral-only program has infimum 1 − 2 min(1, σ²µ).Here µ is the spectral capacity of the odd dual coset, whose dual characterization is a minimum-trace ellipsoid; the Hessian constraint doubles the capacity required at Gaussian spectral level.Source: §7.3 · pp. 32–34

7.4 Code lattices: the Gaussian prover is not optimal

• For every c < 0.2735, code lattices furnish order-two targets with f_L(x) ≥ 1/2 where the Gaussian prover fails but a Hessian-augmented certificate passes.For the explicit rational parameters, a certificate has cosine expectation −0.06 and zero first and second derivative checks.Source: §7.4 · p. 36
• For code lattices, targets satisfy dist(x,L)≥c√n while a certificate has Σ(P)⪯0.1582I, E_Pχ=−0.06, and D1(P)=D2(P)=0.The constructed odd dual vectors have norm at most 0.3844√n.Source: §7.4 · pp. 36–37

7.5 Obstructions from random lattices

• For every ε∈(0,1/2) and all sufficiently large n, there are L and t with 2t∈L, t∉L, dist(t,L)≥r, and every odd vector of L* has norm at least r.The construction uses an index-two sublattice of a Haar-random unimodular lattice and a uniformly random nonzero class of its dual modulo twice the dual lattice.Source: §7.5 · p. 37

7.6 Where the far side stands

• c(2)_far lies in [0.1352, 0.3676].The upper end is Theorem 2.Source: §7.6 · p. 38
• The Gaussian prover cannot achieve a constant below 0.2520; going beyond that bound requires a different prover, and the balanced parity prover works on one lattice family.The Gaussian prover fails on the coset lattices of Theorem 39; a better prover must integrate the dual inequality against something other than DL*.Source: §7.6 · p. 38
• 0.1468√n is the target distance at which random lattices give an order-two obstruction to constructing dual solutions.For order-two targets, the best dual solution is the trace-minimal ellipsoid excluding the odd dual vectors.Source: §7.6 · p. 38

8 Concluding remarks

• Derivative tests on the close side yield the constant 2/(π√3); line tests at target multiples may lower it by about two percent more, numerically but without a closed form.The analysis is complete for tests on derivatives of the cosine sum at the target.Source: §8 · p. 39
• Whether a prover can beat Banaszczyk’s threshold on every lattice reduces to excluding quadratic certificates of small trace.Optimal distributions at order-two targets suggest weighting short dual vectors by how far their target pairing is from an integer rather than by Gaussian mass.Source: §8 · p. 39
• The Gaussian prover threshold c0 remains unknown, with the stated range extending from c* to 1/√(2π).Source: §8 · p. 39
• A polynomial-time checkable certificate for near-lattice behavior beyond second moments and target derivatives remains an open question tied to approaching n/log n.Source: §8 · p. 39

A A finite-bit verifier

• For dimensions n ≥ 8, the appendix implements the Hessian-augmented verifier in the bit model; smaller dimensions, including those below n0(c), are decided by Kannan’s algorithm.Source: A A finite-bit verifier · p. 40
• The input consists of binary-encoded rational entries for B, t, and r, with B nonsingular and r > 0.Source: A A finite-bit verifier · p. 40
• Verifier decisions use exact comparisons of rational numbers or rational symmetric matrices, enclosing transcendental quantities by rational intervals first.Source: A A finite-bit verifier · p. 40

A.1 Rational scale and computable constants

• The verifier parameters use E1,n = 1/√n, E2,n = 4.5/√n, and Nn = 100n²⌈log2 n⌉.Source: §A.1 · p. 40
• The constants π and square roots are enclosed with rational intervals, and O(log n) bits of precision make the interval for the close-radius formula narrower than mn.The appendix uses Machin’s identity and the alternating Taylor series for arctan, plus rational bisection for square roots.Source: §A.1 · p. 40
• The rational scale qn/r defines L′ = (qn/r)BZn and t′ = (qn/r)t, while certificate vectors are represented using integer vectors zi.Source: §A.1 · pp. 40–41
• The phase ⟨wi,t′⟩ is reduced modulo 1 to φi using exact rational arithmetic.Source: §A.1 · p. 41
• The certificate list contains exactly Nn integer vectors zi with entries bounded in absolute value by n^24ℓin; other strings are rejected.Source: §A.1 · p. 41

• Taylor-based rational approximations keep the errors in the function, gradient, and Hessian tests at most mn/16, with polynomial bit complexity.The verifier approximates π and trigonometric terms; the bit length of ξ^-1 and the rational computations are polynomially bounded.Source: §A.2 · p. 41
• Acceptance requires four rational tests corresponding to bounds on the vector sum, function value, gradient, and Hessian.The analytical conditions are ΣW ⪯ SnI, FW < τn, ∥GW∥ ≤ E1,n, and ∥HW∥ ≤ E2,n.Source: §A.2 · pp. 41–42
• Positive semidefiniteness is tested in polynomial time by checking that all coefficients of det(xI + A) are nonnegative.The characteristic polynomial is computable in polynomial time over Q, making this a deterministic polynomial-time test.Source: §A.2 · p. 41
• For n ≥ 8, the finite-bit verifier rejects every rational input and certificate when dist(t, BZ_n) ≤ r.Source: §A.2 · p. 41
• For the stated far-target inputs, every rational input with dist(t, BZ_n) > c√n r has an accepted certificate of polynomial bit length.The passage specifies n ≥ n0(c) and the cutoff of Table 2.Source: §A.2 · p. 42