SHARP HARDNESS FOR MAX-3-CUT AND QUANTUM MAX-CUT

STEVEN HEILMAN

Abstract. Assuming the Unique Games Conjecture, we show it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of α_{3} + ε for every ε > 0, where α_{3} ≈ .83600811464 is the approximation ratio of Frieze-Jerrum’s polynomial-time algorithm from 1995. That is, we prove sharp hardness of approximation for MAX-3-CUT. This result resolves a conjecture of Khot-Kindler-Mossel-O’Donnell from 2004 by proving the three candidate Plurality is Stablest Conjecture for correlations in [−1/2, 2/5] and generalizes the Majority is Stablest Theorem of Mossel-O’Donnell-Oleszkiewicz [Annals of Math, 2010].

With a similar strategy we prove: assuming the Unique Games Conjecture, it is NP-hard to approximate the product-state value of Quantum MAX-CUT within a multiplicative factor of α_{BOV} + ε for every ε > 0, where α_{BOV} ≈ 0.9563372685 is the approximation ratio of the Briët-de Oliveira Filho-Vallentin algorithm. This sharp hardness result completes the conjectured hardness of Hwang-Neeman-Parekh-Thompson-Wright from 2021 by proving their S^{k−1}-valued Borell inequality for correlations in [−.5843, .5843] for all k ≥ 3.

1. Introduction

The MAX-CUT problem is arguably one of the simplest and most thoroughly studied combinatorial optimization problems. It is one of Karp’s original 21 NP-complete problems [Kar72]. In this paper we make progress on understanding the computational hardness of two of its natural generalizations: MAX-3-CUT and Quantum MAX-CUT. For these problems, efficient algorithms are known, but understanding their optimality was a significant challenge.

The MAX-CUT problem asks for the partition of the vertices of a finite undirected graph into two sets that maximizes the number of edges going between the two sets. The result of [CST01] shows that the weighted and unweighted versions of MAX-CUT have the same hardness of approximation (and likewise for MAX-3-CUT). The MAX-CUT problem is NPhard, so if P≠NP, no polynomial-time algorithm can solve it. It is easy to find a partition of the vertices into two sets that is at least 50% as good as the best possible, by random selection of vertices into one of the sets. This algorithm can be derandomized [SG76]. However, achieving a quality of approximation beyond 50% appeared to be a difficult problem.

A highly nontrivial improvement appeared in 1995: for any ε > 0, the semidefinite programming algorithm of [GW95] approximates the MAX-CUT problem in polynomial-time within a multiplicative factor of α_{2} − ε, where

α_{2} := inf_{−1≤ρ≤1} \frac{2}{1} \frac{\frac{1}{π} arccos(ρ)}{1 − ρ} ≈ .87856720578.  (1)

Date: August 3, 2026. Email: stevenmheilman@gmail.com

Supported by NSF Grant CCF AF 2448108. 2020 Mathematics Subject Classification: 68W27, 65K10, 68Q32 Keywords: MAX-CUT, MAX-3-CUT, hardness of approximation, Unique Games Conjecture Department of Mathematics, University of Southern California, Los Angeles, CA 90089.

That is, it is possible to obtain in polynomial-time a partition of the graph where the number of edges going between the two partition elements is at least 87.8% as much as the largest partition value.

The approximation factor (1) remains the best possible in polynomial-time. It is then desirable to obtain a matching hardness result. MAX-CUT was proven MAX-SNP hard in 1991 [PY91], and in 1998, it was shown [BGS98] that approximating MAX-CUT within a factor of 83/84 is NP-hard. This was improved to 16/17 ≈ .9412 in [Hås01]. Despite not reaching the .878 value, this is the best known unconditional NP-hardness result for MAX-CUT. It was also shown in [FS02] that integrality gap instances exist for the Goemans-Williamson algorithm, i.e. graphs exist that achieve the worst case behavior of this algorithm.

In a breakthrough work, [KKMO07] showed that, assuming the Unique Games Conjecture, the gap between the 16/17 hardness and the .87856 … approximation can be closed exactly.

Theorem 1.1 (Sharp Hardness for MAX-CUT, [KKMO07, Theorem 1]). Assume that the Unique Games Conjecture is true [Kho02, KN10, KMS23]. Then, for any ε > 0, it is NPhard to approximate MAX-CUT within a multiplicative factor of α_{2} + ε.

Theorem 1.1 is called a sharp hardness result since the quantity α_{2} gives an exact barrier between tractability (i.e. the polynomial-time algorithm of [GW95]) and intractability (as stated in Theorem 1.1). Theorem 1.1 relied on the Majority is Stablest Theorem and Invariance Principle of [MOO10]. The invariance principle showed that the discrete Majority is Stablest Theorem is equivalent to the continuous Borell’s inequality [Bor85], a known fact from Gaussian geometry proven 20 years prior. In other words, [MOO10] showed that the discrete problem they needed was equivalent to a known continuous problem. Other examples of invariance principles used in different contexts include [Cha06] and [Rot79].

For a statement of the Unique Games Conjecture, see [Kho02, KN10]. For some recent progress demonstrating that the conjecture is “halfway proven,” see [KMS23].

Before the Unique Games Conjecture was introduced, the PCP Theorem [ALM+98, AS98, Hås01] implied that any constraint satisfaction problem (CSP) should be NP-hard to approximate with some multiplicative approximation less than 1. This led to some optimal inapproximability results [Hås01]. For example, MAX-3-SAT has an elementary efficient 7/8 approximation algorithm that chooses variable assignments randomly, but for any ε > 0, a 7/8 + ε approximation is NP-hard [Hås01]. Similarly, MAX-3-LIN(2) has an elementary efficient 1/2 approximation algorithm that chooses variable assignments randomly, but for any ε > 0, a 1/2 + ε approximation is NP-hard [Hås01]. The problems MAX-3-SAT and MAX-3-LIN(2) are therefore approximation resistant: it is hard to approximate them better than simple random guessing. Other sharp NP-hardness of approximation results include: Maximum k-coverage [Fei98], Metric k-center [HS85] and set cover [DS14], the latter relying on parallel repetition.

Some optimal inapproximability results that rely on the Unique Games Conjecture (besides Max-CUT) include: MAX-2-SAT [BHZ24], Min Vertex Cover [KR08], Grothendieck’s inequality [RS09], kernel clustering [KN13], etc. In these problems, unlike MAX-3-SAT and MAX-3-LIN(2), random guessing does not lead to an optimal algorithm. Raghavendra’s result [Rag08] shows that essentially any CSP will have some sharp inapproximability, assuming the Unique Games Conjecture holds. However, this result does not determine what the constant of inapproximability will be for any particular problem.

1.1. MAX-3-CUT. The MAX-3-CUT problem asks for the partition of the vertices of a finite undirected graph into three sets that maximizes the number of edges going between the three sets. This is a natural generalization of MAX-CUT to three sets of vertices. This problem is equivalent to the Maximum 3-Colorable Subgraph problem. As we will see, the analysis of MAX-3-CUT reveals surprising difficulties that were not apparent for MAX-CUT itself. In particular, efficient approximation algorithms for this problem were developed in succession with those for MAX-CUT, but the sharp hardness has remained an open problem until now.

A random assignment of vertices to parts of the partition yields a 2/3 multiplicative approximation to MAX-3-CUT, so an approximation larger than 2/3 yields a nontrivial algorithm.

In 1997, Frieze and Jerrum [FJ97] found an α_{3} approximation algorithm for MAX-3-CUT by generalizing the semidefinite programming algorithm of [GW95], where

α_{3} := inf_{− \frac{1}{2} ≤ρ≤1} \frac{3}{2} \frac{1 − 3(\frac{1}{9} + \frac{[arccos(−ρ)]^{2}−[arccos(ρ/2)]^{2}}{4π^{2}} )}{1 − ρ}

= \frac{3}{2} \frac{1 − 3(\frac{1}{9} + \frac{[arccos(1/2)]^{2}−[arccos(−1/4)]^{2}}{4π^{2}} )}{1 + 1/2} ≈ .83600811464.

(2)

As with the Goemans-Williamson algorithm for MAX-CUT, this remains the best known polynomial-time approximation algorithm for MAX-3-CUT. And it again becomes desirable to obtain a matching hardness result.

In 1996 [KKLP97] proved that approximating MAX-3-CUT within a multiplicative factor of 101/102 is NP-hard. This was improved to 67/68 in [TSSW00], and further improved to 32/33 in [GS13]. The best known NP-hardness of approximation is now 16/17 from 2014 [AOTW14]. Also [NRT25] obtained a gadget-based reduction with a worse approximation factor of 55/57. As with MAX-CUT, there is a gap between the best known algorithm’s performance and the best known NP-hardness result.

In 2009, [IM12] attempted to generalize the proof of sharp Unique Games hardness [KKMO07] from MAX-CUT to MAX-3-CUT. They succeeded in applying the invariance principle machinery from [MOO10] to MAX-3-CUT. Recall that, in the case of MAX-CUT, the required Majority is Stablest Theorem was shown to be equivalent to the known Borell’s inequality. However, MAX-3-CUT hardness requires the Plurality is Stablest Conjecture, which is equivalent to a continuous but unproven inequality known as the Standard Simplex Conjecture [IM12].

Our first main result, Theorem 1.2 below, proves the Standard Simplex Conjecture of [IM12] for three sets for correlations in [−1/2, 2/5]. We state an informal version here.

Theorem 1.2 (Standard Simplex Conjecture, Informal, Three Sets, −1/2 ≤ ρ ≤ 2/5). Let −1/2 ≤ ρ < 0. The three sets in Euclidean space of dimension n ≥ 2 minimizing noise stability with correlation ρ are (Θ_{i} × ℝ^{n−2})_{i=1}^{3} where (Θ_{i})_{i=1}^{3} ⊆ ℝ^{2} are three disjoint 120 degree sectors centered at the origin. Up to rotations and measure zero changes, these are the only minimizing sets.

If 0 < ρ ≤ 2/5, these three sets maximize noise stability among partitions each of whose sets have Gaussian measure 1/3.

The case ρ = 0 is uninteresting, since the noise stability of a set at correlation zero is just the squared Gaussian measure of the set.

Theorem 1.2 is proven by combining Theorems 7.1 and A.1 below.

Due to the equivalence results of [IM12, Theorem 1.10], a standard simplex conjecture proof implies also a Plurality is Stablest result. For now, we keep the statement somewhat informal. For a more formal statement, see [IM12, Hei23].

Theorem 1.3 (Plurality is Stablest, Informal, Three Candidates, −1/2 ≤ ρ ≤ 2/5). Let −1/2 ≤ ρ < 0. The plurality function has the smallest noise stability with correlation ρ among all low-influence functions f: {1, 2, 3}^{n} → {1, 2, 3}.

Let 0 < ρ ≤ 2/5. The plurality function has the largest noise stability with correlation ρ among all low-influence functions with ℙ(f = i) = 1/3 for all i = 1, 2, 3.

As shown in [IM12], Theorem 1.2 or 1.3 with ρ = −1/2 implies our first main application.

Theorem 1.4 (Sharp Hardness for MAX-3-CUT). Assume the Unique Games Conjecture holds. Then, for any ε > 0, it is NP-hard to approximate MAX-3-CUT within α_{3} + ε.

Theorem 1.4 therefore completes the strategy initiated in 2004 in [KKMO07] for sharp MAX-3-CUT hardness.

Theorem 1.3 can also be applied to the MAX-2-LIN(3) problem, which asks to maximize the number of satisfied linear equations among two-term linear equations in the field of three elements. The positive correlation case of Theorem 1.3 implies a hardness result for MAX-2-LIN(3), due to [KKMO07, Theorem 12]. However, the optimal correlation choice of around ρ ≈ .615 is outside the range of Theorem 1.3, so the hardness result is not optimal. Nevertheless, Theorem 1.5 appears to be the best known hardness result for this problem.

Theorem 1.5 (Hardness for MAX-2-LIN(3)). Assume the Unique Games Conjecture. Then, for every ε > 0, it is NP-hard to distinguish instances I of MAX-2-LIN(3) satisfying OPT(I) ≥ \frac{3}{5} − ε from those satisfying OPT(I) ≤ \frac{1}{3} + \frac{3}{4π^{2}} (arccos(−2/5)^{2} − arccos(1/5)^{2}) + ε. Consequently, assuming the Unique Games Conjecture, it is NP-hard to approximate MAX-2-LIN(3) within a multiplicative factor of

α_{2LIN(3)} + ε.

where α_{2LIN(3)} ≈ 0.815723527338279. The result holds even when every equation has the form x_{i} − x_{j} = c mod 3.

Here the constant appearing in the hardness result is

α_{2LIN(3)} := \frac{5}{9} + \frac{5}{4π^{2}} (arccos(−2/5)^{2} − arccos(1/5)^{2}) .

Note that MAX-3-CUT can also be understood by analogy with MAX-2-LIN(3) as maximizing the number of satisfied expressions of the form x_{i} − x_{j} ≠ 0 mod 3.

Hardness for MAX-3-CUT and MAX-2-LIN(3) is partly motivated by their relation to the Unique Games Conjecture (UGC) itself. Suppose we are given m two-term linear equations in indeterminates x_{1}, …, x_{n} of the form x_{i} − x_{j} = c_{ij} mod p for some prime p > 0. Then UGC says: for any ε > 0, there exists a prime p = p(ε) such that it is NP-hard to decide if at least (1 − ε)m equations are satisfiable, or at most εm equations are satisfiable. (If neither situation occurs, an arbitrary output of the algorithm is allowed.)

1.2. Quantum MAX-CUT. As mentioned above, there is a general theory of hardness of approximation for CSPs, including PCP Theorems, the Unique Games Conjecture, and Raghavendra’s sharp inapproximability result [Rag08]. However, these results do not directly apply to their quantum analogues. The quantum analogue of a constraint satisfaction problem is a local Hamiltonian problem. In this context, there is a conjectured but still unproven form of the PCP Theorem [AAV13], so the hardness of approximation for these problems is less understood. (Despite recent progress such as [BMVZ25], the Quantum PCP Conjecture is still unresolved.) So, it is natural to investigate the inapproximability of a relatively simple version of a local Hamiltonian problem, such as Quantum MAX-CUT.

The Quantum MAX-CUT problem is a special case of the local Hamiltonian problem that in some sense generalizes the usual MAX-CUT problem. The Quantum MAX-CUT problem is QMA-complete [PM17], which is the quantum analogue of NP-complete. As with MAX-CUT, it is natural to ask for approximation algorithms for Quantum MAX-CUT, and to try to prove sharp computational hardness of those algorithms. Such a hardness result would then be evidence towards a quantum version of the PCP theorem. Below, we mainly discuss classical algorithms for Quantum MAX-CUT, i.e. we do not discuss quantum algorithms for Quantum MAX-CUT.

The Quantum MAX-CUT problem was formally described in 2019 [GP19], though it is a natural maximization variant of the anti-ferromagnetic Heisenberg XYZ model, a classic family of QMA-complete [CM16, PM17] 2-local Hamiltonians first investigated nearly a century ago by Heisenberg [Hei28] which models magnetic systems where interacting particles have opposing spins.

The Quantum MAX-CUT problem itself has some efficient approximation algorithms [ALM+25, BBKL26], though there does not appear to be a conjectured optimal algorithm.

For the product state Quantum MAX-CUT problem, a conjecturally optimal efficient algorithm was found in 2014 by [BOV14] with a multiplicative approximation of

α_{BOV} := 0.9563372685 …

Then, [HNP+23] showed a matching NP-hardness result conditional on the Unique Games Conjecture, assuming an unproven S^{k−1}-valued Borell inequality [Bor85] with k = 3.

In this manuscript, we prove the conjecture from [HNP+23] for all correlation parameters in [−.5843, .5843] when k = 3, and all correlations in [−3/5, 3/5] when k > 3. The k = 3 result is then sufficient to deduce sharp hardness of approximation for the algorithm of [BOV14], assuming the Unique Games Conjecture.

Theorem 1.6 (S^{k−1}-Valued Borell Inequality, Informal). Let n ≥ k ≥ 3. If k = 3, fix a correlation −.5843 ≤ ρ < 0. If k > 3, fix a correlation −3/5 ≤ ρ < 0. Then the function f: ℝ^{n} → S^{k−1} with smallest noise stability with correlation ρ is f(x) := (x_{1}, …, x_{k})/\sqrt{x_{1}^{2} + ⋯ + x_{k}^{2}} for all x = (x_{1}, …, x_{n}) ∈ ℝ^{n} where x_{1}^{2} + ⋯ + x_{k}^{2} ≠ 0. (The function f can be defined arbitrarily on the set x_{1}^{2} + ⋯ + x_{k}^{2} = 0.)

For any correlation 0 < ρ ≤ .5843 (or 0 < ρ ≤ 3/5 when k > 3), this function f maximizes noise stability among all mean zero functions (with respect to the Gaussian measure).

Moreover, up to rotations and measure zero changes, this is the only optimizing function.

The case ρ = 0 is uninteresting, since the noise stability of a function at correlation zero is just the squared length of its Gaussian expected value.

As shown in [HNP+23], Theorem 1.6 with k = 3 allows us to conclude sharp hardness for Quantum MAX-CUT.

Theorem 1.7 (Sharp Hardness for Product State Quantum MAX-CUT). Assume the Unique Games Conjecture. Then, for any ε > 0, it is NP-hard to approximate the product state Quantum MAX-CUT problem within a multiplicative factor α_{BOV} + ε.

Define α_{BOV,k} in (6) below. As shown in [HNP+23], Theorem 1.6 with k ≥ 3 allows us to conclude sharp hardness for rank-k MAX-CUT.

Theorem 1.8 (Sharp Hardness for rank-k MAX-CUT). Let k ≥ 3. Assume the Unique Games Conjecture. Then, for any ε > 0, it is NP-hard to approximate the rank-k MAX-CUT problem within a multiplicative factor α_{BOV,k} + ε.

The product state of Quantum MAX-CUT is a special case of Quantum MAX-CUT. More specifically, [HNP+23, Theorem 11.3] shows that Theorem 1.6 implies the same hardness of approximation as in Theorem 1.7 to the Quantum MAX-CUT problem itself.

Corollary 1.9. Assuming the Unique Games Conjecture, for every ε > 0, it is NP-hard to approximate Quantum MAX-CUT within a multiplicative factor α_{BOV} + ε.

Efficient algorithms for Quantum MAX-CUT have approximation guarantees smaller than α_{BOV} at present, so it is unclear if Corollary 1.9 is sharp or not. For example, there is a .614 approximation algorithm in the unweighted case [BBKL26] and a .611 approximation algorithm in the weighted case [ALM+25], which are both quite far from the α_{BOV} ≈ .956 hardness result from Corollary 1.9. Still, Quantum MAX-CUT has an unconditional NPhardness of approximation result [Pid25] for some unspecified constant less than one.

1.3. Discussion of the Proofs. At a high level, the proofs of the main results Theorems 1.4 and 1.7 proceed along the same lines as [Hei25] and [Hei23] by sharpening various estimates, though the details are fairly different. We first summarize the proof of the sphere-valued Borell inequality, Theorem 1.6, which implies Theorem 1.7.

• As in [Hei25], split the noise stability of a function f on ℝ^{n} into two terms, one of which is the (bilinear) average of the average value of f on spheres centered at the origin, and the remaining part. (See Lemma 3.1.)

• Whereas [Hei25] estimates these two terms separately using a sequence of integral estimates, we instead write one single integral estimate as an inequality for an infinitedimensional matrix in the radial Laguerre basis on (0, ∞). (See Proposition 3.5.)

• The final estimate then only requires proving this infinite-dimensional matrix has operator norm less than one. (See Section 4 culminating in Proposition 4.5.)

• Since the matrix entries decay exponentially, this can be done by numerically estimating the operator norm of a finite 20 × 20 matrix with positive entries, together with an elementary analytic decay bound on the remaining (small) infinite matrix.

In other words, the final estimate amounts to bounding the largest eigenvalue of a specific 20 × 20 symmetric matrix (20) with nonnegative entries.

We now summarize the proof of the three set Standard Simplex Problem, Theorem 1.2 which implies Theorem 1.4.

• As in [Hei23], it suffices to consider three subsets of ℝ^{2} by [HT21]. Then write the noise stability of these sets as a (bilinear) average of restrictions to spheres centered at the origin, and a remaining part. (See (55) or [Hei23, Section 2].)

• Whereas [Hei23] splits these spherical noise stabilities into a few separate terms and combines these separate estimates later on, we instead create one estimate for any pair of radii of spheres, and then integrate it over the radial coordinates to obtain a single integral operator. (See (58) and (94) then (105).)

