Difficulty with diophantine approximation: building sets with arbitrary lower and upper natural densities

82 Views Asked by At

$\newcommand{\d}{\mathrm{d}}\newcommand{\du}{\overline{\mathrm{d}}}\newcommand{\dl}{\underline{\mathrm{d}}}\newcommand{\card}{\operatorname{card}}$This was left as an exercise:

Show that for all $0\le\alpha\le\beta\le1$, there exists an $A\subseteq\Bbb N$ with: $$\dl(A)=\alpha,\,\du(A)=\beta$$

Where:

$$\dl(A)=\liminf_{n\to\infty}\frac{1}{n}\card[A\cap[1,2,\cdots,n]],\,\du(A)=\limsup_{n\to\infty}\frac{1}{n}\card[A\cap[1,2,\cdots,n]]$$

I will construct $A$ through the notion of $1$ and $0$ values in the sequence. Suppose $A$ is of the form $[1,1,1,1,...,0,0,0,....,1,1,1,1....]$ etc. where the lengths of each $0,1$ run are to be found. Suppose the $n$th run of ones terminates at position $\lambda_n$, and the $n$th run of zeroes terminates at position $\kappa_n$ (for me $\Bbb N$ does not here contain $0$ and I index from position $1$):

$$\cdots,0,0,0,0,\underset{\kappa_n}{0},1,1,1,1,\cdots,1,1,1,\underset{\lambda_{n+1}}{1},0,0,\cdots$$

Then the optimum density value will be obtained from the sequence:

$$\frac{1}{\lambda_n}\card[A\cap[1,2,\cdots,\lambda_n]]=\frac{1}{\lambda_n}\sum_{k=0}^{n-1}(\lambda_{n+1}-\kappa_n)$$

If I set $\kappa_0:=0$ for convenience. Likewise the minimal density value will be obtained from the sequence:

$$\frac{1}{\kappa_n}\card[A\cap[1,2,\cdots,\kappa_n]]=\frac{1}{\kappa_n}\sum_{k=0}^{n-1}(\lambda_{n+1}-\kappa_n)$$

We know we can write $\Bbb Q\supset(p_n/q_n)\to\alpha$, $\Bbb Q\supset(r_n/s_n)\to\beta$. If I assert $s_n:=\lambda_n$, $q_n:=\kappa_n$, I obtain the following equations that need solving:

$$r_n=p_n=\sum_{k=0}^{n-1}(\lambda_{n+1}-\kappa_n)=\sum_{k=0}^{n-1}(s_{n+1}-q_n)$$

Ok, well if the numerators are known and we wish to find suitable denominators this amounts to the recurrences:

$$s_n=q_{n-1}+r_n-r_{n-1},\,q_n=s_n-r_n+r_{n-1}$$

But now the thorny issue: can I guarantee finding numbers $s_n,q_n,r_n,p_n$ in this way such that $(p_n=r_n)/q_n\to\alpha,\,(p_n=r_n)/s_n\to\beta$? I know that if I have two rational approximations to $\alpha,\beta$ I can set the numerators the same by e.g. using the lowest common multiple, but I don't think I can ensure the denominators have this pattern. Differently put, if $p_n/q_n\to\alpha$ and $r_n/s_n\to\beta$, I need to find $\tau_n$ a common multiple of $p_n,r_n$ at each stage, i.e. $\tau_n=i_np_n=j_nr_n$, such that $j_ns_n\gt i_nq_n$, $j_ns_n=i_{n-1}q_{n-1}+\tau_n-\tau_{n-1}$ and $i_nq_n=j_ns_n-\tau_n+\tau_{n-1}$, because then letting $\lambda_n:=j_ns_n$ and $\kappa_n:=i_nq_n$ will build $A$ so that the cardinality ratios will equal $p_n/q_n,r_n/s_n$ at each stage and tend to $\alpha,\beta$. Can we show existence for $i_n,j_n$?

Let's wlog take the initial sequences such that $q_n\gt s_n$ at each stage. We want then to find $j_n\ge i_n$, two sequences, which solve:

$$j_n=\frac{1}{s_n}(i_{n-1}q_{n-1}+i_np_n-i_{n-1}p_{n-1}),\,i_n=\frac{1}{q_n}(j_ns_n-j_nr_n+j_{n-1}r_{n-1}),\,i_np_n=j_nr_n$$

With $i_0=j_0=0$.

Which determines $i_n$ completely if $j_n$ is known, but honestly I don't know how to resolve this - if it even can be resolved. How can I make this work? Many thanks, and a note: I never touch number theory usually - this exercise came from an ergodic theory textbook and just piqued my interest - so I really do not know anything; I could well be missing something obvious.

1

There are 1 best solutions below

4
On BEST ANSWER

Let me propose a solution that can be written simply.

For $0<\alpha<\beta<1$, define the following procedure.

[[The proof isn't that different for $0=\alpha<\beta<1$, or $\alpha=\beta$, or for the few other cases.]]

The first number in our sequence is $0$, that is to say $a_1=0$.

Then keep having $1$ as the next term, and stop as soon as the density exceeds $\beta$.

Formally, $a_2=\cdots=a_{m_1}=1$ where $m_1$ is chosen so that $\dfrac{m_1-2}{m_1-1}\leq\beta$ and $\dfrac{m_1-1}{m_1}>\beta$.

Afterwards, keep having $0$ as the next term, and stop as soon as the density is less than $\alpha$.

Formally, $a_{m_1+1}=\cdots=a_{m_1+k_1}=0$, where $k_1$ is chosen so that $\dfrac{m_1-1}{m_1+k_1-1}\geq\alpha$ and $\dfrac{m_1-1}{m_1+k_1}<\alpha$.

Define $m_i,k_i$ similarly for $i>1$.

In other words, $\dfrac{m_1+m_2-2}{m_1+k_1+m_2-1}\leq\beta$, $\dfrac{m_1+m_2-1}{m_1+k_1+m_2}>\beta$,

and also $\dfrac{m_1+m_2-1}{m_1+k_1+m_2+k_2-1}\geq\alpha$, $\dfrac{m_1+m_2-1}{m_1+k_1+m_2+k_2}<\alpha$.

Et cetera.

Let the density of the first $t$ terms be $f(t)$.

Since $m_i$ and $k_i$ are positive for all $i$,

you'd be right to think that $f\bigg(\sum_{i=1}^n (m_i+k_i)\bigg)\to\alpha$ and that $f\bigg(m_{n+1}+\sum_{i=1}^n (m_i+k_i)\bigg)\to\beta$.

For example, start with $0<\dfrac{N-k}{N}<\alpha$. We want to know how close $a_m=\dfrac{N-k+m}{N+m}$ gets to $\beta$ once it exceeds $\beta$. It will be as close to $\beta$ (if not closer) as the largest difference $a_{m+1}-a_m$. Notice that $\dfrac{N-k+x}{N+x}$ is a concave function of $x\geq0$. So the differences get smaller as $m$ gets larger. Therefore, the largest difference is $a_1-a_0=\dfrac{k}{N(N+1)}$. You can set a bound on it by recalling that $N$ and $k$ are related by $0<\dfrac{N-k}{N}<\alpha$. How does the bound behave as $N$ gets large?

In the argument, $N$ is supposed to represent $\sum_{i=1}^n (m_i+k_i)$. Both $m_i$ and $k_i$, because of the way we've defined them, are positive integers. Therefore, $\sum_{i=1}^n (m_i+k_i)\geq 2n$. That's why we regard $N$ as getting arbitrarily large.

These sequences, converging to $\alpha$ and $\beta$, are also useful bounds for $f(t)$ on $t>N$.