Two Remarks on the Largest Prime Factors of n and n + 1

Sungjin Kim Department of Mathematics Santa Monica College California State University, Northridge 18111 Nordhoff Street Northridge, CA 91330 USA

                     sungjin.kim@csun.edu

Abstract Let P (n) be the largest prime factor of n. We give an alternative proof of the existence of infinitely many n such that P (n) > P (n + 1) > P (n + 2). Further, we prove that the set {P (n+1)/P (n)}_{n∈ℕ} has infinitely many limit points {0, x_{n}, 1, y_{n}}_{n∈ℕ} with 0 < x_{n} < 1 < y_{n} and lim x_{n} = lim y_{n} = 1.

1 Introduction

Let n ≥ 2 be a positive integer. Let P (n) denote denote the largest prime factor of n. Erdős and Pomerance [4] proved that the number of n ≤ x such that P (n) < P (n + 1) is at least 0.0099x, and the same holds for P (n) > P (n + 1). This lower density 0.0099 was subsequently improved by several authors (0.05544 by de la Bretèche, Pomerance and Tenenbaum [2], 0.1063 by Z. Wang [14]). The current record holders are Lü and Wang [7], who proved that the lower density is at least 0.2017.

Erdős and Pomerance [4] also noted that the three patterns P (n) < P (n+1) > P (n+2), P (n) > P (n + 1) < P (n + 2), and P (n) < P (n + 1) < P (n + 2) occur infinitely often. They presented a simple proof for the infinitude of the third pattern. Namely, they took

n = p^{2^{m}} − 1, n + 1 = p^{2^{m}}, and n + 2 = p^{2^{m}} + 1,

where p is prime and m = inf{k|P (p^{2^{k}} + 1) > p}. They left the infinitude of the fourth pattern P (n) > P (n + 1) > P (n + 2) as an open problem.

This problem was later solved by Balog [1], who showed that the number of occurrence of this pattern for n ≤ x is ≫ \sqrt{x}. Building on earlier results by Matomäki, Radziwiłł, and Tao [10], and Teräväinen [12], Tao and Teräväinen [13] proved that the following sets have positive lower density:

{n ∈ ℕ | P (n) < P (n + 1) < P (n + 2) > P (n + 3)} and
{n ∈ ℕ | P (n) > P (n + 1) > P (n + 2) < P (n + 3)}.

Using the Maynard-Tao theorem [11], in this paper we provide a simple alternative proof of the infinitude of the patterns P (n) < P (n + 1) < P (n + 2) and P (n) > P (n + 1) > P (n + 2). We prove that both patterns occur for ≫ x/(log x)^{50} values of n ≤ x. The result is weaker than Tao and Teräväinen’s, and stronger than Balog’s.

Theorem 1. For sufficiently large x, we have

#\{n ≤ x | P (n) < P (n + 1) < P (n + 2)\} ≫ \frac{x}{(log x)^{50}} and

#\{n ≤ x | P (n) > P (n + 1) > P (n + 2)\} ≫ \frac{x}{(log x)^{50}} .

Erdős and Pomerance [4, Theorem 1] proved that for any ϵ > 0, there is δ > 0 such that the number of n ≤ x with

x^{−δ} < \frac{P (n + 1)}{P (n)} < x^{δ}

is less than ϵx. They remarked that this means P (n) and P (n + 1) are usually not close. In the opposite direction, we prove that this ratio can approach arbitrarily close to 1 from both sides.

Theorem 2. For any ϵ > 0, we have

# \{n ≤ x |1 ≤ \frac{P (n + 1)}{P (n)} < 1 + ϵ\} ≫_{ϵ} \frac{x}{(log x)^{50}} and

# \{n ≤ x |1 − ϵ < \frac{P (n + 1)}{P (n)} ≤ 1\} ≫_{ϵ} \frac{x}{(log x)^{50}} .

