Tuesday, November 1, 2016

Polynomial Identities

Let $F$ be a field and $F\langle X\rangle$ the free associative algebra with alphabet $X$. Let $f(x_1,\ldots,x_m)\in F\langle X\rangle$ be a nonzero polynomial (in non-commuting variables.) We say that an algebra $A$ satisfies the identity $f=0$ if $f(a_1,\ldots,a_m)=0$ for all $m$-tuples of elements of $A$.


Examples:
  1. $A$ commutative: then $A$ satisfies $x_1x_2-x_2x_1=0$.
  2. $A$ nilpotent (say $A^n=0$.) Then $A$ satisfies $x_1\ldots x_n=0$.
  3. $A$ finite dimensional (say of dimension $d$.) Let $$f(x_1,\ldots,x_{d+1})=\sum_{\sigma\in \mathcal{S}_{d+1}}(-1)^{|\sigma|}x_{\sigma(1)}\ldots x_{\sigma(d)}.$$ Then $f$ is multilinear and antisymmetric. If $e_1,\ldots,e_d$ is a basis for $A$, then $f(a_1,\ldots,a_{d+1})$ can be expressed as a linear combination of elements $f(e_{i_1},\ldots,e_{i_{d+1}})$ by multilinearity. However in each such summand, some basis element appears twice, and so $f$ vanishes by antisymmetry. We denote this particular $f$ by $S_{d+1}(x_1,\ldots,x_{d+1})$.
We will call algebras satisfying a polynomial identity "PI algebras."

Lemma: If $A$ satisfies a polynomial identity, it satisfies a multilinear polynomial identity.

Proof:
Let $f$ be a nonzero identity satisfied by $A$. We show how to linearize in the first variable $x_1$. Suppose $x_1$ appears with maximal degree $d$. Introduce new variables $y_1,\ldots, y_d$ and consider the sum
$$f(y_1+\cdots+y_d,x_2,\ldots, x_n)-\sum f(y_1+\cdots+\hat{y}_i+\cdots+y_d,x_2,\ldots)+\cdots$$
which is an alternating sum in which the second term is the sum of ways of omitting one variable. The next term will be the sum of ways of omitting two variables etc. Then this identity still holds since it is a sum of $f$'s, each of which is $0$, but it has the effect that it kills any momomials involving fewer than $d$ instances of $x_1$ and it linearizes those that do. In fact, thinking of the $x_1$'s as indicating $d$ spots in a subword, it sums over putting the variables $y_1,\ldots, y_d$ in those spots in all possible ways.  So for example $f(x_1,x_2)=x_1^2x_2x_1$ would get linearized to
$$\sum_{\sigma\in \mathcal{S}_3} y_{\sigma(1)}y_{\sigma(2)}x_2y_{\sigma(3)}.$$
Now  that we have linearized $x_1$, repeat the process to linearize the other variables.
$\Box$

Lemma: If $A$ is a PI algebra and $R$ is a commutative $F$-algebra, then $A\otimes_F R$ is also a PI algebra.

Proof:
In view of the previous lemma, we may assume that $A$'s polynomial identity, $f(x_1,\ldots, x_m)=0$ is multilinear. So $$f=\sum_{\sigma\in S_m}\alpha_\sigma x_{\sigma(1)}\cdots x_{\sigma(m)},$$ for some coefficients $\alpha_\sigma\in F$.
 We claim that $A\otimes_F R$ satisfies the same polynomial identity. Since $f$ is linear in each variable, $f$ applied to a general $m$-tuplet of elements of $A\otimes_F R$ is a linear combination of $f$ applied to basic tensors. Now
$\begin{align*}
f(a_1\otimes r_1,\ldots ,a_m\otimes r_m)&=\sum_{\sigma\in \mathcal{S}_m}\alpha_\sigma a_{\sigma(1)}\cdots a_{\sigma(m)}\otimes r_{\sigma(1)}\cdots r_{\sigma(m)}\\
&= \sum_{\sigma\in \mathcal{S}_m}\alpha_\sigma a_{\sigma(1)}\cdots a_{\sigma(m)}\otimes r_{1}\cdots r_{m}\\
&=f(a_1,\ldots,a_m)\otimes r_1\cdots r_m\\
&=0
\end{align*}
$
$\Box$

Corollary: The algebra of $n\times n$ matrices over a commutative $F$ algebra $R$,  $M_n(R)$, is a PI algebra.

Proof:
$M_n(F)$ is finite dimensional, so is a PI algebra as we saw earlier. On the other hand,
$M_n(R)=M_n(F)\otimes _F R$, so the previous lemma applies. $\Box$

Indeed, since the dimension of $M_n(F)$ is $n^2$, we know that $M_n(R)$ will satisfy the identity $S_{n^2+1}(x_1,\ldots,x_{n^2+1})=0$. It becomes an interesting question as to whether this is the best that can be done. Does $M_n(R)$ satisfy a lower degree identity? The answer turns out to be yes.

