1 Introduction
Values of arithmetical functions, especially Euler’s totient function
$\varphi ,$
on special sequences are intriguing. Baczkowski et al. [Reference Baczkowski, Filaseta, Luca and Trifonov1] investigated arithmetic functions and factorials,
$\varphi (n!\kern-1.2pt), d(n!\kern-1.2pt)$
and
$\sigma (n!\kern-1.2pt),$
where d is the divisor counting function and
$\sigma $
is the sum function for divisors. In [Reference Luca and Shparlinski6], Luca and Shparlinski obtained asymptotic formulas for moments of certain arithmetic functions on linear recurrence sequences. Further, Luca [Reference Luca5] considered
$\varphi (F_n),$
where
$F_n$
is the nth Fibonacci number. In [Reference Luca and Stănică7], Luca and Stănică investigated quotients of the form
$\varphi (C_m)/\varphi (C_n),$
where
$C_n$
is the nth Catalan number.
Luca and Stănică in [Reference Luca and Stănică8] considered an analogue of binomial coefficients constructed from Euler’s totient function
$\varphi $
, which were previously proved integral by Edgar [Reference Edgar2]. They defined the
$\varphi $
-actorial
$n!_{\varphi }=\varphi (1)\varphi (2)\cdots \varphi (n)$
and the phinomial coefficient
$$ \begin{align*}\binom{a+b}{a}_{\varphi}=\frac{(a+b)!_{\varphi}}{a!_{\varphi}b!_{\varphi}}.\end{align*} $$
In a similar spirit, we consider the quotient
$$ \begin{align*}\frac{\varphi((a+b)!\kern-1.2pt)}{\varphi(a!\kern-1.2pt)\varphi(b!\kern-1.2pt)}.\end{align*} $$
It does not take long to see that this quantity is not always an integer. In fact, the quotient is not an integer for all pairs
$(a,b)$
, with the exception of a set of density zero (see Theorem 1.2). On the other hand, there are arbitrarily large a and b such that it is an integer; indeed, it is an integer for
$(a,b)=(n,\varphi (n!\kern-1.2pt)-1)$
. (See Proposition 4.2 for more such pairs.)
Many interesting divisibilities in number theory are of the form
$\!f(a)f(b)\mid f(c)$
where
$f:\mathbb N\to \mathbb N$
. A classical result of Erdős [Reference Erdős3] states there is an absolute constant c so that if
$a!b!$
divides
$n!$
then
$a+b< n +c \log n,$
but
$n!/a!b!$
is an integer for infinitely many values of n and some positive constant c with
$a+b= \left \lfloor {n+c\log n} \right \rfloor$
. In fact, it is true that
$(2n)!/(n! \left \lfloor {n+c\log n} \right \rfloor\kern-1.2pt !\kern-1.2pt)$
is an integer for all n with the exception of a set of density zero (see [Reference Erdős, Graham, Ruzsa and Straus4]). This motivates us to consider the quotient
$$ \begin{align*} \mathcal T(a,b;c) = \frac{\varphi(c!\kern-1.2pt)}{\varphi(a!\kern-1.2pt)\varphi(b!\kern-1.2pt)}. \end{align*} $$
As
$\varphi (n!\kern-1.2pt)$
divides
$\varphi (m!\kern-1.2pt)$
whenever
$m\ge n,$
it makes sense to study the least positive integer c such that
$\varphi (a!\kern-1.2pt)\varphi (b!\kern-1.2pt)$
divides
$\varphi (c!\kern-1.2pt).$
Let
$c(a,b)$
denote the least such c for a pair
$(a,b)$
. To understand the behaviour of
$c(a,b)$
consider Figure 1, which is the graph of
$c(a,b)$
against
$a+b$
for all pairs
$(a,b)$
with
$1\le a,b\le 100$
.
Plot of
$c(a,b)$
against
$a+b$
.
One immediately observes that the plot tracks the line
$y=x.$
This suggests that
$c(a,b)$
is close to
$a+b,$
which motivates us to study the ratio
$c(a,b)/(a+b)$
.
Definition 1.1. Define
$c(a,b)$
as the least positive integer c such that
$\varphi (a!\kern-1.2pt)\varphi (b!\kern-1.2pt)$
divides
$\varphi (c!\kern-1.2pt),$
and denote the ratio
$c(a,b)/(a+b)$
by
$r(a,b).$
It is observed using a computer that almost always
$r(a,b)>1$
. Table 1 shows the proportion of pairs
$(a,b)$
with
$1\le a, b \le N$
such that
$r(a,b)>1$
for various values of N.
Proportions of pairs
$(a,b)$
such that
$r(a,b)>1.$
The following theorem proved in this paper confirms the evidence obtained in Table 1.
Theorem 1.2. For all pairs of positive integers
$(a,b),$
we have
$r(a,b)>1$
with the exception of a set of density zero.
In light of Figure 1, it is natural to ask whether
$\lim _{a,b\to \infty }r(a,b)$
exists, and if it does, whether it equals
$1$
. Or, if the limit does not exist, what are the values of the limit inferior and the limit superior? The following theorem shows the exact value of the limit inferior.
Theorem 1.3. We have
$$ \begin{align*} \liminf_{a,b\to \infty}r(a,b)= 1.\end{align*} $$
Studying the limit superior is equivalent to obtaining bounds on the ratio
$r(a,b).$
We prove the following ‘sharp’ upper bound on
$r(a,b).$
Theorem 1.4. For all large positive integers a and b, we have
$r(a,b)\le \tfrac 98.$
It turns out that the sequence
$r(a,b)$
continues to fluctuate and never stabilises. Figure 2 shows a plot of
$r(n,n)$
against n.
Fluctuation of
$r(n,n).$
Under the hypothesis of Dickson’s conjecture, a very well-known and intuitive hypothesis in number theory, we prove the following theorem showing that the limit does not exist.
Theorem 1.5. Assuming Dickson’s conjecture, there are infinitely many positive integers n such that
$$ \begin{align*}r(n,n)\ge\frac{9}{8}-\frac{9}{8n}.\end{align*} $$
More importantly, Theorem 1.5 shows that Theorem 1.4 is sharp in the sense that the constant
$9/8$
cannot be improved any further. It is now easy to see that Theorems 1.4 and 1.5 imply the following result.
Corollary 1.6. Assuming Dickson’s conjecture, we have
$$ \begin{align*}\limsup_{a,b\to\infty}r(a,b) = \tfrac{9}{8}.\end{align*} $$
This paper is organised as follows. In Section 2 we state some well-known results and prove a preliminary lemma. In Section 3 we show that almost all pairs
$(a,b)$
satisfy
$r(a,b)>1$
and hence prove Theorem 1.2. We present the proofs of Theorems 1.3 and 1.4 in Sections 4 and 5, respectively. Finally, in Section 6, we prove Theorem 1.5 under the hypothesis of Dickson’s conjecture.
Notations. We employ the Landau–Bachmann notation
$\mathcal O$
and o as well as the associated Vinogradov notation
$\ll $
and
$\gg $
with their usual meanings. Throughout this paper, the letters p and q are reserved for primes and the letters a and b will always denote positive integers. As usual,
$\pi (x;m,a)$
denotes the number of primes
$p<x$
such that
$p\equiv a\ (\mathrm {mod}\ m).$
For a prime p and a nonzero integer
$n,$
define
$\nu _p(n)$
as the exponent of p in the prime factorisation of
$n.$
For a nonzero rational number
$r=a/b$
where a and b are integers, define
$\nu _p(r)=\nu _p(a)-\nu _p(b)$
for any prime
$p.$
2 Preliminaries
Here we list some classical results which are helpful in our work. The first theorem is crucial in proving Lemma 2.4.
Theorem 2.1 (Siegel–Walfisz)
Let C be a positive constant. If a and q are two relatively prime positive integers such that
$a<q\ll (\log x)^C$
, then
$$ \begin{align*}\bigg| \pi (x;q,a) - \frac{1}{\varphi (q)} \cdot \frac{x}{\log{x}} \bigg| \ll \frac{x}{(\log{x})^B}\end{align*} $$
for some absolute constant
$B>C+1.$
Theorem 2.2 (Legendre)
For all positive integers n and primes
$p,$
$$ \begin{align*}\nu_p(n!\kern-1.2pt)=\sum_{i=1}^{\infty}\bigg\lfloor\frac{n}{p^i}\bigg\rfloor=\frac{n-s_p(n)}{p-1},\end{align*} $$
where
$s_p(n)$
is the sum of the digits of n in base
$p.$
Theorem 2.3 (Kummer)
Let p be a prime. The highest power of a prime p that divides
$(\begin {smallmatrix} n \\ k \end {smallmatrix})$
is the number of carries in the addition
$k+(n-k)$
in base
$p.$
Since
$\varphi (n!\kern-1.2pt)=n!\prod _{p\le n}{(p-1)}/{p}$
, to calculate the exponent of q in
$\varphi (n!\kern-1.2pt)$
we need to estimate
$\nu _q(\prod _{p<x}(p-1))$
.
Lemma 2.4. If q is a fixed prime and K is a real constant, then
$$ \begin{align*}\nu_{q} \bigg ( \prod_{p<x} (p-1) \bigg ) = \frac{q}{(q-1)^2} \cdot \frac{x}{\log{x}} +\mathcal O \bigg (\frac{x}{\log^{K}x} \bigg ).\end{align*} $$
Proof. By a simple double counting argument,
$$ \begin{align*}\nu_{q} \bigg ( \prod_{p<x} (p-1) \bigg ) = \sum_{q^n<x} \pi (x;q^n,1).\end{align*} $$
We split the summation into two intervals:
$$ \begin{align*}\sum_{q^n<x} \pi (x;q^{n} ,1) = \sum_{q^n<(\log{x} )^{C} } \pi (x;q^{n} ,1)+\sum_{(\log{x})^C\le q^n < x} \pi (x;q^{n} ,1).\end{align*} $$
Using Theorem 2.1,
$$ \begin{align*} \sum_{q^n<(\log{x} )^{C} } \pi (x;q^{n} ,1) &= \sum_{q^n<(\log{x} )^{C}} \bigg(\frac{x}{\varphi(q^n)\log x} + \mathcal O\bigg(\frac{x}{\log^B x}\bigg)\bigg) \\ &= \frac{x}{\log x}\sum_{q^n<(\log x)^C}\frac{1}{q^{n-1}(q-1)} + \mathcal O\bigg(\frac{x\log\log x}{\log^B x}\bigg)\\ &= \frac{q}{(q-1)^2}\cdot\frac{x}{\log x}(1+\mathcal O(\log^{-C}x))+\mathcal O\bigg(\frac{x\log\log x}{\log^B x}\bigg)\\ &= \frac{q}{(q-1)^2}\cdot\frac{x}{\log x} + \mathcal O\bigg(\frac{x\log\log x}{\log^B x}\bigg), \end{align*} $$
where B is the constant from Theorem 2.1. Also,
$$ \begin{align*} \sum_{(\log x)^C\le q^n < x } \pi (x;q^{n} ,1) \le \sum_{(\log x)^C\le q^n < x} \frac{x}{q^n} = \mathcal O\bigg(\log x\frac{x}{(\log x)^C}\bigg)=\mathcal O\bigg(\frac{x}{\log^{C-1}x}\bigg). \end{align*} $$
Since
$B>C+1,$
the lemma follows.
3 Pairs
$(a,b)$
such that
$r(a,b)>1$
In this section we prove Theorem 1.2.
Lemma 3.1. Let A be any constant. If a and b are positive integers such that
$b\ge a>{b}/{(\log b)^A},$
then
$r(a,b)>1$
for all sufficiently large
$b.$
Proof. Set
$c=a+b.$
We want to prove that
$\mathcal T(a,b;c)$
is not an integer for all sufficiently large
$b.$
By routine manipulations,
$$ \begin{align*}\mathcal T(a,b;c)=\binom{a+b}{a}\prod_{p\le a}\frac{p}{p-1}\prod_{b<p\le c}\frac{p-1}{p}.\end{align*} $$
We consider the largest power of
$2$
dividing
$\mathcal T(a,b;c)$
and claim that it is negative for all large
$b.$
By Theorem 2.3,
$\nu _2((\begin {smallmatrix} {a+b} \\ {a} \end {smallmatrix}))$
is the number of carries in the base
$2$
addition of a and
$b,$
which is at most
$1+\log _{2}b.$
Therefore, by Lemma 2.4,
$$ \begin{align*} \nu_2(\mathcal T(a,b;c)) &= 2\bigg(\frac{c}{\log c}-\frac{a}{\log a}-\frac{b}{\log b}\bigg)+\mathcal O\bigg(\frac{b}{\log^{K}b}\bigg)\\ &\ll \frac{2b}{\log^{K-1}b} + 2\bigg(\frac{a+b}{\log (a+b)}-\frac{a}{\log a}-\frac{b}{\log b}\bigg)\\ &< 2\bigg(\frac{b}{\log^{K-1} b} +\frac{a}{\log (a+b)} - \frac{a}{\log a}\bigg) \\ &<2a\bigg(\frac{1}{\log^{K-1-A}b}+\frac{1}{\log(a+b)}-\frac{1}{\log a}\bigg) \quad \mbox{(since } b/a < \log^A b). \end{align*} $$
It is routine to check that
$(\log (a+b))^{-1}-(\log a)^{-1}$
is increasing in
$a\in (0,\infty ).$
Hence, as
$a\le b,$
the above expression is bounded above by
$$ \begin{align*}2a\bigg(\frac{1}{\log^{K-1-A}b}+\frac{1}{\log b + \log 2}-\frac{1}{\log b}\bigg)< -\frac{\delta a}{\log^2 b}\end{align*} $$
for some positive constant
$\delta ,$
provided
$K-1-A>2,$
which can be ensured by taking K large. This completes the proof.
With Lemma 3.1 in hand, it is easy to prove that the density of pairs
$(a,b)$
such that
$r(a,b)>1$
is
$1.$
The proportion of pairs
$(a,b)$
such that
$a=b$
is
$0$
, so we can ignore them. It suffices to prove that the proportion of pairs
$(a,b)$
with
$a< b$
and
$r(a,b)>1$
is
$\tfrac 12$
. The number of pairs
$(a,b)$
such that
$1\le a<b\le N$
and
$r(a,b)>1$
is at least
$$ \begin{align*} \sum_{b=N_0}^N\bigg((b-1)-\frac{b}{(\log b)^A}\bigg)&> \frac{N(N-1)}{2} - \frac{N^2}{(\log N)^A}+\mathcal O(1)\\ &=N^2\bigg(\frac 12 -\frac{1}{2N}-\frac{1}{(\log N)^A}+\mathcal O\bigg(\frac{1}{N^2}\bigg)\bigg), \end{align*} $$
where
$N_0$
is some constant depending only on a and
$A.$
Thus, the density of such pairs is
$\tfrac 12$
, proving Theorem 1.2.
4 The limit inferior
The proof of Theorem 1.3 has two steps. First, we need to prove the limit inferior is at least
$1$
, and then show that there are arbitrarily large a and b such that
$r(a,b)\le 1.$
The following result implies that the limit inferior is at least
$1.$
Lemma 4.1. Let A be any real constant. If a and b are positive integers with
$a\le b$
, then
$c(a,b)\ge a+b-{b}/{\log ^{A}b}$
for all sufficiently large
$b.$
Proof. Assume to the contrary that
$c=c(a,b)\le a+b-{b}/{\log ^A b}$
infinitely often. We calculate
$\nu _2$
of
$\mathcal T(a,b;c)$
and claim that it is negative for all large b, contradicting the assumption that
$\mathcal T(a,b;c)$
is an integer. From Theorem 2.2,
$\nu _2(n!\kern-1.2pt)=n+\mathcal O(\log n).$
Note that
$b\le c\le a+b\le 2b.$
By Lemma 2.4,
$$ \begin{align*} \nu_2(\mathcal T(a,b;c)) &= \nu_2(c!\kern-1.2pt)-\nu_2(a!\kern-1.2pt)-\nu_2(b!\kern-1.2pt)+1+\nu_2\bigg(\prod_{b<p\le c} (p-1)\bigg) -\nu_2\bigg(\prod_{p\le a} (p-1)\bigg)\\ &= c-a-b + 2\bigg(\frac{c}{\log c}-\frac{a}{\log a}-\frac{b}{\log b}\bigg)+\mathcal O\bigg(\frac{b}{\log^{K}b}\bigg) \end{align*} $$
for some constant K where we choose
$K>A.$
Note that
$$ \begin{align*} \frac{c}{\log c}-\frac{a}{\log a}-\frac{b}{\log b} \le \frac{c}{\log b} - \frac{a}{\log a}-\frac{b}{\log b} = \frac{c-b}{\log b}-\frac{a}{\log a} \le \frac{c-b-a}{\log a} <0. \end{align*} $$
Therefore,
$$ \begin{align*}\nu_2(\mathcal T(a,b;c))\le -\frac{b}{\log^A b} + \mathcal O\bigg(\frac{b}{\log^K b}\bigg).\end{align*} $$
Since
$K>A,$
the above quantity is negative for all sufficiently large
$b,$
contradicting the assumption that
$\mathcal T(a,b;c)$
is an integer. The proof is complete.
By Lemma 4.1,
$$ \begin{align*}r(a,b)\ge 1 - \frac{b}{(a+b)\log^A b}\ge 1-\frac{1}{2\log^A b}\end{align*} $$
for all sufficiently large
$b.$
It is now evident that
$$ \begin{align*} \liminf_{a,b\to\infty}r(a,b) \ge 1. \end{align*} $$
It remains to prove that there exist arbitrarily large a and b such that
$r(a,b)\le 1.$
Indeed,
$\mathcal T(a,\varphi (a!\kern-1.2pt)-1;\varphi (a!\kern-1.2pt))=1$
for all
$a\ge 4$
, so
$r(n,\varphi (n!\kern-1.2pt)-1)<1$
for all
$n\ge 4.$
This completes the proof of Theorem 1.3.
However, we prove the following result, which says that, given a, many b satisfy
$r(a,b)\le 1.$
The proof also demonstrates a natural way to construct such pairs.
Proposition 4.2. Let a be a fixed positive integer. A positive proportion of positive integers b satisfy
$r(a,b)\le 1.$
Proof. We provide a way to construct such
$b.$
At the end, it will be clear that we can ensure
$b\ge a,$
so let us assume
$b\ge a$
from now onwards. Recall that
$$ \begin{align*}\mathcal T(a,b;a+b)=\binom{a+b}{a}\prod_{p\le a}\frac{p}{p-1}\prod_{b<p\le a+b}\frac{p-1}{p}.\end{align*} $$
Set
$D=\prod _{p\le a}(p-1)$
. Clearly,
$\prod _{b<p\le a+b}p$
divides
$(\kern-1.3pt\begin {smallmatrix} {a+b} \\ {a} \end {smallmatrix}\kern-1.3pt)$
, and D is relatively prime to
$\prod _{b<p\le a+b} p.$
Therefore, it suffices to prove that there exist infinitely many b such that D divides
$(\kern-1.3pt\begin {smallmatrix} {a+b} \\ {a} \end {smallmatrix}\kern-1.3pt).$
Let the prime factorisation of D be
$\prod _{i=1}^{m}q_i^{\alpha _i}.$
By Theorem 2.3, we want the addition of a and b in base
$q_i$
to have at least
$\alpha _i$
carries for each
$i=1,2,\ldots ,m.$
Therefore, we choose b such that
$b\equiv -a \ (\mathrm {mod}\ q_i^{\alpha _i})$
for each
$i=1,2,\ldots , m,$
and we take
$$ \begin{align*}b=k\prod_{i=1}^m q_i^{\alpha_i}-a=k\prod_{p\le a}(p-1)-a\end{align*} $$
for any positive integer k such that
$b\ge a.$
Thus, the proportion of positive integers b such that
$r(a,b)\le 1$
is positive.
Remark 4.3. The size of b obtained in the above proof is around
$\exp {a(1+o(1))},$
and so the proportion of such b is at least
$\exp a(-1+o(1)).$
5 Upper bound on
$r(a,b)$
In this section we prove Theorem 1.4.
5.1 Set-up
Set
$c=a+b+ \left \lfloor {{a+b}/{8}} \right \rfloor$
. Without loss of generality, assume
$a\le b.$
We wish to prove that
$\mathcal T(a,b;c)$
is an integer for all large a and
$b.$
It is easy to see that
$$ \begin{align*}\mathcal T:=\mathcal T(a,b;c)=\binom{a+b}{a}(a+b+1)\cdots\bigg(a+b+\bigg\lfloor{\frac{a+b}{8}}\bigg\rfloor\bigg)\prod_{p\le a}\frac{p}{p-1} \prod_{b<p\le c}\frac{p-1}{p}.\end{align*} $$
We prove that
$\mathcal T$
is an integer by showing that
$\nu _q(\mathcal T)\ge 0$
for all primes
$q.$
It is clear that
$\nu _q(\mathcal T)\ge 0$
for all
$q>a.$
So, let us assume that
$q\le a$
for the rest of the argument. We split our proof into three cases:
$q\le 7,~q\in [8,a^{1/2}]$
and
$ q\in (a^{1/2}, a]$
. Take
$a> 64$
so that the intervals do not overlap.
5.2 Bounding
$\nu _q(\mathcal T)$
for
$q\le 7$
This case is straightforward using Lemma 2.4:
$$ \begin{align*} \nu_q(\mathcal T) &\ge \nu_q\bigg((a+b+1)\cdots\bigg(a+b+\bigg\lfloor{\frac{a+b}{8}}\bigg\rfloor\bigg)\bigg)-\nu_q\bigg(\prod_{p\le a}(p-1)\bigg)\nonumber\\ &\ge \frac 1q \bigg\lfloor{\frac{a+b}{8}}\bigg\rfloor + \mathcal O\bigg(\frac{a}{\log a}\bigg), \end{align*} $$
which is positive for all large b as
$a\le b.$
5.3 Bounding
$\nu _q(\mathcal T)$
for
$q\in [8,a^{1/2}]$
In this case, the estimates of Lemma 2.4 do not work because the error terms get large with q. Hence, we require an alternative bound for
$\nu _q(\prod _{p\le a}(p-1)),$
which is given in the next two lemmas.
Lemma 5.1. Let
$d>7$
be a positive integer relatively prime to
$3,5$
and
$7.$
Then, the number of primes in
$\{d+1,2d+1,3d+1,\ldots ,nd+1\}$
is at most
$0.46n+7.$
Proof. The proof is a routine application of the inclusion–exclusion principle. The number of elements in the set divisible by some positive integer k is either
$ \left \lfloor {{n}/{k}} \right \rfloor $
or
$ \left \lceil {{n}/{k}} \right \rceil$
. Applying Eratosthenes’ sieve with respect to the primes
$3,5$
and
$7$
, the number of primes in the set is at most
$$ \begin{align*} n- \left\lfloor {\frac n3} \right\rfloor - \left\lfloor {\frac n5} \right\rfloor - \left\lfloor {\frac n7} \right\rfloor + \left\lceil {\frac n{15}} \right\rceil + \left\lceil {\frac n{21}} \right\rceil + \left\lceil {\frac n{35}} \right\rceil - \left\lfloor {\frac{n}{105}} \right\rfloor < 0.46n+7, \end{align*} $$
as desired.
Lemma 5.2. If
$q> 7$
, then
$$ \begin{align*}\nu_q\bigg(\prod_{p\le a}(p-1)\bigg)\le \frac{0.23a}{q-1}+\frac{7\log a}{\log q}.\end{align*} $$
Proof. Similarly to the proof of Lemma 2.4, by a double counting argument and using Lemma 5.1,
$$ \begin{align*} \nu_q\bigg(\prod_{p\le a}(p-1)\bigg) = \sum_{2q^m<a}\pi(a;2q^m,1) &\le\sum_{2q^m<a}\bigg(\frac{0.46a}{2q^m}+7\bigg) < \frac{0.23a}{q-1}+\frac{7\log a}{\log q}, \end{align*} $$
as desired.
By a standard application of Theorem 2.2,
$$ \begin{align*} \nu_q\bigg((a+b+1)\cdots\bigg(a+b+\bigg\lfloor{\frac{a+b}{8}}\bigg\rfloor\bigg)\bigg) &\ge \nu_q\bigg(\bigg\lfloor{\frac{a+b}{8}}\bigg\rfloor!\bigg) \\ &\ge \frac 1{q-1} \bigg\lfloor{\frac{a+b}{8}}\bigg\rfloor-\frac{\log(a+b)}{\log q} + \mathcal O\bigg(\frac 1{\log q}\bigg)\\ & \ge \frac{a+b}{8(q-1)}-\frac{\log b}{\log q} + \mathcal O\bigg(\frac 1{\log q}\bigg). \end{align*} $$
Therefore,
$$ \begin{align*} \nu_q(\mathcal T) &\ge \frac{a+b}{8(q-1)}-\frac{\log b}{\log q} + \mathcal O\bigg(\frac 1{\log q}\bigg)- \bigg(\frac{0.23a}{q-1}+\frac{7\log a}{\log q}\bigg). \end{align*} $$
Since
$a\le b$
and
$q\le a^{1/2},$
it follows that
$$ \begin{align*} \nu_q(\mathcal T) &\ge \frac{0.02a}{q-1} + \frac{b-a}{8(q-1)} - \frac{8\log b}{\log q}+\mathcal O\bigg(\frac 1{\log q}\bigg)\\ &\ge 0.02\bigg(a^{1/2} + \frac{b-a}{400(q-1)} - \delta \log b\bigg) \end{align*} $$
for some positive constants
$\delta .$
This expression is nonnegative if
$a>\delta ^2 \log ^2 b.$
Again, if
$a<\delta ^2\log ^2 b,$
we see that
${(b-a)}/{400(q-1)}$
is greater than
$\delta \log b$
for all sufficiently large
$b.$
Thus,
$\nu _q(\mathcal T)\ge 0$
and this case is complete.
5.4 Bounding
$\nu _q(\mathcal T)$
for
$q\in (a^{1/2},a]$
Estimates like Lemmas 2.4 and 5.2 are not suitable as the margin is quite thin in this case. A careful analysis involving sharp bounds is required. We need a sharp upper bound for
$$ \begin{align*}\nu_q\bigg(\prod_{p\le a} (p-1)\bigg) = \pi(a;2q,1).\end{align*} $$
Lemma 5.3. Let
$q>7$
be a prime. The number of primes in
$\{2q+1,4q+1,\ldots,2qk+1\}$
is at most
$ \left \lfloor { k/2} \right \rfloor +1,$
where equality can occur if
$k=4$
and
$q=11.$
Proof. By Lemma 5.1, the number of primes in the set is at most
$0.46k+7,$
which is less than or equal to
$ \left \lfloor { k/2} \right \rfloor + 1$
for all
$k\ge 174.$
We check the smaller values of k one by one. Fix some
$k\le 173.$
Consider the aforementioned set modulo
$3\cdot 5\cdot 7=105.$
Obviously, q can only be congruent to residues relatively prime to
$105.$
We check all such residues one by one. A number in the set cannot be a prime if it is not relatively prime to
$105.$
This procedure can be automated with a naive PARI/GP [9] script for all
$k\le 173,$
completing the proof.
Similarly to the previous cases, since
$a\le b$
,
$$ \begin{align*} \nu_q\bigg(\bigg\lfloor{\frac{a+b}{8}}\bigg\rfloor!\bigg)\ge \bigg\lfloor{\frac 1q\bigg\lfloor{\frac{a+b}{8}}\bigg\rfloor}\bigg\rfloor \ge\bigg\lfloor{\frac{a}{4q}}\bigg\rfloor, \end{align*} $$
By Lemma 5.3,
$$ \begin{align*}\pi(a;2q,1) \le \bigg\lfloor{\frac 12\bigg\lfloor{\frac{a}{2q}}\bigg\rfloor}\bigg\rfloor+1=\bigg\lfloor{\frac{a}{4q}}\bigg\rfloor+1.\end{align*} $$
Thus,
$$ \begin{align*} \nu_q(\mathcal T) \ge \nu_q\bigg(\bigg\lfloor{\frac{a+b}{8}}\bigg\rfloor!\bigg)+\nu_q\bigg(\prod_{p\le a}\frac{p}{p-1}\bigg) \ge \bigg\lfloor{\frac{a}{4q}}\bigg\rfloor + 1 - \bigg(\bigg\lfloor{\frac{a}{4q}}\bigg\rfloor+1\bigg)=0, \end{align*} $$
and the proof of Theorem 1.4 is complete.
6 Does the limit exist?
Until now, we have proved results on the inferior and superior limits. A question that arises naturally is whether the limit exists. Numerical evidence suggests that the sequence
$r(a,b)$
keeps on fluctuating (see Figure 2).
In this section, we provide a convincing argument for the nonconvergence of the sequence using Dickson’s conjecture and prove Theorem 1.5.
Hypothesis 6.1 (Dickson’s conjecture)
Let
$a_1,a_2,\ldots ,a_k$
be integers and
$b_1, b_2,\ldots ,b_k$
be positive integers. There are infinitely many positive integers n for which all the elements in the set
$\{a_1 + b_1n, a_2 + b_2n, \ldots , a_k + b_kn\}$
are primes, unless there is a congruence condition preventing this, that is, there is no prime q (necessarily at most k) such that the product
$(a_1+b_1n)(a_2+b_2n)\cdots (a_k+b_k n)$
is divisible by q for all
$n\in \{0,1,\ldots , q-1\}.$
The next lemma gives an application of Dickson’s conjecture.
Lemma 6.2. Assuming Dickson’s conjecture, there exist infinitely many primes q such that
$2q+1,6q+1$
and
$8q+1$
are primes but
$iq+1$
is not prime for each
$i=10,12,14,16,18.$
Proof. The main idea is to find one such prime q and apply the Chinese remainder theorem. It is easy to see that q must be greater than
$7.$
Observe that
$q\equiv 2 \ (\mathrm {mod}\ 3)$
and
$q\equiv 1 \ (\mathrm {mod}\ 5).$
Therefore,
$iq+1$
is divisible by
$3$
for each
$i\in \{10,16\},$
and
$14q+1$
is divisible by
$5.$
It is easily verified that
$q=131$
satisfies the conditions of the statement. Indeed,
$2\cdot 131 + 1 = 263,~ 6\cdot 131+ 1= 787,~ 8\cdot 131+ 1 =1049, 12\cdot 131+1=11^2\cdot 13$
, and
$18\cdot 131+ 1 =7\cdot 337$
. Consider the system of congruences
$$ \begin{align*} q \equiv 131 \ (\mathrm{mod}\ 11\kern-1pt),\quad q \equiv 131 \ (\mathrm{mod}\ 7). \end{align*} $$
This is solved by
$q\equiv 54 \ (\mathrm {mod}\ 77).$
So, if q is of the form
$77\ell +54$
, then
$12q+1$
and
$18q+1$
are not primes. By Dickson’s conjecture, there exist infinitely many
$\ell $
such that
$77\ell +54,2(77\ell +54)+1, 6(77\ell +54)+1$
and
$8(77\ell +54)+1$
are primes. No modular conditions are preventing this because of the way we chose
$q.$
The proof is complete.
Take
$n=8q+1$
and let
$c(n,n)=2n+m$
for some integer
$m.$
By Lemma 3.1, it is clear that m is positive. Let us assume for now that
$m < {(n-9)}/{4}$
; it will be clear later why we are assuming this. Recall that
$$ \begin{align*}\mathcal T(n,n;2n+m)=\binom{2n}{n}(2n+1)(2n+2)\cdots (2n+m)\prod_{p\le n}\frac{p}{p-1}\prod_{n< p\le 2n+m}\frac{p-1}{p}.\end{align*} $$
We consider
$\nu _q(\mathcal T(n,n;2n+m))$
. Since
$q>17$
and the base q representation of n is
$81$
, there are no carries in the addition
$n+n$
in base q. Therefore, by Theorem 2.3, q does not divide
$(\begin {smallmatrix} {2n} \\ {n} \end {smallmatrix}).$
Observe that
$$ \begin{align*}\nu_q\bigg(\prod_{p\le n}\frac{p}{p-1}\bigg)\le -2.\end{align*} $$
Whether q divides
$\prod _{n<p\le 2n+m}(p-1)$
or not depends on how many of the numbers
$9q+1,10q+1,\ldots ,18q+1$
are primes. Clearly,
$9q+1,11q+1,13q+1,15q+1$
and
$17q+1$
are even. The remaining
$iq+1$
for
$i\in \{10,12,14,16,18\}$
are not primes by assumption. Therefore, the product
$\prod _{n<p\le 2n+m}(p-1)$
has no contribution to the exponent of q. Lastly, the set
$\{2n+1,2n+2,\ldots ,2n+m\}$
is equivalent to
$\{3,4,\ldots ,m+2\}$
when considered modulo
$q.$
Note that
$2n+(q-2)= 17q$
is not divisible by
$q^2.$
Therefore, for
$\mathcal T(n,n;2n+m)$
to be an integer, we must have
$m+2\ge 2q,$
which implies that
$m \ge {(n-9)}/{4}.$
This is a contradiction to our initial assumption. Thus
$$ \begin{align*} c(n,n)\ge 2n+\frac{n-9}{4}=\frac{9n}{4}-\frac{9}{4} \quad\mbox{and}\quad r(n,n) \ge \frac{9}{8} -\frac{9}{8n}\end{align*} $$
completing the proof of Theorem 1.5.
Remark 6.3. By a quantitative version of Dickson’s conjecture, known in its very general form as the Bateman–Horn conjecture, the number of integers in
$[1,x]$
which satisfy the condition of Theorem 1.5 is of order at least
$x/(\log x)^4$
.
