Shanks’ SQUFOF according to McMath

In 2003, a math major named Steven McMath approached Fred Crabbe and I about directing his Trident thesis. (A Trident is like an honors thesis, but the student gets essentially the whole year to focus on writing the project.) After he graduated, I put a lot of his work online at the USNA website. Of course, I’ve retired since then and the materials were removed. This blog post is simply to try to repost a lot of the materials which arose as part of his thesis (which are, as official works of the US government, all in the public domain; of course, Dan Shanks notes are copyright of his estate and are posted for scholarly use only).

McMath planned to study Dan ShanksSQUFOF method, which he felt could be exploited more than had been so far up to that time (in 2004). This idea had a little bit of a personal connection for me. Dan Shanks was at the University of Maryland during the time (1981-1983) I was a grad student there. While he and I didn’t talk as much as I wish we had, I remember him as friendly guy, looking a lot like the picture below, with his door always open, happy to discuss mathematics.

One of the first things McMath did was to type up the handwritten notes we got (I think) from Hugh Williams and Duncan Buell. A quote from a letter from Buell:

Dan probably invented SQUFOF in 1975. He had just bought an HP 67 calculator, and the algorithm he invented had the advantages of being very simple to program, so it would fit on the calculator, very powerful as an algorithm when measured against the size of the program, and it factors double precision numbers using single precision arithmetic.

Here are some papers on this topic (with thanks to Michael Hortmann for the references to Gower’s papers):

David Joyner, Notes on indefinite integral binary quadratic forms with SageMath, preprint 2004. pdf

F. Crabbe, D. Joyner, S. McMath, Continued fractions and Parallel SQUFOF, 2004. arxiv

D. Shanks, Analysis and Improvement of the Continued Fraction Method of Factorization, handwritten notes 1975, typed into latex by McMath 2004. pdf.

D. Shanks, An Attempt to Factor N = 1002742628021, handwritten notes 1975, typed into latex by McMath 2004. pdf.

D. Shanks, SQUFOF notes, handwritten notes 1975, typed into latex by McMath 2004. pdf.

S. McMath, Daniel Shanks’ Square Forms Factorization, 2004 preprint. pdf1, pdf2.

S. McMath, Parallel Integer Factorization Using Quadratic Forms, Trident project, 2004. pdf.

Since that time, many excellent treatments of SQUFOF have been presented. For example, see

J. Gower, S. Wagstaff, Square Form Factorization, Math Comp, 2008. pdf.

J. Gower, Square Form Factorization, PhD Thesis, December 2004. pdf.

The truncated tetrahedron covers the tetrahedron

At first, you might think this is obvious – just “clip” off each corner of the tetrahedron \Gamma_1 to create the truncated tetrahedron \Gamma_2 (by essentially creating a triangle from each of these clipped corners – see below for the associated graph). Then just map each such triangle to the corresponding vertex of the tetrahedron. No, it’s not obvious because the map just described is not a covering. This post describes one way to think about how to construct any covering.

First, color the vertices of the tetrahedron in some way.

\Gamma_1

The coloring below corresponds to a harmonic morphism \phi : \Gamma_2\to \Gamma_1:

\Gamma_2

All others are obtained from this by permuting the colors. They are all covers of \Gamma_1 = K_4 – with no vertical multiplicities and all horizontal multiplicities equal to 1. These 24 harmonic morphisms of \Gamma_2\to\Gamma_1 are all coverings and there are no other harmonic morphisms.

A mathematical card trick

If you search hard enough on the internet you’ll discover a pamphlet from the 1898 by Si Stebbins entitled “Card tricks and the way they are performed” (which I’ll denote by [S98] for simplicity). In it you’ll find the “Si Stebbins system” which he claims is entirely his own invention. I’m no magician, by from what I can dig up on Magicpedia, Si Stebbins’ real name is William Henry Coffrin (May 4 1867 — October 12 1950), born in Claremont New Hampshire. The system presented below was taught to Si by a Syrian magician named Selim Cid that Si sometimes worked with. However, this system below seems to have been known by Italian card magicians in the late 1500’s. In any case, this blog post is devoted to discussing parts of the pamphlet [S98] from the mathematical perspective.

In stacking the cards (face down) put the 6 of Hearts 6 \heartsuit first, the 9 of Spades 9 \spadesuit next (so it is below the 6 \heartsuit in the deck), and so on to the end, reading across left to right as indicted in the table below (BTW, the pamphlet [S98] uses the reversed ordering.) My guess is that with this ordering of the deck — spacing the cards 3 apart — it still looks random at first glance.

Hearts \heartsuitSpades \spadesuitDiamonds \diamondsuitClubs \clubsuit
69Queen2
58JackAce
4710King
369Queen
258Jack
Ace4710
King369
Queen258
JackAce47
10King36
9Queen25
8JackAce4
710King3
Si Stebbins’ System

Next, I’ll present a more mathematical version of this system to illustrate it’s connections with group theory.

We follow the ordering suggested by the mnemonic CHaSeD, we identify the suits with numbers as follows: Clubs is 0, Hearts is 1, Spades is 2 and Diamonds is 3. Therefore, the suits may be identified with the additive group of integers (mod 4), namely: {\bf{Z}}/4{\bf{Z}} = \{ 0,1,2,3 \}.

For the ranks, identify King with 0, Ace with 1, 2 with 2, \dots, 10 with 10, Jack with 11, Queen with 12. Therefore, the ranks may be identified with the additive group of integers (mod 13), namely: {\bf{Z}}/13{\bf{Z}}=\{ 0,1,2,\dots 12\}.

Rearranging the columns slightly, we have the following table, equivalent to the one above.

