# Michael Reid’s Happy New Year Puzzles, 2018

Belatedly posted by permission of Michael Reid. Enjoy!

Here are some New Year’s puzzles to help start out 2018.

1. Arrange the ten digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 in the
expression $a^b + c^d + e^f + g^h + i^j$ to make 2018.

2. (a) Express $2018 = p^q + r^s$ where p, q, r, s are primes.
(b) Express $2018 = p^q - r^s$ where p, q, r, s are primes.

3. (a) Is it possible to put the first 9 primes, 2, 3, 5, 7, 11, 13,
17, 19 and 23 into a 3×3 matrix that has determinant 2018?
(b) Is it possible to put the first 16 primes, 2, 3, 5, … , 53,
into a 4×4 matrix that has determinant 2018?

4. (a) Express 2018 = A / B using the fewest number of distinct
digits.
For example, the expression 7020622 / 3479 uses only seven
different digits. But it is possible to do better than this.
(b) Express $2018 = (A_1 \cdot A_2 \cdot ... \cdot A_m) / (B_1 \cdot B_2 \cdot ... \cdot B_n)$ using the fewest number of distinct digits.

# Michael Reid’s Happy New Year Puzzle, 2017

Belatedly posted by permission of Michael Reid. Enjoy!

Here are some interesting puzzles to start the New Year; hopefully they are not too easy!

1. Express 2017 as a quotient of palindromes.

2. (a) Are there two positive integers whose sum is 2017 and whose product
is a palindrome?
(b) Are there two positive integers whose difference is 2017 and whose
product is a palindrome?

3. Is there a positive integer n such that both 2017 + n and
2017 n are palindromes?

4. What is the smallest possible sum of the decimal digits of 2017 n ,
where n is …
(a) … a positive integer?
(b) … a prime number?
(c) … a palindrome?

5. Consider the following two operations on a positive integer:
(i) replace a string of consecutive digits by its square,
(ii) if a string of consecutive digits is a perfect cube,
replace the string by its cube root.

Neither the string being replaced, nor its replacement, may have
have “leading zeros”. For example, from 31416 , we may change it to
319616 , by squaring the 14 . From 71253 , we may change it to
753 by taking the cube root of 125 .

(a) Starting from the number 2017 , what is the smallest number we
can reach with a sequence of these operations?
(b) What is the smallest number from which we can start, and reach
the number 2017 with a sequence of these operations?

6. Find a list of positive rational numbers, q_1 , q_2 , … , q_n
whose product is 1 , and whose sum is 2017 . Make your list as
short as possible.
Extra Credit: Prove that you have the shortest possible list.

# Michael Reid’s Happy New Year Problems, 2020

Posted by permission of Michael Reid. Enjoy!

New Year’s Greetings!

Here are some fun puzzles to start the year.

1. Substitute the numbers 1, 2, … , 9 for the letters
a, b, … , i in the expression $a^b + c^d + (e + f + g - h)^i$
to get 2020.

2. Use the digits 1, 2, … , 9 in order, and any of the usual
arithmetic operations and parentheses to get a number that is
as close as possible to, but not exactly equal to 2020.

3. Express 2019/2020 as a sum of distinct Egyptian fractions,
i.e. $1 / n_1 + 1 / n_2 + ... + 1 / n_k$ for integers $0 < n_1 < n_2 < ... n_k < 202049$
(but 202049 is not square).

5. Make a 4×4 matrix of single-digit integers (0-9) with digits
2, 0, 2, 0 on the main diagonal, and having determinant 2020.
Is it possible to do it with a symmetric matrix?

If you liked this one, check out other puzzles ont this blog tagged with “Michael Reid”.

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

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

# 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?

Let $P$ denote the set of all primes and, for $p \in P$, let $(*/p)$ denote the Legendre quadratic residue symbol mod p. Let ${\mathbb N}=\{1,2,\dots\}$ denote the set of natural numbers and let

$L: {\mathbb N}\to \{-1,0,1\}^P,$

denote the mapping $L(n)=( (n/2), (n/3), (n/5), \dots),$ so the $k$th component of $L(n)$ is $L(n)_k=(n/p_k)$ where $p_k$ denotes the $k$th prime in $P$. The following result is “well-known” (or, as the joke goes, it’s well-known to those who know it well:-).

Theorem: The restriction of $L$ to the subset ${\mathbb S}$ of square-free integers is an injection.