• The final estimate then requires that the eigenvalues of this integral operator be bounded by 2 in absolute value. (See Lemma 9.1 and (133).)

• It further suffices to bound two suitable Hilbert-Schmidt norms of these integral operators by 2. (It is possible to perform operator norm estimates for an infinite matrix in the radial Laguerre basis, but bounding the Hilbert-Schmidt norm is a bit simpler, so we take that approach.)

• After a change of variables to remove a singularity, these Hilbert-Schmidt bounds can be verified numerically, by explicitly upper bounding some bounded continuous integrals on [0, 5]^{2}, combined with an analytic tail bound (since the integrals decay exponentially at infinity) on [0, ∞)^{2} \ [0, 5]^{2}. (See Lemma 9.3.)

The strategy for Theorem 1.2 hides several subtle issues that were found in [HMN16] and [Hei23]. For example, Theorem 1.2 cannot hold when unequal measure restrictions are imposed on the sets. So, the proof of Theorem 1.2 must somehow get around this issue by using some property of the three 120 degree sectors that does not hold for partitions into non-congruent sectors. This is achieved by first performing a rearrangement on circles centered at the origin (as was done already in [Hei23]). The other main technical issue (also circumvented in [Hei23]) is that when you decompose the noise stability into different pieces, those different pieces may no longer have the same optimizers (of three 120 degree sectors). In the present work, this issue is dealt with by integrating in the radial direction and bounding the operator norm of the whole operator, instead of decomposing into pieces and estimating each piece separately.

The need for this new strategy arose since previous approaches to noise stability inequalities (for a single set) did not appear to generalize to the setting of Theorem 1.2. Such strategies included: semigroup monotonicity [Led94]; induction from discrete settings [Bob97]; rearrangement [BS01]; differential inequalities [MN15]; stochastic calculus [Eld15]. Our approach instead uses: (i) calculus of variations (to reduce the ambient dimension [HT21]), (ii) then rearrangement on spheres, (iii) Fourier analytic decompositions, (iv) and finally, reassembled operator norm estimates.

As we can see, the approaches to Theorems 1.2 and 1.6 are related but distinct. The step for averaging over spheres is common to both approaches, though we choose slightly different strategies for bounding the operator norms. The details of the arguments are also fairly different. Theorem 1.2 requires a rearrangement argument on spheres that is not needed in Theorem 1.6. Hence, Theorem 1.6 is in some sense easier than Theorem 1.2. Another difference between Theorems 1.2 and 1.6 is the Fourier analytic formulas, since the latter uses Fourier analysis on S^{k−1} with k ≥ 3 and with exponential measures on (0, ∞), while the former uses Fourier analysis on S^{1}. Lastly, it is easier in Theorem 1.6 to obtain a full range of positive and negative correlation values, while this is a more difficult task in Theorem 1.2 due to a lack of any obvious monotonicity with respect to the correlation parameter.

The sphere averaging idea originated in [HNP+23], although their attempted proof of Theorem 1.6 was erroneous. Weaker versions of Theorems 1.2 and 1.6 appeared in [Hei23] and [Hei25], respectively. The innovation of the present paper is to obtain suitably sharp estimates in order to obtain the appropriate correlation quantity required for the inapproximability results in Theorems 1.4 and 1.7.

1.4. Possible Future Work.

• As mentioned above, our Standard Simplex and Plurality is Stablest results are proven for correlations in [−1/2, 2/5]. Some small improvements beyond these values seem possible, but it seems difficult to make the argument work simultaneously for all correlations in (−1, 1). Perhaps it is an accident that a single argument works this way in the case of a single set in Euclidean space [MOO10]. It is well understood that correlations close to 0 have a more Fourier analytic content, while correlations close to one have more isoperimetric content. Our argument combines Fourier analytic arguments with functional analytic bounds, in contrast to the various other quite different approaches to the single set case.

• The inapproximability result Theorem 1.5 for MAX-2-LIN(3) can be strictly improved by resolving the three candidate Plurality is Stablest Conjecture for all positive correlations. The optimal choice of correlation is around .615, which seems difficult to achieve at present.

• It should be possible to write stronger stability estimates of Theorems 1.2 and 1.6, though for the sake of brevity we did not pursue this approach. A stability estimate says: if you are close to optimizing the functional value, then you are close in the domain to the optimizer.

• The analogue of Theorem 1.2 for four or more sets, and Theorem 1.3 for four or more candidates both remain largely open. Some of the steps in the present paper carry over readily to this setting, but some do not. There are a few significant technical issues that arise in these settings, most notably the lack of rearrangement. The first step of Theorem 1.2 is to rearrange the sets on spheres centered at the origin, which amounts to a one-dimensional rearrangement on S^{1} into three circular arcs. Moreover, it does not matter if these arcs intersect each other or not (and a geodesic ball and a spherical arc are the same on S^{1}, which is good since rearrangement on S^{1} naturally moves toward geodesic balls). For four sets in ℝ^{3}, the analogous step would be a two-dimensional rearrangement of four sets in S^{2} into four spherical triangles. On S^{2}, a geodesic ball is not the same as a spherical triangle, so the most straightforward rearrangement inequalities on S^{2} cannot apply here. There does not appear to be any result in the literature or any general strategy that allows for rearrangement of four disjoint sets on the sphere into four disjoint spherical triangles. This is the main obstruction to progress. [Hei22] provides an alternative strategy to circumvent this issue.

• It should be possible to use our results to construct integrality-gap instances showing that the Frieze–Jerrum semidefinite program for MAX-3-CUT attains its worst-case behavior.

• Theorem 1.7 addresses the product state of Quantum MAX-CUT. There is also a generalization of that problem known as (the product state of) Quantum MAX-k-CUT [CJK+23]. It could be interesting to pursue a sharp hardness result in that more general setting. Theorem 1.7 only required S^{2}-valued functions in Theorem 1.6. An analogue of Theorem 1.7 for Quantum MAX-k-CUT may require S^{k−1}-valued functions, which is one reason we proved Theorem 1.6 for S^{k−1}-valued functions for all k ≥ 3 (besides Theorem 1.8). However, it is not clear exactly what inequality is needed for Quantum MAX-k-CUT (since extra constraints may need to be placed on the function range), or what the “target correlation value” should be (i.e. what is the analogue of ρ_{BOV,k} in (6)).

1.5. GitHub Link. Associated codes for Theorems 1.2 and 1.6 appear at the following

GitHub link: https://github.com/sheilman77/cut_bounds.

2. Part I. Quantum MAX-CUT Preliminaries

Let n ≥ k ≥ 3. Let γ_{n}(x) := (2π)^{−n/2}e^{−∥x∥^{2}/2} for all x ∈ ℝ^{n} with ∥x∥ := (∑_{i=1}^{n} x_{i}^{2})^{1/2} for all x = (x_{1}, …, x_{n}) ∈ ℝ^{n}. For any −1 < ρ < 1 and for any bounded measurable f: ℝ^{n} → ℝ^{k}, let T_{ρ} be the Ornstein–Uhlenbeck operator

T_{ρ}f(x) := ∫_{ℝ^{n}} f(ρx + y\sqrt{1 − ρ^{2}})γ_{n}(y)dy, ∀ x ∈ ℝ^{n}.

For a bounded measurable f: ℝ^{n} → 𝔹^{k}, where 𝔹^{k} = {x ∈ ℝ^{k}: ∥x∥ ≤ 1}, define the noise stability with correlation parameter ρ to be

Stab_{ρ}(f) := ∫_{ℝ^{n}}⟨f(x), T_{ρ}f(x)⟩ γ_{n}(x) dx.

Equivalently, Stab_{ρ}(f) = 𝔼⟨f(X), f(Y)⟩ when X, Y are ρ-correlated standard Gaussians. For any n ≥ k ≥ 3, put

f_{opt,k}(x) := \frac{(x_{1}, …, x_{k})}{(x_{1}^{2} + ⋯ + x_{k}^{2})^{1/2}} , ∀ x = (x_{1}, …, x_{n}) ∈ ℝ^{n} with x_{1}^{2} + ⋯ + x_{k}^{2} ≠ 0.

Its noise stability is expressed using hypergeometric functions as [HNP+23, Theorem 7.15]

F^{∗}(k, ρ) := Stab_{ρ}(f_{opt,k}) = \frac{2}{k} (\frac{Γ((k + 1)/2)}{Γ(k/2)})^{2} ρ · _{2}F_{1}(\frac{1}{2}, \frac{1}{2}; \frac{k}{2} + 1; ρ^{2}) .  (3)

Theorem 1.6 follows from the following two theorems.

Theorem 2.1 (Negative vector-valued Borell inequality). Let n ≥ k ≥ 3, let f: ℝ^{n} → 𝔹^{k} be measurable, and let −0.5843 ≤ ρ < 0 (or −3/5 ≤ ρ < 0 if k > 3). Then

Stab_{ρ}(f) ≥ F^{∗}(k, ρ).  (4)

Theorem 2.2 (Positive vector-valued Borell inequality). Let n ≥ k ≥ 3, let f: ℝ^{n} → 𝔹^{k} be measurable with ∫_{ℝ^{n}} f dγ_{n} = 0. Let 0 < η ≤ 0.5843 (or 0 < η ≤ 3/5 if k > 3). Then

Stab_{η}(f) ≤ F^{∗}(k, η).  (5)

Let ρ_{BOV,k} be the value of ρ achieving the infimum below. That is

α_{BOV,k} := inf_{−1<ρ<0} \frac{1 − F^{∗}(k, ρ)}{1 − ρ} = \frac{1 − F^{∗}(k, ρ_{BOV,k})}{1 − ρ_{BOV,k}}.  (6)

As shown in [BOV14, HNP+23], when k = 3, we have ρ_{BOV,3} = −0.5842676623 … and α_{BOV,3} = 0.9563372685 . . .. Theorem 2.1 together with [HNP+23, Theorem 11.3] proves Theorem 1.7 since

−.5843 < ρ_{BOV,3} < 0.  (7)

2.1. Quantum MAX-CUT. Below we describe the Quantum MAX-CUT problem by analogy with MAX-CUT. When M is a 2 × 2 matrix and j is a positive integer, we denote

M^{⊗j} := \underbrace{M ⊗ ⋯ ⊗ M}_{j times} .

If n is a positive integer and 1 ≤ j ≤ n, denote

Z_{j} := I_{2}^{⊗(j−1)} ⊗ (\begin{matrix}1 & 0 \\ 0 & −1 \end{matrix}) ⊗ I_{2}^{⊗(n−j)},  ∀ 1 ≤ j ≤ n,  I_{2} := (\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}) .

The (weighted) MAX-CUT problem can be stated as: given w: {1, …, n}^{2} → [0, ∞) satisfying w_{ij} = w_{ji} and w_{ii} = 0 for all 1 ≤ i, j ≤ n, compute the following quantity [GP19, HNP+23]

max_{u∈(ℂ^{2})^{⊗n}: ∥u∥≤1} u^{∗}( ∑_{i,j=1}^{n} w_{ij}(I_{2}^{⊗n} − Z_{i}Z_{j}))u.

Define now

X_{j} := I_{2}^{⊗(j−1)} ⊗ (\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix}) ⊗ I_{2}^{⊗(n−j)}, ∀ 1 ≤ j ≤ n,

Y_{j} := I_{2}^{⊗(j−1)} ⊗ (\begin{matrix}0 & −\sqrt{−1} \\ \sqrt{−1} & 0 \end{matrix}) ⊗ I_{2}^{⊗(n−j)}, ∀ 1 ≤ j ≤ n.

The Quantum MAX-CUT problem is [GP19, HNP+23]: given w: {1, …, n}^{2} → [0, ∞) satisfying w_{ij} = w_{ji} and w_{ii} = 0 for all 1 ≤ i, j ≤ n, compute the following quantity

max_{u∈(ℂ^{2})^{⊗n}: ∥u∥≤1} u^{∗}( ∑_{i,j=1}^{n} w_{ij}(I_{2}^{⊗n} − X_{i}X_{j} − Y_{i}Y_{j} − Z_{i}Z_{j}))u.

The product state of Quantum MAX-CUT is the more restricted optimization problem of computing

max_{\begin{matrix}u=u_{1}⊗···⊗u_{n}: \\ u_{i}∈ℂ^{2}, ∥u_{i}∥≤1, ∀ 1≤i≤n \end{matrix}} u^{∗}( ∑_{i,j=1}^{n} w_{ij}(I_{2}^{⊗n} − X_{i}X_{j} − Y_{i}Y_{j} − Z_{i}Z_{j}))u.

3. The weighted radial reduction

Fix 0 < η < 1. Following the shell decomposition in [Hei25], we first prove the centered positive inequality in dimension k. Let X, Y ∈ ℝ^{k} be η-correlated standard Gaussians and write R = ∥X∥, S = ∥Y ∥, U = X/R, and V = Y/S, away from null sets. Let I_{m} denote the modified Bessel function (59). Conditional on R = r and S = s, the angular noise operator on S^{k−1} has first nonconstant eigenvalue [Hei25, Eq. 17] [HNP+23, Corollary 4.9]

λ_{η,k}^{r,s} = \frac{I_{k/2}(z)}{I_{k/2−1}(z)},  z = \frac{ηrs}{1 − η^{2}} .  (8)

For any bounded measurable f: ℝ^{n} → 𝔹^{k}, let m: (0, ∞) → 𝔹^{k} be defined by

m(r) = m_{f}(r) := ∫_{S^{n−1}} f(rθ) dσ(θ),  ∀ 0 < r < ∞,  (9)

where σ is normalized surface measure on S^{n−1} (so that σ(S^{n−1}) = 1). (Note that m(r) is well-defined for a.e. r ∈ (0, ∞) by Fubini’s Theorem.)

Lemma 3.1 (Ball-valued shell estimate). For every measurable f: ℝ^{k} → 𝔹^{k},

Stab_{η}(f) − F^{∗}(k, η) ≤ 𝔼⟨m(R), m(S)⟩ − 𝔼[λ_{η,k}^{R,S}∥m(R)∥^{2}] .  (10)

Proof. This follows from [Hei25, Eq. 5] and (the proof of) [Hei25, Lemma 2.2], the only change being that q(r) := ∫_{S^{k−1}} ∥f(rθ)∥^{2} dσ(θ) − ∥m(r)∥^{2} ≤ 1 − ∥m(r)∥^{2} in [Hei25, Lemma 2.1]. □

Let G ∈ ℝ^{k} be a standard Gaussian random vector. Let s > 0. Define

m_{k} := 𝔼∥G∥ = \sqrt{2} \frac{Γ((k + 1)/2)}{Γ(k/2)},  (11)
δ = δ_{η}(s) := \frac{ηs}{\sqrt{1 − η^{2}}} ,  Y_{η,k}(s) := \frac{m_{k}δ}{k} · _{1}F_{1}(\frac{1}{2}; \frac{k}{2} + 1; −\frac{δ^{2}}{2} ) .  (12)

Lemma 3.2 (Exact conditional angular weight). For every s > 0,

𝔼[λ_{η,k}^{R,S} | S = s] = Y_{η,k}(s).  (13)

Consequently,

𝔼[λ_{η,k}^{R,S}∥m(R)∥^{2}] = 𝔼[Y_{η,k}(R)∥m(R)∥^{2}] .  (14)

Proof. Denote e_{1} = (1, 0, …, 0) ∈ ℝ^{k}. Since (X, Y) is rotation invariant, 𝔼[λ_{η,k}^{R,S} | S = s] = 𝔼[λ_{η,k}^{R,S} | Y = se_{1}]. Conditional on Y = se_{1}, X is equal in distribution to ηse_{1} + \sqrt{1 − η^{2}}G = \sqrt{1 − η^{2}}(δe_{1} + G) by (12). Conditional on R = r, U = X/∥X∥ then has the von Mises-Fisher distribution with known expected value 𝔼[U | R = r, Y = se_{1}] = λ_{η,k}^{r,s}e_{1}. Consequently, 𝔼[U_{1} | R = r, Y = se_{1}] = λ_{η,k}^{r,s}. Taking the conditional expectation over R,

𝔼[λ_{η,k}^{R,S} | S = s] = 𝔼[λ_{η,k}^{R,s} | Y = se_{1}] = 𝔼[U_{1} | Y = se_{1}] = 𝔼\frac{δ + G_{1}}{∥δe_{1} + G∥}.

We compute this quantity as M′_{k}(δ) where M_{k}(δ) := 𝔼∥δe_{1} + G∥. The expected value of the noncentral chi distribution has a known formula M_{k}(δ) = m_{k} · _{1}F_{1}(−\frac{1}{2}; \frac{k}{2}; −\frac{δ^{2}}{2} ) in terms of the confluent hypergeometric function. Then using a known differentiation formula, \frac{d}{dz}_{1}F_{1}(a; b; z) = (a/b)_{1}F_{1}(a + 1; b + 1; z), we get

𝔼[λ_{η,k}^{R,S} | S = s] = M′_{k}(δ) = m_{k}(−δ)(−1/k)· _{1}F_{1}(\frac{1}{2}; \frac{k}{2} + 1; −\frac{δ^{2}}{2} ) =^{(12)} Y_{η,k}(s).

That is, (13) holds. Equation (14) follows from exchangeability. □

The next bound is the only estimate applied to the exact weight.

Lemma 3.3 (Reciprocal bound). Let k ≥ 3, s > 0. Let δ = δ_{η}(s) from (12). Then

\frac{1}{Y_{η,k}(s)} ≤ \sqrt{1 + (\frac{k}{m_{k}δ} )^{2}} ≤ 1 + \frac{k}{m_{k}δ} .  (15)

Proof. Let B have distribution Beta(1/2, (k + 1)/2). Kummer’s integral formula gives

1F_{1}(\frac{1}{2}; \frac{k}{2} + 1; −\frac{δ^{2}}{2} ) = 𝔼e^{−δ^{2}B/2}.  (16)

Let H have the gamma distribution with shape α = 1/2 and scale θ_{k} = 2 (\frac{m_{k}}{k} )^{2} . The leading constants at zero in the densities of B and H agree. Indeed, by (11), θ_{k}^{−1/2} = \frac{Γ(k/2+1)}{Γ((k+1)/2)}. On 0 < t < 1, the density ratio is

\frac{f_{B}(t)}{f_{H}(t)} = (1 − t)^{(k−1)/2}e^{t/ϑ_{k}}.

Its logarithmic derivative,

\frac{1}{θ_{k}} − \frac{k − 1}{2(1 − t)},

is strictly decreasing, is positive at zero, and tends to −∞ as t ↑ 1. Positivity at zero follows from m_{k}^{2} < k, by (11) and Jensen’s inequality, so θ_{k} < 2/k, i.e. 1/θ_{k} > k/2. Thus the two densities have one crossing at some 0 < t_{0} < 1: f_{B}(t) ≥ f_{H}(t) for 0 < t < t_{0} and f_{B}(t) ≤ f_{H}(t) for t_{0} < t < 1, and hence B is stochastically dominated by H. So, using this property and the known formula for the moment generating function of H,

1F_{1}(\frac{1}{2}; \frac{k}{2} + 1; −\frac{δ^{2}}{2} ) =^{(16)} 𝔼e^{−δ^{2}B/2} ≥ 𝔼e^{−δ^{2}H/2} = (1 + \frac{m_{k}^{2}δ^{2}}{k^{2}} )^{−1/2} , ∀ δ > 0.

Multiplying by m_{k}δ/k and using (12) proves the first inequality. The second is \sqrt{1 + x^{2}} ≤ 1 + x valid for any x ≥ 0. □

We now isolate the radial quadratic form. The random variable R^{2}/2 has law

dν_{k}(t) := \frac{t^{(k/2)−1}e^{−t}}{Γ(k/2)} dt.  (17)

Let

ℓ_{j}^{(k)}(t) := (\frac{j!Γ(k/2)}{Γ(k/2 + j)})^{1/2} L_{j}^{(k/2)−1}(t),  j ≥ 0,  (18)

where L_{j}^{(α)}(t) := \frac{t^{−α}e^{t}}{j!} \frac{d^{j}}{dt^{j}} (e^{−t}t^{j+α}), ∀ t ∈ ℝ. Then (ℓ_{j}^{(k)})_{j≥0} is an orthonormal basis of L^{2}(ν_{k}). The radial Ornstein–Uhlenbeck operator satisfies

T_{η}ℓ_{j}^{(k)}(∥x∥^{2}/2) = η^{2j}ℓ_{j}^{(k)}(∥x∥^{2}/2),  (19)