0123
36912
25811
14710
0369
12258
11147
10036
91225
81114
71003
69122
58111
47100
Mathematical version of the Si Stebbins Stack

In this way, we identify the card deck with the abelian group

G = {\bf{Z}}/4{\bf{Z}} \times {\bf{Z}}/13{\bf{Z}} .

For example, if you spot the 2 \clubsuit then you know that 13 cards later (and If you reach the end of the deck, continue counting with the top card) is the 2 \heartsuit, 13 cards after that is the 2 \spadesuit, and 13 cards after that is the 2 \diamondsuit.

Here are some rules this system satisfies:

Rule 1 “Shuffling”: Never riff shuffle or mix the cards. Instead, split the deck in two, the “bottom half” as the left stack and the “top half” as the right stack. Take the left stack and place it on the right one. This has the effect of rotating the deck but preserving the ordering. Do this as many times as you like. Mathematically, each such cut adds an element of the group G to each element of the deck. Some people call this a “false shuffle” of “false cut.”

Rule 2 “Rank position”: The corresponding ranks of successive cards in the deck differs by 3.

Rule 3 “Suit position”: Every card of the same denomination is 13 cards apart and runs in the same order of suits as in the CHaSeD mnemonic, namely, Clubs \clubsuit, Hearts \heartsuit, Spades \spadesuit, Diamonds \diamondsuit.

At least, we can give a few simple card tricks based on this system.

Trick 1: A player picks a card from the deck, keeps it hidden from you. You name that card.

This trick can be set up in more than one way. For example, you can either

(a) spread the cards out behind the back in such a manner that when the card is drawn you can separate the deck at that point bringing the two parts in front of you, say a “top” and a “bottom” stack, or

(b) give the deck to the player, let them pick a card at random, which separates the deck into two stacks, say a “top” and a “bottom” stack, and have the player return the stacks separately.

You know that the card the player has drawn is the card following the bottom card of the top stack. If the card on the bottom of the top stack is denoted (a,\alpha) \in G and the card drawn is (b,\beta) then

b \equiv a+3 \pmod{13}, \ \ \ \ \ \ \beta \equiv \alpha +1 \pmod{4}.

For example, a player draws a card and you find that the bottom card is the 9 \diamondsuit. What is the card the player picked?

solution: Use the first congruence listed: add 3 to 9, which is 12 or the Queen. Use the second congruence listed: add one to Diamond \diamondsuit (which is 3) to get 0 \pmod 4 (which is Clubs \clubsuit). The card drawn is the Q \clubsuit.

Trick 2: Run through the deck of cards (face down) one at a time until the player tells you to stop. Name the card you were asked to stop on.

Place cards behind the back first taking notice what the bottom card is. To get the top card, add 3 to the rank of the bottom card, add 1 to the suit of the bottom card. As you run through the deck you silently say the name of the next card (adding 3 to the rank and 1 to the suit each time). Therefore, you know the card you are asked to stop on, as you are naming them to yourself as you go along.

Quartic graphs with 12 vertices

This is a continuation of the post A table of small quartic graphs. As with that post, it’s modeled on the handy wikipedia page Table of simple cubic graphs.

According to SageMath computations, there are 1544 connected, 4-regular graphs. Exactly 2 of these are symmetric (ie, arc transitive), also vertex-transitive and edge-transitive. Exactly 8 of these are vertex-transitive but not edge-transitive. None are distance regular.

Example 1: The first example of such a symmetric graph is the circulant graph with parameters (12, [1,5]), depicted below. It is bipartite, has girth 4, and its automorphism group has order 768, being generated by (9,11), (5,6), (4,8), (2,10), (1,2)(5,9)(6,11)(7,10), (1,7), (0,1)(2,5)(3,7)(4,9)(6,10)(8,11).

Example 2: The second example of such a symmetric graph is the cuboctahedral graph, depicted below. It has girth 3, chromatic number 3, and its automorphism group has order 48, being generated by (1,10)(2,7)(3,6)(4,8)(9,11), (1,11)(3,4)(6,8)(9,10), (0,1,9)(2,8,10)(3,7,11)(4,5,6).

A footnote to Robert H. Mountjoy

In an earlier post titled Mathematical romantic? I mentioned some papers I inherited of one of my mathematical hero’s Andre Weil with his signature. In fact, I was fortunate enough to go to dinner with him once in Princeton in the mid-to-late 1980s – a very gentle, charming person with a deep love of mathematics. I remember he said he missed his wife, Eveline, who passed away in 1986. (They were married in 1937.)

All this is simply to motivate the question, why did I get these papers? First, as mentioned in the post, I was given Larry Goldstein‘s old office and he either was kind enough to gift me his old preprints or left them to be thrown away by the next inhabitant of his office. BTW, if you haven’t heard of him, Larry was a student of Shimura, when became a Gibbs Fellow at Yale, then went to the University of Maryland at COllege Park in 1969. He wrote lots of papers (and books) on number theory, eventually becoming a full professor, but eventually settled into computers and data science work. He left the University of Maryland about the time I arrived in the early 1980s to create some computer companies that he ran.

This motivates the question: How did Larry get these papers of Weil? I think Larry inherited them from Mountjoy (who died before Larry arrived at UMCP, but more on him later). This motivates the question, who is Mountjoy and how did he get them?

I’ve done some digging around the internet and here’s what I discovered.

The earliest mention I could find is when he was listed as a recipient of an NSF Fellowship in “Annual Report of the National Science Foundation: 1950-1953” under Chicago, Illinois, Mathematics, 1953. So he was a grad student at the University of Chicago in 1953. Andre Weil was there at the time. (He left sometime in 1958.) Mountjoy could have gotten the notes of Andre Weil then. Just before Weil left Chicago, Walter Lewis Baily arrived (in 1957, to be exact). This is important because in May 1965 the Notices of the AMS reported that reported:

Mountjoy, Robert Harbison
Abelian varieties attached to representations of discontinuous groups (S. Mac Lane and W. L. Baily)

(His thesis was published posthumously in American Journal of Mathematics Vol. 89 (1967)149-224.) This thesis is in a field studied by Weil and Baily but not Saunders.

But we’re getting ahead of ourselves. The 1962 issue of Maryland Magazine had this:


Mathematics Grant
A team of University of Maryland mathematics researchers have received a grant of $53,000 from the National Science Foundation to continue some technical investigations they started two years ago.
The mathematical study they are directing is entitled “Problems in Geometric Function Theory.” The project is under the direction of Dr. James Hummel. Dr. Mischael Zedek. and Prof. Robert H. Mountjoy, all of the Mathematics Department. They are assisted by four graduate-student researchists. The $53,000 grant is a renewal of an original grant which was made two years ago.

We know he was working at UMCP in 1962. 

Here’s the sad news. 

The newspaper Democrat and Chronicle, from Rochester, New York, on Wednesday, May 25, 1965 (Page 40) published the news that Robert H. Mountjoy “Died suddenly at Purcellville, VA, May 23, 1965”. I couldn’t read the rest (it’s behind a paywall but I could see that much). The next day, they published more: “Robert H. Mountjoy, son-in-law of Mr and Mrs Allen P Mills of Brighton, was killed in a traffic crash in Virgina. Mountjoy, about 30, a mathematics instructors at the University of Maryland, leaves a widow Sarah Mills Mountjoy and a 5-month old son Alexander, and his parents Mr and Mrs Lucius Mountjoy of Chicago.”

It’s so sad. The saying goes “May his memory be a blessing.” I never met him, but from what I’ve learned of Mountjoy, his memory is indeed a blessing.

The Riemann-Hurwitz formula for regular graphs

A little over 10 years ago, M. Baker and S. Norine (I’ve also seen this name spelled Norin) wrote a terrific paper on harmonic morphisms between simple, connected graphs (see “Harmonic morphisms and hyperelliptic graphs” – you can find a downloadable pdf on the internet of you google for it). Roughly speaking, a harmonic function on a graph is a function in the kernel of the graph Laplacian. A harmonic morphism between graphs is, roughly speaking, a map from one graph to another that preserves harmonic functions.

They proved quite a few interesting results but one of the most interesting, I think, is their graph-theoretic analog of the Riemann-Hurwitz formula. We define the genus of a simple connected graph \Gamma = (V,E) to be

{\rm genus}(\Gamma) = |E| - |V | + 1.


It represents the minimum number of edges that must be removed from the graph to make it into a tree (so, a tree has genus 0).

Riemann-Hurwitz formula (Baker and Norine): Let \phi:\Gamma_2\to \Gamma_1 be a harmonic morphism from a graph \Gamma_2 = (V_2,E_2) to a graph \Gamma_1 = (V_1, E_1). Then

{\rm genus}(\Gamma_2)-1 = {\rm deg}(\phi)({\rm genus}(\Gamma_1)-1)+\sum_{x\in V_2} [m_\phi(x)+\frac{1}{2}\nu_\phi(x)-1].

I’m not going to define them here but m_\phi(x) denotes the horizontal multiplicity and \nu_\phi(x) denotes the vertical multiplicity.

I simply want to record a very easy corollary to this, assuming \Gamma_2 = (V_2,E_2) is k_2-regular and \Gamma_1 = (V_1, E_1) is k_1-regular.

Corollary: Let \Gamma_2 \rightarrow \Gamma_1 be a non-trivial harmonic morphism from a connected k_2-regular graph
to a connected k_1-regular graph.
Then

\sum_{x\in V_2}\nu_\phi(x) = k_2|V_2| - k_1|V_1|\deg (\phi).

The number-theoretic side of J. Barkley Rosser

By chance, I ran across a reference to a paper of J Barkey Rosser and it brought back fond memories of days long ago when I would browse the stacks in the math dept library at the University of Washington in Seattle. I remember finding papers describing number-theoretic computations of Rosser and Schoenfeld. I knew nothing about Rosser. Was he a number theorist?

j-barkley-rosser1

J. Barkley Rosser, taken at Math meeting in Denver

Here’s all I could glean from different sources on the internet:
J. Barkley Rosser was born in Jacksonville, Florida in 1907. He earned both his Bachelor of Science (1929) and his Master of Science (1931) from the University of Florida. Both degrees were in physics. He obtained his Ph.D. in mathematics (in fact, mathematical logic) from Princeton University in 1934, under the supervision of Alonso Church. After getting his Ph.D., Rosser taught at Princeton, Harvard, and Cornell and spent the latter part of his career at the University of Wisconsin-Madison. As a logician, Rosser is known for his part in the Church-Rosser Theorem and the Kleene–Rosser Paradox in lambda calculus. Moreover, he served as president of the Association for Symbolic Logic. As an applied mathematician, he served as president of the Society of Industrial and Applied Mathematics (otherwise known as SIAM). While at the University of Wisconsin-Madison, he served as the director of the U.S. Army Mathematics Research Center. He continued to lecture well into his late 70s, and passed away at his home in Madison in 1989. He has a son, J. Barkley Rosser Jr, who’s an economist at James Madison University.

What about Schoenfeld?

Lowell_Schoenfeld

