# What are Weak Arithmetics?

Patrick CÉGIELSKI
Denis RICHARD

Contents

I. An attempt to define Weak Arithmetics from the Journées sur les Arithmétiques Faibles

Theme 1: Construction of Nonstandard Models of first-order Arithmetics in order to investigate:

1) axiomatizations of subtheories of PEANO Arithmetic in which induction schemata are restricted to special subset of formulas;

2) complexities of the considered subtheories, especially for getting algorithms of polynomial time.

Theme 2: Definability and decidability of weak substructures of the Standard Model of PEANO

Theme 3: Abstract Machines, Automata and Words

Other Themes:

a) Graphs, Spectra and RUD;
b) Elementary proofs of classical Number Theory results, Arithmetical Proof Theory;
c) Functional Programming and Recursivity;
d) General Logic;
e) Applied Algorithmics.

II. An illustration of definability problem in Weak Arithmetics: the WOODS- ERDÖS conjecture

II-1 The Number Theoretical approach to WE

II-2 Logical approach to WE

Conclusion.

I. -     An attempt to define Weak Arithmetics from the Journées sur les Arithmétiques Faibles

It is amusing, indeed astonishing, that no-one among a community of about one hundred computer scientists, logicians and mathematicians organizing meetings twice a year for almost ten years has thought it advisable properly and precisely to define the field of research one usually calls Weak Arithmetics. In my opinion, everybody, within this group, brought to it his own interest and wondered at not having to justify the relevance of Weak Arithmetics. In discussions by ourselves, it appears that this relevance is intuitively founded on a common field of mathematical interest, a common set of questions and logical methods to investigate problems, and a general culture within computer science. Basically, a scientist interested in Weak Arithmetics knows some mathematical logic, likes PEANO Arithmetic and the two G¨ODEL Theorems, works or has been working on decision problems, on algorithms and their complexities, and uses all kinds of abstract machines. Through these machines Weak Arithmetics are strongly influenced by the computer-dominated modern world. The Weak Arithmetics scientist is not a professional mathematician who studies numbers (using such tools as algebraic methods, complex analysis and algebraic geometry) but is often (or always in some areas) in contact with Number Theory. Therefore it is difficult to give a precise definition of Weak Arithmetics as a discipline in the same way as - say - Model Theory. Nevertheless we can nowadays consider the list of lectures and talks given from JAF1 to JAF17, in order to determine the main directions and themes provided by the participants at those events. One can distinguish four groups of lectures which the reader can find in the Annex.

Theme 1.- Construction of Nonstandard Models of first-order Arithmetics in order to investigate:

1) axiomatizations of subtheories of PEANO Arithmetic (denoted PA) in which induction schemata are restricted to a special subset of formulas;

2) complexities of the considered subtheories, especially for developing polynomial time algorithms.

This theme is closely linked, on the one hand, to the study of induction schemata which are respectively called logarithmic, open, parameter free, -induction, etc., and, on the other hand, to the BUSS Arithmetic. In this theme, logicians try to construct (nonstandard) models having specific properties (for example an ordered field without an integer part (BOUGHATTAS)). One tries also to prove (or disprove) some axiomatizability properties such as the fact that open-induction in normal rings is not finitely axiomatisable (BOUGHATTAS). Algorithmic and Complexity theories are also connected to this theme because computability in polynomial time corresponds to some specific axiomatisations one can characterize: for instance P. PUDLAK, TAKEUTI and KRAJICEK proved the equivalence between the provability in bounded arithmetic of the collaps of the strict polynomial time hierarchy and the finite axiomatizability of the arithmetical theory in the language of addition, multiplication and with induction schemata restricted to -formulas. The lively style of the preface by J.P. RESSAYRE provides a precise and well-documented presentation, the deep links between nonstandard models, axiomatizability and algorithmic complexity. So on this matter, we refer to his text. Another illustration of this theme is bounded arithmetics, which were introduced by BUSS within a first-order logical language which we denote . This language contains the symbols of successor, addition, multiplication, 0, , length of , that is to say , the function , identity and natural order. In this language, BUSS defines a special induction-schemata on certain subset of formulas providing a Weak Arithmetical theory such that a subset of is if and only if it is -provably . In so doing, BUSS provides a promising method to prove a set is since, according to this result, it is sufficient to prove it is both and in some explicitly known and specific (weak) theory. About this result, P. CEGIELSKI wrote: Practically, if we know it is both and , then the method used to prove this result certainly is not too complex and the demonstration can be formalized in such a theory. However, up to now, no set has been shown in P by such a method. The reason is that bounded arithmetics are still not widely developed. For instance we do not know which classical theorems of Number Theory are true in these Weak Arithmetics. The length of proof of any classical theorem increases greatly with weakness of the arithmetical theory in which this proof takes place. For instance, a proof of DIRICHLET theorem on (infinity of) primes in arithmetical sequences in primitive recursive arithmetic is one hundred pages long. Such results would help to apply BUSS'(results).