since for a smooth function h: ℝ → ℝ with t := ∥x∥^{2}/2, we have Δh(t) − ⟨x, ∇h(t)⟩ = 2[h′′(t)t + (k/2 − t)h′(t)], and the generalized Laguerre polynomials with parameter α = k/2 − 1 satisfy tℓ′′_{j} + (α + 1 − t)ℓ′_{j} + jℓ_{j} = 0, so (Δ − ⟨x, ∇⟩)ℓ_{j}(t) = −2jℓ_{j}(t), hence (19) follows. Finally, the orthonormality with respect to dν_{k}(t) follows from known orthogonality and the identity ∫_{0}^{∞} t^{α}e^{−t}(L_{j}^{(α)}(t))^{2} dt = Γ(j + α + 1)/j!.

Define the positive semidefinite matrix A_{η}^{(k)} = ((A_{η}^{(k)})_{ij})_{i,j≥1} by

(A_{η}^{(k)})_{ij} = η^{i+j} ∫_{0}^{∞} \frac{ℓ_{i}^{(k)}(t)ℓ_{j}^{(k)}(t)}{Y_{η,k}(\sqrt{2t})} dν_{k}(t).  (20)

Here ∥A_{η}^{(k)}∥ denotes the supremum of the operator norms of its finite principal sections; Proposition 4.1 below shows that this quantity is finite.

Lemma 3.4 (Weighted radial analysis). For every measurable m: (0, ∞) → ℝ^{k} for which the right-hand side is finite,

∑_{j≥1} η^{2j} ∥∫_{0}^{∞} m(\sqrt{2t})ℓ_{j}^{(k)}(t) dν_{k}(t)∥^{2} ≤ ∥A_{η}^{(k)}∥ ∫_{0}^{∞} Y_{η,k}(\sqrt{2t})∥m(\sqrt{2t})∥^{2} dν_{k}(t).  (21)

Proof. It suffices to consider scalar m. For every finitely supported sequence c = (c_{j})_{j≥1},

Cauchy–Schwarz together with dividing and multiplying by \sqrt{Y_{η,k}(\sqrt{2t})} gives

|∑_{j≥1} c_{j}η^{j} ∫_{0}^{∞} m(\sqrt{2t})ℓ_{j}^{(k)}(t) dν_{k}(t)|^{2} = |∫_{0}^{∞} m(\sqrt{2t}) ∑_{j≥1} c_{j}η^{j}ℓ_{j}^{(k)}(t) dν_{k}(t)|^{2}

≤ ∫_{0}^{∞} |m(\sqrt{2t})|^{2}Y_{η,k}(\sqrt{2t}) dν_{k}(t) · ∫_{0}^{∞} \frac{( ∑_{j≥1} c_{j}η^{j}ℓ_{j}(t))^{2}}{Y_{η,k}(\sqrt{2t})} dν_{k}(t)

=^{(20)} (∫_{0}^{∞} Y_{η,k}(\sqrt{2t})|m(\sqrt{2t})|^{2} dν_{k}(t)) ∑_{i,j≥1} c_{i}c_{j}(A_{η}^{(k)})_{ij}

≤ ∥A_{η}^{(k)}∥∥c∥_{ℓ_{2}}^{2} ∫_{0}^{∞} Y_{η,k}(\sqrt{2t})|m(\sqrt{2t})|^{2} dν_{k}(t).

Taking the supremum over ∥c∥_{ℓ^{2}} = 1 proves the scalar case of (21). Applying it componentwise proves the vector-valued case. □

Proposition 3.5 (Radial criterion). If ∥A_{η}^{(k)}∥ < 1, then (5) holds for every mean-zero measurable map f: ℝ^{n} → 𝔹^{k} and every n ≥ k ≥ 3.

Proof. First let n = k and let m be the spherical mean of f. Since ∫_{ℝ^{k}} f dγ_{k} = 0, the constant Laguerre coefficient of m vanishes. Define m = m_{f} from (9). For any j ≥ 1, write

m̂_{j} := ∫_{0}^{∞} m(\sqrt{2t})ℓ_{j}^{(k)}(t) dν_{k}(t).

Recall that the modified Laguerre polynomials (ℓ_{j}^{(k)}(t))_{j≥0} with t = ∥x∥^{2}/2 form a complete orthonormal basis of radial functions on ℝ^{k}, since e.g. any rotation invariant polynomial of x is a polynomial in t. So, (19) together with m̂_{0} = 0 give

𝔼⟨m(R), m(S)⟩ = ∑_{j≥1} η^{2j}∥m̂_{j}∥^{2}.

Combine Lemmas 3.1, 3.2 and 3.4 with the assumption ∥A_{η}∥ < 1 to obtain

Stab_{η}(f) − F^{∗}(k, η) ≤ (∥A_{η}∥ − 1)𝔼[Y_{η,k}(R)∥m(R)∥^{2}] ≤ 0.  (22)

For n > k, [HNP+23, Theorem 6.1] says that the maximum among mean-zero maps ℝ^{n} → 𝔹^{k} is attained and that every maximizer depends, after an orthogonal change of coordinates, on at most k coordinates. The k-dimensional result therefore proves the claim in every dimension n > k. □

4. A uniform spectral certificate

We now prove ∥A_{η}^{(k)}∥ < 1 uniformly through η = 0.5843 when k = 3 (and through η = 3/5 with k > 3). Instead of bounding ∥A_{η}^{(k)}∥ directly, we bound the operator norm of a slightly larger operator V_{η}^{(k)} whose entries have more explicit (hence more tractable) formulas.

Lemma 3.3 with (11) and (12) give

\frac{1}{Y_{η,k}(\sqrt{2t})} ≤ 1 + β_{η,k}t^{−1/2}, ∀ t > 0,  β_{η,k} := \frac{k\sqrt{1 − η^{2}}}{2η} \frac{Γ(k/2)}{Γ((k + 1)/2)}.  (23)

Define

V_{η}^{(k)} := T_{η}^{1/2}M_{1+β_{η,k}t^{−1/2}}T_{η}^{1/2}.  (24)

By (23) and (12), we have the operator inequality M_{1/Y_{η,k}(\sqrt{2t})} ≤ M_{1+β_{η,k}t^{−1/2}}. From this

we will conclude the operator inequality A_{η}^{(k)} ⪯ V_{η}^{(k)} on the nonconstant radial subspace. Here M_{w} denotes multiplication by w. Indeed, for any i, j ≥ 1,

⟨ℓ_{i}, T_{η}^{1/2}M_{\frac{1}{Y_{η,k}(\sqrt{2t})}} T_{η}^{1/2}ℓ_{j}⟩ = ⟨T_{η}^{1/2}ℓ_{i}, M_{\frac{1}{Y_{η,k}(\sqrt{2t})}} T_{η}^{1/2}ℓ_{j}⟩ = ∫_{0}^{∞} η^{i+j} \frac{ℓ_{i}(t)ℓ_{j}(t)}{Y_{η,k}(\sqrt{2t})} dν_{k}(t) =^{(20)} (A_{η})_{ij}.

So, if f = ∑_{j≥1} c_{j}ℓ_{j}(t), then

⟨f, (V_{η}^{(k)} − A_{η}^{(k)})f⟩ = ∫_{0}^{∞} (1 + β_{η,k}t^{−1/2} − \frac{1}{Y_{η,k}(\sqrt{2t})})| ∑_{j≥1} η^{j}c_{j}ℓ_{j}(t)|^{2} dν_{k}(t) ≥^{(23)∧(12)} 0. (25)

We next record the matrix of V_{η}^{(k)}. Let (z)_{0} := 1, (z)_{j} := z(z + 1) ⋯ (z + j − 1) for any integer j ≥ 1. Let

s_{j}^{(k)} := (\frac{j!Γ(k/2)}{Γ(k/2 + j)})^{1/2} ,  c_{j} := \frac{(1/2)_{j}}{j!} ,  d_{j}^{(k)} := \frac{((k − 1)/2)_{j}}{j!} .  (26)

The Laguerre connection formula [Olv10, Eq. 18.18.18],

L_{j}^{(k/2−1)}(t) = ∑_{m=0}^{j} c_{j−m}L_{m}^{((k−3)/2)}(t),

and orthogonality of L_{j}^{((k−3)/2)} with respect to t^{(k−3)/2}e^{−t} dt on (0, ∞) give

∫_{0}^{∞} \frac{ℓ_{i}(t)ℓ_{j}(t)}{\sqrt{t}} dν_{k}(t) =^{(17)} \frac{1}{Γ(k/2)} ∫_{0}^{∞}s_{i}^{(k)}s_{j}^{(k)} ∑_{m=0}^{i} ∑_{m′=0}^{j} c_{i−m}L_{m}^{( \frac{k−3}{2} )}(t)c_{j−m′}L_{m′}^{( \frac{k−3}{2} )}(t)t^{(k−3)/2}e^{−t} dt

= \frac{1}{Γ(k/2)}s_{i}^{(k)}s_{j}^{(k)} ∑_{m=0}^{min(i,j)} c_{i−m}c_{j−m} \frac{Γ(m + (k − 1)/2)}{m!}.

\begin{aligned}(V_{η}^{(k)})_{ij} & = ⟨ℓ_{i}, T_{η}^{1/2}M_{1+β_{η,k}t^{−1/2}}T_{η}^{1/2}ℓ_{j}⟩ = ⟨T_{η}^{1/2}ℓ_{i}, M_{1+β_{η,k}t^{−1/2}}T_{η}^{1/2}ℓ_{j}⟩ \\ & =^{(23)} η^{2i}δ_{ij} + \frac{k}{k − 1}\sqrt{1 − η^{2}} η^{i+j−1}s_{i}^{(k)}s_{j}^{(k)} · ∑_{m=0}^{min(i,j)} c_{i−m}c_{j−m}d_{m}^{(k)},  ∀ i, j ≥ 0. \end{aligned} (27)

Proposition 4.1 (Certified radial bound, k = 3). For every 0 < η ≤ 0.5843, on the subspace span(1)^{⊥} perpendicular to constant functions, we have the operator norm bounds

∥A_{η}^{(3)} |_{span(1)^{⊥}}∥ ≤ ∥V_{η}^{(3)} |_{span(1)^{⊥}}∥ < 0.987 < 1.  (28)

Proof. Set η_{0} := 0.5843. Every entry of (27) is nonnegative. Moreover, η^{2i} and η^{i+j−1}\sqrt{1 − η^{2}} are increasing for 0 < η ≤ η_{0} < 1/\sqrt{2}: indeed, if p = i + j − 1 ≥ 1, then η^{p}\sqrt{1 − η^{2}} is increasing for η < \sqrt{p/(p + 1)}. The norm of a nonnegative self-adjoint matrix can be tested on nonnegative vectors. It is therefore enough to upper bound ∥V_{η_{0}}^{(3)}∥.

Let V_{1:20} be the leading 20×20 block of V_{η_{0}}^{(3)}. We will explicitly describe an approximation v ∈ ℝ^{20} to the largest eigenvector of V_{1:20}. For the positive vector v, normalized by v_{1} = 1, the following terminating decimals describing v are interpreted as exact rational numbers:

\begin{matrix}1.000000000000, & 0.256858556823, & 0.097396033098, & 0.043379992735, & 0.020897660126, \\ 0.010513466380, & 0.005433117499, & 0.002859305346, & 0.001524852414, & 0.000821489732, \\ 0.000446145076, & 0.000243896114, & 0.000134063610, & 0.000074033654, & 0.000041046277, \\ 0.000022835796, & 0.000012742970, & 0.000007129915, & 0.000003998799, & 0.000002247496, \end{matrix}

Directed rational interval arithmetic then gives the following upper bounds on the vector (V_{1:20}v)_{i}/v_{i} where i = 1, …, 20:

\begin{matrix}0.986730842649 & 0.986730842648 & 0.986730842645 & 0.986730842643 & 0.986730842659 \\ 0.986730842616 & 0.986730842679 & 0.986730842649 & 0.986730842823 & 0.986730842081 \\ 0.986730842495 & 0.986730841950 & 0.986730841227 & 0.986730846599 & 0.986730840460 \\ 0.986730830803 & 0.986730849170 & 0.986730809040 & 0.986730872693 & 0.986730716257 \end{matrix}

Each displayed entry is rounded upward. To make the check exact, note that s_{j}^{2} and c_{j} are rational numbers by (26). Thus, at η_{0} = 5843/10000, every entry of V_{1:20} is algebraic with only square roots of rational numbers. Enclosing every square root between consecutive rationals with denominator 10^{60} and carrying out the remaining operations over ℚ gives the table. In particular,

max_{1≤i≤20} \frac{(V_{1:20}v)_{i}}{v_{i}} < 0.986731.  (29)

The accompanying file certify_quantum_cut.py reproduces these bounds by exact rational arithmetic using only the Python standard library. The Collatz–Wielandt upper bound applied to (29) then gives

∥V_{1:20}∥ < 0.986731.  (30)

It remains to control the infinite tail of V_{η_{0}}^{(3)}. Since s_{j} ≤ 1 and 0 < c_{j} ≤ 1, the diagonal terms satisfy, with q = η_{0}^{2} and κ = 3\sqrt{1 − η_{0}^{2}}/(2η_{0}),

(V_{η_{0}}^{(3)})_{jj} ≤ q^{j}(1 + κ(j + 1)), ∀ j ≥ 1.

Therefore the trace of the principal block indexed by j ≥ 21 is at most

\frac{q^{21}}{1 − q} + κ\frac{q^{21}(22 − 21q)}{(1 − q)^{2}} < 1.150 × 10^{−8} =: τ.  (31)

Recall that the proof of (25) shows that V_{η_{0}}^{(3)} is symmetric positive semidefinite. So, we finally combine (30) and (31) with Lemma 4.2 to get

∥V_{η_{0}}^{(3)}∥ < .986731 + τ < 0.986732 < 0.987.

This proves (28) for all 0 < η ≤ η_{0}. □

Lemma 4.2 (Positive block tail bound). Let M = ( \begin{matrix}B & E \\ E^{∗} & C \end{matrix}) be a real symmetric positive semidefinite (finite or infinite) matrix with ∥B∥ ≤ λ and tr C ≤ τ. Then

∥M∥ ≤ λ + τ.  (32)

Proof. Positive semidefiniteness with r := −⟨x, Ey⟩/⟨y, Cy⟩ gives

0 ≤ \binom{x}{ry} (\begin{matrix}B & E \\ E^{∗} & C \end{matrix}) \binom{x}{ry} = ⟨x, Bx⟩ + 2r⟨x, Ey⟩ + r^{2}⟨y, Cy⟩ = ⟨x, Bx⟩ − ⟨x, Ey⟩^{2}/⟨y, Cy⟩.

That is, |⟨x, Ey⟩|^{2} ≤ ⟨x, Bx⟩⟨y, Cy⟩. (If it occurs that ⟨y, Cy⟩ = 0, then choosing r → ±∞ shows that ⟨x, Ey⟩ = 0 as well.) Then if ∥\binom{x}{y}∥ = 1, using ∥C∥ ≤ trC ≤ τ, we get

\binom{x}{y} (\begin{matrix}B & E \\ E^{∗} & C \end{matrix}) \binom{x}{y} ≤ λ∥x∥^{2}+2\sqrt{λτ}∥x∥∥y∥+τ∥y∥^{2} = (\sqrt{λ}∥x∥+\sqrt{τ}∥y∥)^{2} ≤ (λ+τ)∥\binom{x}{y}∥^{2}.

Since ∥\binom{x}{y}∥ = 1, this concludes the bound. □

We now treat the case k > 3 by certifying two dimension-four operators. We define the following slight modification of (24).

Z_{η} := η^{2} · T_{η}^{1/2}M_{1+ \frac{15}{16} β_{η,4}t^{−1/2}}T_{η}^{1/2}.  (33)

Proposition 4.3 (k = 4 Bounds). For 0 < η ≤ 3/5, on the subspace perpendicular to constant functions, we have the operator norm bounds

∥V_{η}^{(4)} |_{span(1)^{⊥}}∥ < 0.962,  ∥Z_{η}∥ < 0.989.  (34)

Proof. All entries of both matrices are nonnegative and increasing for 0 < η ≤ 3/5 < 1/\sqrt{2}. It suffices to take η = η_{0} = 3/5. At k = 4, by (26) we have

s_{j}^{(4)} = \frac{1}{\sqrt{j + 1}},  d_{j}^{(4)} = \frac{(3/2)_{j}}{j!} .  (35)

Consequently, for any i, j ≥ 1, using k\sqrt{1 − η^{2}}/(k − 1) = 16/15,

(V_{3/5}^{(4)})_{ij} =^{(27)} (3/5)^{2i}δ_{ij} + \frac{16}{15} \frac{(3/5)^{i+j−1}}{\sqrt{(i + 1)(j + 1)}} · ∑_{m=0}^{min(i,j)} c_{i−m}c_{j−m}d_{m}^{(4)},  (36)

whereas, for i, j ≥ 0,

(Z_{3/5})_{ij} =^{(33)} (3/5)^{2i+2}δ_{ij} + \frac{(3/5)^{i+j+1}}{\sqrt{(i + 1)(j + 1)}} · ∑_{m=0}^{min(i,j)} c_{i−m}c_{j−m}d_{m}^{(4)}.  (37)

Let V_{1:20} be the leading 20 × 20 block of V_{3/5}^{(4)} and let Z_{0:20} be the leading 21 × 21 block of Z_{3/5}. As in Proposition 4.1, we will explicitly describe approximations to the largest eigenvectors of V_{1:20} and Z_{0:20}, respectively. For V_{1:20}, we use the vector

\begin{matrix}1.000000000000, & 0.235502283787, & 0.084412886242, & 0.036251000101, & 0.017062434237, \\ 0.008462067457, & 0.004337666976, & 0.002274532283, & 0.001212712406, & 0.000654921483, \\ 0.000357321574, & 0.000196590782, & 0.000108918778, & 0.000060704275, & 0.000034005732, \\ 0.000019134287, & 0.000010808471, & 0.000006126515, & 0.000003483353, & 0.000001985998. \end{matrix}

As in Proposition 4.1, for the above vector v ∈ ℝ^{20}, we computationally upper bound max_{i=1,...,20}(V_{1:20}v)_{i}/v_{i} and obtain an upper bound of .961 in this case. Similarly, for Z_{0:20}, we use the vector

1.000000000000, 0.195759686570, 0.064856944384, 0.026690658790, 0.012232805093,
0.005957417255, 0.003013602699, 0.001564396228, 0.000827507987, 0.000444045497,
0.000240996163, 0.000132006969, 0.000072862879, 0.000040478067, 0.000022611648,
0.000012691740, 0.000007153611, 0.000004046971, 0.000002296977, 0.000001307540,

0.000000746272.

The entries of (36) and (37) involve only rational numbers and square roots of integers. Enclosing each square root by rationals and using the Collatz-Wielandt upper bound,

∥V_{1:20}∥ < 0.961,  ∥Z_{0:20}∥ < 0.98865.  (38)

The largest directed upper bounds for the row ratios are 0.960805417209 and 0.988644133222, respectively. The bound (38) is verified by certify_rank_k_cut.py.

We now control the tails of the matrices. Since c_{m} ≤ 1 by (26) and d_{m}^{(4)} ≤ 2m + 1 by (35)

∑_{m=0}^{j} c_{j−m}^{2}d_{m}^{(4)} ≤ (j + 1)^{2}.

With q := η_{0}^{2} = (3/5)^{2}, the respective tail traces, beginning at j = 21, are at most

τ_{V} := \frac{q^{21}}{1 − q} + \frac{16}{9} \frac{q^{21}(22 − 21q)}{(1 − q)^{2}} < 3.0913 × 10^{−8},  (39)
τ_{Z} := q \frac{q^{21}}{1 − q} + (3/5)\frac{q^{21}(22 − 21q)}{(1 − q)^{2}} < 1.0450 × 10^{−8}.

Combining (38), (39), and Lemma 4.2 gives the two inequalities in (34). □

It remains to show why dimension k = 4 controls every larger target dimension k > 4.

Proposition 4.4 (Dimension-four reduction). For any k ≥ 5 and 0 < η ≤ 3/5,

∥V_{η}^{(k)} |_{span(1)^{⊥}}∥ ≤ max (∥V_{η}^{(4)} |_{span(1)^{⊥}}∥, ∥Z_{η}∥).  (40)