Lowell Schoenfeld spent his early years in New York City, graduating Cum Laude from the College of the City of New York in 1940. He went on to MIT to earn a Master’s. He received his Ph.D. in 1944 from the University of Pennsylvania under the direction of Hans Rademacher. (During his years in graduate school, he seems to have worked for the Philadelphia Navy Yard as well, writing reports on aircraft navigational computers.) After positions at Temple University and Harvard, he moved to the University of Illinois, where he met his future wife. He met Josephine M. Mitchell when she was a tenured Associate Professor and he was an untenured Assistant Professor. After they married, the University would no longer allow Mitchell to teach, so the couple both resigned their positions and eventually settled at Pennsylvania State University. They spent about 10 years there but in 1968 the couple moved to the University of Buffalo, where they remained until their retirements in the 1980s.

As far as I can tell, these are the papers they wrote together, all in analytic number theory:

[1] Rosser, J. Barkley; Schoenfeld, Lowell. “Approximate formulas for some functions of prime numbers”. Illinois J. Math. 6 (1962), no. 1, 64–94.
[2] Rosser, J. Barkley; Schoenfeld, Lowell; J.M. Yohe. “Rigorous Computation and the Zeros of the Riemann Zeta-Function,” 1969
[3] Rosser, J. Barkley; Schoenfeld, Lowell. “Sharper Bounds for the Chebyshev Functions \theta (x) and \psi (x)” Mathematics of Computation Vol. 29, No. 129 (Jan., 1975), pp. 243-269
[4] Rosser, J. Barkley; Schoenfeld, Lowell. “Approximation of the Riemann Zeta-Function” 1971.

I haven’t seen a copy of the papers [2] and [4] in years but I’m guessing these are what I looked at as a teenager in Seattle, years ago, wandering through the stacks at the UW.

Rosser also wrote papers on topics in recreational mathematics, such as magic squares. Two such papers were co-written with R.J. Walker from Cornell University, who’s more well-known for his textbook Algebraic Curves:

Rosser, Barkley; Walker, R. J. “The algebraic theory of diabolic magic squares,” Duke Math. J. 5 (1939), no. 4, 705–728
Rosser, Barkley; Walker, R. J. “On the transformation group for diabolic magic squares of order four,” Bull. Amer. Math. Soc. 44 (1938), no. 6, 416–420.

Diabolic magic squares, also called pan-diagonal magic squares, are n\times n squares of integers 1, 2, ..., n^2 whose rows all add to a constant C, whose columns all add to C, whose diagonals both add to C, and whose “broken diagonals” all add to C. An example was given by the German artist Albrecht Durer in the 1514 engraving called Melencolia I: (where C=34):

melencolia_i_1943.3.3522_diabolic-magic-square

I wish I knew more about this number-theoretic side of Rosser. He’s a very  interesting mathematician.

A table of small quartic graphs

This page is modeled after the handy wikipedia page Table of simple cubic graphs of “small” connected 3-regular graphs, where by small I mean at most 11 vertices.

These graphs are obtained using the SageMath command graphs(n, [4]*n), where n = 5,6,7,… .

5 vertices: Let V=\{0,1,2,3,4\} denote the vertex set. There is (up to isomorphism) exactly one 4-regular connected graphs on 5 vertices. By Ore’s Theorem, this graph is Hamiltonian. By Euler’s Theorem, it is Eulerian.
4reg5a: The only such 4-regular graph is the complete graph \Gamma = K_5.
graph4reg5
We have

  • diameter = 1
  • girth = 3
  • If G denotes the automorphism group then G has cardinality 120 and is generated by (3,4), (2,3), (1,2), (0,1). (In this case, clearly, G = S_5.)
  • edge set: \{(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)\}

6 vertices: Let V=\{0,1,\dots, 5\} denote the vertex set. There is (up to isomorphism) exactly one 4-regular connected graphs on 6 vertices. By Ore’s Theorem, this graph is Hamiltonian. By Euler’s Theorem, it is Eulerian.
4reg6a: The first (and only) such 4-regular graph is the graph \Gamma having edge set: \{(0, 1), (0, 2), (0, 4), (0, 5), (1, 2), (1, 3), (1, 4), (2, 3), (2, 5), (3, 4), (3, 5), (4, 5)\}.
graph4reg6
We have

  • diameter = 2
  • girth = 3
  • If G denotes the automorphism group then G has cardinality 48 and is generated by (2,4), (1,2)(4,5), (0,1)(3,5).

7 vertices: Let V=\{0,1,\dots, 6\} denote the vertex set. There are (up to isomorphism) exactly 2 4-regular connected graphs on 7 vertices. By Ore’s Theorem, these graphs are Hamiltonian. By Euler’s Theorem, they are Eulerian.
4reg7a: The 1st such 4-regular graph is the graph \Gamma having edge set: \{(0, 1), (0, 3), (0, 5), (0, 6), (1, 2), (1, 3), (1, 5), (2, 3), (2, 4), (2, 6), (3, 4), (4, 5), (4, 6), (5, 6)\}. This is an Eulerian, Hamiltonian (by Ore’s Theorem), vertex transitive (but not edge transitive) graph.
graph4reg7a
We have

  • diameter = 2
  • girth = 3
  • If G denotes the automorphism group then G has cardinality 14 and is generated by (1,5)(2,4)(3,6), (0,1,3,2,4,6,5).

4reg7b: The 2nd such 4-regular graph is the graph \Gamma having edge set: \{(0, 1), (0, 3), (0, 4), (0, 6), (1, 2), (1, 5), (1, 6), (2, 3), (2, 4), (2, 6), (3, 4), (3, 5), (4, 5), (5, 6)\}. This is an Eulerian, Hamiltonian graph (by Ore’s Theorem) which is neither vertex transitive nor edge transitive.
graph4reg7b
We have

  • diameter = 2
  • girth = 3
  • If G denotes the automorphism group then G has cardinality 48 and is generated by (3,4), (2,5), (1,3)(4,6), (0,2)

