Is Presburger arithmetic, augmented with two unary predicates P2, P3, for powers of 2 and powers of 3 respectively, decidable? I know that adding just one of P2, P3 to Presburger keeps it decidable, and I'm asking about both. If I understood correctly the table in the end of http://www.logique.jussieu.fr/~point/papiers/Pres.pdf, it is unknown. Is this truly unknown?
-
3$\begingroup$ A small comment. Presburger arithmetic usually means $(\mathbb{Z},+,<)$ (or $(\mathbb{N},+)$ depending on taste). So the structure described in the question is $(\mathbb{Z},+,<,P_2,P_3)$, which is not the same as $(\mathbb{Z},+,P_2,P_3)$ in the table in Point's paper. $\endgroup$– Gabe ConantOct 8, 2020 at 23:48
-
2$\begingroup$ As an example of the difficulty, try deciding the sentence $\forall x(P2(x) \wedge P3(x+1) \rightarrow x<9)$. It was only settled by Mihailescu in 2002. $\endgroup$– user44143Oct 9, 2020 at 3:32
-
2$\begingroup$ This does follow from the Catalan conjectureu, but it turns out to have been known much earlier, see for example dms.umontreal.ca/~andrew/PDF/catalan.pdf. But it is certainly true that the theory of $(\mathbb{Z},+,<,2^\mathbb{N},3^\mathbb{N})$ contains difficult number theory. $\endgroup$– Erik WalsbergOct 12, 2020 at 21:13
2 Answers
Christian Schulz (a grad student at Urbana) and Philipp Hieronymi have recently shown that $(\mathbb{Z},+,<,2^{\mathbb{N}},3^{\mathbb{N}})$ is undecidable. And I believe they prove this for $(\mathbb{Z},+,<,m^{\mathbb{N}},n^{\mathbb{N}})$ for $m,n \in \mathbb{N}$ with $\log_m n$ irrational. The paper isn't out yet but the result has been presented in talks (for example, SIU Pure Mathematics Conference in May 2019).
Edit: I am going to add an explanation of one reason why this result is interesting.
Let $m,n$ be natural numbers $\ge 2$. A subset $X$ of $\mathbb{Z}^k$ is $n$-recognizable if the set of $n$-ary expansions of elements of $X$ is recognized by some finite automaton. For example $n^\mathbb{N}$ is $n$-recognizable, the set of odious numbers (numbers with an odd number of $1$'s in their binary expansion) is $2$-recognizable. The Cobham–Semanov theorem states that if $m,n$ are multiplicatively independent and $X$ is both $m$- and $n$-recognizable then $X$ is definable $(\mathbb{Z},+,<)$. So in particular if $k = 1$ then $X$ is a finite union of arithmetic progressions.
There is a connection to logic. Let $V_n$ be the ternary predicate on $\mathbb{Z}$ where $V_n(d,j,l)$ holds if $d$ is the $j$th $n$-ary digit of $l$. Then $X$ is $n$-recognizable iff $X$ is definable in $(\mathbb{Z},+,<,V_n)$. This is used to show that $(\mathbb{Z},+,<,V_n)$ is decidable. (And in fact decidability of these structures has had notable mathematical applications, see for example the paper Madhusudan–Nowotka–Rajasekaran–Shallit, Lagrange’s Theorem for Binary Squares, MFCS 2018, doi:10.4230/LIPIcs.MFCS.2018.18, arXiv:1710.04247.)
Villemaire showed that $(\mathbb{Z},+,<,V_n,V_m)$ is undecidable when $m,n$ are multiplicatively independent. Bes showed that if $X$ is definable in $(\mathbb{Z},+,<,V_n)$ and not definable in $(\mathbb{Z},+,<)$ then $(\mathbb{Z},+,<,X)$ defines $n^\mathbb{N}$. So putting it together we see that if $m,n$ are multiplicatively independent, $X$ is $(\mathbb{Z},+,<,V_n)$-definable, $Y \subseteq \mathbb{Z}^l$ is $(\mathbb{Z},+,<,V_m)$-definable, and neither $X$ nor $Y$ is definable in $(\mathbb{Z},+,<)$, then $(\mathbb{Z},+,<,X,Y)$ is undecidable. This is a mutual generalization of Cobham–Semenov and Villemaire's result.
It should be noted that $(\mathbb{Z},+,<,n^\mathbb{N})$ does not define $V_n$. In fact these two structures are separated by a deep dividing line, $(\mathbb{Z},+,<,n^{\mathbb{N}})$ is NIP and $(\mathbb{Z},+,<,V_n)$ is as IP as you can get.
-
$\begingroup$ Do you have any reference whatsoever for this? At the very least something like an abstract of a talk which claims that? $\endgroup$– WojowuOct 8, 2020 at 22:12
-
$\begingroup$ 192.17.3.249/… It was on March 15 2019. (I went to the talk). $\endgroup$ Oct 8, 2020 at 23:11
-
1$\begingroup$ Here's a pdf with a (short) abstract on page 11: math.siu.edu/llmc2019/Logic2019-abstracts.pdf (I was also at the talk, for what it's worth.) Erik, my understanding is that is is joint with Philipp? $\endgroup$ Oct 8, 2020 at 23:11
-
1$\begingroup$ @JamesHanson The proof does not yield definibility of multiplication, and last time I talked to them they thought that multiplication might not be definable. They uniformly interpret $([0,n],+,\times,<)$ where $+$ and $\times$ are considered as partial functions. All of this happens on a sparse set. $\endgroup$ Oct 9, 2020 at 5:24
-
2$\begingroup$ @DavidRoberts $(\mathbb{Z},+,<)$ and $(\mathbb{N},+)$ are bi-interpretable. People studying "expansions of Presburger" will often pick and choose between the two. $\endgroup$ Oct 9, 2020 at 10:45
Yes, that does seem to be what the paper is claiming. The author seems to be an expert, so there seems to be little reason to doubt the question is open. :)
-
$\begingroup$ Thanks Bjorn! I just want to make sure, it seems like a very classical question, so I'm not sure. $\endgroup$– ikpMar 13, 2014 at 8:42
-
$\begingroup$ It's classical but it's fairly specific... that structure with the sets $P_2$ and $P_3$ is not the most natural, right? $\endgroup$ Mar 13, 2014 at 18:13
-
3$\begingroup$ it's not natural before you know you can either one of them :) $\endgroup$– ikpMar 13, 2014 at 19:10