A LOWER BOUND FOR GROTHENDIECK’S CONSTANT

STEVEN HEILMAN

Abstract. We show that Grothendieck’s real constant K_{G} satisfies K_{G} ≥ c + 10^{−26}, improving on the lower bound of c = 1.676956674215576 … of Davie and Reeds from 1984 and 1991, respectively.

1. Introduction

Grothendieck’s real constant K_{G} is the infimum over all K ∈ (0, ∞) such that, for all positive integers m, n and for every real m × n matrix (a_{ij}), we have

max_{\begin{matrix}x_{1},...,x_{m} \\ y_{1},...,y_{n} \end{matrix}∈S^{m+n−1}} ∑_{i=1}^{m} ∑_{j=1}^{n} a_{ij}⟨x_{i}, y_{j}⟩ ≤ K · max_{\begin{matrix}ε_{1},...,ε_{m} \\ δ_{1},...,δ_{n} \end{matrix}∈\{−1,1\}} ∑_{i=1}^{m} ∑_{j=1}^{n} a_{ij}ε_{i}δ_{j},  (1)

where ⟨x, y⟩ = ∑_{i=1}^{d} x_{i}y_{i} for all x, y ∈ ℝ^{d} and S^{d−1} = {x ∈ ℝ^{d}: ⟨x, x⟩ = 1} for any d ≥ 1.

Inequality (1) was originally stated as an inequality of two different tensor norms [G53] (see also [P12, Section 3]), though the discretized formulation (1) was proven in [LP68].

Determining the exact value of K_{G} remains a significant open problem since it was first posited in [G53]. We can rephrase the problem of finding the constant K_{G} as: what is the “best” way to “round” the vectors x_{1}, …, x_{m}, y_{1}, …, y_{n} to ±1? There are many good references on (1), and its interest in combinatorics, functional analysis, Banach space theory, operator algebras and the Connes embedding problem, theoretical computer science, quantum mechanics, etc. such as [P12, KN12]. We briefly mention some interpretations of Grothendieck’s constant in quantum information and theoretical computer science:

• Grothendieck’s constant is the maximal quantum violation in Bell’s inequality from quantum mechanics [T87]. That is, Grothendieck’s inequality is a reformulated version of Bell’s inequality.

• Assuming the Unique Games Conjecture [K02], it is NP-hard to approximate the right side of (1) within any constant smaller than Grothendieck’s constant K_{G} [RS09]. The left side of (1) is a semidefinite program which can be computed efficiently, while the right side is an integer program. So, (1) itself efficiently approximates the right side of (1) using its left side, within a constant factor K_{G} [AN04]. The cut norm and the MAX-CUT problem are special cases of the right side of (1) [AN04].

Date: March 23, 2026.

Email: stevenmheilman@gmail.com Supported by NSF Grant CCF 2448108 Department of Mathematics, University of Southern California, Los Angeles, CA 90089 MSC 2020 Classification: 15A60, 15A45, 90C27, 90C22, 42C10, 68Q17 Keywords: Grothendieck inequality, Grothendieck constant, Rounding schemes, Semidefinite programming, inequalities, computational complexity.

1.1. Upper Bounds on K_{G}. [G53] originally proved that K_{G} ≤ sinh(π/2) ≈ 2.3013. In [K77], Krivine showed that K_{G} ≤ \frac{π}{2 log(1+\sqrt{2})} ≈ 1.78221397819, and it was generally believed that this inequality should be an equality [K01]. However, it was then shown in [BMMN13] that there is a c′ > 0 such that

K_{G} < \frac{π}{2 log(1 + \sqrt{2})} − c′.

An effective c′ was proven but not specified in [BMMN13]; an inspection of the argument seems to give c′ = 10^{−500}. Krivine’s argument [K77] shows that, after “preprocessing” the vectors x_{1}, …, x_{m}, y_{1}, …, y_{n} by nonlinearly mapping them to a different Hilbert space (Fock space), we can then map those vectors to ±1 by projecting them onto a Gaussian random vector, and taking the sign of this projected value. (The nonlinear preprocessing removes the nonlinearity that appears after projecting onto the Gaussian.) The argument of [BMMN13] instead projects the preprocessed vectors onto a random plane through the origin, and then (with probability 0 < p < 1) applies a perturbation of the sign function on this two-dimensional plane to “round” the vectors to ±1 (and with probability 1 − p applies the sign function). Also, rounding schemes of this form can obtain arbitrarily good approximations of K_{G} [RN14]. In other words, finding the exact value of K_{G} reduces to finding the best “rounding scheme” for vectors x_{1}, …, x_{m}, y_{1}, …, y_{n} in (1).

In contrast to these upper bounds, lower bounds for K_{G} result from finding a matrix where the ratio of both sides of (1) is far from 1.

1.2. Lower Bounds on K_{G}. It was shown in [G53] that, if we add the restriction in (1) that (a_{ij}) is symmetric positive semidefinite, then the best constant in (1) becomes equal to π/2 ≈ 1.57079632679. Consequently, K_{G} ≥ π/2. Achieving better lower bounds on K_{G} therefore requires considering matrices that are not symmetric positive semidefinite (such as the infinite-dimensional matrix R_{λ} in (3)). Independently of each other, [R91] and [D84] showed (using (3)) that

K_{G} ≥ 1.676956674215576237077855078853 …  (2)

While the upper bound of π/(2 log(1 + \sqrt{2})) was previously believed to be an equality [K77], the lower bound (2) was not believed to be an equality. Nevertheless, no better lower bound has been described in the literature since 1984.

1.3. Brief Review of the Existing Lower Bound. To prove (2), [R91] and [D84] consider the following linear operator for some fixed 0 < λ < 1.

R_{λ} := P_{1} − λI  (3)

on the Hilbert space L_{2}(γ_{n}) = {f: ℝ^{n} → ℝ: ∫_{ℝ^{n}} |f(x)|^{2}γ_{n}(x)dx < ∞}, where I is the identity map (note that R_{λ} is not positive definite),

γ_{n}(x) := (2π)^{−n/2}e^{− \frac{1}{2} ∥x∥_{ℓ_{2}(ℝ^{n})}^{2}}, ∀ x ∈ ℝ^{n}.

and P_{1} is the projection onto the level one Hermite-Fourier coefficients, i.e.

P_{1}f(x) := ∫_{ℝ^{n}}⟨x, y⟩f(y)γ_{n}(y)dy,  ∀ x ∈ ℝ^{n}, ∀ f ∈ L_{2}(γ_{n}).  (4)

Then, interpreting R_{λ} as an infinite-dimensional matrix in (1), Davie and Reeds obtain

K_{G} ≥ sup_{n≥1} sup_{λ>0} \frac{sup_{g: ℝ^{n}→B_{n}} ∫_{ℝ^{n}} ∥R_{λ}g(x)∥_{ℓ_{2}(ℝ^{n})}γ_{n}(x)dx}{sup_{f: ℝ^{n}→[−1,1]} ∫_{ℝ^{n}} |R_{λ}f(x)|γ_{n}(x)dx},  (5)

where ∥x∥_{ℓ_{2}(ℝ^{n})} := ⟨x, x⟩^{1/2} for all x ∈ ℝ^{n} and B_{n} := {x ∈ ℝ^{n}: ∥x∥_{ℓ_{2}(ℝ^{n})} ≤ 1}. (The equivalence of (1) to a ratio of operator norms of maps from L_{∞} to L_{1} as in (5) is shown e.g. in the introduction of [R91] or [P12, Theorem 2.5])

They then show that, as n → ∞, the numerator of (5) converges to 1−λ (which can be seen by considering the function g(x) = x/∥x∥), and the denominator is (λ/η)^{2} + λ(1 − 4Φ(−η)), where η ∈ (0, 1) satisfies \sqrt{\frac{2}{π}}ηe^{−η^{2}/2} = λ. Choosing the optimal λ which is

λ_{∗} ≈ 0.1974790909949819604066867498464070553745 …

then yields

K_{G} ≥^{(5)} \frac{1 − λ_{∗}}{(λ_{∗}/η_{∗})^{2} + λ_{∗}(1 − 4Φ(−η_{∗}))} ≈ 1.676956674215576237077855078853 …,

where Φ(t) := ∫_{−∞}^{t} e^{−z^{2}/2}dz/\sqrt{2π}, ∀ t ∈ ℝ and η_{∗} ∈ (0, 1) satisfies \sqrt{\frac{2}{π}}η_{∗}e^{−η_{∗}^{2}/2} = λ_{∗}. (We mention in passing that choosing λ = 0 recovers the weaker bound K_{G} ≥ π/2.)

It is natural to try to consider further perturbations of R_{λ} by e.g. adding some multiples of P_{j}, where P_{j} is the projection onto level j Hermite-Fourier coefficients, and then use (5) for such a perturbation of R_{λ}. The main difficulty then becomes computing the denominator of (5) for the perturbation of R_{λ}. That is, we want to find some perturbation of R_{λ} such that the numerator of (5) is the same (1 − λ as n → ∞), but the denominator is slightly smaller.

Concerning this strategy, Reeds [R91] comments:

“It would be interesting to attempt the direct computation of the norm of some more general operator ∑_{j} α_{j}P_{j}, where the α_{j} are not all of the same sign, but the methods of this paper probably do not extend beyond the case where only one of the α_{j} is positive.”

1.4. Our Contribution. We find that, in fact, the operator of Reeds can be perturbed slightly into the form

R_{λ,β} = P_{1} − λI − βP_{3}.  (6)

so that (5) implies an improved lower bound on K_{G}.

Theorem 1.1 (Main).

K_{G} ≥ 10^{−26} + c.

Here c = 1.676956674215576237077855078853 … is the lower bound proven by [D84, R91]. Instead of exactly computing the norm of R_{λ,β} (which could be difficult since functions

achieving the operator norm should have a “high-dimensional” structure, unlike the case β = 0 where the optimizing functions have a “one-dimensional” structure), we instead indirectly estimate the operator norm of R_{λ,β}.

The argument proceeds by a simple perturbation, together with a characterization of the maximizers of R_{λ}, which is already apparent from [R91]. Let M be the set of measurable functions f: ℝ^{n} → [−1, 1] that are maximizers of ∥R_{λ}f∥_{1}. (From Lemma 4.1, all such maximizers take values in {−1, 1} almost surely.) Theorem 1.1 follows from the following:

(a) There is some ε > 0 such that, if f is within L_{1}(γ_{n}) distance ε from M, then for all 0 < β < 10^{−10}, ∥R_{λ,β}f∥_{1} ≤ ∥R_{λ}∥_{∞→1} − (.0057)β. (And ε = 10^{−7} suffices.)

(b) If f has L_{1}(γ_{n}) distance at least ε from M, then ∥R_{λ,β}f∥_{1} ≤ ∥R_{λ}∥_{∞→1} − ε^{2}10^{−12} + β. Here ∥R_{λ}∥_{∞→1} := sup_{g: ℝ^{n}→[−1,1]} ∫_{ℝ^{n}} |R_{λ}g(x)|γ_{n}(x)dx. It is crucial in (a) that ε > 0 is fixed, i.e. that there is a fixed ε that works for all small β > 0.

Combining (a) and (b) means, for β small enough,

∥R_{λ,β}∥_{∞→1} ≤ max(∥R_{λ}∥_{∞→1} − (.0057)β, ∥R_{λ}∥_{∞→1} − ε^{2}10^{−12} + β) < ∥R_{λ}∥_{∞→1}.

The strict inequality follows by choosing β < 10^{−12}ε^{2}. Theorem 1.1 follows. (We have presented Case (b) here informally for illustrative purposes; for the actual statement that we prove, we split into a few different cases, such as (95) and (98), culminating in (103).)

Most of our arguments use elementary inequalities. Our main innovation is our strategy which reduces much of the problem to one-dimensional Gaussian analytic inequalities, by not directly considering maximizers of ∥R_{λ,β}∥_{∞→1}. Since our goal is to provide an explicit constant in Theorem 1.1, this unfortunately increases the length of the paper.

1.5. Technical Challenges. One difficulty of part (a) of the strategy for proving Theorem 1.1 is that the set of maximizers M is infinite. The set M can be characterized using the argument of Reeds [R91] (see Lemma 2.1), but we require our operator norm estimate for R_{λ,β} to hold uniformly over all elements of (a neighborhood of) the infinite set M.

The main difficulty with part (b) of our strategy for Theorem 1.1 is that modulus of continuity estimates for R_{λ,β} are most naturally stated in terms of the L_{1} norm of functions f on ℝ^{n}, whereas modulus of continuity estimates for R_{λ} are most naturally stated in terms of the L_{1} norm of the (one-dimensional) conditional expectation 𝔼(f|P_{1}f). The first notion of closeness implies the second, but the second might not imply the first. In order to connect these two different estimates, we then need to show: if 𝔼(f|P_{1}f) is close to {𝔼(g|P_{1}g): g ∈ M} in L_{1} norm (on ℝ), then f is close to M in L_{1} norm (on ℝ^{n}). However, the most natural way to prove this statement fails since these two norms are incomparable. If g is the closest element to f in M, then 𝔼(g|P_{1}g) and 𝔼(f|P_{1}f) could a priori be close or far in L_{1} norm, since the moment vectors ∫_{ℝ^{n}} xf(x)γ_{n}(x)dx and ∫_{ℝ^{n}} xg(x)γ_{n}(x)dx might not be parallel. Since we want to maintain explicit constants, one cannot simply rotate g so that its moment vector is parallel to f and hope that the rotation is still close to f. To circumvent this issue, we instead explicitly construct a function h that is close to f in L_{1} norm, with h satisfying the conditions of M except it takes values in [−1, 1], and from that we infer there is some g ∈ M closer to f in L_{1} norm (so that |g| = 1). This strategy avoids reasoning about the closest g ∈ M.

1.6. Organization. We prove (a) above in several steps of increasing generality. After reviewing the argument of Reeds in Section 2, we then prove the ε = 0, n = 1 case of (a). Then (a) is proven in (60), using a uniform third moment bound from Section 5 together with some stability estimates in Section 6. That is, a more formal statement of (a) is (60).

We then move on to proving (b) in Section 7. This is proven by some one-dimensional triangle inequalities and rearrangement arguments in Sections 7, 8 and 9, together with Lemma 4.2. Then (b) is proven in Case 2 of the proof of Theorem 1.1 in Section 10.

Section 10 proves Theorem 1.1 by combining (a) and (b).

1.7. Conclusions and Future Directions. The main contribution of this paper is to demonstrate that the previous best lower bounds on Grothendieck’s constant from 1984 can be improved, by modifying a method of proof that was viewed skeptically in [R91]. Instead of explicitly computing the operator norm of R_{λ,β}, we instead approximate it by proving one estimate for a neighborhood of the maximizers of R_{λ}, and another estimate for functions outside this neighborhood. Computing the operator norm of R_{λ,β} directly seems more difficult (as [R91] expresses), since these optimizers should be “high-dimensional,” whereas optimizers of R_{λ} are “one-dimensional.” However, it would be interesting to more accurately compute the ∞ → 1 norm of R_{λ,β}, since we only approximate it using upper bounds that are probably far from the truth.

