Nontrivial Effective Lower Bounds for the Least Common Multiple of a q-Arithmetic Progression

Bakir Farhi Laboratoire de Mathématiques Appliquées Faculté des Sciences Exactes Université de Bejaia 06000 Bejaia Algeria

                     bakir.farhi@gmail.com

Abstract This paper is devoted to establish nontrivial effective lower bounds for the least common multiple of consecutive terms of a sequence (u_{n})_{n∈ℕ} whose general term has the form u_{n} = r(q^{n} − 1)/(q − 1) + u_{0}, where r, q and u_{0} are non-negative integers satisfying some specific conditions. This can be considered as a q-analog of the lower bounds already obtained by the author (in 2005) and by Hong and Feng (in 2006) for arithmetic progressions.

1 Introduction and the main results

Throughout this paper, we let ℕ^{∗} denote the set ℕ \ {0} of positive integers. For t ∈ ℝ, we let ⌊t⌋ denote the integer part of t. We say that an integer a is a multiple of a non-zero rational number r if the quotient a/r is an integer. The letter q always denotes a positive integer; furthermore, it is assumed, if necessary, that q ≥ 2. (This assumption is needed in Subsection 2.2.) Let us recall the standard notation of q-calculus (see, e.g., [10]). For n, k ∈ ℕ, with n ≥ k, we define

[n]_{q} := \frac{q^{n} − 1}{q − 1} for q ≠ 1 and [n]_{1} := n,
[n]_{q}! := [n]_{q}[n − 1]_{q} ⋯ [1]_{q} (with the convention [0]_{q}! = 1),
[ \begin{matrix}n \\ k \end{matrix} ]_{q} := \frac{[n]_{q}!}{[k]_{q}![n − k]_{q}!} = \frac{[n]_{q}[n − 1]_{q} ⋯ [n − k + 1]_{q}}{[k]_{q}!} .

The numbers [\begin{matrix}n \\ k \end{matrix}]_{q} are called the q-binomial coefficients (or the gaussian binomial coefficients) and it is well-known that they are all positive integers (see, e.g., [10]). From this last fact, we derive the important property stating that

For all a, b ∈ ℕ, the positive integer [a]_{q}![b]_{q}! divides the positive integer [a + b]_{q}!. (1)

Indeed, for a, b ∈ ℕ, we have \frac{[a+b]_{q}!}{[a]_{q}![b]_{q}!} = [\begin{matrix}a+b \\ a \end{matrix}]_{q} ∈ ℕ^{∗}.

The study of the least common multiple of consecutive positive integers began with Chebychev’s work [4] in his attempts to prove the prime number theorem. The latter defined ψ(n) := log lcm(1, 2, …, n) (∀n ≥ 2) and showed that \frac{ψ(n)}{n} is bounded between two positive constants, but he failed to prove that ψ(n) ∼_{+∞} n, which is equivalent to the prime number theorem. Quite recently, Hanson [7] and Nair [12], respectively, obtained the bounds lcm(1, 2, …, n) ≤ 3^{n} (∀n ∈ ℕ^{∗}) and lcm(1, 2, …, n) ≥ 2^{n} (∀n ≥ 7) in simple and elegant ways. Later, the author [5, 6] obtained nontrivial effective lower bounds for the least common multiple of consecutive terms in an arithmetic progression. In particular, he proved that for any u_{0}, r, n ∈ ℕ^{∗}, with gcd(u_{0}, r) = 1, we have lcm(u_{0}, u_{0} + r, …, u_{0} + nr) ≥ u_{0}(r + 1)^{n−1}. By developing the author’s method, Hong and Feng [8] managed to improve this lower bound to the optimal one:

lcm(u_{0}, u_{0} + r, …, u_{0} + nr) ≥ u_{0}(r + 1)^{n} (∀n ∈ ℕ),  (2)

which was already conjectured by the author [5, 6]. It is interesting to note that the method used to obtain (2) is based on the following fundamental theorem:

Theorem 1 ([6, Theorem 2]). Let I be a finite non-empty set of indices and (u_{i})_{i∈I} be a sequence of non-zero integers. Then the integer

lcm \{u_{i}, i ∈ I\} · lcm \{∏_{\begin{matrix}i∈I \\ i≠j \end{matrix}} |u_{i} − u_{j}|, j ∈ I\}

is a multiple of the integer ∏_{i∈I} u_{i}.

Furthermore, several authors obtained improvements of (2) for n sufficiently large in terms of u_{0} and r (see, e.g., [9, 11]). Concerning the asymptotic estimates and the effective upper bounds for the least common multiple of an arithmetic progression, we can cite the work of Bateman et al. [1] and the very recent work of Bousla [2].

In this paper, we apply and adapt the author’s method [5, 6] (slightly developed by Hong and Feng [8]) to establish nontrivial effective lower bounds for the least common multiple of consecutive terms in a sequence that we call a q-arithmetic progression; that is, a sequence (u_{n})_{n} with general term having the form u_{n} = r[n]_{q} + u_{0} (∀n ∈ ℕ), where r ∈ ℕ^{∗}, u_{0} ∈ ℕ and r, u_{0}, q satisfy some technical conditions. Our main results are the following:

Theorem 2 (The crucial result). Let q and r be two positive integers and u_{0} be a nonnegative integer. Let (u_{n})_{n∈ℕ} be the sequence of natural numbers whose general term u_{n} is given by u_{n} = r[n]_{q} + u_{0}. Suppose that gcd(u_{0}, r) = gcd(u_{1}, q) = 1. Then, for all positive integers n and k such that n ≥ k, the positive integer lcm (u_{k}, u_{k+1}, …, u_{n}) is a multiple of the rational number \frac{u_{k}u_{k+1}···u_{n}}{[n−k]_{q}!} .

Theorem 3. In the situation of Theorem 2, set

A := max (0 , \frac{u_{0}(q − 1) + 1 − r}{2r}) .

Then, for all positive integers n, we have

lcm (u_{1}, u_{2}, …, u_{n}) ≥ u_{1} (\frac{r + 1}{\sqrt{r}(A + 1)})^{n−1} q^{\frac{(n−1)(n−4)}{4}} .

Theorem 4. In the situation of Theorem 2, set

B := max (r , \frac{u_{0}(q − 1) + 1 − r}{2}) .

Then, for all positive integers n, we have

lcm (u_{1}, u_{2}, …, u_{n}) ≥ u_{1} (\frac{r + 1}{2\sqrt{B}})^{n−1} q^{\frac{(n−1)(n−4)}{4}} .

Note that Theorem 2 is a q-analog of a result due to the author (see [5, Théorème 2.3] or [6, Theorem 3]). Furthermore, Theorems 3 and 4 are derived from Theorem 2 by optimizing a certain specific expression, and they can be considered as q-analogs of the results by the author [5, 6] and those by Hong and Feng [8].

From Theorems 3 and 4, we immediately derive the following two corollaries:

Corollary 5. Let q, a and b be integers such that q ≥ 2, a ≥ 1 and b ≥ −a and let (v_{n})_{n∈ℕ} be the sequence of natural numbers whose general term v_{n} is given by

v_{n} = aq^{n} + b (∀n ∈ ℕ).

Suppose that gcd(aq, b) = gcd(a + b, q − 1) = 1 and set

A′ := max (0 , \frac{b}{2a} + \frac{1}{2a(q − 1)}) .

Then, for all positive integers n, we have

lcm (v_{1}, v_{2}, …, v_{n}) ≥ (aq + b) (\frac{a(q − 1) + 1}{\sqrt{a(q − 1)}(A′ + 1)})^{n−1} q^{\frac{(n−1)(n−4)}{4}} .

Corollary 6. In the situation of Corollary 5, set

B′ := max (a(q − 1) , \frac{b(q − 1) + 1}{2}) .

Then, for all positive integers n, we have

lcm (v_{1}, v_{2}, …, v_{n}) ≥ (aq + b) (\frac{a(q − 1) + 1}{2\sqrt{B′}})^{n−1} q^{\frac{(n−1)(n−4)}{4}} .

2 The proofs

Throughout the following, we fix q, r ∈ ℕ^{∗} and u_{0} ∈ ℕ such that gcd(u_{0}, r) = gcd(u_{1}, q) = 1 and we let (u_{n})_{n∈ℕ} denote the sequence of natural numbers defined by its general term u_{n} := r[n]_{q} + u_{0} (∀n ∈ ℕ).

2.1 Proof of Theorem 2

To prove Theorem 2, we need the following three lemmas:

Lemma 7. For all i, j ∈ ℕ, we have

|u_{i} − u_{j}| = rq^{min(i,j)}[|i − j|]_{q}.

Proof. Let i, j ∈ ℕ. Because the two sides of the equality of the lemma are both symmetric (in i and j), we may suppose without loss of generality that i ≥ j. Doing so we have

|u_{i} − u_{j}| = u_{i} − u_{j} = (r[i]_{q} + u_{0}) − (r[j]_{q} + u_{0})

= r ([i]_{q} − [j]_{q})

= r (\frac{q^{i} − 1}{q − 1} − \frac{q^{j} − 1}{q − 1})

= r (\frac{q^{i} − q^{j}}{q − 1} )

= rq^{j} (\frac{q^{i−j} − 1}{q − 1})

= rq^{j}[i − j]_{q}

= rq^{min(i,j)}[|i − j|]_{q},

as required. The lemma is proved.

Lemma 8. For all n ∈ ℕ, we have

gcd(u_{n}, r) = 1.

If in addition n ≥ 1, then we have

gcd(u_{n}, q) = 1.

Proof. Let n ∈ ℕ and let us show that gcd(u_{n}, r) = 1. This is equivalent to show that d = 1 is the only positive common divisor of u_{n} and r. So let d be a positive common divisor of u_{n} and r and let us show that d = 1. The hypotheses d|u_{n} and d|r together imply that d|(u_{n} − r[n]_{q}) = u_{0}. Hence d is a positive common divisor of u_{0} and r. But since gcd(u_{0}, r) = 1, it follows that d = 1, as required. Consequently, we have gcd(u_{n}, r) = 1.

Next, let n ∈ ℕ^{∗} and let us show that gcd(u_{n}, q) = 1. Equivalently, we have to show that d = 1 is the only positive common divisor of u_{n} and q. So let d be a positive common divisor of u_{n} and q and let us show that d = 1. The hypotheses d|u_{n} and d|q together imply that d|((rq^{n} + u_{0}q) − (q − 1)u_{n}) = r + u_{0} = u_{1}. So d is a positive common divisor of u_{1} and q. But since gcd(u_{1}, q) = 1, we conclude that d = 1, as required. Consequently, we have gcd(u_{n}, q) = 1. This completes the proof of the lemma.

Lemma 9. For all positive integers n and k such that n ≥ k and any j ∈ {k, k + 1, …, n}, we have

∑_{\begin{matrix}k≤i≤n \\ i≠j \end{matrix}} min(i, j) ≤ \frac{(n − k)(n + k − 1)}{2}.

Proof. Let n and k be positive integers such that n ≥ k and let j ∈ {k, k + 1, …, n}. We have

∑_{\begin{matrix}k≤i≤n \\ i≠j \end{matrix}} min(i, j) = ∑_{k≤i<j} min(i, j) + ∑_{j<i≤n} min(i, j)

= ∑_{k≤i<j} i + ∑_{j<i≤n} j

= \frac{(j − k)(j + k − 1)}{2} + (n − j)j

= \frac{2nj − j^{2} − k^{2} − j + k}{2}

= \frac{(n − k)(n + k − 1) + (n − j) − (n − j)^{2}}{2}

≤ \frac{(n − k)(n + k − 1)}{2}

(since n − j ≤ (n − j)^{2}, because n − j ∈ ℕ). The lemma is proved.

Now we are ready to prove the crucial Theorem 2:

Proof of Theorem 2. Let n and k be positive integers such that n ≥ k. By applying the fundamental Theorem 1 to the set of indices I = {k, k +1, …, n} and the sequence (u_{i})_{i∈I} = {u_{k}, u_{k+1}, …, u_{n}}, we find that the positive integer

lcm (u_{k}, u_{k+1}, …, u_{n}) · lcm \{ ∏_{\begin{matrix}k≤i≤n \\ i≠j \end{matrix}} |u_{i} − u_{j}|; j = k, …, n\}

is a multiple of the positive integer u_{k}u_{k+1} ⋯ u_{n}. Now let us find a simple multiple for the positive integer lcm {∏_{k≤i≤n,i≠j} |u_{i} − u_{j}|; j = k, …, n}. According to Lemma 7, we have for any j ∈ {k, k + 1, …, n}, that

∏_{\begin{matrix}k≤i≤n \\ i≠j \end{matrix}} |u_{i} − u_{j}| = ∏_{\begin{matrix}k≤i≤n \\ i≠j \end{matrix}} (rq^{min(i,j)}[|i − j|]_{q})

= r^{n−k}q^{∑\begin{matrix}k≤i≤n \\ i≠j \end{matrix} min(i,j)} ∏_{\begin{matrix}k≤i≤n \\ i≠j \end{matrix}} [|i − j|]_{q}

= r^{n−k}q^{∑\begin{matrix}k≤i≤n \\ i≠j \end{matrix} min(i,j)}[1]_{q}[2]_{q} ⋯ [j − k]_{q} × [1]_{q}[2]_{q} ⋯ [n − j]_{q}

= r^{n−k}q^{∑\begin{matrix}k≤i≤n \\ i≠j \end{matrix} min(i,j)}[j − k]_{q}![n − j]_{q}!,

which divides (according to Lemma 9 and Property (1)) the positive integer

r^{n−k}q^{\frac{(n−k)(n+k−1)}{2}} [n − k]_{q}!.

Consequently, the positive integer lcm{∏_{k≤i≤n,i≠j} |u_{i} − u_{j}|; j = k, …, n} divides the pos-

itive integer r^{n−k}q^{\frac{(n−k)(n+k−1)}{2}} [n − k]_{q}!. It follows (according to what obtained at the beginning of this proof) that the positive integer u_{k}u_{k+1} ⋯ u_{n} divides the positive integer r^{n−k}q^{\frac{(n−k)(n+k−1)}{2}} [n − k]_{q}! lcm (u_{k}, u_{k+1}, …, u_{n}). Next, since (according to Lemma 8) the integers u_{i} (i ≥ 1) are all coprime with r and q then the product u_{k}u_{k+1} ⋯ u_{n} is coprime with r^{n−k}q^{\frac{(n−k)(n+k−1)}{2}} , which shows (according to the Gauss lemma) that u_{k}u_{k+1} ⋯ u_{n} divides [n − k]_{q}! lcm (u_{k}, u_{k+1}, …, u_{n}). Equivalently, the positive integer lcm (u_{k}, u_{k+1}, …, u_{n}) is a multiple of the rational number \frac{u_{k}u_{k+1}···u_{n}}{[n−k]_{q}!} . This completes the proof.

2.2 Proofs of Theorems 3 and 4 and their corollaries

To deduce Theorems 3 and 4 from Theorem 2, we need some additional preparations. Since, for q = 1, Theorems 3 and 4 are immediate consequences of (2), we may suppose for the sequel that q ≥ 2. Next, we naturally extend the definition of u_{n} to negative indices n and for all n, k ∈ ℤ such that n ≥ k we define

C_{n,k} := \frac{u_{k}u_{k+1} ⋯ u_{n}}{[n − k]_{q}!} .

