guessRec for algebraic numbers

[Ralf Hemmecke]

Hi Martin, hi Waldek,

I just stumpled over the behaviour below.
The result is not wrong in the case of algebraic numbers, but I wonder
why the resulting recurrence is not "normalized" in some way.

OK, one cannot simply take out the "gcd" of the coefficients, because
that wouldn´t work for AN without recognizing that the numbers in the
recurrence are actually integers.

Can you explain your design decision or is it just an oversight and
there is room for improvement?

Ralf


%%% (1) -> cq := [(1/2)^k for k in 0..20]

(1)
1 1 1 1 1 1 1 1 1 1 1 1 1 1
[1, -, -, -, --, --, --, ---, ---, ---, ----, ----, ----, ----, -----,
2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384
1 1 1 1 1 1
-----, -----, ------, ------, ------, -------]
32768 65536 131072 262144 524288 1048576
Type:
List(Fraction(Integer))
%%% (2) -> sq := guessRec(cq, functionName=='co).1

(2) [co(n): - 2 co(n + 1) + co(n) = 0, co(0) = 1]
Type:
Expression(Integer)
%%% (3) -> ca := [((1/2)::AN)^k for k in 0..20]

(3)
1 1 1 1 1 1 1 1 1 1 1 1 1 1
[1, -, -, -, --, --, --, ---, ---, ---, ----, ----, ----, ----, -----,
2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384
1 1 1 1 1 1
-----, -----, ------, ------, ------, -------]
32768 65536 131072 262144 524288 1048576
Type:
List(AlgebraicNumber)
%%% (4) -> sa := guessRec(ca, functionName=='co).1

(4)
[
co(n):
- 738578176637708424660750 co(n + 1) + 369289088318854212330375
co(n) = 0
,
co(0) = 1]
Type:
Expression(Integer)

[Waldek Hebisch]

In case of algebraic numbers we use fraction-free solver which works
over quite gerneal rings but due to this can not remove common
factors. In case of algebraic numbers one can try to remove
integer common divisor. I think that this is not done mainly due
to structure of the solver. Namely over integers solver removes
common divisors already during solving. But general solver can
not do this in general, it would need special case for algebraic
numbers to do this. In your example solver could cheat, that
is recognize that all numbers are rational and hand work to
integer solver. But such case is probably quite rare in normal
use and when testing there is advantage in passing such problems
to general solver.

--
Waldek Hebisch

[Ralf Hemmecke]

On 11/8/24 12:54, Waldek Hebisch wrote:
> In your example solver could cheat, that is recognize that all
> numbers are rational and hand work to integer solver. But such case
> is probably quite rare in normal use and when testing there is
> advantage in passing such problems to general solver.

Yes, probably, my example is in a zero-set. I was not suggesting to
create a special case solver, but wouldn't it make sense to add some
post-processing to show a nicer result. That should be cheap for
constant-coefficient linear recurrences.

Ralf

[Waldek Hebisch]

My point is that recurrence-finding part is generic, it works over
quite general rings. Any simplification to "show a nicer result"
must depend on a special structure, so we will need a special case
simplifier. For algebraic numbers and for Expression(Integer) there
is an easy trick: treat than as rational functions (or plynomials) in
kernels and compute common divisors over integers. But you can easily
invent a type for which it will not work. So problem is where to
stop. For example currently factoring code has a special cases
for several common and not so common cases and there is
PolynomialFactorizationExplicit to handle "general" case. But
it is not clear to me if adding many special simplifications to
guessing is very useful (Expression(Integer) and AlgebraicNumber
are probably worth doing).

--
Waldek Hebisch