We have made some effort to sharpen the constants in our proof, but presumably they can be improved further, leading to better lower bounds on K_{G}. Moreover, a perturbation of the form

P_{1} − λI − βP_{3} − δP_{5}

could lead to an even better estimate on K_{G}. Obtaining the best possible bound of this type is left to future work. Instead, our contribution is conceptual, as we identify a strategy to give better lower bounds on K_{G} that was doubted to work properly in [R91].

The upper bounds on K_{G} from [BMMN13] were proven with a roughly similar strategy, since they considered a perturbation of the sign function by a fifth degree Hermite polynomial. They could have used a third order Hermite polynomial instead, but chose not to, perhaps due to additional complications added to the argument. The details of the strategy of [BMMN13] are fairly different and perhaps more sophisticated than ours. Also,

[BMMN13] does not provide an explicit upper bound on K_{G}. It seems their argument shows that K_{G} < \frac{π}{2 log(1+\sqrt{2})} − 10^{−500}, though a sharper analysis might prove a better upper bound. So, in terms of absolute constant improvements, our improvement on the lower bound seems larger than their improvement on the upper bound.

1.8. Remark on the Complex Case. [D84] also obtains the best known lower bound on the complex Grothendieck constant using the same approach as sketched above, i.e. optimizing the ∞ → 1 norm over λ for the operator P_{1} − λI. It seems plausible our result could also give an improved lower bound for this constant. That is, for appropriate λ, β, an improved lower bound on Grothendieck’s complex constant should be achievable by analyzing the operator norm of P_{1} − λI − βP_{3}. Some preliminary computations suggest our approach could work in the complex setting. However, we leave this problem to future work.

1.9. Summary of Notation.

• γ_{n}(x) := e^{− \frac{1}{2} ∥x∥_{ℓ_{2}(ℝ^{n})}^{2}}(2π)^{−n/2}, ∀ x ∈ ℝ^{n}.

• γ_{n}(A) := ∫_{A} γ_{n}(x)dx for all measurable A ⊂ ℝ^{n}.

• P_{k} denotes projection onto the level k Hermite-Fourier coefficients in L_{2}(ℝ^{n}, γ_{n}).

• R_{λ} := P_{1} − λI, λ ∈ ℝ.

• R_{λ,β} := P_{1} − λI − βP_{3}, λ, β ∈ ℝ.

• H_{3}(z) = z^{3} − 3z, ∀ z ∈ ℝ.

• θ(z) = θ_{g}(z) := 𝔼[g|P_{1}g = αz], ∀ z ∈ ℝ, g: ℝ^{n} → [−1, 1].

• α := ∥ ∫_{ℝ^{n}} xg(x)γ_{n}(x)dx∥_{ℓ_{2}(ℝ^{n})} = | ∫_{ℝ} zθ(z)γ_{1}(z)dz|.

• η := λ/α (if α ≠ 0).

• ∥f∥_{p} := (∫_{ℝ^{n}} |f(x)|^{p}γ_{n}(x)dx)^{1/p}, ∀ p ≥ 1, ∀ f: ℝ^{n} → [−1, 1].

• L_{2}(γ_{n}) := {f: ℝ^{n} → ℝ : ∥f∥_{2} < ∞}.

• ⟨f, g⟩ := ∫_{ℝ^{n}} f(x)g(x)γ_{n}(x)dx, ∀ f, g ∈ L_{2}(γ_{n}).

• ∥R_{λ}∥_{∞→1} = sup{∥R_{λ}f∥_{1} : f: ℝ^{n} → [−1, 1]}.

• M = M_{λ,n} := {g: ℝ^{n} → [−1, 1] : ∥R_{λ}g∥_{1} = ∥R_{λ}∥_{∞→1}}.

• Θ = {θ_{g}: g ∈ M}.

• λ_{∗} ≈ 0.197479091.

• α_{∗} ≈ 0.7722165032.

• η_{∗} := λ_{∗}/α_{∗} ≈ 0.255730213. Unless otherwise stated, we will always use λ := λ_{∗}.

2. Review of Reeds

We provide more details for the sketch in Section 1.3 of the argument of Reeds proving (2), since we will extend this argument.

Let g: ℝ^{n} → {−1, 1} be measurable. Denote α := ∥P_{1}g∥_{2}. Denote θ_{g}(z) := 𝔼[g | P_{1}g = αz], for all z ∈ ℝ. (𝔼 is taken with respect to γ_{n}.) Then by its definition

∫_{ℝ} zθ_{g}(z)γ_{1}(z)dz = α.

∫_{ℝ^{n}} |R_{λ}g(x)|γ_{n}(x)dx =^{(3)} ∫_{ℝ} γ_{1}(z)(ℙ(g = 1|P_{1}g = αz)|αz − λ| + ℙ(g = −1|P_{1}g = αz)|αz + λ|)dz

= ∫_{ℝ} γ_{1}(z)((\frac{1}{2} + \frac{1}{2}θ_{g}(z))|αz − λ| + (\frac{1}{2} − \frac{1}{2}θ_{g}(z))|αz + λ|)dz

= ∫_{ℝ} γ_{1}(z)(\frac{1}{2}(|αz − λ| + |αz + λ|) + \frac{1}{2}θ_{g}(z)(|αz − λ| − |αz + λ|)dz

= 2λγ_{1}([0, λ/α]) + 2αe^{− \frac{λ^{2}}{2α^{2}}} /\sqrt{2π} + ∫_{ℝ} γ_{1}(z)\frac{1}{2}θ_{g}(z)(|αz − λ| − |αz + λ|)dz.

(7)

If α, λ are fixed, then θ_{g} only appears in the last term. We therefore focus on optimizing that integral term (with α, λ fixed). Denote

ψ(z) := \frac{1}{2}(|αz − λ| − |αz + λ|), ∀ z ∈ ℝ.

If z > 0, then ψ(z) = −αz1_{(z<λ/α)} − λ1_{(z≥λ/α)}, and

ψ(z)/z = −α1_{(|z|<λ/α)} − \frac{λ}{|z|}1_{(|z|≥λ/α)},  ∀ z ∈ ℝ.  (8)

So, we consider the problem of maximizing

∫_{ℝ} γ_{1}(z)ψ(z)θ(z)dz  (9)

subject to the constraints that α > 0 is fixed, and

∫_{ℝ} θ(z)zγ_{1}(z)dz = α,  |θ(z)| ≤ 1,  ∀ z ∈ ℝ,  α > 0.  (10)

Note that ψ(z)/z inside the integrand of (9) is the only different term when comparing that integrand and the integrand in (10). Since evidently ψ(z)/z is even, strictly increasing when z > λ/α, and constant when 0 < z < λ/α by (8), a θ maximizing this optimization problem must take the value sign(z) for any |z| > λ/α, if the constraint (10) can be satisfied for such a θ; if not, then θ must be sign(z) for some h > λ/α, and −1 otherwise.

More specifically, when α > 0, let h > 0 be the unique value satisfying

α = ( ∫_{h}^{∞} − ∫_{0}^{h} )2zγ_{1}(z)dz = \sqrt{\frac{2}{π}} (2e^{−h^{2}/2} − 1).  (11)

If h > λ/α, then there is a unique θ maximizing (9) subject to (10) (namely, θ is odd and θ(z) = sign(z − h) for all z > 0). But if h < λ/α, then the maximizer θ is not unique, since ψ(z)/z is constant for all |z| < λ/α, and we only have θ(z) = sign(z) for all |z| > λ/α. Denote η := λ/α. For such a θ we have

α =^{(10)} ∫_{−η}^{η} θ(z)zγ_{1}(z)dz + ∫_{|z|>η} |z|γ_{1}(z)dz = ∫_{−η}^{η} θ(z)zγ_{1}(z)dz + 2γ_{1}(η).  (12)

If we choose the right parameters, we can then characterize the maximizing functions θ.

Lemma 2.1 (Characterization of Maximizing Profiles). Let 0 < λ_{∗} < 1. Assume h < λ_{∗}/α_{∗}. Assume \sqrt{\frac{2}{π}}η_{∗}e^{−η_{∗}^{2}/2} = λ_{∗}. (So that γ_{1}(η_{∗}) = α_{∗}/2.) Let Θ be the set of θ maximizing (9) subject to constraints (10). Then Θ consists of all θ: ℝ → [−1, 1] such that

• θ(z) = sign(z), ∀ |z| > η_{∗}.

• ∫_{−η_{∗}}^{η_{∗}} θ(z)zγ_{1}(z)dz = 0.

Plugging in θ = −1_{[0,h]} + 1_{(h,∞]} + 1_{[−h,0)} − 1_{(−∞,−h)} into (7) and using (11), we get

∫_{ℝ^{n}} |R_{λ}g(x)|γ_{n}(x)dx = 4λγ_{1}([0, λ/α]) − α^{2} + 4αe^{− \frac{λ^{2}}{2α^{2}}} /\sqrt{2π} − λ.

The bound (2) comes from optimizing this quantity over all α > 0, then plugging the result into (5) and optimizing that over all 0 < λ < 1. Related to that calculation, we have

Lemma 2.2. For any 0 < α < 1, let F (α) := 4λγ_{1}([0, λ/α]) − α^{2} + 4αγ_{1}(λ/α) − λ. Then

F′(α) = 4γ_{1}(λ/α) − 2α.
F′′(α) = 4λ^{2}α^{−3}γ_{1}(λ/α) − 2.

So, if α_{∗} ≈ .77 satisfies F′(α_{∗}) = 0, and if λ_{∗} ≈ .197479091, then for all α with |α−α_{∗}| < .1,

F (α) ≤ F (α_{∗}) − \frac{9}{10}(α − α_{∗})^{2}.

(And if |α − α_{∗}| > .1, then F (α) ≤ F (α_{∗}) − (9/10)(1/10)^{2}.)

3. Third Moment Bounds

We begin proving our third moment bound for elements of M by treating the onedimensional n = 1 case.

Let H_{3}(z) := z^{3} − 3z for all z ∈ ℝ, so that ∫_{ℝ}(H_{3}(z))^{2}γ_{1}(z) dz = 6.

Fix λ > 0 and α > 0 and set η := λ/α.

When setting F′(α) = 0 in Lemma 2.2, we get, if 0 < η_{∗} < 1, then

α_{∗} = 2γ_{1}(η_{∗}) ⟺ \sqrt{\frac{2}{π}} η_{∗}e^{−η_{∗}^{2}/2} = λ_{∗},  (13)

and we will often assume (13) below. Let θ: ℝ → [−1, 1] satisfy

θ(z) = sign(z) ∀ |z| ≥ η_{∗}.  (14)

Under (13), the moment constraint ∫_{ℝ} zθ(z)γ_{1}(z)dz = α_{∗} reduces to the single condition

∫_{−η_{∗}}^{η_{∗}} z θ(z) γ_{1}(z) dz = 0.  (15)

Lemma 2.1 shows that (14) and (15) characterize Θ.

In this section we prove a uniform third Gaussian moment bound for any θ: ℝ → {−1, 1} satisfying (14) and (15).

Lemma 3.1. For every η ≥ 0,

B := 2 ∫_{η}^{∞} H_{3}(z) γ_{1}(z) dz = −2(1 − η^{2}) γ_{1}(η).  (16)

Lemma 3.2. Assume θ satisfies ∫_{−η}^{η} θ(z)zγ_{1}(z)dz = 0. Define

A(θ) := ∫_{−η}^{η} H_{3}(z) θ(z) γ_{1}(z) dz.

Then

|A(θ)| ≤ η^{2}(γ_{1}(0) − γ_{1}(η)).  (17)

Proof. By replacing θ with its odd part (θ − θ(−·))/2, it suffices to prove the lemma for odd θ. Denote μ(z) := zγ_{1}(z) for all z > 0. For any z ∈ (0, η), we have

H_{3}(z)γ_{1}(z) = (z^{3} − 3z)γ_{1}(z) = (z^{2} − 3) zγ_{1}(z) = (z^{2} − 3)μ(z).

Let r(z) := z^{2} − 3. Then since θ and H_{3} are odd, H_{3}θ is even, so

\frac{A(θ)}{2} = ∫_{0}^{η} r(z) θ(z)μ(z)dz.

Note that r is increasing on [0, η] and

max_{z∈[0,η]} r(z) − min_{z∈[0,η]} r(z) = ( − 3 + η^{2}) − (−3) = η^{2}.

Also μ(0, η) = ∫_{0}^{η} zγ_{1}(z) dz = γ_{1}(0)−γ_{1}(η). Since |θ(z)| ≤ 1 ∀ z ∈ ℝ, define p(z) := (1+θ)/2 and q(z) := (1 − θ)/2, so p(z), q(z) ∈ [0, 1] and p(z) − q(z) = θ(z) for all z ∈ ℝ. Therefore

∫_{0}^{η} r(z)θ(z)μ(z)dz = ∫_{0}^{η} r(z)p(z)μ(z)dz − ∫_{0}^{η} r(z)q(z)μ(z)dz.  (18)

The constraint ∫_{0}^{η} θ(z)μ(z)dz = 0 implies ∫_{0}^{η} p(z)μ(z)dz = ∫_{0}^{η} q(z)μ(z)dz = μ(0, η)/2. Then each term on the right side of (18) lies between min_{z∈[0,η]} r(z) · μ(0, η)/2 and max_{z∈[0,η]} r(z) · μ(0, η)/2, so their difference is bounded by \frac{1}{2}[max_{z∈[0,η]} r(z)−min_{z∈[0,η]} r(z)]μ(0, η) = \frac{η^{2}}{2} (γ_{1}(0)− γ_{1}(η)). Multiplying by 2 yields (17). □

Lemma 3.3. Assume θ satisfies θ(z) = sign(z) for all |z| > η for some η < 1/2. Then

∫_{−∞}^{∞} θ(z)zγ_{1}(z)dz ≠ 0.

Moreover, if θ̄: ℝ → [−1, 1] satisfies ∥θ − θ̄∥_{2} < 1/100, then

| ∫_{−∞}^{∞} \overline{θ}(z)zγ_{1}(z)dz| > .6.

Proof. We have

∫_{−∞}^{∞} θ(z)zγ_{1}(z)dz ≥ 2 ∫_{0}^{η}(−1)zγ_{1}(z)dz+2 ∫_{η}^{∞} zγ_{1}(z)dz = 2(2e^{−η^{2}/2}−1)/\sqrt{2π} ≥ .6104 … > 0,

since η < 1/2. For the second conclusion, note that

| ∫_{ℝ} z(θ(z) − θ̄(z))γ_{1}(z)dz| ≤ ∥θ − θ̄∥_{2}( ∫_{ℝ} z^{2}γ_{1}(z)dz)^{1/2} < 1/100.

So ∫_{ℝ} zθ̄(z)γ_{1}(z)dz > .6 by the reverse triangle inequality. □

4. Maximizers have absolute value 1 a.e.

We now build upon Lemma 2.1 and further characterize the maximizing set M. Let

M = M_{λ,n} := {g: ℝ^{n} → [−1, 1] : ∥R_{λ}g∥_{1} = ∥R_{λ}∥_{∞→1}}.

Lemma 4.1 (Every maximizer of ∥R_{λ}∥_{∞→1} is {±1}-valued). For every g ∈ M we have |g(x)| = 1 for γ_{n}-a.e. x (hence g ∈ {±1} a.e.).

Proof. Fix g ∈ M. Let a := R_{λ}g. Choose h : ℝ^{n} → {±1} with h(x) ∈ sign(a(x)) for all x. Then |h| ≤ 1 and

∥R_{λ}g∥_{1} = ∫_{ℝ^{n}} |a(x)| γ_{n}(x)dx = ∫_{ℝ^{n}} h(x)a(x)γ_{n}(x)dx = ⟨h, R_{λ}g⟩.  (19)

Since P_{1} is an orthogonal projection, it is self-adjoint on L_{2}(γ_{n}); hence R_{λ} is self-adjoint as well. Therefore (19) becomes

∥R_{λ}g∥_{1} = ⟨R_{λ}h, g⟩.

Because |g| ≤ 1, we have the pointwise bound (R_{λ}h)g ≤ |R_{λ}h|, hence

∥R_{λ}g∥_{1} = ⟨R_{λ}h, g⟩ ≤ ∫_{ℝ^{n}} |R_{λ}h(x)| γ_{n}(x)dx = ∥R_{λ}h∥_{1}.  (20)

On the other hand, since g is a maximizer,

∥R_{λ}h∥_{1} ≤ ∥R_{λ}∥_{∞→1} = ∥R_{λ}g∥_{1}.

Combining with (20) and (19) forces equality:

⟨R_{λ}h, g⟩ = ∫_{ℝ^{n}} |R_{λ}h(x)| γ_{n}(x)dx.

But equality in (R_{λ}h)g ≤ |R_{λ}h| implies that for γ_{n}-a.e. x with (R_{λ}h)(x) ≠ 0, we must have g(x) = sign((R_{λ}h)(x)), and in particular |g(x)| = 1 there.

It therefore remains to show that R_{λ}h ≠ 0 almost everywhere. Write P_{1}h(x) = ⟨m, x⟩ ∀ x ∈ ℝ^{n} where m := 𝔼[h(X)X] ∈ ℝ^{n}. Then

R_{λ}h(x) =^{(3)} ⟨m, x⟩ − λh(x).

On the set {h = +1} we have R_{λ}h = ⟨m, x⟩ − λ, whose zero set is contained in the hyperplane {⟨m, x⟩ = λ}; similarly on {h = −1} the zero set is contained in {⟨m, x⟩ = −λ}. Each hyperplane has γ_{n}-measure 0, hence γ_{n}({R_{λ}h = 0}) = 0. Therefore |g| = 1 almost everywhere. So, R_{λ}h ≠ 0 almost everywhere, completing the proof. □

Lemma 4.2. Let f: ℝ^{n} → {−1, 1} be measurable, and let

N := {h: ℝ^{n} → [−1, 1]: ∫_{ℝ^{n}} x_{i}h(x)γ_{n}(x)dx = 0, ∀ 2 ≤ i ≤ n, ∧ ∫_{|x_{1}|<η_{∗}} xh(x)γ_{n}(x)dx = 0
∧ h(x) = sign(x_{1}), for a.e. x ∈ ℝ^{n} with |x_{1}| > η_{∗}}.

Let h ∈ N. Then there exists g ∈ M such that

∥f − g∥_{1} ≤ ∥f − h∥_{1}

Proof. Since |f| = 1 and |h| ≤ 1, we have the pointwise equality |f − h| = 1 − fh, so that

∥f − h∥_{1} = 1 − ⟨f, h⟩.  (21)

Consider then the linear functional L: N → ℝ defined by

L(h_{0}) := ⟨f, h_{0}⟩, ∀ h_{0} ∈ N .

Note that N is a convex and compact subset with respect to the weak topology on the Hilbert space L_{2}(γ_{n}), since it is norm bounded and weakly closed and the moment constraints such as h_{0} ↦ ∫_{ℝ^{n}} x_{i}h_{0}(x)γ_{n}(x)dx are weakly continuous and linear. Since L is then a continuous linear functional on the convex compact set N, L achieves its maximum on N at an extreme point of N by the Bauer Maximum Principle. We therefore characterize the extreme points of N.

The extreme points of N are contained in the set of elements of N taking values in {−1, 1} almost surely. To see this, note that if an extreme point g ∈ N satisfies γ_{n}(|g| ≠ 1) > 0, then we can exhibit g as an element of a line in N by adding a small multiple of a bounded function g̃ supported in the set A := {|x_{1}| < η_{∗}}∩{|g| < 1−ε_{0}} satisfying ∫_{|x_{1}|<η_{∗}} xg̃(x)γ_{n}(x)dx = 0 for some 0 < ε_{0} < 1 small enough such that γ_{n}(|g| < 1 − ε_{0}) > 0. (Such a g̃ exists by e.g. letting A_{1}, …, A_{n+1} ⊂ A be disjoint sets with positive measure, then choosing by linear algebra constants a_{1}, …, a_{n+1} ∈ ℝ not all zero such that g̃ = ∑_{i=1}^{n+1} a_{i}1_{A_{i}} and ∫_{ℝ^{n}} xg̃(x)γ_{n}(x)dx = 0, which amounts to solving n equations in n + 1 unknowns a_{1}, …, a_{n+1}.) Then |g + tg̃| ≤ 1 and g + tg̃ ∈ N for all |t| < ε_{0}/∥g̃∥_{∞}.

That is, the extreme points of N are elements of M, by Lemma 2.1. Therefore, L achieves its maximum on N on the subset M ∩ N. That is,

sup_{h_{0}∈N} L(h_{0}) = max_{g∈M∩N} L(g).

From (21), we conclude that

inf_{h_{0}∈N} ∥f − h_{0}∥_{1} = min_{g∈M∩N} ∥f − g∥_{1}.

That is, there exists some g ∈ M such that

∥f − g∥_{1} ≤ ∥f − h∥_{1}.
□

5. Derivative Bound

The main result of this section is Lemma 5.2, which gives a lower bound on the ⟨P_{3}g, signR_{λ_{∗}}g⟩ for all g ∈ M.

Lemma 5.1 (Lower bound for ⟨sign(R_{λ}g), P_{3}g⟩ via (p, s_{1}, t_{2})). Assume we are at the Reeds point, i.e. there exist η_{∗} > 0 and α_{∗} > 0 such that

\sqrt{\frac{2}{π}} η_{∗}e^{−η_{∗}^{2}/2} = λ_{∗} < 1,  α_{∗} = \frac{λ_{∗}}{η_{∗}} = 2γ_{1}(η_{∗}).  (22)

Let g: ℝ^{n} → {±1} satisfy g ∈ M (by Lemma 4.1 there is no loss of generality.) Let X ∼ γ_{n} (X ∈ ℝ^{n} is a mean zero Gaussian with identity covariance matrix) and set

m := 𝔼[g(X) X] ∈ ℝ^{n},  u := \frac{m}{∥m∥_{2}} ∈ S^{n−1},  Z := ⟨u, X⟩ ∼ N(0, 1),

(m ≠ 0 by Lemma 3.3 since η_{∗} < 1/2) so that

P_{1}g(X) = ⟨m, X⟩ = α_{∗}Z  with  α_{∗} = ∥P_{1}g∥_{2} = ∥m∥_{2},

Let Y := X − Zu ∈ ℝ^{n−1} denote the orthogonal complement so that (Z, Y) are independent Gaussians. Let

f := sign(R_{λ_{∗}}g) = sign(α_{∗}Z − λ_{∗}g) ∈ {±1} a.e.

Let H_{3}(z) := z^{3} − 3z ∀ z ∈ ℝ (so 𝔼[H_{3}(Z)^{2}] = 6). Define

B := 2 ∫_{η_{∗}}^{∞}(z^{3} − 3z)γ_{1}(z) dz = −2(1 − η_{∗}^{2})γ_{1}(η_{∗}),  A_{max} := η_{∗}^{2}(γ_{1}(0) − γ_{1}(η_{∗})), (23)

κ_{Q} := \frac{B^{2} − A_{max}^{2}}{6} .  (24)

Finally define the inner-region quantities (with Z ∼ N(0, 1))

p := ℙ(|Z| < η_{∗}),  s_{1} := 𝔼[|Z| 1_{{|Z|<η_{∗}}}],  t_{2} := 𝔼[Z^{2} 1_{{|Z|<η_{∗}}}].  (25)

Then:

(i) The following explicit formulas hold:

p = 2Φ(η_{∗}) − 1,  s_{1} = 2(γ_{1}(0) − γ_{1}(η_{∗})),  t_{2} = p − 2η_{∗}γ_{1}(η_{∗}),  (26)

where Φ(η_{∗}) := ∫_{−∞}^{η_{∗}} e^{−z^{2}/2}dz/\sqrt{2π}. (ii) One has the decomposition

⟨f, P_{3}g⟩ = \underbrace{\frac{1}{6}𝔼[g(X)H_{3}(Z)] 𝔼[f(X)H_{3}(Z)]}_{≥ κ_{Q}} − ∥P_{⊥}g∥_{2}^{2},  (27)

where P_{⊥} denotes the orthogonal projection of the third chaos onto the direct sum of the transverse components

(H_{1}(Z) ⊗ H_{2}(Y)) ⊕ (H_{2}(Z) ⊗ H_{1}(Y)) ⊕ (H_{0}(Z) ⊗ H_{3}(Y)).

(here H_{k}(Z) denotes the span of H_{k}(Z)) and accordingly write

P_{3} = P_{3,0} + P_{⊥} = P_{3,0} + P_{1,2} + P_{2,1} + P_{0,3}  (28)

for the orthogonal projections, where P_{3,0} projects onto the span of H_{3}(Z) ⊗ H_{0}(Y).

(iii) The transverse mass satisfies the explicit bound

∥P_{⊥}g∥_{2}^{2} ≤ p^{2} + s_{1}^{2} + \frac{1}{2} t_{2}^{2}.  (29)

(iv) Consequently,

⟨f, P_{3}g⟩ ≥ κ_{Q} − (p^{2} + s_{1}^{2} + \frac{1}{2}t_{2}^{2}).  (30)

Proof. Step 1: formulas for (p, s_{1}, t_{2}). By symmetry,

p =^{(25)} ℙ(−η_{∗} < Z < η_{∗}) = Φ(η_{∗}) − Φ(−η_{∗}) = 2Φ(η_{∗}) − 1.

Also

s_{1} =^{(25)} 2 ∫_{0}^{η_{∗}} zγ_{1}(z) dz = 2(γ_{1}(0) − γ_{1}(η_{∗})),

Finally, we deduce (26) from

t_{2} =^{(25)} 2 ∫_{0}^{η_{∗}} z^{2}γ_{1}(z) dz = 2( − η_{∗}γ_{1}(η_{∗}) + ∫_{0}^{η_{∗}} γ_{1}(z) dz)

= 2(Φ(η_{∗}) − \frac{1}{2} − η_{∗}γ_{1}(η_{∗})) =^{(25)} p − 2η_{∗}γ_{1}(η_{∗}).

Step 2: a pointwise identity on the “flat” region. Since g maximizes ∥R_{λ_{∗}}g∥_{1}, Lemma 2.1 implies that the conditional bias θ(z) := 𝔼[g | Z = z] satisfies θ(z) = sign(z) for |z| > η_{∗}; since g ∈ {±1} this forces g = sign(Z) almost surely on {|Z| > η_{∗}}. In particular, on {|Z| > η_{∗}} the function g depends only on Z.

Since g ∈ {±1} and |Z| < η_{∗} implies |α_{∗}Z| < λ_{∗} by (22), we have pointwise

f = sign(α_{∗}Z − λ_{∗}g) = \begin{cases}g & , if |Z| > η_{∗} \\ −g & , if |Z| < η_{∗}. \end{cases}  (31)

Step 3: transverse pairing is a negative square. Let ψ(Z, Y) be any Hermite polynomial of total degree 3 that is a nonconstant function of Y. Then

𝔼[ψ | Z] = 0  (32)

because its Y -part has mean 0. Using that g depends only on Z on {|Z| > η_{∗}}, we obtain

𝔼[gψ 1_{{|Z|>η_{∗}}}] = 𝔼[𝔼[gψ 1_{{|Z|>η_{∗}}}|Z]] = 𝔼[g 1_{{|Z|>η_{∗}}}𝔼[ψ | Z]] = 0,  (33)

hence ⟨g, ψ⟩ = 𝔼[gψ 1_{{|Z|<η_{∗}}}]. Similarly, 𝔼[fψ 1_{{|Z|>η_{∗}}}] = 0 by (31). On {|Z| < η_{∗}} we have f = −g by (31), hence

⟨f, ψ⟩ = 𝔼[fψ 1_{{|Z|<η_{∗}}}] = −𝔼[gψ 1_{{|Z|<η_{∗}}}] = −⟨g, ψ⟩.  (34)

Let {ψ_{j}} be an orthonormal basis of the transverse third chaos. Then

⟨f, P_{⊥}g⟩ = ∑_{j}⟨f, ψ_{j}⟩⟨g, ψ_{j}⟩ =^{(34)} ∑_{j}(−⟨g, ψ_{j}⟩)⟨g, ψ_{j}⟩ = − ∑_{j}⟨g, ψ_{j}⟩^{2} = −∥P_{⊥}g∥_{2}^{2}.

This gives

⟨f, P_{3}g⟩ =^{(28)} ⟨f, P_{3,0}g⟩ + ⟨f, P_{⊥}g⟩ = ⟨f, P_{3,0}g⟩ − ∥P_{⊥}g∥_{2}^{2},

where P_{3,0} is defined after (28).

Step 4: lower bound on the zonal component. Since the zonal third chaos is onedimensional, P_{3,0}g is a scalar multiple of H_{3}(Z):

P_{3,0}g =^{(28)} \frac{𝔼[gH_{3}(Z)]}{6} H_{3}(Z).

Therefore

⟨f, P_{3,0}g⟩ = \frac{𝔼[gH_{3}(Z)] 𝔼[fH_{3}(Z)]}{6}.

Then (31) and Lemma 2.1 imply 𝔼[gH_{3}(Z)] = B + A and 𝔼[fH_{3}(Z)] = B − A, where B is defined in (16) and A is the inner-region term

A := ∫_{−η_{∗}}^{η_{∗}}(z^{3} − 3z)θ(z)γ_{1}(z) dz, θ(z) = 𝔼[g | Z = z] ∈ [−1, 1].

Lemma 2.1 says ∫_{−η_{∗}}^{η_{∗}} zθ(z)γ_{1}(z) dz = 0 and Lemma 3.2 says |A| ≤^{(17)} η_{∗}^{2}(γ_{1}(0) − γ_{1}(η_{∗})). So

⟨f, P_{3,0}g⟩ = \frac{(B + A)(B − A)}{6} = \frac{B^{2} − A^{2}}{6} ≥ \frac{B^{2} − A_{max}^{2}}{6} =^{(24)} κ_{Q}.

Step 5: bounding ∥P_{⊥}g∥_{2}^{2} in terms of (p, s_{1}, t_{2}). Let I := 1_{{|Z|<η_{∗}}}. Define the Y -measurable functions

m_{0}(Y) := 𝔼[gI | Y],  a_{1}(Y) := 𝔼[gZI | Y],  a_{2}(Y) := \frac{1}{\sqrt{2}}𝔼[gZ^{2}I | Y].  (35)

Since |g| ≤ 1 and Z ⊥ Y, we have the pointwise bounds (via (25))

|m_{0}(Y)| ≤ 𝔼[I] =^{(25)} p,  |a_{1}(Y)| ≤ 𝔼[|Z|I] =^{(25)} s_{1},  |a_{2}(Y)| ≤ \frac{1}{\sqrt{2}}𝔼[Z^{2}I] =^{(25)} \frac{t_{2}}{\sqrt{2}}. (36)

Now consider each transverse block in the orthogonal decomposition of the third chaos: (0,3) block. For any ψ ∈ H_{3}(Y),

⟨g, ψ(Y)⟩ =^{(33)} 𝔼[gI ψ(Y)] =^{(35)} 𝔼[m_{0}(Y)ψ(Y)] = ⟨m_{0}(Y), ψ(Y)⟩.

Thus P_{0,3}g =^{(28)} P_{H_{3}(Y)}(m_{0}) and

∥P_{0,3}g∥_{2} ≤ ∥m_{0}∥_{2} ≤ ∥m_{0}∥_{∞} ≤^{(36)} p.  (37)

(1,2) block. For any ψ ∈ H_{2}(Y), we similarly have

⟨g, Zψ(Y)⟩ =^{(33)} 𝔼[gZI ψ(Y)] =^{(35)} 𝔼[a_{1}(Y)ψ(Y)] = ⟨a_{1}(Y), ψ(Y)⟩.

Thus P_{1,2}g =^{(28)} Z · P_{H_{2}(Y)}(a_{1}) and since ∥Z∥_{2} = 1,

∥P_{1,2}g∥_{2} = ∥P_{H_{2}(Y)}(a_{1})∥_{2} ≤ ∥a_{1}∥_{2} ≤ ∥a_{1}∥_{∞} ≤^{(36)} s_{1}.  (38)

(2,1) block. Let ℓ(Y) ∈ H_{1}(Y) be any linear form in the Y -coordinates. Since P_{1}g is parallel to u (the Z-direction), we have 𝔼[g ℓ(Y)] = 0. Also, 𝔼[gZ^{2}ℓ(Y)1_{|Z|>η_{∗}}] = 0 because ℓ(Y) has mean 0 and g is constant when |Z| > η_{∗}. So, writing h_{2}(Z) := (Z^{2} − 1)/\sqrt{2},

⟨g, h_{2}(Z) ℓ(Y)⟩ = \frac{1}{\sqrt{2}}𝔼[g · (Z^{2} − 1)ℓ(Y)] = \frac{1}{\sqrt{2}}𝔼[gZ^{2}I ℓ(Y)] =^{(35)} 𝔼[a_{2}(Y) ℓ(Y)].

Hence P_{2,1}g = h_{2}(Z) · P_{H_{1}(Y)}(a_{2}) and since ∥h_{2}∥_{2} = 1,

∥P_{2,1}g∥_{2} = ∥P_{H_{1}(Y)}(a_{2})∥_{2} ≤ ∥a_{2}∥_{2} ≤ ∥a_{2}∥_{∞} ≤^{(36)} \frac{t_{2}}{\sqrt{2}}.  (39)

By orthogonality of the three transverse blocks,

∥P_{⊥}g∥_{2}^{2} =^{(28)} ∥P_{0,3}g∥_{2}^{2} + ∥P_{1,2}g∥_{2}^{2} + ∥P_{2,1}g∥_{2}^{2} ≤^{(37)∧(38)∧(39)} p^{2} + s_{1}^{2} + \frac{1}{2}t_{2}^{2},

which is (29). Combining with (27) completes the proof. □

We can now plug constants into (30) and verify the lower bound is positive.

Lemma 5.2 (Formal Derivative). Let g: ℝ^{n} → {±1} satisfy g ∈ M. Then

⟨sign(R_{λ_{∗}}g), P_{3}g⟩ ≥ 0.0868120048 − 0.0414080847 ≈ 0.0454039202.

Proof. If λ_{∗} = 0.197479091 then η_{∗} ≈^{(22)} 0.255730213173163, α_{∗} ≈^{(22)} 0.772216503281451, B ≈^{(23)}

−0.721715133242779, A_{max} ≈^{(23)} 0.000839319067615, so κ_{Q} ≈^{(24)} 0.086812004849191. Moreover p ≈ 0.201840836034193, s_{1} ≈ 0.0256680575214142, t_{2} ≈ 0.00436174503419317, by (26), so p^{2} + s_{1}^{2} + \frac{1}{2}t_{2}^{2} ≈ 0.0414080846777763. Therefore (30) concludes the proof. □

Lemma 5.3 (Pointwise sign-flip inequality). For all a, b ∈ ℝ and all β ≥ 0,

|a − βb| ≤ |a| − β sign(a) b + 2β |b| 1_{{|a|≤β|b|}}.  (40)

Proof. If |a| > β|b|, then a and a − βb have the same sign, hence |a − βb| = |a| − β sign(a) b and the indicator term vanishes. If |a| ≤ β|b|, then |a − βb| ≤ |a| + β|b| = |a| − β sign(a) b + β(|b| + sign(a)b) ≤ |a| − β sign(a) b + 2β|b|. □

6. Fixed Neighborhood with Norm Drop

Informally, Lemma 5.2 implies that, for small enough β > 0, if g is in a neighborhood of M, then ∥R_{λ,β}g∥_{1} < ∥R_{λ}∥_{∞→1} for small β, since the quantity in Lemma 5.2 is a formal derivative of ∥R_{λ,β}g∥_{1} with respect to β.

In this section, we formalize this argument, first by extending Lemma 5.2 to a neighborhood of M in Lemma 6.6, then formalizing the derivative computation in Proposition 6.7 via Lemma 5.3. Our final desired bound then appears in (60), where we plug in some explicit values of the parameters.

For any f: ℝ^{n} → [−1, 1] write dist_{1}(f, M) := inf_{g∈M} ∥f − g∥_{1}.

Assume the following uniform constants exist (and do not depend on the dimension n):

L := ∥R_{λ}∥_{2→2},  (41)
κ_{0} := inf_{g∈M} ⟨sign(R_{λ}g), P_{3}g⟩ > 0,  (42)
K_{0} := sup_{g∈M} ∥P_{3}g∥_{2} < ∞,  (43)
L_{0} := sup_{g∈M} sup_{t∈(0,1]} \frac{γ_{n}(\{|R_{λ}g| ≤ t\})}{t} < ∞.  (44)

(L_{0} < ∞ by Lemmas 3.3, 4.1 and 6.4 below, and κ_{0} > 0 by Lemma 5.2.)

Lemma 6.1 (L_{1} bounds for Projections). Let h: ℝ^{n} → [−1, 1] with ∥h∥_{1} ≤ 1/100. Then

∥P_{1}h∥_{1} ≤ \frac{1}{2}∥h∥_{1} log(1/∥h∥_{1}).

∥P_{3}h∥_{1} ≤ (e/\sqrt{3})^{3}∥h∥_{1}[log(1/∥h∥_{1})]^{3/2}.

Also, if h: ℝ^{n} → [−1, 1] (with no other assumptions), then ∥P_{3}h∥_{1} ≤ 1.

Proof. Suppose ∥h∥_{1} is fixed. A rearrangement argument shows that the first inequality is saturated when h is the indicator function of a half space, so we may assume n = 1 and h = 1_{[a,∞]} with a > 2.3, in which case ∥h∥_{1} = ∫_{a}^{∞} γ_{1}(z)dz and ∥P_{1}h∥_{1} = ∫_{ℝ} |z|γ_{1}(z)dz · ∫_{a}^{∞} zγ_{1}(z)dz = \sqrt{2/π}γ_{1}(a). So, using γ_{1}(a) ≤ .583Φ(−a) log(1/Φ(−a)) ∀ a ≥ 2.3, we get

∥P_{1}h∥_{1} = \sqrt{2/π}γ_{1}(a) ≤ \sqrt{2/π}(.583) ∫_{a}^{∞} γ_{1}(z)dz · log (1/ ∫_{a}^{∞} γ_{1}(z)dz).

For the P_{3} bound, we let g: ℝ^{n} → [−1, 1], let r, s > 1 with 1/r + 1/s = 1 and r := 1 + \frac{1}{3} log(1/∥h∥_{1}) > 2 and use Hölder’s inequality to write

|⟨g, P_{3}h⟩| = |⟨P_{3}g, h⟩| ≤ ∥P_{3}g∥_{r}∥h∥_{s}.  (45)

By hypercontractivity for the P_{3} term [G75], for every r ≥ 2, ∥P_{3}g∥_{r} ≤ (r − 1)^{3/2}∥P_{3}g∥_{2} ≤ (r − 1)^{3/2}∥g∥_{2} ≤ (r − 1)^{3/2}. Since |h| ≤ 1 and s ≥ 1, we have ∥h∥_{s}^{s} ≤ ∥h∥_{1}, so ∥h∥_{s} ≤ ∥h∥_{1}^{1/s}. In summary, (after taking the supremum over all g: ℝ^{n} → [−1, 1] in (45)),

∥P_{3}h∥_{1} ≤ ∥h∥_{1}^{1/s}(r − 1)^{3/2} = ∥h∥_{1}^{1−1/r}(r − 1)^{3/2}.

Now, by definition of r, since ∥h∥_{1} < 1/100, we have r > 2 and

∥h∥_{1}^{−1/r} = exp (\frac{log(1/∥h∥_{1})}{1 + \frac{1}{3} log(1/∥h∥_{1})}) ≤ e^{3}.

So, combining the above,

∥P_{3}h∥_{1} ≤ ∥h∥_{1}e^{3}((1/3) log(1/∥h∥_{1}))^{3/2}.

For the final assertion, note that ∥P_{3}h∥_{1} ≤ ∥P_{3}h∥_{2} ≤ ∥h∥_{2} ≤ 1. □

For any integer k ≥ 1, denote H_{k} as the image of P_{k} in L_{2}(ℝ^{n}, γ_{n}).

Lemma 6.2 (Third chaos on a bounded Z-strip). Let h ∈ H_{3}. Fix u ∈ S^{n−1} and write X = Zu + Y where Z = ⟨u, X⟩ ∼ N(0, 1) and u ⊥ Y. Then for every z_{0} > 0 and every measurable A ⊆ {|Z| ≤ z_{0}},

∫_{ℝ^{n}} |h(x)| 1_{A}(x) γ_{n}(x)dx ≤ \sqrt{C_{z_{0}}} ∥h∥_{2} γ_{n}(A),  (46)

where

C_{z_{0}} := sup_{|z|≤z_{0}} (\frac{H_{3}(z)^{2}}{6} + \frac{H_{2}(z)^{2}}{2} + z^{2} + 1),  H_{2}(z) = z^{2} − 1, H_{3}(z) = z^{3} − 3z. (47)

Proof. Decompose the third chaos in (Z, Y) as

h(Z, Y) = aH_{3}(Z) + H_{2}(Z)L(Y) + ZQ(Y) + C(Y),

with a ∈ ℝ, L ∈ H_{1}(Y), Q ∈ H_{2}(Y), C ∈ H_{3}(Y) and the four summands are orthogonal (conditional on Z = z). Then for each z ∈ ℝ,

𝔼[h^{2} | Z = z] = a^{2}H_{3}(z)^{2}+H_{2}(z)^{2}𝔼[L^{2}]+z^{2}𝔼[Q^{2}]+𝔼[C^{2}] ≤ (\frac{H_{3}(z)^{2}}{6} + \frac{H_{2}(z)^{2}}{2} +z^{2}+1)∥h∥_{2}^{2}.

Thus on A ⊆ {|Z| ≤ z_{0}},

∫_{A}(h(x))^{2} γ_{n}(x)dx = ∫_{A} 𝔼[h^{2} | Z] γ_{n}(x)dx ≤ C_{z_{0}}∥h∥_{2}^{2} γ_{n}(A),

and (46) follows by the Cauchy–Schwarz inequality. □

Lemma 6.3 (Tail bound for H_{3}). Let h ∈ H_{3} with ∥h∥_{2} ≤ 1. Then for every s ≥ e,

∫_{ℝ^{n}} |h(x)| 1_{\{|h|≥s\}} γ_{n}(x)dx ≤ exp ( − \frac{1}{2}(s/e)^{2/3} − \frac{1}{2}).  (48)

Proof. By hypercontractivity for H_{3} [G75], for every r ≥ 2, ∥h∥_{r} ≤ (r−1)^{3/2}∥h∥_{2} ≤ (r−1)^{3/2}. By Markov’s inequality, γ_{n}(|h| ≥ s) ≤ ∥h∥_{r}^{r}/s^{r}. Choose r := 1 + (s/e)^{2/3} ≥ 2, so (r − 1)^{3/2} = s/e, giving γ_{n}(|h| ≥ s) ≤ e^{−r} = exp(−(s/e)^{2/3} −1). Then by the Cauchy-Schwarz inequality, ∫_{ℝ^{n}} |h(x)|1_{\{|h|≥s\}}γ_{n}(x)dx ≤ ∥h∥_{2} γ_{n}(|h| ≥ s)^{1/2} ≤ exp(−\frac{1}{2}(s/e)^{2/3} − 1/2). □

Lemma 6.4 (Small-ball via the P_{1}-direction). Let f: ℝ^{n} → {−1, 1} and write P_{1}f(x) = α_{f}⟨u_{f}, x⟩ with α_{f} = ∥P_{1}f∥_{2}, u_{f} ∈ S^{n−1}. Set Z_{f} := ⟨u_{f}, X⟩ ∼ N(0, 1) and η_{f} := λ/α_{f}. Then

\{|R_{λ}f| ≤ t\} ⊆ \{||Z_{f}| − η_{f} | ≤ \frac{t}{α_{f}} \}, ∀ t > 0.

Consequently, if α_{f} ≥ α_{min} := .6 > 0 and t > 0, then

γ_{n}(|R_{λ}f| ≤ t) ≤ \frac{4γ_{1}(0)}{α_{min}} t = \frac{4}{α_{min}\sqrt{2π}} t.  (49)

Proof. Pointwise, |R_{λ}f| =^{(3)} |P_{1}f − λf| ≥ ||P_{1}f| − |λf|| = ||P_{1}f| − λ| since |f| = 1. With

|P_{1}f| = α_{f}|Z_{f}|, this is ≥ α_{f} ||Z_{f}| − η_{f} |, proving the inclusion. The probability bound follows by the exact formula ℙ(||Z_{f}| − η| ≤ δ) = 2(Φ(η + δ) − Φ(η − δ)) ≤ 4γ_{1}(0)δ with δ = t/α_{f} and 0 < t < λ, which implies δ < η. (If t > λ, then δ > η and ℙ(||Z_{f}| − η| ≤ δ) = ℙ(|Z_{f}| ≤ η + δ) = Φ(η + δ) − Φ(−η − δ) ≤ 4γ_{1}(0)δ.) □

Lemma 6.5 (Flip correction bound with a free cutoff t). Let f: ℝ^{n} → {−1, 1} and set a := R_{λ}f and b := P_{3}f ∈ H_{3}. Assume α_{f} = ∥P_{1}f∥_{2} ≥ α_{min} > 0. Fix β ∈ (0, 1) and choose any cutoff t ∈ (0, λ). Assume also that {|a| ≤ t} ⊆ {|Z_{f}| ≤ z_{0}} for some z_{0} > 0 (e.g. it suffices by the triangle inequality that z_{0} ≥ η_{f} + t/α_{min}). Assume t/β > e. Then

∫_{ℝ^{n}} |b(x)| 1_{\{|a|≤β|b|\}} γ_{n}(x)dx ≤ \sqrt{C_{z_{0}}} ∥b∥_{2} γ_{n}(|a| ≤ t) + exp ( − \frac{1}{2}(\frac{t}{eβ} )^{2/3} − \frac{1}{2}), (50)

where C_{z_{0}} is as in (47). In particular, since ∥b∥_{2} ≤ ∥f∥_{2} ≤ 1, combining with (49) yields

2β ∫_{ℝ^{n}} |P_{3}f(x)| 1_{\{|R_{λ}f|≤β|P_{3}f|\}} γ_{n}(x)dx ≤ \underbrace{\frac{8\sqrt{C_{z_{0}}}}{α_{min}\sqrt{2π}}}_{=:K_{strip}} βt + 2β exp ( − \frac{1}{2}(\frac{t}{eβ} )^{2/3} − \frac{1}{2}). (51)

Proof. Split {|a| ≤ β|b|} ⊆ {|a| ≤ t} ∪ {|b| ≥ t/β}, hence

∫_{ℝ^{n}} |b(x)|1_{{|a|≤β|b|}}γ_{n}(x)dx ≤ ∫_{ℝ^{n}} |b(x)|1_{{|a|≤t}}γ_{n}(x)dx + ∫_{ℝ^{n}} |b(x)|1_{{|b|≥t/β}}γ_{n}(x)dx.

On {|a| ≤ t} ⊆ {|Z_{f}| ≤ z_{0}} apply Lemmas 6.2 and 6.3 to get (50) with s = t/β. To obtain (51), apply Lemma 6.4 to (50). □

We now extend Lemma 5.2 to a neighborhood of M.

Lemma 6.6 (Pairing stability near maximizers). Let f: ℝ^{n} → [−1, 1] with dist_{1}(f, M) ≤ ε. Pick g ∈ M with ∥f − g∥_{1} ≤ ε < 1/100 and define h := f − g. Let s_{f} ∈ sign(R_{λ}f). Then

⟨s_{f}, P_{3}f⟩ ≥ κ_{0} − 3.87ε[log(2/ε)]^{3/2} − 2^{3/2}[εL_{0}(λ + .5 log(2/ε))]^{1/4}K_{0}.  (52)

Proof. Fix f with dist_{1}(f, M) ≤ ε and pick g ∈ M with

∥f − g∥_{1} ≤ ε.  (53)

Write

s_{f} ∈ sign(R_{λ}f), s_{g} ∈ sign(R_{λ}g),

i.e. s_{f}R_{λ}f = |R_{λ}f| a.e. and similarly for s_{g}.

Step 1: sign stability ∥s_{f} − s_{g}∥_{2} ≤ Õ(ε^{1/4}).

Recall h := f − g. Then R_{λ}f = R_{λ}g + R_{λ}h. If sign(a + b) ≠ sign(a) then |a| ≤ |b|, so using a = R_{λ}g and b = R_{λ}h and s_{f} = sign(a + b), for any u > 0,

{s_{f} ≠ s_{g}} ⊆ {|R_{λ}g| ≤ |R_{λ}h|} ⊆ {|R_{λ}g| ≤ u} ∪ {|R_{λ}h| ≥ u}.

Therefore, for any u > 0,

γ_{n}(s_{f} ≠ s_{g}) ≤ γ_{n}(|R_{λ}g| ≤ u) + γ_{n}(|R_{λ}h| ≥ u).  (54)

By (44), γ_{n}(|R_{λ}g| ≤ u) ≤ L_{0}u.

By Lemma 6.1 for h/2, 0 < ε < 1/100, and then Markov’s inequality and ∥h∥_{1} ≤ ε,

∥R_{λ}h∥_{1} ≤^{(3)} λ∥h∥_{1} + ∥P_{1}h∥_{1} ≤ λ∥h∥_{1} + \frac{1}{2}∥h∥_{1} log(2/∥h∥_{1}).

γ_{n}(\{|R_{λ}h| ≥ u\}) ≤ \frac{∥R_{λ}h∥_{1}}{u} ≤ \frac{ε(λ + .5 log(2/ε))}{u}.

Minimizing L_{0}u + c/u over u > 0 in (54) gives (with c = ε(λ + .5 log(2/ε)))

γ_{n}(\{s_{f} ≠ s_{g}\}) ≤^{(54)} 2\sqrt{L_{0}ε(λ + .5 log(2/ε))}.

Since |s_{f} − s_{g}| = 2 on {s_{f} ≠ s_{g}} and 0 otherwise,

∥s_{f} − s_{g}∥_{2} = 2[γ_{n}(s_{f} ≠ s_{g})]^{1/2} ≤ 2^{3/2}[εL_{0}(λ + .5 log(2/ε))]^{1/4}.  (55)

Step 2: pairing stability ⟨s_{f}, P_{3}f⟩ ≥ κ_{0} − Õ(ε^{1/4})

Using P_{3}f = P_{3}g + P_{3}h,

⟨s_{f}, P_{3}f⟩ = ⟨s_{g}, P_{3}g⟩ + ⟨s_{f} − s_{g}, P_{3}g⟩ + ⟨s_{f}, P_{3}h⟩.  (56)

The first term is ≥ κ_{0} by (42). For the second term, we apply Cauchy-Schwarz to get

|⟨s_{f} − s_{g}, P_{3}g⟩| ≤ ∥s_{f} − s_{g}∥_{2} ∥P_{3}g∥_{2} ≤^{(43)∧(55)} 2^{3/2}[εL_{0}(λ + .5 log(2/ε))]^{1/4}K_{0}.

For the third term, Lemma 6.1 for h/2 says

∥P_{3}h∥_{1} ≤ (e/\sqrt{3})^{3}∥h∥_{1}[log(2/∥h∥_{1})]^{3/2} ≤^{(53)} 3.87ε[log(2/ε)]^{3/2},

so

|⟨s_{f}, P_{3}h⟩| ≤ ∥P_{3}h∥_{1} ≤ 3.87ε[log(2/ε)]^{3/2}.

Hence, combining the above

⟨s_{f}, P_{3}f⟩ ≥^{(56)} κ_{0} − 3.87ε[log(2/ε)]^{3/2} − 2^{3/2}[εL_{0}(λ + .5 log(2/ε))]^{1/4}K_{0}.  (57)
□

We can now turn Lemma 6.6 into an operator norm upper bound.

Proposition 6.7. Let ε ∈ (0, 1) and suppose f: ℝ^{n} → [−1, 1] satisfies dist_{1}(f, M) ≤ ε. Assume moreover that α_{f} = ∥P_{1}f∥_{2} ≥ α_{min} > 0. Then for every β ∈ (0, 1) and every cutoff t ∈ (0, λ) such that {|R_{λ}f| ≤ t} ⊆ {|Z_{f}| ≤ z_{0}} (for some z_{0}, such as z_{0} > η_{f} + t/α_{min}),

∥R_{λ,β}f∥_{1} ≤ ∥R_{λ}∥_{∞→1} − β(κ_{0} − 3.87ε[log(2/ε)]^{3/2} − 2^{3/2}[εL_{0}(λ + .5 log(2/ε))]^{1/4}K_{0})

+ K_{strip}βt + 2β exp ( − \frac{1}{2}(\frac{t}{eβ} )^{2/3} − \frac{1}{2}),

(58)

Here K_{strip} = ^{\frac{8\sqrt{C_{z_{0}}}}{α_{min}\sqrt{2π}}}. In particular, fix any exponent ρ ∈ (0, 1) and choose t = β^{ρ}. Then

∥R_{λ,β}f∥_{1} ≤ ∥R_{λ}∥_{∞→1} − β κ_{eff}(ε) + K_{strip} β^{1+ρ} + 2β exp ( − \frac{1}{2}e^{−2/3} β^{− \frac{2}{3} (1−ρ)} − \frac{1}{2}), (59)

where

κ_{eff}(ε) := κ_{0} − 3.87ε[log(2/ε)]^{3/2} − 2^{3/2}[εL_{0}(λ + .5 log(2/ε))]^{1/4}K_{0}.

Consequently, if κ_{eff}(ε) > 0, then there exists β_{0}(ε, ρ) > 0 such that for all 0 < β ≤ β_{0}(ε, ρ),

∥R_{λ,β}f∥_{1} ≤ ∥R_{λ}∥_{∞→1} − \frac{1}{2} κ_{eff}(ε) β.

Thus: for every fixed ε with κ_{eff}(ε) > 0, the entire ε-neighborhood of M experiences a uniform linear-in-β drop for all sufficiently small β, with ε independent of β.

Proof. Apply Lemma 5.3 with a = R_{λ}f and b = P_{3}f, integrate, and use ∥R_{λ}f∥_{1} ≤ ∥R_{λ}∥_{∞→1}:

∥R_{λ,β}f∥_{1} ≤^{(6)} ∥R_{λ}∥_{∞→1} − β⟨s_{f}, P_{3}f⟩ + 2β ∫_{ℝ^{n}} |P_{3}f(x)|1_{{|R_{λ}f|≤β|P_{3}f|}}γ_{n}(x)dx.

Lower bound ⟨s_{f}, P_{3}f⟩ by Lemma 6.6. Upper bound the last integral term by Lemma 6.5. This yields (58). The specialization (59) follows by choosing t = β^{ρ}. □

Remark 6.8. Lemma 3.3 says if ε < 1/100, we can take α_{min} = .6, λ = .19747 …,

η_{f} = λ/α_{f} < 1/3, t = β^{ρ}, z_{0} := 1/3 + t/.6 = 1/3 + β^{ρ}/.6, C_{z_{0}} ≤^{(47)} 1.7 (if z_{0} < .36),

K_{strip} = ^{\frac{8\sqrt{C_{z_{0}}}}{α_{min}\sqrt{2π}}} = \frac{8}{.6\sqrt{π}} \sqrt{\frac{1.7}{2}} ≤ 7. From Lemma 5.2, we can take κ_{0} =^{(42)} .0454, K_{0} ≤

\sqrt{.0871 + .04141} ≤ .359 (by Lemma 5.2 modified to get an upper bound instead of a lower bound, i.e. ∥P_{3}g∥_{2}^{2} ≤ (B+A)^{2}/6+p^{2}+s_{1}^{2}+t_{2}^{2}/2 and (B+A)^{2} ≤ .7226^{2}), L_{0} ≤ 4/[α_{min}\sqrt{2π}] ≤ 2.66 by (44) and (49). Then we can take

κ_{eff}(ε) = .0454 − 3.87ε[log(2/ε)]^{3/2} − ε^{1/4}2^{3/2}(2.66)^{1/4}(.19747 + .5 log(2/ε))^{1/4}(.359).

Choose ε = 10^{−7}, then κ_{eff} ≥ .0454 − .0396 > .0058, choose ρ = .7, and β ≤ 10^{−10}. Then K_{strip}β^{ρ} ≤ 10^{−6} and 2 exp(−.5 − .5e^{−2/3}β^{−(2/3)(1−ρ)}) < 10^{−10}, z_{0} < .36, so (59) says

\begin{aligned}∥R_{λ,β}f∥_{1} & ≤ ∥R_{λ}∥_{∞→1} − β(.0058 − 10^{−6} − 10^{−10}) \\ & ≤ ∥R_{λ}∥_{∞→1} − β(.0057), \\ & ∀ f: ℝ^{n} → \{−1, 1\} with inf_{g∈M} ∥f − g∥_{1} < ε, ∀ 0 < β < 10^{−10}. \end{aligned}  (60)

Remark 6.9. Theorem 1.1 with an ineffective constant follows immediately from (60), since there must exist some c(ε) such that ∥R_{λ}f∥_{1} < ∥R_{λ}∥_{∞→1} − c(ε) for all f: ℝ^{n} → [−1, 1] with inf_{g∈M} ∥f − g∥_{1} > ε, hence ∥R_{λ,β}f∥_{1} < ∥R_{λ}∥_{∞→1} − c(ε) + β, for all such f (using the final part of Lemma 6.1). That is, choosing 0 < β < min(c(ε), 10^{−10}) (and using (60)) completes the proof of Theorem 1.1 (with an ineffective constant), i.e. ∥R_{λ,β}∥_{∞→1} < ∥R_{λ}∥_{∞→1}. Since we would like an effective constant, we now proceed to find an explicit form for c(ε).

7. Lower Bounds for the Operator Norm

Having obtained a norm drop for R_{λ,β} in (60) for a fixed L_{1} neighborhood of M, we now move on to the second step of the main theorem’s proof, i.e. proving a norm drop for ∥R_{λ}f∥_{1} for all f outside an ε neighborhood of M.

We first recall notation from Section 2. Fix 0 < λ_{∗} < 1 and let 0 < η_{∗} < 1 solve

λ_{∗} = 2η_{∗}γ_{1}(η_{∗}).

For any λ, α > 0, define

η := \frac{λ}{α},  η_{∗} := \frac{λ_{∗}}{α_{∗}}  α_{∗} = 2γ_{1}(η_{∗}).  (61)

(These are the usual Reeds/Davie parameters; numerically λ_{∗} ≈ 0.197479091, η_{∗} ≈ 0.25573, α_{∗} ≈ 0.7722165.) Let f: ℝ^{n} → [−1, 1] satisfy ∥P_{1}f∥_{2} = α. Let u ∈ S^{n−1} be such that

(P_{1}f)(x) = α⟨u, x⟩, ∀ x ∈ ℝ^{n},

and define Z := ⟨u, X⟩ ∼ N(0, 1) for X ∼ γ_{n}. Define the conditional profiles

θ(z) := 𝔼[f(X) | Z = z] ∈ [−1, 1],  ν(z) := 𝔼[f(X)^{2} | Z = z] ∈ [0, 1].  (62)

Assume θ is odd (we will show later there is no loss of generality in assuming this). For any α, λ > 0, z ∈ ℝ, define

A(z) = A_{α}(z) := \frac{|αz − λ| + |αz + λ|}{2},  B(z) = B_{α}(z) := \frac{|αz − λ| − |αz + λ|}{2}. (63)

For z > 0, one has the explicit form

B(z) = \begin{cases}−αz, & 0 < z < η, \\ −λ, & z > η. \end{cases}  (64)

Define, for ξ : ℝ → [−1, 1] satisfying the moment constraint ∫_{ℝ} zξ(z)γ_{1}(z) dz = α,

V_{α,λ}(ξ) := ∫_{ℝ} γ_{1}(z)(A_{α}(z) + ξ(z)B_{α}(z)) dz.  (65)

Let

\begin{aligned}F_{α,λ} & := sup\{V_{α,λ}(ξ) : ξ: ℝ → [−1, 1], |ξ| ≤ 1, ∫_{ℝ} zξ(z)γ_{1}(z)dz = α\}. \\ F_{∗} & := sup_{α,λ>0} F_{α,λ}. \end{aligned}  (66)

Lemma 7.1 (Dual certificate gap formula). For all 0 < α < 1 with |α − α_{∗}| < 1/100, for every feasible ξ (i.e. |ξ| ≤ 1 and ∫_{ℝ} zξ(z)γ_{1}(z) dz = α), one has

F_{α,λ} − V_{α,λ}(ξ) = ∫_{|z|>η}(α|z| − λ) (1 − ξ(z)sign(z)) γ_{1}(z) dz.  (67)

Proof. Step 1: Weak duality. For μ ∈ ℝ, define the dual functional

D_{α}(μ) := ∫_{ℝ} A(z)γ_{1}(z)dz + μα + ∫_{ℝ} |B(z) − μz|γ_{1}(z)dz.  (68)

For any feasible ξ (|ξ| ≤ 1, ∫_{ℝ} zξ(z)γ_{1}(z)dz = α), we have

\begin{aligned}V_{α,λ}(ξ) & =^{(65)} ∫_{ℝ} A(z)γ_{1}(z)dz + ∫_{ℝ} γ_{1}(z)ξ(z)B(z)dz \\ & = ∫_{ℝ} A(z)γ_{1}(z)dz + μα + ∫_{ℝ} ξ(z)(B(z) − μz)γ_{1}(z)dz, \end{aligned}  (69)

where we used the moment constraint to replace ∫_{ℝ} ξ(z)μzγ_{1}(z)dz by μα. Since |ξ| ≤ 1, pointwise ξ(B − μz) ≤ |B − μz|, hence V_{α,λ}(ξ) ≤ D_{α}(μ). Taking the infimum over μ gives V_{α,λ}(ξ) ≤ inf_{μ∈ℝ} D_{α}(μ) and therefore

F_{α,λ} =^{(66)} sup_{\begin{matrix}ξ: ℝ→[−1,1] \\ ∫_{ℝ} zξ(z)γ_{1}(z)dz=α \end{matrix}} V_{α,λ}(ξ) ≤ inf_{μ∈ℝ} D_{α}(μ).  (70)

Step 2: The Reeds dual optimizer μ = −α. Set μ := −α and define the slack

S(z) = S_{α}(z) := B(z) − μz = B(z) + αz,  ∀ z ∈ ℝ.  (71)

Using (64), for z > 0 we have S is odd and

S(z) = \begin{cases}0, & 0 < z < η, \\ αz − λ = α(z − η), & z > η. \end{cases}

By oddness, S(z) < 0 for z < −η and S(z) = 0 for |z| < η.

Step 3: A primal point attaining D_{α}(μ). Let ξ: ℝ → [−1, 1] satisfy ∫_{ℝ} zξ(z)γ_{1}(z)dz = α, and ξ(z) = sign(z) for all |z| > η. (Since |α − α_{∗}| < 1/100, such a ξ exists by e.g. defining ξ(z) to be a · sign(z) for all |z| < η for some a ∈ [−1, 1] and ξ(z) = sign(z) for all |z| > η, so that ∫_{ℝ} zξ(z)γ_{1}(z)dz = 2γ_{1}(η) + 2a(γ_{1}(0) − γ_{1}(η)). When a = 0 and α = α_{∗}, this integral is 2γ_{1}(η_{∗}) = α_{∗}. Choosing a = −1 or a = 1 shows that any intermediate value in [α_{∗} − 1/100, α_{∗} + 1/100] can be achieved, using also e.g. |η − η_{∗}| < 1/100 by (87) below; a = 1 gives \sqrt{2/π} > α_{∗} + .01; when a = −1, η ≥ η_{∗} − .01 ≥ .24 and the integral is ≤ 2γ_{1}(.24) − 2(γ_{1}(0) − γ_{1}(.24)) ≤ .753 < α_{∗} − .01.) Then ξ(z) = sign(S(z)) for all |z| > η, and S(z) = 0 for all |z| < η, so ξ(z)S(z) = |S(z)| for all z ∈ ℝ, and

V_{α,λ}(ξ) =^{(69)∧(71)} ∫_{ℝ} A(z)γ_{1}(z)dz + μα + ∫_{ℝ} ξ(z)S(z)γ_{1}(z)dz

= ∫_{ℝ} A(z)γ_{1}(z)dz + μα + ∫_{ℝ} |S(z)|γ_{1}(z)dz =^{(68)∧(71)} D_{α}(μ).

Hence F_{α,λ} ≥^{(66)} V_{α,λ}(ξ) = D_{α}(μ). Combined with (70) (F_{α,λ} ≤ inf_{μ∈ℝ} D_{α}(μ)), we get

F_{α,λ} = D_{α}(μ).

Step 4: Gap identity. For any feasible ξ,

F_{α,λ} − V_{α,λ}(ξ) = D_{α}(μ) − V_{α,λ}(ξ) =^{(68)∧(69)∧(71)} ∫_{ℝ} (|S(z)| − ξ(z)S(z))γ_{1}(z)dz.

On |z| < η, S(z) = 0 so the integrand vanishes. On z > η, S(z) = αz − λ > 0, so |S(z)|−ξS(z) = (1−ξ(z))(αz −λ). Similarly, on z < −η, S(z) = λ−α|z|, |S(z)| = α|z|−λ, so |S(z)| − ξ(z)S(z) = (α|z| − λ)(1 − sign(z)ξ(z)). □

8. Lower Bounds and L1 Distance

In the previous section, we showed that when |θ| ≠ 1 for |z| > η, θ = θ_{f} does not optimize ∥R_{λ}f∥_{1}. In this section, we upgrade this statement to: if θ is far from the optimal set Θ in the L_{1} norm, then θ does not optimize ∥R_{λ}f∥_{1}, in Lemmas 8.2 and 8.3.

Δ = Δ_{η_{∗}} := |∫_{−η_{∗}}^{η_{∗}} z θ(z)γ_{1}(z) dz| .  (72)

d := inf_{ξ∈Θ} ∥θ − ξ∥_{1}.

Lemma 8.1. If Δ ≤ η_{∗}d/4 and if θ: ℝ → [−1, 1], then

∫_{|z|>η_{∗}}(1 − θ(z)sign(z))γ_{1}(z) dz ≥ \frac{1}{2} d.  (73)

Proof. We explicitly construct ξ ∈ Θ and bound ∥θ − ξ∥_{1}.

Step 1: Fix the tail to match Θ. Define \overline{θ}: ℝ → ℝ by setting \overline{θ}(z) = sign(z) for |z| > η_{∗} and \overline{θ}(z) = θ(z) for |z| ≤ η_{∗}. Then |\overline{θ}| ≤ 1, and \overline{θ}(z) = 1 for all z > η_{∗}. Moreover, on the tail |z| > η_{∗} we have \overline{θ}(z) − θ(z) = sign(z) − θ(z), so

∥θ − \overline{θ}∥_{1} = ∫_{|z|>η_{∗}}(1 − θ(z)sign(z))γ_{1}(z) dz.  (74)

Step 2: Correct the inner moment by modifying on a set S ⊂ [η_{∗}/2, η_{∗}]. Let

Δ′ := ∫_{0}^{η_{∗}} z \overline{θ}(z)γ_{1}(z) dz = ∫_{0}^{η_{∗}} z θ(z)γ_{1}(z) dz,  Δ = |Δ′|.  (75)

We want to change \overline{θ} on (−η_{∗}, η_{∗}) so that the new function ξ satisfies ∫_{−η_{∗}}^{η_{∗}} z ξ(z)γ_{1}(z) dz = 0. Let s := sign(Δ′) ∈ {−1, +1} (with s = +1 if Δ′ = 0).

Consider the nonnegative integrable function on η_{∗}/2 < |z| < η_{∗}

g(z) := z(sign(z) + s θ(z))γ_{1}(z) ≥ 0.

We claim

∫_{η_{∗}/2<|z|<η_{∗}} g(z) dz ≥ Δ.  (76)

Assuming this claim for a moment, define G(t) := ∫_{η_{∗}/2<|z|<t} g(z) dz for t ∈ [η_{∗}/2, η_{∗}]. Then G is continuous, G(η_{∗}/2) = 0, and G(η_{∗}) ≥ Δ by (76), so by the intermediate value theorem there exists t_{0} ∈ [η_{∗}/2, η_{∗}] such that G(t_{0}) = Δ. Set S := {z ∈ ℝ: η_{∗}/2 < |z| < t_{0}}; then

∫_{S} z(sign(z) + sθ(z))γ_{1}(z) dz = Δ.  (77)

Now define ξ on (−η_{∗}, η_{∗}) by

ξ(z) := \begin{cases}−s · sign(z), & z ∈ S, \\ θ(z), & z ∈ (−η_{∗}, η_{∗}) \ S, \end{cases}  (78)

and on the tails set ξ(z) = sign(z) for |z| > η_{∗}. Then |ξ| ≤ 1, and ξ(z) = 1 for z > η_{∗}.

Finally, we show ∫_{−η_{∗}}^{η_{∗}} ξ(z)zγ_{1}(z)dz = 0: if Δ′ > 0 then s = +1 and on S we changed θ to −1, so the inner moment Δ′ decreases by ∫_{S} z(θ(z) + sign(z))γ_{1}(z) dz = Δ (by (77)), hence ∫_{−η_{∗}}^{η_{∗}} ξ(z)zγ_{1}(z)dz = 0. If Δ′ < 0 then s = −1 and on S we changed θ to +1, increasing the inner moment by ∫_{S} z(sign(z) − θ(z))γ_{1}(z) dz = Δ, again making it 0. Thus ξ ∈ Θ.

Step 3: Bound the L_{1} cost of the inner correction. On S we have

|θ(z) − ξ(z)| =^{(78)} |θ(z) − (−s)sign(z)| = |s(θ(z) + s · sign(z))| = 1 + sθ(z)sign(z) ∈ [0, 2],

so

∫_{S} |θ(z) − ξ(z)|γ_{1}(z)dz = ∫_{S}(1 + sθ(z)sign(z))γ_{1}(z)dz  (79)

Now use that |z| ≥ η_{∗}/2 on S ⊂ {z ∈ ℝ: η_{∗}/2 < |z| < η_{∗}} and 1 + sθ · sign(z) ≥ 0 on S:

Δ =^{(77)} ∫_{S} z(sign(z) + sθ(z))γ_{1}(z)dz ≥ \frac{η_{∗}}{2} ∫_{S}(1 + sθ(z)sign(z))γ_{1}(z)dz,

Insert this into (79) to get

∫_{S} |θ(z) − ξ(z)|γ_{1}(z)dz ≤ \frac{2Δ}{η_{∗}}.

Combining this with (78) gives

∫_{|z|<η_{∗}} |\overline{θ}(z) − ξ(z)|γ_{1}(z)dz = ∫_{|z|<η_{∗}} |θ(z) − ξ(z)|γ_{1}(z)dz ≤ \frac{2Δ}{η_{∗}}.  (80)

Step 4: Combine tail + inner costs. Using ∥θ − ξ∥_{1} ≤ ∥θ − \overline{θ}∥_{1} + ∥\overline{θ} − ξ∥_{1} (or directly summing disjoint supports: tail vs. inner strip), combining (74) and (80) gives

∥θ − ξ∥_{1} ≤ ∫_{|z|>η_{∗}} |1 − θ(z)sign(z)|γ_{1}(z) dz + \frac{2}{η_{∗}} Δ,  (81)
d ≤ ∫_{|z|>η_{∗}} |1 − θ(z)sign(z)|γ_{1}(z) dz + \frac{2}{η_{∗}} Δ,  (82)

Step 5: One-line consequence: Δ small forces tail defect. If Δ ≤ \frac{η_{∗}}{4} d, then (82) implies

∫_{|z|>η_{∗}} |1 − θ(z)sign(z)|γ_{1}(z)dz ≥ d − \frac{2}{η_{∗}} Δ ≥ \frac{d}{2},

which is (73).

Proof of the capacity claim (76). It remains to prove ∫_{η_{∗}/2<|z|<η_{∗}} z(sign(z)+sθ(z))γ_{1}(z)dz ≥ |Δ′|. Assume first Δ′ ≥ 0, so s = +1 and Δ = Δ′. Then

∫_{η_{∗}/2<|z|<η_{∗}} z(sign(z) + θ(z))γ_{1}(z)dz = ∫_{η_{∗}/2<|z|<η_{∗}} zθ(z)γ_{1}(z)dz + ∫_{η_{∗}/2<|z|<η_{∗}} |z|γ_{1}(z)dz

=^{(75)} Δ′ − ∫_{−η_{∗}/2}^{η_{∗}/2} zθ(z)γ_{1}(z)dz + ∫_{η_{∗}/2<|z|<η_{∗}} |z|γ_{1}(z)dz.

Since θ ≤ 1, we have ∫_{−η_{∗}/2}^{η_{∗}/2} zθ(z)γ_{1}(z)dz ≤ ∫_{−η_{∗}/2}^{η_{∗}/2} |z|γ_{1}(z)dz. Taking antiderivatives shows

∫_{η_{∗}/2<|z|<η_{∗}} |z|γ_{1}(z)dz ≥ ∫_{−η_{∗}/2}^{η_{∗}/2} |z|γ_{1}(z)dz. Therefore the last two terms satisfy

− ∫_{−η_{∗}/2}^{η_{∗}/2} zθ(z)γ_{1}(z)dz + ∫_{η_{∗}/2<|z|<η_{∗}} |z|γ_{1}(z)dz ≥ 0,

and we conclude ∫_{η_{∗}/2<|z|<η_{∗}} z(sign(z) + θ(z))γ_{1}(z)dz ≥ Δ′.

If Δ′ < 0, then s = −1 and Δ = −Δ′. The same argument (using θ ≥ −1) gives

∫_{η_{∗}/2<|z|<η_{∗}} z(sign(z) − θ(z))γ_{1}(z)dz = ∫_{η_{∗}/2<|z|<η_{∗}} |z|γ_{1}(z)dz − ∫_{η_{∗}/2<|z|<η_{∗}} zθ(z)γ_{1}(z)dz

=^{(75)} −Δ′ + ∫_{η_{∗}/2<|z|<η_{∗}} |z|γ_{1}(z)dz + ∫_{−η_{∗}/2}^{η_{∗}/2} zθ(z)γ_{1}(z)dz

≥ −Δ′ + ∫_{η_{∗}/2<|z|<η_{∗}} |z|γ_{1}(z)dz − ∫_{−η_{∗}/2}^{η_{∗}/2} |z|γ_{1}(z)dz ≥ −Δ′ =^{(72)} Δ.

This proves (76), thereby completing the proof. □

Lemma 8.2. Let α :=^{(10)} ∫_{ℝ} zθ(z)γ_{1}(z)dz. If Δ ≤ η_{∗}d/4, |α−α_{∗}| < 1/100, and d−2.6|α−α_{∗}| >

0 then

F_{α,λ} − V_{α,λ}(θ) ≥ \frac{(d − 2.6|α − α_{∗}|)^{2}}{32.7} .

Proof. Define for |z| ≥ η the tail deficit δ(z) := 1 − θ(z)sign(z) ∈ [0, 2], and set

m = m_{η} := ∫_{|z|>η} δ(z)γ_{1}(z) dz,  J = J_{η} := ∫_{|z|>η}(|z| − η) δ(z)γ_{1}(z) dz.  (83)

Let

t := \frac{m}{8γ_{1}(η)}.  (84)

Since γ_{1} is decreasing on [η, ∞),

∫_{η<|z|<η+t} γ_{1}(z) dz ≤ 2tγ_{1}(η) =^{(84)} \frac{m}{4}.

Using δ ≤ 2, we get

∫_{η<|z|<η+t} δ(z)γ_{1}(z) dz ≤ 2 ∫_{η<|z|<η+t} γ_{1}(z) dz ≤ \frac{m}{2},

hence ∫_{|z|>η+t} δ(z)γ_{1}(z)dz ≥^{(83)} m/2. For |z| ∈ [η + t, ∞) we have |z| − η ≥ t, so

J =^{(83)} ∫_{|z|>η}(|z| − η)δ(z)γ_{1}(z)dz ≥ t ∫_{|z|>η+t} δ(z)γ_{1}(z)dz ≥ t · \frac{m}{2} =^{(84)} \frac{m^{2}}{16γ_{1}(η)}. (85)

We then apply Lemma 8.1, which says m_{η_{∗}} ≥ d/2. Therefore, writing m = m − m_{η_{∗}} + m_{η_{∗}}, from (83) and (87) below, |m−m_{η_{∗}}| ≤ 4|η−η_{∗}|/\sqrt{2π} ≤ 1.3|α−α_{∗}|, so if d/2−1.3|α−α_{∗}| > 0, then

F_{α,λ} − V_{α,λ}(θ) =^{(67)∧(61)} αJ ≥^{(85)} α\frac{(d/2 − 1.3|α − α_{∗}|)^{2}}{16γ_{1}(η)} ≥^{(89)} \frac{(d − 2.6|α − α_{∗}|)^{2}}{32.7} . (86)

In the last inequality, we used η =^{(61)} λ/α and η_{∗} = λ/α^{∗}, α_{∗} =^{(61)} 2γ_{1}(η_{∗}). If α, α_{∗} > 1/2 and λ < .2, we have

|η − η_{∗}| = λ|α^{−1} − α_{∗}^{−1}| = λ|α − α_{∗}|/(αα_{∗}) ≤ (4/5)|α − α_{∗}|.  (87)
|γ_{1}(η) − γ_{1}(η_{∗})| ≤ \frac{1}{4}|η − η_{∗}| ≤ \frac{1}{5}|α − α_{∗}|.  (88)

|\frac{α}{2γ_{1}(η)} − \frac{α_{∗}}{2γ_{1}(η_{∗})}| = |\frac{α − α_{∗}}{2γ_{1}(η)} − α_{∗}(\frac{1}{2γ_{1}(η_{∗})} − \frac{1}{2γ_{1}(η)})| ≤ |\frac{α − α_{∗}}{2γ_{1}(η)} | + |α_{∗} \frac{γ_{1}(η) − γ_{1}(η_{∗})}{2γ_{1}(η)γ_{1}(η_{∗})}|.

So if |α − α_{∗}| < 1/100 with α_{∗} = .7722 …, and η_{∗} = .25573 …, we get γ_{1}(η) ≥ .387, and

\frac{α}{2γ_{1}(η)} ≥ 1 − \frac{.01}{2(.387)} − .7722\frac{.01/5}{2 · .387 · .386} ≥ .98.  (89)

□

Lemma 8.3 (Complementary regime, Odd Case: large Δ forces a direct gap). Let θ: ℝ →

[−1, 1] be odd. Let α :=^{(10)} ∫_{ℝ} zθ(z)γ_{1}(z)dz. Let d := inf_{\overline{θ}∈Θ} ∥θ − \overline{θ}∥_{1} and let

Δ = Δ_{η_{∗}} := |∫_{−η_{∗}}^{η_{∗}} z θ(z)γ_{1}(z) dz| .

Assume |α − α_{∗}| < 1/100. Assume ∫_{−η}^{η} zθ(z)γ_{1}(z)dz ≥ 0, and

Δ ≥ \frac{η_{∗}}{4} d.  (90)

Then, if \frac{1}{8} d(1 − 4|α − α_{∗}|) − 6.4|α − α^{∗}| > 0,

F_{α,λ} − V_{α,λ}(θ) ≥ min [d(\frac{λ}{8} − |α − α_{∗}|), \frac{.98}{8} (\frac{1}{8} d(1 − 4|α − α_{∗}|) − 6.4|α − α^{∗}|)^{2} ]. (91)

Proof. Let δ(z) = 1 − θ(z) for z ≥ η and define m, J as in (83). We split into two subcases. Case 1: J ≥ Δ/2. Then by the gap formula (67) and (61)

F_{α,λ} − V_{α,λ}(θ) = αJ ≥ αΔ/2.

Using Δ ≥ (η_{∗}/4)d and α_{∗}η_{∗} =^{(61)} λ gives

F_{α,λ} − V_{α,λ}(θ) ≥ α · \frac{η_{∗}}{8} d = (α − α_{∗})\frac{η_{∗}}{8} d + α_{∗} \frac{η_{∗}}{8} d ≥ d(\frac{λ}{8} − |α − α_{∗}|).

Case 2: J < Δ/2. Let s := sign(∫_{0}^{η} zθ(z)γ_{1}(z)dz) (and s = 1 if the integral is zero). We first show that (defining Δ_{η} := | ∫_{−η}^{η} zθ(z)γ_{1}(z)dz|)

ηm + J = sΔ_{η} − (α − 2γ_{1}(η)).  (92)

This follows since (recalling θ is odd), by definition of α

α = 2 ∫_{0}^{η} zθ(z)γ_{1}(z)dz + 2 ∫_{η}^{∞} zθ(z)γ_{1}(z)dz

= 2 ∫_{0}^{η} zθ(z)γ_{1}(z)dz + 2γ_{1}(η) − 2 ∫_{η}^{∞} z(1 − θ(z))γ_{1}(z)dz

=^{(83)} sΔ_{η} + 2γ_{1}(η) − (ηm + J).

By assumption s = 1. Now, from (92) and α_{∗}/2 = γ_{1}(η_{∗}) (by (22))

ηm = Δ_{η} − J − (α − 2γ_{1}(η))

= Δ_{η} − J − (α − α_{∗} − 2γ_{1}(η) + 2γ_{1}(η_{∗}))

≥^{(88)} Δ_{η} − Δ + sΔ − J − |α − α_{∗}| − 2|α − α_{∗}|/5

≥ Δ/2 − |Δ_{η} − Δ| − |α − α_{∗}| − 2|α − α_{∗}|/5

≥^{(87)} Δ/2 − .173|α − α_{∗}| − |α − α_{∗}| − 2|α − α_{∗}|/5

(By definition, |Δ_{η} − Δ| ≤ \frac{2}{\sqrt{2π}} max(η, η_{∗})|η − η_{∗}| ≤^{(87)} \frac{2}{\sqrt{2π}}(.27)(4/5)|α − α_{∗}|.) In summary,

ηm > Δ/2 − 1.6|α − α_{∗}|.

Using Δ ≥ (η_{∗}/4)d

m > \frac{Δ}{2η} − \frac{1.6}{η}|α − α_{∗}| ≥ \frac{1}{8} \frac{η_{∗}}{η} d − 6.4|α − α^{∗}| ≥ \frac{1}{8} d(1 − 4|α − α_{∗}|) − 6.4|α − α^{∗}|. (93)

Therefore, if \frac{1}{8} d(1 − 4|α − α_{∗}|) − 6.4|α − α^{∗}| > 0,

F_{α,λ} −V_{α,λ}(θ) =^{(67)} αJ ≥^{(85)} α· \frac{m^{2}}{16γ_{1}(η)} ≥^{(89)} \frac{.98}{8} m^{2} ≥^{(93)} \frac{.98}{8} (\frac{1}{8} d(1 − 4|α − α_{∗}|) − 6.4|α − α^{∗}|)^{2} .

Combining the Case 1 and Case 2 yields (91). □

9. Tail Equality

Let θ: ℝ → [−1, 1]. Define θ^{odd}(z) := (θ(z) − θ(−z))/2, ∀ z ∈ ℝ.

Lemma 9.1. Let x, y ∈ [−1, 1]. Let s := \frac{x−y}{2}. Then

\frac{|1 − x| + | − 1 − y|}{2} = |1 − s|.

Consequently, choosing x = θ(z) and y = θ(−z), upon integration we get

∫_{|z|>η} |sign(z) − θ(z)|γ_{1}(z)dz = ∫_{|z|>η} |sign(z) − θ^{odd}(z)|γ_{1}(z)dz.

Proof. Since x ≤ 1 and y ≥ −1 the left side is

[1 − x + 1 + y]/2 = [2 − x + y]/2 = 1 − (x − y)/2.

Similarly, since s ≤ 1, the right side is |1 − s| = 1 − s = 1 − (x − y)/2. The final assertion follows from the first after writing

∫_{|z|>η} |sign(z) − θ(z)|γ_{1}(z)dz = ∫_{z>η} (|1 − θ(z)| + | − 1 − θ(−z)|)γ_{1}(z)dz
= ∫_{z>η} 2|1 − θ^{odd}(z)|γ_{1}(z)dz = ∫_{|z|>η} |sign(z) − θ^{odd}(z)|γ_{1}(z)dz.
□

10. Proof of Main Theorem

Proof of Theorem 1.1. Since we let n → ∞ to prove Theorem 1.1, we assume below that n ≥ 2 (though the proof also works when n = 1, in which case we just choose A := ∅ below). Fix ε := 10^{−7}. Let f: ℝ^{n} → [−1, 1] maximize ∥R_{λ,β}f∥_{1}. (We may assume f takes values in {−1, 1} by convexity.) Let d := inf_{g∈M} ∥f − g∥_{1}. Define α := ∥ ∫_{ℝ^{n}} xf(x)γ_{n}(x)dx∥_{ℓ_{2}(ℝ^{n})}.

Case 1. If d < ε, then apply (60) to get

∥R_{λ,β}f∥_{1} ≤ ∥R_{λ}∥_{∞→1} − β(.0057), ∀ 0 < β < 10^{−10}.

Case 2. Suppose d ≥ ε.

Define

θ(z) = θ_{f}(z) := 𝔼[f | P_{1}f = αz],  ∀ z ∈ ℝ.  (94)

Then α =^{(94)} ∫_{ℝ} zθ(z)γ_{1}(z)dz. Let α_{∗} := .772216503281451 …

Sub-Case 2.1. Suppose |α − α_{∗}| > 10^{−12}. Then Lemma 2.2 implies that

∥R_{λ}f∥_{1} ≤ ∥R_{λ}∥_{∞→1} − \frac{9}{10} min((α − α_{∗})^{2}, 1/100).  (95)

Therefore, by the L_{1} triangle inequality and the last part of Lemma 6.1

∥R_{λ,β}f∥_{1} ≤^{(6)} ∥R_{λ}f∥_{1} + β∥P_{3}f∥_{1} ≤^{(95)} ∥R_{λ}∥_{∞→1} − \frac{9}{10} · 10^{−24} + β.

Sub-Case 2.2. Suppose |α − α_{∗}| < 10^{−12}. We have by the triangle inequality and the last part of Lemma 6.1

∥R_{λ,β}f∥_{1} ≤^{(6)} ∥R_{λ}f∥_{1} + β∥P_{3}f∥_{1} ≤ ∥R_{λ}f∥_{1} + β =^{(65)} V_{α,λ}(θ_{f}) + β.  (96)

By definition (65), the odd part of θ_{f} satisfies V_{α,λ}(θ_{f}) = V_{α,λ}(θ_{f}^{odd}), so

∥R_{λ,β}f∥_{1} ≤^{(96)} V_{α,λ}(θ_{f}^{odd}) + β.  (97)

Denote

d′ := inf_{\overline{θ}∈Θ} ∥\overline{θ} − θ_{f}^{odd}∥_{1}.

Sub-Case 2.2.1. Suppose d′ > 10^{−10}. We can then apply (91) and Lemma 8.2 to get

\begin{aligned}∥R_{λ,β}f∥_{1} & ≤^{(97)} F_{α,λ} + β − min [d′(\frac{λ}{8} − |α − α_{∗}|), \frac{.98}{8} (\frac{1}{8} d′(1 − 4|α − α_{∗}|) − 6.4|α − α^{∗}|)^{2} ] \\ & ≤ ∥R_{λ}∥_{∞→1} + β − \frac{.98}{8} (\frac{10^{−10}}{8} (1 − 10^{−10}) − 6.4 · 10^{−12})^{2} ]. \end{aligned}

