Problem of the Week, #118

Posted on 2013/02/03 by wdjoyner

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

PROBLEM 118

Suppose that you draw numbers $x_1,x_2,\dots$ from $[0,1]$ randomly until $x_1+x_2+\dots +x_n$ first exceeds $1$ . What is the probability that this happens on the fourth draw? That is, what is the probability that $x_1+x_2+x_3 < 1$ and $x_1+x_2+x_3+x_4 > 1$ ?

PROBLEM 118A

In the above problem, what is the expected number of draws until the sum first exceeds $1$ ?

Problem of the Week, #117

Posted on 2013/01/28 by wdjoyner

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

PROBLEM 117

What is the largest number of regions $r(n)$ that a plane is divided into by $n$ straight lines in the plane?
Give $r(n)$ as a function of $n$ and explain why your answer is correct.

PROBLEM 117A

What is the largest number of regions $r(n, d)$ that $d$ -dimensional Euclidean space is divided into by $n$ hyperplanes?
Give $r(n, d)$ as a function of $n$ and $d$ , and find formulas for $b(n, d)$ , the number of regions that are bounded, and for $u(n, d)$ , the number of regions that are unbounded.
Of course, $r(n, d) = b(n, d) + u(n, d).$ Explain why these numbers are correct.

Problem of the Week, #116

Posted on 2013/01/24 by wdjoyner

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

PROBLEM 116

Bob invites Joe to see his new program, which prints $2 \times 2$ matrices with random integer entries. (These entries are as likely to be even as to be odd.) Joe, being a bit of a gambler, wants to bet Bob a dollar that the next matrix will have an even determinant. Should Bob take the bet? What is the probability that the next matrix will have an even determinant?

Note:
The determinant of the 2 x 2 matrix

$A = \left( \begin{array}{cc} a & b \\ c & d \\ \end{array} \right)$

is given by $det(A) = ad - bc$ .

ADVANCED PROBLEM 116A

What is the probability that the determinant of an $n \times n$ matrix with randomly chosen integer entries is divisible by the prime number $p$ ?
(Assume that the residues $0, 1, 2, ... , p-1$ are equally likely for each integer entry.)

The strange story of ternary bent functions in 2 variables

Posted on 2012/12/29 by wdjoyner

Consider a function $f:GF(3)^2\to GF(3)$ .

Such functions are often studied in terms of their Walsh(-Hadamard) transforms – a complex-valued function on $V=GF(3)^2$ that can be defined as

$W_f(u) = \sum_{x \in V} \zeta^{f(x)- \langle u,x\rangle},$
where $\zeta = e^{2\pi i/3}$ . We call $f$ bent if
$|W_f(u)|=3^{n/2},$
for all $u\in V$ (here $n=2$ ). Such ternary (or $3$ -ary) bent functions have been studied by a number of authors. Here we shall only consider those ternary bent functions of two variables which are even (in the sense $f(-x)=f(x)$ ) and $f(\vec{0})=0$ .

Thanks to a Sage computation, there are precisely $18$ such functions.

$\begin{array}{cccccccccc} {\rm bents}\backslash GF(3)^2 & (0, 0) & (1, 0) & (2, 0) & (0, 1) & (1, 1) & (2, 1) & (0, 2) & (1, 2) & (2, 2) \\ \hline b1 & 0 & 1 & 1 & 1 & 2 & 2 & 1 & 2 & 2 \\ b2 & 0 & 2 & 2 & 1 & 0 & 0 & 1 & 0 & 0 \\ b3 & 0 & 1 & 1 & 2 & 0 & 0 & 2 & 0 & 0 \\ b4 & 0 & 2 & 2 & 0 & 1 & 0 & 0 & 0 & 1 \\ b5 & 0 & 0 & 0 & 2 & 1 & 0 & 2 & 0 & 1 \\ b6 & 0 & 1 & 1 & 0 & 2 & 0 & 0 & 0 & 2 \\ b7 & 0 & 0 & 0 & 1 & 2 & 0 & 1 & 0 & 2 \\ b8 & 0 & 2 & 2 & 0 & 0 & 1 & 0 & 1 & 0 \\ b9 & 0 & 0 & 0 & 2 & 0 & 1 & 2 & 1 & 0 \\ b10 & 0 & 2 & 2 & 2 & 1 & 1 & 2 & 1 & 1 \\ b11 & 0 & 0 & 0 & 0 & 2 & 1 & 0 & 1 & 2 \\ b12 & 0 & 2 & 2 & 1 & 2 & 1 & 1 & 1 & 2 \\ b13 & 0 & 1 & 1 & 2 & 2 & 1 & 2 & 1 & 2 \\ b14 & 0 & 1 & 1 & 0 & 0 & 2 & 0 & 2 & 0 \\ b15 & 0 & 0 & 0 & 1 & 0 & 2 & 1 & 2 & 0 \\ b16 & 0 & 0 & 0 & 0 & 1 & 2 & 0 & 2 & 1 \\ b17 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ b18 & 0 & 1 & 1 & 2 & 1 & 2 & 2 & 2 & 1 \\ \end{array}$

The (edge-weighted) Cayley graph of the second function $b_2$ is shown here (thanks to Sage):

cayley graph GF3 bent

When I showed this (actually, not just this graph but the print-outs of most of these Cayley graphs) to my colleague T.S. Michael, he observed that there is only one (up to iso) strongly regular (unweighted) graph of degree $4$ with $9$ vertices, and this is it!

Here are some relationships they satisfy:

$b_1=-b_{10}, \ \ b_2=-b_3, \ \ b_4 = -b_6, \ \ b_5 = -b_7, \ \ b_8=-b_{14},$

$b_9=-b_{15}, \ \ b_{11}=-b_{16}, \ \ b_{12}=-b_{18}, \ \ b_{13}=-b_{17},$

$b_1 = b_7+b_{14} = b_6+b_{15}, \ \ b_{10} = b_{4}+b_{9} = b_{5}+b_{8}, \ \ b_{12} = b_{2}+b_{11} = b_{7}+b_{8},$

$b_{13} = b_{3}+b_{11} = b_{6}+b_{9}, \ \ b_{17} = b_{2}+b_{16} = b_{4}+b_{15,}\ \ b_{18} = b_{3}+b_{16} = b_{5}+b_{14}.$

Their supports are given as follows:

$\{1,2,3,6\} = supp(b_2)=supp(b_3), \ \ \{1,2,4,8\} = supp(b_4)=supp(b_6),$

$\{1,2,5,7\} = supp(b_8)=supp(b_{14}), \ \ \{3,5,6,7\} = supp(b_9)=supp(b_{15}),$

$\{3,4,6,8\} = supp(b_{5})=supp(b_{7}),\ \ \{4,5,7,8\} = supp(b_{11})=supp(b_{16}),$

$\{1,2,3,4,5,6,7,8\} = supp(b_{1})=supp(b_{10}) = supp(b_{12})=supp(b_{13}) = supp(b_{17})=supp(b_{18}).$

Note that all these functions are weight $4$ or weight $8$ .

In fact, my colleague David Phillips and I found that if you consider their set of supports (together with the emptyset $\emptyset$ ),

$S = \{ \emptyset \} \cup \{ {\rm supp}(f)\ |\ f:GF(3)^2\to GF(3), \ f(0)=0,\ f\ {\rm bent} \},$
then $S$ forms a group under the symmetric difference operator $\Delta$ ! In fact, $S\cong GF(2)^3$ .

I told you this was strange!

The Sage code for this is rather involved but it can be found here: hadamard_transform.sage.

[1] Sage, mathematics software, sagemath.com.

A particularly simple puzzles on round pegs

Posted on 2012/12/24 by wdjoyner

I just thought of this simple (at least I think it is simple) puzzle.

Consider a long loop of string and a number (at least 2) of round pegs of radius 1 inch each, parallel to each other. Drape the string around the pegs and pull the pegs so that the string is tight, as in the picture (which has only 3 pegs). Notice some sections of the string are straight and some are curved (shown in red in the picture).

Why is the total length of the curved sections equal to $2\pi$ ?

This is related to a pulley puzzle of Harry Langman, published in 1949.

Mathematicians and Chess

Posted on 2012/11/12 by wdjoyner

This page contains information on

which mathematicians (which we define as someone who has earned a PhD or equivalent in Mathematics) play(ed) chess at the International Master level or above (in OTB or correspondence or problem composing), and
how to get papers on mathematical chess problems.

Similar pages are here and here and here and here.

Mathematicians who play(ed) chess

