OctoInformBeta

OpenAI preprint, September 2026 · §3. A Hilbert kernel with chart extensions

The common kernel and rounded chart labels: Positive semidefiniteness for nonnegative weights and Gram identity for positive scale bounds, together with threshold hyperplanes and rounded integer labels

A Hilbert kernel with chart extensions and rounded vertices.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

An integrality gap construction for the Goemans-Linial relaxation of uniform sparsest cut requires a finite vertex set carrying a negative-type semimetric that admits no low-distortion L1L_1 embedding. Starting from a positive integer mm with S=m3S = m^3 direction families of N=m6N = m^6 vectors in ℝm\mathbb{R}^m, the construction discretizes points of an open cube off threshold hyperplanes into rounded integer labels to form a finite vertex set. An integral Hilbert kernel combining Gaussian and Fourier components with linear chart-extension weights then provides the positive semidefinite Gram structure on those vertices.

Direction Families and Kernel Ingredients

The empirical covariance cov(g,v)∈ℝ\mathrm{cov}(g, v) \in \mathbb{R} of an NN-tuple of vectors g=(g1,…,gN)g = (g_1, \dots, g_N) (N∈ℕN \in \mathbb{N}) in a real inner-product space EE along v∈Ev \in E is the real scalar defined in (1): cov(g,v)=1N∑i=1N⟨v,gi⟩2.\mathrm{cov}(g, v) = \frac{1}{N} \sum_{i=1}^{N} \langle v, g_i \rangle^2.(1)✦ Given a natural number NN, vectors g=(g1,…,gN)g = (g_1, \dots, g_N) in a real inner-product space EE, and w∈Ew \in E, the empirical sine transform ψ(g,w)∈E\psi(g, w) \in E is the vector defined in (2): ψ(g,w)=1N∑i=1Nsin⁡(⟨gi,w⟩)gi.\psi(g, w) = \frac{1}{N} \sum_{i=1}^{N} \sin(\langle g_i, w \rangle)\, g_i.(2)✦

Given a real threshold ρ\rho, a natural number NN, and a vector vv in a real inner-product space EE, the bad projection set ℬN(ρ,v)⊂EN\mathcal{B}_N(\rho, v) \subset E^N is the set of NN-tuples defined in (3): ℬN(ρ,v)={y∈EN:|⟨v,yi⟩|>ρ for some 1≤i≤N}.\mathcal{B}_N(\rho, v) = \bigl\{ y \in E^N : |\langle v, y_i \rangle| > \rho \text{ for some } 1 \le i \le N \bigr\}.(3)✦ For an ambient space Ω\Omega, a subset A⊂ΩA \subset \Omega, a natural number SS, and an SS-tuple y=(y1,…,yS)∈ΩSy = (y_1, \dots, y_S) \in \Omega^S, the number of bad samples bad(A,y)∈ℕ\mathrm{bad}(A, y) \in \mathbb{N} is the count defined in (4): bad(A,y)=|{1≤s≤S:ys∈A}|.\mathrm{bad}(A, y) = \bigl|\{ 1 \le s \le S : y_s \in A \}\bigr|.(4)✦

