\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\DeclareMathOperator{\lcm}{lcm}
\newcommand{\Z}{\mbox{$\mathbb Z$}}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf Rectangles Of Nonvisible Lattice Points }
\vskip 1cm
\large
Shanta Laishram\\
Stat-Math Unit\\ Indian Statistical Institute\\
7 S. J. S. Sansanwal Marg\\
New Delhi, 110016\\ 
India\\
\href{mailto:shanta@isid.ac.in}{\tt shanta@isid.ac.in} \\
\ \\
Florian Luca\\
School of Mathematics\\
University of the Witwatersrand\\
P.~O.~Box X3, Wits 2050 \\
South Africa\\
\href{mailto:florian.luca@wits.ac.za}{\tt florian.luca@wits.ac.za} \\
\end{center}

\vskip .2 in

\begin{abstract}
A lattice point $(0, 0)\neq (x, y)\in \Z^2$ is called \emph{visible} (from the origin) if 
$\gcd(x, y)=1$, and \emph{nonvisible} otherwise. 
Given positive integers $a, b$, define $M:=M(a, b)$ and $N:=N(a, b)$ 
to be the positive integers $M$ and $N$ having the least value of 
$\max(M, N)$ with the property that $\gcd(M-i, N-j)>1$ for all 
$1\leq i\leq a$ and $1\leq j\leq b$.
We give upper and lower bounds 
for $M, N$.
\end{abstract}

\section{Introduction}
\label{sec1}
A lattice point $(0, 0)\neq (x, y)\in \Z^2$ is called \emph{visible} (from the origin) if 
$\gcd(x, y)=1$ and \emph{nonvisible} otherwise (see Herzog and Stewart \cite{HS}).
In other words, $(r, s)$ is visible iff $\frac{r}{s}$ is in lowest terms.

In \cite{Shallit}, Pighizzini and Shallit defined, for a positive integer 
$n$, the function $S(n)$, which is the least positive integer $r$ such that 
there exists $m\in \{0,1,\ldots, r\}$ with $\gcd(r-i, m-j)>1$ for 
$0\leq i, j<n$. This is equivalent to finding the square of side $n$, nearest  
to the origin in the first quadrant of the real $xy$ plane, where all its lattice 
points are nonvisible from the origin. It was shown in \cite{Shallit} that 
\begin{equation}\label{eq:1}
S(n)<e^{(2+o(1))n^2\log n}\qquad {\text{\rm as}}\qquad n\to\infty,
\end{equation}
and computed $S(n)$ and the corresponding $m$'s for $n=1, 2, 3$. This function 
was also studied by Wolfram \cite[pp.~613, 1093]{Wolf} who computed $S(4)$.  

Here, we generalize the function $S(n)$. Given positive integers $a, b$, let
$(M(a, b),N(a, b))$ be a minimal pair of positive integers such that 
$\gcd(M-i, N-j)>1$ for all $1\leq i\leq a$ and $1\leq j\leq b$.
More precisely,
given positive integers $a, b$, define $M:=M(a, b)$ and $N:=N(a, b)$ 
to be the positive integers $M$ and $N$ having the least value of 
$\max(M, N)$ with the property that $\gcd(M-i, N-j)>1$ for all 
$1\leq i\leq a$ and $1\leq j\leq b$.
This is equivalent to finding the rectangle with sides $a, b$, nearest
to the origin in the first quadrant of real $xy$ plane, where all its lattice 
points are nonvisible from the origin.

Without loss of generality, we assume that $a\geq b$.  In this note, we prove the following result. We always write $p$ for a prime number.

