A question about dense sets

Question

Suppose that $A$ is a given subset of $I=[0,1],\ $ and $ \left\{ x_j = \frac{j}{m} \right\}_{j=0}^{m}\ $ is the $m$-partition of $I$, and $\nu(m)$ is the number of $\ [x_{i-1},x_{i}]\ $ such that $\ [x_{i-1},x_{i}]\cap A \neq \emptyset\ $ for intervals $\ [x_{i-1},x_{i}]\ $ belonging to the $m$-partition. Also assume that $M>0$ is such that

$$ \forall_{m>M}\quad \nu(m) \ge \ln(m) $$

Does it follow that $A$ is dense on some open non-empty subinterval of $I$?

Remark (editorial by wlod): the rest of the post is unclear to editor wlod. Once the things get clear, this remark should be removed. ### This remark is here to avoid a prolonged (if momentary) discussion in comments. ### Also, Wlod followed by Andreas have provided counter-examples, and -- to make it better -- they need not the complication of constant $M$. Wlod stated the result for general functions $f$ in place of $\ f:=\ln$. Then Andreas had it for a wider class of functions $f$ (but Wlod's proof handles it too).

An example:

Let $A = \{\frac{1}{j}\}_{j=1}^{\infty}$. By some calculation we can get the value of $n$: $$1,7,23,70,211,649,$$ when $m$ is $1,10,100,1000,10000,100000$,respectively.

Notes: I want to emphasize that you cannot construct $A$ with $m$ related to the precondition, because $m$ is given and changing to $\infty$ after $A$ has been supposed. Even if you want to construct $A$ with some variables, please notice that when $A$ is constructed, your variables are fixed and cannot follow the change of $m$.

Answer 1

I'll construct an $A$ that satisfies the conditions of the question but is not dense in any interval. I'll use the notation in the question and abbreviate the $i$-th interval of the $m$-th partition as $J(m,i)$. There are two requirements that I need to satisfy:

(1) For every $m$, $A$ contains points from at least $\ln m$ of the $m$ intervals $J(m,i)$.

(2) For all $m$ and all $i$, $J(m,i)$ has a nontrivial subinterval $K(m,i)$ disjoint from $A$.

Note that requirement (2) ensures that $A$ is not dense in any nontrivial interval, because any such interval includes $J(m,i)$ for some $m$ and some $i$.

I'll build $A$ by an inductive process. At step number $m$, I'll choose some finitely many points to put into $A$ in order to satisfy (1) for the current $m$, and I'll choose the $m$ subintervals $K(m,i)$ to satisfy (2) for the current $m$ and all $i\leq m$. Of course I need to make sure that the points I put into $A$ for the sake of (1) are not in any previously chosen excluded interval $K$ and that the intervals $K$ that I exclude for the sake of (2) don't contain any of the points previously put into $A$.

Fix, for the rest of the construction, a sequence of positive real numbers $r(m)$ small enough so that $\sum_{m=1}^\infty mr(m)<\frac12$. The subintervals $K(m,i)$ chosen at step $m$ will each have length $\leq r(m)$.

Now here's how to do step $m$. The previous steps have put (altogether) finitely many points into $A$. So I can choose, inside each of the $m$ intervals $J(m,i)$, a subinterval containing none of the points already put into $A$. Shrinking those subintervals if necessary, I can arrange that each has length $\leq r(m)$. Take those shrunken subintervals as $K(m,i)$.

What is the total length of all the intervals $K(q,i)$ chosen so far, i.e., with $q\leq m$ and $i\leq q$? Well, at step $q$, we chose $q$ intervals of length at most $r(q)$, so the total length is at most $\sum_{q=1}^m q\cdot r(q)$, which is less than $\frac12$ by our choice of the $r$ sequence. So those intervals, though they might intersect all of the current $J(m,i)$'s, cannot completely cover more than $\frac m2$ of them. In each of the $J(m,i)$ that are not completely covered, which is at least $\frac m2$ of them, we can choose a point and put it into $A$. Do so; this satisfies requirement (1) with room to spare ($\lceil\frac m2\rceil$ instead of $\ln m$). This completes the construction of the counterexample.

Remark: The "room to spare" that I pointed out at the end of the construction can be amplified. For any fixed $\epsilon$, we can get $A$ to meet all but $\epsilon m$ of the intervals $J(m,i)$ in the $m$-th partition. Just choose the $r(m)$'s a little smaller.1

Answer 2

Let the number of the $m$-th partition intervals which intersect $\ A\ $ be $\ \ge f(m).\ $ Then

Theorem  There exists $\ A\ $ which is not dense in any non-trivial interval whenever

$$ \lim_{m=\infty} \frac {f(m)}m\ =\ 0 $$

Proof  The required $\ A\ $ can be given as follows:

$$ A\ :=\\ \ \left\{ \frac {2\cdot k-1}{2\cdot m}: \ m\in\Bbb N\ \ \text{and} \ \ k\in\Bbb Z\ \ \text{and}\ \ 0<k\le f(m)\,\right\} $$

End of Proof