 # Celebratio Mathematica

## Andrew Mattei Gleason

### Andrew Gleason’s discrete mathematics

#### Ramsey theory

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 (, 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  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.

#### Coding theory

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

The­or­em 1: The Pro­ject­ive Simple Lin­ear Group $$\operatorname{PSL}_2 (n )$$ is a sub­group of the group of sym­met­ries of $$C$$.

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}$$.

The­or­em 2: If $$C$$ is self-dual, then $$W_C$$ is gen­er­ated by $$g_1 (x, y ) = x^2 + y^2$$ and $$g_2 (x, y ) = x^8 + 14x^2 y^2 + y^8$$.

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.

The­or­em 3: The MacWil­li­ams Iden­tity: $W_{C^{\perp}}(x,y) = \frac{1}{|C|}W_C (x+y, x-y).$

Gleason proved much more along these lines in . 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.”

#### The Putnam Exam

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

### Works

R. E. Green­wood and A. M. Gleason: “Com­bin­at­or­i­al re­la­tions and chro­mat­ic graphs,” Can. J. Math. 7 (1955), pp. 1–​7. MR 0067467 Zbl 0064.​17901 article

A. M. Gleason: “Weight poly­no­mi­als of self-dual codes and the MacWil­li­ams iden­tit­ies,” pp. 211–​215 in Act­es du Con­grès In­ter­na­tion­al des Math­ématiciens, 1970 [Pro­ceed­ings of the In­ter­na­tion­al Con­gress of Math­em­aticians, 1970] (Nice, 1–10 Septem­ber 1970), vol. 3. Gau­th­i­er-Vil­lars (Par­is), 1971. To Mar­shall Hall, Jr. on his six­tieth birth­day. MR 0424391 Zbl 0287.​05010 incollection

A. M. Gleason, R. E. Green­wood, and L. M. Kelly: The Wil­li­am Low­ell Put­nam Math­em­at­ic­al Com­pet­i­tion. Math­em­at­ic­al As­so­ci­ation of Amer­ica (Wash­ing­ton, DC), 1980. Prob­lems and Solu­tions: 1938–1964. MR 588757 Zbl 0444.​00006 book