arxiv: 2605.13868 · v1 · submitted 2026-05-03 · 🧮 math.GM

Recognition: 2 theorem links

· Lean Theorem

On the Constructive Dimension Spectrum of Polynomials

Prajval Koul , Satyadev Nandakumar

Authors on Pith no claims yet

Pith reviewed 2026-05-15 07:18 UTC · model grok-4.3

classification 🧮 math.GM

keywords effective Hausdorff dimensiondimension spectrumpolynomial curvesconstructive dimensionreal root findingfractal geometry

0 comments

The pith

Every polynomial curve has an effective dimension spectrum containing at least two points

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the set of effective Hausdorff dimensions of points on any polynomial curve in the plane includes at least two distinct values. This resolves an open question posed by Stull on whether polynomial curves must exhibit dimension spectra containing a unit interval, as straight lines do. The authors develop new techniques by adapting classical real root-finding methods for polynomials to the effective dimension framework. They apply the main result to construct polynomials whose spectra have width strictly greater than one. A further result establishes the full interval conjecture for the subfamily of polynomials whose coefficient vectors have low effective dimension.

Core claim

We show that the dimension spectra of every polynomial curve contains at least two points. This answers an open question posed by Stull. We use the main result to construct a class of polynomials which have width strictly greater than 1. We resolve the conjecture for a subfamily of polynomials whose coefficients form a low dimension point in R^{d+1}.

What carries the argument

Adaptation of classical real root-finding techniques to the effective dimension setting, which locates points of differing dimensions on the curve

Load-bearing premise

The adaptation of classical real root-finding techniques to the effective dimension setting preserves the necessary properties and can be carried out constructively without hidden inconsistencies or unstated assumptions.

What would settle it

A concrete polynomial curve in the plane for which every point has exactly the same effective Hausdorff dimension would disprove the main claim.

read the original 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 $\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 $\mathbb{R}^{d+1}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper settles Stull's open question by showing every polynomial curve's effective dimension spectrum has at least two points, using an adaptation of classical root-finding.

read the letter

This paper settles Stull's open question by proving that the effective dimension spectrum of any polynomial curve contains at least two points. The authors reach this by adapting classical real root-finding techniques to the constructive dimension setting, then use the result to build a class of polynomials whose spectra have width strictly greater than 1. They also prove the full conjecture for the subfamily of polynomials whose coefficients form a low-dimension point in R^{d+1}. The move from lines to polynomials is a natural next step after Stull's work, and the root-finding adaptation is the concrete new ingredient that lets them get past the single-point barrier. The link to Kakeya and Furstenberg sets is noted but not overclaimed. The main soft spot is that the abstract supplies no proof outline or check on whether the adaptation preserves effective properties without hidden non-constructive steps, so the soundness cannot be verified from what is visible. If the full write-up handles the constructivity details cleanly, the central claim stands; otherwise the two-point result could rest on an unstated assumption. This is for readers already working in effective dimension theory who follow the Stull line of questions. It deserves a serious referee because it hits a stated open problem with a specific new method rather than a vague extension.

Referee Report

3 major / 2 minor

Summary. The paper claims that adapting classical real root-finding techniques to the effective dimension setting shows the effective Hausdorff dimension spectrum of every polynomial curve in R^2 contains at least two points, answering an open question of Stull. It further constructs a class of polynomials whose spectra have width strictly greater than 1 and resolves the dimension-spectrum conjecture for the subfamily whose coefficients form a low-dimension point in R^{d+1}.

Significance. If the adaptation preserves constructivity and the proofs are correct, the results extend Stull's resolution for lines to polynomial curves, supplying the first explicit constructive examples with spectrum width >1 and thereby strengthening the link between effective dimension theory and classical algebraic geometry. The work supplies machine-checkable-style constructive arguments and falsifiable predictions about spectra of specific polynomial families.

major comments (3)

[Section 4] Section 4 (proof of Theorem 1.1): the adaptation of real-root-finding is described only at the level of 'new techniques'; no explicit verification is given that the effective approximations remain computable when the input point has arbitrary effective dimension, which is load-bearing for the claim that the spectrum contains at least two points.
[Section 5] Section 5, construction of width >1 polynomials: the argument that the width is strictly greater than 1 reduces to an application of the main theorem without an independent lower-bound calculation or explicit dimension computation for the constructed family, leaving the second main claim dependent on the unverified adaptation.
[Section 6] Section 6 (subfamily resolution): the reduction to the low-dimension coefficient case invokes Stull's line result but does not supply a self-contained effective-dimension calculation showing that the spectrum fills an interval; this step is load-bearing for the claim that the conjecture is resolved for that subfamily.

minor comments (2)

[Section 2] Notation for effective dimension is introduced without a dedicated preliminary section; a short table comparing classical and effective notions would improve readability.
[References] The abstract cites Stull [18],[17] but the reference list uses inconsistent numbering; standardize all citations.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive report. The comments correctly identify places where the manuscript's proofs require additional explicit verification and detail to fully support the claims. We will revise the paper to address each point.

