Rectangles Of Nonvisible Lattice Points

Shanta Laishram Stat-Math Unit Indian Statistical Institute 7 S. J. S. Sansanwal Marg New Delhi, 110016 India

                   shanta@isid.ac.in

Florian Luca School of Mathematics University of the Witwatersrand P. O. Box X3, Wits 2050 South Africa

                florian.luca@wits.ac.za

Abstract

A lattice point (0, 0) ≠ (x, y) ∈ ℤ^{2} is called visible (from the origin) if gcd(x, y) = 1 and 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 ≤ i ≤ a and 1 ≤ j ≤ b. We give upper and lower bounds for M, N.

1 Introduction

A lattice point (0, 0) ≠ (x, y) ∈ ℤ^{2} is called visible (from the origin) if gcd(x, y) = 1 and nonvisible otherwise (see Herzog and Stewart [2]). In other words, (r, s) is visible iff \frac{r}{s} is in lowest terms.

In [4], 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 ∈ {0, 1, …, r} with gcd(r − i, m − j) > 1 for 0 ≤ 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 [4] that

S(n) < e^{(2+o(1))n^{2} log n} as n → ∞,  (1)

and computed S(n) and the corresponding m’s for n = 1, 2, 3. This function was also studied by Wolfram [6, pp. 613, 1093] 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 ≤ i ≤ a and 1 ≤ j ≤ 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 ≤ i ≤ a and 1 ≤ j ≤ 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 ≥ b. In this note, we prove the following result. We always write p for a prime number.

Theorem 1. If a ≥ b, we then have

(i) max{M(a, b), N(a, b)} ≤ exp((6/π^{2} + o(1))ab log ab) as b → ∞.

(ii) max{M(a, b), N(a, b)} ≤ exp(0.721521ab log ab) if b > 100.

(iii) We have

M(a, b) ≥ exp((c_{1} + o(1))b log ab) and N(a, b) ≥ exp((c_{1} + o(1))a log ab),

where

c_{1} = 1 − ∑_{p≥2} \frac{1}{p^{2}} = 0.547753 ⋯

provided b → ∞ in such a way that log log a = o(b).

Taking a = b = n, (i) above shows that

S(n) ≤ exp((12/π^{2} + o(1))n^{2} log n) as n → ∞,

which improves (1). We also give a lower bound for S(n). We prove

Theorem 2. For n > 1, we have

S(n) ≥ exp(.82248n log n).

We also give an algorithm for computing M and N for a given a and b. This is stated in Section 3 and values of M and N are computed for some small values of a, b. The proof of Theorem 2 is given in Section 4.

2 Preliminaries

For a positive integer i, let p_{i} denote the i-th prime. Thus p_{1} = 2, p_{2} = 3, . . .. For real x > 1, let

π(x) = ∑_{p≤x} 1 and θ(x) = ∑_{p≤x} log p.

From the prime number theorem, we have π(x) ≤ s_{1}x/ log x and θ(p_{ℓ}) ≤ s_{2}ℓ log ℓ for positive constants s_{1}, s_{2}. The following results give explicit values of s_{1} and s_{2}.

Lemma 3. Let x be real and positive and ℓ be a positive integer. We have

(i) π(x) ≤ \frac{x}{log x} (1 + \frac{1.2762}{log x}) for x > 1.

(ii) p_{ℓ} ≥ ℓ log ℓ for ℓ ≥ 1.
(iii) θ(p_{ℓ}) ≤ ℓ(log ℓ + log log ℓ − .75) for ℓ ≥ 8.
(iv) θ(x) ≥ x (1 − \frac{1}{log x}) for x ≥ 41.

(v) ∑_{p≤x} \frac{1}{p} ≤ log log x + 0.2615 + \frac{1}{log^{2} x} for x > 1.

The estimates (ii), (iv) and (v) are Rosser and Schoenfeld [5, (3.12), (3.16), (3.20)], respectively. The estimate (i) is due to Dusart [1] and (iii) is derived from estimates in [1].

For given integers j ≥ r ≥ 1, let

r′ := r′(j) := #{i : 1 ≤ i ≤ r and gcd(i, j) = 1}.

Let

R_{j} := max \{r′ − \frac{rφ(j)}{j} : 1 ≤ r < j\} ,

where φ(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 − ⌊x⌋. We prove the following estimate.

Lemma 4. If n > 100, then

∑_{j=1}^{n} R_{j} ≤ .375n log n − .432n − 10.

Proof. For 1 ≤ r < j, we have

r′(j) ≤ r − ∑_{p|j} ⌊\frac{r}{p}⌋ + ∑_{pq|j} ⌊\frac{r}{pq} ⌋ − ∑_{pqr|j} ⌊\frac{r_{j}}{pqr}⌋ + ⋯,

where p, q, r, … are primes dividing j. Since

\frac{φ(j)}{j} = 1 − ∑_{p|j} \frac{1}{p} + ∑_{pq|j} \frac{1}{pq} − ∑_{pqr|j} \frac{1}{pqr} + ⋯,

we get

r′ − \frac{rφ(j)}{j} ≤ ∑_{p|j} \{\frac{r_{j}}{p} \} − ∑_{pq|j} \{\frac{r_{j}}{pq} \} + ∑_{pqr|j} \{\frac{r_{j}}{pqr}\} − · · · .

Since r/s ≤ ⌊r/s⌋ + 1 − 1/s holds for positive integers r, s, we get

R_{j} ≤ ∑_{p|j} (1 − \frac{1}{p}) + ∑_{pqr|j} (1 − \frac{1}{pqr}) + ⋯

Let ω(j) be the number of distinct prime divisors of j and put ω_{t} = \binom{j}{t}. Then

R_{j} ≤ ∑_{t odd} ω_{t} − ∑_{p|j} \frac{1}{p} = 2^{ω(j)−1} − ∑_{p|j} \frac{1}{p}.

Thus, for n > 100, we have

∑_{j=1}^{n} R_{j} ≤ ∑_{j=1}^{100} R_{j} + \frac{1}{2} ∑_{j>100}^{n} 2^{ω(j)} − ∑_{j>100}^{b} ∑_{p|j} \frac{1}{p}

= ∑_{j=1}^{100} (R_{j} − 2^{ω(j)−1} − ∑_{p|j} \frac{1}{p}) + \frac{1}{2} ∑_{j=1}^{n} 2^{ω(j)} − ∑_{j=2}^{n} ∑_{p|j} \frac{1}{p}

≤ −130.4778 + \frac{1}{2} ∑_{j=1}^{n} 2^{ω(j)} − ∑_{p≤n} ⌊\frac{n}{p}⌋ \frac{1}{p}.  (2)

Assuming n > 100, we have

∑_{p≤n} ⌊\frac{n}{p}⌋ \frac{1}{p} ≥ ∑_{p≤n} (\frac{n + 1}{p^{2}} − \frac{1}{p}) ≥ (n + 1) ∑_{p≤b} (\frac{1}{p^{2}} − \frac{1}{p(n + 1)})

≥ (n + 1) ∑_{p≤101} (\frac{1}{p^{2}} − \frac{1}{101p}) ≥ .432(n + 1).  (3)

As in the proof of [3, Lemma 9] for n ≥ 248, and using exact computations for n ∈ [101, 247], we obtain

∑_{j=2}^{n} 2^{ω(j)} − 120 ≤ .375n log n for all n > 100.  (4)

Combining the estimates (2), (3) and (4) above, we get the assertion of the lemma.

Lemma 5. For a positive integer n, we have

∑_{j=1}^{n} \frac{φ(j)}{j} ≤ \frac{6n}{π^{2}} + log n + 1.  (5)

Proof. We have

∑_{j=1}^{n} \frac{φ(j)}{j} = ∑_{j=1}^{b} \frac{μ(j)}{j} ⌊\frac{n}{j}⌋ = ∑_{j=1}^{n} \frac{μ(j)}{j} (\frac{n}{j} − \{\frac{n}{j}\}) = n ∑_{j=1}^{b} \frac{μ(j)}{j^{2}} − ∑_{j=1}^{n} \frac{μ(j)}{j} \{\frac{n}{j}\} .

Hence, inequality (5) follows from

∑_{j=1}^{n} \frac{μ(j)}{j^{2}} = ∑_{j=1}^{∞} \frac{μ(j)}{j^{2}} − ∑_{j>n} \frac{μ(j)}{j^{2}} < \frac{6}{π^{2}} + ∑_{j>n} \frac{1}{j^{2}} ≤ \frac{6}{π^{2}} + ∫_{n}^{∞} \frac{du}{u^{2}} = \frac{6}{π^{2}} + \frac{1}{n},

and

− ∑_{j=1}^{n} \frac{μ(j)}{j} \{\frac{n}{j}\} ≤ ∑_{j=2}^{n} \frac{1}{j} < ∫_{1}^{n} \frac{du}{u} = log n.

We now define two functions f and g on ℕ with values in the positive real numbers given by

f(n) = \begin{cases}∑_{j=1}^{n} φ(j)/j, & if n ≤ 100; \\ 6n/π^{2} + log n + 1, & if n > 100; \end{cases}

and

g(n) = \begin{cases}∑_{j=1}^{n} R_{j}, & if n ≤ 100; \\ .375n log n − .432n − 10, & if n > 100. \end{cases}

We observe from Lemmas 4 and 5 that inequalities f(n) ≤ 6n/π^{2} + log n + 1 for n ≥ 1 and g(n) ≤ .375n log n hold for all n ≥ 7.

3 Proof of Theorem 1

3.1 Proof of the upper bounds (i) and (ii) in Theorem 1

Let a and b be positive integers with a ≥ b. If p | M and p | N for each p ≤ b, then

gcd(M − i, N − j) > 1 for 1 ≤ i ≤ a, 1 ≤ j ≤ b and gcd(i, j) ≠ 1.

If p | M and N ≡ 1 (mod p) for every b < p ≤ a, then

gcd(M − i, N − 1) > 1 for b < i ≤ a.

Let

T := T (a, b) : = {(i, j) : 1 ≤ i ≤ a, 1 ≤ j ≤ b, gcd(i, j) = 1} \ {(i, 1) : b < i ≤ a},

and let t = #T. We label the elements of T (a, b) as

T (a, b) = {(i_{l}, j_{l}) : 1 ≤ l ≤ t}

in lexicographic order. Hence (i_{1}, j_{1}) = (1, 1), (i_{2}, j_{2}) = (1, 2), . . ..

We consider the system of congruences

M, N ≡ 0 (mod p) for p ≤ b;
M ≡ 0 (mod p) and N ≡ 1 (mod p) for b < p ≤ a;

and

M ≡ i_{ℓ} (mod p_{π(b)+ℓ}) and N ≡ j_{l} mod p_{π(b)+ℓ}) for 1 ≤ ℓ ≤ t.

