IMFM Institute of Mathematics, Physics and Mechanics JADRANSKA 19, 1000 LJUBLJANA, SLOVENIA Preprint series Vol. 48 (2010), 1112 ISSN 2232-2094 POLYNOMIAL RING AUTOMORPHISMS, RATIONAL (w, a)-CANONICAL FORMS, AND THE ASSIGNMENT PROBLEM S. A. Abramov H. Q. Le M. Petkovsek Ljubljana, January 20, 2010 Polynomial Ring Automorphisms, Rational (w, a)-Canonical Forms, CD and the Assignment Problem § O CD m u a CD U S. A. Abramov* Russian Academy of Sciences Dorodnicyn Computing Centre Vavilova 40, 119991, Moscow GSP-1, Russia sabramov@ccas.ru H. Q. Le Department of Mathematics Simon Eraser University Burnaby, British Columbia, V5A 1S6, Canada hle@cecm.sfu.ca M. Petkovsek Faculty of Mathematics and Physics University of Ljubljana Jadranska 19, SI-1000 Ljubljana, Slovenia CO marko.petkovsek@fmf.uni-lj.si We investigate representations of a rational function R e k(x) where k is a field of characteristic zero, in the form R = K ■ aS/S. Here K,S e k(x), and a is an automorphism of k(x) which maps k[x] onto k[x]. We show that the degrees of the numerator and denominator of K are simultaneously minimized iff K = r/s where r,s e k[x] and r is coprime with ans for all n e Z. Assuming existence of algorithms for computing orbital decompositions of R e k(x) and semi-periods of irreducible p e k[x] \ k, we present an algorithm for minimizing w(deg num(S), deg den(S)) among representations with minimal K, where w is any appropriate weight function. This algorithm is based on a reduction to the well-known assignment problem of combinatorial optimization. CD We show how to use these representations of rational functions to obtain succinct representations of a-hypergeometric terms. Abstract * Partially supported by RFBR grant 04-01-00757. tPartially supported by ARRS grant P1-0294. o o CSI 00 CSI CSI CO 1 Introduction Let k be a field of characteristic zero, and let x be transcendental over k. Denote by £ the unique k-automorphism1 of k(x) which satisfies £x = x +1 (the shift operator). If q G k*, denote by Q the unique k-automorphism of k(x) which satisfies Qx = qx (the q-shift operator). Representations of a rational function R G k(x) in the form c R = K • f (1) d 2 where a is either the shift or the q-shift operator, and K is a-reduced 2, play a significant role in various computer algebra algorithms for symbolic summation and solution of difference equations (see, e.g., (Gosper, 1978); (Zeilberger, 1991); (Petkovsek, 1992); (Pirastu and Strehl, 1995); (van der Put and Singer, 1997, Section 2.1); (Abramov and Petkovsek, 2002)). We call such a pair (K, S) a rational a-normal form (RNFCT) of R, with kernel K and shell S. For the case a = £, it is shown in (Abramov and Petkovsek, 2001, Cor. 1) that the degrees of the numerator and denominator of K in (1) are simultaneously minimized iff K is a-reduced. Once K has been minimized, it is also desirable to minimize S. Not surprisingly, the degrees of the numerator and denominator of S cannot, in general, be minimized simultaneously, and there is a choice of minimization criteria. In a preliminary version (Abramov, Le and Petkovsek, 2003), we used four such criteria, and called the corresponding rational normal forms (which are unique if S is monic), rational canonical forms. In this paper, we generalize the theory and algorithms for computing rational normal and canonical forms in two directions. First, we allow a to be any automorphism of k(x) which maps k[x] onto k[x]. In particular, we do not require that ConstCT(k(x)) = ConstCT (k); instead, we assume that orbital decompositions3 of rational functions in k(x) and semi-periods1 of irreducible polynomials in k[x] \ k can be computed. Second, we show how to minimize w(degnum(S), degden(S)) for any weight function w, by which we mean a monomorphism of the partially ordered Abelian group Z x Z into some computable linearly ordered Abelian group L. Typically, L = Z x Z ordered lexicographically. For example, if w(n, d) = (n + d, d) then we minimize degnum(S) + degden(S), and in case of ties take the form with the least deg den(S). The overview of the paper is as follows: After describing our algebraic framework and notation in Section 2, we define rational a-normal forms and state some of their basic properties in Section 3. In Section 4 we show how to use orbital decompositions with respect to a to reduce problems about RNFCT's of general rational functions to corresponding problems about p-orbital rational CO functions for an irreducible polynomial p. We give a constructive proof of existence of strict RNFct's in Section 5, and in Section 6 we show that the degrees 1see Section 2 for definitions 2see Definition 1 in Section 3 3see Definition 3 in Section 4 u a CD U of the numerator and denominator of K in (1) are simultaneously minimized iff (K, S) is an RNECT of R. The core of the paper consists of Sections 7 and 8 where we define rational (w, a)-canonical forms (RCEw a's), and show how to compute them. After presenting our algorithmic prerequisites in Section 8.1, we reduce in Section 8.2 computation of RCEWjCT's to the assignment problem, a well-known combinatorial optimization problem with efficient algorithms to solve it (cf. (Papadimitriou and Steiglitz, 1982)). Two cases need to be distinguished in constructing this reduction, corresponding to p being non-periodic4 or semi-periodic4 w.r.t. a. They are treated in Sections 8.3 and 8.4, respectively. In Section 9 we show that the rational (w, a)-canonical form of R G k(x) is unique provided that each irreducible factor of R is non-periodic w.r.t. a. In Section 10, we present an application of rational canonical forms to the problem of obtaining succinct multiplicative representations of hypergeometric terms. Such representations are useful in simplification of hypergeometric terms and in investigation of their asymptotics. In this section we require that a is a k-automorphism, and denote by n the value of anx G k[x] at x =1. In particular, if a = £ then n = n + 1; if a = Q then n = qn. We call a sequence t = (tn)n>0 of elements of k a a-hypergeometric term if tn = 0 for n large enough, and there are coprime polynomials p, q G k[x] \ {0} such that o I CSI 00 m CD p(n)tn+i = q(n)tn for all n > 0. If there are F, G G k(x) such that tn = G(n)\\ "=0 F (i) for all n, we call (F, G) a multiplicative decomposition of t. We show that if t0 = 0, and (K, S) is an RNECT of F • aG/G such that S(1) G k*, then (K, S • G(1)/S(1)) is a multiplicative decomposition of t with minimal degrees of the numerator and denominator of its first component. Furthermore, if (K,S) is the RCEw,CT of F • aG/G, then, in addition, the weight w of its second component is minimal among all such decompositions. C^ 2 Preliminaries CO We denote the set {1, 2,..., n} by [n]. In particular, [0] = 0. Throughout the paper, k is a field of characteristic zero, x is transcendental over k, and a is a fixed automorphism of the polynomial ring k[x]. From a(k[x]*) = k[x]* and k[x]* = k* it follows that a(k) = k, hence a restricted to k is an automorphism of k. This implies that deg ap = deg p • deg ax for every p G k[x], and so deg ax = 1 or else a would not be surjective. Hence ax = ax + b for some a G k* and b G k. It follows that a preserves degrees of polynomials, and maps irreducibles to irreducibles. The unique automorphism of the rational-function field k(x) which extends a will be denoted by a as well. For p, q G k[x] \ {0}, it is defined by a(p • q-1) = (ap) • (aq)_1. Note that (k(x), a, 0) is a unimonomial extension of (k, a, 0) in the sense of (Bronstein, 2000). An automorphism a of k[x] or k(x) is a k-automorphism if aA = A for all A G k. Eor u CD _ 4see Section 2 for definitions u a CD U any field F and automorphism a of F we write ConstCT (F) := (A G F; a A = A} for the constant field of F. For p, q G k[x], we write p ± q iff deggcd(p, q) = 0. Clearly p ± q iff ap ± aq. The leading coefficient of p G k[x] is denoted by lc (p). For u, v G k(x), we write u ~ v iff u = Av for some A G k*. For u G k(x), its numerator num(u) and denominator den(u) are uniquely determined by requiring that num(u) G k[x], den(u) G k[x] \ (0}, u = num(u)/den(u), num(u) ± den(u), and lc (den(u)) = 1. Obviously num(au) ~ a num(u) and den(au) ~ a den(u). We define lc (u) := lc (num(u)), and call u monic if lc (u) = 1. Similarly as in (Abramov and Bronstein, 2002), we denote the n-th rising a-factorial of an element u G k(x)* by n-1 n ua'n = ^ aiu, ua'-n = n a-iu-1 i=0 i=1 1—1 for all n G Z, n > 0, where an empty product equals 1. It is straightforward to see that for all n, m G Z and u, v G k(x)*, n ua'n+m = ua'n • an(uCT'm), ua'nm = (ua'n)a ,m , /au \ a,n anu (uv)ff'n = ua'nva'n, (au)CT'n = a (uff'n), (— J = -. V u / u If p G k[x] \ k is irreducible and n is a positive integer, then anp is irreducible and deg anp = degp, so either anp ±p or anp ~ p. The semi-period n(p) of p is defined by _( ) f 0, if anp±p for all n > 1, n(p) := min(n > 1; anp ~ p}, otherwise. CN We call p non-periodic if n(p) = 0, and semi-periodic if n(p) > 0. We denote t(p) := M(p) := an(p)p/p, (2) CO and call t(p) the total span of p. HH Proposition 1 Let p G k[x] \ k be irreducible. Then (i) if p is non-periodic then t(p) = 1, (ii) at(p) = ^(p)t(p) and at(p) ~ t(p). CO CD $H CD CO $H a CD Jh We omit the easy proof. Let Gi and G2 be two partially ordered Abelian groups. A monomorphism of Gi into G2 is an injective mapping h : G1 ^ G2 such that h(a + b) = h(a) + h(b) and a < b h(a) < h(b) for all a, b G G1. 3 Rational a-normal forms Definition 1 An element R G k(x) is a-reduced if num(R) ± anden(R) for all n G Z. Definition 2 Let R G k(x). If K G k(x) and S G k(x)* are such that g (i) r = k.£ £ (ii) K is a-reduced, then (K, S) is a rational a-normal form (RNFCT) of R. The set of all RNFCT's of R is denoted by RNFff (R). We call K the kernel and S the shell of (K, S). If, in addition, i—l (iii) num(K) ± num(S) ■ den(aS) and den(K) ± den(S) ■ num(aS), then (K, S) is a strict RNFCT of R. The set of all strict RNFCT's of R is denoted by sRNFff (R). Example 1 In our examples, a is a k-automorphism of k(x) unless explicitly stated otherwise. We specify it by giving a G k* and b G k such that ax = ax+b. Let 3 ^ R(x) = _x_ v 7 (x - 1)(x - 2)(x - 3)' I CO CO u CD C0 Jh a CD U 1. If ax = 2x then (R, 1) G sRNFff(R). 2. If ax = x + 1 then (1, (x - 1)3(x - 2)2(x - 3)) G sRNFff(R). CO 3. If ax =1 - x then (-x2/((x - 2)(x - 3)), 1 - x) G sRNFff(R). Lemma 1 Let (K, S) be an RNFff of R G k(x)*. Then (K-1,S-1) is an RNFa of R-1. If (K, S) is strict then so is (K-1,S-1). Proof: As a preserves degrees, K G k(x)* is a-reduced iff K 1 is a-reduced. □ Lemma 2 Let R G k(x). If (K, S) G sRNFCT(R) then num(K) | num(R) and den(K) | den(R). Proof: As num(R)den(K)num(S)den(aS) = den(R)num(K)den(S)num(aS) and num(K) ± den(K) num(S) den(aS), it follows that num(K) | num(R). From den(K) ± num(K) den(S) num(aS) it follows that den(K) | den(R). □ From Lemma 2 it follows immediately that if (K, S) is an sRNFCT of a A G k then K G k as well. In fact, the same holds for any RNFCT of A G k. Lemma 3 Let (K, S) be an RNFff of A G k. Then K G k. o CSI Proof: If A = 0 then K = 0 G k. Now let A = 0. Write num(S) = p1p2 • • • pm, den(S) = q1q2 • • • qn where p4, qj G k[x] are irreducible. From A = K • aS/S it follows that num(K) | num(S)den(aS) and den(K) | den(S)num(aS). Let CSI o u a CD U num(K) — m Pi \ m aqj 1 , den(K) where A, C C [m] and B, D C [n]. Denote A = [m] \ A, B = [m] \ B, C = [n] \ C, d =[n] \ d. Then (nieJ4 Pi) (ru^ aq^ — (niec5 ap») (ru. qj).Since k[x] is a unique factorization domain and pi i qj, it follows that there is a bijection b : A ^ C such that pi — apb(i) for all i G A. Assume that C = 0, and pick an i G C. As K is a-reduced, A n C = 0, so i G A and b can be applied to i. If there is an infinite sequence over A of the form (i, b(i), b2(i),...} then bn(i) = bm(i) for some n > m > 0, so bn-m(i) = i G C. On the other hand, bn-m(i) G b(A) = C1. This contradiction shows that there is an r > 1 such that i, b(i),..., br-1(i) G A while br(i) G A. Then pbr(i) | num(K). From the properties of b it follows that pi ~ arpbr(i), therefore a-rpi | num(K). But this is impossible since api | den(K) and K is a-reduced. Hence the assumption was false, and C = A = 0. By Lemma 1, (K-1, S-1) is an RNFCT of A-1. Applying the above argument to (K-1,S-1) we see that B = D = 0 as well. Hence K - 1, i.e., K G k*. □ 4 Orbital decompositions i Definition 3 Let p G k[x] \ k. Following (Bronstein, 2000) we say that q G k[x] is p-orbital (with respect to a) if q — "=0 aipei for some n, ei > 0. We say that R G k(x) is p-orbital (with respect to a) if R can be written as the quotient of two p-orbital polynomials. An orbital decomposition of R G k(x) with respect to a is a factorization R = ^=1 Ri where each Ri G k(x) is pi-orbital for some irreducible pi G k[x] and pi /pj is a-reduced for all i, j G [N]. A closely related CO concept is called a-factorization in (Karr, 1981; Schneider, 2005). Lemma 4 Let n^ Ri and ^^=1 Ri be two orbital decompositions of R G k(x)* where Ri and Ri are pi-orbital. Then Ri — Ri /^or all i G [N]• Proof: This follows from (Bronstein, 2000, Lemma 17(v)). □ Lemma 5 Let p G k[x] be irreducible:. If R G k(x)* is p-orbital and (K, S) G RNFCT(R), then K is p-orbital. Proof: Let K = Hi=1 Ki and S = Hi=1 Si be orbital decompositions of K resp. 5 where Ki,Si are pi-orbital. They exist by (Bronstein, 2000, Lemma 17(i)). • 1 W.l.g. assume that p = p1. Denote K' = K/K1, S' = S/S1. Then !» k' . OS:=R . S1 S' K1aS1 u a CD U While the right-hand side is p1-orbital, the left-hand side has an orbital de- 2 composition of the form N2 Wj where Wj _ KjaSj/Sj is p-orbital for i _ 2,..., N. By Lemma 4, this is only possible if K'aS'/S' _ RS1/(K1aS1) e k Since K is a-reduced, K' is a-reduced as well, and Lemma 3 implies that K' e k*. Thus K _ K'K1 is p-orbital. □ Note that in Lemma 5, S need not be p-orbital, even if (K, S) e sRNFCT (R). Example 2 Let ax _ 2x and R(x) _ x + 1. Then ((x +1)/2n,xn) e sRNFCT(R) for all n e Z. While R(x) is (x + 1)-orbital, xn for n _ 0 is not. Corollary 1 Let R _ N1 Rj be an orbital decomposition of R e k(x)*, and JN—1 Rj be an (Kj, Sj) e RNFff(Rj) for each i e [N]. Then (ni—1 Kj, nN—1 Sj) e RNFff(R). Proof: Denote K _ nN—1 Kj,S _ nN=1 Sj. Clearly K • aS/S _ R. Suppose that K is not a-reduced. Then there are i and j such that num(Kj)/den(Kj) 1 is not a-reduced. But by Lemma 5, Kj is pj-orbital and Kj is pj-orbital, while pj/pj is a-reduced, so this is impossible. □ o £ 5 Existence of strict rational a-normal forms To prove existence of RNFCT for any R e k(x)*, by Corollary 1 it suffices to do so for p-orbital rational functions of the form o R _ A • aa;pa°2p ••• abmp, m < n, (3) ab1 pa"2p ■ ■ ■ abnp c^ p where A e k*, a1 < a2 < • • • < am and b1 < b2 < • • • < bn are nonnegative integers such that aj _ bj for all i e [m], j e [n], and p e k[x] is irreducible. When p is semi-periodic we will assume w.l.g. that aj,bj < n(p). If m > n we consider R-1 and apply Lemma 1. Existence of RNFCT for R _ 0 in a nS-field5 k(x) over a semi-computable6 constant field is proved constructively in (Schneider, 2005, Alg. 4.17). For R as in (3), this algorithm yields (K, S) e RNFCT(R) with HH m a _ 1 K _ A •pm-n, S ^^lU ^V nn= 1 nbi-1 ajp which, in general, is not strict. In order to minimize the shell S, we need to consider the sRNFCT's of R. Theorems 1 and 4 below describe strict RNFCT's of R in (3) by means of injections f : [m] ^ [n], similar to those used in (Caruso, 2003, Chapter 4) to estimate the degree of polynomials involved in the Gosper-Form of Zeilberger's algorithm. 5see (Karr, 1981), (Karr, 1985), or (Schneider, 2001) for definitions 6 Following (Schneider, 2005), a field F is semi-computable if Z C F is recognizable, there is an algorithm for factoring multivariate polynomials over F, and the orbit problem (given f, g € F*, decide if there is an n G Z such that fn = g, and if so, find one) is solvable in F. CO CO u a CD U Theorem 1 Let R be as in (3). Let f : [m] ^ [n] be an injection. Define K/ := ^-A-r~, S/ := TT / (4) / j ([m]) afejp, / M (/) W j) (f) f nf a^ aj >b/(j^ v(/) = J 1, b 1 aj >b/ , , otherwise, j | rL= 0 we distinguish three cases. 00 (a) m = n: In this case we take f = id[m]. (b) 0 < m < n and am < bn: By inductive hypothesis, there exists an increasing injection g : [m] ^ [n — 1] which satisfies |{i G [m]; bg(j) < bj }| = |{i G [m]; aj < bj}| for each j G [n — 1] \ g([m]). We define f : [m] ^ [n] by f (i) := g(i) for all i G [m]. (c) 0 < m < n and am > bn: By inductive hypothesis, there exists an increasing injection g : [m — 1] ^ [n — 1] which satisfies |{i G [m — 1]; bg(j) < bj}| = |{i G [m — 1]; aj < bj }| for each j G [n — 1] \ g([m — 1]). We define f : [m] ^ [n] by f (i) := g(i) for all i G [m — 1] and f (m) := n. In all three cases, it is easily seen that f satisfies (5). By Theorem 1 it follows that R has a strict RNECT of the form (K/ ,S/) where both K/ and S/ are p-orbital. □ Corollary 2 Every R G k(x) has a strict RNECT. Proof: Take an orbital decomposition R = nN=1 Rj. By Lemmas 6 and 1, for each i G [N] there is a strict RNECT (Kj, Sj) of Rj withpj-orbital kernel and shell. =1 Kj, s=n CD Let K =HN1 Kj, S 1 sj. It is easy to see that (K, S) G sRNEff (R). □ 6 Minimality of the kernel It is shown in (Schneider, 2005, Thm. 4.14) for nS-extensions k(x) of k that degnum(K) and degden(K) in (1) are simultaneously minimized iff K is a-reduced. Here we show this for all unimonomial extensions k(x) of k. Lemma 7 Let p G k[x] be irreducible. If R G k(x)* is p-orbital and (K, S), (K', S') G RNFct(R), then degnum(K) = degnum(K') and degden(K) = deg den(K'). Proof: From K • aS/S = K' • aS'/S' it follows that degnum(K) + degden(K') = degnum(K') + degden(K). (6) By Lemma 5, K and K' are p-orbital. Since they are a-reduced, either degnum(K) = 0 or degden(K) = 0, and either degnum(K') = 0 or degden(K') = 0. Thus we distinguish four cases, and use (6) in each: 1. If degnum(K) = degnum(K') = 0 then degden(K) = degden(K'). 2. If degnum(K) = degden(K') = 0 then degnum(K') + degden(K) = 0, hence degden(K) = degnum(K') = 0. 3. If degden(K) = degden(K') = 0 then degnum(K) = degnum(K'). 4. If degden(K) = degnum(K') = 0 then degnum(K) +degden(K') = 0, hence degnum(K) = degden(K') =0. □ I Theorem 2 If (K, S) and (K', S') are two RNFff's of the same R G k(x)*, 00 then degnum(K) = degnum(K') and degden(K) = degden(K'). Proof: Let K = nf=1 Ki, S = ft*! Si, K' = nf=1 K', S' = ft*! Si be orbital decompositions of K, S, K', S', respectively, where K',Si,Ki', Si are p'-orbital. As K and K' are a-reduced, so are K' and K'. Denote R' = Ki • aS'/S' and R' = K' • aS'/S'. Then R' and R' are p'-orbital, (Ki,Si) G RNFff(R'), and (K',S') G RNFff(R'), for all i G [N]. As ni=1 R' = EIi=1 R', it follows from Lemma 4 that R' ~ R'. By Lemma 7, degnum(K') = degnum(K') and degden(K') = degden(K') for all i G [N]. Hence degnum(K) = ^N=1 degnum(K') = ^N=1 degnum(K') = degnum(K') and degden(K) = ^N=1 degden(K') = ^N=1 degden(K') =degden(K'). □ Corollary 3 Let K, S G k(x)* and R = K • aS/S. Then (K, S) G RNFff (R) iff degnum(K) < degnum(K') and degden(K) < degden(K') (7) CD for all K', S' G k(x)* such that R = K' • aS'/S'. CD u a CD U o CSI I CSI CSI CO u a CD u Proof: Assume that (K, S) G RNFT (R), and let (L,T) be a strict RNFT of K' which exists by Corollary 2. Then (L, S'T) G RNFT (R), and Theorem 2 implies that degnum(K) = degnum(L) and degden(K) = degden(L). By Lemma 2, num(L) | num(K') and den(L) | den(K'), hence degnum(K) < degnum(K') and degden(K) < degden(K'). Conversely, assume that (K, S) G RNFT (R). Then K is not a-reduced, hence there are p G k[x] \ k and n G Z \ {0} such that p | num(K) and anp | den(K). Let K' = K • anp/p and S' = S/pT'n. Then K' • aS'/S' = K • aS/S = R, degnum(K') = degnum(K) — deg(p) < degnum(K), and degden(K') = degden(K) — deg(p) < degden(K), contrary to (7). □ 7 Minimization of the shell According to Theorem 2, all RNFT's of the same R G k(x) have kernels of the 1 same degrees. In contrast, the degrees of their shells can differ widely. We wish 1 to minimize the shell with respect to one of the many possible weight functions which we define in the following way. o Definition 4 A weight function is a monomorphism7 of the Abelian group Z x Z, partially ordered by components8, into some computable linearly ordered Abelian group L. If w is a weight function, we define the associated weight W of a rational function S G k(x)* by setting W(S) := w(degnum(S), degden(S)). Definition 5 Let w be a weight function, and R G k(x). We call (K, S) G RNFT (R) a rational (w, a)-canonical form (an RCFWT ) of R if S is monic, and W(S) is minimal among all RNFT's of R. Remark 2 From Corollary 2 it follows immediately that rational (w,a)-canonical forms exist for all weight functions and all R G k(x). In Corollary 4 we will see that they are unique provided that each irreducible factor of R is non-periodic with respect to a. Example 3 Take L = Z x Z, ordered lexicographically by (a1, b1) a261). Remark 3 In (Abramov, Le and Petkovsek, 2003), the forms RCF1t, RCF2 t RCF3jT , and RCF4,T are denoted by RCF1, RCF2, RCF1, and RcF^, respectively, in the special case when a = £. Note that the definitions of RCF1 and RCF2 given in (Abramov, Le and Petkovsek, 2003) are different from, but equivalent to those of RCF1t and RCF2 t in this case. Example 4 Let a be any automorphism of k[x]. Assume that p G k[x] is a non-periodic polynomial of degree 1, and let R p a3p a10p a16p a21p ap a2p a6p a7p a12p a13p a19p a20p Consider the following four strict RNFT's of R: 1 K1 a6p a12p a19p' K2 = a2p a7p a13p' K3 K4 a6p a7p a19p' a6p a7p a13p' 51 = 52 = 53 54 2 7 8 9 13 14 15 20 a2p a'p a8p a9p a13p a14p a p a p _a2^__ p a3p a4p a5p a10p a11p a16p a17p a18p' a2p a13p a14p a15p a20p p a10p a11p 2 20 a2p a20p p a10p a11p a16p a17p a18p The weights W1, W2, W3, W4 of S1, S2, S3, S4 are given in the following table: W1 W2 W3 W4 S1 (1, 8) (8,1) (9,1) (9, 8) S2 (9,1) (1, 9) (10, 9) (10,1) S3 (3, 5) (5, 3) (8, 3) (8, 5) S4 (6, 2) (2, 6) (8, 6) (8, 2) u a CD U p 1 1 1 In each column, the lexicographically minimum weight is shown in boldface. It can be verified that ((aAj/Aj)Kj, Sj/Aj) where Aj _ lc(Sj) is an RCFjT of R, for i _ 1, 2, 3,4. Theorem 3 Any RCFw T of R is strict. Proof: Let (K, S) be an RNFT of R which is not strict. We distinguish three cases. a) deggcd(num(K), num(S)) > 0: Write num(K) _ rg, num(S) _ ug where g _ gcd(num(K), num(S)). We claim that £ CO CO CO CD U a CD U v" 7 Vden(K)' den(S) 0: Write num(K) _ rg, den(aS) _ av • g where g _ gcd(num(K), den(aS)). Similarly as in a), we can verify that « (K^ (SSK?^ ) e RNF-(«)• Thus, again (K, S) is not an RCFWjCT of R because degnum(S') _ degnum(S) and degden(S') < degden(S), hence W(S') < W(S). c) deggcd(den(K), num(aS)den(S)) > 0: By Lemma 1, (K-1, S-1) is a non-strict RNFCT of R-1 such that deggcd(num(K-1), den(aS-1) • num(S-1)) > 0. By a) and b), (K-1,S-1) is not an RCFWj(T of R-1, so by Lemma 1, (K, S) is not an RCFW T of R. □ 8 Computing rational (w, a)-canonical forms 8.1 Algorithmic prerequisites A rational (w, a)-canonical form for a given R e k(x) and a given weight function w : Z x Z ^ L can be computed by the following algorithm: m c^ I CD CO u a CD U Algorithm RCFw tN 3. Compute K = flNi K., S = 11^1. s., and a = lc (5). 1. Compute an orbital decomposition L[N=1 R. of R. C^ 2. For each i G [N], compute a rational (w, a)-canonical form (K., S.) of R.. & 4. Return ((aA/A)K, S/A). Proof of correctness: Note that (K, S) G RNFCT(R) by Corollary 1, hence the same is true of ((aA/A) • K, S/a). Now take any (K', S') G RNFCT(R), and let K' = ]1 M =i k. , s' = n i=1S.be orbital decompositions such that m > n and K., S., K., S' are p-orbital for each i G [N]. Suppose that K. is not a-reduced for some i G [M]. Since K' is a-reduced, there exists some j G [M] such that deggcd(num(K.), den(Kj)) > 0 or deggcd(den(K.), num(Kj)) > 0. But this is impossible as K. is p.-orbital and Kj is pj-orbital, while p./pj is a-reduced. Hence (K?,S') G RNFff(R') where R' = K. • aS./S', for all i G [M]. Since ni=1 R. = K' • aS'/S' = R is another orbital decomposition of R, Lemma 4 implies that R. ~ R. for all i G [M]. Therefore for each i G [M] there is some A. G k* such that (A.K., S.) G RNFff(R.). Since (K., S.) is an RCFw,ff of R., it follows that W(S.) < W(S.) for all i G [M]. By additivity of w, M M ^ W (S.) = ^ w(degnum(S.), degden(S.)) .=i .=i ii CSI = w I degnum(S.), degden(S.) i .=i ii CSI = w I deg num(S.), deg J^den(S.j) £ CO where the fourth equality follows from the fact that S. is p.-orbital, Sj is pj-orbital, and p./pj is a-reduced for all i, j G [M]. In the same way we obtain \ .=i .=i / = w(degnum(S), degden(S)) = W (S), i ]TW (S.) = w(degnum(S'), degden(S')) = W (S'). .=i Hence W(S) < W(S') for all (K', S') G RNFff(R). Together with lc (S/A) = 1 this implies that ((aA/A)K, S/A) is an RCFw,CT of R. □ w It remains to explain how to perform steps 1 and 2 of Algorithm RCFw,CT. In step 1, an orbital decomposition of R can be computed9 if we have 9cf. (Bronstein, 2000, Lemma 15(i) and its proof) c^ 1. an algorithm PF for factoring polynomials in k[x]; 2 2. an algorithm SE which, given irreducible p, q G k[x] \ k, decides if there is an n G Z such that p — anq, and if so, computes one. These two conditions are satisfied, e.g., when k(x) is a nS-field over a semi-computable constant field (Schneider, 2005, Thm. 2.11). Step 2 of Algorithm RCFw,T requires computation of an RCFw,T of a p-orbital rational function R. An algorithm for doing this via reduction to the assignment problem is the main result of the paper and is described in Sections 8.2, 8.3 and 8.4. However, this algorithm assumes that the value of n(p) is known. Therefore we sketch here an algorithm which computes the semi-period of an irreducible polynomial p G k[x] \ k, provided that we have C^ 1. an algorithm LDE which, given a G k* and b G k, decides if there is a w G k such that aw = aw + b, and if so, computes one; 2. an algorithm SR which, given a G k*, decides if a is a a-radical10; 3. an algorithm HSO which, given a G k*, computes a nonnegative generator of the ideal J (a) := {n G Z; aT'n = 1} C Z. o CSI I Using these algorithms, we can proceed as follows: Run LDE on a and b where ax = ax + b. If there is no w G k such that aw = aw + b, Theorem 1 of (Karr, 1981) implies that there is no q G k[x] \ k such that aq/q G k*. However, if n(p) > 0 then t(p) G k[x] \ k and Proposition 1(ii) implies that at(p)/t(p) G k*. Hence n(p) = 0. If w G k satisfies aw = aw + b, introduce a new variable y = x — w. Then ay = ay, so it suffices to consider the case b = 0. Run SR on a. If a is not a a-radical, then Theorems 2 and 9(d) of (Karr, 1981) imply that n(p) G {0,1}. Hence: if ap — p then n(p) = 1 else n(p) = 0. So let ax = ax where a is a a-radical. Assume that anp = Ap for some n > 0 and A G k*. Write p(x) = ^[ cixi where r > 0. If c0 = 0 then r =1 (since p is irreducible), hence n(p) = 1. Otherwise (since n(Ap) = n(p) for any A G k*) assume w.l.g. that c0 = 1. Then anci • (aT'")i = Aci for all i G [r] and also for i = 0. This yields A = 1 and )a,n = 1 for all i G [r] such that ci = 0. Run HSO on ai := ai • aci/ci for all i G [r] such that ci = 0, and let ni be the generators of the corresponding ideals J(ai). Then, clearly, n(p) = lcm{ni; i G [r], ci =0}. CO CD Example 5 Let a be a k-automorphism of k(x) where ax = ax and a G k* is a primitive m-th root of unity. Then (ai • aci/ci)T'n = 1 ^ ain = 1 ^ J-H a CD U CD 10a G k is a a-radical if an = aA/A for some n G Z, n > 0, and A G fc* m | (in) ^ (m/ gcd(m, i)) | n. Hence n _ m/ gcd(m, i) and Jh a CD Jh Example 6 Let a be any automorphism of k(x) where ax _ x (i.e., a _ 1 and x is an explicit new constant). Define the period n(c) of c e k* by S n(p)=lcmigcd(mi); i e [r],cj • So we can compute n(p) if we know m. ( ) ( 0, if anc _ c for all n > 1, | min{n > 1; anc _ c}, otherwise. Then (aj • acj/cj)T'n _ 1 ^ a"cj _ c ^ n(cj) | n, hence n _ n(cj) and n(p) _ lcm{n(cj); i e [r],Cj _ 0} . So we can compute n(p) if we can compute n(c) for each c e k*. Algorithms LDE and SR exist, e.g., when k is a nS-field over a a-computable11 constant field (see (Karr, 1981, Section 3); (Schneider, 2005, Thm. 3.2)). If also k(t) is a nS-extension of k then n(p) e {0,1} by (Karr, 1981, Thm. 9(d)), hence algorithm HSO is not needed in this case. Furthermore, if n(p) _ 1 then R in (3) is a-reduced, so (R, 1) is trivially an RCFW T of R for any weight function w, and the algorithm of Section 8.4 is not needed either. Incidentally, a k-automorphism of k[x] such that n(p) e {0,1} for each irreducible p e k[x] \ k is called aperiodic in (Bauer and Petkovsek, 1999). 8.2 The assignment problem Let R be as in (3). Theorem 3 tells us that in order to find an RCFW T of R, we need to minimize W(S) over all (K, S) e sRNFT(R). Up to a factor from k, the kernel K is determined by some increasing injection f : [m] ^ [n]. The shell S satisfies the first-order a-difference equation aS _ (R/K) • S, so once the kernel is fixed, the shell is determined up to a factor T e k(x) such that aT - T (Theorem 4). If, in addition, (K, S) is an RCFW T of R, then T - t(p)« where t(p) is the total span of p, and £ e Z (Theorem 5). Theorem 4 Let R be as in (3), and let (K, S) e sRNFT(R). Then there is T e k(x)* such that aT — T, and an increasing injection f : [m] ^ [n] such that K — Kf and S _ TSf, where (Kf, Sf) is the RNFT of R induced by f. HH Proof: By Lemma 5, K is p-orbital. As it is a-reduced, either num(K) — 1 or den(K) — 1. But degnum(K) — degden(K) _ (m — n) degp < 0, CD hence num(K) — 1 and degden(K) _ (n — m) deg p. By Lemma 2, 11Following (Schneider, 2005), a field F is a-com,putable if it is semi-computable (see footnote 6) and the generalized orbit problem (given fi,... ,fr € F *, find a basis for the Z-module 'U -1 {(n1,.. .,nr); fi1 ■■■ fUr = 1} C Zr) is solvable in F. den(K) I nn . ab o I CO ^ CO CO CO u a CD u den(K) | rj 1 abjp. Let j1 < ••• < jm be such that fj=1 abjp/den(K) rim1 abjip. Define f(i) := jj. Then f : [m] ^ [n] is an increasing injection Lemma 8 ^^^ u = 1 then aTj — Tj for all i G [m]. ^ m Proof: Clearly m1(aTj/Tj) is an orbital decomposition of some A G k*, and so is A • 1 • 1 • • • 1. By Lemma 4, aTj/Tj — 1 for all i G [m]. □ and den(K) — rij£[n]\/([m]) abjp, hence K — Kf and R — Kf • aS/S. Let T := S/Sf. By Theorem 1, R = Kf • aSf/Sf. Hence aT - T. □ Lemma 8 Let\\m=1 T be an orbital decomposition of T G k(x)*. If aT — T Lemma 9 Let T G k(x) be such that aT — T. Then anum(T) — num(T) and aden(T) — den(T). Proof: From the assumption it follows that anum(T) • den(T) — aden(T) • num(T). Hence anum(T) | num(T), den(T) | aden(T), aden(T) | den(T), and num(T) | anum(T), proving the claim. □ Proposition 2 Let p G k[x] be irreducible, and let P G k[x] \ {0} be a p-orbital polynomial such that aP — P. Then P — t(p)^ for some £ G Z, £ > 0. Proof: Assume that ajp | P for some j > 0. Then aj+1p | aP. From aP — P it follows that aj+1p | P. By induction, ajp | P for all i > j. If n(p) = 0 this is impossible, so P G k*. If n(p) > 0 we use induction on deg P. If deg P = 0 then P — t(p)0. Otherwise P = t(p)P' where P' G k[x] \ {0}, aP' — P', and deg P' < deg P. By inductive hypothesis, P' — t(p)^ , hence P — t(p)^ +1. □ Theorem 5 Let R be as in (3), and let (K, S) be an RCFw T of R for some weight function w. Then there are an increasing injection f : [m] ^ [n] and £ G Z such that K — Kf and S — t(p)^Sf where (Kf ,Sf) is the RNFT of R induced by f. Proof: By Theorem 3, (K, S) is strict. By Theorem 4, there are T G k(x)* and an increasing injection f : [m] ^ [n] such that aT — T, K — Kf, and S = TSf. Let nj=1 Tj be an orbital decomposition of T where each Tj is pj-orbital and p1 =p. Write T' = T/T1. By Lemma 8, aT1 — T1. By Lemma 9 and Proposition 2, T1 — t(p)^ for some £ G Z, hence T — t(p)^T' and S — t(p)«T'Sf. From num(t(p)«T'Sf) = num(T')num(t(p)«Sf) it follows that degnum(S) = degnum(t(p)^T'Sf) = degnum(T') + degnum degnum(t(p)^Sf). Similarly, degden(S) = degden(T') + degden(t(p)^Sf) > degden(t(p)«Sf), hence W(S) > W(t(p)«Sf). But (K, S) isanRCFw,T of R and (Kf /^(p)«, t(p)«Sf) is an RNFT of R, so W(S) = W(t(p)«Sf). This implies that degnum(S) = degnum(t(p)^Sf) and degden(S) = degden(t(p)^Sf). Hence degnum(T') = degden(T') =0, T' — 1, and S — t(p)«Sf. □ CD Now we will reduce the problem of finding an RCFw T of R as in (3) to an instance of the following combinatorial optimization problem: Assignment problem input: a computable linearly ordered Abelian group L; a cost matrix [cj,j]i£[m],j£[n] where cj,j G L and m < n; output: an injection f : [m] ^ [n] such that its cost c(f) = i cj,f(j) is minimal. w u a CD U The assignment problem can be solved in time polynomial in max{m, n} by linear programming techniques (see, e.g., (Papadimitriou and Steiglitz, 1982)), hence an RCFWjCT of R can be computed efficiently for arbitrary R G k(x) from the orbital decomposition of R. In order to reduce the computation of RCFWjCT to the assignment problem, we need to distinguish two cases - according to whether p is non-periodic or semi-periodic. Remark 4 In standard specifications of the assignment problem, L is a computable subgroup (such as Z or Q) of the linearly ordered additive group R. Allowing more general groups L - as we do above - does not affect algorithms for solving the assignment problem, provided that subroutines for computing addition and comparison of elements of L are available (which is implied by computability of L). Nevertheless, if one wishes to model this more general situation in a standard setting, one can often do so quite easily. For instance, if L = Z x Z ordered lexicographically as in Example 3, one can replace each weight Cjj = (ftjj, frjj) G Zx Z where ajj, bjj > 0, by the weight ajj N+bj,j G Z where N = max {J2 mi maxj£[„] a-jj, J2 mi maxj£[„] bjj} + 1. Since the cost of an injection f : [m] ^ [n] does not exceed (N — 1, N — 1), this mapping (representing evaluation of 2-digit numbers in base N) faithfully embeds the original lexicographic order in Z x Z into the usual order in Z. 8.3 The non-periodic case In this subsection, p G k[x] is an irreducible non-periodic polynomial, hence t(p) = 1. We denote S := deg p. If (K, S) is an RCFw ,CT of R, then by Theorem 5, K ~ Kf and S ~ Sf where f : [m] ^ [n] is an increasing injection. Thus it only remains to define a cost matrix [cj j]i£[m],j£[n] so that the solution f of the associated assignment problem will also minimize the weight of Sf. Definition 6 Let R be as in (3), let f : [m] ^ [n] be an injection, and let w be a weight function. We define the weight of f as w(f) := w(di,d2) where di = s Y1 (aj— bfj)^ ai >bf (j) d2 = S ^ (bf (j) — aj). ai bf (j), aj2 < bf(j2), and there are ii, i2 such that q ~ a®1 p where bf(j) < ii < aj and q ~ a®2p where aj2 < i2 < bf (j2). From a®1 p ~ a®2p we get a|i1-®2|p ~ p. As p is non-periodic, this implies that ii = i2. Hence aj2 < aj which implies that j2 < ji, and bf (j) < bf(j2) which implies that f(ji) < f(j2). As f is increasing, it follows that j < j2, a contradiction. Thus in this case degnum(Sf) = YjjLi degwjf) = di and degden(Sf) = deg v(f) = d2, whence W(Sf ) = w(/). □ Theorem 6 Let R be as in (3), w a weight function, g : [m] ^ [n] an injection of minimum weight, and let (Kg, Sg) be the RNFCT of R induced by g. Then ((aA/A)Kg, Sg/A), where A = lc (Sg), is an RCFw,CT of R. Proof: Let (K, S) be an RCFw,CT of R. By Theorem 5, there is an increasing injection f : [m] ^ [n] such that K ~ Kf and S ~ Sf. Then by Lemma 10, W(S) = W(Sf) = w(f) > w(g) > W(Sg). Hence W(Sg) = W(S) is minimal among all RNFCT's of R, and the assertion follows because lc (Sg/A) = 1. □ Theorem 6 shows that to compute an RCFw,CT of R where R is as in (3), it suffices to find an injection f : [m] ^ [n] of minimum weight. This can be done by solving the assignment problem with the cost matrix (a® — bj, 0), a® > bj, c®j = 1 w w Indeed, the cost c(f) of f is then given by _ i. ^ , V^ .../n i. ^ _ „Jdi d2 CO c® j = . (8) ® 1 w(0,bj — a®), a® < bj. w c(f) = 53 w(a®— bf(®), 0) + w(0,bf(®) — a®) = w ( y, y -i>bf(i) ai 1. Denote S := deg p and p := n(p). If (K, S) is an RCFWjCT of R, then by Theorem 5, K ~ Kf and S ~ t(p)^Sf where f : [m] ^ [n] is an increasing injection, t(p) is the total span of p, and £ G Z. Here it can happen that W(t(p)^Sf) < W(Sf) for £ = ±1 because of cancellations, hence it is not enough to consider merely those RNFCT's which are induced by injections. For example, if R = f(j)}|-|{j e s 1 (-1); aj < fj)^ v _ n; +r(j)-i i mod p i=b /(j) p, n6/(j)+r(j)-1 ai mod pp I Ii=a, a p, s(j) • (aj - bf (j)) > ° otherwise, s(j) • (aj - bf(j)) > 0, otherwise. Then (Kf,s, Sf,s) e RNFa(R). Proof: Kf,s is trivially a-reduced. Assume that s(j) • (aj - bf j)) > 0. If r(j) _ 0 then ,(/,s) and n;= aip, ,(f,s) ,(f,s) a"j p ab/(j) p. CD ■ i Jh CD m If r(j) _ p then uj/,s) _ np=6/(j) aip • n;=0 aip, and Hence ,(f,s) ,(f,s) ,(f,s) a p a jp ,(f,s) abf(j) p p a j p f(j) p M(p) "(j)/p a;j p ab/(j) p M(p). s(j) • (aj - bf(j)) > 0 otherwise. u a CD U j j j j j j j o 0 o 1 CO £ CO CO CO CD u CD CO Similarly we compute „,(f,s) 1, ,(f,s) a j p f (j) p M(p) -r(()/p s(j) • (aj - bf(j)) > 0 otherwise. Therefore aS f,s n ,(f,s) „,(f,s) J J Sf,s hence Kf,s • aSf,s/Sf,s = R. — ?/(f,s) av(f,s) j=1 avj aaj p f-«■ abf (j) p j=1 n M(p)- □ Remark 5 We call (Kf,s, Sf,s) defined in (9) the RNFa induced by (f, s) Definition 8 Let R be as in (3), let (f, s) be a signed injection, and let w be a weight function. We define the weight of (f, s) as w(f, s) := w(d1, d2) where d1 = < (aJ +r(j) - bf s(J)(aj-bf(j))>0 d2 = <5 (bf (J) + r(j) - ), s(()*(aj-bf(j))<0 and r(j) is defined in Theorem 7. Lemma 11 Let (f, s) be a signed injection, and let w be a weight function. Then W(Sf,s) < w(f, s). Proof: From (9), deg num(Sf,s) < m=1 degujf,s) = d1 and degden(Sf,s) < £J=1 deg v (f,s) d2, hence W(Sf,s) = w(deg num(Sf,s), deg den(Sf,s)) < w(d1, ^2)= w(f, s). □ Definition 9 A signed injection (f, s) is non-crossing if W(Sf,s) = w(f, s). Lemma 12 Let (f, s) be a signed injection. Then there is a non-crossing signed injection (f', s') which induces the same RNFa as (f, s). Proof: If nm=1 ujf s) ^ nj=1 v(f,s) then (f, s) is non-crossing and we can take f' = f, s' = s. Otherwise there are j = l G [m] such that wjf,s) and v; share a nontrivial common factor. This means that s(j) • (a(- — bf (j)) > 0, s(l) • (a; — bf(;)) < 0, and (f,s) Q(j'l) := f) • f) v( Vi ' ( 1 n: aj +r(()-1 aj mod p f (j) p nb=f™-1 aj mod pp- There are four ways in which the intervals I := [bf(j),aj + r(j) — 1] n Z and J := [a;, bf(;) + r(l) — 1] n Z can intersect when projected into u a CD U J a J T £ CO CO u a CD U (a) one of I, J is contained in the other, (b) I and J partially overlap (c) I n J = 0 but when projected into Z/pZ one is contained in the other, (d) I n J = 0 but when projected into Z/pZ they partially overlap. In each of these cases there are two subcases as to the roles played by I and J. Hence altogether we distinguish eight subcases: (a1) bf(j) < a, < bf(0 + r(l) < aj + r(j): This is only possible if r(l) = 0, or r(j) = r(l) = p. Then ai-i °j +r(j)-i Q(j,1) = n a® mod Pp • n a® mod Pp. ®=bf (j) ®=bf(i) +r(l) (a2) a, < bfj < a, + r(j) < bf(,) + r(l): This is only possible if r(j) = 0, or r(j) = r(l) = p. Then ~ 1 Q(j,1) = nbf(j)-ia®modp„ nbf(D +r(l)-ia®modpp. H®=ai a 'V 1 l®=0j. +r(j) a 'V O (b1) bf(j) < a < a, +r(j) < bf(i) +r(1): This is only possible if r(j) = 0, or r(j) = r(l) = p. Then n0i-i a® mod Pp n®=bf(j) 1 n'jrS) i a® mod pp (b2) a, < bf (j) < bf (,) + r(l) < a, + r(j): This is only possible if r(l) = 0, or r(j) = r(l) = p. Then j-J°j +r(j)-i a® mod pp nb=°) i a® mod pp ®=bf( i)+r(l) In subcases (c1) and (d1) we have bf(,) < a, + r(j) < a, < bf(,) + r(l) and bf (j) + p < bf (,) + r(l). This is only possible if r(j) = 0 and r(l) = p, hence a > bf(i) > bf(j). CO (c1) If aj < bf (i) then ■ I 1 Q(j,1) = —s—z—i-£-i-. nb=°)+P-i a® mod Pp •!!b=°j-i a® mod Pp o (d1) If aj > bf (;) then naj i mod pP nb=a)+p—i mod pp' In subcases (c2) and (d2) we have a; < bf(;) + r(l) < bf(j) < aj + r(j) and a; + p < aj + r(j). This is only possible if r(j) = p and r(l) = 0, hence a; < aj < bf(j). (c2) If aj > bf (;) then aj+p—i a7- — i Q(j,i) = n mod pp •; j mod p P. j=b f (j) j=b f (j) 0 o 1 00 ^ CO CO CO CD $H CD CO (d2) If aj < bf (;) then Q(j,i) ja ai+P— 1 i mod j=b f(j) <7 nb=a—i mod pp' Define f : [m] ^ [n] by fi(x) = f (x) for x = j, l, fi(j) = f (l), fi(l) = f (j). Define si : [m] ^ {-1, +1} by si(x) = s(x) for x = j, l, and in cases (a), (b): si(j) si(l) +1, 1, s(j) = s(l), otherwise, = +1; in cases (c), (d): si(j) = +1, si (l) = -1. Then it is straightforward to check that (fi, si) is a signed injection which induces the same RNFCT as (f, s), and that deggcd ( nj=i M(fl'Sl), fi ir=i v(fi,si)] < deggcd ^rij=i M(f'S), nm=i . Iterating this procedure, we eventually arrive at a signed injection (f', s') which induces the same RNFCT as (f, s), and is such that j=i (f V) ,(f V) . Hence (f', s') is non-crossing. □ Lemma 13 Let R be as in (3), and let (K, S) be an RCFWj0- of R. Then there is a non-crossing signed injection (f, s) such that W(S) = w(f, s). Proof: By Theorem 5, there are an increasing injection f : [m] ^ [n] and £ G Z such that K - Kf and S - t(p)«Sf. Let Sf = f] j=i U (f)/ (f) as in (4), and assume that £ > 0 (if £ < 0 the proof is analogous). Denote J = {j G [m]; aj < bf (j)} and N = | J |. We distinguish two cases: u a CD U p P a) £ > N: In this case, S, equals t(p)P for some polynomial P G k[x]. Then (nKf,P) G RNFff(R) where n = (K/K,)a(s/P)/(S/P). Since deg P < deg(t(p)P) = degnum(S), we have W(P) = w(deg P, 0) < w(degnum(S), degden(S)) = W(S). So this case is impossible. C^ o CSI I CO u a CD U b) £ < N: W.l.g. assume that aj < b, (j) for j G [N]. Then § = ii lii , = n j^n , « aj +P-1 m (f) = n n mod ■ n , = where j=1 i=6/(j) j=«+1 sj) = «! -1, 1 < j < £ ' +1, £ + 1 < j < m. By Lemma 12, there is a non-crossing signed injection (f', s') which induces the same RNFff as (f,s). Hence W(S) = W(t(p)«Sf) = W(Sfs) = W(Sf, s) = w(f ',s'). ' ' □ Theorem 8 Let R be as in (3), let w be a weight function, let (g, z) be a signed injection of minimum weight, and let , Sg,z) be the RNFCT of R induced by (g, z). Then ((ctA/A)KSjZ, Sg,z/A) where A = lc (Sg,z) is an RCFWjCT of R. Proof: Let (K, S) be an RCFWjCT of R. By Lemma 13, there is a signed injection (f, s) such that W(S) = w(f, s). By minimality of (g, z), we have w(f, s) > w(g, z), and by Lemma 11, w(g, z) > W(Sg,z), so W(S) > W(Sg,z). Hence W(Sg z) = W(S) is minimal among all RNFCT's of R, and the assertion follows because lc (Sg,z/A) = 1. □ CSI Theorem 8 shows that to compute an RCFWjCT of R where R is as in (3), it suffices to find a signed injection of minimum weight. By additivity of w, we have min w(f, s) = min w(d1,d2) = minS ■ w S aj, S $ (f,s) (f,s) (f,s) where S- min> w (a,, 5,) = S- min min > w (a;,5,) w' ) ;=1 ;=1 (a, + r(i) - b,w, 0), s(i) ■ (a, - b,w) > 0, (a;, The values of s can be chosen independently of each other, therefore m m m min^ w (aj,5i) = ^ min w (a,,^) = ^min(£;,ni) v | (0, b,(;) + r(i) - a;), otherwise. CD 0 o 1 CO £ CO CO CO CD ■ i-H $H CD CO where ) = (w(aj, A)|s(i)=+i, A)|s(i) = -i) (w(aj - bf(i), 0), w(0, bf(i) + p - flj)) (w(0, bf(i) - Oj), + p - bf (i), 0)) ai > bf(i^ ai < bf(i). Thus min(f,s) w(f, s) = J • minf i ci,f(i) where min (w(ai - bj, 0), w(0, bj + p - ai)), ai > bj, min (w(0, bj - ai), w(ai + p - bj, 0)), ai < bj. (10) Consequently, a signed injection (f, s) of minimum weight can be found in the following way. By solving the assignment problem with cost matrix (10) we obtain f, and s is determined by f: if ai > bf (i) and w(0, bf (i) + p - ai) < w(ai - bf (i), 0), or if ai < bf(i) and w(ai + p - bf(i), 0) < w(0, bf (i) - ai), then s(i) = -1. Otherwise s(i) = +1. Example 8 Let p(x) = x and ax = wx + 1 where w is a primitive 22nd root of unity. Then a22p = p, and p is semi-periodic with semi-period p = n(p) = 22. Let R be as in Example 4. Then ((aAi/Ai)Ki, Si/Ai) where Ai = lc (Si) and Ki K2 K3 K4 p a6p ai2p' a7p ai3p a20p' a6p a7p ai9p' a6p a7p ai3p' 51 52 53 54 2 n9 2p rii aip EIi=i3 aip ai9p (a20p) a2ip; p2 ap nf=3 aip n-^io aip ni=i6 aipa2ip' a2p ai3p ai4p ai5p a20p p ai0p aiip 2 20 a2p a20p p ai0p aiip ai6p ai7p ai8p' is an RCFij(T of R, for i = 1, 2, 3, 4. The weights Wi, W2, W3, W4 of Si, S2, S3, S4 are given in the following table: Wi W2 W3 W4 Si (0,11) (11,0) (11,0) (11,11) S2 (12,0) (0,12) (12,12) (12, 0) S3 (3, 5) (5, 3) (8, 3) (8, 5) S4 (6, 2) (2, 6) (8, 6) (8, 2) In each column, the lexicographically minimum weight is shown in boldface. It is instructive to compare this table with the one in Example 4. Proposition 3 Let p G k[x] be irreducible semi-periodic, let R G k(x) be p-orbital, and let (Ki,Si) resp. (K2,S2) be an RCFijCT resp. an RCF2jCT of R. Then Si and 1/S2 are polynomials. u a CD U 1 a 1 1 1 1 Proof: In the case of RCFijCT, the cost matrix (10) is o 0 o 1 CO ^ CO CO CO CD $H CD CO (0, a® - bj), a® > bj, (0, a® + p - bj), a® < bj, hence W(Si) = (degden(Si), degnum(Si)) is of the form (0, u) for some u G Z, u > 0. - Similarly, in the case of RCF2jCT, the cost matrix (10) is (0, bj + p - a®), a® > bj, (0, bj - a® < bj, hence W(S2) = (deg num(S2), degden(S2)) is of the form (0, v) for some v G Z, v > 0. □ 9 Uniqueness of rational (w, a)-canonical forms Definition 10 Let /i,/2 : [m] ^ [n] be two increasing injections, and s > 1. A sequence of integers (ii, i2,. .., is), 1 < ii < «2 < ••• < is < m, is an (/i, /2 )-chain if 1. /i( ij) < /2(ij), for 1 < j < s, 2. /i(ij+i) = /2(ij),for 1 < j < s - 1. Such a chain is maximal if /i(ii) G /2([m]) and /2(is) G /i([m]). Lemma 14 If there is an i G [m] such that /i(i) < /2 (i) then [m] contains a maximal (/i, /2)-chain. Proof: Let (ii, i2,..., is) be an (/i, /2)-chain. If it is not maximal then either there is i0 < ii such that /2(io) = /i(ii) or is+i > is such that /i(is+i) = /2(is). In the former case, /i(io) < /i(ii) = /2(io), so (io, ii,..., is) is a larger (/i, /2)-chain. In the latter case, /i(is+i) = /2(is) < /2(is+i), so (ii,..., is, is+i) is a larger (/i, /2)-chain. Thus every chain which is not maximal can be extended to a maximal chain. In particular, if /i(i) < /2(i) then (i) is an (/i,/2)-chain which is contained in some maximal chain. □ Proposition 4 Let /i,/2 : [m] ^ [n], /i = /2, be two increasing injections such that c(/i) = c/2) where c is the cost matrix (8). Then there is an injection / : [m] ^ [n] such that c(/) < c(/i). Proof: Let i G [m] be such that /i(i) = /2(i). W.l.g. assume that /i(i) < /2(i) (otherwise interchange the roles of /i and /2). By Lemma 14, [m] contains a maximal (/i, /2)-chain (ii, i2,..., is). Define g, h : [m] ^ [n] by g(x) h(x) /i(x), x = ii, i2, /2(x), otherwise, /2(x), x = ii, i2, /i (x) , otherwise. Jh a CD Jh s s We claim that g and h are injective. Indeed, if g is not injective then fi(x) = f2(ij) for some x = ii,..., is and j G [s]. Since f2(ij) = fi(ij+i) for 1 < j < s — 1, this is only possible if j = s. But then f2(is) = fi(x) G fi([m]), contrary to the maximality of (ii, i2,..., is). - In an analogous way we can see that h is injective. The cost of g respectively h is c(g) = y — a, c(h) = y + a, CO CO m CD $h CD m u a CD U where y = c(fi) = c(f2) and /_J(Cjj ,fi(jj ) Cjj ,f2 (jj )). C^ j=i for some uj, Vj G Z. Then a = S=i w(uj, Vj) = w(u, v) where u = ^®=i and v = ^S=i Vj. Since bf1(ij) < bf2(ij), it suffices to distinguish three cases: We wish to show that a = 0. By (8), we can write cij,f1(ij) —cij,f2(ij) = w(uj, Vj) >S=i w(uj ,vj >j=i vj. Since bfi(ij) < b 1. If ajj < bfi(jj) < bf2(jj) then, by (8), uj = 0 and Vj = bfi(ij) — bf2(jj) < 0. 2. If bfi(jj) < ajj < bf2(jj) then, by (8), uj = ajj — bfi(jj) > 0 and Vj = ajj — bf2(jj) < 3. If bfi (j j) < bf2 (jj) < ajj then, by (8), uj = bf2(jj) — bfi (jj) > 0 and Vj = 0. Hence u = Xj=i Uj > 0, v = Xj=i Vj < 0, and at least one of these inequalities is strict. As w is injective, it follows that a = w(u,v) = w(0,0) = 0. Now define ( g, a > 0, f \ h, a < 0. Then c(f) = y — |a| < y. □ Corollary 4 Let R G k(x) be as in (3) where p G k[x] is non-periodic. Then R has a unique RCFw,CT for any weight function w. Proof: Existence of RCFWjCT has already been established (see Remark 2). To prove uniqueness, assume that (Ki,Si) and (K2,S2) are two distinct RCFw,ff's of R. By Theorem 5, (Ki,Si) and (K2,S2) arise from increasing injections fi,f2 : [m] ^ [n], respectively. By Lemma 10, w(fi) = W(Si) = W(S2) = w(f2), hence c(fi) = c(f2) where c is the cost matrix (8). By Proposition 4, there is an injection f : [m] ^ [n] such that c(f) < c(fi). But then w(f) < w(fi), which is impossible. □ 10 An application: Succinct representation of a-hypergeometric terms In this section we assume that a is a k-automorphismi2 of k(x), which implies that aR(x) = R(ax) for all R G k(x). In addition, we assume that the mapping Z ^ k defined by n = (anx) |x=i, is injective. CD Definition 11 A sequence t = (tn)n>0 of elements of k is a a-hypergeometric term if tn = 0 for all large enough n, and there are polynomials p, q G k[x] \ {0}, p ± q, such that p(n)tn+i = q(n)tn for all n > 0, where n = (anx) |x=i. The quotient q/p G k(x)* is called the certificate of t. A sequence (sn)n>n0 with n0 G Z \ {0} is also called a a-hypergeometric term if the sequence t = (tn)n>0 where tn = sn+n0 satisfies Definition 11. Proposition 5 The certificate of a a-hypergeometric term is unique. Proof: By the assumptions on t and both tn and p(n) are nonzero for all large enough n, hence q(n)/p(n) = tn+i/tn for such n. Thus any two certificates of t agree infinitely often, and hence are equal. □ Tn = anG J] aiF. (11) i=0 tn = Tn(1) is a a-hypergeometric term with certificate H = F • aG/G. CO CD m u a CD U Theorem 9 Let F, G G k(x)* be rational functions. For each n > 0, let n-i If den(Tn)(1) = 0 f^or all n > 0 and num(Tn)(1) = 0 f^or all large enough n, then the sequence t = (tn)n>0 defined by a Proof: Denote p = den(H), q = num(H), and hi = aiH. Then Tn+i _ an+iG „nv-„nTj_u Tn anG therefore den(hn)Tn+i = num(hn)Tn. As den(hn)(1) = den(anH(x))|x=i = den(H (anx))|x=i = den(H)(an x)|x=i = p(anx)|x=i = p((anx)|x=i) = p(n), and similarly num(hn)(1) = q(n), it follows that p(n)tn+i = q(n)tn. □ HH Definition 12 Let F, G and t be as in Theorem 9. Then we call (F, G) a multiplicative decomposition of t. If degnum(F) < degnum(F') and degden(F) < degden(F') for all multiplicative decompositions (F', G') of t, then (F, G) is a minimal 'multiplicative decomposition of t. 12In this case, we could also restrict our attention to the two special cases ax: = x + b and ax = ax, for if ax = ax + b and a =1, the new variable y = x + b/(a — 1) satisfies ay = ay. Example 9 Let ax = x + 1. Then n = (x + n) |x=1 = n +1. Let p G k[x] \ {0} be a polynomial such that p(0) = 0, and let the sequence t = (tn)n>o be defined by tn = p(n). Then p(n — 1)tn+1 = p(n)tn for all n > 0, so t is a a-hypergeometric term. Since (anp(x-1)^"=0 aj 1)|x=1 = p(x+n—1)|x=1 = p(n) and (anp(0) ■ aj(p(x)/p(x - 1)))|x=1 = (p(0) ■ n—Wx + i)/p(x + i -1)))|x=1 = (p(0) ■ p(x + n - 1)/p(x - 1))|x=1 = p(n), both (1,p(x - 1)) and (p(x)/p(x - 1),p(0)) are multiplicative decompositions of t. Note that in the latter case, some of the factors in J^In^^x + i)/p(x + i - 1)) may well be undefined at x = 1, but this represents no obstacle since the product itself is defined at x =1. Definition 13 Let w be a weight function, and let (F, G) be a minimal multiplicative decomposition of t. If W(G) < W(G') for all minimal multiplicative decompositions (F', G') of t, then (F, G) is a w-minimal multiplicative decomposition of t. o C/3 Jh a CD U Theorem 10 Let t = (tn)n>o be a a-hypergeometric term such that to = 0, with multiplicative decomposition (F, G) and certificate H = F ■ aG/G. If (K, S) G RNFff (H) is such that S(1) G k*, and if S' = S ■ G(1)/S(1), then (i) (K, S') is a minimal multiplicative decomposition of t; (ii) if, in addition, (K, S) is an RCFWjCT of H for some weight function w, then (K, S') is a w-minimal multiplicative decomposition of t. o Proof: We have I n-1 n-1 ( aG \ T„ = anG ■ & a;F = G ■ & F ■ — i=o i=o ^ ' ^ = G ■ n1 -j (k ■ -S\ = G . —n. n1 G II —M K ■ ^ = G ■ anS J] ajK. i=0 S S i=0 By assumption, G(1) = to G k* and S(1) G k*. Therefore n — 1 \ / n— 1 tn = Tn(1) = Gy) ■ (^nS ■ H ajKj (1) = (^anS' ■ fl ajKj (1), hence (K, S') is a multiplicative decomposition of t. (i) Let (F', G') be any multiplicative decomposition of t. Then by Theorem 9 and Proposition 5, H = F' ■ —G'/G'. As (K, S) G RNFff (H), Corollary 3 implies that degnum(K) < degnum(F') and degden(K) < degden(F'). Hence (K, S') is a minimal multiplicative decomposition of t. (ii) Let (F', G') be any minimal multiplicative decomposition of t. By (i), (K, S') is a minimal multiplicative decomposition of t as well, therefore degnum(F') = degnum(K) and degden(F') = degden(K). As (K, S) e RNFff (H), Corollary 3 implies that degnum(F') < degnum(F") and deg den(F') < degden(F") for all F'', G'' e k* such that H = F" • aG"/G". Hence, by Corollary 3, (F',G') e RNFff(H). Since (K,S) is an RCFWj(T of H, it follows that W(S') = W(S) < W(G'), and so (K, S') is a w-minimal multiplicative decomposition of t. □ Example 10 Let ax = qx where q e k* is transcendental over Q C k. In this case, n = (anx)|x=i = qn. Let t be a a-hypergeometric term (called q-hypergeometric in this case) with multiplicative decomposition (F, G). By factoring F into linear factors over k, we may be able to avoid the explicit use of the product operator in (11), and instead express t entirely by means of the q-Pochhammer symbol (z; q)n defined for z e k and n e Z, n > 0, by n-i (z; q)n = !J(1 - zq4). i=0 o c/3 $H a CD U Consider the q-hypergeometric term t with multiplicative decomposition (R, 1) where R is given in Example 7. Then n- i n- i n- i tn = Tn(1) = n ajR(x)|x=i = n R(ajx|x=i) = n R(qj) j=0 j=0 j=0 t-1 (qj +q2 )(qj+1)(qj+q5-q3)(qj +q4-q2)(q3qj+q2-1)(qi2 qj+q2-1) j=0 (qj+q5)(qj+q4)2(q4qj + 1)(qj+q2-1)(q2qj+q2-1) , 00 __ _ _ _ t = n V q2 ; V n ( 1; q)nyg3-g5 ; V ; V nV ^ ; V nV ^ tn = a • which can be expressed in terms of q-Pochhammer symbols as -;q) (-1;q^fq^-;q) fqAr;q) (A-;q) (i2^;q (-a5; q) n (-a4; q) n (-q4; ^; q) n ; q) n where a = (q2 - 1)2/q6 e k*. Note that the number of q-Pochhammer symbols appearing in the above expression (counted with multiplicities) is degnum(R) +degden(R) = 12. By replacing decomposition (R, 1) with some decomposition (K, S) where (K, S) e RNFct (R) and S(1) = 1, we can reduce the number of q-Pochhammer symbols to its minimal possible value degnum(K) + degden(K) = 4, at the reasonable price of introducing the rational-function factor S(qn). Furthermore, if (K, S) is an RCFw,CT of R for some weight function w, then, in addition, W(S) will be minimal among all such representations of t. Thus for the term t given above, and for the weight functions wi, w2, w3, w4 from Example 3, we obtain the following succinct representations of t: an ( a31 a5 ; q ) ( q2 1 q4 ; q tn = tO^ • Si(qn) Va 2 ;"Va 2 Si(1) (-q5;q) (-q4;q)r n n o S2(1) S3(1) S4(1) S2(qn) S3(qn) S4(qn) ^ ; / n 11-2 ; V n - q5; V n I-q4; q i- q2;q q3 — q5 ; q (-q5; q)n (-q4; q)r J31q5 ; q) ( i-q2 ; q - q5; qJ n I-q4; V n where the rational functions Si, for i = 1, 2, 3,4, are given in Example 7. Note that in each of the above representations, the number of q-Pochhammer symbols is four (which is the least possible), and the weight Wi(Si) is minimal among all representations of t containing no more than four q-Pochhammer symbols, for i = 1, 2, 3,4. 0 o 1 CO ^ CO CO 11 Questions for further research 1. Our approach to the computation of RCFWjCT's is based on orbital decomposition which requires polynomial facorization. In special cases (such as computing RCF1jCT and RCF2jCT when a = £) algorithms are known which require only gcd and resultant computations (Abramov, Le and Petkovsek, 2003, Section 4.5). Is there an algorithm for computing RCFWjCT , based perhaps on a suitable generalization of the greatest factorial factorization of (Paule, 1995), which avoids polynomial factorization? 2. The problem solved by the (hypothetical) algorithm HSO of Section 8.1 is the homogeneous case (^ = 1) of the a-orbit problem13 of (Abramov and Bronstein, 2002). In an analogous way, an algorithm for solving the a-orbit problem can also be used to construct algorithm SE of Section 8.1 in the case ax = ax. Based on (Karr, 1981, Thms. 4 and 5), (Abramov and Bronstein, 2002) give an algorithm for solving the a-orbit problem in towers of n-extensions over certain commonly occurring base fields. In which other fields is this important problem solvable? 3. Is RCFWjCT(R) unique even if R contains irreducible factors which are semi-periodic with respect to a? co CD Jh CD CO Acknowledgements The authors wish to express their thanks to the referees whose reports inspired a thorough revision of the initial submission and helped clear up the question 13Given a, ft G k*, decide if the affine set A(a, ft) := {n G Z; a" not, find m,n G Z such that A(a,ft) = m + nZ. = ft} is empty, and if u a CD U n a n a n n a n of the necessary algorithmic prerequisites in the revised version, as well as to Prof. Peter Paule for his encouragement and great patience while waiting for the revised version. We are especially indebted to our late colleague Manuel Bronstein whose scholarly work in (Bronstein, 2000) paved the way for our investigations. o u a CD U References S. A. Abramov and M. Bronstein. Hypergeometric dispersion and the orbit problem. Proc. Int. Symp. on Symbolic and Algebraic Computation (ISSAC 2000), St. Andrews, ACM Press, New York, 2000, 8-13. S. A. Abramov, H. Q. Le, and M. Petkovsek. Rational canonical forms and efficient representations of hypergeometric terms. Proc. Int. Symp. on Symbolic and Algebraic Computation (ISSAC 2003), Philadelphia, ACM Press, New York, 2003, 7-14. S. A. Abramov, M. Petkovsek. Canonical representations of hypergeometric terms. Proc. Formal Power Series and Algebraic Combinatorics (FPSAC 2001), Arizona, U.S.A., 2001, 1-10. A. Bauer and M. Petkovsek. Multibasic and mixed hypergeometric Gosper-type algorithms. J. Symb. Comput. 28, 711-736, 1999. M. Bronstein. On solutions of linear ordinary difference equations in their coefficient field. J. Symb. Comput. 29, 841-877, 2000. S. A. Abramov and M. Petkovsek. Rational normal forms and minimal decompositions of hypergeometric terms. J. Symb. Comput. 33, 521-543, 2002. o F. Caruso. Polynomial arithmetic and linear systems in symbolic summation, Ph.D. Thesis. RISC-Linz (Austria), 2003. R. W. Gosper, Jr. Decision procedure for indefinite hypergeometric summation. Proc. Natl. Acad. Sci. U.S.A. 75, 40-42, 1978. M. Karr. Summation in finite terms. J. ACM 28, 305-350, 1981. M. Karr. Theory of summation in finite terms. J. Symb. Comput. 1, 303-315, 1985. C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall Inc., Englewood Cliffs, New Jersey, 1982. P. Paule. Greatest factorial factorization and symbolic summation. J. Symb. Comput. 20, 235-268, 1995. M. Petkovsek. Hypergeometric solutions of linear recurrences with polynomial coefficients. J. Symb. Comput. 14, 243-264, 1992. R. Pirastu and V. Strehl. Rational summation and Gosper-Petkovsek representation. J. Symb. Comput. 20, 617-635, 1995. M. van der Put and M. F. Singer. Galois Theory of Difference Equations. Springer-Verlag, Berlin Heidelberg, 1997. CSI 0 o CSI 1 CSI CO CSI c^ £ CO CO CO CD $H CD CO u a CD U C. Schneider. Symbolic summation in difference fields, Ph.D. Thesis. RISC-Linz (Austria), 2001. C. Schneider. Product representations in nS-fields. Ann. Comb. 9, 75-99, 2005. D. Zeilberger. The method of creative telescoping. J. Symb. Comput. 11, 195204, 1991.