Marcel-Paul Schützenberger (1920-1996)

Marcel-Paul Schützenberger, one of the most creative and influential combinatorialists of this century, died on Monday, July 29, 1996. He was possessed of a lively curiosity, a brilliant mind, a passion for all kinds of mathematics and for substantive intellectual achievement of all sorts, a low tolerance for poseurs and fools, a warm and vibrantly supportive personality as regards his interaction with young people of promise, a deep affection for the human race despite its numerous foibles, and a personal charm, grace and good humor that was totally captivating.

This is not an obituary or an attempt to summarize all of his mathematical and particularly combinatorial contributions. It is intended to be a notice to the community that one of our giants has passed on, and an invitation to that community to contribute further remembrances of him, discussions of his work or of his life, etc. that will be appended here to a make a long scroll of recollections, in the spirit of a Quaker meeting.

I met Marco first in 1973 at a conference in Rome. Over the years we visited each other several times, and I have been privileged to hear his views on a variety of topics. His opinions were numerous, fervently held, ardently propounded, backed up by his extensive knowledge base, punctuated, when delivered in English, by a pyrotechnic display of choice expletives, and utterly compelling, to this listener at least, because of the persona of their bearer and the force of reason and humanity with which they were delivered.

His contributions to combinatorics are wide ranging and of the first magnitude. In the theory of Young tableaux he discovered the jeu de taquin that became the basis for so many later investigations; he illuminated the Schensted correspondence between pairs of permutations and tableaux by revealing many facets of its fine structure; he created the subject of context-free languages and explored some of its many consequences, as well as finding many results in the theory of combinatorial words and languages of other kinds; with Foata he developed a general theory of counting families of unlabeled combinatoral objects by factoring them into primes, etc. His work has found important and numerous applications. For example his theory of formal languages has spawned many fine successes in the enumeration of various kinds of polyominoes and cellular structures and his work on factorization of families of unlabeled objects has been responsible for methods of selecting such objects at random.

Throughout his life Marco was interested in (and therefore passionately interested in) the many flaws in the Darwinian theory of evolution as it is commonly presented. In 1967 he participated in a remarkable conference at the Wistar Institute of the University of Pennsylvania, which brought together a collection of renowned physical scientists and mathematicians, on the one hand, and life scientists, on the other. At that meeting Marco became one of the first distinguished scientists in the world to point out that a theory of evolution that depends on uniformly randomly occurring mutations cannot be the truth because the number of mutations needed to create the speciation that we observe, and the time that would be needed for those mutations to have happened by chance, exceed by thousands of orders of magnitude the time that has been available.

A recent interview with Marco, on the subject of evolution can be read on the Web.

He worked steadily at mathematics until the very end. Just some weeks ago he published in the Electronic Journal of Combinatorics, jointly with Alain Lascoux, an article in the special Festschrift issue issue that honors the 60th birthday of Dominique Foata. I spoke with him by telephone a few days before his death. Though he knew that he had only a few days to live, he wanted to speak about only one thing with me, namely the recent appearance of an article in Commentary magazine by David Berlinski [2], which further probes the deficiencies of Darwinism. At the end of that conversation I asked him how he was. He replied "Herbert, I am nothing!". In that, he was very wrong.

My small and too-infrequently-renewed friendship with Marco was a disproportionately strong source of warmth, knowledge and support in my own life.

Herbert Wilf,
Philadelphia, PA, USA, August 29, 1996.

[1] Mathematical Challenges to the Neo Darwinian Interpretation of evolution, Wistar Institute Press, 1967.
[2] David Berlinski, The deniable Darwin, Commentary Magazine, Vol. 101 ; No. 6 ; Pg. 19; ISSN: 0010-2601 (June, 1996)

Here are two more photos of him. The first one is from 1960 and was taken on a ferry to Cape Hatteras in America; the second one was taken in Oberwolfach in 1972 (photos courtesy of Dominique Foata).
    

From Chapel Hill to Lotharingia