Conel Hugh O’Donel Alexander (1909-1974), late British chess champion. Alexander may not have had a PhD in mathematics but taught mathematics and he did mathematical work during WWII (code and cryptography), as did the famous Soviet chess player David Bronstein (see the book Kahn, Kahn on codes). He was the strongest English player after WWII, until Jonathan Penrose appeared.
Adolf Anderssen (1818-1879). Pre World Championships but is regarded as the strongest player in the world between 1859 and 1866. He received a degree (probably not a PhD) in mathematics from Breslau University and taught mathematics at the Friedrichs gymnasium from 1847 to 1879. He was promoted to Professor in 1865 and was given an honorary doctorate by Breslau (for his accomplishments in chess) in 1865.
Magdy Amin Assem (195?-1996) specialized in p-adic representation theory and harmonic analysis on p-adic reductive groups. He published several important papers before a ruptured aneurysm tragically took his life. He was IM strength (rated 2379) in 1996.
Gedeon Barcza (1911-1986), pronounced bartsa, was a Hungarian professor of mathematics and a chess grandmaster. The opening 1.Nf3 d5 2.g3 is called the Barcza System. The opening 1.e4 e6 2.d4 c5 is known as the Barcza-Larsen Defense.
Ludwig Erdmann Bledow (1795-1846) was a German professor of mathematics (PhD). He founded the first German chess association, Berliner Schachgesellschaft, in 1827. He was the first person to suggest an international chess tournament (in a letter to von der Lasa in 1843). His chess rating is not known but he did at one point win a match against Adolf Anderssen.
Robert Coveyou (1915 – 1996) completed an M.S. degree in Mathematics, and joined the Oak Ridge National Laboratory as a research mathematician. He became a recognized expert in pseudo-random number generators. He is known for the quotation “The generation of random numbers is too important to be left to chance,” which is based on a title of a paper he wrote. An excellent tournament chess player, he was Tennessee State Champion eight times.
Nathan Divinsky (1925-2012) earned a PhD in Mathematics in 1950 from the University of Chicago and was a mathematics professor at the University of British Columbia in Vancouver. He tied for first place in the 1959 Manitoba Open.
Noam Elkies (1966-), a Professor of Mathematics at Harvard University specializing in number theory, is a study composer and problem solver (ex-world champion). Prof. Elkies, at age 26, became the youngest scholar ever to have attained a tenured professorship at Harvard. One of his endgame studies is mentioned, for example, in the book Technique for the tournament player, by GM Yusupov and IM Dvoretsky, Henry Holt, 1995. He wrote 11 very interesting columns on Endgame Exporations (posted by permission).
Some other retrograde chess constructions of his may be found at the interesting Dead Reckoning web site of Andrew Buchanan.
See also Professor Elkies’s very interesting Chess and Mathematics Seminar pages.
Thomas Ernst earned a Ph.D. in mathematics from Uppsala Univ. in 2002 and does research in algebraic combinatorics with applications to mathematical physics. His chess rating is about 2400 (FIDE).
Machgielis (Max) Euwe (1901-1981), World Chess Champion from 1935-1937, President of FIDE (Fédération Internationale des Echecs) from 1970 to 1978, and arbitrator over the turbulent Fischer – Spassky World Championship match in Reykjavik, Iceland in 1972. I don’t know as many details of his mathematical career as I’d like. One source gives: PhD (or actually its Dutch equivalent) in Mathematics from Amsterdam University in 1926. Another gives: Doctorate in philosophy in 1923 and taught as a career. Published an important paper on the mathematics of chess “Mengentheoretische Betrachtungen uber das Schachspiel”. This paper lead to a rule change in chess regarding the 3-times repetition draw.
Ed Formanek (194?-), International Master. Ph.D. Rice University 1970. Retired from the mathematics faculty at Penn State Univ. Worked primarily in matrix theory and representation theory.
Stephen L. Jones is an attorney in LA, but when younger, taught math in the UMass system and spent a term as a member of the Institute for Advanced Study in Princeton NJ. He is one rung below the level of International Master at over the board chess; in correspondence chess, he has earned two of the three norms needed to become a Grandmaster.
Charles Kalme (1939-2002), earned his master title in chess at 15, was US Junior champ in 1954, 1955, US Intercollegiate champ in 1957, and drew in his game against Bobby Fischer in the 1960 US championship. In 1960, he also was selected to be on the First Team All-Ivy Men’s Soccer team, as well as the US Student Olympiad chess team. (Incidently, it is reported that this team, which included William Lombary on board one, did so well against the Soviets in their match that Boris Spassky, board one on the Soviet team, was denied forieng travel for two years as punishment.) In 1961 graduated 1st in his class at the Moore School of Electrical Engineering, The University of Pennsylvania, in Philadelphia. He also received the Cane award (a leadership award) that year. After getting his PhD from NYU (advisor Lipman Bers) in 1967 he to UC Berkeley for 2 years then to USC for 4-5 years. He published 2 papers in mathematics in this period, “A note on the connectivity of components of Kleinian groups”, Trans. Amer. Math. Soc. 137 1969 301–307, and “Remarks on a paper by Lipman Bers”, Ann. of Math. (2) 91 1970 601–606. He also translated Siegel and Moser, Lectures on celestial mechanics, Springer-Verlag, New York, 1971, from the German original. He was important in the early stages of computer chess programming. In fact, his picture and annotations of a game were featured in the article “An advice-taking chess computer” which appeared in the June 1973 issue of Scientific American. He was an associate editor at Math Reviews from 1975-1977 and then worked in the computer industry. Later in his life he worked on trying to bring computers to elementary schools in his native Latvia A National Strategy for Bringing Computer Literacy to Latvian Schools. His highest chess rating was acheived later in his life during a “chess comeback”: 2458.
Here is his game against Bobby Fischer referred to above:[Event “?”]
[Site “New York ch-US”]
[Date “1960.??.??”]
[Round “3”]
[White “Fischer, Robert J”]
[Black “Kalme, Charles”]
[Result “1/2-1/2”]
[NIC “”]
[Eco “C92”]
[Opening “Ruy Lopez, Closed, Ragozin-Petrosian (Keres) Variation”]
1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Ba4 Nf6 5.O-O Be7 6.Re1 b5 7.Bb3 O-O 8.c3 d6 9.h3 Nd7 10.a4 Nc5 11.Bd5 Bb7 12.axb5 axb5 13.Rxa8 Qxa8 14.d4 Nd7 15.Na3 b4 16.Nc4 exd4 17.cxd4 Nf6 18.Bg5 Qd8 19.Qa4 Qa8 20.Qxa8 Rxa8 21.Bxf6 Bxf6 22.e5 dxe5 23.Ncxe5 Nxe5 24.Bxb7 Nd3 25.Bxa8 Nxe1 26.Be4 b3 27.Nd2 1/2-1/2
Miroslav Katetov (1918 -1995) earned his PhD from Charles Univ in 1939. Katetov was IM chess player (earned in 1951) and published about 70 research papers, mostly from topology and functional analysis.
Martin Kreuzer (1962-), CC Grandmaster, is rated over 2600 in correspondence chess (ICCF, as of Jan 2000). His OTB rating is over 2300. His specialty is computational commutative algebra and applications. Here is a recent game of his:
Kreuzer, M – Stickler, A
[Eco “B42”]
[Opening “Sicilian, Kan”]
1.e4 c5 2.Nf3 e6 3.d4 cxd4 4.Nxd4 a6 5.Bd3 Nc6 6.c3 Nge7 7.0-0 Ng6 8.Be3 Qc7 9.Nxc6 bxc6 10.f4 Be7 11.Qe2 0-0 12.Nd2 d5 13.g3 c5 14.Nf3 Bb7 15.exd5 exd5 16.Rae1 Rfe8 17.f5 Nf8 18.Qf2 Nd7 19.g4 f6 20.g5 fxg5 21.Nxg5 Bf6 22.Bf4 Qc6 23.Re6 Rxe6 24.fxe6 Bxg5 25.Bxg5 d4 26.Qf7+ Kh8 27.Rf3 Qd5 28.exd7 Qxg5+ 29.Rg3 Qe5 30.d8=Q+ Rxd8 31.Qxb7 Rf8 32.Qe4 Qh5 33.Qe2 Qh6 34.cxd4 cxd4 35.Bxa6 Qc1+ 36.Kg2 Qc6+ 37.Rf3 Re8 38.Qf1 Re3 39.Be2 h6 40.Kf2 Re8 41.Bd3 Qd6 42.Kg1 Kg8 43.a3 Qe7 44.b4 Ra8 45.Qc1 Qd7 46.Qf4 1-0
Emanuel Lasker (1868-1941), World Chess Champion from 1894-1921, PhD (or more precisely its German equivalent) in Mathematics from Erlangen Univ in 1902. Author of the influential paper “Zur theorie der moduln und ideale,” Math. Ann. 60(1905)20-116, where the well-known Lasker-Noether Primary Ideal Decomposition Theorem in Commutative Algebra was proven (it can be downloaded for free here). Lasker wrote and published numerous books and papers on mathematics, chess (and other games), and philosophy.
Vania Mascioni, former IECG Chairperson (IECG is the Internet Email Chess Group), is rated 2326 by IECG (as of 4-99). His area is Functional Analysis and Operator Theory.
A. Jonathan Mestel, grandmaster in over-the-board play and in chess problem solving, is an applied mathematician specializing in fluid mechanics and is the author of numerous research papers. He is on the mathematics faculty of the Imperial College in London.
Walter D. Morris (196?-), International Master. Currently on the mathematics faculty at George Mason Univ in Virginia.
Karsten Müller earned the Grandmaster title in 1998 and a PhD in mathematics in 2002 at the University of Hamburg.
John Nunn (1955-), Chess Grandmaster, D. Phil. (from Oxford Univ.) in 1978 at the age of 23. His PhD thesis is in algebraic topology. Nunn is also a GM chess problem solver.
Hans-Peter Rehm (1942-), earned his PhD in Mathematics from Karlsruhe Univ. (1970) then taught there for many years. He is a grandmaster of chess composition. He has written several papers in mathematics, such as “Prime factorization of integral Cayley octaves”, Ann. Fac. Sci. Toulouse Math (1993), but most in differential algebra, his specialty. A collection of his problems has been published as: Hans+Peter+Rehm=Schach Ausgewählte Schachkompositionen & Aufsätze (= selected chess problems and articles), Aachen 1994.
Kenneth W. Regan, Professor of Computer Science at the State Univ. of New York Buffalo, is currently rated 2453. His research is in computational complexity, a field of computer science which has a significant mathematical component.
Jakob Rosanes obtained his mathematics doctorate from the Univ. of Breslau in 1865 where he taught for the rest of his life. In the 1860s he played a match against A. Anderssen which ended with 3 wins, 3 losses, and 1 draw.
Jan Rusinek (1950-) obtained his mathematics PhD in 1978 and earned a Grandmaster of Chess Composition in 1992.
Jon Speelman (1956-) is an English Grandmaster chess player and chess writer. He earned his PhD in mathematics from Oxford.

