Arithmetic Progressions in the Graphs of Slightly Curved Sequences

Kota Saito and Yuuya Yoshida Graduate School of Mathematics Nagoya University Furo-cho, Chikusa-ku, Nagoya, 464-8602 Japan

              m17013b@math.nagoya-u.ac.jp
              m17043e@math.nagoya-u.ac.jp

Abstract

A strictly increasing sequence of positive integers is called a slightly curved sequence with small error if the sequence can be well-approximated by a function whose second derivative goes to zero faster than or equal to 1/x^{α} for some α > 0. In this paper, we prove that arbitrarily long arithmetic progressions are contained in the graph of a slightly curved sequence with small error. Furthermore, we extend Szemerédi’s theorem to a theorem about slightly curved sequences. As a corollary, it follows that the graph of the sequence {⌊n^{a}⌋}_{n∈A} contains arbitrarily long arithmetic progressions for every 1 ≤ a < 2 and every A ⊂ ℕ with positive upper density. Using this corollary, we show that the set { ⌊⌊p^{1/b}⌋^{a}⌋ | p prime } contains arbitrarily long arithmetic progressions for every 1 ≤ a < 2 and b > 1. We also prove that, for every a ≥ 2, the graph of {⌊n^{a}⌋}_{n=1}^{∞} does not contain any arithmetic progressions of length 3.

1 Introduction

This paper considers problems involving arithmetic progressions. Let k ≥ 3 and d ≥ 1 be integers. A sequence {a(j)}_{j=0}^{k−1} ⊂ ℕ^{d} is called an arithmetic progression (AP) of length k if there exists D ∈ ℕ^{d} such that

a(j) = a(0) + jD

for all j = 0, 1, …, k−1. We discuss only the cases d = 1 and d = 2. Here, note the following two points. First, all components of the common difference D are positive, since ℕ = {1, 2, …} does not contain zero. Second, this paper addresses strictly increasing sequences alone and then regards sequences of positive integers as subsets of ℕ. That is why we denote a sequence by, say, {a(n)}_{n=1}^{∞} instead of (a(n))_{n=1}^{∞}.

APs have elicited much interest from researchers studying arithmetic combinatorics, geometric measure theory, and fractal geometry. Most studies consider the density of sets to ensure the existence of long APs. For example, we recall Szemerédi’s celebrated result:

Proposition 1 (Szemerédi [1]). For every k ≥ 3 and 0 < δ ≤ 1 there exists an integer N(k, δ) > 0 such that if N ≥ N(k, δ), then every set A ⊂ {1, 2, …, N} with |A| ≥ δN contains an AP of length k.

Here |X| denotes the cardinality of a finite set X. Furthermore, Steinhaus showed that every set with positive Lebesgue measure contains arbitrarily long APs from Lebesgue’s density theorem; for instance, see [2, Theorem 3]. These sufficient conditions are traditional and important, but it is difficult to weaken them. Hence we have found a new class of sets containing arbitrarily long APs, which is a main contribution of this paper. We call this new class slightly curved sequences, which are defined below.

Let g : ℕ → ℝ be an eventually positive function and let ℝ^{+} = (0, ∞). A strictly increasing sequence {a(n)}_{n=1}^{∞} ⊂ ℕ is called a slightly curved sequence with error O(g(n)) if there exists a twice differentiable function f : ℝ^{+} → ℝ such that

f′′(x) = O(1/x^{α}),  (1)
a(n) = f(n) + O(g(n))

for some α > 0. A slightly curved sequence with error o(g(n)) is also defined in the same way. Here the notation f(x) = O(g(x)) denotes that there exist C > 0 and x_{0} > 0 such that |f(x)| ≤ Cg(x) for all x ≥ x_{0}, where g(x) is an eventually positive function. In this paper, the constant C often depends on the length k or the exponent α in (1). When emphasizing the dependence on k or α, we write f(x) = O_{k,α}(g(x)). Also, the notation f(x) = o(g(x)) denotes that f(x)/g(x) goes to zero as x → ∞. Furthermore, to address two-dimensional APs, we define the graph of a sequence: for every A ⊂ ℕ, the graph of a sequence {a(n)}_{n∈A} ⊂ ℕ is defined as the set {(n, a(n)) ∈ ℕ^{2} | n ∈ A}.

Surprisingly, we do not impose any density conditions on sets of the above new class. Instead of density conditions, we restrict the behavior of leading terms of sequences. The first goal of this paper is to prove the following theorem:

Theorem 2. Fix an integer k ≥ 3. The graph of every slightly curved sequence with error o((log log n)^{1/c_{k}}) contains an AP of length k, where c_{k} = 2^{2^{k+9}}.

For small k, we can improve the above error term:

Theorem 3. The graph of every slightly curved sequence with error o((log n)(log log n)^{−4}) contains APs of length 3. The graph of every slightly curved sequence with error o((log n)^{c}) contains APs of length 4, where c > 0 is an absolute constant.

Theorems 2 and 3 are proved in Section 3. Since the second derivative (1) of f must vanish as x → ∞, we cannot apply Theorem 2 or 3 to the case when f is a quadratic function. To compensate this weak point, Appendix A proves another result without the assumption f′′(x) = O(1/x^{α}), which can be applied to the sequence {⌊c_{2}n^{2} + c_{1}n + c_{0}⌋}_{n=1}^{∞} with a sufficiently small c_{2} > 0.

To state the second goal of this paper, let us introduce basic notions. We say that a set A ⊂ ℕ has positive upper density if the condition

lim sup_{N→∞} \frac{|A ∩ [1, N]|}{N} > 0

holds. We also say that a set A ⊂ ℕ has positive upper Banach density if the condition

lim sup_{N→∞} \frac{max_{n≥0} |A ∩ [n + 1, n + N]|}{N} > 0

holds. If a set A ⊂ ℕ has positive upper density, then a fortiori A has also positive upper Banach density. However, the converse does not hold in general.

The second goal of this paper is to show the following result:

Theorem 4 (An extension of Szemerédi’s theorem). If {a(n)}_{n=1}^{∞} is a slightly curved sequence with error O(1) and a set A ⊂ ℕ has positive upper Banach density, then the graph of {a(n)}_{n∈A} contains arbitrarily long APs.

As a corollary, we also obtain the following result:

Corollary 5. If a set A ⊂ ℕ has positive upper Banach density, then the graph of {⌊n^{a}⌋}_{n∈A} contains arbitrarily long APs for every 1 ≤ a < 2.

Here, for every x ∈ ℝ the notation ⌊x⌋ denotes the greatest integer less than or equal to x and the notation ⌈x⌉ denotes the least integer greater than or equal to x. Corollary 5 with a = 1 is just Szemerédi’s theorem (Proposition 1). By using Corollary 5, Section 2 shows that the set { ⌊⌊p^{1/b}⌋^{a}⌋ | p prime } contains arbitrarily long APs for every 1 ≤ a < 2 and b > 1.

Proof of Corollary 5 assuming Theorem 4. Fix 1 ≤ a < 2 and let f(x) = x^{a}. Then ⌊n^{a}⌋ = f(n) + O(1). Since f′′(x) = O(1/x^{2−a}), Theorem 4 implies Corollary 5.

In particular, Corollary 5 with A = ℕ implies the following result immediately:

Corollary 6. The graph of {⌊n^{a}⌋}_{n=1}^{∞} contains arbitrarily long APs for every 1 ≤ a < 2.

When a > 1 and a ∉ ℕ, the sequences {⌊n^{a}⌋}_{n=1}^{∞} are called Piatetski-Shapiro sequences. Hence Corollary 6 implies that the Piatetski-Shapiro sequence with every exponent 1 < a < 2 contains arbitrarily long APs. Piatetski-Shapiro sequences are named after Piatetski-Shapiro [3], who proved that for every 1 < a < 12/11 the sequence {⌊n^{a}⌋}_{n=1}^{∞} contains infinitely many primes. It is known that the range 1 < a < 12/11 can be improved to 1 < a < 243/205 [4]. Many preceding studies considered prime numbers contained in Piatetski-Shapiro sequences. For instance, Mirek [5] proved that for every 1 < a < 72/71 the set of all primes of the form ⌊n^{a}⌋ contains an AP of length 3. Recently, Li and Pan [6] claimed that for every integer k ≥ 3 there exists a_{k} > 1 such that for every 1 < a < a_{k} the set of all primes of the form ⌊n^{a}⌋ contains an AP of length k. Although this paper considers Piatetski-Shapiro sequences, prime numbers are not our main topic. Remark 7. When a > 1, the sum of the reciprocals of {⌊n^{a}⌋}_{n=1}^{∞} converges:

∑_{n=2}^{∞} \frac{1}{⌊n^{a}⌋} ≤ ∑_{n=2}^{∞} \frac{1}{n^{a} − 1} ≤ ∑_{n=2}^{∞} \frac{2}{n^{a}} < ∞.

Thus we cannot apply the Erdős-Turán conjecture to this sequence. Here the Erdős-Turán conjecture asserts that every subset of positive integers whose sum of reciprocals diverges must contain arbitrarily long APs [7]. Since the sum of the reciprocals of all primes diverges, the Erdős-Turán conjecture implies that the set of all primes contains arbitrarily long APs. Green and Tao [8] proved that the set of all primes contains arbitrarily long APs, but the Erdős-Turán conjecture is still open even in the case when the length of an AP is three. The Erdős-Turán conjecture is a strong statement that implies the result by Green and Tao; nevertheless, it does not imply Corollary 6 directly.

Corollary 6 ensures that the graph of {⌊n^{a}⌋}_{n=1}^{∞} with 1 ≤ a < 2 contains arbitrarily long APs, but the graph of {⌊n^{a}⌋}_{n=1}^{∞} with a ≥ 2 does not contain any APs of length 3, which is proved in Section 6. Hence the graph of {n^{2}}_{n=1}^{∞} does not contain any APs of length 3, while the sequence {n^{2}}_{n=1}^{∞} (not the graph) contains APs of length 3, e.g., {1, 25, 49}. However, there are not any APs of length 4 in {n^{2}}_{n=1}^{∞}, which was proposed by Fermat in 1640 and first shown by Euler in 1780, according to Dickson’s book [9, pp. 440 and 635]. Euler also showed that there are not any APs of length 3 in {n^{3}}_{n=1}^{∞}, according to [9, pp. 572–573]. Moreover, Dénes [10] showed that for every integer 3 ≤ a ≤ 30 there are not any APs of length 3 in {n^{a}}_{n=1}^{∞}. Finally, for every integer a ≥ 3, Darmon and Merel [11] showed that {n^{a}}_{n=1}^{∞} contains no APs of length 3. We do not know whether {⌊n^{a}⌋}_{n=1}^{∞} would contain long APs if a > 2 is not an integer. One might guess that such a sequence would not contain APs, but the following sequences are APs of length 4:

{⌊2^{2.2}⌋, ⌊11^{2.2}⌋, ⌊15^{2.2}⌋, ⌊18^{2.2}⌋},
{⌊14^{2.655015}⌋, ⌊39^{2.655015}⌋, ⌊50^{2.655015}⌋, ⌊58^{2.655015}⌋},
{⌊27^{2.720398}⌋, ⌊89^{2.720398}⌋, ⌊114^{2.720398}⌋, ⌊132^{2.720398}⌋}.

In the course of this study, we proved a result in Appendix B, which is that the graph of {⌊f(n)⌋}_{n=1}^{∞} contains an AP of length 4 if a function f : ℕ → ℝ^{+} satisfies Δf > 0, Δ^{2}f ≥ 0, and lim inf_{n→∞} f(n)/n^{2} < 1/18, where Δ denotes the difference operator which is defined in Section 3. This result can be applied to the sequence {⌊c_{2}n^{2} + c_{1}n + c_{0}⌋}_{n=1}^{∞} with 0 < c_{2} < 1/18, but Theorem 2 or 3 cannot be applied.

2 Warming up

As an application of Corollary 5, this section shows that the set { ⌊⌊p^{1/b}⌋^{a}⌋ | p prime } contains arbitrarily long APs for every 1 ≤ a < 2 and b > 1. Once we put A = { ⌊p^{1/b}⌋ | p prime }, the above set can be expressed as { ⌊⌊p^{1/b}⌋^{a}⌋ | p prime } = {⌊n^{a}⌋}_{n∈A}. Thus, if A has positive upper density, the above statement follows from Corollary 5. Let us verify that A has positive upper density. Let π(x) be the number of primes less than or equal to x > 0 and π̃(S) be the number of primes contained in a set S ⊂ ℝ^{+}. Then every x > 0 satisfies

|A ∩ [1, x]| = |{ ⌊p^{1/b}⌋ ≤ x | p prime }|

≥ \frac{|\{ p ≤ x^{b} | p prime \}|}{max_{n≤x} π̃[n^{b}, (n + 1)^{b})} ≥ \frac{π(x^{b})}{max_{n≤x} π̃[n^{b}, (n + 1)^{b}]}.

Since there exists y_{0} > 0 such that every x > 0 and y ≥ y_{0} satisfy π̃[x, x + y] ≤ 3y/ log y [12, Corollary 3.4], the denominator π̃[n^{b}, (n+1)^{b}] of the above right-hand side is upper bounded as

π̃[n^{b}, (n + 1)^{b}] ≤^{(i)} max_{n≤x} π̃[n^{b}, n^{b} + b(n + 1)^{b−1}]

≤ max_{n≤x} π̃[n^{b}, n^{b} + b(x + 1)^{b−1}] ≤^{(ii)} \frac{3b(x + 1)^{b−1}}{log(b(x + 1)^{b−1})}

for every x ≥ (y_{0}/b)^{1/(b−1)} − 1, where (i) and (ii) follow from the mean value theorem and [12, Corollary 3.4], respectively. We now use the prime number theorem [12, Chapter 6]: π(x) ∼ x/ log x, where the notation f(x) ∼ g(x) denotes that f(x)/g(x) goes to one as x → ∞. Therefore, the prime number theorem yields

\frac{|A ∩ [1, x]|}{x} ≥ π(x^{b})/x\frac{3b(x + 1)^{b−1}}{log(b(x + 1)^{b−1})}

∼ \frac{x^{b}}{b log x}/x\frac{3b(x + 1)^{b−1}}{(b − 1) log(x + 1)} ∼ \frac{b − 1}{3b^{2}} > 0 (x → ∞),

whence A has positive upper density.

As a special case of the above result, it follows that the set { ⌊⌊p^{1/b}⌋^{b}⌋ | p prime } contains arbitrarily long APs for every 1 < b < 2. However, the case b = 1, i.e., the Green-Tao theorem [8] would not be proved by the above method. This is because the set { ⌊p^{1/b}⌋ | p prime, |⌊p^{1/b}⌋^{b} − p| ≤ C } has probably upper density zero for every 1 < b < 2 and C > 0.

3 More general statement than Theorems 2 and 3

In order to prove Theorems 2 and 3, this section introduces another proposition which is proved in Section 4. This proposition uses a function satisfying three properties below. Before stating them, let us define the van der Waerden numbers [13]. For every k ≥ 3 and r ≥ 2, the van der Waerden number W (r, k) is the smallest number N such that if {1, 2, …, N} are partitioned into r different sets then there exists at least one set which contains an AP of length k. Fix an integer k ≥ 3. This section considers a function U_{k} satisfying the following properties:

(U1) there exist x_{k} ≥ 1 and y_{k} ≥ 1 such that a function U_{k} : [x_{k}, ∞) → [y_{k}, ∞) is increasing and bijective;

(U2) U_{k}(r^{α}) = O_{k,α}(U_{k}(r)) for all α > 0;

(U3) the inverse function U_{k}^{−1} of U_{k} satisfies W (r, k) = O_{k}(U_{k}^{−1}(r)).

Using such a function U_{k}, we obtain the following proposition:

Proposition 8. Fix an integer k ≥ 3. Assume that a function U_{k} satisfies (U1), (U2), and (U3). If {a(n)}_{n=1}^{∞} is a slightly curved sequence with error o(U_{k}(n)), then there exists an arithmetic progression P of length k such that a(P) is also an arithmetic progression of length k.

The proof of Theorem 2 uses the function U_{k}(r) = (log log r)^{1/c_{k}} with c_{k} = 2^{2^{k+9}}. Similarly, the proof of Theorem 3 uses the functions U_{3}(r) = C_{3}^{−1}(log r)(log log r)^{−4} and U_{4}(r) = C_{4}^{−1}(log r)^{c} for some C_{3}, C_{4} > 0 and some absolute constant c > 0. Thus Theorems 2 and 3 are special cases of Proposition 8. To prove Theorem 2 by assuming Proposition 8, we need to use upper bounds of the van der Waerden numbers. As such upper bounds, Gowers’ upper bounds [14, Theorem 18.6] are known:

W (r, k) ≤ 2^{2^{r^{c_{k}}}} , c_{k} = 2^{2^{k+9}}.  (2)

For general r and k, Gowers’ upper bounds are best at present.

Proof of Theorem 2 assuming Proposition 8. Fix an integer k ≥ 3. Let U_{k}(r) = (log log r)^{1/c_{k}} with c_{k} = 2^{2^{k+9}}. It is enough to show that the function U_{k} satisfies (U1), (U2), and (U3). The properties (U1) and (U2) follow from the definition of U_{k}. Also, Gowers’ upper bound (2) implies that the function U_{k} satisfies W (r, k) ≤ exp(exp(r^{c_{k}})) = U_{k}^{−1}(r), which is just (U3).

Next, to prove Theorem 3 by assuming Proposition 8, we introduce the notation r_{k}(N) [7]. The notation r_{k}(N) is the maximum cardinality of all subsets of {1, 2, …, N} that contain no APs of length k. For k = 3, 4, the following upper bounds of r_{k}(N) are known [15, Theorem 1.1], [16, Theorem 1.1]:

r_{3}(N) = O(\frac{N}{(log N)(log log N)^{−4}} ), r_{4}(N) = O(\frac{N}{(log N)^{c}} )  (3)

for some absolute constant c > 0. As explained below, the upper bounds (3) correspond to upper bounds of the van der Waerden numbers W (r, k) with k = 3, 4, which are better than Gowers’ upper bounds (2).

Proof of Theorem 3 assuming Proposition 8. First, we show that if a function U_{k} satisfies (U1) and

r_{k}(N) < N/U_{k}(N) (N ≥ x_{k})  (4)

then the function U_{k} satisfies (U3). Due to (U1), there exists r_{k} > 0 such that every r ≥ r_{k} satisfies U_{k}^{−1}(r) ≥ 1. Let r ≥ r_{k} be an integer and let N = ⌈U_{k}^{−1}(r)⌉. The definition of N yields N = ⌈U_{k}^{−1}(r)⌉ ≥ U_{k}^{−1}(r) and then (U1) does U_{k}(N) ≥ r. Take an arbitrary partition of {1, 2 …, N} into r small sets. Then the pigeonhole principle implies that there exists a set A consisting of at least ⌈N/r⌉ elements. Thus A contains an AP of length k because the inequality

|A| ≥ ⌈N/r⌉ ≥ N/r ≥^{(i)} N/U_{k}(N) >^{(4)} r_{k}(N)

holds, where (i) follows from U_{k}(N) ≥ r. Since the partition of {1, 2 …, N} is arbitrary, the van der Waerden number W (r, k) is upper bounded by N. Thus it follows that

W (r, k) ≤ N ≤ U_{k}^{−1}(r) + 1 ≤ 2U_{k}^{−1}(r)

from the definition of N and (U1). Therefore, the function U_{k} satisfies (U3).

Next, using the result in the previous paragraph, we show Theorem 3. The upper bounds (3) imply that there exist constants C_{3}, C_{4} > 0 such that

r_{3}(N) < C_{3} · \frac{N}{(log N)(log log N)^{−4}} , r_{4}(N) < C_{4} · \frac{N}{(log N)^{c}}

for every sufficiently large N. If taking the functions U_{3}(N) = C_{3}^{−1}(log N)(log log N)^{−4} and U_{4}(N) = C_{4}^{−1}(log N)^{c}, the inequality (4) holds for k = 3 and k = 4, respectively. Since the functions U_{3} and U_{4} satisfy (U1) and (U2), the result in the previous paragraph implies that the functions U_{3} and U_{4} also satisfy (U3). Therefore, Proposition 8 implies Theorem 3.

4 Proof of Proposition 8

This section proves Proposition 8. Before proving Proposition 8, let us define a semi-norm on the vector space F = {f | f : ℝ^{+} → ℝ}. Let k ≥ 3 be an integer and P = {b(j)}_{j=0}^{k−1} ⊂ ℝ^{+} be a strictly increasing sequence. We define

N_{P} (f) = ∑_{j=0}^{k−3} |Δ^{2}[f ∘ b](j)| ,

for every f ∈ F, where Δ denotes the difference operator, that is,

Δf(x) = f(x + 1) − f(x),

and Δ^{2} := Δ ∘ Δ. We can find that N_{P} satisfies the following properties:

(N1) for every strictly increasing function f ∈ F,

N_{P} (f) = 0 if and only if f(P) is an AP of length k;

(N2) N_{P} (f) ≥ 0 for all f ∈ F;

(N3) N_{P} (f + g) ≤ N_{P} (f) + N_{P} (g) for all f, g ∈ F.

All the properties above can be easily checked from the definition.

Proof of Proposition 8. Fix an integer k ≥ 3 and take an arbitrary slightly curved sequence {a(n)}_{n=1}^{∞} with error o(U_{k}(n)): there exists a twice differentiable function f : ℝ^{+} → ℝ satisfying (1) and a(n) = f(n) + o(U_{k}(n)). Let r be a sufficiently large positive integer. We define W (r) = W (r, k), R(n) = a(n) − f(n), and

A(r) = { m ∈ ℕ | ⌊W (r)^{3/α}⌋ ≤ m < ⌊W (r)^{3/α}⌋ + W (r) } .

Then every m ∈ A(r) satisfies

R(m) = o(U_{k}(2W (r)^{max{3/α,1}})) = o(U_{k}(U_{k}^{−1}(r))) = o(r)

thanks to (U1), (U2), and (U3). Thus there exists a positive function δ(r) such that

R(m) ∈ [−δ(r), δ(r))

for all m ∈ A(r), and

δ(r) = o(r)  (5)

as r → ∞. We also define

I_{j} = [−δ(r) + \frac{2δ(r)}{r}j, −δ(r) + \frac{2δ(r)}{r}(j + 1)), A_{j}(r) = \{m ∈ A(r) | R(m) ∈ I_{j}\}

for all j = 0, 1, …, r − 1. Note that the union of all the small sets A_{j}(r) equals A(r). From the definition W (r) = W (r, k), it follows that there exists an integer q ∈ {0, 1, …, r − 1} such that A_{q}(r) contains an arithmetic progression P = {b(j)}_{j=0}^{k−1} of length k. Here b(j) is expressed as b(j) = dj + e with two integers d, e > 0. Since every j = 0, 1, …, k − 1 satisfies b(j) ∈ A(r), we obtain

d ≤ W (r), ⌊W^{3/α}(r)⌋ ≤ e.  (6)

Then the triangle inequality (N3) implies N_{P} (a) ≤ N_{P} (f) + N_{P} (R).

Finally, we show that N_{P} (a) = o(1) as r → ∞, which follows from the two relations N_{P} (f) = o(1) and N_{P} (R) = o(1). Since we have (5) and b(j) ∈ A_{q}(r) for all j = 0, 1, …, k−1, the inequality

N_{P} (R) ≤ ∑_{j=0}^{k−3}(|Δ[R ∘ b](j + 1)| + |Δ[R ∘ b](j)|) ≤ \frac{4(k − 2)δ(r)}{r} = o(1)

holds as r → ∞. Hence the remaining is to show that N_{P} (f) = o(1) as r → ∞. The mean value theorem implies that for every j = 0, 1, …, k − 3 there exist θ_{j}, η_{j} ∈ (0, 1) such that

Δ^{2}[f ∘ b](j) = Δ[f ∘ b](j + 1) − Δ[f ∘ b](j) = (Δ[f ∘ b])′(j + θ_{j})
= d{f′ ∘ b(j + θ_{j} + 1) − f′ ∘ b(j + θ_{j})} = d^{2}f′′ ∘ b(j + θ_{j} + η_{j}),

where b(x) := dx + e. Since (6) and the assumption f′′(x) = O(1/x^{α}) hold, every j = 0, 1, …, k − 3 satisfies

Δ^{2}[f ∘ b](j) = d^{2}f′′(d(j + θ_{j} + η_{j}) + e) = O(W (r)^{2} · \frac{1}{W (r)^{3}} ) = o(1)

as r → ∞, whence N_{P} (f) = o(1) as r → ∞. Therefore, a sufficiently large integer r > 0 satisfies N_{P} (a) < 1. Since N_{P} (a) is a non-negative integer from the definition, the equation N_{P} (a) = 0 holds, which implies that a(P) is also an AP of length k due to (N1).

5 Proof of Theorem 4

This section considers, for every α > 0, whether the set A ∩ (h_{α}(x), h_{α}(x + 1)] contains an AP or not, which is useful to prove Theorem 4. Here h_{α} is a function satisfying the following properties:

(H1) h_{α} is a differentiable function defined on the interval (x_{0}, ∞) for some x_{0} > 0;

(H2) there exists a positive number x_{1} ≥ x_{0} such that h_{α} and h′_{α} strictly increase on the interval (x_{1}, ∞);

(H3) lim_{x→∞} h′_{α}(x + 1)^{2}/h_{α}(x)^{α} = 0;

(H4) lim_{x→∞} h′_{α}(x) = ∞.

For example, the function h_{α}(x) = x log x satisfies the above three properties. As another example, we can take the function h_{α}(x) = x^{1+α/2}. The latter example is used in Appendix A. In order to prove Theorem 4, we introduce the following condition for a set A ⊂ ℕ:

(C) for every integer k ≥ 3 and every α > 0, there exist a function h_{α} satisfying (H1)–(H3) and a strictly increasing sequence {x_{n}}_{n=1}^{∞} ⊂ ℝ^{+} which diverges such that for every integer n > 0 the set A ∩ (h_{α}(x_{n}), h_{α}(x_{n} + 1)] contains an AP of length k.

Theorem 4 follows from the following proposition and preliminary lemma.

Proposition 9. Let A be a subset of positive integers with (C), and {a(n)}_{n=1}^{∞} be a slightly curved sequence with error O(1). Then the graph of {a(n)}_{n∈A} contains arbitrarily long APs.

Proof. Let k ≥ 3 be an integer. There exists a twice differentiable function f : ℝ^{+} → ℝ satisfying (1) and a(n) = f(n) + O(1). Defining R(n) = a(n) − f(n), we can take an integer M satisfying |R(n)| < M. Put r = 4kM. Then (C) implies that there exist a function h_{α} satisfying (H1)–(H3) and a strictly increasing sequence {x_{n}}_{n=1}^{∞} ⊂ ℝ^{+} which diverges such that for every integer n > 0 the set A∩(h_{α}(x_{n}), h_{α}(x_{n}+1)] contains an AP of length W (r, k). Let P (n) be such an AP of length W (r, k). Then we define the following sets:

