Fixed Points of Maps on the Space of Rational Functions

Edward Mosteig Department of Mathematics Loyola Marymount University Los Angeles, California 90045 E-mail: emosteig@lmu.edu

Submitted: September 15, 2005; Accepted: May 2, 2006; Published: May 5, 2006

Abstract

Given integers s, t, define a function ϕ_{s,t} on the space of all formal series expansions by ϕ_{s,t}(∑ a_{n}x^{n}) = ∑ a_{sn+t}x^{n}. For each function ϕ_{s,t}, we determine the collection of all rational functions whose Taylor expansions at zero are fixed by ϕ_{s,t}. This collection can be described as a subspace of rational functions whose basis elements correspond to certain s-cyclotomic cosets associated with the pair (s, t).

Subject Class: Primary 33 Keywords: Rational functions, integrals, fixed points

1 Introduction

Let ℜ denote the space of rational functions with complex coefficients. The Taylor expansion at x = 0 of R ∈ ℜ can be written as a Laurent series, i.e.,

R(x) = ∑_{n≫−∞} a_{n}x^{n}  (1.1)

where n ≫ −∞ denotes the fact that the coefficients vanish for large negative n. For s, t ∈ ℤ, define the map ϕ_{s,t} : ℜ → ℜ by

ϕ_{s,t}(∑ a_{n}x^{n}) = ∑ a_{sn+t}x^{n}.  (1.2)

Denote the standard s-th root of unity throughout this paper by ω_{s} = e^{2πi/s}. When s is positive, consider the restriction ϕ_{s,t} : ℜ → ℜ. One can rewrite this map explicitly without the use of series expansions:

ϕ_{s,t}(R(x)) = (\frac{1}{s}) x^{−t/s} ∑_{j=0}^{s−1} ω_{s}^{−jt}R(ω_{s}^{j}x^{1/s}).  (1.3)

Indeed, if R(x) = ∑ a_{n}x^{n}, then R(ω_{s}^{j}x^{1/s}) = ∑ a_{n}ω_{s}^{jn}x^{n/s}, and so the coefficient of x^{(sn+t)/s} in the summation ∑ a_{n}ω_{s}^{jn}x^{n/s} is a_{sn+t}ω_{s}^{j(sn+t)}. Therefore, the coefficient of x^{n} in (\frac{1}{s}) x^{−t/s} ∑_{j=0}^{s−1} ω_{s}^{−jt}R(ω_{s}^{j}x^{1/s}) is (\frac{1}{s}) ∑_{j=0}^{s−1} ω_{s}^{−jt}a_{sn+t}ω_{s}^{j(sn+t)} = (\frac{1}{s}) ∑_{j=0}^{s−1} a_{sn+t} = a_{sn+t}.

The map ϕ_{2,1} can be used in a general procedure for the exact integration of rational functions, as described in [?]. Dynamical properties of ϕ_{2,1}, including kernels of the iterates, dynamics of subclasses of rational functions, and fixed points are discussed in [?]. The purpose of this paper is to generalize one of the results in [?] by classifying, for each pair of integers s, t, the collection of all rational functions that are fixed by ϕ_{s,t}. If s is an integer such that s ≤ 1, then 0 is the only rational function fixed by ϕ_{s,t}, unless, of course, (s, t) = (1, 0), in which case ϕ_{s,t} is the identity. When s ≥ 2, however, the story is much more interesting.

2 Cyclotomic Cosets

In this section, we assume throughout that s ≥ 2, 0 ≤ t ≤ s − 2, and R ∈ ℜ such that

ϕ_{s,t}(R(x)) = R(x).  (2.1)

Given these restrictions on s and t, it follows that |t/(s − 1)| < 1. Thus, if n ≤ −1, then n < −t/(s − 1), and so sn + t < n. Assuming that R(x) is fixed by ϕ_{s,t}, we have that a_{sn+t} = a_{n} for all n. Thus, if a_{n} is nonzero for any negative value of n, then there are infinitely many nonzero coefficients of negative powers of x, contradicting the assumption that R(x) is of the form given in equation (??).

We write R in the form

R(x) = ∑_{n=0}^{∞} f(n)x^{n}  (2.2)

