density of set question. help appreciated again!

Question

Here's another question I don't know what to do with. Compute the Shnirelman density of the set

$$A = \{ \lfloor n \ln (n) \rfloor : n = 1,2,3,... \}.$$

I know that the Shnirelman density of a set $A$ is

$$\inf \left\{ \frac{ | A \cap \{1,\ldots,n\}|}{n} : n \in \mathbb{N} \right\}$$

I've computed some values of $\lfloor n \ln (n) \rfloor$:

$$ \begin{array}{l|ccccccccccc} \,\,n&1&2&3&4&5&6&7&8&9&10&11\\\hline \lfloor n \ln (n) \rfloor&0&1&3&5&8&10&13&16&19&23&26 \end{array} $$

So I guess the first elements of $A$ are $\{0,1,3,5,8,10,13,16,19,23,26\}$. This means I can start trying to figure ou tthe density.

$$ \begin{array}{l|ccccccccccc} \,\,n&1&2&3&4&5&6&7&8&9&10&11\\\hline | A \cap \{1,...,n\}| &1&1&2&2&3&3&3&4&4&5&5 \\ \frac{| A \cap \{1,...,n\}|}{n}&1&\frac{1}{2}&\frac{2}{3}&\frac{2}{4}&\frac{3}{5}&\frac{3}{6}&\frac{3}{7}&\frac{4}{8}&\frac{4}{9}&\frac{5}{10}&\frac{5}{11} \end{array} $$

Not sure where to go from here. Any help is great! Better help is better! Thanks in advance!

Answer 1

(Getting another question off the unanswered list.)

This can be solved with elementary techniques.

For $n\in\Bbb Z^+$ let $a_n=\lfloor n\ln n\rfloor$ and $b_n=\big|A\cap[n]\big|$, where as usual $[n]=\{1,\ldots,n\}$; we want to determine $\inf\left\{\frac{b_n}n:n\in\Bbb Z^+\right\}$.

It’s worth noting that a rough heuristic argument suggests that this infimum is $0$: in the first $n\ln n$ positive integers there should be about $n$ members of $A$, and $\frac{n}{n\ln n}=\frac1{\ln n}$ tends to $0$ as $n$ increases without bound.

Let

$$c_n=\max\{k\in\Bbb Z^+:b_k=n\}\,,$$

so that $b_{c_n}=n$, and $b_{c_n+1}=n+1$, and in particular $c_n+1\in A$, i.e., $c_n+1=a_k$ for some $k\ge 2$. The sequence $\langle a_k:k\ge 2\rangle$ enumerates $A$ in ascending order, so in fact $c_n+1$ must be the $(n+1)$-st term of this sequence, i.e., $c_n+1=a_{n+2}$, and therefore

$$c_n=a_{n+2}-1=\lfloor(n+2)\ln(n+2)\rfloor-1$$

for each $n\in\Bbb Z^+$. Now $\ln(n+2)>1$ for $n\in\Bbb Z^+$, so

$$(n+2)\ln(n+2)-n\ln(n+2)=2\ln(n+2)>2\,,$$

and hence

$$\lfloor(n+2)\ln(n+2)\rfloor-\lfloor n\ln(n+2)\rfloor\ge 2\,.$$

Then $\lfloor(n+2)\ln(n+2)\rfloor\ge\lfloor n\ln(n+2)\rfloor+2$, so

$$\begin{align*} \frac{c_n}n&=\frac{\lfloor(n+2)\ln(n+2)\rfloor-1}n\\ &\ge\frac{\lfloor n\ln(n+2)\rfloor+1}n\\ &>\frac{n\ln(n+2)}n\\ &=\ln(n+2)\,. \end{align*}$$

Recalling that $b_{c_n}=n$, we see that

$$\frac{b_{c_n}}{c_n}=\frac{n}{c_n}<\frac1{\ln(n+2)}\,,$$

so

$$\lim_{n\to\infty}\frac{b_{c_n}}{c_n}=0\,,$$

and hence

$$\inf\left\{\frac{b_n}n:n\in\Bbb Z^+\right\}=0\,,$$

as expected.