15 problems

Presburger Arithmetic, denoted by $\mathbf{PrA}$, is the true theory of natural numbers with addition. A theory is reflexive when it can prove the consistency of all its finitely a…

Doubly exponential upper-bound conjecture. A doubly exponential upper bound on $\textup{VC}(F)$ holds in the general setting.

Let $R=\\Z[t]$ and $X=\\N$. Define … where each $g_{\alpha(t)}$ is interpreted by … with $g_{\alpha(t)}(x)=0$ when $\alpha(t)=0$. Quantifier-elimination conjecture. Every…

Let $\mathcal{L}$ be an infinite linear order. Suppose that $\operatorname{SC}(\mathcal{L})=\Gamma_{\alpha}$, where $\Gamma$ is one of $\Pi$, $\Sigma$, or $d$-$\Sigma$. The associa…

Let $(a,b)$ be coprime, let $\mathcal{U}_{a,b}$ denote the expansion of $(\mathbb{N},+,0,1)$ by the associated Ulam predicate, and let $\operatorname{Th}(\mathcal{U}_{a,b})$ be its…

Let $(a,b)$ be coprime, and let $\mathcal{U}_{a,b}$ be the expansion of $(\mathbb{N},+,0,1)$ by the predicate for the associated Ulam sequence. Ulam dichotomy. For every coprime…

An interpretable ordering is an ordering definable by an interpretation in Presburger arithmetic; the relevant construction starts with the lexicographic ordering on $\mathbb{N}^k$…

Let $\alpha$ be a quadratic scalar. NP-hardness conjecture. Deciding $\alpha$-Presburger arithmetic sentences with two alternating blocks of quantifiers, a fixed number of variable…

Let $\alpha$ be a non-quadratic scalar. Undecidability conjecture. $\alpha$-Presburger arithmetic sentences with three alternating blocks of quantifiers are undecidable. The paper…

For fixed $m\geq 3$, consider short Presburger sentences … where the quantifiers alternate, each $\mathbf{x}_i\in\mathbb{Z}^{n_i}$ has fixed dimension, and $\Phi$ is a fixed Boolea…

Let $\mathcal{GF}_{1,s}$ be the class of one-variable short generating functions of index at most $s$, and let $\boldsymbol{\Sigma}^{\mathrm{PA}}_1$ and…

Let $\\{S_t:t\in\\N\\}$ be a parametric Presburger family, and suppose $S_t$ is finite. Write $\max(S_t)$ for its maximum. Woods's parametric Frobenius conjecture. The function…

Let $t$ range over $\\N$ and fix $d \in \\N$. A parametric Presburger family is a family $\\{S_t:t\in\\N\\}$ of subsets of $\\Z^d$ defined by an inequality … with…

Let $S_t$ be a parametric Presburger family, meaning a family of subsets of $\mathbb{N}^d$ definable over the natural numbers using quantifiers, boolean operations, and inequalitie…

Let $S_t$ be a family of subsets of $\mathbb{N}^d$ defined using quantifiers, boolean operations, and inequalities of the form … where $\vec a(t)\in\mathbb{Z}[t]^d$,…