% corrections 08.01.2001
% corrections 18.01.2001
% corrections 22.01.2001
% corrections 17.09.2001
\documentclass[12pt]{article}
\usepackage{amssymb,amsmath}
\sloppy

\newcommand{\Bd}{\mathop{\rm Bd}}

\begin{document}


\date{}
\title{The definable criterion for definability in Presburger
arithmetic and its applications.}

\author{An.A. Muchnik\\
Institute of New Technologies,\\
Moscow, 109004, Russia, Nizhnaya Radishevskaya 10,\\
fax 7095 915-69-63}

\maketitle

\begin{abstract}

In section~1 of present paper we construct a formula
$\varphi_{n}({A})$ of Presburger arithmetic (integers with
addition and order) with additional $n$-ary predicate variable
$A$. This formula is true if and only if predicate $A$ is
definable in Presburger arithmetic (Theorem~2).

This formula is used to prove the following facts: (1)~given a
finite synchronous automaton recognizing a set of $n$-tuples of
integers written in positional notation one can effectively
decide whether this set is definable in Presburger arithmetic;
(2)~every predicate (set of $n$-tuples of integers) recognizable
in two essentially different positional systems is definable in
Presburger arithmetic. The last result was proved by
Cobham~\cite{cob1} for the case $n=1$. In general case both (1)
and (2) were proved by Semenov~\cite{sem2},~\cite{sem3}
(Semenov's proofs are very difficult).

Author is grateful to A.Shen for help in writing the
draft version of the present paper.

Keywords: definability, Presburger arithmetic, Cobham--Semenov
theorem.

\end{abstract}

\pagebreak[4]


\section*{Background\footnotemark}

\footnotetext{
This paper is a translation of preprint \cite{much7} published ten
years ago. Since then several articles that apply logical approach
to automata theory appeared, see \cite{b97,bhmv94,mv93,mv96}.
}

The present work appeared while author was reading Semenov's
thesis~\cite{sem2}. Using induction over $n$, Semenov constructs
an algorithm that for a given recognizable set of $n$-tuples of
integers decides whether this set is definable by a formula of
Presburger arithmetic. The case $n=1$ is very simple:
One-dimensional set is definable if and only if it is ultimately
periodic. This property can be expressed directly in Presburger
arithmetic. Then we use the effective closeness of the family of
recognizable sets under Presburger operations. A similar
argument works for every $n$, but we need to use Theorem~2
below.

At first sight Theorem~2 is not plausible: Even two-dimensional
Presburger-definable sets may have subsets with different
periods that cannot be reduced to one period (as in
one-dimensional case).

%Thus, if we try to express directly then
%we'll come to quantifier on the system of periodic subsets.

The property of self-definability (``to have a definable
criterion for definability'') is rather interesting. If we add
to a self-definable structure new predicates such that the
theory of the new structure is decidable then given a formula of
the new structure one can effectively decide whether this
formula is equivalent to some formula of the old structure.
Unfortunately, we don't know any other examples of nice
self-definable structures.

Structures with unsolvable elementary theory are usually
mutually interpretable with the arithmetic of addition and
multiplication of integers, the non-self-definability of which is
proved in \cite{add4} and \cite{tan5} (using category and
measure arguments respectively).

We believe that the structure formed by algebraic real numbers
(with addition and multiplication) is not self-definable;
however, a formal proof is missing (and seems to be rather
complicated).

(Note that it is easy to prove that the structure formed by all
real numbers with addition and multiplication is not
self-definable. Indeed, let us assume that $\varphi_{1}(A)$ is
true if and only if $A$ is definable. Now we replace $A(x)$ by
$x=y$. The new formula $\varphi'(y)$ is true if and only if $y$
is algebraic. But we can eliminate quantifiers in $\varphi'(y)$
and get a finite union of segments. So we come to a
contradiction.)

\section{The definable criterion of definability}

Let $A\subseteq \mathbb{Z}^{n}$ be some set of ${n}$-tuples of
integers. We say that a vector ${v\in \mathbb{Z}^{n}}$ is $A$'s
\emph{period} if ${x\in A\Longleftrightarrow x+v\in A}$ for
every ${x\in \mathbb{Z}^{n}}$. Let ${W\subseteq
\mathbb{Z}^{n}}$. We say that $v$ is a period of set $A$ in $W$,
if the equivalence $$ x\in A\Longleftrightarrow x+v\in A $$
holds when ${x\in W}$ and $x+v\in W$ (two points in $W$ that
differ by $v$ either both belong to $A$ or both do not belong to
$A$). Note that if $v$ is a period of $A$ in $W$, then $-v$ is
also a period of $A$ in $W$.

\emph{Presburger arithmetic} is the elementary theory of
integers with addition and order. The length $|x|$ of vector
${x}$ is the sum of modules of its components.

Let $A\subseteq \mathbb{Z}^{n}$. We will call a {\it section of
$A$} any set of the form
        $$
{A_{i,l}=\{\langle
{x}_{1},\ldots,{x}_{i-1},{x}_{i+1},\ldots,{x}_{n}\rangle\mid
\langle x_{1},\ldots,
{x}_{i-1},l,x_{i+1},\ldots,{x}_{n}\rangle\in A\}},
        $$
where ${i\in \{1,\ldots,n\}}$, ${l\in \mathbb{Z}}$. The set
${A}_{i,l}$ is called the $(i,l)$-\emph{section} of ${A}$.

THEOREM 1. \textit{%
A set $A\subseteq \mathbb{Z}^{n}$ is definable in
Presburger arithmetic if and only if all its sections are definable
and there exists a finite set $V\subset\mathbb{Z}^{n}$ of
non-zero vectors \textup{(}called ``possible periods''\textup{)}
with the following property:}
        \begin{equation*}
\parbox{0.85\textwidth}{%
  \textit{for every ${k}$ there exists ${l}$ such that
  for every point $x\in \mathbb{Z}^{n}$ with
  $|x|>l$ the set $A$ is periodic in the $k$-neighborhood
  of point $x$ with some period that belongs to $V$.}%
}
\leqno{(*)}
        \end{equation*}

PROOF. I. Let us prove that every definable set has property
$(*)$ (the definability of sections of a definable set is
obvious). Using quantifiers' elimination, we may assume that
formula $\psi(x_{1}\ldots {x}_{n})$ which defines $A$ is a
Boolean combination of expressions of
types
        $$
t_{i}(x_{1}\ldots {x}_{n})={c}_{i}\bmod m
        $$
and
        $$
u_{i}(x_{1}\ldots x_{n})\ge d_{i},
        $$
where $t_{i}(x_{1}\ldots x_{n})$, $u_{i}(x_{1}\ldots x_{n})$ are
linear combinations of variables ${x}_{1}\ldots {x}_{n}$ with
integer coefficients and ${m}$, $c_{i}$, $d_{i}$ are constants.

Hyperplanes $u_{i}(x_{1}\ldots x_{n})=d_{i}$ divide
$\mathbb{Z}^n$ into several regions. Periodicity is obvious
within each region: $\psi$ is reduced to statements about
divisibility only, and every variable can be increased or
decreased by $m$.

The problem arises when point $x$ is close to some hyperplane
($k$-neighborhood of the hyperplane contains $x$). Let us
consider the set of all hyperplanes (of the form considered
above) that intersect $k$-neighborhood of some point $x$. There
are two possibilities. If this set of hyperplanes has the full
rank (normals to hyperplanes generate $\mathbb{Q}^n$) then the
intersection of $k$-neighborhoods of hyperplanes is bounded, so
this possibility can be ignored for points $x$ with large $|x|$.
If not, then there exists a vector (with integer coordinates)
that is parallel to all those hyperplanes. Multiplying this
vector by $m$, we get one of the periods.

Now let us continue with a more formal account.

(1) Every inequality ${u}_{i}({x}_{1}\ldots {x}_{n})\ge {d}_{i}$
has form ${u_{i1}x_{1}+\ldots+u_{in}x_{n}\ge d_{i}}$. We denote
the integer vector ${\langle {u}_{i1},\ldots,u_{in}\rangle}$ by
$u_{i}$ and call $u_{i}$ the \emph{$i$-th normal vector}
(because ${u}_{i}$ is orthogonal to hyperplane
${({u}_{i},{x})=d_i}$). Here $i\in\{1,\dots,s\}$ where $s$ is the
number of inequalities.

(2) Let ${E}$ be an arbitrary subset of the set $\{1\ldots s\}$
of indices. Let us say that ${E}$ is a \emph{set of the first
type}, if the family of vectors $\{u_{i}\mid i\in E\}$ has full
rank (generates $\mathbb{Q}^n$). Otherwise we call ${E}$ a
\emph{set of the second type}.

(3) For every set ${E}$ of the second type we choose a non-zero
integer vector which is orthogonal to vectors ${u}_{i}$ for all
${i\in E}$. Without loss of generality we may assume that all
components of this vector are multiples of $m$. These vectors,
chosen for different sets $E$ of the second type, form a set
${V}$ of possible periods.

(4) Let $k$ be an arbitrary positive integer (the size of
neighborhood). Consider an arbitrary set ${E}$ of indices that
belongs to the first type. As the family of normal vectors has
the full rank, the intersection of hyperplanes corresponding to
$E$ has at most one point. The $k$-neighborhood of a hyperplane
is a finite union of parallel hyperplanes, therefore for every
$E$ the intersection of $k$-neighborhoods of all $E$-hyperplanes
is finite. The union of such intersections for all sets $E$ of
first type is also finite, and we take as $l$ the maximal length
of its elements.

(5) Let $|x|>l$. Let us consider all hyperplanes that intersect
the $k$-neigh\-bor\-hood of the point ${x}$; let $E$ be the set
of their indices. This set belongs to the second type (because
of the choice of ${l}$). So there exists some vector ${v\in V}$
parallel to all these hyperplanes. As ${v\in V}$, all its
components are multiples of ${m}$. And ${v}$ is a period (all
hyperplanes that do not belong to ${E}$ do not intersect the
neighborhood).

II. Let us prove now that if the property~$(*)$ is fulfilled for
some finite set $V$ (in this case we say that set $A$ is
$V$-\emph{periodic}) and all sections of $A$ are definable, then
$A$ is definable. To prove this assertion we use induction on
cardinality of the set ${V}$. (We identify $v$ and $-v$ and
count them as one element of $V$ since the definition of period
is symmetric.)

INDUCTION BASE. Let $V=\{v\}$, $v=\langle
v_{1},\ldots,{v}_{n}\rangle$. As $v\neq 0$, we may assume that
$v_{1}>0$. Let $l>0$ be so large that for $|x|>l$, vector $v$ is a
period of $A$ in $|v|$-neighborhood of $x$. Obviously, this
implies that ${v}$ is a period of $A$ in the set $\{x\in
\mathbb{Z}^{n}\mid \; |x|>l\}$. Consider the sections
$A_{1,l},A_{1,l+1},\ldots,A_{1,l+v_{1}-1}$ (the first coordinate
is fixed as $l,l+1,\ldots,l+v_{1}-1$ respectively). They define
all the sections ${A}_{1,s}$ of the set $A$ with $s>l+v_{1}-1$
because of periodicity. More precisely, if
      $$
A'=\{\langle {x}_{1}\ldots {x}_{n}\rangle\in A\mid l\le x_{1}<l+v_{1}\},
      $$
then for a vector $x=\langle x_{1}\ldots x_{n}\rangle$ with
$x_{1}>l$ the property $x\in A$ can be expressed in the
equivalent form: ``there exist ${y}=\langle {y}_{1}\ldots
{y}_{n}\rangle\in A'$ and $q\in\mathbb{Z}$ such that ${x}_{1}\ge
{y}_{1}$, ${x}_{1}-{y}_{1}={v}_{1}{q}$, $x_2-y_2=v_2
q,\ldots,x_n-y_n=v_n q$''. As ${A}'$ is definable (it consists
of finite number of definable sections), the part ${A}^{*}$ of
set $A$ which consists of vectors ${x}=\langle {x}_{1}\ldots
{x}_{n}\rangle$ with ${x}_{1}>{l}$ is also definable. The part
${A}^{**}$ of set $A$ which consists of vectors ${x}=\langle
{x}_{1},\ldots,{x}_{n}\rangle$ with $x_1<-l$ is also definable
for similar reasons. The set $A\setminus (A^{*}\bigcup A^{**})$
consists of finite number of definable sections, therefore $A$
is definable. The base of induction is proved.

INDUCTION STEP. We start with the following definition: Let
$A\subseteq \mathbb{Z}^n$ be a set and $v\in\mathbb{Z}$ be a
vector. By the \emph{boundary} $\Bd(A,v)$ of the set $A$ in the
direction $v$ we mean the set ${\{x\in A\mid x+v\notin A\}}$.
We'll prove the following facts for any set $A\subseteq
\mathbb{Z}^n$ and for any non-zero vector $v\in\mathbb{Z}^n$.

LEMMA 1.0. \textit{If all sections of a set $A$ are definable,
then all sections of $\Bd({A},{v})$ are definable.}

LEMMA 1.1. \textit{If $A$ is ${V}$-periodic, $v\in V$ and $V$
consists not only of $v$ and $-v$, then the set $\Bd({A},{v})$
is $V\setminus \{v,-v\}$-periodic.}

LEMMA 1.2. \textit{$A$ is definable in terms of $\Bd({A},{v})$,
$\Bd({A},-{v})$ and a finite number of sections of set ${A}$.}

(This means that $A$ can be defined by a formula that uses
addition, order and unary predicates for sets $\Bd({A},{v})$,
$\Bd({A},-{v})$ and for finite number of sections of $A$.)

Lemmas 1.0, 1.1 and 1.2 enable us to make the step of induction.
It remains to prove them.

