Let’s do the Landau shuffle

Here’s a shuffle I’ve not seen before:

  1. Take an ordinary deck of 52 cards and place them, face up, in the following pattern:
    Going from the top of the deck to the bottom, placing cards down left-to-right, put 13 cards in the top row:
    \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\
    11 cards in the next row:
    \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\
    then 9 cards in the next row:
    \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\
    then 7 cards in the next row:
    \Box\ \Box\ \Box\ \Box\ \Box\ \Box\ \Box\
    then 5 cards in the next row:
    \Box\ \Box\ \Box\ \Box\ \Box\
    then 3 cards in the next row:
    \Box\ \Box\ \Box\
    and finally, the remaining 4 cards in the last row:
    \Box\ \Box\ \Box\ \Box\
  2. Now, take the left-most card in each row and move it to the right of the others (effectively, this is a cyclic shift of that row of cards to the left).
  3. Finally, reassemble the deck by reversing the order of the placement.

In memory of the great German mathematician Edmund Landau (1877-1938, see also this bio), I call this the Landau shuffle. As with any card shuffle, this shuffle permutes the original ordering of the cards. To restore the deck to it’s original ordering you must perform this shuffle exactly 180180 times. (By the way, this is called the order of the shuffle.) Yes, one hundred eighty thousand, one hundred and eighty times. Moreover, no other shuffle than this Landau shuffle will require more repetitions to restore the deck. So, in some sense, the Landau shuffle is the shuffle that most effectively rearranges the cards.

Now suppose we have a deck of n (distictly labeled) cards, where n>2 is an integer. The collection of all possible shuffles, or permutations, of this deck is denoted S_n and called the symmetric group. The above discussion leads naturally to the following question(s).

Question: What is the largest possible order of a shuffle of this deck (and how do you construct it)?

This requires a tiny bit of group theory. You only need to know that any permutation of n symbols (such as the card deck above) can be decomposed into a composition or product) of disjoint cycles. To compute the order of an element g \in S_n, write that element g in disjoint cycle notation. Denote the lengths of the disjoint cycles occurring in g as k_1, k_2, \dots , k_m, where k_i>0 are integers forming a partition of n: n = k_1 + k_2 +\dots + k_m. Then the order of g is known to be given by order(g) = LCM(k_1, k_2, ...., k_m), where LCM denotes the least common multiple.

The Landau function g(n) is the function that returns the maximum possible order of an element g \in S_n. Landau introduced this function in a 1903 paper where he also proved the asymptotic relation \lim_{n\to \infty} \frac{\ln(g(n))}{\sqrt{n\ln(n)}}=1.

Example: If n=52 then note 52 = 13+11+9+7+5+3+4 and that LCM(13,11,9,77,5,3,4)=180180.

Oddly, my favorite mathematical software program SageMath does not have an implementation of the Landau function, so we end with some SageMath code.

def landau_function(n):
L = Partitions(n).list()
lcms = [lcm(P) for P in L]
return max(lcms)

Here is an example (the time is included to show this took about 2 seconds on my rather old mac laptop):

sage: time landau_function(52)
CPU times: user 1.91 s, sys: 56.1 ms, total: 1.97 s
Wall time: 1.97 s
180180

Coding Theory and Cryptography

This was once posted on my USNA webpage. Since I’ve retired, I’m going to repost it here.

Coding Theory and Cryptography:
From Enigma and Geheimschreiber to Quantum Theory

(David Joyner, ed.) Springer-Verlag, 2000.
ISBN 3-540-66336-3

Summary: These are the proceedings of the “Cryptoday” Conference on Coding Theory, Cryptography, and Number Theory held at the U. S. Naval Academy during October 25-26, 1998. This book concerns elementary and advanced aspects of coding theory and cryptography. The coding theory contributions deal mostly with algebraic coding theory. Some of these papers are expository, whereas others are the result of original research. The emphasis is on geometric Goppa codes, but there is also a paper on codes arising from combinatorial constructions. There are both, historical and mathematical papers on cryptography.
Several of the contributions on cryptography describe the work done by the British and their allies during World War II to crack the German and Japanese ciphers. Some mathematical aspects of the Enigma rotor machine and more recent research on quantum cryptography are described. Moreover, there are two papers concerned with the RSA cryptosystem and related number-theoretic issues.