Let R := \{\frac{P (n+1)}{P (n)} | n ∈ ℕ\}. As a direct consequence of Theorem 2, we obtain that 1 ∈ \overline{R}. From the proof of Theorem 2, we obtain a finite set {a_{1}, …, a_{50}} ⊆ ℕ with 1 ≤ a_{i} < a_{j} for each 1 ≤ i < j ≤ 50 such that a_{j_{1}}/a_{i_{1}} ∈ \overline{R} ∩ (1, ∞) for some 1 ≤ i_{1} < j_{1} ≤ 50, and a_{i_{2}}/a_{j_{2}} ∈ \overline{R} ∩ (0, 1) for some 1 ≤ i_{2} < j_{2} ≤ 50. Changing a_{i} with ϵ, we obtain a sequence rational numbers with 0 < x_{n} < 1 < y_{n} such that lim x_{n} = lim y_{n} = 1 and \{x_{n}, y_{n}\}_{n∈ℕ} ⊆ \overline{R}.

In fact, there is an elementary proof of 1 ∈ \overline{R}. This elementary proof is based on a solution (ϵ = 1 in the following argument) that appeared in Mathematics Stack Exchange [3] by Barry Cipra. For any 0 < ϵ ≤ 1, take primes p and q satisfying p < q < (1 + ϵ)p so that

\frac{1}{1 + ϵ} < \frac{p}{q} < 1 < \frac{q}{p} < 1 + ϵ.

By the extended Euclidean algorithm, there exist integers u and v with 0 < u < q, 0 < v < p and pu − qv = 1. Let U = q − u, V = p − v. Then qV − pU = 1. The integers qu and qV have q as largest prime factor. Since u + U = q < (1 + ϵ)p, at least one of u ≤ p or U ≤ p holds. If u ≤ p, then p is the largest prime factor of pu. If U ≤ p, then p is also the largest prime factor of pU. Thus, either one of the following holds:

n = qv, n + 1 = pu, \frac{P (n + 1)}{P (n)} = \frac{p}{q},

or

n = pU, n + 1 = qV, \frac{P (n + 1)}{P (n)} = \frac{q}{p}.

Therefore, 1 ∈ \overline{R} follows. From this argument the number of n ≤ x with \frac{1}{1+ϵ} < \frac{P (n+1)}{P (n)} < 1+ϵ is ≫_{ϵ} x/(log x)^{2}. Slightly modifying this argument, we have for any x ∈ [1, 2], either x or 1/x is in \overline{R}. However, this argument does not determine whether a limit point is in [0, 1) or (1, ∞).

By Dirichlet’s theorem on primes in arithmetic progressions, it is easy to see that 0 is also a limit point of R. For if we take a prime n = ar − 1, with a large, then P (n) = ar − 1 and P (n+1) ≤ max(a, r). Assuming the prime k-tuples conjecture (Conjecture 4), we prove that all nonnegative real numbers are limit points of R.

Theorem 3 (Conditional). Assuming the prime k-tuples conjecture (Conjecture 4), we have \overline{R} = [0, ∞).

2 Estimates on the numbers of prime k-tuples

A set of k-tuple of linear forms {a_{1}x + b_{1}, … a_{k}x + b_{k}} is said to be admissible if for any prime p there is x_{p} ∈ ℤ such that p ∤ ∏_{i=1}^{k}(a_{i}x_{p} + b_{i}). We consider the tuples with

∏_{i} a_{i} ≠ 0 and ∏_{i<j}(a_{i}b_{j} − a_{j}b_{i}) ≠ 0.

The following is a special case of Bateman-Horn conjecture (a quantitative estimate on Dickson’s prime k-tuples conjecture).

Conjecture 4 (Bateman-Horn). Let k ≥ 2 and A_{k} = {a_{1}x+b_{1}, …, a_{k}x+b_{k}} be an admissible set of linear forms. Then for sufficiently large x, the number R_{k}(x) of r ≤ x such that a_{i}x+b_{i}, 1 ≤ i ≤ k are all prime satisfies

R_{k}(x) ≫_{A_{k}} \frac{x}{(log x)^{k}} .

