Re: periodic generating function

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* Kevin Ryde [2016-05-15 09:18]:
> To notice a periodic part in a generating function I think I want to
> find whether a denominator polynomial is a divisor of 1 - C*x^p, for
> some constant C and some power p.  What would be a good way to do that?
> 
> I got the effect I wanted by working upwards determining successive
> terms of quotient until only a high term (or stop if too long).
> Coefficients might be complex or quad and I'm happy for C to be
> likewise.

A partial answer:

Input : a t_POL T with complex coefficients
Output: (C,p) such that T (probably) divides C - x^p; or FAIL

0) If T is not squarefree, FAIL.
1) Approximate the complex roots of T to a huge accuracy: should all be of the
   form z = C^(1/p)*exp(j(z)*2iPi/p) for some integer j(z),
   with "C^(1/p)" := exp(Log(C)/p), principal branch.
2) Given two roots (z1,z2), if |z1/z2| is not close to 1, FAIL;
   else find smallest p(z1,z2) such that z1/z2 is (very close to) 1 by
   successive multiplication ( or guess via bestappr( log(z1/z2)/2*I*Pi ) )
   Do that for all pairs of roots and let p be the lcm of the p(z1,z2).

3) Raise all complex roots to power p and check whether they are all
   (approximately) equal. If so we are done.

   At this point you may be unlucky and all j(z) belong to a fixed
   congruence class Mod(A,B) so you may want to raise the roots to
   higher powers 2*p, 3*p, etc., checking whether all entries become
   approximately equal until you hit this potential B*p. I see no way to
   rule out arbitrarily large p without further information.

(I guess that your input is exact and that you can check whether any
tentative value is actually correct.)

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite de Bordeaux         Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
`