Bedtime mathematics

A problem

December 30, 2009 mymbl Leave a comment

Let A and B be connected subsets of [0,1]² where π(A) = [0,1] = π(B) where π is the projection map π(x,y) = x. We construct a new set C out of A and B as follows.
Let C = {(x,y,z) | (x,y) ∈ A and (x,z) ∈ B}.

Is C connected always? If not then are there counterexamples?
Read below to see an answer.
Read more…

Categories: Uncategorized Tags: gt.geometric-topology

We know that set of commutators of ${n\times n}$ matrices is exactly the space of matrices of trace zero and has dimension ${n^2-1}$ . I discuss an interesting question related to this which was brought to my notice by Anamika:

Given a matrix ${C}$ of trace zero can we construct two matrices ${A}$ and ${B}$ of determinant ${1}$ , such that ${AB - BA = C}$ . Here is a proposed way of finding matrices ${A}$ and ${B}$ such that ${AB - BA = C}$ .

It turns out that this problem has a variety of applications and it goes by the name Sylvester equation (after fixing one matrix say A). For example, it is used in Computer Vision to estimate the pose(position, orientation ) of an object based on a series of images. See video here

We first try a simple case: Suppose ${D}$ is matrix with non-zero entries only in the diagonal and at locations ${i,(i+1)}$ for ${i=1,2,\ldots, n-1}$ (like in the Jordan Normal form) with ${[D]_{i\overline{i+1}} = 1}$ or ${0}$ . We want to find a matrix ${X}$ such that ${DX - XD = C}$ where ${C}$ is a ${n\times n}$ matrix with trace zero. We equate the ${i,j}$ entries on both sides to get,

$\displaystyle [C]_{ij} = \sum_{k=1}^n ( [D]_{ik} [X]_{kj} - [X]_{ik} [D]_{kj})$

expanding we get

$\displaystyle [C]_{ij} = [D]_{ii} [X]_{ij} - [X]_{ij} [D]_{jj} + [D]_{i \overline{i+1}}[X]_{\overline{i+1}j} - [X]_{i\overline{j-1}}[D]_{\overline{j-1}j}$

Now if ${\text{vec}(X)}$ denotes the operator that flattens the rectangular(column-wise) matrix to a column vector then we need to solve the system.

$\displaystyle \breve{A} \cdot \text{vec}(X) = \text{vec}(C)$

where,

We can solve the system ${\breve{A}\,\text{vec}(X) = \text{vec}(C)}$ provided ${\breve{A}}$ has maximum rank. We can reconstruct ${X}$ from ${\text{vec}(X)}$ but this does not ensure that the matrix ${X}$ is of determinant ${1}$ . We can ensure that ${X}$ has determinant ${1}$ by addition of a suitable scalar times identity matrix ( which must also be a solution trivially)

