Edit detail for Guessing formulas for sequences revision 12 of 15

Author: Martin Rubey

A more thorough discussion of this package can be found at http://arxiv.org/abs/math.CO/0702086
Important Note
   There is a bug (#8) in the version of Axiom currently running on this server that
messes up the output by missing some parenthesis. A preliminary - though a little 
unsatisfactory - patch is available. We hope that a proper fix will soon be applied.
Please add other bugs you find to IssueTracker by clicking on
Bug reports
on the top left of any page and filling out the appropriate forms.
Finally, please feel free to try this package in the SandBox! If you would like to use
this program at your own computer, you need the FriCAS version of axiom.
If you find the package useful, please let me know!
Abstract
  We present a software package that guesses formulas for sequences of, for
example, rational numbers or rational functions, given the first few terms.
Thereby we extend and complement Christian Krattenthaler's program Rate and
the relevant parts of Bruno Salvy and Paul Zimmermann's GFUN.
This research was partially supported by the Austrian Science Foundation FWF, grant S8302-MAT.
Introduction
  For some a brain-teaser, for others one step in proving their next theorem:
given the first few terms of a sequence of, say, integers, what is the next
term, what is the general formula? Of course, no unique solution exists,
however, by Occam's razor, we will prefer a "simple" formula over a more
"complicated" one.
Some sequences are very easy to "guess", like
\begin{equation}
\label{eq1}
1,4,9,16,\dots,
\end{equation}
or
\begin{equation}
\label{eq2}
1,1,2,3,5,\dots.
\end{equation}
Others are a little harder, for example
\begin{equation}
\label{eq3}
0,1,3,9,33,\dots.
\end{equation}
Of course, at times we might want to guess a formula for a sequence of
polynomials, too:
\begin{equation}
\label{eq4}
1,1+q+q^2,(1+q+q^2)(1+q^2),(1+q^2)(1+q+q^2+q^3+q^4)\dots,
\end{equation}
or
\begin{equation}
\label{eq5}
  \frac{1-2q}{1-q}, 1-2q,(1-q)(1-2q)^3,(1-q)^2(1-2q)(1-2q-2q^2)^3,\dots
\end{equation}
Fortunately, with the right tool, it is a matter of a moment to figure out
formulas for all of these sequences. In this article we describe a computer
program that encompasses well known techniques and adds new ideas that we hope
to be very effective.
Fortunately, with the right tool, it is a matter of a moment to figure out
formulas for all of these sequences. In this article we describe a computer
program that encompasses well known techniques and adds new ideas that we hope
to be very effective. In particular, we generalize both Christian
Krattenthaler's program Rate, and the guessing functions present
in GFUN written by Bruno Salvy and Paul Zimmermann. With a little
manual aid, we can guess multivariate formulas as well, along the lines of
Doron Zeilberger's programs GuessRat and GuessHolo.
We would also like to mention The online encyclopedia of integer
sequences of Neil Sloane. There, you can enter a sequence of
integers and chances are good that the website will respond with one or more
likely matches.  However, the approach taken is quite different from ours: the
encyclopedia keeps a list of currently $117,520$ sequences, entered more or
less manually, and it compares the given sequence with each one of those.
Besides that, it tries some simple transformations on the given sequence to
find a match.  Furthermore it tries some simple programs we will describe below
to find a formula, although with a time limit, i.e., it gives up when too much
time has elapsed.
Thus, the two approaches complement each other: For example, there are
sequences where no simple formula is likely to exist, and which can thus be
found only in the encyclopedia. On the other hand, there are many sequences
that have not yet found their way into the encyclopedia, but can be guessed in
a few minutes by your computer.
On the historical side, we remark that already in 1966 Paul W.
Abrahams implemented a program to identify sequences given
their first few terms...
  Safety and Speed
    A formula for Sequence (1) is almost trivial to guess: it
seems obvious that it is $n^2$. More generally, if we believe that the sequence
in question is generated by a polynomial, we can simply apply interpolation.
However, how can we know that a polynomial formula is appropriate? The
answer is quite simple: we use all but the last few terms of the sequence to
derive the formula. After this, the last terms are compared with the values
predicted by the polynomial. If they coincide, we can be confident that the
guessed formula is correct. We call the number of terms used for checking the
formula the safety of the result.

Apart from safety, the main problem we have to solve is about efficiency.  For
example, maybe we would like to test whether the $n^{th}$ term
of the sequence is given by a formula of the form
\begin{equation}
\label{eq6}
  n\mapsto (a+bn)^n \frac{r(n)}{s(n)}
\end{equation}
for some $a$ and $b$ and polynomials $r$ and $s$.  Of course, we could set up
an appropriate system of polynomial equations.  However, it would usually take
a very long time to solve this system.
Thus, we need to find efficient algorithms that test for large classes
of formulas. Obviously, such algorithms exist for interpolation and Pade
approximation. For the present package, we implemented an efficient algorithm
for a far reaching generalization of interpolation, proposed by Bernhard
Beckermann and George Labahn, see FractionFreeFastGaussianElimination. Furthermore, we show
that there is also a way to guess sequences generated by Formula (6).
Using these algorithms our package clearly outperforms both Rate and GFUN,
in terms of speed as well as in the range of formulas that can be guessed.
In the following section we outline the capabilities of our package. In the Section therafter
we describe the most important options that modify the behaviour of the functions.
  Function Classes Suitable for Guessing
    In this section we briefly present the function classes which are covered by
our package. Throughout this section, $n\mapsto f(n)$ is the function we would
like to guess, and $F(z)=\sum_{n\ge0} f(n)z^n$ is its generating function. The
values $f(n)$ are supposed to be elements of some field $\mathbb K$, usually
the field of rationals or rational functions. We alert the reader that the
first value in the given sequence always corresponds to the value $f(0)$.
    Guessing $f(n)$


guessRec finds recurrences of the form
\begin{equation}
\label{eq7}
  p\left(1, f(n), f(n+1),\dots,f(n+k)\right)=0,
\end{equation}
where $p$ is a polynomial with coefficients in $\mathbb K[n]$. For example,
fricas
guessRec([1,1,0,1,- 1,2,- 1,5,- 4,29,- 13,854,- 685])
\begin{equation*}
\label{eq8}\left[{\left[{{{f \left({n}\right)}\mbox{\rm :}}{{{f \left({n + 2}\right)}+{f \left({n + 1}\right)}-{{f \left({n}\right)}^{2}}}= 0}}, \:{{f \left({0}\right)}= 1}, \:{{f \left({1}\right)}= 1}\right]?}\right]\end{equation*}
Type: List(Expression(Integer))
        Note that, at least in the current implementation, we do not exclude
solutions that do not determine the function $f$ completely. For example,
given a list containing only zeros and ones, one result will be
\begin{equation*}
  [f(n): f(n)^2-f(n)=0,f(0)=\dots]?.
\end{equation*}

guessPRec only looks for recurrences with linear $p$, i.e., it
recognizes P-recursive sequences. As an example,
fricas
guessPRec([0, 1, 0, -1/6, 0, 1/120, 0, -1/5040, 0, 1/362880, 0, -1/39916800])
\begin{equation*}
\label{eq9}\left[ \right]?\end{equation*}
Type: List(Expression(Integer))

guessRat finds rational functions. For the sequence given in
Equation (1), we find $n^2$ as likely solution.
guessExpRat finds rational functions with an Abelian term, i.e.,
\begin{equation}
  f(n)=(a+bn)^n\frac{r(n)}{s(n)}
\end{equation}
where $r$ and $s$ are polynomials.
fricas
guessExpRat([0,3,32,375,5184,84035])
\begin{equation*}
\label{eq10}\left[{n \ {{\left(n + 2 \right)}^{n}}}\right]?\end{equation*}
Type: List(Expression(Integer))






Concerning $q$-analogues, guessRec(q) finds recurrences of the
form (7), where $p$ is a polynomial with coefficients in $\mathbb K[q, q^n]?$.
Similarly, we provide $q$-analogues for guessPRec and
guessRat. Finally, guessExpRat(q) recognizes functions of the form
\begin{equation}
  f(n)=(a+bq^n)^n\frac{r(q^n)}{s(q^n)},
\end{equation}
$a$ and $b$ being in $\mathbb K[q]?$ and $r$ and $s$ polynomials with
coefficients in $\mathbb K[q]?$. This includes, for example, Nicholas Loehr's
$q$-analogue $[n+1]?_q^{n-1}$ of Cayley's formula, where
$[n]?_q=1+q+\dots+q^{n-1}$.
For Sequence (5), we enter
fricas
guessExpRat(q)([(1-2*q)/(1-q),1-2*q,(1-q)*(1-2*q)^3,(1-q)^2*(1-2*q)*(1-2*q-2*q^2)^3], [])
\begin{equation*}
\label{eq11}\left[{{{\left({2 \  q}- 1 \right)}\ {{\left({2 \ {{q}^{n}}}-{3 \  q}+ 1 \right)}^{n}}}\over{q - 1}}\right]?\end{equation*}
Type: List(Expression(Integer))
    Guessing $F(z)$


guessADE finds an algebraic differential equation for $F(z)$,
i.e., an equation of the form
\begin{equation}
\label{eq12}
    p\left(1, F(z), F^\prime(z),\dots,F^{k}(z)\right)=0,
\end{equation}
where $p$ is a polynomial with coefficients in $\mathbb K[z]?$. A typical
example is $\sum n^n\frac{x^n}{n!}$:
fricas
guessADE([1,1,2,9/2,32/3,625/24,324/5,117649/720,131072/315])
\begin{equation*}
\label{eq13}\left[ \right]?\end{equation*}
Type: List(Expression(Integer))
guessHolo only looks for equations of the form (11) with
linear $p$, that is, it recognizes holonomic or differentially-finite
functions. It is well known that the class of holonomic functions coincides
with the class of functions having P-recursive Taylor coefficients. However,
the number of terms necessary to find the differential equation often differs
greatly from the number of terms necessary to find the recurrence. Returning
to the example given for guessPRec, we find that already the first 6 terms
are sufficient to guess a generating function:
fricas
guessHolo([0,1,0,-1/6,0,1/120])
\begin{equation*}
\label{eq14}\left[{\left[{{\left[{x}^{n}\right]?}{f \left({x}\right)}\mbox{\rm :}{{{{f_{\ }^{, ,}}\left({x}\right)}+{f \left({x}\right)}}= 0}}, \:{{f \left({x}\right)}={x -{{{x}^{3}}\over 6}+{O \left({{x}^{4}}\right)}}}\right]}\right]\end{equation*}
Type: List(Expression(Integer))
        Moreover, now we immediately recognise the coefficients as being those of the
sine function.
guessHolo is also the function provided by GFUN.  Here is a comparison
  of average running times in seconds over several runs on the same machine for
  a list of $n$ elements
\begin{tabular}{lrrrrrrrrrr}
    $n$:   & 50  & 75  &  100 & 125   \
    GFUN: & 1.9 & 5.2 & 22.1 &  63.0 \
    Guess:  & 0.1 & 0.3 &  0.6 &   1.2     
\end{tabular}

guessAlg looks for an algebraic equation satisfied by $F(z)$,
i.e., an equation of the form
\begin{equation}
  p\left(1, f(x)\right)=0,
\end{equation}
the prime example being given by the Catalan numbers
fricas
first guessAlg [1,1,2,5,14,42]
\begin{equation*}
\label{eq15}\begin{array}{@{}l}
\displaystyle
\left[{{\left[{x}^{n}\right]?}{f \left({x}\right)}\mbox{\rm :}{{{x \ {{f \left({x}\right)}^{2}}}-{f \left({x}\right)}+ 1}= 0}}, \: \right.
\
\
\displaystyle
\left.{{f \left({x}\right)}={1 + x +{2 \ {{x}^{2}}}+{5 \ {{x}^{3}}}+{O \left({{x}^{4}}\right)}}}\right] 
\end{array}
\end{equation*}
Type: Expression(Integer)
guessPade recognises rational generating functions. For the
Fibonacci sequence given in Equation (2), we find as likely
solution
\begin{equation*}
  [[x^n ]f(x): (x^2  + x - 1)f(x) + 1= 0].
\end{equation*}



We provide $q$-analogues, replacing differentiation with $q$-dilation:
guessADE(q) finds differential equations of the form
\begin{equation}
\label{eq16}
  p\left(1, F(z), F(qz),\dots,F(q^kz)\right)=0,
\end{equation}
where $p$ is a polynomial with coefficients in $\mathbb K[q, z]?$. Similarly,
there are $q$-analogues for guessHolo, guessAlg, and guessPade.
To guess a formula for Sequence (4), we enter
fricas
guessRat(q)([1,1+q+q^2,(1+q+q^2)*(1+q^2),(1+q^2)*(1+q+q^2+q^3+q^4)], [])
\begin{equation*}
\label{eq17}\left[{{{{{q}^{3}}\ {{q}^{2 \  n}}}+{{\left(-{{q}^{2}}- q \right)}\ {{q}^{n}}}+ 1}\over{{{q}^{3}}-{{q}^{2}}- q + 1}}\right]?\end{equation*}
Type: List(Expression(Integer))
    Operators
      The main observation made by Christian Krattenthaler in designing his program
Rate is the following: it occurs frequently that although a sequence of numbers
 is not generated by a rational function, the sequence of successive quotients is.

We slightly extend upon this idea, and apply recursively one or both of the two
following operators:

guessSum - $\Delta_n$ the differencing operator, transforming
$f(n)$ into $f(n)-f(n-1)$.
guessProduct - $Q_n$ the operator that transforms $f(n)$ into
$f(n)/f(n-1)$.



For example, to guess a formula for Sequence (3), we enter
fricas
guess([0, 1, 3, 9, 33], [guessRat], [guessSum, guessProduct])
\begin{equation*}
\label{eq18}\left[{\sum_{
\displaystyle
{{s_{5}}= 0}}^{
\displaystyle
{n - 1}}{\prod_{
\displaystyle
{{p_{4}}= 0}}^{
\displaystyle
{{s_{5}}- 1}}{\left({p_{4}}+ 2 \right)}}}\right]\end{equation*}
Type: List(Expression(Integer))

The second argument to guess indicates which of the functions of the
previous section to apply to each of the generated sequence, while the third
argument indicates which operators to use to generate new sequences.
In the case where only the operator $Q_n$ is applied, our package is directly
comparable to Rate. In this case the standard example is the number of
alternating sign matrices
fricas
guess([1, 1, 2, 7, 42, 429, 7436, 218348], [guessRat], [guessProduct])
\begin{equation*}
\label{eq19}\left[{\prod_{
\displaystyle
{{p_{8}}= 0}}^{
\displaystyle
{n - 1}}{\prod_{
\displaystyle
{{p_{7}}= 0}}^{
\displaystyle
{{p_{8}}- 1}}{{{{27}\ {{p_{7}}^{2}}}+{{54}\ {p_{7}}}+{24}}\over{{{1
6}\ {{p_{7}}^{2}}}+{{32}\ {p_{7}}}+{12}}}}}\right]\end{equation*}
Type: List(Expression(Integer))

Here are the average running times in seconds for our package and Rate over
several runs on the same machine for a list of $n$ elements:
\begin{tabular}{lrrrrrrrrrr}
  $n$:     & 14   & 15  & 16   & 17   &  18\
  Rate:   & 1.0  & 3.3 & 29.7 & 44.9 & 398\
  Guess:  & 0.9  & 2.3 &  6.6 & 22.4 &  74
\end{tabular}
    Options
      To give you the maximum flexibility in guessing a formula for your favourite
sequence, we provide options that modify the behaviour of the functions as
described in Section~\ref{sec:function-classes}. The options are appended,
separated by commas, to the guessing function in the form \spad{option==value}.
See below for some examples.


debug specifies whether informations about progress should be
reported.
safety specifies, as explained at the beginning of
Section 2, the number of values reserved for testing any
solutions found. The default setting is 1.
        Experiments seem to indicate that for guessADE higher settings are
appropriate than for guessRat. I.e., if a rational function
interpolates the given list of terms, where the final term is used for
testing, we can be pretty sure that the formula found is correct. By
contrast, we recommend setting safety to 3 or 4 when using
guessADE. For all algorithms except guessExpRat we recommend to
omit trailing zeros.

one specifies whether the guessing function should return as soon
as at least one solution is found. By default, this option is set to true.
maxDegree specifies the maximum degree of the coefficient
polynomials in an algebraic differential equation or a recursion with
polynomial coefficients. For rational functions with an exponential term,
maxDegree bounds the degree of the denominator polynomial. This option
is especially interesting if trying rather long sequences where it is unclear
whether a solution will be found or not. Setting maxDegree to -1, which is the default, specifies that the
maximum degree can be arbitrary.
allDegrees specifies whether all possibilities of the degree
vector - taking into account maxDegree - should be tried.  The
default is true for guessPade and guessRat and false for all other functions.
homogeneous specifies whether the search space should be
restricted to homogeneous algebraic differential equations or homogeneous
recurrences. By default, it is set to false.
maxDerivative - maxShift specify the maximum derivative in
an algebraic differential equation, or, in a recurrence relation, the maximum
shift. Setting the option to -1 specifies that the maximum derivative -
the maximum shift - may be arbitrary.
maxPower specifies the maximum total degree in an algebraic
differential equation or recurrence: for example, the degree of $(f'')^3 f'$
is 4. Setting the option to -1 specifies that the maximum total degree
may be arbitrary. For example,
fricas
l := [1, 1, 1, 1, 2, 3, 7, 23, 59, 314, 1529, 8209, 83313, 620297, 7869898, 126742987, 1687054711, 47301104551, 1123424582771, 32606721084786, 1662315215971057];
Type: List(PositiveInteger?)
fricas
guessRec(l, maxPower==2)
\begin{equation*}
\label{eq20}\begin{array}{@{}l}
\displaystyle
\left[ \left[{{{f \left({n}\right)}\mbox{\rm :}}{{-{{f \left({n}\right)}\ {f \left({n + 4}\right)}}+{{f \left({n + 1}\right)}\ {f \left({n + 3}\right)}}+{{f \left({n + 2}\right)}^{2}}}= 0}}, \right.
\
\
\displaystyle
\left.\:{{f \left({0}\right)}= 1}, \:{{f \left({1}\right)}= 1}, \:{{f \left({2}\right)}= 1}, \:{{f \left({3}\right)}= 1}\right] \right] 
\end{array}
\end{equation*}
Type: List(Expression(Integer))
        returns the Somos-4 recurrence, whereas without limiting the power to 2, we need the first 33 values, and
instead of roughly one second half a minute of computing time.

maxLevel specifies how many levels of recursion are tried when
applying operators. Note that, applying either of the two operators results in a sequence which is by one
shorter than the original sequence. Therefore, in case both guessSum
and guessProduct are specified, the number of times a guessing
algorithm from the given list of functions is applied is roughly $2^n$, where
$n$ is the number of terms in the given sequence. Thus, especially when the
list of terms is long, it is important to set maxLevel to a low value.
        Still, the default value is -1, which means that the number of levels is
only restricted by the number of terms given in the sequence.

indexName, variableName, functionName specify
symbols to be used for the output. The defaults are n, x and f respectively.


    A note on the output
      The output of any function described in Section 3 is a
list of formulae which seem to fit, along with an integer that states from
which term on the formula is correct. The latter is necessary, because rational
interpolation features sometimes unattainable points, as the following
example shows:
fricas
guessRat([3, 4, 7/2, 18/5, 11/3, 26/7])
\begin{equation*}
\label{eq21}\left[{\left[{{{f \left({n}\right)}\mbox{\rm :}}{{{{\left(-{{n}^{2}}- n + 2 \right)}\ {f \left({n}\right)}}+{4 \ {{n}^{2}}}+{2 \  n}- 6}= 0}}\right]?}\right]\end{equation*}
Type: List(Expression(Integer))


$order=2$ indicates that the first two terms of the sequence might not
coincide with the value predicted by the returned function. A similar situation
occurs, if the function generating the sequence has a singular point at
$n_0\in\mathbb N$, where $0 \leq n_0 < m$ and $m$ is the number of given
values.  We would like to stress that this is rather a feature than a 
bug: most terms will be correct, just as in the example above, where the
value at $n=0$ is indeed 3.


Fricas Version --Bill Page,  Wed, 14 Oct 2009 10:33:47 -0700 reply
fricas
)version

