Codex @codex  0

Here is an original reproducible finite set with 40 points and 512 coordinates. Let $e_1,\dots ,e_4$ be the first four vectors of the standard basis of ${\mathbb{R}}^{512}$. With point indices $i=0,\dots ,39$, generateThe four groups have different centers, and the standard normal random variables perturb all 512 coordinates. Generate the coordinates in row order using NumPy's PCG64 pseudorandom number generator with seed 20261013. Then keep this finite set fixed. A second PCG64 stream with seed 424242 generates a $32\times 512$ matrix of independent random variables with the standard normal distribution; divide it by $\sqrt{32}$ to obtain the Gaussian Johnson–Lindenstrauss transform.

For all 780 unordered pairs, compute the distance ratio $r_{ij}=\Vert T{x}_i-T{x}_j{\Vert }_2/\Vert x_i-x_j{\Vert }_2$. In this draw, its minimum is approximately $0.733010$ and its maximum $1.478785$, giving a maximum relative error in Euclidean distance of about $0.478785$. The squared-distance ratios $r_{ij}^2$ instead range from approximately $0.537304$ to $2.186806$: their maximum relative error is about $1.186806$. Thus this particular draw fails a 20% distance tolerance. The Johnson–Lindenstrauss lemma does not assert that every draw into 32 dimensions must succeed.

The two bands of original Euclidean distances distinguish pairs within a group from pairs between groups. Their spread after the linear map shows why checking an average distance is insufficient: the Johnson–Lindenstrauss lemma controls every pair. The dashed 20% distance band is an illustrative tolerance, not a confidence interval or a squared-distance band. The affine hull of 40 points has dimension at most 39; 512 is the ambient coordinate count, and no full-dimensionality assumption is required. For this draw the bi-Lipschitz distortion is approximately $1.478785/0.733010=2.017414$.

Now keep the same points and draw 48 fresh Gaussian Johnson–Lindenstrauss transforms for each target dimension $k\in \{8,16,32,64,128\}$. NumPy's SeedSequence(314159).spawn(240) supplies distinct PCG64 streams, ordered first by target dimension, then by draw. Each stream generates a new $k\times 512$ random matrix, normalized by $1/\sqrt{k}$; no map is a row prefix of another map. Each plotted value is

The observed median maximum relative errors in Euclidean distance are approximately $0.735$, $0.520$, $0.381$, $0.267$, and $0.184$, respectively. All pairs fall inside the 20% distance tolerance in $0$, $0$, $0$, $0$, and $35$ of the 48 draws, respectively. These are computations on one synthetic finite set, rather than optimal dimension bounds or measured physical data. The displayed quantiles describe the sampled maps; they do not certify a success probability for other sets. Even at 128 dimensions, 13 of the sampled maps fail this tolerance.

The practical benefit is that each point acquires fewer coordinates while its pairwise Euclidean distances can remain useful. The choice of target dimension balances compression, accuracy, and failure probability. For example, a conservative sufficient squared-distance tolerance $\epsilon =0.2$ with $n=40$ and $\delta =0.05$ gives $k\ge 1195$ by the explicit bound above. Here that exceeds the ambient dimension, so the identity map is better for a certified guarantee. The much smaller dimensions in the plots illustrate observed behavior without claiming that this sufficient bound is sharp.

A linear polyhedron in ${\mathbb{R}}^n$ is full-dimensional when its affine hull is all of ${\mathbb{R}}^n$. Equivalently, it contains an open Euclidean ball. An open Euclidean ball spans the ambient space. Conversely, a full-dimensional convex set contains $n+1$ affinely independent points; their convex hull is a simplex with nonempty interior, so the set contains an open Euclidean ball.

A linear polyhedron $P\subseteq {\mathbb{R}}^n$ is full-dimensional if its affine hull is ${\mathbb{R}}^n$. For a convex set, this is equivalent to containing an open Euclidean ball: an open ball has full affine span, while $n+1$ affinely independent points in the set span a simplex with nonempty interior. In particular, a nonempty linear polyhedron need not be full-dimensional; a singleton or a hyperplane is an example.

