Source-linked AI summary
Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance
Fengqi Hou
TL;DR
Hutter’s open problems concern scale-embeddings of finite complete bipartite graphs and integer lattices, and exact real-Hilbert representations of positive powers of information distance. The paper constructs finite-field-based string and fixed-sequence embeddings for complete bipartite graphs and bounds the number of strings lying within a fixed excess of a two-string distance. For 0 < α ≤ α0, the embeddings cover the remaining exponent range; no positive-dimensional integer lattice admits a scale-embedding into B∗ K.
Problem
Hutter’s open problems concern scale-embeddings of finite complete bipartite graphs and integer lattices, and exact real-Hilbert representations of positive powers of information distance.
Source: §1 · pp. 1–2, §6 · p. 13Method
The paper constructs finite-field-based string and fixed-sequence embeddings for complete bipartite graphs and bounds the number of strings lying within a fixed excess of a two-string distance.
Source: §1 · pp. 1–2, §3.1 · p. 5Results
For 0 < α ≤ α0, the embeddings cover the remaining exponent range; no positive-dimensional integer lattice admits a scale-embedding into B∗ K.
Source: §1 · p. 2Takeaways & Limitations
The results resolve the finite complete bipartite scale-embedding problem affirmatively and rule out the proposed Hilbert-space and integer-lattice representations.
Source: §1 · pp. 1–2The real ℓ1 conclusion follows from the lattice obstruction and does not establish non-embeddability for every unbounded subset.
Source: §5.3 · p. 13
Abstract
from arXiv · showhide
We encode the vertices of every finite complete bipartite graph as binary strings at each scale. The information distances between these strings approximate the scaled graph distances with an additive error bounded by a constant independent of the scale. We also assign one fixed infinite binary sequence to each vertex; suitable prefixes satisfy the same distance estimate with logarithmic error. This extends Hutter's construction for $K_{3,3}$ and resolves his open problem on scale-embeddings of finite complete bipartite graphs. Combined with his complete bipartite obstruction, these embeddings show that no positive power of information distance can be represented exactly by distances in a real Hilbert space, resolving his question about such representations. For conditional prefix complexity, we further prove that at most $2^{\delta+C}$ strings lie between any two strings with total distance exceeding their mutual distance by at most $\delta$, where $C$ is independent of the endpoints. This bound rules out scale-embeddings of the integer line and every positive-dimensional integer lattice, resolving Hutter's lattice embedding problem for both string and sequence embeddings. Restriction to the integer lattice gives the same conclusion for $(\mathbb R^m,\|\cdot\|_1)$ for every $m\ge1$.
1 Introduction
Hutter’s scale-embedding problem asked whether every finite complete bipartite graph could be embedded into information distance, beyond his construction for K3,3 [2]. This paper establishes string and sequence embeddings, then derives consequences for Hilbert representations and integer lattices.
1 Introduction
- The embeddings extend Hutter’s K3,3 construction [2] and resolve Open Problem 37 for both string and sequence scale-embeddings.String-embedding distances approximate s times graph distance within a constant; sequence-prefix distances have error at most A log2(s + 2) + C.Source: §1 · p. 1
- Every finite complete bipartite graph has a string embedding with scale-independent constant error and a fixed-sequence embedding with logarithmic error.The matrix construction uses 2 × 2 matrices over a sufficiently large finite field.Source: §1 · pp. 1–2
- For each positive exponent, prefixes of a fixed finite family of infinite sequences give non-Euclidean finite sets at every sufficiently large selected scale; embeddings cover the remaining range 0 < α ≤ α0.Source: §1 · p. 2
- A bound on near-geodesic intermediate strings rules out scale-embeddings of the integer line and positive-dimensional integer lattices.Restriction to the integer lattice also rules out the full space (Rm, ∥·∥1); the optional monotone-complexity convention is discussed separately.Source: §1 · p. 2
2 Definitions and main results
The paper defines information distance and scale-embeddings, then proves embeddings for every finite complete bipartite graph. These results rule out exact real-Hilbert representations of positive powers of information distance and scale-embeddings of positive-dimensional integer lattices.
2.1 Information distance and scale-embeddings
- Information distance is the maximum of the two conditional prefix complexities, with distance zero on the diagonal and a fixed constant added otherwise.A string scale-embedding approximates scaled metric distances with uniform additive error; a sequence scale-embedding uses prefixes of fixed infinite sequences.Source: §2.1 · pp. 2–3
2.2 Complete bipartite graph embeddings
- For every pair of positive integers m,n, the theorem supplies injections from V(G) to binary strings for each s≥1 and fixed infinite binary sequences whose length-L(s) prefixes are injective for every s≥1.Source: §2.2 · p. 3
2.3 Positive powers of information distance and Hilbert-space representations
- For every α > 0, no map represents dK(x, y)^α exactly as distances in a real Hilbert space.For every positive exponent, selected finite sets of prefixes of fixed infinite sequences also have no isometric real-Hilbert representation at sufficiently large scales.Source: §2.3 · p. 4
2.4 Integer lattices
- No positive-dimensional integer lattice (Zm, ∥·∥1) has a string or sequence scale-embedding into conditional prefix-complexity distance.This gives a negative answer to Hutter’s Open Problem 29 for that distance.Source: §2.4 · p. 4
3 Complete bipartite graph embeddings
The construction uses finite-field matrix products to encode complete bipartite graph vertices and control their conditional complexities. It yields scale-dependent finite strings with constant error and fixed infinite sequences whose prefixes have logarithmic error.
3.1 The finite-field matrix construction
- Each vertex string concatenates encodings of its products with successive matrices; products at two same-side vertices determine the matrix, while opposite-side products are convertible using one additional field element.The construction uses fixed direction vectors over a finite field, with enough distinct directions for both sides.Source: §3.1 · pp. 4–5
3.2 Conditional complexity estimates
- For matrix data Wℓ satisfying (10), K(Wℓ|ℓ)≥4T−∆, and combining this condition with the preceding upper bound gives k≥2T−∆−C; one constant C0 works for all distinct vertices, lengths ℓ, and such data.Source: §3.2 · pp. 6–7
3 Complete bipartite graph embeddings
- For each scale, counting arguments provide matrix data with the required incompressibility, while a fixed random infinite sequence supplies data with logarithmic complexity loss.The fixed-sequence construction uses prefixes of one sequence and prefixes grow linearly with scale.Source: §3.2 · p. 6, §3.3 · p. 7, §3.4 · p. 8
3.3 The finite-string embedding
- At each scale, injective vertex strings approximate scaled graph distances with error bounded independently of scale; diagonal distances are exact.Incompressible matrix data and fixed tags produce the strings.Source: §3.3 · pp. 7–8
3.4 The fixed infinite sequences
- Fixed infinite sequences have prefixes whose information distances approximate scaled graph distances with logarithmic error, and their selected lengths grow linearly with scale.The sequences remain fixed as scale increases; only prefix lengths change.Source: §3.2 · p. 6, §3.4 · p. 8
4 Non-Euclidean powers of information distance
The paper applies a zero-sum weighted squared-distance test to complete bipartite graph embeddings. It concludes that no positive power of information distance has an exact representation by distances in a real Hilbert space.
4 Non-Euclidean powers of information distance
- For every positive exponent, no exact representation of information distance raised to that power by real Hilbert-space distances exists.The result includes exponents for which the powered distance need not satisfy the triangle inequality.Source: §4 · pp. 8, 10
- In a real Hilbert space, any zero-sum weights make the weighted sum of squared pairwise distances nonpositive; a positive sum therefore rules out representation.The paper applies this criterion using weights 1/N on one side of K_N,N and −1/N on the other.Source: §4 · p. 9
- For sufficiently large selected scales, the fixed-sequence prefixes also cannot be represented by real Hilbert-space distances equal to the powered information distances.At each scale, the proposed representation may use its own Hilbert space and map.Source: §4 · p. 10
- The fixed-sequence construction covers the range 0 < α ≤ α0 left open by Hutter’s K3,3 sequence construction, yielding the conclusion for every α > 0.The cited prior construction gives the conclusion for α > α0.Source: §4 · p. 10
5 Non-embeddability of integer lattices
The section uses conditional prefix-complexity estimates to bound the number of strings near any pair, then uses that bound to rule out scale-embeddings of integer lattices and real ℓ1 spaces.
5.1 Two prefix-complexity estimates
- The conditional chain rule yields a composition estimate K(w, y | x) ≤ K(w | x) + K(y | w) + Ccomp, with Ccomp independent of the strings.The chain rule supplies K(x | t) as auxiliary input, and the estimate follows by ignoring additional conditions at fixed cost.Source: §5.1 · pp. 10–11
5.2 Uniform interval counting
- At most 2^(δ+C) strings lie in the δ-interval between any x and y, with C independent of the endpoints; consequently, every such interval is finite.The bound applies both when x ≠ y and on the diagonal; unlike a related plain-complexity argument, its constant depends only on δ and a fixed constant.Source: §5.2 · pp. 11–12
5.3 From the integer line to integer lattices
- No map from the nonnegative integers to strings can approximate ray distances at any fixed positive scale with finite uniform error, even without computability or injectivity assumptions.The images of arbitrarily long initial segments would lie in one uniformly bounded interval, while each image can occur only a bounded number of times.Source: §5.3 · p. 12
- Restricting a proposed lattice embedding to an integer ray contradicts the ray theorem; the same argument rules out both string and sequence embeddings of positive-dimensional integer lattices.For sequence embeddings, the selected prefix lengths may vary by lattice point without affecting the restricted distance estimate.Source: §5.3 · pp. 12–13
- For every m ≥ 1, (R^m, ||·||_1) admits neither a string nor a sequence scale-embedding, by restriction to its integer-coordinate lattice.This conclusion does not assert non-embeddability for every unbounded subset.Source: §5.3 · p. 13
6 Concluding remarks
The paper’s finite-field construction resolves the finite complete bipartite graph embedding problem and, with Hutter’s obstruction, rules out exact Hilbert-space representations of positive powers of information distance.
6 Concluding remarks
- Every finite complete bipartite graph has a scale-embedding into information distance, with constant error for finite strings and logarithmic error for prefixes of fixed infinite sequences.Combined with Hutter’s Theorem 36 [2], these embeddings show that no positive power of information distance is represented exactly by distances in a real Hilbert space.Source: §6 · p. 13
- The interval bound rules out scale-embeddings of the whole integer line into information distance, even at one positive scale with finite uniform error.The obstruction applies to all integer pairs.Source: §6 · p. 13
A Scope of formal verification
The main results are formalized in Lean, with library support for standard complexity estimates and proofs in the accompanying code for the paper’s central constructions and non-embedding arguments.
A Scope of formal verification
- The formalization covers both parts of the graph-embedding theorem, including exact string lengths, injectivity, error bounds, and selected-prefix-length properties.The formal statement also covers s = 0; restricting to s ≥ 1 gives the paper’s stated result.Source: A Scope of formal verification · p. 14
- The formalized infinite-source construction uses Martin–Löf random sequences and the Levin–Schnorr theorem to establish the logarithmic conditioning cost of the block count.The proof also establishes that the packed matrix blocks are prefixes of the chosen random sequence.Source: A Scope of formal verification · p. 14
- The interval lemma is formalized using the conditional chain rule, bounded conditional prefix complexity, and a fixed cost for exchanging encoded-pair components.The nonrepresentation results use prefix K throughout; monotone Km is outside the formalization’s scope.Source: A Scope of formal verification · pp. 14–15