# Blancmange curve

(Redirected from Midpoint displacement)

In mathematics, the blancmange curve is a fractal curve constructible by midpoint subdivision. It is also known as the Takagi curve, after Teiji Takagi who described it in 1901, or as the Takagi–Landsberg curve, a generalization of the curve named after Takagi and Georg Landsberg. The name blancmange comes from its resemblance to a pudding of the same name. It is a special case of the more general de Rham curve.

## Definition

The blancmange function is defined on the unit interval by

${\displaystyle {\rm {blanc}}(x)=\sum _{n=0}^{\infty }{s(2^{n}x) \over 2^{n}},}$

where ${\displaystyle s(x)}$ is the triangle wave, defined by ${\displaystyle s(x)=\min _{n\in {\mathbf {Z}}}|x-n|}$, that is, ${\displaystyle s(x)}$ is the distance from x to the nearest integer.

The Takagi–Landsberg curve is a slight generalization, given by

${\displaystyle T_{w}(x)=\sum _{n=0}^{\infty }w^{n}s(2^{n}x)}$

for a parameter w; thus the blancmange curve is the case ${\displaystyle w=1/2}$. The value ${\displaystyle H=-\log _{2}w}$ is known as the Hurst parameter.

The function can be extended to all of the real line: applying the definition given above shows that the function repeats on each unit interval.

## Graphical construction

The blancmange curve can be visually built up out of triangle wave functions if the infinite sum is approximated by finite sums of the first few terms. In the illustration below, progressively finer triangle functions (shown in red) are added to the curve at each stage.

 n = 0 n ≤ 1 n ≤ 2 n ≤ 3

## Properties

### Convergence and continuity

The infinite sum defining ${\displaystyle T_{w}(x)}$ converges absolutely for all x: since ${\displaystyle 0\leq s(x)\leq 1/2}$ for all ${\displaystyle x\in \mathbb {R} }$, we have:

${\displaystyle \sum _{n=0}^{\infty }|w^{n}s(2^{n}x)|\leq 1/2\sum _{n=0}^{\infty }|w|^{n}={\frac {1}{2}}\cdot {\frac {1}{1-|w|}}}$ if ${\displaystyle |w|<1}$.

Therefore, the Takagi curve of parameter w is defined on the unit interval (or ${\displaystyle \mathbb {R} }$) if ${\displaystyle |w|<1}$.

The Takagi function of parameter w is continuous. Indeed, the functions ${\displaystyle T_{w,n}}$ defined by the partial sums ${\displaystyle T_{w,n}(x)=\sum _{k=0}^{n}w^{k}s(2^{k}x)}$ are continuous and converge uniformly toward ${\displaystyle T_{w}}$, since:

${\displaystyle \left|T_{w}(x)-T_{w,n}(x)\right|=\left|\sum _{k=n+1}^{\infty }w^{k}s(2^{k}x)\right|=\left|w^{n+1}\sum _{k=0}^{\infty }w^{k}s(2^{k+n+1}x)\right|\leq {\frac {|w|^{n+1}}{2}}\cdot {\frac {1}{1-|w|}}}$ for all x when ${\displaystyle |w|<1}$.

This value can be made as small as we want by selecting a big enough value of n. Therefore, by the uniform limit theorem, ${\displaystyle T_{w}}$ is continuous if |w|<1.

### The special case of the parabola

For ${\displaystyle w=1/4}$, one obtains the parabola: the construction of the parabola by midpoint subdivision was described by Archimedes.

### Differentiability

The Takagi curve is a fractal for parameters ${\displaystyle \scriptstyle w\neq 1/4}$, as it is nowhere differentiable in the classic definition of delta-epsilon differentiability on the real number line (that is, w.r.t. the natural topology on the reals). However, by instead representing a real number as a 2-adic expansion of binary bits, one may temporarily adopt the product topology of the Cantor set, and immediately give meaning of the differential as a formal sum. That is, by noting that the derivative of a triangle wave is a square wave (equivalently, the repeated Haar mother wavelet):

