INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5(1) (2005), #A23

FINDING ALMOST SQUARES II

Tsz Ho Chan

American Institute of Mathematics, 360 Portage Avenue, Palo Alto, CA 94306, USA

                             thchan@aimath.org

Received: 3/25/05, Revised: 9/30/05, Accepted: 10/17/05, Published: 10/20/05

Abstract

In this article, we study short intervals that contain “almost squares” of the type: any integer n which can be factored in two different ways n = a_{1}b_{1} = a_{2}b_{2} with a_{1}, a_{2}, b_{1}, b_{2} close to \sqrt{n}.

1. Introduction

In [1], the author studied the problem of finding “almost squares” in short intervals, namely:

Question 1. For 0 ≤ θ < 1/2, what is the least f(θ) such that, for some constants c_{1}, c_{2} > 0, any interval [x−c_{1}x^{f(θ)}, x+c_{1}x^{f(θ)}] contains an integer n with n = ab, where a, b are integers in the interval [x^{1/2} − c_{2}x^{θ}, x^{1/2} + c_{2}x^{θ}]? Note: The constants c_{1} and c_{2} may depend on θ.

A similar question is the following.

Question 2. For 0 ≤ θ < 1/2, what is the least g(θ) such that, for some constants c_{1}, c_{2} > 0, any interval [x − c_{1}x^{g(θ)}, x + c_{1}x^{g(θ)}] contains an integer n with n = a_{1}b_{1} = a_{2}b_{2}, where a_{1} < a_{2} ≤ b_{2} < b_{1} are integers in the interval [x^{1/2} − c_{2}x^{θ}, x^{1/2} + c_{2}x^{θ}]? Note: The constants c_{1} and c_{2} may depend on θ.

Note: We first considered Question 2 and then turned to Question 1, which has connections to problems on the distribution of n^{2}α (mod 1) and gaps between sums of two squares.

In [1], we showed that f(θ) = 1/2 when 0 ≤ θ < 1/4, f(1/4) = 1/4 and f(θ) ≥ 1/2 − θ. We conjectured that f(θ) = 1/2 − θ for 1/4 < θ < 1/2 and gave conditional result when 1/4 < θ < 3/10. For Question 2, we have the following result.

Theorem 1. For 0 < θ < 1/4, g(θ) does not exist (i.e. all possible products of pairs of integers in [x^{1/2} − c_{2}x^{θ}, x^{1/2} + c_{2}x^{θ}] are necessarily distinct for large x).

Theorem 2. For 1/4 ≤ θ < 1/2, g(θ) ≥ 1 − 2θ.

Theorem 3. For 1/4 ≤ θ ≤ 1/3, g(θ) ≤ 1 − θ.

We believe that the lower bound is closer to the truth.

Conjecture 1. For 1/4 ≤ θ < 1/2, g(θ) = 1 − 2θ.

2. Preliminaries and 0 ≤ θ < 1/4

Suppose n = a_{1}b_{1} = a_{2}b_{2} with x^{1/2}−c_{2}x^{θ} ≤ a_{1} < a_{2} ≤ b_{2} < b_{1} ≤ x^{1/2}+c_{2}x^{θ}. Let d_{1} = (a_{1}, a_{2}) and d_{2} = (b_{1}, b_{2}) be the greatest common divisors. Then we must have d_{1}, d_{2} > 1. Otherwise, if d_{1} = 1, then a_{2} divides b_{1} which implies x^{1/2} + c_{2}x^{θ} ≥ b_{1} ≥ 2a_{2} ≥ 2x^{1/2} − 2c_{2}x^{θ}. This is impossible for large x as θ < 1/2. Now, let a_{1} = d_{1}e_{1}, a_{2} = d_{1}e_{2}, b_{1} = d_{2}f_{1} and b_{2} = d_{2}f_{2}. Here (e_{1}, e_{2}) = 1 = (f_{1}, f_{2}). Then

n = d_{1}e_{1}d_{2}f_{1} = d_{1}e_{2}d_{2}f_{2} gives e_{1}f_{1} = e_{2}f_{2}.

Due to co-primality, e_{2} = f_{1} and e_{1} = f_{2}. Therefore,

n = (d_{1}e_{1})(d_{2}e_{2}) = (d_{1}e_{2})(d_{2}e_{1})  (1)

with 1 < d_{1} < d_{2}, e_{1} < e_{2} and (e_{1}, e_{2}) = 1.

Now, from a_{2} − a_{1} ≤ 2c_{2}x^{θ}, d_{1} ≤ d_{1}e_{2} − d_{1}e_{1} ≤ 2c_{2}x^{θ}. Similarly, one can deduce that d_{2}, e_{1}, e_{2} ≤ 2c_{2}x^{θ}. Moreover, as d_{1}e_{1} = a_{1} ≥ x^{1/2} − c_{2}x^{θ}, we have d_{1}, e_{1} ≥ \frac{1}{2c_{2}} x^{1/2−θ} − \frac{1}{2}. Similarly, d_{2}, e_{2} ≥ \frac{1}{2c_{2}} x^{1/2−θ} − \frac{1}{2}. Summing up, we have

\frac{1}{2c_{2}} x^{1/2−θ} − \frac{1}{2} ≤ d_{1}, d_{2}, e_{1}, e_{2} ≤ 2c_{2}x^{θ}.  (2)

From (2), we see that no such n exists for 0 ≤ θ < 1/4 and hence Theorem 1 follows.

3. Lower bound for g(θ)

From (1) and (2), we see that an integer n = a_{1}b_{1} = a_{2}b_{2}, satisfying the conditions for a_{1}, a_{2}, b_{1}, b_{2} in Question 2, must be of the form:

n = (d_{1}e_{1})(d_{2}e_{2}) with \frac{1}{2c_{2}} x^{1/2−θ} − \frac{1}{2} ≤ d_{1}, d_{2}, e_{1}, e_{2} ≤ 2c_{2}x^{θ}

and x^{1/2} − c_{2}x^{θ} ≤ d_{1}e_{1} < d_{1}e_{2}, d_{2}e_{1} < d_{2}e_{2} ≤ x^{1/2} + c_{2}x^{θ}. In particular, e_{2}d_{2} − e_{2}d_{1} ≤ 2c_{2}x^{θ} which implies e_{2} − e_{1} ≤ 2c_{2}x^{θ}/d_{2}. Similarly, d_{2} − d_{1} ≤ 2c_{2}x^{θ}/e_{2}. Thus, the number of such tuples (d_{1}, d_{2}, e_{1}, e_{2}) is bounded by

≪ ∑_{x^{1/2−θ}≪d_{2},e_{2}≪x^{θ}} ; x^{1/2}−c_{2}x^{θ}≤d_{2}e_{2}≤x^{1/2}+c_{2}x^{θ} \frac{x^{θ}}{e_{2}} \frac{x^{θ}}{d_{2}} ≪ \frac{x^{2θ}}{x^{1/2}} x^{θ}x^{ϵ} = x^{3θ−1/2+ϵ}

for any ϵ > 0 as the number of divisor function d(n) ≪ n^{ϵ}. It follows that there are at most ≪ x^{3θ−1/2+ϵ} such integers n in the interval [x − c_{2}x^{1/2+θ}/3, x + c_{2}x^{1/2+θ}/3]. Therefore, there exist two consecutive such n’s with difference

≫ \frac{x^{1/2+θ}}{x^{3θ−1/2+ϵ}} = x^{1−2θ−ϵ}.

Pick y to be the midpoint between these two integers. Then, for some constant c > 0, the interval [y − cy^{1−2θ−ϵ}, y + cy^{1−2θ−ϵ}] does not contain any integer n = a_{1}b_{1} = a_{2}b_{2} with y^{1/2} − c_{2}y^{θ}/2 ≤ a_{1} < a_{2} ≤ b_{2} < b_{1} ≤ y^{1/2} + c_{2}y^{θ}/2, as x − c_{2}x^{1/2+θ}/3 ≤ y ≤ x + c_{2}x^{1/2+θ}/3. Consequently, for any constants c, c′ > 0, there is an arbitrarily large y such that the interval [y − cy^{1−2θ−2ϵ}, y + cy^{1−2θ−2ϵ}] does not contain any integer n = a_{1}b_{1} = a_{2}b_{2} with y^{1/2} − c′y^{θ} ≤ a_{1} < a_{2} ≤ b_{2} < b_{1} ≤ y^{1/2} + c′y^{θ}. Therefore, g(θ) ≥ 1 − 2θ − 2ϵ which gives Theorem 2 by letting ϵ → 0.

4. Upper bound for g(θ)