Others that might go on this list would be Henry Ernest Atkins (he taught mathematics but never got a PhD, but won the British Chess Championship 9 times in the early 1900s), Andrew Kalotay (who earned a PhD in statistics in 1968 from the Univ of Toronto, and was a Master level chess player but was not formally given an IM chess ranking), Kenneth Rogoff (has a PhD in economics but has published statistics research papers and is a GM in chess), and Duncan Suttles (in the 1960s he started but never finished his PhD in mathematics, but is a chess GM).

Papers about mathematical problems in chess

Timothy Chow, “A Short Proof of the Rook Reciprocity Theorem”, in volume 3, 1996, of the Electronic Journal of Combinatorics.
Noam Elkies, “On numbers and endgames: Combinatorial game theory in chess endgames”, in 1996 “Games of No Chance” = Proceedings of the workshop on combinatorial games held July’94 at MSRI. Available from MSRI Publications — Volume 29 or Noam Elkies’ site.
Noam Elkies and Richard Stanley, “Chess and Mathematics” book (in preparation).
Awani Kumar, “Knight’s Tours in 3 Dimensions”, in The Games and Puzzles Journal The On-line Journal for Mathematical Recreations, Issue 43, January-April 2006.
Richard M. Low and Mark Stamp, “King and Rook Vs. King on a Quarter-Infinite Board“, in Integers, volume 6(2006).
Igor Rivin, Ilan Vardi, Paul Zimmermann, “The N-queens problem“, American Mathematical Monthly 101 (1994), no. 7, 629-639.
Lewis Benjamin Stiller, “Exploiting symmetries on parallel architecture”, PhD thesis, CS Dept, Johns Hopkins Univ. 1995 Closely related is his Games of No Chance paper, “Multilinear Algebra and Chess Endgames“.
Mario VELUCCHI’s math chess problems
Wikipedia’s, Eight queens puzzle.
Herbert S. Wilf, “The Problem of the Kings”, and Michael Larsen, “The Problem of Kings”, both in volume 2, 1995, of the Electronic Journal of Combinatorics.
Papers on odd king tours by D. Joyner and M. Fourte (appeared in the J. of Rec. Math., 2003) and even king tours by M. Kidwell and C. Bailey (in Mathematics Magazine, vol 58, 1985).
Lesson 3 in the chess lessons by Coach Epshteyn at UMBC.

Thanks to Christoph Bandelow, Max Burkett, Elaine Griffith, Hannu Lehto, John Kalme, Ewart Shaw, Richard Stanley, Will Traves, Steven Dowd, Z. Kornin, Noam Elkies and Hal Bogner for help and corrections on this page. This page is an updated version of that page and the other page.

A water sharing problem and Sage

Posted on 2012/10/18 by wdjoyner

Here is the problem: There are n students, each with a cup that could contain water or could be empty. We assume that the cups have no limit and that there is at least one student with some water. Order the students from those who have the most water to those who have the least, with arbitrary choices in cases of ties. Following this order, each student takes turn sharing his water equally with the other students. In other words, a student with r ounces of water will give r/n ounces to each of the others (and hence have r/n ounces remaining for himself).

Q1: Is it possible that there is an initial configuration so that, at the end, all the students have exactly the same amount they started with?
This would mean that sharing was in fact not a loss.

Q2: Will this process “usually even out” the distribution of water?
(Part of the answer is to try to make this question more precise!)

Q3: Does the initial ordering of the students (ie, who pours when) matter?

This can be viewed as a matrix question. The action of the i-th student sharing water can be viewed as a linear transformation $A_i$ on the vector of water quantities, indexed by the students. I think that in general the answer to Q1 is “yes.” Here is the Sage code in the case of 3 students:

sage: A1 = matrix(QQ, [[1/3,0,0],[1/3,1,0],[1/3,0,1]])
sage: A2 = matrix(QQ, [[1,1/3,0],[0,1/3,0],[0,1/3,1]])
sage: A3 = matrix(QQ, [[1,0,1/3],[0,1,1/3],[0,0,1/3]])
sage: (A1*A2*A3).eigenvectors_right()                 
[(1, [(1, 2, 3)], 1), 
 (0.1851851851851852? - 0.05237828008789241?*I, 
 [(1, 0.?e-57 + 1.414213562373095?*I, -1.000000000000000? - 1.414213562373095?*I)], 1), 
 (0.1851851851851852? + 0.05237828008789241?*I, 
 [(1, 0.?e-57 - 1.414213562373095?*I, -1.000000000000000? + 1.414213562373095?*I)], 1)]

In other words, the product $A_1A_2A_3$ has eigenvalue $\lambda = 1$ with eigenvector $\vec{v} = (1,2,3)$ . This means that in the case that student 1 has 3 ounces of water, student 2 has 2 ounces of water, student 3 has 1 ounce of water, if each student shares water as explained in the problem, at the end of the process, they will each have the same amount as they started with.

I don’t know the answer to Q2 or Q3.

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

Posted on 2012/10/06 by wdjoyner

Backstory: Lester Saunders Hill wrote unpublished notes, about 40 pages long, probably in the mid- to late 1920s. They were titled “The checking of the accuracy of transmittal of telegraphic communications by means of operations in finite algebraic fields”. In the 1960s this manuscript was given to David Kahn by Hill’s widow. The notes were typewritten, but mathematical symbols, tables, insertions, and some footnotes were often handwritten. I thank Chris Christensen, the National Cryptologic Museum, and NSA’s David Kahn Collection, for their help in obtaining these notes. Many thanks also to Rene Stein of the NSA Cryptologic Museum library and David Kahn for permission to publish this transcription. Comments by transcriber will look like this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the eighth section of his paper. I hope to post more later. (Part 7 is here.)

Section 8: Examples of finite fields

The reader is probably accustomed to the congruence notation in dealing with finite fields. It may therefore be helpful to insert here two simple examples of finite fields, and to employ, in these concrete cases, the notations of the present paper rather than those of ordinary number theory.

Example: A small field in which the number $\Gamma$ is not prime.

Let the elements of the field be the symbols or marks

$0, 1, a,b,c,d,e,f,g;$
and let us define, by means of two appended tables, the field of operations of addition and multiplcation in such a manner that the marks $0$ , $1$ represent respectively the zero and the unit elements of the field.

These tables are

$\begin{tabular}{r|*{9}{r}} \multicolumn{1}{c|} +&0&1&a&b&c&d&e&f&g\\\hline {}0&0&1&a&b&c&d&e&f&g\\ {}1&1&a&0&c&d&b&f&g&e\\ {}a&a&0&1&d&b&c&g&e&f\\ {}b&b&c&d&e&f&g&1&a&0\\ {}c&c&d&b&f&g&e&a&0&1\\ {}d&d&b&c&g&e&f&0&1&a\\ {}e&e&f&g&1&a&0&c&d&b\\ {}f&f&g&e&a&0&1&d&b&c\\ {}g&g&e&f&0&1&a&b&c&d\\ \end{tabular}$

$\begin{tabular}{r|*{9}{r}} \multicolumn{1}{c|} {*}&0&1&a&b&c&d&e&f&g\\\hline {}0&0&0&0&0&0&0&0&0&0\\ {}1&0&1&a&b&c&d&e&f&g\\ {}a&0&a&1&e&g&f&b&d&c\\ {}b&0&b&e&a&d&g&1&c&f\\ {}c&0&c&g&d&e&1&f&a&b\\ {}d&0&d&f&g&1&b&c&e&a\\ {}e&0&e&b&1&f&c&a&g&d\\ {}f&0&f &d&c&a&e&g&b&1\\ {}g&0&g&c&f&b&a&d&1&e\\ \end{tabular}$

Denoting by $x$ an arbitrary element of this field, we see that negatives and reciprocals of the elements of the field are as shown in the scheme:

$\begin{tabular}{r|rrrrrrrrr} x & 0&1&a&b&c&d&e&f&g\\ \hline -x &0&a&1&e&g&f&b&d&c\\ \hline 1/x & - &1&a&e&d&c&b&g&f \\ \end{tabular}$

The use of notations is easily illustrated. Thus, for example, we note that the determinant

$\Delta = \left| \begin{array}{ccc} f & b & g \\ 1 & f & a \\ d & e & 1 \\ \end{array} \right| \, .$
of the system of equations

$\begin{array}{r} fx+by+gz = 0\\ x+fy+az=0\\ dx+ey+z=0 \end{array}$
vanishes. For, expanding the determinant by the elements of its first row, we obtain

$\begin{array}{lcr} \Delta &= & f(f-ea) - b(1-da)+g(e-fd) \\ &= & f(f+e)+e(1+d)+g(e+b) \\ &= & fc+eb+g(0) =fc+eb=a+1 = 0. \end{array}$
Hence the system has solutions other than $x=y=z=0$ . By the usual methods, it is quickly found that one solution is ( $x=d$ , $y=1$ , $z=0$ ). The general solution is ( $x=\lambda d$ , $y=\lambda$ , $z=0$ ), where $\lambda$ denotes an element of the field.

For further practice, we note that the system of equations

$\begin{array}{rl} bx+gy &= d\\ ax+ez & = 0\\ ex+fy+az &= f \\ \end{array}$
has exactly one solution. It may be found by the standard method employing quotients of determinants [What we call today Cramer’s rule – wdj.]. or as follows:

[11 lines of hand calculations are omitted. – wdj]

The solution is $x=y=f$ , $z=c$ .
$\Box$

As noted in Section 1, the number $\Gamma$ of the elements of a finite algebraic field is either a prime integer greater than $1$ , or a positive integral power of such an integer. In the present example, we have $\Gamma = 9= 3^2$ . It may be observed in passing that if $\lambda$ is any element of a finite field for which

