Learn you Galois fields for great good (2023)

This isn't essential, but it's worth noting that the construction of Galois fields is basically done in the same way as a more familiar one: building the complex numbers from the real numbers. In that case, the new "numbers" are defined to be polynomials with real coefficients, with addition and multiplication being performed modulo the polynomial x^2+1. This has the effect of equating x^2+1 with 0, since the division (x^2+1)/(x^2+1) has remainder 0. With this rule, x is now a square root of -1; of course we usually write i instead of x. In terms of the compact notation mentioned in the article, the complex numbers are the same thing as R[x]/(x^2+1).

The Galois field case can be thought of in the same way, as long as a little care is taken with the choice of polynomial. When the coefficients come from GF(2), there's not much point in using the polynomial x^2+1 as above, because x^2+1 = x^2+2x+1 = (x+1)^2. Forcing x^2+1 = (x+1)^2 to be 0 would basically just have the effect of setting x = -1 = 1, so we don't get any new numbers. [Technically, 0, 1, x, 1+x would still be distinct in this construction, but it doesn't result in a field since 1+x would have no multiplicative inverse.] As explained in the article, the polynomial should be irreducible to avoid this problem, so x^2+x+1 works to build GF(4) from GF(2). But this is the only difference from complex numbers: we can think of GF(4) as being GF(2) with an added "fictional number" h satisfying h^2+h+1 = 0 (i.e. h^2 = h+1). The elements of GF(4) are therefore numbers ah+b where a,b are in GF(2), multiplied just like complex numbers except that we simplify using the rule h^2 = h+1 instead of i^2 = -1.

In the Galois field case, lots of different polynomials appear because (1) we need a degree k irreducible polynomial to construct GF(p^k) from GF(p) and (2) there's not really an obvious "simplest" such polynomial to use, unlike in the case of the complex numbers C. In that case, a miraculous fact intervenes to save us from a similar zoo of polynomials: as soon as we add the one "fictional number" i, all polynomials with complex coefficients have roots in terms of it, so there are no more fictional numbers to be created this way starting from C.

I love it when the simple stuff is explained in simple language that anybody can understand. Like Einstein said:

Make it simple. As simple as possible. But no simpler!

A somewhat related explanation that also covers groups and fields: https://explained-from-first-principles.com/number-theory/ , https://news.ycombinator.com/item?id=32879801

The problem with algebra teaching is, they just declare a thing without explaining the root reason of why it's there in first place.

For abstract algebra, there is the polished

I.\ N.\ Herstein, {\it Topics in Algebra,\/}

(markup for TeX word processing).

For Galois theory, took an oral exam on what was in Herstein.

For linear algebra where the field is any of the rationals, reals, complex, and finite fields there is

Evar D.\ Nering, {\it Linear Algebra and Matrix Theory,\/} John Wiley and Sons, New York, 1964.\ \

As I recall, Nering was an Artin student at Princeton.

Some of the proofs for the rational, real, or complex fields don't work for finite fields so for those need special proofs.

Had a course in error correcting codes -- it was applied linear algebra where the fields were finite.

Linear algebra is usually about finite dimensional vector spaces with an inner product (some engineers say dot product), but the main ideas generalize to infinite dimensions and Hilbert and Banach spaces.

Wow, wonderful stuff. Thanks for posting!

1) the properties of a field is missing closure under the operation. This is kind of assumed from context, but I would include it.

2) the reduction step up multiplication of nth order polynomials (to keep them nth order) is missing (or at least I missed it after a couple of readings.)

Apart from those quibbles, this was really good overall though. I enjoyed it.

of course it's written in Rust! But I was lowkey looking for something more Haskell-y, even Lean. And I wish the visualizations would continue throughout the chapters.

(2023) https://web.archive.org/web/20230815034422/https://xorvoid.c...

Someone should check grammar before posting a title

Whining about algebra not being in most CS curriculums is just a lie. Every university in the world has (if it doesn't, it's not a university) maths as a minor regardless of what your major is. And everyone I know, including me, took algebra as a minor being a CS major (if you didn't, question your choice of career).