Karim Belabas on Sun, 15 May 2016 10:53:49 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: periodic generating function |
* 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] `