Substantial progress toward this conjecture begin with Zhang’s result [15] on bounded gaps in primes. Subsequently, Maynard [8] and Polymath8b ([11] led by Tao) improved upon Zhang’s result. We state a quantitative form of the Maynard-Tao theorem for admissible sets of linear forms. The proof requires slight modifications of [11] and the stated lower bound can be found in [11, Remark 32]. Note that the following is unconditional.

Lemma 5 (Maynard-Tao-Polymath8b). Let A = {a_{1}r + b_{1}, …, a_{50}r + b_{50}} be an admissible set of linear forms. Then for sufficiently large x, the number R(A, x) of r ≤ (x − max_{i} b_{i})/ max_{i} a_{i} such that at least two of the linear forms are primes satisfies

R(A, x) ≫_{A} \frac{x}{(log x)^{50}} .

We will apply the above lemma in the following two special cases:

Case 1. 0 < a_{1} < ⋯ < a_{k} and b_{i} = 1 for all i = 1, …, k.

Case 2. 0 < a_{1} < ⋯ < a_{k} and b_{i} = −1 for all i = 1, …, k.

The set of linear forms in these cases is always admissible.

3 The main lemma

We construct a special sequence {a_{i}} by the following inductive process.

Lemma 6 (The main lemma). Let k ≥ 2 and e_{k} = 1. For each 0 ≤ j ≤ k − 2, assume that {e_{k−j}, …, e_{k}} satisfies

∑_{s<i≤t} e_{i} | ∑_{k−j≤i≤s} e_{i} for any k − j ≤ s < t ≤ k.

Let e_{k−j−1} be a multiple of

lcm { ∑_{s≤i≤t} e_{i} |k − j ≤ s < t ≤ k} .

Then a_{i} = ∑_{m≤i} e_{m} satisfies 0 < a_{j} − a_{i} | a_{i} for each 1 ≤ i < j ≤ k.

Proof. The proof is clear from the inductive construction.

We exhibit some sequences {a_{i}} that can be produced by the main lemma.

Example 7. If k = 2, then let {e_{1}, e_{2}} = {1, 1} and {a_{1}, a_{2}} = {1, 2}.

If k = 3, then let {e_{1}, e_{2}, e_{3}} = {2, 1, 1} and {a_{1}, a_{2}, a_{3}} = {2, 3, 4}.

If k = 4, then let {e_{1}, e_{2}, e_{3}, e_{4}} = {12, 2, 1, 1} and {a_{1}, a_{2}, a_{3}, a_{4}} = {12, 14, 15, 16}.

If k = 5, then let {e_{1}, e_{2}, e_{3}, e_{4}, e_{5}} = {1680, 12, 2, 1, 1} and

{a_{1}, a_{2}, a_{3}, a_{4}, a_{5}} = {1680, 1692, 1694, 1695, 1696}.

Note that e_{1} can be made arbitrarily large in the final inductive step. We will use the sequence {a_{i}}_{1≤i≤50}.

Lemma 8. Let {a_{i}}_{1≤i≤50} be a sequence produced in the main lemma. That is, 0 < a_{j} −a_{i} | a_{i} for each 1 ≤ i < j ≤ 50. Suppose that a_{i}r + 1 and a_{j}r + 1 are primes. Then by taking

n = \frac{a_{i}}{a_{j} − a_{i}} (a_{j}r + 1), n + 1 = \frac{a_{j}}{a_{j} − a_{i}} (a_{i}r + 1),  (1)

we have for sufficiently large r,

P (n) = a_{j}r + 1, P (n + 1) = a_{i}r + 1.

Now suppose that a_{i}r − 1 and a_{j}r − 1 are primes. Then by taking

n = \frac{a_{j}}{a_{j} − a_{i}} (a_{i}r − 1), n + 1 = \frac{a_{i}}{a_{j} − a_{i}} (a_{j}r − 1),  (2)

we have for sufficiently large r,

P (n) = a_{i}r − 1, P (n + 1) = a_{j}r − 1.

Proof. We take large enough r so that a_{1}r − 1 exceeds the largest prime factor of ∏ a_{i}.