to emphasize the fact that the coefficients can be interpreted as the images of a generating function f : ℕ → ℂ. Since R(x) is fixed by ϕ_{s,t}, it follows that

f(n) = f(sn + t)  (2.3)

for all integers n. The following result, which was proven on page 202 of [?], elucidates the relationship between the generating function f of the coefficients of the Taylor expansion of R(x) and the representation of R(x) as a quotient of polynomials.

Lemma 2.1. Let q_{1}, q_{2}, …, q_{d} be a fixed sequence of complex numbers, d ≥ 1, and q_{d} ≠ 0. The following conditions on a function f : ℕ → ℂ are equivalent:

1. ∑_{n≥0} f(n)x^{n} = \frac{P (x)}{Q(x)} where, Q(x) = 1 + q_{1}x + q_{2}x^{2} + q_{3}x^{3} + ⋯ + q_{d}x^{d}.

2. For n ≫ 0,

f(n) = ∑_{i=1}^{J} P_{i}(n)λ_{i}^{n},

where 1 + q_{1}x + q_{2}x^{2} + q_{3}x^{3} + ⋯ + q_{d}x^{d} = ∏_{i=1}^{J}(1 − λ_{i}x)^{d_{i}}, the λ_{i}’s are distinct, and P_{i}(n) is a polynomial in n of degree less than d_{i}.

In this section, we construct a collection of rational functions that are fixed by ϕ_{s,t}, and in the next section we use the above lemma to justify that this collection spans the subspace of ℜ consisting of all rational functions that are fixed by ϕ_{s,t}.

The description of all the fixed points of ϕ_{s,t} requires the notion of cyclotomic cosets: given n, r ∈ ℕ with r ≥ 1 such that r and s are relatively prime,

C_{s,r,n} = {s^{i}n mod r : i ∈ ℤ}  (2.4)

is a finite set called the s-cyclotomic coset of n mod r. We will characterize the fixed points ϕ_{s,t} using cyclotomic cosets with a special property. To describe this property, first define

β_{s,t}(k) = t (\frac{s^{k} − 1}{s − 1})  (2.5)

for which we have the following recursive formula:

β_{s,t}(j + 1) = sβ_{s,t}(j) + t.  (2.6)

Definition 2.2. A positive integer r is called distinguished with respect to the pair (s, t) if r and s are relatively prime and

r | β_{s,t}(Ord(s; r)),  (2.7)

where Ord(s; r) represents the smallest positive integer i such that s^{i} ≡ 1 mod r. We say r = 0 is distinguished with respect to (s, t) if and only if t = 0. We denote the set of integers distinguished with respect to (s, t) by Ω(s, t).

Proposition 2.3. For each pair (s, t), the set Ω(s, t) is infinite.

Proof. Since Ω(s, t) ⊂ Ω(s, 1), we need only show that Ω(s, 1) is infinite. Let r be a positive integer such that gcd(r, s(s − 1)) = 1. If α = Ord(s; r), then s^{α} ≡ 1 mod r; that is, r | s^{Ord(s;r)} − 1. Since s^{Ord(s;r)} − 1 is a multiple of (s − 1), and r is relatively prime to (s − 1), it follows that r(s − 1) | s^{Ord(s;r)} − 1. Thus, r | \frac{s^{Ord(s;r)}−1}{s−1} = β_{(s,1)}(Ord(s; r)), and so r is distinguished with respect to (s, 1).

For example, consider

Ω(3, 1) = {1, 4, 5, 7, 10, 11, 13, 14, 17, 19, 20, 23, 25, 28, 29, 31, 34, 35, 37, 38, … }.

From Proposition ??, we see that Ω(3, 1) contains the arithmetic sequences {6n + 1} and {6n + 5}. With a little more effort, one can show that Ω(3, 1) also contains the arithmetic sequences {24n+4}, {24n+10}, {24n+14}, and {24n+20}. The smallest integer in Ω(3, 1) not contained in any of these sequences is 40. Moreover, a calculation shows that 96n + 40, for 0 ≤ n ≤ 5 is in Ω(3, 1), but 616 = 96 · 6 + 40 is not in Ω(3, 1). An interesting question of further study is whether the sets Ω(s, t) have a nice characterization. For example, we might ask whether they can be written as a (possibly infinite) union of arithmetic sequences, as is the case for Ω(2, 1), which consists precisely of all odd natural numbers. However, the example Ω(3, 1) suggests that this may not be the case in general.