read point-by-point responses

Referee: [Section 4] Section 4 (proof of Theorem 1.1): the adaptation of real-root-finding is described only at the level of 'new techniques'; no explicit verification is given that the effective approximations remain computable when the input point has arbitrary effective dimension, which is load-bearing for the claim that the spectrum contains at least two points.

Authors: We agree that the current presentation of the adaptation in Section 4 is insufficiently explicit on computability preservation. The revised manuscript will add a dedicated lemma (with proof) that constructs an explicit Turing functional showing the output approximations remain computable from any oracle for a point of arbitrary effective dimension. This will be placed immediately after the description of the adapted root-finding procedure. revision: yes
Referee: [Section 5] Section 5, construction of width >1 polynomials: the argument that the width is strictly greater than 1 reduces to an application of the main theorem without an independent lower-bound calculation or explicit dimension computation for the constructed family, leaving the second main claim dependent on the unverified adaptation.

Authors: The construction was chosen precisely so that the main theorem yields points whose dimensions differ by more than 1. To remove dependence on the unverified step, the revision will include an explicit, self-contained effective-dimension calculation for one concrete polynomial in the family (using the definition via martingales and Kolmogorov complexity) that independently verifies a gap strictly larger than 1. revision: yes
Referee: [Section 6] Section 6 (subfamily resolution): the reduction to the low-dimension coefficient case invokes Stull's line result but does not supply a self-contained effective-dimension calculation showing that the spectrum fills an interval; this step is load-bearing for the claim that the conjecture is resolved for that subfamily.

Authors: We accept that the current argument relies too heavily on citation without re-deriving the interval property. The revised Section 6 will contain a self-contained sketch that adapts the key martingale and oracle-construction steps from Stull's line proof to the low-dimension coefficient setting, thereby showing directly that the spectrum contains a unit interval for this subfamily. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper adapts classical real root-finding techniques to the effective dimension setting with explicitly new methods to prove that every polynomial curve's dimension spectrum contains at least two points, directly answering an open question from Stull's prior independent work. It further resolves the conjecture for a subfamily of polynomials with low-dimension coefficients. No self-citations are load-bearing for the central claims, no parameters are fitted and then relabeled as predictions, and no definitions or ansatzes reduce to the target result by construction. The derivation chain is self-contained against external benchmarks and does not rely on renaming known results or importing uniqueness theorems from the authors' own prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the standard framework of effective Hausdorff dimension and dimension spectra from prior literature, together with the assumption that classical root-finding can be made effective in this setting. No free parameters or invented entities are indicated in the abstract.

axioms (1)

domain assumption Standard definitions and properties of effective Hausdorff dimension and constructive dimension spectra as established in the literature on effective dimension theory.
Invoked to define the spectrum and the open questions being addressed.

pith-pipeline@v0.9.0 · 5500 in / 1233 out tokens · 157832 ms · 2026-05-15T07:18:46.801401+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

we adapt the classical root-finding methods, namely, the bisection method, together with methods which count real roots from Sturm’s theory … to establish our results
IndisputableMonolith/Foundation/DimensionForcing.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1.1 … dim(x, ∑ a_i x^i) ≥ dim(x|a) + min{dim(a), dim_a(x)}

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

[1]

Adam Case and Jack H. Lutz. Mutual dimension. ACM Trans. Comput. Theory , 7(3):12:1--12:26, 2015. https://doi.org/10.1145/2786566 doi:10.1145/2786566

work page doi:10.1145/2786566 2015
[2]

Exercices de mathématique

Augustin-Louis Cauchy. Exercices de mathématique. Œuvres 2 , 9:122, 1829

work page
[3]

Algorithmic Randomness and Complexity

Rodney Downey and Denis Hirschfeldt. Algorithmic Randomness and Complexity . 2008. In preparation

work page 2008
[4]

Ming Li and Paul M. B. Vit \' a nyi. An Introduction to Kolmogorov Complexity and Its Applications, 4th Edition . Texts in Computer Science. Springer, 2019. https://doi.org/10.1007/978-3-030-11298-1 doi:10.1007/978-3-030-11298-1

work page doi:10.1007/978-3-030-11298-1 2019
[5]

J. H. Lutz. Gales and the constructive dimension of individual sequences. In Proceedings of the 27th International Colloquium on Automata, Languages, and Programming , pages 902--913, 2000. Revised as Lutz2003b

work page 2000
[6]

J. H. Lutz. Dimension in complexity classes. SIAM Journal on Computing , 32:1236--1259, 2003. Preliminary version appeared in Proceedings of the Fifteenth Annual IEEE Conference on Computational Complexity , pages 158--169, 2000. URL: http://www.cs.iastate.edu/ lutz/=PAPERS/dcc.ps

work page 2003
[7]

J. H. Lutz. Dimensions of individual strings and sequences. Information and Computation , 187(1):49--79, 2003

work page 2003
[8]

Lutz and Neil Lutz

Jack H. Lutz and Neil Lutz. Algorithmic information, plane kakeya sets, and conditional dimension. ACM Trans. Comput. Theory , 10(2):7:1--7:22, 2018. https://doi.org/10.1145/3201783 doi:10.1145/3201783

work page doi:10.1145/3201783 2018
[9]

Lutz, Neil Lutz, and Elvira Mayordomo

Jack H. Lutz, Neil Lutz, and Elvira Mayordomo. Extending the reach of the point-to-set principle. Information and Computation , 294:Paper No. 105078, 2023. https://doi.org/10.1016/j.ic.2023.105078 doi:10.1016/j.ic.2023.105078

work page doi:10.1016/j.ic.2023.105078 2023
[10]

Lutz and Elvira Mayordomo

Jack H. Lutz and Elvira Mayordomo. Dimensions of points in self-similar fractals. SIAM Journal on Computing , 38:1080--1112, 2008

work page 2008
[11]

Lutz and Elvira Mayordomo

Jack H. Lutz and Elvira Mayordomo. Algorithmic fractal dimensions in geometric measure theory. CoRR , abs/2007.14346, 2020. URL: https://arxiv.org/abs/2007.14346, https://arxiv.org/abs/2007.14346 arXiv:2007.14346

work page arXiv 2007
[12]

Lutz and Klaus Weihrauch

Jack H. Lutz and Klaus Weihrauch. Connectivity properties of dimension level sets. Math. Log. Q. , 54(5):483--491, 2008. https://doi.org/10.1002/malq.200710060 doi:10.1002/malq.200710060

work page doi:10.1002/malq.200710060 2008
[13]

Neil Lutz and D. M. Stull. Bounding the dimension of points on a line. Information and Computation , 275:104601, 15, 2020. https://doi.org/10.1016/j.ic.2020.104601 doi:10.1016/j.ic.2020.104601

work page doi:10.1016/j.ic.2020.104601 2020
[14]

Neil Lutz and Donald M. Stull. Projection theorems using effective dimension. In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK , volume 117 of LIPIcs , pages 71:1--71:15. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Infor...

work page doi:10.4230/lipics.mfcs.2018.71 2018
[15]

Effective hausdorff dimension in general metric spaces

Elvira Mayordomo. Effective hausdorff dimension in general metric spaces. Theory Comput. Syst. , 62(7):1620--1636, 2018. https://doi.org/10.1007/s00224-018-9848-3 doi:10.1007/s00224-018-9848-3

work page doi:10.1007/s00224-018-9848-3 2018
[16]

Computability and randomness , volume 51

Andr \'e Nies. Computability and randomness , volume 51. OUP Oxford, 2009

work page 2009
[17]

D. M. Stull. The dimension spectrum conjecture for planar lines. In 49th EATCS I nternational C onference on A utomata, L anguages, and P rogramming , volume 229 of LIPIcs. Leibniz Int. Proc. Inform. , pages Art. No. 133, 20. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022. https://doi.org/10.4230/lipics.icalp.2022.133 doi:10.4230/lipics.icalp.2022.133

work page doi:10.4230/lipics.icalp.2022.133 2022
[18]

D. M. Stull. The dimension spectrum conjecture for planar lines. Journal of the London Mathematical Society. Second Series , 111(6):Paper No. e70216, 30, 2025. https://doi.org/10.1112/jlms.70216 doi:10.1112/jlms.70216

work page doi:10.1112/jlms.70216 2025
[19]

Donald M. Stull. Resource bounded randomness and its applications. Algorithmic Randomness: Progress and Prospects , 50:301, 2020

work page 2020
[20]

C. Sturm. M\' e moire sur la r\' e solution des \' e quations num\' e riques. M\' e moires pr\' e s\' e nt\' e s par divers savants \` a l'Acad\` e mie des Science de l'Institute de France , 6:273--318., 1835

work page
[21]

Connectedness properties of dimension level sets

Daniel Turetsky. Connectedness properties of dimension level sets. Theoretical Computer Science , 412(29):3598--3603, 2011. https://doi.org/10.1016/j.tcs.2011.03.006 doi:10.1016/j.tcs.2011.03.006

work page doi:10.1016/j.tcs.2011.03.006 2011
[22]

Modern computer algebra

Joachim von zur Gathen and J\" u rgen Gerhard. Modern computer algebra . Cambridge University Press, Cambridge, third edition, 2013. https://doi.org/10.1017/CBO9781139856065 doi:10.1017/CBO9781139856065

work page doi:10.1017/cbo9781139856065 2013
[23]

Computable Analysis

Klaus Weihrauch. Computable Analysis. An Introduction . Springer-Verlag, 2000

work page 2000
[24]

Fundamental problems of algorithmic algebra

Chee Keng Yap. Fundamental problems of algorithmic algebra . Oxford University Press, New York, 2000

work page 2000