8 vertices: Let V=\{0,1,\dots, 7\} denote the vertex set. There are (up to isomorphism) exactly six 4-regular connected graphs on 8 vertices. By Ore’s Theorem, these graphs are Hamiltonian. By Euler’s Theorem, they are Eulerian.
4reg8a: The 1st such 4-regular graph is the graph \Gamma having edge set: \{(0, 1), (0, 5), (0, 6), (0, 7), (1, 3), (1, 6), (1, 7), (2, 3), (2, 4), (2, 5), (2, 7), (3, 4), (3, 6), (4, 5), (4, 6), (5, 7)\}. This is vertex transitive but not edge transitive.
graph4reg8a
We have

  • diameter = 2
  • girth = 3
  • If G denotes the automorphism group then G has cardinality 16 and is generated by (1,7)(2,3)(5,6) and (0,1)(2,4)(3,5)(6,7).

4reg8b: The 2nd such 4-regular graph is the graph \Gamma having edge set: \{(0, 1), (0, 5), (0, 6), (0, 7), (1, 3), (1, 6), (1, 7), (2, 3), (2, 4), (2, 5), (2, 7), (3, 4), (3, 6), (4, 5), (4, 6), (5, 7)\}. This is a vertex transitive (but not edge transitive) graph.
graph4reg8b
We have

  • diameter = 2
  • girth = 3
  • If G denotes the automorphism group then G has cardinality 48 and is generated by (2,3)(5,7), (1,3)(4,5), (0,1,3)(4,5,6), (0,4)(1,6)(2,5)(3,7).

4reg8c: The 3rd such 4-regular graph is the graph \Gamma having edge set: \{(0, 1), (0, 2), (0, 5), (0, 6), (1, 3), (1, 4), (1, 7), (2, 3), (2, 4), (2, 7), (3, 5), (3, 6), (4, 5), (4, 6), (5, 7), (6, 7)\}. This is a strongly regular (with “trivial” parameters (8, 4, 0, 4)), vertex transitive, edge transitive graph.
graph4reg8c
We have

  • diameter = 2
  • girth = 4
  • If G denotes the automorphism group then G has cardinality 1152=2^7\cdot 3^2 and is generated by (5,6), (4,7), (3,4), (2,5), (1,2), (0,1)(2,3)(4,5)(6,7).

4reg8d: The 4th such 4-regular graph is the graph \Gamma having edge set: \{(0, 1), (0, 2), (0, 4), (0, 6), (1, 3), (1, 5), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 6), (5, 7), (6, 7)\}. This graph is not vertex transitive, nor edge transitive.
graph4reg8d
We have

  • diameter = 2
  • girth = 3
  • If G denotes the automorphism group then G has cardinality 16 and is generated by (3,5), (1,4), (0,2)(1,3)(4,5)(6,7), (0,6)(2,7).

4reg8e: The 5th such 4-regular graph is the graph \Gamma having edge set: \{(0, 1), (0, 2), (0, 6), (0, 7), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 7), (3, 5), (3, 7), (4, 5), (4, 6), (5, 6), (6, 7)\}. This graph is not vertex transitive, nor edge transitive.
graph4reg8e
We have

  • diameter = 2
  • girth = 3
  • If G denotes the automorphism group then G has cardinality 4 and is generated by (0,1)(2,4)(3,6)(5,7), (0,2)(1,4)(3,6).

4reg8f: The 6th (and last) such 4-regular graph is the bipartite graph \Gamma=K_{4,4} having edge set: \{(0, 1), (0, 2), (0, 6), (0, 7), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 5), (3, 7), (4, 5), (4, 6), (5, 6), (5, 7), (6, 7)\}. This graph is not vertex transitive, nor edge transitive.
graph4reg8f
We have

  • diameter = 2
  • girth = 3
  • If G denotes the automorphism group then G has cardinality 12 and is generated by (3,4)(6,7), (1,2), (0,3)(5,6).

9 vertices: Let V=\{0,1,\dots, 8\} denote the vertex set. There are (up to isomorphism) exactly 16 4-regular connected graphs on 9 vertices. Perhaps the most interesting of these is the strongly regular graph with parameters (9, 4, 1, 2) (also distance regular, as well as vertex- and edge-transitive). It has an automorphism group of cardinality 72, and is referred to as d4reg9-14 below.

Without going into details, it is possible to theoretically prove that there are no harmonic morphisms from any of these graphs to either the cycle graph C_4 or the complete graph K_4. However, both d4reg9-3 and d4reg9-14 not only have harmonic morphisms to C_3, they each may be regarded as a multicover of C_3.