(98)

(When we apply (91) we need to verify that Δ′_{η} := ∫_{−η}^{η} zθ_{f}^{odd}(z)γ_{1}(z)dz ≥ 0. Since η, m, J > 0, (92) implies that Δ′_{η} ≥ α −2γ_{1}(η). Since |α −α_{∗}| < 10^{−12}, we have α −2γ_{1}(η) ≥ −(7/5)|α − α_{∗}| ≥ −(7/5)10^{−12} by (88). So, if Δ′_{η} < 0, we get |Δ′_{η}| ≤ (7/5)10^{−12}, but (91) assumes Δ ≥ η_{∗}d′/4 ≥ 10^{−10}/16, and

Δ = |Δ′_{η_{∗}} − Δ′_{η} + Δ′_{η}| ≤^{(87)} \frac{7}{5}10^{−12} + 2|η − η_{∗}|(.26)γ_{1}[−η_{∗}, η_{∗}] ≤ \frac{7}{5}10^{−12} + .09 · 10^{−12}

which contradicts Δ ≥ 10^{−10}/16. That is, we have verified that Δ′_{η} ≥ 0, as desired.)

Sub-Case 2.2.2. Suppose d′ ≤ 10^{−10}. Since each \overline{θ} ∈ Θ satisfies \overline{θ}(z) = sign(z) for all |z| > η_{∗}, we have

∫_{|z|>η_{∗}} |sign(z) − θ_{f}^{odd}(z)|γ_{1}(z)dz ≤ d′.

By Lemma 9.1, we then have

∫_{|z|>η_{∗}} |sign(z) − θ_{f}(z)|γ_{1}(z)dz ≤ d′.  (99)

We will show this contradicts d ≥ ε. Let u := ∫_{ℝ^{n}} xf(x)γ_{n}(x)dx ∈ ℝ^{n}. (u ≠ 0 since ∥u∥ = α and |α−α_{∗}| < 10^{−12}.) Denote ∥u∥ := ∥u∥_{ℓ_{2}(ℝ^{n})}. For any v ∈ ℝ^{n} with ⟨v, u⟩ = 0 and ∥v∥ = 1, we have by rearrangement

| ∫_{|⟨ \frac{u}{∥u∥} ,x⟩|>η_{∗}}⟨v, x⟩f(x)γ_{n}(x)dx|

= | ∫_{|⟨ \frac{u}{∥u∥} ,x⟩|>η_{∗}}⟨v, x⟩(f(x) − sign(⟨u, x⟩))γ_{n}(x)dx|

≤ 2 ∫_{−Φ^{−1}((5/4)d′)}^{∞} sγ_{1}(s)ds = 2γ_{1}(−Φ^{−1}((5/4)d′))
≤ .583 · 2.5 · d′ log(1/[(5/4)d′]) ≤ 3.33 · 10^{−9}.

(100)

That is, the integrand is largest when f = −sign(⟨u, x⟩) for ⟨v, x⟩ > a for some a > 0, so the integral is bounded by 2 times the length of the Gaussian moment of a half space with measure at most (5/4)d′. Here we used γ_{1}(a) ≤ .583Φ(−a) log(1/Φ(−a)) ∀ a ≥ 2.3. By definition of u and ⟨v, u⟩ = 0, we have ∫_{ℝ^{n}}⟨v, x⟩f(x)γ_{n}(x)dx = ⟨v, u⟩ = 0, so that

| ∫_{|⟨ \frac{u}{∥u∥} ,x⟩|<η_{∗}}⟨v, x⟩f(x)γ_{n}(x)dx| ≤^{(100)} 3.33 · 10^{−9}.

Let δ := 3.33 · 10^{−9}/.0805 ≤ 4.2 · 10^{−8}. Let ṽ ∈ ℝ^{n} with ⟨ṽ, u⟩ = 0 and ṽ ≠ 0 (since n ≥ 2 this is possible). Let A := \{x ∈ ℝ^{n}: |⟨\frac{u}{∥u∥}, x⟩| < η_{∗}, ⟨\frac{ṽ}{∥ṽ∥}, x⟩ ≥ 0\}. Choose ṽ such that ∫_{A} xγ_{n}(x)dx is parallel to the part of the vector ∫_{{x∈ℝ^{n}: |⟨x,u/∥u∥⟩|<η_{∗}}} xf(x)γ_{n}(x)dx that is perpendicular to u. Then γ_{n}(A) = γ_{1}[−η_{∗}, η_{∗}]/2 ≈ .10092, ∫_{A}⟨x, u⟩γ_{n}(x)dx = 0, ∥ ∫_{A} xγ_{n}(x)dx∥ = γ_{1}[−η_{∗}, η_{∗}] ∫_{0}^{∞} sγ_{1}(s)ds > .0805. So, replacing ṽ with −ṽ if necessary, there exists 0 < δ′ ≤ δ such that