In dimension m∈ℕm \in \mathbb{N} with S=m3S = m^3 and N=m6N = m^6, a direction family ff is a collection of vectors g=(gs,i)1≤s≤S,1≤i≤Ng = (g_{s,i})_{1 \le s \le S,\, 1 \le i \le N} in ℝm\mathbb{R}^m (with ss-th subfamily gs=(gs,1,…,gs,N)g_s = (g_{s,1}, \dots, g_{s,N})) satisfying the conditions (5) for all 1≤s≤S1 \le s \le S, all 1≤i,a,b≤N1 \le i, a, b \le N with a≠ba \ne b, all t∈ℝt \in \mathbb{R}, and all v,w∈ℝmv, w \in \mathbb{R}^m with ∥v∥=1\|v\| = 1 and ∥w∥≤m42\|w\| \le m^{42}: m2≤∥gs,i∥≤2m,gs,a≠tgs,b,12≤cov(gs,v)≤2,∥ψ(gs,w)−e−∥w∥2/2w∥≤2m,bad(ℬN(11log⁡m,v),(g1,…,gS))≤m32.\begin{aligned} \frac{\sqrt{m}}{2} &\le \|g_{s,i}\| \le 2\sqrt{m}, & g_{s,a} &\ne t\, g_{s,b}, \\ \frac{1}{2} &\le \mathrm{cov}(g_s, v) \le 2, & \bigl\|\psi(g_s, w) - e^{-\|w\|^2/2} w\bigr\| &\le \frac{2}{\sqrt{m}}, \\ \mathrm{bad}\bigl(\mathcal{B}_N(11\sqrt{\log m}, v),\, (g_1, \dots, g_S)\bigr) &\le \frac{m^3}{2}. && \end{aligned}(5)✦ A pivoted direction family ff of dimension m∈ℕm \in \mathbb{N} is a direction family (gs,i)1≤s≤m3,1≤i≤m6(g_{s,i})_{1 \le s \le m^3,\, 1 \le i \le m^6} in ℝm\mathbb{R}^m whose coordinates satisfy |gs,i,j|>1/m30|g_{s,i,j}| > 1/m^{30} for all 1≤s≤m31 \le s \le m^3, 1≤i≤m61 \le i \le m^6, and 1≤j≤m1 \le j \le m. For a direction family ff of dimension m∈ℕm \in \mathbb{N} with vectors (gs,i)1≤s≤m3,1≤i≤m6(g_{s,i})_{1 \le s \le m^3,\, 1 \le i \le m^6}, the normalized directions us,iu_{s,i} of ff are the vectors in ℝm\mathbb{R}^m defined for 1≤s≤m31 \le s \le m^3 and 1≤i≤m61 \le i \le m^6 by us,i=gs,i/mu_{s,i} = g_{s,i}/\sqrt{m}.

The inverse power p(x,n)∈ℝp(x, n) \in \mathbb{R} of a real number xx and a natural number nn is the scalar p(x,n)=1/xnp(x, n) = 1/x^n.✦

The circle embedding γ(t,ζ)∈ℝ2\gamma(t, \zeta) \in \mathbb{R}^2 of real parameters tt and ζ\zeta is the Euclidean plane vector defined in (6): γ(t,ζ)=(cos⁡t−ζsin⁡t,sin⁡t+ζcos⁡t).\gamma(t, \zeta) = (\cos t - \zeta \sin t,\, \sin t + \zeta \cos t).(6)✦ For a finite index set 𝒦\mathcal{K}, directions (gi)i∈𝒦(g_i)_{i \in \mathcal{K}} in a real inner-product space EE, real parameters q,ε,σ∈ℝq, \varepsilon, \sigma \in \mathbb{R}, points θ,η∈E\theta, \eta \in E, and real functions α,β:𝒦→ℝ\alpha, \beta : \mathcal{K} \to \mathbb{R}, the kernel pairing Pg,q,ε,σ(θ,η;α,β)∈ℝP_{g,q,\varepsilon,\sigma}(\theta, \eta; \alpha, \beta) \in \mathbb{R} is the scalar defined in (7): Pg,q,ε,σ(θ,η;α,β)=qexp⁡(−∥η−θ∥22σ2)+εσ∑i∈𝒦((1+αiβi)cos(⟨gi,η−θ⟩σ)+(αi−βi)sin(⟨gi,η−θ⟩σ)).P_{g,q,\varepsilon,\sigma}(\theta, \eta; \alpha, \beta) = q \exp\!\left(-\frac{\|\eta - \theta\|^2}{2\sigma^2}\right) + \frac{\varepsilon}{\sigma} \sum_{i \in \mathcal{K}} \left( (1 + \alpha_i \beta_i)\cos\!\left(\frac{\langle g_i, \eta - \theta \rangle}{\sigma}\right) + (\alpha_i - \beta_i)\sin\!\left(\frac{\langle g_i, \eta - \theta \rangle}{\sigma}\right) \right).(7)✦ Given a finite index set 𝒦\mathcal{K} and an index set ℐ\mathcal{I}, directions (gi)i∈𝒦(g_i)_{i \in \mathcal{K}} and points (θv)v∈ℐ(\theta_v)_{v \in \mathcal{I}} in a real inner-product space EE, weight functions (αv)v∈ℐ(\alpha_v)_{v \in \mathcal{I}} with αv:𝒦→ℝ\alpha_v : \mathcal{K} \to \mathbb{R}, and real parameters q,ε,a,b∈ℝq, \varepsilon, a, b \in \mathbb{R}, the kernel Gram matrix Gg,θ,α,q,ε,a,b∈ℝℐ×ℐG_{g,\theta,\alpha,q,\varepsilon,a,b} \in \mathbb{R}^{\mathcal{I} \times \mathcal{I}} is the real matrix whose (v,w)(v, w)-entry is defined in (8): Gg,θ,α,q,ε,a,b(v,w)=q∫abexp⁡(−∥θv−θw∥22σ2)dσ+ε∑i∈𝒦∫ab1σ⟨γ(⟨gi,θv⟩σ,αv(i)),γ(⟨gi,θw⟩σ,αw(i))⟩dσ.G_{g,\theta,\alpha,q,\varepsilon,a,b}(v, w) = q \int_a^b \exp\!\left(-\frac{\|\theta_v - \theta_w\|^2}{2\sigma^2}\right) d\sigma + \varepsilon \sum_{i \in \mathcal{K}} \int_a^b \frac{1}{\sigma} \left\langle \gamma\!\left(\frac{\langle g_i, \theta_v \rangle}{\sigma}, \alpha_v(i)\right),\, \gamma\!\left(\frac{\langle g_i, \theta_w \rangle}{\sigma}, \alpha_w(i)\right) \right\rangle d\sigma.(8)

