Celebratio Mathematica

Six points are in gen­er­al po­s­i­tion in space (no three in a line, no four in a plane). The fif­teen line seg­ments join­ing them in pairs are drawn, and then painted, some seg­ments red, some blue. Prove that some tri­angle has all its sides the same col­or.

–Wil­li­am Low­ell Put­nam Com­pet­i­tion, 1953 ([3], page 38)

An­drew Gleason’s fas­cin­a­tion with com­bin­at­or­i­al puzzles, his com­pu­ta­tion­al skills, and his al­geb­ra­ic in­sights of­ten led to in­ter­est­ing deep res­ults in dis­crete math­em­at­ics. We sample some of them here.

The Put­nam prob­lem quoted above in­tro­duces Ram­sey the­ory, where Gleason made one of his first con­tri­bu­tions. Ram­sey the­ory starts with the fact that for any \( k_1 ,\dots, k_r \) there is a least \( n = R (k_1 ,\dots, k_r ) \) such that when each of the \( \binom{n}{2} \) line seg­ments join­ing \( n \) points in pairs is painted with one of \( r \) col­ors, then for some \( 1 \leq i \leq r \) there are \( k_i \) points with all seg­ments between them giv­en col­or \( i \). \( R \) is gen­er­ally called the Ram­sey func­tion and the \( n = R (k_1 ,\dots, k_r ) \) are called Ram­sey num­bers. Solv­ing the Put­nam prob­lem above proves \( R (3, 3) \leq 6 \). The ar­gu­ments for the ex­ist­ence of \( R (k, l ) \) had been giv­en by Ram­sey and, in­de­pend­ently, by Erdös and Szekeres in the early 1930s (see [e2] for gen­er­al ref­er­ence). Ram­sey the­ory fas­cin­ated Gleason.

In 1955 Gleason and coau­thor R. E. Green­wood [1] cal­cu­lated some small Ram­sey num­bers. They found \( R (3, 3) = 6 \), \( R (3, 4) = 9 \), \( R (3, 5) = 14 \), \( R (4, 4) = 18 \), and \( R (3, 3, 3) = 17 \). The lower bounds some­times called for in­geni­ous al­geb­ra­ic con­struc­tions to provide counter­examples. For in­stance, to show \( R (3, 3, 3) > 16 \) they con­sider the 16 points as \( \operatorname{GF} (16) \). Let \( H \subset \operatorname{GF}(16)^{\ast} \) con­sist of the nonzero cubes. Then they col­or the edge between \( \alpha , \beta \in \operatorname{GF}(16) \) by the coset of \( \operatorname{GF}(16)^{\ast} /H \) con­tain­ing \( \alpha - \beta \). Des­pite great ef­forts and high speed com­puters, only a few oth­er val­ues are known today. Even the value of \( R (5, 5) \) seems out of reach.

As a gradu­ate stu­dent at Har­vard in the late 1960s I chose to write a thes­is par­tially on Ram­sey num­bers. Gleason told me he had spent a great deal of time look­ing for oth­er ex­act val­ues. Since I knew of his le­gendary cal­cu­lat­ing powers, I took this as sage ad­vice to re­strict my at­ten­tion to their asymp­tot­ics.

Gleason’s re­search in dis­crete math­em­at­ics began not with Ram­sey the­ory but with his cryp­to­graph­ic work dur­ing World War II.1 That’s when he first col­lab­or­ated with Green­wood. After the war he par­ti­cip­ated in the bur­geon­ing de­vel­op­ment of cod­ing the­ory. Al­though he pub­lished little, he had a sig­ni­fic­ant in­flu­ence on oth­ers.

Vera Pless (her [e3] is a good gen­er­al ref­er­ence for cod­ing the­ory) re­calls “Gleason meet­ings” in the 1950s on er­ror-cor­rect­ing codes.

These monthly meet­ings were what I lived for. No mat­ter what ques­tions we asked him on any area of math­em­at­ics, Andy knew the an­swer. The nu­mer­ic­al cal­cu­la­tions he did in his head were amaz­ing.

A bin­ary code is a sub­set of \( \{0, 1\}^n \). The ele­ments are called code­words. The weight of a code­word is the num­ber of co­ordin­ates with value one. Gleason stud­ied codes with an al­geb­ra­ic rep­res­ent­a­tion.

To define a quad­rat­ic residue code, be­gin by identi­fy­ing \( \{0, 1\}^n \) with \( Z_2 [x]/(x^n - 1) \). Sup­pose \( n \) is a prime con­gru­ent to \( \pm 1 \bmod 8 \). Let \( Q \) be the quad­rat­ic residues of \( Z^{\ast}_n \) and set \( e (x) = \sum_{i \in Q} x^i \). Then let \( C = (1 + e (x)) \), the ideal gen­er­ated by \( 1 + e (x) \) in \( Z_2 [x]/(x^n - 1) \). Then \( C \) is a code of di­men­sion \( (n + 1)/2 \). These codes have proven par­tic­u­larly use­ful, in part be­cause of their sym­met­ries.

