Paley graphs in Sage

Let q be a prime power such that q\equiv 1 \pmod 4. Note that this implies that the unique finite field of order q, GF(q), has a square root of -1. Now let V=GF(q) and

E = \{(a,b)\in V\times V\ |\ a-b\in GF(q)^2\}.
By hypothesis, (a,b)\in E if and only if (b,a)\in E. By definition G = (V, E) is the Paley graph of order q.

Paley was a brilliant mathematician who died tragically at the age of 26. Paley graphs are one of the many spin-offs of his work. The following facts are known about them.

  1. The eigenvalues of Paley graphs are \frac{q-1}{2} (with multiplicity 1) and
    \frac{-1 \pm \sqrt{q}}{2} (both with multiplicity \frac{q-1}{2}).
  2. It is known that a Paley graph is a Ramanujan graph.
  3. It is known that the family of Paley graphs of prime order is a vertex expander graph family.
  4. If q=p^r, where p is prime, then Aut(G) has order rq(q-1)/2.

Here is Sage code for the Paley graph (thanks to Chris Godsil, see [GB]):

def Paley(q):
    K = GF(q)
    return Graph([K, lambda i,j: i != j and (i-j).is_square()])

(Replace “K” by “K.\langle a\rangle” above; I was having trouble rendering it in html.) Below is an example.

sage: X = Paley(13)
sage: X.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
sage: X.is_vertex_transitive()
True
sage: X.degree_sequence()
[6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6]
sage: X.spectrum()
[6, 1.302775637731995?, 1.302775637731995?, 1.302775637731995?,
1.302775637731995?, 1.302775637731995?, 1.302775637731995?,
-2.302775637731995?, -2.302775637731995?, -2.302775637731995?,
-2.302775637731995?, -2.302775637731995?, -2.302775637731995?]
sage: G = X.automorphism_group()
sage: G.cardinality()
78

We see that this Paley graph is regular of degree 6, it has only three distinct eigenvalues, and its automorphism group is order 13\cdot 12/2 = 78.

Here is an animation of this Paley graph:

The frames in this animation were constructed one-at-a-time by deleting an edge and plotting the new graph.

Here is an animation of the Paley graph of order 17:

The frames in this animation were constructed using a Python script:

X = Paley(17)
E = X.edges()
N = len(E)
EC = X.eulerian_circuit()
for i in range(N):
    X.plot(layout="circular", graph_border=True, dpi=150).save(filename="paley-graph_"+str(int("1000")+int("%s"%i))+".png")
    X.delete_edge(EC[i])
X.plot(layout="circular", graph_border=True, dpi=150).save(filename="paley-graph_"+str(int("1000")+int("%s"%N))+".png")

Instead of removing the frames “by hand” they are removed according to their occurrence in a Eulerian circuit of the graph.

Here is an animation of the Paley graph of order 29:

[GB] Chris Godsil and Rob Beezer, Explorations in Algebraic Graph Theory with Sage, 2012, in preparation.

Mathematics Problem, #120

A colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his students, giving a prize of a cookie if they could solve it. Here is one of them.

Mathematics Problem, #120

A calculus 1 student Joe asks another student Bob “Is the following expression correct?” and writes

f'(x^3)=3x^2
on the blackboard. Bob replies, “Well, it could be, but I don’t think that is what you mean.”

Find a function that makes what Joe said correct.

Solution to #119:
There are (16!)/(2^8) (about 82 billion) different orders that the spider can put on shoes and socks.

Lester Hill’s “The checking of the accuracy …”, part 8

Introductory example of checking

We may use the field F_{23} as the basis for a simple illustrative exercise in the actual procedure of checking. The general of the operations involved will thus be made clear, so far as modus operandi is concerned, and we shall be enabled to discuss more easily the pertinent mathematical details.

It is easy to set up telegraphic codes of high capacity using combinations of four letters each which are not required to be pronounceable. In fact, a sufficiently high capacity may be obtained when only
twenty-three letters of the alphabet are used at all. Hence we can omit any three letters whose Morse equivalents (dot-dash) are most frequently used. Let us suppose that we have before us a code of this kind which employs the letters

A\ \ B\ \ C\ \ E\ \ F\ \ G\ \ H\ \ I\ \ J\ \ L\ \ M\ \ N\ \ P\ \ Q\ \ R\ \ S\ \ T\ \ U\ \ V\ \ W\ \ X\ \ Y\ \ Z
and avoids, for reasons stated of for some good reason, the three letters

D\ \ K\ \ O\, .

Suppose that, by prearrangement with telegraphic correspondents, the letters used are paired in
an arbitrary, but fixed, way with the thwenty-three elements of F_{23}.
Let the pairings be, for instance:

\begin{tabular}{ccccccccccccccccccccccc}  A & B  & C & E & F & G & H  & I    & J    & L & M & N  & P   & Q   & R    & S & T   & U   & V & W & X   & Y & Z \\ \hline  4 & 7 & 9 & 14& 2 & 1 & 11 & 15 & 10 & 3 & 19 & 18 & 21 & 16 & 6 & 20 & 17 & 12 & 0 & 22 & 5 & 13 & 8 \\  \end{tabular}
or, in numerical arrangement:

