ANNEX 1

 

WORK PROGRAMME

 

 

1                     TITLE

 

WEAK ARITHMETICS

 

2                     OBJECTIVES & BACKGROUND

 

2.1                Objectives

 

·       To construct Nonstandard Models of Buss Arithmetic to establish some bounds on the class NP inter co-NP.

 

·       To solve the problem of existence of end extensions of countable models of bounded collection.

 

·       To explore further the additive theory of infinite sets of prime numbers, both with absolute results and its links with number theory via the Schinzel's hypothesis.

 

·       To code natural numbers, complex numbers, and quadratic integers by automata accepting numbers (written in non-classical systems).

 

·       To prove results for ultra-linear unary recursive schemata (with individual constants).

 

·       To obtain decidability results for S2S[P]  theories.

 

·       To build formal constructive theories (from Grzegorczyk hierarchy) with applications to databases. To investigate the power of counting in very small complexity classes and in the corresponding logical or arithmetical settings.

 

·       To explore the relation between Infinite games, automata, and arithmetic.

 

·       To study the fine structure of the BSS recursive enumerable sets.

 

·       To investigate concurrent processes in distributed conveyer systems and their relation with corresponding weak arithmetics.

 

·       To construct Diophantine representations of recursively enumerable sets of particular interest.

 

·       To show the cofinality of primes in D0 (P), where P is the function which counts the primes below x.

 

·       To study subsystems of Goodstein’s Arithmetic (without quantifiers).

 

·       To develop families of formalized languages for presenting arithmetical texts.

 

 

2.2                Background

 

Weak arithmetic is the study of problems of Number theory and Computer Science using methods of mathematical logic, just as Algebraic Number Theory or Analytic Number Theory use Algebra and Analysis.

 

Weak arithmetic was born in the 1930’s, then really emerged with a famous paper of Julia Robinson in 1949 ; Weak arithmetic has known its most famous result with the (negative) solution of Hilbert’s tenth problem in 1970 by Yuri Matiyasevich, and is involving more and more topics.

 

Works in weak arithmetic are 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ödel Theorems, works or has been working on decision problems, on algorithms and their complexities, and uses all kinds of abstract machines.

 

****

Five of the main sources of results in weaks arithmetics are :

 

·       undecidability of the field of rational numbers (Julia Robinson, 1949),

 

·       Matiyasevich-Davis-Robinson-Putnam theorem (1970), solving Hilbert’s tenth problem (there is no algorithm to determine whether a given diophantine equation has a solution),

 

·       Erdös-Woods conjecture (1981) : there is an integer k such that for every pair (x,y) of integers, the equality x = y holds if and only if x+i and y+i have the same prime divisors for 0 £ i £ k,

 

·       Buss arithmetic (1985): a first-order logical language L(BA) which contains symbols for arithmetical operations  and a special induction-schema on certain subset of formulas providing a Weak Arithmetical theory S such that a subset A of the set N of natural integer is in the complexity class P (we may determine wether an integer belongs to A in polynomial time) if and only if it is S-provably in NP Ç co-NP.

 

·       study of the real exponential field : Tarski has proved in the 1920’s than the first-order theory of the structure (R,+,x,=), where R is the set of real numbers, is decidable, hence the elementary geometry is decidable. He asks the question of the status of (R,+,x,exp,=), where exp is the exponential. In the 90’s very substantial results about this structure and this question have been obtained by Wilkie, Macintyre and others : decidability assuming Shammel’s conjecture, quantifier elimination and « o-minimality ».

 

 

 

 

 

 

 

3              SCIENTIFIC/TECHNICAL DESCRIPTION

           
3.1                Research Programme

 

Table 1 Summary of task involvement

 

TASKS

ITEMS

Responsible

Partner

Involved

Partners

TASK 1

Construction of Nonstandard Models of first-order Arithmetics

P1

P1,P9

TASK 2

Definability and decidability of weak substructures of the Standard Model of Peano

P1

P1,P2,P3,P5,P7,P8

TASK 3

Abstract Machines, Automata, and Words

P2

P1,P2,P4,P5,P7,P8

TASK 4

Elementary proofs of classical Number Theory results

P9

P4,P6,P8,P9

