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 $(\genfrac{}{}{0ex}{}{n}{2})$ line seg­ments join­ing $n$ points in pairs is painted with one of $r$ col­ors, then for some $1\le i\le 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)\le 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 $\mathrm{GF}(16)$. Let $H\subset \mathrm{GF}(16{)}^{\ast }$ con­sist of the nonzero cubes. Then they col­or the edge between $\alpha ,\beta \in \mathrm{GF}(16)$ by the coset of $\mathrm{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 1mod8$. Let $Q$ be the quad­rat­ic residues of $Z_n^{\ast }$ 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 $\bar{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 $\bar{C}$ is a per­muta­tion $\sigma \in S_{n+1}$ of the co­ordin­ates for which $\sigma (\bar{C})=\bar{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 _{i=0}^n{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.