----------------------------------------------------------------------------- | List of user-visible changes for the q-Zeilberger package since version 1.4 | ----------------------------------------------------------------------------- Version 2.3x ************ - New function MakeHomRec[]. Calling MakeHomRec[rec] where rec is a recurrence or a list of recurrences returned by qZeil, transforms inhomogeneous recurrences into homogeneous ones. Version 2.2x (finished 04-11-02) ************ - If the order is of the form {ord1, ord2}, qZeil tries to find a recurrence whose order is between ord1 and ord2. Omitting the order is equivalent to specifying {0, Infinity}. - New option NumericCheck for qZeil and qTelescope. With NumericCehck -> True, qZeil and qTelescope check numerically (and therefore fast) whether the underlying system of equations might have a solution. Version 2.1x (finished 12-31-01) ************ - New option qParameterized for qTelescope. With qParameterized -> {rat0, rat1, ... }, qTelescope computes coefficients a0, a1, ..., and a closed form for the sum of a0 f0 + a1 f1 + ... , where fi equals rati multiplied with the input summand. Here the rati are rational functions in q^k and the ai are constants. Note that qParameterized cannot be combined with PolyMult. - If Output is set to True, then intermediate results are written to a notebook and no longer to the file 'GoOut'. - qfac has been renamed to qPochhammer. The old name still works for backward compatibility. Version 2.0 (finished 05-03-01) *********** - No user-visible changes. Version 1.9 (finished 10-05-00) *********** - The source code is now distributed as one single file "qZeil.m". Note that this file is encoded. This means it is not readable but can be treated like any normal Mathematica file. - The default value for Output has been changed to False. - The option EquationSolver now allows to specify any nullspace algorithm that takes as argument a matrix and returns a basis for its nullspace. - To compute the certificate of the last computation, the user has to call Cert[] instead of Cert. - The function Check1[] has been superseded by CheckRec[]. Calling CheckRec[rec, f] where rec is a recurrence or a list of recurrences returned by qZeil, checks whether f satisfies rec. Version 1.8 (finished 12-13-99) *********** - The whole package has been adapted for Mathematica 3.0. The collection of examples (qZeilExamples.txt) is now distributed as a MMA notebook (called qZeilExamples.nb). - The pivot search in Erhard Aichinger's ENullSpace has been completely rewritten resulting in an overall speedup factor between 1 and 20. Several out-of-memory examples can be done now. - Pulling out constant factors in the coefficients of the Sigma[.] results in a VERY dramatic speedup for many applications. With this improvement the collection of examples could be extended significantly. - The boolean variable Simp for turning on/off simplification is no longer supported. - SameRec[rec1, rec2] checks whether the recurrences rec1 and rec2 are equal. This is useful for transformation formulas with several pages of output, since SameQ does not necessarily give True for equal recurrences and Together[ rec1[[2]] - rec2[[2]] ] can be very time-consuming. - Option FindAlpha has been superseded by FindAlphaBeta. For a description see changes in version 1.5 below. - New option EquationSolver for qZeil and qTelescope. With EquationSolver -> NullSpace, qZeil and qTelescope use the built in function NullSpace for computing the null space of the corresponding matrix in LinSolve. Default value for EquationSolver is Automatic, which invokes the null space algorithm provided with the qZeil package. Note that for users at RISC, EquationSolver -> CNullSpace invokes an improved version of Erhard Aichinger's CNullSpace, a null space algorithm implemented in C requiring SACLIB. For this, one has to read in < {int1, int2}, qZeil computes extended *homogeneous* recurrences of the form Sigma[0] SUMX[n,P] + Sigma[1] SUMX[n-1,P] + ... + Sigma[ord] SUMX[n-ord,P] = 0, where SUMX[n-j,P] := Sum[F(n-j,k) * P(k), k] for a polynomial P(k) of maximal degree int1 and not depending on q^n. int2 is an upper bound for the degree of the Sigma[j] w.r.t. q^n. Note that this option implicitly changes the summation range to the set of all integers (you will get a warning about this), so no inhomogeneous recurrences can be dealt with. Remark: This is a non-linear problem which seems to be rather impossible for Mathematica even for small examples. Thus, the system of equations is solved very efficiently with Maple. For this, the global variable MapleCall has to be assigned a string specifying the command to invoke Maple (the command line version) redirecting the input from the file "MapleIn", for instance, under Windows 95 MapleCall = "cmaple -q < True, qZeil only computes Sum[Sigma[i] F(n-i,k), {i, 0, order}] in the form F(n,k) Sum[Sigma[i] F(n-i,k) / F(n,k), {i, 0, order}] as a rational function multiple of F(n,k) with undetermined Sigma[i]. This feature, for instance, allows to perform and check all steps of the qWZ- method "by hand": Call qZeil with order 1 and OnlySummand -> True, replace Sigma[0] and Sigma[1] by 1 and -1, resp., and finally run qTelescope on the output (note that this might cause problems if the rational function is "large", because factorization in qTelescope fails then). - New option MagicFactor applying Paule's method of creative symmetrizing for decreasing the order of the recurrence in qZeil. Let f = f(k) denote a non-constant linear integer function of k with the property that Sum[F(n,k), {k, low, upp}] = Sum[F(n,f(k)), {k, low, upp}]. Typical examples for f are -k, -k-1, -k+1, n-k, 2n-k, etc. Then we have Sum[F(n,k), k] = (Sum[F(n,k), k] + Sum[F(n,f(k)), k]) / 2 = Sum[F(n,k) (1 + F(n,f(k)) / F(n,k)) / 2, k] =: Sum[F(n,k) MF(n,k), k] for some function MF(n,k) in q^n and q^k. Now, if MF(n,k) satisfies the input restrictions for qZeil or qTelescope, option MagicFactor -> f automatically multiplies the summand with this magic factor MF. See the example notebook for various applications. - In qTelescope all parameters of the form q^par[i], for integer parameters par[i] appearing only linearly, are (temporarily) replaced by subs[i]. This results in dramatic speedup for examples involving parameters of this type, as for instance Rahman, Verma [1993, (3.*)]. - Dualization now also works correctly if, for instance, qfac[q, q, k] is given as (1 - q) * qfac[q^2, q, k-1], etc., thanks to a new rewrite rule for such terms. - The pole checking feature now also works with qZeil if the summation bounds are explicitly given. Thus, the output of qZeil has changed in the same way as described for qTelescope 1.5 below. Version 1.6 (finished 11-18-96) *********** - After a dual pair {F'(n,k), G'(n,k)} has been computed by the program, calling DualId[{k, low, upp}, n] evaluates SUM' := Sum[F', {k, low, upp}] provided that SUM' is constant, i.e., not depending on n. DualId uses the value of the (global) variable DualPair. Note that all elements c_i of intconst (beside n) are now automatically replaced by -c_i - 1 to preserve their non-negativity under shadowing. - The computation of companion identities has been improved. In particular, the computation of Limit[F(n,k), n->Infinity] no longer fails in so many instances where the limit actually exists and is finite. As with dual identities, this improvement is due to the application of several transformation rules to the summand. Moreover, the notation (k >= 0) has been changed to the corresponding Mathematica expression If[k >= 0, 1, 0]. Plugging in concrete values for k in CompId now makes sense giving 1 or 0 instead of True or False. - Simplification of q-hypergeometric expressions has been corrected and improved. In particular, poles found by qTelescope may influence certain non-negativity conditions of integer parameters, which is of fundamental importance for 0-recognition. Example: Assume that n is an element of intconst, i.e., n is a non- negative integer. If there is a pole for n = 0, we may conclude that n >= 1. Thus, for instance, qfac[q^(1-n),q,n] = 0 for all n. A very nice application of this feature is a special case of Gasper and Rahman [1990b, (II.27)], which no longer needs the transformation n->n+4. Note that in case of more than ONE solution, the new conditions are applied to all solutions which might be incorrect. Furthermore, simplification now also works for terms of the form a + b, a == b, and Sum[a, ...]. Thus, special cases of dual identities etc. can be simplified easily by applying qSimplify. By adding some additional rules for cancelling qfac's, simplification has become slightly slower but much more powerful. Version 1.5 (finished 08-10-96) *********** - ToqHyper[rec] converts the recurrence rec into valid input for Petkovsek's qHyper in terms of SUM[N] := SUM[q^n] where n is the recurrence variable. - Options are now supported for qZeil and qTelescope. New syntax: qZeil[F, {k, low, upp}, n, ord, , , ..., ] qTelescope[F, {k, low, upp}, , , ..., ] where the opt_i are options from the following list: FindAlphaBeta with FindAlphaBeta -> True, qZeil and qTelescope make suggestions for all possible choices of alpha and beta such that there possibly exists a solution for F * q^(alpha Binomial[k,2] + beta k). The result should be interpreted in the following way: For all integers NOT being alpha-beta-candidates there actually does not exist a solution. However, not all candidates necessarily yield a solution. Note that there are always only finitely many alpha-candidates, but sometimes it is not possible to find any restriction on beta (actually many --- I conjecture ALL --- identities find a solution for either no beta or infinitely many beta's). Remark: In qZeil version 1.5 this option was originally called FindAlpha only working for alpha-candidates. The change to FindAlphaBeta was actually done in version 1.8. PolyMult with PolyMult -> int (int a non-negative integer), qTelescope computes all polynomial multipliers of maximal degree int which make the input *Gosper* summable. Default value for int is 0. Shadow with Shadow -> rat (rat a rational number), the default shadowing strategy for computing dual identities in qZeil is changed as following: The shadowing rule is applied to all qfac-terms except qfac[q, q, a n + b k + c] for which a + rat b = 0 but not a = 0 = b. Default value for rat is 1 (as suggested by Wilf and Zeilberger). Example: If the summand contains the factor qfac[q^(-2n),q,k], it turns out that qZeil should be called with Shadow -> 2 (otherwise the dual qWZ-pair is not well-defined). More details about the theoretic background behind this strategy can be found in my PhD Thesis. - The computation of dual identities has been corrected and improved. The shadowing rule for qfac[A, q, a n + b k + c] only holds if A is free of n and k. Thus, transformation rules are applied to achieve this form. - Finding poles of the solution function(s) in qTelescope now works correctly if there is more than one solution (cf. option PolyMult). As a consequence, the output of qTelescope has changed to { {Sum[F_1, {k, low, upp}] == cf_1, polelist_1}, {Sum[F_2, {k, low, upp}] == cf_2, polelist_2}, ... , {Sum[F_m, {k, low, upp}] == cf_m, polelist_m} }. If m = 1 or polelist_i = {} for some 1 <= i <= m, then some of the nested lists are flattened out. ------------ | Known bugs | ------------ - If the summand F(n,k) for qZeil is not well-defined for all non-negative integers n and all integers k from the summation range, or actually needs some sophisticated limit considerations, evaluation might fail. The same holds true for the summand F(k) for qTelescope. - The q-binomial coefficient qBinomial[a, b, q] might cause problems if a is negative. ------------------ | qZeil on the Web | ------------------ The qZeil homepage is located at http://www.risc.uni-linz.ac.at/research/combinat/risc/software/qZeil/ To get the password send an email to me. The password will be given for free to all researchers and non-commercial users. ======================================================================= Axel Riese Research Institute for Symbolic Computation J. Kepler University Linz Tel: +43 (0)732 2468 9966 Altenbergerstrasse 69 Fax: +43 (0)732 2468 9930 A-4040 Linz mailto:Axel.Riese@risc.uni-linz.ac.at Austria https://risc.jku.at/m/axel-riese/ =======================================================================