APPROXIMATION OF IRRATIONAL NUMBERS BY PAIRS OF INTEGERS FROM A LARGE SET

Abstract

We show that there is a set $S \subseteq {\mathbb N}$ with lower density arbitrarily close to $1$ such that, for each sufficiently large real number $\alpha $, the inequality $|m\alpha -n| \geq 1$ holds for every pair $(m,n) \in S^2$. On the other hand, if $S \subseteq {\mathbb N}$ has density $1$, then, for each irrational $\alpha>0$ and any positive $\varepsilon $, there exist $m,n \in S$ for which $|m\alpha -n|<\varepsilon $.

1 Introduction

By Hurwitz’s theorem, for each irrational number $\alpha>0$ , there are infinitely many pairs of positive integers $(m,n)$ such that

(1.1) $$ \begin{align}|m\alpha-n|< \frac{1}{\sqrt{5} m}\end{align} $$

(see, for example, [4, page 189] or [16]). In particular, (1.1) implies that if $\alpha>0$ is irrational, then, for any $\varepsilon>0$ , there exist $m,n \in {\mathbb N}$ for which

(1.2) $$ \begin{align}|m\alpha-n|< \varepsilon.\end{align} $$

For some infinite subsets S of ${\mathbb N}$ , the inequality (1.2) also holds for infinitely many pairs $(m,n)$ , where $m \in S$ and $n \in {\mathbb N}$ . In [10], such a set S is called a Heilbronn set. For example, by Furstenberg’s theorem (see [2, 7]), the inequality (1.2) with any $\varepsilon>0$ holds for some $m \in S$ and $n \in {\mathbb N}$ , where $S \subseteq {\mathbb N}$ is a multiplicative semigroup with at least two multiplicatively independent integers, for instance, ${S=\{p^u q^v \mid u, v \in {\mathbb N} \cup \{0\}\}}$ , where $p<q$ are two fixed prime numbers. (See [11, 12, 17, 18] for some generalisations of Furstenberg’s theorem.) Also, there are some interesting sets S for which the inequality weaker than (1.1) but stronger than (1.2), namely, $|m\alpha -n|<m^{-\tau }$ , has been derived for some $\tau $ in the range $0<\tau <1$ . These are, for example, the set of squares $S=\{n^2 \mid n \in {\mathbb N}\}$ (see [19]) and the set of prime numbers ${S=P=\{p_1<p_2<p_3<\cdots \}}$ (see [1, 8, 14]), so they are Heilbronn sets.

In this paper, we are interested in obtaining inequality (1.2) for each irrational $\alpha>0$ when not only just m but both m and n belong to a subset S of ${\mathbb N}$ . For an irrational $\alpha>0$ it is clear that, for each $\varepsilon>0$ , the inequality (1.2) holds with some $m,n \in S$ if and only if $\liminf _{m,n \in S} |m\alpha -n|=0.$

For a subset E of the set of real numbers ${\mathbb R}$ , we define

(1.3) $$ \begin{align}\Delta(E):= \liminf_{x, y \in E, \> x \ne y} |x-y|.\end{align} $$

It is clear that $\Delta (S) \geq 1$ for $S \subseteq {\mathbb N}$ . With the notation as in (1.3), the problem we are interested in can be rephrased as follows: for a given $S \subseteq {\mathbb N}$ , determine whether or not, for each irrational $\alpha>0$ ,

(1.4) $$ \begin{align} \Delta(S \cup \alpha S)=0 \end{align} $$

or, alternatively, whether or not there exists an irrational $\alpha>0$ for which

(1.5) $$ \begin{align} \Delta(S \cup \alpha S)>0. \end{align} $$

For the set of squares $S=\{n^2 \mid n \in {\mathbb N}\}$ , we have option (1.5). Indeed, the distance between any two distinct elements of S is at least $3$ , while the distance between any two distinct elements of $\alpha S$ is at least $3\alpha $ . Recall that the number $\beta>0$ is badly approximable if there exists a constant $c=c(\beta )>0$ such that $|m\beta -n|>{c}/{m}$ for all $m,n \in {\mathbb N}$ . (A number is badly approximable if and only if the partial quotients of its continued fraction are bounded [4, page 190]. For example, all quadratic algebraic numbers $\beta $ are badly approximable [4, page 194].) For $\alpha =\beta ^2$ , where $\beta>0$ is a badly approximable number, the distance between $\alpha m^2 \in \alpha S$ and $n^2 \in S$ is

$$ \begin{align*}|m^2\beta^2-n^2|=|(m\beta -n)(m \beta+n))| \geq \frac{c}{m}|m\beta+n|=\frac{c}{m}(m\beta+n)>c\beta=c \sqrt{\alpha}\end{align*} $$

for some $c>0$ . Hence,

$$ \begin{align*}\Delta(S \cup \alpha S) \geq \min(3,3\alpha,c\sqrt{\alpha})>0\end{align*} $$

for each such $\alpha $ , which proves (1.5). This example appears in Ruzsa’s paper [15] in a slightly different context. (We will also use another idea from the proof of [15, Theorem 1] in the proof of our own Theorem 1.2.)

On the other hand, for the set of primes $S=P$ , the problem of determining whether we have option (1.4) or (1.5) seems to be out of reach. Option (1.4) takes place if and only if, for each irrational $\alpha>0$ and any $\varepsilon>0$ , there are prime numbers $p_i, p_j$ satisfying $|p_i \alpha -p_j|<\varepsilon $ . This is true if and only if there is an infinite sequence of primes $q_1<q_2<q_3<\cdots $ such that

(1.6) $$ \begin{align} \|q_j \alpha\| \to 0 \quad \text{as } j \to \infty \end{align} $$

and the nearest integer to $\alpha q_j$ , namely,

(1.7) $$ \begin{align} \lfloor q_j \alpha + 1/2\rfloor, \end{align} $$

is a prime number. In particular, condition (1.7) alone, without condition (1.6), is satisfied if and only if there are infinitely many primes p for which $\lfloor p \alpha + 1/2\rfloor $ is also a prime number. For any $\alpha>0$ , which is not an integer, this problem is completely out of reach (even for rational numbers $\alpha $ ). For example, for $\alpha =1/2$ , this problem is equivalent to the following. Are there infinitely many primes p for which $2p-1$ is also a prime?

As for the problem described in (1.2), in general, it is natural to expect that (1.4) is true when the set S is ‘large’ whereas (1.5) is true when S is ‘small’. However, we show that the answer to the problem does not depend just on the size of S. Recall that the lower and the upper density of the set $E \subseteq {\mathbb N}$ are defined by

