Skip to main content
fixed a typo where "$S_{1/3}$" should have been "the range of $S_{1/3}$"
Source Link
Ronnie Pavlov
  • 2.6k
  • 10
  • 15

For (1), I'm not sure you're going to find a better condition than "$r$ is an algebraic number which is the root of some polynomial with coefficients $0$ and $1$"; I certainly don't think there's an intrinsic necessary and sufficient condition there.

For (2), the answer is yes, the function is always surjective. You could prove this with a greedy algorithm. For a fixed $x \in (0, \frac{r}{1-r}]$, define $x_0 = x$, and for all $n > 0$, define $x_{n}$ to be $0$ if $x_{n-1} = 0$, and if $x_{n-1} > 0$, define $x_n = x_{n-1} - r^m$, where $m = m_n$ is the minimal positive integer for which $r^m \leq x_{n-1}$.

Since $m$ was minimal, $x_{n-1} < r^{m-1}$, and so $x_n < x_{n-1}(1-r)$. Therefore, $x_n \rightarrow 0$. This means that $x = \sum_n r^{m_n}$. Clearly $m_0 > 0$, since $x < 1$. So it remains only to check that the $m_n$ are strictly increasing. But this is easy; if $m_{n+1} \leq m_n$, then $x_{n-1} \geq r^{m_n}$ and $x_n = x_{n-1} - r^{m_n} \geq r^{m_{n+1}}$ , so $x_{n-1} \geq r^{m_n} + r^{m_{n+1}} \geq 2r^{m_n} \geq r^{m_n-1}$, contradicting minimality of $m_n$. Therefore $m_n$ is strictly increasing, and you have a representation $x = \sum_n r^{m_n}$.

By the way, this proof works even if there is a finite expansion, it will just end at that point (when $x_n = 0$).

Another point is that even when your (1) is true, i.e. $1$ has a finite expansion, you can still find an infinite expansion of $1$! This is because, if $1 = r^{n_1} + \ldots + r^{n_k}$, then $1 - r^{n_k} = r^{n_1} + \ldots + r^{n_{k-1}}$. But $1 + r^{n_k} + r^{2n_k} + r^{3n_k} + \ldots = \frac{1}{1 - r^{n-k}}$. Multiplying these yields

$1 = (r^{n_1} + \ldots + r^{n_{k-1}})(1 + r^{n_k} + r^{2n_k} + \ldots) = r^{n_1} + \ldots + r^{n_{k-1}} + r^{n_1 + n_k} + r^{n_2 + n_k} + \ldots + r^{n_{k-1} + n_k} + r^{n_1 + 2n_k} + r^{n_2 + 2n_k} + \ldots + r^{n_{k-1} + 2n_k} + \ldots$.

So, you don't have to have the clause "when (1) is not true"; for every $r \in (1/2, 1)$, $1$ can be written as $S_r(F)$ for some $F \in \mathcal{F}_N$.

Also, something you said is confusing; you said if you allow $0$ exponents, then $S_{1/n}$ would always be surjective, but this is clearly false. For instance, the range of $S_{1/3}$ would be the set of numbers with ternary expansion (including a possible $(1/3)^0 = 1$ term) containing only $0$s and $1$s, which is clearly a Cantor set and not an interval.

For (1), I'm not sure you're going to find a better condition than "$r$ is an algebraic number which is the root of some polynomial with coefficients $0$ and $1$"; I certainly don't think there's an intrinsic necessary and sufficient condition there.

For (2), the answer is yes, the function is always surjective. You could prove this with a greedy algorithm. For a fixed $x \in (0, \frac{r}{1-r}]$, define $x_0 = x$, and for all $n > 0$, define $x_{n}$ to be $0$ if $x_{n-1} = 0$, and if $x_{n-1} > 0$, define $x_n = x_{n-1} - r^m$, where $m = m_n$ is the minimal positive integer for which $r^m \leq x_{n-1}$.

