AP-SETS OF RATIONALS DEFINE THE NATURAL NUMBERS (PRELIMINARY REPORT)

ALFRED DOLICH AND CHRIS MILLER

Abstract. We show that if K is a field of characteristic zero and A ⊆ ℚ contains arbitrarily long arithmetic progressions, then A defines ℚ over K. As a corollary of results of J. Robinson and E. Szemerédi, if A ⊆ ℕ is infinite and does not define ℕ over K, then a_{n}/n → ∞ as n → ∞, where (a_{n})_{n∈ℕ} is a strictly increasing enumeration of A.

We are interested in the definability theory of expansions of the field of real numbers by collections of sets of natural numbers. An instinctual reaction might be that such structures must be rather poorly behaved, as every real projective set is definable in (ℝ, +, ·, ℕ) [7, 37.6], and it is easy to produce nontrivial examples of A ⊆ ℕ such that (ℝ, +, ·, A) defines ℕ, e.g., images f(ℕ) of ℕ under nonconstant f ∈ ℕ[x], the set all factorials, and the set of all primes. (The last follows from, say, Schnirelmann’s Theorem [12]: there exists M ∈ ℕ such that every n > 1 is a sum of at most M primes.) But, beginning in the late 1980s, examples began to surface that are as well behaved as one could reasonably hope for. In particular, given m ∈ ℕ, the expansion of the real field by every subset of each cartesian power of { m^{n} : n ∈ ℕ } is d-minimal (i.e., in every elementarily equivalent structure, every unary definable set either has interior or is a finite union of discrete sets). See [3–5, 8–10] for details and other examples. In this brief note, we show that if A ⊆ ℕ does not define ℕ over the real field, then every subset of ℕ definable from A must be arithmetically sparse. We shall make this precise.

The upper (Banach) density of A ⊆ ℤ is defined by

lim sup_{n→+∞} \frac{max\{ card(A ∩ [j + 1, j + n]) : j ∈ ℤ \}}{n} ∈ [0, 1].

We say that A has density zero if this number is 0. If A has density zero and is enumerated by a strictly monotone sequence (a_{j})_{j∈ℤ}, then lim_{|j|→+∞} |a_{j}/j| = +∞. Similarly, if A has density zero and is enumerated by a strictly increasing sequence (a_{n})_{n∈ℕ}, then lim_{n→+∞} a_{n}/n = +∞.

We say that a subset A of a ring of characteristic zero is an AP-set if it contains arbitrarily long arithmetic progressions, more precisely, for every n ∈ ℕ there exist a, b ∈ ℤ such that b ≠ 0 and { a + mb : 0 ≤ m ≤ n } ⊆ A. By Szemerédi’s Theorem [13], every subset of ℤ having positive upper density is an AP-set.

Here is the main result of this note.

Theorem. Let 𝔎 be an expansion of a field K of characteristic zero. The following are equivalent.

Date: March 25, 2009.

(i) 𝔎 does not define ℕ.

(ii) 𝔎 defines no AP-subsets of ℚ.

(iii) ℤ ∩ A has density zero for every A ⊆ ℚ definable in 𝔎.

(We regard ℚ ⊆ K as usual.)

Proof. We have (ii)⇒(iii) by Szemerédi, and (iii)⇒(i) is immediate. For (i)⇒(ii), we do the contrapositive. Let A ⊆ ℚ be an AP-set definable in 𝔎. Put

S := { x ∈ K : ∃a, b ∈ K, b ≠ 0 & a, a + b, a + xb ∈ A }.

Then 𝔎 defines S and ℕ ⊆ S ⊆ ℚ, so 𝔎 defines ℚ = { ±x/y : x, y ∈ S & y ≠ 0 }. By J. Robinson [11], 𝔎 defines ℕ. □

Note. John Griesmer (grad student, Ohio State) has pointed out to us that (i)⇒(iii) can be established without appeal to Szemerédi’s Theorem. Let A ⊆ ℚ be such that A ∩ ℤ has positive upper density. It follows from [ still looking for the best published source ] that ℤ is contained in a finite union T of additive translates of the difference set of A. Now replace S above by T. Nevertheless, the equivalence of (ii) is of independent interest, as there are AP sets of density zero, e.g., the set of all primes (Green and Tao [6]) and multiplicatively large sets as defined by Bergelson [1].

As the reader can imagine, there are a number of immediate applications of the Theorem to undecidability theory via known results from number theory. We refrain from attempting to list them, but here is an amusing

Corollary. For every finite partition A of ℕ there exists A ∈ A such that A defines ℕ over every field of characteristic zero. In particular, if A ⊆ ℕ, then at least one of A or ℕ \ A defines ℕ over every field of characteristic zero.

Proof. Zero density is preserved under finite unions, so there exists A ∈ A having positive upper density. □

Remark. This really only needs the implication (i)⇒(ii) and van der Waerden’s Theorem [14], that is, that some A ∈ A is an AP-set.

At present, we are interested primarily in applications of the Theorem to definability theory and asymptotic analysis over the real field. Let f: ℕ → ℕ be strictly monotone. Suppose that (ℝ, +, ·, f(ℕ)) does not define ℕ. What can be concluded about f? By the Theorem, f(ℕ) has density zero, so lim_{n→+∞} f(n)/n = +∞. But, as every subset of ℕ definable in (ℝ, +, ·, f(ℕ)) has density zero, a reasonable conjecture is that lim_{n→+∞} f(n)/n^{m} = +∞ for every m ∈ ℕ, at least, under some assumption of regularity of growth of f. Indeed, if f extends to some g: ℝ → ℝ such that (ℝ, +, ·, g) is o-minimal, then much more is true: By [9, Theorem B], either lim_{n→+∞} f(n)/e^{n^{m}} = +∞ for every m ∈ ℕ, or there exists p ∈ ℝ[x] such that lim_{n→+∞} f(n)/e^{p(n)} = 1 with exponential decay of the error. This result does not use that g(ℕ) ⊆ ℕ, only that lim_{x→+∞} g(x) = +∞, (ℝ, +, ·, g) is o-minimal, and (ℝ, +, ·, g(ℕ)) does not define ℕ. We hope that the Theorem might shed further light on the coefficients of p or the asymptotics of the error. Neither is o-minimality really needed: it is enough to assume that g is sufficiently non-oscillatory at +∞; see [9, §3] for one possible definition of what this might mean. We would like to relax the notion of “sufficiently non-oscillatory” even further. For example, let ⌊x⌋ denote the integer part of x ∈ ℝ. Instead of assuming that f extends to some g such that (ℝ, +, ·, g) is o-minimal, suppose only that f is the restriction of ⌊g⌋ to ℕ of such a g. Do we have the same result on the asymptotics of f? This would follow from [9, Theorem B] if (ℝ, +, ·, g(ℕ)) does not define ℕ, but we do not know if this true. Work is ongoing.

News. Let f: ℝ → ℝ be such that its germ at +∞ belongs to a Hardy field, lim_{x→+∞} f(x) = +∞, f is bounded at +∞ by some x^{N}, and lim_{x→+∞} |f(x) − p(x)| = +∞ for all p ∈ ℚ[x]. By recent work of Chan, Kumchev and Wierdl [2] (as yet unpublished, as far as we know), there exists d ∈ ℕ such that every sufficiently large natural number is a sum of d elements of ⌊f(ℕ)⌋. Hence, ⌊f(ℕ)⌋ certainly defines ℕ over any field of characteristic zero. We believe that we have a much easier (modulo our above Theorem) proof of the latter statement by showing that ⌊f(ℕ)⌋ defines a positive-density subset of ℕ, but we might be content just to appeal to [2].

References

[1] V. Bergelson, Multiplicatively large sets and ergodic Ramsey theory, Israel J. Math. 148 (2005), 23–40. Probability in mathematics. MR 2191223 (2008f:37017)

[2] T. Chan, A. Kumchev, and M. Wierdl, Additive bases arising from functions in a Hardy field, preprint, arXiv:0902.4895.

[3] L. van den Dries, The field of reals with a predicate for the powers of two, Manuscripta Math. 54 (1985), no. 1-2, 187–195. MR 808687 (87d:03098)

[4] H. Friedman and C. Miller, Expansions of o-minimal structures by sparse sets, Fund. Math. 167 (2001), no. 1, 55–64. MR 1816817 (2001m:03075)

[5] , Expansions of o-minimal structures by fast sequences, J. Symbolic Logic 70 (2005), no. 2, 410–418. MR 2140038 (2006a:03053)

[6] B. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, Ann. of Math. (2) 167 (2008), no. 2, 481–547. MR 2415379

[7] A. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR 1321597 (96e:03057)

[8] C. Miller, Tameness in expansions of the real field, Logic Colloquium ’01, Lect. Notes Log., vol. 20, Assoc. Symbol. Logic, Urbana, IL, 2005, pp. 281–316. MR 2143901 (2006j:03049)

[9] , Avoiding the projective hierarchy in expansions of the real field by sequences, Proc. Amer. Math. Soc. 134 (2006), no. 5, 1483–1493 (electronic). MR 2199196 (2007h:03065)

[10] C. Miller and J. Tyne, Expansions of o-minimal structures by iteration sequences, Notre Dame J. Formal Logic 47 (2006), no. 1, 93–99 (electronic). MR 2211185 (2006m:03065)

[11] J. Robinson, The undecidability of algebraic rings and fields, Proc. Amer. Math. Soc. 10 (1959), 950–957. MR 0112842 (22 #3691)

[12] L. Schnirelmann, Über additive Eigenschaften von Zahlen, Math. Ann. 107 (1933), no. 1, 649–690 (German). MR 1512821

[13] E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975), 199–245. Collection of articles in memory of Juriĭ Vladimirovič Linnik. MR 0369312 (51 #5547)

[14] B. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wiskd. 15 (1927), 212–216.

Department of Mathematics and Computer Science, Chicago State University, Chicago, Illinois 60628,

E-mail address: adolich@csu.edu

Department of Mathematics, The Ohio State University, 231 West 18th Avenue, Columbus, OH 43210

E-mail address: miller@math.ohio-state.edu
URL: http://www.math.ohio-state.edu/~miller