In fact, one can be a little more precise. Let $P_{\leq M}$ denote the set of the first $M$ primes, let ${\mathbb S}_N$ denote the set of square-free integers $\leq N$, and let

$L_M: {\mathbb N}\to \{-1,0,1\}^{P_M},$

denote the mapping $L_M(n)=( (n/2), (n/3), (n/5), \dots, (n/p_M)).$

Theorem: For each $N>1$, there is an $M=M(N)>1$ such that the restriction of $L_M$ to the subset ${\mathbb S}_N$ is an injection.

I am no expert in this field, so perhaps the following question is known.

Question: Can one give an effective upper bound on $M=M(N)>1$ as a function of $N>1$?

I’ve done some computer computations using SageMath and it seems to me that

$M=O(N)$

(i.e., there is a linear bound) is possible. On the other hand, my computations were pretty limited, so that’s just a guess.

# Jesse Douglas – yet another Beautiful Mind?

Nobel prize winner John Nash struggled with mental illness for most of his life. His struggles were described Sylvia Nasar’s well-known biography, A Beautiful Mind, as well as a film of the same name starring Russell Crowe. Now, John Nash is practically a household name, honored for his contributions to the mathematics of game theory and economics.

While Jesse Douglas isn’t nearly as well-known as Nash, and didn’t win a Nobel Prize, he was (with Lars Ahlfors in 1936) the first recipient of the Fields Medal. According to one source, he too struggled with mental illness. However, before talking about the life of Jesse Douglas, let’s talk about his mathematical research.

Jesse Douglas in his 40s.

#### His Mathematics

Jesse Douglas solved a geometrical problem formulated in the 1700’s now called Plateau’s problem.  Plateau’s problem (also known as the soap bubble problem) is to show the existence of a minimal surface with a given boundary. Plateau was a a Belgian physicist who lived in the 1800s, known for his experiments with soap films. A minimal surface is a surface that locally minimizes its area. For example, the catenoid (see below) obviously doesn’t have minimum area for its (disconnected) boundary, but any piece of it bounded by a (connected) closed curve does have minimum area.

His research was not universally recognized at first. According to Reid [R76]:

Arriving in the year 192901930 at the end of a European tour as a National Research Fellow, he proposed to talk about his not-yet-published work on Plateau’s Problem at the weekly meeting of the mathematische Gesellschaft [at Gottingen University]. The problem had been around for a long time. Many outstanding mathematicians, including Riemann himself, had worked on it. The members of the Gesellschaft simply did not believe that an American had solved it. … When he had finished his presentation, some of the members of the Gesellschaft took him severely to task on almost every detail of the proof. Let left Gottingen deeply offended …

Douglas solved this geometrical problem in his paper “Solution of the problem of Plateau,” Trans. Amer. Math. Soc. 33 (1931)263–321. Gray and Micallef [GM07] do an excellent job of describing Jesse’s mathematical approach to the problem. Jesse continued working on generalizing and refining aspects of his research on this problem for the next 10 years or so. Some of his papers in this field include

• A method of numerical solution of the problem of Plateau, Annals of Mathematics 29(1927 – 1928)180-188
• Solution of the problem of Plateau, Trans. Amer. Math. Soc. 33 (1931) 263–321.
• Systems of K-dimensional manifolds in an N-dimensional space, Mathematische Annalen 105 (1931) 707-733.
• The Problem of Plateau for Two Contours, Studies in Applied Mathematics 10(1931)315-359.
• One-sided minimal surfaces with a given boundary, Trans. Am Math Soc 34(1932)731–756.
• A Jordan space curve no arc of which can form part of a contour which bounds a finite area, Annals of Mathematics 35(1934) 100-103.
• Green’s function and the problem of Plateau, American Journal of Mathematics. 61 (1939) 545–589.
• The most general form of the problem of Plateau, American Journal of Mathematics. 61 (1939)590–608.
• Solution of the inverse problem of the calculus of variations, Proceedings of the National Academy of Sciences. 25(1939) 631–637.
• The analytic prolongation of a minimal surface across a straight line, Proc Natl Acad Sci USA. 25(1939)375-377.
• The higher topological form of Plateau’s problem, Annali della Scuola Normale Superiore di Pisa , 8 (1939)195-218.
• Minimal surfaces of higher topological structure, Annals of Mathematics 40(1939) 205-298 .
• Theorems in the inverse problem of the calculus of variations, Proc Natl Acad Sci USA, 26(1940) 215–221.

