Primes in Intersections of Beatty Sequences

Glyn Harman Department of Mathematics Royal Holloway, University of London EGHAM Surrey TW20 0EX United Kingdom

                  g.harman@rhul.ac.uk

Abstract

In this note we consider the question of whether there are infinitely many primes in the intersection of two or more Beatty sequences ⌊ξ_{j}n + η_{j}⌋, n ∈ ℕ, j = 1, …, k. We begin with a straightforward sufficient condition for a set of Beatty sequences to contain infinitely many primes in their intersection. We then consider two sequences when one ξ_{j} is rational. However, the main result we establish concerns the intersection of two Beatty sequences with irrational ξ_{j}. We show that, subject to a natural “compatibility” condition, if the intersection contains more than one element, then it contains infinitely many primes. Finally, we supply a definitive answer when the compatibility condition fails.

1 Introduction

Let ⌊·⌋ denote the integer part function and {x} the fractional part of x, so that x = ⌊x⌋+{x}. The sequence ⌊ξn + η⌋, n = 1, 2, … is called a Beatty sequence. If ξ ∈ ℤ this is an arithmetic progression, so one can consider Beatty sequences to be, in some sense, a generalisation of arithmetic progressions. If ξ = a/b ∈ ℚ with a > b > 1, gcd(a, b) = 1, then the corresponding Beatty sequence is a union of b arithmetic progressions (mod a). Original problems involving Beatty sequences therefore come from the case of irrational ξ. The question of primes in an arithmetic progression is of importance in analytic number theory and correspondingly many researchers have recently considered problems involving primes in Beatty sequences [1, 3, 10, 15]. We write B(ξ, η) = {⌊ξn + η⌋ : n ∈ ℕ}. The problem we address in this paper concerns the intersection of a finite number of Beatty sequences. Suppose

ξ = (ξ_{1}, …, ξ_{s}) and η = (η_{1}, …, η_{s}),

with each ξ_{j} a real exceeding 1. Put

B(ξ, η) = ⋂_{j=1}^{s} B(ξ_{j}, η_{j}) .

Clearly we need some conditions on the pair ξ, η just to ensure that B(ξ, η) ≠ ∅. We recall an observation from at least as far back as 1894 [13, p. 123] that in the case s = 2, η_{1} = η_{2} = 0, for any ξ_{1} > 1, ξ_{1} ∉ ℚ, the value ξ_{2} satisfying 1/ξ_{1} + 1/ξ_{2} = 1 gives B(ξ, η) = ∅, while the union of the two sequences comprises the whole of ℕ. This observation (noted in the context of the theory of vibrating strings) was stated without proof and predates Beatty’s original question concerning the sequences which now bear his name, and which inspired formal demonstrations [4, 14]. This result has led to much further research (for example, [12, 7, 11, 6, 9]).

Here we shall address the question of whether B(ξ, η) contains infinitely many primes. The following theorem provides us with a simple sufficient condition.

Theorem 1. Let k ∈ ℕ and reals ξ_{1}, …, ξ_{k} each exceeding 1 be given such that

1, \frac{1}{ξ_{1}} , …, \frac{1}{ξ_{k}} , are linearly independent over ℚ.  (1)

Then, for every η ∈ ℝ^{k}, the set B(ξ, η) contains infinitely many primes. Indeed, the number of such primes up to x equals

\frac{x}{ξ_{1} ⋯ ξ_{k} log x}(1 + o(1)).  (2)

Our remaining results consider what happens in the case k = 2 when (1) fails. We first consider the case when one or both of the ξ_{j} are rational. When both are rational either B(ξ, η) is empty or it consists of the union of arithmetic progressions. In that case there will be infinitely many primes in the intersection if and only if at least one of these progressions has the form a (mod q) with gcd(a, q) = 1. If exactly one ξ_{j} is rational we have the following result.

Theorem 2. Let ξ_{1}, ξ_{2} be reals exceeding 1 with ξ_{1} ∈ ℚ, ξ_{2} ∉ ℚ. If η_{1} is such that ⌊ξ_{1}n + η_{1}⌋ takes infinitely many prime values, then the set B(ξ, η) contains infinitely many primes for evey real η_{2}.

Before discussing the case where both ξ_{j} are irrational we need the following definition given by Balog and Friedlander [2].

