[Axiom-math] Re: multivariate resultants

[Martin Rubey]

I sort of forgot to ask, is there an easy way to exclude the trivial solution
(0,0) with your algorithm? (i.e, decide whether the system has a nontrivial
common root?)

Martin

Martin Rubey writes:
 > Dear Amit,
 > 
 > thanks a lot for the code and your support. In fact, it's me who would need
 > multivariate resultants, and the application is as follows:
 > 
 > Suppose you have the first few numbers of a sequence and you want to guess a
 > closed formula, what can you do?
 > 
 > Well, if you know for some reason, that the sequence is 
 > 
 > r(1), r(2), r(3),... 
 > 
 > for some rational function r(n) you are lucky, just use rational
 > interpolation and you're done. Conversely, you can simply use rational
 > interpolation on the numbers you have, and if the formula you get is of low
 > total degree, i.e., deg numerator + deg denominator < number of numbers you
 > supplied, you can bet that the formula is "correct".
 > 
 > The next step is to realise that you can guess formulas of the form
 > 
 > prod_{i_0=0}^n prod_{i_1=0}^{i_0} ... prod_{i_k=0}^{i_{k-1}} r(i_k) 
 > 
 > just as easily: Simply generate the sequence of successive quotients of your
 > original sequence and recurse. This procedure is implemented in Christian
 > Krattenthaler's program rate.m and used by Sloanes Online Encylopedia, for
 > example.
 > 
 > A slight twist, which I "discovered" recently, is that you can also generate
 > the sequence of successive differences and thus guess formulas of the form
 > 
 > sum_{i_0=0}^n prod_{i_1=0}^{i_0} ... sum_{i_k=0}^{i_{k-1}} r(i_k) 
 > 
 > with sum's and prod's appearing. So far, so good.
 > 
 > Now, what happens if the sequence does not stem from a rational function,
 > but from a rational function times an "Abelian"-type term, like
 > (a+b*n)^n*r(n), r(n) being rational, a and b some numbers?
 > 
 > Well, the solution is not so difficult: let's call the numbers you've got
 > y1, y2, y3, ... y_(k+3). (i.e., we have the first k+3 terms available)
 > 
 > Do rational interpolation on the sequence
 > 
 > y1*(a+b)^-1, y2*(a+2*b)^-2, y3*(a+3*b)^-3, ... y_k*(a+k*b)^-k
 > 
 > and so on, where you keep a and b symbolic. What you get is a rational
 > function p(n,a,b) in n, a and b.
 > 
 > To recover a and b, and test whether the solution is sound, we defined the
 > three polynomials in a and b
 > 
 > p1=numer(y_(k+1)*(a+(k+1)*b)^(-k-1)-p(k+1,a,b))
 > p2=numer(y_(k+2)*(a+(k+2)*b)^(-k-2)-p(k+2,a,b))
 > p3=numer(y_(k+3)*(a+(k+3)*b)^(-k-3)-p(k+3,a,b))
 > 
 > and check whether they have a common root (a0,b0).
 > 
 > If these three polynomials have a common root, it is most likely, that the
 > sequence was generated by p(n,a0,b0).
 > 
 > We have to be a little more careful, however: There may be the unwanted
 > solution (a0,b0)=(0,0) which we would have to exclude, but I have not
 > thought about this yet.
 > 
 > What I did up to now was the following: Take the resultant of p1 and p2 and
 > p1 and p3 and then the gcd of the two resultants. However, this was far to
 > slow, of course...
 > 
 > By the way, if you have a way of solving four equations in three unknows, we
 > could even guess formulas of the form
 > 
 > (a+b*n+c*n^2)^n*r(n)...
 > 
 > You might wonder, what for? Well, such sequences do arise frequently in
 > combinatorics and it's not so trivial to guess them by hand. For example,
 > the number of alternating sign matrices is
 > 
 > (6) -> guess([1, 2, 7, 42, 429, 7436, 218348, 10850216],2,2)$G
 > 
 >                               p  - 1      2
 >                      n - 1     8      27p   + 54p  + 24
 >                      ++-++    ++-++      7       7
 >    (6)  [[function= ( | |   2( | |    -----------------)),order= 0]]
 >                       | |      | |        2
 >                      p = 1    p = 1   16p   + 32p  + 12
 >                       8        7         7       7
 >               Type: List Record(function: Expression Integer,order: Integer)
 > 
 > 
 > Thanks again,
 > 
 > Martin