The note written by Herb Wilf [1] in memory of Marcel-Paul Schützenberger summarizes the superb intellectual and human qualities of the great master, mentor, friend that many of us have recently lost. He was indeed a versatile mind, keeping abreast of the scientific developments of his time. As Moshe Flato wrote in his contribution to "Mots" [2, p. 70] he was "one of the most pluridisciplinary scholars I had ever known." His discourse was full of unexpected images and paradoxes; he never had a banal view on any subject, but always developed a well-structured and original reasoning in which plenty of new ideas flourished naturally. He undeniably was a great master of the Word. A conversation with him was an enrichment in which all kinds of subjects would be discussed: Mathematics, Physics, Biology, Philosophy, Political Science, ... , or simply l'air du temps.

It is a shock to realize that my own conversation with him that started some thirty-six years ago is now interrupted. I met him for the first time in Chapel Hill, North Carolina, back in 1960. He was not yet forty. The late Professor Raj-Chandra Bose, who had just constructed, jointly with Dijen Ray-Chaudhury, the celebrated infinite family of error-correcting codes that carry their names, had invited him to spend a year in Chapel Hill. Marco had known the great period of the M.I.T. in the late fifties, when the pioneering work of Claude Shannon initiated Information Theory and he himself with Noam Chomsky made the theory of context-free languages accessible to linguists.

There was indeed at that time a demand for structured information codes that would be easy to conceive, analyze and implement. One answer was the concept of block code of finite length. It has kept active several generations of mathematicians and electrical engineers ever since. Marco did not work in that area proper, but rather laid down the foundations of what we call the variable-length codes in the context of formal languages. Bose thought that his vision of the problems related to Coding Theory in general would be of great help to his school in Chapel Hill. Marco gave several seminars there on the theory of formal languages, in his personal way, unorthodox, colorful, witty. In fact, the best of his teaching was given after class, around a cup of coffee, within a small group. Fortunately, he was never asked to address a big Freshman Calculus class!

In 1961-62 he joined the Harvard Medical School and returned to the Faculté des Sciences in Poitiers (in France the University, as such, was created in 1968 by aggregating several independent Faculties). He got a permanent position in Paris in 1964, first as a research director at the C.N.R.S., then as a professor at the Faculté des Sciences that later split into the so-called Université Paris VI and Université Paris VII.

I was very privileged to meet him again in Paris after my military service in 1963. My Doctorat d'Etat was really completed thanks to him and thanks to his outstanding guidance. A visit to his place could last the whole afternoon and the whole evening, as it was still the case last January when I saw him for the last time.

In the late sixties and early seventies he built a solid reputation in Paris as the world figure in the theory of Formal Languages and Theoretical Computer Science. Among his doctoral students at that time one finds Maurice Nivat, Jean-François Perrot, Maurice Gross, Jean Berstel, Robert Cori, Gérard-Xavier Viennot, André Lentin, Michel Fliess, Dominique Perrin. The list is not complete, for he had many other disciples in France and overseas.

We can wonder why he did not write himself the reference book on Formal Languages. The work was done instead by Samuel Eilenberg [3] who says in the preface of his first volume: "The reader will find that the name of M. P. Schützenberger is often mentioned as author (or coauthor with me) of many of the new results or proofs that appear in this volume; most have not been previously published. However, his contributions went much beyond that; virtually every phase of the development presented here was endlessly discussed with him."

In the seventies he was elected corresponding member of the French Academy of Sciences. It was clear that this recognition on the part of the Establishment pleased him, although he kept joking that the main advantage of the appointment was the privilege of making speeches without being interrupted on the first occasion!

In 1988 he was promoted full member of the Academy. I remember asking him how he felt to belong to that respectable Assembly. The reply was: "Well, now Jean-Pierre Serre shakes hands with me!"

One of his deep convictions was that most identities in Classical Analysis were simply accidents and could be derived by ad hoc geometric methods. Our monograph on the Eulerian polynomials [4] was written in that spirit. It is true that a good bunch of formulas in Special Functions can now be proved combinatorially, that is, sequences of finite structures have been found in which the underlying identity simply reflects the action of a transformation in the geometry of those structures.

The first great paper that initiated the combinatorial theory of symmetric functions and the algebra of tableaux goes back to 1963 ("Quelques remarques sur une construction de Schensted" [5]), the second one being entitled "La correspondance de Robinson" [6] that was published in the proceedings of The Strasbourg Table Ronde in 1976. In 1978 he started a fruitful collaboration with Alain Lascoux that lasted until the week of his death. In the list of Marco's publications up to 1988 that appeared in [2] there are already as many as fifteen joint papers. Some of those articles are rather rough reading. Perhaps. However their contribution is significant: the integrality of the Foulkes polynomials, the study of Schubert polynomials, the tableau algebras derived from the jeu de taquin, ...

In 1990 Alain Lascoux and Dominique Perrin prepared an original Festschrift dedicated to Marco, the "Mots" volume. We can read in the preface: "This volume is a homage to Marcel-Paul Schützenberger offered by his friends and disciples. Although the actual contributors form a restricted subset of the total set of his friends, students, disciples and admirers, the diversity in their contributions shows that they belong to a great variety of species. The outcome is this multi-faceted book that includes mathematical reasonings as well as historical analysis." Our duty is now to make the book accessible to a larger public, perhaps by means of Electronic Publishing.

As Herb mentioned in his note, Marco was deeply involved in his struggle against the votaries of Darwinism. His other bête noire was Artificial Intelligence. When he was asked to contribute to the volume "Le Savant et la Foi" [7] in which "nineteen scientists were invited to express why they were Christian and how they made their scholarly work compatible with their faith" Marco sent a paper entitled "Intelligence artificielle, néo-darwinisme et principe anthropique." The paper is not a theological essay, but a convincing analysis of the failures of to-day's cosmological theories, neo-Darwinism, with or without the help of Artificial Intelligence!

Was Marco a believer? We had many discussions about religion in the past, but they are too personal to be reported in this note. In any case his family was of the Lutheran persuasion. At the end of his life he had reached a state of serenity. From his hospital bed he told me last June: "Mon pauvre Dominique, je suis tout déglingué." ("I am an utter wreck!"). Alain Lascoux stayed with him to the very last; he will present the tenor of their ultimate joint work during our next Séminaire Lotharingien in Bellagio.

The name of Schützenberger is well-known in Alsace. One of his ancestors was the great chemist Paul Schützenberger who discovered the cellulose acetates. Like many of the pro-French Alsatian families, his great-grandfather left Strasbourg just after the Franco-Prussian War in 1871.

He is survived by his daughter Hélène who has been a great comfort to him when he became seriously ill. His wife Hariati died in 1993, and his son Mahar was killed in a car accident back in 1980 at the age of twenty-three. One the photos shows Marco with four-year-old Mahar on the ferry to Cape Hatteras.

One never dies as long as their memory lives with us.

Dominique Foata,
Strasbourg, France, September 20, 1996.

[1] Herb Wilf, Marcel Paul Schützenberger 1920-1996
[2] M. Lothaire. Mots (Mélanges offerts à M.-P. Schützenberger), Hermès, Paris, 1990.
[3] Samuel Eilenberg. Automata, Languages, and Machines, vol. 1. Academic Press, New York, 1974.
[4] Dominique Foata et Marcel-Paul Schützenberger. Théorie des polynomes Eulériens, Lecture Notes in Math. 138, Springer-Verlag, Berlin, 1970.
[5] M.-P. Schützenberger. Quelques remarques sur une construction de Schensted, Math. Scandinavica, vol. 12, 1963, p. 117-128.
[6] M.-P. Schützenberger. La correspondance de Robinson, Lecture Notes in Math., no. 579, Springer-Verlag, Berlin, 1977, p. 59-113.
[7] Jean Delumeau, ed. Le savant et la Foi, Flammarion, Paris, 1989.

My friendship with Marco Schützenberger was the most extraordinary of my life. I knew little of his purely mathematical research. He had in 1979 arranged for me to spend a year at Paris so that we might work together on a book devoted to the Darwinian theory of evolution. We met almost every day. He talked and I listened. His conversation ranged over every conceivable intellectual topic. At the end of the year, I had compiled a mass of notes, but our book was never finished.

We stayed in touch thereafter; and I managed to visit him in Paris almost every year; but that year spent together in what was to have been research remains singular. He was healthy and happy, his family untouched by tragedy, and intellectually at the very height of his powers. Through his voice, I heard the echo of a vanished France, a way of life that is now gone.