TASK 5

Weak arithmetics, Pure and Computational Logic

P5

P1,P5,P8

 

Every task is 36 months long

 

TASK 1

Construction of Nonstandard Models

 

Partners 1,9

Objectives: To investigate which functions and sets cannot be defined in the Arithmetic axiomatizations of subtheories of Peano Arithmetic and what is the algorithmic complexity of those who can be defined.

 

T1.1  nonstandard models of Buss Arithmetic (P1)

T1.2  to investigate whether bounded induction proves MDRP theorem (P9)

 

 

TASK 2

Definability and decidability of weak substructures

 

Partners 1,2,3,5,7,8

Objectives: To prove that either the whole arithmetical standard model is definable in such a structure or to prove decidability and determine its complexity.

 

T2.1  to explore the additive theory of primes (P1,P2,P7,P8)

T2.2  to explore expansions of <N,+> (P7)

T2.3 systems of Diophantine Linear Equations and Applications (P5)

T2.4 decidability results for S2S[P] theories (P5)

T2.5 formal constructive theories (P3,P8)

 

 

 

TASK 3

Abstract Machines, Automata, and Words

 

Partners 1,2,4,5,7,8

Objectives: to study abstract models of computation

 

T3.1  to explore the relation between infinite games, automata, and arithmetic (P1)

T3.2 BSS model of computation (P7)

T3.3 concurrent processes in distributed conveyer systems (P4)

T3.4 verification of real-time distributed systems (P1)

T3.5 classification of real functions (P5)

T3.6 counting classes  (P1,P8)

T3.7 fusion theory and multihead automata (P8)

T3.8 diophantine representations (P2) 

 

 

 

TASK 4

Elementary proofs of classical Number Theory results

 

Partners 4,6,8,9

Objectives: to determine whether a given theorem of Number Theory is provable in a subsystem of Peano Arithmetic

 

T4.1  to show the cofinality of primes in D0(P) (P6,P9)

T4.2  subsystems of Goodstein’s Arithmetics (P4,P8)

 

 

 

TASK 5

Weak arithmetics, Pure and Computational Logic

 

Partners 1,5,8

Objectives: to apply general methods of Pure Logic and automated theorem proving to arithmetic

 

T5.1  Nezondet’s p-destinies (P8)

T5.2  Computtional Logic (P1,P5)

 

 

 

 

 

 

3.2              Deliverables, Reporting, Exploitation & Dissemination of Results

 

Deliverables are related to the tasks mentioned in the section above and shall be listed accordingly

 

Every task is 36 months long, but partial results will be presented at the following meetings:

 

·        D1 : June 2001 Presentation of every tasks at Fontainebleau (France)

·        D2 : June 2002 Presentation of first results at the first meeting in Saint-Petersburg

·        D3 :  June 2003 Presentation of results at the second meeting

·        D4 : May 2004 Presentation of conclusion at the third meeting

 

Normal discussions from distant members of different teams will be by e-mail but we expect a workshop every year (JAF, for Journées sur les Arithmétiques Faibles; the name exists since ten years, perhaps now WAD for Weak Arithmetics Days)  to present results and, mainly, lively discussions. Normal dissemination will consist of papers in reviews (Journal of Symbolic Logic, Theoretical Computer Science, Annals of Pure and Applied Logic…). Also we expect to publish communications either in a special issue of a review or as a Lecture Note in Mathematics (Springer).

 

 

 

Report Schedule

Reports must be submitted to the INTAS Secretariat as set out in Article 9 of the General Conditions (Annex II) in the format specified in the INTAS Reporting Guidelines, which are updated regularly on the internet site http://www.intas.be

 


 

4              MANAGEMENT

 

4.1              Planning & Tasks Allocation

The project will last 36 months with the activities as indicated in the table below.

 

Tasks
Teams
Months
1-6
Months
7-12
Months
13-18
Month
19-24
Months
25-30
Months
31-36
 
 
 
 
 
 
 
 
T1.1
Team 1
 
 
 
 
 
 
T1.2
Team 9
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
T2.1
Team 7,1,2,8
 
 
 
 
 
 
T2.2
Team 7
 
 
 
 
 
 
T2.3
Team 5
 
 
 
 
 
 
T2.4
Team 5
 
 
 
 
 
 
 