Furthermore, for a given positive integer n, the problem of determining the positive integer k ≤ n which maximizes C_{n,k} leads us to introduce the function f : ℝ → ℝ, defined as follows:

f(x) := q^{x−1} (rq^{x−1} + u_{0}(q − 1) + 1 − r) (∀x ∈ ℝ).

It is immediate that f increases, tends to 0 as x tends to (−∞) and satisfies, for all n ∈ ℕ^{∗}, the property

∀k ∈ ℤ : k > n ⇒ f(k) > q^{n}.

For a given positive integer n, these properties ensure the existence of a largest k_{n} ∈ ℤ satisfying f(k_{n}) ≤ q^{n}, and show, in addition, that k_{n} ≤ n. From the increase of f and the definition of k_{n} (n ∈ ℕ^{∗}), we derive that

∀k ∈ ℤ : k ≤ k_{n} ⟺ f(k) ≤ q^{n}.  (3)

Now since for any n ∈ ℕ^{∗} and any k ∈ ℤ, we have

f(k) ≤ q^{n} ⟺ q^{k−1} (rq^{k−1} + u_{0}(q − 1) + 1 − r) ≤ q^{n}

⟺ rq^{k−1} + u_{0}(q − 1) + 1 − r ≤ q^{n−k+1}

⟺ \frac{q^{n−k+1} − 1}{q − 1} ≥ r\frac{q^{k−1} − 1}{q − 1} + u_{0}

⟺ [n − k + 1]_{q} ≥ u_{k−1},

then Property (3) is equivalent to

∀k ∈ ℤ : k ≤ k_{n} ⟺ [n − k + 1]_{q} ≥ u_{k−1}.  (4)

For a given positive integer n, we set

ℓ_{n} := max(1, k_{n}).

Since k_{n} ≤ n, we have that ℓ_{n} ∈ {1, 2, …, n}.

Next, it is immediate that f satisfies the following inequality:

f(x − 1) ≤ \frac{1}{q}f(x)  (∀x ∈ ℝ).  (5)

For a fixed n ∈ ℕ^{∗}, the following lemmas aim to maximize the quantity C_{n,k} (1 ≤ k ≤ n) appearing in Theorem 2. Precisely, we shall determine two simple upper bounds for max_{1≤k≤n} C_{n,k} from which we derive our Theorems 3 and 4.

Lemma 10. Let n be a fixed positive integer. The sequence (C_{n,k})_{k∈ℤ,k≤n} is non-decreasing until k = k_{n}, and then it decreases. So it reaches its maximal value at k = k_{n}.

Proof. For any k ∈ ℤ, with k ≤ n, we have

C_{n,k} ≥ C_{n,k−1} ⟺ \frac{C_{n,k}}{C_{n,k−1}} ≥ 1

⟺ \frac{u_{k}u_{k+1} ⋯ u_{n}}{[n − k]_{q}!} /\frac{u_{k−1}u_{k} ⋯ u_{n}}{[n − k + 1]_{q}!} ≥ 1

⟺ \frac{[n − k + 1]_{q}}{u_{k−1}} ≥ 1

⟺ [n − k + 1]_{q} ≥ u_{k−1}

⟺ k ≤ k_{n} (according to (4)),

which concludes the proof.

From the last lemma, we obviously derive the following:

Lemma 11. Let n be a fixed positive integer. Then the sequence (C_{n,k})_{1≤k≤n} reaches its maximal value at k = ℓ_{n}. □

If n ∈ ℕ^{∗} is fixed, we have from Lemma 11 above that max_{1≤k≤n} C_{n,k} = C_{n,ℓ_{n}}; however, the exact value of C_{n,ℓ_{n}} (in terms of n, q, r, u_{0}) is complicated. The lemmas below provide studies of the sequences (k_{n})_{n}, (ℓ_{n})_{n} and (C_{n,ℓ_{n}})_{n} in order to find a good lower bound for C_{n,ℓ_{n}} that has a simple expression in terms of n, q, r, u_{0}.

Lemma 12. For all positive integers n, we have

k_{n} ≤ k_{n+1} ≤ k_{n} + 1.

In other words, we have

k_{n+1} ∈ {k_{n}, k_{n} + 1} .

Proof. Let n be a fixed positive integer. By definition of the integer k_{n}, we have

f(k_{n}) ≤ q^{n} ≤ q^{n+1},

which implies (by definition of the integer k_{n+1}) that

k_{n+1} ≥ k_{n}.

On the other hand, we have (according to (5) and the definition of the integer k_{n+1})

f(k_{n+1} − 1) ≤ \frac{1}{q}f(k_{n+1}) ≤ \frac{1}{q} q^{n+1} = q^{n},

which implies (by definition of the integer k_{n}) that

k_{n} ≥ k_{n+1} − 1;

that is

k_{n+1} ≤ k_{n} + 1.

This completes the proof of the lemma.

Lemma 13. For all positive integers n, we have

ℓ_{n+1} ∈ {ℓ_{n}, ℓ_{n} + 1} .

In addition, in the case when ℓ_{n+1} = ℓ_{n} + 1, we have ℓ_{n} = k_{n} and ℓ_{n+1} = k_{n+1} = k_{n} + 1.