Meeting Marco was like taking one's first sip of champagne. Those who never touch the stuff will never know what they are missing. I have tried in my book, Black Mischief: Language, Life, Logic & Luck, to make Marco live in the minds of other people. I do not know whether I have succeeded, but I hope that those who loved him, as I did, will read what I have written and see whether cigarette in hand Marco appears yet again for just a minute.


David Berlinski,
San Francisco, CA, USA, September 30, 1996.

Marcel-Paul Schützenberger died on Monday, July 29, 1996. He was a great figure of science, leaving to mankind a bunch of fundamental discoveries and new ideas. He worked during his life in an incredible number of areas and many people, including some of his former students, don't know the full extent of the diversity and depth of the results of all sorts that he had obtained. I am not sure that I am aware myself of all of them, such as his contribution to the discovery of the gene of trisomy in the early 50's.

I will concentrate here on his work in Theoretical Computer Science. A source of additional information is the volume Mots (by Lothaire, Hermes, 1990). It is a collection of papers dedicated to Marco Schützenberger by his friends and former students. You will find there a bibliography (compiled by Imre Simon) of 155 scientific papers by Marco.

The starting point of Marco's work in Computer Science was the theory of variable length codes. He published in 1955 a paper ('Une théorie algébrique du codage') presented at the algebra seminar in Paris which already contains many of the ideas of his work on automata. For example, one finds in this paper the definition of the syntactic semigroup, of recognizable sets and their equality with rational sets, actually almost simultaneously with the appearance of Kleene's work. The problem of understanding the nature of the property of unique decipherability fascinated him from the beginning. He found there an incredible interplay between algebra through the use of finite semigroups, probability theory and combinatorics. Many of his favourite subjects were put together. Later he published a series of results on variable-length codes all of them reported in our book with Jean Berstel (Theory of Codes, Academic Press, 1984). To single out just one of them, I would quote the theorem expressing that a finite maximal code either is prefix or has an infinite deciphering delay (J. Comb. Th., 1, 1966, 437-442). His ideas on codes led him later on to several deep results on rational functions and transducers.

It was also very early that Marco Schützenberger began to work on context-free grammars. The famous Chomsky-Schützenberger theorem asserting that any context-free language is a coding of a simple Dyck language appeared in 1963. His fundamental idea was that context-free languages were a non-commutative version of algebraic series, in the same way as finite-state languages are the non-commutative counterpart of rational series. His work on context-free grammars is thus closely related to the ones on algebraic and rational series. He did in this vein publish in 1962 a paper in which he proved a version for series of the property of the family of context-free languages to be closed under intersection with a rational languages, thus appearing as a non-commutative version of a theorem on the Hadamard product of an algebraic series with a rational one (On a theorem of R. Jungen, Proc. Amer. Math. Soc., 13, 885-890).

The beautiful theorem on aperiodic and star-free sets was published in 1965 ( On finite monoids having only trivial subgroups, Inf. and Control, 8, 190-194). It is the first result of the theory of varieties that he would develop with S. Eilenberg and appears in the second volume of Automata, Languages and Machines (Academic Press, 1976).

A good part of the rest of his mathematical work is either in algebra or in combinatorics.

In algebra, he has deeply influenced the theory of semigoups. The name of Schützenberger group of a D-class was coined by A. H. Clifford in the first book on semigroup theory (A. H. Clifford and G. B. Preston, The algebraic Theory of Semigroups, Amer. Math. Soc., 1961). The techniques that he had developed in semigroups were in many cases his 'arme secrèt' for his work on automata. For example, the theorem on star-free sets mentioned above can be easily stated without reference to semigroups but I don't know of a proof that does not use finite semigroups (a fact which might explain that this result is not as well-known as one could expect). Another part of Marco's work in algebra is on Lie algebras. This is again related with codes and automata. Actually, one of his most beautiful results relates Lie algebra decompositions with factorizations of the free monoid (On a factorization of free monoids, Proc. Amer. Math. Soc., 16, 1965, 21-24).

His contributions in combinatorics are probably as important as those in computer science, making Marco, to quote Herbert Wilf, 'one of the most creative and influential combinatorialists of this century'. It is probably his work on Young tableaux which is most famous. Some of his early work is reported in Knuth's volume 3 (Sorting and Searching, Addison Wesley, 1975). He was not so far from his grass roots since he introduced there, in his further work with Alain Lascoux, a semigroup (the plactic monoid) which reveals many properties of the tableaux. He was also the inventor of bijective proofs. The rough idea is to prove combinatorial identities by exhibiting a bijection between two sets enumerated by the two sides of the identity. The sets were often formal languages as for the case of the description of graphs by context-free languages.

