Memories of TS Michael, by Bryan Shader

Posted on 2016/11/28 by wdjoyner

TS Michael passed away on November 22, 2016, from cancer. I will miss him as a colleague and a kind, wise soul.

TS Michael in December 2015 at the USNA

Bryan Shader has kindly allowed me to post these reminiscences that he wrote up.

Memories of TS Michael, by Bryan Shader

Indirect influence
TS indirectly influenced my choice of U. Wisconsin-Madison for graduate school. My senior year as an undergraduate, Herb Ryser gave a talk at my school. After the talk I was able to meet Ryser and asked for advice on graduate schools. Herb indicated that one of his very good undergraduate students had chosen UW-Madison and really liked the program. I later found out that the person was TS.

About the name
Back in the dark ages, universities still did registration by hand. This meant that for a couple of days before each semester the masses of students would wind their way through a maze of stations in a large gymnasium. For TS’s first 4 years, he would invariably encounter a road block because someone had permuted the words in his name (Todd Scott Michael) on one of the forms. After concretely verifying the hatcheck probabilities and fearing that this would cause some difficulties in graduating, he legally changed his name to TS Michael.

Polyominoes & Permanents
I recall many stories about how TS’s undergraduate work on polyominoes affected
his life. In particular, he recalled how once he started working on tilings on
polyominoes, he could no longer shower, or swim without visualizing polynomino
tilings on the wall’s or floor’s tiling. We shared an interest and passion for permanents (the permanent is a function of a matrix much like the determinant and plays a critical role in combinatorics). When working together we frequently would find that we both couldn’t calculate the determinant of a 3 by 3 matrix correctly, because we were calculating the permanent rather than the determinant.

Presentations and pipe-dreams
TS and I often talked about how best to give a mathematical lecture, or
presentation at a conference. Perhaps this is not at all surprising, as our common advisor (Richard Brualdi) is an incredible expositor, as was TS’s undergraduate advisor (Herb Ryser, our mathematical grandfather). TS often mentioned how Herb Ryser scripted every moment of a lecture; he knew each word he would write on the board and exactly where it would be written. TS wasn’t quite so prescriptive–but before any presentation he gave he would go to the actual room of the presentation a couple of times and run through the talk. This would include answering questions from the “pretend” audience. After being inspired by TS’s talks, I adopted this preparation method.
TS and I also fantasized about our talks ending with the audience lifting us up on their shoulders and carrying us out of the room in triumph! That is never happened to either of us (that I know of), but to have it, as a dream has always been a good motivation.

Mathematical heritage
TS was very interested in his mathematical heritage, and his mathematics brothers and sisters. TS was the 12th of Brandi’s 37 PhD students; I was the 15th. In 2005, TS and I organized a conference (called the Brualidfest) in honor of Richard Brualdi. Below I attach some photos of the design for the T-shirt.

t-shirt design for Brualdi-Fest, 1

The first image shows a biclique partition of K_5; for each color the edges of the given color form a complete bipartite graph; and each each of the completed graph on 5 vertices is in exactly one of these complete bipartite graph. This is related to one of TS’s favorite theorem: the Graham-Pollak Theorem.

t-shirt design for Bruldi-Fest, 2

The second image (when the symbols are replaced by 1s) is the incidence matrix of the projective plane of order 2; one of TS’s favorite matrices.

Here’s a photo of the Brualdi and his students at the conference:

ts-michaels_memories3

From L to R they are: John Mason (?), Thomas Forreger, John Goldwasser, Dan Pritikin, Suk-geun Hwang, Han Cho, T.S. Michael, B. Shader, Keith Chavey, Jennifer Quinn, Mark Lawrence, Susan Hollingsworth, Nancy Neudauer, Adam Berliner, and Louis Deaett.

Here’s a picture for a 2012 conference:

ts-michaels_memories4

From bottom to top: T.S. Michael (1988), US Naval Academy, MD; Bryan Shader (1990), University of Wyoming, WY; Jennifer Quinn (1993), University of Washington, Tacoma, WA; Nancy Neudauer (1998), Pacific University, OR; Susan Hollingsworth (2006), Edgewood College, WI; Adam Berliner (2009), St. Olaf College, MN; Louis Deaett (2009), Quinnipiac University, CT; Michael Schroeder (2011), Marshall University, WV; Seth Meyer (2012), Kathleen Kiernan (2012).