d4reg9-1
Gamma edges: E1 = [(0, 1), (0, 2), (0, 7), (0, 8), (1, 2), (1, 3), (1, 7), (2, 3), (2, 8), (3, 4), (3, 5), (4, 5), (4, 6), (4, 8), (5, 6), (5, 7), (6, 7), (6, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  12 
aut gp gens:  [(1,2)(4,5)(7,8), (0,1)(3,8)(5,6), (0,4)(1,5)(2,6)(3,7)] 

d4reg9_1

d4reg9-2 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 3), (1, 7), (2, 3), (2, 5), (2, 8), (3, 4), (4, 5), (4, 6), (4, 8), (5, 6), (5, 7), (6, 7), (6, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  2 
aut gp gens:  [(0,5)(1,6)(2,8)(3,4)] 

d4reg9_2

d4reg9-3 
Gamma edges: E1 = [(0, 1), (0, 2), (0, 7), (0, 8), (1, 2), (1, 3), (1, 4), (2, 3), (2, 8), (3, 4), (3, 5), (4, 5), (4, 6), (5, 6), (5, 7), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  18 
aut gp gens:  [(1,7)(2,8)(3,6)(4,5), (0,1,4,6,8,2,3,5,7)] 

d4reg9_3

d4reg9-4 
Gamma edges: E1 = [(0, 1), (0, 5), (0, 7), (0, 8), (1, 2), (1, 4), (1, 7), (2, 3), (2, 4), (2, 5), (3, 4), (3, 6), (3, 8), (4, 5), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  4 
aut gp gens:  [(2,4), (0,6)(1,3)(7,8)] 

d4reg9_4

d4reg9-5 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 5), (0, 8), (1, 2), (1, 4), (1, 7), (2, 3), (2, 5), (2, 7), (3, 4), (3, 8), (4, 5), (4, 6), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  12 
aut gp gens:  [(1,5)(2,4)(6,7), (0,1)(2,3)(4,5)(7,8)] 

d4reg9_5

d4reg9-6 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 5), (1, 6), (2, 3), (2, 5), (2, 6), (3, 4), (3, 8), (4, 5), (4, 7), (4, 8), (5, 6), (6, 7), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  8 
aut gp gens:  [(2,6)(3,7), (0,3)(1,2)(4,7)(5,6)] 

d4reg9_6

d4reg9-7 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 4), (0, 8), (1, 2), (1, 3), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (4, 5), (4, 8), (5, 6), (5, 7), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  2 
aut gp gens:  [(0,3)(1,4)(2,8)(5,6)] 

d4reg9_7

d4reg9-8 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 3), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (4, 5), (4, 6), (4, 8), (5, 6), (5, 8), (6, 7), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  2 
aut gp gens:  [(0,8)(1,5)(2,6)(3,4)] 

d4reg9_8

d4reg9-9 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 6), (0, 8), (1, 2), (1, 3), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (4, 5), (4, 7), (4, 8), (5, 6), (5, 8), (6, 7), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  4 
aut gp gens:  [(5,7), (0,3)(2,6)(4,8)] 

d4reg9_9

d4reg9-10 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 5), (0, 8), (1, 2), (1, 4), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 8), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  16 
aut gp gens:  [(2,6)(3,8), (1,5), (0,1)(2,3)(4,5)(6,8)] 

d4reg9_10

d4reg9-11 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 4), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 5), (4, 5), (4, 8), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  8 
aut gp gens:  [(2,4)(7,8), (0,2)(3,7)(4,6)(5,8)] 

d4reg9_11

d4reg9-12 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 6), (0, 8), (1, 2), (1, 4), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 8), (5, 6), (5, 8), (6, 7), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  18 
aut gp gens:  [(1,6)(2,5)(3,8)(4,7), (0,1,6)(2,7,3)(4,5,8), (0,2)(1,3)(5,8(6,7)] 

d4reg9_12

d4reg9-13 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 4), (0, 8), (1, 2), (1, 5), (1, 6), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 8), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  8 
aut gp gens:  [(2,6)(3,8), (0,1)(2,3)(4,5)(6,8), (0,4)(1,5)] 

d4reg9_13

d4reg9-14 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 4), (0, 8), (1, 2), (1, 5), (1, 8), (2, 3), (2, 5), (2, 7), (3, 4), (3, 7), (4, 5), (4, 6), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  72 
aut gp gens:  [(2,5)(3,4)(6,7), (1,3)(4,8)(5,7), (0,1)(2,3)(4,5)] 

d4reg9_14

d4reg9-15 
Gamma edges: E1 = [(0, 1), (0, 4), (0, 6), (0, 8), (1, 2), (1, 3), (1, 5), (2, 3), (2, 4), (2, 7), (3, 4), (3, 7), (4, 5), (5, 6), (5, 8), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  32 
aut gp gens:  [(6,8), (2,3), (1,4), (0,1)(2,6)(3,8)(4,5)] 

d4reg9_15

d4reg9-16 
Gamma edges: E1 = [(0, 1), (0, 3), (0, 7), (0, 8), (1, 2), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 7), (3, 8), (4, 5), (4, 6), (5, 6), (6, 7), (6, 8), (7, 8)] 
diameter:  2 
girth:  3 
is connected:  True 
aut gp size:  16 
aut gp gens:  [(7,8), (4,5), (0,1)(2,3)(4,7)(5,8), (0,2)(1,3)(4,7)(5,8)] 

d4reg9_16

10 vertices: Let V=\{0,1,\dots, 9\} denote the vertex set. There are (up to isomorphism) exactly 59 4-regular connected graphs on 10 vertices. One of these actually has an automorphism group of cardinality 1. According to SageMath: Only three of these are vertex transitive, two (of those 3) are symmetric (i.e., arc transitive), and only one (of those 2) is distance regular.

Example 1: The quartic, symmetric graph on 10 vertices that is not distance regular is depicted below. It has diameter 2, girth 4, chromatic number 3, and has an automorphism group of order 320 generated by \{(7,8), (4,6), (1,2), (1,7)(2,8)(3,4)(5,6), (0,1,3,4,7)(2,5,6,8,9)\}.

d4reg10-46a

Example 2: The quartic, distance regular, symmetric graph on 10 vertices is depicted below. It has diameter 3, girth 4, chromatic number 2, and has an automorphism group of order 240 generated by \{(2,5)(4,7), (2,8)(3,4), (1,5)(7,9), (0,1,3,2,7,6,9,8,4,5)\}.

d4reg10-51a

11 vertices: There are (up to isomorphism) exactly 265 4-regular connected graphs on 11 vertices. Only two of these are vertex transitive. None are distance regular or edge transitive.