He also wrote papers in other fields in mathematics, for example, the theory of finite groups. For example, in 1951 he published a series of short articles On finite groups with two independent generators, all in the Proc. Natl. Acad. Sci. USA. Also, in 1953, he published a series of short articles On the basis theorem for finite abelian groups, again, all in the Proc. Natl. Acad. Sci. USA.

#### His Life

Jesse’s father, Louis, was a Polish immigrant who moved to Canada sometime in the late 1800s. The family name was changed at Canadian Immigration and I don’t know his original name. At some point, Louis married Sarah Kommel (I don’t know when the move occurred, nor when and where they met) and moved to New York City. I think both Louis and Sarah were Jewish. Jesse was born in NYC on July 3rd, 1897. According to a geneology website, Sarah’s parents were Leazar Louis Kommel (1851-1923) and Chaya Lande, who died in 1906. Jesse’s mother Sarah passed away in 1939, a year before Jesse married (as we will see below).

Jesse was educated at public schools in New York City. According to Steinhardt [St92], Jesse had a photographic memory. After graduation from high school, he entered the City College of New York and won the Belden Medal for excellence in mathematics in his first year at City College of New York, the youngest recipient at the time. He graduated with a B.Sc. cum laude in February 1916 at the age of 18. Then he entered Columbia University to undertake research under the supervision of Edward Kasner. He took part in Kasner’s seminar on differential geometry and it was there that Jesse first heard of Plateau’s Problem. He submitted his doctoral thesis On Certain Two-Point Properties of General Families of Curves in 1920 (some references say 1921). After getting his PhD, he was an instructor at Columbia from 1920 to 1926. (Was this in the statistics department or the mathematics department? I don’t know.)

He won a National Research Fellowship and as a result, traveled widely for four years, visiting Princeton and Harvard in 1927, Chicago in 1928, and Paris from 1928 to 1930, with trips to Gottingen, Hamburg, and Rome. Jesse was offered an Assistant Professor position at MIT in January 1930. He took leave of absence for a term in 1932. After his promotion to Associate Professor at MIT in 1934, he almost at once took leave of absence again to be a Research Worker at the Institute for Advanced Study in Princeton from 1934 to 1935.  After returning to MIT, Jesse was awarded the first Fields Medal, together with Lars Ahlfors, in 1936. Once again, Jesse took leave of absence from MIT in 1936, and on 1 July 1938, he resigned. According to Aronson [A13], Jesse “became ill” at this time and Levinson was eventually hired as his replacement.

This may seem like the romantic life of a world-class mathematician, but it really is very unusual to be “homeless” 18 years after your get your PhD degree. Something is going on. According to Hersh [H10]:

Douglas’s name is almost forgotten today. He is a rather tragic figure, one of several important mathematicians gravely handicapped by what are now called bipolar, and used to be called manic-depressive, symptoms. He had a junior position at M.I.T., which he lost as a result of inability to perform consistently in the classroom.

According to Steinhardt [St92],

… the volatility of this mix of great gifts and sharp emotions [in which his “over-sized sensitivity surfaced not infrequently in intense feelings articulated vigorously to colleagues”] in Douglas’ makeup worked to the disadvantage of the great American mathematician’s external fortunes.

I don’t know what he did professionally in the 1939-1940 period, but he married Jessie Nayler on June 30th, 1940 (they had one son Lewis Philip Douglas). The husband named Jesse and the wife named Jessie! He often taught summer courses at Columbia University, as well as courses at Yeshiva University. The following year, Jesse was a Guggenheim fellow at Columbia University from 1940 to 1941. He taught at Brooklyn College from 1942 to 1946, as an assistant professor. His teaching during these war years went well according to a letter of commendation (did he teach students from the US Military Academy during this time?), and he received a Distinguished Service Award. In 1945, Jesse wrote an application letter for a teaching position saying [St92]:

This semester I have a teaching load of 19 hours per week at Brooklyn College, including two advances courses: complex variables and calculus of variations.

It is no surprise that he published nothing in the period 1942-1950. According to Micallef [M13],

There is a blank in Douglas’s career from 1946 to 1950, and the later part of Douglas’ life seems to have been troubled. His marriage ended in divorce in 1950.