Here’s a caricature of TS made by Kathy Wilson (spouse of mathematician
Richard Wilson) at the Brualdifest:

TS Michael, by Kathy Wilson

Long Mathematical Discussions
During graduate school, TS and I would regularly bump into each other as we
were coming and going from the office. Often this happened as we were crossing University Avenue, one of the busiest streets in Madison. The typical conversation started with a “Hi, how are you doing? Have you considered X?” We would then spend the next 60-90 minutes on the street corner (whether it was a sweltering 90 degrees+, or a cold, windy day) considering X. In more recent years, these conversations have moved to hotel lobbies at conferences that we attend together. These discussions have been some of the best moments of my life, and through them I have become a better mathematician.

Here’s a photo of T.S. Michael with Kevin van der Meulen at the Brualdi-fest.

OLYMPUS DIGITAL CAMERA

I’m guessing they are in the midst of one of those “Have you considered X?” moments that TS is famous for.

Mathematical insight
TS has taught me a lot about mathematics, including:

How trying to generalize a result can lead to better understanding of the original result.
How phrasing a question appropriately is often the key to a mathematical breakthrough
Results that are surprising (e.g. go against ones intuition), use an elegant proof (e.g. bring in matrices in an unexpected way), and are aesthetically pleasing are worth pursing (as Piet Hein said “Problems worthy of attack, prove their worth by fighting back.”)
The struggle to present the proof of a result in the simplest, most self-contained way is important because often it produces a better understanding. If you can’t say something in a clean way, then perhaps you really don’t understand it fully.

TS’ mathematics fathers are:
Richard Brualdi ← Herb Ryser ← Cyrus MacDuffee ← Leonard Dickson ← E.H. Moore ← H. A. Newton ← Michel Chasles ← Simeon Poisoon ← Joseph Lagrange ← Leonhard Euler ← Johann Bernoulli.

Simple unsolved math problem, 4

Posted on 2016/11/23 by wdjoyner

Problem: Optimally pack n unit circles into the smallest possible equilateral triangle.

circle-packing_60_60_60_wikipedia

Let L(n) denote the length of the side of the smallest equilateral triangle in which n circles have been packed optimally. This number is, in general, unknown.

The minimum upset ranking problem

Posted on 2016/11/11 by wdjoyner

Suppose n teams play each other, and let Team $r_1 <$ Team $r_2 < \dots <$ Team $r_n$ denote some fixed ranking (where $r_1,\dots,r_n$ is some permutation of $1,\dots,n$ ). An upset occurs when a lower ranked team beats an upper ranked team. For each ranking, ${\bf r}$ , let $U({\bf r})$ denote the total number of upsets. The minimum upset problem is to find an “efficient” construction of a ranking for which $U({\bf r})$ is as small as possible.

In general, let $A_{ij}$ denote the number of times Team i beat team $j$ minus the number of times Team j beat Team i. We regard this matrix as the signed adjacency matrix of a digraph $\Gamma$ . Our goal is to find a Hamiltonian (undirected) path through the vertices of $\Gamma$ which goes the “wrong way” on as few edges as possible.

Construct the list of spanning trees of $\Gamma$ (regarded as an undirected graph).
Construct the sublist of Hamiltonian paths (from the spanning trees of maximum degree 2).
For each Hamiltonian path, compute the associated upset number: the total number of edges transversal in $\Gamma$ going the “right way” minus the total number going the “wrong way.”
Locate a Hamiltonian for which this upset number is as large as possible.

Use this sagemath/python code to compute such a Hamiltonian path.