The Claim

Definition 1. Given a finite index set 𝒦\mathcal{K}, directions (gi)i∈𝒦(g_i)_{i \in \mathcal{K}} in a real inner-product space EE, real parameters q,ε,a,bq, \varepsilon, a, b, points θ,η∈E\theta, \eta \in E, and real functions α,β:𝒦→ℝ\alpha, \beta : \mathcal{K} \to \mathbb{R}, the Hilbert kernel Kg,q,ε,a,b(θ,η;α,β)∈ℝK_{g,q,\varepsilon,a,b}(\theta, \eta; \alpha, \beta) \in \mathbb{R} is the real scalar defined in (9): Kg,q,ε,a,b(θ,η;α,β)=∫abPg,q,ε,σ(θ,η;α,β)dσ.K_{g,q,\varepsilon,a,b}(\theta, \eta; \alpha, \beta) = \int_a^b P_{g,q,\varepsilon,\sigma}(\theta, \eta; \alpha, \beta)\, d\sigma.(9)✦

Theorem 1. Let 𝒦\mathcal{K} be a finite index set, let ℐ\mathcal{I} be an index set, let (gi)i∈𝒦(g_i)_{i \in \mathcal{K}} and (θv)v∈ℐ(\theta_v)_{v \in \mathcal{I}} be families of vectors in a real inner-product space EE, let (αv)v∈ℐ(\alpha_v)_{v \in \mathcal{I}} be real functions on 𝒦\mathcal{K}, and let q,ε,a,b∈ℝq, \varepsilon, a, b \in \mathbb{R} satisfy 0<a≤b0 < a \le b. Then for all v,w∈ℐv, w \in \mathcal{I}, the kernel Gram matrix equals the Hilbert kernel as in (10): Gg,θ,α,q,ε,a,b(v,w)=Kg,q,ε,a,b(θv,θw;αv,αw).G_{g,\theta,\alpha,q,\varepsilon,a,b}(v, w) = K_{g,q,\varepsilon,a,b}(\theta_v, \theta_w; \alpha_v, \alpha_w).(10)✦

Theorem 2. Suppose 𝒦\mathcal{K} and ℐ\mathcal{I} are finite index sets, (gi)i∈𝒦(g_i)_{i \in \mathcal{K}} and (θv)v∈ℐ(\theta_v)_{v \in \mathcal{I}} are families of vectors in a real inner-product space EE, (αv)v∈ℐ(\alpha_v)_{v \in \mathcal{I}} are real functions on 𝒦\mathcal{K}, and q,ε,a,b∈ℝq, \varepsilon, a, b \in \mathbb{R} satisfy q≥0q \ge 0, ε≥0\varepsilon \ge 0, and 0<a≤b0 < a \le b. Then the real symmetric matrix with (v,w)(v, w)-entry Kg,q,ε,a,b(θv,θw;αv,αw)K_{g,q,\varepsilon,a,b}(\theta_v, \theta_w; \alpha_v, \alpha_w) is positive semidefinite (≽0\succeq 0), as stated in (11): (Kg,q,ε,a,b(θv,θw;αv,αw))v,w∈ℐ≽0.\bigl(K_{g,q,\varepsilon,a,b}(\theta_v, \theta_w; \alpha_v, \alpha_w)\bigr)_{v,w \in \mathcal{I}} \succeq 0.(11)✦