A generating set for the collection of fixed points of ϕ_{s,t} will be indexed by s-cyclotomic cosets C_{s,r,n} where r is distinguished with respect to (s, t). Note that by computing

ϕ_{s,t} (\frac{1}{1 − λx}) = \frac{λ^{t}}{1 − λ^{s}x}  (2.8)

we acquire the following formula for the iterates of ϕ_{s,t}:

ϕ_{s,t}^{(k)} (\frac{1}{1 − λx}) = \frac{λ^{β_{s,t}(k)}}{1 − λ^{s^{k}}x}.  (2.9)

For r ≥ 1 and n ∈ ℕ, define

ψ_{s,t,r,n}(x) = ∑_{j=1}^{Ord(s;r)} \frac{ω_{r}^{nβ_{s,t}(j)}}{1 − ω_{r}^{ns^{j}}x} = ∑_{j=1}^{Ord(s;r)} ϕ_{s,t}^{(j)} (\frac{1}{1 − ω_{r}^{n}x}) .  (2.10)

Note that if n = 0, then ψ_{s,t,r,0} = 1/(1−x). If t = 0, then r = 0 is distinguished with respect to (s, t), and we define

ψ_{s,0,0,n}(x) = 1.  (2.11)

Proposition 2.4. If r is distinguished with respect to (s, t), then ψ_{s,t,r,n}(x) is fixed by ϕ_{s,t}.

Proof. If r > 1 is distinguished with respect to (s, t), then

ϕ_{s,t}^{(Ord(s;r)+1)} (\frac{1}{1 − ω_{r}^{n}x}) = ϕ_{s,t} (ϕ_{s,t}^{(Ord(s;r))} (\frac{1}{1 − ω_{r}^{n}x})) = ϕ_{s,t} (\frac{1}{1 − ω_{r}^{n}x}) ,

and so

ϕ_{s,t}(ψ_{s,t,r,n}(x)) = ϕ_{s,t} ( ∑_{j=1}^{Ord(s;r)} ϕ_{s,t}^{(j)} (\frac{1}{1 − ω_{r}^{n}x})) = ( ∑_{j=1}^{Ord(s;r)} ϕ_{s,t}^{(j+1)} (\frac{1}{1 − ω_{r}^{n}x})) = ψ_{s,t,r,n}(x).

Thus ψ_{s,t,r,n}(x) is fixed by ϕ_{s,t}. Since constants are fixed by ϕ_{s,0}, it follows that ψ_{s,0,0,n} is fixed by ϕ_{s,0}. Since r = 0 is distinguished only with respect to t = 0, we have shown the result holds in all possible cases.

3 The Space of Fixed Points of ϕ_{s,t}

We now classify all the fixed points of ϕ_{s,t} for all integers s, t. To do so, we first demonstrate a bijective correspondence between fixed points of ϕ_{s,t} and ϕ_{s,t+u(s−1)} where u is an arbitrary integer.

Lemma 3.1. For all integers s, t, u, the rational function R(x) is a fixed point of ϕ_{s,t} iff x^{−u}R(x) is a fixed point of ϕ_{s,t+u(s−1)}.

Proof. Using equation (??), one can show directly that for any integers s, t, u,

ϕ_{s,t}(R(x)) = x^{u}ϕ_{s,t+(s−1)u}(x^{−u}R(x)),

and so

ϕ_{s,t}(R(x)) = R(x) ⇔ x^{u}ϕ_{s,t+(s−1)u}(x^{−u}R(x)) = R(x)
⇔ ϕ_{s,t+(s−1)u}(x^{−u}R(x)) = x^{−u}R(x).