$$ \begin{align*}\underline{d}(E)=\liminf_{x \to \infty} \frac{\#\{E \cap [1,x]\}}{x} \quad \text{and}\quad \overline{d}(E)=\limsup_{x \to \infty} \frac{\#\{E \cap [1,x]\}}{x}, \end{align*} $$

respectively. Clearly, $0\leq \underline {d}(E) \leq \overline {d}(E) \leq 1$ . In the case when $\underline {d}(E) = \overline {d}(E)$ , their common value $d(E)=\underline {d}(E) = \overline {d}(E)$ is called the density of E.

First, observe that, for any $\delta>0$ , there is a set of positive integers S with density at most $\delta $ such that, for each irrational $\alpha>0$ , we have $\Delta (S \cup \alpha S)=0$ . To see this, we can take, for example, an integer $b>{1}/{\delta }$ and $S=\{bk \mid k \in {\mathbb N}\}$ . Then the set S has density $d(S)=1/b<\delta $ . Also, by (1.1), for each irrational number $\alpha>0$ there are infinitely many pairs $(m,n) \in {\mathbb N}^2$ for which

$$ \begin{align*}|bm\alpha-bn|<\frac{b}{\sqrt{5}m}.\end{align*} $$

For any $\varepsilon>0$ , selecting $m>{b}/{\varepsilon \sqrt {5}}$ , we see that $0<|bm\alpha -bn|<\varepsilon $ with $bm, bn \in S$ . Hence, $\Delta (S \cup \alpha S)=0$ , as claimed. In this direction, it would be of interest to determine whether or not there is a set $S \subseteq {\mathbb N}$ with density zero such that $\Delta (S \cup \alpha S)=0$ for each irrational $\alpha $ .

In this paper, we investigate the problem in the opposite direction. First, we show that there is a ‘large’ set S (much greater than the set of squares $\{n^2 \mid n \in {\mathbb N}\}$ with density zero) for which we have option (1.5).

Theorem 1.1. For each $\delta>0$ and each sufficiently large real number $\alpha $ , there is a set of positive integers S with lower density greater than $1-\delta $ such that

(1.8) $$ \begin{align} \Delta(S \cup \alpha S) \geq \Delta\bigg(\bigcup_{k=0}^{\infty} \alpha^k S \bigg) \geq 1. \end{align} $$

Second, we prove that every set $S \subseteq {\mathbb N}$ with density $1$ satisfies option (1.4).

Theorem 1.2. If S is a set of positive integers with density $1$ , then, for each irrational number $\alpha>0$ , we have $\Delta (S \cup \alpha S)=0$ .

One can also consider approximation weaker than that in (1.2), namely, for a given $S \subseteq {\mathbb N}$ , investigate whether or not, for each $\alpha>0$ and any $\varepsilon>0$ , there are $m,n \in S$ for which

(1.9) $$ \begin{align}\bigg|\alpha-\frac{n}{m}\bigg|<\varepsilon.\end{align} $$

For example, for the set of primes $S=P$ , this problem has been considered in [9]. It was shown there that the quotients of primes are everywhere dense in $[0,\infty )$ , so each $\alpha>0$ can be approximated as in (1.9) by a quotient of two primes $n/m$ . The density of the sequence of rational numbers of the form $b^m/m$ modulo one, where $b \geq 2$ is a fixed integer and m runs through the set ${\mathbb N}$ , and similar sequences, have been considered in [3, 5, 6, 13].

The proofs of Theorems 1.1 and 1.2 will be given in Sections 2 and 3, respectively. In fact, the irrationality of $\alpha $ is not relevant in Theorem 1.2. We show that if $S \subseteq {\mathbb N}$ is a set with density $1$ , then, for each rational $\alpha>0$ ,

(1.10) $$ \begin{align} m\alpha-n=0 \end{align} $$

for infinitely many pairs $(m,n) \in S^2$ (see the end of Section 3).

2 Proof of Theorem 1.1

By the definition of $\Delta $ in (1.3), it is clear that $\Delta (E) \geq \Delta (F)$ whenever $E \subseteq F$ . Since $S \cup \alpha S$ is a subset of $\bigcup _{k=0}^{\infty } \alpha ^k S$ , this immediately implies the first inequality in (1.8).

In order to prove the second inequality in (1.8), we fix $\delta $ in the interval $(0,1)$ and a real number $\alpha $ satisfying

(2.1) $$ \begin{align} \alpha> \frac{3}{\delta}+1. \end{align} $$

We begin the construction of an infinite set $S=\{s_1<s_2<s_3<\cdots \}$ depending on $\alpha $ by selecting $s_1=1$ . Assume that, for some $m \in {\mathbb N}$ , we have already chosen the first m elements $s_1<s_2<\cdots <s_m$ of S. The next element $s_{m+1}$ is always taken as the least positive integer that is greater than $s_{m}$ and is not equal to any of the numbers

(2.2) $$ \begin{align} \lfloor \alpha^k s_j \rfloor, \quad \lceil \alpha^k s_j \rceil, \quad \text{where} \>\> k \in {\mathbb N} \>\> \text{and} \>\> j=1,\ldots,m. \end{align} $$

To see that the integers in (2.2) do not occupy all integers greater than $s_m$ and that such an $s_{m+1}>s_m$ always exists, we choose $t=t(m) \in {\mathbb N}$ so large that $\alpha ^t>s_m+2tm+1$ . (This is possible because $\alpha>1$ .) Then, for $k \geq t$ , the numbers in (2.2) are all greater than or equal to

$$ \begin{align*}\lfloor \alpha^k \rfloor>\alpha^k-1 \geq \alpha^t-1>s_m+2tm,\end{align*} $$

while for k in the range $1 \leq k \leq t-1$ , there are at most $2m(t-1)<2mt$ integers of the form (2.2). So, for each $m \in {\mathbb N}$ , it is always possible to choose the required integer $s_{m+1}$ in the interval $[s_m+1,s_m+2tm]$ ; therefore, the set S is infinite.

We claim that, for this set S, the distance between any two distinct elements of the set

$$ \begin{align*}S_{\alpha}:=\bigcup_{k=0}^{\infty} \alpha^k S\end{align*} $$

is at least $1$ . Indeed, take $x=\alpha ^u s_i \in S_{\alpha }$ and $y=\alpha ^v s_j \in S_{\alpha }$ , where $u,v \in {\mathbb N} \cup \{0\}$ and $i,j \in {\mathbb N}$ . Assume that $x \ne y$ . Then $|x-y| \geq 1$ in the case when $u=v$ , since $i \ne j$ and ${|x-y|=\alpha ^u|s_i-s_j|}$ . Assume that $u \ne v$ . Without restriction of generality, we may assume that $u<v$ . Setting $w:=v-u \in {\mathbb N}$ , we find that

$$ \begin{align*}|x-y|=|\alpha^u s_i-\alpha^v s_j|=\alpha^u|s_i-\alpha^{w}s_j| \geq |\alpha^w s_j-s_i|.\end{align*} $$

Now, in the case when $i \leq j$ , using (2.1) and $s_j \geq s_i$ , we deduce that

$$ \begin{align*}|\alpha^w s_j-s_i| = \alpha^w s_j -s_i \geq \alpha^w s_j - s_j \geq \alpha^w-1 \geq \alpha-1>\frac{3}{\delta}>3,\end{align*} $$

so $|x-y|>3$ . In the case when $i>j$ , by (2.2), $s_i$ is neither $\lfloor \alpha ^w s_j \rfloor $ nor $\lceil \alpha ^w s_j \rceil $ . Thus, the distance between $\alpha ^w s_j$ and $s_i \in {\mathbb N}$ is greater than or equal to $1$ , that is, ${|\alpha ^w s_j-s_i| \geq 1}$ . This yields $|x-y| \geq 1$ and implies that $\Delta (S_{\alpha }) \geq 1$ , which is the second inequality in (1.8).

It remains to show that the lower density of S is greater than $1-\delta $ . Let $x \geq \alpha $ be a real number. Choose the unique $\ell \in {\mathbb N}$ for which $\alpha ^{\ell } \leq x+1 < \alpha ^{\ell +1}$ . We derive a lower bound for the number of elements of S in the interval $(x/\alpha ,x]$ . By (2.2), an integer in this interval belongs to S if and only if it is not of the form $\lfloor \alpha ^k s_j \rfloor $ or $\lceil \alpha ^k s_j \rceil $ for some $k \in {\mathbb N}$ and some $j \in {\mathbb N}$ . Note that it is sufficient to consider k in the range $ 1 \leq k \leq \ell $ , since, otherwise, when $k>\ell $ ,

$$ \begin{align*} \lceil \alpha^k s_j \rceil \geq \lfloor \alpha^k s_j \rfloor \geq \lfloor \alpha^{k} \rfloor \geq \lfloor \alpha^{\ell+1} \rfloor> \alpha^{\ell+1}-1>x.\end{align*} $$

Fix $k \in \{1,\ldots ,\ell \}$ . For this k, at least one of the numbers $\lfloor \alpha ^k s_j \rfloor $ , $\lceil \alpha ^k s_j \rceil $ belongs to the interval $(x/\alpha ,x]$ only if j is such that $x/\alpha <\lceil \alpha ^k s_j \rceil $ or j is such that $\lfloor \alpha ^k s_j \rfloor \leq x$ . The first inequality does not hold if

$$ \begin{align*}x \geq \alpha \lceil \alpha^k s_j \rceil \geq \alpha^{k+1} s_j,\end{align*} $$

while the second inequality does not hold if

$$ \begin{align*}x< \lfloor \alpha^k s_j \rfloor \leq \alpha^k s_j.\end{align*} $$

Consequently, at least one of the inequalities $x/\alpha <\lceil \alpha ^k s_j \rceil $ or $\lfloor \alpha ^k s_j \rfloor \leq x$ holds only if j is such that

(2.3) $$ \begin{align}\frac{x}{\alpha^{k+1}}<s_j \leq \frac{x}{\alpha^k}.\end{align} $$

Fix a pair of positive integers $(k,j)$ for which (2.3) is true. Recall that $1 \leq k \leq \ell $ . The pair $(k,j)$ prevents at most two integers $\lfloor \alpha ^k s_j \rfloor $ , $\lceil \alpha ^k s_j \rceil $ in the interval $(x/\alpha ,x]$ from belonging to the set S. Evidently, for each $k \in \{1,\ldots ,\ell \}$ , there are at most $x/\alpha ^k$ indices j satisfying (2.3). So, the collection of all relevant pairs $(k,j)$ , where $k=1,\ldots ,\ell $ and j satisfies (2.3), prevents at most

$$ \begin{align*}2\sum_{k=1}^{\ell} \frac{x}{\alpha^k}<2\sum_{k=1}^{\infty} \frac{x}{\alpha^k}=\frac{2x}{\alpha-1}\end{align*} $$

integers of the interval $(x/\alpha ,x]$ from being in S. It follows that the intersection ${S \cap (x/\alpha ,x]}$ contains at least

$$ \begin{align*}\lfloor x \rfloor - \lfloor x/\alpha \rfloor -1 -\frac{2x}{\alpha-1}> x-2- \frac{x}{\alpha}-\frac{2x}{\alpha-1}=x\bigg(1-\frac{1}{\alpha}-\frac{2}{\alpha-1}\bigg)-2\end{align*} $$

elements. Therefore,

$$ \begin{align*}\underline{d}(S) =\liminf_{x \to \infty} \frac{\#\{S \cap [1,x]\}}{x} &\geq \liminf_{x \to \infty} \frac{\#\{S \cap (x/\alpha,x]\}}{x}\\ &\geq 1-\frac{1}{\alpha}-\frac{2}{\alpha-1}>1-\frac{3}{\alpha-1},\end{align*} $$

which is greater than $1-\delta $ in view of (2.1).

3 Proof of Theorem 1.2

Let S be a set of positive integers with density $1$ and let $\alpha>0$ be an irrational number. It is sufficient to prove that

(3.1) $$ \begin{align}\liminf_{m,n \in S} |m\alpha-n|=0\end{align} $$

for each irrational $\alpha $ in the range $0<\alpha <1$ . Indeed, for irrational $\alpha>1$ , applying (3.1) to the number $\alpha ^{-1} \in (0,1)$ , by $|m\alpha ^{-1}-n|=\alpha ^{-1}|m-n\alpha |$ , we deduce that

$$ \begin{align*}\liminf_{m,n \in S} |m-n\alpha|=0,\end{align*} $$

and hence $\Delta (S \cup \alpha S)=0$ .

So, from now on, we assume that $0<\alpha <1$ . Let $\varepsilon $ be in the range

$$ \begin{align*} 0<\varepsilon<\tfrac{1}{9}. \end{align*} $$

Throughout, we consider positive integers n satisfying

(3.2) $$ \begin{align} n> \frac{3}{\varepsilon} \quad \text{and} \quad n > \frac{1}{1-\alpha}. \end{align} $$

Assume that the nth and the $(n+1)$ st convergents of the continued fraction of $\alpha $ are $h_n/k_n$ and $h_{n+1}/k_{n+1}$ (here $h_n,k_n,h_{n+1},k_{n+1} \in {\mathbb N}$ ), which means that

(3.3) $$ \begin{align}\bigg|\alpha-\frac{h_n}{k_n}\bigg|<\frac{1}{k_n k_{n+1}} \quad \text{and} \quad \bigg|\alpha-\frac{h_{n+1}}{k_{n+1}}\bigg|<\frac{1}{k_{n+1} k_{n+2}}\end{align} $$

(see [4, page 181]). Let $u,v$ be positive integers satisfying

(3.4) $$ \begin{align} u \leq \varepsilon k_{n+1} \quad \text{and} \quad v \leq \varepsilon k_n.\end{align} $$

(Such integers exist, because $\varepsilon k_{n+1} \geq \varepsilon (k_n+k_{n-1})> \varepsilon k_n \geq \varepsilon n > 3$ by the first inequality in (3.2).) Consider the rational number

$$ \begin{align*}\mu:=\frac{uh_n+vh_{n+1}}{uk_n+vk_{n+1}}.\end{align*} $$

It is well known that ${h_n}/{k_n}<\alpha <{h_{n+1}}/{k_{n+1}}$ for even n and ${h_{n+1}}/{k_{n+1}}<\alpha <{h_{n}}/{k_{n}}$ for odd n (see [4, page 181]). In both cases, the numbers $\alpha $ and $\mu $ are between the fractions ${h_n}/{k_n}$ and ${h_{n+1}}/{k_{n+1}}$ . Therefore, by the identity

(3.5) $$ \begin{align} h_{n+1}k_n-h_nk_{n+1}=(-1)^n \end{align} $$

(see [4, page 180]), we derive

$$ \begin{align*}\bigg|\alpha-\frac{uh_n+vh_{n+1}}{uk_n+vk_{n+1}}\bigg|=|\alpha-\mu| < \bigg|\frac{h_n}{k_n}-\frac{h_{n+1}}{k_{n+1}}\bigg|=\frac{1}{k_n k_{n+1}}.\end{align*} $$

This, combined with (3.4), implies that, for

(3.6) $$ \begin{align}s(u,v,n):=uk_n+vk_{n+1} \in {\mathbb N} \quad \text{and} \quad t(u,v,n):=uh_n+vh_{n+1} \in {\mathbb N}, \end{align} $$

we have

(3.7) $$ \begin{align}|s(u,v,n)\alpha-t(u,v,n))|<\frac{uk_n+vk_{n+1}}{k_n k_{n+1}} =\frac{u}{k_{n+1}}+\frac{v}{k_n}\leq 2\varepsilon.\end{align} $$

Now, to complete the proof of the theorem it suffices to show that there are ${u,v, n \in {\mathbb N}}$ satisfying (3.2) and (3.4) such that the integers $s(u,v,n)$ , $t(u,v,n)$ as defined in (3.6) both belong to the set S.

Put

(3.8) $$ \begin{align} L_n:=\lfloor 2\varepsilon k_n k_{n+1} \rfloor. \end{align} $$

We first show that, for infinitely many $n \in {\mathbb N}$ ,

(3.9) $$ \begin{align} \# \{j \notin S, \> 1 \leq j \leq L_n\} \leq \varepsilon^2 L_n. \end{align} $$

Indeed, if the inequality opposite to (3.9) holds for all sufficiently large $n \in {\mathbb N}$ , then

$$ \begin{align*}\frac{\# \{j \in S, \> 1\leq j \leq L_n\}}{L_n}<\frac{L_n-\varepsilon^2 L_n }{L_n}=1-\varepsilon^2,\end{align*} $$

and hence

$$ \begin{align*}\underline{d}(S) =\liminf_{x \to \infty} \frac{\#\{S \cap [1,x]\}}{x} \leq \liminf_{n \to \infty} \frac{\# \{j \in S, \> 1 \leq j \leq L_n\}}{L_n} \leq 1-\varepsilon^2,\end{align*} $$

which is contrary to $d(S)=\underline {d}(S)=1$ .

We want to show that there are n satisfying (3.2) and $u,v \in {\mathbb N}$ satisfying (3.4) such that $s(u,v,n)$ and $t(u,v,n)$ both belong to S. Take any $n \in {\mathbb N}$ for which the inequalities (3.2) and (3.9) hold. Note that, by (3.4), (3.6) and (3.8), it follows that $ s(u,v,n) \leq L_n$ . We claim that

(3.10) $$ \begin{align} t(u,v,n)< s(u,v,n) \leq L_n. \end{align} $$

Indeed, by the first inequality in (3.3), we find that $|k_n \alpha -h_n|<{1}/{k_{n+1}}$ . Hence, ${h_n<k_n \alpha +{1}/{k_{n+1}}}$ . By the second inequality in (3.2), we obtain

$$ \begin{align*}1 < (1-\alpha)n \leq (1-\alpha) k_n \leq (1-\alpha) k_n^2.\end{align*} $$

It follows that $k_n\alpha +{1}/{k_{n+1}}<{1}/{k_n}+k_n\alpha < k_n$ , and hence $h_n<k_n$ . By the same argument, from the second inequality in (3.3), we get $h_{n+1}<k_{n+1}$ . Thus,

$$ \begin{align*}t(u,v,n)=uh_n+vh_{n+1}<uk_n+vh_{n+1}=s(u,v,n),\end{align*} $$

which completes the proof of (3.10) because $s(u,v,n) \leq L_n$ .

By (3.10), the integers $s(u,v,n)$ and $t(u,v,n)$ are distinct. Assume that, for some two pairs of positive integers $(u,v) \ne (u',v')$ satisfying (3.4), we have ${s(u,v,n)=s(u',v',n)}$ . This implies that $uk_n+vk_{n+1}=u'k_n+v'k_{n+1}$ by (3.6). Hence, $(u-u')k_n=(v'-v)k_{n+1}$ . By (3.5), the numbers $k_n$ and $k_{n+1}$ are coprime, which implies that $k_n \mid (v'-v)$ . However, by (3.4), $1 \leq v,v' \leq \varepsilon k_n<k_n$ , so this is only possible if $v=v'$ . This forces $u=u'$ , which is a contradiction. Therefore, $s(u,v,n) \ne s(u',v',n)$ . By the same argument, we conclude that $t(u,v,n) \ne t(u',v',n)$ .

We call a positive integer bad if it does not belong to the set S. Similarly, we call a pair of distinct integers $(s(u,v,n),t(u,v,n))$ bad if at least one of those integers is bad. Let us consider all bad integers not exceeding $L_n$ . Because of (3.9), there are at most $\varepsilon ^2 L_n$ of them. By what we have just shown above, each of them occurs in at most two pairs $(s(u,v,n),t(u,v,n))$ . (It may happen that $s(u,v,n)$ is equal to $t(u',v',n)$ for $(u,v) \ne (u',v')$ .) So, by (3.8), at most

$$ \begin{align*}2\varepsilon^2 L_n \leq 4\varepsilon^3 k_n k_{n+1}\end{align*} $$

among the pairs under consideration are bad. Note that, by (3.4), there are exactly $\lfloor \varepsilon k_{n+1}\rfloor \lfloor \varepsilon k_{n}\rfloor $ pairs $(s(u,v,n),t(u,v,n))$ with $u,v$ satisfying (3.4). Using $\varepsilon k_{n+1}>\varepsilon k_n>3$ and $0<\varepsilon <{1}/{9}$ , we deduce that

$$ \begin{align*} \lfloor \varepsilon k_{n+1}\rfloor\lfloor \varepsilon k_{n}\rfloor> (\varepsilon k_{n+1}-1)(\varepsilon k_n-1) >\frac{2\varepsilon k_{n+1}}{3} \cdot \frac{2\varepsilon k_{n}}{3} >4\varepsilon^3 k_n k_{n+1}.\end{align*} $$

Consequently, there is a pair $(s(u,v,n),t(u,v,n))$ , where $u,v$ satisfy (3.4), which is not bad. This means that these two positive integers $s(u,v,n)$ , $t(u,v,n)$ for which (3.7) is true are both in S, which is the desired conclusion. This completes the proof of Theorem 1.2.

Finally, to prove (1.10), we write $\alpha ={u}/{v}$ , where $u,v \in {\mathbb N}$ are coprime. The result is trivial for $u=v=1$ , so assume that $u \ne v$ . Take $N \in {\mathbb N}$ and consider the N pairs $(m,n)=(kv,ku)$ with $k=1,\ldots ,N$ . As above, a positive integer is called bad if it does not belong to the set S. Since the density of S is $1$ , for infinitely many $N \in {\mathbb N}$ , the set $\{1,2,\ldots ,N\max (u,v)\}$ contains at most $N/4$ bad integers. Each of those bad integers can appear in at most two pairs $(kv,ku)$ for $k=1,2,\ldots ,N$ . So, for at least ${N-2N/4=N/2}$ indices k in the range $1 \leq k \leq N$ , we must have $m=kv \in S$ and ${n=ku \in S}$ . For each of those k and $(m,n)=(kv,ku) \in S^2$ , we get ${m\alpha -n=kv({u}/{v})-ku=0}$ , as claimed in (1.10).