PROOF OF LEMMA 1.0. The $({i},{l})$-section of $\Bd({A},{v})$ is
easily definable in terms of $({i},{l})$-section and
$({i},{l}+{v}_{i})$-section of ${A}$.

PROOF OF LEMMA 1.1. We have to prove that the set $\Bd({A},{v})$
is $V\setminus \{v,-v\}$-periodic. Let $k$ be an arbitrary size
of a neighborhood.

Since $A$ is ${V}$-periodic, one can find $l$ such that in
$k+|v|$-neighborhood of every point ${x}$ with $|x|>l$ the set
$A$ has a period ${w}$ which belongs to ${V}$. If ${w}={v}$ (or
$w=-v$), the set $\Bd({A},{v})$ is empty in the
${k}$-neighborhood of point ${x}$ (and is periodic with any
period). If ${w\neq \pm v}$, then in ${k}$-neighborhood of ${x}$
the set $\Bd({A},{v})$ is also periodic with period ${w}$.
Lemma~1.1 is proved.

PROOF OF LEMMA 1.2. Let ${x}$ be an arbitrary point of $A$. We
denote the point $x+iv$ by ${u}_{i}$ (so that ${u}_{0}={x}$,
${u}_{1}=x+v$, ${u}_{-1}={x}-{v}$ and so on). There are four
(mutually exclusive) possibilities:

(1) for some ${s}$ and some ${t}$ ($s\le 0\le t$) all points
${u}_{s},\ldots,{u}_{t}$ belong to $A$ and ${u}_{s}\in
\Bd({A},-{v})$, ${u}_{t}\in \Bd({A},{v})$;

(2) for some $s\le 0$ all points ${u}_{s},{u}_{s+1}\ldots$
belong to $A$ and ${u}_{s}\in \Bd({A},-{v})$;

(3) for some $t\ge 0$ all points $\ldots,{u}_{t-1},{u}_{t}$
belong to $A$ and ${u}_{t}\in \Bd({A},{v})$;

(4) the points ${u}_{i}$ belong to $A$ for every ${i}$.

