Existence of a "densest" sequence with natural density $0$

Question

Determine whether there exists an increasing, infinite sequence of natural numbers $S$ with natural density $0$ such that, for almost all $n$ and any increasing, infinite sequence $P\neq S$ also with natural density $0$, $$\sum_{i=1}^{n}(\mathbb{I}_i(S)-\mathbb{I}_i(P))>0$$ (Note: Here, $\mathbb{I}_i$ represents the indicator function, which equals $1$ if $i$ is in sequence $S$ or $P$ and $0$ otherwise)

I came up with this problem while idly daydreaming, not from any textbook or math course. I'm not very experienced with this type of problem (as a high school senior, it's kind of out of my historical purview), but I think I have a solution, written below. If I've made any mistakes in notation, rigorousness, or otherwise, feel free to let me know.

Answer 1

Suppose such a sequence $S$ exists. Then there is some natural number $k\notin S$ because the natural density of $S$ is zero. Inserting $k$ into the sequence yields a new sequence that violates the condition for all $n$. So no such sequence exists.

So not only does such a sequence not exist, but in fact for any sequence $S$ of density $0$ and any natural number $N$, there exists a sequence $P$ of density $0$ such that for almost all $n$ you have $$\sum_{i=1}^{n}(\mathbb{I}_i(S)-\mathbb{I}_i(P))<N.$$

Answer 2

Assume, for the sake of contradiction, that we have such a sequence $A$. By construction, no other sequence can fulfill the conditions in the question- otherwise it would be impossible for both the sum and its negative to be $>0$ almost all of the time. Because $A$ has natural density $0$, there must exist a point at which the gap between consecutive elements of the sequence have a difference $>1$. At that point, we insert an element with a value strictly between that of the anterior and posterior elements to create a sequence $A'$. We now want to show, for the sake of contradiction, that $A'$ fulfills all of the conditions given in the question.

The addition of one element will not change an infinite sequence with natural density $0$ to one with a natural density $>0$, so this condition on $A'$ is fulfilled. Furthermore, there are only finitely many elements before the point at which we inserted the extra value, and infinitely many after that point. Therefore almost all of the possible $n$ on which to test whether $$\sum_{i=1}^{n}(\mathbb{I}_i(A')-\mathbb{I}_i(A))>0$$ do in fact give $$\sum_{i=1}^{n}(\mathbb{I}_i(A')-\mathbb{I}_i(A))=1>0$$ and so $A'$ fulfills the conditions of the question. But the original $A$ was just such a sequence that there could be no other sequence that fulfilled those conditions! This is a contradiction, and so we have shown that no such sequence can exist. QED. $\blacksquare$

Answer 3

Given an infinite set $S$ with density $0$, to construct a set $P$ of density $0$ whose summatory function grows asymptotically faster:

For all $k\ge 0,a\ge 0$, $2^k-a\in P$ if $2^{k/2} (\sum_{n\in S,n\le 2^{k+1}} 1)^{1/2}\ge a$