Proof. As above, we identify the set of radial functions from ℝ^{k} → [−1, 1] as functions from (0, ∞) → [−1, 1] via the identification t = ∥x∥^{2}/2, x ∈ ℝ^{k}. Let A and C be independent gamma random variables with shape parameters α equal to 2 and (k − 4)/2, respectively, and scale θ = 1. Then A has law ν_{4}, C has law ν_{k−4}, and A + C has law ν_{k} by (17), so

J: L_{2}(ν_{k}) ⟶ L_{2}(ν_{4}) ⊗ L_{2}(ν_{k−4}),  (Jf)(a, c) := f(a + c),  ∀ a, c > 0,

is an isometry. The Ornstein-Uhlenbeck semigroup commutes with J:

JT_{η} = ((T_{η}|_{L_{2}(ν_{4})}) ⊗ (T_{η}|_{L_{2}(ν_{k−4})}))J.  (41)

This follows from (19) Laguerre’s addition formula L_{n}^{(k/2−1)}(a + c) = ∑_{j=0}^{n} L_{j}^{(1)}(a)L_{n−j}^{(k/2−3)}(c), rewritten as

Jℓ_{n}^{(k)} =^{(18)} ∑_{j=0}^{n} \frac{s_{n}^{(k)}}{s_{j}^{(4)}s_{n−j}^{(k−4)}} · ℓ_{j}^{(4)}ℓ_{n−j}^{(k−4)}.

Conditioning on A + C reveals that the adjoint J^{∗} is conditional expectation:

J^{∗}(g)(x) = 𝔼[g(A, C) | A + C = x],  ∀ x > 0.  (42)

Conditional on A + C = x, the ratio A/x has the Beta(2, (k − 4)/2) distribution. Hence

𝔼[A^{−1/2} | A + C = x] = x^{−1/2} \frac{Γ(3/2)Γ(k/2)}{Γ(2)Γ((k − 1)/2)}.  (43)

Consequently

J^{∗}(M_{a^{−1/2}}|_{L_{2}(ν_{4})} ⊗ I)J = \frac{Γ(3/2)Γ(k/2)}{Γ(2)Γ((k − 1)/2)}M_{x^{−1/2}}.  (44)

Using (41) and (44) we obtain

B_{η,k} := β_{η,k}T_{η}^{1/2}M_{x^{−1/2}}T_{η}^{1/2} = r_{k}J^{∗}[B_{η,4} ⊗ T_{η}|_{L_{2}(ν_{k−4})}] J,  (45)

r_{k} := \frac{β_{η,k}}{β_{η,4}} \frac{Γ(2)Γ((k − 1)/2)}{Γ(3/2)Γ(k/2)} =^{(23)} \frac{k}{4} \frac{Γ(5/2)}{Γ(3/2)} \frac{Γ((k − 1)/2)}{Γ((k + 1)/2)} = \frac{3}{4} \frac{k}{k − 1} ≤^{(k≥5)} \frac{15}{16},

V_{η}^{(k)} =^{(45)∧(24)} J^{∗}[(T_{η}|_{L_{2}(ν_{4})} + r_{k}B_{η,4}) ⊗ T_{η}|_{L_{2}(ν_{k−4})}] J.  (46)

Let f ∈ L_{2}(ν_{k}) with ν_{k} mean zero. For any j ≥ 0, let f_{j} ∈ L_{2}(ν_{4}) be defined by Jf = ∑_{j=0}^{∞} f_{j} ⊗ ℓ_{j}^{(k−4)}. Then using J(1) = 1 ⊗ 1 and that J is an isometry,

⟨f_{0}, 1⟩_{ν_{4}} = ⟨f_{0} ⊗ ℓ_{0}^{(k−4)}, 1 ⊗ 1⟩_{ν_{4}⊗ν_{k−4}} = ⟨Jf, 1 ⊗ 1⟩_{ν_{4}⊗ν_{k−4}} = ⟨J^{∗}Jf, 1⟩_{ν_{k}} = ⟨f, 1⟩_{ν_{k}} = 0, (47)

since f has mean zero. Also, applying T_{η} to the ℓ_{j}^{(k−4)} terms, we get

⟨f, V_{η}^{(k)}f⟩ =^{(46)} ⟨Jf, [(T_{η}|_{L_{2}(ν_{4})} + r_{k}B_{η,4}) ⊗ T_{η}|_{L_{2}(ν_{k−4})}] Jf⟩ =^{(19)} ∑_{j=0}^{∞} η^{2j}⟨f_{j}, (T_{η} + r_{k}B_{η,4}) f_{j}⟩.

(48)

Since r_{k} ≤ 15/16 and B_{η,4} ≥ 0, we have the following operator inequalities on L_{2}(ν_{4}) ∀ j ≥ 1:

T_{η} + r_{k}B_{η,4} ≤ T_{η} + B_{η,4} =^{(24)} V_{η}^{(4)}, η^{2j}(T_{η} + r_{k}B_{η,4}) ≤ η^{2}(T_{η} + \frac{15}{16}B_{η,4}) =^{(33)} Z_{η}.

Combining this with (47) and (48) gives

⟨f, V_{η}^{(k)}f⟩ ≤ ∥V_{η}^{(4)} |_{span(1)^{⊥}} ∥ ∥f_{0}∥^{2} + ∥Z_{η}∥ ∑_{j=1}^{∞} ∥f_{j}∥^{2} ≤ max (∥V_{η}^{(4)} |_{span(1)^{⊥}} ∥, ∥Z_{η}∥)∥f∥^{2}.

This concludes the proof. □

We now summarize the above findings.

Proposition 4.5 (Certified radial bound). For every k ≥ 3,

∥A_{η}^{(k)}∥ ≤ ∥V_{η}^{(k)}|_{1^{⊥}}∥ < \begin{cases}.987, & k = 3, 0 < η ≤ .5843 \\ .989, & k ≥ 4, 0 < η ≤ 3/5. \end{cases}  (49)

Proof. The first inequality follows from (25). Then, the case k = 3 is Proposition 4.1; the case k = 4 is Proposition 4.3; and all cases k ≥ 5 follow from Propositions 4.3 and 4.4. □

Proof of Theorem 2.2. Combine Propositions 3.5 and 4.5. For the corresponding uniqueness statement of Theorem 1.6, note that the inequality (22) is an equality only when m(R) = 0, i.e. the average value of f on all spheres centered at the origin is zero. The equality case then follows from [HNP+23, Lemma 5.4] when ρ > 0, and for ρ < 0 by Lemma 5.1 below. In the latter case, equality means that the even part of f vanishes, so the equality case for ρ > 0 then applies to the ρ < 0 case. □

5. Quantum MAX-CUT hardness

We now pass from the centered positive inequality to the unrestricted negative inequality.

Lemma 5.1 (Gaussian oddification). Let 0 < η < 1 and let f: ℝ^{n} → 𝔹^{k} be measurable. Define

f_{e}(x) = \frac{f(x) + f(−x)}{2},  f_{o}(x) = \frac{f(x) − f(−x)}{2},  ∀ x ∈ ℝ^{n}.

Then f_{o} is odd, 𝔹^{k}-valued, and mean zero, and

Stab_{−η}(f) = Stab_{η}(f_{e}) − Stab_{η}(f_{o}) ≥ − Stab_{η}(f_{o}).  (50)

Proof. The functions f_{e} and f_{o} are supported on the even and odd Hermite-Fourier levels, respectively, and these subspaces are orthogonal. On a degree-d Hermite level, T_{−η} has eigenvalue (−η)^{d}. This gives the equality in (50); the inequality follows from positivity of T_{η}. The remaining assertions follow directly from the definition of f_{o}. □

Proof of Theorem 2.1. Write ρ = −η so that η > 0. By Lemma 5.1 and Theorem 2.2,

Stab_{ρ}(f) = Stab_{−η}(f) ≥ − Stab_{η}(f_{o}) ≥ −F^{∗}(k, η) =^{(3)} F^{∗}(k, −η) = F^{∗}(k, ρ).

This proves (4), completing the proof. □

As noted in the introduction, Theorem 2.1 immediately implies Theorem 1.7, since the correlation ρ_{BOV,3} from (6) satisfies (7).

6. Rank-k MAX-CUT Hardness

Theorem 1.8 follows from Theorem 2.1 for k ≥ 4 once we prove that ρ_{BOV,k} from (6) satisfies ρ_{BOV,k} ∈ (−3/5, 0) for any k ≥ 4.

Proposition 6.1 (Location of the worst correlation). For every k ≥ 4, the minimizer ρ_{BOV,k} in (6) is unique and satisfies

−\frac{3}{5} < ρ_{BOV,k} < 0.

Proof. Write Φ_{k}(q) := F^{∗}(k, q) for 0 ≤ q ≤ 1. Since Φ_{k} is odd by (3), minimizing (6) is equivalent to minimizing

a_{k}(q) := \frac{1 + Φ_{k}(q)}{1 + q}, q ∈ [0, 1].

The sign of a′_{k}(q) is the sign of

H_{k}(q) = (1 + q)Φ′_{k}(q) − Φ_{k}(q) − 1.

The power series in (3) has strictly positive coefficients, so H′_{k}(q) = (1 + q)Φ′′_{k}(q) > 0 for all q > 0. It remains to show H_{k}(0) < 0 and H_{k}(3/5) > 0. By its definition,

H_{k}(0) = g_{k} − 1 < 0, g_{k} := Φ′_{k}(0) =^{(3)} \frac{2}{k} (\frac{Γ((k + 1)/2)}{Γ(k/2)})^{2} =^{(11)} \frac{m_{k}^{2}}{k} <^{(11)} 1.

The hypergeometric series has known power series expansion _{2}F_{1}(1/2, 1/2, k/2 + 1, z) = ∑_{j=0}^{∞} \frac{(1/2)_{j}^{2}}{(k/2+1)_{j}j!}z^{j}. Since Φ_{k}(q) = g_{k}q_{2}F_{1}(1/2, 1/2, k/2 + 1, q^{2}), this leads to a power series expansion for H_{k} of the form

H_{k}(q) = g_{k} −1+g_{k} \frac{3q^{2} + 2q^{3}}{2(k + 2)} +g_{k} \frac{9(5q^{4} + 4q^{5})}{8(k + 2)(k + 4)} +g_{k} ∑_{j=3}^{∞} \frac{(1/2)_{j}^{2}}{(k/2 + 1)_{j}j!}((2j +1)q^{2j} +2jq^{2j+1}).

Since all of the coefficients are nonnegative, we can lower bound H_{k}(q) by dropping the j ≥ 3 terms. Plugging in q = 3/5 then gives

H_{k}(3/5) ≥ g_{k} (1 + \frac{18900k + 102573}{25000(k + 2)(k + 4)}) − 1.  (51)

The classical Wallis-ratio bound

\frac{Γ(x + 1/2)}{Γ(x)} > \sqrt{x − \frac{1}{4}}, ∀ x > \frac{1}{4},

gives g_{k} > 1 − \frac{1}{2k}. Also, for k ≥ 4,

\frac{18900k + 102573}{25000(k + 2)(k + 4)} > \frac{1}{2k − 1},

since this inequality is equivalent to 12800k^{2} + 36246k − 302573 > 0. Thus the right-hand side of (51) is positive. Since H_{k} is strictly increasing, it has exactly one zero in (0, 3/5). The derivative of a_{k} changes there from negative to positive, proving the claim. □

Proof of Theorem 1.8. For k = 3, the minimizing correlation is ρ_{BOV,3} = −0.5842676623 … ∈ (−.5843, 0). For k ≥ 4, Proposition 6.1 places ρ_{BOV,k} in (−3/5, 0). Apply Theorem 2.1 at ρ_{BOV,k} and then [HNP+23, Theorem C.4]. The resulting hardness factor is (6). □

7. Part II. MAX-3-CUT Preliminaries

Let Θ = (Θ_{1}, Θ_{2}, Θ_{3}) be the standard simplex partition of ℝ^{2}, consisting of three sectors of angle 2π/3 with vertex at the origin. For partitions A = (A_{i})_{i=1}^{3} and B = (B_{i})_{i=1}^{3} of ℝ^{n} into three disjoint measurable sets, put

Q_{ρ}^{(n)}(A, B) := ∑_{i=1}^{3} ∫_{ℝ^{n}} 1_{A_{i}}(x)T_{ρ}1_{B_{i}}(x)γ_{n}(x) dx.  (52)

For measurable E ⊆ ℝ^{n}, write −E = {−x: x ∈ E}, and −A := (−A_{i})_{i=1}^{3}. Below we prove

Theorem 7.1 (Standard Simplex, Negative Correlation). Let n ≥ 2, let Ω = (Ω_{1}, Ω_{2}, Ω_{3}) be a measurable partition of ℝ^{n}. Let ρ ∈ [−1/2, 0). Then

Q_{ρ}^{(n)}(Ω, Ω) ≥ Q_{ρ}^{(2)}(Θ, Θ).

Put σ := −ρ. Since T_{−σ}1_{E} = T_{σ}1_{−E} for every measurable E, negative noise stability can be written in bilinear form. For m ≥ 2, let M_{m} be the infimum of Q_{σ}^{(m)}(A, B) over pairs of partitions satisfying γ_{m}(A_{i}) = γ_{m}(B_{i}) for i = 1, 2, 3. Existence of minimizers and the optimal bilinear dimension-reduction theorem for negative correlation [Hei22, Lemma 7.3 and Theorem 7.9], which refines the method of Heilman–Tarter [HT21], together with the cylinder embedding, give M_{m} = M_{2}. Thus, for every partition Ω of ℝ^{n},

∑_{i=1}^{3}⟨1_{Ω_{i}}, T_{−σ}1_{Ω_{i}}⟩_{L_{2}(γ_{n})} = Q_{σ}^{(n)}(Ω, −Ω) ≥ M_{n} = M_{2}.

Consequently, it is enough to prove, for every pair of partitions A, B of ℝ^{2} satisfying γ_{2}(A_{i}) = γ_{2}(B_{i}) for all i,

Q_{σ}^{(2)}(A, B) ≥ Q_{σ}^{(2)}(Θ, −Θ).  (53)

Let dν(r) = e^{−r} dr. For r ≥ 0, on the circle of radius \sqrt{2r}, let p_{i}(r) and q_{i}(r) be the normalized angular measures of A_{i} and B_{i}. That is, p_{i}(r) = ∫_{A_{i}∩\sqrt{2r}S^{1}} dx/(2π\sqrt{2r}), for all r > 0, 1 ≤ i ≤ 3. Thus p(r), q(r) ∈ Δ_{3}, where

Δ_{3} = {z ∈ [0, 1]^{3} : ∑_{i=1}^{3} z_{i} = 1}.

Since γ_{2}(A_{i}) = γ_{2}(B_{i}) for all 1 ≤ i ≤ 3, we have

∫_{0}^{∞} p_{i}(r) dν(r) = ∫_{0}^{∞} q_{i}(r) dν(r),  i = 1, 2, 3.  (54)

Let μ be normalized Haar measure on the circle S^{1}. Let (ξ, η) be a σ-correlated pair of standard Gaussian vectors in ℝ^{2}, and set t = |ξ|^{2}/2 and s = |η|^{2}/2. Conditional on t, s, the joint angular density relative to μ ⊗ μ is [Hei23, Section 2]

κ_{a}(θ − ϕ) := e^{a cos(θ−ϕ)}/I_{0}(a),  (55)

where I_{0} is the modified Bessel function of the first kind of order zero (see (59)) and

d := 1 − σ^{2},  a := \frac{2σ\sqrt{ts}}{d}.  (56)

Since ∫ κ_{a}(θ − ϕ) dμ(ϕ) = 1, measurable sets E, F on the circle satisfy

∫∫_{E×F} κ_{a}(θ − ϕ) dμ(θ) dμ(ϕ) = μ(E) − ∫∫_{E×F^{c}} κ_{a}(θ − ϕ) dμ(θ) dμ(ϕ).

If we wish to maximize the last integral over all measurable E, F ⊆ S^{1} with μ(E) and μ(F) fixed, then the circular Riesz rearrangement inequality [BT76, Theorem 2] implies that the maximum occurs for circular arcs with the same center of mass. Therefore, the first integral is minimized by opposing arcs. Applying this separately for each 1 ≤ i ≤ 3 on the left side of (53), we obtain a lower bound of Q_{σ}^{(2)}(A, B) where A, B are rearranged on a given radius \sqrt{2r}S^{1} to be opposing arcs. The three rearranged arcs on either circle need not be disjoint for the purpose of proving (53).

We therefore proceed to minimize the spherical noise stability over circular arcs, as in [Hei23].

8. The joint arc inequality

Our first task is proving a strengthened version of [Hei23, Lemma 3.3] for negative correlations. From now on, set

b := \frac{1}{3}.  (57)

Thus b is the normalized angular length of each of the three sectors in the standard simplex partition, and b1 = (1/3, 1/3, 1/3) is the center of Δ_{3}. Identify the circle with 𝕋 = ℝ/(2πℤ) and write dμ(θ) = dθ/(2π). For any p, q ∈ [0, 1], let

E_{p} := {θ ∈ 𝕋: |θ| ≤ πp}, F_{q} := {ϕ ∈ 𝕋: |ϕ − π| ≤ πq},

where both descriptions are understood modulo 2π. These are arcs of normalized lengths p and q with opposing centers of mass. Their conditional overlap under the angular kernel (55) is

K_{a}(p, q) := ∫∫_{E_{p}×F_{q}} \frac{e^{a cos(θ−ϕ)}}{I_{0}(a)} dμ(θ) dμ(ϕ),  ∀ p, q ∈ [0, 1], a ∈ ℝ.  (58)

We now derive a Fourier formula for K_{a} and the mixed-derivative identity used below. For an integer m ≥ 0, the modified Bessel function of the first kind has the integral representation

I_{m}(a) := \frac{1}{2π} ∫_{−π}^{π} e^{a cos ϑ} cos(mϑ) dϑ,  ∀ a ∈ ℝ.  (59)

It also has the power-series representation

I_{m}(a) = ∑_{ℓ≥0} \frac{(a/2)^{m+2ℓ}}{ℓ!(m + ℓ)!},  m ≥ 0.  (60)

We now derive a generating function of these Bessel functions. We write

e^{az/2}e^{a/(2z)} = ∑_{r,s≥0} \frac{(a/2)^{r+s}}{r!s!} z^{r−s}, ∀ a ∈ ℝ, z ∈ ℂ \ \{0\}.

For m ≥ 0, the coefficient of z^{m} is obtained by setting r = s + m and is exactly the series for I_{m}(a) above; the coefficient of z^{−m} is the same. With the standard convention I_{−m}(a) := I_{m}(a) for m ≥ 1, this proves

exp(\frac{a}{2}(z + z^{−1})) = ∑_{m∈ℤ} I_{m}(a)z^{m},  ∀ a ∈ ℝ, z ∈ ℂ \ \{0\}.  (61)

Taking z = e^{iϑ} for some ϑ ∈ ℝ gives

\frac{e^{a cos ϑ}}{I_{0}(a)} = 1 + 2 ∑_{m≥1} \frac{I_{m}(a)}{I_{0}(a)} cos(mϑ).  (62)

For bounded 2π-periodic f: ℝ → ℝ and m ∈ ℤ define f̂(m) := ∫_{𝕋} f(θ)e^{−imθ} dμ(θ). The nonzero Fourier coefficients of the two arcs are

ˆ1_{E_{p}}(m) = \frac{sin(πmp)}{πm},  ˆ1_{F_{q}}(m) = (−1)^{m} \frac{sin(πmq)}{πm} (m ≠ 0),

and their zeroth coefficients are p and q, respectively. The factor (−1)^{m} comes precisely from translating the second arc by π. Substituting these coefficients and (62) into (58) gives

K_{a}(p, q) = pq + 2 ∑_{m≥1}(−1)^{m} \frac{I_{m}(a)}{I_{0}(a)} \frac{sin(πmp) sin(πmq)}{π^{2}m^{2}},  ∀ p, q ∈ [0, 1], a ∈ ℝ. (63)

For fixed a ≥ 0, the coefficients I_{m}(a) have inverse factorial decay in m by (60). Thus the series obtained by differentiating (63) once in each variable converges absolutely and uniformly on [0, 1]^{2}. Writing ∂_{pq} := ∂^{2}/(∂p ∂q), we obtain, for all a ∈ ℝ and p, q ∈ [0, 1],

∂_{pq}K_{a}(p, q) = 1 + 2 ∑_{m≥1}(−1)^{m} \frac{I_{m}(a)}{I_{0}(a)} cos(πmp) cos(πmq)