Theme 3.- Abstract Machines, Automata and Words. Any program in a specified language which we use in a computer has a corresponding abstract machine, for instance a TURING machine. Actually, we can formalize any program because with addition and multiplication we can define (or simulate) all recursive schemata. Now if we consider only some Weak Arithmetic (for instance PRESBURGER Arithmetic) then a corresponding abstract machine computing functions and relations definable in this theory, or in a model of this one, is of course weaker than a TURING Machine (for instance it can be an automat on for PRESBURGER Arithmetic). In this way, it is natural to associate abstract machines (Automata, Push Down Automata, Cellular Automata, BELTIUKOV Machines, Alternating TURING Machines, etc) with different weak arithmetical theories and to the models we investigate. During the JAF, many machines, algorithms and the objects they represent were presented. Of course, the words - arguments which these machines use - with the different meaning we give to this notion in computer science, were studied. To this theme also belong general coding theory and all problems of weak arithmetical structures consisting of the usual integers with pairing functions (such as CANTOR pairing polynomial) or codings of -tuples (using for example the well-known -function of G¨ODEL). Machines as tools for solving problems of definability or decidability were used by I. KOREC, A. BES, V. BRUYÈRE, C. MICHAUX, J.E. PIN, J. TOMASIK, etc. Machines are not only tools but are themselves the objects of investigation such as for instance the smallest universal TURING Machines (M. MARGENSTERN and PAVLOTSKAIA), or the MATIASSEVITCH machines introduced to solve problems of trace monoid (A. MUSCHOLL, Y. MATIASSEVITCH). Results on these machines are due to O. TEYTAUD and A. BES. The problem of determining whether counting is possible with a given abstract machine is closely connected to question of complexity hierarchies as in the case of the GRZEGORCZYK hierarchy. Automata trees and modular counting were developed by H.A. ESBELIN and R. ESPEL LLIMA. In the framework of infinite games and particularly on Borelsets, J. DUPARC, J.P. RESSAYRE, O. FINKEL refer to automata but this is considered to be on the boundary between Weak Arithmetics and Set Theory. We have seen that Weak Arithmetics cover two main themes (Axiomatizibility and Complexity in Subtheories of PEANO Arithmetic on the one hand, and Arithmetical Definability and Decidability on the other). We have also noted that Abstract Machines underlie our investigations and thus become another theme of studies within the framework of Weak Arithmetics. Nevertheless these three areas do not exhaust the topics presented by participants of the JAF. We list some recurrent questions and some new concepts in the last section of this part.

Other Themes.- a) Graphs, Spectra and RUD; b) Elementary proofs of classical Number Theory results, Arithmetical Proof Theory; c) Functional Programing and Recursivity; d) General Logic; e) Applied Algorithmics.

Theme a) refers to Finite Models and to the FAGIN conjecture which is also linked to RUD according to some results of A. WOODS. The notion of Graph is central and its arithmetisation addresses this question within Weak Arithmetics. In the present issue there is an arithmetisation of the four-colour problem due to Y. MATIASSEVITCH.

Theme b) stems from the work ERDÖS and SELFRIDGE who were the first to ask for what they called elementary proofs (i.e. in the framework of real analysis instead of complex analysis) of results such as the DIRICHELET Theorem on the infinity of primes in arithmetical sequences. Logicians such as TAKAEUTI, KREISEL and SIMPSON (with his reverse mathematics) have contributed to the subject but in a general way. P. CEGIELSKI and O. SUDAC have constructed proofs for specific classical theorems (such as the Prime Number Theorem of DE LA VALLÉE POUSSIN). They have also constructed some first order denumerable structures modelling a version of PEANO Analysis to provide proofs within PEANO Arithmetic models or even within the standard model of weaker arithmetical theories (e.g. , the Primitive Recursive Arithmetic). It is clear that this work should be continued in order to strengthen the tools developed by BUSS.

Theme c) is clearly within the scope of Weak Arithmetics wherein one attempts to reconstruct a missing induction or recursive schemata. In Functional Programming also attempts to avoid recursion and recursive definition. For example L. COLSON demonstrates that roughly speaking primitive recursive algorithms are not optimal in terms of complexity.

Theme d) is mainly concerned with NEZONDET's -destinies which are a general tool founded on trees for deciding closed sentences when applied to theories consisting of a set of sentences in a relational language which have a bounded number of quantifiers. This a promising new method which, for example gives rise to many interesting questions in Number Theory (GUILLAUME, JELEI YIN, RICHARD).

Theme e) could be considered to be the future of Weak Arithmetics in Informatics. A considerable proportion of software relies on algorithms which derive from numerical analysis however, due to the undecidability of the real zero, many of these programs have to be written within the framework of the standard model of integers. This is particularly the case in discrete geometry, computer imagery and artificial vision where faster computation with increasing precision is constantly demanded. Some structure such as the natural integers with the mappings ceiling and floor is necessary to describe digital planes and their algorithms of connectivity, or to perform ray tracing and so on. Here the blend of Number Theory, Logical Arithmetic and Computer Science (automata and chips) which make up Weak Arithmetics has been applied effectively and will become more and more useful.

II. - An illustration of a definability problem is Weak Arithmetics definability: the WOODS-ERDÖS conjecture

The question of whether first-order arithmetic on the set of nonnegative integers is definable in terms of the successor function and the coprimeness predicate is a typical problem of Weak Arithmetics and perhaps, historically speaking, one of the first to be posed in this modern framework. It was raised in 1949 by Julia ROBINSON in her thesis, when she investigated the axiomatizability of different theories of elementary structures on numbers. More precisely, Julia ROBINSON stated: We might also try to improve the theorem by replacing divisibility by the relation of relative primeness. However I have not been able to determine whether is arithmetically definable in terms of and or even in terms of and . This question, and some others of the same nature such as the definability of all arithmetical relations in terms of addition and coprimeness, were neglected for decades. In the eighties, Alan WOODS, returned to these problems. He was the first to realize that the question of definability within mathematical logic is equivalent to the following conjecture of Number Theory: there is an integer such that for every pair of integers, the equality holds if and only if and have the same prime divisors for . This number-theoretical form of Julia ROBINSON's question is itself very closely linked to some open questions proposed by Paul ERDÖS and for which he had conjectured a positive answer. In the book by Richard GUY entilted Unsolved Problems of Number Theory, the question is attributed to Alan WOODS, but due to its close relation with conjectures of ERDÖS which were known to A. WOODS, this conjecture is known as the WOODS-ERDÖS conjecture, or WE or WE if it is necessary to state the parameter . Indeed, WE is a weakening of the following conjecture of P. ERDÖS: ERDÖS asks if there are infinitely many -tuples such that and with can contain the same prime factors. For example 2.3.4.5.6.7.8.9.10 and 14.15.16 or 48.49.50, also 2.3.4.5.6.7.8.9.10.11 and 98.99.100. For he conjectures that there are only finitely many. ERDÖS' interest is the relationship between prime divisors and consecutive integers is supported by many other papers. Weak Arithmetic, combines a Number-Theoretoc pointof view with approchies based on mathematical Logic and concept of definability in a fashion particulary appropriate to the investigation of the WE-conjecture.

II-1     The Number Theoretical approach to WE.

The problem of finding a local characterization of an integer by its prime divisors and by the prime divisors of (or ) - which actually is a problem of definability - was raised by famous mathematicians many years ago. The fundamental result on this question is due to ZSIGMONDY and was rediscovered and generalized by BIRKHOFF and VANDIVER twelve years later. They showed that, except for 2 and 8, each power of a prime number is characterized by and the prime divisors of . An analogue of the previous result dealing with has been proved by LUCAS and generalized by CARMICHAEL. Another Classical result closely related to WE is due to C. STøRMER who showed the following: Let be distinct prime numbers and , be nonnegative integers. For , let us put if is odd, if is even and set
. If then is the fundamental solution of the PELL-FERMAT equation ; If then is the fundamental solution of the PELL-FERMAT equation .
Now, we define as the set of the prime divisors of . From this result, the following:     (i) If E is a set of n distinct prime integers, there are at most nonnegative integers satisfying the condition SUPP(x(x + 1)) E, so that, for any nonnegative integer a, the set ST(a) of nonnegative integers b such that

SUPP (a) = SUPP(b) and SUPP(a + 1) = SUPP(b + 1) is also finite.

(ii) The nonnegative integers x and y are equal if and only if the following conditions are simultaneously satisfied:         1) SUPP(x - 1) = SUPP(y - 1) and SUPP(x + 1)=SUPP(y + 1);         2) for all prime numbers p in SUPP( (or in SUPP() the exponent of p in the factorisation of x + 1 (resp. x - 1) has the same parity as in the factorisation of y + 1 (resp. y - 1).

Recently, number theoretists such as M. LANGEVIN, R. BALASUBRAMANIAN, T.N. SHOREY and M. WALDSCHMIDT have investigated bounds and inequalities which permit the location of integers in according to the relationship of their supports. In this direction, LANGEVIN provides a fundamental result he calls the reduction lemma. To present it, we introduce his notation:     SUPP is prime and ?      is the product of the primes in SUPP(n);      is the greatest prime in SUPP(n);      is the cardinality of SUPP(n);      is the product of all primes in SUPP ;

Reduction Lemma. (LANGEVIN). Let x and y be positive integers. In each group labelled (i), (ii), (iii), (iv), the conditions given are equivalent:

(i)
u(y +i ) = u(x + i) for i k (condition (k));
u(x,k) = u(y,k) (y - x) (condition (k)).
(ii)
u(y + i) u(x + i) for i k (condition (k));
u(x,k) (y -x ) (condition (k));
u(y,k) = gcd ((y - x),u(x,k)) (condition (k)).
(iii)
(y + i) (x + i) for i k (condition (k));
v(y,k) (y - x) (condition (k)).
(iv)
(y + i) = (x + i) for i k (condition (k));
v(y,k) = v(x,k) (y - x) (condition (k)).

We note that condition is the very hypothesis of WE. These conditions show how close the links are between the languages of successor and coprimeness on one hand and successor and divisibility on the other hand.

Beginning with the results on inequalities, we first mention a fundamental result of M. LANGEVIN who proved that for , if then

This inequality was improved upon by R. BALASUBRAMANIAN, T.N. SHOREY and M. WALDSCHMIDT who proved that for x, y, k being nonnegative integers satisfying 0xy and k 1 and (k) of the previous reduction lemma:

1)
There exists an effectively computable absolute positive constant C such that: y-x (k y for y 27;
2)
There exists an effectively computable absolute positive constant D such that: x D( (k) (k))) for k 3.
3)
There exists an effectively computable absolute positive constant E such that: y-x (E.k ((k)(k) for k 3.

Importance of the Woods-Erdös conjecture

Beyond its intrinsic interest both to Mathematical Logic (more precisely for arithmetical definability and axiomatizability) and Number Theory, the attempt to prove or disprove the questions of J. ROBINSON, A. WOODS and P. ERDÖS, gains in importance if we realize how strong the links are between WE and other classical conjectures of Number Theory. In the same paper by LANGEVIN, the following results were proved: Let k be the parameter appearing in the WOODS-ERDÖS conjecture WE(k).     1) If there is an absolute constant C such that for any pair (x,y) of positive integers the condition implies: (HALL's conjecture). then the answer to WE is positive.

2) Moreover, under the same hypothesis above, if we can prove then the answer to WE(k) is positive with modulo a finite set of exceptions.

3) If for every positive real , there exists a constant D such that for any pair (a,b) of positive integers we have; u(a + b)abD(a + b)(gcd(a,b) ((a-b-c)-conjecture), then the answer to WE(k) is positive with modulo a finite set of exceptions.

We note that as a result of conclusions 2) and 3) the above theorem is a negative answer to WE would refute both HALL 's conjecture, and the so-called OESTERLÉ-MASSER 's conjecture (also called the ---conjecture).

There are still other relationships of WE to questions recently answered by Capi Corrales RODRIGÀNEZ and René SCHOOF about the characterization of by supports of , for infinitely many positive this was also a question posed by ERDÖS. Maxim VSMIRNOV (unpublished) has a proof of the characterization of integers by finitely many supports. Ten years ago, we asked whether for all implies and we gave a proof due to A. SCHINZEL of the fact that the (--)-conjecture implies a positive answer to our question. In the section devoted to the logical approach to WE, we present an analogue of these results within the frame-work of definability, when we prove that .

II-2     Logical approach to WE.

To place the logical approach to WE in a more general and historical setting, it is worth pointing out that arithmetical definability goes back to Kurt G¨ODEL who proved that the structure is closed under primitive recursion. In order to appreciate the power of this result, consider the effort required to obtain a direct first-order definition of exponentiation, or of the natural enumeration of prime integers, from equality, addition and multiplication. Another interesting aspect of G¨ODEL's result is that there exist arithmetical structures which are not closed under primitive recursion:     - addition does not belong to as shown by LANGFORD in 1926;     - multiplication does not belong to as shown by PRESBURGER in 1929. Defining addition and multiplication from some a priori weaker languages of arithmetic is not always easy but is sometimes possible. A classical example is the language which defines all arithmetical relations. A. TARSKI provided a first-order -definition of addition from the following equivalence: if and only if or

Julia ROBINSON's results

In a sense, folling the G¨ODEL's works and the above relation due to TARSKI, the first important and really difficult result was the characterization of definability within a Weak Arithmetic structure and was obtained by J. ROBINSON: Addition and multiplication are definable in the structure .

In the same paper, J. ROBINSON showed that the set of nonnegative integers is definable in terms of addition and multiplication within the field of rationals. This result is central to the investigation of decidable and undecidable theories. In order to find other natural axiomatisations of arithmetic, J. ROBINSON asked whether There was first an unpublished positive solution by J. ROBINSON, then a second solution by A. WOODS proving that the -definability of multiplication is a corollary of the SCHNIRELMANN Theorem (stating that every integer is the sum of a finite bounded number of primes). Finally we obtained a proof using coding devices.

It is worth observing that J. ROBINSON attempt to propose a natural axiomatization of first-order PEANO arithmetic in terms of and , was in part completely realized by P. CEGIELSKI in his thesis. Indeed CEGIELSKI has given a first-order natural axiomatization of first-order PEANO Arithmetic in the language . To obtain this axiomatization, he used the so-called ZBV-method of coding which we describe below.

Alan WOODS' results.

Concerning the language , the first result is due to A. WOODS who also proved that . In the sequel we call this question the ROBINSON problem (namely: is there an equality between and ). A. WOODS has linked the ROBINSON problem to the WOODS-ERDÖS conjecture by proving that the answer to the ROBINSON problem is positive if and only if the WE conjecture is true. More precisely, Alan WOODS proved that the following assertions are all equivalent:     (i) The answer to the ROBINSON problem is positive, namely one can define addition and multiplication in terms of equality, coprimeness predicate and successor function; (and vice-versa)

(i') One can define natural order, or addition, or multiplication in terms of equality, coprimeness predicate and successor function;

(ii) One can define equality, addition and multiplication in terms of coprimeness predicate and successor function;

(ii') One can define natural order, or addition, or multiplication in terms of coprimeness predicate and successor function;

(iii) One can define equality in terms of coprimeness predicate and successor
function;

(iv) The answer to the WOODS-ERDÖS conjecture is positive, namely, there is an integer such that for every pair of integers, the equality holds if and only if and have the same prime divisors for .

Remark. It is worth pointing out the status of equality: if we consider successor and coprimeness without equality, then to define equality is equivalent to a positive answer to WE; on the other hand, if we consider equality, successor and coprimeness together, then a success at definition equality order (resp. addition or multiplication) is still equivalent to a positive answer to WE.

At this step in the investigation of the ROBINSON problem, farther results are obtained via the so called ZBV-Method (for ZSIGMONDY-BIRKHOFF-VANDIVER) which we have introduced. This method allows are to prove all the results already mentioned this section as well as providing new results.

ZBV-method of coding.

The ZBV-method consists in considering integers of the form or (where and are coprime) to be coded by their respective support or their respective set of primitive or characteristic divisors. This method is most effective when is a fixed prime and is 1, 2 or 3. By this method, one reduces arithmetical questions to an investigation of finite sets of primes and their boolean combinatorics. Moreover, every finite set of primes (or every function of finite domain mapping primes to primes) is itself codable in infinitely many ways by a single prime integer using a combination of the Chineese Remainder Theorem and the DIRICHLET Theorem. A prime which is a code plays the role of a memory in which we store a finite set of primes. One can interpret the structure as a set theory on the supports of nonnegative integers. Any finite part of the set of primes is coded by the set of integers having as its support.

New -definable relations and undecidability of via the ZBV-method.

It can be proved that an integer is a power of a prime (we say also primary) if and only if the support of is included in the support of any integer not coprime to . As a consequence, the following relations are -definable:     - the set of powers of primes;     - the set of powers of the same prime ;     - every finite relation on ;     - the equality restricted to ;     - the successor function and the predecessor function restricted to ; every integer which is a constant (this is not obvious but is a corollary of the previous point).

A fundamental result derived from the ZBV-method is the possibility of defining the set of primes within the structure . This result can be extended to the structure where Pred denotes the predecessor function on . They are in both structures and , we have all set theoretical combinatorics exist on the supports. For every pair of distinct primes the notation is by definition the only power of such that is a primitive divisor of . The crucial fact is that the ternary relation

such that
is definable in both structures and . >From this relation, one can provide a natural and intrinsic definability within by successor and coprimeness, and also shed some new light on why the elementary theory of is undecidable. Let us begin by putting NewAdd (resp. NewMult if and only if (resp. ) and denoting the restriction of equality to One can show that:     (i) The function transforms the structure into a new structure , NewAdd, NewMult which is definable in ;

(ii) consequently, the theory is undecidable;

What may be added to successor and coprimeness in order to define all arithmetical relations?

At this step the logical approach consists in finding out what are the relations we can add to successor and coprimeness to obtain the definability of all arithmetical relations. With this in mind, we consider the binary relations of exponentiation and power of the form such that there exists which satisfies

and
From the previous result, it can be shown (see [RD,1985-4] and [GSRD,1989]) that

(i) Every relation or function which is first-order definable in is actually first-order definable in .

(ii) Every relation or function definable by a first-order formula of is also definable in the structure by a first-order formula of the associated language

It now follows that the structure where denotes the natural order on restricted to primaries, allows the first-order definition all arithmetical relations on , and verifies that .

The last result we would like to mention, is due to Francis NEZONDET who showed the importance of equality and, the difference between relational and functional languages, to the investigation of arithmetical definability in terms of successor and exprimeness. Actually, there is a structure which is elementarily equivalent to the standard model and in which the identity relation is not definable. More precisely: Let , be respectively the functional symbols of addition and multiplication. There exists an arithmetical model

of
and of the relational theory with equality of the finite arithmetic and within which there is no -formula defining equality, thus refuting WE.

Here , are respectively the functional symbols of addition and multiplication, will be interpreted in the usual way on . The coprimeness predicate on and on the domain is the interpreted as a first-order formula meaning (x and y are coprime) on . By finite arithmetic, we denote the -axioms which characterize an ordered semi-ring. Of course, our finite arithmetic (namely the RR system of Raphael ROBINSON) is a purely relational theory which contains a symbol of equality and does not contain any schema of induction. The proof of this result, consists in first building a model of the finite arithmetic RR and of and then demonstration, that equality is not -definable. We emphasise that here addition and multiplication are functions and not relations. Finally, the theory of the standard model with the functions of addition and multiplication, the coprimeness relation and the constants 0 and 1, does not decide the WOODS-ERDÖS conjecture.

Conclusion: Due to the new tools, the computers, and the new objects of our investigation, the abstracts machines modelizing fragments of the human reasoning, weak arithmetics have appeared. Perhaps weak arithmetics precede weak real analysis which we can observe showing up against the mist of the complexity theory of reals.