DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.65

On Positivity of Exponential-Trigonometric Polynomials and Irrationality Exponents

Authors: Pieter Collins, Bernard Hanzon, and Eike Neumann

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract

We establish Diophantine hardness results for the decidability of the Positivity Problem for exponential-trigonometric polynomials over computable discrete subfields of the real numbers, and for related questions. We show that any algorithm for deciding either non-negativity, eventual non-negativity, the existence of a zero, or the existence of infinitely many zeros of exponential-trigonometric polynomials over a computable discrete subfield K of the reals containing the number π can be translated into an algorithm for computing the irrationality exponents of all elements of K. As a consequence, we exhibit a computable discrete subfield K of the reals such that all of the aforementioned questions about exponential-trigonometric polynomials over K are undecidable. In particular, we provide the first example of a natural generalisation of the Continuous Skolem Problem that is provably undecidable.

Cite as

Pieter Collins, Bernard Hanzon, and Eike Neumann. On Positivity of Exponential-Trigonometric Polynomials and Irrationality Exponents. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 65:1-65:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{collins_et_al:LIPIcs.MFCS.2026.65,
  author =	{Collins, Pieter and Hanzon, Bernard and Neumann, Eike},
  title =	{{On Positivity of Exponential-Trigonometric Polynomials and Irrationality Exponents}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{65:1--65:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.65},
  URN =		{urn:nbn:de:0030-drops-274478},
  doi =		{10.4230/LIPIcs.MFCS.2026.65},
  annote =	{Keywords: Linear Dynamical Systems, Computability, Computable Numbers, Transcendental Numbers, Irrationality Measure, Irrationality Exponent}
}

Document

DOI: 10.4230/OASIcs.CCA.2009.2263

Computability of Homology for Compact Absolute Neighbourhood Retracts

Authors: Pieter Collins

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract

In this note we discuss the information needed to compute the homology groups of a topological space. We argue that the natural class of spaces to consider are the compact absolute neighbourhood retracts, since for these spaces the homology groups are finite. We show that we need to specify both a function which defines a retraction from a neighbourhood of the space in the Hilbert cube to the space itself, and a sufficiently fine over-approximation of the set. However, neither the retraction itself, nor a description of an approximation of the set in the Hausdorff metric, is sufficient to compute the homology groups. We express the conditions in the language of computable analysis, which is a powerful framework for studying computability in topology and geometry, and use cubical homology to perform the computations.

Cite as

Pieter Collins. Computability of Homology for Compact Absolute Neighbourhood Retracts. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 107-118, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{collins:OASIcs.CCA.2009.2263,
  author =	{Collins, Pieter},
  title =	{{Computability of Homology for Compact Absolute Neighbourhood Retracts}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{107--118},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2263},
  URN =		{urn:nbn:de:0030-drops-22635},
  doi =		{10.4230/OASIcs.CCA.2009.2263},
  annote =	{Keywords: Computability, homology, compact absolute neighbourhood retract}
}

Search Results

Documents authored by Collins, Pieter

On Positivity of Exponential-Trigonometric Polynomials and Irrationality Exponents

Abstract

Cite as

Computability of Homology for Compact Absolute Neighbourhood Retracts

Abstract

Cite as

Thanks for your feedback!

Could not send message