🔢 mathematics

Maximal Kolmogorov Complexity in a Hamming Ball

This paper characterizes the attainable values of the maximal Kolmogorov complexity within a Hamming ball of a given radius around a string, establishing a realizability condition for the triple (complexity, radius, maximal complexity) and identifying four universal properties of the resulting complexity-radius function while leaving the characterization of intermediate profiles as an open problem.

Original authors: Alexander Kozachinskiy, Nikolay Vereshchagin

Published 2026-09-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexander Kozachinskiy, Nikolay Vereshchagin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a vast library containing every possible book of a certain length, written in a simple language of only zeros and ones. In this library, every single book is unique, but some are far more intricate than others. A short book might be a simple repetition of a pattern, easy to describe in a few words. A long, complex book, however, might look like random static, requiring a description as long as the book itself to be fully captured. This measure of how much information is needed to describe a specific string of data is known as its complexity. Now, imagine taking one of these books and introducing a few errors—flipping a few zeros to ones or vice versa. This creates a small neighborhood of slightly corrupted versions surrounding the original. The question researchers ask is: within this neighborhood of corrupted versions, how complex can the most complicated book be?

This inquiry sits at the heart of algorithmic information theory, a field that treats information as a physical property of data itself, independent of any specific computer or human observer. For decades, scientists have studied the opposite side of this coin: they looked for the simplest possible version of a book within a neighborhood of errors, treating that simple version as the "true" signal hidden beneath the noise. This paper turns the lens around to investigate the other extreme. It asks how much complexity can be generated by adding noise. If you start with a moderately complex string and allow for a certain number of errors, what is the ceiling of complexity you can reach? The answer is not a single fixed number but depends on the specific starting string and the size of the error allowance, revealing a landscape of possibilities that was previously uncharted.

The researchers, Alexander Kozachinskiy and Nikolay Vereshchagin, set out to map the boundaries of this complexity. They defined a specific function that tracks the maximum complexity found at every possible distance from a starting string. As you allow for more errors, the radius of your search expands, and you encounter new strings. The authors wanted to know the shape of the curve that describes the highest complexity found at each step. They discovered that while the curve can take many forms, it is strictly confined by two invisible walls. One wall represents the simplest possible scenario, where the starting string is part of a tightly packed cluster of similar strings, limiting how much complexity can be found nearby. The other wall represents the most chaotic scenario, where the starting string is part of a highly structured code designed to correct errors, allowing the search to reach strings of maximum possible complexity.

The paper proves that for any starting complexity level, the maximum complexity found at a given distance must fall between these two limits. The lower limit is determined by a geometric principle known as an isoperimetric inequality, which essentially states that a compact shape has the smallest possible surface area. In this context, it means that if you start with a string that is part of a dense cluster, the surrounding strings cannot be too complex because there simply aren't enough unique variations available within that tight space. The upper limit is determined by the properties of error-correcting codes. If the starting string is part of a code designed to fix errors, the neighborhood can reach out to cover a much wider variety of complex strings, effectively maximizing the complexity found at that distance.

The authors did not just find these limits; they showed that both extremes are actually achievable. They constructed specific examples of strings that hit the lower bound, behaving like a single, dense ball of similar data. They also constructed strings that hit the upper bound, behaving like the centers of a robust error-correcting code. Furthermore, they demonstrated that for any single point of measurement, the possible values of maximum complexity are fully characterized and fall within a specific range. However, the question of whether every possible curve shape that obeys the basic rules can be realized by some string remains an open problem. The researchers established four fundamental rules that any such complexity profile must follow: it never decreases, it starts at the complexity of the original string, it cannot grow too quickly, and it cannot grow too slowly if it has already reached a certain height.

While the paper successfully characterizes the possible values at any single distance and proves that the absolute minimum and maximum profiles are attainable, it leaves one significant question open. It remains unknown whether every possible curve that obeys the four basic rules can actually be realized by some string. The authors suspect that the answer is yes, but they have not yet found a way to prove that every intermediate shape is possible. They suggest that the techniques used to build the extreme examples might be the key to unlocking this final piece of the puzzle. The work provides a complete map of the boundaries and the corners of the territory, offering a clear understanding of the limits of complexity in the presence of noise, while pointing toward the unexplored terrain in the middle.

Technical Summary: Maximal Kolmogorov Complexity in a Hamming Ball

Problem Statement
This paper investigates the behavior of the maximal Kolmogorov complexity of strings within a Hamming ball of a given radius. Let $x$ be a binary string of length $n$ , and let $B_r(x)$ denote the Hamming ball of radius $r$ centered at $x$ . The authors define the complexity profile of $x$ as the function:
$g_x(r) = \max \{ C(y) : y \in B_r(x) \}$
where $C(y)$ denotes the plain Kolmogorov complexity.

