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?

  • 1
    Every number will be rational with a denominator a power of $2$. See if you can get every possible odd numerator. – fleablood Feb 14 at 0:00
  • 4
    @fleablood Yeah, I got that, and no, I've already demonstrated that not all odd numerators are possible (e.g. 5/8) – Frpzzd Feb 14 at 0:01
  • 2
    Numbers have the form $\dfrac n {2^{k}}$, so essentially we're interested in the pairs generated by the mappings $$(n, k) \to (2^{2k} - n^2, 2k)$$ $$(n, k) \to (n, k+1)$$ – orlp Feb 14 at 0:24
  • 1
    And because the denominator always goes up in each case, one can figure out which dyadic rationals with denominator $2^\ell$ are realized, simply by applying $f,g$ successively enough times. – Cheerful Parsnip Feb 14 at 0:32
  • 1
    I've been trying a bit using conjugacy with the fixpoint of $f(x)$ which is $\varphi ={\sqrt 5-1\over 2} \approx 0.618 $, however no clear new and usable pattern so far. Unfortunately I've n more time today... – Gottfried Helms Feb 15 at 10:41

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

enter image description here

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$.

  • Interesting... there seems to be a gap between $0.5$ and $0.7$. – Frpzzd Feb 14 at 0:33
  • 3
    I believe the gap is between $0.5$ and $0.75$ as f[g[1]] = 3/4. – David G. Stork Feb 14 at 0:36
  • 9
    It is easy to see that $I=(1/2,3/4)$ is a forbidden interval. If $x\in[0,1]$ we always have $g(x)\notin I$. On the other hand, for $f(x)$ to be in $I$ we need $x\in(1/2,\sqrt2/2)$. But that is a subset of $I$. A trivial induction then proves the presence of this gap. – Jyrki Lahtonen Feb 14 at 1:10
  • I feel a bit bad that I couldn't split the bounty evenly. I learned a piece of Mathematica programming from your answer, but, while ok, this was not quite what I was hoping to achieve with the bounty. I hope that the bounty at least resulted in more people seeing your post. Better luck next time! – Jyrki Lahtonen Feb 24 at 20:14
up vote 14 down vote
+200

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: $10^6$ numbers generated randomly.

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.

  • 4
    Instead of counting sheep last night I was thinking about this, and also reached your recurrence formula for $N_k$. I also suspect that there are no coincidences, but I'm no longer willing to bet money on it. My sample set was too small for that :-). Anyway, your argument proves that (asymptotically) only a tiny fraction of all the dyadic rationals can be reached, so +1. – Jyrki Lahtonen Feb 14 at 8:20
  • I thought the same. It seamed to me that it was too sparse a set even as to be dense in $[0,1]\setminus(0.5,0.75)$. So you should read my update. – Alejandro Nasif Salum Feb 14 at 11:04
  • Basically the plots where sampling is based on the number of iterations, while definitely indicating that some regions are sparser than others, don't seem to support the presence of other gaps. But I am not necessarily willing to bet in favor of the closure of the set of obtainable points being the complement of $(1/2,3/4)$ either :-/ – Jyrki Lahtonen Feb 14 at 12:44
  • No, but you might be right. I see that some points that were calculated are missing in my graph. Just in case, I went back to the previous version. Actually, it would make more sense to me that the set be a fractal than dense on a non-connected set. But it is what it is. – Alejandro Nasif Salum Feb 14 at 12:49
  • 1
    @RobertFrost We know that several dyadics cannot be reached, among them $61/64$. But it may still be dense in the sense that we can reach numbers arbitrarily close to $61/64$. For example $$1129896551151672206499089201035775775660700380062570008497942647651486\ 65418900223/\ 1185710993790117841137366886488964176417484642976159375764045660241030\ 44751294464$$ can be reached in less than twelve steps. It's approximately $0.95297$. Its denominator is $2^{266}$. – Jyrki Lahtonen Feb 25 at 14:56

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}$$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.