Chapters

  • Reminiscences and Reflections of a Codebreaker, by Peter Hilton pdf
  • FISH and I, by W. T. Tutte pdf
  • Sturgeon, The FISH BP Never Really Caught, by Frode Weierud, pdf
  • ENIGMA and PURPLE: How the Allies Broke German and Japanese Codes During the War, by David A. Hatch pdf
  • The Geheimschreiber Secret, by Lars Ulfving, Frode Weierud pdf
  • The RSA Public Key Cryptosystem, by William P. Wardlaw pdf
  • Number Theory and Cryptography (using Maple), by John Cosgrave pdf
  • A Talk on Quantum Cryptography or How Alice Outwits Eve, by Samuel J. Lomonaco, Jr. pdf
  • The Rigidity Theorems of Hamada and Ohmori, Revisited, by T. S. Michael pdf
  • Counting Prime Divisors on Elliptic Curves and Multiplication in Finite Fields, by M. Amin Shokrollahi pdf,
  • On Cyclic MDS-Codes, by M. Amin Shokrollahi pdf
  • Computing Roots of Polynomials over Function Fields of Curves, by Shuhong Gao, M. Amin Shokrollahi pdf
  • Remarks on codes from modular curves: MAPLE applications, by David Joyner and Salahoddin Shokranian, pdf

For more cryptologic history, see the National Cryptologic Museum.


This is now out of print and will not be reprinted (as far as I know). The above pdf files are posted by written permission. I thank Springer-Verlag for this.

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 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).

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)\}.

NCF Boolean functions

I recently learned about a new class of seemingly complicated, but in fact very simple functions which are called by several names, but perhaps most commonly as NCF Boolean functions (NCF is an abbreviation for “nested canalyzing function,” a term used by mathematical biologists). These functions were independently introduced by theoretical computer scientists in the 1960s using the term unate cascade functions. As described in [JRL2007] and [LAMAL2013], these functions have applications in a variety of scientific fields. This post describes these functions.

A Boolean function of n variables is simply a function f:GF(2)^n\to GF(2). Denote the GF(2)-vector space of such functions by B(n). We write an element of this space as f(x_1,x_2,\dots,x_n), where the variables x_i will be called coordinate variables. Let
Res_{x_i=a}:B(n)\to B(n-1)
denote the restriction map sending f(x_1,x_2,\dots,x_n) to f(x_1,x_2,\dots,x_{i-1},a,x_{i+1},\dots, x_n). In this post, the cosets
H_{i,a,n}=\{x=(x_1,x_2,\dots,x_n) \in GF(2)^n\ |\ x_i=a\}
will be called coordinate hyperplanes (a \in GF(2), 1\leq i\leq n). A function in B(n) which is constant along some coordinate hyperplane is called canalyzing. An NCF function is a function f\in B(n) which (a) is constant along some coordinate hyperplane H_{i_1,a_1,n}, (b) whose restriction f_1 = Res_{x_{i_1}=a_1}(f)\in B(n-1) is constant along some coordinate hyperplane H_{i_2,a_2,n-1}\subset GF(2)^{n-1}, (c) whose restriction f_2 = Res_{x_{i_2}=a_2}(f_1)\in B(n-2) is constant along some coordinate hyperplane H_{i_2,a_2,n-2}\subset GF(2)^{n-2}, (d) and so on. This “nested” inductive definition might seem complicated, but to a computer it’s pretty simple and, to boot, it requires little memory to store.

If 1\leq i\leq n and x=(x_1,x_2,\dots,x_n) \in GF(2)^n then let x^i\in GF(2)^n denote the vector whose i-th coordinate is flipped (bitwise). The sensitivity of f\in B(n) at x is
s(f,x) = |\{i\ |\ 1\leq i\leq n, f(x)\not= f(x^i)\}|. Roughly speaking, it’s the number of single-bit changes in x that change the value of f(x). The (maximum) sensitivity is the quantity
s(f)=max_x s(f,x). The block sensitivity is defined similarly, but you allow blocks of indices of coordinates to by flipped bitwise, as opposed to only one. It’s possible to

  • compute the sensitivity of any NCF function,
  • show the block sensitivity is equal to the sensitivity,
  • compute the cardinality of the set of all monotone NCF functions.