While the minimal complexity within $B_r(x)$ (the algorithmic rate-distortion function) has been extensively studied and characterized by Vereshchagin and Vitányi, the maximal complexity $g_x(r)$ represents the opposite extreme. The paper asks: what values can $g_x(r)$ attain for a given $C(x)$ and $r$ ? Furthermore, what are the possible shapes of the function $r \mapsto g_x(r)$ ? The authors note that unlike the minimal case, the maximal complexity depends not only on the complexity of $x$ but also on the specific structure of $x$ .

Methodology
The paper employs a combination of combinatorial isoperimetric inequalities, probabilistic methods, and constructive arguments involving error-correcting codes and list decoding concepts.

Combinatorial Tools:
- Harper's Isoperimetric Inequality: Used to establish lower bounds on the size of neighborhoods. Specifically, among subsets of $\{0,1\}^n$ of a given cardinality, Hamming balls have the smallest neighborhoods. This is used to derive the lower bound for $g_x(r)$ .
- Log-Concavity of Ball Volumes: The sequence of Hamming ball volumes $V(a) = \sum_{i=0}^a \binom{n}{i}$ is shown to be log-concave, which is crucial for analyzing the growth rates of the complexity profile.
Constructive Techniques:
- Concentrators: The authors introduce a new combinatorial object called a $(k, r, l, \epsilon)$ -concentrator. This is a set of strings $C$ of size $\approx 2^k$ such that the union of Hamming balls of radius $r$ around $C$ has size $\approx 2^l$ , and this property is robust against the removal of a small fraction of $C$ .
- List Decoding Relaxation: To construct concentrators for intermediate parameters where disjoint error-correcting codes may not exist, the authors utilize a relaxation inspired by list decoding. They employ a probabilistic argument (Lemma 6) to show the existence of a family of centers with "small covering multiplicity" (every point in the space is covered by at most $O(n)$ balls).
Enumeration and Diagonalization:
- For the global profile results, particularly for achieving the maximal profile, the authors use an enumeration-based construction (Second proof of Theorem 9). This involves iteratively discarding candidate strings if they fail to contain a sufficiently complex string within a specific radius, ensuring the final constructed string satisfies the desired properties.

Key Contributions and Results

1. Pointwise Characterization (Theorem 1)
The paper characterizes the set of realizable triples $(k, r, l)$ , where $k=C(x)$ , $r$ is the radius, and $l=g_x(r)$ , up to an additive error of $O(\log n)$ .

Necessity: If $(k, r, l)$ is realizable, then:
$\log V(r_k + r) - O(\log n) \le l \le \min\{n, \log V(r_k) + \log V(r)\} + O(\log n)$
Here, $r_k$ is the radius of a Hamming ball with volume $\approx 2^k$ .
Sufficiency: For any $l$ within this interval, there exists a string $x$ with complexity $k' \approx k$ such that $g_x(r) \approx l$ .
Interpretation: The lower bound corresponds to the case where $x$ is a "random" string within a ball (minimizing the expansion of the ball), while the upper bound corresponds to $x$ being a codeword in an error-correcting code (maximizing the expansion). The construction interpolates between these extremes using the concentrator framework.

2. Global Profile Properties (Section 3)
The authors establish four fundamental properties that any complexity profile $g_x(r)$ must satisfy:

(P1) Non-decreasing.
(P2) $g_x(0) = C(x)$ and $g_x(r) \le n + O(1)$ .
(P3) Growth constraint: $g_x(r+a) \le g_x(r) + \log V(a) + O(\log n)$ .
(P4) Lower growth constraint: If $g_x(r)$ is sufficiently large, it must grow at least as fast as the volume of a ball shifted by $a$ .

3. Extremal Profiles (Theorems 8 and 9)
The paper proves that both the minimal and maximal functions consistent with properties (P1)–(P4) are attainable for every complexity level $k$ :

Minimal Profile: There exists a string $x$ such that $g_x(r) \approx \log V(r_k + r)$ for all $r$ . This represents the "slowest" possible growth.
Maximal Profile: There exists a string $x$ such that $g_x(r) \approx \min\{n, k + \log V(r)\}$ for all $r$ . This represents the "fastest" possible growth.

Significance and Open Questions
The paper provides a complete characterization of the possible values of $g_x(r)$ at a single radius $r$ and identifies the extremal behaviors of the complexity profile function. It highlights that the profile is not solely determined by $C(x)$ but depends on the specific string $x$ .

The authors explicitly state that a full characterization of all attainable intermediate profiles remains an open problem. While the minimal and maximal profiles are shown to be attainable, it is unknown whether every function satisfying the four necessary properties (P1)–(P4) corresponds to the profile of some string. The paper suggests that the enumeration techniques used in the proof of Theorem 9 may be a natural tool for addressing this open question. Additionally, the authors note that the $O(\log n)$ additive error in their bounds is not optimized and question whether this error term is optimal for the pointwise problem.

More like this