阅读视图

发现新文章,点击刷新页面。
🔲 ☆

continuation 教程: 理解 CPS

这是一个 continuation 系列教程:

  1. continuation 教程:理解 CPS
  2. continuation 教程:用 yield 实现协程调度
  3. continuation 教程:用 call/cc 实现协程调度
  4. continuation 教程:用 shift/reset 实现协程调度
  5. continuation 教程:体验 Racket 语言
  6. continuation 教程:实现抢占式协程调度

我们来由浅入深地系统学习下 continuation 的原理以及应用场景。这个系列教程的内容和王垠的 continuation 专项班无关,是我自己学习和研究的成果,所以不会有版权问题。不过当然正是因为我学习了基础班,打下了坚实的基础,才知道该如何去自学和理解 continuation 这个概念。这篇文章会少量透露出基础班学到的技能,毕竟 continuation 属于基础班的进阶内容,无法跳过基础技能去理解。

递归

首先用递归的形式写一个阶乘函数 fact,我们已经很熟悉它的写法,不需要过多解释:

function fact(n){  if (n === 0)   {    return 1;  }  else  {    return n * fact(n - 1);  }}console.log("fact1=", fact(1)); // 1console.log("fact3=", fact(3)); // 6console.log("fact5=", fact(5)); // 120

尾递归

接着把 fact 函数改为尾递归的形式。尾递归会比递归多一个参数,新参数用来保存每个调用计算后的值:

function factTail(n, prod){  if (n == 0)  {    return prod;  }  else  {    return factTail(n-1, prod*n);  }}console.log("factTail1=", factTail(1, 1)); // 1console.log("factTail3=", factTail(3, 1)); // 6console.log("factTail5=", factTail(5, 1)); // 120

CPS 形式

我们基于 fact 函数的尾递归形式,再新增一个参数 k,这个 k 是一个函数,fact 不直接返回计算后的值,而是结果值对 k 函数的调用,像这样:

function factTailCPS(n, prod, k){  if (n == 0)  {    return k(prod);  }  else  {    return factTailCPS(n-1, prod*n, k);  }}factTailCPS( 1, 1, x => console.log("factTailCPS1=", x) ); // 1factTailCPS( 3, 1, x => console.log("factTailCPS3=", x) ); // 6factTailCPS( 5, 1, x => console.log("factTailCPS5=", x) ); // 120

这个 k 就是 continuation,意味着告诉 fact 函数,你执行完了计算出结果之后,应该如何进行下一步延续。不用怀疑,这个函数完全符合 CPS(Continuation-Passing-Style)的形式。

典型 CPS

但是用尾递归结合 continuation 参数的形式,显然不够简洁,并不算典型的 CPS 形式。典型的 CPS 形式比较难理解,所以不需要自己思考出来,直接看这个现成的例子,我们对递归形式的 fact 函数改进一下:

function factCPS(n, k){  if (n == 0)  {    return k(1);  }  else  {    return factCPS(n-1, r => k(n * r));  }}

可能看着有点懵,不要慌,我们拆解一下其中的内容。首先 k 仍然代表 continuation,并且 k 是一个函数。然后我们这样来调用:

let factCPS1 = factCPS(0, x => x);console.log("factCPS1=", factCPS1); // 1let factCPS3 = factCPS(3, x => x);console.log("factCPS3=", factCPS3); // 6let factCPS5 = factCPS(5, x => x);console.log("factCPS5=", factCPS5); // 120

关键在于调用的时候,传入函数的第二个参数是 x => x,如果结合函数内部的 r => k(n * r),也许一下子就糊涂了。

这确实是最难理解的部分。我们以计算 2 的阶乘为例,写一个拆解 factCPS 函数调用步骤的过程。这里用到的技巧是在基础班第一课就学过的 单步替换,对于理解递归非常有帮助。如果在基础班经过训练并且打好基础,确实会有助于理解更复杂的东西,比如这里的 CPS 调用:

let factCPS2 = factCPS(2, x => x);console.log("factCPS2=", factCPS2); // 2// n=2, k=x=>x, return factCPS(1, r => k(2 * r));  // n=1, k=r=>(x=>x)(2*r), return factCPS(0, r => k(1 * r));    // n=0, k=r=>(r=>(x=>x)(2*r)(1*r)), return k(1);      // k(1) = r=>(x=>x)(2*r)(1*1)      //      = (x=>x)(2)      //      = 2