⟨v, δ′ ∫_{A} xγ_{n}(x)dx + ∫_{|⟨ \frac{u}{∥u∥} ,x⟩|<η_{∗}} xf(x)γ_{n}(x)dx⟩ = 0,  ∀ v ∈ ℝ^{n} with ⟨v, u⟩ = 0. (101)

That is, the inner Gaussian moment of f can be made parallel to u by adding a δ′1_{A} to f. To make this moment zero, we add a multiple of 1_{B} where B := \{x ∈ ℝ^{n}: 0 ≤ ⟨\frac{u}{∥u∥}, x⟩ < η_{∗}\}. Then ∫_{B} xγ_{n}(x)dx = \frac{u}{∥u∥}(1 − e^{−η_{∗}^{2}/2})/\sqrt{2π} ≈ \frac{u}{∥u∥}.012834, γ_{n}(B) = γ_{1}[0, η_{∗}] ≈ .10092, and by definition of α,

α = ∫_{ℝ} θ_{f}(z)zγ_{1}(z)dz = ∫_{ℝ} θ_{f}^{odd}(z)zγ_{1}(z)dz = ∫_{−η_{∗}}^{η_{∗}} zθ_{f}^{odd}(z)γ_{1}(z)dz + ∫_{|z|>η_{∗}} zθ_{f}^{odd}(z)γ_{1}(z)dz