In this section, we prove Theorem 3. For any large x, set N = [x^{1/4}] and ξ = {x^{1/4}}, the integer part and fractional part of x^{1/4} respectively. Based on (1), we choose, for 0 ≤ ϵ ≤ 1/2,

d_{1} = qN + r_{1}, d_{2} = qN + r_{2}, e_{1} = \frac{N + s_{1}}{q} , e_{2} = \frac{N + s_{2}}{q}  (3)

for some 1 ≤ q ≤ N^{ϵ}, 0 ≤ r_{1}, r_{2} < N and s_{1}, s_{2} ≪ q with N ≡ −s_{1} ≡ −s_{2} (mod q). Our goal is to make

\begin{matrix}x = & (N + ξ)^{4} = N^{4} + 4N^{3}ξ + O(N^{2}) ≈ (qN + r_{1})\frac{N + s_{1}}{q} (qN + r_{2})\frac{N + s_{2}}{q} \\ = & [N^{2} + (\frac{r_{1}}{q} + s_{1})N + \frac{r_{1}s_{1}}{q} ][N^{2} + (\frac{r_{2}}{q} + s_{2})N + \frac{r_{2}s_{2}}{q} ] \\ = & N^{4} + (\frac{r_{1} + r_{2}}{q} + s_{1} + s_{2})N^{3} + [\frac{r_{1}s_{1}}{q} + \frac{r_{2}s_{2}}{q} + (\frac{r_{1}}{q} + s_{1})(\frac{r_{2}}{q} + s_{2})]N^{2} \\ + [\frac{r_{1}s_{1}}{q} (\frac{r_{2}}{q} + s_{2}) + \frac{r_{2}s_{2}}{q} (\frac{r_{1}}{q} + s_{1})]N + \frac{r_{1}s_{1}r_{2}s_{2}}{q^{2}} \end{matrix}  (4)

By Dirichlet’s Theorem on diophantine approximation, we can find an integer 1 ≤ q ≤ N^{ϵ} such that

|4ξ − \frac{p}{q}| ≤ \frac{1}{qN^{ϵ}}

for some integer p. Fix such a q. Then, pick s_{1} < s_{2} < 0 to be the largest two integers such that N ≡ −s_{1} ≡ −s_{2} (mod q). Clearly, s_{1}, s_{2} ≪ q. Then, one simply picks some 0 < r_{1} < r_{2} ≪ q^{2} such that \frac{r_{1}+r_{2}}{q} + s_{1} + s_{2} = \frac{p}{q}. With these values for q, r_{1}, r_{2}, s_{1}, s_{2}, (4) becomes

x ≈ N^{4} + 4N^{3}ξ + O(N^{3−ϵ}) + O(q^{2}N^{2}) + O(q^{3}N) + O(q^{4}).

Hence, we have just constructed an integer n = d_{1}e_{1}d_{2}e_{2} which is within O(N^{3−ϵ})+O(N^{2+2ϵ}) = O(x^{3/4−ϵ/4}) + O(x^{1/2+ϵ/2}) = O(x^{3/4−ϵ/4}) from x if ϵ ≤ 1/3. One can easily check that a_{1} = d_{1}e_{1}, b_{1} = d_{2}e_{2}, a_{2} = d_{1}e_{2} and b_{2} = d_{2}e_{1} are in the interval [x^{1/2} −Cx^{1/4+ϵ/4}, x^{1/2} +Cx^{1/4+ϵ/4}] for some constant C > 0. Set θ = 1/4 + ϵ/4. We have, for some C′ > 0, n = a_{1}b_{1} = a_{2}b_{2} in the interval [x − C′x^{1−θ}, x + C′x^{1−θ}] such that a_{1} < a_{2}, b_{2} < b_{1} are integers in [x^{1/2} − Cx^{θ}, x^{1/2} + Cx^{θ}], provided 1/4 ≤ θ ≤ 1/4 + 1/12 = 1/3. This proves Theorem 3.

5. Open questions

Conjecture 1 may be too hard to prove at the moment. As a possible starting point, one can attempt to show that g(1/4) = 1/2, or even just g(1/4) < 3/4. Another possibility is to try to obtain some conditional results, as in [1]. Also, one may consider g(θ) when θ is near 1/2. This leads to the problem about gaps between integers that have more than one representation as a sum of two squares.

Acknowledgments

The author would like to thank the American Institute of Mathematics for providing a stimulating environment.

References

[1] Tsz Ho Chan, Finding Almost Squares, preprint, 2005, arXiv:math.NT/0502199.