\begin{theorem}\label{Th1}
If $a\geq b$, we then have
\begin{itemize}
\item[(i)] $\max\{M(a,b),N(a,b)\}\leq \exp((6/\pi^2+o(1))ab\log ab)$ as $b\to\infty$.
\item[(ii)] $\max\{M(a,b),N(a,b)\}\leq \exp(0.721521 ab\log ab)$ if $b>100$.
\item[(iii)] We have 
\begin{align*}
M(a,b)\geq \exp((c_1+o(1)) b\log ab)\quad {\text{\rm and}}\quad 
N(a,b)\geq \exp((c_1+o(1)) a\log ab), 
\end{align*}
where 
\begin{align*}
c_1=1-\sum_{p\geq 2} \frac{1}{p^2}=0.547753\cdots 
\end{align*}
provided $b\to\infty$ in such a way that $\log\log a=o(b)$.
\end{itemize}
\end{theorem}
Taking $a=b=n$, (i) above shows that 
\begin{align*}
S(n)\leq \exp((12/\pi^2+o(1)) n^2\log n)\qquad {\text{\rm as}}\qquad n\to\infty,
\end{align*}
which improves \eqref{eq:1}. We also give a lower bound for $S(n)$. We prove 
\begin{theorem}\label{Slb}
For $n>1$, we have
\begin{align*}
S(n)\geq  \exp(.82248n\log n). 
\end{align*}

\end{theorem}

We also give an algorithm for computing $M$ and $N$ for a given $a$ and $b$. 
This is stated in Section~\ref{sec3} and values of $M$ and $N$ are computed for 
some small values of $a, b$. The proof of Theorem \ref{Slb} is given in 
Section~\ref{sec4}.


\section{Preliminaries}
\label{sec2}

For a positive integer $i$, let $p_i$ denote the $i$-th prime. Thus 
$p_1=2, p_2=3, \ldots$. For real $x>1$, let
\begin{align*}
\pi(x)=\sum_{p\leq x}1 \ \ {\rm and} \ \ \theta(x)=\sum_{p\leq x}\log p.
\end{align*}
From the prime number theorem, we have $\pi(x)\leq s_1 x/\log x$ and
$\theta(p_\ell)\leq s_2\ell\log \ell$ for positive constants $s_1, s_2$. The following results give
explicit values of $s_1$ and $s_2$.

\begin{lemma}\label{pnt}
Let $x$ be  real and positive and $\ell$ be a positive integer. We have
\begin{enumerate}
\item[$(i)$]{$\displaystyle{\pi(x)\leq \frac{x}{\log x}\left(1+
\frac{1.2762}{\log x}\right)}$ for $x>1$.}
\item[$(ii)$]{$\displaystyle{p_\ell \geq \ell\log \ell  \ {\text {\it for}} \ \ell\geq 1.}$}
\item[$(iii)$]{$\displaystyle{\theta(p_\ell)\leq \ell(\log \ell+\log \log \ell-.75) \ {\text{\it for}} \ \ell\geq 8.}$}
\item[$(iv)$]{$\displaystyle{\theta(x)\geq x\left(1-\frac{1}{\log x}\right) \ {\text{\it for}} \ x\geq 41.}$}
\item[$(v)$]{$\displaystyle{\sum_{p\leq x}\frac{1}{p}\leq \log\log x+0.2615+\frac{1}{\log^2 x} \ {\text{\it for}} \
x>1.}$}
\end{enumerate}
\end{lemma}

The estimates $(ii), (iv)$ and $(v)$ are Rosser and Schoenfeld \cite[(3.12), (3.16), (3.20)]{ros}, respectively. The estimate $(i)$ is due to Dusart \cite{Dus1} and $(iii)$ is derived from estimates in \cite{Dus1}. 