Given this correspondence, we only have to compute the fixed points of ϕ_{s,t} in case 0 ≤ t ≤ s − 2. Once this is accomplished, to compute the fixed points of ϕ_{s,t} for arbitrary t, we only need to find t′, u such that 0 ≤ t′ ≤ s − 2 and t = t′ + u(s − 1), and then use the correspondence. The following result provides the missing component of this scheme, thus allowing us to compute the fixed points ϕ_{s,t} for any integers s and t.

Proposition 3.2. Suppose s ≥ 2 and 0 ≤ t ≤ s − 2. A rational function is fixed by ϕ_{s,t} if and only if it is a linear combination of the functions ψ_{s,t,r,n}(x) where r is distinguished with respect to (s, t) and n is relatively prime to r.

Proof. We showed in Proposition ?? that if r is distinguished with respect to (s, t), then ψ_{s,t,r,n}(x) is fixed by ϕ_{s,t}, and so every linear combination of such functions must be fixed by ϕ_{s,t}.

To prove the converse, we consider a rational function R(x) fixed by ϕ_{s,t}, and express it as

R(x) = C(x) + \frac{P (x)}{Q(x)}  (3.1)

where C(x), P (x), Q(x) are polynomials such that P (x) and Q(x) are relatively prime with deg P (x) < deg Q(x). Our first goal is to show that the poles of R(x) must be simple. We write

\frac{P (x)}{Q(x)} = ∑_{n=0}^{∞} f(n)x^{n}  (3.2)

where f(n) is the generating function for P (x)/Q(x). Since f(n) = f(sn + t), we have by Lemma ??, f(sn + t) = ∑ P_{i}(sn + t)λ_{i}^{t}(λ_{i}^{s})^{n} and

Q(x) = ∏_{i=1}^{J}(1 − λ_{i}x)^{d_{i}} = ∏_{i=1}^{J}(1 − λ_{i}^{s}x)^{e_{i}},  (3.3)

and so

{λ_{1}, …, λ_{J}} = {λ_{1}^{s}, …, λ_{J}^{s}}.  (3.4)

Thus the set {λ_{1}, ⋯, λ_{J}} is permuted by the map z ↦ z^{s}, and so each λ_{j} is a primitive r_{j}-th root of unity where r_{j} is a positive integer. Moreover, since {λ_{1}, …, λ_{J}} is permuted by the map z ↦ z^{s}, it follows that for each 1 ≤ j ≤ J, there exists a positive integer ℓ such that λ_{j}^{sℓ} = λ_{j} (after applying the map z ↦ z^{s} multiple times). Therefore, λ_{j}^{sℓ−1} = 1, and so r_{j} | sℓ − 1. Thus r_{j} and s are relatively prime.

Let M = lcm(r_{1}, …, r_{j}) and for a ∈ ℕ, define

R_{a} = {m ∈ ℕ : m ≡ a mod M}.

Let f_{a} = f|_{R_{a}} be the restriction of the function f : ℕ → ℂ to the set R_{a}. Then

f_{a}(a + jM) = ∑_{i=1}^{J} P_{i}(a + jM)λ_{i}^{a+jM} = ∑_{i=1}^{J} P_{i}(a + jM)λ_{i}^{a},

and so each f_{a} has a representation as a polynomial in the variable j since λ_{i}^{a} is constant on the set R_{a}. We denote the natural extension of this map to an element of the polynomial ring ℂ[j] by F_{a}. Note that the restriction of F_{a} to ℕ need not be f in general. Our goal is to prove that each F_{a} is a constant function, with corresponding constant denoted by c_{a}. Once this is shown, we have

\frac{P (x)}{Q(x)} = ∑_{n=0}^{∞} f(n)x^{n} = ∑_{a=0}^{M−1} c_{a} ∑_{j=0}^{∞} x^{a+jM} = ∑_{a=0}^{M−1} \frac{c_{a}x^{a}}{1 − x^{M}} ,  (3.5)

and so P (x)/Q(x) is a rational function with only simple poles, as desired.

It remains to show that each polynomial map F_{a} : ℂ → ℂ is a constant function. For each positive integer n, define

S_{n} = {β_{s,t}^{(j)}(n) : j ∈ ℕ}.  (3.6)

We say that a has an infinite cross-section if R_{a} ∩ S_{n} is an infinite set for some n ∈ ℕ. We proceed by considering two cases, depending on whether a has an infinite cross-section or not