$\Gamma = 2^n,\ \ \ \ \ n\geq 1,$
that is, for which $\Gamma$ is a power of $2$ , then in that field $\lambda = -\lambda$ .

Example: A small field in which the number $\Gamma$ of elements is prime.

Let $f_0$ , $f_1$ , $\dots$ $f_{p-1}$ be $p$ symbols or marks, and let $p$ be a prime integer. We readily define a finite algebraic field of which the elements are the $f_i$ . To this end, we regard $f_i$ as associated with the integer $i$ which we shall call the “affix” of the mark $f_i$ . Understanding that of course $0$ is the “smallest integer” in any set of non-negative integers which includes $0$ , we now define as follows:

Sum: The sum of the marks $f_i$ and $f_j$ is given by the formula

$f_i+f_j = f_k,$
where $k$ is the smallest non-negative integer satisfying

$i+j\equiv k \pmod{p}.$

Product: The product of the marks $f_i$ and $f_j$ is given by the formula

$f_if_j = f_h,$
where $h$ is the smallest non-negative integer satisfying

$ij\equiv h \pmod{p}.$

With the operations of addition and multiplication thus defined, our set of $p$ marks constitutes, as is well-known, an algebraic field. We call a field of this type a “primary” field.
$\Box$

In a primary field, an addition table would never be required. For we note that, if

$f_{j_1}, f_{j_2}, \dots, f_{j_t},$
are $t$ elements of our field then

$\sum_{i=1}^t f_{j_i} = f_k,$
where $k$ is the smallest non-negative integer satisfying the congruence

$\sum_{i=1}^t j_i \equiv k\ \pmod{p}\ .$

Naturally, a similar statement holds for the product. We have

$\prod_{i=1}^t f_{j_i} = f_h,$
where $h$ is the smallest non-negative integer satisfying the congruence

$\prod_{i=1}^t j_i \equiv h\ \pmod{p}\ .$

In the foregoing definitions, any of the terms of a sum, or of the factors of a product, may, of course, be equal.

When dealing with a primary field, we may obviously replace the marks of the fields by their affixes. We do this in the example which follows.

Example: Let the marks of a finite field be

$0,1,2,\dots, 21, 22,$
the field containing $p=23$ elements. An addition table is not needed. The multiplication table is as follows:

$\begin{tabular}{l|rrrrrrrrrrrrrrrrrrrrrr} \ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 \\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 \\ 2 & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 & 18 & 20 & 22 & 1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 & 17 & 19 & 21 \\ 3 & 3 & 6 & 9 & 12 & 15 & 18 & 21 & 1 & 4 & 7 & 10 & 13 & 16 & 19 & 22 & 2 & 5 & 8 & 11 & 14 & 17 & 20 \\ 4 & 4 & 8 & 12 & 16 & 20 & 1 & 5 & 9 & 13 & 17 & 21 & 2 & 6 & 10 & 14 & 18 & 22 & 3 & 7 & 11 & 15 & 19 \\ 5 & 5 & 10 & 15 & 20 & 2 & 7 & 12 & 17 & 22 & 4 & 9 & 14 & 19 & 1 & 6 & 11 & 16 & 21 & 3 & 8 & 13 & 18 \\ 6 & 6 & 12 & 18 & 1 & 7 & 13 & 19 & 2 & 8 & 14 & 20 & 3 & 9 & 15 & 21 & 4 & 10 & 16 & 22 & 5 & 11 & 17 \\ 7 & 7 & 14 & 21 & 5 & 12 & 19 & 3 & 10 & 17 & 1 & 8 & 15 & 22 & 6 & 13 & 20 & 4 & 11 & 18 & 2 & 9 & 16 \\ 8 & 8 & 16 & 1 & 9 & 17 & 2 & 10 & 18 & 3 & 11 & 19 & 4 & 12 & 20 & 5 & 13 & 21 & 6 & 14 & 22 & 7 & 15 \\ 9 & 9 & 18 & 4 & 13 & 22 & 8 & 17 & 3 & 12 & 21 & 7 & 16 & 2 & 11 & 20 & 6 & 15 & 1 & 10 & 19 & 5 & 14 \\ 10 & 10 & 20 & 7 & 17 & 4 & 14 & 1 & 11 & 21 & 8 & 18 & 5 & 15 & 2 & 12 & 22 & 9 & 19 & 6 & 16 & 3 & 13 \\ 11 & 11 & 22 & 10 & 21 & 9 & 20 & 8 & 19 & 7 & 18 & 6 & 17 & 5 & 16 & 4 & 15 & 3 & 14 & 2 & 13 & 1 & 12 \\ 12 & 12 & 1 & 13 & 2 & 14 & 3 & 15 & 4 & 16 & 5 & 17 & 6 & 18 & 7 & 19 & 8 & 20 & 9 & 21 & 10 & 22 & 11 \\ 13 & 13 & 3 & 16 & 6 & 19 & 9 & 22 & 12 & 2 & 15 & 5 & 18 & 8 & 21 & 11 & 1 & 14 & 4 & 17 & 7 & 20 & 10 \\ 14 & 14 & 5 & 19 & 10 & 1 & 15 & 6 & 20 & 11 & 2 & 16 & 7 & 21 & 12 & 3 & 17 & 8 & 22 & 13 & 4 & 18 & 9 \\ 15 & 15 & 7 & 22 & 14 & 6 & 21 & 13 & 5 & 20 & 12 & 4 & 19 & 11 & 3 & 18 & 10 & 2 & 17 & 9 & 1 & 16 & 8 \\ 16 & 16 & 9 & 2 & 18 & 11 & 4 & 20 & 13 & 6 & 22 & 15 & 8 & 1 & 17 & 10 & 3 & 19 & 12 & 5 & 21 & 14 & 7 \\ 17 & 17 & 11 & 5 & 22 & 16 & 10 & 4 & 21 & 15 & 9 & 3 & 20 & 14 & 8 & 2 & 19 & 13 & 7 & 1 & 18 & 12 & 6 \\ 18 & 18 & 13 & 8 & 3 & 21 & 16 & 11 & 6 & 1 & 19 & 14 & 9 & 4 & 22 & 17 & 12 & 7 & 2 & 20 & 15 & 10 & 5 \\ 19 & 19 & 15 & 11 & 7 & 3 & 22 & 18 & 14 & 10 & 6 & 2 & 21 & 17 & 13 & 9 & 5 & 1 & 20 & 16 & 12 & 8 & 4 \\ 20 & 20 & 17 & 14 & 11 & 8 & 5 & 2 & 22 & 19 & 16 & 13 & 10 & 7 & 4 & 1 & 21 & 18 & 15 & 12 & 9 & 6 & 3 \\ 21 & 21 & 19 & 17 & 15 & 13 & 11 & 9 & 7 & 5 & 3 & 1 & 22 & 20 & 18 & 16 & 14 & 12 & 10 & 8 & 6 & 4 & 2 \\ 22 & 22 & 21 & 20 & 19 & 18 & 17 & 16 & 15 & 14 & 13 & 12 & 11 & 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \end{tabular}$

