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

<blockquote>
  <p>(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 &gt; 0$.</p>
</blockquote>

<p>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$.</p>

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

<ol>
<li><p>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.</p></li>
<li><p>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?</p></li>
</ol>

CC BY-SA 3.0
2018-02-25T04:56:46.890Z
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.
Steven Stadnicki
CC BY-SA 3.0
2018-02-25T06:26:21.553Z
@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. ...
Pteromys
CC BY-SA 3.0
2018-02-25T06:29:04.647Z
@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.
Pteromys
<cc.complexity-theory><reference-request><lo.logic>
Fischer and Rabin's theorem (1974) for theories of "additive" structures
Pteromys
# Fischer and Rabin's theorem (1974) for theories of "additive" structures

(Asked by: username_0 on 2018-02-20)

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?

**Tags:** cc.complexity-theory, reference-request, lo.logic

> **Comments:**
> **username_1**: 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.  
> **username_0**: @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. ...  
> **username_0**: @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.  

---

## 0 answers