def hamiltonian_paths(Gamma, signed_adjacency_matrix = []):
    """
    Returns a list of hamiltonian paths (spanning trees of 
    max degree <=2).

    EXAMPLES:
        sage: Gamma = graphs.GridGraph([3,3])
        sage: HP = hamiltonian_paths(Gamma)
        sage: len(HP)
        20
        sage: A = matrix(QQ,[
        [0 , -1 , 1  , -1 , -1 , -1 ],
        [1,   0 ,  -1,  1,  1,   -1  ],
        [-1 , 1 ,  0 ,  1 , 1  , -1  ],
        [1 , -1 , -1,  0 ,  -1 , -1  ],
        [1 , - 1 , - 1 , 1 , 0 , - 1  ],
        [1 ,  1  ,  1  , 1  , 1  , 0 ]
        ])
        sage: Gamma = Graph(A, format='weighted_adjacency_matrix')
        sage: HP = hamiltonian_paths(Gamma, signed_adjacency_matrix = A)
        sage: L = [sum(x[2]) for x in HP]; max(L)
        5
        sage: L.index(5)
        21
        sage: HP[21]                                 
        [Graph on 6 vertices,
         [0, 5, 2, 1, 3, 4],
         [-1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1]]
        sage: L.count(5)
        1

    """
    ST = Gamma.spanning_trees()
    if signed_adjacency_matrix == []:
        HP = []
        for X in ST:
            L = X.degree_sequence()
            if max(L)<=2:
                #print L,ST.index(X), max(L)
                HP.append(X)
        return HP
    if signed_adjacency_matrix != []:
        A = signed_adjacency_matrix
        HP = []
        for X in ST:
            L = X.degree_sequence()
            if max(L)<=2:
                #VX = X.vertices()
                EX = X.edges()
		if EX[0][1] != EX[-1][1]:
                    ranking = X.shortest_path(EX[0][0],EX[-1][1])
		else:
		    ranking = X.shortest_path(EX[0][0],EX[-1][0])
		signature = [A[ranking[i]][ranking[j]] for i in range(len(ranking)-1) for j in range(i+1,len(ranking))]
                HP.append([X,ranking,signature])
        return HP

Wessell describes this method in a different way.