Proof. Let n be a fixed positive integer. By Lemma 12, we have that

k_{n} ≤ k_{n+1} ≤ k_{n} + 1.

Hence

max(1, k_{n}) ≤ max(1, k_{n+1}) ≤ max(1, k_{n} + 1) = max(0, k_{n}) + 1 ≤ max(1, k_{n}) + 1;

therefore

ℓ_{n} ≤ ℓ_{n+1} ≤ ℓ_{n} + 1.

This confirms the first part of the lemma.

Now let us show the second part of the lemma. So suppose that ℓ_{n+1} = ℓ_{n} + 1 and show that ℓ_{n} = k_{n} and ℓ_{n+1} = k_{n+1} = k_{n} + 1. Since ℓ_{n} = max(1, k_{n}) ≥ 1 and ℓ_{n+1} = ℓ_{n} + 1 then ℓ_{n+1} ≥ 2. This implies that ℓ_{n+1} ≠ 1; thus ℓ_{n+1} = k_{n+1} (since ℓ_{n+1} = max(1, k_{n+1}) ∈ {1, k_{n+1}}). Using this and Lemma 12 above, we derive that ℓ_{n} = ℓ_{n+1} − 1 = k_{n+1} − 1 ≤ (k_{n} +1)−1 = k_{n}; that is ℓ_{n} ≤ k_{n}. But since ℓ_{n} = max(1, k_{n}) ≥ k_{n}, we conclude that ℓ_{n} = k_{n}. This completes the proof of the second part of the lemma and finishes the proof.

Lemma 14. For all positive integers n, we have

C_{n+1,ℓ_{n+1}} ≥ (r + 1)q^{ℓ_{n}−1}C_{n,ℓ_{n}}.

Proof. Let n be a fixed positive integer. By Lemma 13, we have that ℓ_{n+1} ∈ {ℓ_{n}, ℓ_{n+1}}. So we have to distinguish two cases: Case 1: (if ℓ_{n+1} = ℓ_{n}) In this case, we have

C_{n+1,ℓ_{n+1}} = C_{n+1,ℓ_{n}} = \frac{u_{ℓ_{n}}u_{ℓ_{n}+1} ⋯ u_{n}u_{n+1}}{[n + 1 − ℓ_{n}]_{q}!} = \frac{u_{ℓ_{n}}u_{ℓ_{n}+1} ⋯ u_{n}}{[n − ℓ_{n}]_{q}!} · \frac{u_{n+1}}{[n + 1 − ℓ_{n}]_{q}}
= C_{n,ℓ_{n}} · \frac{u_{n+1}}{[n + 1 − ℓ_{n}]_{q}} .  (6)

Next, we have

u_{n+1} − (r + 1)q^{ℓ_{n}−1}[n + 1 − ℓ_{n}]_{q} = r[n + 1]_{q} + u_{0} − (r + 1)q^{ℓ_{n}−1} (\frac{q^{n+1−ℓ_{n}} − 1}{q − 1})

= r (\frac{q^{n+1} − 1}{q − 1}) + u_{0} − (r + 1) (\frac{q^{n} − q^{ℓ_{n}−1}}{q − 1} )

= \frac{r(q^{n+1} − 1) + u_{0}(q − 1) − (r + 1)(q^{n} − q^{ℓ_{n}−1})}{q − 1}

= \frac{rq^{n+1} − (r + 1)q^{n} + (r + 1)q^{ℓ_{n}−1} − r + u_{0}(q − 1)}{q − 1}

= \frac{(r(q − 1) − 1)q^{n} + [(r + 1)q^{ℓ_{n}−1} − r] + u_{0}(q − 1)}{q − 1}

≥ 0

(since q ≥ 2, r ≥ 1, u_{0} ≥ 0 and ℓ_{n} ≥ 1). Thus

\frac{u_{n+1}}{[n + 1 − ℓ_{n}]_{q}} ≥ (r + 1)q^{ℓ_{n}−1}.

By substituting this into (6), we get

C_{n+1,ℓ_{n+1}} ≥ (r + 1)q^{ℓ_{n}−1}C_{n,ℓ_{n}},

as required. Case 2: (if ℓ_{n+1} = ℓ_{n} + 1)

In this case, we have (according to Lemma 13): ℓ_{n} = k_{n} and ℓ_{n+1} = k_{n+1} = k_{n} + 1. Thus, we have

C_{n+1,ℓ_{n+1}} = C_{n+1,k_{n}+1} = \frac{u_{k_{n}+1}u_{k_{n}+2} ⋯ u_{n}u_{n+1}}{[n − k_{n}]_{q}!} = C_{n,k_{n}} · \frac{u_{n+1}}{u_{k_{n}}} = C_{n,ℓ_{n}} · \frac{u_{n+1}}{u_{k_{n}}} .  (7)

Next, according to the inequality of the right-hand side of (4) (applied for (n + 1) instead of n and k_{n+1} instead of k), we have (since k_{n+1} ≤ k_{n+1})

u_{k_{n}} = u_{k_{n+1}−1} ≤ [(n + 1) − k_{n+1} + 1]_{q} = [n − k_{n} + 1]_{q}.

Hence

u_{n+1} − (r + 1)q^{ℓ_{n}−1}u_{k_{n}} = u_{n+1} − (r + 1)q^{k_{n}−1}u_{k_{n}}

