The Cantor function¶
Level: 201 → 301 · for anyone who has met a derivative
One line: A continuous function can climb from 0 to 1 while its slope is 0 almost everywhere, because its whole rise happens on the Cantor set, which has length 0 — so "almost everywhere" can miss the one place where everything happens.
A staircase with no steep steps¶
The Cantor set matched every Cantor point with a number in [0, 1] by halving its base-3 digits. Stretch that matching across the gaps, holding it level over each one, and you get a function on all of [0, 1]. This is the Cantor function, better known as the devil's staircase, and it is the classic example of how much can hide inside a set of measure zero. Cantor published it in 1884; it has collected several other names since, including the Lebesgue function (Wikipedia ↗).
Its graph (section 2 below) looks like a staircase: flat treads, connected by risers. Look closer and every riser turns out to be more treads and more risers, forever. There is no interval anywhere on which it simply keeps rising — every stretch contains a flat tread — and still it gets from 0 to 1.
What the program prints¶
Verified output of cantor_function.py — regenerated by tools/run_examples.py, never hand-typed.
1. THE RULE
Read x in base 3. Cut everything after the first 1. Turn 2s into 1s.
Read what is left in base 2.
x base 3 after the rule F(x)
1/4 0.0202020202... 0.0101010101... 1/3
3/4 0.2020202020... 0.1010101010... 2/3
1/5 0.0121012101... 0.01 1/4
1/2 0.1111111111... 0.1 1/2
5/9 0.12 0.1 1/2
200/243 0.21102 0.11 3/4
1/13 0.0020020020... 0.0010010010... 1/7
7/10 0.2002200220... 0.1001100110... 3/5
A number with no 1 is in the Cantor set, and the rule just halves its
digits -- lesson 3's map. A number that cannot be written without a 1
lies in a gap, and cutting at the first 1 gives the whole gap one value.
2. THE STAIRCASE
1 | ##
| #####
| ###
| ###########
| ###
| #####
| ###
| #############################
| ###
| #####
| ###
| ###########
| ###
| #####
| ###
0 |##
+---------------------------------------------------------------------------------
x = 0 x = 1
3. FLAT ON EVERY GAP
Each gap the Cantor set deletes becomes one tread of the staircase:
step gap F on the whole gap
1 (1/3, 2/3) 1/2
2 (1/9, 2/9) 1/4
2 (7/9, 8/9) 3/4
3 (1/27, 2/27) 1/8
3 (7/27, 8/27) 3/8
3 (19/27, 20/27) 5/8
3 (25/27, 26/27) 7/8
Checked at both ends and at 50 points inside every gap.
The gaps have total length 1 (lesson 3), so the slope of F is 0
everywhere except on the Cantor set, a set of length 0. F is flat
ALMOST EVERYWHERE.
4. THE SAME FUNCTION, BUILT FROM RAMPS
Start with the diagonal F_0(x) = x. For F_n, squeeze F_(n-1) into
[0,1/3] and [2/3,1] at half height, and hold 1/2 across the middle.
n largest change from F_(n-1) digit rule agrees on the 3^n grid?
1 1/6 yes
2 1/12 yes
3 1/24 yes
4 1/48 yes
5 1/96 yes
6 1/192 yes
7 1/384 yes
8 1/768 yes
The largest change halves every time, so the ramps close in on one
function at a steady rate (checked on grids 81 times finer: F stays
within (1/3)(1/2)^n of F_n). A limit of continuous functions that
converges like that is continuous. The staircase never jumps.
5. WHERE THE CLIMB HIDES
F_n has 2^n ramps, each rising 1/2^n over a run of 1/3^n: slope (3/2)^n.
In the limit the ramps are gone, and so is any finite slope. The slope
of F just to the left of 1/3, over a run of 1/3^n:
n run rise slope
1 1/3 1/2 1.50
2 1/9 1/4 2.25
3 1/27 1/8 3.38
5 1/243 1/32 7.59
10 1/59049 1/1024 57.67
20 1/3^20 1/2^20 3,325.26
To the right of 1/3 the slope is 0 (it is the start of a gap). To the
left it grows without bound. F has no derivative at 1/3.
So where does the rise of 1 happen? Not on the gaps: they contribute
nothing. The pieces left at step n have total length (2/3)^n, and F
climbs 1/2^n across each of the 2^n of them -- all 1 of the rise,
packed into a length that goes to 0:
step 1: 2 pieces, total length 6.667e-01, total rise 1
step 3: 8 pieces, total length 2.963e-01, total rise 1
step 5: 32 pieces, total length 1.317e-01, total rise 1
step 10: 1,024 pieces, total length 1.734e-02, total rise 1
6. THE GRAPH IS AS LONG AS AN L
Length of the graph of F_n = its flat parts + its 2^n ramps:
n flat parts ramps total
0 0.000000 1.414214 1.414214
1 0.333333 1.201850 1.535184
2 0.555556 1.094318 1.649873
5 0.868313 1.008633 1.876946
10 0.982658 1.000150 1.982809
20 0.999699 1.000000 1.999699
50 1.000000 1.000000 2.000000
Walking right 1 and then up 1 is a path of length 2. The staircase's
graph closes in on exactly that: all of its run on the flat treads,
and all of its rise over a set of length zero.
7. A RANDOM NUMBER WITH NO DENSITY
Build Y by flipping a fair coin for each base-3 digit: heads 2, tails 0.
Y always lands in the Cantor set. Counting all 2^16 ways the first 16
flips can go, exactly:
x P(Y <= x) is between F(x)
1/4 0.333328 and 0.333344 1/3
1/5 0.250000 and 0.250000 1/4
1/2 0.500000 and 0.500000 1/2
7/10 0.599991 and 0.600006 3/5
9/10 0.799988 and 0.800003 4/5
P(Y <= x) is the Cantor function. It has no jumps, so no single value
of Y has positive probability. Yet all of Y's probability sits on the
Cantor set, length 0 -- so no density function could describe Y: it
would give a set of length 0 probability 0.
The rule¶
Four steps give F(x) for any x in [0, 1]:
- Write x in base 3.
- If a 1 appears, cut every digit after the first one.
- Turn every 2 into a 1.
- Read the result in base 2.
1/4 = 0.0202…₃ has no 1, so it simply halves to 0.0101…₂ = 1/3 — exactly lesson 3's map. 1/5 = 0.0121…₃ is cut to 0.01, which read in base 2 is 1/4. Every number in the gap (1/3, 2/3) must be written starting 0.1…₃, gets cut to 0.1, and comes out as 1/2. The cut is what holds each tread level.
The wrinkle from lesson 3 now earns its keep. There, 1/3 = 0.0222…₃ and 2/3 = 0.2₃ both halved to 1/2, which cost the uncountability argument nothing. Here it is essential. Those two numbers are the ends of the gap (1/3, 2/3), and because both land on 1/2, the tread across the gap meets the rest of the staircase at both ends without a jump.
Flat almost everywhere¶
Section 3 takes every gap from the first three steps of the Cantor construction and checks F at both ends and at 50 points inside: it is constant on each. The gap (1/3, 2/3) is the tread at height 1/2, (1/9, 2/9) the tread at 1/4, and so on down.
The gaps have total length 1. So F's slope is 0 everywhere except on the Cantor set, a set of length 0. That is what almost everywhere means: everywhere except on a set of measure zero.
But it never jumps¶
Section 4 builds the same function a second way. Start with the diagonal, F₀(x) = x. To get Fₙ, squeeze Fₙ₋₁ into [0, 1/3] and [2/3, 1] at half its height, and hold it at 1/2 across the middle. Each Fₙ is a continuous chain of ramps and treads.
The largest change from one to the next is 1/6, then 1/12, then 1/24, halving every time. So the Fₙ close in on a single function uniformly, and a uniform limit of continuous functions is continuous. On the grid of multiples of 1/3ⁿ, Fₙ agrees exactly with the digit rule for every n the program tries, so the two constructions really are one function.
So F is continuous and never decreases, with F(0) = 0 and F(1) = 1. Being continuous, it passes through every height in between.
Where the climb hides¶
Every ramp of Fₙ rises 1/2ⁿ over a run of 1/3ⁿ, so its slope is (3/2)ⁿ. As n grows, the ramps get narrower and steeper. In the limit there are no ramps left at all — only treads, and a dust of points where the slope is not a number.
Section 5 measures it just to the left of 1/3. Over a run of 1/3ⁿ, F rises 1/2ⁿ: a slope of (3/2)ⁿ, which is 57.67 at n = 10 and 3,325.26 at n = 20. To the right of 1/3, F is already on the middle tread, with slope 0. So F has no derivative at 1/3.
Now follow the rise of 1. The treads contribute nothing to it. The pieces left at step n have total length (2/3)ⁿ, and F rises by exactly 1/2ⁿ across each of the 2ⁿ of them, so by 1 in total. At step 10 that is 1,024 pieces with a total length of 0.017, carrying the entire climb. Each step shrinks the length and leaves the rise at 1. All of the climb happens on the Cantor set.
Why the fundamental theorem does not rescue it¶
Calculus says F(b) − F(a) is the integral of F′ from a to b. Try it here. F′ = 0 on the gaps, which is almost everywhere, so the integral of F′ comes out as 0 — yet F(1) − F(0) = 1.
Nothing is broken, because the theorem asks for more than F provides:
- The calculus version needs F′ to exist at every point of the interval. F′ does not exist at 1/3 (section 5). Wherever else it fails, it can only fail on the Cantor set, since F′ = 0 on every gap — and the Cantor set is exactly where the climbing happens.
- The Lebesgue version accepts a derivative that exists only almost everywhere, but it needs F to be absolutely continuous: making the total length of a batch of small intervals tend to 0 must make F's total rise across them tend to 0. The Cantor function fails that as badly as a function can. Section 5's pieces have total length tending to 0 and total rise always exactly 1. Vitali pointed out in 1905 that F is not the integral of its derivative (Wikipedia ↗).
So a set of measure zero is negligible for lengths and for integrals, but not for everything. What happens on it can still decide the answer.
The graph is as long as an L¶
Section 6 measures the graph of Fₙ. The treads have total length 1 − (2/3)ⁿ, the 2ⁿ ramps have total length √(1 + (4/9)ⁿ), and the sum grows from √2 ≈ 1.414 at n = 0 to 1.999699 at n = 20.
The Cantor function's own graph has length exactly 2, as Scheeffer showed in 1884 (Wikipedia ↗). Two is the most any never-decreasing function from (0, 0) to (1, 1) can manage, because it is the length of walking right 1 and then up 1. The devil's staircase gets there by doing all of its walking right on the treads, and all of its climbing on a set of length 0.
A random number with no density¶
Section 7 builds a random number Y by flipping a fair coin for each base-3 digit: heads writes a 2, tails a 0. Y always lands in the Cantor set, and the chance that Y ≤ x is F(x). The Cantor function is Y's cumulative distribution function. Counting all 2¹⁶ ways the first 16 flips can go pins P(Y ≤ 1/4) between 0.333328 and 0.333344, either side of F(1/4) = 1/3.
Y fits neither of the two kinds of random number most courses describe:
- It is not discrete. F has no jumps, so every single value of Y has probability 0 — the situation of the next lesson, probability zero.
- It has no density — no curve under which area gives probability. Any density would give the Cantor set probability 0, since the set has length 0, but Y lands there every time.
A distribution like this, with all of its probability on a set of measure zero and none of it on any single point, is called singular. It is the Cantor distribution ↗.
Run it yourself¶
From the root of your clone of this repository:
See also¶
- The Cantor set — the halve-the-digits map this function stretches across the gaps
- The fat Cantor set — the previous lesson: measure zero as the line between integrable and not
- Probability zero — the next lesson: probability zero on the line, and on a machine
- Cantor function ↗ — Wikipedia: the definitions, the history, and its other names
- Cantor distribution ↗ — Wikipedia: the random number of section 7