For given integers $j\geq r\geq 1$, let 
\begin{align*}
r':=r'(j):=\#\{i: 1\leq i\leq r \ {\rm and} \ \gcd(i, j)=1\}.
\end{align*}
Let
\begin{align*}
R_j:=\max\left\{r'-\frac{r\varphi(j)}{j}: 1\leq r<j\right\},
\end{align*}
where $\varphi(j)$ is the Euler phi-function. It is easy to see that $R_p=1-1/p$. For a real number $x$, let $\{x\}$ denote the fractional part of $x$; i.e., $\{x\}=x-\lfloor x\rfloor$. We prove the following estimate.

\begin{lemma}\label{Rj}
If $n>100$, then
\begin{align*}
\sum^n_{j=1}R_j\leq .375n\log n-.432n-10.
\end{align*}

\end{lemma}

\begin{proof}
For $1\leq r<j$, we have
\begin{align*}
r'(j)\leq r-\sum_{p\mid j}\left\lfloor \frac{r}{p}\right\rfloor+\sum_{pq\mid j}\left\lfloor \frac{r}{pq}\right\rfloor-
\sum_{pqr\mid j}\left\lfloor \frac{r_j}{pqr}\right\rfloor+\cdots,
\end{align*}
where $p, q, r, \ldots$ are primes dividing $j$. Since
\begin{align*}
\frac{\varphi(j)}{j}=1-\sum_{p\mid j}\frac{1}{p}+\sum_{pq\mid j}\frac{1}{pq}-
\sum_{pqr\mid j}\frac{1}{pqr}+\cdots ,
\end{align*}
we get
\begin{align*}
r'-\frac{r\varphi(j)}{j}\leq \sum_{p\mid j}\left\{\frac{r_j}{p}\right\}-\sum_{pq\mid j}\left\{\frac{r_j}{pq}\right\}+
\sum_{pqr\mid j}\left\{\frac{r_j}{pqr}\right\}-\cdots.
\end{align*}
Since ${r}/{s}\leq \lfloor {r}/{s}\rfloor +1-{1}/{s}$ holds for positive integers $r, s$, we get
\begin{align*}
R_j\leq \sum_{p\mid j}\left(1-\frac{1}{p}\right)+\sum_{pqr\mid j}\left(1-\frac{1}{pqr}\right)+\cdots
\end{align*}
Let $\omega(j)$ be the number of distinct prime divisors of $j$ and put $\omega_t=\binom{j}{t}$. Then
\begin{align*}
R_j\leq \sum_{t \ {\rm odd}}\omega_t -\sum_{p\mid j}\frac{1}{p}=2^{\omega(j)-1}-\sum_{p\mid j}\frac{1}{p}.
\end{align*}
Thus, for $n>100$, we have
\begin{eqnarray}
\label{eq:11}
\sum^n_{j=1}R_j&\leq & \sum^{100}_{j=1}R_j+\frac{1}{2}\sum^n_{j>100}2^{\omega(j)}-\sum^b_{j>100}\sum_{p\mid j}\frac{1}{p}\nonumber\\
&= & \sum^{100}_{j=1}\left(R_j-2^{\omega(j)-1}-\sum_{p\mid j}\frac{1}{p}\right)+
\frac{1}{2}\sum^n_{j=1}2^{\omega(j)}-\sum^n_{j=2}\sum_{p\mid j}\frac{1}{p}\nonumber\\
&\leq &  -130.4778+\frac{1}{2}\sum^n_{j=1}2^{\omega(j)}-\sum_{p\leq n}\left\lfloor \frac{n}{p}\right\rfloor\frac{1}{p}.
\end{eqnarray}
Assuming $n>100$, we have
\begin{eqnarray}
\label{eq:12}
\sum_{p\leq n}\left\lfloor \frac{n}{p}\right\rfloor\frac{1}{p}&\geq & \sum_{p\leq n}\left(\frac{n+1}{p^2}-\frac{1}{p}\right)
\geq (n+1)\sum_{p\leq b}\left(\frac{1}{p^2}-\frac{1}{p(n+1)}\right)\nonumber \\
&\geq & (n+1)\sum_{p\leq 101}\left(\frac{1}{p^2}-\frac{1}{101p}\right)\geq .432(n+1).
\end{eqnarray}
As in the proof of \cite[Lemma 9]{slpmd} for $n\geq 248$, and using exact computations for $n\in [101, 247]$, we obtain
\begin{equation}
\label{eq:13}
\sum^n_{j=2}2^{\omega(j)}-120\leq .375n\log n \qquad {\text{\rm for~all}} \qquad n>100.
\end{equation}
Combining the estimates \eqref{eq:11}, \eqref{eq:12} and \eqref{eq:13} above, we get the assertion of the lemma.
\end{proof}

\begin{lemma}\label{phi/j}
For a positive integer $n$, we have
\begin{align}\label{logn+1}
\sum^n_{j=1}\frac{\varphi(j)}{j}\leq \frac{6n}{\pi^2}+\log n+1.
\end{align}

\end{lemma}

\begin{proof}
We have
\begin{align*}
\sum^n_{j=1}\frac{\varphi(j)}{j}=\sum^b_{j=1}\frac{\mu(j)}{j}\left\lfloor\frac{n}{j}\right\rfloor
=\sum^n_{j=1}\frac{\mu(j)}{j}\left(\frac{n}{j}-\left\{\frac{n}{j}\right\}\right)=n\sum^b_{j=1}\frac{\mu(j)}{j^2}
-\sum^n_{j=1}\frac{\mu(j)}{j}\left\{\frac{n}{j}\right\}.
\end{align*}
Hence, inequality \eqref{logn+1} follows from
\begin{equation*}
\sum^n_{j=1}\frac{\mu(j)}{j^2}=\sum^\infty_{j=1}\frac{\mu(j)}{j^2}-\sum_{j>n}\frac{\mu(j)}{j^2}
<\frac{6}{\pi^2}+\sum_{j>n}\frac{1}{j^2}\leq \frac{6}{\pi^2}+\int^\infty_n\frac{du}{u^2}=
\frac{6}{\pi^2}+\frac{1}{n},
\end{equation*}
and
\begin{equation*}
\label{eq:5}
-\sum^n_{j=1}\frac{\mu(j)}{j}\left\{\frac{n}{j}\right\}\leq \sum^n_{j=2}\frac{1}{j}<\int^n_1\frac{du}{u}=\log n.
\end{equation*}
\end{proof}

We now define two functions $f$ and $g$ on ${\mathbb N}$ with values in the positive real numbers given by
\begin{align*}
f(n)=\begin{cases}
\sum^n_{j=1}{\varphi(j)}/{j}, & {\rm if} \ n\leq 100;\\
{6n}/{\pi^2}+\log n+1, & {\rm if} \ n>100;
\end{cases}
\end{align*}
and
\begin{align*}
g(n)=\begin{cases}
\sum^n_{j=1}R_j, & {\rm if} \ n\leq 100;\\
.375n\log n-.432n-10, & {\rm if} \ n>100.
\end{cases}
\end{align*}
We observe from Lemmas \ref{Rj} and \ref{phi/j} that inequalities $f(n)\leq 6n/\pi^2+\log n+1$ for $n\geq 1$ and 
$g(n)\leq .375n\log n$ hold for all $n\geq 7$.

\section{Proof of Theorem \ref{Th1}}
\label{sec3}
\subsection{Proof of the upper bounds (i) and (ii) in Theorem \ref{Th1}}
\label{subsec31}

Let $a$ and $b$ be positive integers with $a\geq b$.
If $p\mid M$ and $p\mid N$ for each $p\leq b$, then
\begin{align*}
\gcd(M-i, N-j)>1\quad {\text{\rm for}}\quad  1\leq i\leq a, 1\leq j\leq b \quad {\text{\rm and}} \quad \gcd(i, j)\neq 1.
\end{align*}
If $p\mid M$ and $N\equiv 1\pmod p$  for every $b<p\leq a$, then
\begin{align*}
\gcd(M-i, N-1)>1 \quad  {\text{\rm for}}\quad  b< i\leq a.
\end{align*}

Let
\begin{align*}
T:=T(a, b):&=\{(i, j): 1\leq i\leq a, 1\leq j\leq b, {\rm gcd}(i, j)=1\}\setminus \{(i, 1): b<i\leq a\},
\end{align*}
and let $t=\#T$. We label  the elements of $T(a, b)$ as
\begin{align*}
T(a, b)=\{(i_l, j_l): 1\leq l\leq t\}
\end{align*}
in lexicographic order. Hence $(i_1, j_1)=(1, 1), (i_2, j_2)=(1, 2), \ldots$.

We consider the system of congruences
\begin{eqnarray*}
M, N & \equiv & 0\pmod p  \quad {\text{\rm for}} \quad  p\leq b; \\
M & \equiv &  0\pmod p \quad  {\text{\rm and}} \quad  N\equiv 1\pmod p \quad {\text{\rm for}} \quad b<p\leq a;
\end{eqnarray*}
and
$$
M\equiv i_{\ell}\pmod {p_{\pi(b)+\ell}} \quad  {\text {\rm and}} \quad N\equiv j_l\mod p_{\pi(b)+\ell}) \quad {\text {\rm for}} \quad  1\leq \ell\leq t.
$$
By the Chinese remainder theorem, we get
\begin{align}\label{pit+a}
\max(M, N)\leq \prod_{\ell\leq \pi(a)+t}p_\ell.
\end{align}