By the Chinese remainder theorem, we get

max(M, N) ≤ ∏_{ℓ≤π(a)+t} p_{ℓ}.  (6)

We now estimate π(a) + t. For every 1 ≤ j ≤ b, write a = jq_{j} + r_{j} where 0 ≤ r_{j} < j. By dividing a into intervals of length j, we obtain

t + a − b = ∑_{j=1}^{b}(q_{j}φ(j) + r′_{j}) = a ∑_{j=1}^{b} \frac{φ(j)}{j} + ∑_{j=1}^{b} (r′_{j} − \frac{r_{j}φ(j)}{j})

≤ a ∑_{j=1}^{b} \frac{φ(j)}{j} + ∑_{j=1}^{b} R_{j},

which gives

t + π(a) ≤ ab (\frac{∑_{j=1}^{b} φ(j)/j − 1}{b} + \frac{b + π(a) + ∑_{j=1}^{b} R_{j}}{ab} ) .

Assume that b > 100. By Lemmas 4, 5, 3 (i) and the fact that a ≥ b, we obtain

\frac{∑_{j=1}^{b} φ(j)/j − 1}{b} + \frac{b + π(a) + ∑_{j=1}^{b} R_{j}}{ab}

≤ \frac{6}{π^{2}} + \frac{log b}{b} + \frac{b + .375b log b − .432b − 10 + π(a)}{ab}
≤ \frac{6}{π^{2}} + \frac{log b}{b} + \frac{.568 + \frac{3}{8} log b}{a} + \frac{a(1 + 1.2762/log a) − 10}{ab log a}
≤ \frac{6}{π^{2}} + \frac{11 log b}{8b} + \frac{1}{b log b} (1 + \frac{1.2762}{log b}) − \frac{10}{b^{2}}.  (7)

In particular,

t + π(a) ≤ (\frac{6}{π^{2}} + o(1)) ab when b → ∞.  (8)

Additionally, since the last expression (7) is a decreasing function of b, we obtain

t + π(a) ≤ .67252ab for b > 100.

Define h_{0}(b) = .67252 if b > 100 and for b ≤ 100 let this function be defined in the following way:

h_{0}(b) := \frac{∑_{j=1}^{b} φ(j)/j − 1}{b}
+ max_{b≤a≤100} \{\frac{b + ∑_{j=1}^{b} R_{j} + π(a)}{ab}, \frac{b + ∑_{j=1}^{b} R_{j}}{101b} + \frac{1}{b log 101} (1 + \frac{1.2762}{log 101})\} .