Products in which $0$ is a factor all vanish, and therefore not shown in the table.

In any algebraic field, the elements $\lambda$ and $\mu$ are negatives — $\lambda = -\mu$ , $\mu = -\lambda$ — when $\lambda+\mu=0$ . In the present example, therefore, two marks $i$ and $j$ are negatives if

$i+j\equiv 0 \pmod{23},$
where $i,j$ are momentarily regarded as ordinary integers of familiar arithmetic.

Negatives, reciprocals, squares and cubes are shown by the scheme:

$\begin{array}{l|rrrrrrrrrrrrrrrrrrrrrrr} x & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 \\ \hline -x & 0 & 22 & 21 & 20 & 19 & 18 & 17 & 16 & 15 & 14 & 13 & 12 & 11 & 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline 1/x & - & 1 & 12 & 8 & 6 & 14 & 4 & 10 & 3 & 18 & 7 & 21 & 2 & 16 & 5 & 20 & 13 & 19 & 9 & 17 & 15 & 11 & 22 \\ \hline x^2 & 0 & 1 & 4 & 9 & 16 & 2 & 13 & 3 & 18 & 12 & 8 & 6 & 6 & 8 & 12 & 18 & 3 & 13 & 2 & 16 & 9 & 4 & 1 \\ \hline x^3 & 0 & 1 & 8 & 4 & 18 & 10 & 9 & 21 & 6 & 16 & 11 & 20 & 3 & 12 & 7 & 17 & 2 & 14 & 13 & 5 & 19 & 15 & 22 \end{array}$
This field will be called $F-23$ . We shall use it in illustrating our checking operations.

Familiarity with the notations here employed may be gained by working out several exercises of simple type. Thus, the reader may note that the polynomial in $F-23$

$x^3+x^2+13x-8,$
has the three roots $x=5,6,11$ , so that we may write

$x^3+x^2+13x-8 = (x+18)(x+17)(x+12).$

He may make the important observation that no two different elements of $F-23$ have the same cube, and that this was to be expected. For the equation

$x^3-\lambda^3 = 0,$
where $\lambda$ denotes any element (other than $0$ ) of $F-23$ , can be written

$(x-\lambda)(x^2+\lambda x + \lambda^2)=0,$
the factor $x^2+\lambda x + \lambda^2$ being irreducible in $F-23$ . The fact that

$x^2+\lambda x + \lambda^2$
has no root in $F-23$ may be shown by “completing the square”, and thus noting that the roots would have to be of the form

$-\frac{\lambda}{2}(1\pm \sqrt{-3})=-\frac{\lambda}{2}(1\pm \sqrt{20}).$
But reference to the scheme of squares given above discloses that $20$ is not the square of an element in $F-23$ .
$\Box$

Boolean functions from the graph-theoretic perspective

Posted on 2012/09/08 by wdjoyner

This is a very short introductory survey of graph-theoretic properties of Boolean functions.

I don’t know who first studied Boolean functions for their own sake. However, the study of Boolean functions from the graph-theoretic perspective originated in Anna Bernasconi‘s thesis. More detailed presentation of the material can be found in various places. For example, Bernasconi’s thesis (e.g., see [BC]), the nice paper by P. Stanica (e.g., see [S], or his book with T. Cusick), or even my paper with Celerier, Melles and Phillips (e.g., see [CJMP], from which much of this material is literally copied).

For a given positive integer $n$ , we may identify a Boolean function

$f:GF(2)^n\to GF(2),$
with its support

$\Omega_f = \{x\in GF(2)^n\ |\ f(x)=1\}.$

For each $S\subset GF(2)^n$ , let $\overline{S}$ denote the set of complements $\overline{x}=x+(1,\dots,1)\in GF(2)^n$ , for $x\in S$ , and let $\overline{f}=f+1$ denote the complementary Boolean function. Note that

$\Omega_f^c=\Omega_{\overline{f}},$

where $S^c$ denotes the complement of $S$ in $GF(2)^n$ . Let

$\omega=\omega_f=|\Omega_f|$

denote the cardinality of the support. We call a Boolean function even (resp., odd) if $\omega_f$ is even (resp., odd). We may identify a vector in $GF(2)^n$ with its support, or, if it is more convenient, with the corresponding integer in $\{0,1, \dots, 2^n-1\}.$ Let

$b:\{0,1, \dots, 2^n-1\} \to GF(2)^n$

be the binary representation ordered with least significant bit last (so that, for example, $b(1)=(0,\dots, 0, 1)\in GF(2)^n$ ).

Let $H_n$ denote the $2^n\times 2^n$ Hadamard matrix defined by $(H_n)_{i,j} = (-1)^{b(i)\cdot b(j)}$ , for each $i,j$ such that $0\leq i,j\leq n-1$ . Inductively, these can be defined by

