1 Introduction
By Hurwitz’s theorem, for each irrational number $\alpha>0$ , there are infinitely many pairs of positive integers $(m,n)$ such that
(see, for example, [Reference Coppel4, page 189] or [Reference Schmidt16]). 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
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 [Reference Iyer10], such a set S is called a Heilbronn set. For example, by Furstenberg’s theorem (see [Reference Boshernitzan2, Reference Furstenberg7]), 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 [Reference Katz11, Reference Kra12, Reference Urban17, Reference Urban18] 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 [Reference Zaharescu19]) and the set of prime numbers ${S=P=\{p_1<p_2<p_3<\cdots \}}$ (see [Reference Balog, Daboussi, Liardet and Rauzy1, Reference Heath-Brown and Jia8, Reference Matomäki14]), 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
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$ ,
or, alternatively, whether or not there exists an irrational $\alpha>0$ for which
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 [Reference Coppel4, page 190]. For example, all quadratic algebraic numbers $\beta $ are badly approximable [Reference Coppel4, 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
for some $c>0$ . Hence,
for each such $\alpha $ , which proves (1.5). This example appears in Ruzsa’s paper [Reference Ruzsa15] in a slightly different context. (We will also use another idea from the proof of [Reference Ruzsa15, 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
and the nearest integer to $\alpha q_j$ , namely,
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
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
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
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
For example, for the set of primes $S=P$ , this problem has been considered in [Reference Hobby and Silberger9]. 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 [Reference Cilleruelo, Kumchev, Luca, Rué and Shparlinski3, Reference Dubickas5, Reference Dubickas6, Reference Lind13].
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$ ,
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
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
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
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
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
Now, in the case when $i \leq j$ , using (2.1) and $s_j \geq s_i$ , we deduce that
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 $ ,
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
while the second inequality does not hold if
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
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
integers of the interval $(x/\alpha ,x]$ from being in S. It follows that the intersection ${S \cap (x/\alpha ,x]}$ contains at least
elements. Therefore,
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
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
and hence $\Delta (S \cup \alpha S)=0$ .
So, from now on, we assume that $0<\alpha <1$ . Let $\varepsilon $ be in the range
Throughout, we consider positive integers n satisfying
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
(see [Reference Coppel4, page 181]). Let $u,v$ be positive integers satisfying
(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
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 [Reference Coppel4, 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
(see [Reference Coppel4, page 180]), we derive
This, combined with (3.4), implies that, for
we have
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
We first show that, for infinitely many $n \in {\mathbb N}$ ,
Indeed, if the inequality opposite to (3.9) holds for all sufficiently large $n \in {\mathbb N}$ , then
and hence
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
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
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,
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
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
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).