Case 1: Suppose a has an infinite cross-section, i.e., R_{a} ∩ S_{n} is an infinite set. Since f(j) = f(sj + t) for all j ∈ ℕ , F_{a} is constant on R_{a} ∩ S_{n}. Since R_{a} ∩ S_{n} is an infinite set, F_{a} is a constant polynomial.

Case 2: Suppose a does not have an infinite cross-section, i.e., R_{a}∩S_{n} is finite for all positive integers n. Then R_{a} ∩ S_{n} must be nonempty for infinitely many values of n. Since there are only finitely many distinct sets of the form R_{b}, it follows that for each S_{n}, there exists b ∈ ℕ such that R_{b} ∩ S_{n} is infinite. Moreover, since there are only finitely many choices for R_{b}, there is at least one b ∈ ℕ such that there exist infinitely many values of n where R_{a} ∩ S_{n} is nonempty and R_{b} ∩ S_{n} is infinite. Since b has an infinite cross-section, an application of Case 1 demonstrates that the restriction of f to R_{b} is the constant function c_{b}. Since f is constant on each S_{n}, the restriction of f to S_{n} is the constant c_{b}. Thus F_{a} achieves the value c_{b} infinitely many times, and so F_{a} must be a constant polynomial.

Thus in either case, we have that F_{a} is a constant polynomial, and so the poles of R must be simple. Using this fact, we can decompose R(x) using partial fractions:

R(x) = C(x) + ∑_{j=1}^{J} \frac{α_{j}}{1 − λ_{j}x}.  (3.7)

Via (??), an application of ϕ_{s,t} yields

R(x) = ϕ_{s,t}(R(x)) = ϕ_{s,t}(C(x)) + ∑_{j=1}^{J} \frac{α_{j}λ_{j}^{t}}{1 − λ_{j}^{s}x}.  (3.8)

Each rational function has a unique decomposition, and since ϕ_{s,t} maps polynomials to polynomials,

C(x) = ϕ_{s,t}(C(x))  (3.9)

and

∑_{j=1}^{J} \frac{α_{j}}{1 − λ_{j}x} = ∑_{j=1}^{J} \frac{α_{j}λ_{j}^{t}}{1 − λ_{j}^{s}x} = ϕ_{s,t} (∑_{j=1}^{J} \frac{α_{j}}{1 − λ_{j}x}) .  (3.10)

If t > 0, it is easy to see that no nonzero polynomial is fixed by ϕ_{s,t}, in which case C(x) = 0. If t = 0, then the only polynomials fixed by ϕ_{s,t} are constant, and so C(x) is a constant multiple of ψ_{s,0,0,n} = 1.

Now we only have left to show that the second summand in (??) is a linear combination of functions of the form ψ_{s,t,r,n}. To do this, we begin by showing that each r_{k} is distinguished with respect to (s, t). We have already shown that r_{k} and s are relatively prime for each k. Using (??), multiple iterations of ϕ_{s,t} to (??) yield

∑_{j=1}^{J} \frac{α_{j}}{1 − λ_{j}x} = ϕ_{s,t}^{(Ord(s;r_{k}))} (∑_{j=1}^{J} \frac{α_{j}}{1 − λ_{j}x}) = ∑_{j=1}^{J} \frac{α_{j}λ_{j}^{β_{s,t}(Ord(s;r_{k}))}}{1 − λ_{j}^{s^{Ord(s;r_{k})}}x} .  (3.11)

The term corresponding to j = k in the first of these three expressions is

\frac{α_{k}}{1 − λ_{k}x},  (3.12)

and the corresponding term in the last of these three expressions is

\frac{α_{k}λ_{k}^{β_{s,t}(Ord(s;r_{k}))}}{1 − λ_{k}^{s^{Ord(s;r_{k})}}x} = \frac{α_{k}λ_{k}^{β_{s,t}(Ord(s;r_{k}))}}{1 − λ_{k}x} .  (3.13)

Thus

λ_{k}^{β_{s,t}(Ord(s;r_{k}))} = 1.  (3.14)

Therefore, r_{k} | β_{s,t}(Ord(s; r_{k})), and so r_{k} is distinguished with respect to (s, t).

