Fischer and Rabin's Super-Exponential Complexity of Presburger Arithmetic (1974) has the following theorem.

(Theorem 12) Let $U$ be any class of additive structures, so if $A = (A, +) \in U$, then $+$ is a binary associative operation on $A$. Let Th($U$) be the set of sentences of $L$ valid in every structure of $U$. Assume $U$ has the property that, for every $k \in \mathbb N$, there is a structure $A_k = (A_k, +) \in U$ and an element $u \in A_k$ such that the elements $u, u + u, u + u + u, ... , k . u$ are distinct. Then the statement of Theorem 1 holds for Th($U$) with the lower bound $2^ {dn}$ for some $d > 0$.

The conclusion that Th($U$) is at least exponential time. They don't provide a proof for this (they say they will in a subsequent paper, which I believe has never appeared), but they say that their proof for the theory of the real numbers can be adapted by using $ku$ as a representation for $k$.

Is there a more detailed exposition of a proof of this theorem? The following points are not clear to me:

  1. The exact hypothesis of this theorem is unclear to me. On one hand, they say "additive", use the symbol $+$, and list commutative monoids or expansions thereof as examples after stating this theorem. On the other hand, they do not explicitly say "commutative" or "abelian"; it may be sufficient to assume associativity if we are applying the operation to $u, u+u, \dots$ to represent natural numbers because commutativity is not an issue as long as these elements are concerned.

  2. Presumably, one needs to say in the language $\{+\}$ that $u, \dots ku$ are distinct in order to use them as representation for natural numbers up to $k$. One also needs very large $k$ to simulate Turing machines. How can one ensure that $u$ has the desired property with a relatively short logical formula?

  • $\begingroup$ For (2) at least, I would take the comment about distinctness of elements as a 'meta-hypothesis'; it's not necessary to try and say in U that the elements are distinct, since we're not trying to prove the theorem within U. $\endgroup$ – Steven Stadnicki Feb 25 '18 at 4:56
  • $\begingroup$ @StevenStadnicki I would imagine the proof goes as follows: given $(e, \sigma, t)$, where $e$ is a code for an $O(2^n)$-time TM, $\sigma$ is an input and $t$ is a number, we write a sentence like $\exists u \exists m T_{e,\sigma,t}(m, u)$, where $T_{e,\sigma,t}(m, u)$ says that $m$ is the code of a computation of time at most $t$ that starts with $\sigma$ on the tape, where the code uses $u, u+u, \dots$ as integers. My worry is that unless we conjoin the sentence with another that says $u, u+u, \dots$ are distinct, $T_{e,\sigma,t}$ might not mean what we want it to mean. ... $\endgroup$ – Pteromys Feb 25 '18 at 6:26
  • $\begingroup$ @StevenStadnicki ... For, for instance, if $ku = u$ for all $k$, there is no hope that $T_{e,\sigma,t}$ can encode/decode any interesting thing. $\endgroup$ – Pteromys Feb 25 '18 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.