Definition 2. Given natural numbers SS and NN, directions (gs′,i)1≤s′≤S,1≤i≤N(g_{s',i})_{1 \le s' \le S,\, 1 \le i \le N} in a real inner-product space EE, continuous linear maps Bs:ℝN→EB_s : \mathbb{R}^N \to E (1≤s≤S1 \le s \le S, where ℝN\mathbb{R}^N carries the Euclidean norm), real scalars q,k,εq, k, \varepsilon, a chart index 1≤s≤S1 \le s \le S, and a vector x∈ℝNx \in \mathbb{R}^N, the chart extension αs,x:{1,…,S}×{1,…,N}→ℝ\alpha_{s,x} : \{1, \dots, S\} \times \{1, \dots, N\} \to \mathbb{R} is the real-valued function defined in (12): αs,x(s′,i)={kε(xi−⟨gs′,i,Bsx⟩q)if s′=s,0if s′≠s.\alpha_{s,x}(s', i) = \begin{cases} \dfrac{k}{\varepsilon}\!\left(x_i - \dfrac{\langle g_{s',i}, B_s x \rangle}{q}\right) & \text{if } s' = s, \\[8pt] 0 & \text{if } s' \ne s. \end{cases}(12)✦ For real normed spaces EE and FF and continuous linear maps J:E→FJ : E \to F and B:F→EB : F \to E, the residual operator R(J,B):F→FR(J, B) : F \to F is the continuous linear operator defined in (13), where IFI_F denotes the identity operator on FF: R(J,B)=IF−JB.R(J, B) = I_F - J B.(13)✦