Thus, the set $A$ is divided into four disjoint parts ${A}_{1}$,
${A}_{2}$, ${A}_{3}$, ${A}_{4}$ and it is enough to prove that
all of them are definable (in terms of $\Bd({A},{v})$,
$\Bd({A},-{v})$ and sections of the set $A$).

Parts ${A}_{1}$, ${A}_{2}$, ${A}_{3}$ are definable in terms of
$\Bd({A},{v})$ and $\Bd({A},-{v})$. Indeed, the statement
``$x\in A_{1}$'' can be expressed as ``there are points $y\in
\Bd({A},-{v})$ and $z\in \Bd({A},{v})$, for which ${z}-{x}$ and
${x}-{y}$ are positive multiples of ${v}$ (i.e.\ $z-x=pv$,
$x-y=qv$ with $p,q\in \mathbb{N}$) and every point ${w}$ between
${y}$ and ${z}$ such that $y-w$ (and $z-w$) are multiples of
${v}$, does not belong to $\Bd({A},{v})$ and $\Bd({A},-{v})$''.
Properties $x\in A_{2}$ and $x\in A_{3}$ can be expressed in a
similar way.

However, the property ``$x\in A_{4}$'' is not equivalent to the
property ``all the points that differ from ${x}$ by a multiple
of ${v}$ do not belong to $\Bd({A},{v})$ and to
$\Bd({A},-{v})$'', because the latter property is true also for
points ${x}$ such that all the points ${u}_{i}=x+iv$ do not
belong to ${A}$. To distinguish between these two possibilities,
we have to use sections of $A$ (as we did while proving
induction base). Lemma~1.2 is proved.

Theorem~1 is proved.

THEOREM 2. {\it There exists a formula $\varphi _{n}({A})$ of
Presburger arithmetic with additional ${n}$-ary predicate symbol
$A$ which is true if and only if predicate $A$ is definable in
Presburger arithmetic (without additional predicates).}

PROOF.
The phrase ``there exists a finite set ${V}$'' used in the
criterion of definability (Theorem~1) cannot be expressed
directly. But the property of $V$ used in the criterion remains
true if $V$ is replaced by a bigger set. Therefore we may assume
w.l.o.g that ${V}$ is ${d}$-neighborhood of zero (the set of all
vectors whose length does not exceed $d$) for some $d$. Then
property $(*)$ becomes definable by a formula. An induction over
$n$ now completes the proof of Theorem~2 (we use that for
sections of $A$ the property ``to be definable'' is definable).

THEOREM 3. {\it Let $M$ be a finite automaton whose input is
${n}$-tuple of natural numbers written in positional system (all
numbers have the same base and are aligned; $M$ reads $n$ least
significant digits at the first step). One can effectively
decide whether the set recognized by $M$ is definable in
Presburger arithmetic.}

PROOF. Let $A$ be a ($n$-ary) predicate recognizable by $M$.
Consider formula $\varphi_{n}(A)$ from Theorem~2. Ternary
predicate $x+y=z$ and binary predicate $x\le y$ (on
$\mathbb{N}$) are recognizable by finite automata. The family of
recognizable sets is closed under logical operations
(complementation, unification, projection and cylindrification).
Therefore, we can construct an automaton that corresponds to
$\varphi_{n}({A})$; it recognizes empty set if
$\varphi_{n}({A})$ is false and the set of all strings if
$\varphi_{n}({A})$ is true. We can distinguish effectively
between these two cases, so Theorem~3 is proved.

Analysing the proof of Theorem~1, we see that in fact a stronger
result was proved: in the if-part of Theorem~1 the
property~$(*)$ can be replaced with the following one:
        \begin{equation*}
\parbox{0.85\textwidth}{%
     \textit{the set $A$
     is periodic in every far enough neighborhood of radius
     ${k}$ \textup{(}where ${k}$ is the sum of lengths of all vectors
     from ${V}$\textup{)} with a period from ${V}$}
}
\leqno{(**)}
        \end{equation*}
(i.e.\ it is sufficient to consider only one value of $k$, namely,
the sum of lengths of vectors from ${V}$).

Indeed: (1) in the proof of the base of induction
(${V}=\{{v\}}$) it is enough to have periodicity in neighborhood
of radius $|v|$, (2) if the set $A$ is periodic in neighborhood
of radius ${k}$ with periods from ${V}$ then the set
$\Bd({A},{v})$ is $V\setminus \{v\}$-periodic in neighborhood of
radius $k-|v|$, and thus property $(**)$ remains true for
$\Bd({A},{v})$.

These arguments prove the following

THEOREM 4. \textit{If all sections of a set $A\subseteq
\mathbb{Z}^{n}$ are definable and there exists a finite set
$V\subset \mathbb{Z}^{n}$ of non-zero vectors such that the
property $(**)$ is fulfilled, then $A$ is definable in
Presburger arithmetic.}

This theorem will be used in the next section to prove the
Cobham--Semenov's result as mentioned in the introduction.

\section{Definability of sets recognizable in \\positional systems
with two bases}

In this section we use the criterion of definability provided by
Theorem~4 to prove that any predicate $P$ recognizable by finite
automata in two positional systems with bases $p$ and $q$ (where
$\ln q/\ln p$ is irrational) is definable in Presburger
arithmetic.

