Affiliations: LACL, EA 4213, Université Paris Est –
IUT, Route forestière Hurtault, F-77300 Fontainebleau, France. E-mail:
[email protected] | LLAIC1, Université d'Auvergne – IUT
Informatique, B.P. 86, F-63172 Aubière Cedex, France. E-mail:
[email protected] | Steklov Institute of Mathematics (POMI), 27 Fontanka,
St Petersburg, 191023, Russia. E-mail: [email protected]
Abstract: The undecidability of the additive theory of prime numbers (with
identity) as well as the theory Th(N, +, n ↦ p_n),
where pn denotes the (n + 1)-th prime, are open questions. In a first
part, we show the undecidability of Th(N, +, n ↦ nf(n)) where f is a
good approximation of the enumeration n ↦ p_n/n. In a
second part, as a possible approach, we extend the former theory by adding some
extra function. In this direction we show the undecidability of the existential
part of the theory Th(N, +, n ↦ p_n, n ↦
r_n), where r_n is the remainder of pn
divided by n in the euclidian division. L'indécidabilité de la théorie additive des
nombres premiers ainsi que de la théorie Th(N, +, n ↦
p_n), où p_n désigne le
(n+1)-ième premier, sont deux questions ouvertes. Dans une
première partie, nous montrons l'indécidabilité de Th(N,
+, n ↦ nf(n)) où f est une bonne approximation de la fonction n
↦ p_n/n des nombres premiers. Dans une seconde partie,
nous étendons la première théorie en lui ajoutant une
fonction supplémentaire et nous montrons l'indécidabilité
de la théorie Th(N, +, n ↦ p_n, n ↦
r_n), où r_n désigne le
reste de p_n dans la division euclidienne de
p_n par n, et même de sa seule partie existentielle.