Definition 3. In Euclidean space ℝm\mathbb{R}^m of dimension m∈ℕm \in \mathbb{N}, the cube Cube(R)\mathrm{Cube}(R) of radius R∈ℝR \in \mathbb{R} is the subset of ℝm\mathbb{R}^m defined in (14) (with base cube U=Cube(2)=(−2,2)mU = \mathrm{Cube}(2) = (-2, 2)^m): Cube(R)={θ∈ℝm:|θj|<R for all 1≤j≤m}.\mathrm{Cube}(R) = \bigl\{\theta \in \mathbb{R}^m : |\theta_j| < R \text{ for all } 1 \le j \le m\bigr\}.(14)✦ A point θ\theta in a real inner-product space EE is regular with respect to N∈ℕN \in \mathbb{N} vectors u=(u1,…,uN)u = (u_1, \dots, u_N) in EE and a scale τ∈ℝ\tau \in \mathbb{R} if it avoids all threshold hyperplanes {y∈E:⟨ui,y⟩=kτ}\{y \in E : \langle u_i, y \rangle = k\tau\}, as in (15): ⟨ui,θ⟩≠kτfor all 1≤i≤N and all k∈ℤ.\langle u_i, \theta \rangle \ne k\tau \qquad \text{for all } 1 \le i \le N \text{ and all } k \in \mathbb{Z}.(15)✦ Relative to N∈ℕN \in \mathbb{N} vectors u=(u1,…,uN)u = (u_1, \dots, u_N) in a real inner-product space EE and a scale τ∈ℝ\tau \in \mathbb{R}, the integer label Xu,τ(θ)∈ℤNX_{u,\tau}(\theta) \in \mathbb{Z}^N of a point θ∈E\theta \in E is the integer vector whose ii-th coordinate (1≤i≤N1 \le i \le N) is defined in (16): (Xu,τ(θ))i=⌊⟨ui,θ⟩τ⌋.\bigl(X_{u,\tau}(\theta)\bigr)_i = \left\lfloor \frac{\langle u_i, \theta \rangle}{\tau} \right\rfloor.(16)✦ Given natural numbers mm, SS, and NN, families of vectors u=(us,i)1≤s≤S,1≤i≤Nu = (u_{s,i})_{1 \le s \le S,\, 1 \le i \le N} in ℝm\mathbb{R}^m (with ss-th subfamily us=(us,1,…,us,N)u_s = (u_{s,1}, \dots, u_{s,N})), and a scale τ∈ℝ\tau \in \mathbb{R}, the rounded chart vertex set V(u,τ)⊂{1,…,S}×ℤNV(u, \tau) \subset \{1, \dots, S\} \times \mathbb{Z}^N is the set of pairs (s,z)(s, z) defined in (17): V(u,τ)={(s,z)∈{1,…,S}×ℤN:∃θ∈Cube(2) regular for (us,τ) with Xus,τ(θ)=z}.V(u, \tau) = \bigl\{(s, z) \in \{1, \dots, S\} \times \mathbb{Z}^N : \exists\, \theta \in \mathrm{Cube}(2) \text{ regular for } (u_s, \tau) \text{ with } X_{u_s, \tau}(\theta) = z\bigr\}.(17)✦ Given natural numbers mm, SS, and NN, vector families u=(us,i)1≤s≤S,1≤i≤Nu = (u_{s,i})_{1 \le s \le S,\, 1 \le i \le N} in ℝm\mathbb{R}^m, and a scale τ∈ℝ\tau \in \mathbb{R}, the vertex coordinate map ξu,τ:V(u,τ)→ℝN\xi_{u,\tau} : V(u, \tau) \to \mathbb{R}^N is the map assigning to each vertex v=(s,z)∈V(u,τ)v = (s, z) \in V(u, \tau) the Euclidean vector whose ii-th coordinate (1≤i≤N1 \le i \le N) is defined in (18): (ξu,τ(v))i=τzi.\bigl(\xi_{u,\tau}(v)\bigr)_i = \tau z_i.(18)✦ For a pivoted direction family ff of dimension m∈ℕm \in \mathbb{N} with normalized directions u=(us,i)1≤s≤m3,1≤i≤m6u = (u_{s,i})_{1 \le s \le m^3,\, 1 \le i \le m^6} and threshold scale τ=p(m,2000)=m−2000\tau = p(m, 2000) = m^{-2000}, the source vertex set VfV_f is the rounded chart vertex set defined in (19): Vf=V(u,p(m,2000)).V_f = V(u, p(m, 2000)).(19)✦ For a pivoted direction family ff of dimension m∈ℕm \in \mathbb{N} with normalized directions u=(us,i)1≤s≤m3,1≤i≤m6u = (u_{s,i})_{1 \le s \le m^3,\, 1 \le i \le m^6} and a chart index 1≤s≤m31 \le s \le m^3, the source vertex map vf,sv_{f,s} is the map sending each point θ∈Cube(2)\theta \in \mathrm{Cube}(2) regular for (us,p(m,2000))(u_s, p(m, 2000)) to the vertex in VfV_f defined in (20): vf,s(θ)=(s,Xus,p(m,2000)(θ)).v_{f,s}(\theta) = \bigl(s, X_{u_s, p(m, 2000)}(\theta)\bigr).(20)✦

What Is Checked

The Hilbert kernel together with its Gram-matrix and positive semidefiniteness statements is stated over a real inner-product space EE, a finite index set 𝒦\mathcal{K} and an index set ℐ\mathcal{I} (finite for positive semidefiniteness), direction and point families (gi)i∈𝒦(g_i)_{i \in \mathcal{K}} and (θv)v∈ℐ(\theta_v)_{v \in \mathcal{I}} in EE, real weights (αv)v∈ℐ(\alpha_v)_{v \in \mathcal{I}}, and parameters q,ε,a,b∈ℝq, \varepsilon, a, b \in \mathbb{R} with 0<a≤b0 < a \le b (and q,ε≥0q, \varepsilon \ge 0 for positive semidefiniteness), while the chart-extension and residual operators together with the rounded chart vertex constructions are stated over real normed and Euclidean spaces equipped with bounded linear maps, arbitrary direction vectors at scale τ∈ℝ\tau \in \mathbb{R}, and a pivoted direction family ff of dimension mm specialized to normalized directions us,i=gs,i/mu_{s,i} = g_{s,i}/\sqrt{m} and τ=m−2000\tau = m^{-2000}.