What numbers can be created by $1-x^2$ and $x/2$?

Suppose I have two functions $$f(x)=1-x^2$$ $$g(x)=\frac{x}{2}$$ and the number $1$. If I am allowed to compose these functions as many times as I like and in any order, what numbers can I get to if I must take $1$ as the input? For example, I can obtain $15/16$ by using $$(f\circ g\circ g)(1)=\frac{15}{16}$$ It is obvious that all obtainable numbers are in the set $\mathbb Q\cap [0,1]$, but some numbers in this set are not obtainable, like $5/8$ (which can be easily verified).

Can someone identify a set of all obtainable numbers, or at least a better restriction than $\mathbb Q\cap[0,1]$? Or, perhaps, a very general class of numbers which are obtainable?

Solution 1:

Here's a sorted plot of all distinct values of compositions of up to 22 elementary functions f and g:

Mathematica code:

f[x_] := 1 - x^2;
g[x_] := x/2;
DeleteDuplicates[
  Sort[
         (Apply[Composition, #][x] /. x -> 1/2) & /@ 
         Flatten[Table[Tuples[{f, g}, i], {i, 22}], 1]]]

ListPlot[%]

This graph confirms the obvious fact that the value can never be greater than $1$ and that there is a gap between $1/2$ and $3/4$.

Solution 2:

By now, we've realized that all the obt. numbers have an expression as irreducible fraction that is $\frac n{2^k}$, with $n$ obviously $odd$ (except for the zero). They all belong to the interval $[0,1]$ and none belongs to $(0.5,0.75)$.

I've seen that is easy to enumerate all of them, starting by $0$ and $1$, then the only one with $k=1$, then those with $k=2$, and so.

And if $k$ is odd, then the last function applied has to be $g(x)$, and so the possible numerators when $k$ is odd are the same available for $k-1$.

Now, if $k$ is even, not only those same numerators available for $k-1$ are still possible (and will be there forever), but those that appear for having applied $f(x)$; these have to come from the obt. numbers with denominator $2^{k/2}$. These numerators will be $2^k-n^2$, where $n$ stands for every possible numerator of the obt. fractions with denominator $2^{k/2}$.

Assuming these two groups of numerators don't have a common element, we can say that the number of obt. fractions with a $2^k$ in the denominator (when expressed as irreducible), say $N_k$ is $$N_{k-1} \quad \text{if $k$ is odd and $k>1$}$$ $$N_{k-1}+N_{k/2} \quad \text{if $k$ is even and $k>2$}.$$

I've typed all the obt. numbers until $k=10$:

$$0$$ $$\color{#C00}{1}$$ $$\frac12$$ $$\frac14 \quad\frac{\color{#C00}{3}}4$$ $$\frac18 \quad \frac38$$ $$\frac1{16}\quad \frac3{16}\quad \frac{\color{#C00}{7}}{16}\quad\frac{\color{#C00}{15}}{16}$$ $$\frac1{32}\quad\frac3{32}\quad\frac7{32}\quad\frac{15}{32}$$ $$\frac1{64}\quad\frac3{64}\quad\frac7{64}\quad\frac{15}{64}\quad\frac{\color{#C00}{55}}{64}\quad\frac{\color{#C00}{63}}{64}$$ $$\frac1{128}\quad\frac3{128}\quad\frac7{128}\quad\frac{15}{128}\quad\frac{55}{128}\quad\frac{63}{128}$$ $$\frac1{256}\quad\frac3{256}\quad\frac7{256}\quad\frac{15}{256}\quad\frac{\color{#C00}{31}}{256}\quad\frac{55}{256}\quad\frac{63}{256}\quad\frac{\color{#C00}{207}}{256}\quad\frac{\color{#C00}{247}}{256}\quad\frac{\color{#C00}{255}}{256}$$ $$\frac1{512}\quad\frac3{512}\quad\frac7{512}\quad\frac{15}{512}\quad\frac{31}{512}\quad\frac{55}{512}\quad\frac{63}{512}\quad\frac{207}{512}\quad\frac{247}{512}\quad\frac{255}{512}$$ $$\tfrac1{1024}\quad\tfrac3{1024}\quad\tfrac7{1024}\quad\tfrac{15}{1024}\quad\tfrac{31}{1024}\quad\tfrac{55}{1024}\quad\tfrac{63}{1024}\quad\tfrac{207}{1024}\quad\tfrac{247}{1024}\quad\tfrac{255}{1024}\quad\tfrac{\color{#C00}{799}}{1024}\quad\tfrac{\color{#C00}{975}}{1024}\quad\tfrac{\color{#C00}{1015}}{1024}\quad\tfrac{\color{#C00}{1023}}{1024}.$$ $$$$

It can be seen that the last even $k$ for which the numbers obtained from $k-1$ and $k/2$ mix up is for $k=8$ (but anyway, there are no coincidences). For $k=10$ both groups are far from each other. It's not hard to prove that 'overlapping' may only happen for $k$ a multiple of $4$. It is not clear if there are coincidences for larger $k$ (I tend to believe there aren't, but I'll have to use something else than my intuition).

I guess is all I have by now. Not a big deal, but it might help to understand the structure of the set. And it's also interesting to know that there is a simple (and recursive) procedure to check whether a number is obt. or not.

UPDATE

After having played quite a bit with this problem and given it some thought, I still can't prove but I'm quite convinced that the set $\mathcal O$ of 'obtainable' numbers through this procedure ought to be dense in $\mathbb Q \cap\left([0,0.5]\cup[0.75,1]\right)$. That is to say, dense in $[0,1]\setminus(0.5,0.75)$ (since $\mathbb Q$ is dense in $\mathbb R$).

I made a lot of plots of finite subsets of $\mathcal O$ through two procedures:

• The first one, was to enumerate all dyadic functions in $\mathcal O$ with denominator $2^k$ until a given $k$, trough a recurrence as explained before. This led to considerable gaps in the graph (besides the already known 'big gap' at $(0.5,0.75)$, unless $k$ was large (not much more than $200$ or $300$ maybe) and this happened at a point where standard floating point operations did not offer enough precision. This process also required a lot of processing power and time. Nevertheless, it allowed me to verify that as far as floating point precision permitted, there were no repetitions in generated elements of $\mathcal O$ at each step (that is, when $k$ was a multiple of $4$ —while there was overlap between the numerators that appeared as a consequence of applying $g$ to the series corresponding to $k-1$ and applying $f$ to the series corresponding to $k/2$— all the numbers that came up with that procedure were different in fact. Precision failed in fact at $k=60$, where two apparently equal numerators appeared ($n\approx 2.88\times 10^{17}$). A deeper inspection showed that those two numerators were carried from the case $k=59$ and from $k=58$ before. But they weren't numerators for $k=57$, so they had to come from $k=58/2=29$. They did, indeed: they corresponded to numerators $n=1$ and $n=3$; but for double precision it turned out that the corresponding numerators for $k=58$, namely $2^{58}-1$ and $2^{58}-3$, where not distinguishable anymore (but these are different numbers of course). So a plain logic check between double type objects won't work for $k\ge58$.
• The other procedure was a random one, in analogy to what @david-g-stork did. First a natural number $n$ was generated, chosen randomly (this was different from david-g's choice, who took a fixed $n$) from a discrete uniform distribution in the set $\{1,2,\ldots,K\}$, and then $f$ or $g$ where applied 'recursively' and randomly (each with equal probability), starting from $x=0.5$, a total of $n$ times (between both $f$ and $g$). A total of $N$ elements of $\mathcal O$ (counting repetitions, of course) were generated this way. Then the sorted numbers where plotted against index, marking just a dot in each case to minimize overlap and increase the number of gaps visible in the graph. While for initial tests there were some small observable gaps, setting $K=100$ and $N=10^6$ was more than enough to get a pattern entirely analogous to the one found by david-g, with no visible gaps at the given resolution:

The analysis of actual gaps (which in any case are not seen in the graph, but naturally existed given the fact that the generated set was finite), showed that there are areas with much less probability of appearing (what in the graph manifests as stiffer slopes), something that could also be seen in the 'systematic' non random graph.

These 'low density' areas—for instance, that one immediately above $0.25$, but not including $0.25$ itself (which is actually a fairly common result)—tend to distribute themselves in what seems to be some kind of 'fractal' pattern, which is not at all incompatible with discrete recursive dynamics like the one described here.

Of course, there is a lot of formal work to do in order to prove —and even to unambiguously state— each one of these conjectures. But it's all I have by now.

Solution 3:

Not really an answer, but something possibly important and interesting.

Suppose we consider this problem as a random dynamical system starting with the seed $1/2$ and applying either the function $f$ or the function $g$ with equal likelihood at each step, repeating this process ad infinitum. Let us define the function $d(x)$ as the asymptotic density of points less than $x$; that is, the limit of the proportion of points less than $x$ as the number of iterations approaches infinity. Then one may establish the following functional equation using a probabilistic argument: $$d(x)=\frac{1}{2}\cdot d(2x)+\frac{1}{2}\cdot (1-d(\sqrt{1-x}))$$ or $$d(x)=\frac{d(2x)-d(\sqrt{1-x})+1}{2}$$ Now observe that the number $m=\frac{\sqrt{17}-1}{8}$ satisfies $2m=\sqrt{1-m}$, implying that $$d\bigg(\frac{\sqrt{17}-1}{8}\bigg)=\frac{1}{2}$$ and so approximately half of the points will be less than $m=\frac{\sqrt{17}-1}{8}$ for a large number of iterations (we've basically found the median of our data set).

By using the fact that $d(x)=d(1/2)\space\forall x\in [1/2,3/4]$ and the fact that $d(x)=1\space\forall x\ge 1$, one may also calculate the following special values: $$d\bigg(\frac{1}{2}\bigg)=\frac{2}{3}$$ $$d\bigg(\frac{\sqrt{17}+23}{32}\bigg)=\frac{3}{4}$$ $$d\bigg(\frac{239-23\sqrt{17}}{512}\bigg)=\frac{3}{8}$$