Example 1: One of the vertex transitive graphs is depicted below. It has diameter 2, girth 4, chromatic number 3, and has an automorphism group of order 22 generated by \{(1,10)(2,9)(3,4)(5,6)(7,8), (0,1,5,4,2,7,8,9,3,6,10)\}.

Example 2:The second vertex transitive graph is depicted below. It has diameter 3, girth 3, chromatic number 4, and has an automorphism group of order 22 generated by \{(1,5)(2,7)(3,6)(4,8)(9,10), (0,1,3,2,4,10,9,8,7,6,5)\}.

Harmonic morphisms from cubic graphs of order 8 to a graph of order 4

There are five simple cubic graphs of order 8 (listed here) and there are 6 connected graphs of order 4 (listed here). But before we get started, I have a conjecture.

Let \Gamma_1 be a simple graph on n1 vertices, \Gamma_2 a simple graph on n2 vertices, and assume there is a harmonic morphism \phi:\Gamma_1 \to \Gamma_2. Call an n1-tuple of “colors” \{0,1,2,..., n2-1\} a harmonic color list (HCL) if it’s attached to a harmonic morphism in the usual way (the ith coordinate is j if \phi sends vertex i of \Gamma_1 to vertex j of \Gamma_2). Let S be the set of all such HCLs. The automorphism group G_1 of \Gamma_1 acts on S (by permuting coordinates associated to the vertices of \Gamma_1, as does the automorphism group G_2 of \Gamma_2 (by permuting the “colors” associated to the vertices of \Gamma_2). These actions commute. Clearly S decomposes as a disjoint union of distinct G_1\times G_2 orbits. The conjecture is that there is only one such orbit.

Note: Caroline Melles has disproven this conjecture. Still, the question of the number of orbits is an interesting one, IMHO.

Onto the topic of the post! The 6 connected graphs of order 4 are called P4 (the path graph), D3 (the star graph, also K_{3,1}), C4 (the cycle graph), K4 (the complete graph), Paw (C3 with a “tail”), and Diamond (K4 but missing an edge). All these terms are used on graphclasses.org. The results below were obtained using SageMath.

  1. We start with the graph \Gamma_1 listed 1st on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [2, 2, -2, -2], 2). This graph \Gamma_1 has diameter 3, girth 3, and its automorphism group G is generated by (5,6), (1,2), (0,3)(4,7), (0,4)(1,5)(2,6)(3,7), |G|=16. This graph is not vertex transitive. Its characteristic polynomial is x^8 - 12x^6 - 8x^5 + 38x^4 + 48x^3 - 12x^2 - 40x - 15. Its edge connectivity and vertex connectivity are both 2. This graph has no non-trivial harmonic morphisms to D3 or P4 or C4 or Paw. However, there are 48 non-trivial harmonic morphisms to \Gamma_2=K4. For example,
    3regular8a-K4-32103210 (the automorphism group of K4, ie the symmetric group of degree 4, acts on the colors {0,1,2,3} and produces 24 total plots), and 3regular8a-K4-01230213 (again, the automorphism group of K4, ie the symmetric group of degree 4, acts on the colors {0,1,2,3} and produces 24 total plots). There are 8 non-trivial harmonic morphisms to \Gamma_2={\rm Diamond}. For example, 3regular8a-Diamond-12033201 and 3regular8a-Diamond-10233201Here the automorphism group of K4, ie the symmetric group of degree 4, acts on the colors {0,1,2,3}, while the automorphism group of the graph \Gamma_1 acts by permuting some of the coordinates, for example, it can swap the 5th and 6th coordinates.Next, we take for \Gamma_1 the graph listed 2nd on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [4, -2, 4, 2], 2). This graph \Gamma_1 has diameter 3, girth 3, and its automorphism group G is generated by (1,7)(2,6)(3,5), (0,4)(1,3)(5,7), |G|=4 (obviously too small to act transitively on the vertices). Its characteristic polynomial is x^8 - 12x^6 - 4x^5 + 38x^4 + 16x^3 - 36x^2 - 12x + 9, its edge connectivity and vertex connectivity are both 3. This graph has no non-trivial harmonic morphisms to D3 or P4 or C4 or Paw or K4. However, it has 4 non-trivial harmonic morphisms to Diamond. They are:
    3regular8b-Diamond-32103210 3regular8b-Diamond-301230123regular8b-Diamond-123012303regular8b-Diamond-10321032Let \Gamma_1 denote the graph listed 3rd on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [2, 4, -2, 3, 3, 4, -3, -3], 1). This graph \Gamma_1 has diameter 2, girth 3, and its automorphism group G is generated by (4,6), (1,2)(3,5), (0,1)(5,7), |G|=12. It does not act transitively on the vertices. Its characteristic polynomial is x^8 - 12x^6 - 2x^5 + 36x^4 - 31x^2 + 12x and its edge connectivity and vertex connectivity are both 3.
    This graph has no non-trivial harmonic morphisms to P4 or C4 or Paw or K4 or Diamond. However, it has 6 non-trivial harmonic morphisms to D3, for example,
    3regular8c-D3-33302010
    The automorphism group of D3 (the symmetric group of degree 3) acts by permuting the colors {0,1,2,3} and so yields a total of 6=3! such harmonic color plots.Let \Gamma_1 denote the graph listed 4th on wikipedia’s Table of simple cubic graphs and defined using the sage code sage: Gamma1 = graphs.LCFGraph(8, [4, -3, 3, 4], 2). This example is especially interesting. Otherwise known as the “cube graph” Q_3, this graph \Gamma_1 has diameter 3, girth 4, and its automorphism group G is generated by ((2,4)(5,7), (1,7)(4,6), (0,1,4,5)(2,3,6,7), |G|=48. It is vertex transitive. Its characteristic polynomial is x^8 - 12x^6 + 30x^4 - 28x^2 + 9 and its edge connectivity and vertex connectivity are both 3.
    This graph has no non-trivial harmonic morphisms to D3 or P4 or Paw. However, it has 24 non-trivial harmonic morphisms to C4, 24 non-trivial harmonic morphisms to K4, and 24 non-trivial harmonic morphisms to Diamond. An example of a non-trivial harmonic morphism to K4:


    3regular8d-K4-31230210 A few examples of a non-trivial harmonic morphism to Diamond:
    3regular8d-Diamond-23320110 and
    3regular8d-Diamond-33210210 A few examples of a non-trivial harmonic morphism to C4:
    3regular8d-C4-12332100 3regular8d-C4-03322110 3regular8d-C4-33012210

    The automorphism group of C4 acts by permuting the colors {0,1,2,3} cyclically, while the automorphism group G acts by permuting coordinates. These yield more harmonic color plots.

Duursma zeta function of a graph

I’m going to start off with two big caveats:

  1. This is not Duursma‘s definition, it’s mine.
  2. I’m not convinced (yet?) that it’s a useful idea to examine such a zeta function.

So that’s your warning – you may be wasting your time reading this!

The Duursma zeta function of a linear block (error-correcting) code is due to Iwan Duursma and is a fascinating object of study. (More precisely, it’s defined for “formal” linear block codes, ie, defined via a weight enumerator polynomial with a suitable MacWilliams-like functional equation.) Sometimes it satisfies an analog of the Riemann hypothesis and sometimes it doesn’t. And sometimes that analog is still an open question.

Duursma zeta function of a code

Before we define the Duursma zeta function of a graph, we introduce the Duursma zeta function of a code.

Let C be an [n,k,d]_q code, ie a linear code over GF(q) of length n, dimension k, and minimum distance d. In general, if C is an [n,k,d]_q-code then we use [n,k^\perp,d^\perp]_q for the parameters of the dual code, C^\perp. It is a consequence of Singleton’s bound that n+2-d-d^\perp\geq , with equality when C is an MDS code. Motivated by analogies with local class field theory, in [Du] Iwan Duursma introduced the (Duursma) zeta function \zeta=\zeta_C:

\zeta_C(T)=\frac{P(T)}{(1-T)(1-qT)},
where P(T)=P_C(T) is a polynomial of degree n+2-d-d^\perp, called the zeta polynomial of C. We next sketch the definition of the zeta polynomial.

If C^\perp denotes the dual code of C, with parameters [n,n-k,d^\perp] then the MacWilliams identity relates the weight enumerator A_{C^\perp} of C^\perp to the weight enumerator A_{C} of C:

A_{C^\perp}(x,y) = |C|^{-1}A_C(x+(q-1)y,x-y).
A polynomial P(T)=P_C(T) for which

\frac{(xT+(1-T)y)^n}{(1-T)(1-qT)}P(T)=\dots +\frac{A_C(x,y)-x^n}{q-1}T^{n-d}+\dots \ .
is a (Duursma) zeta polynomial of C.

Theorem (Duursma): If C be an [n,k,d]_q code with d\geq 2 and d^\perp\geq 2 then the Duursma zeta polynomial P=P_C exists and is unique.

See the papers of Duursma for interesting properties and conjectures.

Duursma zeta function of a graph

Let \Gamma=(V,E) be a graph having |V(\Gamma)| vertices and |E(\Gamma)| edges. We define the zeta function of \Gamma via the Duursma zeta function of the binary linear code defined by the cycle space of \Gamma.

Theorem (see [DKR], [HB], [JV]): The binary code B=B_\Gamma generated by the rows of the incidence matrix of \Gamma is the cocycle space of \Gamma over GF(2), and the dual code B^\perp is the cycle space Z=Z_\Gamma of \Gamma:

B_\Gamma^\perp = Z_\Gamma.
Moreover,
(a) the length of B_\Gamma is |E|, dimension of B_\Gamma is |V|-1, and the minimum distance of B_\Gamma is the edge-connectivity of \Gamma,
(b) length of Z_\Gamma is |E|, dimension of Z_\Gamma is |E|-|V|+1, and the minimum distance of Z_\Gamma is the girth of \Gamma.

Call Z_\Gamma the cycle code and B_\Gamma the cocycle code.

Finally, we can introduce the (Duursma) zeta function \Gamma:

\zeta_\Gamma(T)=\zeta_{Z_\Gamma} =\frac{P(T)}{(1-T)(1-qT)},
where P=P_\Gamma=P_{Z_\Gamma} is the Duursma polynomial of \Gamma.

Example: Using SageMath, when \Gamma = W_5, the wheel graph on 5 vertices, we have

P_\Gamma(T) = \frac{2}{7}T^4 + \frac{2}{7}T^3 + \frac{3}{14}T^2 + \frac{1}{7}T + \frac{1}{14}.
All its zeros are of absolute value 1/\sqrt{2}.

References

[Du] I. Duursma, Combinatorics of the two-variable zeta function, in Finite fields and applications, 109–136, Lecture Notes in Comput. Sci., 2948, Springer, Berlin, 2004.

[DKR] P. Dankelmann, J. Key, B. Rodrigues, Codes from incidence matrices of graphs, Designs, Codes and Cryptography 68 (2013) 373-393.

[HB] S. Hakimi and J. Bredeson, Graph theoretic error-correcting codes, IEEE Trans. Info. Theory 14(1968)584-591.

[JV] D. Jungnickel and S. Vanstone, Graphical codes revisited, IEEE Trans. Info. Theory 43(1997)136-146.