Theorem: $M_n(R)$ satisfies the identity $S_{2n}(x_1,\ldots,x_{2n})=0$ but does not satisfy any identity of degree $<2n$.

Suppose that $A$ satisfies an identity of degree $k<2n$. Linearize, rename variables, and multiply by a scalar so that $$f=x_1\ldots x_k+\sum_{\sigma\neq 1} \alpha_\sigma x_{\sigma(1)}\cdots x_{\sigma(k)}.$$ Let $e_{ij}$ be the matrix with a $0$ in every entry except at the $(i,j)$ entry where there is a $1$.
Now let $$x_1=e_{11},x_2=e_{12},x_2=e_{22}, x_4=e_{23},\ldots$$
Then the only order in which this multiplies to be nonzero is $x_1 x_2\ldots x_k$, so $f(x_1,\ldots,x_k)= x_1\ldots x_k\neq 0$, and therefore $A$ does not satisfy the identity $f$.

Stay tuned until the next blog post for the fact that $S_{2n}=0$.







Sunday, October 30, 2016

Grigorchuk's group

In a previous post we constructed a rather intricate counterexample to the Generalized Burnside Problem using the Golod-Shafarevich criterion for the infinite dimensionality of algebras.
In this post, we will look at a famous group introduced by Grigorchuk which will also be a counterexample to the generalized Burnside problem. Namely, it will be an infinite, finitely generated, $2$-group. The construction is amazingly elementary.

Start with an infinite rooted binary tree $T$, which we visualize growing downward.

         
The non-root nodes of the tree are in 1-1 correspondence with finite sequences of $0$'s and $1$'s. $0$ means head left while $1$ means head right.  The Grigorchuk group $G$ is a subgroup of the automorphism group of $T$. Let $a\in\mathrm{Aut}(T)$ be the involution which exchanges the left and right branches of the tree. On the level of finite bitstrings, it just flips the first bit. We define three other automorphisms $b$, $c$, and $d$ as follows:

    So each of $b,c,d$ fixes the rightmost chain of nodes and alternates acting by $a,a,1$ on the sequence of trees branching off to the left.

If an automorphism fixes the two nodes adjacent to the root, it can be written as a pair of autmorphisms $(x,y)$, each acting on a tree isomorphic to $T$. In other words, let $\mathrm{stab}_1$ denote the group of automorphisms fixing the two nodes of distance $1$ from the root. Then $\mathrm{stab}_1\cong \mathrm{Aut}(T)\times \mathrm{Aut}(T)$. With this convention, we see that $$b=(a,c), c=(a,d), d=(1,b).$$ Moreover one can take these as recursive definitions for $b,c,d$! It is easy to see that $\{1,b,c,d\}$ form a Klein 4-group.

Definition: Grigorchuk's group $G$ is the subgroup of $\mathrm{Aut}(T)$ generated by $\{a,b,c,d\}$.

By definition, $G$ is finitely generated. We also want so show that it is infinite and torsion.

To see that it is infinite, calculate $aba=(c,a), aca=(d,a)$ and $ada=(b,1)$. Thus $H=\mathrm{stab}_1\cap G$ contains elements with $a,b,c,d$ as their first coordinates. So $H$ surjects onto $G$ itself. But $H$ is a proper subgroup of $G$ (in fact index $2$) so the only way this could happen is if $G$ is infinite.

Now we show that $G$ is a torsion group. Any element of $G$ can be written as a product of generators which alternate between $a$ and non-$a$ letters. Moreover any such word is conjugate to one which begins with $a$ and ends with a non-$a$ letter. So consider a word
$$g=au_1au_2\ldots au_k,$$ where $u_i\in\{b,c,d\}$. We proceed by induction on the length $2k$. (If $k=1$, it is not hard to check that $ab,ac,ad$ are all torsion.) We consider two cases: $k$ even and $k$ odd. If $k$ is even, then $g\in\mathrm{stab}_1$, so we can write $g=(x,y)$. But $x$ and $y$ are now both words of length $\leq k$. For example, $$abac=(aba)c=(c,a)(a,d)=(ca,ad).$$ So we have reduced to a smaller case. Now suppose that $k$ is odd. Then $g\not\in\mathrm{stab}_1$, so we can't quite do the same thing. However $g^2\in\mathrm{stab}_1$. Now $g^2=(x,y)$ where $x$ and $y$ have length $\leq|g|$, so it doesn't look like we've made progress. However, if $d$ appears as one of the letters, then the length of each $x,y$ does go down. For example, if $g=abacad$, then
$\begin{align*}
g^2&=(aba)c(ada)b(aca)d\\
&=(c,a)(a,d)(b,1)(a,c)(d,a)(1,b)\\
&=(cabad,adcab)
\end{align*}$
The point is that $d$ appears (at least) twice and parity considerations show that it puts a copy of $1$ into the first and second coordinates. Thus $g^2$ is torsion, and hence so is $g$, by induction.