≥ u_{n+1} − (r + 1)q^{k_{n}−1}[n − k_{n} + 1]_{q}

= r (\frac{q^{n+1} − 1}{q − 1}) + u_{0} − (r + 1)q^{k_{n}−1} (\frac{q^{n−k_{n}+1} − 1}{q − 1})

= \frac{r(q^{n+1} − 1) + u_{0}(q − 1) − (r + 1)(q^{n} − q^{k_{n}−1})}{q − 1}

= \frac{(r(q − 1) − 1)q^{n} + u_{0}(q − 1) + (r + 1)q^{k_{n}−1} − r}{q − 1}

≥ 0

(since q ≥ 2, r ≥ 1, u_{0} ≥ 0 and k_{n} = ℓ_{n} ≥ 1). Thus

\frac{u_{n+1}}{u_{k_{n}}} ≥ (r + 1)q^{ℓ_{n}−1}.

By substituting this into (7), we get

C_{n+1,ℓ_{n+1}} ≥ (r + 1)q^{ℓ_{n}−1}C_{n,ℓ_{n}},

as required. The proof of the lemma is complete.

By induction, we derive the following from Lemma 14 above:

Corollary 15. For all positive integers n, we have

C_{n,ℓ_{n}} ≥ u_{1}(r + 1)^{n−1}q^{∑_{i=1}^{n−1}(ℓ_{i}−1)}.

Proof. Let n be a positive integer. From Lemma 14, we have

C_{n,ℓ_{n}} = C_{1,ℓ_{1}} ∏_{i=1}^{n−1} \frac{C_{i+1,ℓ_{i+1}}}{C_{i,ℓ_{i}}} ≥ C_{1,ℓ_{1}} ∏_{i=1}^{n−1} \{(r + 1)q^{ℓ_{i}−1}\} = C_{1,ℓ_{1}}(r + 1)^{n−1}q^{∑_{i=1}^{n−1}(ℓ_{i}−1)}.

Next, since k_{1} ≤ 1, we have ℓ_{1} = max(1, k_{1}) = 1; hence C_{1,ℓ_{1}} = C_{1,1} = \frac{u_{1}}{[0]_{q}!} = u_{1}. Consequently, we have

C_{n,ℓ_{n}} ≥ u_{1}(r + 1)^{n−1}q^{∑_{i=1}^{n−1}(ℓ_{i}−1)},

as required. The corollary is proved.

From Theorem 2 and Corollary 15 above, we immediately deduce the following result:

Corollary 16. For all positive integers n, we have

lcm (u_{1}, u_{2}, …, u_{n}) ≥ u_{1}(r + 1)^{n−1}q^{∑_{i=1}^{n−1}(ℓ_{i}−1)}.

Proof. Let n be a fixed positive integer. Since the positive integer lcm (u_{1}, u_{2}, …, u_{n}) is obviously a multiple of the positive integer lcm (u_{ℓ_{n}}, u_{ℓ_{n}+1}, …, u_{n}), which is a multiple of the rational number \frac{u_{ℓn}u_{ℓn+1}···u_{n}}{[n−ℓ_{n}]_{q}!} = C_{n,ℓ_{n}} (according to Theorem 2), then we have

lcm (u_{1}, u_{2}, …, u_{n}) ≥ C_{n,ℓ_{n}}.

The result of the corollary then follows from Corollary 15. The proof is complete.

Remark 17. If we allow to take q = 1 in Corollary 16, then we exactly obtain the result of Hong and Feng [8] (recalled in (2)).

Now in order to derive an explicit lower bound for lcm (u_{1}, u_{2}, …, u_{n}) (n ≥ 1) from Corollary 16 above, it remains to bound the ℓ_{i} from below in terms of n, q, r and u_{0}. Here we just give two ways to bound the ℓ_{i} from below, but there are certainly other ways (perhaps more intelligent) to do this. We have the following lemmas:

Lemma 18. Let

A := max (0 , \frac{u_{0}(q − 1) + 1 − r}{2r}) .

Then, for all positive integers n, we have

ℓ_{n} > \frac{1}{2} (n − \frac{log r + 2 log(A + 1)}{log q}) .

Proof. Let n be a fixed positive integer. Since the inequality of the lemma is obvious for n ≤ \frac{log r+2 log(A+1)}{log q}, we may assume for the sequel that n > \frac{log r+2 log(A+1)}{log q}. Now for any x ≥ 1, we have

f(x) := q^{x−1} (rq^{x−1} + u_{0}(q − 1) + 1 − r)

= r ((q^{x−1} + \frac{u_{0}(q − 1) + 1 − r}{2r})^{2} − (\frac{u_{0}(q − 1) + 1 − r}{2r})^{2})

≤ r (q^{x−1} + \frac{u_{0}(q − 1) + 1 − r}{2r})^{2}

≤ r (q^{x−1} + A)^{2}

≤ r (q^{x−1} + Aq^{x−1})^{2}

= r(A + 1)^{2}q^{2(x−1)}.

By applying this for

x_{0} := \frac{1}{2} (n − \frac{log r + 2 log(A + 1)}{log q}) + 1