Wikipedia mentions that there is a better way to represent this matrix using tensor product ${\otimes}$ ( also called Kronecker product of matrices http://en.wikipedia.org/wiki/Kronecker_product):

$\displaystyle \breve{A} = I_n \otimes A - A^T \otimes I_n$

where ${I_n}$ is the ${n\times n}$ identity matrix.

0.1. Related results

On a related note, here is another question. Can you produce matrices ${E}$ and ${F}$ such that the commutator ${EF - FE}$ is the sum of two other ${n \times n}$ commutators ${AB-BA}$ and ${CD-DC}$ ? . Using the methods above we can find ${E}$ and ${F}$ indirectly, but is there a simple representation of ${E}$ and ${F}$ in terms of ${A,B,C,D}$ ? I do not know. However here are some insights:

Suppose ${e_{ij}}$ denotes the matrix with ${1}$ only at the position ${i,j}$ , ( ${1\leq i,j \leq n}$ ), in the matrix and the rest filled by zeros. We use the fact that the set of ${n\times n}$ matrices which are commutators is a linear space with basis:

$\displaystyle e_{ij} = e_{ii}e_{ij} - e_{ij}e_{ji} \text{ for } i \neq j$

and

$\displaystyle e_{ii} - e_{i+1\,i+1}$

I will leave this to the diligent reader to see why this is true. This says that any ${n\times n}$ commutator ${CD - DC}$ is a linear combination of these basis vectors. Armed with this result we can break the original problem down to the following two problems:

Given matrices ${n\times n}$ matrices ${A,B}$ with commutator ${AB-BA}$ , the commutator ${e_{ij}}$ ( ${j \neq i}$ ) and a scalar ${c}$ , find ${E}$ and ${F}$ such that
$\displaystyle AB - BA + c (e_{ij}) = EF -FE$

.
Similarly given a scalar ${c}$ , and matrices ${A,B}$ , for each ${i}$ , find matrices ${E,F}$ such that
$\displaystyle AB - BA + c( e_{ii} - e_{i+1\,i+1}) = EF - FE$

I could not give a simple representation of ${E,F}$ in terms of ${A,B,e_{ij}}$ . For for some special cases, it seems possible. Suppose you know that for the index ${j}$ , ${B_j}$ is the only column of ${B}$ containing non-zero entries. Now choose constants ${c_k = \text{signum } b_{kj}}$ , ${k=1,2\ldots,n}$ , such that ${\sum_k c_k b_{kj} \neq 0}$ .

We next note the identity ${e_{ij} = e_{ik}e_{kj} - e_{kj}e_{ij}}$ , for ${i \neq j}$ and ${1\leq k\leq n}$ , using which we can write:

$\displaystyle (\sum_k |b_{kj}|) e_{ij} = \sum_k (c_k e_{ik}) (b_{kj} e_{kj}) - {b_{kj}e_{kj}}c_{k}e_{ik}$

where ${B_{kj}}$ denotes the entry at the location ${k,j}$ in the matrix ${B}$ . Now let ${B_j = \sum_k B_{kj}e_{kj}}$ . Next using the fact that ${e_{ik}e_{lj} = 0}$ is ${k \neq l}$ , we have ${e_{ik} B_{kj}e_{kj} = e_{ij}B_j}$ and ${B_j e_{ik} = 0 = \sum_k B_{kj}e_{kj}}$ , so the above expression for ${e_{ij}}$ can be rewritten as:

$\displaystyle (\sum_k |b_{kj}| ) e_{ij} = \sum_k{ c_k e_{ik} B_j - B_j c_k e_{ik}}$

or,

$\displaystyle e_{ij} = H_iB_j - B_jH_i$

where ${H_i = (\sum_k c_k e_{ik})/(\sum_k |b_{kj}|) }$ . Now if ${B_j = B}$ , then

$\displaystyle e_{ij} = ( H_i B - B H_i )$

Thus,

$\displaystyle AB - BA + e_{ij} = AB - BA + ( H_i B - B H_i ) = (A + H_i) B - B ( A + H_i)$

Here are other examples: For ${i\neq j}$ , ${i \neq l}$ , ${l \neq k}$ ,

$\displaystyle c e_{ij} + d e_{kl} = (c e_{ii} + d e_{kk} ) ( e_{ij} + e_{kl} ) - ( e_{ij} + e_{kl} ) ( c e_{ii} + de_{kk} )$

Also, for the case where ${ i \neq j}$ and ${k \neq i}$ , we have:

$\displaystyle c e_{ij} + de_{ki} = ( c e_{ii} + (d+c) e_{kk}) ( e_{ij} + e_{ki} ) - (e_{ij} + e_{ki} ) ( c e_{ii} + (d+c) e_{kk} )$

Categories: Uncategorized Tags: linear algebra

Three non-idiotic guesses

December 23, 2009 mymbl Leave a comment

Three problems to ponder for the next 100 years:

First one may seem contrived but thinking about this would hightlight some major properties of primes. So here it is : The number 82 is the largest positive number that cannot be written as sum of two square free numbers each having odd number of prime factors.
Motivation for this guess comes from the result of the following python program that was run on sage to compute the number of such pairs of numbers summing upto a given number.

def sqfreesum(n):
sum = 0;
for i in range(1,n ):
sum +=moebius(i)^2* moebius(n-i)^2
*( ( 1 + moebius(i))*( 1 + moebius(n-i) )/4 );
return sum;

The graph which shows the number of ways of writing a number as a sum of two such square free numbers, reveals a trend:it increasingly stays away from zero. In fact after taking off from 82, where it is zero, it never seems to drop down.

Note that we can always write a number as a sum of two square free numbers. The numbers of ways of writing them is:
$a(n) \sim n \cdot \Pi_{p \text{ prime}} (1-2/p^2) * \Pi_{p^2|n} \frac{(p^2-1)}{(p^2-2)}$ . Have to warn you that I have not seen an actual proof but I have seen it mentioned here:
A098235
The second one is in the same spirit as the previous one. Any even number > 10 can be written as the sum of two square free numbers with one having odd number of prime factors and the other having even number of prime factors.
Motivation for this guess comes from the the result of the following python program that was run on sage to compute the number of such pairs of numbers summing upto a given number.

def sqfreesum(n):
sum = 0;
for i in range(1,n ):
sum +=moebius(i)^2* moebius(n-i)^2
*( ( 1 + moebius(i))*( 1 – moebius(n-i) )/4 + ( 1 – moebius(i))*( 1 + moebius(n-i) )/4);
return sum;

As with the previous conjecture the graph which shows the number of ways of writing a number as sum of such square free numbers. has only a few hiccups taking off, and at n=10 it achieves escape velocity. I should also mention here that any even number according to Chen Jigrun can be written as the sum of prime and semi-prime(product of two primes) or a sum of two primes. So when diluted, this result that says if Goldbach conjecture were false, we atleast know that every even positive number can be written as sum of two square free positive numbers one with odd number of prime factors( infact 1) and the other with even number of factors ( in fact 2).
Treat the following with caution please. If $\phi$ denotes the Euler totient function, then the following number is always greater than 2n.
$\sum_{i=2}^{2n-2} (2n)^{ (2n - (2n-i)\cdot i + \phi(2n-i)\cdot \phi(i)) }$ .
Proving this will prove the Goldbach conjecture. This is because, it is only when both i and 2n-i are prime that: $(2n - (2n-i)\cdot i + \phi(2n-i)\cdot \phi(i))$ is 1. There are better ways to reformulate the Golbach conjecture. One other way is the following:
Given an even number $2n$, there exists a number $k<2n$ such that
$k^2 - n^2 - \phi(k^2-n^2) = (2 n-1)$

Categories: Uncategorized Tags: number theory;

A bound for matrix norm

November 16, 2009 mymbl Leave a comment

We wish to better the bounds for the norm of a matrix ${M = (k(i,j))}$ with scalar entries when it defines a linear map with from ${l^p}$ to ${l^p}$ , that is the series ,

$\displaystyle Mx(i) = \sum_{j=1}^\infty k_{i,j} x(j)$

is convergent for each ${i}$ and ${Mx \in l^p}$ . The standard bounds for matrix norm given in the text for ${p \geq 2}$ , are ${\alpha_1^{1/p} \alpha_\infty^{1/q}}$ and ${\beta_p}$ , for ${l^p}$ spaces. We give yet another bound using the power mean inequality:

1. Power Mean Inequality :

Consider positive weights ${p_k}$ , ${k = 1, 2, \ldots, }$ which have total mass ${p_1 + p_2 + \ldots= 1}$ , then for nonnegative real numbers ${x_k}$ , ${k = 1, 2,\ldots }$ and for all ${-\infty < s < t < \infty}$ one has

$\displaystyle (\sum_{k=1}^\infty p_k x_k^s)^{1/s} \leq (\sum_{k=1}^\infty p_k x_k^t)^{1/t} \ \ \ \ \ (1)$

2. Bound for matrix norm

Consider,

$\displaystyle \begin{array}{rcl} \left | \left | Mx \right | \right |_p^p &= \sum_{i=1}^\infty \left|\sum_{j = 1}^\infty k_{i,j} x(j) \right |^p \\ &\leq \sum_{i=1}^\infty \left( \sum_{j=1}^\infty \left |k_{i,j} x(j) \right | \right )^p \\ &= \sum_{i=1,r_i \neq 0}^\infty r_i^p \left ( \sum_{j=1}^\infty \left |\frac{k_{i,j}}{r_i} x(j) \right | \right )^p \end{array}$

where for some fixed ${s > 0}$ and ${s <= 1}$ , ${r_i = \sum_{j=1}^\infty |k_{i,j}^{s}|}$ .

$\displaystyle \begin{array}{rcl} \left | \left | Mx \right | \right |_p^p & \leq \sum_{i=1, r_i \neq 0}^\infty r_i^p \left ( \sum_{j=1}^\infty \frac{\left |k_{i,j}^{s} \right |}{r_i} \left|k_{i,j}\right|^{1-s}\left| x(j) \right | \right )^p \end{array}$

Now we use power mean inequality with ${\alpha=1}$ { and } ${\beta = p}$ , ${ p_k = \frac{|k_{i,j}^{s}|}{r_i}}$ { and } ${x_k = | k_{i,j}^{1-s} x(j)|}$ . So,

$\displaystyle \begin{array}{rcl} \left | \left | Mx \right | \right |_p^p &\leq \sum_{i=1,r_i\neq 0}^\infty r_i^p \sum_{j=1}^\infty \left | \frac{|k_{i,j}^{s}|}{r_i} k_{i,j}^{p(1-s)}x(j)^p \right | \\ &= \sum_{i=1}^\infty\sum_{j=1}^\infty r_i^{p-1}\left | { k_{i,j}^{s+p(1-s)}} \right | \left|x(j)\right|^p \\ & = \sum_{j=1}^\infty \left|x(j)\right|^p \sum_{i=1}^\infty r_i^{p-1}\left | { k_{i,j}^{s+p(1-s)}} \right | \\ \end{array}$

Now if we take,

$\displaystyle \gamma_s = \sup_j \left \{ \sum_{i=1}^\infty r_i^{p-1} \left| k_{i,j}^{s + p(1-s)}\right| \right \}^{1/p}$

Then we have ${Mx \leq \gamma_s \left| \left | x \right |\right |_p}$ . So we have infinite number of bounds for the norm as we vary ${s}$ among positive reals (of course, not all values of ${s}$ might be useful )

Example : Consider the matrix

$\displaystyle A = \begin{pmatrix} 1 & 1/2^{3} & 1/3^3 & \ldots \\ 1/2 & 1 & 0 & \ldots \\ 1/3 & 0 & 1 & \ldots \\ \vdots & & & \vdots \\ \end{pmatrix}$

For this matrix ${\alpha_1 = \infty}$ and ${\beta_2}$ is also infinity, however ${\gamma}$ is finite with ${s =1/2}$ . This is because ${\sup_i r_i = \sum_n (1/n^3)^{1/2} < \infty }$ and ${\sup_{i} \sum_{j=1}^n k_{i,j}^{(2+1)/2} =\sum_{j=1}^n 1/n^{3/2} < \infty}$ . Thus ${\gamma_{2} \leq \sup_i r_i \sup_i \sum_{j=1}^n k_{i,j}^{3/2} < \infty}$ .

You can further see that ${\gamma_s}$ is a better bound than ${\alpha_\infty^{1/q}\alpha_1^{1/p}}$ always, since if we take ${s = 1}$ and ${r = \infty}$ , we have

$\displaystyle \sup_j \sum_{i=1}^\infty r_i^{p-1} \left|k_{i,j}^{s + p(1-s)}\right| = \sup_i {r_i^{p/q}} \sup_j \sum_{i=1}^\infty \left |k_{i,j}\right| \leq \alpha_\infty^{p/q} \alpha_1,$

where we have used the fact that ${p-1 = p/q}$ .

Categories: Uncategorized Tags: functional-analysis, matrix, norm

Presentations and cardinality

October 29, 2009 mymbl Leave a comment

Have a look at the presentation of a group defined by the generators ${x_1,x_2,x_3}$ , and the presentation below.

$\displaystyle (1) \quad x_2 x_1 x_2^{-1} = x_1^2 \qquad x_3 x_2 x_3^{-1} = x_3^2 \qquad x_1^1 x_3 x_1^{-1} = x_3$

It is symmetric, it is recursively presented, but can you guess the cardinality of this group. Or, of the group defined by four generators ${x_1,x_2,x_3,x_4}$ and relations:

$\displaystyle (2) \quad x_2 x_1 x_2^{-1} = x_1^2 \quad x_3 x_2 x_3^{-1} = x_1^2 \quad x_4 x_3 x_4^{-1} = x_3 \quad x_1 x_4 x_1^{-1} = x_4^2$

Some very basic group theory but some sweating and toiling(maybe some shedding of tears) will reveal that the group formed by with first set of relations collapses to identity element. But the same methods do not shed any light on the cardinality of the group with the second set of relations. Once you have mastered the dark art of amalgam-making you will realize that the second set of relations is actually a recipe for cooking an infinite group. The moral is this: Presentations do not immediately reveal the subtle ways in which cancellations can occur. Below, I show how the second presentation gives an infinite group as was shown by Higman. The first presentation is an exercise in Trees and I broke some sweat working it out.

Proposition 1 (Higman) Let ${G}$ be the group defined by the four generators ${x_1,x_2,x_3,x_4}$ and the four relations in 0. Then

Each subgroup of finite index in ${G}$ is equal to ${G}$
${G}$ is infinite.

Proof: We first prove a). Every subgroup ${H}$ of finite index in ${G}$ contains a normal subgroup of finite index ( the kernel of the action of the group ${G}$ on the cosets of ${H}$ which is the intersection of the conjugates of ${H}$ ; the action induces a homomorphism of ${G}$ into a finite sysmmetric group, so the index of the kernel in ${G}$ must be finite as well). It therefore suffices to prove that ${G}$ does not have any finite non-trivial quotient. Now suppose ${\bar {G}}$ is such a quotient and let ${n_i}$ be the order of ${x_i}$ in ${G_i}$ . Note that not all ${n_i}$ can be ${1}$ since we had assumed that ${\bar G}$ is non-trivial. Now let ${p}$ be the smallest prime divisor of any of the ${n_i}$ , and suppose without loss of generality that ${p}$ divides ${n_1}$ . The fact that

$\displaystyle x_1^{2^{n_2}} = x_2^{n_2} x_1 x_2^{-n_2} = x_1 \text{ in } \bar G$

and so ${2^{n_2} \equiv 1 \mod{n_1}}$ and thus also ${2^{n_2} \equiv 1 \mod{p}}$ . This implies that ${p \neq 2}$ . On the other hand, we have ${2 \not \equiv 1 \mod{p}}$ . Let the order of ${2}$ in in ${{\mathbb Z}/{p{\mathbb Z}}}$ be ${N}$ . Clearly ${1 < N \leq p-1}$ . Thus ${n_2 \equiv 0 \mod{N}}$ . If ${p'}$ is a prime factor of ${N}$ we then have ${n_2 \equiv 0 \mod{p'}}$ and ${p' \leq N \leq p-1}$ , which contradicts the minimal character of ${p}$ , hence a). Proof of b). Let

$\displaystyle G_{12} = \langle x_1, x_2 | x_2 x_1 x_2^{-1} = x_1^2 \rangle$

and let ${G_1,G_2}$ be the sub-groups generated by ${x_1,x_2}$ resp. in ${G_{12}}$ . The groups ${G_1,G_2}$ are each isomorphic to ${\mathbb Z}$ and ${G_1 \cap G_2 = \{1\}}$ . Similarly one can define the group ${G_{23}}$ ( ${G_{34}, G_{41}}$ ) with subgroups ${G_2}$ and ${G_3}$ (resp. ${G_3,G_4}$ and ${G_4,G_1}$ ).

The key idea now is to recognize that the presentation gives us a recipe for forming the amalgam:

$\displaystyle (G_{12} *_{G_2} G_{23} ) *_{G_1 * G_3} (G_{34} *_{G_4} G_{41})$

The result now follows by the fact that the free product ${G_1 * G_2}$ which is also a subgroup of ${G}$ is infinite. $\Box$

For proving that the group whose presentation is given by 0 collapses, the methods employed are more elementary:

${G}$ has three generators ${x_1, x_2, x_3}$ and defining relations 0 We must then have from the first relation:

$\displaystyle x_1^{-1}x_2x_1 =x_1x_2$

Raising both sides of the first relation to the ${i}$ -th power, we have

$\displaystyle x_2 x_1^i x_2^{-1} = x_1^{2i}$

and therefore,

$\displaystyle x_1^{-i}x_2x_1^i= x_1^{i}x_2$

and similarly also from the second and third relations we have,

$\displaystyle x_2^{-i}x_3x_2^i = x_2^ix_3 \qquad x_3^{-i}x_1x_2^i = x_3^ix_1.$

Conjugating the third relation by ${x_2}$ , the left-hand side becomes

$\displaystyle x_2 x_1 x_3 x_1^{-1} x_2^{-1} = x_1^2 x_2 x_3 x_2^{-1} x_1^{-2} = x_1^2 (x_2^{-1} x_3) x_1^{-2} = (x_1^{2} x_2^{-1} x_1^{-2} ) (x_1^2 x_3 x_1^{-2}) = (x_2^{-1} x_1^2) x_3^4.$

While the right hand side becomes

$\displaystyle x_2 x_3^2 x_2^{-1} = (x_2 x_3)^2 = x_2(x_3 x_2 x_3^{-1} ) x_3^2 = x_2^3 x_3^2.$

So we have,

$\displaystyle x_2^{-1} x_1^2 x_3^4 = x_2^3 x_3^2,$

$\displaystyle (3) \qquad x_2^4 = x_1^2 x_3^2$

Symmetry of the relations suggest that we must also have

$\displaystyle x_3^4 = x_2^2 x_1^2 \qquad x_1^4 = x_3^2 x_2^2$

Multiplying (3) by ${x_2^2}$ gives

$\displaystyle x_2^6 = x_1^2 x_3^2 x_2^2 = x_1^6$

and

$\displaystyle x_2^6 = x_2^2 x_1^2 x_3^2 = x_3^6$

But by raising the first relation to the power 3 we have

$\displaystyle x_2 x_1^3 x_2^{-1} = x_1^6 = x_2^6$

Thus

$\displaystyle x_1^3 = x_1^6 \Rightarrow x_1^3 = 1$

Similary, we also have

$\displaystyle x_2^3 = x_3^3 = 1$

. Finally, conjugating the first relation with ${x_2}$ we must have on the left hand side

$\displaystyle x_2^2 x_1 x_2^{-2} = x_2^{-1} x_1 x_2$

while on the right hand side we get,

$\displaystyle x_2x_1^2 x_2^{-1} = x_1^4 = x_1$

Thus ${x_1 x_2 = x_2 x_1}$ . Again, from the first relation this implies ${x_1 = x_1^2}$ or ${x_1 = 1}$ . Then from the third relation we must also have ${x_3^2 = x_3}$ or ${x_3 = 1}$ and so also ${x_2^2 = x_2}$ or ${x_2 = 1}$ . The group formed by these generators hence collapses.

Categories: Expository, Trees Tags: amalgams, group-theory

Embedding a torsion-free group in a infinite simple group

October 26, 2009 mymbl Leave a comment

Using the HNN theorem we have an easy corollary.

Corollary 1 Every group can be embedded in a group ${K}$ enjoying the following properties.

All elements of ${K}$ of the same order are conjugate.
Furthermore, if ${G}$ is denumerable (or torsion-free) we can choose ${K}$ to be denumerable( or torsion-free)

Proof: For a change, Serre was kinder with me in this proof. So lot of the content here are his words. If ${x,y \in G}$ have the same order there exists an injective map from ${A = \langle x \rangle}$ to ${G}$ which sends the generator ${x}$ to ${y}$ . The HNN theorem gives us a group ${G_{xy}}$ in which both ${x}$ and ${y}$ are conjugate. Repeating this operation for every such pair of ${(x,y)}$ which have same order in ${G}$ , we construct, bigger and bigger groups, whose direct limit (their union) is a group ${E(G)}$ containing ${G}$ , in which every pair of elements with same order in ${G}$ (identified with theire images in ${E(G)}$ ) are conjugate. Now we repeat this procedure on ${E(G)}$ to get a bigger group ${E(E(G)) = E^2(G)}$ where every pair of elements of ${E(G)}$ ( identified with their images in ${E^2(G)}$ ) which are of the same order are conjugate to each other. After ${k}$ such steps we get a group we denote by ${E^k(G)}$ in which every of elements of ${E^{k-1}(G)}$ of the same order are conjugate. Passing to the direct limit (union) we claim that the direct limit ${K}$ in which every pair of elements which are of the same order are conjugate. For if, ${x,y \in K}$ which are of same order then ${x,y \in E^k(G)}$ for some ${j \in \mathbb N}$ , so ${x,y}$ must be conjugate to each other in ${E^{k+1}(G)}$ by construction. So the group ${K}$ answers the question.

Why is ${K}$ torsion-free (denumerable) if ${G}$ is torsion free (denumerable)? This is because HNN extensions may be chosen to be torsion-free (denumerable) if the group whose extension is being taken is torsion-free ( denumerable). Also, direct limits of an increasing sequence of groups is also torsion free( or denumerable) if the groups are so. In particular if ${K}$ is torsion-free, every pair of elements must be conjugate to each other. This means if ${H}$ is any normal subgroup of ${K}$ and ${h \in H}$ then as every element conjugate of ${H}$ must be in ${H}$ , and the set of conjugates of each ${h \in H}$ is the entire group ${K}$ , ${H = K}$ . So ${K}$ is simple if it does not reduce to ${\{1\}}$ . Cute!

$\Box$

Categories: Trees Tags: amalgams, group-theory, HNN extension

HNN Extensions

October 24, 2009 mymbl 1 comment

I have been studying amalgams from the book Trees ( vying for time with five other courses) with little progress. Serre, the author of this book, is absolutely merciless on the reader, leaving out all details that a stout hearted reader, who is motivated enough can fill in( maybe a background in decrypting ciphers will help). The answers are there in book, but hidden behind some carefully crafted words, and God knows ploughing through this thick crust of words is not easy. But after about fifteen to sixteen readings(read boxing rounds) of the proof, matters usually settle down without anyone being mortally wounded with the dawning of the realization that I understand the proof well-enough to write it myself.

I will try to fill in the details in this post and few others. I will start with a construction I particularly liked (it is a twelve line proof in Trees). This proof is one that elaborates on the proof given in Trees(the mistakes, are well, most likely to be mine).

Proposition 1 (G. Higman, B.H Neumann, H. Neumann) Let ${A}$ be a subgroup of a group ${G_n}$ and ${\theta: A \rightarrow G}$ an injective homomorphism. Then there is a group ${G'}$ containing ${G}$ and an element ${s}$ of ${G'}$ such athat ${\theta(a) = sas^{-1}}$ for all ${a \in A}$ . Furthermore, if ${G}$ is denumerable( or finitely generated, or torsion free) we can choose ${G'}$ to be a group with the same property.

Proof: For each ${n \in \mathbb Z}$ , we put ${A_n = A}$ and ${G_n = G}$ . By amalgamating ${G_n}$ with the injective homomorphisms: ${\theta: A_n \rightarrow G_n}$ and ${id: A_n \rightarrow G_{n+1}}$ ( id is is the identity map), we construct the group ${H}$ :

hnn extension

Let ${f_n: G_n \rightarrow H}$ for ${n \in \mathbb Z}$ , be the homomorphisms obtained by the amalgamation. Recall that in constructing amalgams we take the quotient of a free group formed of the disjoint union of these sets, so ${G_n}$ for ${n=1,2\ldots}$ are different subgroups of ${H}$ . Let ${u_n: G_n \rightarrow G_{n+1}}$ be the canonical isomorphism: ${ u_n(g_n) = g_{n+1}}$ . These maps induce the maps ${g_n = f_{n} \circ u_{n-1} : G_{n-1} \rightarrow H}$ for ${n \in \mathbb Z}$ . The homomorphisms ${g_n}$ are also compatible with maps ${id}$ and ${\theta}$ because

$\displaystyle \begin{array}{rcl} g_n (\theta(a_{n-1})) = f_{n} ( u_{n-1} ( \theta(a_{n-1}))) \\ = f_n (\theta( a_n)) = f_{n+1}(a_n) = f_{n+1}( u_n( a_{n-1} )) = g_{n+1}(a_{n-1}) \end{array}$

By the universal property of amalgams, we have a induced map ${u:H \rightarrow H}$ that makes the diagram below commutative:

null

A similar argument shows that the inverse maps

$\displaystyle v_{n} : G_{n+1} \rightarrow G_n$

induce the map ${v: H \rightarrow H}$ . Now as ${u_n \circ v_n = v_n \circ u_n = id}$ . We show that we also have ${u \circ v = v \circ u = id}$ . This will show that ${u}$ is an automorphism between ${H}$ and ${H}$ . To see this note that the maps

$\displaystyle v \circ f_{n+1} = f_n \circ v_n$

so for all ${n \in \mathbb Z}$ , we have

$\displaystyle u \circ v \circ f_{n+1} = u \circ f_n \circ v \\ = f_{n+1} \circ u_{n} \circ v_n = f_{n+1} \\$

Thus the homomorphisms ${u \circ v \circ f_n}$ are each compatible with the maps ${\theta}$ and ${id}$ from each ${A_n}$ . So, these maps must induce a unique homomorphism ${\Phi}$ from ${H}$ to ${H}$ such that ${u \circ v \circ f_{n} = \Phi \circ f_{n} = f_{n}}$ . Both the identity map also ${u \circ v}$ are homormophisms from ${H}$ to ${H}$ which satisy the above conditions, by uniquenesss of the induced isomorphism (universal property of the amalgam), we must have that ${u \circ v = id}$ . By a similar reasoning using ${v \circ u}$ , we must also have ${v \circ u = id}$ . Thus ${u}$ is indeed an automorphism.

Further by commutativity of the diagram ${u(f_n(g_n)) = f_{n+1}(u_n(g_{n})) = f_{n+1}(g_{n+1})}$ we must have in particular that ${u(f_{n}(a_{n})) = f_{n+1}(a_{n+1}) = f_{n}(\theta(a_n)}$ . Thus, if we identify groups ${G}$ with ${G_0}$ , ${A}$ with ${A_{0}}$ and ${G_0}$ with its images in ${H}$ , the map ${u}$ is just an extension of the map ${\theta}$ .

The construction of group is now fairly easy. If ${S = \langle s \rangle }$ is the infinite cyclic group generated by ${s}$ , we form the semi-direct product ${G' = H \rtimes S}$ , with ${u}$ acting on ${H}$ via ${u}$ by conjugation as follows

$\displaystyle s \cdot h = s h s^{-1} = u(h)$

Clearly when we restrict this action to ${A = A_0}$ we have for any ${a_0 \in A_0}$ :

$\displaystyle s\cdot (f_0(a_{0})) = u(f_0(a_0)) = \theta(a_0)$

The pair ${G',s}$ then has the desired property.

Moreover if ${G}$ is denumerarble, then ${H}$ is also denumerable being the quotient of the disjoint union of denumerable groups. Next as ${G' = H \rtimes \langle s \rangle }$ has the same cardinality as ${\langle s \rangle \times H}$ , ${G'}$ must also be denumerable. If ${G}$ is without torsion, we would like to show that ${G'}$ is also without torsion. For this, we first prove by induction that for all ${n \in {\mathbb N} \cup \{0\}}$ the group

$\displaystyle H_{n} = G_{-n} *_{A_{-n}} G_{-n+1} * \ldots *_{A_{-1}} G_0 *_{A_0} \ldots G_{n} *_{A_{n}} G_{n+1}$

is without torsion. This is clear for ${n=0}$ as from the structure theorem, the only elements of finite order in the amalgam ${G_0 *_{A_0}G_1}$ , are those that are conjugate to either ${G_1}$ or ${G_0}$ , both of which are without torsion. Now assume the that this is true for all natural numbers less than ${n}$ . Then for ${n}$ , use associativity of amalgams( proved in previous post) to write

$\displaystyle H_{n+1} = G_{-n-1} *_{A_{-n-1}} * (H_n *_{A_{n+1}} G_{n+2})$

Notice that ${H_n' = H_n *_{A_{n+1}} G_{n+2}}$ is without torsion as ${H_n}$ (by induction hypothesis) and ${G_{n+2}}$ also is without torsion. Also as ${G_{-n-1}}$ and ${H_n'}$ are without torsion so is ${H_{n+1} = G_{-n-1} *_{A_{-n-1}} H_n'}$ is also without torsion. Thus for all ${n}$ , ${H_n}$ is without torsion. Now by passing to the direct limit of the groups ${H_n}$ , we see that the direct limit ${H}$ (being the union: ${\bigcup_{n \in {\mathbb N}}H_n}$ ) is also without torsion. Moreover, the infinite cyclic group ${S}$ is also without torsion and so the semidirect product ${H \rtimes S}$ as its elements are of the form ${(h,s)}$ where ${h \in H}$ and ${s \in S}$ . If ${s = 1}$ , for any ${n \in \mathbb N}$ we have ${(h,1)^n = (h^n,1) \neq 1}$ and if ${s \neq 1}$ , then for any ${n \in \mathbb N}$ , ${(h,s)^n = (h',s^n) \neq 1}$ for some ${h'}$ .

Finally we show that if ${G}$ is finitely generated, so is ${G'}$ (in a later post)

$\Box$

Categories: Uncategorized Tags: amalgams, group-theory

associativity of amalgams or why universal properties can be powerful

October 23, 2009 mymbl 2 comments

Amalgams of groups are examples of what are known as colimits in category theory(aka abstract non-sense). With abstract non-sense, you can turn a blind-eye to the structure of the groups and concentrate wholly on its social behavior, determined by its universal property. There is nothing deep about proving results using universal properties of groups, as we are using the most obvious properties of groups when interacting with other groups. But these can be super-powerful when it comes to proving stuff which would otherwise be non-trivial ( for example when you are only looking at the structure of these groups).

Recall that the product of groups ${G_i}$ where ${i \in {\mathbb N}}$ , amalgamated with groups ${A_i}$ using injective homomorphisms ${f_i: A_i \rightarrow G_i}$ and ${f_{i}':A_i \rightarrow G_{i+1}}$ for ${i=1,2,\ldots}$ is the group ${U}$ along with homomorphisms ${g_i:G_i \rightarrow U}$ that are compatible with ${f_i}$ and ${f_i'}$ . This means that ${g_i \circ f_i = g_{i+1} \circ f_{i}'}$ for all ${i}$ . Further, ${U}$ has the universal property that if ${H}$ is any group with homomorphisms ${h_i: G_i \rightarrow H}$ which are compatible with the maps ${f_i,f_i'}$ for each ${i \in I}$ , we have a unique homomorphism ${\Phi : U \rightarrow H}$ such that:

$\displaystyle h_i = \Phi \circ g_i \text{ for } i \in \mathbb N$

The group ${U}$ is usually denoted by ${G_1 *_{A_1} G_2 *_{A_2} G_3 *_{A_3} \ldots}$ . To illustrate the power of this definition, lets us prove the following assertion about associativity of amalgams.

$\displaystyle (G_1 *_{A_1} G_2) *_{A_2} G_3 \equiv G_1 *_{A_2} G_2 *_{A_3} G_3$

Note that the amalgam ${G_1 *_{A_2} G_2 *_{A_3} G_3}$ is exactly the group that makes the following diagram commute and

whats more important: it is best candidate for making the diagram commute in the sense that, if ${H}$ is any other group replacing ${G_1 *_{A_1} G_2 *_{A_2} G_3}$ that also makes the above diagram commute then there is a unique homomorphism from ${G_1 *_{A_1} G_2 *_{A_2} G_3}$ to ${H}$ . Such a ${G_1 *_{A_1} G_2 *_{A_2} G_3}$ is hence unique upto a unique isomorphism. To prove the above equality we try to show that LHS also has the universal property of the amalgam RHS and hence there must be a unique isomorphism between the two. Consider the diagram below:

With the amalgam ${G_1 *_{A_1} G_2}$ we have homomorphisms ${\eta_1: G_1 \rightarrow G_1 *_{A_1} G_2}$ and ${\eta_2 : G_2 \rightarrow G_2 *_{A_1} G_2}$ and the with amalgam ${(G_1 *_{A_1} G_2) *_{A_2} G_3}$ we have homomorphisms ${\xi_1: G_1 *_{A_1} G_2 \rightarrow (G_1 *_{A_1} G_2) *_{A_2} G_3}$ .

Now if ${H}$ is any group with maps ${h_i: G_i\rightarrow H}$ for ${i=1,2,3}$ , that are compatible with ${f_i:A_i \rightarrow G_i}$ , then we need to show that ${h_i}$ factors via a unique homomorphism ${\Phi:(G_1 *_{A_1} G_2) *_{A_2} G_3 \rightarrow H}$ . ${h_i}$ .

The map ${h_1 : G_1 \rightarrow H}$ and ${h_2 : G_2 \rightarrow H}$ are compatible with ${f_1}$ and ${f_1'}$ so by universal property of the amalgam ${G_1 *_{A_1} G_2}$ we have a unique morphism ${\varphi : G_1 *_{A_1} G_2 \rightarrow H}$ such that ${h_1 =\varphi \circ i_1}$ . Now since ${\varphi, h_3}$ are compatible with ${\eta_2 \circ f_2}$ and ${f_2'}$ , the map ${\varphi}$ can be further factored using the universal property of the amalgam ${(G_1 *_{A_1} G_2) *_{A_2} G_3}$ by the unique homomorphism ${\Phi: (G_1 *_{A_1} G_2) *_{A_2} G_3 \rightarrow H}$ . This shows the associativity of amalgamation.

Note 1: When amalgams were first introduced, before category theory came into being, (see for example pre-ww-2 era papers by B.H Neumann on free groups with amalgamation et. al), they were treated as generalized versions of free products of groups with complicated inner structures. They never made use of these elegant universal properties and proving such things as associativity, can get really messy.

Updated:Fixed typo

Categories: Uncategorized Tags: group-theory

cheat sheet for continuity.

October 21, 2009 mymbl Leave a comment

You are interested in establishing the continuity of a linear map ${F:X \rightarrow Y}$ where ${X}$ and ${Y}$ are normed spaces. You would like to know some sufficient conditions for proving continuity. The thought about browsing your old fat text book makes you cringe and would like a quicker way (like what a Schaum series textbook would offer). Heres a list

Continuity at zero.
Existence of a positive ${\alpha}$ such that ${ \left|\left|F(x)\right|\right| \leq \alpha \left|\left| x\right |\right|}$ .
Did you know that if ${X}$ and ${Y}$ are Banach, thanks to the venerable Closed Graph Theorem, it is sufficient to check that ${F}$ is closed for proving its continuity.
Is the range space your linear map finite dimensional?. In this case it is enough to check that the null space of your linear map is closed.
Is your map a projection map? If yes, then it is enough to check that range space and zero space of your linear map are closed.

Btw Iam a fan of the Schaum series books. They explain the basics in as little notation as possible and with little to and fro references.Even Gian Carlo Rota sings paens about them(well, he likes atleast one book). Come join the league of fans, don’t be snooty…

Categories: Uncategorized

which random variables have uniform distribution

October 14, 2009 mymbl Leave a comment

Sometime back I was asked this question by our professor teaching us probability : How do we characterize random variables which have uniform distribution?. I revisited my old measure notes to give a partial answer to this question:

Let ${X}$ be a random variable defined on the probability space ${[0,1]}$ with Lebesgue measure. Suppose further that ${[0,1]}$ is the union of disjoint intervals ${I_1, I_2 , \ldots }$ where in each interval ${I_k}$ we have either ${X'>0}$ or ${X'<0}$ a.e. Then, a necessary condition for ${X}$ to have the uniform distribution is the following. For each ${y \in X([0,1])}$ we have

$\displaystyle 1 = \sum_{\omega : X(\omega) = y} \frac{1}{ |X'(\omega)|}$

a.e ( ${\mu X^{-1}}$ ).

Proof: Let ${A \subset \mathbb R}$ , then if ${\mu}$ is the probability measure (lebesgue measure) on ${[0,1]}$ . Let ${I_1, I_2, \ldots}$ be the intnervals where ${X'(\omega) >0}$ a.e or ${X'(\omega)< 0}$ . Then,

$\displaystyle \mu X^{-1}(A) = \mu(A) = \int_A d\mu = \int_{[0,1]} \sum_{k \geq 1} {\chi_{I_k \cap A}} d\mu = \sum_{k \geq 1} \int_{[0,1]} \chi_{I_k \cap A} d \mu$

where the last equality holds by m.c.t ( ${\chi}$ denotes the indicator function). Let ${S_k = I_k \cap A}$ for ${k=1,2,\ldots,}$ then note that the restriction of ${X}$ to ${S_k}$ ( which we denote by ${X_k}$ ) is 1-1, so ${X_k^{-1}}$ makes sense and its derivative exists so by change of variables we may write,

$\displaystyle \begin{array}{rcl} \mu(S_k) = \int_{S_k} d\mu = \int_{X(S_k)} \left |dX_k^{-1}(X_k(s))/d\mu \right |d\mu(s) \\ = \int_{X([0,1])} \chi_{X(S_k)} \left| \frac{1}{ X_k'(X_k^{-1}(s)) } \right|\,d\mu (s) \end{array}$

So,

$\displaystyle \begin{array}{rcl} \mu X^{-1}(A) = \sum_{k \geq 1} \int_{X[0,1]} \chi_{X(S_k)} \left| \frac{1}{ X'(X^{-1}(s)) } \right|\,d\mu(s)\\ = \int_{X[0,1]} \sum_{k \geq 1}\chi_{X(S_k)} \left| \frac{1}{ X'(X^{-1}(s)) } \right|\,d\mu (s) \end{array}$

But the density function of ${\mu X^{-1}}$ is ${1}$ as ${X}$ is given to have the uniform distribution, the integrand on the right must be ${1}$ a.e. Thus, for almost all ${s \in X[0,1]}$ ,

$\displaystyle 1 = \sum_{ k \geq 0} \chi_{X(S_k)} \left| \frac{1}{ X'(X^{-1}(s)) } \right| = \sum_{\omega: X(\omega) = y} \left| \frac{1}{ X'(y) } \right|$

$\Box$

Here is a simple example: Consider the random variable ${X}$ as shown in the diagram which has uniform distribution. Notice that for each ${y}$ in the range of ${X}$ , that is not in 0 or 1, the sum of the inverse of slopes at each point where ${X}$ assumes the value ${y}$ is ${1}$ .

Categories: Uncategorized Tags: Probability, Random variables, Uniform distribution

Bedtime mathematics

A problem

matrix commutators

Three non-idiotic guesses

A bound for matrix norm

cheat sheet for continuity.

which random variables have uniform distribution

Tags

Blogroll

Archives