\begin{tabular}{ccccccccccccccccccccccc}  0 & 1  & 2 & 3 & 4 & 5 & 6  & 7  & 8  & 9 & 10 & 11 & 12 & 13 & 14  & 15 & 16  & 17  & 18 & 19 & 20  & 21 & 22 \\ \hline  V & G & F & L& A & X & R & B & Z & C & J & H & U & Y & E & I & Q & T & N & M & S & P & W \\  \end{tabular}

A four-letter group (code word), such as EZRA or XTYP, will indicate a definite entry of a specific page of a definite code volume, several such volumes being perhaps employed in the code. An entry will, in general, be a phrase of sentence, or a group of phrases or sentences, commonly occurring in the class of messages for which the code has been constructed.

Suppose that we have agreed to provide, in our messages, three-letter checks upon groups of twelve letters; in other words, to check in one operation a sequence of three four-letter code words. The twelve letters of the three code words are thus expanded to fifteen; but we send just three telegraphic words — three combinations of five letters, each of which is, in general, unpronounceable.

For illustration, let the first three code words of a message be:

XTYP\ \ \ \ VZRV\ \ \ \ HVHH
The corresponding sequence of paired elements in F_{23} is:

5 \ \ 17\ \ 13\ \ 21\ \ 0\ \ 8\ \ 6\ \ 0\ \ 11\ \ 0\ \ 11\ \ 11.
This is our operand sequence f_i:

f_1 = 5,\ \ f_2=17,\ \ f_3=13,\ \ f_4=21,\ \ f_5=0,\ \dots,\ ,f_{12}=11.

Let us determine the checking matrix c_1, c_2, c_3 by using as reference matrix

\left(  \begin{array}{cccccccccccc}  1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\  1^2 & 2^2 & 3^2 & 4^2 & 5^2 & 6^2 & 7^2 & 8^2 & 9^2 & 10^2 & 11^2 & 12^2 \\  1^3 & 2^3 & 3^3 & 4^3 & 5^3 & 6^3 & 7^3 & 8^3 & 9^3 & 10^3 & 11^3 & 12^3 \\  \end{array}  \right)
Thus the c_j are to be

c_j = \sum_{i=1}^{12} i^jf_i\ \ \ \ (j = 1,2,3),

or

c_1 = \sum_{i=1}^{12} if_i.\ \ \ c_2 = \sum_{i=1}^{12} i^2f_i.\ \ \ c_3 = \sum_{i=1}^{12} i^3f_i.

Referring to the multiplication table of F_{23}, we easily compute the c_j.

For the first element 5, of the operant sequence f_i, write

\begin{tabular}{ccc}  5 & 5  & 5\\  \end{tabular}

For the second element 17 place a sheet of paper (or a ruler) under the second row
of the multiplication table, and in that row read: 11 in column 17, 22 in column 11, 21 in column 22. we now have a second line for the tabular scheme:

\begin{tabular}{ccc}  5 & 5  & 5\\  11 & 22 & 21 \\  \end{tabular}

For the third element 13 place a sheet of paper (or a ruler) under the third row
of the multiplication table, and in that row read: 16 in column 13, 2 in column 16, 6 in column 2. We now have the scheme:

\begin{tabular}{ccc}  5 & 5  & 5\\  11 & 22 & 21 \\  16 & 2 & 6 \\  \end{tabular}

The fifth, eighth, and tenth rows of the table will not be used, since
f_5=f_8=f_{10}=0. The complete scheme is readily found to be:

\begin{tabular}{cccc}  5 & 5  & 5 & \\  11 & 22 & 21  & \\  16 & 2 & 6  & \\  15 & 14  & 10 & \\  2 & 12 & 3  & \\  19 & 18 & 11  & \\  7 & 17  & 15 & \\  6 & 20 & 13  & \\  17 & 20 & 10  & \\ \hline  98 & 130 & 94 & sum in ZZ\\  6 & 15 & 2 & sum in F-23\\  \end{tabular}

We have c_1=6, c_2=15, c_2=2.

We transmit, of course, the sequence of letters paired, in our system of communications, with the elements of the sequence,

f_1\ f_2\ \dots f_{12}\ c_1\ c_2 \ c_3.

Thus we transmit the sequence of letters: XTYP VZRV HVHH RIF; but we may conveniently agree to transmit it in the arrangement:

XTYPR\ \ \ VZRVI\ \ \ HVHHF ,

or in some other arrangement which employs only three telegraphic words (unpronounceable five letter groups).

We could have used other reference matrices, but we shall not stop to discuss this point. We may remark, however, that if the matrix

\left(  \begin{array}{cccccccccccc}  1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\  1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12\\  1^2 & 2^2 & 3^2 & 4^2 & 5^2 & 6^2 & 7^2 & 8^2 & 9^2 & 10^2 & 11^2 & 12^2 \\  \end{array}  \right)

had been adopted, the checking elements would have been

c_1 = \sum_{i=1}^{12} f_i.\ \ \ c_2 = \sum_{i=1}^{12} if_i.\ \ \ c_3 = \sum_{i=1}^{12} i^2f_i;

and their evaluation would have been accomplished with equal
ease by means of the multiplication table of F_{23}.