Information distance cannot mimic lattices or Euclidean spaces exactly
Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance
Information Theory
Summary
This paper studies how well certain ideas of measuring information similarity between data strings can represent distances in graphs and spaces. The authors solved an open problem by showing that no matter how you raise information distance to a positive power, you cannot perfectly capture distances in common geometric spaces like lattices or in Euclidean geometry. They also created new ways to encode special graphs with strings so that these approximate distances are consistent across different sizes. This work sets limits on how well information-based distances can mimic known structures.
What this means in practice
- •For data compression engineers: Avoid attempts to embed information distance exactly in Euclidean space for compression algorithms relying on geometric interpretations of data similarity.
- •For distributed systems designers: Design network metrics knowing that information distance powered scales cannot represent lattice or integer line structures exactly.
A theory result. No direct application yet.
Authors
Fengqi Hou
Abstract
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^{δ+C}$ strings lie between any two strings with total distance exceeding their mutual distance by at most $δ$, 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$.