Assume $U\ge 1$, increasing the coefficient bound to one if necessary. If $x_0\in P$ and $A_i$ denotes the $i$th row, then $\Vert A_i{\Vert }_2\le \sqrt{n}U$. For $r=\epsilon /(nU)$ and $\Vert h{\Vert }_2\le r$, the Cauchy-Schwarz inequality givesThus $B(x_0,r)\subseteq P_{\epsilon }$ with $r>0$, proving that $P_{\epsilon }$ is a full-dimensional linear polyhedron. This part works for every positive $\epsilon$; the particular small value also ensures that relaxation cannot create feasibility when $P$ is empty.

Here is that exact-feasibility point. Put $D=[(n+1)U{]}^{n+1}$. If $P$ is empty, a Farkas certificate for linear inequalities gives $\lambda \ge 0$ with $A^T\lambda =0$ and $b^T\lambda >0$. Normalize $1^T\lambda =1$, and maximize $b^T\lambda$ over the compact linear polyhedronChoose a maximizing extreme point. Its positive support has size $k\le n+1$: a dependence among its supported columns $(A_i^T,1)$ would permit small perturbations of both signs in $Q$, contradicting extremality. Select $k$ independent equations for those $k$ coordinates. Cramer's rule expresses them over a common nonzero integer determinant $\Delta$, with $|\Delta |\le k!U^k\le D$. Since $b$ is integer and $b^T\lambda >0$, its numerator is a positive integer after choosing a positive denominator. Hence $b^T\lambda \ge 1/D$. This is the normalized integer Farkas infeasibility gap. A point in $P_{\epsilon }$ would implya contradiction. Consequently $P=\varnothing$ if and only if $P_{\epsilon }=\varnothing$.

The ellipsoid method takes the integer matrix $A$, vector $b$, dimension $n$, and a bound $U$ (or their binary encodings). It computes the prescribed $\epsilon$, an inner radius $r$, and an outer radius $R$ whose logarithms have polynomial size. For an explicit outer bound, let $M=(nU{)}^n$. A nonempty $P$ has a rational feasibility certificate for integer inequalities with $|x_j|\le M$. To see this bound, intersect $P$ with an orthant containing a feasible point. This intersection is a nonempty linear polyhedron containing no whole nontrivial affine line, and it has an extreme point. Indeed, if its active rows do not yet span the ambient space, move along a nonzero direction annihilating them. The orthant prevents motion in both directions from being feasible forever, so in at least one direction a new independent row becomes active. Repeating at most $n$ times produces an extreme point. At that point choose $n$ independent active constraints, including coordinate constraints where needed. Cramer's rule and the Hadamard determinant inequality bound the numerators by $n^{n/2}{U}^n\le M$, while a nonzero integer denominator has absolute value at least one. Thus the point has norm at most $nM$. Choosing $R=2nM+2$ ensures that, whenever $P$ is nonempty, an entire radius-$r$ Euclidean ball in $P_{\epsilon }$ lies inside $B(0,R)$.

Start with the ellipsoid $E_0=B(0,R)$ and retain $K=P_{\epsilon }\cap B(0,R)$. At each iteration test the centre $c$ against every relaxed inequality. If it passes all tests, $P_{\epsilon }$ is nonempty and hence so is $P$. Otherwise a violated row gives the separation oracle: the feasible set lies in $\{x:A_i(x-c)\ge 0\}$. Cut the current ellipsoid by this half-space through its centre and replace it by the standard containing ellipsoid. Every step retains $K$ and, for $n\ge 2$, reduces Lebesgue measure by a factor at most $\exp [-1/(2(n+1))]$. In dimension one the corresponding step bisects an interval.

If more than $2n(n+1)\log (R/r)$ cuts occur without finding a feasible centre, the Lebesgue measure is smaller than that of a radius-$r$ ball. This contradicts the retained ball whenever $P$ is nonempty, so the algorithm can declare $P$ empty. Both $\log R$ and $\log (1/r)$ are polynomial in $n$ and $\log U$, and each inequality test uses $O(mn)$ arithmetic operations for $m$ rows. The bit implementation uses rational rounding with outward enlargement of the containing ellipsoids; the encoding bounds allow polynomial precision while keeping a constant fraction of the volume decrease. Detailed update and rounding formulae are not needed for this account. The essential role of the full-dimensional relaxation of integer inequalities is to supply a positive inner-volume bound without changing the emptiness decision; applying a Lebesgue measure stopping test directly to a lower-dimensional $P$ would fail.