For details, see for example Li and Adeyeye [LA2012].

REFERENCES
[JRL2007] A.S. Jarrah, B. Raposa, R. Laubenbachera, “Nested Canalyzing, Unate Cascade, and Polynomial Functions,” Physica D. 2007 Sep 15; 233(2): 167–174.

[LA2012] Y. Li, J.O. Adeyeye, “Sensitivity and block sensitivity of nested canalyzing function,” ArXiV 2012 preprint. (A version of this paper was published later in Theoretical Comp. Sci.)

[LAMAL2013] Y. Li, J.O. Adeyeye, D. Murrugarra, B. Aguilar, R. Laubenbacher, “Boolean nested canalizing functions: a comprehensive analysis,” ArXiV, 2013 preprint.

Differential equations and SageMath

The files below were on my teaching page when I was a college teacher. Since I retired, they disappeared. Samuel Lelièvre found an archived copy on the web, so I’m posting them here.

The files are licensed under the Attribution-ShareAlike Creative Commons license.

  1. Partial fractions handout, pdf
  2. Introduction to matrix determinants handout, pdf
  3. Impulse-response handout, pdf
  4. Introduction to ODEs, pdf
  5. Initial value problems, pdf
  6. Existence and uniqueness, pdf
  7. Euler’s method for numerically approximating solutions to DEs, pdf.
    Includes both 1st order DE case (with Euler and improved Euler) and higher order DE and systems of DEs cases, without improved Euler.
  8. Direction fields and isoclines, pdf
  9. 1st order ODEs, separable and linear cases, pdf
  10. A falling body problem in Newtonian mechanics, pdf
  11. A mixing problem, pdf
  12. Linear ODEs, I, pdf
  13. Linear ODEs, II, pdf
  14. Undetermined coefficients for non-homogeneous 2nd order constant coefficient ODEs, pdf
  15. Variation of parameters for non-homogeneous 2nd order constant coefficient ODEs, pdf.
  16. Annihilator method for non-homogeneous 2nd order constant coefficient ODEs, pdf.
    I found students preferred (the more-or-less equivalent) undetermined coefficient method, so didn’t put much effort into these notes.
  17. Springs, I, pdf
  18. Springs, II, pdf
  19. Springs, III, pdf
  20. LRC circuits, pdf
  21. Power series methods, I, pdf
  22. Power series methods, II, pdf
  23. Introduction to Laplace transform methods, I, pdf
  24. Introduction to Laplace transform methods, II, pdf
  25. Lanchester’s equations modeling the battle between two armies, pdf
  26. Row reduction/Gauss elimination method for systems of linear equations, pdf.
  27. Eigenvalue method for homogeneous constant coefficient 2×2 systems of 1st order ODEs, pdf.
  28. Variation of parameters for first order non-homogeneous linear constant coefficient systems of ODEs, pdf.
  29. Electrical networks using Laplace transforms, pdf
  30. Separation of variables and the Transport PDE, pdf
  31. Fourier series, pdf.
  32. one-dimensional heat equation using Fourier series, pdf.
  33. one-dimensional wave equation using Fourier series, pdf.
  34. one-dimensional Schroedinger’s wave equation for a “free particle in a box” using Fourier series, pdf.
  35. All these lectures collected as one pdf (216 pages).
    While licensed Attribution-ShareAlike CC, in the US this book is in the public domain, as it was written while I was a US federal government employee as part of my official duties. A warning – it has lots of typos. The latest version, written with Marshall Hampton, is a JHUP book, much more polished, available on amazon and the JHUP website. Google “Introduction to Differential Equations Using Sage”.

Course review: pdf

Love, War, and Zombies, pdf
This set of slides is of a lecture I would give if there was enough time towards the end of the semester

