Archive | February 2017

# Cantor Set Construction through Ternary Expansions

Recall the Cantor (middle-third) set $\Lambda$ which is equal to

$\displaystyle{\bigcap_{k=0}^{\infty}{E_k}}$

where $E_0 = [0,1]$ and $E_k$ for $k \geq 1$ is obtained by removing the middle-thirds of each of the disjoint closed intervals making up $E_{k-1}$, i.e. each disjoint closed interval $[a,b]$ making up $E_{k-1}$ gets mapped to $[a, a + 1/3^k] \cup [a+2/3^k, b]$.

For example, to obtain $E_1$, $[0,1]$ gets mapped to $[0,1/3] \cup [2/3,1]$, and this latter set is $E_1$. To obtain $E_2$, $[0,1/3]$ gets mapped to $[0,1/9] \cup [2/9,1/3]$, and $[2/3,1]$ gets mapped to $[2/3, 7/9] \cup [8/9, 1]$, and $E_2$ is the union of these disjoint intervals.

The purpose of this post is to show that in fact

$\displaystyle{S := \left\{ \sum_{k=1}^{\infty}a_{k}3^{-k}:a_{k}\in\left\{ 0,2\right\}\right\} } = \Lambda$

This set $S$ is the collection of all ternary expansions with coefficients $0$ and $2$.

First, it is important to note that the elements of $S$ all coverge to real numbers. This is true because

$\displaystyle{\sum_{k=1}^{\infty}{a_k 3^{-k}} \leq 2 \sum_{k=1}^{\infty}{3^{-k}} <\infty}$

the latter series being geometric.

Next, it will be shown that $\Lambda \subseteq S$. Let $x \in \Lambda$. It is sufficient to construct a sequence $a_k \subseteq \{0,2\}$ corresponding to $x$ such that

$\displaystyle{x = \sum_{k=1}^{\infty}{a_k 3^{-k}}} (*)$

By definition of $\Lambda$, $x \in E_k$ for all $k$. First, $x \in E_0 = [0,1]$. Second, $x \in E_1$. Since $E_1$ is the result of removing the middle-third of $[0,1]$, therefore necessarily $x$ is in the left or right remaining third. If it was the left, define $a_1 = 0$, and otherwise define $a_1 = 2$. Now let $k \geq 1$. Since $x \in E_{k-1}$, therefore it is in one of the disjoint closed intervals $[a,b]$ making up $E_{k-1}$. Since $x \in E_k$ and $[a,b]$ has its left and right thirds mapped into $E_k$, therefore necessarily $x$ is in the left third ($a_k = 0$) or the right third ($a_k = 2$).

Inductively this defines a sequence $a_k \subseteq \{0,2\}$ corresponding to $x$. Define the partial sums

$\displaystyle{S_k = \sum_{i=1}^k{a_i 3^{-i}}}$

To show (*) holds for our choice of $a_k$, it is sufficient to show that $\forall{k}$, $a_k$ and $S_k$ are in one of the disjoint closed intervals $[a,b]$ making up $E_k$ with $a = S_k$. This is sufficient because a property of $\Lambda$ is that the length of the $[a,b]$, excluding $E_0$, is $3^{-k}$ (e.g. by an inductive argument), so $|S_k - x| \leq |a-b| = 3^{-k} \rightarrow 0$ as $k \rightarrow \infty$. This would imply

$\displaystyle{\sum_{k=1}^\infty{a_k 3^{-k}} = \lim S_k = x}$

We proceed by induction. For $k=1$, if $a_1 = 0$, then by definition $x \in [0,1/3]$ and $S_1 = 0$. Otherwise $a_1 = 2$ in which case $x \in [2/3,1]$ and $S_1 = 2/3$. Hence the claim holds for $k=1$.

Now suppose that $x$ and $S_k$ are both in one of the disjoint closed intervals $[a,b]$ making up $E_k$ and $S_k = a$. Then $[a,b]$ is mapped to $[a,a+1/3^{k+1}] \cup [a+2/3^{k+1},b]$ for $E_{k+1}$. If $x$ is in the left interval, then $a_{k+1} = 0$, in which case $S_{k+1} = S_k = a$. Otherwise $x$ is in the right interval in which case $a_{k+1} = 2$, so

$S_{k+1} = S_k + 2/3^{k+1} = a + 2/3^{k+1}$

This completes showing (*) so that indeed $\Lambda \subseteq S$.

To show that $S \subseteq \Lambda$ as well, let $x \in S$. Then

$\displaystyle{\sum_{k=1}^\infty{a_k 3^{-k}} = x}$

and $a_k \in \{0,2\}$. The latter fact and an earlier argument show that the partial sums $S_k$ of $x$ are still a left endpoint of one of the disjoint closed intervals making up $E_k$ for all $k$. Consequently $S_k \in \Lambda$. Since $\Lambda$ is (topologically) closed, it then follows that