T2.5
Team 3,8
 
 
 
 
 
 
 
 
 
 
 
 
 
 
T3.1
Team 1
 
 
 
 
 
 
T3.2
Team 7
 
 
 
 
 
 
T3.3
Team 4
 
 
 
 
 
 
T3.4
Team 1
 
 
 
 
 
 
T3.5
Team 5
 
 
 
 
 
 
T3.6
Team 1,8
 
 
 
 
 
 
T3.7
Team 8
 
 
 
 
 
 
T3.8
Team 2
 
 
 
 
 
 
 
 
 
 
 
 
 
 
T4.1
Team 6,9
 
 
 
 
 
 
 
T4.2
Team 4,8
 
 
 
 
 
 
 
 

 

 
 
 
 
 
 
 
 
T5.1
Team 8
 
 
 
 
 
 
 
T5.2
Team 5,1
 
 
 
 
 
 
 

 

CO           Professor Patrick Cegielski

  Université Paris XII, IUT de Fontainebleau, France

 

CR1         Professor Yuri Matiyasevich

                Steklov Institute of Mathematics at Saint-Petersburg, Russia

 

CR2         Professor Anatoly Beltiukov

                Udmurt University, mathematics faculty, Russia

 

CR3         Professor Yuri Shoukourian

               Institute for Informatics and Automation Problems, Yerevan, Armenia

 

CR4         Senior research scientist Alexander Lyaletski

                 Kiev University, Ukraine

 

CR5        Senior researcher Paola D’Aquino

               University of Naples II, Italy

 

CR6        Professor Véronique Bruyère

               Université de Mons-Hainaut, Belgium

 

CR7        Professor Denis Richard

               Université de Clermond-Ferrand 1, France

 

CR8         Professor Constantinos Dimitracopoulos

               University of Athens, Greece   


 

 

5 -SUMMARY

 

WEAK ARITHMETICS

 

Weak arithmetic is the study of problems of Number theory and Computer Science using methods of mathematical logic, just as Algebraic Number Theory or Analytic Number Theory use Algebra and Analysis. Five of the main sources of results in weaks arithmetics are undecidability of the field of rational numbers, Matiyasevich-Davis-Robinson-Putnam theorem, solving Hilbert’s tenth problem, Erdös-Woods conjecture, Buss arithmetic and study of the real exponential field.

 

The proposed project is constituted of nine teams from university of Paris, Steklov Institute of Mathematics at Saint-Petersburg (Russia), Udmurt University (Russia), Institute for Informatics and Automaton Problems at Yerevan (Armenia), Kiev University (Ukraine), University of Naples (Italy), university of Mons-Hainaut (Belgium), university of Clermont-Ferrand (France), and University of Athens (Greece).

 

Objectives for the three years were : to construct Nonstandard Models of Buss Arithmetic to establish some bounds on the class NP inter co-NP ; to solve the problem of existence of end extensions of countable models of bounded collection ; to explore further the additive theory of infinite sets of prime numbers, both with absolute results and its links with number theory via the Schinzel's hypothesis ; to code natural numbers, complex numbers, and quadratic integers by automata accepting numbers (written in non-classical systems) ; to prove results for ultra-linear unary recursive schemata (with individual constants); to obtain decidability results for S2S[P]  theories ; to build formal constructive theories with (from Grzegorczyk hierarchy) with applications to databases ; to investigate the power of counting in very small complexity classes and in the corresponding logical or arithmetical settings ; to explore the relation between Infinite games, automata, and arithmetic ; to study the fine structure of the BSS recursive enumerable sets ; to investigate concurrent processes in distributed conveyer systems and their relation with corresponding weak arithmetics; to construct Diophantine representations of recursively enumerable sets of particular interest ; to show the cofinality of primes in D0 (P), where P is the function which counts the primes below x ; to study subsystems of Goodstein’s Arithmetic (without quantifiers) ; to develop families of formalized languages for presenting arithmetical texts.

 

Main exchanges are by e-mail but it is planning two workshops (a local one and a general) by year, two co-ordination meeting and exchanges of scientists.