Re: [Axiom-developer] Re: article "standard" header/footer

[Martin Rubey]

Ralf Hemmecke <address@hidden> writes:

> Maybe I should learn about the term "executive overview". I am not quiet sure
> what "executive" stands for in this phrase. Isn't it a kind of "Introduction"
> what Martin wants? So what could possibly be the difference between
> "Introduction" and "Executive Overview"?

I'm not quite sure what I wanted some months ago, but I suggest the following:

Many contributions consist of several packages, categories and domains, which
are somehow related. We should have documentation for users (!!!) that consists
of the following:

* a short introduction to what the contribution does. An example can be found
  by clicking "examples" in HyperDoc after browsing "RECLOS". For my guessing
  package, it would be everything following the section "Using the package" at 

http://page.axiom-developer.org/zope/mathaction/GuessingFormulasForSequences

  However, this is a bit longish for my taste.

* For every constructor (package, domain, category) a short description what it
  does.  This is the ++ description of the package.

* For every operation a short description what it does. Again, this is the ++
  description of the package.

* Maybe we also need an indroduction that *roughly* describes the mathematical
  background. This would be everything up to "Using the package" in my Guessing
  package example and would not contain details. The details should probably go
  along with the program. This would not contain code, only mathematics.

  Unfortunately, I do not yet have such a description in pamphlet format for my
  guessing package. I attach a draft at the end of this mail. Note however,
  that this is outdated material.

I think that the way these bits of documentation are presented in HyperDoc is
just perfect. I don't think that it would be too difficult to make ALPROSE do
the same. In principle, HyperDoc is a collection of hyperlinked pages -- just
as ALPROSE when viewed in a browser and not a dvi-viewer.

I.e., we would need to devise a tex4ht interface for ALPROSE that suitable
splits the input into a tree of subpages, which can then be accessed by
selecting an item from the index...

Finally I'd like to stress that I strongly believe that AxiomUI should use the
same file format as the documentation. There is no semantic difference between
a worksheet and a literate program, except that a worksheet will be
interpreted, not compiled.


Martin

-------------------------------------------------------------------------------

\section{Guessing formulas with an Abelian term}
In this section we explain in detail how \verb|guessExpRat| works.

The basic idea is to reduce the problem to rational interpolation. Let
$s=(s_1,s_2,\dots,s_m)$ be the given list of values, which are elements of a
field $\mathbb K$. We then follow the following algorithm for each pair $(k,
l)$ with $k+l=m-4$:

\begin{itemize}
\item Let $y_n=s_n (a+bn)^{-n}$, where $a$ and $b$ are indeterminates.
\item Let $p$ be the result of interpolating $(y_1,y_2,\dots,y_{m-3})$ using
  rational interpolation, where the degree of the numerator is $k$, the degree
  of the denominator is $l$.
\item Let $p_i=\numer\left(p(i+m-3)-y(i+m-3)\right)$ for $i\in\{1,2,3\}$.
\end{itemize}
It remains to solve the system of the three polynomial equations $p_i = 0$,
$i\in\{1,2,3\}$ in the two variables $a$ and $b$.
%, such that $a$ and $b$ do not both vanish. 
This can be done reasonably efficiently using resultants:

\begin{itemize}
\item Substitute $A-mb$ for $a$ in the three polynomials $p_1$, $p_2$ and
  $p_3$.
\item Let $r_1=\resultant(p_1, p_3, A)$ and $r_2=\resultant(p_2, p_3, A)$.
\item Compute $r_3=\gcd(r_1, r_2)$ and calculate the solutions $\tilde A$ of
  $r_3=0$. For simplicity, we consider only those that are elements of the
  field.
\item For each $\tilde A$ calculate the solutions $\tilde a$ of $p_2(\tilde
  A, \tilde a)=0$ that satisfy $p_3(\tilde A, \tilde a)=0$, too.