Integral Calculus and SageMath

Long ago, using LaTeX I assembled a book on Calculus II (integral calculus), based on notes of mine, Dale Hoffman (which was written in word), and William Stein. I ran out of energy to finish it and the source files mostly disappeared from my HD. Recently, Samuel Lelièvre found a copy of the pdf of this book on the internet (you can download it here). It’s licensed under a Creative Commons Attribution 3.0 United States License. You are free to print, use, mix or modify these materials as long as you credit the original authors.

Table of Contents

0 Preface

1 The Integral
1.1 Area
1.2 Some applications of area
1.2.1 Total accumulation as “area”
1.2.2 Problems
1.3 Sigma notation and Riemann sums
1.3.1 Sums of areas of rectangles
1.3.2 Area under a curve: Riemann sums
1.3.3 Two special Riemann sums: lower and upper sums
1.3.4 Problems
1.3.5 The trapezoidal rule
1.3.6 Simpson’s rule and Sage
1.3.7 Trapezoidal vs. Simpson: Which Method Is Best?
1.4 The definite integral
1.4.1 The Fundamental Theorem of Calculus
1.4.2 Problems
1.4.3 Properties of the definite integral
1.4.4 Problems
1.5 Areas, integrals, and antiderivatives
1.5.1 Integrals, Antiderivatives, and Applications
1.5.2 Indefinite Integrals and net change
1.5.3 Physical Intuition
1.5.4 Problems
1.6 Substitution and Symmetry
1.6.1 The Substitution Rule
1.6.2 Substitution and definite integrals
1.6.3 Symmetry
1.6.4 Problems

2 Applications
2.1 Applications of the integral to area
2.1.1 Using integration to determine areas
2.2 Computing Volumes of Surfaces of Revolution
2.2.1 Disc method
2.2.2 Shell method
2.2.3 Problems
2.3 Average Values
2.3.1 Problems
2.4 Moments and centers of mass
2.4.1 Point Masses
2.4.2 Center of mass of a region in the plane
2.4.3 x-bar For A Region
2.4.4 y-bar For a Region
2.4.5 Theorems of Pappus
2.5 Arc lengths
2.5.1 2-D Arc length
2.5.2 3-D Arc length

3 Polar coordinates and trigonometric integrals
3.1 Polar Coordinates
3.2 Areas in Polar Coordinates
3.3 Complex Numbers
3.3.1 Polar Form
3.4 Complex Exponentials and Trigonometric Identities
3.4.1 Trigonometry and Complex Exponentials
3.5 Integrals of Trigonometric Functions
3.5.1 Some Remarks on Using Complex-Valued Functions

4 Integration techniques
4.1 Trigonometric Substitutions
4.2 Integration by Parts
4.2.1 More General Uses of Integration By Parts
4.3 Factoring Polynomials
4.4 Partial Fractions
4.5 Integration of Rational Functions Using Partial Fractions
4.6 Improper Integrals
4.6.1 Convergence, Divergence, and Comparison

5 Sequences and Series
5.1 Sequences
5.2 Series
5.3 The Integral and Comparison Tests
5.3.1 Estimating the Sum of a Series
5.4 Tests for Convergence
5.4.1 The Comparison Test
5.4.2 Absolute and Conditional Convergence
5.4.3 The Ratio Test
5.4.4 The Root Test
5.5 Power Series
5.5.1 Shift the Origin
5.5.2 Convergence of Power Series
5.6 Taylor Series
5.7 Applications of Taylor Series
5.7.1 Estimation of Taylor Series

6 Some Differential Equations
6.1 Separable Equations
6.2 Logistic Equation

7 Appendix: Integral tables

Problem of the Week, #121

A former 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.

Problem 121

The Maryland “Big Game” lottery is played by selecting 5 different numbers in \{ 1,2,3,\dots, 50\} and then selecting one of the numbers in \{ 1,2,3,\dots, 36\}. The first section is an unordered selection without replacement (so, arrange them in increasing order if you like) but the second selection can repeat one of the 5 numbers initially picked.

How many ways can this be done?