Archive for May, 2011

Boundary operators

May 12, 2011 8 comments

Consider the vector space of polynomials with coefficients on a field \mathbb{F}, \mathbb{F}[X], with the obvious sum of functions and scalar multiplication. For each n \in \mathbb{N}, consider the subspaces \Pi_n spanned by polynomials of order n,

\Pi_n = \{ a_0 + a_1 x + \dotsb + a_n x^n : (a_0, a_1, \dotsc, a_n) \in \mathbb{F}^{n+1} \}.

These subspaces have dimension n+1. Consider now for each n \in \mathbb{N} the maps \partial_n \colon \Pi_n \to \Pi_{n-1} defined in the following way:

\partial_n \big( a_0 + a_1 x + \dotsb + a_n x^n \big) = \displaystyle{\sum_{k=0}^{n} (-1)^k \sum_{j\neq k} a_j x^{\varphi(j,k)},}

where \varphi(j,k) = j if j < k, and \varphi(j,k) = j-1 otherwise.

Schematically, this can be written as follows

\begin{pmatrix} a_0 \\ a_1 \\ \vdots \\ a_n \end{pmatrix} \xrightarrow{\partial_n} \begin{pmatrix} a_1 \\ a_2 \\ \vdots \\ a_n \end{pmatrix} - \begin{pmatrix} a_0 \\ a_2 \\ \vdots \\ a_n \end{pmatrix} + \dotsb + (-1)^k \begin{pmatrix} \vdots \\ a_{k-1} \\ a_{k+1} \\ \vdots \end{pmatrix} + \dotsb + (-1)^n \begin{pmatrix} a_0 \\ a_1 \\ \vdots \\ a_{n-1} \end{pmatrix},

and it is not hard to prove that these maps are homeomorphisms of vector spaces over \mathbb{F}.

Notice this interesting relationship between \partial_3 and \partial_2:

\begin{array}{rl} \partial_2(a_0 + a_1 x + a_2 x^2) &= (a_1 + a_2 x) - (a_0 + a_2 x) + (a_0 +a_1 x) \\ &= a_1 + a_1 x \\ \partial_3( a_0 + a_1 x + a_2 x^2 + a_3 x^3) &= ( a_1 + a_2 x + a_3 x^2 ) - ( a_0 + a_2 x + a_3 x^2) \\ &\mbox{} \quad + (a_0 + a_1 x + a_3 x^2) - (a_0 +a_1 x +a_2 x^2) \\ &= (a_1-a_0) + (a_3-a_2)x^2 \end{array}

The kernel of \partial_2 and the image of \partial_3 are isomorphic!

\begin{array}{rl} \ker \partial_2 &= \{ a_0 + a_2 x^2 : (a_0,a_2) \in \mathbb{F}^2 \}. \\ \partial_3\big( \Pi_3 \big) &= \{ b_0 + b_2 x^2 : (b_0, b_2) \in \mathbb{F}^2 \}. \end{array}

The reader will surely have no trouble to show that this property is satisfied at all levels: \ker \partial_n = \partial_{n+1} \big( \Pi_{n+1} \big). As a consequence, \partial_n \partial_{n+1} = 0 for all n \in \mathbb{N}.

We say that a family of homomorphisms \{ \partial_n \colon \Pi_n \to \Pi_{n+1} \} are boundary operators if \partial_n \partial_{n+1} = 0 for all n \in \mathbb{N}. If this is the case, then trivially \partial_{n+1} \big( \Pi_{n+1} \big) \subseteq \ker \partial_n. The example above is a bit stronger, because of the isomorphism of both subspaces.

So this is the question I pose as today’s challenge:

Describe all boundary operators \big\{ \partial_n\colon \Pi_n \to \Pi_{n-1} \big\} \big( \partial_n\partial_{n+1} = 0 \big)

Include a precise relationship between kernels and images of consecutive maps.

The Cantor Pairing Function

May 8, 2011 8 comments

The objective of this post is to construct a pairing function, that presents us with a bijection between the set of natural numbers, and the lattice of points in the plane with non-negative integer coordinates.

\pi\colon \mathbb{N} \cup \{ 0 \} \to \big( \mathbb{N} \cup \{ 0 \} \big)^2.

We will accomplish this by creating the corresponding map (and its inverse), that takes each natural number z and drops it at a location in the lattice, as the following diagram suggests:


Read more…

%d bloggers like this: