.EQ delim $$ gsize 11 .EN .ds HP 10 10 10 .am DE .sp .ls 2 .. .TL Application of Symbolic Mathematics to Mathematics .AF "Bell Laboratories" .AU "A. M. Odlyzko" AMO MH 11218 7286 2C-380 .AS 1 .P Some of the most interesting applications of symbolic mathematics are in mathematics itself. Areas of both pure and applied mathematics, including cryptography, coding theory, probablity theory, analysis, combinatorics, and number theory, have all gained from the availability of the new symbolic manipulation tools. These tools have been used to prove a number of results directly. Their main application, however, has been to obtain insight into behavior of various mathematical objects, which then led to conventional proofs being constructed. .AE .MT 4 .ls 2 .nr Pt 1 .H 1 INTRODUCTION This paper is an account of some applications of symbolic algebra systems to mathematics. It is not a general survey of this very wide subject, but rather a small selection from my own work, a selection made so as to illustrate the main point of the paper, which is that the most important applications of symbolic algebra systems is not to compute formulas as such, but to help in formulating and testing hypothesis. .P My experience with symbolic mathematics goes back over ten years. Most of this work was with MACSYMA\ [10], although at various points I or my collaborators used other systems such as ALTRAN\ [2], MAPLE\ [5], and SMP\ [4]. These systems were used in many fields of mathematics, as the examples presented here demonstrate. Still, these extremely varied examples do not cover the full range of applications that have been made, and are a reflection of my research interests. For example, one of the most impressive achievements in the field of computer algebra is the development of algorithms for indefinite integration. However, I have not yet made any serious use of them. The reason is that all of the many integrals I have worked with werre either very easy, so that I was able to do them either directy or with the help of a table of integrals, or else they were so hard that even the algorithms in MACSYMA failed on them. On the other hand, I have made use of most of the other capabilities of computer algebra systems at one time or another. Since my problems are usually quite mathematical to start with, I had a strong advantage over people in some other fields in not having to devote too much effort into translating these problems into a form suitable for symbolic manipulation programs. .P The theme of this paper is reflected in the famous aphorism of R.\ W. Hamming\ [8]: .DS 2 .I ``The purpose of computing is insight, not numbers.'' .R .DE In the context of computer algebra, this maxim could be modified to say that the purpose of symbolic maniuplation is insight, not formulas. To make it clear what is meant by this remark, consider some of the most successful applications of symbolic algebra, namely those to physics and celestial mechanics, which are listed and summarized briefly in\ [3]. In those applications, one is usually faced witha tremendously complicated mathematical descriptions of the system under consideration, and the goal of the symbolic algebra package is to go through a very long series of complicated transformations which result in a relatively simple formula which can then be used for numerical computation of planetary orbits, for example. The validity of the results depends on the correctness of the program that was used, and little or no insight is provided by those results into why they cam out the way they did. Important applications of this type do occur in mathematics, and an example will be presented in Section\ 2. It is my feeling, though, that such applications are not the most important ones. I see the main role of symbolic algebra systems as that of helping to formulate hypotheses, search for examples and counterexamples, and in general explore ramifications of mathematical models. In other words, the main role of these systems is to obtain mathematical insight. Once that insight is obtained, one can then go on and construct canonical mathematical proofs, in which there might not even be any traces of the use of computer algebra. Several examples of such applications are presented in Sections\ 3-5. .H 1 "CLASSIFICATION OF FINITE SIMPLE GROUPS" .P This section presents an application of computer algebra to our small chapter in the big subject of classification of finite simple groups, namely Boulieri's proof\ [1] of the uniqueness of simple groups of Ree type. This application was chosen as an example where only some computing power was needed, and no special insight was gained from the computation. .P Thompson had earlier shown that the uniqueness of simple groups of Ree type would follow if one could show that given any automorphism $sigma$ of $GF(3 sup 2n+1 )$, $n~>=~1$, $sigma~!=~3 sup n+1$, and integers $a, ^s$ such that $a$ is even, $s$ is odd, and $x sup {( sigma +1)}~=~x sup 2$ and $x sup {( sigma +2)s}~=~x$ for all $x~member~GF(3 sup 2n+1 )$, then is an element $x~member~GF(3 sup 2n+1 )$\e$GF(3)$ such that if .DS 3 .EQ z~=~(x~+~1) sup s^, ~~ y~=~(x~-~1) sup 2^,~~n~=~(x~+~1) sup 1-s~-~(x~-~1) sup 1-s^, .EN .DE then $u~nomem~GF(3)$ and .DS 3 .EQ (2.1) z(u~-~1) sup a~-~(z~-~y~+~1)u sup a~-~ y(u~+~1) sup 2~+~(u sup 2~-~1) sup a~!=~0~. .EN .DE Bombien succeeded in showing, by a sophisticated argument, that a suitable $x$ for which (2.1) holds can be found except possibly in a finite number of cases. Then the problem was reduced to a finite computation. .P The computations that completed Bombien's proof were carried out by D.\ Hart and myself (independently)\ [1]. Given any $x~member~GF(3 sup 2n+1 )$\e$GF(3)$, the chances of (2.1) being false seemed very low, so unless there were some unexpected phenomena (such as a counterexample to the conjecture), it seemed likely that choosing a random $x$ and computing the quantity o nthe left side of (2.1) would suffice. That, in fact, turned out to be the case. .P The computation of the quantity in (2.1) in a straightforward computer algebra step. It is necessary to generate the field $GF( 3 sup 2n+1 )$, which is equivalent to finding an irreducible polynomial of degree $2n~+~1$ over $GF(3)$, which can be done easily using known factorization algorithms and then to carry out the computations in the field $GF(3 sup 2n+1 )$. These computations are, in principle, quite straightforward. Their validity (and that of the main result) depend on the correctness of the programs and machines. The fact that (2.1) did hold for the choices of $x$ that were made only confirmed the guess that (2.1) would hold for most $x$'s, and did not provide any insight that would enable one to prove the result without the computations. .P As an aside, the computations required to complete Bombien's proof were in principle perfectly suited to the capabilities of the MACSYMA system. I wrote the necessary program in MACSYMA in a fraction of an hour and ran some small cases succesfully through it (and in the process discovered a previously unknown bug in MACSYMA). However, a quick extrapolation of the times needed for those examples showed that the entire computation would have taken on the order of several days of MACSYMA's time. Since I was then a non-paying guest at the MIT MACSYMA machine, I did not feel like straining my host's hospitality to such an extent. Therefore I spent a day or two writing a FORTRAN program especially for their job, which then carried out the entire computation in a few hours. Some of the output of that program was checked using MACSYMA, though. .H 1 "DISCRIMINANTS OF NUMBER FIELDS" In the precision example, the symobolic algebra application stood out on its own, since the final result depended on the correctness of the computation, and no special insight was provided into the reasons the result turned out the way it did. We next consider another application, where the role of computer algebra was quite different. This example is drawn from my dissention, which appeared in [12]. The subject of it was improved lower bounds for discriminants of number fields. The mehtods used were from analytic number theory. Some of the crucial technical lemmas required showing certain national functions were nonnegative over a wide range. For example, one of these problems was reduced to showing that .DS 3 .EQ P(v)~mark =~73v sup 8~-~20,214^v sup 7~+~ 2,094,^217v sup 6~-~92,766,496^v sup 5 .EN .sp .EQ lineup +~1,419,515,855~v sup 4~+~3,533,810,602~v sup 3 .EN .sp .EQ - 2,837,192,781~v sup 2~-~29,267,901,572~ v~+~237,342,960,316 .EN .DE satisfies $P(v)~>=~0$ for all $v~>=~-10$ [12, p.\ 288]. Now this is a problem that can be solved easily by some computer algebra systems, since there is an algorithm due to Sturm for determining the exact number of zeros of a polynomial in a given interval, and that algorithm is available in MACSYMA. However, the proof presented in\ [12] does not rely on the use of blot algorithm. .P It is easy to see, for example, that for $v~>=~0$, .DS 3 .EQ P sub 2 (v)~=~10 v sup 8~mark -~277v sup 7~+~2,868v sup 6~-~ 12,708v sup 5~+~19,445v sup 4 .EN .sp .EQ lineup +~4,840v sup 3~-~389v sup 2~-~401v~+~325~. .EN .DE Now for $0~<=~v~<=~1/2$, say, .DS 3 .EQ 389v sup 2~+~401v~<=~325,~~~12,708v sup 5~<=~19,~445v sup 4 ,~~ 277v sup 7~<=~2,868v sup 6 , .EN .DE and so $P sub 2 (v)~>=~0$ in that range. Other ranges are treated similarly. .P During the preparation of\ [12], the MACSYMA algorithm for finding the number of zeros of a polynomial in an internal was used (and some bugs in it were found). In fact, I used MACSYMA in the initial analysis that led to the reduction of the problem to the nonnegativity of polynomials like $P(v)$ of (3.1), and I used MACSYMA again in constructing the case-by-case proofs of the nonnegativity of the kind outlined above. As a result the proof can be verified even by people without access to computer algebra systems. The role of symbolic manipulation in this case was to spped up my own work by letting me kow which polynomials could be used and in helping to construct paper-and-pencil type proofs. .P The application of computer algebra disucssed here is roughly intermediate between the case discussed in Section\ 2, where the output of the computation was the result, and the cases to be discussed next, when computer algebra served only to provide insight. In the case of bounds for discriminants of number fields, the proof is much easier for the reader to check with the use of a computer algebra program than by following the proof given in the paper step-by-step. The point of going to the extra effort was to make the proof accessible even to those without access to such programs. In the cases of the result to be discussed next, even access to a symbolic manipulation system is of no help to the reader in verifying the proofs, although such access was very helpful in figuring out what the results ought be. .H 1 "ENUMERATION OF 2,3-TREES" A 2,3-tree is a rooted, oriented tree each of whose nonleaf nodes has either two or three successors, and all of whom root-to-leaf paths has the same length. 2,3-trees and their generalizations, of $B$-trees, and used as data structures in situations where it is desirable to be able to insert and delete records in time that is logarithmic in the total number of records present. Let $a sub n$ denote the number of \%2,3-trees of size (i.e., number of leaves) equal to $n$. In the paper\ [13], I showed that .DS 3 .EQ (4.1) a sub n~wig~n sup -1 q sup n~u( log n ) ~~roman as~n~->~inf~, .EN .DE where $q~=~(1~+~5 sup 1/2 )/2$ is the ``golden ratio,'' and $u(x)$ is a positive nonconstant continuous function which satisfies $u(x)~=~u(x~+~log ( u-q))$ for all real $x$. The proof contains no trace of the use of a symbolic manipulation program. However, such a program was very helpful in obtaining this result. The proof uses complex analyses techniques to study the generating function .DS 3 .EQ (4.2) f(z)~=~sum from n=1 ot inf~a sub n z sup n~. .EN .DE It is a general principle that the behavior of the coefficient $a sub n$ of $a$ generating function of the form (4.2) is determined by the analytic behavior of the function $f(z)$ was its singularities. It is easy to show that the generating function $f(z)$ for \%2,3-tries is analytic inside the circle $|z|~=~q sup -1$, and also on that circle with the exception of the point $z~=~q sup -1$, where it has a singularity. Since it was already known that .DS 3 .EQ (4.3) c sub 1 n sup -1 q sup n~<~a sub n~<~c sub 2 n sup -1 q sup n .EN .DE for some constants $c sub 1$ and $c sub 2$, I started out trying to prove the natural conjecture, namely that .DS 3 .EQ (4.4) a sub n~wig~cn sup -1 q sup n~~~roman as~n~->~inf .EN .DE for some constant $c$. If (4.4) were to hold, though, one would expect that .DS 3 .EQ (4.5) f(x)~wig~-c log (q usp -1~-~z)~~roman as~z~->~q sup -1~. .EN .DE It was not too difficult to prove (4.5), but I was unable to obtain a good enough estimate for the difference of the two sides in (4.5) to prove (4.4). The reason for that was that (4.4) is false, and (4.1) is the correct result. The crucial analytic result that led to the proof of (4.1) was the relation .DS 3 .EQ (4.6) f(z)~=~- c log (q sup -1 ~-~z)~+~w( log (q sup -1 ~-~z))~+~ 0(|q sup -1~-~z| ) .EN .DE as $z~->~q sup -1$, valid in a section of the form $| A~wig~g^(q sup -1~-~z)|~<~pi /2~+~delta$ for some $delta~>~0$, where $w(z)$ is a nonconstant analytic function which is periodic with period $log (4~-~q)$. The proof (4.6) involves intensive study of the polynomial iteration $T(z)~=~z sup 2~+~z sup 3$, since $f(z)$ satisfies the functional equation .DS 3 .EQ (4.7) f(z)~=~z~+~f(z sup 2~+~z sup 3 )~. .EN .DE .P The conjecture that the behavior of $f(z)$ is given by (4.6) was made partially on the basis of computations with MACSYMA. Having failed to prove (4.4), I used the high-precision floating point facility of that system to explore the behavior of $f(x)$ for $z$ mean $q sup -1$ by using the functional equation (4.7). By using the results of those computations and simultaneously investigating what phenomena could arise from iterating the mass $T(z)~=~z sup 2~member~z sup 3$, I was led to conjecture (4.6) and later to prove it. Also, by studying the polynomials $T(z)$, $T(T(z))$, etc., I was led to an understanding of how the behavior of $f(z)$ near its singularity at $z~=~q sup 1$ influenced the behavior of the coefficients $a sub n$, which led to the proof of (4.1). .P The role of computer algebra in this case was purely to provide insight, not to help with the proof itself. The result certainly could have been obtained without the use of symbols mathematics, and perhaps would have been, had I not had access to such systems, but the work would have been harder and would undoubted have taken longer. .H 1 "STRING ENUMERATION" Another example where computer algebra had as its main function providing insight is given by the work on enumeration strings\ [6,7]. As is shown in those papers and the references cited in them, a surprising variety of problems can be reduced to the question of evaluating the number of strings of length $n$ over some alphabet of $q$ symbols, call it $f(n)$, which contain none of a given set, call them $A$, $B$, ..., $T$ of words as subwords (i.e., blocks of consecutive characters). The basic result of\ [6], from which most of the others follow, is a simple formula for the generating function of $f(n)$, .DS 3 .EQ (5.1) F(z)~=~sum from n=0 to inf~f(n) z sup -n~. .EN .DE (we take $f(0)~=~1$. $F(x)$ is written as a power series on $z sup -1$ in order to obtain formulas.) To explain it, we define the correlation polynomial $XY sub z$ of the words $X~=~x sub 1 ... x sub k$ and $Y~=~y sub 1 ... y sub m$ to be .DS 3 .EQ (5.2) XY sub z~=~sum from j=1 to k~c sub jz sup j-1~, .EN .DE where $c sub j~=~1$ if the suffix of $X$ of length $j$ (i.e., $x sub k-j+1 ... x sub k )$ equals the prefix of $Y$ of length $j$ (i.e., $y sub i ... y sub j$), and $c sub j~=~0$ otherwise. (These are special values to take care of the case $m~<~k$.) The first result of [6] is that if the set of excluded words consists of a single word, call it $A$, then .DS 3 .EQ (5.3) F(z)~=~{zAA sub z} over {1~+~(z~-~q)AA sub z}~. .EN .DE The proof of (5.3) that we gave is very simple, taken only a couple of lines, and certainly does not require, nor is it even helped by the use of computer algebra. (Moreover, this particular result had been obtained earlier by Solov's\ [17].) However, computer algebra was extremely helpful in obtaining that proof in the first place. Guibar and I started out by constructing finite state automata, reducing the number of states i them, and obtaining generating functions from them which determined $F(z)$. It was a very laborious process, and we used MACSYMA to carry out the symbolic manipulations that were involved. The formulas for $F(z)$ that came out were surprisingly compact, and inspection of a number of them showed that they were all of the simple form (5.3). Once we saw this elegant formula, we considered that a simple proof had to exist, and it did not take very long to find it. Then in this case the role of computer algebra was to bring initial approaches. We might have found the result (5.3) by hand, but it would have taken us a lot longer. .P Once a simple proof of (5.3) was found, it was a simple matter to generalize it. If the set of excluded words is $"{"A,^B,~...,~T"}"$, and no word in this set contains another (as we may assume without loss of generality), then $F(z)$ is determined by the following system of linear equations: .DS 3 .EQ (z~-~q)^F(z)~+~zF sub A (z)~+~zF sub p (z)~+~...~ zF sub T (z)~=~z .EN .sp .EQ (5.4) F(z)~-~zAA sub z F sub A (z)~-~zBA sub z F sub B (z)~-~...~-~ zTA sub z F sub T (z)~=~0 .EN .sp .EQ 3dot .EN .sp .EQ F(z)~-~zAT sub z F sub A (z)~-~zBT sub z F sub p (z)~-~...~ -~zTT sub z F sub T (z)~=~0 .EN .DE Here $F sub A (z)$, ..., $F sub T (z)$ are generating functions related to $F(z)$. The system (5.4) can easily be shown to be nonsingular\ [6], and so $F(z)$ is seen to be a national function. Computer algebra is not needed in the proof of (5.4), and was not even used in deriving the proof, as it was fairly easy to generalize the proof of (5.3). .P Computer algebra was also useful in deriving other string enumeration results, but again at the level of providing insight, rather than providing proof. As an example, we might consider the asymptotic estimation of $f(x)$. If the set of excluded words consists of $A$ only, then (5.3) holds, and it can be shown that the behavior of $f(n)$ is determined almost completely by a first order pole of $F(z)$ near $z~=~q$\ [6,7]. No computer algebra is involved there, as only basic complex analysis is used. However, when several words are excluded, the situation can become much more complicated. For example, it can happen that $f(n)~=~0$ for all sufficiently large $n$, as occurs for the set {000, 111, 10} of $g~=~2$, in which case $F(z)$ is a polynomial on $z sup -1$. Thus in general we cannot say too much about the generating function $F(z)$ determined by (5.4). However, something can be done when we consider repetition patterns. Suppose that $B$ is a nonperiodic word of length $m$\ [7], so it cannot be written as $B~=~CC...C$ for any word $C$ shorter than $B$. A $B*$-run of length $k$ is a word $A~=~B prime prime BB ... B B prime$ of length $k$ where $B prime prime$ is a suffix of $B$ and $B prime$ is a prefix of $B$. Thus, if $B~=~010$, then $A~=~001001$ in a $B sup * -run$ of length $sigma$. Once can ask about the distribution of lengths of maximal $B sup *$-runs in random sequences. Now the number of strings of length $n$ that contains no $B sup *$-run of length $k$ is exactly $f(n)$, the number of strings of length $n$ that contain none of $A(1),~...,~A(m)$, where .DS 3 .EQ A(n)~=~b sub m-r+1~b sub m-r+2~...b sub n~ BB~...~BB prime~, .EN .DE and $B prime~=~B prime ( r )$ is a prefix of $B$ of the appropriate length. It can then be shown [7] that (for $q~=~2$, say) .DS 3 .EQ (5.5) F(z)~=~ {z sup (k+1)m+1~(z sup m~-~1) sup m-1~+~g sub 1(z)} over {(z~-~2) z sup (k+1)m~(z sup m~-~1) sup m-1~+~g sub 2 (z)}~, .EN .DE where $g sub 1 (z)$ and $g sub 2 (z)$ are polynomials of small degrees and small coefficients that satisfy some additional conditions (see\ [7] for details). From (5.5) one can then show that a good approximation to $f(n)$ is given by .DS 3 .EQ (5.6) f(n)~approx~2 sup n~exp (-nm2 sup -k-1 )~. .EN .DE Also, $E sub B sup * (n)$, the expected length of the maximal $B sup *$-run in a random binary sequence can be shown to satisfy .DS 3 .EQ (5.7) E sub B sup * (n)~=~mark log n~-~3/2~+~sigma ( log^2) sup -1~+~ log m .EN .sp .EQ +~v( log ^n~+~log m)~+~sigma (1)~roman as~n~->~inf~, .EN .DE when $lg x$ is the logarithm of $x$ to base 2, $gamma$ is Eulen's construct (0.577...), and $v(x)$ is a certain nonconstant continuous periodic function of period\ 1 and near value 0. .P The proof of (5.6) and (5.7) did not rely in any way on computer algebra. Even (5.5), which is a very algebraic result, and was proved by some very messy algebraic manipulations, was proved without the help of symbolic manipulation programs; since the algebra involve exponents and as $k$ and $m$ as variables, as small as $z$. However, computer algebra was very helpful in guessing that something like (5.5) might hold. The function $F(z)$ was computed for various $B * $-runs, and from their algebraic forms and their singularities, the correct conjectures were derived. .H 1 "MISCELLANEOUS APPLICATIONS AND CONCLUSIONS" Many more examples of the application of computer algebra to mathematics could be presented. I will note a few minor applications. In recent work on discrete logarithms\ [15], it was desirable to verify that for various degrees $n$, there are polynomials of the form $x sup n~+~f(x)$ which an irreducible over $GF(2)$ and such that the degree of $f(x)$ as small. Since about one out of $n$ polynomials of degree $n$ is irreducible over $GF (2)$, it was expected and confirmed by computation that one can find such $f(x)$ with dig $f(x)~