13

This is an extension of this recent question. We assume $0 \notin \mathbb{N}$.

Let's say a subset $S \subseteq\mathbb{N}$ is quotient-dense if

$$\overline{\left\{\frac{p}{q} :p,q \in S\right\}} = \mathbb{R}_{\geq 0}$$

Can we characterize the quotient-dense subsets of the natural numbers?

Some obvious examples are $\mathbb{N}$ itself, and subsets of the form $\{an+b:n \in \mathbb{N}\}$ for fixed natural $a,b$.

$S$ must obviously be countably infinite. However, this is not a sufficient condition. If we consider the set $X$ of all powers of two, then $\frac pq = 2^k$ for some $k \in \mathbb{Z}$. The closure of the set is certainly not $\mathbb{R}_{\geq 0}$

The answers in the linked question above show that the set of primes is quotient-dense. One guess is that $S$ is quotient-dense iff $$\sum_{k \in S} \frac{1}{k} = +\infty$$

EDIT: The guess above is wrong, as shown in the comments.

Eric Wofsey
  • 330,363

1 Answers1

5

This is not a complete answer to your question, but more an argument which should demonstrate that the property of being quotient-dense seems to have very few to do with the overall density of $S$.

Especially, I found two counterexamples to my former conjecture (see comments to your question) that $S=\{s_n\mid n\in\Bbb N\}$ is quotient-dense if and only if the always increasing sequence $s_n$ is sub-exponential. One of them is another counterexample to your own conjecture, but of another kind as the one given in the comments.


$s_n$ is sub-exponential, but $S$ is not quotient-dense

This not quotient dense set $S$ is generated by a sequence $s_n<7n$, obviously sub-exponential. To write down the set nicely, I will write $[a,b]_\Bbb N$ for the range of natural numbers from $a$ to $b$, e.g. $[1,6]_\Bbb N$ is short for $1,2,3,4,5,6$. Now we can define

$$S=\{[a_0,b_0]_\Bbb N,\;[a_1,b_1]_\Bbb N,\;[a_2,b_2]_\Bbb N,\;...\}$$

with $a_0=b_0=1$ and recursively $a_i=3b_{i-1}$ and $b_i=\lfloor 3/2\cdot a_i \rfloor$. The following picture shows the generating sequence $s_n$ up to $n\approx 80$ together with the bounding linear function (in gray).

It remains to show that this sequence is bounded by $7n$ and $S$ is not quotient-dense. The former statement is not hard to show but it is annoying to do nicely (I tried). So, I will only show the latter one:

Note that $a_0=b_0<a_1<b_1<a_2<b_2<\cdots$. We will see that no rational number $x\in(1/3,2/3)$ can be expressed by quotients $p,q\in S$. Lets say $p\in[a_i,b_i]_\Bbb N$ and $q\in[a_j,b_j]_\Bbb N$. Because we want to build a rational $<1$, we can assume $i\leq j$. At first assume $i<j$. Then

$$\frac pq\leq\frac {b_i}{a_j}\leq\frac{b_{j-1}}{a_j}=\frac{b_{j-1}}{3b_{j-1}}=\frac13.$$

In the other case $i=j$ we have

$$\frac pq\geq\frac {a_i}{b_i}=\frac {a_i}{\lfloor 3/2\cdot a_i\rfloor}\geq\frac {a_i}{3/2\cdot a_i}=\frac23.$$

So we indeed have this gap $(1/3, 2/3)$ that we cannot fill.


$s_n$ is growing exponentially, but $S$ is quotient-dense

At first note that it suffices to show that any number in $[0,1]$ can be approximated by $s_n/s_m$. Because given a number $x>1$, we can instead approximate $1/x\in(0,1)$ by a sequence $s_{n(i)}/s_{m(i)}$ and then convert this via exchanging nominator and denominator to the sequence $s_{m(i)}/s_{n(i)}$ which converges to $x$.

Choose an enumeration $p_i/q_i,i=1,2,3,...$ of all rational numbers in $(0,1)$. If all of these numbers are representable from $S$, then all of $[0,1]$ can be approximated. Now choose $s_1=1$ (we skip $s_0$ for no real reason) and define recursively

$$s_{2i}=2p_i \cdot s_{2i-1},\qquad s_{2i+1}=2q_i \cdot s_{2i-1}.$$

Note that because $p_i<q_i$, we indeed have $s_{2i}<s_{2i+1}$. Now we have $s_{2i}/s_{2i+1}=p_i/q_i$, hence every rational numbers in $(0,1)$ can be generated from this sequence. We have to show that the sequence is growing exponentially, but this is easy:

$$s_{2i+1}=2q_i\cdot s_{2i-1}\geq 2s_{2i-1}$$

which is an exponentially growing sub-sequence. And because $s_{2i+1}=s_{n(i)}$ with linearly growing $n(i)$, this suffices to imply that $s_n$ itself grows exponentially.


Moral of the story

If you want a nice characterization of quotient-dense sets, you should not look at properties like density. This involves your conjecture on $\sum_n s_n<\infty$ and my conjecture about sub-exponential growth.


Update

Actually any arbitrarily sparse set $S=\{s_n\mid n\in\Bbb N\}$ can be made quotient-dense by at most "doubling its density". Take an enumeration of the rationals $p_n/q_n$ as above. Then we have this new quotent-dense set

$$S':=\{p_ns_n\mid n\in\Bbb N\}\cup\{q_n s_n\mid n\in\Bbb N\}.$$

This new set has "dense" clusters of two elements and big gaps between these clusters. So it seems to have more to do with local clustering than global structure.

M. Winter
  • 29,928