Let $P(x_1\ldots x_n)$ be a $n$-ary predicate on
$\mathbb{N}$. Assume that ${x}_{1},\ldots,{x}_{n}$ are written
in positional system with base $p$:
${x}_{i}=\sum\limits^{m}_{j=0}x_{ij}p^{j}$, and ${x}_{im}\neq 0$
for some ${i}$. We form an input string for an automaton by
combining digits $x_{1j}\ldots {x}_{nj}$ into one input
symbol. In this way any tuple $\langle {x}_{1}\ldots
{x}_{n}\rangle$ is represented by a string in an alphabet whose
letters are columns of height ${n}$ containing digits $0\ldots
p-1$. (The most significant letter differs from the zero
column). Let us consider for every $n$-ary predicate ${P}$ and
for every base $p$ the set of strings that correspond to all
${n}$-tuples satisfying ${P}$. If this set is recognizable, we
say that ${P}$ a is \emph{recognizable predicate in $p$-based
system}.

It is well known that every predicate definable in Presburger
arithmetic is recognizable in ${p}$-based system for any ${p}$.
On the other hand, the set of powers of ${p}$, which is
recognizable in ${p}$-system, is not definable. Is is easy to
show that if ${p}$ and ${q}$ are powers of the same number (this
condition is equivalent to $\ln q/\ln p\in \mathbb{Q}$),
recognizable predicates are the same for bases $p$ and
$q$~\cite{buc6}.

THEOREM 5. {\it If a predicate ${P}({x}_{1}\ldots {x}_{n})$ is
recognizable in both ${p}$-based and $q$-based systems and $\ln
q/\ln p$ is irrational then predicate ${P}$ is definable in
Presburger arithmetic.}

PROOF. Consider ``mixed'' $(p,q)$-based system that uses
digits $0\ldots p-1$ with subscript $p$ as well as digits
$0\ldots q-1$ with subscript ${q}$. If digits of only one type
are used, we get ${p}$-based or ${q}$-based system. In general
case, the value of the string that includes both types of digits
is defined as follows: if string $s$ represents number $x$, the
string $si_p$ represents ${px}+{i}$ and string $sj_q$ represents
$qx+j$. As an example,
        $$
\overline{1_{8}2_{8}7_{10}}=\overline{1_{8}2_{8}}\cdot 10+7=(\overline{1_{8}}\cdot 8+2)\cdot 10+7=
107=\overline{1_{10}3_{10}3_{8}}.
        $$

The $(p,q)$-based system can be used to represent
${n}$-tuples of natural numbers in the same way as it was done
for one base. An additional requirement is needed: every column
must contain digits of the same type (only ${p}$-digits or only
${q}$-digits). We come to the following

DEFINITION: A predicate $P$ is $(p,q)$-recognizable if the set
of all strings that represent (in $(p,q)$-based system)
$n$-tuples for which $P$ is true, is recognizable by a finite
automaton.

It is clear that every $(p,q)$-recognizable predicate is
recognizable in both systems (with bases $p$ and $q$). It turns
out that the converse assertion is also true.

LEMMA 5.1. {\it If predicate ${P}$ is recognizable in
${p}$-based and ${q}$-based systems then ${P}$ is
$(p,q)$-recognizable.}

PROOF. We start with some observations. Consider a string that
contains $k$ digits with base $p$ and $l$ digits with base $q$.
This string may represent any number between $0$ and
${p}^{k}{q}^{l}-1$. If we fix the places for ${p}$-digits and
${q}$-digits then this representation is unique.

Let $S$ be a $({p},{q})$-based representation of a number ${x}$,
and $T$ be a substring of $S$ that $(p,q)$-represents some
number $y$. Consider another string $T'$ that represents the
same number $y$ and has the same number of $p$- and $q$-digits
as $T$. It is easy to see that string $S'$ that is obtained from
$S$ by replacement $T\to T'$, represents $x$. (It must be
stressed that it is not enough for $T'$ to have the same length
as $T$. It is important that numbers of ${p}$- and ${q}$-digits
in $T$ and $T'$ are the same: a string of ${k}$ ${p}$-digits and
${l}$ ${q}$-digits gives factor ${p}^{k}{q}^{l}$ for digits that
precede it.)

Let us use the following criterion of recognizability. Let $M$
be a set of strings in a fixed alphabet. Define the relation
``strings $S$ and $T$ are $k$-equivalent with respect to~$M$''
as follows: $SR\in M\Leftrightarrow {TR\in M}$ for all strings
$R$ of length at most~$k$. It is well known that a set $M$ is
recognizable if and only if the relations of $k$-equivalence
with respect to $M$ coincide for all sufficiently large values
of $k$. (We may assume without loss of generality that $S$ and
$T$ are non-empty.)

We know that predicate $P$ is recognizable in ${p}$-based
system. Consider the set of strings that corresponds to $P$ is
$p$-based system. This set is recognizable by a finite
automaton. We use the criterion above and let ${k}_{p}$ be the
first number such that for all $k\ge k_{p}$ the relations of
$k$-equivalence are the same. A similar number for $q$-based
system is denoted by ${k}_{q}$.

Let us prove that for $(p,q)$-based system relations of
$k$-equivalence for all $k\ge k_{p}+{k}_{q}$ are the same.