In 1951, Jesse published a string of papers in a completely different field, finite group theory. Perhaps the end of Jesse’s marriage to Jessie caused him to reinvent himself, mathematically?

According to some sources, Douglas harbored resentment towards his research “competition” Rado (who he strongly beieved should not be credited with solving Plateau’s Problem [St92]) and Courant, as well as J.F. Ritt at Columbia, who may have blocked his appointment to a permanent position at his alma mater. (Sadly, anti-Semitic prejudices common of those times may have played a role in Jesse’s troubles in this regard.) Never-the-less, he is remembered as a helpful, sympathetic, and approachable colleague [St92].

His resentment of Courant was unfortunate because some 10 years earlier, in March 1935, Courant invited Jesse to speak at NYU. According to Reid [R76]:

Courant’s invitation to Douglas to speak at NYU was to a certain extent an olive branch. … Remembering this past history [Jesse’s reception at Gottingen 5 years earlier], Courant did his best to make Douglas’ lecture at NYU an event.

Clearly, Courant appreciated Jesse’s work and tried to treat him with due respect.

Other than Jesse’s mathematical research, this does not appear to have been a happy period in Jesse’s life. According to O’Conner and Robertson [OCR],

His [ex-]wife, Jessie Douglas died in 1955, the year in which Douglas was appointed professor of mathematics at the City College of New York. He remained in that post for the final ten years of his life, living in Butler Hall, 88 Morningside Drive in New York.

Steinhardt [St92] recalls the difficulty that Abraham Schwartz had in having CCNY give tenure at the full professor level to Jesse, when he was 1958. Except for the logician Emil Post, there was no one at CCNY at the time close to Jesse’s stature as a researcher. Ironically, a number of CCNY mathematicians “felt threatened by the appointment”, presumably fearing Jesse would require them to work harder.

There are a number of anecdotes of Jesse Douglas and his interactions with students. They aren’t universally flattering and I hesitate to repeat the negative ones, as I don’t know how typical they are. A number of sources suggest that when he was feeling well, he could be an impressive, charismatic, self-confident expositor and a lucid  teacher. While I don’t know the teaching load at Columbia University the time (where he belonged), I do know that, compared to today’s teaching loads, they were often quite heavy (see for example Parikh’s biography, The Unreal Life of Oscar Zariski). Are these unflattering reports of Jesse’s interactions with students merely due to his oppressive teaching load and inability to handle that volume of students? I don’t know. Perhaps he held others to the same very high standards that he held himself in his own mathematical research.

#### References

[A13] D.G. Aronson, Norman Levinson: 1912-1975, Biographical memoirs, Nat. Acad. Sci., 2013.

[GM07] Jeremy Gray, Mario Micallef, The work of Jesse Douglas on minimal surfaces, 2013. (appeared in Bull AMS 2008)  pdf

[H10] R. Hersh, Under-represented then over-represented, College J. Math, 2010.

[M13] M. Micallef, The work of Jesse Douglas on Minimal Surfaces, talk at Universidad de Granada, 2013-02-07.

[OCR] John J. O’Connor and Edmund F. Robertson, Jesse Douglas.

[R76] C. Reid, Courant, Springer-Verlag, 1976.

[St92] F. Steinhardt, “Jesse Douglas as teacher and colleague”, in The Problem of Plateau, ed. T. Rassias, World Scientific, 1992.

# Ring theory, via coding theory and cryptography

In these notes on ring theory, I tried to cover enough material to get a feeling for basic ring theory, via cyclic codes and ring-based cryptosystems such as NTRU. Here’s a list of the topics.

1 Introduction to rings
1.1 Definition of a ring
1.2 Integral domains and fields
1.3 Ring homomorphisms and ideals
1.4 Quotient rings
1.5 UFDs
1.6 Polynomial rings
1.6.1 Application: Shamir’s Secret Sharing Scheme
1.6.2 Application: NTRU
1.6.3 Application: Modified NTRU
1.6.4 Application to LFSRs

2 Structure of finite fields
2.1 Cyclic multiplicative group
2.2 Extension fields
2.3 Back to the LFSR

3 Error-correcting codes
3.1 The communication model
3.2 Basic definitions
3.3 Binary Hamming codes
3.5 Reed-Solomon codes as polynomial codes
3.6 Cyclic codes as polynomial codes
3.6.1 Reed-Solomon codes as cyclic codes
3.6.3 BCH bound for cyclic codes
3.6.4 Decoding cyclic codes
3.6.5 Cyclic codes and LFSRs