If $d$ doesn't appear in $g$, then similar parity considerations will show that every appearance of $b$ in $g$ will put a copy of $c$ into $x$ and $y$, while every appearance of $c$ will put a copy of $d$ into $x$ and $y$. That is $g^2=(x,y)$ where $x$ and $y$ now have either a $c$ or $d$ in both. If there is a $d$, then $x$ and $y$ are both torsion, and so therefore is $g^2$ and $g$. If there is a $c$, then $$g^4=(x^2,y^2)=((\alpha_1,\alpha_2),(\alpha_3,\alpha_4)),$$ where $d$ appears in each $\alpha_i$, so $g^4$ is torsion here as well.

Thus we have shown that $G$ is torsion (in fact a $2$-group)!






Thursday, October 27, 2016

Niven's proof of the irrationality of Pi (Edited)

There is a beautiful short proof of $\pi$'s irrationality due to Ivan Niven, which I'd like to present here. In some sense, one could just read Niven's short one page paper, but I'd like to go over it anyway, if only to assure myself that there are no hidden details! I have presented this proof to a couple of my undergraduate classes, and I am editing this post to try to address some of the points where students tended to get confused.

As with most proofs of irrationality, we assume toward a contradiction that $\pi=a/b$ for some positive integers $a,b$. In other words, we suppose that $\pi=a/b$ and get a contradiction, i.e. a false statement. Since we get a false statement, it means that our initial assumption has to have been incorrect, and so $\pi$ cannot possibly equal $a/b$ for any $a,b$ integers.

Our strategy will be to use $a,b$ to construct a "magic" function, one so magical that it can't possibly exist! Our function will have the following two properties:
  1. $\int_0^\pi f(x)\sin x\,dx$ is a positive integer.
  2. $0<\int_0^\pi f(x)\sin x\,dx<1$
This is of course impossible, and is the desired contradiction. 

Now define the magic function to be of the form $$f(x)=\frac{x^n(a-bx)^n}{n!}$$
where $n$ is a positive integer which we will now determine. Let us look at $f(x)$ on the interval $[0,\pi]$. The biggest $x^n$ can be is $\pi^n$, whereas the biggest $(a-bx)^n$ can be is $a^n$ (when $x=0$). So $f(x)\leq \frac{\pi^na^n}{n!}$. This is a crude upper bound, it is not the exact maximum, but that's okay. Also, $f(x)>0$ when $0<x<\pi=a/b$ since one can easily see that $(a-bx)>0$ for $x<\pi$. So we have
$$ 0<\int_0^\pi f(x)\sin x\,dx \leq \frac{\pi^na^n}{n!}\cdot \pi,$$
because the integrand is bounded by $\frac{\pi^na^n}{n!}$ and the length of the interval is $\pi$. It is a calculus exercise to show that $\lim_{n\to\infty} \pi\frac{\pi^na^n}{n!}=0$. One way to solve this exercise is to note that this limit is equal to $\pi\lim_{n\to\infty} \frac{c^n}{n!}$ for $c=\pi a$, and $\sum_{n=0}^\infty \frac{c^n}{n!} =e^c$ is a power series which converges everywhere. So in particular $\lim_{n\to\infty} \frac{c^n}{n!}=0$. So now that we know the limit is $0$, we may pick a large $n$ so that $\int_0^\pi f(x)\sin x\,dx<1$ since the integral is bounded by a sequence tending to $0$. This establishes the second property we want for our "magic" function $f$.

To establish the first property, we use integration by parts to calculate  $\int_0^\pi f(x)\sin x\,dx$.
$$\begin{align*}
 \int f(x) \sin x\,dx&= -f(x)\cos x+\int f'(x)\cos x\,dx\\
&=-f(x)\cos x+f'(x)\sin x -\int f''(x)\sin x\,dx\\
&=-f(x)\cos x+f'(x)\sin x + f''(x)\cos x -\int f'''(x)\cos x\,dx\\
&\vdots\\
&=-f(x)\cos x+f'(x)\sin x + f''(x)\cos x-f''(x)\sin x+\cdots \pm f^{(2n)}(x)\cos x
\end{align*}
 $$
The reason this eventually terminates is that $f(x)$ is a polynomial of degree $2n$. So $f^{(2n+1)}(x)=0$.  We now have an antiderivative for $f(x)\sin x$, which we can use to calculate $\int_0^\pi f(x)\sin x\,dx$  by plugging in $\pi$ and subtracting off the value at $0$. Notice that all the $\sin$ terms disappear since $\sin(0)=\sin(\pi)=1$. We get
$\begin{multline*} \int_0^\pi f(x)\sin x\,dx= f(\pi)-f^{(2)}(\pi)+f^{(4)}(\pi)-\cdots\pm f^{(2n)}(\pi)\\
 +f(0)-f^{(2)}(0)+\cdots \mp f^{(2n)}(0)
\end{multline*}
$