= 1 + ∑_{m≥1}(−1)^{m} \frac{I_{m}(a)}{I_{0}(a)}( cos(πm(p − q)) + cos(πm(p + q))).

Replacing ϑ by π + u in (62) yields

1 + 2 ∑_{m≥1}(−1)^{m} \frac{I_{m}(a)}{I_{0}(a)} cos(mu) = \frac{e^{−a cos u}}{I_{0}(a)} .

Averaging the two instances of this identity with u = π(p − q) and u = π(p + q) proves

∂_{pq}K_{a}(p, q) = \frac{e^{−a cos(π(p−q))} + e^{−a cos(π(p+q))}}{2I_{0}(a)} .  (64)

Recall b = 1/3 by (57). For any a ≥ 0 define

k(a) := K_{a}(b, b), P (a) := ∂_{1}K_{a}(b, b), τ(a) := 4P (a) − 3k(a), j(a) := P (a) − 3k(a).

(65)

Here ∂_{1} denotes differentiation in the first scalar argument. Formula (60) gives I_{0}(0) = 1 and I_{m}(0) = 0 for every m ≥ 1. Hence by (65),

\begin{matrix}K_{0}(p, q) = pq,  k(0) = K_{0}(b, b) = b^{2} = \frac{1}{9},  P (0) = ∂_{1}K_{0}(b, b) = b = \frac{1}{3}, \\ τ(0) = 4P (0) − 3k(0) = \frac{4}{3} − \frac{1}{3} = 1,  j(0) = P (0) − 3k(0) = \frac{1}{3} − \frac{1}{3} = 0. \end{matrix}  (66)

Lemma 8.1 (joint signed arc bound). For every a ≥ 0 and p, q ∈ Δ_{3}, with b = 1/3 as above, put x = p − b1 and y = q − b1. Then

∑_{i=1}^{3} K_{a}(p_{i}, q_{i}) − 3K_{a}(b, b) ≥ τ(a)⟨x, y⟩ + j(a)(∥x∥^{2} + ∥y∥^{2}).  (67)

Moreover, j(a) > 0 when a > 0.

Proof. If a = 0, applying the identities in (66) coordinatewise gives

∑_{i=1}^{3} K_{0}(p_{i}, q_{i}) − 3K_{0}(b, b) = ∑_{i=1}^{3} p_{i}q_{i} − 3b^{2} = ⟨p − b1, q − b1⟩.

The last equality uses p, q ∈ Δ_{3} and 3b = 1. Since τ(0) = 1 and j(0) = 0, this is exactly equality in (67). Henceforth assume a > 0 and suppress the dependence of k, P, τ, j on a. In the scalar argument below, p, q denote arbitrary numbers in [0, 1], rather than the vectors in the lemma statement. We prove the stronger scalar inequality

K_{a}(p, q) ≥ τpq − j{p(1 − p) + q(1 − q)},  ∀ a > 0, p, q ∈ [0, 1].  (68)

Let

L := 2b = 2/3,  r_{a}(u) := \frac{e^{−a cos(πu)}}{I_{0}(a)} ,  ∀ u ∈ ℝ.  (69)

The function r_{a} is even and 2-periodic. Integrating (64) from the lower edges of the square gives

P = \frac{1}{2} ∫_{0}^{L} r_{a}(u) du,  k = \frac{1}{2} ∫_{0}^{L}(L − u)r_{a}(u) du.  (70)

We will now prove the following inequalities.

j = \frac{1}{2} ∫_{0}^{L}(3u − 1)r_{a}(u) du ≥ 0,  (71)
τ = ∫_{0}^{L}(1 + 3u/2)r_{a}(u) du ≤ 1,  (72)
τ + 2j = \frac{9}{2} ∫_{0}^{L} ur_{a}(u) du ≤ r_{a}(L).  (73)

Since r_{a} is increasing on [0, L], the first inequality follows from (3u−1){r_{a}(u)−r_{a}(1/3)} ≥ 0 and ∫_{0}^{L}(3u − 1) du = 0. For the second, (59) and the substitution θ ↦ π − θ give

∫_{0}^{1} r_{a}(v) dv = \frac{1}{πI_{0}(a)} ∫_{0}^{π} e^{−a cos θ} dθ = 1.

Now use the change of variables v = L + 3u^{2}/4:

∫_{L}^{1} r_{a}(v) dv − \frac{3}{2} ∫_{0}^{L} ur_{a}(u) du = \frac{3}{2} ∫_{0}^{L} u\{r_{a}(L + 3u^{2}/4) − r_{a}(u)\} du ≥ 0.

Indeed, r_{a} is increasing on [0, 1] and L + 3u^{2}/4 ≥ u for 0 ≤ u ≤ L. The last inequality in (73) follows since (9u/2) du is a probability measure on [0, L]. Strict monotonicity gives j > 0 for a > 0.

Fix a > 0. For any p, q ∈ [0, 1] define

Φ(p, q) := K_{a}(p, q) − τpq + j[p(1 − p) + q(1 − q)].  (74)

Then Φ is nonnegative on all four boundary edges of the square [0, 1]^{2}. For example,

Φ(p, 0) = jp(1 − p), Φ(p, 1) = (1 − τ)p + jp(1 − p).

Here we used K_{a}(p, 0) = 0 and K_{a}(p, 1) = p by (63). The other two boundary edges follow by symmetry. Now, if Φ were negative somewhere on [0, 1]^{2}, its minimum would therefore occur at an interior critical point. To analyze such a point, put

G(δ) := ∫_{0}^{δ} r_{a}(u) du,  ∀ δ ∈ [−1, 1].  (75)

For δ < 0, this is understood as a signed integral. Since r_{a} is even, G is odd. Also, K_{a}(p, 0) = K_{a}(0, q) = 0. We can then integrate (64) from the corresponding lower edge of [0, 1]^{2} to get

∂_{1}K_{a}(p, q) = ∫_{0}^{q} ∂_{12}K_{a}(p, v) dv = \frac{1}{2} ∫_{0}^{q}[r_{a}(p − v) + r_{a}(p + v)] dv
= \frac{1}{2}[G(p + q) − G(p − q)],  (76)
∂_{2}K_{a}(p, q) = ∫_{0}^{p} ∂_{12}K_{a}(u, q) du = \frac{1}{2} ∫_{0}^{p}[r_{a}(u − q) + r_{a}(u + q)] du
= \frac{1}{2}[G(p + q) + G(p − q)],  ∀ p, q ∈ [0, 1].  (77)

Subtracting (76) and (77) and using the oddness of G gives

∂_{1}K_{a}(p, q) − ∂_{2}K_{a}(p, q) = −G(p − q) = G(q − p) ∀ p, q ∈ [0, 1], a ∈ ℝ.  (78)

At an interior critical point of Φ, we have ∇Φ = 0, which by (74) says

0 = ∂_{1}K_{a}(p, q) − τq + j(1 − 2p),
0 = ∂_{2}K_{a}(p, q) − τp + j(1 − 2q).

If the critical point (p, q) is off the diagonal, put δ := q − p ≠ 0. Subtracting the second critical point equation from the first and applying (78) gives

G(δ) = (τ − 2j)δ.  (79)

Now, differentiating (76) and (77) once more gives

\begin{aligned}∂_{11}K_{a}(p, q) = ∂_{22}K_{a}(p, q) & = \frac{1}{2}\{r_{a}(p + q) − r_{a}(p − q)\}, \\ ∂_{12}K_{a}(p, q) & = \frac{1}{2}\{r_{a}(p + q) + r_{a}(p − q)\},  ∀ p, q ∈ [0, 1], a ∈ ℝ. \end{aligned} (80)

Consequently, the unnormalized directional derivative satisfies

∂_{(1,−1)}^{2}Φ(p, q) := \frac{d^{2}}{dt^{2}} Φ(p + t, q − t)|_{t=0} ,

∂_{(1,−1)}^{2}Φ = ∂_{11}Φ + ∂_{22}Φ − 2∂_{12}Φ =^{(74)∧(80)} −2r_{a}(δ) + 2τ − 4j =^{(79)} −2 (r_{a}(δ) − \frac{G(δ)}{δ}) .

Since r_{a} is even and strictly increasing on [0, 1] by (69), while 0 < |δ| < 1, we have

\frac{G(δ)}{δ} =^{(75)} \frac{1}{|δ|} ∫_{0}^{|δ|} r_{a}(u) du < r_{a}(|δ|) = r_{a}(δ).

Thus ∂_{(1,−1)}^{2}Φ < 0, so such a point cannot be a local minimum.

It remains to consider the case δ = 0, i.e. p = q. Define then

g(p) := Φ(p, p) = K_{a}(p, p) − τp^{2} + 2jp(1 − p), ∀ p ∈ [0, 1].

By (63), K_{a}(0, 0) = 0 and K_{a}(1, 1) = 1, while symmetry and the definitions (65) give K_{a}(b, b) = k and ∂_{1}K_{a}(b, b) = ∂_{2}K_{a}(b, b) = P. Therefore

9g(b) = 9k − τ + 4j = 0,
g′(b) = 2P − \frac{2}{3}τ + \frac{2}{3}j = 0,

where we used τ = 4P − 3k and j = P − 3k by (65). Consequently,

g(0) = g(b) = g′(b) = 0, g(1) = 1 − τ ≥ 0.

Equations (76) and (77) also give

\frac{d}{dp}K_{a}(p, p) = G(2p), \frac{d^{2}}{dp^{2}} K_{a}(p, p) = 2r_{a}(2p).

It follows that

g′′(p) = 2[r_{a}(2p) − τ − 2j].  (81)

Since p ↦ r_{a}(2p) increases on [0, 1/2] and decreases on [1/2, 1], the set on which (81) is nonnegative is an interval of the form [s, 1 − s] for some 0 ≤ s ≤ 1/2. Inequality (73) gives s ≤ b. Convexity and g′(b) = 0 give g ≥ 0 on [s, 1 − s]. On each complementary interval in [0, 1] \ [s, 1 − s], g is concave, so it lies above the line joining its nonnegative endpoint values. Thus (68) holds.

To conclude the proof of (67) from (68), note that ∑_{i=1}^{3} x_{i} = ∑_{i=1}^{3} y_{i} = 0 and hence

∑_{i=1}^{3} p_{i}q_{i} = \frac{1}{3} + ⟨x, y⟩,  ∑_{i=1}^{3} p_{i}(1 − p_{i}) = \frac{2}{3} − ∥x∥^{2},  ∑_{i=1}^{3} q_{i}(1 − q_{i}) = \frac{2}{3} − ∥y∥^{2}.

Summing (68) over i gives a constant (τ − 4j)/3 = 3k, since τ − 4j = 9k by (65) yielding (67). □

8.1. Gain from the first angular mode. We need a modest strengthening of Lemma 8.1 at the negative endpoint.

We first record the homogeneous form of the preceding argument. Let r be a continuous, nonnegative, even, 2-periodic function that is nondecreasing on [0, 1]. Define \overline{K}_{r}: [0, 1]^{2} → ℝ by

\overline{K}_{r}(p, q) := ∫_{0}^{p} ∫_{0}^{q} \frac{1}{2}[r(u − v) + r(u + v)] dv du,  ∀ p, q ∈ [0, 1].  (82)

Put

k_{r} = \overline{K}_{r}(b, b),  P_{r} = ∂_{1}\overline{K}_{r}(b, b),  τ_{r} = 4P_{r} − 3k_{r},  j_{r} = P_{r} − 3k_{r}.  (83)

The proof of Lemma 8.1 gives, without any change other than normalization,

∑_{i=1}^{3} \overline{K}_{r}(p_{i}, q_{i}) − 3k_{r} ≥ τ_{r}⟨x, y⟩ + j_{r}(∥x∥^{2} + ∥y∥^{2}).  (84)

Indeed, if M = ∫_{0}^{1} r(u) du, then the boundary identity used there is \overline{K}_{r}(p, 1) = Mp, and the inequality τ_{r} ≤ 1 is replaced by the homogeneous inequality τ_{r} ≤ M. All other steps are linear in r. Equivalently, one may apply the normalized lemma to r/M and then multiply by M; the case M = 0 is immediate. If r is only nondecreasing rather than strictly increasing, apply the argument to r + εr^{(1)} and let ε ↓ 0. All quantities in (84) depend continuously and linearly on r.

When r^{(1)}(u) = 1 − cos(πu) for all u ∈ [0, 1], we compute from (83) that

r^{(1)}(u) := 1 − cos(πu), j_{(1)} := j_{r^{(1)}} = \frac{9 − \sqrt{3} π}{4π^{2}} , τ_{(1)} := τ_{r^{(1)}} = 1 + \frac{9 − 4\sqrt{3} π}{4π^{2}} , ∀ u ∈ [0, 1].

(85)

Integrating (82) and using the cosine addition formula gives

\overline{K}_{(1)}(p, q) := \overline{K}_{r^{(1)}}(p, q) = pq − \frac{sin(πp) sin(πq)}{π^{2}}.  (86)

Direct substitution at p = q = b gives the constants in (85).

The following is a variant of [Hei23, Lemma 5.4].

Lemma 8.2 (simplex trigonometric estimate). For any m = (m_{1}, m_{2}, m_{3}) ∈ Δ_{3},

3 + 2 ∑_{i=1}^{3} cos(2πm_{i}) ≥ 6 ∑_{i=1}^{3}(m_{i} − b)^{2}.  (87)

Proof. Choose z := min_{i=1,2,3} m_{i} ∈ [0, 1/3] and, after permuting the coordinates, assume that m_{1} = z and m_{2} ≥ m_{3}. Put w = m_{2} − m_{3}. Since m_{2} + m_{3} = 1 − z, we have

m_{1} = z,  m_{2} = \frac{1 − z + w}{2},  m_{3} = \frac{1 − z − w}{2}.  (88)

The condition m_{3} ≥ z shows that 0 ≤ w ≤ 1 − 3z.

We now calculate the difference between the two sides of (87). By the cosine addition formula,

3 + 2 ∑_{i=1}^{3} cos(2πm_{i}) = 3 + 2 cos(2πz) + 2 cos(π(1 − z + w)) + 2 cos(π(1 − z − w))
= 3 + 2 cos(2πz) − 4 cos(πz) cos(πw)
= 1 + 4 cos^{2}(πz) − 4 cos(πz) cos(πw) = 1 + 4 cos(πz)[cos πz − cos πw].

On the other hand, using ∑_{i=1}^{3} m_{i} = 1 then (88)

6 ∑_{i=1}^{3}(m_{i} − 1/3)^{2} = 6( − \frac{1}{3} + ∑_{i=1}^{3} m_{i}^{2}) = 6z^{2} + 3(1 − z)^{2} + 3w^{2} − 2 = 9z^{2} − 6z + 1 + 3w^{2}.

Consequently, the left side of (87) minus its right side is

F_{z}(w) := 3z(2 − 3z) − 3w^{2} − 4 cos(πz)[cos(πw) − cos(πz)].

It therefore remains to prove F_{z}(w) ≥ 0 for 0 ≤ z ≤ 1/3 and 0 ≤ w ≤ 1 − 3z. We have

F′_{z}(0) = 0,  F′′′_{z}(w) = −4π^{3} cos(πz) sin(πw) ≤ 0,  ∀ 0 ≤ w ≤ 1.

Thus F′′_{z} is decreasing on [0, 1], so F′_{z} can change from positive to negative at most once on [0, 1 − 3z]. The minimum of F_{z} is therefore attained at w = 0 or w = 1 − 3z.

It remains to show that F_{z}(0) ≥ 0 and F_{z}(1 − 3z) ≥ 0.

Put t := 3z. The condition F_{z}(0) ≥ 0 is equivalent to

4c(1 − c) ≤ t(2 − t), c := cos(πt/3).

Since t ↦ cos(πt/3) is concave on [0, 1], it is lower bounded by its secant line, i.e. c ≥ 1−t/2, which implies 4y(1 − y) ≤ 2t − t^{2} when 0 ≤ y = 1 − c ≤ t/2 by concavity of y ↦ y(1 − y) on [0, 1/2].

When w = 1 − t, the triple angle formula cos πt = 4 cos^{3}(tπ/3) − 3 cos(tπ/3) = 4c^{3} − 3c gives

F_{z}(1 − t) = (4c^{2} − 1)^{2} − 4(1 − t)^{2}.

Again c ≥ 1−t/2 gives 4c^{2}−1 ≥ 4(1−t/2)^{2}−1 ≥ 2(1−t) ∀ t ∈ [0, 1], proving F_{z}(1−t) ≥ 0. □

We now prove the following improvement to (84) when r = r^{(1)}.

Lemma 8.3 (first-mode endpoint gain). For any p, q ∈ Δ_{3}, put x := p − b1 and y := q − b1. Then

∑_{i=1}^{3} \overline{K}_{(1)}(p_{i}, q_{i}) − 3\overline{K}_{(1)}(b, b) ≥ (τ_{(1)} + 2j_{(1)})⟨x, y⟩ + \frac{3}{2}j_{(1)}(∥x∥^{2} + ∥y∥^{2}).  (89)

Proof. Let

m := \frac{p + q}{2} ,  M := m − b1,  δ := \frac{p − q}{2} ,

and put

S := ∥x∥^{2} +∥y∥^{2} +4⟨x, y⟩ = ∥M +δ∥^{2} +∥M −δ∥^{2} +4⟨M +δ, M −δ⟩ = 6∥M∥^{2} −2∥δ∥^{2}. (90)

Subtract the right side of (89) from its left side. Using (86) and

sin(π(m_{i} + δ_{i})) sin(π(m_{i} − δ_{i})) = sin^{2}(πm_{i}) − sin^{2}(πδ_{i}),

∑_{i=1}^{3} \overline{K}_{(1)}(p_{i}, q_{i}) − 3\overline{K}_{(1)}(b, b) = ⟨x, y⟩ + \frac{1}{π^{2}} (\frac{9}{4} − ∑_{i=1}^{3} sin^{2}(πm_{i}) + ∑_{i=1}^{3} sin^{2}(πδ_{i})).

Subtracting the right-hand side of (89) from this, we get a deficit

Δ = \frac{1}{π^{2}} (\frac{9}{4} − ∑_{i=1}^{3} sin^{2}(πm_{i}) + ∑_{i=1}^{3} sin^{2}(πδ_{i})) + (1 − τ_{(1)} − 2j_{(1)})⟨x, y⟩ − \frac{3}{2}j_{(1)}(∥x∥^{2} + ∥y∥^{2}).

Letting D := 4π^{2}Δ, and using (85) with ∥x∥^{2} + ∥y∥^{2} = 2∥M∥^{2} + 2∥δ∥^{2} and ⟨x, y⟩ = ∥M∥^{2} − ∥δ∥^{2},

D = 3 + 2 ∑_{i=1}^{3} cos(2πm_{i}) + 4 ∑_{i=1}^{3} sin^{2}(πδ_{i}) + 9(\sqrt{3} π − 6)∥M∥^{2} − 3\sqrt{3} π∥δ∥^{2}. (91)

Lemma 8.2 and the concave secant line inequality sin(π|u|) ≥ 2|u| for |u| ≤ 1/2 imply

D ≥ (3\sqrt{3} π − 16)(3∥M∥^{2} − ∥δ∥^{2}) =^{(90)} \frac{3\sqrt{3} π − 16}{2}S.

Since 3\sqrt{3} π − 16 > 0, this proves the assertion (89) when S ≥ 0. When S < 0, the right side of (89) minus the right side of the homogeneous estimate (84) is j_{(1)}S/2 < 0 by (85). Hence (84) proves the case S < 0 of (89). So, in all cases, (89) holds. □

Define

θ(a) := \frac{j_{(1)}}{2} \frac{ae^{−a}}{I_{0}(a)},  ∀ a ≥ 0.  (92)

Since

r_{a}(u) =^{(69)} \frac{e^{−a cos(πu)}}{I_{0}(a)} = r_{a}(0)e^{a(1−cos(πu))}, ∀ u ∈ ℝ,

we have the exact decomposition

r_{a}(u) = r_{a}(0)[1 + ar^{(1)}(u)] + r_{rem}(u),  ∀ u ∈ ℝ,  (93)

where

r_{rem}(u) := r_{a}(0) (e^{a(1−cos(πu))} − 1 − a(1 − cos(πu))) , ∀ u ∈ ℝ.

The remainder is nonnegative and nondecreasing on [0, 1], since

r′_{rem}(u) = r_{a}(0)aπ sin(πu) (e^{a(1−cos(πu))} − 1) ≥ 0, ∀ a ≥ 0, u ∈ [0, 1].

Observe that (82) and all quantities defined in (83) are linear in r. We then apply (84) to three different choices of r, corresponding to the three functions on the right side of (93):

(i) the constant function r = r_{a}(0), (ii) r := r_{a}(0)ar^{(1)}, and (iii) r = r_{rem}. By linearity, and recalling K_{a} = \overline{K}_{r_{a}}, the quantity ∑_{i=1}^{3} K_{a}(p_{i}, q_{i}) − 3K_{a}(b, b) is then lower bounded by a sum of three terms corresponding to (i), (ii) and (iii). In cases (i) and (iii) we apply (84), and in case (ii) we apply the improved bound (89). Summing up all three contributions then gives

Corollary 8.4. For any a ≥ 0 and p, q ∈ Δ_{3}, put x = p − b1 and y = q − b1. Then

∑_{i=1}^{3} K_{a}(p_{i}, q_{i}) − 3K_{a}(b, b) ≥ (τ(a) + 4θ(a))⟨x, y⟩ + (j(a) + θ(a))(∥x∥^{2} + ∥y∥^{2}).  (94)

Note that this is an improvement to (67). The first gained term comes from the right side of (89) where r_{a}(0)a2j_{(1)} = 4θ(a) via (92), and the second gained term comes from r_{a}(0)aj_{(1)}/2 = θ(a).

9. The radial operator

We first derive the radial law used in this section. Recall that (ξ, η) is a σ-correlated pair of standard Gaussian vectors in ℝ^{2} and

t := \frac{∥ξ∥^{2}}{2} , s := \frac{∥η∥^{2}}{2} .

Thus the corresponding Euclidean radii are \sqrt{2t} and \sqrt{2s}. Equivalently, if Z is an independent standard Gaussian vector, then η = σξ + \sqrt{d} Z, where d = 1 − σ^{2}. Since ∥ξ∥^{2} and ∥η∥^{2} are each χ_{2}^{2}-distributed, both t and s have the exponential probability law

dν(r) = e^{−r} dr, r ≥ 0.

𝔼t = 𝔼s = 1,  Var(t) = Var(s) = 1,  Cov(t, s) = σ^{2}.

The joint Gaussian density of (ξ, η) is

\frac{1}{(2π)^{2}d} exp (−\frac{∥ξ∥^{2} + ∥η∥^{2} − 2σ⟨ξ, η⟩}{2d}) .

Suppose we parametrize ξ, η as

ξ = \sqrt{2t}(cos θ, sin θ),  η = \sqrt{2s}(cos ϕ, sin ϕ),  θ, ϕ ∈ [0, 2π).

Observe ⟨ξ, η⟩ = 2\sqrt{ts} cos(θ−ϕ). So the joint density of (t, s, θ, ϕ), relative to dt ds dμ(θ) dμ(ϕ) is

\frac{1}{d} exp (−\frac{t + s}{d} + \frac{2σ\sqrt{ts}}{d} cos(θ − ϕ)) .  (95)

Put

a = a(t, s) := \frac{2σ\sqrt{ts}}{d}.  (96)

Since I_{0}(a) = ∫_{𝕋} e^{a cos u} dμ(u) by (59), integrating (95) over the two angular variables gives the ordinary joint density of (t, s) relative to dt ds:

f_{t,s}(t, s) = \frac{1}{d}e^{−(t+s)/d}I_{0} (\frac{2σ\sqrt{ts}}{d}) ,  t, s ≥ 0.  (97)

On the other hand, ν ⊗ ν has Lebesgue density e^{−(t+s)}. Therefore the Radon–Nikodym derivative of the joint radial law with respect to ν ⊗ ν is

R_{0}(t, s) = \frac{f_{t,s}(t, s)}{e^{−(t+s)}} = \frac{1}{d}e^{−σ^{2}(t+s)/d}I_{0} (\frac{2σ\sqrt{ts}}{d}) ,  ∀ t, s ≥ 0.  (98)

Thus, for every measurable D ⊆ [0, ∞)^{2},

Pr[(t, s) ∈ D] = ∫∫_{D} R_{0}(t, s) dν(t) dν(s).

In particular, since each marginal is ν,

∫_{0}^{∞} R_{0}(t, s) dν(s) = 1 for ν-almost every t,  (99)

and likewise with t and s interchanged. Equivalently, the complete radial-angular factorization is

dℙ = R_{0}(t, s) dν(t) dν(s) \frac{e^{a cos(θ−ϕ)}}{I_{0}(a)} dμ(θ) dμ(ϕ).

We now apply (94) at each pair (t, s) of radii. Put

K_{0}(t, s) := R_{0}(t, s)τ(a) =^{(72)} \frac{e^{−σ^{2}(t+s)/d}}{2d} ∫_{0}^{2/3}(2 + 3v)e^{−a cos(πv)} dv,  (100)
J_{0}(t) := ∫_{0}^{∞} R_{0}(t, s)j(a) dν(s) =^{(71)} ∫_{0}^{∞} \frac{e^{−σ^{2}(t+s)/d}}{2d} ∫_{0}^{L}(3u − 1)e^{−a cos(πu)} du dν(s), (101)
B(t, s) := R_{0}(t, s)θ(a) =^{(92)∧(96)} \frac{j_{(1)}}{2d} a e^{−σ^{2}(t+s)/d−a},  (102)
B_{(1)}(t) := ∫_{0}^{∞} B(t, s) dν(s) =^{(96)} σ\sqrt{t}\frac{j_{(1)}}{d^{2}} ∫_{0}^{∞} \sqrt{s}e^{−2σ\sqrt{ts}/d}e^{−σ^{2}(t+s)/d−s} ds,  (103)
K_{∗}(t, s) := K_{0}(t, s) + 4B(t, s),  J_{∗}(t) := J_{0}(t) + B_{(1)}(t).  (104)

If K_{∗} is the integral operator with kernel K_{∗} and M_{J_{∗}} is multiplication by J_{∗}, then integration of (94) in t, s gives the quadratic expression

∑_{i=1}^{3} (⟨x_{i}, K_{∗}y_{i}⟩ + ⟨x_{i}, M_{J_{∗}}x_{i}⟩ + ⟨y_{i}, M_{J_{∗}}y_{i}⟩),  (105)

where x_{i} := p_{i} − b, y_{i} := q_{i} − b, and p_{i}, q_{i}: (0, ∞) → [0, 1] are defined after (53), for all i = 1, 2, 3, and here ⟨·, ·⟩ denotes the L_{2} inner product on (0, ∞) with respect to the exponential measure ν.

9.1. Operator norm inequality. Our first task is to bound the first term in (105) in Lemma 9.1 below.

We record an elementary weighted Hilbert–Schmidt estimate used twice below. If J > 0 almost everywhere and L: (0, ∞)^{2} → ℝ is a symmetric bounded kernel, put

h(L, J) := ( ∫_{0}^{∞} ∫_{0}^{∞} \frac{L(t, s)^{2}}{J(t)J(s)} dν(t) dν(s))^{1/2}.

Then every bounded real z: (0, ∞) → ℝ satisfies

|⟨z, Lz⟩| ≤ h(L, J)⟨z, M_{J}z⟩.  (106)

Indeed, with f := \sqrt{J}z and H(s, t) := L(s, t)/\sqrt{J(t)J(s)}, the Cauchy–Schwarz inequality on the space (0, ∞)^{2} gives

|⟨z, Lz⟩| = |⟨f, Hf⟩| ≤ ∥H∥_{L_{2}(ν⊗ν)}∥f∥_{L_{2}(ν)}^{2}.  (107)

For the endpoint certificate, define

u_{∗} := K_{∗}1,  C_{∗} := ⟨1, u_{∗}⟩,  (108)
R_{∗}(t, s) := K_{∗}(t, s) − \frac{u_{∗}(t)u_{∗}(s)}{C_{∗}},  ∀ t, s > 0,  (109)
E_{∗}(t, s) = K_{∗}(t, s) − u_{∗}(s) − u_{∗}(t) + C_{∗} ∀ t, s > 0.  (110)

Then R_{∗} has zero row and column integrals, and if ∫_{0}^{∞} z dν = 0, ⟨z, E_{∗}z⟩ = ⟨z, K_{∗}z⟩. Set

h_{lower} = h_{lower}(σ) := ( ∫_{0}^{∞} ∫_{0}^{∞} \frac{R_{∗}(t, s)^{2}}{J_{∗}(t)J_{∗}(s)} dν(t) dν(s))^{1/2},  (111)
h_{upper} = h_{upper}(σ) := ( ∫_{0}^{∞} ∫_{0}^{∞} \frac{E_{∗}(t, s)^{2}}{J_{∗}(t)J_{∗}(s)} dν(t) dν(s))^{1/2}.  (112)

Lemma 9.1 (Spectral bounds). Let z: (0, ∞) → ℝ be bounded. Then

⟨z, K_{∗}z⟩ ≥ −h_{lower}⟨z, M_{J_{∗}}z⟩.  (113)

⟨z, K_{∗}z⟩ ≤ h_{upper}⟨z, M_{J_{∗}}z⟩  when ∫_{0}^{∞} z(s) dν(s) = 0.  (114)

Proof. We first identify the rank-one part. By definition,

u_{∗}(t) = ∫_{0}^{∞} K_{∗}(t, s) dν(s), C_{∗} = ∫_{0}^{∞} u_{∗}(t) dν(t) = ∫_{0}^{∞} ∫_{0}^{∞} K_{∗}(t, s) dν(t) dν(s) > 0.

The residual R_{∗} has zero row and column integrals:

∫_{0}^{∞} R_{∗}(t, s) dν(s) = u_{∗}(t) − \frac{u_{∗}(t)}{C_{∗}} ∫_{0}^{∞} u_{∗}(s) dν(s) = 0,

and similarly in the other variable. With the convention (u_{∗} ⊗ u_{∗})z = u_{∗} ⟨u_{∗}, z⟩, we have

K_{∗} = R_{∗} + \frac{u_{∗} ⊗ u_{∗}}{C_{∗}} , ⟨z, K_{∗}z⟩ = ⟨z, R_{∗}z⟩ + \frac{|⟨z, u_{∗}⟩|^{2}}{C_{∗}} .

The normalization here is C_{∗} = ⟨1, u_{∗}⟩, rather than ∥u∥_{L_{2}(ν)}^{2}: it is chosen so that R_{∗}1 = 0 and is not asserted to make (u_{∗} ⊗ u_{∗})/C_{∗} an orthogonal projection. The rank-one term is nonnegative, so its omission together with (106) and (107) with J = J_{∗} prove (113).

If ∫_{0}^{∞} z(s) dν(s) = 0, then the u_{∗}, C_{∗} terms in (110) vanish by Fubini’s Theorem:

∫_{0}^{∞} ∫_{0}^{∞}[−u_{∗}(t) − u_{∗}(s) + C_{∗}]z(t)z(s) dν(t) dν(s) = 0.

Consequently, (114) holds by (106), (107) and (110). □

9.2. Eigenvalue Bounds. We now bound the quantities (111) and (112) from Lemma 9.1.

We next give the formulas and directed bounds used to certify h_{upper} < 2 and h_{lower} < 2. Recall that 0 < σ ≤ 1/2, and

d = d_{σ} := 1 − σ^{2} κ = κ_{σ} := \frac{σ^{2}}{d} ,  q = q_{σ,t} := \frac{σ\sqrt{t}}{\sqrt{d}}  (115)

For the uncorrected radial terms, put

b_{v}(t) := q · cos(πv),  ∀ v ∈ [0, 1], t ≥ 0.  (116)
F_{v}(t) := e^{−κt} [1 − \sqrt{π}b_{v}(t)e^{b_{v}(t)^{2}} erfc(b_{v}(t))] ,  ∀ t ≥ 0.  (117)

Here erfc(z) := \frac{2}{\sqrt{π}} ∫_{z}^{∞} e^{−u^{2}} du, ∀ z ∈ ℝ is the complementary error function. The same Gaussian integration as in the previous section gives Lemma 9.2. u_{∗} = u_{0} + 4B_{(1)} by (108) and J_{∗} = J_{0} + B_{(1)} by (104) where

u_{0}(t) := K_{0}1 = \frac{1}{2} ∫_{0}^{2/3}(2 + 3v)F_{v}(t) dv,  J_{0}(t) =^{(101)} \frac{1}{2} ∫_{0}^{2/3}(3v − 1)F_{v}(t) dv,  ∀ t ≥ 0.

(118)

Proof. Using d = 1 − σ^{2} and a from (96), then substituting s = d · y^{2}, we get

I_{v}(t) := ∫_{0}^{∞} e^{−σ^{2}s/d}e^{−a cos(πv)} dν(s) =^{(96)} ∫_{0}^{∞} exp (−\frac{s}{d} − \frac{2σ\sqrt{ts}}{d} cos(πv)) ds
= d ∫_{0}^{∞} exp (−y^{2} − 2σ\sqrt{t}y cos(πv)) 2y dy = 2d ∫_{0}^{∞} ye^{−y^{2}−2b_{v}(t)y} dy
= 2d ∫_{0}^{∞} ye^{−(y+b_{v}(t))^{2}+b_{v}(t)^{2}} dy = 2de^{b_{v}(t)^{2}} ∫_{b_{v}(t)}^{∞}(y − b_{v}(t))e^{−y^{2}} dy

= de^{b_{v}(t)^{2}}[e^{−b_{v}(t)^{2}} − b_{v}(t)\sqrt{π}erfc(b_{v}(t))] = d[1 − \sqrt{π}b_{v}(t)e^{b_{v}(t)^{2}}erfc(b_{v}(t))] = de^{κt}F_{v}(t). (119)

u_{0}(t) = ∫_{0}^{∞} K_{0}(t, s) dν(s) =^{(100)} \frac{e^{−σ^{2}t/d}}{2d} ∫_{0}^{2/3}(2 + 3v) [∫_{0}^{∞} e^{−σ^{2}s/d}e^{−a cos(πv)} dν(s)] dv

=^{(119)} \frac{e^{−σ^{2}t/d}}{2d} ∫_{0}^{2/3}(2 + 3v)de^{κt}F_{v}(t) dv =^{(115)} \frac{1}{2} ∫_{0}^{2/3}(2 + 3v)F_{v}(t) dv.

Likewise, applying the same calculation to J_{0},

J_{0}(t) =^{(101)} ∫_{0}^{∞} \frac{e^{−σ^{2}(t+s)/d}}{2d} ∫_{0}^{L}(3u − 1)e^{−a cos πu} du dν(s) = \frac{1}{2} ∫_{0}^{2/3}(3v − 1)F_{v}(t) dv.

□

From (118) and (117), F_{v}(x^{2}) = 1 − \sqrt{π}(σ/\sqrt{d})x cos(πv) + O(x^{2}) uniformly in v, so

J_{0}(x^{2}) = \frac{1}{2} ∫_{0}^{2/3}(3v − 1)(−\sqrt{π}(σ/\sqrt{d})x cos πv + O(x^{2})) =^{(85)} x\sqrt{π} \frac{σ}{\sqrt{d}}j_{(1)} + O(x^{2}). (120)

We now derive a similar asymptotic expansion for B_{(1)}. If t = x^{2} and q = σx/\sqrt{d}, direct integration in the second radial variable gives

B_{(1)}(x^{2}) =^{(103)} e^{−κx^{2}} \frac{j_{(1)}q}{2} [\sqrt{π}(1 + 2q^{2})e^{q^{2}} erfc(q) − 2q] .  (121)

Proof. Using the substitution y = \sqrt{1 + σ^{2}/d}\sqrt{s} = \sqrt{s/d} by (115),

B_{(1)}(t) = σ\sqrt{t}\frac{j_{(1)}}{d^{2}} ∫_{0}^{∞} \sqrt{s}e^{−2σ\sqrt{ts}/d}e^{−σ^{2}(t+s)/d−s} ds

= \sqrt{t}j_{(1)} \frac{σ}{d^{2}} e^{− \frac{σ^{2}}{d} t} 2d^{3/2} ∫_{0}^{∞} y^{2}e^{−2yσ\sqrt{t}/\sqrt{d}}e^{−y^{2}} dy

= \sqrt{t}j_{(1)} \frac{2σ}{\sqrt{d}} ∫_{0}^{∞} y^{2}e^{−(y+σ\sqrt{t/d})^{2}} dy = \sqrt{t}j_{(1)} \frac{2σ}{\sqrt{d}} ∫_{σ\sqrt{t/d}}^{∞}(y − σ\sqrt{t/d})^{2}e^{−y^{2}} dy

= 2j_{(1)}q ∫_{σ\sqrt{t/d}}^{∞} (y^{2} − 2yσ\sqrt{t/d} + σ^{2}t/d)e^{−y^{2}} dy

= 2j_{(1)}q(\frac{\sqrt{π}}{4} erfc(q) + (1/2)qe^{−q^{2}} − qe^{−q^{2}} + q^{2} \frac{\sqrt{π}}{2} erfc(q))

□

So, lim_{x→0^{+}} B_{(1)}(x^{2})/x =^{(121)} \frac{j_{(1)}σ}{2\sqrt{d}} \sqrt{π}, lim_{x→0^{+}} J_{0}(x^{2})/x =^{(120)} \frac{j_{(1)}σ}{\sqrt{d}} \sqrt{π}, and by Lemma 9.2,

lim_{x→0^{+}} J_{∗}(x^{2})/x = j_{(1)} \frac{3}{2}\sqrt{π} \frac{σ}{\sqrt{d}} >^{(85)} 0.

Then, for any x > 0,

J̃_{∗}(x) := \frac{J_{∗}(x^{2})}{x},  J̃_{∗}(0) = j_{(1)} \frac{3}{2}\sqrt{π} \frac{σ}{\sqrt{d}} >^{(85)} 0.  (122)

Consequently, J̃_{∗} is continuous and positive near zero (J_{∗}(x) > 0 ∀ x > 0 by (128) below). The change of variables t = x^{2}, s = y^{2} therefore transforms both (111) and (112) into

(4 ∫_{0}^{∞} ∫_{0}^{∞} e^{−x^{2}−y^{2}} \frac{[L(x^{2}, y^{2})]^{2}}{J̃_{∗}(x)J̃_{∗}(y)} dx dy)^{1/2},  (123)

with L = R_{∗} or E_{∗}. We can now state the eigenvalue bounds for (111) and (112) using (123).

Lemma 9.3 (Uniform Eigenvalue Bound). Uniformly for all σ ∈ [1/43, 1/2], we have

h_{upper}(σ) < 1.967 < 2,  h_{lower}(σ) < 0.824 < 2.  (124)

Proof. The accompanying program plur_cert.py uses Arb balls for transcendental evaluations and outward-rounded binary64 interval arithmetic for the remaining operations. It subdivides [1/43, 1/2] into 640 nonuniform σ-intervals and [0, 5] into 1000 intervals in each radial variable. Here the nonuniform intervals [σ_{i}, σ_{i+1}] use σ_{i} = (1/43) + (1/2 − 1/43)(i/640)^{p} for each 0 ≤ i ≤ 640, where p = 1.3. The auxiliary tables use 64 second-order interval midpoint panels in the angular variable, together with 4096, 8192, and 65536 nonuniform intervals (with p = 2) for q, a, and the exponential factor, respectively.

On every box I_{i} ×I_{j} in the integrand domain and every σ-interval, the program encloses J̃_{∗} away from zero and encloses R_{∗}^{2} and E_{∗}^{2} from above. It therefore bounds the box’s contribution to (123) by

4|I_{i}||I_{j}|\frac{sup_{x∈I_{i}} e^{−x^{2}} sup_{y∈I_{j}} e^{−y^{2}} sup_{(x,y)∈I_{i}×I_{j}} L(x^{2}, y^{2})^{2}}{inf_{x∈I_{i}} J̃_{∗}(x) inf_{y∈I_{j}} J̃_{∗}(y)} ,

where L is either R_{∗} or E_{∗}, and we additionally take a supremum over σ values in the given σ-interval. The identity

C_{∗} − 1 =^{(108)} ∫_{0}^{∞} 2xe^{−x^{2}}(u_{∗}(x^{2}) − 1) dx

is used instead of integrating C_{∗} directly; this preserves the exact cancellation at σ = 0 and makes the interval enclosure uniform down to σ = 1/43. The enclosure for C_{∗} occurs at lines 599, 618 and 621 of the code.

For clarity, we also record the analytic tail bounds. From the ℓ = m = 0 term in (60),