4 Lattices
4.1 Basic definitions
4.2 The shortest vector problem
4.2.1 Application to a congruential PKC
4.3 LLL and a reduced lattice basis
4.4 Hermite normal form
4.5 NTRU as a lattice cryptosystem

# Gray codes

This is based on work done about 20 years ago with a former student Jim McShea.

Gray codes were introduced by Bell Labs physicist Frank Gray in the 1950s. As introduced, a Gray code is an ordering of the n-tuples in $GF(2)^n = \{0,1\}^n$ such that two successive terms differ in only one position. A Gray code can be regarded as a Hamiltonian path in the cube graph. For example:

[[0, 0, 0], [1, 0, 0], [1, 1, 0], [0, 1, 0], [0, 1, 1], [1, 1, 1], [1, 0, 1], [0, 0, 1]]

These can be generalized to n-tuples of integers (mod m) in the obvious way.

Gray codes have several applications:

• solving puzzles such as the Tower of Hanoi and the Brain [G],
• analog-digital-converters (goniometers) [S],
• Hamiltonian circuits in hypercubes [Gil] and Cayley graphs of Coxeter groups [CSW],
• capanology (the study of bell-ringing) [W],
• continuous space-filling curves [Gi],
• classification of Venn diagrams [R],
• design of communication codes,
• and more (see Wikipedia).

The Brain puzzle

Here's a SageMath/Python function for computing Gray codes.
def graycode(length,modulus):
"""
Returns the n-tuple reverse Gray code mod m.

EXAMPLES:
sage: graycode(2,4)

[[0, 0],
[1, 0],
[2, 0],
[3, 0],
[3, 1],
[2, 1],
[1, 1],
[0, 1],
[0, 2],
[1, 2],
[2, 2],
[3, 2],
[3, 3],
[2, 3],
[1, 3],
[0, 3]]

"""
n,m = length,modulus
F = range(m)
if n == 1:
return [[i] for i in F]
L = graycode(n-1, m)
M = []
for j in F:
M = M+[ll+[j] for ll in L]
k = len(M)
Mr = [0]*m
for i in range(m-1):
i1 = i*int(k/m)
i2 = (i+1)*int(k/m)
Mr[i] = M[i1:i2]
Mr[m-1] = M[(m-1)*int(k/m):]
for i in range(m):
if is_odd(i):
Mr[i].reverse()
M0 = []
for i in range(m):
M0 = M0+Mr[i]
return M0



REFERENCES

[CSW] J. Conway, N. Sloane, and A. Wilks, “Gray codes and reflection groups”, Graphs and combinatorics 5(1989)315-325

[E] M. C. Er, “On generating the N-ary reflected Gray codes”, IEEE transactions on computers, 33(1984)739-741

[G] M. Gardner, “The binary Gray code”, in Knotted donuts and other mathematical entertainments, F. H. Freeman and Co., NY, 1986

[Gi] W. Gilbert, “A cube-filling Hilbert curve”, Math Intell 6 (1984)78

[Gil] E. Gilbert, “Gray codes and paths on the n-cube”, Bell System Technical Journal 37 (1958)815-826

[R] F. Ruskey, “A Survey of Venn Diagrams“, Elec. J. of Comb.(1997), and updated versions.

[W] A. White, “Ringing the cosets”, Amer. Math. Monthly 94(1987)721-746

# Simple unsolved math problem, 8

Sylver coinage is a game for 2 players invented by John H. Conway.

The two players take turns naming positive integers that are not the sum of non-negative multiples of any previously named integers. The player who is forced to name 1 loses.

James Joseph Sylvester proved the following fact.

Lemma: If a and b are relatively prime positive integers, then (a – 1)(b – 1) – 1 is the largest number that is not a sum of nonnegative multiples of a and b.

Therefore, if a and b have no common prime factors and are the first two moves, this formula gives an upper bound on the next number that can still be played.

R. L. Hutchings proved the following fact.

Theorem: If the first player selects any prime number $p>3$ as a first move then he/she has a winning strategy.

Very little is known about the subsequent winning moves. That is, a winning strategy exists but it’s not know what it is!

Unsolved problem:Are there any non-prime winning opening moves in Sylver coinage?

For further info, Sicherman maintains a Sylver coinage game webpage.