On the Constructive Dimension Spectrum of Polynomials

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 ${ℝ}^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 ${ℝ}^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.

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.

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.

We denote the binary alphabet by $\mathrm{\Sigma }=\{0,1\}$. The set of finite binary strings is denoted by ${\mathrm{\Sigma }}^{\ast }$ and the set of infinite binary sequences, by ${\mathrm{\Sigma }}^{\mathrm{\infty }}$. Empty string is denoted by $\lambda$. The length of a finite string $w\in {\mathrm{\Sigma }}^{\ast }$ is denoted by $\mathrm{\ell }(w)$.

We denote the set of rational numbers by $\mathbb{Q}$ and the set of reals by $ℝ$. In this work, we assume a binary encoding $e:\mathbb{Q}\to {\mathrm{\Sigma }}^{\ast }$ of the set of rationals.

We denote by $𝐚$ the tuple $a_0,a_1,\mathrm{\dots },a_d$, denoting the coefficients of a polynomial ${\sum }_{i=0}^d{a}_i{x}^i\in ℝ[x]$, such that $a_d\ne 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]).

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 the open neighborhood of radius $2^{-r}$ around $x$ is a valid description of $x$ to within precision $r\in \mathbb{N}$. The shortest description of a real point $x$ in ${ℝ}^n$ to within a precision $r\in \mathbb{N}$ is the shortest description of any rational point within the $2^{-r}$ neighborhood of $x$. Note that this may not necessarily be the rational obtained by truncating the binary expansion of $x$ to $r$ bits.

The conditional Kolmogorov complexity of $x\in {ℝ}^m$ given $y\in {ℝ}^n$ is defined using the Kolmogorov complexity of rational approximations to $x$ and $y$.

In this section, we state a few basic properties of Kolmogorov complexity, conditional Kolmogorov complexity and relative Kolmogorov complexity of reals pertinent for the remainder of the work.

The following approximate symmetry of information holds for pairs of reals.

The following lemma establishes a one-sided bound between the relativized Kolmogorov complexity and the conditional complexity, at a specific precision.

When the precision of either the conditioning variable or the conditioned variable changes, then the Kolmogorov complexity changes at most by an amount linear in the change in precision, uniformly in the points, as the following lemmas show.

The following lemma states similar bounds for conditional Kolmogorov complexity.

Let $A(x)={\sum }_{i=0}^d{a}_i{x}^i$. It is easy to establish an upper bound on the dimension of a point $(x,A(x))$, given approximations to the coefficients of $A$ and to $x$. We can give a lower bound on the dimension of the vector $(x,a_0,\mathrm{\dots },a_d)$ using symmetry of information. However, the Kolmogorov complexity of the point $(x,A(x))$ may be lower than that of $(x,a_0,\mathrm{\dots },a_d)$. The main task we accomplish is to establish lower bounds for the complexity of $(x,A(x))$ and consequently, its effective Hausdorff dimension.

The outline of the proof, adapting that of Lutz and Stull [19] is as follows. In Theorem 18, we show that if a different $d$-degree polynomial $B(x)={\sum }_{i=0}^d{b}_i{x}^i$ intersects $A$ at $x$, then either the coefficients of $B$ are close in $L_2$ norm to $A$, or the coefficients of $B$ must have very high Kolmogorov complexity. We introduce a technique of approximating roots when only approximations to the coefficients and rational approximations to points in the domain are available, adapting Sturm’s theory to this new setting. This lower bounds the Kolmogorov complexity of $(x,A(x))$.

Lemma 21 (Lemma 3.3 from [13]) ensures an oracle $D$ which limits the complexity of the coefficients of $A$. These results are then used to obtain the main technical lemma, Lemma 20, which yields the exact lower bound for the Kolmogorov complexity of $(x,A(x))$ at a specified precision $r$. The main lemma is then utilized to obtain a lower bound for the effective Hausdorff dimension of $(x,A(x))$.

In this subsection, we prove a lower bound for the Kolmogorov complexity of any approximation to the coefficients of a polynomial in terms of Kolmogorov complexity of the exact coefficients and the roots. This is crucial bound which leads to the main result (˜1.1). To this end, we provide an algorithm which lists approximations to all points where two given polynomials $B(x)={\sum }_{i=0}^d{b}_i{x}^i$ and $A(x)={\sum }_{i=0}^d{a}_i{x}^i$ intersect. This ensures that the complexity of any $x$ such that $A(x)=B(x)$ can be lower bounded using the complexities of $𝐚$ and $𝐛$. Since the coefficients and $x$ are real, this algorithm will take as input approximations to these values, and output approximations to the roots to any arbitrary precision.

The points of intersection of $A$ and $B$ are exactly the roots of the $d$-degree polynomial $C(x)=A(x)-B(x)$. Thus there are at most $d$ points of intersection between $A$ and $B$ on $ℝ$. The problem at hand therefore reduces to computing all possible real roots, with multiplicities, of a polynomial with real coefficients, up to arbitrary precision. We start by outlining the bisection method, followed by the importance of Sturm’s theorem, and then specify the algorithm.

In the special case of polynomials, the following method enumerates all the real roots of any univariate polynomial. Assume that we know the exact values of all the coefficients of a polynomial (in our case, we will have to work with approximations, and this makes the procedure much more technical). We start by getting a bound on the absolute value of any real root. This helps us to select an interval that is large enough to contain all the real roots of the polynomial. Recall that the roots of the polynomial are not guaranteed to be distinct - roots may have multiplicity greater than 1. In order to get all the real roots (with multiplicities), we use Sturm’s theorem to get the number of distinct roots (with arbitrary multiplicities) of the polynomial in any given interval. This allows us to improve the bisection method whenever there are repeated roots (of even multiplicities) in any interval.

