# Non standard solution to $f(x) = \frac{1}{2}\Big(f(\frac{x}{2}) + f(\frac{1+x}{2})\Big)$

This functional equation appears in the following context. Let $$\alpha\in[0,1]$$ be an irrational number (called seed) and consider the sequence $$x_n=\{2^n \alpha\}$$. Here the brackets represent the fractional part function. In particular, $$\lfloor 2x_n\rfloor$$ is the $$n$$-th digit of $$\alpha$$ in base $$2$$.

The values $$x_n$$ are distributed in a certain way due to the ergodicity of the underlying process. The density associated with this distribution is the function $$f$$, and for the immense majority of seeds $$\alpha$$ that density is uniform on $$[0, 1]$$, that is, $$f(x) = 1, x \in [0, 1]$$. Such seeds $$\alpha$$ producing the uniform density are sometimes called normal numbers; their digit distribution is also uniform.

However, the functional equation $$f(x) = \frac{1}{2}\Big(f(\frac{x}{2}) + f(\frac{1+x}{2})\Big)$$ may have plenty of other solutions. Such solutions are called non-standard solutions. Can you find a seed $$\alpha$$ producing a non-standard solution, with an explicit form for $$f$$? Maybe a step-wise uniform function? The set of seeds producing non-standard solutions is known to have Lebesgue measure zero, but there are infinitely many such seeds.

All rational seeds $$\alpha$$ work, but they produce a discrete distribution. Thus their density is of the discrete type. Here however, I am interested in a continuous function $$f$$, even if it has infinitely many points of discontinuity (that is, a function $$f$$ continuous almost everywhere: the set of discontinuity points has Lebesgue measure zero.)

Update

I am looking for a function $$f$$ that is a density on $$[0, 1]$$, so there are additional constraints here: $$\int_0^1 f(x)\,dx = 1$$ and $$f(x) \geq 0$$. However, note that if $$f$$ is a solution, then $$cf$$ is also a solution regardless of the constant $$c$$. So any solution can be normalized to integrate to one. Also, $$cf+d$$ is also a solution ($$c, d$$ constants).

Second update

Below is a density satisfying all the requirements. Actually, the plot below represents its percentile distribution. It was produced with a seed $$\alpha$$ built as follows: its $$n$$-th binary digit is $$1$$ if $$\mbox{Rand}(n) < 0.75$$, and $$0$$ otherwise, using a pseudo random number generator. Note that $$P._{25} = 0.5$$ and corresponds to a dip ($$P._{25}$$ denotes the $$25$$-th percentile.) Dips are everywhere, only the big ones are visible. By contrast, the percentile distribution for the uniform case (if you replace $$0.75$$ by $$0.50$$ in $$\mbox{Rand}(n) < 0.75$$) is a straight line, with no dips.

• $f(x)=0$ is a solution, but it's not clear to me how that would relate to the seed mechanism. – Adrian Keister Aug 21 at 16:57
• One thing we know: $f(0)=f(1/2)=f(1),$ regardless of the solution elsewhere. – Adrian Keister Aug 21 at 17:12
• $f(x)=\text{const}$ works for any constant actually. – Adrian Keister Aug 21 at 17:17
• Have you looked at any of the numbers whose digits are known not to be normal or equidistributed, e.g. Liouville numbers? – Steven Stadnicki Aug 21 at 17:28
• @StevenStadnicki: it is on my "to do" list, thanks. – Vincent Granville Aug 21 at 17:39

Not an answer, just some thoughts.

Let's try applying Fourier transform:

$$f(x)=\frac{1}{\sqrt{2 \pi}}\int_{-\infty}^\infty e^{i k x} g(k) dk$$

The equation becomes:

$$\int_{-\infty}^\infty \left(2 e^{i k x}-e^{i k x/2} (1+e^{i k /2}) \right) g(k) dk=0$$

Making a simple substitution:

$$\int_{-\infty}^\infty e^{i k x} \left(g(k)- (1+e^{i k }) g(2k) \right) dk=0$$

We can consider a particular case (or is this the general case?):

$$g(k)=(1+e^{i k }) g(2k)$$

Examples:

$$g(0)=0$$

For any $$a \neq 0$$:

$$g(a)=C$$

$$g(2a)= \frac{C}{1+e^{ia}}$$

$$g(2^n a)= C \prod_{q=1}^{n-1} \frac{1}{1+e^{i q a}}$$

In the same way we can find $$g(2^{-n} a)$$.

For $$a$$ not being a rational multiple of $$\pi$$ the infinite product doesn't converge, and the function itself is not nice.

If we call:

$$G_n= -\log g(2^n), \qquad g(1)=1$$

Then the plot $$G_n$$ looks like this:

Not sure if this could lead to a non-trivial solution to the original equation though.

• I will check this out. Also the constraint that $\int_0^1 f(x) dx = 1$ is not important after all: if $f$ is a solution, then $c\cdot f$ is also a solution regardless of the constant $c$. – Vincent Granville Aug 21 at 18:46
• Sounds very interesting and inspiring. I updated my post and included an example of a special function (continuous everywhere it seems, but maybe differentiable nowhere) that satisfies the equation. – Vincent Granville Aug 22 at 5:53

Here I discuss in more detail the case mentioned in the section "second update". This special distribution was produced with a seed $$\alpha$$ built as follows: its $$n$$-th binary digit is $$1$$ if $$\mbox{Rand}(n)< p$$, and $$0$$ otherwise, using a pseudo random number generator. I used $$p=0.75$$ in my example.

Now $$x_n$$ (introduced in the first paragraph in my question) is a random variable, and we have:

$$x_n=\sum_{k=1}^\infty \frac{d_{n+k}}{b^k}.$$

Here $$b$$ is the base ($$b=2$$), and $$d_{n+k}$$ is the $$(n+k)$$-th digit of $$\alpha$$ in base $$b$$. Furthermore, by construction, these digits are identically and independently distributed with a Bernouilli distribution of parameter $$p$$. Thus, using the convolution theorem, the characteristic function of $$x_n$$ is

$$\phi(t; p, b) = \prod_{k=1}^\infty \Big(1-p(1-\exp \frac{it}{b^k})\Big).$$

Take the derivative of the inverse Fourier transform (see section inverse formula here) and you obtain

$$f(x) = \frac{1}{2\pi} \int_{-\infty}^{\infty} e^{-ity} \phi(t; p,b) dy.$$

If $$p=0.5$$ and $$b=2$$ we are back to the uniform case. If $$p\neq 0.5$$ then the solution is quite special: the density $$f$$ is nowhere continuous it seems. See picture below for $$p=0.55, b=2$$.

Now we should prove that this case is ergodic, for the functional equation to apply. I also tried to check with some sampled values of $$x$$ to see whether $$f(x) = \frac{1}{2}\Big(f(\frac{x}{2}) + f(\frac{1+x}{2})\Big)$$, but the function being discontinuous everywhere, and since I got its value approximated probably to no more than two decimals, it is not easy. The distribution attached to this density has the following moments:

• Expectation: $$\frac{p}{b-1}.$$
• Variance: $$\frac{p(1-p)}{b^2-1}.$$

An Excel spreadsheet with the computation of $$x_n$$ up to $$n=200,000$$ and with a precision of 14 decimals, is available upon request. You can interactively change $$b$$ or $$p$$ and see the result on the chart. Despite dealing with more than 200K digits, the computations are done very efficiently. Finally, the functional equation can be adapted to base $$b$$, provided $$b$$ is an integer. It becomes:

$$f(x) = \frac{1}{b}\sum_{m=0}^{b-1}f\Big(\frac{x+m}{b}\Big).$$