12
$\begingroup$

I have been teaching a ring theory course this semester, focusing on modular arithmetic and quotient rings of polynomials over fields.

Several students have asked me how one could graph functions from a finite field (or any $Z_n$) to itself. I've considered drawing them on a torus (since the input and output loop around onto themselves), but this would be difficult to depict on a two-dimensional chalkboard.

In your experience, is there an effective graphical representation of a function from a finite field to itself?

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ Perhaps you'll think this is a bit of a non sequitor, but Edward Tufte says rightly that tables are a good way of displaying numerical information, and since in any case we graph functions because we can't list their infinitely many inputs and outputs, why not simply give a table? i.e. $0\mapsto0; 1\mapsto2;... $ $\endgroup$
    – Marius Kempe
    Apr 13, 2015 at 22:00
  • $\begingroup$ I've added the abstract-algebra tag to make your question a little easier to find. If you feel a different tag is more appropriate, please feel free to edit. $\endgroup$
    – J W
    Aug 7, 2019 at 15:12

6 Answers 6

Reset to default
15
$\begingroup$

Just supplementing Benjamin Dickman's nice answer, here is $x \mapsto x^2 - x$ in $\mathbb{Z}_{18}$ in the same style:

FieldGraphZ18
For example, the pentagon wheel reflects the fact that $$(5+3k)^2-(5+3k) = 9k^2 + 27k + 20 = 9k(k+3) + 20 = 2\bmod 18 \;.$$

Improve this answer
$\endgroup$
6
  • $\begingroup$ +1! My MS Paint skills put to shame... $\endgroup$
    – Benjamin Dickman
    Apr 14, 2015 at 3:03
  • $\begingroup$ @BenjaminDickman: I used Mathematica. $\endgroup$
    – Joseph O'Rourke
    Apr 14, 2015 at 11:30
  • 1
    $\begingroup$ @JosephO'Rourke: Your graphics are always supremely clear! May I ask how exactly you got those graphs to look so nice in mathematica? That is, which package/format were you using? $\endgroup$
    – Zach Haney
    Apr 22, 2015 at 3:00
  • 1
    $\begingroup$ @ZachHaney: I wish I could claim cleverness, but I just used Graph[edges, VertexLabels -> "Name", VertexStyle -> Pink] after filling up edges appropriately. $\endgroup$
    – Joseph O'Rourke
    Apr 22, 2015 at 11:01
  • 3
    $\begingroup$ I made this GeoGebra applet for $\mathbb{Z}_7$ where you can drag the points around to get a better view of the arrows: ggbtu.be/m1194053 $\endgroup$
    – DavidButlerUofA
    May 16, 2015 at 7:36
13
$\begingroup$

One of the approaches taken in some areas of mathematics (e.g., in arithmetic dynamics and considerations of preperiodic points, etc) is to create these graphs by drawing discrete points and then using arrows to show which values map to which other ones.

