On the Constructive Dimension Spectrum of Polynomials
Prajval Koul, Satyadev Nandakumar · 2026
Read On the Constructive Dimension Spectrum of Polynomials by Prajval Koul, Satyadev Nandakumar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13868.txt.
Introduction
Koul and Nandakumar study dimension spectra of polynomial curves, a topic in fractal shape theory. They adapt old real root-find methods to this setting. The key result: each polynomial curve has a spectrum with at least two points. That settles a query Stull had posed. The same result yields polynomials with width past one, settling a second Stull query.
Catalog record
| CREATOR | Prajval Koul, Satyadev Nandakumar |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71171 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.13868
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the Constructive Dimension Spectrum of Polynomials Prajval Koul, Satyadev Nandakumar Abstract Recently, Stull [ 18 ] , [ 17 ] resolved a long-standing open problem posed by Lutz, on whether the set of effective Hausdorff dimensions of points on a straight line in ℝ 2 \mathbb{R}^{2} - the effective dimension spectrum of the line - contains a unit interval. This question is related to problems in classical fractal geometry like the Kakeya conjecture and Furstenberg sets. Stull posed an open question on the dimension spectra of polynomial curves. For the first result, with new techniques which adapt the theory of classical real root-finding of polynomials to the current setting, we show that the dimension spectra of every polynomial curve contains at least two points. This answers an open question posed by Stull [ 18 ] , [ 17 ] . We use the main result to construct a class of polynomials which have width strictly greater than 1, answering a second problem stated in [ 18 ] , [ 17 ] . Stull [ 18 ] resolved the dimension spectrum conjecture for planar lines, showing that it contains a unit interval. For the second result, we resolve the conjecture for a subfamily of polynomials whose coefficients form a ”low” dimension point in ℝ d + 1 \mathbb{R}^{d+1} . Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, India. and https://prajvalkoul.github.io/ [email protected]://orcid.org/0000-0002-8879-8330 Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur, Uttar Pradesh, India. and https://www.cse.iitk.ac.in/users/satyadev/ [email protected]://orcid.org/0000-0002-0214-0598 ccs Theory of computation. keywords Kolmogorov Complexity, Dimension, Polynomials. † † runningtitle: On the Constructive Dimension Spectrum of Polynomials † † runningauthor: P. Koul and S. Nandakumar † † copyright: Prajval Koul and Satyadev Nandakumar † † editors: Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis † † event-title: 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) † † event-shorttitle: ICALP 2026 † † event-acronym: ICALP † † year: 2026 † † event-date: July 7–10, 2026 † † event-location: Royal Holloway, University of London, Egham, United Kingdom † † series-volume: 374 † † articleno: 180 1 Introduction The theory of effective Hausdorff dimension was introduced by J. Lutz in 2000 [ 5 ] , [ 7 ] initially over the Cantor Space of infinite binary sequences as a tool to study the relationships between complexity classes [ 6 ] . Subsequent works have adapted the theory to study the effective Hausdorff dimensions and points in Euclidean space and in general metric spaces ( [ 10 ] , [ 12 ] , [ 21 ] , [ 8 ] , [ 14 ] , [ 19 ] , [ 17 ] , [ 9 ] , [ 15 ] ). A major highlight of this theory is the “point-to-set principle”, allowing classical Hausdorff dimensions to be derived using effective pointwise arguments. A central question arising in this setting concerns the effective dimension spectrum of sets in the Euclidean plane: what values are attained by the effective dimensions of points inside sets in \mathbb{R}^{2} ? In a recent work, Stull [ 17 ] , extending an earlier work by N. Lutz and Stull [ 13 ] , settled a long-standing conjecture of J. Lutz showing that the dimension spectrum of every line in \mathbb{R}^{2} contains a unit interval. Stull [ 17 ] proposes extending the study to the dimensions of points along polynomial curves. In this work, we resolve Stull’s problem for every univariate polynomial with real coefficients. We show that its dimension spectrum of every polynomial contains at least two points. Further, we show that the dimension spectrum of every polynomial contains unit-length interval when the coefficients have low dimension. Our first main result is the following. Theorem 1.1 . For (a_{0},\dots,a_{d})\in\mathbb{R}^{d+1} , x\in\mathbb{R} , we have \displaystyle{\mathrm{dim}}\left(x,\sum_{i=0}^{d}a_{i}x^{i}\right)\geq{\mathrm{dim}}\left(x\mid a_{0},\dots,a_{d}\right)+\min\left\{{\mathrm{dim}}\left(a_{0},\dots,a_{d}\right),{\mathrm{dim}}^{a_{0},\dots,a_{d}}(x)\right\}. (1) The second main theorem for this paper establishes that the dimension spectrum of polynomials with coefficients with effective dimension at most 1, contains a unit-length interval. Theorem 1.2 . Let \sum_{i=0}^{d}a_{i}x^{i}\in\mathbb{R}[x] be a degree d polynomial with {\mathrm{dim}}(\mathbf{a})\leq 1 . Then for every s\in[0,1] , there is a point x\in\mathbb{R} such that {\mathrm{dim}}\left(x,\sum_{i=0}^{d}a_{i}x^{i}\right)=s+{\mathrm{dim}}(\mathbf{a}) . The proofs adapt the techniques in N. Lutz and Stull [ 13 ] to polynomials. We adapt the classical root-finding methods, namely, the bisection method, together with methods which count real roots from Sturm’s theory [ 20 ] (see for example, von zur Gathen and Gerhard [ 22 ] and Yap [ 24 ] ) to establish our results. Due to the fact that the coefficients can be arbitrary real numbers, we have to adapt these techniques to form short descriptions of the roots of these functions. These versions may be of broader interest. The proof of the second result, building on the first, involves encoding the coefficients of a given polynomial in such a way so as to control the dimension of the corresponding point. We conclude by discussing the implications of our result - in particular, that dimension level sets - sets consisting of points of the same effective dimension - cannot contain polynomials. 2 Prerequisites We denote the binary alphabet by \Sigma=\{0,1\} . The set of finite binary strings is denoted by \Sigma^{*} and the set of infinite binary sequences, by \Sigma^{\infty} . Empty string is denoted by \lambda . The length of a finite string w\in\Sigma^{*} is denoted by \ell(w) . We denote the set of rational numbers by \mathbb{Q} and the set of reals by \mathbb{R} . In this work, we assume a binary encoding e:\mathbb{Q}\to\Sigma^{*} of the set of rationals. We denote by \mathbf{a} the tuple a_{0},a_{1},\ldots,a_{d} , denoting the coefficients of a polynomial \sum_{i=0}^{d}a_{i}x^{i}\in\mathbb{R}[x] , such that a_{d}\neq 0 . We now introduce the basic notions in Kolmogorov complexity (see, for example, Downey and Hirschfeldt [ 3 ] , Nies [ 16 ] or Li and Vitányi [ 4 ] ). Definition 1 (Kolmogorov Complexity of binary strings) . For each pair of strings v,w\in\{0,1\}^{*} , the Kolmogorov complexity of v given w is defined as K\left(v|w\right) = \min_{\pi\in\{0,1\}^{*}} \left\{\ell(\pi):U\left(\pi,w\right)=v\right\} , where U is a fixed universal (prefix) Turing machine. The Kolmogorov complexity of v , denoted by K(v) , is K(v\mid\lambda) . Definition 2 (Kolmogorov Complexity of binary strings relative to an oracle) . For each pair of strings v,w\in\{0,1\}^{*} , the Kolmogorov complexity of v given w relative to an oracle A\subseteq\mathbb{N} is defined as K^{A}\left(v|w\right) = \min_{\pi\in\{0,1\}^{*}}\left\{\ell(\pi):U^{A}\left(\pi,w\right)=v\right\} , where U is a fixed universal (prefix) Turing machine with oracle access to A . In recent works ( [ 10 ] , [ 12 ] , [ 21 ] , [ 8 ] , [ 14 ] , [ 19 ] , [ 17 ] , [ 9 ] ) the theory of Kolmogorov complexity of binary strings has been adapted to the study of Kolmogorov complexity of reals. Instead of defining the complexity in terms of the truncated binary expansions of the real (which has known issues such as addition of reals being uncomputable - see Weihrauch [ 23 ] for a discussion), the approach defines the complexity of a real in terms of the complexities of its rational approximations. The intuition behind the following definition is this: any rational q within