On the Additive Theory of Prime Numbers

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'indecidabilite de la theorie additive des nombres premiers ainsi que de la theorie Th(N, +, n → p_n), ou p_n designe le (n+1)-ieme premier, sont deux questions ouvertes. Dans une premiere partie, nous montrons l'indecidabilite de Th(N, +, n → nf(n)) ou f est une bonne approximation de la fonction n → p_n/n des nombres premiers. Dans une seconde partie, nous etendons la premiere theorie en lui ajoutant une fonction supplementaire et nous montrons l'indecidabilite de la theorie Th(N, +, n → p_n, n → r_n), ou r_n designe le reste de p_n dans la division euclidienne de p_n par n, et meme de sa seule partie existentielle.