\item If such a solution can be found return $\left(\tilde A + \tilde b
    (n-m)\right)^n p(\tilde a,\tilde b)$ as a formula generating the sequence
  $s$.
\end{itemize}

Clearly, the method to solve three polynomial equations in two unknowns just
outlined is feasible only when the degree of the polynomials is not too large.
The substitution in the first step results in a much lower degree of the
polynomial $p_3$, which speeds up the process significantly. Still, for
sequences with more than about $7$ terms, it is too slow to be useful.
However, numerical evidence supports the following conjecture:

\begin{cnj}
  The order and the degree of the polynomials $r_1$ and $r_2$ is given by the
  following formulas, where $n=m-i$, $m$ is the number of terms in the given
  sequence $s$ and $i$ is the degree of the numerator in $p$:
  \begin{align*}
    \ord r_1 &= \frac{(n - 1)n(3n^2 - n + 2)}{12}\\
    \deg r_1 &= \frac{(n - 1)(3n^3 + (12i + 5)n^2 + (12i^2 + 6i + 20)n 
                             - 12i^2 + 12i + 12)}{12}\\
    \ord r_2 &= \ord r_1 +
    \begin{cases}
      \frac{n(n-1)}{2} &\text{if $i=0$}\\
      0                &\text{otherwise}
    \end{cases}\\
    \deg r_2 &= \deg r_1 + \frac{n^2+(2i+1)n-2i+2}{2}.
  \end{align*}
\end{cnj}

Thus, since it appears that the two resultants have very large orders, it makes
sense to calculate them by interpolation. For example, the values of 
$$\resultant(p_1(A=k),p_3(A=k)) k^{-\ord res_1}$$
at $k\in\{1,2,\dots,\deg r_1-\ord r_1+1\}$ determine $r_1$ uniquely.

Although this yields a significant speedup for sequences longer than $7$ terms,
more work needs to be done to be able to guess more complicated formulas with
\verb|guessExpRat|. For example,
\begin{verbatim}
  guessExpRat(n, [(2*n+3)^n*(4*n^3+3*n^2+2*n+1) for n in 1..7], 
              n+->n)$GuessInteger
\end{verbatim}
takes roughly $13$ seconds, while
\begin{verbatim}
  guessExpRat(n, [(2*n+3)^n*(5*n^4+4*n^3+3*n^2+2*n+1)
                  for n in 1..8], n+->n)$GuessInteger
\end{verbatim}
takes already $55$ seconds on a {\tt Pentium III} with $900$ megahertz and
$512$ Megabytes of memory.

Note that care has to be taken if the original sequence contains zeros. In this
case it might happen that $(a + bn)$ vanishes for some $n\in\{1,2,\dots,m\}$
and the formula would not be found. In this case we set $z(n)=\prod_{s_i=0}
(n-i)$ and $s^\prime$ to the sequence $s$ with the zeros omitted. Then we apply
\verb|guessExpRat| to the list $\left(s^\prime_1/z(1), s^\prime_2/z(2),\dots,
  s^\prime_m/z(m)\right)$ and multiply the results with $z(n)$.

\section{Further work}

To conclude, we would like to point out future directions:
\begin{itemize}
\item Obviously, it would be nice to be able to guess formulas of a more
  general type then those guessed by \verb|guessExpRat|. This would involve
  finding a fast algorithm that tests whether an overdetermined systems of
  equations has a solution. Much work has been done in this direction, for
  starting points see \cite{CoxLittle, EmirisPan2005, Khetan}, but strange
  enough, the naive elimination algorithm detailed above seems to be the
  fastest method available currently.

\item We did not yet implement a guessing algorithm that covers algebraic
  differentially finite functions.
  
\item Finally, maybe there are other interesting operators besides $\Delta_n$
  and $Q_n$ that could be applied to the sequence. The list of transformations
  used in \emph{The online encyclopedia of integer sequences} is available, so
  it might be rewarding to check, which of those extend the class of functions
  already covered significantly.
\end{itemize}