Since $m$ was minimal, $x_{n-1} < r^{m-1}$, and so $x_n < x_{n-1}(1-r)$. Therefore, $x_n \rightarrow 0$. This means that $x = \sum_n r^{m_n}$. Clearly $m_0 > 0$, since $x < 1$. So it remains only to check that the $m_n$ are strictly increasing. But this is easy; if $m_{n+1} \leq m_n$, then $x_{n-1} \geq r^{m_n}$ and $x_n = x_{n-1} - r^{m_n} \geq r^{m_{n+1}}$ , so $x_{n-1} \geq r^{m_n} + r^{m_{n+1}} \geq 2r^{m_n} \geq r^{m_n-1}$, contradicting minimality of $m_n$. Therefore $m_n$ is strictly increasing, and you have a representation $x = \sum_n r^{m_n}$.

By the way, this proof works even if there is a finite expansion, it will just end at that point (when $x_n = 0$).

Another point is that even when your (1) is true, i.e. $1$ has a finite expansion, you can still find an infinite expansion of $1$! This is because, if $1 = r^{n_1} + \ldots + r^{n_k}$, then $1 - r^{n_k} = r^{n_1} + \ldots + r^{n_{k-1}}$. But $1 + r^{n_k} + r^{2n_k} + r^{3n_k} + \ldots = \frac{1}{1 - r^{n-k}}$. Multiplying these yields

$1 = (r^{n_1} + \ldots + r^{n_{k-1}})(1 + r^{n_k} + r^{2n_k} + \ldots) = r^{n_1} + \ldots + r^{n_{k-1}} + r^{n_1 + n_k} + r^{n_2 + n_k} + \ldots + r^{n_{k-1} + n_k} + r^{n_1 + 2n_k} + r^{n_2 + 2n_k} + \ldots + r^{n_{k-1} + 2n_k} + \ldots$.

So, you don't have to have the clause "when (1) is not true"; for every $r \in (1/2, 1)$, $1$ can be written as $S_r(F)$ for some $F \in \mathcal{F}_N$.

Also, something you said is confusing; you said if you allow $0$ exponents, then $S_{1/n}$ would always be surjective, but this is clearly false. For instance, $S_{1/3}$ would be the set of numbers with ternary expansion (including a possible $(1/3)^0 = 1$ term) containing only $0$s and $1$s, which is clearly a Cantor set and not an interval.

For (1), I'm not sure you're going to find a better condition than "$r$ is an algebraic number which is the root of some polynomial with coefficients $0$ and $1$"; I certainly don't think there's an intrinsic necessary and sufficient condition there.

For (2), the answer is yes, the function is always surjective. You could prove this with a greedy algorithm. For a fixed $x \in (0, \frac{r}{1-r}]$, define $x_0 = x$, and for all $n > 0$, define $x_{n}$ to be $0$ if $x_{n-1} = 0$, and if $x_{n-1} > 0$, define $x_n = x_{n-1} - r^m$, where $m = m_n$ is the minimal positive integer for which $r^m \leq x_{n-1}$.

Since $m$ was minimal, $x_{n-1} < r^{m-1}$, and so $x_n < x_{n-1}(1-r)$. Therefore, $x_n \rightarrow 0$. This means that $x = \sum_n r^{m_n}$. Clearly $m_0 > 0$, since $x < 1$. So it remains only to check that the $m_n$ are strictly increasing. But this is easy; if $m_{n+1} \leq m_n$, then $x_{n-1} \geq r^{m_n}$ and $x_n = x_{n-1} - r^{m_n} \geq r^{m_{n+1}}$ , so $x_{n-1} \geq r^{m_n} + r^{m_{n+1}} \geq 2r^{m_n} \geq r^{m_n-1}$, contradicting minimality of $m_n$. Therefore $m_n$ is strictly increasing, and you have a representation $x = \sum_n r^{m_n}$.

By the way, this proof works even if there is a finite expansion, it will just end at that point (when $x_n = 0$).

Another point is that even when your (1) is true, i.e. $1$ has a finite expansion, you can still find an infinite expansion of $1$! This is because, if $1 = r^{n_1} + \ldots + r^{n_k}$, then $1 - r^{n_k} = r^{n_1} + \ldots + r^{n_{k-1}}$. But $1 + r^{n_k} + r^{2n_k} + r^{3n_k} + \ldots = \frac{1}{1 - r^{n-k}}$. Multiplying these yields