虽然我已经按照正确的思路拆解出了正确的步骤,但是从阅读者的角度,这仍然会非常难理解,可以自己拆解一下试试,逐步理解典型 CPS 的调用过程。理解这些步骤也许需要几个小时的时间,这是正常的。

总结来说,CPS 的每一次调用,都是在用闭包来储存当前步骤计算的值。尾递归是直接用参数传递值,而 CPS 是在用闭包传递给下个步骤值,就是这样的关系。当然理解这一点的前提是,知道闭包是什么,这个也是基础班学习的重点内容,尤其是会在实现解释器环节,自己实现闭包的语句,对于闭包的理解会很透彻。

fib 函数的 CPS

计算阶乘的函数 fact 特点是只在函数体内进行一次递归调用,我们再来看计算斐波那契数列的 fib 函数,它会在函数体内进行两次递归调用,CPS 该怎么处理这个情况。

fib 函数的递归形式的定义是这样:

function fib(n){  if (n == 0)  {    return 0;  }  else if (n == 1)  {    return 1;  }  else   {    return fib(n-1) + fib(n-2);  }}console.log("fib(2)=", fib(2)); // 1console.log("fib(5)=", fib(5)); // 5

这里直接给出 fib 函数的 CPS,然后理解一下 fib 函数的运作过程:

function fibCPS(n, k){  if (n == 0)  {    return k(0);  }  else if (n == 1)  {    return k(1);  }  else  {    return fibCPS(n-1, r1 => fibCPS(n-2, r2=>k(r1+r2)) );  }}

可以看到,对于需要两次递归调用的情况,CPS 是把另一次递归调用,写在了原本的 r => k(r) 函数里,让第二次内部调用成为了递归调用 fib 时候的子调用。这句话有点绕,可以结合代码理解一下。

CPS 形式的 fib 函数这样来调用:

let fibCPS1 = fibCPS(1, x=>x);console.log("fibCPS1=", fibCPS1); // 1let fibCPS2 = fibCPS(2, x=>x);console.log("fibCPS2=", fibCPS2); // 1let fibCPS4 = fibCPS(4, x=>x);console.log("fibCPS4=", fibCPS4); // 3let fibCPS5 = fibCPS(5, x=>x);console.log("fibCPS5=", fibCPS5); // 5

我们以计算 3 的斐波那契数为例,拆解一下具体的执行步骤。要注意的是,这个过程非常复杂,比 fact 函数还要复杂很多,只有自己亲自写一下才能搞清楚:

let fibCPS3 = fibCPS(3, x=>x);console.log("fibCPS3=", fibCPS3); // 1+1=2// n=3, k=x=>x,        // return fibCPS(2, r1 => fibCPS(1, r2=>(x=>x)(r1+r2)) );// n=2, k= r1 => fibCPS(1, r2=>(x=>x)(r1+r2)),        // return fibCPS(1, r1 => fibCPS(0, r2 => ( r1 => fibCPS(1, r2=>(x=>x)(r1+r2)) )(r1+r2)) );// n=1, k= r1 => fibCPS(0, r2 => ( r1 => fibCPS(1, r2=>(x=>x)(r1+r2)) )(r1+r2)),        // return k(1)       // return ( r1 => fibCPS(0, r2 => ( r1 => fibCPS(1, r2=>(x=>x)(r1+r2)) )(r1+r2)) )(1)       // return fibCPS(0, r2 => ( r1 => fibCPS(1, r2=>(x=>x)(r1+r2)) )(1+r2))          // n=0, k= r2 => ( r1 => fibCPS(1, r2=>(x=>x)(r1+r2)) )(1+r2)              // return k(0)              // return ( r2 => ( r1 => fibCPS(1, r2=>(x=>x)(r1+r2)) )(1+r2) )(0)              // return ( r1 => fibCPS(1, r2=>(x=>x)(r1+r2)) ) (1+0)              // return fibCPS(1, r2=>(x=>x)(1+r2))                  // n=1, k = r2=>(x=>x)(1+r2)                  // return k(1)                  // return (x=>x)(1+1)                  // return 2

