DROPS

Document

DOI: 10.4230/LIPIcs.LICS.2026.7

On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic

Authors: Piotr Bacik, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, Madhavan Venkatesh, and Emil Rugaard Wieser

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

Abstract

We consider expansions of Presburger arithmetic with families of monadic polynomial predicates. (Examples of such predicates are the set of perfect squares, or the set of integers of the form 2n³-5n+3, etc.) Although the full attendant first-order theories are well known to be undecidable, very little is known when one restricts the number of variables. In the case of single-variable theories, we obtain positive results for the following two families of predicates: (i) for perfect fixed powers, decidability of the corresponding theory follows from the solvability of hyperelliptic Diophantine equations; and (ii) for polynomials of degree at most three, we establish decidability by relying on the low genus of the resulting algebraic curves. Finally, we discuss limitations and hardness results (via encodings of longstanding open Diophantine problems) as soon as any of the above restrictions are lifted.

Cite as

Piotr Bacik, Joris Nieuwveld, Joël Ouaknine, Mihir Vahanwala, Madhavan Venkatesh, and Emil Rugaard Wieser. On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bacik_et_al:LIPIcs.LICS.2026.7,
  author =	{Bacik, Piotr and Nieuwveld, Joris and Ouaknine, Jo\"{e}l and Vahanwala, Mihir and Venkatesh, Madhavan and Wieser, Emil Rugaard},
  title =	{{On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.7},
  URN =		{urn:nbn:de:0030-drops-267947},
  doi =		{10.4230/LIPIcs.LICS.2026.7},
  annote =	{Keywords: Presburger arithmetic, Diophantine equations, decidability, B\"{u}chi’s conjecture}
}

Search Results

Documents authored by Venkatesh, Madhavan

On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic

Abstract

Cite as

Thanks for your feedback!

Could not send message