finite field | Gyre&Gimble

My early life as a mathematician.

Revised 22 January 2016.

In 1965, I received my Ph.D. at Duke University based on a dissertation about polynomials over finite fields. My advisor was Leonard Carlitz.

In Carlitz’s algebra course, the textbook was Van der Waerden’s Algebra. It is way too old-fashioned to be used nowadays, but it did indeed present post-Noether type abstract algebra. Carlitz also had me read large chunks of Martin Weber’s Lehrbuch der Algebra, written in German in 1895 (so totally not post-Noether) and published using Fraktur. A few years ago one of my sons asked me to retype the words to some of the songs written in Fraktur in a German-American shape note book in Roman type (but still in German), which I did. This was for German teachers in the Concordia Language Villages to use with their students. I sometimes wonder if I am the last person on earth able to read Fraktur fluently.

I learned mathematical logic from Joe Shoenfield from his dittoed notes that later became an excellent textbook. I rediscovered Craig’s Trick while working on problem he gave. That considerably strengthened my sense of self-worth.

I accepted a job at Western Reserve University, now Case Western Reserve University, where I stayed until I retired in 1999. In the few years after 1965, I wrote several papers about finite fields. They are all summarized in the book Finite Fields, by Rudolf Lidl and Harald Niederreiter.

I was almost immediately attracted to category theory and to computing science, both of which Carlitz hated. I did not let that stop me. (Now is the time to say, Follow The Beat of your Own Drum or some such cliché.)

Early on, Paul Dedecker was at CWRU briefly, and from him I learned about sheaves, cribles and the like. This inspired me to take part in an algebraic geometry summer school at Bowdoin College, where I learned from lectures by David Mumford and by reading his Red Book when it was still red.

Because one of the papers in finite fields showed that certain types of permutation polynomials formed wreath products of groups, I also pursued group theory, in particular by taking part in the finite group theory summer school at Bowdoin in 1970.

During that time I pored over Beck’s thesis on cohomology, which with the group theory I had learned resulted in my paper Automorphisms of group extensions. That paper has the most citations of all my research papers.

In the early days, I had several graduate students. All of them worked in group theory. One of them, Shair Ahmad, went on to produce several Ph.D. students, all in differential equations and dynamical systems.

One thing I can brag about is that I never ever told him I hated differential equations or dynamical systems. In fact, I didn’t hate either one. There were people in the department in both fields and they made me jealous the way they could model real life phenomena with those tools. One relevant point about that is that I was a liberal arts math major from Oberlin before going to Duke and had had very few courses in any kind of science. This made me very different from most people in the department, who has B.S. undergrad degrees.

In those days, John Isbell and Peter Hilton were in the math department at CWRU for awhile, which boosted my knowledge and interest in category theory. Hilton arranged for me to spend a year at the E.T.H. in Zürich, where I met Michael Barr. I eventually wrote two books on category theory with him. But that is getting away from Early Days, so I will stop here.

Send to Kindle

I discussed endographs of real functions in my post Endographs and cographs of real functions. Endographs of finite functions also provide another way of thinking about functions, and I show some examples here. This is not a new idea; endographs have appeared from time to time in textbooks, but they are not used much, and they have the advantage of revealing some properties of a function instantly that cannot be seen so easily in a traditional graph or cograph.

In contrast to endographs of functions on the real line, an endograph of a finite function from a set to itself contains all the information about the function. For real functions, only some of the arrows can be shown; you are dependent on continuity to interpolate where the infinite number of intermediate arrows would be, and of course, it is easy to produce a function, with, say, small-scale periodicity, that the arrows would miss, so to speak. But with an endograph of a finite function, WYSIATI (what you see is all there is).

Here is the endograph of a function. It is one function. The graph has four connected components.

You can see immediately that it is a permutation of the set $\{1,2,3,4,5,6\}$ , and that it is involution (a permutation $f$ for which $f f=\text{id}$ ). In cycle notation, it is the permutation $(1 2)(5 6)$ , and the connected components of the endograph correspond to the cycle structure.

Here is another permutation:

You can see that to get $f^n=\text{id}$ you would have to have $n=6$ , since you have to apply the 3-cycle 3 times and the transposition twice to get the identity. The cycle structure $(1 2 4)(0 3)$ tells you this, but you have to visualize it acting to see that. The endograph gives the newbie a jumpstart on the visualization. “The power to understand and predict the quantities of the world should not be restricted to those with a freakish knack for manipulating abstract symbols” (Brett Victor). This is an argument for insisting that this permutation is the endograph, and the abstract string of symbols $(1 2 4)(0 3)$ is a representation of secondary importance. [See Note 1.]

Here is the cograph of the same function. It requires a bit of visualization or tracing arrows around to see its cycle structure.

If I had rearranged the nodes like this

the cycle structure would be easier to see. This does not indicate as much superiority of the endograph metaphor over the cograph metaphor as you might think: My endograph code [Note 2] uses Mathematica’s graph-displaying algorithm, which automatically shows cycles clearly. The cograph code that I wrote specifies the placement of the nodes explicitly, so I rearranged them to obtain the second cograph above using my knowledge of the cycle structure.

The following endographs of functions that are not permutations exhibit the general fact that the graph of a finite function consists of cycles with trees attached. This structure is obvious from the endographs, and it is easy to come up with a proof of this property of finite functions by tracing your finger around the endographs.

This is the endograph of the polynomial $2 n^9+5 n^8+n^7+4 n^6+9 n^5+1$ over the finite field of 11 elements.

Here is another endograph:

I constructed this explicitly by writing a list of rules, and then used Mathematica’s interpolating polynomial to determine that it is given by the polynomial

$6 x^{16}+13 x^{15}+x^{14}+3 x^{13}+10 x^{12}+5 x^{11}\\ +14 x^{10}+4 x^9+9 x^8+x^7+14 x^6\\ +15 x^5+16 x^4+14 x^3+4 x^2+15 x+11$

in GF[17].

Quite a bit is known about polynomials over finite fields that give permutations. For example there is an easy proof using interpolating polynomials that a polynomial that gives a transposition must have degree $q-2$ . The best reference for this stuff is Lidl and Niederreiter, Introduction to Finite Fields and their Applications

The endographs above raise questions such as what can you say about the degree or coefficients of a polynomial that gives a digraph like the function $f$ below that is idempotent ( $f f=f$ ). Students find idempotence vs. involution difficult to distinguish between. Digraphs show you almost immediately what is going on. Stare at the digraph below for a bit and you will see that if you follow $f$ to a node and then follow it again you stay where you are (the function is the identity on its image). That’s another example of the insights you can get from a new metaphor for a mathematical object.

The following function is not idempotent even though it has only trivial loops. But the digraph does tell you easily that it satisfies $f^4=f^3$ .

Notes

[1] Atish Bagchi and I have contributed to this goal in Graph Based Logic and Sketches, which gives a bare glimpse of the possibility of considering that the real objects of logic are diagrams and their limits and morphisms between them, rather than hard-to-parse strings of letters and logical symbols. Implementing this (and implementing Brett Victor’s ideas) will require sophisticated computer support. But that support is coming into existence. We won’t have to live with string-based math forever.

[2] The Mathematica notebook used to produce these pictures is here. It has lots of other examples.

Send to Kindle

math, language and other things that may show up in the wabe

Gyre&Gimble

Tag Archives: finite field

A tiny step towards killing string-based math

Notes

math, language and other things that may show up in the wabe