Now that we’ve shown that each r_{k} is distinguished with respect to (s, t), group terms in the sum

∑_{j=1}^{J} \frac{α_{j}}{1 − λ_{j}x}  (3.15)

according to the orbits of the map z ↦ z^{s} on the set {λ_{1}, …, λ_{J}}. Since r_{k} | β_{s,t}(Ord(s; r_{k})) for each k, we know that the sum of terms in (??) corresponding to a single orbit must be of the form

O(k) = ∑_{i=1}^{m} ϕ_{s,t}^{(i)} (\frac{α_{k}}{1 − λ_{k}x}) ,  (3.16)

where m is the length of the orbit of λ_{k} under the map z ↦ z^{s}. That is, m is the smallest positive integer such that λ_{k}^{s^{m}} = 1, and so m = Ord(s; r_{k}). Moreover, λ_{k} is a primitive r_{k}-th root of unity, and so it must be of the form λ_{k} = (ω_{r_{k}})^{n} for some n ∈ ℕ such that r_{k} and n are relatively prime. Thus

O(k) = α_{k} ( ∑_{i=1}^{Ord(s;r_{k})} ϕ_{s,t}^{(i)} (\frac{1}{1 − ω_{r_{k}}^{n}x})) = α_{k}ψ_{s,t,r_{k},n}(x),  (3.17)

and so (??), and hence (??), is a linear combination of rational functions of the form ψ_{s,t,r,n}.

It turns out that the collection of rational functions of the form ψ_{s,t,r,n} does not form a basis of fixed points. The lemma below shows that there is redundancy in the collection. Since cyclotomic cosets have many different representations, we must compare the ways in which ψ_{s,t,r,n} and ψ_{s,t,r,n′} are defined for two distinct representations C_{s,r,n} and C_{s,r,n′} of the same coset. Although we have not defined ψ_{s,t,r,n} to be invariant with respect to different representations, they will be the same up a constant multiple.

Lemma 3.3. If C_{s,r,n} = C_{s,r,n′}, then ψ_{s,t,r,n} and ψ_{s,t,r,n′} are scalar multiples of one another.

Proof. With the aid of (??), we compute

ψ_{s,t,r,ns}(x) = ∑_{j=1}^{Ord(s;r)} \frac{ω_{r}^{nsβ_{s,t}(j)}}{1 − ω_{r}^{sns^{j}}x}

= ∑_{j=1}^{Ord(s;r)} \frac{ω_{r}^{n(β_{s,t}(j+1)−t)}}{1 − ω_{r}^{ns^{j+1}}x}

= ω_{r}^{−nt} ∑_{j=1}^{Ord(s;r)} \frac{ω_{r}^{nβ_{s,t}(j+1)}}{1 − ω_{r}^{ns^{j+1}}x}

= ω_{r}^{−nt} ∑_{j=1}^{Ord(s;r)} ϕ_{s,t}^{(j+1)} (\frac{1}{1 − ω_{r}^{n}x})
= ω_{r}^{−nt}ϕ_{s,t}(ψ_{s,t,r,n}(x))
= ω_{r}^{−nt}ψ_{s,t,r,n}(x).

Thus ψ_{s,t,r,s^{i}n} and ψ_{s,t,r,n} are scalar multiples of one another for all i ∈ ℕ. If C_{s,r,n} = C_{s,r,n′}, then for some i ∈ ℕ, we have n′ ≡ s^{i}n mod r. By this equivalence, ψ_{s,t,r,n′} = ψ_{s,t,r,s^{i}n}, and so the result follows.

Using Lemma ??, we can show that if two of functions of the form ψ_{s,t,r,n} have a pole in common, then they are actually the same up to a scalar multiple. The following lemma leads us this result.

Lemma 3.4. Suppose r_{i} is a positive integer that is distinguished with respect to (s, t), and n_{i} is a positive integer relatively prime to r_{i} for i = 1, 2. If ψ_{s,t,r_{1},n_{1}} and ψ_{s,t,r_{2},n_{2}} have a pole in common, then r_{1} = r_{2} and C_{s,r_{1},n_{1}} = C_{s,r_{2},n_{2}}.

Proof. Note that ψ_{s,t,r,n} has poles at ω_{r}^{−ns^{j}} for 0 ≤ j ≤ Ord(s; r); that is, ψ_{s,t,r,n} has poles at ω_{r}^{−c} where c ∈ C_{s,r,n}. Suppose ψ_{s,t,r_{1},n_{1}} and ψ_{s,t,r_{2},n_{2}} have a pole in common; that is, e^{−2πic_{1}/r_{1}} = e^{−2πic_{2}/r_{2}}, where c_{i} ∈ C_{s,r_{i},n_{i}}. Thus, c_{1}/r_{1} −c_{2}/r_{2} ∈ ℤ. Without loss of generality, we can choose 1 ≤ c_{i} < r_{i}, in which case 0 < c_{1}/r_{1} < 1, and so c_{1}/r_{1} = c_{2}/r_{2}. Since gcd(r_{i}, n_{i}) = 1 and c_{i} = s^{j_{i}}n_{i} mod r_{i} for some j_{i} ∈ ℕ, it follows that c_{i} and r_{i} are relatively prime, and so c_{1} = c_{2} and r_{1} = r_{2}. Therefore, s^{j_{1}}n_{1} = s^{j_{2}}n_{2} mod r (where r = r_{1} = r_{2}), and so C_{s,r,n_{1}} = C_{s,r,n_{2}}.

We now precisely describe the redundancy in the collection {ψ_{s,t,r,n}} for fixed s and t. We begin by defining an equivalence relation ∼_{s,r} on (C_{s,r,n} − {0}) by n_{1} ∼_{s,r} n_{2} if C_{s,r,n_{1}} = C_{s,r,n_{2}}. Let Λ_{s,r} be a collection of coset representatives (all chosen to be less than r) of (C_{s,r,n} − {0})/ ∼_{s,r}. That is, Λ_{s,r} is maximal set consisting of positive integers such that no two are in the same cyclotomic coset.

Theorem 3.5. Suppose s ≥ 2 and 0 ≤ t ≤ s − 2. The function 1/(1 − x) together with the collection of all ψ_{s,t,r,n} where r is distinguished with respect to (s, t) and n ∈ Λ_{s,r} form a basis for the set of all rational functions that are fixed points of ϕ_{s,t}.

Proof. The case n = 0 corresponds to the function 1/(1 − x). We now consider the case n > 0. Given an integer r that is distinguished with respect to (s, t), and an integer n that is relatively prime to r, there exists n′ ∈ Λ_{s,r} such that C_{s,r,n} = C_{s,r,n′}, in which case by Lemma ??, ψ_{s,t,r,n} and ψ_{s,t,r,n′} are scalar multiples of one another. Thus, by Proposition ??, this collection spans the space of rational functions fixed by ϕ_{s,t}.

Suppose ψ_{s,t,r_{1},n_{1}} and ψ_{s,t,r_{2},n_{2}} have a pole in common where n_{i} ∈ Λ_{s,r_{i}}. Then by Lemma ??, r_{1} = r_{2} and C_{s,r_{1},n_{1}} = C_{s,r_{2},n_{2}}. Thus by the definition of Λ_{s,r_{1}} = Λ_{s,r_{2}}, n_{1} = n_{2}. Therefore, none of the elements of the collection have a pole in common, and so no nontrivial linear combination of elements of this collection can be zero.

References

[1] G. Boros, J. Little, V. Moll, E. Mosteig, R. Stanley, A map on the space of rational functions, Rocky Mountain Journal of Mathematics. 35 (2005), 1861–1880.

[2] G. Boros, V. Moll, Landen transformations and the integration of rational functions, Mathematics of Computation. 71 (2002), 649–668.

[3] J. Gil, S. Robins, Hecke operators on rational functions. I., Forum Mathematicum. 17 (2005), no. 4, 519–554.

[4] V. Moll, The evaluation of integrals: a personal story, Notices of the AMS. 49 (2002), 311–317.

[5] R. Stanley, Enumerative Combinatorics, Volume 1, Cambridge Studies in Advanced Mathematics, Cambridge University Press, 1997.