A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
LEVEL 2 OF 2 · Uniform sparsest cut: hardness and semidefinite gaps
Near-square-root logarithmic integrality gaps for uniform sparsest cut
expertly designed by an internal OpenAI model · released 2026-09-24
· original PDF
IntroductionSparsest cut asks for a partition with small crossing capacity relative to the demand it separates. It is a basic graph-partitioning problem, and its relaxations connect approximation algorithms with the geometry of finite metric spaces. When every pair of vertices has the same demand, the denominator depends only on the two part sizes. An integrality-gap lower bound in this uniform case requires an obstruction to preserving the average distance over all pairs. Let \(C=(c_{ij})\) be symmetric nonnegative capacities on the unordered pairs of distinct vertices in \([n]=\{1,\ldots,n\}\). The uniform sparsest-cut optimum is \[ \mathop{\mathrm{OPT}}(C)=\min_{\varnothing\ne B\subsetneq[n]} \frac{\sum_{i\in B,\,j\notin B}c_{ij}}{|B|(n-|B|)}. \tag{1}\] Thus every pair has demand exactly one. We allow arbitrary capacities; no regularity or degree-weighted vertex measure is assumed. A negative-type semimetric on a finite set is a function \(d(i,j)=|x_i-x_j|^2\), for vectors in a real Hilbert space, that satisfies all triangle inequalities. Distinct points may have distance zero. The Goemans–Linial relaxation (Goemans 1997; Linial 2002) is \[ \mathop{\mathrm{GL}}(C)=\min\left\{ \sum_{i<j}c_{ij}d(i,j):\ \sum_{i<j}d(i,j)=1,\quad d\text{ is a negative-type semimetric} \right\}. \tag{2}\] Every finite Hilbert configuration can be realized in \(\mathbb R^n\), so this is the usual squared-Euclidean SDP with triangle inequalities. There is no unit-norm constraint on the vectors. Cut distances are feasible after normalization, and hence \(\mathop{\mathrm{GL}}(C)\le\mathop{\mathrm{OPT}}(C)\). Theorem 1. There are an absolute constant \(c>0\) and capacity instances \(C^{(j)}\) on \(n_j\to\infty\) vertices, with \(\mathop{\mathrm{GL}}(C^{(j)})>0\), such that \[\frac{\mathop{\mathrm{OPT}}(C^{(j)})}{\mathop{\mathrm{GL}}(C^{(j)})} \ge c\,\frac{\sqrt{\log n_j}}{(\log\log n_j)^3}\] for all sufficiently large \(j\). The demand is one between every pair of distinct vertices. History and the uniform-demand obstacleThe metric viewpoint on cuts was developed by Linial, London, and Rabinovich (Linial et al. 1995): finite \(\ell_1\) distances are nonnegative combinations of cut distances, and an embedding into \(\ell_1\) can be rounded to a cut. For uniform demands, the relevant quantity is the average distance preserved by a nonexpanding map. Rabinovich developed this average-distortion framework and its connection to uniform sparsest cut (Rabinovich 2003, 2008). Here a map is nonexpanding, or a contraction, if its distance on each pair is at most the original distance. The proof below constructs a negative-type semimetric for which every contraction into \(\ell_1\) preserves only a small fraction of the average distance. Arora, Rao, and Vazirani gave an \(O(\sqrt{\log n})\) approximation for uniform sparsest cut through their semidefinite relaxation and geometric separation theorem (Arora et al. 2009). Their work, first presented in 2004, provides the upper-bound benchmark for 1. Devanur, Khot, Saket, and Vishnoi obtained an \(\Omega(\log\log n)\) integrality gap, refuting the uniform constant-gap conjecture (Devanur et al. 2006). Kane and Meka subsequently proved the stronger bound \(\exp(\Omega(\sqrt{\log\log n}))\) through pseudorandom generators for Lipschitz functions of polynomials (Kane and Meka 2013). Their work also gives lower bounds for strengthened relaxations; the present paper concerns the basic Goemans–Linial SDP. Our bound reaches the exponent \(1/2\) in \(\log n\), with the displayed iterated-logarithmic loss, and quantitatively strengthens the earlier negative resolution of the uniform constant-gap conjecture. For arbitrary demands, the Goemans–Linial Conjecture predicted a constant integrality gap, equivalently a uniform bound on the \(\ell_1\) distortion of finite negative-type metrics. Khot and Vishnoi disproved this conjecture (Khot and Vishnoi 2015). A geometric line of work based on the Heisenberg group was developed by Lee and Naor (Lee and Naor 2006), Cheeger and Kleiner (Cheeger and Kleiner 2010), and Cheeger, Kleiner, and Naor (Cheeger et al. 2009, 2011). Naor and Young obtained the sharp general-demand lower bound \(\Omega(\sqrt{\log n})\) (Naor and Young 2018); Chang, Naor, and Ren proved the matching upper bound (Chang et al. 2025a, 2025b). These lower bounds do not imply the uniform-demand conclusion. Indeed, Cheeger, Kleiner, and Naor explain explicitly that their bounded-doubling examples have constant average distortion into a line, so their construction cannot yield a diverging uniform gap (Cheeger et al. 2009, Remark 1.1). This distinction between worst-pair distortion and average-distance preservation is the obstacle addressed here. Proof strategyThe construction has two tasks: build a negative-type semimetric with large average distance, and force every \(\ell_1\) contraction to have small average distance for the same probability measure. The final passage to capacities uses cut-cone duality in the average-distortion framework of Linial–London–Rabinovich and Rabinovich (Linial et al. 1995; Rabinovich 2003, 2008). We give the full finite-dimensional argument in 6, including the passage to exactly uniform demands and positivity of the SDP optimum. A common parameter space, many rounded charts.Fix a large integer \(m\) and the parameter cube \(U=(-2,2)^m\). For each \(s\in\{1,\ldots,S\}\), choose a linear map \(J_s:\mathbb R^m\to\mathbb R^N\) with rows \(u_{s,i}^{T}\), and round its coordinates to a lattice of mesh \(\tau>0\). The resulting vertex label is \[v_s(\theta)=(s,X_s(\theta)),\qquad X_s(\theta)_i=\tau\left\lfloor \frac{\langle u_{s,i},\theta\rangle}{\tau}\right\rfloor.\] Each chart partitions the same cube into cells cut out by hyperplanes; \(V\) consists of all labels attained off those hyperplanes. The directions are fixed before choosing any contraction. Their simultaneous guarantee, proved in 2 and Appendix 7, ensures that every unit direction has small projections onto all normals in at least half the charts. The powers of \(m\) determining \(S,N,\tau\) are chosen so that \(|V|\le\exp(Cm\log m)\). Large global distances and small interface costs.3 builds Hilbert vectors for the labels using one common smooth feature map of \(\theta\). Squared distances between these features approximate \(c_*\sqrt m\,|\theta-\eta|\) with a uniform additive error, where \(c_*>0\) is absolute. Small additional Fourier components allow extensions away from each chart subspace whose coordinate derivatives have small inner products against all feature vectors. These derivative profiles control the cost of changing one rounded coordinate. The extension operators may have large norms; sufficiently fine rounding controls their effect on the feature values. The resulting squared distances need not yet satisfy every triangle inequality. [sec:metric] repairs them using a scale integral of Gaussian positive-definite kernels, building on the classical Gaussian-kernel principle of Schoenberg (Schoenberg 1938). The local angle estimate is indispensable: a bounded global error alone would overwhelm the tiny costs at cell interfaces. Together, the local and global angle bounds permit a repair of bounded total size with only a logarithmic loss at those interfaces. In the resulting semimetric \(d\), with tolerance \(r=m^{-8}\), labels from different charts at the same parameter have distance at most \(Cr\), while adjacent labels within a chart have the much smaller bound in (32). Independent uniform parameters in \(T=(-1,1)^m\) have expected first-chart distance at least \(cm\). Simultaneous constraints on a contraction.Given any contraction \(F:V\to\ell_1^D\), define \(f_s(\theta)=F(v_s(\theta))\) almost everywhere on \(U\). The same-parameter estimate makes these functions uniformly close. After smoothing, their gradients are close as well. In each chart, small jumps across cell interfaces express each scalar gradient as a combination of that chart’s normals. The absolute coefficients, summed over all normals and target components, have total budget \(Cm(\log m)^2\). Small projections in the appropriate charts contribute a factor \(C\sqrt{(\log m)/m}\), bounding the sum of the Euclidean norms of the scalar gradients. A dimension-free first-moment inequality on the cube, proved by the Maurey–Pisier Gaussian rotation method (Pisier 1986), converts this bound into \[\mathbb E_{\theta,\eta\in T} \|F(v_1(\theta))-F(v_1(\eta))\|_1 \le C\sqrt m(\log m)^{5/2}.\] 5 proves this estimate uniformly in the target dimension \(D\). In particular, the favorable charts may depend on the scalar component and parameter; the proof averages over charts before summing the components. Uniform copies and capacities.The probability measure used for these averages is supported on the first chart, but all charts impose constraints on \(F\). We approximate that measure by multiplicities while retaining at least one copy of every vertex of \(V\). Copies of the same vertex have distance zero, so each contraction on the copies induces a contraction on all of \(V\). The measure on the copies is exactly uniform; its pushforward only approximates the original first-chart measure. The average bounds survive, and cut-cone duality supplies capacities with unit demand on each distinct pair of copies. 1 summarizes the two estimates used by this final step. The size and gap conversion in 6 is \[\mathrm{gap}\gtrsim\frac{m}{\sqrt m(\log m)^{5/2}}, \qquad \log n\asymp m\log m,\] which yields the power \(3\) of \(\log\log n\) in 1. Conventions.All logarithms are natural. Constants denoted by \(c,C>0\) are absolute and may change from one occurrence to the next. We work with sufficiently large integers \(m\). Euclidean and Hilbert norms are denoted by \(|\cdot|\), and operator norms by \(\|\cdot\|_{\mathrm{op}}\). The notation \(A\lesssim B\) means \(A\le CB\) for an absolute constant. All maps into \(\ell_1\) used below have a finite, arbitrary target dimension, and all estimates are independent of that dimension. Families of directionsThe construction uses many linear images of the same parameter space. The directions defining each image must approximate a Gaussian transform, while most images must have small projections in any prescribed direction. Sampling Fourier features and controlling them on finite nets is a standard route to uniform kernel approximation (Rahimi and Recht 2007). Here the same samples must also control derivative profiles and satisfy a majority-chart guarantee in every direction. Lemma 1. There is an absolute constant \(C\) such that, for every sufficiently large integer \(m\), the following holds. Set \(N=m^6\) and \(S=m^3\). There are vectors \(g_{s,i}\in\mathbb R^m\), indexed by \(1\le s\le S\) and \(1\le i\le N\), with these properties:
Independent standard Gaussian vectors give such a family. The frequency net needed in the proof has \(\exp(O(m\log m))\) points, whereas the failure probability for each scalar empirical estimate is at most \(\exp(-cm^4)\). A separate sphere net and independence across charts give the last assertion simultaneously for every unit direction. The full probabilistic argument appears in Appendix 7. Fix one such family for the remainder of the proof. In particular, its every-direction guarantee is available before any contraction is chosen. Define \[ u_{s,i}=\frac{g_{s,i}}{\sqrt m}, \qquad J_s:\mathbb R^m\longrightarrow\mathbb R^N, \qquad (J_s\theta)_i=\langle u_{s,i},\theta\rangle. \tag{6}\] The eigenvalues of \(J_s^TJ_s\) lie in \([N/(2m),2N/m]\), so \(J_s\) has full column rank. Its left pseudoinverse \(J_s^+=(J_s^TJ_s)^{-1}J_s^T\) satisfies \(J_s^+J_s=I_m\), and \(J_sJ_s^+\) is the orthogonal projection onto the range of \(J_s\). We will use \[ \|J_s\|_{\mathrm{op}}\le\sqrt{\frac{2N}{m}}, \qquad \|J_s^+\|_{\mathrm{op}}\le2\sqrt{\frac mN}, \qquad |J_s^+e_i|\le\frac{4m}{N}\quad(1\le i\le N), \tag{7}\] where \(e_i\) is the \(i\)th standard coordinate vector of \(\mathbb R^N\). The final bound follows from \(J_s^+e_i=(J_s^TJ_s)^{-1}u_{s,i}\), \(\|(J_s^TJ_s)^{-1}\|_{\mathrm{op}}\le2m/N\), and \(|u_{s,i}|\le2\). A Hilbert kernel with chart extensionsRetain the directions, maps, and pseudoinverses from 1. We construct common Hilbert features on the parameter space and extend them to the rounded chart labels. Their squared distances will approximate Euclidean distance. We will control violations of the triangle inequalities both globally and in proportion to within-chart coordinate distance. These are the inputs for the metric construction in [sec:metric]. The parameters in this section are \[ a=m^{-40},\qquad b=m^{40},\qquad \varepsilon=m^{-200},\qquad r=m^{-8},\qquad \tau=m^{-2000}. \tag{8}\] The numerical exponents only enforce separation of scales. The cutoffs \(a,b\) approximate Euclidean distance; \(\varepsilon\) controls the added Fourier components; \(r\) is the tolerance for the angle repair; and \(\tau\) is small enough to absorb every polynomial norm bound below. All choices are fixed powers of \(m\), which is essential for the vertex count. The common kernelThe Gaussian block below produces the macroscopic Euclidean distance by integrating positive-definite Gaussian kernels over scales, as in the classical negative-type framework of Schoenberg (Schoenberg 1938). The additional Fourier blocks have negligible distance contribution but will supply the coordinate profiles for the chart extensions. Write \(E(t)=(\cos t,\sin t)\), and let \(\gamma_m\) be standard Gaussian measure on \(\mathbb R^m\). Define a map \(p:\mathbb R^m\to\mathcal H\) into the real Hilbert space \[\mathcal H= L_2([a,b]\times\mathbb R^m,d\sigma\,d\gamma_m;\mathbb R^2) \mathbin{\oplus} \bigoplus_{s=1}^{S}\bigoplus_{i=1}^{N} L_2([a,b],d\sigma/\sigma;\mathbb R^2)\] by assigning to \(p(\theta)\) the first component \(m^{1/4}E(\langle g,\theta\rangle/\sigma)\) and the component \(\sqrt\varepsilon E(\langle g_{s,i},\theta\rangle/\sigma)\) in summand \((s,i)\). The Gaussian characteristic function gives \[ \begin{split} \langle p(\theta),p(\eta)\rangle &=\sqrt m\int_a^b e^{-|\eta-\theta|^2/(2\sigma^2)}\,d\sigma\\ &\quad+\varepsilon\sum_{s=1}^{S}\sum_{i=1}^{N} \int_a^b \cos\!\left(\frac{\langle g_{s,i},\eta-\theta\rangle}{\sigma}\right) \frac{d\sigma}{\sigma}. \end{split} \tag{9}\] Lemma 2 (Approximation of Euclidean distance). There is an absolute constant \[c_*=2\int_0^\infty\bigl(1-e^{-1/(2t^2)}\bigr)\,dt>0\] such that, whenever \(|\theta|,|\eta|\le3\sqrt m\), \[ \left|\,|p(\theta)-p(\eta)|^2 -c_*\sqrt m\,|\theta-\eta|\,\right|\le m^{-37}. \tag{10}\] Proof. The integral defining \(c_*\) converges: its integrand is bounded near zero and is at most \(1/(2t^2)\) for \(t\ge1\). Scaling the integration variable shows that the first component of the squared distance, if integrated over all positive scales, would equal \(c_*\sqrt m\,|\theta-\eta|\). The omitted scales contribute at most \[2\sqrt m\,a+\frac{\sqrt m\,|\theta-\eta|^2}{b} \le 2\sqrt m\,a+\frac{36m^{3/2}}{b}.\] The squared distance in all the additional components is at most \(4\varepsilon SN\log(b/a)\). Consequently the error is at most \[2m^{-79/2}+36m^{-77/2}+320m^{-191}\log m,\] which is at most \(m^{-37}\) for sufficiently large \(m\). ◻ Extensions with small coordinate profilesThe auxiliary components have amplitude \(\sqrt\varepsilon\), while the preliminary extension below has amplitude \(\varepsilon^{-1/2}\). Their inner products therefore retain full strength despite the negligible contribution to squared distances. We use this to extend the derivative of \(p\) from each chart subspace with small coordinate profiles against all the common features. The extension must agree exactly with \(Dp\) along the chart subspace; its small pairings against \(p(\eta)\) will control the triangle inequalities after rounding. We keep separate polynomial bounds on ordinary Hilbert norms to control the rounding errors. Lemma 3 (Chart derivatives). For every \(s\) there is a smooth map \(A_s:\mathbb R^m\to\mathcal L(\mathbb R^N,\mathcal H)\) such that \[ A_s(\theta)J_s=Dp(\theta). \tag{11}\] For \(|\theta|,|\eta|\le3\sqrt m\) and \(1\le i\le N\), \[ \bigl|\langle A_s(\theta)e_i,p(\eta)\rangle\bigr| \le C\frac{m}{N}\log m. \tag{12}\] Moreover, uniformly in \(\theta\in\mathbb R^m\) and \(s\), \[ |p(\theta)|,\quad \|Dp(\theta)\|_{\mathrm{op}},\quad \|D^2p(\theta)\|_{\mathrm{op}},\quad \|A_s(\theta)\|_{\mathrm{op}},\quad \|DA_s(\theta)\|_{\mathrm{op}}\le m^{300}. \tag{13}\] Here the norm of a second derivative or an operator-valued derivative is the corresponding multilinear operator norm. Proof. We first identify the profile that the preliminary extension should reproduce. For \(|\theta|,|\eta|\le3\sqrt m\), put \(w=(\eta-\theta)/\sigma\). Differentiation in \(\theta\) of the Gaussian term in (9) gives the vector \[\sqrt m\int_a^b w e^{-|w|^2/2}\,\frac{d\sigma}{\sigma}.\] The empirical approximation in 1 suggests replacing \(w e^{-|w|^2/2}\) by \(N^{-1}\sum_i g_{s,i}\sin\langle g_{s,i},w\rangle\). We realize this profile using the auxiliary Fourier components. Define \(A_s^0(\theta)e_i\) to be supported in summand \((s,i)\) of \(\mathcal H\), where it is the function \[\frac{m}{N}\varepsilon^{-1/2} E'\!\left(\frac{\langle g_{s,i},\theta\rangle}{\sigma}\right).\] Its profile is \[ \langle A_s^0(\theta)e_i,p(\eta)\rangle =\frac{m}{N}\int_a^b\sin\langle g_{s,i},w\rangle\, \frac{d\sigma}{\sigma}. \tag{14}\] Since \(u_{s,i}=g_{s,i}/\sqrt m\), the profile of \(A_s^0J_s\) is represented by the vector \[\sqrt m\int_a^b \left(\frac1N\sum_{i=1}^N g_{s,i}\sin\langle g_{s,i},w\rangle\right) \frac{d\sigma}{\sigma}.\] Thus \(A_s^0J_s\) has the intended empirical profile. Set \(R_s=Dp-A_s^0J_s\); we now bound its pairings against the common features before correcting the extension on the chart subspace. For the parameters under consideration, \(|w|\le6\sqrt m/a<m^{42}\). Thus 1 bounds the difference between these vectors by \(2\log(b/a)\). The gradient of the second term of (9) has norm at most \[\varepsilon\sum_{t=1}^{S}\sum_{i=1}^{N}|g_{t,i}| \int_a^b\frac{d\sigma}{\sigma^2} \le\frac{2\varepsilon SN\sqrt m}{a}\le1.\] It follows that \[ \bigl|\langle R_s(\theta)v,p(\eta)\rangle\bigr| \le C(\log m)|v|. \tag{15}\] Now define \[ A_s=A_s^0+R_sJ_s^+=A_s^0(I-J_sJ_s^+)+Dp\,J_s^+. \tag{16}\] The identity \(J_s^+J_s=I\) proves (11). Combining (14), (15), and the column bound \(|J_s^+e_i|\le4m/N\) from (7) proves (12). For completeness, the required Hilbert norm bounds have ample polynomial slack. Differentiation under the Hilbert space formulas is valid to every order, because \(a>0\) and Gaussian moments of every order are finite. For \(j=0,1,2\), the squared multilinear derivative norm of the first component of \(p\) is at most \[\sqrt m\,b\,a^{-2j}\mathbb E|G|^{2j},\] and that of all the additional components together is at most \[\varepsilon SN\log(b/a) \left(\frac{2\sqrt m}{a}\right)^{2j}.\] Using \(\mathbb E|G|^2=m\) and \(\mathbb E|G|^4=m(m+2)\), these estimates give \(\|D^jp\|_{\mathrm{op}}\le m^{110}\) for \(0\le j\le2\). Bounding an operator by \(\sqrt N\) times its largest column norm gives \[\|A_s^0\|_{\mathrm{op}} \le \sqrt N\,\frac{m}{N}\varepsilon^{-1/2}\sqrt{\log(b/a)}, \qquad \|DA_s^0\|_{\mathrm{op}} \le \sqrt N\,\frac{m}{N}\varepsilon^{-1/2} \sqrt{\log(b/a)}\frac{2\sqrt m}{a}.\] In particular, these two quantities are at most \(m^{110}\) and \(m^{150}\), respectively. Substitute these bounds in (16), together with \(R_s=Dp-A_s^0J_s\), its derivative, and \(\|J_s\|_{\mathrm{op}}\le2\sqrt N\) and \(\|J_s^+\|_{\mathrm{op}}\le2\sqrt{m/N}\). The projection \(I-J_sJ_s^+\) has norm at most one; the last expression in (16) and its derivative therefore bound all five quantities in (13) by \(m^{300}\) for sufficiently large \(m\). ◻ Rounded charts and their anglesLet \(Q_s=I-J_sJ_s^+\), the orthogonal projection perpendicular to the image of \(J_s\). Define \[ P_s(x)=p(J_s^+x)+A_s(J_s^+x)Q_sx, \qquad x\in\mathbb R^N. \tag{17}\] On the chart subspace this gives \(P_s(J_s\theta)=p(\theta)\) and \(DP_s(J_s\theta)=A_s(\theta)\): use \(Q_sJ_s=0\) and (11). We use only values very close to that subspace; the derivative away from it is computed explicitly below. Let \(U=(-2,2)^m\), and for \(\theta\in U\) put \[ X_s(\theta)_i =\tau\left\lfloor\frac{\langle u_{s,i},\theta\rangle}{\tau} \right\rfloor. \tag{18}\] In each chart, discard the threshold hyperplanes \(\langle u_{s,i},\theta\rangle=k\tau\), \(k\in\mathbb Z\); their union has Lebesgue measure zero. Define the finite set \[ V=\{(s,X_s(\theta)):1\le s\le S,\ \theta\in U\text{ off the threshold hyperplanes of chart }s\}. \tag{19}\] Write \(v_s(\theta)=(s,X_s(\theta))\) whenever this is defined, and \(P_v=P_s(x)\) for \(v=(s,x)\in V\). For any Hilbert vectors \(Z_v\), their squared distances satisfy all triangle inequalities exactly when \[ \langle Z_v-Z_z,Z_y-Z_z\rangle\ge0 \qquad(v,y,z\in V). \tag{20}\] We next bound how far the vectors \(P_v\) can violate this condition. Lemma 4 (Two angle estimates). For sufficiently large \(m\), all \(v,z,y\in V\) satisfy \[ \langle P_v-P_z,P_y-P_z\rangle\ge-r. \tag{21}\] There is an absolute constant \(C_0\) such that, with \(L=C_0\log m\), for \(v=(s,x)\) and \(z=(s,x')\) in the same chart and every \(y\in V\), \[ \bigl|\langle P_v-P_z,P_y-P_z\rangle\bigr| \le L\frac{m}{N}\|x-x'\|_1. \tag{22}\] Moreover, for all defined \(v_s(\theta),v_t(\eta)\), \[ \left|\,|P_{v_s(\theta)}-P_{v_t(\eta)}|^2 -c_*\sqrt m\,|\theta-\eta|\,\right| \le m^{-37}+m^{610}\tau\le r/10. \tag{23}\] Proof. For \(x=X_s(\theta)\), rounding and (7) give \[ |x-J_s\theta|\le\sqrt N\tau,\qquad |J_s^+x-\theta|\le2\sqrt m\tau,\qquad |Q_sx|\le\sqrt N\tau. \tag{24}\] In particular, \(|J_s^+x|\le3\sqrt m\). By (13) and (17), \[ |P_{v_s(\theta)}-p(\theta)| \le m^{300}(2\sqrt m+\sqrt N)\tau \le m^{305}\tau. \tag{25}\] The change in a squared distance caused by the two errors in (25) is at most \(m^{610}\tau\), since \(|p(\theta)|\le m^{300}\). Therefore 2 gives (23); its last inequality follows directly from (8). Choose parameter representatives in \(U\) for \(v,z,y\). Apply (23) to their three pairs and use \[2\langle P_v-P_z,P_y-P_z\rangle =|P_v-P_z|^2+|P_y-P_z|^2-|P_v-P_y|^2.\] The corresponding expression for the ordinary Euclidean distances of the three representatives is nonnegative by the triangle inequality. The total error is at most \(3r/10\), proving (21). For the local estimate, we integrate coordinate profiles so that the bound scales with \(\|x-x'\|_1\). Consider the segment joining \(x\) to \(x'\). Every point \(\xi\) on this segment satisfies \(|Q_s\xi|\le\sqrt N\tau\) and \(|J_s^+\xi|\le3\sqrt m\), by convexity and (24). Differentiating (17) and using (11) gives the exact identity \[ DP_s(\xi)h =A_s(J_s^+\xi)h +DA_s(J_s^+\xi)[J_s^+h]Q_s\xi. \tag{26}\] The operator norm of the second term is at most \(2m^{300}\sqrt m\tau\le m^{305}\tau\). For a vertex \(y=v_t(\eta)\), replace \(P_y\) by \(p(\eta)\) using (25). Equations (12) and (13) then imply, throughout this segment, \[\bigl|\langle DP_s(\xi)e_i,P_y\rangle\bigr| \le C\frac{m}{N}\log m+3m^{605}\tau \le C'\frac{m}{N}\log m.\] The same bound holds with \(P_z\) in place of \(P_y\). Integrating (26) along the segment and summing the absolute coordinate increments proves (22) after choosing a sufficiently large absolute \(C_0\). ◻ The finite negative-type semimetric
The vectors \(P_v\) from 4 have the desired macroscopic distances. Their inner products in (20) can still be negative, but the lemma bounds their negative parts both by \(r\) and by a quantity proportional to within-chart coordinate distance. We complete the construction by appending a Hilbert correction that compensates the smaller of these bounds. A correction controlled only by \(r\) could dominate the cost of crossing an individual cell interface. The following lemma corrects violations of (20) while preserving small distances up to a logarithmic loss. We state it for arbitrary chartwise \(\ell_1\) distances so that the required local and global bounds are explicit. Lemma 5 (Triangle repair). Let a finite set \(V\) be partitioned into charts. In each chart let \(\delta\) be a nonnegative multiple of an \(\ell_1\) distance, and set \(\delta(v,w)=\infty\) for points in different charts. Suppose that \(r>0\) and Hilbert vectors \(P_v\) satisfy \[ \langle P_v-P_z,P_y-P_z\rangle \ge-\min\{r,\delta(v,z),\delta(y,z)\} \qquad(v,y,z\in V). \tag{27}\] Then there are Hilbert vectors \(q_v\) such that \[d(v,w)=|P_v-P_w|^2+|q_v-q_w|^2\] is a negative-type semimetric. They satisfy \[ |q_v-q_w|^2 =8\int_0^r\bigl(1-e^{-\delta(v,w)/l}\bigr)\,dl\le8r. \tag{28}\] If \(0<\delta(v,w)\le r\), then \[ |q_v-q_w|^2 \le8\delta(v,w)\left(1+\log\frac r{\delta(v,w)}\right). \tag{29}\] If \(\delta(v,w)=0\), then \(q_v=q_w\). Proof. We use the convention \(e^{-\infty}=0\). Define a Gram matrix by \[ \langle q_v,q_w\rangle=4\int_0^r e^{-\delta(v,w)/l}\,dl. \tag{30}\] This matrix is positive semidefinite. Indeed, in one coordinate the map \(t\mapsto\mathbf1_{[b,t]}\) into \(L_2\) has squared distance \(|t-t'|\), where \(b\) is a fixed lower bound on the finitely many coordinate values. Direct sums and scaling show that an \(\ell_1\) distance is squared Hilbertian. For finitely many Hilbert vectors \(h_v\), the kernel \[e^{-|h_v-h_w|^2/l} =\mathbb E\cos\!\left(\sqrt{2/l}\,\langle G,h_v-h_w\rangle\right)\] is positive semidefinite: \(G\) is a standard Gaussian in their finite linear span, and the cosine is the inner product of the corresponding \((\cos,\sin)\) pairs. This is the Gaussian-kernel criterion of Schoenberg (Schoenberg 1938), here in its elementary finite form. The kernels in (30) are block diagonal across charts; integration preserves positive semidefiniteness. Thus the specified Gram matrix has a Hilbert realization. The extended distance \(\delta\) satisfies the triangle inequality, including triples meeting different charts. Consequently, for \(a=\delta(v,z)\) and \(b=\delta(y,z)\), \[\begin{split} 1-e^{-a/l}-e^{-b/l}+e^{-\delta(v,y)/l} &\ge 1-e^{-a/l}-e^{-b/l}+e^{-(a+b)/l}\\ &=(1-e^{-a/l})(1-e^{-b/l}). \end{split}\] For \(t=\min\{r,a,b\}\), this product is at least \((1-e^{-1})^2\) when \(0<l<t\). Equation (30) therefore gives \[\langle q_v-q_z,q_y-q_z\rangle \ge4(1-e^{-1})^2t\ge t.\] Together with (27), this proves (20) for \(Z_v=(P_v,q_v)\). The diagonal entries of (30) are \(4r\), which proves (28). Finally, \(1-e^{-s}\le\min\{1,s\}\) and \[\int_0^r\min\{1,t/l\}\,dl=t\bigl(1+\log(r/t)\bigr) \qquad(0<t\le r)\] give (29). The assertion at distance zero follows directly from (28). ◻ We now apply 5 to the rounded labels of 4. The following proposition collects the metric properties needed for the contraction and duality arguments. Proposition 1. For every sufficiently large integer \(m\), the vertex set \(V\) in (19) admits a negative-type semimetric \(d\) with the following properties. Its chart maps \(v_s(\theta)\), defined almost everywhere on \(U=(-2,2)^m\), satisfy \[ \left|d(v_s(\theta),v_t(\eta)) -c_*\sqrt m\,|\theta-\eta|\right|\le Cr \qquad(\theta,\eta\in U) \tag{31}\] whenever the labels are defined, where \(r=m^{-8}\). For labels in the same chart, \[ \|x-x'\|_1=\tau \quad\Longrightarrow\quad d((s,x),(s,x'))\le C\tau\frac mN(\log m)^2. \tag{32}\] Moreover, \[ |V|\le\exp(Cm\log m),\qquad \operatorname{diam}(V,d)\le Cm, \tag{33}\] and, for independent uniform \(\theta,\eta\in T=(-1,1)^m\), \[ \mathbb Ed(v_1(\theta),v_1(\eta))\ge cm. \tag{34}\] Here \(N=m^6\), \(\tau=m^{-2000}\), and all constants are absolute. Proof. Let \(P_v\) and \(L=C_0\log m\) be as in 4. Within a chart set \[\delta((s,x),(s,x'))=L\frac mN\|x-x'\|_1,\] and put \(\delta=\infty\) between different charts. Equation (21) bounds every \(P\)-angle below by \(-r\). Equation (22) also bounds it below by \(-\delta(v,z)\) whenever \(v,z\) are in the same chart, and by \(-\delta(y,z)\) whenever \(y,z\) are in the same chart, after swapping the two arguments of the inner product. Thus the hypothesis of 5 holds. Use its vectors \(q_v\) and set \[ d(v,w)=|(P_v,q_v)-(P_w,q_w)|^2. \tag{35}\] This is a negative-type semimetric. The bound \(|q_v-q_w|^2\le8r\) and (23) prove (31). Taking \(y=v\) in (22) gives \(|P_v-P_z|^2\le\delta(v,z)\). If \(\|x-x'\|_1=\tau\), then \[\delta= C_0\tau(m/N)\log m<r, \qquad \log(r/\delta) =1997\log m-\log(C_0\log m)=O(\log m).\] Equation (29) now proves (32). We next count the rounded labels. Since \(|u_{s,i}|\le2\), a hyperplane \(\langle u_{s,i},\theta\rangle=k\tau\) meeting \(U\) has \(|k\tau|<4\sqrt m\). Hence at most \[H\le N(1+8\sqrt m/\tau)\] threshold hyperplanes meet \(U\) in a chart. An arrangement of \(H\) hyperplanes in \(\mathbb R^m\) has at most \(\sum_{j=0}^m\binom Hj\) full-dimensional regions (see (Zaslavsky 1975)). This follows by induction: an added hyperplane creates at most as many new regions as the preceding hyperplanes cut out on it. The labels are constant on the regions, and their intersections with the convex cube \(U\) are connected. Therefore \[|V|\le S\sum_{j=0}^m\binom Hj\le\exp(Cm\log m),\] because \(H\) is bounded by a fixed power of \(m\). The diameter bound in (33) follows from (31) and \(\operatorname{diam}(U)=4\sqrt m\). Finally, for independent uniform parameters on \(T\), \[\mathbb E|\theta-\eta|^2=\frac{2m}{3},\qquad |\theta-\eta|\le2\sqrt m.\] It follows that \(\mathbb E|\theta-\eta|\ge\sqrt m/3\). Equation (31) gives \(\mathbb Ed(v_1(\theta),v_1(\eta))\ge c_*m/3-Cr\), proving (34) for sufficiently large \(m\). ◻ The macroscopic comparison (31) does not make the interface constraints redundant: its additive error \(O(r)=O(m^{-8})\) is far larger than the interface bound \(O(m^{-2005}(\log m)^2)\) in (32). The next section uses these much smaller interface distances to constrain every contraction. Contractions into \(\ell_1\)The small jumps in every chart force small average variation in \(\ell_1\). Throughout this section, scalar gradients carry the Euclidean norm. Proposition 2 (Contraction bound). Let \((V,d)\) and the chart maps \(v_s:U\to V\) be those of 1, where \(U=(-2,2)^m\), \(1\le s\le S=m^3\), and \(N=m^6\). There is an absolute constant \(C\) such that every map \(F:V\to\ell_1^D\), for every finite \(D\), satisfying \[\|F(v)-F(w)\|_1\le d(v,w)\qquad(v,w\in V)\] obeys \[ \mathbb E_{\theta,\eta\in T} \|F(v_1(\theta))-F(v_1(\eta))\|_1 \le C\sqrt m\,(\log m)^{5/2}, \tag{36}\] where \(T=(-1,1)^m\) and the two parameters are independent and uniform. After smoothing, each gradient is a combination of chart normals. The jump bounds give a total coefficient budget \(Cm(\log m)^2\), while the good-chart property contributes the factor \(C\sqrt{(\log m)/m}\). We then use the following scalar inequality to pass from gradients to average distances without a further dimension factor. Lemma 6 (First-moment inequality on a cube). Let \(T=(-1,1)^m\), and let \(h\) be a real-valued \(C^1\) function on a neighborhood of \(\overline T\). If \(\theta,\eta\) are independent and uniform on \(T\), then \[ \mathbb E|h(\theta)-h(\eta)| \le \mathbb E|\nabla h(\theta)|. \tag{37}\] We use the Gaussian rotation argument of Maurey and Pisier (Pisier 1986), followed by the coordinatewise Gaussian distribution function. Proof. Write \(\Phi\) for the standard Gaussian distribution function, set \(\psi(t)=2\Phi(t)-1\), and let \(\Psi:\mathbb R^m\to T\) apply \(\psi\) coordinatewise. If \(G,G'\) are independent standard Gaussian vectors in \(\mathbb R^m\), then \(\Psi(G),\Psi(G')\) are independent and uniform on \(T\). For \(0\le t\le\pi/2\), put \[Y(t)=\cos(t)G+\sin(t)G', \qquad Y'(t)=-\sin(t)G+\cos(t)G'.\] At each fixed time, \(Y(t)\) and \(Y'(t)\) are independent standard Gaussian vectors. Consequently, conditioning on \(Y(t)\) gives \[\begin{align*} \mathbb E\left[\left|\frac{d}{dt}h(\Psi(Y(t)))\right| \,\middle|\,Y(t)\right] &=\sqrt{\frac{2}{\pi}}\, \left|D\Psi(Y(t))^{T}\nabla h(\Psi(Y(t)))\right|\\ &\le \frac{2}{\pi}\,|\nabla h(\Psi(Y(t)))|, \end{align*}\] because \(\sup|\psi'|=\sqrt{2/\pi}\). The fundamental theorem of calculus, followed by Tonelli’s theorem, bounds the expected difference between the endpoints by the integral of the expected absolute derivative. The distribution of \(\Psi(Y(t))\) is uniform on \(T\) for every \(t\), so integration over \([0,\pi/2]\) proves (37). All the integrands are integrable: \(\nabla h\) is bounded on \(\overline T\), and Gaussian vectors have finite first moments. ◻ Proof of 2. We use \(r=m^{-8}\) and \(\tau=m^{-2000}\) as in 1. For each chart, define \[f_s(\theta)=F(v_s(\theta))\quad\text{for almost every }\theta\in U,\] and extend \(f_s\) by zero outside \(U\). Set \(f_s=0\) also on the threshold hyperplanes and on \(\partial U\). These are bounded, compactly supported functions because \(V\) is finite. The macroscopic estimate in 1 implies \[\begin{align*} \|f_s(\theta)-f_1(\theta)\|_1&\le Cr, &&\text{for almost every }\theta\in U,\tag{38}\\ \|f_s(\theta)-f_s(\eta)\|_1 &\le c_*\sqrt m\,|\theta-\eta|+Cr, &&\text{off the threshold hyperplanes in }U. \tag{39}\end{align*}\] Smoothing.Fix an even, nonnegative function \(\rho\in C_c^\infty((-1,1))\) with \(\int_\mathbb R\rho=1\). Set \(\lambda=m^{-2}\) and \[\kappa_\lambda(z)=\prod_{j=1}^m\lambda^{-1}\rho(z_j/\lambda), \qquad H_s=f_s*\kappa_\lambda.\] The functions \(H_s:\mathbb R^m\to\mathbb R^D\) are smooth. For sufficiently large \(m\), the support of \(x\mapsto\kappa_\lambda(\theta-x)\) lies in \(U\) whenever \(\theta\in\overline T\). Also \[\int_{\mathbb R^m}|\partial_j\kappa_\lambda| =\lambda^{-1}\|\rho'\|_{L_1(\mathbb R)}.\] Every displacement in the support of \(\kappa_\lambda\) has Euclidean norm at most \(\sqrt m\lambda\). Thus (39) gives \[ \|H_s(\theta)-f_s(\theta)\|_1\le C(m\lambda+r) \quad\text{for almost every }\theta\in T. \tag{40}\] Since \(f_s-f_1\) vanishes outside \(U\), (38) bounds its \(\ell_1\) norm by \(Cr\) almost everywhere on \(\mathbb R^m\). Differentiating the convolution therefore yields, for every \(\theta\in T\) and every \(j\), \[ \|\partial_jH_s(\theta)-\partial_jH_1(\theta)\|_1 \le Cr/\lambda. \tag{41}\] The derivative carried by each family of interfaces.Fix a chart \(s\) and abbreviate \(u_i=u_{s,i}\). Its interfaces are contained in the hyperplanes \[Q_{i,k}=\{x\in\mathbb R^m:\langle u_i,x\rangle=k\tau\}, \qquad 1\le i\le N,\quad k\in\mathbb Z.\] Only finitely many of these hyperplanes meet \(U\). At almost every point of \(Q_{i,k}\cap U\), let \(\Delta_{i,k}(x)\in\mathbb R^D\) denote the value of \(f_s\) on the side of increasing \(\langle u_i,x\rangle\) minus its value on the opposite side. This is well-defined away from intersections with the other interface hyperplanes. By the nonparallelism in 1, those intersections have zero \((m-1)\)-dimensional measure. The two labels at such an interface differ by \(\tau e_i\), so the adjacent-label estimate in 1 gives \[ \|\Delta_{i,k}(x)\|_1 \le C\tau\frac{m}{N}(\log m)^2 \quad\text{for almost every }x\in Q_{i,k}\cap U. \tag{42}\] For completeness, the distributional gradient of each scalar component of \(f_s\) on \(U\) is the vector-valued measure \[ D f_{s,\alpha} =\sum_{i,k}\frac{u_i}{|u_i|}\, \Delta_{i,k,\alpha}\, \mathcal H^{m-1}\!\restriction(Q_{i,k}\cap U). \tag{43}\] Indeed, test against a smooth function compactly supported in \(U\) and integrate by parts on each polyhedral cell. The cell interiors contribute nothing because \(f_s\) is constant there. The two contributions on each shared facet combine into the jump times the unit normal \(u_i/|u_i|\); lower-dimensional intersections have zero facet measure. The test function vanishes near \(\partial U\), so there is no contribution from the outer boundary. For \(\theta\in T\), the kernel \(\kappa_\lambda(\theta-\cdot)\) is a smooth test function compactly supported in \(U\). Convolving (43) with this kernel gives, for every component \(\alpha\), \[ \nabla H_{s,\alpha}(\theta) =\sum_{i=1}^N u_{s,i}\,b_{s,i,\alpha}(\theta), \tag{44}\] where the vector coefficient \(b_{s,i}(\theta)\in\mathbb R^D\) is \[ b_{s,i}(\theta)=\frac{1}{|u_{s,i}|} \sum_{k\in\mathbb Z}\int_{Q_{i,k}\cap U} \kappa_\lambda(\theta-x)\Delta_{i,k}(x) \,d\mathcal H^{m-1}(x). \tag{45}\] This identity holds at every \(\theta\in T\): distributional convolution agrees with the classical derivative of the smooth function \(H_s\). We claim that the coefficients satisfy the pointwise budget \[ \sum_{\alpha=1}^D|b_{s,i,\alpha}(\theta)| \le C\frac{m}{N}(\log m)^2 \qquad(\theta\in T). \tag{46}\] To establish it, fix \(u=u_{s,i}\) and \(\theta\), and let \(Z\) have density \(x\mapsto\kappa_\lambda(\theta-x)\). Write \(h\) for the density of the real random variable \(\langle u,Z\rangle\). The coarea formula for this linear functional states that \[h(t)=\frac{1}{|u|} \int_{\langle u,x\rangle=t} \kappa_\lambda(\theta-x)\,d\mathcal H^{m-1}(x).\] The lower bound \(|u|\ge1/2\) in 1 supplies a coordinate \(j\) with \(|u_j|\ge1/(2\sqrt m)\). Conditional on the other coordinates of \(Z\), the variable \(\langle u,Z\rangle\) has a translated, possibly reflected copy of the one-dimensional density \(\rho\), scaled by \(\lambda|u_j|\). Its derivative has \(L_1\) norm \(\|\rho'\|_{L_1}/(\lambda|u_j|)\). Taking the mixture over the other coordinates shows that \(h\) is continuously differentiable, compactly supported, and satisfies \[ \int_\mathbb R|h'(t)|\,dt\le C\sqrt m/\lambda. \tag{47}\] For any nonnegative, continuously differentiable, compactly supported density \(h\), comparison on each interval \([k\tau,(k+1)\tau]\) gives \[\tau h(k\tau) \le\int_{k\tau}^{(k+1)\tau}h(t)\,dt +\tau\int_{k\tau}^{(k+1)\tau}|h'(t)|\,dt.\] Summing and using (47), we obtain \[ \tau\sum_{k\in\mathbb Z}h(k\tau) \le1+C\tau\sqrt m/\lambda\le2 \tag{48}\] for all sufficiently large \(m\). Because the convolution kernel is nonnegative and is supported inside \(U\), the triangle inequality in (45), followed by (42) and (48), proves (46). Combining the charts.Fix \(\theta\in T\) and a component \(\alpha\), and put \(a_\alpha=\nabla H_{1,\alpha}(\theta)\). If \(a_\alpha\ne0\), the direction property in 1 gives at least \(S/2\) charts \(s\) such that \[\max_i\left|\left\langle \frac{a_\alpha}{|a_\alpha|},u_{s,i}\right\rangle\right| \le C\sqrt{\frac{\log m}{m}}.\] For each such chart, (44) implies \[|a_\alpha| \le C\sqrt{\frac{\log m}{m}}\sum_i|b_{s,i,\alpha}(\theta)| +|\nabla H_{s,\alpha}(\theta)-a_\alpha|.\] All terms on the right are nonnegative. Summing over the good charts and then enlarging that sum to all charts therefore gives \[ |a_\alpha|\le\frac{2}{S}\sum_{s=1}^S \left( C\sqrt{\frac{\log m}{m}}\sum_i|b_{s,i,\alpha}(\theta)| +|\nabla H_{s,\alpha}(\theta)-a_\alpha| \right). \tag{49}\] For \(a_\alpha=0\) the same inequality holds trivially. The good charts may depend on \(\alpha\) and \(\theta\); (49) removes that dependence before we sum over components. For each \(s\), the Euclidean norm is at most the sum of absolute coordinates, so (41) gives \[\sum_{\alpha=1}^D |\nabla H_{s,\alpha}(\theta)-\nabla H_{1,\alpha}(\theta)| \le\sum_{j=1}^m \|\partial_jH_s(\theta)-\partial_jH_1(\theta)\|_1 \le Cmr/\lambda.\] Sum (49) over \(\alpha\) and apply this bound and (46). We obtain at every \(\theta\in T\) \[\begin{align*} \sum_{\alpha=1}^D|\nabla H_{1,\alpha}(\theta)| &\le C\sqrt{\frac{\log m}{m}}\, N\frac{m}{N}(\log m)^2+Cmr/\lambda\\ &\le C\sqrt m\,(\log m)^{5/2}, \tag{50}\end{align*}\] where \(mr/\lambda=m^{-5}\). Finally, apply 6 to every component of \(H_1\) and sum. Equation (50) yields \[\mathbb E_{\theta,\eta\in T}\|H_1(\theta)-H_1(\eta)\|_1 \le C\sqrt m\,(\log m)^{5/2}.\] The expected distance for \(f_1\) exceeds this by at most \(2C(m\lambda+r)\), by (40). Since \(m\lambda=m^{-1}\), this additional term is absorbed into the same bound. The definition of \(f_1\) now proves (36). ◻ Exactly uniform demandsWe finish by converting the metric obstruction into capacities with unit demand on every unordered pair. We first record the precise duality statement, allowing distinct points to have distance zero. This is the average-distortion form of the cut/embedding correspondence (Linial et al. 1995, sec. 4)(Rabinovich 2008, sec. 1.3); the explicit programs below keep the unit-demand normalization visible. Lemma 7 (Cut-cone duality). Let \(d\) be a semimetric on \([n]\), where \(n\geq 2\), that satisfies the triangle inequalities and is a squared Hilbert distance. Suppose that \(a,b>0\) satisfy \[ \frac{1}{n^2}\sum_{i,j=1}^n d(i,j)\geq a, \qquad \frac{1}{n^2}\sum_{i,j=1}^n \|F(i)-F(j)\|_1\leq b \tag{51}\] for every map \(F\) into a finite-dimensional \(\ell_1\) space such that \(\|F(i)-F(j)\|_1\leq d(i,j)\) for all \(i,j\). Then there are nonnegative capacities \(c_{ij}\) on unordered pairs of distinct vertices such that, with demand exactly one on every pair, \[ \mathop{\mathrm{OPT}}(C)\geq 1, \qquad 0<\mathop{\mathrm{GL}}(C)\leq \frac{b}{a}. \tag{52}\] Proof. Let \(\mathcal S\) be the finite collection of nonempty proper subsets of \([n]\). For \(S\in\mathcal S\), write \(\delta_S(i,j)=|\mathbf 1_S(i)-\mathbf 1_S(j)|\). Consider the finite linear program.1 \[ \begin{aligned} \text{maximize}\quad & \sum_{S\in\mathcal S}|S|(n-|S|)t_S,\\ \text{subject to}\quad & \sum_{S\in\mathcal S}t_S\delta_S(i,j)\leq d(i,j) \quad (i<j),\\ &t_S\geq 0\quad(S\in\mathcal S). \end{aligned} \tag{53}\] It is feasible by taking every \(t_S=0\). For any feasible \(t\), the map \(F_t(i)=(t_S\mathbf 1_S(i))_{S\in\mathcal S}\) takes values in \(\ell_1^{|\mathcal S|}\) and is a contraction for \(d\). Its sum of distances over unordered pairs is exactly the objective in (53). Consequently (51) bounds the primal optimum by \(n^2b/2\). The primal optimum is attained: for each \(S\in\mathcal S\) and any pair separated by \(S\), feasibility implies \(0\leq t_S\leq d(i,j)\), so its feasible region is closed and bounded. The dual of (53), with one nonnegative variable \(c_{ij}\) for each unordered pair, is \[ \begin{aligned} \text{minimize}\quad &\sum_{i<j}c_{ij}d(i,j),\\ \text{subject to}\quad & \sum_{i\in S,\ j\notin S}c_{ij}\geq |S|(n-|S|) \quad(S\in\mathcal S),\\ &c_{ij}\geq 0\quad(i<j). \end{aligned} \tag{54}\] Here the cut sum counts each separated unordered pair once. The dual is feasible, for example with \(c_{ij}=1\) for every pair. Finite-dimensional linear programming duality therefore gives an optimal dual solution \(C\) satisfying \[ \sum_{i<j}c_{ij}d(i,j)\leq \frac{n^2b}{2}. \tag{55}\] Its cut constraints give \(\mathop{\mathrm{OPT}}(C)\geq1\) with exactly unit pair demands. Set \(D=\sum_{i<j}d(i,j)\geq n^2a/2>0\). If \(d(i,j)=|z_i-z_j|^2\) in a Hilbert space, the vectors \(z_i/\sqrt D\) give the feasible normalized SDP distances \(d(i,j)/D\). The span of the finitely many \(z_i\) has dimension at most \(n\), so these vectors can be realized in \(\mathbb R^n\). The triangles are preserved by normalization, and (55) gives \(\mathop{\mathrm{GL}}(C)\leq b/a\). Finally, the graph of pairs with \(c_{ij}>0\) is connected: otherwise the vertex set of one component would violate a cut constraint in (54). Choose a spanning tree \(\mathcal T\) in this graph and put \(\gamma=\min_{\{i,j\}\in\mathcal T}c_{ij}>0\). For any feasible SDP distance array \(d'\), the triangle inequalities along tree paths imply \[1=\sum_{i<j}d'(i,j) \leq \binom n2\sum_{\{i,j\}\in\mathcal T}d'(i,j).\] Hence its objective is at least \(\gamma/\binom n2>0\). This proves \(\mathop{\mathrm{GL}}(C)>0\), including when the original semimetric \(d\) has zero distances between distinct vertices. ◻ Replacing the parameter distribution by multiplicitiesFix a sufficiently large integer \(m\), and use the vertex set \(V\), semimetric \(d\), and chart map \(v_1\) from 1. Define the probability weights \[w_v=\Pr_{\theta\ \mathrm{uniform\ on}\ T} \big[v_1(\theta)=v\big], \qquad T=(-1,1)^m.\] Weights on vertices outside the first chart are thus zero. By [prop:metric,prop:contraction], for absolute positive constants that may change from line to line, \[ \begin{gathered} |V|\leq \exp(Cm\log m),\qquad \operatorname{diam}(V,d)\leq Cm,\qquad \sum_{v,z\in V}w_vw_zd(v,z)\geq cm,\\ \sum_{v,z\in V}w_vw_z\|F(v)-F(z)\|_1 \leq C\sqrt m\,(\log m)^{5/2} \end{gathered} \tag{56}\] for every finite-dimensional \(\ell_1\)-valued contraction \(F\) for \(d\). Every chart vertex must remain present, even if its weight is zero: its distance constraints still restrict contractions on the first chart. We therefore give each vertex at least one copy. In the choice below, the term \(m^2|V|\) controls the measure error, while \(m^m\) ensures the lower bound on \(\log n\) needed in the final parameter conversion. Set \[\begin{gathered} M=m^m+m^2|V|, \qquad k_v=1+\lfloor Mw_v\rfloor,\\ \widetilde V=\{(v,h):v\in V,\ 1\leq h\leq k_v\}, \qquad n=|\widetilde V|. \end{gathered}\] Give these copies the semimetric \(\widetilde d((v,h),(z,k))=d(v,z)\). It is again a squared Hilbert distance satisfying all triangles, by assigning the same Hilbert vector to every copy of a vertex. In particular, distances between copies of one vertex are zero. Let \(\mu_v=k_v/n\) be the pushforward to \(V\) of the uniform probability measure on \(\widetilde V\). To bound the rounding error, write \(e_v=k_v-Mw_v\in(0,1]\) and \(E_0=\sum_v e_v\). Then \(n=M+E_0\), where \(0<E_0\leq |V|\), and \[\mu_v-w_v=\frac{e_v-E_0w_v}{n}.\] Using the convention \(\|\mu-w\|_{\mathrm{TV}}=\frac12\sum_v|\mu_v-w_v|\), we obtain \[ \|\mu-w\|_{\mathrm{TV}} \leq \frac{E_0}{n} \leq \frac{|V|}{M} \leq \frac{1}{m^2}, \qquad \|\mu\otimes\mu-w\otimes w\|_{\mathrm{TV}} \leq \frac{2}{m^2}. \tag{57}\] The second inequality follows by writing the difference of the product measures as \((\mu-w)\otimes\mu+w\otimes(\mu-w)\) and applying the triangle inequality for total variation. For any function with values in \([0,Cm]\), the change in its expectation under these two product measures is at most \(2C/m\). Applying this to \(d\) gives \[ \frac{1}{n^2}\sum_{x,y\in\widetilde V}\widetilde d(x,y) =\sum_{v,z\in V}\mu_v\mu_zd(v,z) \geq c'm \tag{58}\] for all sufficiently large \(m\). Every contraction \(\widetilde F\) from \((\widetilde V,\widetilde d)\) into a finite-dimensional \(\ell_1\) space agrees on copies of a vertex, because the distance between those copies is zero. Since \(k_v\geq1\) for every \(v\), it therefore induces a contraction \(F\) on all of \(V\). The function \(\|F(v)-F(z)\|_1\) is bounded by \(d(v,z)\leq Cm\). Thus (56) and (57) give \[ \frac{1}{n^2}\sum_{x,y\in\widetilde V} \|\widetilde F(x)-\widetilde F(y)\|_1 \leq C'\sqrt m\,(\log m)^{5/2}. \tag{59}\] Apply 7 to (58)–(59). After labeling \(\widetilde V\) by \([n]\), this gives nonnegative capacities \(C^{(m)}\) with unit demands on all distinct pairs and \[ \frac{\mathop{\mathrm{OPT}}(C^{(m)})}{\mathop{\mathrm{GL}}(C^{(m)})} \geq c''\frac{\sqrt m}{(\log m)^{5/2}}, \qquad \mathop{\mathrm{GL}}(C^{(m)})>0. \tag{60}\] The number of verticesSince \(M\leq n\leq M+|V|\), (56) implies, for an absolute constant \(K\) and all sufficiently large \(m\), \[ m\log m\leq\log n\leq K m\log m. \tag{61}\] In particular \(n\to\infty\) and \(\log\log n\geq\log m\) for large \(m\). Consequently \[\frac{\sqrt{\log n}}{(\log\log n)^3} \leq \sqrt K\, \frac{\sqrt m}{(\log m)^{5/2}}.\] Combining this with (60) proves 1. Gaussian directions: the probabilistic proofProof of 1. Choose all the \(g_{s,i}\) independently with the standard Gaussian distribution on \(\mathbb R^m\). We show that the required events hold simultaneously with probability tending to one as \(m\to\infty\). We first record the elementary estimates used below. For a standard Gaussian \(G\) in \(\mathbb R^m\), \[ \mathbb E\cos\langle G,w\rangle=e^{-|w|^2/2}, \qquad \mathbb E\bigl[G\sin\langle G,w\rangle\bigr]=w e^{-|w|^2/2}. \tag{62}\] Indeed, rotation reduces the first identity to the one-dimensional cosine transform. Gaussian integration by parts gives the differential equation \(\phi'(t)=-t\phi(t)\) for that transform, with \(\phi(0)=1\). Differentiating the first identity with respect to \(w\) gives the second; the finite first Gaussian moment justifies this differentiation. Also, exponential Markov inequalities applied to \(\mathbb Ee^{t|G|^2}=(1-2t)^{-m/2}\), for \(t<1/2\), give for an absolute \(c>0\) \[ \Pr\left\{|G|\notin[\sqrt m/2,2\sqrt m]\right\} \le 2e^{-c m}. \tag{63}\] We will use the following bounded-variable estimate, a form of Hoeffding’s inequality (Hoeffding 1963). If \(X_1,\ldots,X_n\) are independent real random variables with \(|X_j|\le B\), then, for \(0<u\le B\), \[ \Pr\left\{\left|\frac1n\sum_{j=1}^n(X_j-\mathbb EX_j)\right|>u\right\} \le 2\exp\left(-\frac{c n u^2}{B^2}\right). \tag{64}\] For completeness, Taylor expansion, the vanishing first centered moment, and \(|X_j-\mathbb EX_j|\le2B\) give \(\mathbb Ee^{t(X_j-\mathbb EX_j)}\le e^{C t^2B^2}\) when \(|t|\le1/(2B)\). Independence and exponential Markov, with \(t\) a sufficiently small constant multiple of \(u/B^2\), give both tails in (64). To obtain (4), truncate each Gaussian summand on the event \(|G|>2\sqrt m\). By Cauchy–Schwarz and (63), uniformly in \(w\), \[ \left|\mathbb E\bigl[G\sin\langle G,w\rangle \mathbf 1_{\{|G|\le2\sqrt m\}}\bigr] -w e^{-|w|^2/2}\right| \le \mathbb E\bigl[|G|\mathbf 1_{\{|G|>2\sqrt m\}}\bigr] \le e^{-c' m}, \tag{65}\] after decreasing the positive constant \(c'\) and taking \(m\) large. For a fixed unit vector \(v\) and fixed \(w\), the scalar truncated summand \[\langle v,G\rangle\sin\langle G,w\rangle \mathbf 1_{\{|G|\le2\sqrt m\}}\] has absolute value at most \(2\sqrt m\). Thus (64), with \(n=N\) and \(u=1/(2\sqrt m)\), bounds its empirical-mean deviation probability by \(2e^{-cN/m^2}\). Choose a \(1/8\)-net \(\mathcal V\) of the unit sphere and an \(m^{-3}\)-net \(\mathcal W\) of the ball of radius \(m^{42}\). The usual disjoint-ball packing argument gives \[|\mathcal V|\le17^m, \qquad |\mathcal W|\le(1+2m^{45})^m =\exp(O(m\log m)).\] Union bound the preceding scalar deviations over \(s\), \(v\in\mathcal V\), and \(w\in\mathcal W\). The failure probability tends to zero, since \(N/m^2=m^4\). On the resulting event, for every \(s\) and \(w\in\mathcal W\), the vector deviation from its truncated expectation is at most \(4/(7\sqrt m)\): bounds on inner products with a \(1/8\)-net control the Euclidean norm with factor \(8/7\). Each truncated empirical vector function is \(4m\)-Lipschitz in \(w\), because the operator norm of its derivative is at most the average of the truncated \(|g_{s,i}|^2\). The function \(w\mapsto we^{-|w|^2/2}\) is \(2\)-Lipschitz. Consequently the bias bound (65) and interpolation from \(\mathcal W\) give, uniformly on the whole ball, an error at most \[\frac{4}{7\sqrt m}+e^{-c'm}+(4m+2)m^{-3} \le \frac2{\sqrt m}\] for all sufficiently large \(m\). This proves the desired approximation for the truncated samples. The covariance estimate follows from the same argument with quadratic forms. For a fixed unit vector \(v\), the variable \(\langle v,G\rangle^2\mathbf 1_{\{|G|\le2\sqrt m\}}\) is bounded by \(4m\), and its expectation differs from \(1\) by at most \[\bigl(\mathbb E\langle v,G\rangle^4\bigr)^{1/2} \Pr\{|G|>2\sqrt m\}^{1/2} \le e^{-c'm},\] where constants can again be adjusted, since \(\mathbb E\langle v,G\rangle^4=3\). Apply (64) with \(u=1/8\), and union bound over \(s\) and \(v\in\mathcal V\). With probability tending to one, every truncated empirical covariance matrix \(M_s\) satisfies \[\|M_s-I_m\|_{\mathrm{op}} \le\frac{1}{1-2/8}\left(\frac18+e^{-c'm}\right) <\frac12.\] Here we used the elementary symmetric-matrix net estimate \(\|A\|_{\mathrm{op}}\le(1-2\rho)^{-1}\max_{v\in\mathcal V}|\langle Av,v\rangle|\) for a sphere net of radius \(\rho<1/2\). By (63), all \(SN=m^9\) original Gaussian samples satisfy (3) with probability tending to one. On this event the truncations change no sample, so the preceding conclusions establish the first two assertions. Pairwise nonparallelism within each family holds almost surely. It remains to establish (5). For a fixed unit vector \(v\), the one-dimensional Gaussian tail bound gives \[\Pr\left\{\max_i|\langle v,g_{s,i}\rangle| >10\sqrt{\log m}\right\} \le 2N e^{-50\log m}=2m^{-44}.\] Call such an index \(s\) bad for \(v\). Before any conditioning, these bad-index events are independent across \(s\). Therefore the probability that at least \(S/2\) indices are bad for this fixed \(v\) is at most \[2^{S}(2m^{-44})^{S/2}.\] Take a sphere net of radius \(1/m\), with cardinality at most \((1+2m)^m\), and union bound this last estimate over its points. The resulting failure probability tends to zero. Finally intersect with the already established norm event. If \(v_0\) is a net point with \(|v-v_0|\le1/m\), then \[|\langle v-v_0,g_{s,i}\rangle|\le\frac2{\sqrt m}\] for every \(s,i\). Every chart good for \(v_0\) consequently satisfies (5) for \(v\), with \(C=11\) for all sufficiently large \(m\). This argument uses independence only for the unconditioned Gaussian samples. A final union bound intersects this event with the preceding high-probability events and proves the lemma. ◻
Arora, Sanjeev, Satish Rao, and Umesh Vazirani. 2009. “Expander Flows, Geometric Embeddings and Graph Partitioning.” Journal of the ACM 56 (2): 5:1–37.
Chang, Alan, Assaf Naor, and Kevin Ren. 2025a. “Optimal Rounding for Sparsest Cut.” Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 643–52. https://doi.org/10.1145/3717823.3718285.
Chang, Alan, Assaf Naor, and Kevin Ren. 2025b. Random Zero Sets with Local Growth Guarantees.
Cheeger, Jeff, and Bruce Kleiner. 2010. “Differentiating Maps into \(L^1\), and the Geometry of BV Functions.” Annals of Mathematics 171 (2): 1347–85. https://doi.org/10.4007/annals.2010.171.1347.
Cheeger, Jeff, Bruce Kleiner, and Assaf Naor. 2009. “A \((\log n)^{\Omega(1)}\) Integrality Gap for the Sparsest Cut SDP.” Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 555–64. https://arxiv.org/abs/0910.2024.
Cheeger, Jeff, Bruce Kleiner, and Assaf Naor. 2011. “Compression Bounds for Lipschitz Maps from the Heisenberg Group to \(L_1\).” Acta Mathematica 207 (2): 291–373. https://arxiv.org/abs/0910.2026.
Devanur, Nikhil R., Subhash A. Khot, Rishi Saket, and Nisheeth K. Vishnoi. 2006. “Integrality Gaps for Sparsest Cut and Minimum Linear Arrangement Problems.” Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC ’06, 537–46.
Goemans, Michel X. 1997. “Semidefinite Programming in Combinatorial Optimization.” Mathematical Programming 79: 143–61. https://doi.org/10.1007/BF02614315.
Hoeffding, Wassily. 1963. “Probability Inequalities for Sums of Bounded Random Variables.” Journal of the American Statistical Association 58 (301): 13–30. https://doi.org/10.1080/01621459.1963.10500830.
Kane, Daniel M., and Raghu Meka. 2013. “A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut.” Proceedings of the 45th Annual ACM Symposium on Theory of Computing, STOC ’13, 1–10.
Khot, Subhash A., and Nisheeth K. Vishnoi. 2015. “The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into \(\ell_1\).” Journal of the ACM 62 (1): 8:1–39.
Lee, James R., and Assaf Naor. 2006. “\(L_p\) Metrics on the Heisenberg Group and the Goemans–Linial Conjecture.” Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 99–108. https://doi.org/10.1109/FOCS.2006.47.
Linial, Nathan. 2002. “Finite Metric-Spaces—Combinatorics, Geometry and Algorithms.” Proceedings of the International Congress of Mathematicians (Beijing) III: 573–86.
Linial, Nathan, Eran London, and Yuri Rabinovich. 1995. “The Geometry of Graphs and Some of Its Algorithmic Applications.” Combinatorica 15 (2): 215–45.
Matoušek, Jiří, and Yuri Rabinovich. 2001. “On Dominated \(\ell_1\) Metrics.” Israel Journal of Mathematics 123: 285–301.
Naor, Assaf, and Robert Young. 2018. “Vertical Perimeter Versus Horizontal Perimeter.” Annals of Mathematics 188 (1): 171–279.
Pisier, Gilles. 1986. “Probabilistic Methods in the Geometry of Banach Spaces.” In Probability and Analysis, edited by Giorgio Letta and Maurizio Pratelli, vol. 1206. Lecture Notes in Mathematics. Springer. https://doi.org/10.1007/BFb0076302.
Rabinovich, Yuri. 2003. “On Average Distortion of Embedding Metrics into the Line and into \(L_1\).” Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 456–62. https://doi.org/10.1145/780542.780609.
Rabinovich, Yuri. 2008. “On Average Distortion of Embedding Metrics into the Line.” Discrete & Computational Geometry 39 (4): 720–33. https://doi.org/10.1007/s00454-007-9047-5.
Rahimi, Ali, and Benjamin Recht. 2007. “Random Features for Large-Scale Kernel Machines.” Advances in Neural Information Processing Systems 20: 1177–84.
Schoenberg, I. J. 1938. “Metric Spaces and Positive Definite Functions.” Transactions of the American Mathematical Society 44 (3): 522–36.
Zaslavsky, Thomas. 1975. “Facing up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes.” Memoirs of the American Mathematical Society 1 (154): vii+102. https://doi.org/10.1090/memo/0154.
|
| ||||||||
|