we have I_{0}(a) ≥ 1 for all a ∈ ℝ. Then θ(a) ≤^{(92)} j_{(1)}/(2e) <^{(85)} 1/50 and 0 ≤ u_{0}(t) ≤ ∫_{0}^{∞} R_{0}(t, s)τ(a)dν(s) ≤ 1 by (72) and (99). Also, 0 ≤ j ≤ 1/2 by (71) and ∫_{0}^{1} r_{a}(u)du = 1 with r_{a} ≥ 0 by (69), so 0 ≤ J_{0} ≤ 1/2 by (101). Then 0 ≤ B_{(1)}(t) ≤ 1/50 by (103). Lemma 9.2 then implies

0 ≤ u_{∗}(t) ≤ 1 + \frac{4}{50} = \frac{27}{25},  0 ≤ J_{∗}(t) ≤ \frac{1}{2} + \frac{1}{50} = \frac{13}{25},  0 ≤ C_{∗} ≤^{(108)} \frac{27}{25}.  (125)

The u_{∗} estimate is used in lines 618 and 716 in the code.

We include the integration-by-parts proof of the lower bound needed in the tail estimate. Define

ψ(b) = 1 − \sqrt{π}be^{b^{2}} erfc(b) =^{(119)} ∫_{0}^{∞} 2we^{−w^{2}−2bw} dw,  ∀ b ∈ ℝ.  (126)

Thus F_{v}(x^{2}) = e^{−κx^{2}}ψ(b_{v}(x^{2})) by (119). Since 3v − 1 = − \frac{d}{dv}[v(1 − 3v/2)] and v(1 − 3v/2) vanishes at v = 0 and v = 2/3, integration by parts in (118) gives

J_{0}(x^{2}) = \frac{1}{2} ∫_{0}^{2/3} v(1 − 3v/2)∂_{v}F_{v}(x^{2}) dv, ∀ x ≥ 0.

On 1/2 ≤ v ≤ 2/3 we have b_{v}(x^{2}) ≤ 0 by (116), and differentiating (126) shows that

−ψ′(b_{v}(x^{2})) = ∫_{0}^{∞} 4w^{2}e^{−w^{2}−2b_{v}(x^{2})w} dw ≥ ∫_{0}^{∞} 4w^{2}e^{−w^{2}} dw = \sqrt{π}.

Also, sin(πv) ≥ \sqrt{3}/2 on this interval and for any x ≥ 0,

∂_{v}b_{v}(x^{2}) =^{(116)} −πxq sin(πv) ≤ −\frac{πxq\sqrt{3}}{2}, ∫_{1/2}^{2/3} v(1 − 3v/2) dv = \frac{5}{432}.

∂_{v}F_{v}(x^{2}) = e^{−κx^{2}}ψ′(b_{v}(x^{2}))∂_{v}b_{v}(x^{2}) = e^{−κx^{2}}ψ′(b_{v}(x^{2}))∂_{v}b_{v}(x^{2}) ≥ e^{−κx^{2}} \sqrt{π} \frac{πxq\sqrt{3}}{2}. (127)

The J_{0} integrand is nonnegative on all of [0, 2/3]; restricting it to [1/2, 2/3] therefore proves

J_{∗}(x^{2}) ≥^{(104)} J_{0}(x^{2}) ≥^{(127)} c_{0} \frac{σ}{\sqrt{d}} · xe^{−κx^{2}}, ∀ x ≥ 0,  c_{0} := \frac{5π\sqrt{π}\sqrt{3}}{4 · 432}.  (128)

Moreover,

K_{∗}(x^{2}, y^{2}) ≤ \frac{1 + 4j_{(1)}/(3e)}{d} exp [−κ(x^{2} + y^{2}) + \frac{σ}{d} xy] ,  ∀ x, y ≥ 0.  (129)

Indeed, K_{0} has the same upper bound with 1/d in front of the exponential:

K_{0}(x^{2}, y^{2}) =^{(100)∧(96)} \frac{1}{2d}e^{−(x^{2}+y^{2})σ^{2}/d} ∫_{0}^{2/3}(2 + 3v)e^{−2(σ/d)xy cos(πv)} dv

≤ \frac{1}{2d}e^{−(x^{2}+y^{2})σ^{2}/d}e^{(σ/d)xy} ∫_{0}^{2/3}(2 + 3v) dv = \frac{1}{d}e^{−(x^{2}+y^{2})σ^{2}/d}e^{(σ/d)xy}, ∀ x, y ≥ 0.

4B(x^{2}, y^{2}) =^{(102)} \frac{4j_{(1)}σ}{d^{2}} xye^{−(x^{2}+y^{2})(σ^{2}/d)−2σxy/d} ≤ \frac{4j_{(1)}}{3de} e^{−(x^{2}+y^{2})σ^{2}/d+σxy/d}, ∀ x, y ≥ 0,

using ae^{−(3/2)a} ≤ 2/(3e) ∀ a ≥ 0, with a = 2σxy/d. So, the K_{0} and B bounds prove (129) by (104).

Equations (128)–(129), completion of the square, and Mills’ inequality bound the complement of [0, 5]^{2}. To see this we estimate

∫∫_{[0,∞)^{2}\[0,5]^{2}} e^{−x^{2}−y^{2}} \frac{[K_{∗}(x^{2}, y^{2})]^{2}}{J̃_{∗}(x)J̃_{∗}(y)} dx dy

≤^{(128)∧(129)} \frac{d}{σ^{2}} c_{0}^{−2} \frac{(1 + 4j_{(1)}/(3e))^{2}}{d^{2}} ∫∫_{[0,∞)^{2}\[0,5]^{2}} e^{−x^{2}−y^{2}}e^{−2κ(x^{2}+y^{2})+2σxy/d}e^{κx^{2}}e^{κy^{2}} dx dy

= \frac{(1 + 4j_{(1)}/(3e))^{2}}{σ^{2}dc_{0}^{2}} ∫∫_{[0,∞)^{2}\[0,5]^{2}} e^{−(κ+1)(x^{2}+y^{2})+2σxy/d} dx dy

=^{(115)} \frac{(1 + 4j_{(1)}/(3e))^{2}}{σ^{2}dc_{0}^{2}} ∫∫_{[0,∞)^{2}\[0,5]^{2}} exp (\frac{−x^{2} − y^{2} + 2σxy}{d} ) dx dy

≤ \frac{(1 + 4j_{(1)}/(3e))^{2}}{σ^{2}dc_{0}^{2}} 2 ∫_{5}^{∞} ∫_{0}^{∞} exp ( − \frac{x^{2} + y^{2}}{1 + σ} ) dx dy

≤ \frac{(1 + 4j_{(1)}/(3e))^{2}}{σ^{2}dc_{0}^{2}} \sqrt{π(1 + σ)}\frac{e^{\frac{−5^{2}}{1+σ}} (1 + σ)}{2 · 5} = \frac{(1 + 4j_{(1)}/(3e))^{2}}{σ^{2}dc_{0}^{2}} \frac{\sqrt{π}(1 + σ)^{3/2}e^{− \frac{5^{2}}{1+σ}}}{10} .

(130)

The penultimate inequality used (115) and

\frac{x^{2} + y^{2} − 2σxy}{d} = \frac{(x^{2} + y^{2})(1 − σ) + σ(x − y)^{2}}{d} ≥ \frac{x^{2} + y^{2}}{1 + σ}

Inequality (130) is used at line 701 of the code. By definition of E_{∗} from (110), we have

|E_{∗}(x^{2}, y^{2})|^{2} = |K_{∗}(x^{2}, y^{2}) − u_{∗}(x^{2}) − u_{∗}(y^{2}) + C_{∗}|^{2}

≤ 2|K_{∗}(x^{2}, y^{2})|^{2} + 2(u_{∗}(x^{2}) + u_{∗}(y^{2}) − C_{∗})^{2} ≤^{(125)} 2|K_{∗}(x^{2}, y^{2})|^{2} + 2(81/25)^{2}.

We can then use this inequality to upper bound 4 ∫∫_{[0,∞)^{2}\[0,5]^{2}} e^{−x^{2}−y^{2}} \frac{[E_{∗}(x^{2},y^{2})]^{2}}{J̃_{∗}(x)J̃_{∗}(y)} dx dy in lines 714, 728 and 701 of the code, together with

∫∫_{[0,∞)^{2}\[0,5]^{2}} \frac{e^{−x^{2}−y^{2}} dx dy}{J̃_{∗}(x)J̃_{∗}(y)} ≤ \frac{d}{c_{0}^{2}σ^{2}} 2 ∫_{5}^{∞} ∫_{0}^{∞} e^{−(1−κ)(x^{2}+y^{2})} dx dy ≤ \frac{d\sqrt{π}e^{−(1−κ)·5^{2}}}{10c_{0}^{2}σ^{2}(1 − κ)^{3/2}} , (131)

recalling 1 − κ = (1 − 2σ^{2})/d > 0 by (115) since 0 < σ ≤ 1/2. For an interval range of values of σ, the code estimates a lower bound C_{∗} ≥ c_{lo}. Then by definition of R_{∗} from (109),

|R_{∗}(x^{2}, y^{2})|^{2} = |K_{∗}(x^{2}, y^{2}) − u_{∗}(x^{2})u_{∗}(y^{2})/C_{∗}|^{2} ≤ 2|K_{∗}(x^{2}, y^{2})|^{2} + 2(u_{∗}(x^{2})u_{∗}(y^{2})/C_{∗})^{2}

≤^{(125)} 2|K_{∗}(x^{2}, y^{2})|^{2} + 2 · (27/25)^{4}/(c_{lo})^{2}.

We can then use this inequality to upper bound 4 ∫∫_{[0,∞)^{2}\[0,5]^{2}} e^{−x^{2}−y^{2}} \frac{[R_{∗}(x^{2},y^{2})]^{2}}{J̃_{∗}(x)J̃_{∗}(y)} dx dy in lines 714, 731 and 701 of the code, together with (130) and (131).

These estimates and (124) via (111), (112) are certified by the output of plur_cert.py:

sigma interval                  [0.023255813953, 0.500000000000]
x cutoff / panels              5 / 1000
sigma panels                   640
uniform C_* enclosure          [0.683223606173, 0.994400009077]
upper H^2 finite worst          3.85644837674 on [0.4990318404,0.5000000000]
upper H^2 analytic tail         0.00724743483992
upper H^2 certified             3.86369581158
upper H certified               1.96562860469
lower H^2 finite worst          0.677401054168 on [0.0321787765,0.0325673567]
lower H^2 analytic tail         9.62724411884e-05
lower H^2 certified             0.677497326609
lower H certified               0.823102257687
runtime                         217.83 seconds
CERTIFIED: uniform upper mean-zero H<2 and unrestricted lower H<2.

□

10. MAX-3-CUT Hardness

Proof of Theorem 7.1. Let σ ∈ (0, 1/2]. The case 0 < σ < 1/43 is covered by [Hei23]. So, it suffices to let 1/43 ≤ σ ≤ 1/2. Apply the strengthened inequality (94) for each pair (t, s) of radial variables and integrate in t, s. For (Θ, −Θ), all six radial arc lengths equal b = 1/3, corresponding to 3K_{a}(b, b). Recall that x_{i} := p_{i} − b, y_{i} := q_{i} − b, and p_{i}, q_{i}: (0, ∞) → [0, 1] are defined after (53), for all i = 1, 2, 3, and below ⟨·, ·⟩ denotes the L_{2} inner product on (0, ∞) with respect to the exponential measure ν. Circular rearrangement with (105) gives

Q_{σ}^{(2)}(A, B) − Q_{σ}^{(2)}(Θ, −Θ) ≥ ∑_{i=1}^{3} (⟨x_{i}, K_{∗}y_{i}⟩ + ⟨x_{i}, M_{J_{∗}}x_{i}⟩ + ⟨y_{i}, M_{J_{∗}}y_{i}⟩),  (132)

with K_{∗} defined in (104). For each 1 ≤ i ≤ 3, set z_{i}^{+} := (x_{i} + y_{i})/\sqrt{2} and z_{i}^{−} := (x_{i} − y_{i})/\sqrt{2}. By (54), ∫_{0}^{∞} z_{i}^{−}(r) dν(r) = 0. The self-adjointness of K_{∗} by (104) shows the i-th summand in (132) is

\frac{1}{2}⟨z_{i}^{+}, K_{∗}z_{i}^{+}⟩ − \frac{1}{2}⟨z_{i}^{−}, K_{∗}z_{i}^{−}⟩ + ⟨z_{i}^{+}, M_{J_{∗}}z_{i}^{+}⟩ + ⟨z_{i}^{−}, M_{J_{∗}}z_{i}^{−}⟩.

Equations (113) and (114), together with Lemma 9.3, bound this from below by

(1 − \frac{h_{lower}}{2} ) ⟨z_{i}^{+}, M_{J_{∗}}z_{i}^{+}⟩ + (1 − \frac{h_{upper}}{2} ) ⟨z_{i}^{−}, M_{J_{∗}}z_{i}^{−}⟩ ≥ 0.  (133)

This proves the bilinear inequality (53) since (132) is ≥ 0. Theorem 7.1 follows. □

Remark 10.1. The uniqueness part of Theorem 1.2 follows by checking that, in the above proof, equality implies that p = q = (1/3, 1/3, 1/3) a.e., and then the circular rearrangement argument implies: for almost every r > 0, each set Ω_{i} ∩ rS^{1} is an arc of Haar measure 1/3; and for each 1 ≤ i ≤ 3, the arc’s midpoint does not depend on r, two distinct midpoints differ by an angle of 2π/3. Hence the partition agrees, up to rotation and permutation of the cells, with the standard simplex partition Θ.

Appendix A. Positive correlation Standard Simplex Inequality

In this appendix we prove the three-set Standard Simplex Conjecture for positive correlations in (0, 2/5]. Positive correlation is a maximization problem, so the circular rearrangement uses aligned rather than opposing arcs. We retain the first angular mode separately, just as in the negative-correlation proof, but its contribution now decreases the cross coefficient and increases the diagonal penalty.

Theorem A.1 (positive-correlation Standard Simplex inequality). Let n ≥ 2, let 0 < ρ ≤ 2/5, and let Ω = (Ω_{1}, Ω_{2}, Ω_{3}) be a measurable partition of ℝ^{n} satisfying γ_{n}(Ω_{i}) = \frac{1}{3} ∀ 1 ≤ i ≤ 3. Then

Q_{ρ}^{(n)}(Ω, Ω) ≤ Q_{ρ}^{(2)}(Θ, Θ).  (134)

The interval 0 < ρ < 1/10 is already contained in [Hei23, Theorem 1.5]. We therefore fix

\frac{1}{10} ≤ ρ ≤ \frac{2}{5},  d := 1 − ρ^{2},  κ := \frac{ρ^{2}}{d} .

A.1. Sharpened joint arc inequality. In this section we prove a positive correlation variant of Lemma 8.1.

For any p, q ∈ [0, 1], let E_{p}, E_{q} ⊆ 𝕋 be centered arcs of normalized lengths p, q, and put

L_{a}(p, q) := ∫∫_{E_{p}×E_{q}} \frac{e^{a cos(θ−ϕ)}}{I_{0}(a)} dμ(θ) dμ(ϕ),  a ≥ 0.  (135)

The Fourier calculation leading to (63) gives

L_{a}(p, q) = pq + 2 ∑_{m≥1} \frac{I_{m}(a)}{I_{0}(a)} \frac{sin(πmp) sin(πmq)}{π^{2}m^{2}},  (136)

∂_{pq}L_{a}(p, q) = \frac{e^{a cos(π(p−q))} + e^{a cos(π(p+q))}}{2I_{0}(a)} .  (137)

Recall that b = 1/3 and set

k_{+}(a) := L_{a}(b, b), P_{+}(a) := ∂_{1}L_{a}(b, b),
τ_{+}(a) := 4P_{+}(a) − 3k_{+}(a),  w(a) := 3k_{+}(a) − P_{+}(a).  (138)

Lemma A.2 (aligned-arc bound). For every a ≥ 0 and p, q ∈ Δ_{3}, put x = p − b1 and y = q − b1. Then

∑_{i=1}^{3} L_{a}(p_{i}, q_{i}) − 3L_{a}(b, b) ≤ τ_{+}(a)⟨x, y⟩ − w(a)(∥x∥^{2} + ∥y∥^{2}).  (139)

Moreover, w(a) > 0 when a > 0.

Proof. When a = 0, one has L_{0}(p, q) = pq, τ_{+}(0) = 1, and w(0) = 0, so (139) is an equality. Henceforth assume a > 0. Put

r_{+}(u) := \frac{e^{a cos(πu)}}{I_{0}(a)} .

This function is even, 2-periodic, and decreasing on [0, 1]. Integrating (137), exactly as in (70), gives

P_{+} = \frac{1}{2} ∫_{0}^{2/3} r_{+}(u) du, k_{+} = \frac{1}{2} ∫_{0}^{2/3}(2/3 − u)r_{+}(u) du.

Consequently,

P_{+} − 3k_{+} = \frac{1}{2} ∫_{0}^{2/3}(3u − 1)r_{+}(u) du < 0,

which proves w > 0. The proof of Lemma 8.1 now applies with all monotonicity inequalities reversed. We give the details needed for the reversal. Since ∫_{0}^{1} r_{+}(u) du = 1, the substitution v = 2/3 + 3u^{2}/4 gives

\begin{aligned}τ_{+} & = ∫_{0}^{2/3}(1 + 3u/2)r_{+}(u) du ≥ 1, \\ τ_{+} − 2w & = \frac{9}{2} ∫_{0}^{2/3} ur_{+}(u) du ≥ r_{+}(2/3). \end{aligned}

Indeed, the first inequality is equivalent to

\frac{3}{2} ∫_{0}^{2/3} ur_{+}(u) du ≥ ∫_{2/3}^{1} r_{+}(v) dv,

and after the displayed substitution its left side minus its right side is

\frac{3}{2} ∫_{0}^{2/3} u[r_{+}(u) − r_{+}(2/3 + 3u^{2}/4)] du ≥ 0.

The second inequality follows because (9u/2) du is a probability measure on [0, 2/3] and r_{+} is decreasing. Now set

Φ_{+}(p, q) := L_{a}(p, q) − τ_{+}pq − w(p(1 − p) + q(1 − q)), ∀ p, q ∈ [0, 1].

It is nonpositive on the boundary of [0, 1]^{2}. If G_{+}(δ) := ∫_{0}^{δ} r_{+}(u) du, the first-derivative formulas corresponding to (76)–(77) show that an off-diagonal interior critical point satisfies

G_{+}(δ) = (τ_{+} + 2w)δ.

At such a point,

∂_{(1,−1)}^{2}Φ_{+} = −2 (r_{+}(δ) − \frac{G_{+}(δ)}{δ}) > 0,

because r_{+} is decreasing; hence it cannot be a local maximum. On the diagonal, g_{+}(p) := Φ_{+}(p, p) for all p ∈ [0, 1] satisfies

g_{+}(0) = g_{+}(b) = g′_{+}(b) = 0, g_{+}(1) = 1 − τ_{+} ≤ 0,

and

g′′_{+}(p) = 2(r_{+}(2p) − τ_{+} + 2w).

The set on which g′′_{+} ≤ 0 is an interval [s, 1 − s], and the second inequality above gives s ≤ b. Concavity and g′_{+}(b) = 0 show that g_{+} ≤ g_{+}(b) = 0 on this middle interval. On each complementary interval g_{+} is convex, so it lies below the chord joining its nonpositive endpoint values. Hence g_{+} ≤ 0 on [0, 1]. Thus Φ_{+} ≤ 0 on the square. Summing this scalar inequality over the three coordinates and using the identities at the end of the proof of Lemma 8.1 proves (139). □

We now provide a positive correlation version of Lemma 8.3. Write

H(p, q) := \frac{sin(πp) sin(πq)}{π^{2}}.

Since K^{(1)}(p, q) = pq − H(p, q) by (86), the first-mode inequality (89) implies

∑_{i=1}^{3}(p_{i}q_{i} + H(p_{i}, q_{i})) − 3(b^{2} + H(b, b)) ≤ (2 − τ_{(1)} − 2j_{(1)})⟨x, y⟩ − \frac{3}{2}j_{(1)}(∥x∥^{2} + ∥y∥^{2}). (140)

Indeed, subtract (89) from 2 ∑_{i=1}^{3} p_{i}q_{i} − 6b^{2} = 2⟨x, y⟩.

Define θ(a) as in (92). The exact decomposition

\frac{e^{a cos(πu)}}{I_{0}(a)} = \frac{e^{−a}}{I_{0}(a)}(1 + a(1 + cos(πu))) + r_{+,rem}(u)  (141)

has