Marco Schützenberger was without doubt the founder of combinatorics on words. One of the references for his pioneering work there is the collective book by Lothaire published in 1983 and in which he himself wrote a chapter, together with the group of his former students in this field (Combinatorics on Words, Cambridge University Press). He used to say that I was the "protonotaire" of Lothaire. Having accepted for many years this mysterious title, I had today the curiosity to look in a dictionnary. Here is what it says:

PROTONOTAIRE n. m. - 1390; lat. ecclés. protonotarius, de proto-, et lat. notarius. -> Notaire

I give up any attempt to translate the definition into English.

Much of his work in mathematics, as we have seen, is connected with automata, words and coding. It would certainly be difficult to tell whether Marco Schützenberger has applied mathematics to computer science or conversely. He once told me long ago that his work consisted in applying his intuitions from data processing to bring new contributions to mathematics. Was he really joking? He had actually especially strong beliefs and a passion for discussion, if not for controversy. Among the favourite victims of his irony were all sorts of fools including the tenants of artificial intelligence, as they were trying to deny, he would say, the difference between men and women.

So much for mathematics. His contributions will live for a long time. A lot of the rest will not survive his numerous friends and students. All of them remember long passionate discussions on all possible subjects. The influence that he had on each of us goes well beyond our mathematical education. We all have lost a close and very affectionate friend who hid behind bitter irony and an immoderate love for paradoxes, an incredibly generous nature.

Dominique Perrin
Université de Marne-la-Vallé, France, September 30, 1996.

Dominique Foata ran a meeting on combinatorics and special functions at Oberwolfach about 15 years ago. Marco Schützenberger was there, and this is when we first méet. I am a very old fashioned classical analyst who gets a headache when around cigarette smoke. Marco had a cigarette in his hand almost all the time, and his mathematics included such things as semi-groups, something that was far too general and abstract for me, or so I thought. It seemed unlikely we would have anything to talk about. In fact, as his many friends can guess, we had much to talk about, and the cigarette smoke didn't even matter.

During one of the talks at this meeting, Marco was sitting immediately behind me. The speaker had come to this meeting with the conviction that he was 75% of the way through the first purely combinatorial proof of a famous result. The talk had started with this claim and was followed by the statement that Curtis Greene had made a comment to the speaker that allowed him to cut the remaining distance in half. After the talk, I turned around and told Marco that it seemed the decimal point was off by two places, at best. He replied that after that talk, he doubted the result was true and would put it on his computer when he returned to Paris. In the few conversations we had, he always had a better way of describing something than I did.

There was one other talk at that meeting where Marco said something to me which showed the type of man he was. Mourad Ismail was talking on some joint work we had done. He was giving a slow introduction, and after about 15 minutes, Marco turned to me and asked what was the big deal, since everything said so far came out directly from one of the big combinatorial structures he had help build. I told him to wait until the end, and see if he still felt that way. Some speakers like to give the audience a chance to follow along for a while, and Mourad was doing that. At the end, Marco said that the last part did not fit into anything he had seen, which reassured me. He would tell you what he thought, both good or not, and he could change his mind.

Marco's wife was at this meeting, and it was also a great pleasure to talk with her. Wives of mathematicians have a tendency to complain that their husbands ignore them, talking or doing mathematics all of the time. I had been her husband had started as a psychiatrist, I asked which made the better husband, a mathematician or a psychiatrist. She said a mathematician, since they just leave you alone.

The one other time we talked was in Paris, but only for an hour. He told me things about Poisson processes and their connections with problems which interested me that I had never dreamed of.

As we grow older, we learn to appreciate things we never thought we would. Marco's coding of MacMahon's inversion statistic on words via non-commutative multiplication once seemed like a weird way of doing something which had a beautiful analytic structure. Now it is seen as central to the development of some important examples of quantum groups. The q-special function I have studied for the last twenty years are seen to live in this non-commutative setting. His insight was remarkable, and often far ahead of others.

It would have been nice to have had more contacts, but those that occurred will not be forgotten.