= ∫_{−η_{∗}}^{η_{∗}} zθ_{f}^{odd}(z)γ_{1}(z)dz + ∫_{|z|>η_{∗}} z[θ_{f}^{odd}(z) − sign(z)]γ_{1}(z)dz + ∫_{|z|>η_{∗}} z · sign(z)γ_{1}(z)dz

Since ∫_{|z|>η_{∗}} |z|γ_{1}(z)dz = 2γ_{1}(η_{∗}) =^{(22)} α_{∗}, and ∫_{|z|>η_{∗}} |z||θ_{f}^{odd}(z) − sign(z)|γ_{1}(z)dz ≤ 3.33 · 10^{−9}

by the same argument as (100), we have by the triangle inequality

| ∫_{−η_{∗}}^{η_{∗}} zθ_{f}^{odd}(z)γ_{1}(z)dz| ≤ |α − α_{∗}| + ∫_{|z|>η_{∗}} |z||θ_{f}^{odd}(z) − sign(z)|γ_{1}(z)dz ≤ 10^{−12} + 3.33 · 10^{−9}.

Consequently, there exists 0 < ω′ ≤ ω := 3.34 · 10^{−9}/.012834 ≤ 2.61 · 10^{−7} such that (after replacing B if necessary with its complement in the strip {x ∈ ℝ^{n}: |⟨x, u/∥u∥⟩| < η_{∗}})

∫_{|⟨ \frac{u}{∥u∥} ,x⟩|<η_{∗}}⟨u, x⟩(ω′ · 1_{B}(x) + f(x))γ_{n}(x)dx = 0.

Combining this with (101), we then define

h := \frac{δ′}{1 + δ′ + ω′} 1_{A} + \frac{ω′}{1 + δ′ + ω′} 1_{B} + \frac{1}{1 + δ′ + ω′} f · 1_{|⟨x, \frac{u}{∥u∥}⟩|<η_{∗}} + sign(⟨x, u⟩)1_{|⟨x, \frac{u}{∥u∥}⟩|>η_{∗}}.

(102)

Then h takes values in [−1, 1], ∫_{ℝ^{n}} xh(x)γ_{n}(x)dx is parallel to u, and θ_{h}(z) := 𝔼(h|⟨x, \frac{u}{∥u∥}⟩ = z) satisfies the conditions of Lemma 2.1 (i.e. ∫_{−η_{∗}}^{η_{∗}} θ_{h}(z)zγ_{1}(z)dz = 0 by (101) and (102), and θ_{h}(z) = sign(z) ∀ |z| > η_{∗}). So, after rotating the domain, we have h ∈ N where N is defined in Lemma 4.2. (By rotation invariance of the Gaussian measure, we may assume u is parallel to the x_{1} axis when applying this Lemma.) Lemma 4.2 says there exists g ∈ M with ∥f − g∥_{1} ≤ ∥f − h∥_{1}. From the Case 2 assumption and the definition of d = inf_{g∈M} ∥f − g∥_{1}, this means ∥f − h∥_{1} ≥ ε. But (102) implies

∥f − h∥_{1} = ∫_{|⟨x, \frac{u}{∥u∥}⟩|<η_{∗}} |f(x) − h(x)|γ_{n}(x)dx + ∫_{|⟨x, \frac{u}{∥u∥}⟩|>η_{∗}} |f(x) − h(x)|γ_{n}(x)dx

≤ (2(δ + w) + w + 2w + δ + w)γ_{1}[−η_{∗}, η_{∗}]/4 + ∫_{|z|>η_{∗}} |θ_{f}(z) − sign(z)|γ_{1}(z)dz

≤^{(99)} (6δ + 6w)(.051) + d′ ≤ (6 · 4.2 · 10^{−8} + 6 · 2.61 · 10^{−7})(.051) + 10^{−10} < 10^{−7}.

This contradicts ∥f − h∥_{1} ≥ ε = 10^{−7}. That is, Sub-Case 2.2.2 does not occur. Combine all cases. Combining the above cases gives (for all 0 < β < 10^{−10})

\begin{aligned}∥R_{λ,β}∥_{∞→1} & ≤ ∥R_{λ}∥_{∞→1} + max [ − β(.0057), β − 9 · 10^{−25}, β − \frac{.9799}{8} (\frac{10^{−10}}{8} − 6.4 · 10^{−12})^{2} ] \\ & ≤ ∥R_{λ}∥_{∞→1} + max [ − β · 5.7 · 10^{−3}, β − 9 · 10^{−25}, β − 4.5 · 10^{−24}]. \end{aligned}

(103)

Choosing β := 8 · 10^{−25} gives

∥R_{λ,β}∥_{∞→1} ≤ ∥R_{λ}∥_{∞→1} − 45.6 · 10^{−28}.

Finally, lim_{n→∞} sup_{g: ℝ^{n}→B_{n}} ∫_{ℝ^{n}} ∥R_{λ}g(x)∥_{ℓ_{2}(ℝ^{n})}γ_{n}(x)dx = 1 − λ by e.g. [R91, Theorem 1], since the function f(x) := x/∥x∥_{2} for all x ∈ ℝ^{n} \ {0} has all of its L_{2} Hermite-Fourier mass on the first level, as n → ∞.

So, (5) completes the proof, since if c := (1 − λ)/∥R_{λ}∥_{∞→1}, with λ = λ_{∗} ≈ .197 …, then ∥R_{λ}∥_{∞→1} ≈ .4788 …, c/∥R_{λ}∥_{∞→1} ≥ 3.5, and

K_{G} ≥^{(5)} \frac{1 − λ}{∥R_{λ}∥_{∞→1} − 45.6 · 10^{−28}} ≥ c + c\frac{45.6 · 10^{−28}}{∥R_{λ}∥_{∞→1}} ≥ c + 159.6 · 10^{−28}.

□

Acknowledgement. Some of the above material was created with the assistance of OpenAI’s ChatGPT 5.2, including some ancillary lemmas and propositions. However, ChatGPT did not contribute to the strategy of this paper; in fact, many of its strategic suggestions were of negative value.

References

[AN04] Noga Alon and Assaf Naor. Approximating the cut-norm via Grothendieck’s inequality. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (STOC ’04). Association for Computing Machinery, New York, NY, USA, 72–80, 2004.

[BMMN13] Mark Braverman, Konstantin Makarychev, Yury Makarychev, and Assaf Naor. The Grothendieck constant is strictly smaller than Krivine’s bound. Forum of Mathematics, Pi. 2013;1:e4. doi:10.1017/fmp.2013.4

[D84] A. M. Davie. A lower bound for K_{G}. Unpublished manuscript, 1984.

[G75] Leonard Gross. Logarithmic Sobolev Inequalities. American Journal of Mathematics. Vol. 97, No. 4, pp. 1061-1083, 1975.

[G53] A. Grothendieck. Resume de la theorie metrique des produits tensoriels topologiques. Bol. Soc. Mat. Sao Paulo, 8:1-79, 1953.

[K02] Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thirty-fourth annual ACM symposium on Theory of computing (STOC ’02). Association for Computing Machinery, New York, NY, USA, 767–775, 2002.

[KN12] S. A. Khot and A. Naor. Grothendieck-type inequalities in combinatorial optimization. Comm. Pure Appl. Math. 65, no. 7, 992–1035, 2012.

[K01] H. König. On an extremal problem originating in questions of unconditional convergence. In Recent progress in multivariate approximation (Witten-Bommerholz, 2000), volume 137 of Internat. Ser. Numer. Math., pages 185-192. Birkhäuser, Basel, 2001.

[K77] J.-L. Krivine. Sur la constante de Grothendieck. C. R. Acad. Sci. Paris Ser. A-B, 284(8):A445-A446, 1977.

[LP68] J. Lindenstrauss and A. Pelczyński. Absolutely summing operators in Lp-spaces and their applications. Studia Math., 29:275-326, 1968.

[P12] Gilles Pisier. Grothendieck’s theorem, past and present. Bull. Amer. Math. Soc. (N.S.) 49, no. 2, 237–323, 2012.

[RS09] P. Raghavendra and D. Steurer. Towards computing the Grothendieck constant. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 525-534, 2009.

[R91] J. A. Reeds. A new lower bound on the real Grothendieck constant. Unpublished manuscript, 1991.

[RN14] Assaf Naor and Oded Regev. Krivine Schemes are Optimal. Proceedings of the American Mathematical Society, vol. 142, no. 12, pp. 4315–20, 2014.

[T87] Tsirel’son, B.S. Quantum analogues of the Bell inequalities. The case of two spatially separated domains. J Math Sci 36, 557–570, 1987.