(which is > 1 according to our assumption n > \frac{log r+2 log(A+1)}{log q}), we get

f(x_{0}) ≤ r(A + 1)^{2}q^{n− \frac{log r+2 log(A+1)}{log q}} = q^{n}.

Then, since f is increasing and ⌊x_{0}⌋ ≤ x_{0}, we derive that

f(⌊x_{0}⌋) ≤ f(x_{0}) ≤ q^{n},

which implies (according to the definition of k_{n}) that

k_{n} ≥ ⌊x_{0}⌋ > x_{0} − 1.

Hence

ℓ_{n} := max(1, k_{n}) ≥ k_{n} > x_{0} − 1,

that is

ℓ_{n} > \frac{1}{2} (n − \frac{log r + 2 log(A + 1)}{log q}) ,

as required. The lemma is proved. Lemma 19. Let

B := max (r , \frac{u_{0}(q − 1) + 1 − r}{2}) .

Then, for all positive integers n, we have

ℓ_{n} > \frac{1}{2} (n − \frac{log(4B)}{log q}) .

Proof. Let n be a fixed positive integer. Since the inequality of the lemma is obvious for n ≤ \frac{log(4B)}{log q}, we may assume for the sequel that n > \frac{log(4B)}{log q}. Now for any x ≥ 1, we have

f(x) := q^{x−1} (rq^{x−1} + u_{0}(q − 1) + 1 − r)
≤ q^{x−1} (Bq^{x−1} + 2B)
< B (q^{x−1} + 1)^{2}
≤ B (2q^{x−1})^{2}
= 4Bq^{2(x−1)}.

By applying this for

x_{1} := \frac{1}{2} (n − \frac{log(4B)}{log q}) + 1

(which is > 1 according to our assumption n > \frac{log(4B)}{log q}), we get

f(x_{1}) ≤ 4Bq^{n− \frac{log(4B)}{log q}} = q^{n}.

Then, since f is increasing and ⌊x_{1}⌋ ≤ x_{1}, we derive that

f(⌊x_{1}⌋) ≤ f(x_{1}) ≤ q^{n},

which implies (according to the definition of k_{n}) that

k_{n} ≥ ⌊x_{1}⌋ > x_{1} − 1 = \frac{1}{2} (n − \frac{log(4B)}{log q}) .

Hence

ℓ_{n} := max(1, k_{n}) ≥ k_{n} > \frac{1}{2} (n − \frac{log(4B)}{log q}) ,

as required. The lemma is proved.

We are now ready to prove Theorems 3 and 4 announced in Section 1.

Proof of Theorem 3. By using successively Corollary 16 and Lemma 18, we have for all n ∈ ℕ^{∗} that

lcm (u_{1}, u_{2}, …, u_{n}) ≥ u_{1}(r + 1)^{n−1}q^{∑_{i=1}^{n−1}(ℓ_{i}−1)}

≥ u_{1}(r + 1)^{n−1}q^{\frac{(n−1)(n−4)}{4} − \frac{1}{2} \frac{log r+2 log(A+1)}{log q} (n−1)}

= u_{1} (\frac{r + 1}{\sqrt{r}(A + 1)})^{n−1} q^{\frac{(n−1)(n−4)}{4}} ,

as required.

Proof of Theorem 4. By using successively Corollary 16 and Lemma 19, we have for all n ∈ ℕ^{∗}

lcm (u_{1}, u_{2}, …, u_{n}) ≥ u_{1}(r + 1)^{n−1}q^{∑_{i=1}^{n−1}(ℓ_{i}−1)}

≥ u_{1}(r + 1)^{n−1}q^{\frac{(n−1)(n−4)}{4} − \frac{1}{2} \frac{log(4B)}{log q} (n−1)}

= u_{1} (\frac{r + 1}{2\sqrt{B}})^{n−1} q^{\frac{(n−1)(n−4)}{4}} ,

as required.

Proof of Corollary 5. It suffices to remark that v_{n} = a(q − 1)[n]_{q} + a + b (∀n ∈ ℕ) and then to apply Theorem 3 for the sequence (v_{n})_{n∈ℕ}. We just specify that the imposed conditions gcd(aq, b) = gcd(a + b, q − 1) = 1 guarantee the conditions gcd(v_{0}, r) = gcd(v_{1}, q) = 1 required in Theorem 3 (with r := a(q − 1)).

Proof of Corollary 6. We simply apply Theorem 4 for the sequence (v_{n})_{n∈ℕ}, after noticing that its general term can be written as: v_{n} = a(q − 1)[n]_{q} + a + b.

3 Numerical examples and remarks

By applying our main results, we get for example the following nontrivial effective estimates:

• lcm (2^{1} − 1, 2^{2} − 1, …, 2^{n} − 1) ≥ 2^{\frac{n(n−1)}{4}} (∀n ≥ 1) (Apply Theorem 3 for u_{n} = [n]_{2} = 2^{n} − 1).

• lcm (2^{1} + 1, 2^{2} + 1, …, 2^{n} + 1) ≥ 3 · 2^{\frac{(n−1)(n−4)}{4}} (∀n ≥ 1) (Apply one of the two corollaries 5 or 6 for v_{n} = 2^{n} + 1).

