DROPS

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2026.183

On the Constructive Dimension Spectrum of Polynomials

Authors: Prajval Koul and Satyadev Nandakumar

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

Recently, Stull [Stull, 2025], [Stull, 2022] resolved a long-standing open problem posed by Lutz, on whether the set of effective Hausdorff dimensions of points on a straight line in ℝ² - 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 [Stull, 2025], [Stull, 2022]. We use the main result to construct a class of polynomials which have width strictly greater than 1, answering a second problem stated in [Stull, 2025], [Stull, 2022]. Stull [Stull, 2025] 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}.

Cite as

Prajval Koul and Satyadev Nandakumar. On the Constructive Dimension Spectrum of Polynomials. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 183:1-183:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{koul_et_al:LIPIcs.ICALP.2026.183,
  author =	{Koul, Prajval and Nandakumar, Satyadev},
  title =	{{On the Constructive Dimension Spectrum of Polynomials}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{183:1--183:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.183},
  URN =		{urn:nbn:de:0030-drops-265717},
  doi =		{10.4230/LIPIcs.ICALP.2026.183},
  annote =	{Keywords: Kolmogorov Complexity, Dimension, Polynomials}
}

Document

DOI: 10.4230/LIPIcs.STACS.2026.61

On Effective Banach-Mazur Games and an Application to the Poincaré Recurrence Theorem for Category

Authors: Prajval Koul and Satyadev Nandakumar

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

The classical Banach-Mazur game characterizes sets of first category in a topological space. In this work, we show that an effectivized version of the game yields a characterization of sets of effective first category. Using this, we provide a game-theoretic proof of an effective theorem in dynamical systems, namely the category version of Poincaré Recurrence. The Poincaré Recurrence Theorem for category states that for a homeomorphism without open wandering sets, the set of non recurrent points forms a first category (meager) set. As an application of the effectivization of the Banach-Mazur game, we show that such a result holds true in effective settings as well.

Cite as

Prajval Koul and Satyadev Nandakumar. On Effective Banach-Mazur Games and an Application to the Poincaré Recurrence Theorem for Category. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 61:1-61:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{koul_et_al:LIPIcs.STACS.2026.61,
  author =	{Koul, Prajval and Nandakumar, Satyadev},
  title =	{{On Effective Banach-Mazur Games and an Application to the Poincar\'{e} Recurrence Theorem for Category}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{61:1--61:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.61},
  URN =		{urn:nbn:de:0030-drops-255509},
  doi =		{10.4230/LIPIcs.STACS.2026.61},
  annote =	{Keywords: Recurrence, Topology, Category, Computable Analysis, Computable Toplogy, Dynamical Systems}
}

Search Results

Documents authored by Koul, Prajval

On the Constructive Dimension Spectrum of Polynomials

Abstract

Cite as

On Effective Banach-Mazur Games and an Application to the Poincaré Recurrence Theorem for Category

Abstract

Cite as

Thanks for your feedback!

Could not send message