We then obtain from a ≥ b and Lemma 3 (i) that t + π(a) ≤ h_{0}(b)ab.

If π(a) + t ≤ 7, then max(M, N) ≤ 510510. In fact, b ≤ a ≤ 4 in that case. Hence, we now assume that π(a) + t ≥ 8. By Lemma 3 (i) and (iii) and from the fact that a ≥ b, we have

∏_{ℓ≤π(a)+t} p_{ℓ} ≤ exp (abh_{0}(b)(log h_{0}(b)ab + log log h_{0}(b)ab − .75)

≤ exp (abh_{0}(b) log ab (1 + \frac{log h_{0}(b) + log log h_{0}(b)ab − .75}{log ab}))
≤ exp (abh_{0}(b) log ab (1 + \frac{log h_{0}(b) + log log h_{0}(b)b^{2} − .75}{log b^{2}}))
:= exp(h_{1}(b)ab log b).

Here,

h_{1}(b) = h_{0}(b) (1 + \frac{log h_{0}(b) + log log h_{0}(b)b^{2} − .75}{log b^{2}}) .

Making b → ∞, we get (i) of Theorem 1 from (8). For b > 100, since h_{0}(b) = .67252, we get

h_{1}(b) ≤ h_{0}(b) (1 + \frac{log h_{0}(b) + log log h_{0}(b) · 101^{2} − .75}{log 101^{2}}) ≤ .721521 := c_{1},

which proves (ii) of Theorem 1. Our arguments give upper bounds for M(a, b) and N(a, b) in smaller ranges of b as well. That is, for b ≤ 100, we get h_{1}(b) ≤ c_{1}(b), where the values of c_{1} are given by:

\begin{matrix}b & c_{1} & b & c_{1} & b & c_{1} & b & c_{1} & b & c_{1} \\ 2 & 9432 & 3 & 1.1429 & 4 & .9344 & 5 & .99964 & 6 & .8587 \\ 7 & .9074 & 8 & .8448 & 9 & .8279 & 10 & .7813 & 11 & .8186 \\ 12 & .7718 & 13 & .8034 & 14 & .7752 & 15 & .7608 & 16 & .7435 \\ 17 & .7689 & 18 & .7419 & 19 & .7646 & 20 & .7454 & ≥ 21 & .7463 \end{matrix}

3.2 Proof of the lower bound (iii) of Theorem 1

Let M, N satisfy the conditions of Theorem 1. For each pair (i, j) with 1 ≤ i ≤ a and 1 ≤ j ≤ b, let p_{i,j} be the least prime dividing gcd(M − i, N − j). We consider the set

P = {p_{i,j} : 1 ≤ i ≤ a, 1 ≤ j ≤ b}.

Suppose that p ∈ P. If p | gcd(M −i, N −j) and p | gcd(M −i′, N −j′) for some 1 ≤ i, i′ ≤ a and 1 ≤ j, j′ ≤ b with (i, j) ≠ (i′, j′). Then p | (i − i′) and p | (j − j′). In particular, p ≤ a. Thus, given p ∈ P, let (i_{0}, j_{0}) be the least pair with 1 ≤ i_{0} ≤ a and 1 ≤ j_{0} ≤ b such that p | gcd(M − i, N − j). Then every other pair (i, j) with 1 ≤ i ≤ a and 1 ≤ j ≤ b such that p | 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 ≤ u ≤ ⌊(a − 1)/p⌋ and 0 ≤ v ≤ ⌊(b − 1)/p⌋. Thus, for a fixed p, the number of pairs (i, j) for which p = p_{i,j} is at most

(1 + ⌊\frac{a − 1}{p}⌋) (1 + ⌊\frac{b − 1}{p}⌋) = 1 + ⌊\frac{a − 1}{p}⌋ + ⌊\frac{b − 1}{p}⌋ + ⌊\frac{a − 1}{p}⌋ ⌊\frac{b − 1}{p}⌋ . (9)

Putting also

T = T (a, b) = {(i, j) : 1 ≤ i ≤ a, 1 ≤ j ≤ b},

and summing up the above inequality (9) over all the possible primes p ∈ P, we get that

#T = ab ≤ ∑_{p∈P} (1 + \frac{a + b}{p} + \frac{ab}{p^{2}}) ≤ #P + (a + b) ∑_{p≤a} \frac{1}{p} + ab ∑_{p≤a} \frac{1}{p^{2}} .  (10)

By the prime number theorem, in the right, the second sum is

(a + b) (log log a + O(1)) = o(ab)

because of the assumption that log log t = o(b) as b → ∞. Put

c_{2} = ∑_{p≥2} \frac{1}{p^{2}} = 1 − c_{1}

and P = #P. We then get that

ab ≤ P + (c_{2} + o(1))ab or P ≥ (c_{1} + o(1))ab (b → ∞).

Now it is clear that

M^{a} > ∏_{1≤i≤a}(M − i) ≥ ∏_{p∈P} p
≥ ∏_{k≤P} p_{k} = exp((1 + o(1))P log P) = exp ((c_{1} + o(1))ab log ab) ,

implying the desired inequality (iii) on M. A similar argument proves the inequality for N. Hence, part (iii) of Theorem 1 is proved.

4 Proof of Theorem 2

We now prove Theorem 2 by computing M(a, a) for a > 1. We follow the same arguments as in Section 3.2 with a = b and arrive at

#T = a^{2} ≤ #P + 2 ∑_{p≤a} ⌊\frac{a − 1}{p}⌋ + ∑_{p≤a} ⌊\frac{a − 1}{p}⌋^{2} ,

giving

#P ≥ a^{2} − 2 ∑_{p≤a} ⌊\frac{a − 1}{p}⌋ − ∑_{p≤a} ⌊\frac{a − 1}{p}⌋^{2} ≥ a^{2} − 2a ∑_{p≤a} \frac{1}{p} − a^{2} ∑_{p≤a} \frac{1}{p^{2}} ,  (11)

and

M^{a} > ∏_{p∈P} p ≥ ∏_{i=1}^{#P} p_{i} = exp(θ(p_{#P})).  (12)

Let a ≤ 100. We explicitly compute the integral part of the middle term of (11), which we call it P_{a}, and compute (∏_{i=1}^{P_{a}} p_{i})^{\frac{1}{a}} to get a lower bound of M giving the assertion for a ≤ 100. In fact we get M ≥ exp(a log a) for a ≥ 2. Now we take a ≥ 101. Then from Lemma 3 (v) and

∑_{p≥a} \frac{1}{p^{2}} ≤ ζ(2) − ∑_{i=1}^{100} \frac{1}{i^{2}} + ∑_{p≤100} \frac{1}{p^{2}} ≤ .4604,

we get

#P ≥a^{2} − .4604a^{2} − 2a (log log a + .2615 + \frac{1}{log^{2} a})

≥a^{2} \{.5396 − \frac{2 log log a + .523 + \frac{2}{log^{2} a}}{a} \} ≥ .5032a^{2}

since a ≥ 101. This together with (12) and Lemma 3 (ii) and (iv) gives

M^{a} > exp (.5032a^{2} log(.5032a^{2})(1 − \frac{1}{log(.5032a^{2})}))
> exp (.5032a^{2}(log a)(2 + \frac{log .5032}{log a})(1 − \frac{1}{log(.5032a^{2})}))
> exp(.82248a^{2} log a)

since a ≥ 101. The proof is now complete.

5 Acknowledgments

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.

References

[1] P. Dusart, Inégalitiés explicites pour ψ(X), θ(X), π(X) et les nombres premiers, C. R. Math. Rep. Acad. Sci. Canada 21 (1999), 53–59.

[2] F. Herzog and B. M. Stewart, Patterns of visible and nonvisible lattice points, Amer. Math. Monthly 78 (1971), 487–496.

[3] S. Laishram, An estimate for the length of an arithmetic progression the product of whose terms is almost square, Pub. Math. Debrecen 68 (2006), 451–475.

[4] G. Pighizzini and J. Shallit, Unary language operations, state complexity and Jacobsthal’s function, Int. J. Found. Comput. Sci. 13 (2002), 145–159.

[5] B. Rosser and L. Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94.

[6] S. Wolfram, A New Kind of Science, Wolfram Media, 2002.

2010 Mathematics Subject Classification: Primary 11N37; Secondary 11P21, 11H06. Keywords: prime number, Chinese remainder theorem, lattice point, visibility, greatest common divisor.

(Concerned with sequence \underline{A052157}.)

Received May 7 2015; revised versions received October 12 2015; October 24 2015; October 27 2015. Published in Journal of Integer Sequences, October 29 2015.

Return to Journal of Integer Sequences home page.