# Solution space to a functional equation

This question comes from my attempts at understanding an example presented by Bill Gasarch on his blog. The example is of a continuous strictly increasing function whose derivative is zero almost everywhere. The example is apparently discussed in the book Probability and Measure by Patrick Billingsley, but I currently do not have access to it.

Gasarch explains the background very well. Given a parameter $p \in (0,1)$, he describes a continuous function $F:[0,1]\to[0,1]$ which is increasing, $F(0) = 0$, $F(1) = 1$, but such that $F' = 0$ a.e. The derivative $f = F'$, which is only defined almost everywhere, must be nonnegative and should satisfy the following functional equation $$f(x) = \begin{cases} 2pf(2x) & \text{when x \in (0,1/2),} \\ 2(1-p)f(2x-1) & \text{when x \in (1/2,1),} \end{cases}$$ almost everywhere. It would seem, from the claimed example, that a nonnegative measurable function that satisfies this functional equation almost everywhere must be $0$ almost everywhere. However, this is not true since every constant function satisfies this functional equation when $p = 1/2$. Thinking about the dynamic properties of the transformation $$T(x) = \begin{cases} 2x & \text{when x \in [0,1/2),} \\ 1/2 & \text{when x = 1/2 (say),} \\ 2x-1 & \text{when x \in (1/2,1],} \end{cases}$$ it does seem that the space of solutions to the above equation is heavily constrained.

Is there a nice characterization of the space of solutions to the above functional equation? A general characterization would be best but a characterization for special cases (e.g. $f \geq 0$, $p = 1/2$) would be welcome.

-

Here is the proof that $F'=0$ almost everywhere, if $p\neq \frac 1 2$ :

We have $F(x) = pF(2x)$ if $x \in [0,0.5]$ and $F(x) = p + (1-p)F(2x-1)$ if $x \in [0.5,1]$.

Let $x \in (0,1)$ and suppose $x$ is normal in binary. Then $F'(x)=0$ :
Let $k>0$, and suppose the first $k$ digits of $x$ contain $a$ digits $0$, $b$ digits $1$, and that the length of the streak of consecutive $0$s (or consecutive $1$s) at the end of those $k$ digits is $c$. For example suppose the $k$th digit is $0$ (so there are $c$ consecutive $0$s)
If $2^{-(k+1)} \le |x-y| < 2^{-k}$, then $y$ has the same $k-c$ first digits as $x$, thus $|F(x)-F(y)| = p^{a-c} (1-p)^b |F(?)-F(?)| \le p^{a-c} (1-p)^b$, so the slope between those points is bounded by $\frac{|F(x)-F(y)|}{|x-y|} \le p^{a-c} (1-p)^b 2^{k+1} = 2 (2p)^a (2(1-p))^b p^{-c} = 2(4p(1-p))^{k/2} (\frac{1-p}p)^{b-a}p^{-c}$.
When $p \neq \frac 1 2$, $4p(1-p) < 1$. Moreover, since $x$ is normal, $(a-b)/k$ converges to $0$ as $k$ grows, as does $c/k$, so after taking logarithms it becomes clear that this quantity converges to $0$ as $k$ grows.

Now, about the positive nonzero solutions of your functional equation. If you write $x$ in binary, the orbit of $x$ when acted on by the two transformations of the functional equation is the set of $y$ such that the binary expansions of $x$ and $y$ are the same up to removing/adding/changing a finite number of digits. Basically they are equivalent if you can truncate them (not necessarily at the same place) so that you are left with two identical infinite strings.

One problem is that if a string is ultimately periodic (so if $x \in \mathbb Q$), then it makes a nontrivial cycle. The functional equation implies that $f(x) = (2p)^a (2(1-p))^b f(x)$ where the repeating portion of the expansion of $x$ has $a$ digits $1$ and $b$ digits $0$. If this multiplier $(2p)^a (2(1-p))^b$ is not one, then $f(x)$ has to be $0$. Thus, for most values of $p$, $f=0$ on $\mathbb Q$.

Then from this point, $f$ is determined by its value for any set of representants of the equivalence classes of binary strings.

if (again) $p \neq \frac 1 2$, then $f$ is unbounded on any open interval, and if $\log {\frac p {1-p}}$ is irrational, its graph is even dense in $[0;1] \times \mathbb R^+$ :

Suppose $x \in (0,1)$ and that $F(x) > 0$. The functional equation basically says that if we plug $a$ digits $0$s and $b$ digits $1$ in front of its binary expansion to get a number $y$ (in any order), then $F(y) = (2p)^{-a}(2(1-p))^{-b}F(x)$. By fixing the first digits of $y$ you can force $y$ to be in any open interval you want, and then by putting additional digits, since $\log(2p)$ and $\log(2(1-p))$ are of different sign, you can make the multiplier as high (or as low) as you need to get above (or under) a specific value. And in case their quotient is irrational you can make it as close to a specific value as you need.

If $p= \frac 1 2$, then the value of $F(x)$ doesn't change if you change/add/remove a finite amount of digits in the binary expansion of $x$, so the solutions are simply functions from the set of equivalence classes of binary strings into $\mathbb R$. They are still not good-looking, except the continuous ones which are constant.

-
Perfect. Thanks! –  François G. Dorais Aug 1 '12 at 7:02