I_{j} = [−M + \frac{2M}{r} j, −M + \frac{2M}{r} (j + 1)) (0 ≤ j ≤ r − 1),

A_{j}(n) = { m ∈ P (n) | R(m) ∈ I_{j} } (0 ≤ j ≤ r − 1).

Since the union of all the small sets A_{j}(n) equals P (n), for some 0 ≤ q ≤ r − 1 the set A_{q}(n) contains an arithmetic progression P̃ = {b(j)}_{j=0}^{k−1}. Here b(j) is expressed as b(j) = dj + e with two integers d, e > 0. For every sufficiently large n the inequality d ≤ h_{α}(x_{n} + 1) − h_{α}(x_{n}) ≤ h′_{α}(x_{n} + 1) holds due to (H2), and the inequality e ≥ h_{α}(x_{n}) also holds. Thus every sufficiently large n satisfies

\begin{aligned}NP̃(f) & = ∑_{j=0}^{k−3} |Δ^{2}[f ∘ b](j)| = ∑_{j=0}^{k−3} d^{2} |f′′(d(j + θ_{j} + η_{j}) + e)| \\ & = O(\frac{h′_{α}(x_{n} + 1)^{2}}{h_{α}(x_{n})^{α}} ) = o(1), \end{aligned}  (7)

where the last equality follows from (H3) and the values θ_{j} = θ_{j}(d, e) and η_{j} = η_{j}(d, e) are real numbers satisfying θ_{j}, η_{j} ∈ (0, 1). Moreover, the relation P̃ ⊂ A_{q}(n) implies

\begin{aligned}NP̃(R) & = ∑_{j=0}^{k−3} |Δ^{2}[R ∘ b](j)| ≤ ∑_{j=0}^{k−3}(|Δ[R ∘ b](j + 1)| + |Δ[R ∘ b](j)|) \\ & ≤ 2(k − 2)\frac{2M}{r} = 1 − 2/k. \end{aligned}  (8)

Hence a sufficiently large integer n satisfies NP̃(f) < 2/k. The inequality NP̃(a) < 1 follows from (7) and (8). Since NP̃(a) is a non-negative integer, the equation NP̃(a) = 0 follows: a(P̃) is an AP of length k. Therefore, the graph of {a(n)}_{n∈A} contains an AP of length k.

Lemma 10. If a set A ⊂ ℕ has positive upper Banach density, then there exists a function h = h_{α} (to be independent of α) satisfying (H1)–(H4), and

lim sup_{x→∞} \frac{|A ∩ (h(x), h(x + 1)]|}{|ℕ ∩ (h(x), h(x + 1)]|} > 0.

Proof. Step 1. For each integer N > 0, we take a non-negative integer F (N) satisfying

max_{n≥0} |A ∩ [n + 1, n + N]| = |A ∩ [F (N) + 1, F (N) + N]|

and then define the functions F_{max} : [0, ∞) → [0, ∞) and F̃ : [0, ∞) → [0, ∞) as follows:

F_{max}(x) = (N + 1 − x) max_{1≤n≤N} F (n) + (x − N) max_{1≤n≤N+1} F (n)
(N ∈ ℕ ∪ {0}, N ≤ x < N + 1),
F̃(x) = xe^{x}(F_{max}(x) + 1),

where max_{1≤n≤x} F (n) = 0 for all 0 ≤ x < 1. Note that F_{max} is continuous and satisfies F_{max}(N) = max_{1≤n≤N} F (n). Thus F̃ is continuous and satisfies the following properties:

1. F (N) + 1 ≤ F̃(N) for all N ∈ ℕ;

2. F̃(x) ≥ e^{x} for all x ≥ 1;

3. F̃(2x) ≥ 2F̃(x) for all x ≥ 0;

4. F̃ : [0, ∞) → [0, ∞) is a homeomorphism and satisfies F̃(0) = 0 and lim_{x→∞} F̃(x) = ∞. Using this function, we define the function h : [0, ∞) → [0, ∞) as

h(x) = ∫_{0}^{x} F̃^{−2}(y) dy,

where F̃^{−2} := F̃^{−1}∘F̃^{−1}, and F̃^{−1} denotes the inverse function of F̃. Since F̃^{−2} is continuous, the function h is continuously differentiable. Also, h satisfies (H1) and (H2). Step 2. To prove that h satisfies (H3), we show the following facts:

1. h(2x) ≤ 4h(x) for all x ≥ 0;

2. h(x) ≤ x log x for every sufficiently large x;

3. xh′(x) ≤ 4h(x) for all x ≥ 0;

4. h^{−1}(x) ≤ x for all x ≥ F̃^{2}(2), where F̃^{2} := F̃ ∘ F̃. First, thanks to property 3 in Step 1, every y ≥ 0 satisfies 2F̃^{−1}(y) ≥ F̃^{−1}(2y). Therefore, every x ≥ 0 satisfies

h(2x) = ∫_{0}^{2x} F̃^{−2}(y) dy = 2 ∫_{0}^{x} F̃^{−2}(2y) dy ≤ 4 ∫_{0}^{x} F̃^{−2}(y) dy = 4h(x),

which is just fact 1. Second, thanks to property 2 in Step 1, every y ≥ F̃(1) satisfies F̃^{−1}(y) ≤ log y. Therefore, every sufficiently large x satisfies

h(x) = ∫_{F̃^{2}(1)}^{x} F̃^{−2}(y) dy + O(1) ≤ ∫_{F̃^{2}(1)}^{x} log log y dy + O(1) ≤ x log log x ≤ x log x,

which is just fact 2. Third, fact 3 is verified as follows:

xh′(x) ≤ ∫_{x}^{2x} h′(y) dy ≤ h(2x) ≤ 4h(x),

where the last inequality follows from fact 1. Fourth, every x ≥ F̃^{2}(2) satisfies

h(x) ≥ ∫_{F̃^{2}(2)}^{x} F̃^{−2}(y) dy ≥ ∫_{F̃^{2}(2)}^{x} 2 dy = 2(x − F̃^{2}(2)) ≥ x,

which implies fact 4. Step 3. We show that h satisfies (H3) for every α > 0. Facts 1 and 3 and (H2) imply

\frac{h′(x + 1)^{2}}{h(x)^{α}} ≤ \frac{h′(2x)^{2}}{h(x)^{α}} ≤ (\frac{4h(2x)}{2x})^{2} \frac{1}{h(x)^{α}} ≤ (\frac{8h(x)}{x})^{2} \frac{1}{h(x)^{α}} = \frac{8^{2}h(x)^{2−α}}{x^{2}} .  (9)

If α ≥ 2, the right-hand side in (9) goes to zero as x → ∞. If 0 < α < 2, fact 2 in Step 2 implies

\frac{h(x)^{2−α}}{x^{2}} ≤ \frac{(x log x)^{2−α}}{x^{2}} = \frac{(log x)^{2−α}}{x^{α}} ⟶^{x→∞} 0.

Therefore, the function h satisfies (H3). Step 4. Assuming

lim sup_{x→∞} \frac{|A ∩ (h(x), h(x + 1)]|}{|ℕ ∩ (h(x), h(x + 1)]|} = 0,

we now deduce a contradiction. This assumption implies that for every 0 < ε < 1/4 there exists x_{0} > 0 such that every x ≥ x_{0} satisfies

|A ∩ (h(x), h(x + 1)]| ≤ ε|ℕ ∩ (h(x), h(x + 1)]|.

We consider only the case when N is sufficiently large below. If F (N) + 1 ≤ h(x_{0}), letting l = ⌈h^{−1}(F (N) + N) − x_{0}⌉, we have

|A ∩ [F (N) + 1, F (N) + N]|

≤ |A ∩ [F (N) + 1, h(x_{0})]| + ∑_{j=1}^{l} |A ∩ (h(x_{0} + j − 1), h(x_{0} + j)]|

≤ h(x_{0}) − F (N) + ε|ℕ ∩ (h(x_{0}), h(x_{0} + l)]| ≤ εh(x_{0} + l) − F (N) + O(1)

≤ εh(h^{−1}(F (N) + N) + 1) − F (N) + O(1) ≤ εh(2h^{−1}(F (N) + N)) − F (N) + O(1)

≤^{(i)} 4ε(F (N) + N) − F (N) + O(1) = 4εN − (1 − 4ε)F (N) + O(1) ≤ 4εN + O(1), (10)

where (i) follows from fact 1 in Step 2. If F (N) + 1 > h(x_{0}), taking a positive number x_{1} and a positive integer l with h(x_{1}) = F (N) + N and h(x_{1} − l) < F (N) + 1 ≤ h(x_{1} − l + 1), we have

|A ∩ [F (N) + 1, F (N) + N]| ≤ |A ∩ (h(x_{1} − l), h(x_{1})]|

≤ ∑_{j=1}^{l} |A ∩ (h(x_{1} − j), h(x_{1} − j + 1)]|

≤ ε|ℕ ∩ (h(x_{1} − l), h(x_{1})]| ≤ ε{h(x_{1}) − h(x_{1} − l)}

≤ ε{F (N) + N − h(h^{−1}(F (N) + 1) − 1)}

≤^{(ii)} ε{F (N) + N − (F (N) + 1) + h′(h^{−1}(F (N) + 1))}

≤ ε{N + h′(h^{−1}(F (N) + 1))} =^{(iii)} εN + o(N).  (11)

We verify the above (ii) and (iii). First, the mean value theorem and (H2) imply

h(x − 1) ≥ h(x) − h′(x)

for every x ≥ 1. Putting x = h^{−1}(F (N) + 1), we obtain the inequality (ii). Next, in order to prove (iii), we show

lim_{x→∞} \frac{(h′ ∘ h^{−1} ∘ F̃ ∘ h′)(x)}{h′(x)} = 0.  (12)

Using h′(x) = F̃^{−2}(x), we obtain

\frac{(h′ ∘ h^{−1} ∘ F̃ ∘ h′)(x)}{h′(x)} = \frac{(h′ ∘ h^{−1} ∘ F̃^{−1})(x)}{h′(x)}

≤^{(iv)} \frac{(h′ ∘ F̃^{−1})(x)}{h′(x)} = \frac{F̃^{−3}(x)}{F̃^{−2}(x)} ≤^{(v)} \frac{log F̃^{−2}(x)}{F̃^{−2}(x)} ⟶^{x→∞} 0,

where (iv) and (v) follow from fact 4 in Step 2 and property 2 in Step 1, respectively. From property 1 in Step 1, (H2), and (12), it follows immediately that

\frac{h′(h^{−1}(F (N) + 1))}{N} ≤ \frac{h′(h^{−1}(F̃(N)))}{N} ⟶^{N→∞} 0,

which is just (iii).

Summarizing the above two cases (10) and (11), we have

lim sup_{N→∞} \frac{max_{n≥0} |A ∩ [n + 1, n + N]|}{N} = lim sup_{N→∞} \frac{|A ∩ [F (N) + 1, F (N) + N]|}{N} ≤ 4ε.

Since 0 < ε < 1/4 is arbitrary, the set A does not have positive upper Banach density, which is a contradiction.

Proof of Theorem 4. Thanks to Proposition 9, it is enough to show that every set A ⊂ ℕ with positive upper Banach density satisfies (C). Let k ≥ 3 be an integer. Lemma 10 implies that there exist a function h = h_{α} (to be independent of α) satisfying (H1)–(H4) and a positive number δ ≤ 1 such that

lim sup_{x→∞} \frac{|A ∩ (h(x), h(x + 1)]|}{|ℕ ∩ (h(x), h(x + 1)]|} = δ.

This equation implies that there exists a strictly increasing sequence {x_{n}}_{n=1}^{∞} ⊂ ℝ^{+} which diverges such that every integer n > 0 satisfies

|A ∩ (h(x_{n}), h(x_{n} + 1)]| ≥ \frac{δ}{2}|ℕ ∩ (h(x_{n}), h(x_{n} + 1)]|.

We can take an integer n_{0} > 0 satisfying h′(x_{n_{0}}) ≥ N(δ/2, k) due to (H4). Since the mean value theorem implies h(x_{n} + 1) − h(x_{n}) ≥ h′(x_{n}) for all n ∈ ℕ, every integer n ≥ n_{0} satisfies

h(x_{n} + 1) − h(x_{n}) ≥ h′(x_{n}) ≥ h′(x_{n_{0}}) ≥ N(δ/2, k).

Thus Proposition 1 implies that the set A ∩ (h(x_{n}), h(x_{n} + 1)] with n ≥ n_{0} contains an AP of length k. Therefore, every A ⊂ ℕ with positive upper Banach density satisfies (C).

6 Future work

Question 11. Suppose that a twice differentiable function f : ℝ^{+} → ℝ satisfies (1). If a strictly increasing sequence {a(n)}_{n=1}^{∞} ⊂ ℕ can be written as

a(n) = f(n) + O(f′(n)),

then does the sequence {a(n)}_{n=1}^{∞} contain arbitrarily long arithmetic progressions?

We do not know the answer to this question, but it is affirmative when the coefficients of the error term O(f′(n)) are contained in a finite set {c_{1}, c_{2}, …, c_{m}}. See Appendix C. Hence Question 11 is probably affirmative. As a question related to Question 11, we are interested in how large the error term can be taken. In particular, we do not know whether the error term O(f′(n)) is best or not.

Next, we remark that the sequence of all primes is a slightly curved sequence: the asymptotic expansion [17]

p_{n} = f(n) + o(\frac{n}{log n})

holds. Here p_{n} is the n-th prime and the function f(x) is

x{log x + log log x − 1 + (log log x − 2)/ log x},

which satisfies f′′(x) = O(1/x). Thus {p_{n}}_{n=1}^{∞} is a slightly curved sequence with error o(n/ log n). If we can improve the error term O((log log n)^{1/c_{k}}) in Theorem 2 to o(n/ log n), the set of all primes contains arbitrarily long arithmetic progressions, which was shown by Green and Tao [8]. If assuming the Riemann hypothesis, the evaluation

|p_{n} − li^{−1}(n)| ≤ \frac{1}{π} \sqrt{n}(log n)^{5/2}

holds [18, Theorem 6.1], where li^{−1}(x) is the inverse function of the logarithmic integral function li(x). Thus \{p_{n}\}_{n=1}^{∞} is a slightly curved sequence with error O(\sqrt{n}(log n)^{5/2}) if assuming the Riemann hypothesis.

Question 12. Does the set of all primes satisfy (C)? In particular, does the graph of {a(p)}_{p prime} contains arbitrarily long arithmetic progressions if {a(n)}_{n=1}^{∞} is a slightly curved sequence with error O(1)?

Since the set of all primes does not have positive upper Banach density [12, Corollary 3.4], we can not apply Theorem 4 to {a(p)}_{p prime}. Nevertheless, we can answer this question if replacing p with li^{−1}(n) + O(1). See Theorem 17.

Question 13. Is it true that

sup { a ≥ 1 | the sequence {⌊n^{a}⌋}_{n=1}^{∞} contains arbitrarily long APs } = 2?

Instead of answering this question, we show that the graph of {⌊n^{a}⌋}_{n=1}^{∞} with a ≥ 1 contains an AP of length 3 if and only if 1 ≤ a < 2. The if part follows from Corollary 6. We show the only if part, i.e., the graph of {⌊n^{a}⌋}_{n=1}^{∞} with a ≥ 2 does not contain any APs of length 3 by contradiction. Suppose that a sequence {⌊(e + dj)^{a}⌋}_{j=0}^{2} is an AP for some two integers d, e > 0 and some a ≥ 2. Then the inequality |(e + 2d)^{a} + e^{a} − 2(e + d)^{a}| < 2 holds. The mean value theorem implies that

(e + 2d)^{a} + e^{a} − 2(e + d)^{a} = d^{2}a(a − 1)(e + dθ + dη)^{a−2},

where θ and η are real numbers satisfying θ, η ∈ (0, 1). Thus it follows that

2 > |(e + 2d)^{a} + e^{a} − 2(e + d)^{a}| = d^{2}a(a − 1)(e + dθ + dη)^{a−2} ≥ 2,

which is a contradiction.

The above argument implies

sup { a ≥ 1 | the graph of {⌊n^{a}⌋}_{n=1}^{∞} contains an AP of length 3 } = 2,

but we do not achieve the answer to Question 13.

7 Acknowledgments

KS is financially supported by Yoshida Scholarship Foundation. YY is grateful to Seunghoan Song for providing many helpful comments for this paper.

A Slightly curved sequences without the assumption f′′(x) = O(1/x^{α})

As stated in Section 1, Theorem 2 requires the assumption f′′(x) = O(1/x^{α}) for some α > 0. This appendix addresses a slightly curved sequence with error O(1) without this assumption. First, the following theorem holds:

Theorem 14. Let f be a twice differentiable function satisfying lim_{x→∞} f′′(x) = 0 and {a(n)}_{n=1}^{∞} ⊂ ℕ be a strictly increasing sequence satisfying a(n) = f(n) + O(1). Then the graph of {a(n)}_{n=1}^{∞} contains arbitrarily long APs.

Of course, Theorem 2 does not completely contain Theorem 14. For example, the function f(x) = ∫_{2}^{x} Li(t) dt satisfies the assumption in Theorem 14 but does not satisfy the assumption in Theorem 2 because f′′(x) = 1/ log x. Here Li(t) is the offset logarithmic integral function, i.e., Li(t) := ∫_{2}^{t}(1/ log s) ds. Theorem 14 is derived from Theorem 15 below immediately, which is more exact. For example, when length k is given, Theorem 15 implies that the graph of {⌊c_{2}n^{2} + c_{1}n + c_{0}⌋}_{n=1}^{∞} with a sufficiently small c_{2} > 0 contains an AP of length k, but Theorem 14 does not imply this statement.

Theorem 15. Let k ≥ 3 and r ≥ 1 be integers, f be a twice differentiable function, R(n) be a bounded function satisfying M_{1} ≤ R(n) ≤ M_{2} for some two real numbers M_{1} and M_{2}, and {a(n)}_{n=1}^{∞} ⊂ ℕ be a strictly increasing sequence satisfying a(n) = f(n) + R(n). If the inequality

lim sup_{x→∞} |f′′(x)| < (\frac{k − 1}{W (r, k) − 1})^{2}(\frac{1}{k − 2} − \frac{2(M_{2} − M_{1})}{r})  (13)

holds, then the graph of {a(n)}_{n=1}^{∞} contains an AP of length k.

In general, the van der Waerden number W (r, k) is large and thus the effect of the factor W (r, k) is larger than that of the other factors of the right-hand side in (13). Hence W (r, k) should be small in order to make the right-hand side in (13) large. To make W (r, k) smallest, we should make r smallest. If the right-hand side in (13) is positive, the smallest integer r > 0 is

r = ⌊2(M_{2} − M_{1})(k − 2)⌋ + 1 > 2(M_{2} − M_{1})(k − 2).  (14)

Thus the integer r with (14) makes W (r, k) smallest. Let us use (14). When M_{2} − M_{1} = 1 and k = 3, the right-hand side in (13) with (14) equals 1/(3 · 13^{2}) because r = 3 and W (3, 3) = 27 [19].

Proof. Thanks to (13), there exists an integer n_{0} > 0 such that every x ≥ n_{0} satisfies

|f′′(x)| < (\frac{k − 1}{W − 1})^{2}(\frac{1}{k − 2} − \frac{2M}{r} ),

where W = W (r, k) and M = M_{2} − M_{1}. Then we define the following sets:

I_{j} = [M_{1} + \frac{M}{r} j, M_{1} + \frac{M}{r} (j + 1)] (0 ≤ j ≤ r − 1),

A = ℕ ∩ [n_{0}, n_{0} + W − 1],

A_{j} = { n ∈ A | R(n) ∈ I_{j} } (0 ≤ j ≤ r − 1).

It can be easily checked that the interval [M_{1}, M_{2}] is the union of all the small intervals I_{j} and the set A is the union of all the small sets A_{j}. Hence, there exists an integer 0 ≤ q ≤ r − 1 such that A_{q} contains an arithmetic progression P = {b(j)}_{j=0}^{k−1}. Here b(j) is expressed as b(j) = dj + e with two integers d, e > 0. The inequalities (k − 1)d ≤ W − 1 and e ≥ n_{0} imply

\begin{aligned}N_{P} (f) & = ∑_{j=0}^{k−3} |Δ^{2}[f ∘ b](j)| = ∑_{j=0}^{k−3} d^{2} |f′′(d(j + θ_{j} + η_{j}) + e)| \\ & < ∑_{j=0}^{k−3}(\frac{W − 1}{k − 1})^{2}(\frac{k − 1}{W − 1})^{2}(\frac{1}{k − 2} − \frac{2M}{r} ) = 1 − 2(k − 2)\frac{M}{r} , \end{aligned}  (15)

where θ_{j} = θ_{j}(d, e) and η_{j} = η_{j}(d, e) are real numbers satisfying θ_{j}, η_{j} ∈ (0, 1). Moreover, the relation P ⊂ A_{q} implies

N_{P} (R) = ∑_{j=0}^{k−3} |Δ^{2}[R ∘ b](j)| ≤ ∑_{j=0}^{k−3}(|Δ[R ∘ b](j + 1)| + |Δ[R ∘ b](j)|) ≤ 2(k − 2)\frac{M}{r} . (16)

Hence the inequality N_{P} (a) < 1 follows from (15) and (16). Since N_{P} (a) is a non-negative integer, the equation N_{P} (a) = 0 follows: a(P) is an AP of length k. Therefore, the graph of {a(n)}_{n=1}^{∞} contains an AP of length k.

Remark 16. As proved above, van der Waerden’s theorem implies Theorem 15 and then Theorem 15 implies Theorem 14, i.e., van der Waerden’s theorem implies Theorem 14. Surprisingly, the converse also holds, and thus Theorem 14 is equivalent to van der Waerden’s theorem. Let us verify the converse. Here it is well-known that van der Waerden’s theorem is equivalent to the statement that if the set of all positive integers is partitioned into finitely many sets then at least one set must contain arbitrarily long APs. We now show that Theorem 14 implies this statement. Suppose that ℕ = C_{1} ∪ C_{2} ∪ ⋯ ∪ C_{r}, where C_{i} and C_{j} are disjoint for every 1 ≤ i < j ≤ r. We define R(n) = j if n ∈ C_{j} and also define a(n) = rn + R(n) for all n ∈ ℕ. Then {a(n)}_{n=1}^{∞} is a strictly increasing sequence. Due to Theorem 14, the graph of {a(n)}_{n=1}^{∞} contains arbitrarily long APs. Fix an arbitrary integer k > r. Then there exists an arithmetic progression P = {b(j)}_{j=0}^{k−1} such that

0 = N_{P} (a) = ∑_{j=0}^{k−3} |Δ^{2}[a ∘ b](j)| = ∑_{j=0}^{k−3} |Δ^{2}[R ∘ b](j)| = N_{P} (R).

Since the inequalities 1 ≤ R(n) ≤ r and k > r hold, the set R(P) is not an AP of length k: R(P) = {j(k)} for some 1 ≤ j(k) ≤ r, which implies that C_{j(k)} contains an AP of length k. From the finiteness of the range 1 ≤ j(k) ≤ r, there exist 1 ≤ j_{0} ≤ r and a sequence k_{1} < k_{2} < ⋯ such that

C_{j_{0}} = C_{j(k_{1})} = C_{j(k_{2})} = ⋯

Note that j_{0} does not depend on k. Thus C_{j_{0}} contains arbitrarily long APs. From the above discussion, Theorem 14 is equivalent to van der Waerden’s theorem.

We use the proof of Theorem 15 to prove the next theorem. As stated in Section 6, we cannot answer Question 12, but the following theorem holds:

Theorem 17. Let {a(n)}_{n=1}^{∞} be a slightly curved sequences with error O(1) and g be a function satisfying the following properties:

(G1) g is a twice differentiable function defined on the interval (x_{0}, ∞) for some x_{0} > 0;

(G2) there exists a positive number x_{1} ≥ x_{0} such that g and g′ increase on the interval (x_{1}, ∞);

(G3) lim_{x→∞} g′(2x)/g(x)^{α} = 0 for all α > 0;

(G4) lim_{x→∞} g′′(x) = 0.

If A = {ã(n)}_{n=n_{0}}^{∞} with n_{0} > x_{1} is a strictly increasing sequence satisfying ã(n) = g(n)+O(1), then the graph of {a(n)}_{n∈A} contains arbitrarily long APs.

Proof. Thanks to Proposition 9, it is enough to show that the set A = {ã(n)}_{n=n_{0}}^{∞} satisfies (C). Let k ≥ 3 be an integer and α be a positive number. We choose the function h_{α} as h_{α}(x) = x^{β} with β = 1 + α/2, which satisfies (H1)–(H4). Hence all we need is to show that there exists a strictly increasing sequence {x_{n}}_{n=1}^{∞} ⊂ ℝ^{+} which diverges such that for every n > 0 the set A ∩ (h_{α}(x_{n}), h_{α}(x_{n} + 1)] contains an AP of length k.

Take two real numbers M_{1} and M_{2} satisfying M_{1} ≤ ã(n) − g(n) ≤ M_{2} and the integer r with (14), and let W = W (r, k) and M = M_{2} − M_{1}. Since g satisfies (G4), Theorem 15 can be applied to A = {ã(n)}_{n=n_{0}}^{∞}. More precisely, the proof of Theorem 15 implies that there exists an integer n_{1} ≥ n_{0} such that for every n ≥ n_{1} the set A ∩ [ã(n), ã(n + W − 1)] contains an AP of length k. Thus (C) can be reduced to the inclusion relation

A ∩ (h_{α}(x_{n}), h_{α}(x_{n} + 1)] ⊃ A ∩ [ã(n), ã(n + W − 1)].  (17)

Let us show (17). Put x_{n} = (g(n) + M_{1} − 1)^{1/β} < ã(n)^{1/β}. Then h_{α}(x_{n}) = g(n) + M_{1} − 1 < ã(n). The mean value theorem implies

ã(n + W − 1) ≤ g(n + W − 1) + M_{2} ≤ g(n) + (W − 1)g′(n + W − 1) + M_{2}
= h_{α}(x_{n}) − (M_{1} − 1) + (W − 1)g′(n + W − 1) + M_{2}
= h_{α}(x_{n}) + (W − 1)g′(n + W − 1) + M + 1,  (18)
h_{α}(x_{n} + 1) ≥ h_{α}(x_{n}) + h′_{α}(x) = h_{α}(x_{n}) + βx_{n}^{β−1}  (19)

due to (G2). Using (G2), (G3), and lim_{x→∞} g(x) = ∞ (this limit follows from the fact that {ã(n)}_{n_{0}}^{∞} is a strictly increasing sequence), we have

lim_{x→∞} \frac{(W − 1)g′(x + W − 1) + M + 1}{β(g(x) + M_{1} − 1)^{1−1/β}} ≤ lim_{x→∞} \frac{(W − 1)g′(2x) + M + 1}{(g(x)/2)^{1−1/β}} = 0,

whence (W − 1)g′(n + W − 1) + M + 1 = o(βx_{n}^{β−1}). Thus there exists an integer n_{2} ≥ n_{1} such that every n ≥ n_{2} satisfies

(W − 1)g′(n + W − 1) + M + 1 ≤ βx_{n}^{β−1}.  (20)

The equations (18), (19), and (20) yield h_{α}(x_{n} + 1) ≥ ã(n + W − 1) for every n ≥ n_{2}. Therefore, the inclusion relation (17) holds for every n ≥ n_{2}.

Remark 18. The function g(x) = li^{−1}(x) satisfies (G1)–(G4). (The definition of li^{−1}(x) is in Section 6.) Moreover, when ã(n) = li^{−1}(n) + O(1), the sequence A = {ã(n)}_{n=n_{0}}^{∞} for some n_{0} is a strictly increasing sequence. Therefore, if {a(n)}_{n=1}^{∞} is a slightly curved sequence with error O(1), the graph of {a(n)}_{n∈A} contains arbitrarily long APs.

B Result similar to Theorem 15

This appendix states a result similar to Theorem 15, which is not completely contained by Theorem 15. Indeed, Theorem 21 below implies that the graph of {⌊c_{2}n^{2} + c_{1}n + c_{0}⌋}_{n=1}^{∞} with 0 < c_{2} < 1/18 contains an AP of length 4, which is better evaluation than that of Theorem 15.

Σ = {0, 1} Σ = {0, 1, 2} Σ = {0, 1, 2, 3}  Σ = {0, 1, 3, 4}
k = 2 n = 4 n = 8 n = 51
k = 3 n = 10  (S_{3}) does not hold [20].

Table 1: Integers n in the statement (S_{k}) for several alphabets Σ. The case when k = 2 and Σ = {0, 1, 2, 3} was computed by a personal computer. If the statement (S_{2}) for Σ = {0, 1, 2, 3, 4} holds, then n > 152 by computing. If the statement (S_{3}) for Σ = {0, 1, 2} holds, then n > 1288 [20].

Theorem 19. If a function f : ℕ → ℝ^{+} satisfies Δf > 0, Δ^{2}f ≥ 0, and

sup_{x>0} N(x)^{2}/x = ∞,  (21)

then the graph of {⌊f(n)⌋}_{n=1}^{∞} contains an AP of length 4. Here N(x) denotes the number of positive integers satisfying f(n) ≤ x, i.e., N(x) := |{ n ∈ ℕ | f(n) ≤ x }|.

Remark 20. Theorem 19 does not assume that the sequence {⌊f(n)⌋}_{n=1}^{∞} strictly increases, but when the function f satisfies Δf(n_{0}) ≥ 1 for some n_{0} > 0, the sequence {⌊f(n)⌋}_{n=n_{0}}^{∞} strictly increases due to the assumption Δ^{2}f ≥ 0.

Let Σ be a nonempty finite set of non-negative integers. In order to show Theorem 19, we address words over the alphabet Σ. Here we allow words to continue infinitely on the right side such as 000 ⋯, and to be the empty word. The length of a word w (i.e., the number of all letters of w) is denoted by |w| and the sum of all letters of a word w is denoted by ∑ w. Then we focus on the following condition (C_{k}) for a word w: there exist k + 1 finite length words w_{0}, …, w_{k} and a word w_{k+1} such that

w = w_{0} ⋯ w_{k}w_{k+1}, |w_{1}| = ⋯ = |w_{k}| > 0, and ∑ w_{1} = ⋯ = ∑ w_{k}.

We also focus on the following statement: there exists an integer n > 0 such that every word w with |w| ≥ n satisfies the condition (C_{k}). We call it the statement (S_{k}). The statement (S_{k}) depends on the alphabet Σ. Table 1 summarizes integers n in the statements (S_{2}) and (S_{3}) for several alphabets Σ. The proof of Theorem 19 uses the statement (S_{3}). The statement (S_{3}) for Σ = {0, 1} can be checked by taking n = 10. Cassaigne et al. [20] proved that the statement (S_{3}) did not hold for Σ = {0, 1, 3, 4}. For details, see [20].

Proof of Theorem 19. We show that for every integer k > 0 there exists an integer n_{0} > 0 such that the function ⌊Δf(n)⌋ takes a constant value for every n_{0} ≤ n ≤ n_{0} + k, by contradiction. Suppose that our assertion does not hold, namely, for some integer k > 0, there exists no positive integer n_{0} such that the function ⌊Δf(n)⌋ takes a constant value for every n_{0} ≤ n ≤ n_{0} + k. Putting the function λ(x) := ⌈N(x)/k⌉ − 1, we find N(x) = kN(x)/k > kλ(x). Hence the inequality N(x) ≥ kλ(x) + 1 holds. Then the assumption Δ^{2}f(n) ≥ 0 yields ⌊Δf(n + 1)⌋ ≥ ⌊Δf(n)⌋. Using this inequality and the assumption of the proof by contradiction to obtain the following (i), we have

x > f(kλ(x) + 1) − f(1) = ∑_{j=1}^{kλ(x)} Δf(j) ≥ ∑_{j=1}^{kλ(x)} ⌊Δf(j)⌋ ≥^{(i)} k ∑_{j=0}^{λ(x)−1} j

= \frac{k}{2}λ(x)(λ(x) − 1) ≥ \frac{k}{2}(\frac{N(x)}{k} − 1)(\frac{N(x)}{k} − 2),

that is, (N(x)−k)(N(x)−2k) < 2kx. This inequality implies that N(x)^{2}/x is upper bounded by a constant, which contradicts the assumption (21).

Putting k = 9, we can take two integers n_{0} > 0 and c ≥ 0 satisfying ⌊Δf(n)⌋ = c for all n_{0} ≤ n ≤ n_{0} + 9. Thus Δ ⌊f(n)⌋ − c ∈ {0, 1} for all n_{0} ≤ n ≤ n_{0} + 9. Since the statement (S_{3}) holds for Σ = {0, 1}, there exist two integers d, e > 0 such that

∑_{j=e}^{e+d−1}(Δ ⌊f(j)⌋ − c) = ∑_{j=e+d}^{e+2d−1}(Δ ⌊f(j)⌋ − c) = ∑_{j=e+2d}^{e+3d−1}(Δ ⌊f(j)⌋ − c).

Thus the equation

⌊f(e + d)⌋ − ⌊f(e)⌋ = ⌊f(e + 2d)⌋ − ⌊f(e + d)⌋ = ⌊f(e + 3d)⌋ − ⌊f(e + 2d)⌋

holds: {⌊f(e + dj)⌋}_{j=0}^{3} is an AP of length 4. That is, the graph of {⌊f(n)⌋}_{n=0}^{∞} contains an AP of length 4.

Theorem 21. If a function f : ℕ → ℝ^{+} satisfies Δf > 0, Δ^{2}f ≥ 0, and

lim sup_{x→∞} N(x)^{2}/x > 18,  (22)

then the graph of {⌊f(n)⌋}_{n=1}^{∞} contains an AP of length 4.

Proof. If the function N(x)^{2}/x is not bounded, our assertion follows from Theorem 19. Hence we assume that the function N(x)^{2}/x is bounded. We show that there exists an integer n_{0} > 0 such that the function ⌊Δf(n)⌋ takes a constant value for every n_{0} ≤ n ≤ n_{0} + 9, by contradiction. In the same way as the proof of Theorem 19, the inequality (N(x) − 9)(N(x) − 18) < 18x holds. Moreover, since the function N(x)^{2}/x is bounded, the limit

\frac{N(x)}{x} = \frac{N(x)}{x^{1/2}} \frac{1}{x^{1/2}} ⟶^{x→∞} 0

holds. Thus the inequality lim sup_{x→∞} N(x)^{2}/x ≤ 18 follows, which contradicts the assumption (22). Therefore, there exists two integers n_{0} and c such that ⌊Δf(n)⌋ = c for every n_{0} ≤ n ≤ n_{0} + 9. The remaining can be shown in the same way as the proof of Theorem 19.

Remark 22. Theorem 21 implies that the graph of {⌊c_{2}n^{2} + c_{1}n + c_{0}⌋}_{n=1}^{∞} with 0 < c_{2} < 1/18 contains an AP of length 4. However, Theorem 15 only implies that the same graph with 0 < c_{2} < 1/(6 · 13^{2}) contains an AP of length 3.

The following propositions provide alternative conditions of (21) and (22).

Proposition 23. If a function f : ℕ → ℝ^{+} satisfies Δf > 0 and Δ^{2}f ≥ 0, then for every c > 0 the following three conditions are equivalent:

(i) lim sup_{x→∞} N(x)^{2}/x > c, (ii) lim sup_{n→∞} n^{2}/f(n) > c, and (iii) lim inf_{n→∞} f(n)/n^{2} < 1/c.

Proof. First, note that the limit f(n) ≥ f(1) + (n − 1)Δf(1) → ∞ holds as n → ∞. The implication (ii)⇒(i) follows from the definition of N(x). Next, we show the implication (i)⇒(ii) by contradiction. Suppose that the condition (i) holds and the condition (ii) does not hold, i.e., lim sup_{x→∞} N(x)^{2}/x > c and lim sup_{n→∞} n^{2}/f(n) ≤ c. The assumption Δf > 0 and the limit f(n) → ∞ imply that for every x > 0 we can take only one positive integer n = n(x) satisfying f(n) ≤ x < f(n + 1). Hence every x > 0 satisfies

N(x)^{2}/x < (n + 1)^{2}/f(n) = n^{2}/f(n) + 2n/f(n) + 1/f(n),  (23)

where n = n(x). Now, the assumption lim sup_{n→∞} n^{2}/f(n) ≤ c yields lim sup_{n→∞} n/f(n) = 0 and lim sup_{n→∞} 1/f(n) = 0. Thus, noting n = n(x) → ∞ as x → ∞ and taking the limit in (23) as x → ∞, we have

c < lim sup_{x→∞} N(x)^{2}/x ≤ lim sup_{n→∞} n^{2}/f(n) ≤ c,

which is a contradiction. Therefore, the implication (i)⇒(ii) holds. The remaining, i.e., the equivalence (ii)⇔(iii) is trivial.

Proposition 24. If a function f : ℕ → ℝ^{+} satisfies Δf > 0 and ∑_{n=1}^{∞} 1/f(n)^{s} = ∞ for some s > 1/2, then the condition sup_{x>0} N(x)^{2}/x = ∞ holds.

Proof. Let ζ be the Riemann zeta function. We show our assertion by contradiction. Suppose that the function N(x)^{2}/x is bounded. Then the inequality N(x)^{2}/x ≤ M holds for some M > 0. Thus the inequality n^{2}/f(n) ≤ M also holds and every s > 1/2 satisfies ∑_{n=1}^{∞} 1/f(n)^{s} ≤ Mζ(2s) < ∞, which is a contradiction.

C Partial answer to Question 11

This section proves that Question 11 is affirmative when the coefficients of the error term O(f′(n)) are contained in a finite set {c_{1}, c_{2}, …, c_{m}}.

Theorem 25. Let f : ℝ^{+} → ℝ be a twice differentiable function satisfying (1), and R̃ : ℕ → {c_{1}, c_{2}, …, c_{m}} be a bounded function. If a strictly increasing sequence {a(n)}_{n=1}^{∞} ⊂ ℕ can be written as

a(n) = f(n) + R̃(n)f′(n) + O(1),

then the sequence {a(n)}_{n=1}^{∞} contains arbitrarily long APs.

Proof. Fix an integer k ≥ 3. First, the assumption (1) implies

a(n) = f(n) + R̃(n)f′(n) + O(1) = f(n + R̃(n)) + O(1).  (24)

We define ã(n) = n + R̃(n), W = W (m, W (r, k)), and the following sets:

Ã = ℕ ∩ [⌊W^{3/α}⌋, ⌊W^{3/α}⌋ + W − 1],
Ã_{j} = { n ∈ Ã | R̃(n) = c_{j} } (1 ≤ j ≤ m).

Since the union of all the small sets Ã_{j} is Ã, a small set Ãq̃ contains an arithmetic progression P̃ of length W (r, k). Thus it follows that

NP̃(ã) ≤ NP̃(id_{ℕ}) + NP̃(R̃) = 0.

In other words, the sequence ã(P̃) (of real numbers) is also an AP of length W (r, k).

Noting that the sequence ã(P̃) is a strictly increasing sequence, we define the function R : ã(P̃) → ℝ as

R(ã(n)) = a(n) − f(ã(n)) (n ∈ P̃).  (25)

Then the function R is bounded. Thanks to (24), we can take two real numbers M_{1} and M_{2} satisfying M_{1} ≤ R(x) ≤ M_{2} such that M_{1} and M_{2} are independent of r. We define M = M_{2} − M_{1} and the following sets:

I_{j} = [M_{1} + \frac{M}{r} j, M_{1} + \frac{M}{r} (j + 1)] (0 ≤ j ≤ r − 1),

A_{j} = { x ∈ ã(P̃) | R(n) ∈ I_{j} } (0 ≤ j ≤ r − 1).

Since the union of all the small sets A_{j} is ã(P̃), a small set A_{q} contains an arithmetic progression P = {b(j)}_{j=0}^{k−1} of length k. Here b(j) is expressed as b(j) = dj + e with two integers d, e > 0. Moreover, the inequalities

d ≤ ã(⌊W^{3/α}⌋ + W − 1) − ã(⌊W^{3/α}⌋) ≤ W − 1 + M,
e ≥ ã(⌊W^{3/α}⌋) ≥ ⌊W^{3/α}⌋ + M_{1}

hold. These inequalities imply that

N_{P} (R) ≤ 2(k − 2)\frac{M}{r} = o(1),

N_{P} (f) = ∑_{j=0}^{k−3} d^{2} |f′′(d(j + θ_{j} + η_{j}) + e)| = O(\frac{(W − 1 + M)^{2}}{(⌊W^{3/α}⌋ + M_{1})^{α}} ) = O(1/W) = o(1)

as r → ∞, where θ_{j} = θ_{j}(d, e) and η_{j} = η_{j}(d, e) are real numbers satisfying θ_{j}, η_{j} ∈ (0, 1). Thus every sufficiently large r satisfies N_{P} (f) + N_{P} (R) < 1.

Recall (25). The domains of f and R are the same, but the domain of a is different from them. Hence we must take a set like the inverse image of P under ã. Now, the restricted function ã|P̃ is injective. When we denote by P′ the inverse image of P ⊂ ã(P̃) under this restricted function, the sequence P′ is also an AP of length k. Then the inequality N_{P′}(a) ≤ N_{P} (f) + N_{P} (R) < 1 holds. Since N_{P′}(a) is a non-negative integer, the equation N_{P′}(a) = 0 follows: a(P′) is an AP of length k.

References

[1] E. Szemerédi. On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975), 199–245.

[2] J. Jasinski. Large sets containing copies of small sets, Real Anal. Exchange 21 (1995/96), 758–766.

[3] I. I. Piatetski-Shapiro. On the distribution of prime numbers in sequences of the form [f(n)], Mat. Sbornik N.S. 33 (75) (1953), 559–566.

[4] J. Rivat and J. Wu. Prime numbers of the form [n^{c}], Glasg. Math. J. 43 (2001), 237–254.

[5] M. Mirek. Roth’s theorem in the Piatetski-Shapiro primes, Rev. Mat. Iberoam. 31 (2015), 617–656.

[6] H. Li and H. Pan. The Green-Tao theorem for Piatetski-Shapiro primes, preprint, 2019.

Available at https://arxiv.org/abs/1901.09372.

[7] P. Erdős and P. Turán. On some sequences of integers, J. London Math. Soc. 11 (1936), 261–264.

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

[9] L. E. Dickson. History of the Theory of Numbers. Vol. II: Diophantine Analysis, Chelsea Publishing Co., 1966.

[10] P. Dénes. Über die Diophantische Gleichung x^{l} + y^{l} = cz^{l}, Acta Math. 88 (1952), 241– 251.

[11] H. Darmon and L. Merel. Winding quotients and some variants of Fermat’s last theorem, J. Reine Angew. Math. 490 (1997), 81–100.

[12] H. L. Montgomery and R. C. Vaughan. Multiplicative Number Theory I. Classical Theory, Cambridge University Press, 2007.

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

[14] W. T. Gowers. A new proof of Szemerédi’s theorem, Geom. Funct. Anal. 11 (2001), 465–588.

[15] T. F. Bloom. A quantitative improvement for Roth’s theorem on arithmetic progressions, J. London Math. Soc. 93 (2016), 643–663.

[16] B. Green and T. Tao. New bounds for Szemerédi’s theorem, III: a polylogarithmic bound for r_{4}(N), Mathematika 63 (2017), 944–1040.

[17] M. Cipolla. La determinazione assintotica dell’n^{imo} numero primo, Matematiche Napoli 3 (1902), 132–166.

[18] J. Arias de Reyna and J. Toulisse. The n-th prime asymptotically, J. Théor. Nombres Bordeaux 25 (2013), 521–555.

[19] V. Chvátal. Some unknown van der Waerden numbers, in Combinatorial Structures and Their Applications (Proc. Calgary Internat. Conf., Calgary, Alberta, 1969), Science Publishers, 1970, pp. 31–33.

[20] J. Cassaigne, J. D. Currie, L. Schaeffer, and J. Shallit. Avoiding three consecutive blocks of the same size and same sum, J. ACM 61 (2014), 10:1-10:17.

2010 Mathematics Subject Classification: Primary 11B25; Secondary 11B30. Keywords: arithmetic progression, Szemerédi’s theorem, Piatetski-Shapiro sequence, van der Waerden number, Gowers’ upper bound.

Received October 22 2018; revised versions received February 21 2019; February 22 2019. Published in Journal of Integer Sequences, February 22 2019.

Return to Journal of Integer Sequences home page.