OctoInformBeta

OpenAI preprint, September 2026 · §4. The finite negative-type semimetric

Proposition 4.2: Metric repair from angles, macroscopic Euclidean comparison, adjacent-step and cardinality bounds, and weighted contraction for pivoted families

Large direction families induce finite negative-type semimetrics.

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

In constructing integrality gaps for the Goemans-Linial relaxation of uniform sparsest cut, one seeks a finite negative-type semimetric, meaning a symmetric distance dd on a finite set that satisfies all triangle inequalities and admits a squared Euclidean realization d(v,w)=∥Z(v)−Z(w)∥2d(v, w) = \|Z(v) - Z(w)\|^2. Given m3m^3 families of m6m^6 directions in ℝm\mathbb{R}^m for a large positive integer mm, one forms a finite vertex set from rounded projections of points in (−2,2)m(-2, 2)^m. The central problem is to convert an approximate inner-product realization on these vertices into a negative-type semimetric whose macroscopic distances match a rescaled Euclidean metric on (−2,2)m(-2, 2)^m, while controlling steps between adjacent labels, vertex cardinality, diameter, weighted average squared distance, and average ℓ1\ell^1 contraction.

Direction Families and Chart Operators

For a nonnegative integer NN, a real inner-product space EE, an NN-tuple g=(g1,…,gN)∈ENg = (g_1, \dots, g_N) \in E^N, and vectors v,w∈Ev, w \in E, the empirical covariance is the real number Cov(g,v)\mathrm{Cov}(g, v) defined by (1), and the empirical sine transform is the vector 𝒮(g,w)∈E\mathcal{S}(g, w) \in E defined by (2): 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)✦ 𝒮(g,w)=1N∑i=1Nsin⁡(⟨gi,w⟩)gi.\mathcal{S}(g, w) = \frac{1}{N} \sum_{i=1}^N \sin(\langle g_i, w \rangle)\, g_i.(2)✦ Given a real inner-product space EE, a nonnegative integer NN, a real threshold qq, and a vector v∈Ev \in E, the bad projection set Bproj(q,v)B_{\mathrm{proj}}(q, v) is the subset of ENE^N consisting of all NN-tuples (x1,…,xN)∈EN(x_1, \dots, x_N) \in E^N satisfying |⟨v,xi⟩|>q|\langle v, x_i \rangle| > q for some 1≤i≤N1 \le i \le N.✦ For any subset AA of an ambient space 𝒳\mathcal{X} and any SS-tuple y=(y1,…,yS)∈𝒳Sy = (y_1, \dots, y_S) \in \mathcal{X}^S, the number of bad samples ν(A,y)\nu(A, y) is the nonnegative integer counting indices 1≤s≤S1 \le s \le S with ys∈Ay_s \in A.✦

Given a positive integer mm, set S=m3S = m^3 and N=m6N = m^6. A direction family ff in dimension mm is a collection of vectors gs,i∈ℝmg_{s,i} \in \mathbb{R}^m for 1≤s≤S1 \le s \le S and 1≤i≤N1 \le i \le N, with ss-th subfamily gs=(gs,1,…,gs,N)g_s = (g_{s,1}, \dots, g_{s,N}), satisfying five conditions: every vector obeys m/2≤∥gs,i∥≤2m\sqrt{m}/2 \le \|g_{s,i}\| \le 2\sqrt{m}; distinct vectors gs,ag_{s,a} and gs,bg_{s,b} (a≠ba \neq b) in the same subfamily are nonparallel (gs,a≠tgs,bg_{s,a} \neq t g_{s,b} for all t∈ℝt \in \mathbb{R}); every unit vector v∈ℝmv \in \mathbb{R}^m satisfies 1/2≤Cov(gs,v)≤21/2 \le \mathrm{Cov}(g_s, v) \le 2 for each ss; every w∈ℝmw \in \mathbb{R}^m with ∥w∥≤m42\|w\| \le m^{42} satisfies ∥𝒮(gs,w)−exp⁡(−∥w∥2/2)w∥≤2/m\|\mathcal{S}(g_s, w) - \exp(-\|w\|^2/2)\, w\| \le 2/\sqrt{m} for each ss; and every unit vector v∈ℝmv \in \mathbb{R}^m obeys ν(Bproj(11log⁡m,v),(gs)s=1S)≤m3/2\nu\bigl(B_{\mathrm{proj}}(11\sqrt{\log m}, v), (g_s)_{s=1}^S\bigr) \le m^3/2.✦ A pivoted direction family ff in dimension mm is a direction family in dimension mm satisfying in addition 1/m30<|(gs,i)j|1/m^{30} < |(g_{s,i})_j| for all 1≤s≤S1 \le s \le S, 1≤i≤N1 \le i \le N, and 1≤j≤m1 \le j \le m.✦

Let EE be a real inner-product space and N′N' a nonnegative integer; the chart operator of an N′N'-tuple u=(u1,…,uN′)∈EN′u = (u_1, \dots, u_{N'}) \in E^{N'} is the continuous linear map J(u):E→ℝN′J(u) : E \to \mathbb{R}^{N'} into N′N'-dimensional Euclidean space with ii-th component (J(u)θ)i=⟨ui,θ⟩(J(u)\theta)_i = \langle u_i, \theta \rangle for each θ∈E\theta \in E and each 1≤i≤N′1 \le i \le N'.✦ Given any continuous linear map J:E→FJ : E \to F between real inner-product spaces and a real constant a>0a > 0 satisfying a∥x∥2≤∥Jx∥2a\|x\|^2 \le \|Jx\|^2 for all x∈Ex \in E, the Gram operator J*J:E→EJ^* J : E \to E is the bijective continuous linear map obtained by composing the adjoint J*J^* with JJ✦, and the left pseudoinverse J+:F→EJ^+ : F \to E is the continuous linear map (J*J)−1J*(J^* J)^{-1} J^*.✦

For a positive integer mm and a direction family ff in dimension mm, the scaled direction family uu of ff is the collection of normalized vectors us,i=gs,i/m∈ℝmu_{s,i} = g_{s,i}/\sqrt{m} \in \mathbb{R}^m for 1≤s≤S1 \le s \le S and 1≤i≤N1 \le i \le N, with ss-th subfamily us=(us,1,…,us,N)u_s = (u_{s,1}, \dots, u_{s,N}) and chart operator Js=J(us):ℝm→ℝNJ_s = J(u_s) : \mathbb{R}^m \to \mathbb{R}^N.✦ The frame lower bound constant for mm is the real number am=m6/(2m)a_m = m^6/(2m)✦, and the chart pseudoinverse Bs:ℝN→ℝmB_s : \mathbb{R}^N \to \mathbb{R}^m at chart index 1≤s≤S1 \le s \le S is the left pseudoinverse Js+J_s^+ of JsJ_s.✦

Rounded Charts and Macro Constants

For a positive integer mm and a real number R>0R > 0, the cube of radius RR in ℝm\mathbb{R}^m is the subset QR={θ∈ℝm:|θj|<R for all 1≤j≤m}Q_R = \{\theta \in \mathbb{R}^m : |\theta_j| < R \text{ for all } 1 \le j \le m\}.✦ Given a real inner-product space EE, an N′N'-tuple u=(u1,…,uN′)∈EN′u = (u_1, \dots, u_{N'}) \in E^{N'}, and a real grid scale τ′\tau', the integer chart label of θ∈E\theta \in E is the vector X(u,τ′,θ)∈ℤN′X(u, \tau', \theta) \in \mathbb{Z}^{N'} with ii-th coordinate ⌊⟨ui,θ⟩/τ′⌋\lfloor \langle u_i, \theta \rangle / \tau' \rfloor✦, and a point θ∈E\theta \in E is regular for uu at scale τ′\tau' if ⟨ui,θ⟩≠kτ′\langle u_i, \theta \rangle \neq k\tau' for every 1≤i≤N′1 \le i \le N' and every integer kk.✦ For nonnegative integers S′S' and N′N', an S′S'-tuple u=(u1,…,uS′)u = (u_1, \dots, u_{S'}) of N′N'-tuples in ℝm\mathbb{R}^m, and a scale τ′\tau', the rounded chart vertex set 𝒱(u,τ′)\mathcal{V}(u, \tau') is the set of all pairs (s,x)(s, x) with 1≤s≤S′1 \le s \le S' and x∈ℤN′x \in \mathbb{Z}^{N'} for which some θ∈Q2\theta \in Q_2 is regular for usu_s at scale τ′\tau' and satisfies X(us,τ′,θ)=xX(u_s, \tau', \theta) = x.✦ The rounded chart coordinate of v=(s,x)∈𝒱(u,τ′)v = (s, x) \in \mathcal{V}(u, \tau') is the vector x‾(v)∈ℝN′\bar{x}(v) \in \mathbb{R}^{N'} (with ℓ2\ell^2 norm) whose ii-th entry is x‾(v)i=τ′xi\bar{x}(v)_i = \tau' x_i, and the chart index of vv is the integer s(v)=ss(v) = s.✦

For a real number xx and a nonnegative integer nn, the inverse power of xx to nn is the real number p(x,n)=1/xnp(x, n) = 1/x^n.✦ Given a positive integer mm and a direction family ff in dimension mm, set the grid scale τ=p(m,2000)=m−2000\tau = p(m, 2000) = m^{-2000} and the angle error scale r=p(m,8)=m−8r = p(m, 8) = m^{-8}; the source vertex set is the set V=𝒱((us)s=1S,τ)V = \mathcal{V}((u_s)_{s=1}^S, \tau)✦, and for each 1≤s≤S1 \le s \le S and each θ∈Q2\theta \in Q_2 regular for usu_s at scale τ\tau, the chart vertex is the pair v(s,θ)=(s,X(us,τ,θ))∈Vv(s, \theta) = (s, X(u_s, \tau, \theta)) \in V.✦

The profile function is the function φ:ℝ→ℝ\varphi : \mathbb{R} \to \mathbb{R} defined by φ(t)=1−exp⁡(−1/(2t2))\varphi(t) = 1 - \exp(-1/(2t^2))✦, and the profile constant is the real number c*c^* given by (3): c*=2∫0∞φ(t)dt.c^* = 2 \int_0^\infty \varphi(t)\,dt.(3)✦ For nonnegative integers N′,S′N', S' and real numbers q,k,ε,a,b,R,T,R+q, k, \varepsilon, a, b, R, T, R_+, the macro cost function Φ\Phi is defined by (4): Φ(N′,S′,q,k,ε,a,b,R,T,R+)=q(2a+(2T)2b)+4εS′N′(1+kRε)2log⁡ba+2c*qR+.\Phi(N', S', q, k, \varepsilon, a, b, R, T, R_+) = q\Bigl(2a + \frac{(2T)^2}{b}\Bigr) + 4\varepsilon S' N' \Bigl(1 + \frac{kR}{\varepsilon}\Bigr)^2 \log\frac{b}{a} + 2c^* q R_+.(4)✦ For a positive integer mm, the macro cost error is the real number eme_m given by (5): em=Φ(m6,m3,m,p(m,5),p(m,200),p(m,40),m40,p(m,1997),3m,0).e_m = \Phi\bigl(m^6,\, m^3,\, \sqrt{m},\, p(m, 5),\, p(m, 200),\, p(m, 40),\, m^{40},\, p(m, 1997),\, 3\sqrt{m},\, 0\bigr).(5)✦

The source metric constant is the real number C0=9+2c*C_0 = 9 + 2c^*✦, and the diameter constant is the real number D=4c*+C0D = 4c^* + C_0.✦ Let β:ℝ→ℝ\beta : \mathbb{R} \to \mathbb{R} be the smooth bump function centered at 00 with inner radius 1/21/2 and outer radius 11✦, let the standard mollifier ρ:ℝ→ℝ\rho : \mathbb{R} \to \mathbb{R} be the normalization of β\beta with respect to Lebesgue measure✦, and let the mollifier derivative integral be the real number H=∫−∞∞|ρ′(t)|dtH = \int_{-\infty}^\infty |\rho'(t)|\,dt.✦ For a positive integer mm, the contraction weight function is the real number W(m)=m(log⁡m)2log⁡mW(m) = \sqrt{m}(\log m)^2\sqrt{\log m}✦, and the contraction constant is the real number CC given by (6): C=2(c*+C0)+π(1,100,000,000+C0H)+1.C = 2(c^* + C_0) + \pi\bigl(1{,}100{,}000{,}000 + C_0 H\bigr) + 1.(6)✦

The Claim

Theorem 1. Suppose ι\iota and KK are finite index sets, ClblC_{\mathrm{lbl}} is a set, EE is a real inner-product space, and H′H' is a real normed space. Given maps c:ι→Clblc : \iota \to C_{\mathrm{lbl}}, x:ι→ℝKx : \iota \to \mathbb{R}^K, P:ι→EP : \iota \to E, and θ:ι→H′\theta : \iota \to H', together with real numbers L≥0L \ge 0, r′>0r' > 0, qq, and ee, set Δ(v,w)=L∑j∈K|x(v)j−x(w)j|\Delta(v, w) = L \sum_{j \in K} |x(v)_j - x(w)_j| for v,w∈ιv, w \in \iota. Assume that for all v,w,z,y∈ιv, w, z, y \in \iota, one has |∥P(v)−P(w)∥2−q∥θ(v)−θ(w)∥|≤e\bigl|\|P(v) - P(w)\|^2 - q\|\theta(v) - \theta(w)\|\bigr| \le e and ⟨P(v)−P(z),P(y)−P(z)⟩≥−r′\langle P(v) - P(z), P(y) - P(z) \rangle \ge -r', and that |⟨P(v)−P(z),P(y)−P(z)⟩|≤Δ(v,z)|\langle P(v) - P(z), P(y) - P(z) \rangle| \le \Delta(v, z) whenever c(v)=c(z)c(v) = c(z). Then there exists an embedding Z:ι→ℝιZ : \iota \to \mathbb{R}^\iota into Euclidean space indexed by ι\iota satisfying (7) for all v,w,z∈ιv, w, z \in \iota: ∥Z(v)−Z(z)∥2≤∥Z(v)−Z(w)∥2+∥Z(w)−Z(z)∥2,|∥Z(v)−Z(w)∥2−q∥θ(v)−θ(w)∥|≤e+8r′,∥Z(v)−Z(w)∥2≤Δ(v,w)(9+8log⁡r′Δ(v,w))if c(v)=c(w) and 0<Δ(v,w)≤r′,Z(v)=Z(w)if c(v)=c(w) and Δ(v,w)=0.\begin{aligned} \|Z(v) - Z(z)\|^2 &\le \|Z(v) - Z(w)\|^2 + \|Z(w) - Z(z)\|^2, \\ \bigl|\|Z(v) - Z(w)\|^2 - q\|\theta(v) - \theta(w)\|\bigr| &\le e + 8r', \\ \|Z(v) - Z(w)\|^2 &\le \Delta(v, w)\Bigl(9 + 8\log\frac{r'}{\Delta(v, w)}\Bigr) \quad\text{if } c(v) = c(w)\text{ and } 0 < \Delta(v, w) \le r', \\ Z(v) &= Z(w) \quad\text{if } c(v) = c(w)\text{ and } \Delta(v, w) = 0. \end{aligned}(7)✦

Let m≥3000m \ge 3000 be an integer satisfying log⁡m≥1\log m \ge 1, and let ff be a pivoted direction family in dimension mm. Then there exists a map Z:V→ℝVZ : V \to \mathbb{R}^V into Euclidean space indexed by VV satisfying (8) for all v,w,z∈Vv, w, z \in V: ∥Z(v)−Z(z)∥2≤∥Z(v)−Z(w)∥2+∥Z(w)−Z(z)∥2,|∥Z(v)−Z(w)∥2−c*m∥Bs(v)(x‾(v))−Bs(w)(x‾(w))∥|≤em+8r,∥Z(v)−Z(w)∥2≤50,000,000τp(m,5)(log⁡m)2if s(v)=s(w) and ∑i=1N|x‾(v)i−x‾(w)i|=τ.\begin{aligned} \|Z(v) - Z(z)\|^2 &\le \|Z(v) - Z(w)\|^2 + \|Z(w) - Z(z)\|^2, \\ \bigl|\|Z(v) - Z(w)\|^2 - c^*\sqrt{m}\,\|B_{s(v)}(\bar{x}(v)) - B_{s(w)}(\bar{x}(w))\|\bigr| &\le e_m + 8r, \\ \|Z(v) - Z(w)\|^2 &\le 50{,}000{,}000\,\tau\,p(m, 5)(\log m)^2 \quad\text{if } s(v) = s(w)\text{ and } \sum_{i=1}^N |\bar{x}(v)_i - \bar{x}(w)_i| = \tau. \end{aligned}(8)✦

Let m≥3000m \ge 3000 be an integer, let ff be a pivoted direction family in dimension mm, and let Z:V→ℝVZ : V \to \mathbb{R}^V satisfy the second inequality of (8) for all v,w∈Vv, w \in V. Then for all chart indices 1≤s,t≤S1 \le s, t \le S and all points θ,η∈Q2\theta, \eta \in Q_2 regular at scale τ\tau for usu_s and utu_t respectively, (9) holds: |∥Z(v(s,θ))−Z(v(t,η))∥2−c*m∥θ−η∥|≤C0r.\bigl|\|Z(v(s, \theta)) - Z(v(t, \eta))\|^2 - c^*\sqrt{m}\,\|\theta - \eta\|\bigr| \le C_0 r.(9)✦

If m≥1m \ge 1, ff is a pivoted direction family in dimension mm, and two vertices v+=(s+,x+)v^+ = (s^+, x^+) and v−=(s−,x−)v^- = (s^-, x^-) in VV satisfy xi+=xi−+1x^+_i = x^-_i + 1 at some index 1≤i≤N1 \le i \le N and xj+=xj−x^+_j = x^-_j for all j≠ij \neq i, then their rounded chart coordinates satisfy (10): ∑j=1N|x‾(v+)j−x‾(v−)j|=τ.\sum_{j=1}^N \bigl|\bar{x}(v^+)_j - \bar{x}(v^-)_j\bigr| = \tau.(10)✦

When m≥5m \ge 5 and ff is a pivoted direction family in dimension mm, the cardinality of VV satisfies (11): |V|≤m4025m.|V| \le m^{4025 m}.(11)✦

Let m≥3000m \ge 3000 be an integer satisfying log⁡m≥1\log m \ge 1 and H≤mH \le m, and let ff be a pivoted direction family in dimension mm. Then there exist a map Z:V→ℝVZ : V \to \mathbb{R}^V and weights w:V→ℝw : V \to \mathbb{R} satisfying (12) for all v,y,z∈Vv, y, z \in V, every finite set AA, and every map F:V→ℝAF : V \to \mathbb{R}^A with ∑a∈A|F(v)a−F(z)a|≤∥Z(v)−Z(z)∥2\sum_{a \in A} |F(v)_a - F(z)_a| \le \|Z(v) - Z(z)\|^2 for all v,z∈Vv, z \in V: wv≥0,∑v∈Vwv=1,∥Z(v)−Z(z)∥2≤∥Z(v)−Z(y)∥2+∥Z(y)−Z(z)∥2,∥Z(v)−Z(z)∥2≤Dm,∑v,z∈Vwvwz∥Z(v)−Z(z)∥2≥c*3m−C0r,∑v,z∈Vwvwz∑a∈A|F(v)a−F(z)a|≤CW(m).\begin{aligned} w_v &\ge 0, \qquad \sum_{v \in V} w_v = 1, \\ \|Z(v) - Z(z)\|^2 &\le \|Z(v) - Z(y)\|^2 + \|Z(y) - Z(z)\|^2, \\ \|Z(v) - Z(z)\|^2 &\le D m, \\ \sum_{v, z \in V} w_v w_z \|Z(v) - Z(z)\|^2 &\ge \frac{c^*}{3} m - C_0 r, \\ \sum_{v, z \in V} w_v w_z \sum_{a \in A} |F(v)_a - F(z)_a| &\le C W(m). \end{aligned}(12)✦

In the paper, the result reads: there exists a negative-type semimetric dd on VV comparing with c*m∥θ−η∥c^*\sqrt{m}\,\|\theta - \eta\| within CprC_{\mathrm{p}} r, with adjacent label jump bound Cpτ(m/N)(log⁡m)2C_{\mathrm{p}} \tau (m/N)(\log m)^2, size bound |V|≤exp⁡(Cpmlog⁡m)|V| \le \exp(C_{\mathrm{p}} m \log m), diameter bound CpmC_{\mathrm{p}} m, and average distance at least cpmc_{\mathrm{p}} m, where c*c^* stands for the paper’s c*c_*, ∥θ−η∥\|\theta - \eta\| for its |θ−η||\theta - \eta|, and Cp,cpC_{\mathrm{p}}, c_{\mathrm{p}} for its constants C,cC, c.

What Is Checked

The metric repair bound (7) is stated over arbitrary finite index sets ι\iota and KK, a set ClblC_{\mathrm{lbl}}, real inner-product spaces EE and H′H', and real parameters L≥0L \ge 0, r′>0r' > 0, qq, and ee, while the remaining claims (8) through (12) are stated over the source vertex set VV, rounded chart coordinates x‾\bar{x}, chart pseudoinverses BsB_s, and the profile, macro, and contraction constants for a pivoted direction family ff in dimension mm (with m≥1m \ge 1 in (10), m≥5m \ge 5 in (11), m≥3000m \ge 3000 in (9), additionally log⁡m≥1\log m \ge 1 in (8), and H≤mH \le m in (12)). For the chart constructions, every positive integer mm has a strictly positive frame lower bound constant am>0a_m > 0✦, and every pivoted direction family ff in dimension mm satisfies the frame energy lower bound am∥x∥2≤∥Jsx∥2a_m \|x\|^2 \le \|J_s x\|^2 for all 1≤s≤S1 \le s \le S and all x∈ℝmx \in \mathbb{R}^m.