How to convert the return values of guessRat$GuessInteger to Fraction(Polynomial(Integer))?

[Neven Sajko]

Suppose I have code like this:

l := [44, 178, 412, 746, 1168, 1669, 2260, 2941, 3712, 4573, 5524, 6565]
guess(l).1

Replacing the "guess" with a "guessRat" is essentially the same thing AFAIU.

The above code returns a value of type Expression(Integer) that
represents (visually, at least) a recurrence relation. The recurrence
relation obviously defines a rational function, which means the
operation was technically a success.

The problem is that if I try to convert the Expression to an actual
rational function in a naive manner, as illustrated in the following,
the conversion fails:

guess(l).1::Fraction(Polynomial(Integer))

So, how difficult would it be to accomplish what I want, either by
improving the Guess package or by writing my own code? Note that I am
able to do the conversion in my head, what I'm asking about is how to
do it in Fricas, mechanically.

My motivation for this is that I want to do iterative guessing, i.e.
guess (using GuessInteger) a rational function for each member of a
List(List(Integer)), and then use GuessPolynomialInteger on the list
of rational functions.

Thanks,
Neven

[Neven Sajko]

After reading up on Kernels and Expressions, I feel like it should be
possible to take apart the Expression(Integer) that represents the
recurrence. But it seems that is not possible in that particular case.
Suppose I have the result of some invocation of guess$GuessInteger in
a variable called g. None of these seem to be useful at all, that is I
don't see how to extract the polynomials:

kernels(g.1)
operator(mainKernel(g.1))
argument(mainKernel(g.1))

From the above I can tell that there's only a single Kernel in the
Expression, and that the Kernel has an operator and two arguments, but
I don't see what to do with them.

Any help?

Thanks,
Neven

[Ralf Hemmecke]

Hi Neven,

> Suppose I have code like this:
>
> l := [44, 178, 412, 746, 1168, 1669, 2260, 2941, 3712, 4573, 5524, 6565]
> guess(l).1
>
> Replacing the "guess" with a "guessRat" is essentially the same thing AFAIU.
>
> The above code returns a value of type Expression(Integer) that
> represents (visually, at least) a recurrence relation. The recurrence
> relation obviously defines a rational function, which means the
> operation was technically a success.
>
> The problem is that if I try to convert the Expression to an actual
> rational function in a naive manner, as illustrated in the following,
> the conversion fails:
>
> guess(l).1::Fraction(Polynomial(Integer))

Welcome. ;-) To tell the truth, when I tried to use the guessing package
for the first time, I ran into the same problem. The user interface is
not very intuitive. One has to be familiar with the Expression domain to
turn the result in something useful for further computation.

But more importantly, one must look up the code of guess, guessRat and
guessHPaux

https://github.com/fricas/fricas/blob/master/src/algebra/mantepse.spad#L3381

in order to learn what the actual structure of the result is.
Then you find that there is RecurrenceOperator. So do it this way:

l := [44, 178, 412, 746, 1168, 1669, 2260, 2941, 3712, 4573, 5524, 6565]

Z ==> Integer
E ==> Expression Z
K ==> Kernel E
ROZE ==> RecurrenceOperator(Z, E)
e1 := guess(l).1
e2 := getEq(e1)$ROZE
k2 := mainKernel(e2)::K

How to continue to actually get the other parts out of the result, is
probably a matter of taking things apart with "Expression(Integer)"
means, probably, isPlus and isTimes, etc.

I definitely agree that this must be improved. Definitely there should
be better documentation of how to take apart the result. Finding that
RecurrenceOperator is the key, is unnecessarily hard and involves
looking into the .spad files.

Can you file a bug report at github?

Thanks
Ralf

[Ralf Hemmecke]

Neve,

to save you some time... see attachement.

BTW, look at the first 4 values in the result below.
Unfortunately, I do not see how one can extract from the result from
which point on it is valid. In fact, I find it a bit strange that it
doesn't agree at the beginning, but seemingly Martin Rubey and Waldek
Hebisch had their reasons or I do not understand why for f(0),...,f(3)
we just get 0*f(n)+0 = 0 from the guessing result.

Ralf

(1) -> l := [44, 178, 412, 746, 1168, 1669, 2260, 2941, 3712, 4573,
5524, 6565]

(1) [44, 178, 412, 746, 1168, 1669, 2260, 2941, 3712, 4573, 5524, 6565]
Type:
List(PositiveInteger)
(2) -> Z ==> Integer
Type:
Void
(3) -> E ==> Expression Z
Type:
Void
(4) -> K ==> Kernel E
Type:
Void
(5) -> P ==> Polynomial Z
Type:
Void
(6) -> e1 := guess(l).1

(6)
[
f(n):
4 3 2 6 5 4 3
(- n + 6 n - 11 n + 6 n)f(n) + 45 n - 174 n - 17 n + 402 n
+
2
128 n - 384 n
=
0
]
Type:
Expression(Integer)
(7) -> e2 := getEq(e1)$RecurrenceOperator(Z, E)

(7)
4 3 2 6 5 4 3
2
(- n + 6 n - 11 n + 6 n)f(n) + 45 n - 174 n - 17 n + 402 n +
128 n
+
- 384 n
Type:
Expression(Integer)
(8) -> k2 := mainKernel(e2)::K

(8) f(n)
Type:
Kernel(Expression(Integer))
(9) -> e3 := k2::E

(9) f(n)
Type:
Expression(Integer)
(10) -> e4 := eval(e2,e3,0)

6 5 4 3 2
(10) 45 n - 174 n - 17 n + 402 n + 128 n - 384 n
Type:
Expression(Integer)
(11) -> pol1 := e4::P

6 5 4 3 2
(11) 45 n - 174 n - 17 n + 402 n + 128 n - 384 n
Type:
Polynomial(Integer)
(12) -> e5 := (e2-e4)/e3

4 3 2
(12) - n + 6 n - 11 n + 6 n
Type:
Expression(Integer)
(13) -> pol2 := e5::P

4 3 2
(13) - n + 6 n - 11 n + 6 n
Type:
Polynomial(Integer)
(14) -> factor pol1

2
(14) (n - 3)(n - 2)(n - 1)n(45 n + 96 n + 64)
Type:
Factored(Polynomial(Integer))
(15) -> factor pol2

(15) - (n - 3)(n - 2)(n - 1)n
Type:
Factored(Polynomial(Integer))
(16) -> rat:=-pol1/pol2

2
(16) 45 n + 96 n + 64
Type:
Fraction(Polynomial(Integer))
(17) -> [eval(rat,n=i) for i in 0..12]

(17)
[64, 205, 436, 757, 1168, 1669, 2260, 2941, 3712, 4573, 5524, 6565, 7696]
Type:
List(Fraction(Polynomial(Integer)))

[Neven Sajko]

Thank you, you're very kind. Both for showing me how to get the
rational function (or polynomial, in this case) from the Expression,
and for pointing out the pitfall with the sequence prefix.