Hence, in order to show $\int_0^\pi f(x)\sin x\,dx$ is an integer, it will suffice to show that all derivatives of $f$ evaluated at $\pi$ and $0$ are integers. In fact, it is not difficult to check that $f(\pi-x)=f(x)$ using that $\pi=a/b$ by direct algebraic computation. Taking the derivative of both sides, using the chain rule, we get:
$$\begin{align*}
f(\pi-x)&=f(x)\\
-f'(\pi-x)&=f'(x)\\
f''(\pi-x)&=f''(x)\\
&\vdots\\
(-1)^kf^{(k)}(\pi-x)&=f^{(k)}(x)
\end{align*}$$
Plugging in $x=\pi$, we get $(-1)^k f^{(k)}(0)=f^{(k)}(\pi)$. So if we can show that $f^{(k)}(0)$ are integers, then it will automatically follow that $f^{(k)}(\pi)$ are integers, since they differ only by a sign.

So, now our proof will finally be done if we can show that $f^{(k)}(0)$ are integers. There is a nice trick for computing $f^{(k)}(0)$ for polynomials $f(x)$. Taylor's theorem says the coefficient of $x^k$ is $f^{(k)}(0)/k!$, or to put it another way $$f^{(k)}(0)=k! \times \text{ coefficient of }x^k.\,\,(\dagger)$$
We can compute the coefficients of powers of $x$ in $f(x)$ using the binomial theorem. First of all, because we are multiplying by $x^n$, the powers of $x$ in $f(x)$ range from $x^n$ to $x^{2n}$. So $f^{(k)}(x)=0$ for all $k<2n$.  Now, for $0\leq d\leq n$, the term involving $x^d$ in $(a-bx)^n$ is given by $\binom{n}{d}(-bx)^da^{n-d}=\binom{n}{d}(-b)^da^{n-d} x^d$. So the coefficient of $x^{n+d}$ in $\frac{1}{n!} x^n(a-bx)^n$ is given by
$\frac{1}{n!}\binom{n}{d}(-b)^da^{n-d}$. So, by the above formula $(\dagger)$ for calculating derivatives, we have
$$f^{(n+d)}(0)=\frac{(n+d)!}{n!}\binom{n}{d}(-b)^da^{n-d}.$$
This is an integer because $\frac{(n+d)!}{n!}=\frac{(n+d)(n+d-1)\cdots (n+1)n(n-1)\cdots 1}{n(n-1)\cdots1}=(n+d)(n+d-1)\cdots (n+1)$ is an integer. 

So in summary, the polynomial $f(x)$ only has nonzero derivatives $f^{(k)}(0)$ for $n\leq k\leq 2n$ and these derivatives have the explicit form given in the above formula, establishing that they are integers.

 It would be interesting to figure out exactly what was needed about $\pi$ to make this argument work. Can it be modified to show other numbers are irrational?

Edit: Matt Baker's Blog has a discussion on how to generalize this in a motivated way.  



Wednesday, October 26, 2016

Burnside Problems

I am sitting in on a nice class given by Efim Zelmanov at UCSD and I thought I'd talk a little bit on this blog about some of the stuff he has covered. This post will be about the Burnside problems:

Generalized Burnside Problem: Suppose that $G$ is a finitely generated group where every element has finite order. Is $G$ a finite group?

Burnside Problem: Suppose that $G$ is a finitely generated group, such that there exists an $N$ for which $g^N=1$ for all $g\in G$. Is $G$ finite?

It turns out that the answer to both these questions is no, and in this blog post we will explore how using a detour through the theory of algebras will help us settle this question!

In 1941, Kurosh formulated the following question. Suppose that $F$ is a field, $A_F$ is an associative $F$ algebra (not assuming a unit) and that $A$ is finitely generated. An element $a\in A$ is said to be nilpotent if $\exists n\geq 1 \,\,a^n=0$, and an algebra is called a nilalgebra if all of its elements are nilpotent. The Kurosh problem is

Kurosh nilalgebra problem: Is every finitely generated nilalgebra finite dimensional?

Kurosh noticed that if there is a counterexample to this question for a field of positive characteristic, then there is a counterexample to the Generalized Burnside Problem. Here is the argument for that.

Theorem: If there is a counterexample to the Kurosh problem, there is counterxample to the generalized Burnside problem.
 [Proof]
Suppose that there is some finitely generated infinite-dimensional nilalgebra over $F$ where $\mathrm{char}(F)=p>0$. Let $A=\langle a_1,\ldots, a_m\rangle$ be such an example. Let $\hat{A}=A\oplus F\cdot 1$ be the unital hull of $A$: the algebra you get by adding a unit. (Since $A$ was nil, it couldn't possibly have had a unit to begin with!) Now notice that for all $a\in A$, $1+a$ is invertible since $1-a+a^2-a^3+\cdots$ is a finite sum and an inverse. Thus $1+a\in G(\hat A)$, the group of units of $\hat A$. Consider the subgroup of the group of units
$$G=\langle 1+a_1,\ldots,1+a_m\rangle\subset 1+A\subset G(\hat{A}).$$
Now every element in $1+A$ is torsion: we know there is some $n(a)$ where $a^{n(a)}=0$. Choose $k$ so that $p^k\geq n(a)$. Then $$(1+a)^{p^k}=1+a^{p^k}=1$$ since we are in characteristic $p$. Therefore $G$ is a finitely generated torsion group. If we can show it is infinite, we have a counterexample to the Generalized Burnside Problem.

Suppose to the contrary that $|G|=d$. Let $g_1\ldots g_d$ be a product of elements of $G$. Then $\{1,g_1,g_1g_2,\ldots,g_1\ldots g_d\}$ is a set of $d+1$ elements, and by the pigeonhole principle two of the elements must coincide: say $g_1\ldots g_i=g_1\ldots g_j$ $(j>i)$. Then $g_{i+1}\ldots g_j=1$. So we can remove a segment from the original word $g_1\ldots g_d$ without changing the group element it represents. In particular any element of $G$ is a product of $<d$ generators (we don't need inverses because the group is torsion).
In other words,
$$\forall g\in G\,\, g=(1+a_{i_1})\cdots (1+a_{i_k})\,\,\,\,(k<d)$$
But now consider an arbitrary product of $d$ generators of $A$: $a_{i_1}\ldots a_{i_d}$. Then
$$(1+a_{i_1})\cdots (1+a_{i_d})=(1+a_{j_1})\cdots(1+a_{j_k})\,\,\,\, k<d.$$
Now expanding this out, we see that $a_{i_1}\ldots a_{i_d}$ is a linear combination of products of generators of length $<d$. This implies $A$ is finite dimensional, which is a contradiction. $\Box$

So it now suffices to find a counterexample to the Kurosh problem. We begin with some graded algebra conventions. Let $F\langle X\rangle$ be the free associative algebra on a finite alphabet $X=\{x_1,\ldots ,x_m\}$. This is graded by length of words:
$$F\langle X\rangle =F\cdot 1+F\langle X\rangle_1+F\langle X\rangle_2+\cdots$$.
 We say a subspace $H\subseteq F\langle X\rangle$ is graded if $H=\sum_i(H\cap F\langle X\rangle_i)$. If $R$ is a graded subspace, we can form the quotient algebra $\langle X\,|\, R=(0)\rangle$. Then since the ideal generated by $R$, $I=\mathrm{id}(R)$, is also graded, the factor algebra $$A=F\langle X\rangle/I=F\cdot 1+A_1+A_2+\cdots$$ is graded as well. (Note we assume all relations have degree $\geq 2$.)

Definition: Given a graded vector space $V=\oplus_{i\geq 0} V_i$ in which each graded summand is finite dimensional, define the Hilbert series $H_V(t)=\sum_{i\geq 0} (\mathrm{dim} V_i)t^i$. Note this is a formal power series.

We can order formal power series lexicographically by coefficients.

Proposition (Golod-Shafarevich): In the situation above, $$H_A(t)(1-mt+H_R(t))\geq 1,$$ where the comparison is of formal power series.

We will come back to the proof of this proposition at the end of the post. According to Zelmanov, it was given to Golod as a homework problem by Shafarevich!

Now, suppose that the proposition is true, and moreover suppose that we can find a $t_0$ with $0<t_0<1$ such that
  1. $H_R(t_0)$ converges.
  2. $1-mt_0+H_R(t_0)<0$.
Then the above proposition shows that $H_A(t_0)$ does not converge, so that $A$ must be infinite. (The formal inequality implies the numerical inequality when both sides converge.)

The construction of a finitely generated nilalgebra which is infinite dimensional:

Let $F$ be a countable field. Then the free algebra on $X$ without identity is also countable:
$$F_0\langle X\rangle =\{f_1,f_2,\ldots,\}.$$
Let $d_1=2$. Let $d_2>\mathrm{deg}(f_1^{d_1})$, and $d_3>\mathrm{deg}(f_2^{d_2})$ etc. Let $R$ be the set of homogeneous components of $f_i^{d_i}$. By choice of the $d_i$'s, every degree occurs no more than once.

Therefore $H_R(t)\leq t^2+t^3+\cdots$, and so $H_R(t)$ converges when $0<t<1$. In order to satisfy the criterion 2. above, we need $1-mt_0+H_R(t_0)<0$, which will be satisfied if
$1-mt_0+t_0^2+t_0^3+\cdots<0$ for some $0<t_0<1$. This is an easy precalculus exercise!

So the algebra $A=\langle F_0\langle X\rangle\,|\, R=(0)\rangle$ is infinite dimensional. Moreover it is nil by construction. Every element of $F_0\langle X\rangle$ has a power which is trivial.

Returning to the proof of the Golod-Shafarevich inequality:

Let $r_i=\mathrm{dim}(R_i), \mathrm{dim}(A_i)=a_i$ and, letting $I=\mathrm{id}(R)$, $b_i=\dim(I_i)$. Note that $a_i+b_i=\mathrm{dim} F_0\langle X\rangle_i=m^i$. The Golod-Shafarevich inequality can now be rewritten as
$$
a_n-ma_{n-1}+\sum_{i+j= n} a_ir_j\geq 0
$$

We use the following basic observation: $I\subseteq XI+RF\langle X\rangle$. This follows since a general element of $I$ is a linear combination of elements of the form $u_iRv_i$. If $R$is not at the left of the word, then $u_iRv_i\in XI$. Otherwise, it is in $RF\langle X\rangle$. Now choose a complementary graded subspace $S$ so that $F\langle X\rangle=I+S$. Then $\mathrm{dim}(S_i)=a_i$. Moreover, we can now say
$$I\subseteq XI+RS$$
Thus $b_n\leq mb_{n-1}+\sum_{i+j=n}r_ia_j$, which is $$(m^n-a_n)\leq m(m^{n-1}-a_{n-1})+\sum_{i+j=n}r_ia_j,$$
which is equivalent to the desired inequality.





Wednesday, October 28, 2015

A beautiful solution to a math contest problem

I was recently involved in writing a math contest at my university. One of the problems I contributed was the following:

Let $L$ be the line passing through points $(\sqrt{2},0)$ and $(0,\sqrt{2})$ of the XY -plane. Let $C_0$ be the circle of radius 1 centered at (0, 0). Let $C_1, C_2, C_3,\ldots $ be an infinite sequence of circles such that each $C_i$  is centered on the x-axis, each $C_i$ is tangent to $L$ and $C_{i+1}$ is tangent to $C_i$ for all $i\geq 0$. What is the total area of all these circles? 

The solution I had in mind was to find a recursive formula for the radius of $C_i$ and then sum the areas as a geometric series. One student came up with an absolutely stunning method, worthy of Archimedes. Consider the trapezoid $T_0$ formed from the $x$-axis, the line $L$ and the two vertical tangents to $C_0$. The area of the trapezoid is $2\sqrt{2}$ while the area of $C_0$ is $\pi$. So the ratio $\lambda$ of the area of $C_0$ to the area of $T_0$ is $\frac{\pi}{2\sqrt{2}}$. Now observe that the ratio of the area of $C_i$ to the area of the trapezoid $T_i$ formed from the vertical tangents to $C_i$, the line $L$ and the $x$-axis, is still $\lambda$ by similarity. So $$\sum \mathrm{Area}(C_i)=\lambda \sum \mathrm{Area}(T_i).$$
The sum of the areas of $T_i$ is just the area of an isosceles right triangle with side lengths $1+\sqrt{2}$, i.e. $\frac{(1+\sqrt{2})^2}{2}$. So we get $\frac{\pi}{2\sqrt{2}}\cdot \frac{(1+\sqrt{2})^2}{2}$. Magic!

Monday, October 12, 2015

More on Tiling Problems

This post continues my previous post. Here is, amazingly, an open problem.

Let the order of a tile be the smallest number of tiles that tiles a rectangle (of any size).

Conjecture (Klarner): The only tiles of odd order are rectangles (so have order $1$.)

It's actually a little difficult to find any tilings of a rectangle with an odd number of tiles, but it can be done. Assume now that our tiles are not themselves rectangles. The smallest known odd rectangular tiling has $11$ tiles. It is known that no tiling with $3$ tiles is possible. It's an interesting exercise to pack a 5x9 rectangle with L-shaped tiles with $3$ cells. I encourage you to try it!

In the last post, I defined tile homology $H(\mathcal T)$ for a given tile set $\mathcal T$. When I was talking about this with Morwen Thistlethwaite, he asked

Question (Thistlethwaite): Which abelian groups can be realized as tile homology groups?

This is an interesting question without an obvious answer!

Tile homology groups are actually the abelianization of tile homotopy groups $\pi(\mathcal T)$, first introduced by Conway and Lagarias. The idea here is to think of the boundaries of tiles (oriented counterclockwise) as paths in the square lattice. If we think of $x$ as meaning move one unit up and $y$ as moving one unit to the right, then every tile $t$ produces a conjugacy class $w(t)$ of words in the free group $F_2=\langle x,y\rangle$. One needs to look at conjugacy classes because different  starting points on the tile boundary will produce conjugate words. Moreover, if we fix the origin as the basepoint, different tile placements in the plane will give conjugate boundary words when we connect the boundary by a path back to the basepoint.

Let $b(\mathcal T)$ be the subgroup of $F_2$ normally generated by  $\{w(t_1), \ldots, w(t_k)\}$.

Theorem (Conway-Lagarias): If $\mathcal T=\{t_1,\ldots, t_k\}$ is a tile set which tiles the region $R$, then the boundary word $\partial R$ lies in $b(\mathcal T)$.

The idea of the proof is that $R$ is glued together from copies of tiles, so reading around the boundary of $R$ will be equivalent in $F$ to reading around the boundaries of the tiles which tile $R$. Thus it is a product of conjugates of boundaries of these tiles.

Let $\mathcal P(\mathcal T)=F_2/b(\mathcal T)$ be the path homotopy group $\mathcal P(\mathcal T)$. Then $\partial R\in \mathcal P(\mathcal T)$ gives an obstruction to tiling $R$ by tiles from $\mathcal T$.

The closed paths in the infinite grid correspond to commutators, and so the tile homotopy group $\pi(\mathcal T)$ is defined to be $[F_2,F_2]/b(\mathcal T)$.

Example: If $\mathcal T$ consists of the two orientations (vertical and horizontal) of an $n\times 1$ tile, then $\pi(\mathcal T)\cong F_{(n-1)^2}$, the free group on $(n-1)^2$ generators.

Example (Reid): If $\mathcal T$ consists of the $+$-shaped pentomino and the two orientations of a $1\times3$ tile, then $\pi(\mathcal T)$ is a finite group of order $120$. It is a $\mathbb Z_2$ extension of $A_5$.

In particular, Reid uses this last example to show that any rectangle tiled by the $+$-pentomino and $1\times 3$ tiles must have a side length divisible by $3$.

Friday, October 9, 2015

Tiling problems

I wanted to talk about some interesting work I uncovered while chasing a particular math.stackexchange problem down the rabbit hole. The setting will be an infinite square grid. The squares within the grid will be called "cells."

A tile is a connected (normally also simply connected) union of cells, where two tiles that are translations of each other are considered equivalent. Unless otherwise noted, we will also include rotations and reflections as equivalent.

A region R is a finite union of cells.

We will concern ourselves with the following problem. Given a tile set $\mathcal T=\{t_1, \ldots, t_k\}$, can a region $R$ be tiled with elements of $\mathcal T$. In other words can $R$ be represented as a disjoint union of placements of the tiles from $\mathcal T$?

The canonical example of this phenomenon is the $8\times 8$  chessboard with opposite corners removed. Can it be tiled by two element tiles (dominos)? The standard method is to note that in the resulting region, there are $30$ tiles of one color and $32$ of the other. Yet every domino must cover both a black and a white square. So the number of black squares covered by the dominoes must equal the number of white squares covered by the dominoes, and therefore the dominoes can't cover $R$.

Here is a trickier example:

Theorem (Klarner 1969): An $a\times b$ rectangle can be tiled by $1\times n$ tiles if and only if
$n|a$ or $n|b$.
[Proof]
The "if" direction is obvious, as one can take all tiles to be oriented in the same direction.

For the "only if" direction, suppose that $n\!\not |a$. Then $a=qn+r$ for some nonnegative integer $q$ and remainder $1\leq r<n$. Suppose the rectangle $R$ is placed in the plane with its bottom edge of length $a$. Color the columns of $R$ with $n$ different colors, cycling back to the start. In other words, the color of the $i$th column is the residue class of $i$ modulo $n$. Let $c_i$ be the number of cells colored by the $i$th color. The number of vertical stripes colored by colors $1,\ldots, r$ is $q+1$, while the number colored by $r+1,\ldots, n$ is $q$. So $c_1=\ldots=c_r=(q+1)b$ and $c_{r+1}=\ldots=c_n=qb$.

Now consider what happens when you place a vertically oriented tile in $R$. It will cover $n$ cells of the same color, so modulo $n$ it covers $0$ cells of each color. On the other hand a horizontally placed tile in $R$ will cover one cell of each color. So, if $h$ is the number of horizontally oriented tiles in some tiling of $R$, we must have $c_i\equiv h\bmod n$. Therefore $c_1\equiv c_2\equiv\cdots\equiv c_n\bmod n$. By our count above, this means $(q+1)b\equiv qb \bmod n$. Subtracting $qb$ from both sides yields $b\equiv 0\bmod n$. So we have shown that $n\!\not |a$ implies $n|b$. $\Box$

Here is another example, due to Michael Reid.
Example: Let $R$ be the $10\times 10$ square and let $\mathcal T$ consist of the different orientations of the $L$-shaped tetromino. Then $R$ cannot be tiled by $\mathcal T$.
[Proof]
Color the columns alternating with the numbers $1$ and $5$. Note that any placement of the tile will contain three $1$'s and one $5$ or three $5$'s and one $1$. In both cases, the numbers sum to $0$ modulo $8$. On the other hand the sum of numbers in $R$ is equal to $50\cdot 1+50\cdot 5\equiv 4\bmod 8$. $\Box$

Tile Homology
The previous example can be systematized into a universal invariant, called tile homology, defined for every tile set. Coloring arguments can then be extracted from this.

Let $A$ be the free abelian group on generators $a_{i,j}$ $i,j\in\mathbb Z$ for every cell in the grid. $A$ can be thought of as the set of numberings of the cells in the grid which are only nonzero in finitely many places. If $\mathcal T$ is a tile set, define $B(\mathcal T)$ to be the subgroup of $A$ generated by filling in the cells of all possible tile placements with $1$'s. The tile homology group is defined as
$$H(\mathcal T)=A/B(\mathcal T).$$

Theorem: If $R$ can be tiled by $\mathcal T$, then $[R]=0\in H(\mathcal T)$, where $[R]$ is the assignment $1$ to all cells in $R$, and $0$ to other cells.
 [Proof]
The proof is trivial. $\Box$

Examples:
  1.  If $\mathcal T$ consists of $1\times n$ and $n\times 1$ tiles, $H(\mathcal T)=\mathbb Z^{(n-1)^2}$.
  2.  If $\mathcal T$ consists of the $L$-shaped tile of height $2$ and width $n$, we have $$H(\mathcal T)=\begin{cases} \mathbb Z/(n+1)\mathbb Z&\text{if } n \text{ even}\\ \mathbb Z\oplus \mathbb Z/(n+1)\mathbb Z &\text{if } n\equiv 3\bmod 4\\ \mathbb Z\oplus \mathbb Z/ \frac{1}{2}(n+1)\mathbb Z&\text{if } n\equiv 1\bmod 4 \end{cases}.$$
Let's prove the first one. Take a horizontally oriented tile and subtract off another one which is displaced one unit to the right. Then $a_{i,j}-a_{i+n+1,j}\in B(\mathcal T)$. Similarly, $a_{i,j}-a_{i,j+n+1}\in B(\mathcal T)$. Thus, the generators $a_{i,j}$ in the $n\times n$ square $1\leq i,j\leq n$ are generators for $H(\mathcal T)$. To determine the relators, consider a tile in the plane. Using the two relations we derived above, we can translate it so that it overlaps the $n\times n$ square. Say it is horizontal, and jutting off the right end. Then, using the translation relations, we can translate the part jutting off the right $n$ units to the left. Thus the relation becomes that the sum of the squares in a row is $0$: $$a_{i,j}+\ldots a_{n,j}=0$$ Similarly the sum of squares in a column is $0$: $$a_{i,1}+\ldots a_{i,n}=0.$$ The result is a free abelian group of rank $(n-1)^2$.

The technique of proof in this case is pretty general. The idea is to find some simple relations as differences of differing tile placements, that allows you to push everything into a finite region. Then push the relators into this region as well to get a  presentation of the group. There are cases where the group is infinitely generated, however.

The proof of the second calculation is a bit tedious and not included here.

Theorem (Reid 2003): If $R\neq 0\in H(\mathcal T)$, there exists an additive homomorphism $\psi\colon A\to\mathbb Q$ such that $R\mapsto \mathbb Q\setminus\mathbb Z$, but every tile placement evaluates to an integer.
[Proof]
If $R\in H(\mathcal T)$ has finite order $n$ define $\phi\colon \langle R\rangle\to \mathbb Q/\mathbb Z$ by sending $R\mapsto 1/n$. (Here $\langle R\rangle$ denotes the subgroup generated by $R$. Otherwise let $R\mapsto 1/2$. Then $\phi$ extends to a map $\phi\colon H(\mathcal T)\to \mathbb Q/\mathbb Z$, since $\mathbb Q/\mathbb Z$ is a divisible group. Then the composition $A\to H(\mathcal T)\to\mathbb Q/\mathbb Z$ lifts to a map $\psi\colon A\to \mathbb Q$, since $A$ is a free abelian group. Now by definition, $\psi(R)=\frac{1}{n}+k$ or $\frac{1}{2}+k$ for some $k\in \mathbb Z $, but any tile placement $t$ maps to $0\in H(\mathcal T)$ and so $\psi(t)\in\mathbb Z$. $\Box$

In the $n\times 1$ case, let $\phi\colon H(\mathcal T)\to \mathbb Q/\mathbb Z$ be defined by sending $a_{1,1}\mapsto \frac{1}{2}$ and all other $a_{i,j}\mapsto 0$, $1\leq i,j\leq n-1$. Lifting this to $\psi\colon A\to \mathbb Q$ gives an assignment in the plane of
$$a_{i,j}\mapsto
\begin{cases} \frac{1}{2} &\text{ if } i,j\in\{0,1\} \bmod 8\\
 0& \text{otherwise} \end{cases}
$$
This coloring gives an alternate proof of Klarner's theorem. Any placement of a tile will hit $0$ or two $1/2$-colored cells, so will evaluate to an integer. On the other hand a rectangle evaluates to an integer iff one of its side lengths is divisible by $n$. If you place the rectangle so that $a_{1,1}$ is its lower left corner, then most of the colored squares come in clumps of $2$ or $4$, with the possible exception of corner squares. If neither $a$ nor $b$ is divisible by $n$ then the other three corners do not contain isolated colored squares, so the total number is odd. This is a contradiction.
See my argument (and picture) here.
$\Box$

References:
  1. Klarner (1969) Packing a rectangle with congruent $n$-ominoes.
  2. Conway-Lagarias (1990) Tiling with polyominoes and combinatorial group theory
  3. Reid (2003) Tile homotopy groups