• lcm (3^{1} + 1, 3^{2} + 1, …, 3^{n} + 1) ≥ 4 · 3^{\frac{(n−1)(n−4)}{4}} (∀n ≥ 1) (Observe that lcm (3^{1} + 1, 3^{2} + 1, …, 3^{n} + 1) = 2 lcm (\frac{3^{1}+1}{2}, \frac{3^{2}+1}{2}, …, \frac{3^{n}+1}{2}) and apply

one of the two Theorems 3 or 4 for u_{n} = [n]_{3} + 1 = \frac{3^{n}+1}{2}).

Remark 20.

(a) Theorems 3 and 4 are incomparable in the sense that there are situations where Theorem 3 is stronger than Theorem 4, and other situations where we have the converse. For example, it is easy to verify that if u_{0}(q − 1) + 1 − r ≤ 0, then Theorem 3 is stronger than Theorem 4, while if u_{0}(q − 1) + 1 − 3r > 0, then Theorem 4 is stronger than Theorem 3.

(b) By refining the arguments of bounding from below the ℓ_{i} (that is the arguments of the proofs of Lemmas 18 and 19), it is perhaps possible to obtain a lower bound for lcm (u_{1}, u_{2}, …, u_{n}) (n ≥ 1) of the form

lcm (u_{1}, u_{2}, …, u_{n}) ≥ c (\frac{r + 1}{\sqrt{r}})^{n−1} q^{\frac{(n−1)(n−4)}{4}} ,

where c is a positive constant depending only on q, r and u_{0}. It appears that this is the best that can be expected from this method!

(c) It is remarkable that our lower bounds of lcm (u_{1}, u_{2}, …, u_{n}), for the considered sequences (u_{n})_{n}, are quite close to \sqrt{u_{1}u_{2} ⋯ u_{n}}. More precisely, we can easily deduce from our main results that in the same context, we have lcm (u_{1}, u_{2}, …, u_{n}) ≥ c_{3}c_{4}^{n}\sqrt{u_{1}u_{2} ⋯ u_{n}}, for some suitable positive constants c_{3} and c_{4}, depending only on q, r and u_{0}.

(d) There is something in common between our results and the recent result by Bousla and Farhi [3] providing effective bounds for lcm(U_{1}, U_{2}, …, U_{n}), when (U_{n})_{n∈ℕ} is a particular Lucas sequence; precisely, when (U_{n})_{n} is recursively defined by U_{0} = 0, U_{1} = 1 and U_{n+2} = P U_{n+1} − QU_{n} (∀n ∈ ℕ) for some P, Q ∈ ℤ^{∗}, with P^{2} − 4Q > 0 and gcd(P, Q) = 1. Indeed, if we take P = q + 1 and Q = q (for some integer q ≥ 2), we obtain that U_{n} = [n]_{q} and the Bousla-Farhi lower bound then gives

lcm ([1]_{q}, [2]_{q}, …, [n]_{q}) ≥ q^{\frac{n^{2}}{4} − \frac{n}{2} −1} (∀n ≥ 1),

which is almost the same as what we obtained in this paper.

References

[1] P. Bateman, J. Kalb, and A. Stenger, A limit involving least common multiples: 10797, Amer. Math. Monthly 109 (2002), 393–394.

[2] S. A. Bousla, Nontrivial upper bounds for the least common multiple of an arithmetic progression, preprint, 2020. Available at https://arxiv.org/abs/2004.07335.

[3] S. A. Bousla and B. Farhi, Identités et estimations concernant le plus petit commun multiple de suites à forte divisibilité, C. R. Math. Acad. Sci. Paris 358 (2020), 481–487.

[4] P. L. Chebyshev, Mémoire sur les nombres premiers, J. Math. Pures Appl. 17 (1852), 366–390.

[5] B. Farhi, Minorations non triviales du plus petit commun multiple de certaines suites finies d’entiers, C. R. Acad. Sci. Paris, Sér. I 341 (2005), 469–474.

[6] B. Farhi, Nontrivial lower bounds for the least common multiple of some finite sequences of integers, J. Number Theory 125 (2007), 393–411.

[7] D. Hanson, On the product of the primes, Canad. Math. Bull. 15 (1972), 33–37.

[8] S. Hong and W. Feng, Lower bounds for the least common multiple of finite arithmetic progressions, C. R. Acad. Sci. Paris, Sér. I 343 (2006), 695–698.

[9] S. Hong and S. D. Kominers, Further improvements of lower bounds for the least common multiples of arithmetic progressions, Proc. Amer. Math. Soc. 138 (2010), 809–813.

[10] V. Kac and P. Cheung, Quantum Calculus, Universitext, Springer-Verlag, 2002.

[11] D. Kane and S. D. Kominers, Asymptotic improvements of lower bounds for the least common multiples of arithmetic progressions, Canad. Math. Bull. 57 (2014), 551–561.

[12] M. Nair, On Chebyshev-type inequalities for primes, Amer. Math. Monthly 89 (1982), 126–129.

2010 Mathematics Subject Classification: Primary 11A05; Secondary 11B25, 11B65, 05A30. Keywords: least common multiple, q-analog, arithmetic progression.

Received September 21 2020; revised version received February 17 2021. Published in Journal of Integer Sequences, February 17 2021.

Return to Journal of Integer Sequences home page.