Richard Askey
Madison, Wisconsin, October 12, 1996

A Marco Schützenberger, par Moshé Flato

Cher Marco,

Cela fait un an, une longue année, que tu nous a quittés. Bien des gens ont écrit sur ta biographie, tes capacités intellectuelles extraordinaires, etc... Tous t'ont admiré et aimé. Tu sais, moi aussi je t'ai aimé et admiré, et jamais ne cesserai. Je crois néanmoins avoir une touche personnelle à apporter, quelques souvenirs, évènements, rencontres avec toi qui me permettront (comme à chacun de ceux qui t'ont approché) d'ajouter quelques notes à l'orchestre véritablement international qui chante si bruyamment tes louanges depuis que tu n'es plus.

Je t'ai rencontré pour la première fois il y a environ 25 ans dans un Séminaire Interdisciplinaire au Collège de France. Quelqu'un avait fait un exposé et (selon mon habitude) j'ai commenté à la fin. Tu étais assis non loin de moi et, te tournant vers moi, tu as dit: "Pas con, petit frère, pas con du tout. Je sens que toi et moi serons de bons amis".

Et il en fut ainsi. Depuis ce jour nous devînmes de bons amis, et cela dura jusqu'à ton dernier jour. A dire vrai, cette amitié restera dans mon coeur aussi longtemps que je vivrai.

Qui étais-tu, Marco ? Avant tout quelqu'un qui aimait profondément l'humanité, en dépit de sa stupidité généralisée et de sa grégarité qui lui fait dans bien des domaines suivre les guides qu'elle se donne.

Tu étais très fidèle en amitié et extrêmement généreux avec les gens.

La profondeur de ta pensée et de ta lecture et tes extraordinaires capacités intellectuelles te rattachent à une espèce qui a disparu depuis plusieurs siècles : une personnalité de la Renaissance, un véritable grand philosophe des sciences de la Nature et un humaniste. Quand tu posais une question portant sur la physique, elle était toujours pénétrante et nous pouvions en discuter - souvent par téléphone - pendant des heures. Il en allait de même en biologie (rappelle-toi, ton dernier combat fut contre les Darwinistes), en linguistique et dans bien d'autres domaines. Tu étais viscéralement non-conformiste. Jamais tu n'as pu te reposer sur tes lauriers dans les divers domaines de la connaissance que tu as touchés et, comme bien de nos collègues, profiter de ta gloire. Il te fallait toujours aller plus loin, plus en profondeur, élargir ton champ de connaissance, penser, lire, converser. Te souvient-il du temps où nous siégions ensemble au Conseil Scientifique de l'UAP. Oh, combien nous avons tous ri à l'époque lorsque tu maniais, avec le brio qui t'est coutumier, divers paradoxes jusqu'à ce que le rival soit acculé dans un coin ! Comme tout ceci était fantastique et très souvent extrêmement productif !

Te rappelles-tu de notre dernière rencontre avec Max Delbruck ? Ou des soirées mémorables avec notre ami commun, trop tôt disparu, Stan Ulam - chez qui l'on retrouvait certains de tes traits intellectuels ?

Et cependant, frère Marco, il y a une question que je n'ai jamais osé te poser. Chaque grand homme a ses contradictions internes et tu n'en étais pas exempt. Rappelle-toi, dans les années 70, nous riions de cette vénérable institution qui a pour nom l'Académie des Sciences et des "vieux boucs" qui en faisaient partie. Je fus peiné de voir que bien des années après le fait de devenir Académicien est devenu important pour toi. Tu avais grandi en âge et avais fini par trouver honorifique d'appartenir à un Club en compagnie de gens dont le niveau était en moyenne très en-dessous du tien.

Mais tout ceci est secondaire et relève de l'anecdote. A tes amis et tes collègues, à tes anciens étudiants, à la communauté scientifique toute entière (où les phénomènes dans ton genre sont malheureusement bien trop rares), à tous ceux qui furent profondément inspirés par ton exemple personnel - à tous tu manques déjà énormément.

Ils t'aimeront et t'admireront toujours.

AN INVITATION: All persons who have remembrances of Marco that they would like to share with others are cordially invited to send them to the Editors, who will publish, in this space, all that seem appropriate.