$H_1 = \left( \begin{array}{cc} 1 & 1\\ 1 & -1 \\ \end{array} \right), \ \ \ \ \ \ H_n = \left( \begin{array}{cc} H_{n-1} & H_{n-1}\\ H_{n-1} & -H_{n-1} \\ \end{array} \right), \ \ \ \ \ n>1.$
The Walsh-Hadamard transform of $f$ is defined to be the vector in ${\mathbb{R}}^{2^n}$ whose $k$ th component is

$({\mathcal{H}} f)(k) = \sum_{i \in \{0,1,\ldots,2^n-1\}}(-1)^{b(i) \cdot b(k) + f(b(i))} = (H_n (-1)^f)_k,$

where we define $(-1)^f$ as the column vector where the $i$ th component is

$(-1)^f_i = (-1)^{f(b(i))},$

for $i = 0,\ldots,2^n-1$ .

Example
A Boolean function of three variables cannot be bent. Let $f$ be defined by:

$\begin{array}{c|cccccccc} x_2 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ x_1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ x_0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \hline (-1)^f & 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ {\mathcal{H}}f & 0 & 8 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array}$
This is simply the function $f(x_0,x_1,x_2)=x_0$ . It is even because

$\Omega_f = \{ (0,0,1), (0,1,1), (1,0,1), (1,1,1) \},\ \mbox{ so } \ \omega = 4.$

Here is some Sage code verifying this:

sage: from sage.crypto.boolean_function import *
sage: f = BooleanFunction([0,1,0,1,0,1,0,1])
sage: f.algebraic_normal_form()
x0
sage: f.walsh_hadamard_transform()
(0, -8, 0, 0, 0, 0, 0, 0)

(The Sage method walsh_hadamard_transform is off by a sign from the definition we gave.) We will return to this example later.

Let $X=(V,E)$ be the Cayley graph of $f$ :

$V = GF(2)^n,\ \ \ \ E = \{(v,w)\in V\times V\ |\ f(v+w)=1\}.$
We shall assume throughout and without further mention that $f(0)\not=1,$ so $X$ has no loops. In this case, $X$ is an $\omega$ -regular graph having $r$ connected components, where

$r = |GF(2)^n/{\rm Span}(\Omega_f)|.$

For each vertex $v\in V$ , the set of neighbors $N(v)$ of $v$ is given by

$N(v)=v+\Omega_f,$

where $v$ is regarded as a vector and the addition is induced by the usual vector addition in $GF(2)^n$ . Let $A = (A_{ij})$ be the $2^n\times 2^n$ adjacency matrix of $X$ , so

$A_{ij} = f(b(i)+b(j)), \ \ \ \ \ 0\leq i,j\leq 2^n-1.$

Example:
Returning to the previous example, we construct its Cayley graph.

First, attach afsr.sage from [C] in your Sage session.

     sage: flist = [0,1,0,1,0,1,0,1]
     sage: V = GF(2)ˆ3
     sage: Vlist = V.list()
     sage: f = lambda x: GF(2)(flist[Vlist.index(x)])
     sage: X = boolean_cayley_graph(f, 3)
     sage: X.adjacency_matrix()
     [0 1 0 1 0 1 0 1]
     [1 0 1 0 1 0 1 0]
     [0 1 0 1 0 1 0 1]
     [1 0 1 0 1 0 1 0]
     [0 1 0 1 0 1 0 1]
     [1 0 1 0 1 0 1 0]
     [0 1 0 1 0 1 0 1]
     [1 0 1 0 1 0 1 0]
     sage: X.spectrum()
     [4, 0, 0, 0, 0, 0, 0, -4]
     sage: X.show(layout="circular")

In her thesis, Bernasconi found a relationship between the spectrum of the Cayley graph $X$ ,

${\rm Spectrum}(X) = \{\lambda_k\ |\ 0\leq k\leq 2^n-1\},$

(the eigenvalues $\lambda_k$ of the adjacency matrix $A$ ) to the Walsh-Hadamard transform $\mathcal H f = H_n (-1)^f$ . Note that $f$ and $(-1)^f$ are related by the equation $f=\frac 1 2 (e - (-1)^f),$ where $e=(1,1,...,1)$ . She discovered the relationship

$\lambda_k = \frac 1 2 (H_n e - \mathcal H f)_k$

between the spectrum of the Cayley graph $X$ of a Boolean function and the values of the Walsh-Hadamard transform of the function. Therefore, the spectrum of $X$ , is explicitly computable as an expression in terms of $f$ .

References:

[BC] A. Bernasconi and B. Codenotti, Spectral analysis of Boolean functions as a graph eigenvalue problem, IEEE Trans. Computers 48(1999)345-351.

[CJMP] Charles Celerier, David Joyner, Caroline Melles, David Phillips, On the Hadamard transform of monotone Boolean functions, Tbilisi Mathematical Journal, Volume 5, Issue 2 (2012), 19-35.

[S] P. Stanica, Graph eigenvalues and Walsh spectrum of Boolean functions, Integers 7(2007)\# A32, 12 pages.

Here’s an excellent video of Pante Stanica on interesting applications of Boolean functions to cryptography (30 minutes):

The mathematics of Midway

Posted on 2012/09/05 by wdjoyner

The battle of Midway was a historic turning point for the US during World War II. Joe Rochefort was the officer in charge of Station Hypo, a group of hand-picked Navy cryptographers tasked with breaking the Japanese Navy cipher. The machine the Japanese used was the JN-25. Unlike the British Bletchley Park cryptographers trying to break the Enigma traffic, he cryptographers did not have a version of the JN-25 machine. The fascinating story of Rochefort is explained brilliantly in the 2011 book “Joe Rochefort’s War” by Elliot Carlson.
Recently, Chris Christensen of Northern Kentucky University, one of the top historical experts on the US Navy cryptographers during WWII, have two lectures on the mathematics behind breaking the JN-25 ciphers.

45 minutes:

30 minutes: