OctoInformBeta

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

Lemma 4.1: Constructing Euclidean vectors qq under the chart triangle inequality and inner-product lower bounds with global and local integral estimates

Repairing triangle deficits into a negative-type semimetric.

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 a finite negative-type semimetric for the Goemans-Linial relaxation of uniform sparsest cut, a point set is partitioned into charts equipped with a within-chart distance, and one starts with vectors P(i)P(i) indexed by the points so that for all points i,j,yi, j, y, the inner product ⟨P(i)−P(y),P(j)−P(y)⟩\langle P(i) - P(y), P(j) - P(y) \rangle may fall below zero down to minus the chart separation truncated at a scale r>0r > 0. The triangle repair problem is to find auxiliary Euclidean vectors q(i)q(i) so that the combined squared distances ∥P(i)−P(j)∥2+∥q(i)−q(j)∥2\|P(i) - P(j)\|^2 + \|q(i) - q(j)\|^2 form a negative-type semimetric, while ∥q(i)−q(j)∥2\|q(i) - q(j)\|^2 remains controlled at scale rr globally and small for pairs i,ji, j at small within-chart distance.

Definitions

Given a chart assignment c:ι→κc \colon \iota \to \kappa from an index set ι\iota to a chart set κ\kappa and a map h:ι→Hh \colon \iota \to H into a normed space HH, the chart triangle inequality is the condition on (c,h)(c, h) that for all i,j,k∈ιi, j, k \in \iota with c(i)=c(j)=c(k)c(i) = c(j) = c(k), ∥h(i)−h(k)∥2≤∥h(i)−h(j)∥2+∥h(j)−h(k)∥2.\|h(i) - h(k)\|^2 \le \|h(i) - h(j)\|^2 + \|h(j) - h(k)\|^2.(1)✦

The capped distance δr:ι×ι→ℝ\delta_r \colon \iota \times \iota \to \mathbb{R} associated with a chart assignment c:ι→κc \colon \iota \to \kappa, a map h:ι→Hh \colon \iota \to H into a normed space HH, and a real cap rr is the real-valued function on ι×ι\iota \times \iota given by δr(i,j)={min⁡{r,∥h(i)−h(j)∥2}if c(i)=c(j),rif c(i)≠c(j).\delta_r(i, j) = \begin{cases} \min\bigl\{r, \|h(i) - h(j)\|^2\bigr\} & \text{if } c(i) = c(j), \\ r & \text{if } c(i) \neq c(j). \end{cases}(2)✦

At a real parameter ll, the chart kernel Kl∈ℝι×ιK_l \in \mathbb{R}^{\iota \times \iota} of a chart assignment c:ι→κc \colon \iota \to \kappa and a map h:ι→Hh \colon \iota \to H into a normed space HH is the real matrix indexed by ι\iota with entries Kl(i,j)={exp⁡(−∥h(i)−h(j)∥2/l)if c(i)=c(j),0if c(i)≠c(j).K_l(i, j) = \begin{cases} \exp\bigl(-\|h(i) - h(j)\|^2 / l\bigr) & \text{if } c(i) = c(j), \\ 0 & \text{if } c(i) \neq c(j). \end{cases}(3)✦

For a chart assignment c:ι→κc \colon \iota \to \kappa, a map h:ι→Hh \colon \iota \to H into a normed space HH, and a real number rr, a map q:ι→ℝιq \colon \iota \to \mathbb{R}^\iota into the real Euclidean space on ι\iota is a repair Gram representation of (c,h,r)(c, h, r) if for all i,j∈ιi, j \in \iota, ⟨q(i),q(j)⟩=4∫0rKl(i,j)dl,\langle q(i), q(j) \rangle = 4 \int_0^r K_l(i, j)\,dl,(4)✦ where KlK_l is the chart kernel (3).

The Claim

Theorem 1. Let EE be a real inner product space, HH a normed space, c:ι→κc \colon \iota \to \kappa a chart assignment from an index set ι\iota to a chart set κ\kappa, and h:ι→Hh \colon \iota \to H a map such that (c,h)(c, h) satisfies the chart triangle inequality (1). Suppose r>0r > 0 and P:ι→EP \colon \iota \to E satisfies ⟨P(i)−P(y),P(j)−P(y)⟩≥−min⁡{δr(i,y),δr(j,y)}\langle P(i) - P(y), P(j) - P(y) \rangle \ge -\min\{\delta_r(i, y), \delta_r(j, y)\} for all i,j,y∈ιi, j, y \in \iota, where δr\delta_r is the capped distance (2). Then there exist maps q,z:ι→ℝιq, z \colon \iota \to \mathbb{R}^\iota into the real Euclidean space on ι\iota such that qq is a repair Gram representation (4) of (c,h,r)(c, h, r) and, for all i,j,k∈ιi, j, k \in \iota, ∥z(i)−z(j)∥2=∥P(i)−P(j)∥2+∥q(i)−q(j)∥2,∥z(i)−z(k)∥2≤∥z(i)−z(j)∥2+∥z(j)−z(k)∥2,∥q(i)−q(j)∥2=8∫0r(1−Kl(i,j))dl,∥q(i)−q(j)∥2≤8r,∥q(i)−q(j)∥2≤8∥h(i)−h(j)∥2(1+logr∥h(i)−h(j)∥2)if c(i)=c(j) and 0<∥h(i)−h(j)∥2≤r,q(i)=q(j)if c(i)=c(j) and ∥h(i)−h(j)∥2=0,\begin{aligned} \|z(i) - z(j)\|^2 &= \|P(i) - P(j)\|^2 + \|q(i) - q(j)\|^2, \\ \|z(i) - z(k)\|^2 &\le \|z(i) - z(j)\|^2 + \|z(j) - z(k)\|^2, \\ \|q(i) - q(j)\|^2 &= 8 \int_0^r \bigl(1 - K_l(i, j)\bigr)\,dl, \\ \|q(i) - q(j)\|^2 &\le 8r, \\ \|q(i) - q(j)\|^2 &\le 8 \|h(i) - h(j)\|^2 \left(1 + \log\frac{r}{\|h(i) - h(j)\|^2}\right) \\ &\qquad \text{if } c(i) = c(j) \text{ and } 0 < \|h(i) - h(j)\|^2 \le r, \\ q(i) &= q(j) \quad \text{if } c(i) = c(j) \text{ and } \|h(i) - h(j)\|^2 = 0, \end{aligned}(5)✦ where KlK_l is the chart kernel (3).

In the paper, the result reads: if a finite set VV is partitioned into charts with δ\delta a nonnegative multiple of an ℓ1\ell_1 distance on each chart and δ(v,w)=∞\delta(v, w) = \infty for points in different charts, and if r>0r > 0 and Hilbert vectors PvP_v satisfy ⟨Pv−Py,Pw−Py⟩≥−min⁡{r,δ(v,y),δ(w,y)}\langle P_v - P_y, P_w - P_y \rangle \ge -\min\{r, \delta(v, y), \delta(w, y)\} for all v,w,y∈Vv, w, y \in V, then there exist Hilbert vectors qvq_v such that d(v,w)=∥Pv−Pw∥2+∥qv−qw∥2d(v, w) = \|P_v - P_w\|^2 + \|q_v - q_w\|^2 is a negative-type semimetric satisfying ∥qv−qw∥2=8∫0r(1−e−δ(v,w)/l)dl≤8r\|q_v - q_w\|^2 = 8 \int_0^r (1 - e^{-\delta(v, w)/l})\,dl \le 8r, together with ∥qv−qw∥2≤8δ(v,w)(1+log⁡(r/δ(v,w)))\|q_v - q_w\|^2 \le 8\,\delta(v, w)\bigl(1 + \log(r / \delta(v, w))\bigr) when 0<δ(v,w)≤r0 < \delta(v, w) \le r and qv=qwq_v = q_w when δ(v,w)=0\delta(v, w) = 0 (here VV, PvP_v, and qvq_v stand for ι\iota, P(v)P(v), and q(v)q(v)).

What Is Checked

The triangle repair claim (5) is stated over an index set ι\iota, a chart set κ\kappa, a chart assignment c:ι→κc \colon \iota \to \kappa, a map h:ι→Hh \colon \iota \to H into a normed space HH satisfying the chart triangle inequality (1), a positive scale r>0r > 0, and a map P:ι→EP \colon \iota \to E into a real inner product space EE satisfying the inner-product lower bound in terms of the capped distance (2), with conclusions in ℝι\mathbb{R}^\iota expressed using the chart kernel (3) and repair Gram representations (4).

Write A≽0A \succeq 0 for a positive-semidefinite real matrix AA indexed by ι\iota. For every real inner product space EE, map x:ι→Ex \colon \iota \to E, and l>0l > 0, the Gaussian kernel satisfies (exp⁡(−∥x(i)−x(j)∥2/l))i,j∈ι≽0.\bigl(\exp(-\|x(i) - x(j)\|^2 / l)\bigr)_{i, j \in \iota} \succeq 0.(6)✦ Applying the exponential entrywise to any real matrix AA indexed by ι\iota with A≽0A \succeq 0 gives (exp⁡(Aij))i,j∈ι≽0.\bigl(\exp(A_{ij})\bigr)_{i, j \in \iota} \succeq 0.(7)✦ If r≥0r \ge 0 and (Ml)l∈ℝ(M_l)_{l \in \mathbb{R}} is a family of real matrices indexed by ι\iota such that Ml≽0M_l \succeq 0 for all l∈[0,r]l \in [0, r] and l↦Ml(i,j)l \mapsto M_l(i, j) is integrable on [0,r][0, r] for all i,j∈ιi, j \in \iota, then (∫0rMl(i,j)dl)i,j∈ι≽0.\left(\int_0^r M_l(i, j)\,dl\right)_{i, j \in \iota} \succeq 0.(8)✦

Every real matrix AA indexed by ι\iota with A≽0A \succeq 0 admits Gram vectors q:ι→ℝιq \colon \iota \to \mathbb{R}^\iota in the real Euclidean space on ι\iota such that ⟨q(i),q(j)⟩=Aijfor all i,j∈ι.\langle q(i), q(j) \rangle = A_{ij} \qquad \text{for all } i, j \in \iota.(9)✦

Whenever d≥0d \ge 0 and r≥0r \ge 0, ∫0r(1−e−d/l)dl≤r,\int_0^r \bigl(1 - e^{-d/l}\bigr)\,dl \le r,(10)✦ and when 0<d≤r0 < d \le r, ∫0r(1−e−d/l)dl≤d(1+logrd).\int_0^r \bigl(1 - e^{-d/l}\bigr)\,dl \le d\left(1 + \log\frac{r}{d}\right).(11)✦