Construct a matrix, $M=(M_{ij})$ , with rows and columns indexed by the teams in some fixed order. The entry in the i-th row and the j-th column is defined by $m_{ij}= \left\{ \begin{array}{rr} 0,& {\rm if\ team\ } i {\rm \ lost\ to\ team\ } j,\\ 1,& {\rm if\ team\ } i {\rm\ beat\ team\ } j,\\ 0, & {\rm if}\ i=j. \end{array} \right.$
Reorder the rows (and corresponding columns) to in a basic win-loss order: the teams that won the most games go at the
top of $M$ , and those that lost the most at the bottom.
Randomly swap rows and their associated columns, each time checking if the
number of upsets has gone down or not from the previous time. If it has gone down, we keep
the swap that just happened, if not we switch the two rows and columns back and try again.

An implementaiton of this in Sagemath/python code is:

def minimum_upset_random(M,N=10):
    """
    EXAMPLES:
        sage: M = matrix(QQ,[
        [0 , 0 , 1  , 0 , 0 , 0 ],
        [1,   0 ,  0,  1,  1,   0  ],
        [0 , 1 ,  0 ,  1 , 1  , 0  ],
        [1 , 0 , 0,  0 ,  0 , 0  ],
        [1 , 0 , 0 , 1 , 0 , 0  ],
        [1 ,  1  ,  1  , 1  , 1  , 0 ]
        ])
        sage: minimum_upset_random(M)
        (
        [0 0 1 1 0 1]                    
        [1 0 0 1 0 1]                    
        [0 1 0 0 0 0]                    
        [0 0 1 0 0 0]                    
        [1 1 1 1 0 1]                    
        [0 0 1 1 0 0], [1, 2, 0, 3, 5, 4]
        )

    """
    n = len(M.rows())
    Sn = SymmetricGroup(n)
    M1 = M
    wins = sum([sum([M1[j][i] for i in range(j,6)]) for j in range(6)])
    g0 = Sn(1)
    for k in range(N):
        g = Sn.random_element()
        P = g.matrix()
        M0 = P*M1*P^(-1)
        if sum([sum([M0[j][i] for i in range(j,6)]) for j in range(6)])>wins:
            M1 = M0
            g0 = g*g0
    return M1,g0(range(n))

Simple unsolved math problem, 3

Posted on 2016/10/22 by wdjoyner

A perfect number is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum of its positive divisors excluding the number itself. For example, 1 + 2 + 3 = 6 implies 6 is a perfect number.

Unsolved Problem: Are there any odd perfect numbers?

The belief, by some, that there are none goes back over 500 years (wikipedia).

If you want to check out some recent research into this problem, see oddperfect.org.

b5527a1273f40d19e7fa821caa0208b9

(Another unsolved problem: Are there an infinite number of even perfect numbers?)

Simple unsolved math problem, 1

Posted on 2016/10/16 by wdjoyner

In 1937 Lothar Collatz proposed the 3n+1 conjecture (known by a long list of aliases), is stated as follows.

First, we define the function $f$ on the set of positive integers:

If the number $n$ is even, divide it by two: $f(n)=n/2$ .
If the number $n$ is odd, triple it and add one: $f(n)=3n+1$ .

In modular arithmetic notation, define the function $f$ as follows:
$f(n)= {n/2},\ if \ n\equiv 0 \pmod 2$ , and $f(n)= {3n+1},\ if \ n\equiv 1 \pmod 2$ . Believe it or not, this is the restriction to the positive integers of the complex-valued map $(2+7z-(2+5z)\cos(\pi z))/4$ .

The 3n+1 conjecture is: The sequence
$n,\ f(n),\ f^2(n)=f(f(n)),\ f^3(n)=f(f^2(n)),\ \dots$
will eventually reach the number 1, regardless of which positive integer $n$ is chosen initially.

This is still unsolved, though a lot of people have worked on it. For a recent survey of results, see the paper by Chamberland.

From xkdc by Randall Munroe – https://xkcd.com/710/

Problem of the week, 137

Posted on 2016/09/18 by wdjoyner

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

Chain addition is a technique employed in cryptography for extending a short sequence of digits, called the seed to a longer sequence of pseudorandom digits. Quoting David Kahn (in Kahn on Codes, MacMillan, New York, 1983, p. 154), “the first two digits of the [seed] are added together modulo 10 [which means they are added and the carry is neglected] and the result placed at the end of the [sequence], then the second and third digits are added and the sum placed at the end, and so forth, using also the newly generated digits when the [seed] is exhausted, until the desired length is obtained”. Thus, the seed 3964 yields the sequence 3964250675632195… .

Periodic pattern

a. Show that this sequence eventually repeats itself.
b. Show that the sequence begins repeating itself with “3964”.
c. EXTRA CREDIT: How many digits are there before the first repetition of “3964”?

Problem of the week, 148

Posted on 2016/09/17 by wdjoyner

Suppose p and q are each monic polynomials of degree 4 with real coefficients and the intersection of their graphs is {(1, 3), (5, 21)}. If p(3) – q(3) = 20, what is the area enclosed by their graphs?

Problem of the week, 150

Posted on 2016/09/17 by wdjoyner

Let a, b, and c be real numbers and let f and g be real valued functions of a real variable such that $\lim_{x\to a} g(x) = b$ and $\lim_{x\to b} f(x) = c$ .
a. Give an example in which $\lim_{x\to a} f(g(x)) \not= c$ .
b. Give an additional condition on f alone and show that it
guarantees $\lim_{x\to a} f(g(x)) = c$ .
c. Give an additional condition on g alone and show that it
guarantees $\lim_{x\to a} f(g(x)) = c$ .

Odd king tours on even chessboards

Posted on 2016/09/08 by wdjoyner

This blog post discusses a paper “Odd king tours …” written with Michael Fourte (a CS undergrad at the time, now is a lawyer and Naval officer in NYC) in 1997. It was published in the now defunct Journal of Recreational Mathematics, issue 31(3), in 2003.

In the paper, we showed that there is no complete odd king tour on an even chessboard, partially answering a question raised in [BK], [S]. This post surveys that paper.

King moves on an 8×8 board.

A complete king tour on an $m\times n$ board may be represented graph theoretically as a Hamiltonian cycle on a particular graph with $mn$ vertices, of which $(m-2)\cdot (n-2)$ of them have degree $8$ , $2(m+n-4)$ have degree $5$ and the remaining $4$ vertices have degree $3$ . The problem of finding an algorithm to find a hamiltonian circuit in a general graph is known to be NP complete. The problem of finding an efficient algorithm to search for such a tour therefore appears to be very hard problem. In [BK], C. Bailey and M. Kidwell proved that complete even king tours do not exist. They left the question of the existence of complete odd tours open but showed that if they did exist then it would have to end at the edge of the board.

We shall show that
Theorem: No complete odd king tours exist on an $m\times n$ board, except possibly in the following cases:

$m=n=7$
$m=7$ and $n=8$ ,
$m >7$ , $n >7$ and $m$ or $n$ (or both) is odd,
$m>7$ , $n>7$ and the tour is “rapidly filling”.

The definition of “rapidly filling” requires some technical notation and will be given later.

Background

Before proving this, we recall briefly some definitions and results from [BK] which we shall use in our proof.

Definition: Two squares are called a neighbor pair if they have a common edge or common vertex. A neighbor pair is called completed if both squares have been visited by the the king at some point in a tour, including the case where the king is still on one of the squares. A foursome is a collection of four squares which form a $2\times 2$ array of neighboring squares on the board. A foursome is called completed if all four squares have been visited by the the king at some point in a tour, including the case where the king is still on one of the four squares.

Unless stated otherwise, after a given move of a given odd king tour, let $\Delta F$ denote the change in the number of completed foursomes and let $\Delta N$ denote the change in the number of completed neighbor pairs. Note that $\Delta N$ is equal to the total number of previously visited squares which are neighboring the king.

The following result was proven in [BK] using a counting argument.

Lemma:

The number of neighbor pairs of an $m\times n$ board is $2mn+2(m-1)(n-1)-m-n.$
(b) The number of foursomes of an $m\times n$ board is $(m-1)(n-1).$

The following result was proven in [BK] using a case-by-case argument:

Lemma: After a particular move in a given even king tour, let $\Delta F$ denote the change in the number of completed foursomes and let $\Delta N$ denote the change in the number of completed neighbor pairs. If $\Delta F=0$ then $\Delta N\geq 2$ . If $\Delta F=1$ then $\Delta N\geq 4$ . If $\Delta F=2$ then $\Delta N\geq 6$ . If $\Delta F=3$ then $\Delta N =8$ .

We shall need the proof of this lemma (for which we refer the reader to [BK]) rather than the lemma itself. The proof of this lemma implies the following:

Lemma: For an odd king tour: If $\Delta F=0$ then $Delta N\geq 1$ . If $\Delta F=1$ then $\Delta N \geq 3$ . If $\Delta F=2$ then $\Delta N\geq 5$ . If $\Delta F=3$ then $\Delta N =7$ .

The proof is omitted.

Definition: We call an odd king tour rapidly filling if there is a move in the tour such that $2\Delta F +1<\Delta N$ and $1\leq \Delta F$ .

The proof of the theorem

Proposition: If $m$ and $n$ are both even then no complete odd king tour exists.

proof: Let $N$ denote the total number of completed neighbor pairs after a given point of a given odd king tour. We may represent the values of $N$ as a sequence of numbers, $0,1,2,...$ . Here $0$ is the total number of completed neighbor pairs after the first move, $1$ for after the second move, and so on. Each time the king moves, $N$ must increase by an odd number of neighbors – either $1$ , $3$ , $5$ , or $7$ . In particular, the parity of $N$ alternates between odd and even after every move. If $m$ and $n$ are both even and if a complete odd king tour exists then the the final parity of $N$ must be odd. By the lemma above, the value of $N$ after any complete king tour is $2mn+2(m-1)(n-1)-m-n$ , which is obviously even. This is a contradiction. QED

It therefore suffices to prove the above theorem in the case where at least one of $m,n$ is odd. This follows from a computer computation, an argument from Sands [Sa], and the sequence of lemmas that follow. The proofs are in the original paper, and omitted.

Let $N$ denote the total number of completed neighbor pairs in a given odd king tour. Let $F$ denote the number of completed foursomes in a given odd king tour. Let $M$ denote the number of moves in a given odd king tour. Let $T=N-2M-2F+4.$

Lemma: Let $\Delta T=\Delta N - 2 - 2\Delta F$ , where $\Delta N ,\Delta F$ are defined as above. Then $\Delta T$ equals $-1$ , $1$ , $3$ , or $5$ . If the tour is not rapidly filling then $\Delta T\geq 1$ only occurs when $\Delta F= 0$ .

Lemma: Let $H(m,n)$ denote the largest number of non-overlapping $2\times 2$ blocks which will fit in the $m\times n$ board. There are no labelings of the $m\times n$ checkerboard by $0$ ‘s and $1$ ‘s with no $2\times 2$ blocks of $1$ ‘s and fewer than $H(m,n)$ $0$ ‘s. In particular, if there are no $2\times 2$ blocks of 1’s then there must be at least $[m/2][n/2]$ 0’s.

We conclude with a question. An odd king tour of length $mn-1$ on an $m\times n$ board will be called nearly complete. Which boards have nearly complete odd king tours? We conjecture: If $n >$ then all $7\times n$ boards have nearly complete odd king tours.

References

[BK] C. Bailey, M. Kidwell, “A king’s tour of the chessboard”, Math. Mag. 58(1985)285-286

[S] S. Sacks, “odd and even”, Games 6(1982)53.

[Sa] B. Sands, “The gunport problem”, Math. Mag. 44(1971)193-194.

Hill verses Hamming

Posted on 2016/08/05 by wdjoyner

It’s easy to imagine the 19th century Philadelphia wool dealer Frank J. Primrose as a happy man. I envision him shearing sheep during the day, while in the evening he brings his wife flowers and plays games with his little children until bedtime. However, in 1887 Frank J. Primrose was not a happy man. This is because in June of that year, he had telegraphed his agent in Kansas instructions to buy a certain amount of wool. However, the telegraph operator made a single mistake in transmitting his message and Primrose unintentionally bought far more wool than he could possibly sell. Ordinarily, such a small error has little consequence, because errors can often be detected from the context of the message. However, this was an unusual case and the mistake cost him about a half-million dollars in today’s money. He promptly sued and his case eventually made its way to the Supreme Court. The famous 1894 United States Supreme Court case Primrose v. Western Union Telegraph Company decided that the telegraph company was not liable for the error in transmission of a message.

Thus was born the need for error-correcting codes.

Introduction

Lester Hill is most famously known for the Hill cipher, frequently taught in linear algebra courses today. We describe this cryptosystem in more detail in one of the sections below, but here is the rough idea. In this system, developed and published in the 1920’s, we take a $k\times k$ matrix K, composed of integers between 0 and 25, and encipher plaintext p by $p\longmapsto c=Kp$ , where the arithmetical operations are performed mod 26. Here K is the key, which should be known only to the sender and the intended receiver, and c is the ciphertext transmitted to the receiver.

On the other hand, Richard Hamming is known for the Hamming codes, also frequently taught in a linear algebra course. This will be describes in more detail in one of the sections below, be here is the basic idea. In this scheme, developed in the 1940’s, we take a $k\times k$ matrix G over a finite field F, constructed in a very particular way, and encode a message m by $m\longmapsto c=mG$ , where the arithmetical operations are performed in F. The matrix G is called the generator matrix and c is the codeword transmitted to the receiver.

Here, in a nutshell, is the mystery at the heart of this post.

These schemes of Hill and Hamming, while algebraically very similar, have quite different aims. One is intended for secure communication, the other for reliable communication. However, in an unpublished paper [H5], Hill developed a hybrid encryption/error-detection scheme, what we shall call “Hill codes” (described in more detail below).

Why wasn’t Hill’s result published and therefore Hill, more than Hamming, known as a pioneer of error-correcting codes?

Perhaps Hill himself hinted at the answer. In an overly optimistic statement, Hill wrote (italics mine):

Further problems connected with checking operations in finite fields will be treated in another paper. Machines may be devised to render almost quite automatic the evaluation of checking elements $c_1,\dots,c_q$ according to any proposed reference matrix of the general type described in Section 7, whatever the finite field in which the operations are effected. Such machines would enable us to dispense entirely with tables of any sort, and checks could be determined with great speed. But before checking machines could be seriously planned, the following problem — which is one, incidentally, of considerable interest from the standpoint of pure number theory — would require solution.

– Lester Hill, [H5]

By my interpretation, this suggests Hill wanted to answer the question below before moving on. As simple looking as it is, this problem is still, as far as I know, unsolved at the time of this writing.

Question 1 (Hill’s Problem):
Given k and q, find the largest r such that there exists a $k\times r$ van der Monde matrix with the property that every square submatrix is non-singular.

Indeed, this is closely related to the following related question from MacWilliams-Sloane [MS77], also still unsolved at this time. (Since Cauchy matrices do give a large family of matrices with the desired property, I’m guessing Hill was not aware of them.)

Question 2: Research Problem (11.1d)
Given k and q, find the largest r such that there exists a $k\times r$ matrix having entries in GF(q) with the property that every square submatrix is non-singular.

In this post, after brief biographies, an even more brief description of the Hill cipher and Hamming codes is given, with examples. Finally, we reference previous blog posts where the above-mentioned unpublished paper, in which Hill discovered error-correcting codes, is discussed in more detail.

Short biographies

Who is Hill? Recent short biographies have been published by C. Christensen and his co-authors. Modified slightly from [C14] and [CJT12] is the following information.

Lester Sanders Hill was born on January 19, 1890 in New York. He graduated from Columbia University in 1911 with a B. A. in Mathematics and earned his Master’s Degree in 1913. He taught mathematics for a few years at Montana University, then at Princeton University. He served in the United States Navy Reserves during World War I. After the WWI, he taught at the University of Maine and then at Yale, from which he earned his Ph.D. in mathematics in 1926. His Ph.D. advisor is not definitely known at this writing but I think a reasonable guess is Wallace Alvin Wilson.

In 1927, he accepted a position with the faculty of Hunter College in New York City, and he remained there, with one exception, until his resignation in 1960 due to illness. The one exception was for teaching at the G.I. University in Biarritz in 1946, during which time he may have been reactivated as a Naval Reserves officer. Hill died January 9, 1961.

Thanks to an interview that David Kahn had with Hill’s widow reported in [C14], we know that Hill loved to read detective stories, to tell jokes and, while not shy, enjoyed small gatherings as opposed to large parties.

Who is Hamming? His life is much better known and details can be readily found in several sources.

Richard Wesley Hamming was born on February 11, 1915, in Chicago. Hamming earned a B.S. in mathematics from the University of Chicago in 1937, a masters from the University of Nebraska in 1939, and a PhD in mathematics (with a thesis on differential equations)
from the University of Illinois at Urbana-Champaign in 1942. In April 1945 he joined the Manhattan Project at the Los Alamos Laboratory, then left to join the Bell Telephone Laboratories in 1946. In 1976, he retired from Bell Labs and moved to the Naval Postgraduate School in Monterey, California, where he worked as an Adjunct Professor
and senior lecturer in computer science until his death on January 7, 1998.

Hill’s cipher

The Hill cipher is a polygraphic cipher invented by Lester S. Hill in 1920’s. Hill and his colleague Wisner from Hunter College filed a patent for a telegraphic device encryption and error-detection device which was roughly based on ideas arising from the Hill cipher. It appears nothing concrete became of their efforts to market the device to the military, banks or the telegraph company (see Christensen, Joyner and Torres [CJT12] for more details). Incidently, Standage’s excellent book [St98] tells the amusing story of the telegraph company’s failed attempt to add a relatively simplistic error-detection to telegraph codes during that time period.

Some books state that the Hill cipher never saw any practical use in the real world. However, research by historians F. L. Bauer and David Kahn uncovered the fact that the Hill cipher saw some use during World War II encrypting three-letter groups of radio call signs [C14]. Perhaps insignificant, at least compared to the practical value of Hamming codes, none-the-less, it was a real-world use.

The following discussion assumes an elementary knowledge of matrices. First, each letter is first encoded as a number, namely

$A \leftrightarrow 0, B \leftrightarrow 1, \dots, Z \leftrightarrow 25$ . The subset of the integers $\{0, 1, \dots , 25\}$ will be denoted by Z/26Z. This is closed under addition and multiplication (mod 26), and sums and products (mod 26) satisfy the usual associative and distributive properties. For R = Z/26Z, let GL(k,R) denote the set of invertible matrix transformations $T:R^k\to R^k$ (that is, one-to-one and onto linear functions).

The construction

Suppose your message m consists of n capital letters, with no spaces. This may be regarded an n-tuple M with elements in R = Z/26Z. Identify the message M as a sequence of column vectors ${\bf p}\in R^k$ . A key in the Hill cipher is a $k\times k$ matrix K, all of whose entries are in R, such that the matrix K is invertible. It is important to keep K and k secret.

The encryption is performed by computing ${\bf c} = K{\bf p},$ and rewriting the resulting vector as a string over the same alphabet. Decryption is performed similarly by computing ${\bf p} = K^{-1} {\bf c}.$ .

Example 1: Suppose m is the message “BWGN”. Transcoding into numbers, the plaintext is rewritten $p_0=1, p_1=22, p_2=6, p_3=13$ . Suppose the key is
$K=\left(\begin{array}{rr} 1 & 3 \\ 5 & 12 \end{array}\right).$
Using Hill’s encryption above gives $c_0=7,c_1=3,c_2=24,c_3=3$ . (Verification is left to the reader as an exercise.)

Security concerns: For example, this cipher is linear and can be broken by a known plaintext attack.

Hamming codes

Richard Hamming is a pioneer of coding theory, introducing the binary
Hamming codes in the late 1940’s. In the days when an computer error could crash the computer and force the programmer to retype his punch cards, Hamming, out of frustration, designed a system whereby the computer could automatically correct certain errors. The family of codes named after him can easily correct one error.

Hill’s unpublished paper

While he was a student at Yale, Hill published three papers in Telegraph and Telephone Age [H1], [H2], [H3]. In these papers Hill described a mathematical method for checking the accuracy of telegraph communications. There is some overlap with these papers and [H5], so it seems likely to me that Hill’s unpublished paper [H5] dates from this time (that is, during his later years at Yale or early years at Hunter).

In [H5], Hill describes a family of linear block codes over a finite field and an algorithm for error-detection (which can be easily extended to error-correction). In it, he states the construction of what I’ll call the “Hill codes,” (defined below), gives numerous computational examples, and concludes by recording Hill’s Problem (stated above as Question 1). It is quite possibly Hill’s best work.

Here is how Hill describes his set-up.

Our problem is to provide convenient and practical accuracy checks upon
a sequence of n elements $f_1, f_2, \dots, f_r$ in a finite algebraic
field F. We send, in place of the simple sequence $f_1, f_2, \dots, f_r$ , the amplified sequence $f_1, f_2, \dots, f_r, c_1, c_2, \dots, c_k$
consisting of the “operand” sequence and the “checking” sequence.

– Lester Hill, [H5]

Then Hill continues as follows. Let F=GF(p) denote the finite field having p elements, where $p>2$ is a prime number. The checking sequence contains k elements of F as follows:
$c_j = \sum_{i=1}^r a_{i}^jf_i,$
for $j = 1, 2, \dots, k$ . The checks are to be determined by means of a
fixed matrix
$A = \left( \begin{array}{cccc} a_{1} & a_{2} & \dots & a_{r} \\ a_{1}^2 & a_{2}^2 & \dots & a_{r}^2 \\ \vdots & & & \vdots \\ a_{1}^k & a_{2}^k & \dots & a_{r}^k \\ \end{array} \right)$
of elements of F, the matrix having been constructed according to the criteria in Hill’s Problem above. In other words, if the operand sequence (i.e., the message) is the vector ${\bf f} = (f_1, f_2, \dots, f_r)$ , then the amplified sequence (or codeword in the Hill code) to be transmitted is

${\bf c} = {\bf f}G,$
where $G = \left( I_r, A \right)$ and where $I_r$ denotes the
$r\times r$ identity matrix. The Hill code is the row space of G.

We conclude with one more open question.

Question 3:
What is the minimum distance of a Hill code?

The minimum distance of any Hamming code is 3.

Do all sufficiently long Hill codes have minimum distance greater than 3?

Summary

Most books today (for example, the excellent MAA publication written by Thompson [T83]) date the origins of the theory of error-correcting codes to the late 1940s, due to Richard Hamming. However, this paper argues that the actual birth is in the 1920s due to Lester Hill. Topics discussed include why Hill’s discoveries weren’t publicly known until relatively recently, what Hill actually did that trumps Hamming, and some open (mathematical) questions connected with Hill’s work.

For more details, see these previous blog posts.

Acknowledgements: Many thanks to Chris Christensen and Alexander Barg for
helpful and encouraging conversations. I’d like to explicitly credit Chris Christensen, as well as historian David Kahn, for the original discoveries of the source material.

Bibliography

[C14] C. Christensen, Lester Hill revisited, Cryptologia 38(2014)293-332.

[CJT12] ——, D. Joyner and J. Torres, Lester Hill’s error-detecting codes, Cryptologia 36(2012)88-103.

[H1] L. Hill, A novel checking method for telegraphic sequences, Telegraph and
Telephone Age (October 1, 1926), 456 – 460.

[H2] ——, The role of prime numbers in the checking of telegraphic communications, I, Telegraph and Telephone Age (April 1, 1927), 151 – 154.

[H3] ——, The role of prime numbers in the checking of telegraphic
communications, II, Telegraph and Telephone Age (July, 16, 1927), 323 – 324.

[H4] ——, Lester S. Hill to Lloyd B. Wilson, November 21, 1925. Letter.

[H5] ——, Checking the accuracy of transmittal of telegraphic communications by means of operations in finite algebraic fields, undated and unpublished notes, 40 pages.
(hill-error-checking-notes-unpublished)

[MS77] F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.

[Sh] A. Shokrollahi, On cyclic MDS codes, in Coding Theory and Cryptography: From Enigma and Geheimschreiber to Quantum Theory, (ed. D. Joyner), Springer-Verlag, 2000.

[St98] T. Standage, The Victorian Internet, Walker & Company, 1998.

[T83] T. Thompson, From Error-Correcting Codes Through Sphere Packings to Simple Groups, Mathematical Association of America, 1983.

Yet Another Mathblog

Tag Archives: math