## Decisions With A Coin

What kind of decisions can we (or can’t we) make with a simple fair coin?

## #3: Generating functions and Fibonacci Numbers

This one goes a little deeper, I think, than the previous videos. I introduce one of childhood’s most famous sequences of numbers and find the fairly well-known (these days – as a child I had no access to the web and so the sequence remained a mystery) closed form for the nth Fibonacci number.

As always, do please comment with suggestions/feedback/glowing praise :)

## The Two Marbles Problem

Here we try to design an efficient (in terms of worst-case) algorithm for determining the strength of two marbles.

As usual all feedback is welcome.

## My First Maths Video

While this is not technically the first time I’ve been videoed talking about maths, it’s the first time I’ve published such a video.

It’s an experiment in which i film a bit of paper (almost like a Lectopia) and talk briefly about the Two Envelopes Paradox.

All feedback is encouraged PLEASE! Technical, stylistic, length. Let me know in the comments if you have feedback or ideas for more things I can talk about.

Posted in Uncategorized | 1 Comment

## Quokka Theory 1 – the Weyl Group

Looking back on the post “Signed Permutations” it seems a mite isolated, and some context might be of use. Also, I need to write about Quokka Theory in my thesis, and have decided this is as good place as any to experiment with exposition. So here goes.

A critical Theorem in counting subsets of classical groups is Niemeyer & Praeger’s Quokka Theorem, which gives a wonderful formula for counting subsets having nice properties. To be specific:

A subset $Q$ of a classical group (specifically, a set of fixed points of a Frobenius map of a connected, reductive algebraic group over an algebraically closed field) is called a quokka set if the following two properties hold:
1) $Q$ is closed under conjugation; and
2) for every $g\in Q$, the semisimple part $s$ of $g$ is in $Q$.

That is to say, membership of $Q$ depends only on its semisimple part in its Jordan-Chevalley Decomposition.

with this definition, the main theorem of Quokka Theory states that

$\frac{|Q|}{|G|} = \sum \frac{|C|}{|W|} \frac{|Q\cap T_C|}{|T_C|}$

Where the sum is over “conjugacy classes in the Weyl group $W$“, $C$ is such a class, and $T_C$ is a representative maximal Torus of a class of Tori in $G$ corresponding to $C$. Now I am very aware of how unenlightening this formula is with so much ill-explained notation, and I suppose that is the point of what will become a series of posts. In the meantime, simply know that computing $\frac{|C|}{|W|}$ and $\frac{|Q\cap T_C|}{|T_C|}$ is easy in comparison to finding the size of $Q$ directly – the Signed Permutations post is an example of the former, while the latter is counting in an abelian group – and so this formula should be considered the goal rather than the starting point.

But first, we will need to understand Tori and the correspondence between conjugacy classes of F-stable maximal tori and F-conjugacy classes in the Weyl group. And before that, we’ll need to talk about the Weyl group. I’ll be following Carter, the standard reference for this kind of thing.

So what exactly is a Torus anyway?
To deal with this we have to talk a little about Algebraic Groups (but not too much). An algebraic group is very tough to define, but we can deal with Linear Algebraic Groups, which are essentially just subgroups of the General Linear Group over an algebraically closed field – the Complex Numbers are a good example of an algebraically closed field (every polynomial has a root), but for us, we are trying to get to a Finite field $\mathbb{F}_q$, and so we need to begin with an algebraically closed extension of that, which we denote $\bar{\mathbb{F}_q}$. Imagine a finite field, only not finite… it looks a bit like an infinite-dimensional $\mathbb{F}_q$-vector space.

So we begin with a connected reductive algebraic group over $\bar{\mathbb{F}_q}$ (think $GL,Sp,O,U$…) – how do we get our finite group back? It’s with the Frobenius Automorphism. Raising elements of a field of characteristic $p$ to the power $p$ is an automorphism (this follows from Fermat’s Little Theorem I suppose, and since all the terms bar the first and last in the binomial expansion have $p$ dividing them), and so raising everything to the $q$th power is an automorphism of $\bar{\mathbb{F}_q}$. The fixed points of this map? Precisely the finite field ${\mathbb{F}_q}$. We call this $q$th power map $F$ (after Frobenius himself).

The Frobenius map can act on our Algebraic Group $G$, too, usually looking like raising each entry of a matrix to the $q$th power, too (there are exceptions which we will meet later). We denote by $G^F$ the fixed points of this map: THIS is our finite group of Lie Type.

Then what’s our Torus? Well, by definition, they are groups of the form $\bar{\mathbb{F}_q}^* \times \bar{\mathbb{F}_q}^* \times \ldots \times \bar{\mathbb{F}_q}^*$, a direct product of some copies of the multiplicative group of the field. in the case of $GL$ maximal tori, then, look like diagonal matrices, and SINCE the field is algebraically closed, a maximal torus (as in, a torus not properly contained in another torus) is always conjugate to the subgroup of diagonal matrices. In the Special Linear Group every maximal torus is conjugate to the set of diagonal matrices with determinant 1 (and so as an abstract group looks like $n-1$ copies of the multiplicative group of the field. In every case, the maximal tori are all conjugate in $G$.

So what’s the Weyl group? Well, the Weyl group of a particular torus is the quotient $N(T)/C(T)$ – for beginners, this all depends on how conjugation affects things. The normaliser of $T$ (in $G$) is the set of all $g\in G$ such that the image $T^g:=\{ g^{-1}tg \mid t\in T\}$ is equal to $T$. That is, if you let an element of $N(T)$ act on an element of $T$, the result is still in $T$. The centraliser is more restricted: it consists of all the elements that fix $T$ pointwise in this action. So $t^g=t$. The centraliser is normal in the normaliser, and so we can take a quotient, which is called the Weyl group of $T$.

The Weyl group of $G$ is defined to be the Weyl group of a maximal torus – remember that they are all conjugate and so this group is always the same (as an abstract group only – it depends on the choice of torus, but the result is always isomorphic).

But you know me, I hate quotient groups because it’s never quite clear what they’re acting on! so we need an action for $W$. And for that……STAY TUNED.