r_{+,rem}(u) = \frac{e^{−a}}{I_{0}(a)} [e^{a(1+cos(πu))} − 1 − a(1 + cos(πu))] .

The remainder is nonnegative and decreasing on [0, 1]. Apply Lemma A.2 homogeneously to the constant and remainder terms in (141), and apply (140) to 1 + cos(πu). By linearity we get the following improvement to Lemma A.2:

Corollary A.3 (sharpened aligned-arc bound). For every a ≥ 0 and p, q ∈ Δ_{3},

∑_{i=1}^{3} L_{a}(p_{i}, q_{i}) − 3L_{a}(b, b) ≤ (τ_{+}(a) − 4θ(a))⟨x, y⟩ − (w(a) + θ(a))(∥x∥^{2} + ∥y∥^{2}). (142)

A.2. Positive radial operator. Define R_{0} as in (98). Put a(t, s) = 2ρ\sqrt{ts}/d. Define

K_{0,+}(t, s) := R_{0}(t, s)τ_{+}(a(t, s)) = \frac{e^{−κ(t+s)}}{2d} ∫_{0}^{2/3}(2 + 3v)e^{a(t,s) cos(πv)} dv,  (143)
W_{0}(t) := ∫_{0}^{∞} R_{0}(t, s)w(a(t, s)) dν(s).  (144)

Use the same first-mode kernel B and its marginal B_{(1)} from (102)–(103), with σ replaced by ρ, and set

K_{+}(t, s) := K_{0,+}(t, s) − 4B(t, s),  J_{+}(t) := W_{0}(t) + B_{(1)}(t).  (145)

Integrating (142) in the two radial variables therefore produces

∑_{i=1}^{3} (⟨x_{i}, K_{+}x_{i}⟩ − 2⟨x_{i}, M_{J_{+}}x_{i}⟩),  (146)

where K_{+} has kernel K_{+}.

We now record the formulas used by the verification code. Put

q = \frac{ρx}{\sqrt{d}}, ψ(z) = 1 − \sqrt{π}ze^{z^{2}} erfc(z),

S(q) := −ψ′(q) = \sqrt{π}(1 + 2q^{2})e^{q^{2}} erfc(q) − 2q,

H_{+}(q) := \frac{π}{2} ∫_{0}^{2/3} v(1 − 3v/2) sin(πv)[−ψ′(−q cos(πv))] dv.  (147)

Integration by parts in (144), followed by (121), gives

J̃_{+}(x) := \frac{J_{+}(x^{2})}{x} = e^{−κx^{2}} \frac{ρ}{\sqrt{d}} [H_{+}(q) + \frac{j_{(1)}}{2} S(q)] .  (148)

Also, if

T_{+}(a) := \frac{1}{2} ∫_{0}^{2/3}(2 + 3v)e^{a cos(πv)} dv,

then

K_{+}(x^{2}, y^{2}) = \frac{e^{−κ(x^{2}+y^{2})}}{d} [T_{+}(\frac{2ρxy}{d} ) − 2j_{(1)} \frac{2ρxy}{d} e^{−2ρxy/d}] .  (149)

For a function ℓ_{ρ}, additive centering does not change the quadratic form on the mean-zero subspace. We use

ℓ_{ρ}(x) = ∑_{n=0}^{4} c_{n}(ρ)x^{n},  c_{n}(ρ) = ∑_{m=0}^{4} C_{nm}ρ^{m},  (150)

where C is the binary64 matrix obtained by parsing the following round-trip decimal strings:

(\begin{matrix}.5001276609531384 & −.04839192730072833 & .3420752274381793 & −.02840693452661011 & .3929215251696178 \\ .0020711604332492072 & .11278766504365427 & .42921652164107776 & −1.4633497642462785 & 2.392753763954644 \\ −.00657914712574693 & .1533613436474771 & −1.6052209990260096 & 4.917034579755538 & −7.5025494501524435 \\ .00509284321106939 & −.11817713264541818 & .9939294369107601 & −4.02653695935449 & 4.798761639440846 \\ −.00111590812093279 & .02578645463758624 & −.21531279149872498 & .776584990984738 & −.6977289068083498 \end{matrix}) .

These numbers merely specify an additive center; no approximation property of them is assumed. Set

𝔥_{+}^{2}(ρ) = 4 ∫_{0}^{∞} ∫_{0}^{∞} e^{−x^{2}−y^{2}} \frac{[K_{+}(x^{2}, y^{2}) − ℓ_{ρ}(x) − ℓ_{ρ}(y)]^{2}}{J̃_{+}(x)J̃_{+}(y)} dx dy.  (151)

The weighted Hilbert–Schmidt argument (106) gives, for every bounded z with ∫ z dν = 0,

⟨z, K_{+}z⟩ ≤ 𝔥_{+}(ρ)⟨z, M_{J_{+}}z⟩.  (152)

Lemma A.4 (uniform directed positive certificate). Uniformly for all 1/10 ≤ ρ ≤ 2/5,

𝔥_{+}^{2}(ρ) < 3.9993, 𝔥_{+}(ρ) < 1.99983 < 2.

Proof. The program plur_cert_positive.py uses Arb balls for all transcendental tables and outward-rounded binary64 interval arithmetic for the remaining operations. It uses 64 second-order midpoint panels in the angular variable, 4096 nonuniform q-intervals, 16384 nonuniform a-intervals, and 65536 nonuniform exponential intervals. Here the nonuniform intervals [q_{i}, q_{i+1}] use q_{i} = q_{max}(i/4096)^{2} for each 0 ≤ i ≤ 4096. The intervals for a and the exponential function z ↦ e^{−z} are constructed similarly. More specifically, q_{max} = \frac{(2/5)7}{\sqrt{1−(2/5)^{2}}} ,

a_{max} = \frac{2(2/5)7^{2}}{1−(2/5)^{2}} , z_{max} = 49. The auxiliary meshes are q_{i} = q_{max}(i/4096)^{2}, a_{i} = a_{max}(i/16384)^{2}, z_{i} = z_{max}(i/65536)^{2}. The square 0 ≤ x, y ≤ 7 is divided into 1600 radial panels in each coordinate. The correlation ρ intervals begin with 30 uniform intervals of width .01 in [.1, .4]. If a slab does not certify 𝔥_{+}^{2}(ρ) < 4, it is bisected dyadically until the upper bound is below 4.

For completeness, we give the analytic tails. Integration by parts in (147), followed by restriction to 0 ≤ v ≤ 1/2, gives

J̃_{+}(x) ≥ c_{+} \frac{ρ}{\sqrt{d}}e^{−κx^{2}},  c_{+} := \frac{6 − π}{4π^{3/2}} .  (153)

Indeed, −ψ′(−q cos(πv)) ≥ \sqrt{π} on this interval and

∫_{0}^{1/2} v(1 − 3v/2) sin(πv) dv = \frac{6 − π}{2π^{3}} .

Moreover, ae^{−a} ≤ 1/e and cos(πv) ≤ 1 give

|K_{+}(x^{2}, y^{2})| ≤ \frac{1 + 2j_{(1)}/e}{d}e^{−κ(x^{2}+y^{2})+(2ρ/d)xy}.  (154)

After division by the two factors in (153), the squared-kernel tail has exponential factor

exp [−\frac{x^{2} + y^{2} − 4ρxy}{d} ] .

Since ρ < 1/2,

\frac{x^{2} + y^{2} − 4ρxy}{d} = \frac{(y − 2ρx)^{2}}{d} + \frac{1 − 4ρ^{2}}{d} x^{2}.

Extending the inner half-line to ℝ, using the union bound, and then Mills’ inequality controls the complement of [0, 7]^{2}. The additive tails follow from (150),

ℓ_{ρ}(x)^{2} ≤ 5 ∑_{n=0}^{4} c_{n}(ρ)^{2}x^{2n},

and the elementary Gaussian moment recurrence. The certification output is

rho interval                    [0.100000000000, 0.400000000000]
x cutoff / panels              7 / 1600
initial rho panels             30
accepted rho slabs             90
total slab attempts            150
H_+^2 finite worst              3.99929063236 on [0.3862500000,0.3875000000]
H_+^2 kernel tail               3.33733813468e-07
H_+^2 additive tail             3.03117401848e-12
H_+^2 certified                 3.99929096609
H_+ certified                   1.99982273367
runtime                         141.11 seconds
CERTIFIED: uniform positive mean-zero H_+<2.

This proves the lemma. □

Proof of Theorem A.1. The case 0 < ρ < 1/10 was proven in [Hei23], so it suffices to consider 1/10 ≤ ρ ≤ 2/5. The positive-correlation dimension-reduction theorem of Heilman– Tarter [HT21], together with the cylinder embedding, reduces the supremum to the planar problem. Recall that x_{i} := p_{i} − b and p_{i}: (0, ∞) → [0, 1] are defined after (53), for all i = 1, 2, 3, and below ⟨·, ·⟩ denotes the L_{2} inner product on (0, ∞) with respect to the exponential measure ν. The assumed condition γ_{2}(A_{i}) = 1/3 for all i = 1, 2, 3 implies

∫_{0}^{∞} x_{i}(t) dν(t) = 0, i = 1, 2, 3.

Circular rearrangement bounds each conditional self-overlap from above by aligned circular arcs. Applying Corollary A.3 and integrating in the two radial variables gives

Q_{ρ}^{(2)}(A, A) − Q_{ρ}^{(2)}(Θ, Θ) ≤ ∑_{i=1}^{3} (⟨x_{i}, K_{+}x_{i}⟩ − 2⟨x_{i}, M_{J_{+}}x_{i}⟩).

Equation (152) and Lemma A.4 bound the right side by

(𝔥_{+}(ρ) − 2) ∑_{i=1}^{3}⟨x_{i}, M_{J_{+}}x_{i}⟩ ≤ 0.

This proves (134). □

Appendix B. MAX-2-LIN(3) Hardness

Proof of Theorem 1.5. The PCP verifier of [KKMO07, Theorem 12 and page 35], with correlation parameter ρ, has completeness

c(ρ) = ρ + \frac{1 − ρ}{3} = \frac{1 + 2ρ}{3}.

Moreover, additive folding [KKMO07, Definition 22] makes each function arising in the soundness analysis balanced. The positive-correlation Plurality Is Stablest Theorem 1.3 and the invariance principle [MOO10] therefore bound the soundness by

Stab_{ρ}(Plur_{3}) + o(1),

where the three-candidate plurality stability is

Stab_{ρ}(Plur_{3}) = \frac{1}{3} + \frac{3}{4π^{2}} (arccos(−ρ)^{2} − arccos(ρ/2)^{2}) .

Taking ρ = 2/5 gives c(2/5) = 3/5 and

Stab_{2/5}(Plur_{3}) = 0.489434116402967 ….

Absorbing the invariance-principle and reduction errors into ε gives the asserted gap. Dividing the soundness by the completeness gives

\frac{Stab_{2/5}(Plur_{3})}{3/5} = 0.815723527338279 …,

as claimed. □

Acknowledgements. Thanks to Elchanan Mossel for introducing me to the Plurality is Stablest Problem at MSRI (now SLMath) in 2011, and for helpful conversations over the years. Thanks to Assaf Naor for helpful conversations over the years. Thanks to Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson, and John Wright for helpful discussions.

ChatGPT 5.6 assisted in the preparation of this manuscript, including producing the spectral certificates in Propositions 4.1 and 4.4 and Lemmas 9.3 and A.4.

References

[AAV13] Dorit Aharonov, Itai Arad, and Thomas Vidick. The Quantum PCP conjecture. ACM SIGACT News (2013), 44 (2) pp. 47–79.

[ALM+25] Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud. Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings. Preprint (2025), arXiv:2504.15276.

[ALM+98] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM (1998). 45 (3), pp. 501–555.

[AS98] Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM (1998). 45 (1), pp. 70–122.

[AOTW14] Per Austrin, Ryan O’Donnell, Li Yang Tan, and John Wright. New NP-hardness results for 3-Coloring and 2-to-1 Label Cover. ACM Transactions on Computation Theory (2014). 6 (1), pp. 2:1–2:20.

[BT76] Alfred Baernstein II and B. Alan Taylor, Spherical rearrangements, subharmonic functions, and ∗-functions in n-space, Duke Mathematical Journal (1976). 43 (2), pp. 245–268.

[BBKL26] Ainesh Bakshi, Arpon Basu, Pravesh Kothari, and Anqi Li. Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut. Preprint (2026), arXiv:2605.14994.

[BGS98] Mihir Bellare, Oded Goldreich, and Madhu Sudan. Free Bits, PCPs, and Nonapproximability—Towards Tight Results. SIAM Journal on Computing (1998). 27 (3), pp. 804–915.

[BMVZ25] Thiago Bergamaschi, Tony Metger, Thomas Vidick, and Tina Zhang. Derandomised tensor product gap amplification for quantum Hamiltonians. Preprint (2025), arXiv:2510.01333.

[Bob97] Sergei Bobkov. An isoperimetric inequality on the discrete cube, and an elementary proof of the isoperimetric inequality in Gauss space. Annals of Probability (1997). 25 (1), pp. 206–214.

[Bor85] Christer Borell. Geometric bounds on the Ornstein-Uhlenbeck velocity process. Probability Theory and Related Fields (1985). 70 (1), pp. 1–13.

[BHZ24] Joshua Brakensiek, Neng Huang, and Uri Zwick. Tight approximability of MAX 2-SAT and relatives, under UGC. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (2024). pp. 1328–1344.

[BOV14] Jop Briët, Fernando Mário de Oliveira Filho, and Frank Vallentin. Grothendieck inequalities for semidefinite programs with rank constraint. Theory of Computing (2014). 10, pp. 77–105.

[BS01] Almut Burchard and Michael Schmuckenschläger. Comparison theorems for exit times. Geometric & Functional Analysis (2001). 11 (4), pp. 651–692.

[CJK+23] Charlie Carlson, Zackary Jorquera, Alexandra Kolla, Steven Kordonowy, and Stuart Wayland. Approximation Algorithms for Quantum Max-d-Cut. Preprint (2023), arXiv:2309.10957.

[Cha06] Sourav Chatterjee. A generalization of the Lindeberg principle. Annals of Probability (2006). 34 (6), pp. 2061–2076.

[CST01] Pierluigi Crescenzi, Riccardo Silvestri, and Luca Trevisan. On Weighted vs Unweighted Versions of Combinatorial Optimization Problems. Information and Computation (2001). 167 (1), pp. 10–26.

[CM16] Toby Cubitt and Ashley Montanaro. Complexity classification of local Hamiltonian problems. SIAM Journal on Computing (2016). 45 (2), pp. 268–316.

[DS14] Irit Dinur and David Steurer. Analytical approach to parallel repetition. ACM symposium on Theory of computing (2014). pp. 624–633.

[Eld15] Ronen Eldan. A two-sided estimate for the gaussian noise stability deficit. Inventiones mathematicae (2015). 201 (2), pp. 561–624.

[Fei98] Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM (1998). 45 (4), pp. 634–652.

[FS02] Uriel Feige and Gideon Schechtman. On the optimality of the random hyperplane rounding technique for MAX CUT. Random Structures & Algorithms (2002). 20 (3), pp. 403–440.

[FJ97] Alan Frieze and Mark Jerrum, Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica (1997). 18, pp. 67–81.

[GP19] Sevag Gharibian and Ojas Parekh. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (2019).

[GW95] Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (1995). 42 (6), pp. 1115–1145.

[GS13] Venkatesan Guruswami and Ali Kemal Sinop. Improved inapproximability results for Maximum k-Colorable Subgraph. Theory of Computing (2013). 9 (11), pp. 413–435.

[Hås01] Johan Håstad. Some optimal inapproximability results. Journal of the ACM (2001). 48

(4), pp. 798–859.

[Hei22] Steven Heilman, Hyperstable Sets with Voting and Algorithmic Hardness Applications, Preprint (2022), arXiv:2209.11216.

[Hei23] Steven Heilman, Three Candidate Plurality is Stablest for Correlations at most 1/10, Preprint (2023), arXiv:2306.03312.

[Hei25] Steven Heilman. Sphere valued noise stability and quantum MAX-CUT hardness. Annals of Probability (2025). 53 (4), pp. 1197–1222.

[HMN16] Steven Heilman, Elchanan Mossel, and Joe Neeman. Standard simplices and pluralities are not the most noise stable. Israel Journal of Mathematics, (2016). 213 (1), pp. 33–53.

[HT21] Steven Heilman and Alex Tarter. Three candidate plurality is stablest for small correlations, Forum of Mathematics, Sigma (2021). 9, e65.

[Hei28] Werner Heisenberg. Zur Theorie des Ferromagnetismus. Zeitschrift für Physik (1928). 49 (9–10), pp. 619–636.

[HS85] Dorit S. Hochbaum, David B. Shmoys. A Best Possible Heuristic for the k-Center Problem. Mathematics of Operations Research (1985). 10 (2), pp. 180–184.

[HNP+23] Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson, and John Wright. Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell’s inequality. In Proceedings of the Annual ACM–SIAM Symposium on Discrete Algorithms (2023). pp. 1319–1384.

[IM12] Marcus Isaksson and Elchanan Mossel, Maximally stable Gaussian partitions with discrete applications, Israel Journal of Mathematics (2012). 189, pp. 347–396.

[KKLP97] Viggo Kann, Sanjeev Khanna, Jens Lagergren, and Alessandro Panconesi. On the hardness of approximating MAX k-CUT and its dual. Chicago Journal of Theoretical Computer Science (1997). 2, pp. 1–18.

[Kar72] Richard M. Karp. Reducibility among Combinatorial Problems. Symposium on Complexity of Computer Computations (1972). pp. 85–103.

[Kho02] Subhash Khot. On the power of unique 2-prover 1-round games. Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (2002). pp. 767–775.

[KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell, Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?, SIAM Journal on Computing (2007). 37 (1), pp. 319–357.

[KR08] Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2 − ε. Journal of Computer and System Sciences (2008). 74 (3), pp. 335–349.

[KN10] Subhash Khot. On the unique games conjecture. Annual IEEE Conference on Computational Complexity (2010). pp. 99–121.

[KN13] Subhash Khot and Assaf Naor. Sharp kernel clustering algorithms and their associated Grothendieck inequalities. Random Structures and Algorithms (2013). 42 (3), pp. 269–300.

[KMS23] Subhash Khot, Dor Minzer, and Muli Safra. Pseudorandom sets in Grassmann graph have near-perfect expansion. Annals of Mathematics (2023). 198 (1), pp. 1–92.

[Led94] Michel Ledoux. Semigroup proofs of the isoperimetric inequality in Euclidean and Gauss space. Bull. Sci. Math. (1994). 118 (6), pp. 485–510.

[MN15] Elchanan Mossel and Joe Neeman. Robust optimality of Gaussian noise stability. Journal of the European Mathematics Society (2015). 17 (2), pp. 433–482.

[MOO10] Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. Annals of Mathematics (2010). 171 (1), pp. 295–341.

[NRT25] Ansh Nagda, Prabhakar Raghavan, and Abhradeep Thakurta. Reinforced generation of combinatorial structures: Hardness of approximation. Preprint (2025), arXiv:2509.18057.

[Olv10] F. W. J. Olver (Editor in Chief), D. W. Lozier, R. F. Boisvert, and C. W. Clark. NIST Handbook of Mathematical Functions, Cambridge University Press (2010), New York.

[PY91] Christos Papadimitriou and Mihalis Yannakakis. Optimization, approximation, and complexity classes. Journal of Computing and System Sciences (1991). 43, pp. 425–440.

[PM17] Stephen Piddock and Ashley Montanaro. The complexity of antiferromagnetic interactions and 2D lattices. Quantum Information and Computation (2017). 17 (7-8), pp. 636–672.

[Pid25] Stephen Piddock. Quantum Max-Cut is NP hard to approximate. Preprint (2025), arXiv:2510.07995.

[Rag08] Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP?. Proceedings of the annual ACM symposium on Theory of computing (2008). pp. 245–254.

[RS09] Prasad Raghavendra and David Steurer. Towards Computing the Grothendieck Constant. Symposium on Discrete Algorithms (2009). pp. 525–534.

[Rot79] V. I. Rotar’. Limit theorems for polylinear forms. Journal of Multivariate Analysis. 9 (4), pp. 511–530, 1979.

[SG76] Sartaj Sahni and Teofilo Gonzalez. P-complete approximation problems. Journal of the ACM (1976). 23, pp. 555–565.

[TSSW00] Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, and David P. Williamson. Gadgets, approximation, and linear programming. SIAM Journal on Computing (2000). 29 (6), pp. 2074–2097.