Let \( \overline{C} \) be the code of di­men­sion \( n + 1 \) giv­en by adding a par­ity bit. (That is, the first \( n \) bits are in \( C \), and the last is such that the weight is even.) A sym­metry of \( \overline{C} \) is a per­muta­tion \( \sigma \in S_{n +1} \) of the co­ordin­ates for which \( \sigma (\overline{C} ) = \overline{C} \) . The Gleason–Prange The­or­em [e3] as­serts that

A lin­ear code is a \( C \subseteq \{0, 1\}^n \) which is a sub­space of \( \{0, 1\}^n \). For such \( C \), \( C^{\perp} \) is the usu­al (over \( Z_2 \)) or­tho­gon­al sub­space. When \( C \) has \( A_i \) vec­tors of weight \( i \), its weight enu­mer­at­or is defined by \[ W_C(x, y) = \sum^n_{i=0} A_i x^{n-i}y^i. \]

The Gleason poly­no­mi­als are fi­nite sets of poly­no­mi­als that gen­er­ate all weight enu­mer­at­ors of a cer­tain type.

Gleason found a par­tic­u­larly strik­ing ex­ample for self-dual codes, those for which \( C = C^{\perp} \).

There are deep con­nec­tions to in­vari­ant the­ory here.

The weight enu­mer­at­or of \( C \) de­term­ines that of \( C^{\perp} \). The ex­act re­la­tion­ship was giv­en by Jessie MacWil­li­ams (1917–1990), one of Gleason’s most ac­com­plished stu­dents, in her thes­is.

Gleason proved much more along these lines in [2]. Neil Sloane starts his pa­per on “Gleason’s the­or­em on self-dual codes and its gen­er­al­iz­a­tions” [e1] with “One of the most re­mark­able the­or­ems in cod­ing the­ory is Gleason’s 1970 the­or­em about the weight enu­mer­at­ors of self-dual codes.”

Gleason was the first three-time win­ner of the Put­nam com­pet­i­tion, fin­ish­ing in the top five while at Yale in 1940, 1941, and 1942. He was dis­ap­poin­ted in his first at­tempt, be­cause he solved only thir­teen of the fif­teen prob­lems.

For many years he se­lec­ted one of the five fin­ish­ers for the Put­nam Fel­low­ship at Har­vard, a fel­low­ship he was awar­ded and de­clined in 1940 in or­der to re­main at Yale. He wrote (with R. E. Green­wood and L. M. Kelly) a beau­ti­ful book [3] on the Put­nam com­pet­i­tion for the years 1938–64. For many prob­lems his solu­tions (and there are of­ten sev­er­al) are splen­did lec­tures in the var­ied sub­jects. El­wyn Ber­lekamp (also a Put­nam win­ner) re­calls dis­cus­sions with him:

[Gleason] would usu­ally of­fer two or three dif­fer­ent solu­tions to the prob­lem he wanted to talk about, where­as I rarely ever had more than one. He be­lieved that Put­nam prob­lems en­cour­aged very strong mas­tery of what he con­sidered to be the fun­da­ment­als of math­em­at­ics.

Gleason was al­ways eager to share his pas­sion for math­em­at­ics in gen­er­al and prob­lems in par­tic­u­lar. Bjorn Poon­en (a mul­tiple Put­nam win­ner and the coau­thor of a fol­low-up book on the Put­nam com­pet­i­tion 1985–2000 [e4]) re­calls his un­der­gradu­ate days:

Andy struck me as someone genu­inely in­ter­ested in help­ing young­er math­em­aticians de­vel­op. When I was an un­der­grad at Har­vard, he vo­lun­teered an hour or two of his time each week for an in­form­al meet­ing in his of­fice with a group con­sist­ing of me and one or two oth­er math un­der­grads to dis­cuss whatever math­em­at­ics was on our minds.

Amen. As a gradu­ate stu­dent I had the good for­tune to be Andy Gleason’s teach­ing as­sist­ant. We would meet in the small pre­par­a­tion room be­fore the classes. Andy would dis­cuss the math­em­at­ics of the lec­ture he was about to give. He was at ease and spoke of the im­port­ance and the in­ter­re­la­tion­ships of the vari­ous the­or­ems and proofs. My con­tri­bu­tions were min­im­al, but I listened with rapt at­ten­tion. It was in those mo­ments that I learned what be­ing a math­em­atician was all about.