Definition 3. A set of real numbers {α_{1}, …, α_{k}} is called compatible if

∑_{j=1}^{k} n_{j}α_{j} ∈ ℚ ⟹ ∑_{j=1}^{k} n_{j}α_{j} ∈ ℤ

whenever n_{1}, …, n_{k} are integers.

Of course, if (1) holds then the set {1/ξ_{1}, …, 1/ξ_{k}} is trivially compatible. For the case k = 2 and a compatible set we can give a definitive answer to the question whether B(ξ, η) contains infinitely many primes as follows.

Theorem 4. Let k = 2, and ξ_{1}, ξ_{2} > 1, both irrational such that {1/ξ_{1}, 1/ξ_{2}} is a compatible set. Then, if the set B(ξ, η) has more than one element, it contains infinitely many primes.

The compatibility condition was introduced in connection with simultaneous Diophantine approximation using prime denominators, so it is quite natural to see its occurrence here given the method used to detect primes in Beatty sequences (see the start of the proof of Theorem 1). However, although compatibility is sufficient to show that

lim inf_{p→∞} max_{j=1,2} ∥α_{j}p∥ = 0,

where ∥x∥ denotes the distance from x to a nearest integer, it is not sufficient by itself to establish the corresponding simultaneous inequalities in our situation. Neither is the condition always necessary as we investigate further in the final section of this paper.

We shall establish Theorem 4 by considering the various possibilities when (1) fails. In the following we assume without further comment that ξ_{1}, ξ_{2} > 1, both irrational, and {1/ξ_{1}, 1/ξ_{2}} is a compatible set. We first mention the homogeneous case (η_{1} = η_{2} = 0) when there exist integers m, n, r such that

m/ξ_{1} + n/ξ_{2} = r with (m, n, r) = 1, m, n, r > 0.  (3)

An important observation here is that the compatibility condition forces m and n to be coprime. We shall assume this consequence without further comment when assuming the compatibility condition. Of course we must have r ≥ 2 or else the intersection of the two Beatty sequences will be empty. This follows from the same argument supplied for the case m = n = 1. The next result shows that r ≥ 2 is a sufficient condition for two such Beatty sequences to have infinitely many primes in their intersection, even in the inhomogeneous case.

Theorem 5. Let k = 2 and suppose that ξ_{1}, ξ_{2} satisfy (3) with r ≥ 2. Then for every η ∈ ℝ^{2} the set B(ξ, η) contains infinitely many primes.

For the case k = 2 with m, n both positive it remains to elucidate what happens when r = 1 in the inhomogeneous case. To that end we also prove the following result which includes the homogeneous case.

Theorem 6. Let k = 2 and suppose that ξ_{1}, ξ_{2} satisfy (3) with r = 1. Then the set B(ξ, η) contains infinitely many primes if and only if

mη_{1}ξ_{1}^{−1} + nη_{2}ξ_{2}^{−1} ∉ ℤ .  (4)

Indeed, if (4) fails the set B(ξ, η) contains at most one element.

We note that in this case Skolem [12] has already proved (when m = n = 1) that B(ξ, η) contains at most one element if (4) fails.

Our final cases cover what happens if m, n, r do not all have the same sign. Without loss of generality we can suppose that m ≥ 1, r ≥ 0, n ≤ −1. We can then replace n by −n to consider

m/ξ_{1} − n/ξ_{2} = r with (m, n, r) = 1, m, n > 0, r ≥ 0.  (5)

The case r ≥ 1 is as follows.

Theorem 7. Let k = 2 and suppose that ξ_{1}, ξ_{2} satisfy (5) with r ≥ 1. Then for every η ∈ ℝ^{2} the set B(ξ, η) contains infinitely many primes.

Finally, in the case r = 0, we note that Morikawa [11] has already studied the condition that makes the two sequences disjoint. We show that when this condition fails the intersection contains infinitely many primes. In the case r = 0 it is, of course, immediate that {1/ξ_{1}, 1/ξ_{2}} is a compatible set.

Theorem 8. Let k = 2 and suppose that ξ_{1}, ξ_{2} satisfy (5) with r = 0. There are infinitely many primes if and only if the following condition fails

1 − \frac{m}{ξ_{1}} ≥ \{\frac{m(η_{1} − η_{2})}{ξ_{1}}\} ≥ \frac{m}{ξ_{1}} .  (6)

When (6) holds with strict inequality B(ξ, η) is empty. If (6) holds with equality then there is at most one element in B(ξ, η).

Remark 9. We note from the above that the set B(ξ, η) contains infinitely many primes for all η if m/ξ_{1} > \frac{1}{2}.

2 Proof of Theorem 1

As is well-known, p = ⌊nξ + η⌋ is equivalent to

0 < {pα + β} ≤ α,  (7)

where

α = 1/ξ, β = (1 − η)/ξ.

In the rest of the paper we therefore write

α_{j} = ξ_{j}^{−1}, β_{j} = (1 − η_{j})/ξ_{j}.

We hence wish to count the number of solutions with p ≤ x to the simultaneous Diophantine inequalities:

0 < {pα_{j} + β_{j}} ≤ α_{j}, j = 1, …, k .  (8)

We note that when (1) holds the fractional parts {α_{1}p}, …, {α_{k}p} are uniformly distributed in [0, 1)^{k} (see the comments at the end of §3 of [8]). It follows that, upon writing π(x) for the number of primes up to x, the number of solutions to (8) is

α_{1} ⋯ α_{k}π(x)(1 + o(1)) .

Since π(x) ∼ x/ log x this establishes (2).

3 Proof of Theorem 2

Before proceeding further we need a result which will be useful in several remaining cases.

Lemma 10. Let ζ be an irrational number, q be a positive integer, and a be a reduced residue (mod q). Then the sequence {pζ} with p ≡ a (mod q) is uniformly distributed modulo one. That is, for every interval I ⊂ [0, 1), |I| > 0, we have

∑_{\begin{matrix}p≤x,p≡a (mod q) \\ \{pζ\}∈I \end{matrix}} 1 ∼ \frac{|I|π(x)(1 + o(1))}{ϕ(q)} as x → ∞ .  (9)

Here ϕ(n) denotes Euler’s totient function.

Proof. This follows from a standard modification of the proof that {ζp} is uniformly distributed as p runs over all primes [16, Chapter 11]. Banks and Shparlinski [3, Theorem 4.2] have given an explicit proof when ζ is of finite type; the general case follows similarly.

Remark 11. We note that if ζ is of finite type it is possible [3, Theorem 4.2] to give an explicit error term in (9), but this is not possible in the general case since ζ could “look like” a rational with relatively small denominator for infinitely many x.

Proof of Theorem 2. From the hypothesis of Theorem 2 we know that ⌊ξ_{1}n + η_{1}⌋ takes infinitely many prime values. Since the values taken by ⌊ξ_{1}n + η_{1}⌋ form the union of a set of arithmetic progressions they must include all sufficiently large primes in some arithmetic progression. The result then follows from Lemma 10 using the working at the start of Section 2.

4 Proof of Theorem 4

If 1, 1/ξ_{1}, 1/ξ_{2} are linearly independent over ℚ there are infinitely many primes in B(ξ, η) by Theorem 1. Otherwise, since {1/ξ_{1}.1/ξ_{2}} is a compatible set, we either have (3) or (switching ξ_{1} and ξ_{2} if necessary) (5). If (3) holds then if r = 2 there are infinitely many primes in B(ξ, η) by Theorem 5. If r = 1 either B(ξ, η) has at most one element or it contains infinitely many primes by Theorem 6. If (5) holds with r ≥ 1 there are infinitely many primes by Theorem 7. If (5) holds with r = 0 by Theorem 8 there is either at most one element in B(ξ, η) or the set contains infinitely many primes. Hence we have demonstrated that if B(ξ, η) contains more than one element then it contains infinitely many primes.

5 Proof of Theorem 5

Our aim is to establish (given (3) with r ≥ 2) that there are infinitely many primes p such that both the inequalities

0 < {α_{1}p + β_{1}} ≤ α_{1}, and 0 < {α_{2}p + β_{2}} ≤ α_{2},  (10)

are satisfied simultaneously.

Now the first inequality in (10) is satisfied if and only we have

0 < \{\frac{α_{1}p + β_{1} + s}{n}\} ≤ \frac{α_{1}}{n} , s ∈ \{0, 1, …, n − 1\} .

We therefore assume for the moment that

\frac{α_{1}p}{n} = A + λ − \frac{β_{1} + s}{n} , A ∈ ℕ, λ ∈ (0, α_{1}/n] .

We shall also suppose for the time being that p ≡ a (mod n). Here a is an arbitrary fixed reduced residue (mod n). Using (3) this gives

\{α_{2}p + β_{2}\} = \{β_{2} + \frac{ar}{n} − m (λ − \frac{β_{1} + s}{n})\} .

Let β_{2} + mβ_{1}/n + ar/n = θ. Then we can rewrite the last expression as

\{θ − mλ + \frac{sm}{n}\} .

Write

t = \begin{cases}\frac{1}{n}\{nθ\}, & if \{nθ\} ≠ 0; \\ \frac{1}{n}, & otherwise. \end{cases}

Since (m, n) = 1 we can choose s such that

\{θ + \frac{sm}{n}\} = t .

It follows that

\{θ − mλ + \frac{sm}{n}\} = t − mλ

so long as the right hand side above is positive.

Write

γ = max (0, \frac{t − α_{2}}{m} ) , δ = min (\frac{t}{m}, \frac{α_{1}}{n} ) , I = (γ, δ).

Then, for λ ∈ I, both inequalities in (10) will be satisfied. Of course, δ > γ since mα_{1}+nα_{2} > 1. By Lemma 10 the number of solutions to (10) with p ≤ x is therefore at least

\frac{π(x)}{ϕ(n)}(1 + o(1))(δ − γ).  (11)

This completes the proof of Theorem 5.

6 Proof of Theorem 6

We need to revisit the proof of the last section but now with r = 1. We note that we can still obtain (11) so long as δ > γ, that is

tn < mα_{1} + nα_{2} = 1 .

So we still obtain infinitely many solutions unless nθ ∈ ℤ, that is

nβ_{2} + mβ_{1} ∈ ℤ .  (12)

Using the definitions of α_{j}, β_{j} and the relation mα_{1} +nα_{2} = 1 this is equivalent to the failure of (4).

Now suppose that (12) holds so that t = 1/n. Any solutions to (10) must now have

{α_{1}p + β_{1}} = α_{1}, and {α_{2}p + β_{2}} = α_{2},  (13)

However, it is easy to see that if {α_{1}g + β_{1}} = α_{1} has more than one solution in integers g then α_{1} is rational: a contradiction. This completes the proof of Theorem 6.

7 Proof of Theorem 7

We still need to solve (10), but the main difference with the previous two cases is that −mλ becomes mλ. If we now write β_{2} − mβ_{1}/n − ar/n = θ and define t as in Section 3, we wish to choose s so that

{α_{2}p + β_{2}} = t − 1/n + mλ

for λ > (1/n − t)/m. Write

γ = \frac{1/n − t}{m}, δ = min (\frac{α_{1}}{n} , \frac{α_{2} + 1/n − t}{m}) , I = (γ, δ) .

Then, for λ ∈ I, both inequalities in (10) will be satisfied. We have δ > γ since mα_{1} > 1 in this case. As before we can apply Lemma 10 to obtain infinitely many prime solutions as required.

8 Proof of Theorem 8

We note that the proof in the previous section still holds when mα_{1} > 1 − nt. We could make an alternative choice of s (there is no restriction of p to an arithmetic progression for this theorem, of course) to obtain

{α_{2}p + β_{2}} = t + mλ .

We then obtain solutions for all λ (if any) satisfying

0 ≤ λ ≤ min (\frac{α_{1}}{n} , \frac{α_{2} − t}{m}) .

This can be satisfied if and only if mα_{1} = nα_{2} > nt. We thus obtain infinitely many solutions if either mα_{1} > nt or mα_{1} > 1 − nt. This covers all possibilities if mα_{1} > \frac{1}{2}. If mα_{1} < \frac{1}{2} there will be infinitely many solutions when (6) fails and none if 1 − mα_{1} > nt > mα_{1}. Indeed there can be no solutions at all in integers (dropping the prime requirement) in the latter case. This just leaves the possibility mα_{1} = nt or mα_{1} = 1 − nt. In this case any solution must have {pα_{1} + β_{1}} = α_{1}. Just as in a previous case it is easy to deduce that there is at most one solution in integers (dropping the prime requirement) for otherwise α_{1} would be rational. This completes the proof of Theorem 8.