Figuring out a "canonical" way to draw these pictures might be a bit tough (this is related in some manner to the concerns about orders in Gerhard Paseman's answer).

Here is a sample picture of the function $x \mapsto x^2 - x$ in $\mathbb{Z}/12\mathbb{Z}$ (the same function drawn by mweiss in his answer):

enter image description here

As for whether this graphical representation is effective: That will depend on how you use it and what you wish to achieve. I do think that, in the above case, some natural questions arise around why certain structures appear more than once. Can students tease out these questions? (What sort of questions do they ask?) Once curiosity has been piqued, can it be resolved by appealing to one's algebraic or graphical intuition?

A brief excerpt related to the notable comment of mweiss below:

enter image description here

The interested reader may wish to check the paper of Kempner, as well as a nice generalization in:

Chen, Z. (1995). On polynomial functions from Zn to Zm. Discrete Mathematics, 137(1), 137-145. ScienceDirect Link.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Sample follow-up question: Suppose you had the graph above, unlabelled, and knew it was over $\mathbb{Z}/12\mathbb{Z}$. Could you figure out the corresponding function? (Is the answer unique?) $\endgroup$
    – Benjamin Dickman
    Apr 13, 2015 at 21:58
  • 4
    $\begingroup$ This is perhaps not the right place to get into it, but did you know that: (1) Any function over $\mathbb{Z}_p$ for prime $p$ can be produced by a unique polynomial of degree $\leq p$, and that this polynomial is unique; and (2) for composite $n$, most functions cannot be represented by a polynomial? In other words, transcendental functions do not exist when working over a prime base, but most functions are transcendental when working over a composite base. $\endgroup$
    – mweiss
    Apr 14, 2015 at 0:33
  • $\begingroup$ (1) @mweiss I did not know that! Do you have a suggested reference? I came across related comments in my reading, which I have incorporated into the body of my post. (2) To answer my own follow-up question, the answer for that unlabelled graph is not unique: Consider the representation of $x \mapsto x^2 - x + 6$ in $\mathbb{Z}/12\mathbb{Z}$. $\endgroup$
    – Benjamin Dickman
    May 12, 2015 at 14:36
  • 1
    $\begingroup$ See math.stackexchange.com/questions/1243509/… (and in particular the first comment there). $\endgroup$
    – mweiss
    May 12, 2015 at 18:00
  • 1
    $\begingroup$ See also the note by Grady and Poston on the Arxiv: A Glimpse of Arithmetic Dynamics, which appeared just recently. $\endgroup$
    – J W
    Aug 7, 2019 at 10:58
6
$\begingroup$

I don't think it's all that bad to put your graph on ordinary everyday axes as long as the students know that the order is more or less irrelevant.

If you are happy to break out of the page, I recommend drawing your graph on a piece of paper and rolling it up to make a cylinder. Then at least one of the axes represents the cyclical nature of the field.

If you want to have the graph on a torus on a screen, it may be better to use technology.

I've used Geogebra to make a workbook of various graphs, including cartesian graphs, cylindrical graphs and input-output graphs for $\mathbb{Z}_7$.

The cartesian graphs looks like the ordinary graphs students would be familiar with:

cartesian graph

The x-axis and y-axis can both be moved so that the labels cycle around, giving you the feel of the toroidal shape. UPDATE: There's now an activity that allows you to choose the order of the ring, from $\mathbb{Z}_3$ to $\mathbb{Z}_{30}$.

The cylindrical graphs are like the cartesian one, only the x-axis has been rolled up to make a circle:

cylindrical graph

The circular axis at the bottom can be rotated, and the vertical axis (the separate circles) can be slid up and down so the values cycle around. (It looks much better in motion than statically.)

Finally, the input-output graph has a domain at the top and a codomain at the bottom with arrows to show where each point goes under the function.

input output graph

You can spin the top and bottom independently or together, and change the perspective.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is great!! $\endgroup$
    – Benjamin Dickman
    May 13, 2015 at 22:06
  • $\begingroup$ Agreed, these are really beautiful. $\endgroup$
    – mweiss
    May 14, 2015 at 3:15
5
$\begingroup$

Edited: I would use a rectangular display that looks, at first, like a standard "Quadrant I" graph, but that can be grabbed and dragged left/right/up/down to move the viewing frame. So, for example, if one is working over $\mathbb{Z}_7$ the horizontal and vertical scales will initially be labeled "0 1 2 3 4 5 6" in both direction, but the view can be dragged so that the horizontal axis reads "3 4 0 1 2 3 4 5" and the vertical axis reads "5 6 0 1 2 3 4".

Here is an attempt at creating such a tool. It shows the function $y=x^2-x$ defined on $\mathbb{Z}_{12}$. The graph behaves in such a way that the top and bottom edges of the plot are identified, as are the left and right edges, so the function is (essentially) graphed on a torus. Points are labeled with $x$ and $y$ coordinates in the set $\{0, 1, \ldots 11\}$ and the "axes" (i.e. the lines $y=0$ and $x=0$) are drawn in as solid lines. Were I more skilled at Geogebra, I would add tick marks to the axes with labels that run $\{0, 1, \ldots 11\}$ and repeat cyclically. If any Geogebra gurus have suggestions on how to do that, I would appreciate the input.

Improve this answer
$\endgroup$
4
  • $\begingroup$ How about this version of a similar idea: tube.geogebra.org/student/m1175993 $\endgroup$
    – DavidButlerUofA
    May 12, 2015 at 20:22
  • $\begingroup$ @DavidButlerUofA Nice! $\endgroup$
    – mweiss
    May 13, 2015 at 0:05
  • $\begingroup$ Actually I have a couple of others now. I think I might make a new answer with all of them, if you don't mind an answer competing with yours. $\endgroup$
    – DavidButlerUofA
    May 13, 2015 at 0:21
  • $\begingroup$ Of course I don't mind -- I'm happy to see them! $\endgroup$
    – mweiss
    May 13, 2015 at 1:01
4
$\begingroup$

Perhaps an approach that mirrors the standard graphing might be useful? One way that I appreciate is seen here:

enter image description here

This is used by N. J. Wildberger and others. I just snagged this off google images to demonstrate. I think this particular image is of $F_{13}$ with two "lines" plotted and their intersection marked at (5,2) -- but don't quote me on that.

I can generate some more examples if anyone is interested. It's fascinating to look at conics in these situations!

Improve this answer
$\endgroup$
3
$\begingroup$

There are dangers in using such graphical representations. The reals are an ordered field, whereas orders are not compatible with field operations for finite fields and other fields. It is easy to think things like "this function is increasing": such thoughts are helpful if you are going to transfer something of the function to the reals, and can mislead in other cases. Inside finite fields it is of more interest whether the function is a permutation of the nonzero elements or not. Also zeroes of the function are important to represent. Choose the representation to emphasize the characteristic of importance.

If you put the necessary cautions in place, it should be OK to embed the graph in the upper right quadrant of the real plane. Be sure to emphasize other views of the function as well: treating it as a polynomial, treating it as a permutation or near permutation, treating it as a fragment of a graph of a real valued function. However, treating an object as something else, while useful, does not make that object something else. If the toroidal nature of the ring appeals to you, use a square and identify edges of the square, and relate this to certain video displays to get them to deal with this form of representation (at, least, until the manufacturers come out with computer screens shaped like doughnuts).

Gerhard "Should Doughnuts Be Called Doughwheels?" Paseman, 2015.04.13

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I believe they are called "nuts" because they look like nuts as in nuts and bolts. $\endgroup$
    – DavidButlerUofA
    Apr 13, 2015 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.