$\lim S_k = x$

is in $\Lambda$. This completes the proof.

# Seki Takakazu and the theory of Resultants

Seki Takakazu was a Japanese mathematician during the Edo period, which ran from 1603 to 1868 and “was characterized by economic growth, arts and culture, and isolationism” [1, 2]. Takakazu actually was around the time of both Leibniz and Newton, but their work was independent [1].

Takakazu [1]

Among many things in Takakazu’s mathematical career, he was known for work in Elimination theory: Algorithmic approaches to getting rid of variables between polynomials of several variables [1, 3]. In regards to the Ontario secondary mathematics curriculum, there are some relevant applications of Takakazu’s work to single variable polynomials.

One particular instance is Takakazu’s work on what is known as resultants [1]. Recall (MHF4U, C3.1.1) that a polynomial of degree $n$, a nonnegative integer, is an expression of the form

$p(x)=a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$

where $a_k$ for $0 \leq k \leq n$ is a real number. In particular the above is a polynomial written as a function. For $n=1$ we have a linear function $p(x)=a_1 x + a_0$ and for $n=2$ we have a quadratic function $p(x)=a_2 x^2 + a_1 x + a_0$. Interestingly, the work of resultants requires two polynomials. So let’s introduce another polynomial $q(x)$ of degree $m$:

$q(x)=b_m x^m + b_{m-1} x^{m-1} + \cdots + b_1 x + b_0$

again for real numbers $b_k$. In MHF4U a lot of work is done with polynomials of degree $n \leq 4$, including graphing and factoring in many different ways. As an extension to this, consider the following question:

“With two polynomials $p(x)$ and $q(x)$, how do we know if they share a common factor?”

Recall (MHF4U, C3) that this question is asking if there is $(x-c)$ for some real number $c$ such that $(x-c)$ is a factor of $p(x)$ and $q(x)$. There are a few ways to accomplish this using the tools from MHF4U:

• Completely factor both polynomials and see if any one factor appears in both
• Completely factor only one of the polynomials and use methods to see if these factors are also factors of the other (e.g. polynomial division, substitution)

However both of these methods require work that seems more complicated than what the question is asking. The area of resultants that Takakazu worked on in fact addresses this. Using a formula, the “resultant of $p(x)$ and $q(x)$” is a real number that can be calculated very fast by computers. Continuing, it turns out that the number is zero if and only if $p(x)$ and $q(x)$ have a common factor. That is, the answer to the question is:

“Yes, if and only if the resultant of $p(x)$ and $q(x)$ is $0$.”

But how do we compute this? The command

resultant[$p(x)$, $q(x)$, $x$]

when given to WolframAlpha does exactly this. Let’s do an example. Suppose

$p(x)=x^3-4x^2-7x+10$

and

$q(x)=x^2+3x-4$

Dealing with a degree $3$ polynomial makes it not so easy to answer the question about a common factor. But in telling WolframAlpha the command

resultant[x^3 – 4x^2 – 7x + 10, x^2 + 3x – 4, x]

the answer given back is $0$. Recall that this means that there is indeed a common factor. This is a nice example of using technology in mathematics. Unfortunately, this method does not also tell us what the common factor actualy is, just that one exists.

If you are curious about what WolframAlpha is doing when it makes this computation, then read a little further on. Note though that even though it is related to the vectors content of MCV4U, it requires content typically first covered in a first-year undergraduate course on an area of math called linear algebra.

By definition, the resultant of arbitrary polynomials $p(x)$ and $q(x)$ is the determinant of their Sylvester matrix [4]. This matrix is a $(n+m)\times(n+m)$ matrix (where $n$ and $m$ are the degrees of $p(x)$ and $q(x)$ resp.) where:

• The first row of the matrix is the coefficients of $p(x)$ in decreasing order of subscripts, with $0$ entries on the right for any remaining entries
• The second row is the first row but shifted to the right by one entry, so the first entry is now a $0$ and there is one less $0$ entry on the right
• This rule continues for the following rows until there are no more zeros on the right
• The remaining rows are the same but done with $q(x)$ instead

[5]. For an example, using the $p(x)$ and $q(x)$ from the earlier example, the Sylvester matrix is

$\begin{pmatrix} 1 & -4 & -7 & 10 & 0\\ 0 & 1 & -4 & -7 & 10\\ 1 & 3 & -4 & 0 & 0\\ 0 & 1 & 3 & -4 & 0\\ 0 & 0 & 1 & 3 & -4 \end{pmatrix}$

The resultant of these particular $p(x)$ and $q(x)$ is then the determinant of this matrix. This can also be computed using WolframAlpha with the command

determinant {{1,-4,-7,10,0},{0,1,-4,-7,10},{1,3,-4,0,0},{0,1,3,-4,0},{0,0,1,3,-4}}

The Sylvester matrix is named after James Joseph Sylvester, an English mathematician in the 1800s [6].