9 When the compatibility condition fails

We first give a simple example of what can happen when the compatibility condition fails. Let ζ = 1/(2\sqrt{2}). Here ζ could be any sufficiently small irrational number. Write

ξ_{1} = \frac{3}{1 − ζ} , ξ_{2} = \frac{3}{1 + ζ} .

This corresponds to 3α_{1} + 3α_{2} = 2, so we are not dealing with a compatible set. Then, with the choice η_{1} = η_{2} = 0, we find that B(ξ, η) only contains integers ≡ 1 (mod 3), and in fact contains infinitely many primes. On the other hand, the choice η_{1} = 1, η_{2} = 1 − 1/ζ ensures that all the members of B(ξ, η) are multiples of 3 exceeding 3 and so there are no primes in this set. It is easy to see that B(ξ, η) is infinite in this case. This example is tackled just by going through a similar analysis to the above. The crucial point is whether we can solve

\{θ − mλ + \frac{sm}{n}\} ≤ α_{2}  (14)

with r = 2, m = n = 3 in integers s and a with (a, n) = 1. Since m = n the variable s plays no role and we only have a to choose. The choice η_{1} = η_{2} = 0 allows this with a = 1, but the choice η_{1} = 1, η_{2} = 1 − 1/ζ requires a = 0 corresponding to the fact that only multiples of 3 can be solutions. Explicitly, we must have 3λ < α_{1} (for otherwise we get a contradiction that α_{1} is rational). Then, for a ≠ 0, (14) becomes

\frac{2}{3} − 3λ ≤ \{\frac{2 or 3}{3} − 3λ\} ≤ α_{2} .

Since 3λ + α_{2} < α_{1} + α_{2} = \frac{2}{3} there can be no solutions.

To deal with the more general case, suppose that there are positive integers m, n, u, v with v ≥ 2, (m, n) = (u, v) = 1 and

\frac{m}{ξ_{1}} + \frac{n}{ξ_{2}} = \frac{u}{v} .  (15)

A simple statement of what can be achieved is as follows.

Suppose ξ_{1}, ξ_{2} are both irrationals exceeding 1 and that (15) holds with u/v > 1. Then there are infinitely many primes in B(ξ, η) for all η ∈ ℝ^{2}.

In fact it is possible to give a complete result, but first we need the following measure of the largest gap between reduced residues to a given modulus.

Definition 12. Given a positive integer v, write w = ϕ(v) and let 1 = a_{1}, …, a_{w} = v − 1 be the reduced residues (mod v). Also, put a_{0} = −1. We define the function σ(v) by

σ(v) = max_{1≤j≤w} |a_{j} − a_{j−1}| .

We are then able to give the analogous result to Theorems 5, and 6 when the compatibility condition fails.

Proposition 13. Suppose ξ_{1}, ξ_{2} are both irrationals exceeding 1 and that (15) holds. Then, if u > σ(v), there are infinitely many primes in B(ξ, η) for all η ∈ ℝ^{2}. However, if u ≤ σ(v), there exist values η ∈ ℝ^{2} such that B(ξ, η) only contains integers n with (n, v) > 1.

The example we gave above had v = 3 which gives σ(v) = 2 = u and so the theorem predicts there exist values η ∈ ℝ^{2} such that B(ξ, η) only contains integers n which are divisible by 3.

Proof. In the proof of Theorem 5 all we needed there essentially was mα_{1} + nα_{2} > tn. Now mα_{1} + nα_{2} = \frac{u}{v}. However

tn = \{nβ_{2} + mβ_{1} + \frac{au}{v}\} ,

(replacing tn with 1 if t = 0). Using the definition of σ(v) the correct choice for a with (a, v) = 1 yields tn ≤ σ(v)/v. Hence there are solutions with p ≡ a (mod v) if u > σ(v). However if u ≤ σ(v) we can choose η so that tn ≥ σ(v)/v and the original simultaneous Diophantine inequalities cannot be satisfied.

We can similarly deal with the case when (15) holds with n < 0. Modifying the proof of Theorem 7 supplies the following result.

