What is the solution to this challenging number theory problem?

[Nono713]

Let $S$ be a nonempty set of natural numbers, equipped with the following membership rules:
$$\text{if} ~ ~ x \in S ~ ~ \text{then} ~ ~ 4x \in S \tag{1}$$
$$\text{if} ~ ~ x \in S ~ ~ \text{then} ~ ~ \lfloor \sqrt{x} \rfloor \in S \tag{2}$$
Show that $S = \mathbb{N}$, and find all the natural numbers $k$ for which this still holds if rule $(1)$ becomes $x \in S \implies kx \in S$ (i.e. substituting $k$ instead of $4$).

 

[mathbalarka]

Spoiler

This is a fun problem! :D I have, or I think I have, a solution for the first part of the problem.

We are given that $\Bbb N \supseteq S \neq \emptyset$, thus there is a $k \in \Bbb N$ such that $k \in S$. By rule $(2)$, $\lfloor \sqrt{k} \rfloor \in S$. Repeatedly applying rule $(2)$ in this fashion $n$ times, we see that there is an integer smaller than $k^{1/2^n}$ and (not strictly) greater $1$ in $S$. However, it is clear there exists a large $n$ for which $k^{1/2^n} \leq 2$. As $S \subseteq \Bbb N$ and since the only integer in $[1, 2)$ is $1$, we conclude that $1 \in S$.

By rule $(1)$, $4 \cdot 1$ is in $S$ and by rule $(2)$, $\lfloor \sqrt{4} \rfloor = 2$ is in $S$. It is thus clear that all of the powers of $2$ are in $S$. Now note that as $\Bbb Q$ is dense in $\Bbb R$, there are (well, countably) infinitely many rationals in the interval $[\log_2(n), \log_2(n+1)]$ for some integer $n$. We can thus cutoff the two ends of this interval to produce some interval $[a_0/b_0, a_1/b_1] \subseteq [\log_2(n), \log_2(n+1)]$ with rational limit points. As $a_0/b_0 < a_1/b_1$, i.e., $a_0 b_1 < a_1b_0$, we can always produce an integer $x$ inside $(a_0 b_1 \cdot 2^k, a_1 b_0 \cdot 2^k)$ for some proper choice of $k$. Thus $x/2^k \in [a_0/b_0, a_1/b_1] \subseteq [\log_2(n), \log_2(n+1)]$, i.e., $n^{(2^k)} \leq 2^x \leq (n + 1)^{(2^k)}$. As $2^x \in S$, applying rule $(2)$, $k$ times, on $2^x$ results $n \in S$. As this procedure can be applied to any integer $n$, we have $S = \Bbb N$.

 

[Nono713]

Well done mathbalarka for participating and correctly answering the first part of the challenge! (though I believe extending it to also solve the second part is reasonably straightforward with some minor changes). My own original solution is given below, it follows the same major steps as mathbalarka's solution but uses different tools to arrive at the result:

Spoiler

I will immediately prove the second part of the challenge, the first part being a special case.

We first prove the lemma that if $[a, b)$ is an interval with $ka < b$ for integers $a, b, k > 1$ then $[a, b)$ contains a power of $k$. We first note that $k^0 = 1 < a$. Now suppose $k^r < a$ for any $r \in \mathbb{N}$. Then there are three possibilities: either $k^{r + 1} < a$, $k^{r + 1} \geq b$, or $k^{r + 1} \in [a, b)$. Now $k^{r + 1} \geq b$ is impossible, since $ka < b$ and $k^r < a$ hence $k(k^r) = k^{r + 1} < b$. If $k^{r + 1} < a$, then we can repeat the argument until $k^{r + s} \in [a, b)$ for some $s > 0$, which will happen as the sequence $(k^n)_{n = 0}^\infty$ is strictly increasing.

Since $\lfloor \sqrt{1} \rfloor = 1$ and $\lfloor \sqrt{x} \rfloor < x$ for $x > 1$ since $\lfloor \sqrt{x} \rfloor^2 \leq x$, it follows that repeatedly applying rule $(2)$ starting from any integer will eventually yield 1. Since $S$ is nonempty, there exists at least one element in $S$, and thus $1 \in S$ by the above reasoning. It therefore suffices to show that $1 \in S \implies x \in S$ for all $x \in \mathbb{N}$ to prove the claim. Denote $I_n$ the interval $[x^{2^n}, (x + 1)^{2^n})$. This interval $I_n$ can be made arbitrarily large by increasing $n$, as:
$$\lim_{n \to \infty} \frac{(x + 1)^{2^n}}{x^{2^n}} = \lim_{n \to \infty} \left ( \frac{x + 1}{x} \right)^{2^n} = \infty$$
In other words, the upper bound of the interval grows faster than the lower bound, and hence $I_n$ is asymptotically unbounded in size.

Now let $k \in \mathbb{N}$ such that $x \in S \implies kx \in S$. Since $1 \in S$, repeatedly applying this rule amounts to saying that $k^r \in S$ for all $r \in \mathbb{N}$. We have seen that $I_n$ can be made arbitrarily large, thus there exists an $n$ such that $kx^{2^n} < (x + 1)^{2^n}$ for any $k$. Hence by the lemma, $k^r \in [ x^{2^n}, (x + 1)^{2^n} )$ for some $r \in \mathbb{N}$. At this point, since $k^r \in S$, it suffices to repeatedly apply rule $(2)$ on $k^r$ which is guaranteed to eventually yield $x$ by monotonicity of the square root floor function, and we conclude that $x \in S$. We have only needed $k > 1$ (for the lemma) and therefore $S = \mathbb{N}$ for all (integer) $k > 1$, including $k = 4$. $\blacksquare$​