16
$\begingroup$

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?

$\endgroup$
3
  • 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$ Oct 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$
    – user44143
    Oct 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$ Oct 12, 2020 at 21:13

2 Answers 2

16
$\begingroup$

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.

$\endgroup$
17
  • $\begingroup$ Do you have any reference whatsoever for this? At the very least something like an abstract of a talk which claims that? $\endgroup$
    – Wojowu
    Oct 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
3
$\begingroup$

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. :)

$\endgroup$
3
  • $\begingroup$ Thanks Bjorn! I just want to make sure, it seems like a very classical question, so I'm not sure. $\endgroup$
    – ikp
    Mar 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$
    – ikp
    Mar 13, 2014 at 19:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.