Ah, there it is! Thanks for the link! I'm looking forward to catch up!
I just recently noticed that I thought for yours I knew how finite fields worked, but actually didn't.
Addition ist dead easy, there's just one field for any finite order, the primes are cyclic, prime powers come from Galois extensions, so they must be like vectors over prime fields, right? Any other way to get a field of order n is going to be isomorphic.
Well, of course not. For one, F_p^2 doesn't have twice as many elements as F_p (unless p=2). It says square, not double! The elements of F_p^n are the polynomials of degree n-1. But then that's still not all!
To write up a multiplication table we need to pick an irreducible polynomial P of degree n, so that when we multiply two elements of our field, we can use P=0 to bring down the degree of our product back to the allowed range.
And here's the kicker I totally missed for more than a decade: The labeling of F_p^n depends on our choice of P! There's even an especially nice kind of canonical polynomials for this purpose.
These are called Conway polynomials, and were invented by R. Parker. They are quite difficult to compute so current computer algebra systems use precomputed tables of them, so they can label GF(q)'s elements consistently.
@b4c50e1b
@133234fb - I know Conway invented a decent system for naming elements of 𝐹ₚⁿ when p = 2, but now I can't find any references to this! I gues Parker generalized it.
I found this insane approach, though:
https://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1977e/art.pdf
I don't quite get that paper, but it mentions Conway's book On Numbers and Games, presumably for his proof that "a suitable beginnjbg segment of On_2 is an algebraic closure of the two-element subfield {0,1}".
I suppose it's not where he wrote about his notation for GF(2^n), or maybe it is. Many years ago I flipped through On Numbers and Games, but I wasn't ready then. Maybe I am now.
Anyways, Richard A. Parker seems to have put Conway's compatibility criterion into a full definition and himself named the resulting polynomials after Conway. I haven't found where Parker published about this. I'm not very good at finding publications, what do people use to find stuff? Google Scholar?
@b4c50e1b @b4c50e1b @133234fb
insane approach? really?
give me a better approach to understand \( \overline{\mathbb{F}_2} \).
it's a beautiful paper if you ever really want to understand Galois theory.
try to prove every statement Conway made in ONAG about \( On_2 \) being the algebraic closure of \( \mathbb{F}_2 \) (or give them as exercises to your better students)
Lenstra went way beyond that in the late 70ties (i think he was a visiting scholar at IHES at the time)
Probably he had to hardcode things, and because of the limited computing power at the time, he could not even approach stage 47.
An eternity ago, i did a post on this, slightly extending his scope (up to level 67)
http://www.neverendingbooks.org/on2-extending-lenstras-list
The best result I know of is by Aaron Siegel, see his book 'Combinatorial Game Theory' or my preview post on it
http://www.neverendingbooks.org/aaron-siegel-on-transfinite-number-hacking
He was able to push things up to level 293, but had to skip 4 levels because calculations seemed to take forever.
it is quite a humbling experience that even the simplest (and in applications the most valuable) of all algebraic closures is still way beyond our reach.
Later Lenstra and Bart de Smit gave another approach to the "Standard Model of Finite Fields"
http://www.damtp.cam.ac.uk/user/na/FoCM/FoCM08/Talks/Lenstra.pdf 
Oddbean new post about login | logout