For a degree $n$ polynomial $P$, we compute a sequence of polynomials, called the Sturm sequence of $P$ as follows (see, for example, Gerhard, von zur Gathen [22, Ch 2], or Yap [24, Ch 7]). The first 2 polynomials in the sequence are the polynomial itself, followed by its derivative - i.e $P_0=P$ and $P_1=P^{\prime }$. For $i\ge 2$, $P_i=P_{i-2}mod{P}_{i-1}$, where $mod$ is the remainder obtained when dividing the polynomial $P_{i-2}$ by $P_{i-1}$. Any Sturm sequence has at most $d+1$ elements, for a degree $d$ polynomial. Now, all the polynomials in the Sturm sequence obtained are evaluated at the end points of an interval, say $(a,b]$, which results in 2 sequences, each corresponding to an end point. We count the number of sign changes in each sequence, and denote them by $\sigma (a)$ and $\sigma (b)$ respectively.

If the end points happen to be the roots of the polynomial, we report them as is, and continue the search if required.

The following lemma bounds the roots of the polynomial $P$. We use this to determine the starting interval for our algorithm, ensuring that it is large enough to output all the real roots of $P$.

Using the above classical results, we now introduce the algorithm that upper bounds the number of roots in an interval from rational approximations of the coefficients. We introduce the preliminary algorithms for the Sturm sequence and the approximate sign counting, concluding with the algorithm that enumerates the roots.

The main subtlety we deal with is this: since the algorithms work with approximations, the exact signs of the polynomial value cannot be determined. This is because a small negative value is considered an acceptable input approximation to a small positive value. This leads to a conservative estimate of the sign changes, leading to a slightly longer list of possible roots. No root will be omitted at the given precision. However, since it is impossible to algorithmically determine whether a function is exactly equal to 0 or is a small positive or small negative value, points besides the roots may be counted if the precision is not sufficiently high. The algorithm outputs a list sufficiently short so that the Kolmogorov complexity of describing any root from the output list remains acceptably small.

The main step in our algorithm to find approximations to all real roots is the following sign computation. If the values of the polynomials are accurately known, then the sign determination is trivial. However, when the true value is nearly 0, it is difficult to determine its actual sign. We adopt a conservative upper bound for the actual number of sign changes.

Thus, we get the following upper bound on the output list of possible roots. This list is guaranteed to contain all the real roots of the polynomial to the given precision. However, since Lemma 15 is a conservative upper bound on the number of sign changes, there could be some values in the output list which are not the roots of the polynomial. This cannot be avoided in general. However, the output list of values is sufficiently small to control the number of bits used to describe any of its members. This upper bounds the Kolmogorov complexity of all the real roots of the polynomial.

Now, in order to bound the dimension of a point on the graph of a polynomial $P(x)={\sum }_{i=0}^d{a}_i{x}^i$, we try to bound the dimension of the coefficients of a polynomial of equal degree, denoted as $Q(x)={\sum }_{i=0}^d{b}_i{x}^i$, almost coinciding with $P$, intersecting it at $x$. The coefficients of this polynomial will provide sufficient information about the original polynomial, which in turn will help estimating $x$.

Recall the statement of the main theorem.

Our proof follows the strategy of the work by Lutz and Stull [19]. However, since we have to work with degree-$d$ polynomials, we deal with an increase in precision, as well as the presence of multiple roots. We indicate the strategy below, while simultaneously showing the similarity and emphasizing the differences from the work of Lutz and Stull [19]. Broadly, the steps involved in the proof are as follows.

First, note that any polynomial $P(x)$ as defined above is completely described by the list of its real coefficients $(a_0,\mathrm{\dots },a_d)$. We show that any other polynomial as characterized by the list of coefficients $(b_0,\mathrm{\dots },b_d)$ which coincides with $P(x)$ must either be very close to $(a_0,\mathrm{\dots },a_d)$ in Euclidean distance, or must have very high Kolmogorov complexity. The technical steps in the proof, however, are radically different from the work of Lutz and Stull - since a degree-$d$ polynomial can have $d$ real roots, hence the intersection point of the polynomials is not uniquely specified by the lists of coefficients. Moreover, in order to compute the intersection points of the two polynomials, we employ a modification of the bisection method to find all real roots, where we have to manage the error introduced in this approximation, and possible multiplicities of real roots.

Second, we show a lower bound for $K_r(b_0,\mathrm{\dots },b_d)$ in terms of $\Vert (a_0,\mathrm{\dots },a_d)-(b_0,\mathrm{\dots },b_d)\Vert$.

Then, as in Lutz and Stull [19], we use an oracle $D$ such that the following sequences of inequalities hold.

establishing that $K_r(x,P(x))$ is not much less than $K_r(x,a_0,\mathrm{\dots },a_d)$.

We use these results to prove the required bound.

This section deals with the polynomials, wherein

$\rho =\dim (𝐚)\le 1$. Following is the main theorem of the section.

The basic idea is to construct a real $x\in ℝ$ by alternating segments of a random point $y\in ℝ$ and approximations of the coefficients $𝐚$. This interleaving is done in a stage-by-stage manner, ensuring that $\dim (x)=s$. Simply adding random bits to $x$ is not helpful, because the information content in the point won’t have any control on the information content of the approximated function value. Instead, the constructed $x$ contains information about the graph of the function ${\sum }_{i=0}^d{a}_i{x}^i$.

We provide some insights into the case where the dimension spectrum of points on a polynomial could have diameter strictly greater than 1. This leads to answer to another question posed by Stull [17].