1
$\begingroup$

Question

I am making a tree using the following two functions:

$$f(x)=\frac{x}{r},\quad g(x)=\frac{x+b}{r}$$

where $1<r<2$ and $0<b$ are rationals. Everything is a real number here.

The starting point is $x=0$. From here, we will compute $f(0)$ and $g(0)$ which will be the branches of $x=0$. We keep on repeating this process by composing the functions in every possible combination, e.g. $f(f(0))$ and $g(f(0))$ will be the branches of $f(0)$, and $f(g(0))$ and $g(g(0))$ will be the branches of $g(0)$, and so on. If we repeat this process $n$ times, we have $2^n$ branches.

My question is, will these tree branches eventually cover all rational numbers in a certain range?

Some headway

Intuitively, when $0<x<\frac{b}{r-1}$, $f(x)$ decreases $x$, whereas $g(x)$ increases $x$, i.e. $f(x)<x$ and $g(x)>x$.

Also, let's not consider all the branches off of $f(0)$, since $f(0)=0$ (it's the same as the starting point $x=0$.) Therefore the real branching starts at the point $g(0)=b/r$.

Now let's consider the branch path where we keep on applying $g(\cdot)$. The $n$ number of compositions would be

$$ b\sum_{i=1}^n\frac{1}{r^i}$$

which converges to $\frac{b}{r-1}$ as $n\rightarrow \infty$. Therefore, the extremities of the tree are $0$ and $\frac{b}{r-1}$, which sets the range.

I guess a related or sub-question is: can there even be branches that have the same value?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ I take it $b$ and $r$ are meant to be rationals, else you're not likely to get many rationals out of your procedure. $\endgroup$
    – Gerry Myerson
    Commented Jun 2, 2023 at 2:19
  • $\begingroup$ Yes. Thank you for pointing that out. $\endgroup$
    – CWC
    Commented Jun 2, 2023 at 2:20
  • $\begingroup$ Note too that for each $r$ all values of $b$ are equivalent (just scale $x$). $$ $$ Some irrational values of $r$ yield coincident branches, e.g. $g(0) = f(g(g(0)))$ iff $r$ is the golden ratio. You may be able to show that this can't happen for rational $r \in (1,2)$. $\endgroup$
    – Noam D. Elkies
    Commented Jun 2, 2023 at 2:23
  • 2
    $\begingroup$ I had assumed when reading this that $b,r$ need not be rationals. If $b,r\in\mathbb{Q}$ we cannot obtain any fraction with prime denominator not dividing the denominator of $b$ or the numerator of $r$, right? (For irrational $b,r$ maybe one can obtain all the rationals by some Baire argument) $\endgroup$
    – Saúl RM
    Commented Jun 2, 2023 at 2:34
  • 1
    $\begingroup$ @Saúl RM there's surely no way to obtain all rationals. Any time you get a rational value you get a polynomial in $b$ and $r$. With enough such relations you can solve for $b,r$ as algebraic numbers. Then there's an integer $N$ such that both $Nb$ and $N/r$ are algebraic integers, and you can never reach any rational whose denominator contains a prime not dividing $N$. $\endgroup$
    – Noam D. Elkies
    Commented Jun 2, 2023 at 2:39

1 Answer 1

Reset to default
4
$\begingroup$

The main Question is answered in the negative by @Saúl RM in the comments. We answer the sub-question "can there even be branches that have the same value?": not for any rational $r$ other than $1$ and $-1$ (neither of which is in the allowed range $1 < r < 2$).

Indeed the "branches" are precisely the sums of finite subsets of $\{ b/r, b/r^2, b/r^3, \ldots, b/r^n, \ldots, \}$. (Proof: by induction on $n$, after $n$ steps we have the $2^n$ subsets of $\{ b/r, b/r^2, b/r^3, \ldots, b/r^n \}$.) So, some two branches coincide if and only if $P(r) = 0$ for some nonzero polynomial $P$ each of whose coefficients is $0$ or $\pm 1$. But such $P$ cannot have any rational roots other than $0$ (which is not allowed because $r$ is the denominator of $f$ and $g$) and $\pm 1$. QED

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .