Monday, April 16, 2012

You should re-read the stuff you think you know.

I started my PhD in June 2011. While I've only worked on a few problems since then, a pattern is emerging: I always spend a couple months stuck on something that looks obvious and silly (both in fore- and hindsight.) Most recently I was stuck on a problem involving basic arithmetic over finite fields. I felt that it was something I should be able to do, but nonetheless was stuck on it for a few weeks.

Maybe it's that I'm doing the PhD thing wrongly, or maybe it's that I'm not spending enough time on my mathematics (I've got a job doing predictive modeling, too!). In any case, the story of how I got unstuck might interest some people:

I've thought it important to continue doing maths reading independent of my research projects. But while there are several subjects I wish to learn about (and do research in), I have not engaged in much outside study. When I approach a subject, I have two separate reactions: Either I find that the subject is too advanced, and I give up quite early - not wanting to get lost in background material. Or I think the material I have repeats too much of stuff I already know, and I give up - not wanting to waste my time on things I've seen before.

After doing this for a few months, I decided that I should read something that I think I already know - just to get in the habit of things. I started reading the field/Galois theory chapters in the abstract algebra book by Dummit and Foote. Pretty light reading as far as mathematics goes. It's stuff I should know.

Those chapters contain some straightforward proofs of basic statements on algebraic field extensions. Exempli gratia, if $\mu$ is the root of a polynomial $f$, and $\sigma$ is an element of the Galois group, then one can prove that $\sigma(\mu)$ is also a root of the polynomial by observing the action of $\sigma$ on the polynomial $f$. Not particularly new or deep material, but it turns out just the stuff I needed...

Now back to my problems with arithmetic over finite fields: I've spent the last few weeks trying to decompose an operator on polynomials into separate components. My supervisor and I both had our own ideas of writing out matrices for these operators. I spent a few late nights on it, wrote down some messy results, and went to bed hoping I'd have an epiphany on how to clean it up. I had been hoping for one for weeks! But soon after I started re-reading the basics I got it. I was just reading about applying the action of the Galois group to polynomials, and here I was staring at an operator on polynomials. So I abandoned the ``matrix approach'', naively started looking at the action of the Galois group, and a few minutes later I had the result I was looking for. It seemed so obvious in hindsight, but it often seems obvious only after you've understood it.

I should probably keep reading the basics.

Sunday, April 15, 2012

Cohomology of Finite Fields Part III

I gave a proof (with help from math.stackoverflow) in my last blog for the 0th cohomology of the field extension ${\mathbb{F}_4/\mathbb{F}_2}$. While I have sketches for descriptions of ${H^0(\mathbb{F}_{p^m} / \mathbb{F}_p)}$ for any prime ${p}$ and positive integer ${m}$, I've not yet been able to describe ${H^1}$ for even the simplest cases. I shall describe the problem in this post.

First, recall that I mention in my first post on NCG cohomologies of field extensions that a first order differential calculus gives rise to a differential graded algebra. Let's briefly describe this:

Given our [possibly noncommutative] algebra ${A = \Omega^0}$, we've already described it's first order differential calculus as an ${A}$-bimodule ${\Omega^1}$ together with a linear map ${d: \Omega^0 \rightarrow \Omega^1}$ that obeys the rules 1) ${d(ab) = a \cdot db + da \cdot b}$ (where ${\cdot}$ is the action of the algebra on the bimodule) and 2) ${\Omega^1 = \{a \cdot db : a, b \in \Omega^0\}}$. The differential graded algebra is then defined as graded algebra ${\Omega = \bigoplus_n \Omega^n}$ together with the map ${d : \Omega^n \rightarrow \Omega^{n+1}}$ and the rules: ${\Omega^0 = A}$, ${\Omega^1}$ as before, ${d^2 = 0}$, and ${\Omega}$ generated by ${\Omega^0}$ and ${\Omega^1}$. The product of the differential graded algebra is the wedge product ${\wedge}$, as in classical differential geometry.

Putting the above together, we get a complex ${A = \Omega^0 \xrightarrow{d^0} \Omega^1 \xrightarrow{d^1} \ldots}$. Here ${d^n}$ is the restriction ${d^n = d |_{\Omega^n}}$. The cohomology is then defined as ${H^n(A) = \text{ker}(d^n)/\text{Im}(d^{n-1})}$, with ${H^0(A) = \text{ker}(d^0)}$ as we saw in the last two posts.

In our case of the field extension ${\mathbb{F}_4/\mathbb{F}_2}$, we have as our algebra the polynomial ring ${A = \mathbb{F}_2[x]}$. We've already defined a differential calculus on it, the polynomial ring ${\Omega^1 = \mathbb{F}_4[x]}$, where ${\mathbb{F}_4 = \mathbb{F}_2(\mu)}$, together with the differential map ${df = \frac{f(x + \mu) - f(x)}{\mu}}$. Using this, how can we describe the differential graded algebra ${\Omega = \bigoplus_n \Omega^n}$ ?

First, recall that ${\mathbb{F}_4}$ is a two dimensional vector space over ${\mathbb{F}_2}$ with basis ${\{1, \mu\}}$. This means that the polynomial ring ${\Omega^1}$ can be ``spanned'' by ${\{1, \mu\}}$ over the polynomial ring ${\mathbb{F}_2[x]}$. In other words, every ${f \in \Omega^1}$ can be written as ${f = f_1 \cdot 1 + f_\mu \cdot \mu}$, with ${f_1, f_\mu \in \Omega^0}$. In order for us to get a graded algebra, ${\Omega^2}$ must have a basis ${\{1 \wedge \mu\}}$, hence it's a one dimensional space over ${\Omega^0}$ and thus is isomorphic to ${\Omega^0}$. ${\Omega^n = 0}$ for ${n > 2}$, as we're using a classical anticommutative wedge product.

But what is the map ${d^1: \Omega^1 \rightarrow \Omega^2}$ ? Well, from our description of ${\Omega^1}$, we can easily express the action of ${d}$ on ${\Omega^1}$ as an action on ${\Omega^0}$, which is well defined. Id est, for ${f \in \Omega^1}$,

$\displaystyle d^1 f = d^0(f_1) \wedge 1 + f_1 \wedge d^0(1) + d^0(f_\mu) \wedge \mu + f_\mu \wedge d^0(\mu)$

Now, ${d^0(a) = 0}$ for any constant polynomial, and ${d^0(g) \in \Omega^1}$ for any ${g \in \mathbb{F}_2}$. So ${d^0g = \partial_1 g \cdot 1 + \partial_\mu g \cdot \mu}$. Hence we have linear maps ${\partial_1, \partial_\mu : \mathbb{F}_2[x] \rightarrow \mathbb{F}_2[x]}$. We return to ${d^1}$ using this idea:

$\displaystyle d^1 f = (\partial_1 f_1 \cdot 1 + \partial_\mu f_1 \cdot \mu) \wedge 1 + (\partial_1 f_\mu \cdot 1+ \partial_\mu f_\mu \cdot \mu) \wedge \mu$

The wedge product is anticommutative, so this leaves us with:

$\displaystyle d^1 f = (\partial_1 f_\mu - \partial_\mu f_1) \cdot 1 \wedge \mu$

And ${d^2 f = 0}$, as the rest of the ${\Omega^n}$'s are 0. Now back to the cohomologies: ${H^1(\mathbb{F}_4/\mathbb{F}_2) = \text{ker}(d^1)/\text{Im}(d^0)}$, where ${\text{ker}(d^1) = \{f \in \Omega^1 : \partial_1 f_\mu = \partial_\mu f_1 \}}$ and ${\text{Im}(d^0) = \{f_1 \cdot 1 + f_\mu \cdot \mu \in \Omega^1 : \exists f \in \mathbb{F}_2[x] \; \text{such that} \; df = f_1 \cdot 1 + f_\mu \cdot \mu\}}$. Hence the we need to find a description of the ``partial derivatives'' ${\partial_1}$ and ${\partial_\mu}$. In other words, we need to describe ${d^0f}$ as:

$\displaystyle \frac{f(x + \mu) -f(x)}{\mu} = \partial_1 f + \partial_\mu f \cdot \mu$

By noting that ${\mu^3 = 1}$, I was able to write down a formula for ${\partial_i x^{3n}}$, and then formulas for ${\partial_i x^{3n+1}}$ and ${\partial_i x^{3n+2}}$ in terms of ${\partial_i x^{3n}}$. But the binomial expansion makes these formulas just too messy to work with. I then tried finding a basis under which the maps would have a nice, neat formula, but I had no luck there. Next I tried looking at the action of the Galois group on $d$.

Now, the only non-trivial element of the $\text{Gal}(\mathbb{F}_4/\mathbb{F}_2)$ is the Frobenius automorphism $\sigma(x) = x^2$, exempli gratia, $\sigma\mu=\mu^2=\mu+1$. The action of the Galois group extends to an action on the polynomial ring - one that leaves $\mathbb{F}_2$ fixed. Hence we have

$\displaystyle \sigma d f = \sigma(\partial_1 f) + \sigma(\partial_\mu f \cdot \mu) = \partial_1 f + \partial_\mu f \cdot (\mu + 1) = df + \partial_\mu f$

This allows us to write the ``partial derivatives'' in terms of $d$ and the Frobenius automorphism. Id est,

$\displaystyle $$\partial_\mu f = \sigma (d f) - d f$


$\displaystyle \partial_1 f = df - \sigma(d f) \mu + (df) \mu$

It remains to be seen if these formulas for the partials will actually help me calculate the remaining cohomologies.

Wednesday, April 11, 2012

Cohomology of Finite Fields Part II

Last time we described a theory of cohomology for finite field extensions, but we fell short of calculating ${H^0(\mathbb{F}_4 / \mathbb{F}_2)}$ as I had discovered a mistake in my proof shortly after I had posted the blog. Thanks to the kind folks on math.stackoverflow I have a correct proof (and result!). Let's go through it.

Recall that ${H^0(\mathbb{F}_{4} / \mathbb{F}_2) = \text{ker}(d)}$, where ${\mathbb{F}_{4} = \mathbb{F}_2(\mu)}$, ${\mu}$ a root of a monic irreducible polynomial of degree ${2}$ in ${\mathbb{F}_2}$, and

$\displaystyle d: \mathbb{F}_2[x] \rightarrow \mathbb{F}_{4}[x] \; \text{by} \; df = \frac{f(x + \mu) - f(x)}{\mu}$

Hence ${H^0(\mathbb{F}_{4}/\mathbb{F}_2)}$ is the set of all polynomials ${f \in \mathbb{F}_2[x]}$ such that ${f(x + \mu) = f(x)}$. To find it, first note that if ${f(x) \in H^0}$, then so is ${g(f(x))}$ for any ${g \in \mathbb{F}_2[x]}$, as ${g(f(x + \mu)) = g(f(x))}$. If we can show that some polynomial ${f}$ is the only polynomial in ${H^0}$ with smallest degree, then we know that every other ${g(f(x)) \in H^0}$ is spanned by ${\{f(x)^n : n\in \mathbb{N}\}}$ and further show that every other ${h \in H^0}$ has degree divisible by the degree of ${f}$, then we have that ${\{f(x)^n : n\in \mathbb{N}\}}$ is the basis for ${H^0}$.

Notice also that ${f(x) = x^{4} + x \in H^0}$. This follows from the fact that ${\mathbb{F}_{4}^{\ast}}$ is the cyclic multiplicative group of order ${3}$, hence ${\mu^{3} = 1}$. So we have

$\displaystyle f(x + \mu) = (x + \mu)^{4} + x + \mu = x^{4} + \mu^{4} + x + \mu = x^{4} + x + \mu + \mu = f(x)$

It's not hard to show (exempli gratia, by exhaustion) that ${x^4 + x}$ is the smallest degree polynomial in ${H^0}$, and that it's the only polynomial in ${H^0}$ of degree ${4}$.

Now let ${f \in H^0}$, and let ${\text{deg}f = n}$, say ${f(x) = x^n + a_1 x^{n-1} + \ldots + a_n }$. Clearly ${n}$ cannot be odd, as then ${\binom{n}{1}}$ is also odd, so in the expansion

$\displaystyle f(x + \mu) = (x+\mu)^n + \ldots + a_n = x^n + \mu x^{n-1} + \ldots + \text{lower order terms}$

has a ${\mu}$ as a coefficient of the ${x^{n-1}}$ term, so it can't possibly equal ${f(x)}$.

Now, we want that ${4 | \text{deg}f}$. Say ${\text{deg}f = n = 4k + 2}$. Let's look at the coefficient of ${x^{4k}}$ in ${f(x + \mu)}$. We have ${(x+\mu)^{4k + 2} = (x+\mu)^{4k}(x+\mu)^2 = (x^4 + \mu^4)^k(x^2 + \mu^2) = x^{4k+2} + \mu^2 x^{4k} + \text{lower order terms...}}$. Also ${(x+\mu)^{4k + 1} = (x^4 + \mu^4)^k (x + \mu) = x^{4k+1} + \mu x^{4k} + \text{lower order terms...}}$. Hence in ${f(x + \mu) - f(x)}$, ${x^{4k}}$ has a coefficient ${(\mu^2 + \mu)}$. Thus, if ${f}$ is not divisble by 4, it's not in ${H^0}$.

So say ${f \in H^0}$ has degree ${4k}$. Then ${f(x) - (x^4 + x)^k}$ is also in ${H^0}$ and divisible by 4. In this way we see that polynomials in ${t = x^4 + x}$ form ${H^0}$.