Consider an alphabet whose letters are columns of $p$-digits and
columns of $q$-digits (of height $n$). Strings over this
alphabet $(p,q)$-represent $n$-tuples of natural numbers. We
write $Z\in P$ for a string $Z$ over this alphabet if $Z$
represents a ${n}$-tuple of integers for which $P$ is true. It
is enough to show that if ${SX\in P}$, ${TX\notin P}$ for some
strings $S$, $T$, $X$ (where $S$ and $T$ are non-empty strings)
and length of $X$ exceeds ${k}_{p}+{k}_{q}$, then there exists a
string ${Y}$ shorter than $X$ such that ${SY\in P}$ and
$TY\notin P$.

If string $T$ starts at the $0$th column, then we can use an
empty string~$Y$. If not, let us count $p$- and $q$- columns in
$X$. As the length of $X$ exceeds $k_p+k_q$, either the number
of $p$-columns exceeds $k_p$, or the number of $q$-columns
exceeds $k_q$. Assume, for example, that the number of
$p$-columns exceeds $k_p$. Consider a string $X'$ that has the
same length and the same value as $X$, but all the $p$-columns
in $X'$ are moved to the right (the number of $p$-columns
remains the same). Then $X'=VW$ where $V$ consists of
${q}$-columns and $W$ consists of $p$-columns. Strings ${SX}$
and $SX'$ represent the same tuple of integers (as well as
${TX}$ and $TX'$). Thus, ${SX'\in P}$, ${TX'\notin P}$. This
means that $SVW\in P$, $TVW\notin P$. The string ${SV}$ is
$(p,q)$-representation of some tuple; let $\overline{SV}$ be a
$p$-representation of this tuple. String ${TV}$ is
$(p,q)$-representation of another tuple; let $\overline{TV}$ be
$p$-representation of this tuple. The string $\overline{SV}W$ is
$p$-based representation of the same tuple as $SVW$, therefore,
$\overline{SV}W\in P$. In a similar way $\overline{TV}W\notin
P$. Since the length of $W$ is greater than $k_p$, one can find
a shorter string $W'$ consisting of $p$-columns for which
$\overline{SV}W'\in P$, $\overline{TV}W'\notin P$ (by definition
of $k_p$). Then, $SVW'\in P$, $TVW'\notin P$. This means that
there exists a string $Y$ (namely, $Y=VW'$) which is shorter
than $X$ and for which $SY\in P$, $TY\notin P$. Lemma~5.1 is
proved.

Let us now go on with the proof of Theorem~5. Lemma 5.1 shows
that the predicate $P$ is $(p,q)$-recognizable. We show that
conditions of Theorem~4 are fulfilled and therefore $P$ is
definable.

We start with a proof sketch. For a sufficiently long vector
$\langle x_1\ldots x_n\rangle$ we have to prove that the
predicate ${P}$ is periodic in the neighborhood of $x$ (and the
period is not very large).

At first we use only base $p$. For simplicity we assume that $P$
is an unary predicate (a set of natural numbers). Let us fix
some number $k$ and divide the set of natural numbers into
segments of length $p^k$ (the numbers in one segment have the
same digits except for the last $k$ digits). For each segment
we consider a bit string of length $p^k$ that is a restriction of
$P$ to this segment.

By our assumption $P$ is recognizable (we assume here that input
string is read starting from most significant digits), and the
number of different bit strings of length $p^k$ that are
restrictions of $P$ does not exceed the number of states.
(Indeed, the state of automaton before it starts to read last
$k$ digits determines $P$'s restriction on the corresponding
segment.)

Now the question of periodicity is divided in two parts:
(1)~what happens if the neighborhood in question intersects the
boundary between segments and (2)~what happens if neighborhood
is contained entirely inside one of the segment.

We reduce the first case to the second one using the following
trick: consider the predicate $P(x)$ together with the predicate
$P'(x)=P(x+c)$, where $c$ is close to $p^k/2$. Predicate $P'$ is
also recognizable, and boundaries between $P$-segments
correspond to midpoints of $P'$-segments.

For neighborhoods within segments we have to consider all
possible restrictions of $P$ (they correspond to different
states of the automaton).

Recall that $P$ is $(p,q)$-recognizable, so we can use $p$-digits and
$q$-digits together. It is important for us that given number has
many $(p,q)$-representations.

There are two methods that allow us to change a string $x$
formed by $p$- and $q$-digits without changing the truth value
of statement ${x\in P}$:

(1) we can replace $x$ by another $(p,q)$-representation of the
same integer;

(2) we can replace $x$ by another string that puts automaton
into the same state.

By our assumption $\ln q/\ln p$ is irrational. Therefore we can
find large natural numbers $k$ and $l$ such that $k\cdot \ln
p-l\cdot \ln q$ is close to zero. Since $k\ln p - l \ln
q=\ln(p^k/q^l)$, this means that $p^k/q^l$ is close to $1$ and
the difference $p^k-q^l$ is small compared to $p^k$ or $q^l$.

%Indeed, let
%$0<k_{1}\cdot \ln(p)-l_{1}\cdot \ln(q)=\varepsilon$, let $m$ is natural
%number such that $m\varepsilon\leq\ln q\leq(m+1)\varepsilon$. Then one of two
%following inequalities is true:\\
%$(ml_{1}+1)\ln(q)-mk_{1}\ln(p)\leq\frac{\varepsilon}{2}$ or\\
%$(m+1)k_{1}\ln(p)-[(m+1)l_{1}+1]\ln(q)\leq\frac{\varepsilon}{2}$.\\
%We described
%the way of decrease twice the quantity which we are interested in. So ${p}^{k}$ is  close
%to ${q}^{l}$ (difference between them is an  arbitrary  small  part  of
%both numbers ${p}^{k}$ and ${q}^{l}$). We'll choose such ${k}$ and ${l}$ (the  needed
%closeness will be determined later).

Before going on, let us consider an example. Let $p=10$, $q=2$; then
$10^{3}=1000\approx 1024=2^{10}$. Let $\overline{abcde}$ be a
five-digit decimal number. Then $\overline{cde}$ is a natural
number from 0 to 999; it can be written in binary as
$v^{9}v^{8}\ldots v^{0}$ (here ${v}^{i}\in\{0,1\}$). Consider
now the (10,2)-representation
${a}_{10}{b}_{10}{v}^{9}_{2}{v}^{8}_{2}\ldots v^{0}_{2}$. How
much does the corresponding number differ from
$\overline{abcde}$? It's easy to see that it exceeds
$\overline{abcde}$ by $24\overline{ab}$. For number
${a}_{10}{b}_{10}{v}^{9}_{2}{v}^{8}_{2}\ldots {v}^{0}_{2}$ to be
equal to $\overline{abcde}$ we need
${v}^{9}_{2}{v}^{8}_{2}\ldots {v}^{0}_{2}$ to be a binary
representation of $\overline{cde}-24\overline{ab}$ (this is
possible only if $\overline{cde}$ is not too close to zero).

Now we return to our proof sketch. As we have said, the set of
natural numbers is partitioned into segments of length $p^k$. We
assume that $p^k\approx q^l$. We study the restriction of $P$
onto one segment. This restriction is determined by the state of
the automaton before reading last $k$ digits. Let us assume that
two different prefixes $x$ and $y$ put the automaton into the
same state. Let us prove that corresponding restriction of $P$
has period $(p^k-q^l)(\bar x-\bar y)$ (where $\bar x$ and $\bar
y$ are values of strings $x$ and $y$ in $(p,q)$-based
system). Indeed, let $s$ be some $k$-digit string formed by
$p$-digits. Let $s_1$ be the $q$-based representation of the
number $\bar s+\bar x(p^k-q^l)$ that contains $l$ digits. Then
$xs_1$ and $xs$ represent the same number: $\bar x\cdot q^l+\bar
s_1=\bar x\cdot p^k+\bar s$. Thus, $xs\in P\Leftrightarrow
xs_1\in P$. And $xs_{1}\in P\Leftrightarrow ys_1\in P$ because
strings $x$ and $y$ put the automaton in the same state.

Now consider the string ${s}_{2}$ which is the ${k}$-digit
${p}$-based representation of number $\bar s_{1}+\bar
y(q^{l}-p^{k})$. Then ${ys}_{2}$ and ${ys}_{1}$ are the
representations of the same number, therefore $ys_{1}\in
P\Leftrightarrow ys_{2}\in P$. Because $ys_{2}\in
P\Leftrightarrow xs_{2}\in P$ we finally get that $xs\in
P\Leftrightarrow xs_{2}\in P$. As
      $$
\overline{xs}_{2}-\overline{xs}=\bar s_{2}-\bar
s=\overline{y}(q^{l}-p^{k})+\overline{x}(p^{k}-q^{l})=
(\overline{x}-\overline{y})(p^{k}-q^{l}),
      $$
the periodicity is proved. (This argument works if $s$ is not
too close to endpoints of the segment and $x$, $y$ are not too
big.)

This sketch of the proof should be filled with details. First of
all we have to explain how to get two different prefixes $x$ and
$y$ that put the automaton into the same state. Let us formulate
corresponding statement for $n$-dimensional case. We assume that
automaton recognizes $P$ in $({p},{q})$-based system. (The
automaton's input is a string formed by columns of $p$-digits
and $q$-digits of height $n$.) We call a string \emph{reduced}
if its first symbol is not a zero column.

LEMMA 5.2. \textit{Let $j$ be the number of states of the
automaton. Then for every reduced string $x$ of length greater
than $j$ there exists another reduced string $x'$ that puts
automaton into the same state as $x$.}

PROOF. Consider all the states that are passed while reading all
nonempty prefixes of $x$. Some state appears twice. Throwing
away the part between two instances of that state, we do not
change the final state and the first symbol of $x$. Lemma~5.2 is
proved.

According to Lemma 5.2, all states are divided into two classes.
The states of the first class appear only after reading reduced
strings of length $j$ or less. Those states can be neglected, as
the criterion of definability deals only with points that are
far enough from the origin. For every state of the second class
there exists a pair of different reduced strings that put the
automaton in this state. Those pairs of strings are used in
the proof of the periodicity.

The proof of periodicity can be easily generalized to
$n$-dimensional case. In that case $\mathbb{N}^{n}$ is
partitioned into $n$-dimensional cubic cells with side $p^k$.
Each cell consists of vectors which differ only in $k$ last
$p$-digits. These cells are divided into classes that correspond
to different states of the automaton that recognizes $P$.

LEMMA 5.3. \textit{Let $x$ and $y$ be two strings that put the
automaton into the same state. Consider the set of all points in
the cell corresponding to this state that are at a distance at
least $|\bar{x}+\bar{y}|\cdot |p^k-q^l|$ from cell boundaries.
On this set predicate $P$ is periodic with period
$(\bar{x}-\bar{y})(p^k-q^l)$.}

PROOF OF LEMMA 5.3 repeats the above arguments.

For this lemma to be nontrivial, $|\bar x+ \bar y|\cdot
|p^{k}-q^{l}|$ must be small compared to ${p}^{k}$ and
${q}^{l}$, i.e.\ $|p^k-q^l|/p^k$ must be much less than $1/|\bar
x+\bar y|$. It can be done, as $|p^k-q^l|/p^k$ can be arbitrary
small and $|\bar x+ \bar y|$ is bounded by a constant that does
not depend on $k$ and is determined by the automaton. Thus, the
inner part of the cell mentioned in Lemma 5.3 can be made large
enough to contain $99\%$ of the cell volume.

Also the sum of lengths of all vectors from the set of periods
must be less than the size of periodic neighborhood (see the
statement of Theorem~4). The number of periods is bounded by the
number of states of the automaton and the length of any period
is bounded by $|p^k-q^l|$ (up to a constant factor). Thus, the
sum of lengths does not exceed $c|p^k-q^l|$ for some constant
$c$. Hence we can choose $k$ and $l$ in such a way that the sum
of periods is less than $1\%$ of the cell edge.

The only remaining problem is the behavior of $P$ near the cell
boundaries. As we have said, we solve this problem by shifting
our predicate. It remains recognizable; however, the
number of states can increase and all our constants will change
(because the shift distance depends on $k$).

To avoid this difficulty we apply the following trick. Instead
of predicate ${P}({x}_{1}\ldots {x}_{n})$, let us consider the
predicate $Q$ with doubled arity:
    $$
Q(u_{1},z_{1},\ldots,u_{n},z_{n})=P(u_{1}+z_{1},\ldots,u_{n}+z_{n}).
    $$
This predicate is also recognizable, and our arguments remain
valid for $Q$. We choose $k$ and $l$ such that $p^k\approx q^l$
and let $z_i$ be equal to $0$ or to $\lfloor p^{k}/2\rfloor$. In
Lemma~5.3 we consider only automaton states that can be reached
on strings in which all $z_i$ are zeros. Then periods will have
zero ${z}$-coordinates. Consequently, ${u}$-coordinates will
form the periods of initial predicate. Thus, we have $2^{n}$ of
partitions of $\mathbb{N}^n$ into cells (corresponding to
different tuples of $z_i$: for every coordinate there exist two
possibilities). For every point in $\mathbb{N}^n$ we can find a
partition for which this point is ``deep inside a cell'' (i.e.\
belongs to the cell together with neighborhood of radius
$p^{k}/5$). Now we can apply the criterion of definability. (The
only thing that we haven't checked is the definability of
sections. As the sections of a recognizable predicate are
recognizable, we can use induction over $n$.)

Theorem 5 is proved.

\newpage
\begin{thebibliography}{99}

\bibitem{cob1}
Cobham A. 1969\\
On the base-dependence of sets of numbers recognizable  by\\
finite automata.\\
Math. Systems Theory, 3, N2, 186-192.

\bibitem{sem2}
Semenov A.L. 1975\\
On definability in some solvable theories.\\
Ph.D. thesis, Moscow State University.

\bibitem{sem3}
Semenov A.L. 1977\\
Predicates that are regular in two positional systems are definable
in Presburger arithmetic.\\
Siberian Mathematical Journal, 18, N2, 403-418.

\bibitem{add4}
Addison J.W. Jr. 1965\\
The undefinability of the definable.\\
Notices Amer. Math. Soc., N12, 347.

\bibitem{tan5}
Tanaka H. 1967\\
Some results in the effective descriptive set theory.\\
Publ. Res. Inst. Math. Sci. Kyoto Univ. Ser.A, N3, 11-52.

\bibitem{buc6}
B\"uchi J.R. 1960\\
Weak second-order arithmetic and finite automata.\\
Z. Math. Logik und Grundl. Math., 6, N1, 66-92.

\bibitem{much7}
Muchnik An.A. 1991\\
The definable criterion for definability in Presburger arithmetic
and its application.\\
Preprint. Institute of New Technologies, Moscow (in Russian).

%\bibitem{muchnik-appear}
%Muchnik An.A. [to appear] \\
%The undefinability of the class of definable predicates for
%arithmetic of addition and multiplication of algebraic real
%numbers.

\bibitem{b97}
B\'es A. 1997\\
Undecidable extensions of B\"uchi arithmetic and
Cobham--Semenov theorem.\\
J. Symbolic Logic 62, N.~4, 1280--1296

\bibitem{bhmv94}
Bruy\`ere V., Hansel G., Michaux C., Villemaire R. 1994\\
Logic and $p$-recognizable sets of integers.\\
Bulletin de la Soc. Math.
de Belgique, 1, 191--238.

\bibitem{mv93}
Michaux C., Villemaire R. 1993\\
Cobham's theorem seen through B\"uchi's theorem.\\
Proc. ICALP, Lecture Notes in Computer Science 700, 325--334.

\bibitem{mv96}
Michaux C., Villemaire R. 1996\\
Presburger arithmetic and recognizability of sets of natural
numbers by automata: new proofs of Cobham's and Semenov's theorems.\\
Annals of Pure and Applied Logic, 77, 251--277.

\end{thebibliography}
\end{document}