那么经过了 factfib 函数的训练,我们就已经知道 CPS 的形式是什么,以及具体的执行步骤是怎样了。理解 CPS 只是开始,接下来还会利用 continuation 实现更多有趣的程序。

练习题

已知一个递归形式的 sumFrom 函数,接收两个参数 ab,函数的功能是计算 a+(a+1)+...+(b-1)+b 的值,例如参数是 14,则计算 1+2+3+4 的结果:

function sumFrom(a, b){  if (a == b)   {    return a;  }  else  {    return b + sumFrom(a, b-1);  }}console.log(sumFrom(1, 3));   // 6console.log(sumFrom(2, 5));   // 14

练习的内容是,将 sumFrom 函数修改为 CPS 形式,补充 sumFromCPS 函数空白处的代码,让程序可以满足测试用例中的输出结果:

function sumFromCPS(a, b, k){  // ____}sumFromCPS(1, 3, x => console.log("sumFromCPS(1, 3)=", x));   // 6sumFromCPS(2, 5, x => console.log("sumFromCPS(2, 5)=", x));   // 14

延伸阅读

我们已经体验了手动将递归程序转变为 CPS 形式的过程,实际上存在能将代码自动转变为 CPS 形式的方法,也就是传说中 “王垠 40 行代码” 在干的事情。可以参考这两个链接查看更多内容:

因为 “自动 CPS 变换” 的难度比较大,我自己并不打算深入学习和实现。

🔲 ☆

Picard's Little Theorem and Twice-Punctured Plane

Introduction

Let $f:\mathbb{C} \to \mathbb{C}$ be a holomorphic function. By Liouville’s theorem, if $f(\mathbb{C})$ is bounded, then $f$ has to be a constant function. However, there is a much stronger result. In fact, if $f(\mathbb{C})$ differs $\mathbb{C}$ from exactly $2$ points, then $f$ is a constant. In other words, suppose $f$ is non-constant, then the equation $f(z)=a$ for all $a \in \mathbb{C}$ except at most one $a$. To think about this, if $f$ is a non-constant polynomial, then $f(z)=a$ always has a solution (the fundamental theorem of algebra). If, for example, $f(z)=\exp(z)$, then $f(z)=a$ has no solution only if $a=0$.

The proof will not be easy. It will not be proved within few lines of obvious observations, either in elementary approaches or advanced approaches. In this post we will follow the later by studying the twice-punctured plane $\mathbb{C} \setminus\{0,1\}$. To be specific, without loss of generality, we can assume that $0$ and $1$ are not in the range of $f$. Then $f(\mathbb{C}) \subset \mathbb{C}\setminus\{0,1\}$. Next we use advanced tools to study $\mathbb{C}\setminus\{0,1\}$ in order to reduce the question to Liouville’s theorem by constructing a bounded holomorphic function related to $f$.

We will find a holomorphic covering map $\lambda:\mathfrak{H} \to \mathbb{C}\setminus\{0,1\}$ and then replace $\mathfrak{H}$ with the unit disc $D$ using the Cayley transform $z \mapsto \frac{z-i}{z+i}$. Then the aforementioned $f$ will be lifted to a holomorphic function $F:\mathbb{C} \to D$, which has to be constant due to Liouville’s theorem, and as a result $f$ is constant.

With these being said, we need analytic continuation theory to establish the desired $\lambda$, and on top of that, (algebraic) topology will be needed to justify the function $F$.

Analytic Continuation

For a concrete example of analytic continuation, I recommend this post on the Riemann $\zeta$ function. In this post however, we only focus on the basic language of it in order that we can explain later content using analytic continuation.

Our continuation is always established “piece by piece”, which is the reason we formulate continuation in the following sense.

Definition 1. A function element is an ordered pair $(f,D)$ where $D$ is an open disc and $f \in H(D)$. Two function elements $(f_1,D_1)$ and $(f_2,D_2)$ are direct continuation of each other if $D_1 \cap D_2 \ne \varnothing$ and $f_1=f_2$ on $D$. In this case we write

The notion of ordered pair may ring a bell of sheaf and stalk. Indeed some authors do formulate analytic continuation in this language, see for example Principles of Complex Analysis by Serge Lvovski.

The $\sim$ relation is by definition reflective and symmetric, but not transitive. To see this, let $\omega$ be the primitive $3$-th root of unity. Let $D_0, D_1,D_2$ be open discs with radius $1$ and centres $\omega^0,\omega^1,\omega^2$. Since the $D_i$ are simply connected, we can always pick $f_i \in H(D_i)$ such that $f_i^2(z)=z$, and $(f_0,D_0) \sim (f_1,D_1)$ and $(f_1,D_1) \sim (f_2,D_2)$ but on $D_0 \cap D_2$ one has $f_2 =-f_0 \ne f_0$. Indeed there is nothing mysterious: we are actually rephrasing the fact that square root function cannot be defined at a region containing $0$.

Definition 2. A chain is a finite sequence $\mathscr{C}$ of discs $(D_0,D_1,\dots,D_n)$ such that $D_{i-1} \cap D_i \ne \varnothing$ for $i=1,\dots,n$. If $(f_0,D_0)$ is given and if there exists function elements $(f_i,D_i)$ such that $(f_{i-1},D_{i-1}) \sim (f_i,D_i)$ for $i=1,\dots,n$, then $(f_n,D_n)$ is said to be the analytic continuation of $(f_0,D_0)$ along $\mathscr{C}$.

A chain $\mathscr{C}=(D_0,\dots,D_n)$ is said to cover a curve $\gamma$ with parameter interval $[0,1]$ if there are numbers $0=s_0<s_1<\dots<s_n=1$ such that $\gamma(0)$ is the centre of $D_0$, $\gamma(1)$ is the centre of $D_n$, and

If $(f_0,D_0)$ can be continued along this $\mathscr{C}$ to $(f_n,D_n)$, we call $(f_n,D_n)$ an analytic continuation of $(f_0,D_0)$ along $\gamma$; $(f_0,D_0)$ is then said to admit an analytic continuation along $\gamma$.

Either way, it is not necessary that $(f_0,D_0) \sim (f_n,D_n)$. However, unicity of $(f_n,D_n)$ is always guaranteed. We will sketch out the proof on unicity.

Lemma 1. Suppose that $D_0 \cap D_1 \cap D_2 \ne \varnothing$, $(D_0,f_0) \sim (D_1,f_1)$ and $(D_1,f_1) \sim (D_2,f_2)$, then $(D_0,f_0) \sim (D_2,f_2)$.

Proof. By assumption, $f_0=f_1$ in $D_0 \cap D_1$, and $f_1=f_2$ in $D_1 \cap D_2$. It follows that $f_0=f_2$ in $D_0 \cap D_1 \cap D_2$, which is open and non-empty. Since $f_0$ and $f_2$ are holomorphic in $D_0 \cap D_2$ and $D_0 \cap D_2$ is connected, we have $f_0 = f_2$ in $D_0 \cap D_2$. This is because on a open connected set $D_0 \cap D_2$, the zero of $f_0-f_2$ is not discrete. Therefore $f_0-f_2$ has to be $0$ everywhere on $D_0 \cap D_2$. $\square$

Theorem 1. If $(f,D)$ is a function element and $\gamma$ is a curve which starts at the centre of $D$, then $(f,D)$ admits at most one analytic continuation along $\gamma$.

Sketch of the proof. Let $\mathscr{C}_1=(A_0,A_1,\dots,A_m)$ and $\mathscr{C}_2=(B_0,B_1,\dots,B_n)$ be two chains that cover $\gamma$. If $(f,D)$ can be analytically continued along $\mathscr{C}_1$ to a function element $(g_m,A_m)$ and along $\mathscr{C}_2$ to $(h_n,B_n)$, then $g_m=h_n$ in $A_m \cap B_n$.

We are also given partitions $0=s_0<s_1<\dots<s_m=s_{m+1}=1$ and $0=t_0<t_1<\dots<t_n=t_{n+1}=1$ such that

and function elements $(g_i,A_i) \sim (g_{i+1},A_{i+1})$ and $(h_j,B_j) \sim (h_{j+1},B_{j+1})$ for $0 \le i \le m-1$ and $0 \le j \le n-1$ with $g_0=h_0=f$. The poof is established by showing that the continuation is compatible with intersecting intervals, where lemma 1 will be used naturally. To be specific, if $0 \le i \le m$ and $0 \le j \le n$, and if $[s_i,s_{i+1}] \cap [t_j,t_{j+1}] \ne \varnothing$, then $(g_i, A_i) \sim (h_j,B_j)$.

The Monodromy Theorem

The monodromy theorem asserts that on a simply connected region $\Omega$, for a function element $(f,D)$ with $D \subset \Omega$, we can extend it to all $\Omega$ if $(f,D)$ can be continued along all curves. To prove this we need homotopy properties of analytic continuation and simply connected spaces.

Definition 1. A simply connected space is a path connected topological space $X$ with trivial fundamental group $\pi_1(X,x_0)=\{e\}$ for all $x_0 \in X$.

The following fact is intuitive and will be used in the monodromy theorem.

Lemma 2. Let $X$ be a simply connected space and let $\gamma_1$ and $\gamma_2$ be two closed curves $[0,1] \to X$ with $\gamma_1(0)=\gamma_2(0)$ and $\gamma_1(1)=\gamma_2(1)$. Then $\gamma_1$ and $\gamma_2$ are homotopic.

Proof. Let $\gamma_i^{-1}$ be the curve defined by $\gamma_i^{-1}(t)=\gamma_i(1-t)$ for $i=1,2$. Then

where $e$ is the identity of $\pi_1(X,\gamma_1(0))$. $\square$

Next we prove the two-point version of the monodromy theorem.

Monodromy theorem (two-point version). Let $\alpha,\beta$ be two points on $\mathbb{C}$ and $(f,D)$ be a function element where $D$ is centred at $\alpha$. Let $\{\gamma_t\}$ be a homotopy class indexed by a map $H(s,t):[0,1] \times [0,1] \to \mathbb{C}$ with the same origin $\alpha$ and terminal $\beta$. If $(f,D)$ admits analytic continuation along each $\gamma_t$, to an element $(g_t,D_t)$, then $g_1=g_0$.

In brief, analytic continuation is faithful along homotopy classes. By being indexed by $H(s,t)$ we mean that $\gamma_t(s)=H(s,t)$. We need the uniform continuity of $H(s,t)$.

Proof. Fix $t \in [0,1]$. By definition, there is a chain $\mathscr{C}=(A_0,\dots,A_n)$ which covers $\gamma_t$, with $A_0=D$, such that $(g_t,D_t)$ is obtained by continuation of $(f,D)$ along $\mathscr{C}$. There are numbers $0=s_0<\dots<s_n=1$ such that

For each $i$, define

The $d_i$ makes sense and is always positive, because $E_i$ is always compact and $A_i$ is an open set. Then pick any $\varepsilon \in (0,\min_i\{d_i\})$. Since $H(s,t)$ is uniformly continuous, there exists a $\delta>0$ such that

We claim that $\mathscr{C}$ also covers $\gamma_u$. To do this, pick any $s \in [s_i,s_{i+1}]$. Then $\gamma_u(s) \in A_i$ because

Therefore by theorem 1, we have $g_t=g_u$. Notice that for any $t \in [0,1]$, there is a segment $I_t$ such that $g_u=g_t$ for all $u \in [0,1] \cap I_t$. Since $[0,1]$ is compact, there are finitely many $I_t$ that cover $[0,1]$. Since $[0,1]$ is connected, we see, after a finite number of steps, we can reach $g_0=g_1$. $\square$

Momodromy theorem. Suppose $\Omega$ is a simply connected open subset of the plane, $(f,D)$ is a function element with $D \subset \Omega$, and $(f,D)$ can be analytically continued along every curve in $\Omega$ that starts at the centre of $D$. Then there exists $g \in H(\Omega)$ such that $g(z)=f(z)$ for all $z \in D$.

Proof. Let $\gamma_0$ and $\gamma_1$ be two curves in $\Omega$ from the centre $\alpha$ of $D$ to some point $\beta \in \Omega$. Then the two-point monodromy theorem and lemma 2 ensures us that these two curves lead to the same element $(g_\beta,D_\beta)$, where $D_\beta \subset \Omega$ is a circle with centre at $\beta$. If $D_{\beta_1}$ intersects $D_\beta$, then $(g_{\beta_1},D_{\beta_1})$ can be obtained by continuing $(f,D)$ to $\beta$, then along the segment connecting $\beta$ and $\beta_1$. By definition of analytic continuation, $g_{\beta_1}=g_\beta$ in $D_{\beta_1} \cap D_\beta$. Therefore the definition

is a consistent definition and gives the desired holomorphic extension of $f$. $\square$

Modular Function

Let $\mathfrak{H}$ be the open upper half plane. We will find a function $\lambda \in H(\mathfrak{H})$ whose image is $E=\mathbb{C} \setminus\{0,1\}$ and is in fact the (holomorphic) covering space of $E$. The function $\lambda$ is called a modular function.

As usual, consider the action of $G=SL(2,\mathbb{Z})$ on $\mathfrak{H}$ given by

Definition 2. A Modular function is a holomorphic (or meromorphic) function $f$ on $\mathfrak{H}$ which is invariant under a non-trivial subgroup $\Gamma$ of $G$. That is, for any $\varphi \in \Gamma$, one has $f \circ \varphi=f$.

In this section, we consider this subgroup:

It has a fundamental domain

Basically, $Q$ is bounded by two vertical lines $x=1$ and $x=-1$ vertically, and two semicircles with centre at $x=\frac{1}{2}$ and $x=-\frac{1}{2}$ with diameter $1$, but only the left part contains boundary points. The term fundamental domain will be justified by the following theorem.

Theorem 4. Let $\Gamma$ and $Q$ be as above.

(a) Let $\varphi_1,\varphi_2$ be two distinct elements of $\Gamma$, then $\varphi_1(Q) \cap \varphi_2(Q) = \varnothing$.

(b) $\bigcup_{\varphi \in \Gamma}\varphi(Q)=\mathfrak{H}$.

(c) $\Gamma$ is generated by two elements

Sketch of the proof. Let $\Gamma_1$ be the subgroup of $\Gamma$ generated by $\sigma$ and $\tau$, and show (b’):

Then (a) and (b’) would imply that $\Gamma_1=\Gamma$ and (b) is proved. To prove (a), one will replace $\varphi_1$ with the identity element and discuss the relationship between $c$ and $d$ for $\varphi_2=\begin{pmatrix}a & b \\ c & d \end{pmatrix}$. To prove (b’), one need to notice that

For $w \in \mathfrak{H}$, by picking $\varphi_0 \in \Gamma$ that maximises $\Im\varphi_0(w)$, only to show that $z=\varphi_0(w) \in \Sigma$ and therefore $w \in \Sigma$.


We are now allowed to introduce the modular function.

Theorem 5. Notation being above, there exists a function $\lambda \in H(\mathfrak{H})$ such that

(a) $\lambda \circ \varphi = \lambda$ for every $\varphi \in \Gamma$.

(b) $\lambda$ is one-to-one on $Q$.

(c) $\lambda(\mathfrak{H})=\lambda(Q)=E=\mathbb{C}\setminus\{0,1\}$.

(d) $\lambda$ has the real axis as its natural boundary. That is, $\lambda$ has no holomorphic extension to any region that properly contains $\mathfrak{H}$.

Proof. Consider

This is a simply connected region with simple boundary. There is a continuous function $h$ which is one-to-one on $\overline{Q}_0$ and is holomorphic in $Q_0$ such that $h(Q_0)=\mathfrak{H}$, $h(0)=0$, $h(1)=1$ and $h(\infty)=\infty$. This is a consequence of conformal mapping theory.

The Schwartz reflection principle extends $h$ to a continuous function on $\overline{Q}$ which is a conformal mapping of $Q^\circ$ (the interior of $Q$) onto the plane minus the non-negative real axis, by the formula

Note the extended $h$ is one-to-one on $Q$, and $h(Q)$ is $E$ defined in (c).

On the boundary of $Q$, the function $h$ is real. In particular,

and that

We now define

for $\varphi \in \Gamma$ and $z \in \varphi(Q)$. This definition makes sense because for each $z \in \mathfrak{H}$, there is one and only one $\varphi \in \Gamma$ such that $z \in \varphi(Q)$. Properties (a) (b) and (c) follows immediately.

Notice $\lambda$ is continuous on

and therefore on an open set $V$ containing $Q$. Cauchy’s theorem shows that $\lambda$ is holomorphic in $V$. Since $\mathfrak{H}$ is covered by the union of the sets $\varphi(V)$ for $\varphi \in \Gamma$, and since $\lambda \circ \varphi = \lambda$, we conclude that $\lambda \in H(\mathfrak{H})$.

Finally, the set of all numbers $\varphi(0)=b/d$ is dense on the real axis. If $\lambda$ could be analytically continued to a region which properly contains $\mathfrak{H}$, the zeros of $\lambda$ would have a limit point in this region, which is impossible since $\lambda$ is not constant. $\square$

We are now ready for the pièce de résistance of this post.

Picard’s Little Theorem

Theorem (Picard). If $f$ is an entire function and if there are two distinct complex numbers $\alpha$ and $\beta$ such that are not in the range of $f$, then $f$ is constant.

The proof is established by considering an analytic continuation of a function $g$ associated with $f$. The continuation will be originated at the origin and validated by monodromy theorem. Then by Cayley’s transformation, we find out the range of $g$ is bounded and hence $g$ is constant, so is $f$.

Proof. First of all notice that without loss of generality, we assume that $\alpha=0$ and $\beta=1$, because otherwise we can replace $f$ with $(f-\alpha)/(\beta-\alpha)$. That said, the range of $f$ is $E$ in theorem 5. There is a disc $A_0$ with centre at $0$ so that $f(A_0)$ lies in a disc $D_0 \subset E$.

For every disc $D \subset E$, there is an associated region $V \subset \mathfrak{H}$ such that $\lambda$ in theorem 5 is one-to-one on $V$ and $\lambda(V)=D$; each such $V$ intersects at most two of the domains $\varphi(Q)$. Corresponding to each choice of $V$, there is a function $\psi \in H(D)$ such that $\psi(\lambda(z))=z$ for all $z \in V$.

Now let $\psi_0 \in H(D_0)$ be the function such that $\psi_0(\lambda(z))=z$ as above. Define $g(z)=\psi_0(f(z))$ for $z \in A_0$. We claim that $g(z)$ can be analytically continued to an entire function.

If $D_1$ is another disc in $E$ with $D_0 \cap D_1 \ne \varnothing$, we can choose a corresponding $V_1$ so that $V_0 \cap V_1 \ne \varnothing$. Then $(\psi_0,D_0)$ and $(\psi_1,D_1)$ are direct analytic continuations of each other. We can proceed this procedure all along to find a direct analytic continuation $(\psi_{i+1},D_{i+1})$ of $(\psi_i,D_i)$ with $V_{i+1} \cap V_i \ne 0$. Note $\psi_i(D_i) \subset V_i \subset \mathfrak{H}$ for all $i$.

Let $\gamma$ be a curve in the plane which starts at $0$. The range of $f \circ \gamma$ is a compact subset of $E$ and therefore $\gamma$ can be covered by a chain of discs, say $A_0,\dots,A_n$, so that each $f(A_i)$ is in a disc $D_i \subset E$. By considering function elements $\{(\psi_{i},D_i)\}$, composing with $f$ on each $D_i$ (this is safe because $f$ is entire), we get an analytic continuation of $(g,A_0)$ along the chain $(A_0,\dots,A_n)$. Note $\psi_i \circ f(A_i) \subset \psi_i(D_i) \subset \mathfrak{H}$ again.

Since $\gamma$ is arbitrary, we have shown that $(g,A_0)$ can be analytically continued along every curve in the plane. The monodromy theorem implies that $g$ extends to an entire function. Thus proving our claim given before.

Note the range of the extended $g$ on every possible $A_i$ has range lying inside $\mathfrak{H}$. Therefore $g(\mathbb{C}) \subset \mathfrak{H}$. It follows that

has range in the unit disc. By Liouville’s theorem, $h$ is a constant function. Thus $g$ is constant too.

Now we move back to $f$ by looking at $A_0$. Since $\psi_0$ is one-to-one on $f(A_0)$ and $A_0$ is not empty and open, $f(A_0)$ has to be a singleton. Thus $f$ is constant on $A_0$. If we represent $f$ as a power series on a disc lying inside $A_0$, we see $f$ has to be a constant. $\square$

Note we have also seen that the range of a non-constant function cannot be half of a plane. But this result is useless because we can find two points on a large chunk of a plane after all.

Reference

  • Walter Rudin, Real and Complex Analysis.
  • Tammo tom Dieck, Algebraic Topology.
❌