Proposition 14. Suppose ξ_{1}, ξ_{2} are both irrationals exceeding 1 and that

\frac{m}{ξ_{1}} − \frac{n}{ξ_{2}} = \frac{u}{v} ,  (16)

with positive integers m, n, u, v such that v ≥ 2, (m, n) = (u, v) = 1. Then, if m/ξ_{1} > σ(v), there are infinitely many primes in B(ξ, η) for all η ∈ ℝ^{2}. However, if m/ξ_{1} < σ(v), there exist values η ∈ ℝ^{2} such that B(ξ, η) only contains integers n with (n, v) > 1.

Combining the above with Theorem 5 produces the following comprehensive result.

Theorem 15. Suppose ξ_{1}, ξ_{2} are both irrationals exceeding 1 and that B(ξ, η) contains more than one element. Then if B(ξ, η) does not contain infinitely many primes, there are positive integers m, n, u, v with v ≥ 2, (m, n) = (u, v) = 1 and either

(i) (15) holds with u ≤ σ(v) or (ii) (16) holds with m/ξ_{1} < σ(v). In either case (i) or (ii) each of the infinitely many elements n of B(ξ, η) satisfies (n, v) > 1.

10 Acknowledgement

The author thanks the referee for his useful comments on the first version of this paper.

References

[1] R. C. Baker and L. Zhao, Gaps between primes in Beatty sequences. Preprint, 2014,

    available at http://arxiv.org/abs/1411.2989.

[2] A. Balog and J. Friedlander, Simultaneous Diophantine approximation using primes, Bull. London Math. Soc. 20 (1988), 289–292.

[3] W. D. Banks and I. Shparlinski, Prime numbers with Beatty sequences, Colloq. Math. 115 (2009), 147–157.

[4] S. Beatty, A. Ostrowski, J. Hyslop, and A. C. Aitken, Problems and solutions, Amer. Math. Monthly 34 (1927), 159–160.

[5] J. Brüdern and K. Kawada, The localisation of primes in arithmetic progressions of irrational modulus, Colloq. Math. 123 (2011), 53–61.

[6] Y. Ginosar and I. Yona, A model for pairs of Beatty sequences, Amer. Math. Monthly 119 (2012), no. 8, 636–645.

[7] R. L. Graham, Covering the positive integers by disjoint sets of the form {[nα + β] : n = 1, 2, …}, J. Combinatorial Theory Ser. A 15 (1973), 354–358.

[8] G. Harman, Simultaneous Diophantine approximation with primes, J. London Math. Soc. 39 (1989), 405–413.

[9] P. Hegarty, On m-covering families of Beatty sequences with irrational moduli, J. Number Theory 132 (2012), 2277–2296.

[10] G. Lü and H. Sun, The ternary Goldbach-Vinogradov theorem with almost equal primes from the Beatty sequence, Ramanujan J. 30 (2013), 153–161.

[11] R. Morikawa, Disjoint sequences generated by the bracket function, Bull. Fac. Liberal Arts, Nagasaki Univ. 26 (1985), 1–13.

[12] T. Skolem, Über einige Eigenschaften der Zahlenmengen [αn+β] bei irrationalem α mit einleitenden Bemerkungen über einige kombinatorische Probleme, Norske Vid. Selsk. Forh. Trondheim 30 (1957), 42–49.

[13] J. W. Strutt (3rd Baron Rayleigh), The Theory of Sound 2nd edition, Macmillan, 1894.

Available at https://archive.org/details/theorysound00raylgoog.

[14] J. V. Uspensky, On a problem arising out of the theory of a certain game, Amer. Math. Monthly 34 (1927), 516–521.

[15] R. C. Vaughan, The general Goldbach problem with Beatty primes. Ramanujan J. 34 (2014), 347–359.

[16] I. M. Vinogradov, The Method of Trigonometric Sums in the Theory of Numbers, translated by A. Davenport and K. F. Roth, revised edition, Dover Publications, 2004.

2010 Mathematics Subject Classification: Primary 11B83; Secondary 11N13; 11J71. Keywords: Beatty sequence, prime number.

Received May 26 2015; revised version received July 4 2015. Published in Journal of Integer Sequences, July 4 2015.

Return to Journal of Integer Sequences home page.