We now estimate $\pi(a)+t$. For every $1\leq j\leq b$, write $a=jq_j+r_j$ where $0\leq r_j<j$.
By dividing $a$ into intervals of length $j$, we obtain
\begin{eqnarray*}
t+a-b & = & \sum^b_{j=1}(q_j\varphi(j)+r'_j)=
a\sum^b_{j=1}\frac{\varphi(j)}{j}+\sum^b_{j=1}\left(r'_j-\frac{r_j\varphi(j)}{j}\right)\\
& \leq & a\sum^b_{j=1}\frac{\varphi(j)}{j}+\sum^b_{j=1}R_j,
\end{eqnarray*}
which gives
\begin{align*}
t+\pi(a)\leq ab\left(\frac{\sum^b_{j=1}{\varphi(j)}/{j}-1}{b}+\frac{b+\pi(a)+\sum^b_{j=1}R_j}{ab}\right).
\end{align*}
Assume that $b>100$. By Lemmas \ref{Rj}, \ref{phi/j}, \ref{pnt} $(i)$ and the fact that $a\geq b$, we obtain
\begin{eqnarray}
\label{eq:6}
& & \frac{\sum^b_{j=1}{\varphi(j)}/{j}-1}{b}+\frac{b+\pi(a)+\sum^b_{j=1}R_j}{ab}\nonumber\\
&  \leq & \frac{6}{\pi^2}+\frac{\log b}{b}+\frac{b+.375b\log b-.432b-10+\pi(a)}{ab}\nonumber\\
&\leq &  \frac{6}{\pi^2}+\frac{\log b}{b}+\frac{.568+\frac{3}{8}\log b}{a}+
\frac{a(1+{1.2762}/{\log a})-10}{a b\log a}\nonumber\\
&\leq & \frac{6}{\pi^2}+\frac{11\log b}{8b}+\frac{1}{b\log b}\left(1+\frac{1.2762}{\log b}\right)-\frac{10}{b^2}.
\end{eqnarray}
In particular,
\begin{equation}
\label{eq:10}
t+\pi(a)\leq \left(\frac{6}{\pi^2}+o(1)\right) ab\qquad {\text{\rm when}}\qquad b\to\infty.
\end{equation}
Additionally, since the last expression \eqref{eq:6} is a decreasing function of $b$, we obtain 
$$t+\pi(a)\leq .67252ab\qquad {\text{\rm for}}\qquad b>100.
$$
Define $h_0(b)=.67252$ if $b>100$ and for $b\leq 100$ let this function be defined in the following way:
\begin{eqnarray*}
h_0(b) & := & \frac{\sum^b_{j=1}{\varphi(j)}/{j}-1}{b}\\
& + & \underset{b\leq a\leq 100}\max\left\{\frac{b+\sum^b_{j=1}R_j +\pi(a)}{ab},
\frac{b+\sum^b_{j=1}R_j}{101b}+\frac{1}{b\log 101}\left(1+\frac{1.2762}{\log 101}\right)\right\}.
\end{eqnarray*}
We then obtain from $a\geq b$ and Lemma \ref{pnt} $(i)$ that
$t+\pi(a)\leq h_0(b)ab$.

If $\pi(a)+t\leq 7$, then $\max(M, N)\leq 510510$. In fact, $b\leq a\leq 4$ in that case.
Hence, we now assume  that $\pi(a)+t\geq 8$. By Lemma \ref{pnt} $(i)$ and $(iii)$ and from the fact that $a\geq b$, we have
\begin{eqnarray*}
\prod_{\ell\leq \pi(a)+t}p_{\ell} &\leq & \exp\left(ab h_0(b)(\log h_0(b)ab+\log \log h_0(b)ab-.75\right)\\
&\leq & \exp\left(ab h_0(b) \log ab\left(1+\frac{\log h_0(b)+\log \log h_0(b)ab-.75}{\log ab}\right)\right)\\
&\leq &  \exp\left(ab h_0(b) \log ab\left(1+\frac{\log h_0(b)+\log \log h_0(b)b^2-.75}{\log b^2}\right)\right)\\
& := & \exp(h_1(b)ab\log b).
\end{eqnarray*}
Here,
$$
h_1(b)=h_0(b)\left(1+\frac{\log h_0(b)+\log \log h_0(b)b^2-.75}{\log b^2}\right).
$$
Making $b\to \infty$, we get (i) of Theorem \ref{Th1} from \eqref{eq:10}. For $b>100$, since $h_0(b)=.67252$, we get
\begin{align*}
h_1(b)\leq h_0(b)\left(1+\frac{\log h_0(b)+\log \log h_0(b)\cdot 101^2-.75}{\log 101^2}\right)
\leq .721521:=c_1,
\end{align*}
which proves (ii) of Theorem \ref{Th1}. Our arguments give upper bounds for $M(a,b)$ and $N(a,b)$ in smaller ranges of $b$ as well. That is, 
for $b\leq 100$, we get $h_1(b)\leq c_1(b)$, where the values of $c_1$ are given by:
\begin{center}
\begin{tabular}{|c|c||c|c||c|c||c|c||c|c|} \hline
$b$ & $c_1$ & $b$ & $c_1$ & $b$ & $c_1$ & $b$ & $c_1$ & $b$ & $c_1$ \\ \hline
$2$ & $9432$ & $3$ & $1.1429$ & $4$ & $.9344$ & $5$ & $.99964$ & $6$ & $.8587$ \\ \hline
$7$ & $.9074$ & $8$ & $.8448$ & $9$ & $.8279$ & $10$ & $.7813$ & $11$ & $.8186$ \\ \hline
$12$ & $.7718$ & $13$ & $.8034$ & $14$ & $.7752$ & $15$ & $.7608$ & $16$ & $.7435$ \\ \hline
$17$ & $.7689$ & $18$ & $.7419$ & $19$ & $.7646$ & $20$ & $.7454$ & $\geq 21$ & $.7463$ \\ \hline
\end{tabular}
\end{center}

\subsection{Proof of the lower bound (iii) of Theorem \ref{Th1}}
\label{subsec32}

Let $M, N$ satisfy the conditions of Theorem \ref{Th1}. For each pair $(i,j)$ with $1\leq i\leq a$ and $1\leq j\leq b$, let $p_{i,j}$ be the least prime dividing $\gcd(M-i, N-j).$ 
We consider the set
\begin{equation*}
{\mathcal P}=\{p_{i, j}: ~1\leq i\leq a, 1\leq j\leq b\}.
\end{equation*}
Suppose that $p\in {\mathcal P}$. If $p\mid \gcd(M-i, N-j)$ and $p\mid \gcd(M-i', N-j')$ for some $1\leq i,i'\leq a$ and $1\leq j,j'\leq b$ with $(i,j)\ne (i',j')$. Then $p\mid (i-i')$ and $p\mid (j-j')$. In particular, $p\leq a$.   Thus, given  $p\in {\mathcal P}$, let $(i_0, j_0)$ be the least pair with $1\leq i_0\leq a$ and $1\leq j_0\leq b$ such that $p\mid \gcd(M-i, N-j)$. Then every other pair $(i,j)$ 
with $1\leq i\leq a$ and $1\leq j\leq b$ such that $p\mid \gcd(M-i,N-j)$ has the property that $i=i_0+up$ and $j=j_0+vp$ for some non-negative integers $u,v$ with 
$0\leq u\leq \lfloor (a-1)/p\rfloor$ and $0\leq v\leq \lfloor (b-1)/p\rfloor$. Thus, for a fixed $p$, the number of pairs $(i,j)$ for which $p=p_{i,j}$ is at most
\begin{equation}
\label{eq:7}
\left(1+\left\lfloor\frac{a-1}{p}\right\rfloor \right)\left(1+\left\lfloor \frac{b-1}{p}\right\rfloor\right)=
1+\left\lfloor\frac{a-1}{p}\right\rfloor +\left\lfloor\frac{b-1}{p}\right\rfloor +\left\lfloor\frac{a-1}{p}\right\rfloor 
\left\lfloor\frac{b-1}{p}\right\rfloor.
\end{equation}
Putting also
$$
T=T(a,b)=\{(i,j): 1\leq i\leq a,~1\leq j\leq b\},
$$
and summing up the above inequality \eqref{eq:7} over all the possible primes $p\in {\mathcal P}$, we get that
\begin{align}\label{T}
\#T=ab\leq \sum_{p\in {\mathcal P}} \left(1+\frac{a+b}{p}+\frac{ab}{p^2}\right)\leq \#{\mathcal P}+(a+b)\sum_{p\leq a} \frac{1}{p}+ab\sum_{p\leq a}\frac{1}{p^2}.
\end{align}
By the prime number theorem, in the right, the second sum is 
$$
(a+b)\left(\log\log a+O(1)\right)=o(ab)
$$
because of the assumption that $\log\log t=o(b)$ as $b\to\infty$. Put 
\begin{align*}
c_2=\sum_{p\geq 2} \frac{1}{p^2}=1-c_1
\end{align*}
and $P=\#{\mathcal P}$. We then get that
\begin{align*}
ab\leq P+(c_2+o(1)) ab\quad {\text{\rm or}}\quad P\geq (c_1+o(1)) ab\qquad (b\to\infty).
\end{align*}
Now it is clear that
\begin{eqnarray*}
M^a & > & \prod_{1\leq i\leq a} (M-i)\geq \prod_{p\in {\mathcal P}} p\\
& \geq &  \prod_{k\leq P} p_k=\exp((1+o(1))P\log P)=\exp\left((c_1+o(1))ab\log ab\right),
\end{eqnarray*}
implying the desired inequality (iii) on $M$. A similar argument proves the inequality for $N$. 
Hence, part (iii) of  Theorem \ref{Th1} is proved.
\qed


\section{Proof of Theorem \ref{Slb} }
\label{sec4}

We now prove Theorem \ref{Slb} by computing $M(a, a)$ for $a>1$. We follow the same arguments as in 
Section~\ref{subsec32} with $a=b$ and arrive at 
\begin{align*}
\#T=a^2\leq  \#{\mathcal P}+2\sum_{p\leq a} \left\lfloor \frac{a-1}{p}\right\rfloor +
\sum_{p\leq a}\left\lfloor \frac{a-1}{p}\right\rfloor^2, 
\end{align*}
giving 
\begin{align}\label{P}
 \#{\mathcal P}\geq a^2-2\sum_{p\leq a} \left\lfloor \frac{a-1}{p}\right\rfloor -
 \sum_{p\leq a}\left\lfloor \frac{a-1}{p}\right\rfloor^2 \geq  
a^2- 2a\sum_{p\leq a} \frac{1}{p}-a^2\sum_{p\leq a}\frac{1}{p^2},
\end{align}
and 
\begin{align}\label{Sa}
M^a>\prod_{p\in {\mathcal P}}p\geq \prod^{\#{\mathcal P}}_{i=1}p_i=\exp(\theta(p_{\#{\mathcal P}})).  
\end{align}
Let $a\leq 100$. We explicitly compute the integral part of the middle term of  \eqref{P}, which we call it $P_a$,  
and compute  $(\prod^{P_a}_{i=1}p_i)^{\frac{1}{a}}$ to get a lower bound of $M$ giving the assertion for $a\leq 100$. 
In fact we get $M\geq \exp(a\log a)$ for $a\geq 2$.  Now we take $a\geq 101$. Then from Lemma \ref{pnt} $(v)$ and 
\begin{align*}
\sum_{p\geq a}\frac{1}{p^2}\leq \zeta(2)-\sum^{100}_{i=1}\frac{1}{i^2}+\sum_{p\leq 100}\frac{1}{p^2}\leq .4604, 
\end{align*}
we get 
\begin{align*}
 \#{\mathcal P}\geq &a^2-.4604a^2-2a\left(\log \log a+.2615+\frac{1}{\log^2 a} \right)\\
 \geq &a^2\left\{.5396-\frac{2\log \log a+.523+\frac{2}{\log^2 a}}{a} \right\}\geq .5032a^2
\end{align*}
since $a\geq 101$. This together with \eqref{Sa} and Lemma \ref{pnt} $(ii)$ and $(iv)$ gives 
 \begin{align*}
M^a>&\exp\left(.5032a^2\log (.5032a^2) (1-\frac{1}{\log (.5032a^2)})\right)\\
>& \exp\left(.5032a^2(\log a) (2+\frac{\log .5032}{\log a}) (1-\frac{1}{\log (.5032a^2)})\right)\\
>&\exp(.82248a^2\log a)  
\end{align*}
since $a\geq 101$. The proof is now complete.
\qed

\section{Acknowledgments}
\label{sec5}

We thank the referee for comments which improved the quality of this paper. The work was done during the visit of S. L. to UNAM Morelia, Mexico in December 2013 under an Indo-Mexican Joint Project. The authors thank DST and CONACyT for their support. The authors also thank Jeffrey Shallit for suggesting the problem studied in the present paper to S. L. and for his helpful  comments and suggestions along with some references in an earlier draft of the paper. 


\begin{thebibliography}{9}


\bibitem{Dus1} P. Dusart, In\'egaliti\'es explicites pour
$\psi(X), \theta(X), \pi(X)$ et les nombres premiers, 
\emph{C. R. Math. Rep. Acad. Sci. Canada} {\bf 21} (1999), 53--59. 

\bibitem{HS} F. Herzog and B. M.  Stewart, Patterns of visible and
nonvisible lattice points, \emph{Amer. Math. Monthly} {\bf 78} (1971),
487--496.

\bibitem{slpmd} S. Laishram, An estimate for the length of an
arithmetic progression the product of whose terms is almost square,
\emph{Pub. Math.  Debrecen} {\bf 68} (2006), 451--475.

\bibitem{Shallit} G. Pighizzini and J. Shallit, Unary language
operations, state complexity and Jacobsthal's function, \emph{Int. J.
Found. Comput. Sci.} {\bf 13} (2002), 145--159.

\bibitem{ros} B. Rosser and L. Schoenfeld, Approximate formulas
for some functions of prime numbers, \emph{Illinois J. Math.} {\bf 6} 
(1962), 64--94.

\bibitem{Wolf} S. Wolfram, \emph{A New Kind of Science}, Wolfram Media,
2002.  \end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 11N37; Secondary 11P21, 11H06.

\noindent \emph{Keywords: } prime number, 
Chinese remainder theorem, lattice point,
visibility, greatest common divisor.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A052157}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 7 2015;
revised versions received  October 12 2015; October 24 2015;
October 27 2015.
Published in {\it Journal of Integer Sequences}, October 29 2015.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}