\documentclass[12pt]{article}
\usepackage{amssymb}
\hfuzz=1pt
\tolerance=1000
\emergencystretch=10pt

%\input amssym.def

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

\begin{document}


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

\author{An.A. Muchnik\\
Institute  of  New Technologies,\\
Moscow,109004, Russia, Nizhnaya Radishevskaya 10,\\
fax 7095 915-69-63; E-mail: amuchnik@int.glasnet.ru}

\maketitle


In  section~1  of  present  paper  the  formula $\varphi _{n}({A})$   of
Presburger arithmetic (integers with  addition  and  order)  with
additional $n$-ary predicate variable $A$ is constructed, which  is
true {\bf iff} predicate  $A$  is  definable  in  Presburger  arithmetic
(Theorem~2).

In section~2 the results of section~1 are applied to  prove
the following facts: (1)~one  can  effectively  decide  given  a
finite synchronous automaton, which recognizes a set of ${n}$-tuple
of integers written in positional notation, whether that set  is
definable  in  Presburger  arithmetic;  (2)~every  property   of
${n}$-tuples of integers which is  recognizable  in  two  essentially
different  scales  of  notation  is  definable   in   Presburger
arithmetic. The last result in case ${n}=1$ was proved by Cobham~\cite{cob1}. In
general case  both  those  facts  were  proved  by  Semenov~\cite{sem2},~\cite{sem3}
(Semenov's proofs are very difficult).

Author is grateful to A.Kh.Shen for listening my  talk  and
writing the draft version of the present paper.

\section*{Historic background}

The  present  work  appeared  during   studying   Semenov's
dissertation~\cite{sem2}. In that paper  the  algorithm,  which  given  a
recognizable set of ${n}$-tuples of integers  decides  whether  this
set is definable  by  a  formula  of  Presburger  arithmetic,  is
constructed using induction on ${n}$. The case $n=1$ is  very  simple.
One-dimensional  set  is  recognizable  {\bf iff}  it  is  finally
periodic.  The  last  property  has  a  direct   expression   in
Presburger  arithmetic.  We  only  have  to  use  the  effective
closeness  of  the  family  of  recognizable  sets  relative  to
Presburger operations. The fact that the  algorithm  exists  for
every ${n}$, follows from our Theorem~2. At first  sight  Theorem~2
isn't plausible. As, even two-dimensional  Presburger  sets  may
consist of some number of subsets with different pe\-ri\-ods,  which
can't 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 periodical subsets.

The author considers the property of  elementary  structure
to have the definable criterion of  definability  to  be  rather
interesting. If we add to a structure  with  this  property  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.  To  author's  regret  any  other
beautiful   ``selfdefinable''   structure  except  Presburger
arithmetic is unknown to him.

As to the structures  with  unsolvable  elementary  theory,
they  are  in  most  cases  mutually  interpretable   with   the
arithmetic of addition and multiplication of integers, the 
``non-selfdefinablity'' of which  is  proved  in \cite{add4}  
and  \cite{tan5} (using
category and measure respectively).

The open  question:  is  the  arithmetic  of  addition  and
multiplication of algebraic real numbers ``selfdefinable''?

The question about non-selfdefinability of all real numbers with addition and 
multiplication is not complicated. Indeed, if $\varphi_{1}(A)$ is
true iff $A$ is definable, let us replace $A(x_{i})$ by $x_{i}=y$.
The new formula $\varphi'(y)$ is true iff $y$ is algebraic. But we
can eliminate quantifiers in $\varphi'(y)$ and get a finite union of
intervals. So we have contradiction.  

\section{The definable criterion of definability}

Let $A\subseteq {\Bbb Z}^{n}$ be some set of ${n}$-tuples of integer. We say  that
a vector ${v\in {\Bbb Z}^{n}}$ is its period if ${x\in A\Longleftrightarrow x+v\in A}$  for  every
${x\in {\Bbb Z}^{n}}$. Let ${W\subseteq {\Bbb Z}^{n}}$. We say that $v$ is the period  of  set  $A$  in
$W$, if the equivalence
$$
x\in A\Longleftrightarrow x+v\in A
$$
is fulfilled whenever ${x\in W}$ and $x+v\in W$ (two points,  both  from
${W}$, which differ on vector ${v}$, either both belong  to $A$ or  both
don't belong to $A$).
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
By Presburger arithmetic we mean 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 {\Bbb 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 {\Bbb Z}}$.  The  set ${A}_{i,l}$  is   called   the
$(i,l)$-section of ${A}$.

THEOREM 1. {\it A  set $A\subseteq {\Bbb Z}^{n}$  is  definable   in   Presburger
arithmetic {\bf iff} all its sections are definable and there exists a
finite set $V\subset {\Bbb Z}^{n}$ of non-zero vectors which  has  the  following
property:\\
$\phantom{aaaaa}$for  every ${k}$  there  exists ${l}$   such   that for  every point $x\in {\Bbb Z}^{n}$\\
$(*)$$\phantom{aa}\,$with $|x|>l$  the  set  $A$  is  periodic  in the $k$-neighborhood\\
$\phantom{aaaaa}$of point $x$ with  some  period  belonging  to the set $V$.}

In other words, definability of  $A$  is  equivalent  to  the
existence of a finite set of ``possible periods'', i.e.\ the set of
vectors such that for every fixed size of neighborhood in  every
far enough neighborhood of that size the  set  $A$  is  periodical
with one of the possible periods, and the  definability  of  all
sections of $A$.

PROOF. I. Let us prove that every  definable  set  has  the
property $(*)$ (the definability of sections of a definable set is
obvious). The well known procedure of elimination of quantifiers
enables us to suggest that the formula $\psi(x_{1}\ldots {x}_{n})$ which  defines
the set $A$ is a Boolean combination of the expressions of one  of
the following types:\\
$t_{i}(x_{1}\ldots {x}_{n})={c}_{i}\bmod m$\\
$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 the  space  into  several
areas. Periodicity is obvious within those areas: $\psi$  is  reduced
to the statements about divisibility only and every variable can
be increased or decreased by ${m}$.

The problem arises, when the point ${x}$ that we have chosen  is
close to  some  hyperplane (${k}$-neighborhood  of  the  hyperplane
contains ${x}$).  Let's  consider  the  set  of  all   hyperplanes,
intersecting with $k$-neighborhood of the chosen point. There  are
two possibilities. If this set of hyperplanes has the full  rank
(the rational cover of normals to hyperplanes is the whole space)
then the  intersection  of $k$-neighborhoods  of  hyperplanes  is
bounded and for  every  point ${x}$  far  enough  such  possibility
doesn't exist. If not then there exists a  vector  with  integer
coordinates which is parallel  to  all  those  hyperplanes  and,
multiplying it by ${m}$, we'll 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}\ (i=1\ldots s)$  has  a  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 we'll call $u_{i}$ the $i$-th normal vector  (because ${u}_{i}$  is
perpendicular to hyperplane ${({u}_{i},{x})=0}$).
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
(2) Let ${E}$  be  an  arbitrary  subset  of  the  set $\{1\ldots s\}$ of
indices. Let us say that ${E}$ is a set of the first  type,  if  the
family of vectors $\{u_{i}\mid i\in E\}$ has full rank  (the  rational  linear
cover is the entire space). In the opposite case we call ${E}$ a set
of the second type.

(3) For every set ${E}$ of  the  second  type  we'll  choose  a
non-zero integer vector which is orthogonal to  vectors ${u}_{i}$  for
all ${i\in E}$.  We  assume,  that  all  components  of  this  vector
(multiplied by a constant, if needed) can be divided by ${m}$. These
vectors, chosen for different ${E}$,  form  a  set ${V}$  of  possible
periods.

(4) Let we are given an arbitrary value ${k}$ (the  size  of  a
neighborhood). Let  us  consider  arbitrary  set ${E}$  of  indices
belonging to the first type. As the family of normal vectors has
the full rank, the intersection of hyperplanes corresponding  to
${E}$ consists of no  more  than  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
hyperplanes which correspond to  equations  belonging  to ${E}$  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  which
intersect the $k$-neighbor\-hood of the point ${x}$; their indices  form
a set, which we denote by ${E}$. This set belongs to the second type
(because of the choice of ${l}$).  Thus  there  exists  some  vector
${v\in V}$, which is parallel to all these hyperplanes. As ${v\in V}$, all
its components can be divided by ${m}$. And ${v}$ is a  period  (as  all
hyperplanes  which  don't  belong  to ${E}$  don't  intersect   the
neighborhood).
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
II. Let us prove now, that if the property~$(*)$ is fulfilled for
some finite set $V$ (in  this  case  we'll  say  that  set  $A$  is
$V$-periodical) and all of the sections of $A$ are  definable,  then
set $A$ is definable also. To prove  this  assertion  let  us  use
induction on cardinality of the set ${V}$.

BASE OF INDUCTION. 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$, $v$ is a  period
of $A$ in $|v|$-neighborhood of ${x}$. Obviously, this involves  that ${v}$
is a period of  $A$  in  the  set $\{x\in {\Bbb 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 exists ${y}=\langle {y}_{1}\ldots {y}_{n}\rangle$ from
${A}'$   and ${q}$   from ${\Bbb Z}$    for    which ${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<-l$ is also definable, its definability is proved  analogously.
The set $A\setminus (A^{*}\bigcup A^{**})$  consists  of  finite  number  of  definable
sections,  therefore  the  set  $A$  is  definable.  The  base  of
induction is proved.

STEP OF INDUCTION. We'll begin with  following  definition.
Let ${A\subseteq {\Bbb Z}^{n}}$ be a set and ${v\in {\Bbb Z}^{n}}$ be a vector. By the {\it 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.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
LEMMA 1.0. {\it From definability of all sections of a set $A$  it
follows the definability of all sections of\/} $\Bd({A},{v})$.

LEMMA 1.1. {\it If a set $A$ is ${V}$-periodical, ${v\in V}$ and ${V}$  consists
of  more  than  one  element,  then  the  set $\Bd({A},{v})$   is
$V\setminus \{v\}$-periodical.}

LEMMA 1.2. {\it Let $A$ be arbitrary set, ${v}$ be arbitrary  non-zero
vector. Then set $A$ is definable through $\Bd({A},{v})$, $\Bd({A},-{v})$ and  a
finite system of sections of set ${A}$ (${A}$  can  be  defined  by  a
formula which has except of the predicates of addition and order
the predicates of the membership to the sets $\Bd({A},{v})$, $\Bd({A},-{v})$
and the predicate  of  the  membership  to  a  finite  union $S(A,v)$ of some
sections of the set $A$).}

Lemmas 1.0, 1.1 and 1.2 enable  us  to  make  the  step  of
induction. What is left is to give their proofs.

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

PROOF OF LEMMA 1.1. Let us check the $V\setminus \{v\}$-periodicity  of
the set $\Bd({A},{v})$. Let we are given an arbitrary ${k}$ (the  size  of
the neighborhood). Because of ${V}$-periodicity of $A$ 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}$,  then  the  set
$\Bd({A},{v})$ is empty in  the ${k}$-neighborhood  of  point ${x}$ (and  is
periodical  with  any  period).  If ${w\neq v}$,  then  in
${k}$-neighborhood of point ${x}$ the set $\Bd({A},{v})$  is  also  periodical
with period ${w}$. Lemma~1.1 is proved.

PROOF OF LEMMA 1.2. Let ${x}$ be an arbitrary point in the  set
${A}$. We denote the point $x+iv$ as ${u}_{i}$ (so that ${u}_{0}={x}$, ${u}_{1}=x+v$, ${u}_{-1}={x}-{v}$
and so on). Then there exists one of the 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 sufficient to prove that every one of them
is definable (through $\Bd({A},{v})$, $\Bd({A},-{v})$  and $S(A,v)$).
Parts ${A}_{1}$, ${A}_{2}$, ${A}_{3}$  are  definable  through $\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 multipliers of ${v}$ (i.e.\ $z-x=pv$, $x-y=qv$ with $p,q\in {\Bbb N}$) and
every point ${w}$ placed strictly between ${y}$ and ${z}$ and differing from
them with vector divisible  by ${v}$,  doesn't  belong  neither  to
$\Bd({A},{v})$, nor to $\Bd({A},-{v})$''. In the same way we  can  express  the
properties $x\in A_{2}$ and $x\in A_{3}$, but the  property  ``$x\in A_{4}$''  is  not
equivalent to the property ``all of the points differing  from ${x}$
with vector divisible by ${v}$ don't belong neither to $\Bd({A},{v})$,  nor
to $\Bd({A},-{v})$'' as the last property is fulfilled also for points ${x}$
such that all of the points ${u}_{i}=x+iv$ don't belong to ${A}$. In  order
to distinguish those  two  possibilities  we  have  to  use  the
sections of set $A$ (in the way similar to our proof of  the  base
of induction). Lemma~1.2 is proved.

So the proof of Theorem~1 is finished.

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

PROOF. The criterion of  definability  which  is  given  by
Theorem~1 has the phrase ``there exists a finite  set ${V}$'',  which
can't be expressed directly. But  the  used  property  of ${V}$  is
preserved under extension of ${V}$,  therefore  it's  sufficient  to
consider as ${V}$ only the ${d}$-neighborhoods of zero (i.e.\ the sets of
all vectors with the length not greater than $d$). Then,  property
$(*)$ becomes definable by a formula and all is  left  is  to  use
induction on $n$ (this is necessary because Theorem~1 contains the
property of definability of sections). Theorem~2 is proved.

THEOREM 3. {\it Let a  finite  automaton  receives  on  input a
${n}$-tuple of  natural  numbers  written  in  the  same  positional
notation, one digit (of every number) for  one  tact,  beginning
with lower grades. One can effectively decide  whether  the  set
recognized  by  the  automaton  is   definable   in   Presburger
arithmetic.}

PROOF. Let us substitute the predicate recognizable by  the
automaton for the symbol $A$ in the the formula $\varphi _{n}$ from Theorem~2.
Using the recognizibility of ternary predicate of  addition  and
binary predicate of  order  on  natural  numbers  and  effective
closeness  of  recognizable  sets   under   logical   operations
(complementation, unification, projection and cylindrification), we get
the automaton recognizing the empty or  full  set  depending  on
$\varphi_{n}({A})$ being true or false. The problem of  emptiness  of  finite
automaton is solvable. Theorem~3 is proved.

Analysing the proof of part II of Theorem~1, one can easily
conclude that in fact a  stronger  result  was  proved:  in  the
if-part of Theorem~1 the property~$(*)$ can be replaced  with  the
following one:\\
$\phantom{aaaaaa}$the set $A$ is periodical in every far enough neighborhood\\
$(**)$$\phantom{aa}\,$of radius ${k}$ with a period from set ${V}$ where ${k}$ is  the  sum\\
$\phantom{aaaaaa}$of lengths of all vectors from ${V}$

\noindent (i.e.\ it is sufficient to study not all of the ${k}$, but only one ---
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  set ${V}$  then  the  set $\Bd({A},{v})$  is $V\setminus \{v\}$-periodical   in
neighborhood  of  radius $k-|v|$,  and  thus  property  $(**)$   is
fulfilled when passing from $A$ to $\Bd({A},{v})$.

Now we formulate the proven facts presisely.

THEOREM 4. {\it If a set $A\subseteq {\Bbb Z}^{n}$ is such that all its sections  are
definable and there exists a finite set $V\subset {\Bbb 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
Kobham-Semenov's result mentioned in introduction.

\section{Definability of sets recognizable in two sca\-les of notation}

In this section we use the criterion of definability  given
in Theorem~4 to prove the following fact: if  some  predicate  is
recognizable by synchronous finite automaton in ${p}$-based notation
and also in ${q}$-based notation, and ratio $\ln q/\ln p$ is irrational,
then this predicate is definable in Presburger arithmetic.

Let $P(x_{1}\ldots x_{n})$ be a $n$-ary predicate on natural numbers. Let
us write numbers ${x}_{1},\ldots,{x}_{n}$  in ${p}$-based  notation: ${x}_{i}=\sum\limits^{m}_{j=0}x_{ij}p^{j}$,
where ${m}$ is such  that ${x}_{im}\neq 0$  for  some ${i}$.  Let  us  put  their
representations one above another in such a way that for every ${j}$
the digits ${x}_{1j}\ldots {x}_{nj}$ are in the same column. Thus we have   code
every tuple $\langle {x}_{1}\ldots {x}_{n}\rangle$ as a word in alphabet the letters of which
are the columns of height ${n}$  of  figures $0\ldots p-1$. (The  first
letter differs from the zero column). Let us consider for  every
${n}$-ary predicate ${P}$ the set of codes of all ${n}$-tuples satisfying ${P}$.
If this set is recognizable, then we  call  the  predicate ${P}$ a
recognizable predicate in ${p}$-based notation.

It  is  well  known  that  every  predicate  definable   in
Presburger arithmetic is recognizable in ${p}$-based  notation  for
every ${p}$. On the other hand, the set of powers  of ${p}$,  which  is
recognizable in ${p}$-notation, is not arithmetic. And, it's easy to
show that if ${p}$ and ${q}$ are  powers  of  the  same  number  (it  is
equivalent   to   rationality   of $\ln q/\ln p)$,    then    the
recognizability   in ${p}$-based   notation   is   equivalent   to
recognizability in ${q}$-based notation.~\cite{buc6}

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

PROOF. We'll use the mixed $({p},{q})$-based  notation.  In  this
notation we'll use the figures $0\ldots p-1$  with  index ${p}$  together
with figures $0\ldots q-1$ with index ${q}$. If the figures  of  only  one
type are used in notation then we get  the ${p}$-based  or ${q}$-based
notation. In general case, the value of  the $({p},{q})$-no\-tation  is
defined as follows: if we add (from the right) figure ${i}_{p}$  to  a
representation of ${x}$ then we get a representation of number ${px}+{i}$,
and if we add figure ${j}_{q}$ then we get a representation  of  number
${qx}+{j}$. For example,
\centerline{$\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}}$}
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Using the $({p},{q})$-based notation it's possible to  write  the
${n}$-tuples of natural numbers. This is done in  the  same  way  as
coding of ${n}$-tuples of intergers written in  one  notation.  Only
one additional requirement is needed: every column must  contain
the figures of one type  (only ${p}$-figures  or  only ${q}$-figures).
Thus, it arises the  concept  of  a  predicate  recognizable  in
$({p},{q})$-based notation. It's clear that every  such  predicate  is
recognizable in both notations. 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  notations  then ${P}$  is  recognizable   in $({p},{q})$-based
notation.}

PROOF. We begin with  some  preliminary  observations.  The
possible value of a number in $({p},{q})$-based notation is determined
by the number of ${p}$-figures and the number of ${q}$-figures in it. If
the number of ${p}$-figures is ${k}$ and the number of ${q}$-figures  is ${l}$
then the number itself may be anyone from 0 to ${p}^{k}{q}^{l}-1$. If we fix
the places of ${p}$-figures and ${q}$-figures then every number from the
interval $[0,{p}^{k}{q}^{l}-1]$ will have only one representation.

Let us be given a $({p},{q})$-based representation of a number ${x}$.
We'll choose in this representation some  group  of  consecutive
figures; this group is the $({p},{q})$-based notation of  some  number
${y}$. If we  will  replace  this  group  with  another $({p},{q})$-based
representation of the same number ${y}$,  consisting  of  the  same
number of ${p}$- and ${q}$-figures, then the result will be  an  another
$({p},{q})$-based representation of the same  number ${x}$.  It  must  be
stressed that not only the full length of the changed  part  must
not be changed, but also the number of ${p}$- and ${q}$-figures must  be
the same: while adding ${k}$ of ${p}$-figures and ${l}$  of ${q}$-figures,  the
number is multiplied by ${p}^{k}{q}^{l}$ (and  then  the  written  number is
added).

Let us use the following criterion of recognizability.  Let
${M}$ be a set of words  in  fixed  alphabet.  Define  the  relation
``words ${S}$ and ${T}$ are ${k}$-equivalent with respect to the set ${M}$'': this
means that $SR\in M\Longleftrightarrow {TR\in M}$ for  every  word ${R}$  of  the  length  not
greater than ${k}$. The following fact is widely known:\\
a set ${M}$ is recognizable$\,\Longleftrightarrow\,$for  every  large  enough ${k}$  the
relations of ${k}$-equivalence with respect to ${M}$ coinside.

We  know  that  predicate ${P}$  is  recognizable  in ${p}$-based
notation. Consider the corresponding set of codes of ${n}$-tuples of
${p}$-based representations and the first number ${k}_{p}$  such  that  for
all $k\ge k_{p}$  the  relations  of ${k}$-equivalence   are   the   same.
Analogously, we'll  consider  the  number ${k}_{q}$  after  which  the
relations of ${k}$-equivalence for ${q}$-based representations  are  the
same. We claim that for $({p},{q})$-based notation  all  relations  of
${k}$-equivalence with $k\ge k_{p}+{k}_{q}$ are the same. Let's  now  prove  this
claim.

Consider the alphabet  letters  of  which  are  columns  of
${p}$-figures of height ${n}$ and columns of ${q}$-figures of height ${n}$. (It
is this alphabet the  words  over  which  are  the ${n}$-tuples  of
naturals written in $({p},{q})$-based notation). If a word ${Z}$ over this
alphabet  represents  the ${n}$-tuple  of  numbers  on  which   the
predicate ${P}$ is true then we write ${Z\in P}$. It's sufficient to  check
that if ${SX\in P}$, ${TX\notin P}$ for some words ${S}$, ${T}$, ${X}$, where  the  length
of word ${X}$ is greater than ${k}_{p}+{k}_{q}$, then there exists a word ${Y}$  of
lower length for which ${SY\in P}$, ${TY\notin P}$.

Let us count how many ${p}$ and ${q}$ columns contains the word ${X}$. As
the length of ${X}$ is greater than ${k_{p}+k_{q}}$, the number  of ${p}$-columns
is greater than ${k}_{p}$, or the number of ${q}$-columns is  greater  than
${k}_{q}$. Let the number of ${p}$-columns be greater than ${k}_{p}$. Consider the
word ${X}'$ which has the same length and the same value as ${X}$  has,
but in which all the ${p}$-columns are moved to the end (the  number
of them isn't  changed): ${X'=VW}$, ${V}$  consists  of ${q}$-columns, ${W}$
consists of ${p}$-columns. Then, ${SX}$ and $SX'$ represent the same tuple
of numbers, and ${TX}$ and $TX'$ also represent the same (but another)
tuple. Thus, ${SX'\in P}$, ${TX'\notin P}$. This means that ${SVW\in P}$, ${TVW\notin P}$.
The word ${SV}$ is $({p},{q})$-based representation of some tuple; let   $\overline{SV}$
be a $p$-based  representation  of  this  tuple.  Word ${TV}$   is
$({p},{q})$-based representation of another tuple; let $\overline{TV}$ be ${p}$-based
representation of this  tuple.  The  word $\overline{SV}W$ is  the ${p}$-based
representation  of  the  same  tuple,  as   $SVW$,   thus ${\overline{SV}W\in P}$.
Analogously, ${\overline{TV}W\notin P}$. As the length ${W}$ is greater than ${k}_{p}$,  one  can
find a shorter word ${W}'$ consisting of ${p}$-columns for which ${\overline{SV}W'\in P}$,
${\overline{TV}W'\notin P}$ (by definition of number ${k}_{p}$). Then, ${SVW'\in P}$, ${TVW'\notin P}$.  This
means that there exists a word $Y$ (namely, the word $VW'$) which is
shorter than ${X}$ and  for  which ${SY\in P}$, ${TY\notin P}$.  Lemma~5.1  is
proved.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Let us now go on with  the  proof  of  Theorem~5.  Let  the
predicate ${P}$ be recognizable in $({p},{q})$-based notation. We'll  show
that the criterion of definability from section~1 (Theorem~4) is
fulfilled. Let us begin with some rather  draft  description  of
the main idea of the proof. Let $\langle {x}_{1}\ldots {x}_{n}\rangle$ be a vector of natural
numbers, we must prove that if this vector is  far  enough  from
the vector $\langle 0\ldots 0\rangle$ then the  predicate ${P}$  is  periodic  in  its
neighborhood (and the period is not very large).

Firstly, we use the ${p}$-based notation only.  For  simplicity
consider the case of unary predicate, i.e.\ the case  of  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
belonging to one segment differs with the last ${k}$ figures  only).
Let us study the structure of the  predicate  on  one  of  those
segments. As the predicate is recognizable (we assume, that  the
input numbers begin with leading digits) the number of different
structures of the predicate  is  not  more  than  the  number  of
automaton states. Indeed, the  state  of  automaton  before  the
beginning of reading of ${k}$ lower digits  completely  defines  the
structure of the predicate on the corresponding segment.

Now the question of periodicity is divided  in  two  parts:
(1)~what will happen if the neighborhood which we are interested
in intersects the boundary between segments  and  (2)~what  will
happen if some segment contains this neighborhood.

We'll reduce the first case to the  second  one  using  the
following trick: we'll consider the predicate ${P}({x})$ together with
the predicate ${P}({x}+{c})$, where ${c}$ is close to the half of ${p}^{k}$.  This
predicate is recognizable also. Consider the predicate ${P}({x})$  as
the marking of naturals by zeros and ones. Then the marking ${P}({x})$
of a neighborhood which covers  the  boundary  between  segments
coincides with the marking ${P}({x}+{c})$ of  a  neighborhood  which  is
close to the middle of segment, and the first case is reduced to
the second one.

If we are interested in the neighborhood  which  is  placed
within one of the segments it will be sufficient to consider the
finite number  of  segments  with  different  behaviors  of  the
automaton.

Now it's time to remember ${q}$-figures,  which  can  be  used
together  with ${p}$-figures, as the predicate  is  recognizable  in
$({p},{q})$-based notation. Remember that in this system every  number
has different representations.

We'll combine two methods using which we   can  change a
$({p},{q})$-based word ${x}$ without changing the truth value of statement
${x\in P}$:

(1) it's  possible   to   pass   to   another $({p},{q})$-based
representation of the same number;

(2) it's possible to pass to  another  word  after  reading
which the automaton is in the same state.

By condition $\ln q/\ln p$ is irrational.  Therefore  we can  find
sufficiently large natural  numbers ${k}$  and ${l}$,  for  which  number
$k\cdot \ln(p)-l\cdot \ln(q)$ is sufficiently close to zero. 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, consider the following example. Let $p=10$,
$q=2$; then $10^{3}=1000\approx 1024=2^{10}$. Let $\overline{abcde}$ be  a  five-digit  number
written in decimal notation. Number $\overline{cde}$ is a natural number from
0 to 999 and it can be written  in  binary  notation: $v^{9}v^{8}\ldots v^{0}$
(each of ${v}^{i}$  is  either  0,  or  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  is  greater
than $\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 equal to binary representation  of
the number $\overline{cde}-24\overline{ab}$ (if $\overline{cde}$ isn't too close to zero, of course).

Now we return to the proof of our theorem. We  assume  that
the set of natural numbers is partitioned on segments of  length
${p}^{k}$ (and ${p^{k}\approx q^{l}}$) and we study the predicate ${P}$ within one  segment.
We had seen already that  the  structure  of  the  predicate  is
defined by the state of the automaton in which it comes before reading the last ${k}$  figures.
Let us assume that the two different beginnings ${x}$ and ${y}$ lead the
automaton into the same  state.  We'll  show  that  in  segments
corresponding  to  this  state  the  predicate ${P}$   has   period
${(p^{k}-q^{l})(\bar x-\bar y)}$ (here $\bar x$ and $\bar y$ are the values of words ${x}$  and ${y}$  in
$({p},{q})$-based notation).  Indeed,  let ${s}$  be  some ${k}$-digit  word
consisting of ${p}$-figures. Let ${s}_{1}$ be the ${q}$-based representation of
the number ${\bar s+\bar x(p^{k}-q^{l})}$, which contains ${l}$ figures. Then ${xs}_{1}$ and ${xs}$
are representations of the same  number:  ${\bar x\cdot q^{l}+\bar s_{1}=\bar x\cdot p^{k}+\bar s}$.  Thus,
${xs\in P\Longleftrightarrow xs_{1}\in P}$. Then, ${xs_{1}\in P\Longleftrightarrow ys_{1}\in P}$, as after reading of  words ${x}$
and ${y}$ the automaton is in the same state.
{\hfuzz=2pt \tolerance=9999 \emergencystretch=20pt

}
Now consider the word ${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\Longleftrightarrow ys_{2}\in P$.
Because $ys_{2}\in P\Longleftrightarrow xs_{2}\in P$ we finally get that $xs\in P\Longleftrightarrow xs_{2}\in P$. As
$$
\overline{xs}_{2}-\overline{xs}=\bar s_{2}-\bar s=y(q^{l}-p^{k})+x(p^{k}-q^{l})=(x-y)(p^{k}-q^{l}),
$$
the periodicity is proved. (This holds for  the  case,  when  we
don't go beyond the segment's boundaries, i.e.\ when ${s}$ is not too
close to its ends and $x$, $y$ aren't too big.)

We have displayed the idea of the proof: now let us  go  to
details. Firstly, about how to get two  different  beginnings ${x}$
and ${y}$ which transfer the automaton to the  same  state.  Let  us
formulate this statement  for a $n$-dimensional  case.  Let  the
automaton recognize the predicate in $({p},{q})$-based notation.  (The
automaton receives a word on input, the letters of which are the
col\-umns of ${p}$-figures and ${q}$-figures of height ${n}$.) We call a  word
reduced if its first letter isn't a column consisting  of  zeros
only.

LEMMA 5.2. {\it Let the number of states of automaton be ${j}$. Then
for every reduced word of length greater than $j+1$  there  exists
another reduced word such that after  reading  these  words  the
automaton is in equal states.}

PROOF. Let a reduced word ${x}$ have the length more than $j+1$.
Then among the  sta\-tes  passed  by  the  automaton  on  nonempty
beginnings of ${x}$ there are two coinciding ones. Throwing away the
part between them doesn't change the final state and  the  first
letter of the word. Lemma~5.2 is proved.

According to Lemma 5.2, all states  are  divided  into  two
classes. The states  of  the  first  class  appears  only  after
reading the reduced words of length not greater  than ${j}$.  Those
states can  be  neglected,  as  the  criterion  of  definability
describes  only  the  points  which  are  far  enough  from  the
beginning of coordinates. For every state of  the  second  class
there exists a pair of different reduced  words  which  transfer
the automata in this state. Those pairs of words will be used in
the proof of the periodicity.

The proof of  periodicity  can  be  easily  generalized  on
${n}$-dimensional case. In that case ${\Bbb N}^{n}$ is  partitioned  into  cells
with the side ${p}^{k}$; each cell consists  of  vectors  which  differ
one from another with the last ${p}$-based figures. From  the  point
of view of predicate ${P}$ there exists the finite number  of  types
of cells (corresponding to different states of automaton).

LEMMA 5.3. {\it Let ${x}$ and ${y}$ be  two  words  which  transfer  the
automaton into the same state. Consider the set of all points in
the cell corresponding to this state which  are  placed  at  the
distance not less than $|x+y|\cdot |p^{k}-{q}^{l}|$ from its boundaries.  On
this set predicate ${P}$ is periodical with period $(x-y)(p^{k}-q^{l})$.}

PROOF OF LEMMA 5.3 repeats the above arguments.

For this lemma to  be  nontrivial, $|x+y|\cdot |p^{k}-q^{l}|$  must  be
small relative to ${p}^{k}$ and ${q}^{l}$, i.e.\ $({p}^{k}-{q}^{l})/{p}^{k}$ must be  more  less
than $1/|x+y|$. It can be done, as $({p}^{k}-{q}^{l})/{p}^{k}$  can  be  arbitrary
small and $|x+y|$ is bounded by a constant which does  not  depend
on ${k}$ and which is defined by the automaton. Thus, the inner part
of the cell mentioned in the last lemma can be made larger  than $99\%$
of the cell. 

Also the sum of lengths of all vectors from the set
of periods must be less than  the  size  of  periodical
neighborhood (see the formulation of Theorem~4). The  number  of
periods is  not  greater  than  the  number  of  states  of  the
automaton and the length of the period is  not  greater  than  a
constant multiplied on ${p}^{k}-{q}^{l}$, thus the  sum  of  lengths  is  not
greater than the constant multiplied  on ${p}^{k}-{q}^{l}$.  Hence  we  can
choose ${k}$ and ${l}$ in such a way that the sum  of  periods  is  less
than $1\%$ of the size of cell.

Now it is left the only problem connected with structure of
predicate on the boundaries of the cells. We had already sketched
how to solve it: we  have  to  move  the  predicate.  The  moved
predicate remains recognizable,  but  the  number  of  automaton
states can increase and all our constants will  spread:  because
the length of move depends on ${k}$.

To avoid this difficulty we  apply  the  following  method.
Instead of predicate ${P}({x}_{1}\ldots {x}_{n})$ let us  consider  the  predicate
with two times larger number of variables:
$$
Q(y_{1},z_{1},\ldots,y_{n},z_{n})=P(y_{1}+z_{1},\ldots,y_{n}+z_{n}).
$$
This predicate is recognizable also and we can repeat for it all
our considerations. We  choose ${k}$ and ${l}$ such that ${p}^{k}\approx {q}^{l}$  and  put
${z}_{i}$ equal to 0 or to $[p^{k}/2]$. In  Lemma~5.3  we'll  consider  only
such automaton states which can be reached on words in which all
${z}_{i}$ are zeros. Then  periods  $(\bar x-\bar y)({p}^{k}-{q}^{l})$  will  have  the  zero
${z}$-coordinates. Consequently, ${y}$-coordinates will form the periods
of initial predicate. Thus, we have $2^{n}$  of  partitions  of  the
space on cells (corresponding to different  tuples  of ${z}_{i}$:  for
every coordinate there  exists  two  possibilities).  For  every
point we can find a partition, for which this  point  is  ``inner
enough'' (i.e.\ belongs to the cell together with the neighborhood
of radius $p^{k}/5$).  It  is  remained  to  use  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 on ${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 automate.\\
Math. Systems Theory, 3, N2, 186-192.

\bibitem{sem2}
Semenov A.L. 1975\\
On definability in some solvable theories.\\
Candidate dissertation. Moscow State University.

\bibitem{sem3}
Semenov A.L. 1977\\
Presburger quality of predicates, regular in two  scales  of notation.\\
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).

\end{thebibliography}
\end{document}