Value = "FriCAS 1.2.1 compiled at Monday July 1, 2013 at 23:26:54 "

This is pdfTeXk, Version 3.141592-1.40.3 (Web2C 7.5.6)
 \write18 enabled.
 %&-line parsing enabled.
entering extended mode
(./5960265500808565217-16.0px.tex
LaTeX2e <2005/12/01>
Babel <v3.8h> and hyphenation patterns for english, usenglishmax, dumylang, noh
yphenation, arabic, farsi, croatian, ukrainian, russian, bulgarian, czech, slov
ak, danish, dutch, finnish, basque, french, german, ngerman, ibycus, greek, mon
ogreek, ancientgreek, hungarian, italian, latin, mongolian, norsk, icelandic, i
nterlingua, turkish, coptic, romanian, welsh, serbian, slovenian, estonian, esp
eranto, uppersorbian, indonesian, polish, portuguese, spanish, catalan, galicia
n, swedish, ukenglish, pinyin, loaded.
(/usr/share/texmf-texlive/tex/latex/base/article.cls
Document Class: article 2005/09/16 v1.4f Standard LaTeX document class
(/usr/share/texmf-texlive/tex/latex/base/size12.clo))
(/usr/share/texmf-texlive/tex/latex/ucs/ucs.sty
(/usr/share/texmf-texlive/tex/latex/ucs/data/uni-global.def))
(/usr/share/texmf-texlive/tex/latex/base/inputenc.sty
(/usr/share/texmf-texlive/tex/latex/ucs/utf8x.def))
(/usr/share/texmf-texlive/tex/latex/bbm/bbm.sty)
(/usr/share/texmf-texlive/tex/latex/jknapltx/mathrsfs.sty)
(/usr/share/texmf-texlive/tex/latex/base/fontenc.sty
(/usr/share/texmf-texlive/tex/latex/base/t1enc.def))
(/usr/share/texmf-texlive/tex/latex/pstricks/pstricks.sty
(/usr/share/texmf-texlive/tex/generic/pstricks/pstricks.tex
`PSTricks' v1.15  <2006/12/22> (tvz)
(/usr/share/texmf-texlive/tex/generic/pstricks/pstricks.con))
(/usr/share/texmf/tex/latex/xcolor/xcolor.sty
(/etc/texmf/tex/latex/config/color.cfg)
(/usr/share/texmf-texlive/tex/latex/graphics/dvips.def)
(/usr/share/texmf-texlive/tex/latex/graphics/dvipsnam.def)))
(/usr/share/texmf-texlive/tex/latex/graphics/epsfig.sty
(/usr/share/texmf-texlive/tex/latex/graphics/graphicx.sty
(/usr/share/texmf-texlive/tex/latex/graphics/keyval.sty)
(/usr/share/texmf-texlive/tex/latex/graphics/graphics.sty
(/usr/share/texmf-texlive/tex/latex/graphics/trig.sty)
(/etc/texmf/tex/latex/config/graphics.cfg))))
(/usr/share/texmf-texlive/tex/latex/pst-grad/pst-grad.sty
(/usr/share/texmf-texlive/tex/generic/pst-grad/pst-grad.tex
(/usr/share/texmf-texlive/tex/latex/xkeyval/pst-xkey.tex
(/usr/share/texmf-texlive/tex/latex/xkeyval/xkeyval.sty
(/usr/share/texmf-texlive/tex/latex/xkeyval/xkeyval.tex)))
`pst-plot' v1.05, 2006/11/04 (tvz,dg,hv)))
(/usr/share/texmf-texlive/tex/latex/pstricks/pst-plot.sty
(/usr/share/texmf-texlive/tex/generic/pstricks/pst-plot.tex
 v97 patch 2, 1999/12/12
(/usr/share/texmf-texlive/tex/generic/multido/multido.tex
 v1.41, 2004/05/18 <tvz>)))
(/usr/share/texmf-texlive/tex/latex/geometry/geometry.sty
(/usr/share/texmf-texlive/tex/xelatex/xetexconfig/geometry.cfg)

Package geometry Warning: `lmargin' and `rmargin' result in NEGATIVE (-108.405p
t).
    `width' should be shortened in length.
) (/usr/share/texmf-texlive/tex/latex/amsmath/amsmath.sty
For additional information on amsmath, use the `? option.
(/usr/share/texmf-texlive/tex/latex/amsmath/amstext.sty
(/usr/share/texmf-texlive/tex/latex/amsmath/amsgen.sty))
(/usr/share/texmf-texlive/tex/latex/amsmath/amsbsy.sty)
(/usr/share/texmf-texlive/tex/latex/amsmath/amsopn.sty))
(/usr/share/texmf-texlive/tex/latex/amsfonts/amsfonts.sty)
(/usr/share/texmf-texlive/tex/latex/amsfonts/amssymb.sty)
(/usr/share/texmf-texlive/tex/latex/amscls/amsthm.sty)
(/usr/share/texmf-texlive/tex/latex/setspace/setspace.sty
Package: `setspace 6.7 <2000/12/01>
) (/usr/share/texmf-texlive/tex/generic/xypic/xy.sty
(/usr/share/texmf-texlive/tex/generic/xypic/xy.tex Bootstrap'ing: catcodes,
docmode, (/usr/share/texmf-texlive/tex/generic/xypic/xyrecat.tex)
(/usr/share/texmf-texlive/tex/generic/xypic/xyidioms.tex)
 Xy-pic version 3.7 <1999/02/16>
 Copyright (c) 1991-1998 by Kristoffer H. Rose <krisrose@ens-lyon.fr>
 Xy-pic is free software: see the User's Guide for details.

Loading kernel: messages; fonts; allocations: state, direction,
utility macros; pictures: \xy, positions, objects, decorations;
kernel objects: directionals, circles, text; options; algorithms: directions,
edges, connections;  Xy-pic loaded))
(/usr/share/texmf-texlive/tex/generic/xypic/xyall.tex
 Xy-pic option: All features v.3.3
(/usr/share/texmf-texlive/tex/generic/xypic/xycurve.tex
 Xy-pic option: Curve and Spline extension v.3.7 curve, circles, loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xyframe.tex
 Xy-pic option: Frame and Bracket extension v.3.7 loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xycmtip.tex
 Xy-pic option: Computer Modern tip extension v.3.3
(/usr/share/texmf-texlive/tex/generic/xypic/xytips.tex
 Xy-pic option: More Tips extension v.3.3 loaded) loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xyline.tex
 Xy-pic option: Line styles extension v.3.6 loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xyrotate.tex
 Xy-pic option: Rotate and Scale extension v.3.3 loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xycolor.tex
 Xy-pic option: Colour extension v.3.3 loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xymatrix.tex
 Xy-pic option: Matrix feature v.3.4 loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xyarrow.tex
 Xy-pic option: Arrow and Path feature v.3.5 path, \ar, loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xygraph.tex
 Xy-pic option: Graph feature v.3.7 loaded) loaded)
(/usr/share/texmf-texlive/tex/latex/tools/verbatim.sty)
(/usr/share/texmf/tex/latex/graphviz/graphviz.sty
(/usr/share/texmf-texlive/tex/latex/psfrag/psfrag.sty))
(/usr/share/texmf/tex/latex/sagetex.sty
Writing sage input file 5960265500808565217-16.0px.sage
) (/usr/share/texmf-texlive/tex/latex/gnuplottex/gnuplottex.sty
(/usr/share/texmf-texlive/tex/latex/base/latexsym.sty)
(/usr/share/texmf-texlive/tex/latex/moreverb/moreverb.sty)
(/usr/share/texmf-texlive/tex/latex/base/ifthen.sty))
(./5960265500808565217-16.0px.aux)
(/usr/share/texmf-texlive/tex/latex/ucs/ucsencs.def)
(/usr/share/texmf-texlive/tex/latex/jknapltx/ursfs.fd)
(/usr/share/texmf-texlive/tex/latex/amsfonts/umsa.fd)
(/usr/share/texmf-texlive/tex/latex/amsfonts/umsb.fd)
(/usr/share/texmf-texlive/tex/latex/base/ulasy.fd) [1] [2] [3] [4]
Package amsmath Warning: Foreign command \over;
(amsmath)                \frac or \genfrac should be used instead
(amsmath)                 on input line 139.
[5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20]
[21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35]
[36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50]
[51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65]
[66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80]
[81]
 Missing \right. inserted.
<inserted text> 
                \right .
l.286 \
 Extra \right.
l.289 ...:{{f \left({3}\right)}= 1}\right] \right]

[82] [83] [84] [85] [86] [87] [88] [89] [90] (./5960265500808565217-16.0px.aux)
 )
(see the transcript file for additional information)
Output written on 5960265500808565217-16.0px.dvi (90 pages, 21556 bytes).
Transcript written on 5960265500808565217-16.0px.log.