More on an undecidability result of Bateman, Jockusch and Woods

Extract

Let P be the set of prime numbers. Theorem 1 of [1] shows that the linear case of Schinzel's Hypothesis (H) implies that multiplication is definable in 〈ω,+,P〉 and therefore that the first-order theory of this structure is undecidable. Let m be any fixed natural number >2, let R be the set of natural numbers <m which are prime to m, and let r be any fixed element of R. The set

is infinite (Dirichlet). Theorem 1 of [1] can be improved as follows:

Proposition. The linear case of Schinzel's Hypothesis (H) implies that multiplication is definable in 〈ω,+,P_m,r〉 and therefore that the first-order theory of this structure is undecidable.

Proof. We follow [1] with the following new ingredients. Let k be the number of elements of R, i.e. k = ϕ(m) where ϕ is Euler's totient function. Since k is even, the polynomial g(n) = n^k + n satisfies g(0) = g(−1) = 0, so (by Lemma 1 of [1]) it follows from the linear case of (H) that there are natural numbers a_l (l ϵ ω) such that a_l+g(0), a_l+g(1),…, a_l+g(l) are consecutive primes. Since R is finite, we may assume that all the a_l's have the same residue t in R, so that a_l+g(i) ≡ t+1+i (mod m) for i ϵ R. This implies that the function t+1+i (reduced mod m) gives a permutation of R, so we can find s ϵ R such that a_l+g(s) ≡ r (mod m). Consider the polynomial h(n) = g(s + mn) and let b_l = a_s+ml. Then b_l + h(0), b_l + h(1),…, b_l + h(l) are elements of P_m,r. They are not necessarily consecutive elements of P_m,r, but they are separated by a fixed number of elements of P_m,r. This implies that {h(n) ∣ n ϵ ω} is definable in 〈ω,+,P_m,r〉(by adapting the proof of Theorem 1 of [1]), and the result follows.