${\displaystyle {\frac {d}{dx}}s(x)=-{\mbox{sgn}}\left(x-{\frac {1}{2}}\right)={\begin{cases}+1{\mbox{ for }}0

one may immediately write the formal sum

${\displaystyle {\frac {d}{dx}}T_{w}(x)=\sum _{n=0}^{\infty }(2w)^{n}\,{\mbox{sgn}}\left(s\left(2^{n}x-{\frac {1}{4}}\right)-{\frac {1}{2}}\right)}$

This sum is manifestly convergent for ${\displaystyle w<1/2}$, although it is ill-defined at all dyadic rationals. It is the temporary adoption of the product topology that allows this formal manipulation to be given a practical meaning. Thus, it is more accurate to say that the Takagi curve is not differentiable on the dyadic rationals; it is "well-behaved" elsewhere (on the irrationals, and the non-dyadic rationals). The derivative is discontinuous at all dyadic rationals.

Equivalently, one may apply the discrete wavelet transform to obtain a representation in terms of Haar wavelets ${\displaystyle \psi _{n,k}(x)}$; the wavelet coefficients take a particularly simple form:

${\displaystyle {\frac {d}{dx}}T_{w}(x)=\sum _{n=0}^{\infty }2^{n/2}w^{n}\,\psi _{n,0}(x)}$

### Fourier series expansion

The Takagi-Landsberg function admits an absolutely convergent Fourier series expansion:

${\displaystyle T_{w}(x)=\sum _{m=0}^{\infty }a_{m}\cos(2\pi mx)}$

with ${\displaystyle \scriptstyle a_{0}=1/4(1-w)}$ and, for ${\displaystyle \scriptstyle m\geq 1}$

${\displaystyle a_{m}:=-{\frac {2}{\pi ^{2}m^{2}}}(4w)^{\nu (m)}\,,}$

where ${\displaystyle \scriptstyle 2^{\nu (m)}}$ is the maximum power of ${\displaystyle 2}$ that divides ${\displaystyle m}$. Indeed, the above triangle wave ${\displaystyle s(x)}$ has an absolutely convergent Fourier series expansion

${\displaystyle s(x)={\frac {1}{4}}-{\frac {2}{\pi ^{2}}}\sum _{k=0}^{\infty }{\frac {1}{(2k+1)^{2}}}\cos {\big (}2\pi (2k+1)x{\big )}.}$

By absolute convergence, one can reorder the corresponding double series for ${\displaystyle T_{w}(x)}$:

${\displaystyle T_{w}(x):=\sum _{n=0}^{\infty }w^{n}s(2^{n}x)={\frac {1}{4}}\sum _{n=0}^{\infty }w^{n}-{\frac {2}{\pi ^{2}}}\sum _{n=0}^{\infty }\sum _{k=0}^{\infty }{\frac {w^{n}}{(2k+1)^{2}}}\cos {\big (}2\pi 2^{n}(2k+1)x{\big )}\,:}$

putting ${\displaystyle \scriptstyle m:=2^{n}(2k+1)}$ yields the above Fourier series for ${\displaystyle \scriptstyle T_{w}(x)}$.

## Recursive definition

The periodic version of the Takagi curve can also be defined recursively by:

${\displaystyle T_{w}(x)=s(x)+wT_{w}(2x)}$.

The version restricted to the unit interval can also be defined recursively by:

${\displaystyle T_{w}(x)={\begin{cases}x+wT_{w}(2x)&{\text{if }}0\leq x\leq 1/2\\(1-x)+wT_{w}(2x-1)&{\text{if }}1/2

Proof:

{\displaystyle {\begin{aligned}T_{w}(x)&=\sum _{n=0}^{\infty }w^{n}s(2^{n}x)\\&=s(x)+\sum _{n=1}^{\infty }w^{n}s(2^{n}x)\\&=s(x)+w\sum _{n=0}^{\infty }w^{n}s(2^{n+1}x)\\&=s(x)+wT_{w}(2x)\end{aligned}}}.

Observe that this definition has the form of a discrete wavelet transform; thus the coefficients of the wavelet transform take a particularly simple form.

## Self similarity

The above recursive definition allows the monoid of self-symmetries of the curve to be given. This monoid is given by two generators, g and r, which act on the curve (restricted to the unit interval) as

${\displaystyle [g\cdot T_{w}](x)=T_{w}\left({\frac {x}{2}}\right)={\frac {x}{2}}+wT_{w}(x)}$

and

${\displaystyle [r\cdot T_{w}](x)=T_{w}(1-x)=T_{w}(x)}$.

A general element of the monoid then has the form ${\displaystyle \gamma =g^{a_{1}}rg^{a_{2}}r\cdots rg^{a_{n}}}$ for some integers ${\displaystyle a_{1},a_{2},\cdots ,a_{n}}$ This acts on the curve as a linear function: ${\displaystyle \gamma \cdot T_{w}=a+bx+cT_{w}}$ for some constants a, b and c. Because the action is linear, it can be described in terms of a vector space, with the vector space basis:

${\displaystyle 1\mapsto e_{1}={\begin{bmatrix}1\\0\\0\end{bmatrix}}}$
${\displaystyle x\mapsto e_{2}={\begin{bmatrix}0\\1\\0\end{bmatrix}}}$
${\displaystyle T_{w}\mapsto e_{3}={\begin{bmatrix}0\\0\\1\end{bmatrix}}}$

In this representation, the action of g and r are given by

${\displaystyle g={\begin{bmatrix}1&0&0\\0&{\frac {1}{2}}&{\frac {1}{2}}\\0&0&w\end{bmatrix}}}$

and

${\displaystyle r={\begin{bmatrix}1&1&0\\0&-1&0\\0&0&1\end{bmatrix}}}$

That is, the action of a general element ${\displaystyle \gamma }$ maps the blancmange curve on the unit interval [0,1] to a sub-interval ${\displaystyle [m/2^{p},n/2^{p}]}$ for some integers m, n, p. The mapping is given exactly by ${\displaystyle [\gamma \cdot T_{w}](x)=a+bx+cT_{w}(x)}$ where the values of a, b and c can be obtained directly by multiplying out the above matrices. That is:

${\displaystyle \gamma ={\begin{bmatrix}1&{\frac {m}{2^{p}}}&a\\0&{\frac {n-m}{2^{p}}}&b\\0&0&c\end{bmatrix}}}$

Note that ${\displaystyle p=a_{1}+a_{2}+\cdots +a_{n}}$ is immediate.

The monoid generated by g and r is sometimes called the dyadic monoid; it is a sub-monoid of the modular group. When discussing the modular group, the more common notation for g and r is T and S, but that notation conflicts with the symbols used here.

The above three-dimensional representation is just one of many representations it can have; it shows that the blancmange curve is one possible realization of the action. That is, there are representations for any dimension, not just 3; some of these give the de Rham curves.

## Integrating the Blancmange curve

Given that the integral of ${\displaystyle {\rm {blanc}}(x)}$ from 0 to 1 is 1/2, the identity ${\displaystyle {\rm {blanc}}(x)={\rm {blanc}}(2x)/2+s(x)}$ allows the integral over any interval to be computed by the following relation. The computation is recursive with computing time on the order of log of the accuracy required. Defining

${\displaystyle I(x)=\int _{0}^{x}{\rm {blanc}}(x)\,dx}$

one has that

${\displaystyle I(x)={\begin{cases}I(2x)/4+x^{2}/2&{\text{if }}0\leq x\leq 1/2\\1/2-I(1-x)&{\text{if }}1/2\leq x\leq 1\\n/2+I(x-n)&{\text{if }}n\leq x\leq (n+1)\\\end{cases}}}$

The definite integral is given by:

${\displaystyle \int _{a}^{b}{\rm {blanc}}(x)\,dx=I(b)-I(a).}$

A more general expression can be obtained by defining

${\displaystyle S(x)=\int _{0}^{x}s(y)dy={\begin{cases}x^{2}/2&{\mbox{ for }}0\leq x\leq {\frac {1}{2}}\\-x^{2}/2+x-1/4&{\mbox{ for }}{\frac {1}{2}}\leq x\leq 1\\n/4+S(x-n)&{\mbox{ for }}(n\leq x\leq n+1)\end{cases}}}$

which, combined with the series representation, gives

${\displaystyle I_{w}(x)=\int _{0}^{x}T_{w}(x)dx=\sum _{n=0}^{\infty }(w/2)^{n}S(2^{n}x)}$

Note that

${\displaystyle I_{w}(1)={\frac {1}{4(1-w)}}}$

This integral is also self-similar on the unit interval, under an action of the same dyadic monoid as described above. Here, the representation is 4-dimensional, having the basis ${\displaystyle \{1,x,x^{2},I(x)\}}$. Re-writing the above to make the action of g more clear: on the unit interval, one has

${\displaystyle [g\cdot I_{w}](x)=I_{w}\left({\frac {x}{2}}\right)={\frac {x^{2}}{8}}+{\frac {w}{2}}I_{w}(x)}$.

From this, one can then immediately read off the generators of the four-dimensional representation:

${\displaystyle g={\begin{bmatrix}1&0&0&0\\0&{\frac {1}{2}}&0&0\\0&0&{\frac {1}{4}}&{\frac {1}{8}}\\0&0&0&{\frac {w}{2}}\end{bmatrix}}}$

and

${\displaystyle r={\begin{bmatrix}1&1&1&{\frac {1}{4(1-w)}}\\0&-1&-2&0\\0&0&1&0\\0&0&0&-1\end{bmatrix}}}$

Repeated integrals transform under a 5,6,... dimensional representation.

## Relation to simplicial complexes

Let

${\displaystyle N={\binom {n_{t}}{t}}+{\binom {n_{t-1}}{t-1}}+\ldots +{\binom {n_{j}}{j}},\quad n_{t}>n_{t-1}>\ldots >n_{j}\geq j\geq 1.}$

Define the Kruskal–Katona function

${\displaystyle \kappa _{t}(N)={n_{t} \choose t+1}+{n_{t-1} \choose t}+\dots +{n_{j} \choose j+1}.}$

The Kruskal–Katona theorem states that this is the minimum number of (t − 1)-simplexes that are faces of a set of N t-simplexes.

As t and N approach infinity, ${\displaystyle \kappa _{t}(N)-N}$ (suitably normalized) approaches the blancmange curve.