🔢 mathematics

On the Constructive Dimension Spectrum of Polynomials

This paper resolves Stull's open questions on polynomial dimension spectra by proving that every polynomial curve contains at least two effective Hausdorff dimensions and by confirming the dimension spectrum conjecture for a subfamily of polynomials with low-dimensional coefficients.

Original authors: Prajval Koul, Satyadev Nandakumar

Published 2026-05-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Prajval Koul, Satyadev Nandakumar

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 you are standing in a vast, infinite library. This library doesn't contain books, but rather points in space. Each point has a secret "complexity score" (called its dimension), which measures how much information is needed to describe it precisely.

Some points are simple and easy to describe (low complexity). Others are chaotic and require a massive amount of data to pin down (high complexity).

The paper you are asking about is a detective story about what happens when we draw polynomial curves (the smooth, curvy lines you might remember from high school algebra, like $y = x^2$ or $y = x^3 + 5x$ ) through this library. The authors, Prajval Koul and Satyadev Nandakumar, wanted to answer two big questions about the "complexity scores" of the points sitting on these curves.

Here is the breakdown of their discovery, using simple analogies.

The Big Picture: The "Complexity Spectrum"

Think of a polynomial curve as a long, winding road. If you stop at any point on this road, that point has a specific complexity score. If you collect the scores of every point on the road, you get a list of numbers. This list is called the Dimension Spectrum.

The Old Mystery: For straight lines (like $y = 2x + 1$ ), a mathematician named Stull recently proved that the list of complexity scores isn't just a few random numbers. It's a solid, unbroken block of numbers (an interval). If the line has points with complexity 0.5 and 1.5, it must also have points with complexity 0.6, 0.7, 0.8, and so on, all the way through.
The New Question: Does this "solid block" rule apply to curvy polynomial roads, too? Or are they weird and broken?

Discovery #1: Even the Curvy Roads Have "At Least Two" Points

The first major finding is a bit of a relief, but also a bit of a tease.

The authors proved that every polynomial curve (no matter how twisty) has a dimension spectrum that contains at least two distinct points.

The Analogy:
Imagine you are trying to find a "complexity" for a rollercoaster. Before this paper, we didn't even know if the rollercoaster had any points with a measurable complexity score, or if they were all the same.
The authors used a clever trick involving Sturm's Theorem (an old-school math method for counting roots) and bisection (cutting a problem in half repeatedly). They showed that no matter how you draw the curve, you can always find at least two different types of points on it:

Points that are "simple" relative to the curve's shape.
Points that are "complex" relative to the curve's shape.

So, the spectrum isn't empty, and it isn't just a single dot. It has at least two distinct values. This answers a question Stull had been asking for a while.

Discovery #2: The "Low-Info" Curves Are Perfectly Smooth

The second, more exciting result happens when the polynomial itself is "simple."

Imagine the coefficients of the polynomial (the numbers $a, b, c$ in $ax^2 + bx + c$ ) are the "blueprint" of the road. If this blueprint is simple (mathematically speaking, if the blueprint has a low dimension, specifically $\le 1$ ), then the road behaves beautifully.

The Finding:
If the blueprint is simple, the dimension spectrum of the curve is a perfect, solid block of numbers (a unit interval). It contains every complexity score between the blueprint's complexity and that number plus 1.

The Analogy:
Think of the blueprint as a recipe.

If the recipe is a simple list of ingredients (low complexity), the resulting cake (the curve) has a "flavor spectrum" that is continuous. You can taste every shade of flavor from the base ingredient up to the maximum.
The authors proved that for these "simple recipes," you can find a point on the curve for every single possible complexity score in that range. There are no gaps.

How did they do this?
They built a specific point $x$ by weaving two things together like a braid:

Randomness: They took a chunk of pure, chaotic noise (random bits).
The Blueprint: They took chunks of the polynomial's coefficients.
By alternating these chunks in a very specific pattern, they created a point $x$ that has exactly the right amount of "chaos" (complexity) to land on any specific spot in the spectrum they wanted.

Discovery #3: Some Curves Are "Wide"

Finally, the authors looked at what happens if the blueprint is very complex (dimension > 1).

They showed that for certain complex polynomials, the range of complexity scores on the curve can be wider than 1.

The Analogy: If a straight line has a "width" of 1 (it covers a range of 1 unit of complexity), some of these curvy polynomials have a width of 2 or more. They contain points that are incredibly simple and points that are incredibly complex, with a huge gap in between that is also filled with points.

Summary of the "Why"

The paper is purely theoretical math. It doesn't talk about building bridges or curing diseases. It is about understanding the fundamental structure of information and geometry.

The Problem: Can we predict the variety of complexity found on a mathematical curve?
The Solution:
1. Yes, there is always at least a little variety (at least two points).
2. If the curve's definition is simple, the variety is perfect and continuous (a solid block).
3. If the curve's definition is complex, the variety can be huge (wider than 1).

The authors used tools from Kolmogorov Complexity (measuring how hard it is to describe something) and adapted old root-finding algorithms to prove that these mathematical roads are far more structured and predictable than we might have guessed. They essentially mapped the "terrain" of information on polynomial curves.

Technical Summary: On the Constructive Dimension Spectrum of Polynomials

Problem Statement
This paper addresses open questions regarding the effective Hausdorff dimension spectra of polynomial curves in $\mathbb{R}^2$ . While Stull [17, 18] recently resolved the dimension spectrum conjecture for straight lines in the plane—proving that the set of effective dimensions of points on any line contains a unit interval—the behavior of polynomial curves remained an open problem. Specifically, the authors investigate whether the dimension spectrum of a polynomial curve $P(x) = \sum_{i=0}^d a_i x^i$ contains a unit interval, and more generally, what the structure of the set $\{ \dim(x, P(x)) : x \in \mathbb{R} \}$ is, given the coefficients $a = (a_0, \dots, a_d)$ .

Methodology
The authors adapt techniques from classical real root-finding and algorithmic information theory to the setting of effective dimension. The methodology relies on three primary pillars:

Adaptation of Root-Finding to Approximations: Since coefficients and points are arbitrary real numbers, the authors cannot rely on exact arithmetic. They adapt the bisection method and Sturm's theory (specifically Sturm sequences) to handle rational approximations of coefficients. They develop algorithms (e.g., RootEnum, MaxSignChange) that enumerate potential roots of the difference polynomial $C(x) = A(x) - B(x)$ with guaranteed precision, accounting for the inability to determine exact signs of values near zero. This allows them to bound the Kolmogorov complexity of intersection points.
Symmetry of Information and Oracle Techniques: Building on the "point-to-set principle" and the work of Lutz and Stull [13, 19], the proofs utilize conditional Kolmogorov complexity and relativized dimensions. The authors employ oracles (specifically Lemma 21) to control the complexity of the coefficients, ensuring that the complexity of the intersection point $x$ and the polynomial value $P(x)$ can be bounded in terms of the complexity of the coefficients and the relative dimension of $x$ .
Interleaved Constructions: For the second main result, the authors construct specific points $x$ by interleaving segments of a Martin-Löf random sequence $y$ with rational approximations of the coefficients $a$ . This construction is designed to precisely control the effective dimension of the point $x$ and the resulting point $(x, P(x))$ on the graph.

Key Contributions and Results

Theorem 1.1 (Lower Bound for General Polynomials): The paper establishes a lower bound for the effective dimension of a point on the graph of any univariate polynomial with real coefficients. For coefficients $a = (a_0, \dots, a_d)$ and a point $x \in \mathbb{R}$ :
$\dim\left(x, \sum_{i=0}^d a_i x^i\right) \ge \dim(x | a) + \min\{ \dim(a), \dim_a(x) \}$
This result answers an open question posed by Stull [17, 18], proving that the dimension spectrum of every polynomial curve contains at least two points. Furthermore, it implies that for almost every $x$ , the dimension is $1 + \min\{\dim(a), 1\}$ .
Theorem 1.2 (Unit Interval Spectrum for Low-Dimensional Coefficients): The authors resolve the dimension spectrum conjecture for a specific subfamily of polynomials where the coefficients have an effective dimension of at most 1 ( $\dim(a) \le 1$ ). They prove that for any $s \in [0, 1]$ , there exists a point $x$ such that:
$\dim\left(x, \sum_{i=0}^d a_i x^i\right) = s + \dim(a)$
Consequently, the dimension spectrum of such polynomials contains a unit-length interval.
Width of Dimension Spectra: The paper demonstrates that the dimension spectrum of polynomial curves can have a diameter strictly greater than 1. By constructing polynomials where the constant term $a_0$ has a specific dimension $q$ and the remaining coefficients are Martin-Löf random, the authors show that the spectrum can range from $q$ to $2$ (or higher depending on the setup), answering a second question from Stull regarding the "width" of these spectra.

Significance and Claims
The paper claims to extend the understanding of effective dimension from linear structures (lines) to non-linear algebraic structures (polynomials). The primary significance lies in:

Generalizing Stull's Results: Moving from the specific case of lines to arbitrary degree- $d$ polynomials, showing that while the spectrum is not always a unit interval for all polynomials, it is guaranteed to contain at least two points and contains a unit interval for coefficients of low dimension.
Technical Innovation: The adaptation of Sturm's theorem and bisection methods to the realm of Kolmogorov complexity and effective dimension provides a new toolkit for analyzing the complexity of roots of polynomials with real coefficients. The authors note that the algorithms for root enumeration under approximation (Remark 17) may be of independent interest.
Structural Insights: The results imply that dimension level sets (sets of points with the same effective dimension) cannot contain entire polynomial curves, as the dimension varies along the curve.

The authors conclude by noting that the methods do not yet extend to arbitrary continuous curves and pose the open problem of whether the dimension spectrum conjecture holds for high-dimensional polynomials or if there exist trigonometric polynomials with singleton dimension spectra.

The Big Picture: The "Complexity Spectrum"

Discovery #1: Even the Curvy Roads Have "At Least Two" Points

Discovery #2: The "Low-Info" Curves Are Perfectly Smooth

Discovery #3: Some Curves Are "Wide"

Summary of the "Why"

More like this