Remark 9. The author recently learned that a sequence {a_{i}} with the property 0 < a_{j} −a_{i} | a_{i} for each 1 ≤ i < j was obtained earlier by Heath-Brown [6, Lemma 1], and such a sequence is used in an unpublished work of Maynard and Ford [5, Theorem 7.18]. Using such a sequence and Lemma 8 (1), Maynard and Ford proved that there is a constant B > 0 so that P (n) ≥ n/B and P (n + 1) ≥ (n + 1)/B for infinitely many n.

4 Proof of theorems

4.1 Proof of Theorem 1

Proof. Let {a_{i}}_{1≤i≤50} be a sequence produced in the main lemma. We apply (1) of Lemma 8. By letting n + 2 divisible by \frac{a_{j}}{a_{j}−a_{i}} + 1, we obtain P (n) > P (n + 1) > P (n + 2) for n in (1). For this idea to work, we need to require r to be divisible by \frac{a_{j}}{a_{j}−a_{i}} + 1 for any choice of 1 ≤ i < j ≤ 50. To see this, we let

M = lcm \{\frac{a_{j}}{a_{j} − a_{i}} + 1 | 1 ≤ i < j ≤ 50\} .

Then we work with the admissible set of linear forms {a_{i}Mr + 1}_{1≤i≤50}. By Lemma 5 and the pigeonhole principle, there is a pair (i, j), 1 ≤ i < j ≤ 50 depending on x such that a_{i}Mr + 1 and a_{j}Mr + 1 are primes for ≫ x/(log x)^{50} values of r ≤ (x − a_{50})/(a_{50}^{2}M). For such r ≥ r_{0}, we have n = \frac{a_{i}}{a_{j}−a_{i}} (a_{j}Mr + 1) ≤ x, P (n) = a_{j}Mr + 1, P (n + 1) = a_{i}Mr + 1, and P (n + 2) ≤ (n + 2)/(\frac{a_{j}}{a_{j}−a_{i}} + 1). Thus, P (n) > P (n + 1) > P (n + 2) is satisfied for such r.

To obtain an analogous result on P (n) < P (n + 1) < P (n + 2), we apply Part (2) of Lemma 8. By letting n − 1 divisible by \frac{a_{j}}{a_{j}−a_{i}} + 1, we obtain P (n − 1) < P (n) < P (n + 1) for n in (2). Then we work with the admissible set of linear forms {a_{i}Mr − 1}_{1≤i≤50}. The rest of the argument is similar to the previous case.

4.2 Proof of Theorem 2

Proof. Let ϵ > 0 be arbitrary. We show that the number of n ≤ x with 1 − ϵ < \frac{P (n+1)}{P (n)} ≤ 1 is ≫_{ϵ} \frac{x}{(log x)^{50}} . In the inductive process in Lemma 6, we let e_{1} be large enough to have

1 − ϵ < \frac{a_{i}}{a_{j}} ≤ 1 for each 1 ≤ i < j ≤ 50.

Then we apply Lemma 8 (1) to conclude the existence of a pair (i, j), 1 ≤ i < j ≤ 50 depending on x such that a_{i}r + 1 and a_{j}r + 1 are primes for ≫_{ϵ} x/(log x)^{50} values of r ≤ (x − a_{50})/a_{50}^{2}. It is clear that \frac{a_{i}r+1}{a_{j}r+1} = \frac{a_{i}}{a_{j}} + \frac{a_{j}−a_{i}}{a_{j}(a_{j}r+1)}. Since P (n) = a_{j}r + 1 and P (n + 1) = a_{i}r + 1 for such r by Lemma 8 (1), we have

1 ≥ \frac{P (n + 1)}{P (n)} = \frac{a_{i}r + 1}{a_{j}r + 1} > \frac{a_{i}}{a_{j}} > 1 − ϵ.

The result now follows.

To obtain an analogous result for 1 ≤ \frac{P (n+1)}{P (n)} < 1 + ϵ, we apply Lemma 8 (2).

4.3 Proof of Theorem 3

Proof. Let a_{1} be an even positive integer, and a_{2} be a positive integer with (a_{1}, a_{2}) = 1. By Bezout’s identity, we can find positive integers b_{1} and b_{2} such that a_{1}b_{2} − a_{2}b_{1} = (a_{1}, a_{2}) = 1. The sets of linear forms {a_{1}r + b_{1}, a_{2}r + b_{2}} and {a_{1}r − b_{1}, a_{2}r − b_{2}} are admissible. By Conjecture 4, there are infinitely many r such that both of these forms are primes. We take

n = a_{2}(a_{1}r + b_{1}), n + 1 = a_{1}(a_{2}r + b_{2})

or

n = a_{1}(a_{2}r − b_{2}), n + 1 = a_{2}(a_{1}r − b_{1}).

If we select r to exceed any prime factor of a_{1}a_{2}, then we see in both cases

\{\frac{a_{1}}{a_{2}} , \frac{a_{2}}{a_{1}} \} ⊆ \overline{R}.

Hence, it follows that any positive rational numbers with numerator and denominator of different parity are limit points of R, and consequently, \overline{R} = [0, ∞).

5 Acknowledgments

The author thanks Kevin Ford for bringing [6], [10], and [12] to his attention. The author also thanks an anonymous referee and Paul Pollack for careful reading of the paper and helpful comments.

References

[1] A. Balog, On triplets with descending largest prime factors, Studia Sci. Math. Hungar. 38 (2001), 45–50.

[2] R. de la Bretèche, C. Pomerance, and G. Tenenbaum, Products of ratios of consecutive integers, Ramanujan J. 9 (2005), 131–138.

[3] B. Cipra, Greatest prime divisor of consecutive integers, Mathematics Stack

    Exchange, available at https://math.stackexchange.com/questions/1894873/
    greatest-prime-divisor-of-consecutive-integers.

[4] P. Erdős and C. Pomerance, On the largest prime factors of n and n + 1, Aequationes Math. 17 (1978), 311–321.

[5] K. Ford, Sieve method lecture notes, 2020. Available at https://faculty.math.

    illinois.edu/~ford/sieve2020.pdf.

[6] D. R. Heath-Brown, The divisor function at consecutive integers, Mathematika 31 (1984), 141-–149.

[7] X. Lü and Z. Wang, On the largest prime factors of consecutive integers, preprint, 2018.

    Available at https://hal.archives-ouvertes.fr/hal-01797939/document.

[8] J. Maynard, Small gaps between primes, Ann. of Math. 181 (2015), 383–413.

[9] J. Maynard, Dense clusters of primes in subsets, Compos. Math. 152 (2016), 1517–1554.

[10] K. Matomäki, M. Radziwiłł, and T. Tao, Sign patterns of the Liouville and Möbius functions, Forum Math. Sigma, 4 (2016), Paper e14. Available at https://doi.org/

    10.1017/fms.2016.6.

[11] D. H. J. Polymath, Variants of Selberg sieve, and bounded intervals containing many primes, Res. Math. Sci. 1 (2014), 1–83.

[12] J. Teräväinen, On binary correlations of multiplicative functions, Forum Math. Sigma

    6 (2018), Paper e10. Available at https://doi.org/10.1017/fms.2018.10.

[13] T. Tao and J. Teräväinen, Value patterns of multiplicative functions and related sequences, Forum Math. Sigma 7 (2019), Paper e33. Available at https://doi.org/10.

    1017/fms.2019.28.

[14] Z. Wang, On the largest prime factors of consecutive integers in short intervals, Proc. Amer. Math. Soc. 145 (2017), 3211–3220.

[15] Y. Zhang, Bounded gaps between primes, Ann. of Math. 179 (2014), 1121–1174.

2010 Mathematics Subject Classification: Primary 11A41; Secondary 11N05. Keywords: largest prime factor, consecutive prime.

(Concerned with sequence \underline{A006530}.)

Received June 15 2020; revised versions received September 7 2020; October 16 2020. Published in Journal of Integer Sequences, October 16 2020.

Return to Journal of Integer Sequences home page.