$1 = (r^{n_1} + \ldots + r^{n_{k-1}})(1 + r^{n_k} + r^{2n_k} + \ldots) = r^{n_1} + \ldots + r^{n_{k-1}} + r^{n_1 + n_k} + r^{n_2 + n_k} + \ldots + r^{n_{k-1} + n_k} + r^{n_1 + 2n_k} + r^{n_2 + 2n_k} + \ldots + r^{n_{k-1} + 2n_k} + \ldots$.

So, you don't have to have the clause "when (1) is not true"; for every $r \in (1/2, 1)$, $1$ can be written as $S_r(F)$ for some $F \in \mathcal{F}_N$.

Also, something you said is confusing; you said if you allow $0$ exponents, then $S_{1/n}$ would always be surjective, but this is clearly false. For instance, the range of $S_{1/3}$ would be the set of numbers with ternary expansion (including a possible $(1/3)^0 = 1$ term) containing only $0$s and $1$s, which is clearly a Cantor set and not an interval.

Source Link
Ronnie Pavlov
  • 2.6k
  • 10
  • 15

For (1), I'm not sure you're going to find a better condition than "$r$ is an algebraic number which is the root of some polynomial with coefficients $0$ and $1$"; I certainly don't think there's an intrinsic necessary and sufficient condition there.

For (2), the answer is yes, the function is always surjective. You could prove this with a greedy algorithm. For a fixed $x \in (0, \frac{r}{1-r}]$, define $x_0 = x$, and for all $n > 0$, define $x_{n}$ to be $0$ if $x_{n-1} = 0$, and if $x_{n-1} > 0$, define $x_n = x_{n-1} - r^m$, where $m = m_n$ is the minimal positive integer for which $r^m \leq x_{n-1}$.

Since $m$ was minimal, $x_{n-1} < r^{m-1}$, and so $x_n < x_{n-1}(1-r)$. Therefore, $x_n \rightarrow 0$. This means that $x = \sum_n r^{m_n}$. Clearly $m_0 > 0$, since $x < 1$. So it remains only to check that the $m_n$ are strictly increasing. But this is easy; if $m_{n+1} \leq m_n$, then $x_{n-1} \geq r^{m_n}$ and $x_n = x_{n-1} - r^{m_n} \geq r^{m_{n+1}}$ , so $x_{n-1} \geq r^{m_n} + r^{m_{n+1}} \geq 2r^{m_n} \geq r^{m_n-1}$, contradicting minimality of $m_n$. Therefore $m_n$ is strictly increasing, and you have a representation $x = \sum_n r^{m_n}$.

By the way, this proof works even if there is a finite expansion, it will just end at that point (when $x_n = 0$).

Another point is that even when your (1) is true, i.e. $1$ has a finite expansion, you can still find an infinite expansion of $1$! This is because, if $1 = r^{n_1} + \ldots + r^{n_k}$, then $1 - r^{n_k} = r^{n_1} + \ldots + r^{n_{k-1}}$. But $1 + r^{n_k} + r^{2n_k} + r^{3n_k} + \ldots = \frac{1}{1 - r^{n-k}}$. Multiplying these yields

$1 = (r^{n_1} + \ldots + r^{n_{k-1}})(1 + r^{n_k} + r^{2n_k} + \ldots) = r^{n_1} + \ldots + r^{n_{k-1}} + r^{n_1 + n_k} + r^{n_2 + n_k} + \ldots + r^{n_{k-1} + n_k} + r^{n_1 + 2n_k} + r^{n_2 + 2n_k} + \ldots + r^{n_{k-1} + 2n_k} + \ldots$.

So, you don't have to have the clause "when (1) is not true"; for every $r \in (1/2, 1)$, $1$ can be written as $S_r(F)$ for some $F \in \mathcal{F}_N$.

Also, something you said is confusing; you said if you allow $0$ exponents, then $S_{1/n}$ would always be surjective, but this is clearly false. For instance, $S_{1/3}$ would be the set of numbers with ternary expansion (including a possible $(1/3)^0 = 1$ term) containing only $0$s and $1$s, which is clearly a Cantor set and not an interval.