Séminaire Lotharingien de Combinatoire 56 (2007), Article B56f

COMBINATORIAL ASPECTS OF ELLIPTIC CURVES

GREGG MUSIKER

Abstract. Given an elliptic curve C, we study here N_{k} = #C(𝔽_{q^{k}}), the number of points of C over the finite field 𝔽_{q^{k}}. This sequence of numbers, as k runs over positive integers, has numerous remarkable properties of a combinatorial flavor in addition to the usual number theoretical interpretations. In particular, we prove that N_{k} = −W_{k}(q, −N_{1}), where W_{k}(q, t) is a (q, t)-analogue of the number of spanning trees of the wheel graph. Additionally we develop a determinantal formula for N_{k}, where the eigenvalues can be explicitly written in terms of q, N_{1}, and roots of unity. We also discuss here a new sequence of bivariate polynomials related to the factorization of N_{k}, which we refer to as elliptic cyclotomic polynomials because of their various properties.

Contents

1. Introduction

2. N_{k} as an alternating sum 3 2.1. The Lucas numbers and a (q, t)-analogue 4 2.2. (q, t)-Wheel polynomials 7 2.3. First proof of Theorem 3: Bijective 8 2.4. Second proof of Theorem 3: Via generating function identities 10 3. More on bivariate Fibonacci polynomials via duality 12 3.1. Duality between the symmetric functions h_{k} and e_{k} 12 3.2. Duality between Lucas and Fibonacci numbers 16 4. Factorizations of N_{k} 19 4.1. Connection to orthogonal polynomials 19 4.2. First proof of Theorem 5: Using orthogonal polynomials 21 4.3. Second proof of Theorem 5: Using the zeta function 23 4.4. Combinatorics of elliptic cyclotomic polynomials 25 4.5. Geometric interpretation of elliptic cyclotomic polynomials 29 5. Conclusions and open problems 30 References 31

1. Introduction

An interesting problem at the cross-roads between combinatorics, number theory, and algebraic geometry, is that of counting the number of points on an algebraic curve over a finite field. Over a finite field, the locus of solutions of an algebraic equation is a discrete subset, but since they satisfy a certain type of algebraic equation this imposes a lot of extra structure beneath the surface. One of the ways to detect this additional structure is by looking at field extensions: the infinite sequence of cardinalities is only dependent on a finite set of data. Specifically the number of points over 𝔽_{q}, 𝔽_{q^{2}}, …, and 𝔽_{q^{g}} will be sufficient data to determine the number of points on a genus g algebraic curve over any other algebraic field extension. This observation motivates the question of how the points over higher field extensions correspond to points over the first g extensions.

This work was supported by the NSF, grant DMS-0500557.

To see this more clearly, we specialize to the case of elliptic curves, where g = 1, and examine the expressions for N_{k}, the number of points on C over 𝔽_{q^{k}}, as functions of q and N_{1}. It follows from the well-known rationality of the zeta function that

(1)  N_{k}(q, N_{1}) = 1 + q^{k} − α_{1}^{k} − α_{2}^{k},

where α_{1} and α_{2} are the two roots of the quadratic 1−(1+q−N_{1})T +qT^{2}. Additionally, we observe, see Theorem 1, that

(2) N_{k}(q, N_{1}) are integral polynomials whose coefficients alternate in sign.

In this paper, we use formulas arising from (1) and (2) to connect elliptic curves to several different areas of combinatorics. Specifically, (1) implies that the family of polynomials 1 + q^{k} − N_{k} are Chebyshev polynomials of the first kind, a wellstudied example of orthogonal polynomials. In Section 4, we describe this perspective in further detail. Alternatively, we can interpret statement (1) as the plethystic expression N_{k} = p_{k}[1+q−α_{1} −α_{2}], where the p_{k}’s are the power symmetric functions. In summary, we exploit both the fields of orthogonal polynomials and symmetric functions to illustrate numerous identities involving the N_{k}’s.

Moreover, we find that the polynomial expressions for N_{k} due to (2) are related to a (q, t)-deformation of the Lucas numbers (Theorem 2), and also lead to a combinatorial interpretation involving spanning trees of the wheel graph (Theorem 3). Thus the aforementioned identities also indicate properties of the Lucas numbers and spanning trees as well.

Using these new combinatorial interpretations for N_{k}, we develop further properties of this sequence, obtaining determinantal formulas (Theorem 5), as well as formulas involving a certain bivariate version of the Fibonacci polynomials (Theorem 4). Another surprising by-product of our analysis is a factorization of N_{k} into a new sequence of polynomials, which we refer to as elliptic cyclotomic polynomials. Both of these families of polynomials are interesting in their own right and have numerous properties which justify their names. We give a geometric interpretation of the elliptic cyclotomic polynomials as Theorem 7 and close with some combinatorial identities involving this new family of expressions.

2. N_{k} as an alternating sum

The zeta function of a curve C is defined to be the exponential generating function

(3)  Z(C, T) = exp ( ∑_{k≥1} N_{k} \frac{T^{k}}{k} ).

A result due to Weil [22] is that the zeta function of a curve is rational with specific formula given as

(4)  Z(C, T) = \frac{(1 − α_{1}T)(1 − α_{2}T) ⋯ (1 − α_{2g}T)}{(1 − T)(1 − qT)}.

Here g is the genus of curve C, and the numerator is sometimes written as L(C, T), a degree 2g polynomial with integer coefficients. Moreover when E is an elliptic curve, Z(E, T) can be expressed as

\frac{1 − (α_{1} + α_{2})T + α_{1}α_{2}T^{2}}{(1 − T)(1 − qT)} .

The zeta function of a curve also satisfies a functional equation which in the elliptic case is simply equivalent to

α_{1}α_{2} = q.

Among other things, (3) and (4) imply that N_{k} = 1+q^{k} −α_{1}^{k} −α_{2}^{k} −⋯−α_{2g}^{k}, which can be written in plethystic notation as p_{k}[1 + q − α_{1} − α_{2}]. We describe symmetric functions and plethystic notation in more depth in Section 3. In the case that E is a curve of genus one and k = 1 we get

α_{1} + α_{2} = 1 + q − N_{1}.

Hence we can rewrite the zeta function Z(E, T) totally in terms of q and N_{1} and as a consequence, all the N_{k}’s are actually dependent on these two quantities. The first few formulas are given below:

N_{2} = (2 + 2q)N_{1} − N_{1}^{2},
N_{3} = (3 + 3q + 3q^{2})N_{1} − (3 + 3q)N_{1}^{2} + N_{1}^{3},
N_{4} = (4 + 4q + 4q^{2} + 4q^{3})N_{1} − (6 + 8q + 6q^{2})N_{1}^{2} + (4 + 4q)N_{1}^{3} − N_{1}^{4},
N_{5} = (5 + 5q + 5q^{2} + 5q^{3} + 5q^{4})N_{1} − (10 + 15q + 15q^{2} + 10q^{3})N_{1}^{2}
+ (10 + 15q + 10q^{2})N_{1}^{3} − (5 + 5q)N_{1}^{4} + N_{1}^{5}.

This data gives rise to the following observation of Adriano Garsia.

Theorem 1.

N_{k} = ∑_{i=1}^{k}(−1)^{i−1}P_{i,k}(q)N_{1}^{i},

where the P_{i,k}’s are polynomials with positive integer coefficients.

This theorem is proved by Garsia using induction and the fact that the sequence of N_{k}’s satisfy a simple recurrence. For the details, see [7, Chap. 7]. This result motivates the combinatorial question: what are the objects that the family of polynomials, {P_{i,k}}, enumerate? We answer this question in due course in multiple ways, thus providing an alternate, combinatorial, proof of Theorem 1.

2.1. The Lucas numbers and a (q, t)-analogue.

Definition 1. Let S_{1}^{(n)} be the circular shift of set S ⊆ {1, 2, …, n} modulo n, i.e., element x ∈ S_{1}^{(n)} if and only if x − 1 ( mod n ) ∈ S. We define the (q, t)-Lucas polynomials to be the sequence of polynomials in variables q and t

(5)  L_{n}(q, t) = ∑_{S⊆\{1,2,...,n\} : S∩S_{1}^{(n)}=∅} q^{#even elements in S} t^{⌊ \frac{n}{2} ⌋−#S}.

Note that this sum is over subsets S with no two numbers circularly consecutive.

These polynomials are a generalization of the sequence of Lucas polynomials L_{n} which have the initial conditions L_{1} = 1, L_{2} = 3 (or L_{0} = 2 and L_{1} = 1) and satisfy the Fibonacci recurrence L_{n} = L_{n−1} + L_{n−2}. The first few Lucas numbers are

1, 3, 4, 7, 11, 18, 29, 47, 76, 123, …

As described in numerous sources, e.g. [1], L_{n} is equal to the number of ways to color an n-beaded necklace black and white so that no two black beads are consecutive. You can also think of this as choosing a subset of {1, 2, …, n} with no consecutive elements, nor the pair 1, n. (We call this circularly consecutive.) Thus letting q and t both equal one, we get by definition that L_{n}(1, 1,) = L_{n}.

We prove the following theorem, which relates our newly defined (q, t)-Lucas polynomials to the polynomials of interest, namely the N_{k}’s.

Theorem 2. We have

(6)  1 + q^{k} − N_{k} = L_{2k}(q, −N_{1})

for all k ≥ 1.

To prove this result it suffices to prove that both sides are equal for k ∈ {1, 2}, and that both sides satisfy the same three-term recurrence relation. Since

L_{2}(q, t) = 1 + q + t

and

L_{4}(q, t) = 1 + q^{2} + (2q + 2)t + t^{2},

we have proven that the initial conditions agree. Note that the sets of (5) yielding the terms of these sums are respectively

{1}, {2}, { } and {1, 3}, {2, 4}, {1}, {2}, {3}, {4}, { }.

It remains to prove that both sides of (6) satisfy the recursion

G_{k+1} = (1 + q − N_{1})G_{k} − qG_{k−1}

for k ≥ 1.

Proposition 1. For the (q, t)-Lucas polynomials L_{k}(q, t) defined as above,

(7)  L_{2k+2}(q, t) = (1 + q + t)L_{2k}(q, t) − qL_{2k−2}(q, t).

Proof. To prove this we actually define an auxiliary set of polynomials, {L̃_{2k}}, such that

L_{2k}(q, t) = t^{k}L̃_{2k}(q, t^{−1}).

Thus recurrence (7) for the L_{2k}’s translates into

(8)  L̃_{2k+2}(q, t) = (1 + t + qt)L̃_{2k}(q, t) − qt^{2}L̃_{2k−2}(q, t)

for the L̃_{2k}’s. The L̃_{2k}’s happen to have a nice combinatorial interpretation also, namely

L̃_{2k}(q, t) = ∑_{S⊆{1,2,...,2k} : S∩S_{1}^{(2k)}=∅} q^{#even elements in S} t^{#S}.

Recall our slightly different description which considers these as the generating function of 2-colored, labeled necklaces. We find this terminology slightly easier to work with. We can think of the beads labeled 1 through 2k + 2 to be constructed from a pair of necklaces; one of length 2k with beads labeled 1 through 2k, and one of length 2 with beads labeled 2k + 1 and 2k + 2.

Almost all possible necklaces of length 2k + 2 can be decomposed in such a way since the coloring requirements of the 2k + 2 necklace are more stringent than those of the pairs. However not all necklaces can be decomposed this way, nor can all pairs be pulled apart and reformed as a (2k + 2)-necklace. For example, if k = 2:

Decomposable →

Not Decomposable ↛

In these figures, the first necklace is decomposable but the second one is not since black beads 1 and 4 would be adjacent, thus violating the rule. It is clear enough that the number of pairs is L̃_{2}(q, t)L̃_{2k}(q, t) = (1 + t + qt)L̃_{2k}(q, t). To get the third term of the recurrence, i.e., qt^{2}L̃_{2k−2}, we must define linear analogues, F̃_{n}(q, t)’s, of the previous generating function. Just as the L̃_{n}(1, 1)’s were Lucas numbers, the F̃_{n}(1, 1)’s are Fibonacci numbers.

Definition 2. The (twisted) (q, t)-Fibonacci polynomials, denoted as F̃_{n}(q, t), are defined as

F̃_{k}(q, t) = ∑_{S⊆{1,2,...,k−1} : S∩(S_{1}^{(k−1)}−{1})=∅} q^{#even elements in S} t^{#S}.

The summands here are subsets of {1, 2, …, k − 1} such that no two elements are linearly consecutive, i.e., we now allow a subset with both the first and last elements. An alternate description of the objects involved are as (linear) chains of k − 1 beads which are black or white with no two consecutive black beads. With these new polynomials at our disposal, we can calculate the third term of the recurrence, which is the difference between the number of pairs that cannot be recombined and the number of necklaces that cannot be decomposed.

Lemma 1. The number of pairs that cannot be recombined into a longer necklace is 2qt^{2}F̃_{2k−2}(q, t).

Proof. We have two cases: either both 1 and 2k + 2 are black, or both 2k and 2k + 1 are black. These contribute a factor of qt^{2}, and imply that beads 2, 2k, and 2k +1 are white, or that 1, 2k − 1, and 2k + 2 are white, respectively. In either case, we are left counting chains of length 2k − 3, which have no consecutive black beads. In one case we start at an odd-labeled bead and go to an evenly labeled one, and the other case is the reverse, thus summing over all possibilities yields the same generating function in both cases. □

Lemma 2. The number of (2k + 2)-necklaces that cannot be decomposed into a 2necklace and a 2k-necklace is qt^{2}F̃_{2k−3}(q, t).

Proof. The only ones that cannot be decomposed are those which have beads 1 and 2k both black. Since such a necklace would have no consecutive black beads, this implies that beads 2, 2k − 1, 2k + 1, and 2k + 2 are all white. Thus we are reduced to looking at chains of length 2k − 4, starting at an odd, 3, which have no consecutive black beads. □

Lemma 3. The difference of the quantity referred to in Lemma 2 from the quantity in Lemma 1 is exactly qt^{2}L̃_{2k−2}(q, t).

Proof. It suffices to prove the relation

qt^{2}L̃_{2k−2}(q, t) = 2qt^{2}F̃_{2k−2}(q, t) − qt^{2}F̃_{2k−3}(q, t),

which is equivalent to

(9)  qt^{2}L̃_{2k−2}(q, t) = qt^{2}F̃_{2k−2}(q, t) + q^{2}t^{3}F̃_{2k−4}(q, t),

since

(10)  F̃_{2k−2}(q, t) = qtF̃_{2k−4}(q, t) + F̃_{2k−3}(q, t).

Note that identity (10) simply comes from the fact that the (2k − 2)nd bead can be black or white. Finally we prove (9) by dividing by qt^{2}, and then breaking it into the cases where bead 1 is white or black. If bead 1 is white, we remove that bead and cut the necklace accordingly. If bead 1 is black, then beads 2 and 2k + 2 must be white, and we remove all three of the beads. □

With this lemma proven, the recursion for the L̃_{2k}’s, hence the L_{2k}’s follows immediately. □

Proposition 2. For an elliptic curve C with N_{k} points over 𝔽_{q^{k}} we have that

1 + q^{k+1} − N_{k+1} = (1 + q − N_{1})(1 + q^{k} − N_{k}) − q(1 + q^{k−1} − N_{k−1}).

Proof. Recalling that for an elliptic curve C we have the identity

N_{k} = 1 + q^{k} − α_{1}^{k} − α_{2}^{k},

we can rewrite the statement of this proposition as

(11)  α_{1}^{k+1} + α_{2}^{k+1} = (α_{1} + α_{2})(α_{1}^{k} + α_{2}^{k}) − q(α_{1}^{k−1} + α_{2}^{k−1}).

Noting that q = α_{1}α_{2} we obtain this proposition after expanding out algebraically the right-hand-side of (11). □

With the proof of Propositions 1 and 2, we have proven Theorem 2.

2.2. (q, t)-Wheel polynomials. Given that the Lucas numbers are related to the polynomial formulas N_{k}(q, N_{1}), a natural question concerns how alternative interpretations of the Lucas numbers can help us better understand N_{k}. As noted in [1], [14], and [18, Seq. A004146], the sequence {L_{2n} − 2} counts the number of spanning trees in the wheel graph W_{n}; a graph which consists of n + 1 vertices, n of which lie on a circle and one vertex in the center, a hub, which is connected to all the other vertices.

We note that a spanning tree T of W_{n} consists of spokes and a collection of disconnected arcs on the rim. Further, since there are no cycles and T is connected, each spoke intersects exactly one arc. (Since it will turn out to be convenient in the subsequent considerations, we make the – somewhat counter-intuitive – convention that an isolated vertex is considered to be an arc of length 1, and more generally, an arc consisting of k vertices is considered as an arc of length k.) We imagine the circle being oriented clockwise, and imagine the tail of each arc being the vertex which is the sink for that arc. In the case of an isolated vertex, the lone vertex is the tail of that arc. Since the spoke intersects each arc exactly once, if an arc has length k, meaning that it contains k vertices, there are k choices of where the spoke and the arc meet. We define the q-weight of an arc to be q^{number of edges between the spoke and the tail}, abbreviating this exponent as spoke − tail distance. We define the q-weight of the tree to be the product of the q-weights for all arcs on the rim of the tree. This combinatorial interpretation motivates the following definition.

Definition 3.

W_{n}(q, t) = ∑_{T a spanning tree of W_{n}} q^{sum of spoke−tail distance in T} t^{# spokes of T} .

Here the exponent of t counts the number of edges emanating from the central vertex, and the exponent of q is as above.

q^{2}t^{3} q^{3}t^{3}

This definition actually provides exactly the generating function that we desired.

Theorem 3.

N_{k} = −W_{k}(q, −N_{1})

for all k ≥ 1.

Notice that this yields an exact interpretation of the P_{i,k} polynomials as follows:

P_{i,k}(q) = ∑_{T a spanning tree of W_{n} with exactly i spokes} q^{sum of spoke−tail distance in T} .

We prove this theorem in two different ways. The first method utilizes Theorem 2 and an analogue of the bijection given in [1] which relates perfect and imperfect matchings of the circle of length 2k and spanning trees of W_{k}. Our second proof uses the observation that we can categorize the spanning trees based on the sizes of the various connected arcs on the rims. Since this categorization corresponds to partitions, this method exploits formulas for decomposing power symmetric function p_{k} into a linear combination of h_{λ}’s, as described in Section 2.4.

2.3. First proof of Theorem 3: Bijective. There is a simple bijection between subsets of {1, 2, …, 2n} with size at most n − 1 as well as no two elements circularly consecutive and spanning trees of the wheel graph W_{n}. We use this bijection to give our first proof of Theorem 3. The bijection is as follows:

Given a subset S of the set {1, 2, …, 2n − 1, 2n} with no circularly consecutive elements, we define the corresponding spanning tree T_{S} of W_{n} (with the correct q and t weight) in the following way:

1) We use the convention that the vertices of the graph W_{n} are labeled so that the vertices on the rim are w_{1} through w_{n}, and the central vertex is w_{0}.

2) We exclude the two subsets which consist of all the odds or all the evens from this bijection. Thus we only look at subsets which contain n − 1 or fewer elements.

3) For 1 ≤ i ≤ n, an edge exists from w_{0} to w_{i} if and only if neither 2i − 2 nor 2i − 1 (element 0 is identified with element 2n) is contained in S.

4) For 1 ≤ i ≤ n, an edge exists from w_{i} to w_{i+1} (w_{n+1} is identified with w_{1}) if and only if element 2i − 1 or element 2i is contained in S.

{ } ⟷

{3} ⟷ {2, 5} ⟷

Proposition 3. Given this construction, T_{S} is in fact a spanning tree of W_{n} and further, tree T_{S} has the same q-weights and t-weights as set S.

Proof. Suppose that set S contains k elements. From our above restriction, we have that 0 ≤ k ≤ n−1. Since S is a k-subset of a 2n element set with no circularly consecutive elements, there are (n − k) pairs {2i − 2, 2i − 1} with neither element in set S, and k pairs {2i − 1, 2i} with one element in set S. Consequently, subgraph T_{S} consists of exactly (n − k) + k = n edges. Since n = (# vertices of W_{n}) − 1, to prove T_{S} is a spanning tree, it suffices to show that each vertex of W_{n} is included. For every oddly-labeled element of {1, 2, …, 2n}, i.e., 2i − 1 for 1 ≤ i ≤ n, we have the following rubric:

1) If (2i − 1) ∈ S then the subgraph T_{S} contains the edge from w_{i} to w_{i+1}.

2) If (2i − 1) ∉ S and additionally (2i − 2) ∉ S, then T_{S} contains the spoke from w_{0} to w_{i}.

3) If (2i − 1) ∉ S and additionally (2i − 2) ∈ S, then T_{S} contains the edge from w_{i−1} to w_{i}. Since one of these three cases happens for all 1 ≤ i ≤ n, vertex w_{i} is incident to an edge in T_{S}. Also, the central vertex, w_{0}, has to be included since by our restriction, 0 ≤ k ≤ n − 1, there are (n − k) ≥ 1 pairs {2i − 2, 2i − 1} which contain no elements of S.

The number of spokes in T_{S} is (n − k) which agrees with the t-weight of a set S with k elements. Finally, we prove that the q-weight is preserved, by induction on the number of elements in the set S. If set S has no elements, the q-weight should be q^{0}, and spanning tree T_{S} will consist of n spokes which also has q-weight q^{0}.

Now given a k element subset S (0 ≤ k ≤ n − 2), it is only possible to adjoin an odd number if there is a sequence of three consecutive numbers starting with an even, i.e., {2i − 2, 2i − 1, 2i}, which is disjoint from S. Such a sequence of S corresponds to a segment of T_{S} where a spoke and tail of an arc intersect. (Note this includes the case of vertex w_{i} being an isolated vertex.)

In this case, subset S′ = S ∪ {2i − 1} corresponds to T_{S′}, which is equivalent to spanning tree T_{S} except that one of the spokes w_{0} to w_{i} has been deleted and replaced with an edge from w_{i} to w_{i+1}. The arc corresponding to the spoke from w_{i} will now be connected to the next arc, clockwise. Thus the distance between the spoke and the tail of this arc will not have changed, hence the q-weight of T_{S′} will be the same as the q-weight of T_{S}.

Alternatively, it is only possible to adjoin an even number to S if there is a sequence {2i − 1, 2i, 2i + 1} which is disjoint from S. Such a sequence of S corresponds to a segment of T_{S} where a spoke meets the end of an arc. (Note this includes the case of vertex w_{i} being an isolated vertex.)

Here, subset S′′ = S ∪ {2i} corresponds to T_{S′′}, which is equivalent to spanning tree T_{S} except that one of the spokes w_{0} to w_{i+1} has been deleted and replaced with an edge from w_{i} to w_{i+1}. The arc corresponding to the spoke from w_{i+1} will now be connected to the previous arc, clockwise. Thus the cumulative change to the total distance between spokes and the tails of arcs will be an increase of one, hence the q-weight of T_{S′′} will be q^{1} times the q-weight of T_{S}.

Since any subset S can be built up this way from the empty set, our proof is complete via this induction. □

Since the two sets we excluded, of size k had (q, t)-weights q^{0}t^{0} and q^{k}t^{0} respectively, we have proven Theorem 3.

2.4. Second proof of Theorem 3: Via generating function identities. For our second proof of Theorem 3, we consider writing the zeta function as an ordinary generating function instead, i.e.,

(12)  Z(C, T) = 1 + ∑_{k≥1} H_{k}T^{k}.

In such a form, the H_{k}’s are positive integers which enumerate the number of effective C(𝔽_{q})-divisors of degree k, as noted in several places, such as [13].

Proposition 4.

(13)  N_{k} = ∑_{λ⊢k}(−1)^{l(λ)−1} \frac{k}{l(λ)}\binom{l(λ)}{d_{1}, d_{2}, … d_{m}} ∏_{i=1}^{l(λ)} H_{λ_{i}}.

Proof. Comparing formulas (3) and (12) for Z(C, T) and taking logarithms, we obtain

\frac{N_{k}}{k} = log Z(C, T)|_{T^{k}} = log (1 + ∑_{n≥1} H_{n}T^{n})|_{T^{k}}

= ∑_{m≥1} \frac{(−1)^{m−1}( ∑_{n=1}^{k} H_{n}T^{n})^{m}}{m} |_{T^{k}}.

To obtain the coefficient of T^{k} in

(14)  (H_{1}T + H_{2}T^{2} + ⋯ + H_{k}T^{k})^{m},

we first select a partition of k with length ℓ(λ) = m. In other words, λ is a vector of positive integers satisfying λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{m}. Each occurrence of λ_{i} = j in this partition corresponds to choosing summand H_{j}T^{j} in the ith term in product (14). Secondly, since the order of these terms does not matter, we include multinomial coefficients. Finally, multiplying through by k yields formula (13) for N_{k}. □

Remark 1. The same manipulations done above for the generating functions are analogous to identities which relate the power symmetric functions and homogeneous symmetric functions. See for example [5], [12], or [20, pg. 21]. This is no coincidence, and in particular the terminology of plethysm provides a rigorous connection between symmetric functions and the enumeration of points on curves. See Section 3 below, [7], or [15] for more details on plethysm and this connection.

Remark 2. The above algebraic reasoning can also be translated into a combinatorial description of how points on C over 𝔽_{q^{k}} can be enumerated using inclusion-exclusion, and points over smaller extension fields. See [15, Chap. 4] for more details.

We now specialize to the case of g = 1. Here we can write H_{k} in terms of N_{1} and q. We expand the series

(15)  Z(E, T) = \frac{1 − (1 + q − N_{1})T + qT^{2}}{(1 − T)(1 − qT)} = 1 + \frac{N_{1}T}{(1 − T)(1 − qT)}

with respect to T, and obtain H_{0} = 1 and H_{k} = N_{1}(1 + q + q^{2} + ⋯ + q^{k−1}) for k ≥ 1. Plugging these into formula (13), we get polynomial formulas for N_{k} in terms of q and N_{1}

N_{k} = ∑_{λ⊢k}(−1)^{l(λ)−1} \frac{k}{l(λ)}\binom{l(λ)}{d_{1}, d_{2}, … d_{k}}( ∏_{i=1}^{l(λ)}(1 + q + q^{2} + ⋯ + q^{λ_{i}−1}))N_{1}^{l(λ)}.

Consequently, Theorem 3 is true if and only if we can replace N_{1} with −t and then multiply by (−1) and get a true expression for W_{k}, the (q, t)-weighted number of spanning trees on the wheel graph W_{k}. We thus provide the following combinatorial argument for the required formula.

Proposition 5.

(16)  W_{k} = ∑_{λ⊢k} \frac{k}{l(λ)}\binom{l(λ)}{d_{1}, d_{2}, … d_{k}}( ∏_{i=1}^{l(λ)}(1 + q + q^{2} + ⋯ + q^{λ_{i}−1}))t^{l(λ)}.

Proof. We construct a spanning tree of W_{k} from the following choices: First we choose a partition λ = 1^{d_{1}}2^{d_{2}} ⋯ k^{d_{m}} of k. We let this dictate how many arcs of each length occur, i.e., we have d_{1} isolated vertices, d_{2} arcs of length 2, etc. Note that this choice also dictates the number of spokes, which is equal to the number of arcs, i.e., the length of the partition.

Second, we pick an arrangement of the l(λ) arcs on the circle. After picking one arc to start with, without loss of generality since we are on a circle, we have

\frac{1}{l(λ)}\binom{l(λ)}{d_{1}, d_{2}, … d_{m}}

choices for such an arrangement. Third, we pick which vertex w_{i} of the rim to start with. There are k such choices. Fourth, we pick where the l(λ) spokes actually intersect the arcs. There are |arc| choices for each arc, and the q-weight of this sum is (1 + q + q^{2} + ⋯ + q^{|arc|}) for each arc. Summing up all the possibilities yields (16) as desired. □

Thus we have given a second proof of Theorem 3.

3. More on bivariate Fibonacci polynomials via duality

In this section we explore further properties of various sequences of coefficients arising from the zeta function of a curve, and also more properties regarding bivariate Fibonacci polynomials. Our tools for such investigations consists of two different manifestations of duality.

3.1. Duality between the symmetric functions h_{k} and e_{k}. Given the usefulness of symmetric functions in discovering the identities described by Propositions 4 and 5, we now illustrate further applications of the plethystic view of the zeta function.

The symmetric functions that we utilize in this paper are the power symmetric functions p_{k}, the complete homogeneous symmetric functions h_{k}, and the elementary symmetric functions e_{k}. Given the alphabet {x_{1}, x_{2}, …, x_{n}}, each of these can be written as

p_{k} = x_{1}^{k} + x_{2}^{k} + ⋯ + x_{n}^{k},
h_{k} = ∑_{i_{1}+i_{2}+···+i_{n}=k^{0≤i_{1},i_{2},...,in≤k}} x_{1}^{i_{1}}x_{2}^{i_{2}} ⋯ x_{n}^{i_{n}}, and

e_{k} = ∑_{1≤i_{1}<i_{2}<···<i_{k}≤n} x_{i_{1}}x_{i_{2}} ⋯ x_{i_{k}}.

In general, a plethystic substitution of a formal power series F (t_{1}, t_{2}, …) into a symmetric polynomial A(x), denoted as A[E], is obtained by setting

A[E] = Q_{A}(p_{1}, p_{2}, …)|_{p_{k}→E(t_{1}^{k},t_{2}^{k},...)},

where Q_{A}(p_{1}, p_{2}, …) gives the expansion of A in terms of the power sums basis {p_{α}}_{α}. The main example of this technique that we use is N_{k} = p_{k}[1+q −α_{1} −α_{2} −⋯−α_{2g}] for a genus g curve.

To begin, we use the following well-known symmetric function identity

∏_{k∈I} \frac{1}{1 − t_{k}T} = exp ( ∑_{n≥1} p_{n} \frac{T^{n}}{n} )

= ∑_{n≥0} h_{n}T^{n}

= \frac{1}{∑_{n≥0}(−1)^{n}e_{n}T^{n}} ,

where h_{n}, p_{n}, and e_{n} are symmetric functions in the variables {t_{k}}_{k∈I}. [20, pgs. 21, 296] The zeta function Z(C, T) is equal to all of these for a certain choice of {t_{k}}_{k∈I} and consequently, we get that

(17)  Z(C, T) = \frac{1}{∑_{k≥0}(−1)^{k}E_{k} · T^{k}} ,

where E_{k} = e_{k}[1 + q − α_{1} − α_{2} − ⋯ − α_{2g}].

Remark 3. Like the N_{k}’s and H_{k}’s, the E_{k}’s also have an algebraic geometric interpretation, namely E_{k} equals the signed number of positive divisors D of degree k on curve C such that no prime divisor appears more than once in D. This follows from the reciprocity between h_{k} and e_{k} which is analogous to the reciprocity between choose and multi-choose, i.e., choice with replacement.

Recall that in Section 2.1, we defined F̃_{k}(q, t), i.e., the twisted (q, t)-Fibonacci polynomials. Here we define F_{k}(q, t), an alternative bivariate analogue of the Fibonacci numbers. The definition of F_{k}(q, t) is identical to that of F̃_{k}(q, t) except for the weighting of parameter t.

Definition 4. We define the (q, t)-Fibonacci polynomials to be the sequence of polynomials in variables q and t given by

F_{k}(q, t) = ∑_{S⊆\{1,2,...,k−1\} : S∩(S_{1}^{(k−1)}−\{1\})=∅} q^{#even elements in S} t^{⌈ \frac{k}{2} ⌉−#S}.

From this definition we obtain the following formulas for the E_{k}’s in the elliptic case.

Theorem 4. If C is a genus one curve, and the E_{k}’s are as above, then for n ≥ 1, E_{−n} = 0, E_{0} = 1, and

E_{n} = (−1)^{n}F_{2n−1}(q, −N_{1}),

where E_{k} and F_{k}(q, t) are as defined above.

The expansions for the first several E_{k}’s, i.e., F_{2k−1}(q, t)’s, are given below.

E_{1} = N_{1},
E_{2} = −(1 + q)N_{1} + N_{1}^{2},
E_{3} = (1 + q + q^{2})N_{1} − (2 + 2q)N_{1}^{2} + N_{1}^{3},
E_{4} = −(1 + q + q^{2} + q^{3})N_{1} + (3 + 4q + 3q^{2})N_{1}^{2} − (3 + 3q)N_{1}^{3} + N_{1}^{4},

E_{5} = (1 + q + q^{2} + q^{3} + q^{4})N_{1} − (4 + 6q + 6q^{2} + 4q^{3})N_{1}^{2} + (6 + 9q + 6q^{2})N_{1}^{3}
− (4 + 4q)N_{1}^{4} + N_{1}^{5}.

Before proving Theorem 4 we develop two key propositions.

Proposition 6. F_{2n+1}(q, t) = (1 + q + t)F_{2n−1}(q, t) − qF_{2n−3}(q, t) for n ≥ 2.

Proof. This follows the similar logic as the proof of Proposition 1 except we can use a more direct method. (One can use the t-weighting of the twisted (q, t)-Fibonacci polynomials instead to see this recursion more clearly, but we omit this detour.) The polynomial F_{2n+1} is a (q, t)-enumeration of the number of chains of 2n beads, with each bead either black or white, and no two consecutive beads both black. Similarly (1 + q + t)F_{2n−1} enumerates the concatenation of such a chain of length 2n − 2 with a chain of length 2. One can recover a legal chain of length 2n this way except in the case where the (2n − 2)nd and (2n − 1)st beads are both black. Such cases are enumerated by qF_{2n−3} and this completes the proof. □

Proposition 7. (−1)^{n+1}E_{n+1} = (1 + q − N_{1})(−1)^{n}E_{n} − q(−1)^{n−1}E_{n−1} for n ≥ 2.

Proof. One can prove this via plethysm, but it also follows directly from the generating function for the E_{n}’s which is given by

∑_{n≥0}(−1)^{n}E_{n}T^{n} = \frac{(1 − T)(1 − qT)}{1 − (1 + q − N_{1})T + qT^{2}} .

The denominator of this series, also known as the series’ characteristic polynomial, yields the desired linear recurrence for the coefficients of T^{n+1}, whenever n+1 exceeds the degree of the numerator. □

With these two propositions verified, we can also now prove Theorem 4.

Proof of Theorem 4. It is clear that E_{1} = −F_{1}(q, −N_{1}), E_{2} = F_{3}(q, −N_{1}), and E_{3} = −F_{5}(q, −N_{1}). Propositions 6 and 7 show that both satisfy the same recurrence relations. Thus we have verified that

E_{n} = (−1)^{n}F_{2n−1}(q, −N_{1}).
□

Remark 4. We can utilize plethysm and obtain results of a similar flavor to Proposition 7, for example see Lemma 4 below. With this result in mind, we obtain the following table of symmetric function e_{k} and h_{k} in terms of various alphabets.

poly. \ alphabet 1 + q − α_{1} − α_{2}  1 + q  α_{1} + α_{2}
e_{k}  E_{k}  e_{1} = 1 + q, e_{2} = q e_{1} = 1 + q − N_{1}, e_{2} = q

h_{k}  H_{k}  1 + q + ⋯ + q^{k}  (−1)^{k}E_{k+1}/N_{1}

Notice that the formulas for e_{k}[1 + q] and h_{k}[1 + q] are precisely the N_{1} = 0 cases of e_{k}[α_{1} + α_{2}] and h_{k}[α_{1} + α_{2}]. This should come at no surprise since 1 and q are the two roots of T^{2} − (1 + q)T + q.

Lemma 4. Letting E_{k} be defined as e_{k}[1 + q − α_{1} − α_{2}], where α_{1} and α_{2} are roots of T^{2} − (1 + q − N_{1})T + q, we obtain

h_{k}[α_{1} + α_{2}] = (−1)^{k}E_{k+1}/N_{1}.

Proof. We have for n ≥ 2 that

N_{1}E_{n} = E_{n+1} + (1 + q)E_{n} + qE_{n−1}

since (−1)^{n+1}E_{n+1} = (1+q−N_{1})(−1)^{n}E_{n}−q(−1)^{n−1}E_{n−1} by Proposition 7. However, by

e_{k}[A − B] = ∑_{i=0}^{k} e_{i}[A](−1)^{k−i}h_{k−i}[B],

we get

E_{n+1} = (−1)^{n+1}(h_{n+1}[α_{1} + α_{2}] − (1 + q)h_{n}[α_{1} + α_{2}] + qh_{n−1}[α_{1} + α_{2}])

using A = 1 + q and B = α_{1} + α_{2}. After verifying initial conditions and comparing with

(−1)^{n+1}E_{n+1} = (−1)^{n+1}E_{n+2}/N_{1} − (−1)^{n}(1 + q)E_{n+1}/N_{1} + (−1)^{n−1}qE_{n}/N_{1},

we get

h_{n+1}[α_{1} + α_{2}] = (−1)^{n+1}E_{n+2}/N_{1}

by induction. □

We apply the above H_{k}–E_{k} (i.e., h_{k}–e_{k}) duality to obtain an exponential generating function for the weighted number of spanning trees of the wheel graph,

W (q, N_{1}, T) = exp ( ∑_{k≥1} W_{k}(q, N_{1})\frac{T^{k}}{k} ).

Using W_{k} = −N_{k}|_{N_{1}→−N_{1}}, and the fact this is an exponential, we use (15) to obtain

W (q, N_{1}, T) = \frac{1}{1 − \frac{N_{1}T}{(1−qT)(1−T)}} = \frac{(1 − qT)(1 − T)}{1 − (1 + q + N_{1})T + qT^{2}} .

Also, rewriting W (q, t, T)as an ordinary generating function, we get

W (q, t, T) = ∑_{k≥0} E_{k}|_{N_{1}→−N_{1}}(−T)^{k} = 1 + ∑_{k≥1} F_{2k−1}(q, t)T^{k}.

We summarize our results as the following dictionary between elliptic curves and spanning trees accordingly.

Elliptic Curves  Spanning Trees
Generating Function  \frac{1−(1+q−N_{1})T +qT^{2}}{(1−qT)(1−T)}  \frac{(1−qT)(1−T)}{1−(1+q+N_{1})T +qT^{2}}
Factors of 1 − (1 + q ∓ N_{1})T + qT^{2}  (1 − α_{1}T)(1 − α_{2}T)  (1 − β_{1}T)(1 − β_{2}T)
N_{k} (resp. W_{k} )  p_{k}[1 + q − α_{1} − α_{2}]  p_{k}[−1 − q + β_{1} + β_{2}]
H_{k} = N_{1}(1 + q + ⋯ + q^{k−1})  h_{k}[1 + q − α_{1} − α_{2}]  (−1)^{k−1}e_{k}[−1 − q + β_{1} + β_{2}]
(−1)^{k}E_{k} = F_{2k−1}(q, ∓N_{1})  (−1)^{k}e_{k}[1 + q − α_{1} − α_{2}]  h_{k}[−1 − q + β_{1} + β_{2}]

3.2. Duality between Lucas and Fibonacci numbers. In addition to the above discussion of how H_{k} and E_{k} are dual, this dictionary also highlights a comparison between elliptic curve–spanning tree duality and duality between Lucas numbers and Fibonacci numbers. As an application, we obtain a formula for E_{k}, i.e., F_{2k−1}(q, t), in terms of the polynomial expansion for the L_{2k}(q, t)’s. If we recall our definition of P_{i,k}’s such that N_{k} = ∑_{i=1}^{k}(−1)^{i+1}P_{i,k}(q)N_{1}^{i}, or equivalently L_{2k}(q, t) = 1 + q^{k} + ∑_{i=1}^{k} P_{i,k}(q)t^{i}, then we have the following identity.

Proposition 8. We have

E_{k} = ∑_{i=1}^{k} \frac{(−1)^{k+i} · i}{k} P_{i,k}(q)N_{1}^{i}.

Proof. We use the identities as above, and the fact that \frac{1}{Z(E,T)} = ∑_{n≥0}(−1)^{n}E_{n}T^{n}. Thus we have

∑_{n≥1}(−1)^{n}E_{n}T^{n} = \frac{1}{Z(E, T)} − 1 = \frac{1}{1 + \frac{N_{1}T}{(1−qT)(1−T)}} − 1

= ∑_{n≥1}(−1)^{n}(\frac{N_{1}T}{(1 − qT)(1 − T)})^{n}

= −N_{1} \frac{∂}{∂N_{1}} ∑_{n≥1} \frac{(−1)^{n−1}}{n} (\frac{N_{1}T}{(1 − qT)(1 − T)})^{n}

= −N_{1} \frac{∂}{∂N_{1}} ( log (1 + \frac{N_{1}T}{(1 − qT)(1 − T)}))

= −N_{1} \frac{∂}{∂N_{1}} log (Z(E, T)),

which equals −N_{1} \frac{∂}{∂N_{1}} ( ∑_{k≥1} \frac{N_{k}}{k} T^{k}). Rewriting the N_{k}’s using the polynomial for-

mulas of Theorem 1, we have

∑_{n≥1}(−1)^{n}E_{n}T^{n} = −N_{1} \frac{∂}{∂N_{1}} ( ∑_{k≥1} \frac{1}{k} ∑_{i=1}^{k}(−1)^{i−1}P_{i,k}(q)N_{1}^{i}T^{k})

= ∑_{k≥1} ∑_{i=1}^{k} \frac{i}{k} (−1)^{i}P_{i,k}(q)N_{1}^{i}T^{k}.

Comparing the coefficients of T^{k} on both sides completes the proof. □

Proposition 8 can also be given a combinatorial proof by the following lemma which contrasts the circular nature of our combinatorial interpretation for the Lucas numbers with the linear nature of the Fibonacci numbers.

Lemma 5. For 1 ≤ i ≤ k and 0 ≤ j ≤ i, we have the number, which we denote as c_{i,j}, of subsets S_{1} of {1, 2, …, 2k} with k − i − j odd elements, j even elements, and no two elements circularly consecutive equals

\frac{k}{i} ·#(subsets S_{2} of \{1, 2, …, 2k−2\} with k−i−j odd elements, j even elements,

and no two elements consecutive).

This notation might seem non-intuitive, but we use these indices so that the total number of elements is k − i and the number of even elements is j. Thus the number of subsets S_{1} (respectively S_{2}) directly describes the coefficient of q^{j}t^{i} in L_{2k}(q, t) (respectively F_{2k−1}(q, t)).

Proof. To prove this result we note that there is a bijection between the number of subsets of the first kind that do not contain 2k − 1 or 2k and those of the second kind. Thus it suffices to show that the number of sets S_{1} which do contain element 2k − 1 or 2k is precisely fraction \frac{k−i}{k} of all sets S_{1} satisfying the above hypotheses.

Circularly shifting every element of set S_{1} by an even amount r, i.e., ℓ ↦ ℓ + r − 1 (mod 2k) + 1, does not affect the number of odd elements and even elements. Furthermore, out of the k possible even shifts, (k − i) of the sets, i.e., the cardinality of set S_{1}, will contain 2k − 1 or 2k. This follows since for a given element ℓ there is exactly one shift which makes it 2k−1 (or 2k) if ℓ is odd (or even), respectively. Since elements cannot be consecutive, there is no shift that sends two different elements to both 2k − 1 and 2k simultaneously and thus we get the full (k − i) possible shifts. □

Using this relationship, we can derive formulas involving binomial coefficients for P_{i,k}(q) using our combinatorial interpretation for the (q, t)-Lucas polynomials and (q, t)-Fibonacci polynomials.

Proposition 9. For k ≥ 1 and 1 ≤ i ≤ k, we have

P_{i,k}(q) = ∑_{j=0}^{i} \frac{k}{i} \binom{k − 1 − j}{i − 1}\binom{i + j − 1}{j} q^{j}.

Proof. See [23, Theorem 2.2] or [16, Theorem 3] which show by algebraic and combinatorial arguments, respectively, that the number of ways to choose a subset S ⊂ {1, 2, …, 2n} such that S contains q odd elements, r even elements, and no consecutive elements is

\binom{n − r}{q}\binom{n − q}{r}.

Letting n = k − 1, q = k − i − j and r = j, we obtain

\frac{i}{k} P_{i,k}(q) = F_{2k−1}(q, N_{1})|_{N_{1}^{i}} = ∑_{j=0}^{i} \binom{k − 1 − j}{i − 1}\binom{i + j − 1}{j}q^{j}.

□

Corollary 1. We have

N_{k}(q, N_{1}) = ∑_{i=1}^{k} ∑_{j=0}^{i} \frac{(−1)^{i+1} · k}{i} \binom{k − 1 − j}{i − 1}\binom{i + j − 1}{j}N_{1}^{i} q^{j}.

and

E_{k} = ∑_{i=1}^{k} ∑_{j=0}^{i}(−1)^{k+i} \binom{k − 1 − j}{i − 1}\binom{i + j − 1}{j}N_{1}^{i} q^{j}.

Remark 5. From the proof in Section 2.4, we have that

W_{k}(q, N_{1}) = ∑_{λ⊢k} \frac{k}{l(λ)}\binom{l(λ)}{d_{1}, d_{2}, … d_{r}}( ∏_{i=1}^{l(λ)}(1 + q + q^{2} + ⋯ + q^{λ_{i}−1}))N_{1}^{l(λ)}

= ∑_{i=1}^{k} \frac{k}{i} ( ∑_{l(λ)=i^{λ⊢k}} \binom{i}{d_{1}, d_{2}, … d_{r}} ∏_{j=1}^{i}(1 + q + q^{2} + ⋯ + q^{λ_{j}−1}))N_{1}^{i}

which implies also that

P_{i,k}(q) = \frac{k}{i} ∑_{l(λ)=i^{λ⊢k}} \binom{i}{d_{1}, d_{2}, … d_{r}} ∏_{j=1}^{i}(1 + q + q^{2} + ⋯ + q^{λ_{j}−1}).

Comparing the coefficients of this identity with the coefficients in Proposition 9 seems to give a combinatorial identity that seems interesting in its own right.

4. Factorizations of N_{k}

We now introduce a family of k-by-k matrices M_{k} which, for elliptic curves, yield a determinantal formula for N_{k} in terms of q and N_{1}.

Theorem 5. Let M_{1} = [−N_{1}], M_{2} = [\begin{matrix}1 + q − N_{1} & −1 − q \\ −1 − q & 1 + q − N_{1} \end{matrix}], and for k ≥ 3, let

M_{k} be the k-by-k “three-line” circulant matrix

[\begin{matrix}1 + q − N_{1} & −1 & 0 & … & 0 & −q \\ −q & 1 + q − N_{1} & −1 & 0 & … & 0 \\ … & … & … & … & … & … \\ 0 & … & −q & 1 + q − N_{1} & −1 & 0 \\ 0 & … & 0 & −q & 1 + q − N_{1} & −1 \\ −1 & 0 & … & 0 & −q & 1 + q − N_{1} \end{matrix}] .

The sequence of integers N_{k} = #C(𝔽_{q^{k}}) satisfies the relation

N_{k} = − det M_{k} for all k ≥ 1.

We provide two proofs of this theorem, one which utilizes the three term recurrence from Section 2.1, and one which introduces a new sequence of polynomials which are interesting in their own right.

4.1. Connection to orthogonal polynomials. Recall from the zeta function of an elliptic curve, Z(E, T), we derived a three term recurrence relation for the sequence {G_{k} = 1 + q^{k} − N_{k}}:

(18)  G_{k+1} = (1 + q − N_{1})G_{k} − qG_{k−1}.

Such a relation is indicative of an interpretation of the (1 + q^{k} − N_{k})’s as a sequence of orthogonal polynomials. In particular, any sequence of orthogonal polynomials, {P_{k}(x)}, satisfies

(19)  P_{k+1}(x) = (a_{k}x + b_{k})P_{k}(x) + c_{k}P_{k−1}(x),

where a_{k}, b_{k} and c_{k} are constants that depend on k ∈ ℕ. Additionally, it is customary to initialize P_{−k}(x) = 0, P_{0}(x) = 1, and P_{1}(x) = a_{0}x + b_{0}.

Since we can think of the bivariate N_{k}(q, N_{1}) as univariate polynomials in variable N_{1} with constants from field ℚ(q), it follows that recurrence (18) is a special case of recurrence (19), therefore {P_{k}(x)}_{k=1}^{∞} = {(1 + q^{k} − N_{k})(N_{1})}_{k=1}^{∞} are a family of orthogonal polynomials. In particular, we plug in the following values for the a_{k}, b_{k}, and c_{k}’s:

a_{k} = −1  for k ≥ 0
b_{k} = 1 + q  for k ≥ 0,
c_{1} = −2q  and
c_{k} = −q  for k ≥ 2.

(Note that we take c_{1} to be −2q since G_{0} = 1+q^{0} −N_{0} = 2, but we wish to normalize so that P_{0}(x) = 1.)

In fact, the family {1+q^{k} −N_{k}}_{k=1}^{∞} can be described in terms of a classical sequence of orthogonal polynomials. Namely T_{k}(x) denotes the kth Chebyshev (Tchebyshev) polynomials of the first kind, which are defined as cos(kθ) written out in terms of x such that θ = arccos x. Equivalently, we can define T_{k}(x) as the expansion of α^{k} + β^{k} in terms of powers of cos θ, where

α = cos θ + i sin θ
β = cos θ − i sin θ.

Theorem 6. Considering the (1 + q^{k} − N_{k})’s as univariate polynomials in N_{1} over the field ℚ(q), we obtain

1 + q^{k} − N_{k} = 2q^{k/2}T_{k}((1 + q − N_{1})/2q^{1/2}).

Proof. We note that Chebyshev polynomials satisfy initial conditions T_{0}(x) = 1, and T_{1}(x) = x and the three-term recurrence

T_{k+1}(x) = 2xT_{k}(x) − T_{k−1}(x)

for k ≥ 1 since

T_{k+1}(x) = α^{k+1} + β^{k+1}
= (α + β)(α^{k} + β^{k}) − αβ(α^{k−1} + β^{k−1})
= 2 cos θ T_{k}(x) − T_{k−1}(x)
= 2xT_{k}(x) − T_{k−1}(x).

Let x = \sqrt[\frac{1+q−N_{1}}{2}]{q}. Clearly Theorem 6 holds for k = 1, and additionally, by Proposition 1, the \frac{1+q^{k}−N_{k}}{2q^{k/2}} ’s satisfy the same recurrence as the T_{k}(x)’s. Namely

\frac{1 + q^{k+1} − N_{k+1}}{2q^{(k+1)/2}} = \frac{(1 + q − N_{1})(1 + q^{k} − N_{k}) − q(1 + q^{k−1} − N_{k−1})}{2q^{(k+1)/2}}

= 2(\frac{1 + q − N_{1}}{2q^{1/2}} )(\frac{1 + q^{k} − N_{k}}{2q^{k/2}} ) − (\frac{1 + q^{k−1} − N_{k−1}}{2q^{(k−1)/2}} ).

□

Another way to foresee the appearance of Chebyshev polynomials is by noting that in the case that we plug in q = 0 or q = 1, we obtain a family of univariate polynomials Ñ_{k} with the property Ñ_{mk} = Ñ_{m}(Ñ_{k}) = Ñ_{k}(Ñ_{m}). It is a fundamental theorem of Chebyshev polynomials that families of univariate polynomials with such a property are very restrictive. In particular, from [2] as described on page 33 of [4]: If {Ñ_{k}} is a sequence of integral univariate polynomials of degree k with the property

Ñ_{mn} = Ñ_{m}(Ñ_{n}) = Ñ_{n}(Ñ_{m})

for all positive integers m and n, then Ñ_{k} must either be a linear transformation of (1) x^{k} or

(2) T_{k}(x), the Chebyshev polynomial of the first kind, where a linear transformation of a polynomial f(x) is of the form

A · f((x − B)/A) + B or equivalently (f(\overline{A}x + \overline{B}) − \overline{B})/\overline{A}.

In particular, we get formulas for W_{k}(0, N_{1}) and W_{k}(1, N_{1}) (respectively N_{k}(0, N_{1}) and N_{k}(1, N_{1})) which are indeed linear transformations of x^{k} and T_{k}(x) respectively.

Proposition 10. We have

(20)  N_{k}(0, N_{1}) = −(1 − N_{1})^{k} + 1,
(21)  N_{k}(1, N_{1}) = −2T_{k}(−N_{1}/2 + 1) + 2.

Proof. The coefficient of N_{1}^{m} in W_{k}(0, N_{1}) is the number of directed rooted spanning trees of W_{k} with m spokes and arcs always directed counter-clockwise. In particular, it is only the placement of the spokes that matter at this point since the placement of the arcs is now forced. Thus the coefficient of N_{1}^{m} in W_{k}(0, N_{1}) is \binom{k}{m} for all 1 ≤ m ≤ k. Thus the generating function W_{k}(0, N_{1}) satisfies

W_{k}(0, N_{1}) = (1 + N_{1})^{k} − 1

since the constant term of W_{k}(0, N_{1}) is zero. Use of the relation N_{k}(q, N_{1}) = −W_{k}(q, −N_{1}) completes the proof in the q = 0 case. We also note that −(1 − x)^{k} + 1 is a linear transformation of x^{k} via A = −1 and B = 1. The case for q = 1 is a corollary of Theorem 6. □

4.2. First proof of Theorem 5: Using orthogonal polynomials. As an application of Theorem 6, we use the theory of orthogonal polynomials to learn properties of the (1 + q^{k} − N_{k})’s. For example, one of the properties of a sequence of orthogonal polynomials is an interpretation as the determinants of a family of tridiagonal k-byk matrices.

Proposition 11. We have

1 + q^{k} − N_{k}

= det [\begin{matrix}1 + q − N_{1} & −2q & 0 & 0 & 0 & 0 \\ −1 & 1 + q − N_{1} & −q & 0 & 0 & 0 \\ 0 & −1 & 1 + q − N_{1} & −q & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ... & 0 \\ 0 & 0 & 0 & ⋯ & 1 + q − N_{1} & −q \\ 0 & 0 & 0 & ⋯ & −1 & 1 + q − N_{1} \end{matrix}] .

We denote this matrix as M′_{k}.

Proof. Given a sequence of orthogonal polynomials satisfying P_{0}(x) = 1, P_{1}(x) = a_{0}x + b_{0} and recurrence (19), we have the formula [10]

P_{k}(x) = det [\begin{matrix}a_{0}x + b_{0} & c_{1} & 0 & 0 & 0 & 0 \\ −1 & a_{1}x + b_{1} & c_{2} & 0 & 0 & 0 \\ 0 & −1 & a_{2}x + b_{2} & c_{3} & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ... & 0 \\ 0 & 0 & 0 & ⋯ & a_{k−2}x + b_{k−2} & c_{k} \\ 0 & 0 & 0 & ⋯ & −1 & a_{k−1}x + b_{k−2} \end{matrix}] .

Plugging in the a_{i}, b_{i}, and c_{i}’s as in Section 4.1 yields the formula. □ Remark 6. Alternatively, we can use symmetric functions and the Newton Identities [20] to obtain these determinant identities, as described in [7, Chap. 7] or [15, Chap. 5].

We can prove Theorem 5 via Proposition 11 followed by an algebraic manipulation of matrix M_{k}. Namely, by using the multilinearity of the determinant, and expansions about the first row followed by the first column, we obtain

det(M_{k}) = det(A_{k}) + det(B_{k}) + det(C_{k}) + det(D_{k}),

where A_{k}, B_{k}, C_{k}, and D_{k} are the following k-by-k matrices:

A_{k} = [\begin{matrix}1 + q − N_{1} & −1 & 0 & 0 & 0 & 0 \\ −q & 1 + q − N_{1} & −1 & 0 & 0 & 0 \\ 0 & −q & 1 + q − N_{1} & −1 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ... & 0 \\ 0 & 0 & 0 & ⋯ & 1 + q − N_{1} & −1 \\ 0 & 0 & 0 & ⋯ & −q & 1 + q − N_{1} \end{matrix}] ,

B_{k} = [\begin{matrix}0 & 0 & 0 & 0 & 0 & −q \\ −q & 1 + q − N_{1} & −1 & 0 & 0 & 0 \\ 0 & −q & 1 + q − N_{1} & −1 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ... & 0 \\ 0 & 0 & 0 & ⋯ & 1 + q − N_{1} & −1 \\ 0 & 0 & 0 & ⋯ & −q & 1 + q − N_{1} \end{matrix}] ,

C_{k} = [\begin{matrix}0 & −1 & 0 & 0 & 0 & 0 \\ 0 & 1 + q − N_{1} & −1 & 0 & 0 & 0 \\ 0 & −q & 1 + q − N_{1} & −1 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ... & 0 \\ 0 & 0 & 0 & ⋯ & 1 + q − N_{1} & −1 \\ −1 & 0 & 0 & ⋯ & −q & 1 + q − N_{1} \end{matrix}] ,

D_{k} = [\begin{matrix}0 & 0 & 0 & 0 & 0 & −q \\ 0 & 1 + q − N_{1} & −1 & 0 & 0 & 0 \\ 0 & −q & 1 + q − N_{1} & −1 & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ... & ... & 0 \\ 0 & 0 & 0 & ⋯ & 1 + q − N_{1} & −1 \\ −1 & 0 & 0 & ⋯ & −q & 1 + q − N_{1} \end{matrix}] .

Cyclic permutation of the rows of B_{k} and the columns of C_{k} yield upper-triangular matrices with −1’s (respectively −q)’s on the diagonal. Given that the sign of such a cyclic permutation is (−1)^{k−1}, we obtain det(B_{k}) + det(C_{k}) = −q^{k} − 1. Additionally, by expanding det(D_{k}) about the first row followed by the first column, we obtain det(D_{k}) = −q det(A_{k−2}). In conclusion

1 + q^{k} + det(M_{k}) = det(A_{k}) − q det(A_{k−2}).

After transposing M′_{k}, by analogous methods we obtain

det M′_{k} = det(A_{k}) − q det(A_{k−2})

and thus the desired formula det M_{k} = −N_{k}.

4.3. Second proof of Theorem 5: Using the zeta function. Alternatively, we note that we can factor

N_{k} = 1 + q^{k} − α_{1}^{k} − α_{2}^{k}

using the fact that q = α_{1}α_{2}. Consequently,

N_{k} = (1 − α_{1}^{k})(1 − α_{2}^{k})

and we can factor each of these two terms using cyclotomic polynomials. We recall that (1 − x^{k}) factors as

1 − x^{k} = ∏_{d|k} Cyc_{d}(x),

where Cyc_{d}(x) is a monic irreducible polynomial with integer coefficients. We can similarly factor N_{k} as

N_{k} = ∏_{d|k} Cyc_{d}(α_{1})Cyc_{d}(α_{2}).

These factors are therefore bivariate analogues of the cyclotomic polynomials, and we refer to them henceforth as elliptic cyclotomic polynomials, denoted as ECyc_{d}.

Definition 5. We define the elliptic cyclotomic polynomials to be a sequence of polynomials in variables q and N_{1} such that for d ≥ 1,

ECyc_{d} = Cyc_{d}(α_{1})Cyc_{d}(α_{2}),

where α_{1} and α_{2} are the two roots of

T^{2} − (1 + q − N_{1})T + q.

We verify that they can be expressed in terms of q and N_{1} by the following proposition.

Proposition 12. Writing down ECyc_{d} in terms of q and N_{1} yields irreducible bivariate polynomials with integer coefficients.

Proof. Firstly we have

α_{1}^{j} + α_{2}^{j} = (1 + q^{j} − N_{j}) ∈ ℤ

for all j ≥ 1 and expanding a polynomial in α_{1} multiplied by the same polynomial in α_{2} yields terms of the form α_{1}^{i}α_{2}^{i}(α_{1}^{j} + α_{2}^{j}). Secondly the quantity N_{j} is an integral polynomial in terms of q and N_{1} by Theorem 1 and α_{1}^{i}α_{2}^{i} = q^{i}. Putting these relations together, and the fact that Cyc_{d} is an integral polynomial itself, we obtain the desired expressions for ECyc_{d}.

Now let us assume that ECyc_{d} is factored as F (q, N_{1})G(q, N_{1}). The polynomial Cyc_{d}(x) factors over the complex numbers as

Cyc_{d}(x) = ∏_{gcd(j,d)=1^{j=1}}^{d}(1 − ω^{j}x),

where ω is a dth root of unity. Thus F (q, N_{1}) = ∏_{i∈S}(1 − ω^{i}α_{1}) ∏_{j∈T} (1 − ω^{j}α_{2}) for some nonempty subsets S, T of elements relatively prime to d. The only way F can be integral is if F equals its complex conjugate \overline{F}. However, α_{1} and α_{2} are complex conjugates by the Riemann hypothesis for elliptic curves [9, 17] (Hasse’s Theorem), and thus F = \overline{F} implies that the sets S and T are equal. Since Cyc_{d}(x) is known to be irreducible, the only possibility is S = T = {j : gcd(j, d) = 1}, and thus F (q, N_{1}) = ECyc_{d}, G(q, N_{1}) = 1. □

Remark 7. Alternatively, the integrality of the ECyc_{d}’s also follows from the Fundamental Theorem of Symmetric Functions that states that a symmetric polynomial with integer coefficients can be rewritten as an integral polynomial in e_{1}, e_{2}, . . .. In this case, Cyc_{d}(α_{1})Cyc_{d}(α_{2}) is a symmetric polynomial in two variables so e_{1} = α_{1} + α_{2} = 1 + q − N_{1}, e_{2} = α_{1}α_{2} = q, and e_{k} = 0 for all k ≥ 3. Thus we obtain an expression for ECyc_{d} as a polynomial in q and N_{1} with integer coefficients.

We can factor N_{k}, i.e., the ECyc_{d}’s even further, if we no longer require our expressions to be integral.

N_{k} = ∏_{j=1}^{k}(1 − α_{1}ω_{k}^{j})(1 − α_{2}ω_{k}^{j})

= ∏_{j=1}^{k}(1 − (α_{1} + α_{2})ω_{k}^{j} + (α_{1}α_{2})ω_{k}^{2j})

= (−1) ∏_{j=1}^{k}(−ω_{k}^{k−j})(1 − (1 + q − N_{1})ω_{k}^{j} + (q)ω_{k}^{2j})

= − ∏_{j=1}^{k} ((1 + q − N_{1}) − qω_{k}^{j} − ω_{k}^{k−j}).

Furthermore, the eigenvalues of a circulant matrix are well-known, and involve roots of unity analogous to the expression precisely given by the second equation above. (For example Loehr, Warrington, and Wilf [11] provide an analysis of a more general family of three-line-circulant matrices from a combinatorial perspective. Using their notation, our result can be stated as

N_{k} = Φ_{k,2}(1 + q − N_{1}, −q),

where Φ_{p,q}(x, y) = ∏_{j=1}^{p}(1 − xω^{j} − yω^{qj}) and ω is a primitive pth root of unity. It is unclear how our combinatorial interpretation of N_{k}, in terms of spanning trees, relates to theirs, which involves permutation enumeration.) In particular, we prove Theorem 5 since det M_{k} equals the product of M_{k}’s eigenvalues, which are precisely given as the k factors of −N_{k} in second equation above.

4.4. Combinatorics of elliptic cyclotomic polynomials. In this subsection we further explore properties of elliptic cyclotomic polynomials, noting that they are more than auxiliary expressions that appear in the derivation of a proof. To start with, by Möbius inversion, we can use the identity

(22)  N_{k} = ∏_{d|k} ECyc_{d}(q, N_{1})

to define elliptic cyclotomic polynomials directly as

(23)  ECyc_{k}(q, N_{1}) = ∏_{d|k} N_{d}^{μ(k/d)}

in addition to the alternative definition

(24)  ECyc_{k}(q, N_{1}) = ∏_{gcd(j,d)=1^{j=1}}^{k} ((1 + q − N_{1}) − qω_{k}^{j} − ω_{k}^{k−j}).

In particular, ECyc_{1} = N_{1} and ECyc_{p} = N_{p}/N_{1} if p is prime. To get a handle on ECyc_{k} for k composite, we provide the following table for small values of k:

ECyc_{4} = N_{1}^{2} − (2 + 2q)N_{1} + 2(1 + q^{2})
ECyc_{6} = N_{1}^{2} − (1 + q)N_{1} + (1 − q + q^{2})
ECyc_{8} = N_{1}^{4} − (4 + 4q)N_{1}^{3} + (6 + 8q + 6q^{2})N_{1}^{2} − (4 + 4q + 4q^{2} + 4q^{3})N_{1} + 2(1 + q^{4})
ECyc_{9} = N_{1}^{6} − (6 + 6q)N_{1}^{5} + (15 + 24q + 15q^{2})N_{1}^{4} − (21 + 36q + 36q^{2} + 21q^{3})N_{1}^{3}
+ (18 + 27q + 27q^{2} + 27q^{3} + 18q^{4})N_{1}^{2}
− (9 + 9q + 9q^{2} + 9q^{3} + 9q^{4} + 9q^{5})N_{1} + 3(1 + q^{3} + q^{6})
ECyc_{10} = N_{1}^{4} − (3 + 3q)N_{1}^{3} + (4 + 3q + 4q^{2})N_{1}^{2}
− (2 + q + q^{2} + 2q^{3})N_{1} + (1 − q + q^{2} − q^{3} + q^{4})
ECyc_{12} = N_{1}^{4} − (4 + 4q)N_{1}^{3} + (5 + 8q + 5q^{2})N_{1}^{2}
− (2 + 2q + 2q^{2} + 2q^{3})N_{1} + (1 − q^{2} + q^{4})

We note several commonalities among these polynomials, as described in the following propositions. These properties are further rationale for our choice of name for this family of polynomials.

Proposition 13. We have

(25)  ECyc_{d}|_{N_{1}=0} = C(d)Cyc_{d}(q)

(26)  ECyc_{d}|_{N_{1}=2q+2} = C′(d)Cyc_{d}(−q),

where C(d) and C′(d) are the functions from ℤ_{>0} to ℤ_{≥0} such that

C(d) = \begin{cases}0 if d = 1 \\ p if d = p^{k} for p prime \\ 1 otherwise \end{cases}

and

C′(d) = \begin{cases}−2 if d = 1 \\ 0 if d = 2 \\ p if d = 2p^{k} for p prime (including 2) \\ 1 otherwise \end{cases} .

Proof. In the case that N_{1} = 0, the characteristic quadratic equation factors as

1 − (1 + q − N_{1})T + qT^{2} = (1 − T)(1 − qT).

Consequently, α_{1} = 1 and α_{2} = q in this special case. (Note this is strictly formal since N_{1} = 0 is impossible, and thus it is not contradictory that the Riemann Hypothesis fails.) Nonetheless, we still have ECyc_{d} = Cyc_{d}(α_{1})Cyc_{d}(α_{2}), and consequently,

ECyc_{d}|_{N_{1}=0} = Cyc_{d}(1)Cyc_{d}(q).

Finally the value of Cyc_{d}(1) equals the function defined as C(d) above [18, Seq. A020500].

For the reader’s convenience we also provide a simple proof of this equality. It is clear that Cyc_{1}(q) = 1 − q and Cyc_{p}(q) = 1 + q + q^{2} + ⋯ + q^{p−1} so by induction on k ≥ 1, assume that Cyc_{p^{k}}(1) = p.

\frac{1 − q^{p^{k}}}{1 − q} = 1 + q + q^{2} + ⋯ + q^{p^{k}−1} = ∏_{j=1}^{k} Cyc_{p^{j}}(q).

Plugging in q = 1, and by induction we get p^{k} = p^{k−1} · Cyc_{p^{k}}(1), thus we have Cyc_{p^{k}}(1) = p. We now proceed to show Cyc_{d}(1) = 1 if d = p_{1}^{k_{1}}p_{2}^{k_{2}} ⋯ p_{r}^{k_{r}} for any r ≥ 2. For this we use k such that d|k. We assume k = p_{1}^{k′_{1}}p_{2}^{k′_{2}} ⋯ p_{r}^{k′_{r}}.

\frac{1 − q^{k}}{1 − q} = 1 + q + q^{2} + ⋯ + q^{k−1}

= ( ∏_{j_{1}=1}^{k′_{1}} Cyc_{p_{1}^{j_{1}}}(q))( ∏_{j_{2}=1}^{k′_{2}} Cyc_{p_{2}^{j_{2}}}(q)) ⋯ ( ∏_{j_{r}=1}^{k′_{r}} Cyc_{p_{r}^{jr}} (q))

× ( ∏_{d is another divisor of k} Cyc_{d}(q)).

The expression \frac{1−q^{k}}{1−q} |_{q=1} equals k, and the first r products on the right-hand-side

equal p_{1}^{k′_{1}}, p_{2}^{k′_{2}}, …, p_{r}^{k′_{r}} respectively. Thus the last set of factors, i.e., the cyclotomic polynomials of d with two or more prime factors, must all equal the value 1.

We prove (26) analogously. When N_{1} = 2q + 2 (again this is strictly formal), the characteristic equation factors as

1 − (1 + q − N_{1})T + qT^{2} = (1 + T)(1 + qT)

implying α_{1} = −1 and α_{2} = −q. Additionally, C′(d) = Cyc_{d}(−1) was observed by Ola Veshta on Jun 01 2001, as cited on [18, Seq. A020513]. □

Proposition 14. For d ≥ 2,

deg_{N_{1}} ECyc_{d} = deg_{q} ECyc_{d} = ϕ(d),

where the Euler ϕ function which counts the number of integers between 1 and d − 1 which are relatively prime to d.

Proof. As noted in Remark 7, we can write ECyc_{d} as an integral polynomial in e_{1} = α_{1} + α_{2} = 1 + q − N_{1} and e_{2} = α_{1}α_{2} = q. The highest degree of N_{1} in ECyc_{d} is therefore equal to the highest degree of e_{1} = α_{1} + α_{2}, which is the same as the largest m such that α_{1}^{m}α_{2}^{0} (respectively α_{1}^{0}α_{2}^{m}) is a term in Cyc_{d}(α_{1})Cyc_{d}(α_{2}). Thus deg_{N_{1}} ECyc_{d}(q, N_{1}) = deg_{α_{1}} Cyc_{d}(α_{1}) = ϕ(d). Analogously, the degree of q comes from the highest power of (α_{1}α_{2})^{m} in Cyc_{d}(α_{1})Cyc_{d}(α_{2}). Thus we have shown

deg_{q} ECyc_{d} ≤ ϕ(d).

Equality follows from the first half of Proposition 13 when d ≥ 2 since the constant term with respect to N_{1}, which equals C(d)Cyc_{d}(q), has degree ϕ(d). □

Finally, if one examines the expressions for ECyc_{d}(q, N_{1}), one notes that they appear alternating in sign just as the polynomials for N_{k}, except for the constant term which equals C(d)Cyc_{d}(q) by Proposition 13. More precisely, the author finds the following empirical evidence for such a claim.

Proposition 15. For d between 2 and 104, we obtain

ECyc_{d}(q, N_{1}) = Cyc_{d}(1) · Cyc_{d}(q) + ∑_{i=1}^{ϕ(d)}(−1)^{i}Q_{i,d}(q)N_{1}^{i},

where Q_{i,d} is a univariate polynomial with positive integer coefficients.

However, the conjecture fails for d = 105. In particular, if we write

ECyc_{105}(q, N_{1}) = Cyc_{105}(1) · Cyc_{105}(q) + ∑_{i=1}^{48}(−1)^{i}Q_{i,105}(q)N_{1}^{i},

where the Q_{i,105}(q)’s are univariate polynomials with integer coefficients, then Q_{2,105}(q) through Q_{48,105}(q) indeed have positive integer coefficients as expected. However the first univariate polynomial, i.e., the coefficient of −N_{1} is

Q_{1,105}(q) = 24q^{47} + 47q^{46} + 69q^{45} + 69q^{44} + 69q^{43} + 50q^{42} + 32q^{41}
− 2q^{40} − 18q^{39} − 33q^{38} − 33q^{37} − 33q^{36} − 21q^{35} − 10q^{34}

+ 9q^{32} + 17q^{31} + 24q^{30} + 24q^{29} + 24q^{28} + 20q^{27} + 20q^{26} + 18q^{25} + 18q^{24}

+ 18q^{23} + 18q^{22} + 20q^{21} + 20q^{20} + 24q^{19} + 24q^{18} + 24q^{17} + 17q^{16} + 9q^{15}

− 10q^{13} − 21q^{12} − 33q^{11} − 33q^{10} − 33q^{9} − 18q^{8} − 2q^{7}
+ 32q^{6} + 50q^{5} + 69q^{4} + 69q^{3} + 69q^{2} + 47q + 24.

Note that there are 46 nonzero coefficients of Q_{1,105} in the expansion of ECyc_{105}(q, N_{1}), 14 of which have the incorrect sign.

The number 105 = 3·5·7 is significant and interesting from a number theoretic point of view. This number is also the first d such that ordinary cyclotomic polynomial Cyc_{d} has a coefficient other than −1, 0, or 1.

Cyc_{105} = 1 + x + x^{2} − x^{5} − x^{6} − 2x^{7} − x^{8} − x^{9} + x^{12} + x^{13} + x^{14}
+ x^{15} + x^{16} + x^{17} − x^{20} − x^{22} − x^{24} − x^{26} − x^{28} + x^{31} + x^{32}
+ x^{33} + x^{34} + x^{35} + x^{36} − x^{39} − x^{40} − 2x^{41} − x^{42} − x^{43}
+ x^{46} + x^{47} + x^{48}.

Despite this counter-example, we still can prove that the coefficients of the ECyc_{d}’s alternate in sign for an infinite number of d’s. Specifically, we note that ECyc_{2^{m}} resemble the coefficients of N_{2^{m−1}}, and moreover the pattern we find is given by the following proposition.

Proposition 16.

(27)  ECyc_{2^{m}} = 2Cyc_{2^{m−1}}(q) − N_{2^{m−1}}.

In particular, for i between 1 and ϕ(2^{m}) = 2^{m−1}, we get

(28)  Q_{i,2^{m}} = P_{i,2^{m−1}},

where the P_{i,k} are the coefficients of N_{k}.

Note that in our proof we use the fact that ECyc_{d} can be written as

Cyc_{d}(1) · Cyc_{d}(q) + ∑_{i=1}^{ϕ(d)}(−1)^{i}Q_{i,d}(q)N_{1}^{i},

where the Q_{i,d}’s are univariate polynomials with possibly negative coefficients. Therefore, our proof of Proposition 16 actually extends Proposition 15 to the case where d is a power of 2 since we previously showed that the P_{i,d}’s alternate.

Proof. We note that Cyc_{2^{m−1}} = 1 + q^{2^{m−1}} and that (28) follows from (27). Also, ECyc_{2^{m}} = N_{2^{m}}/N_{2^{m−1}} and thus it suffices to prove

N_{2^{m}} = (2 + 2q^{2^{m−1}})N_{2^{m−1}} − N_{2^{m−1}}^{2}.

However, this is a special case of

N_{2}(q, N_{1}) = (2 + 2q)N_{1}(q, N_{1}) − N_{1}(q, N_{1})^{2}

where we plug in q^{2^{m−1}} in the place of q. □

Unfortunately, formulas for Q_{i,d}’s in terms of P_{i,k}’s when d is not a power of 2 are not as simple. On the other hand, the last part of this proof highlights a principle that has the potential to open up a new direction. Namely, N_{k}(q, N_{1}) is defined as the number of points on C(𝔽_{q^{k}}) where q itself can also be a power of p. Consequently,

(29)  N_{m·k}(q, N_{1}) = #C(𝔽_{q^{m·k}}) = N_{m}(q^{k}, N_{k}).

While this relation is immediate given our definition of N_{k} = #C(𝔽_{q^{k}}), when we translate this relation in terms of spanning trees, the relation

(30)  W_{mk}(q, t) = W_{m}(q^{k}, W_{k}(q, t))

seems much more novel. Furthermore, in this case, this relation involves only positive integer coefficients and thus motivates exploration for a bijective proof. As noted in Section 4.1, such a compositional formula is indicative of the appearance of a linear transformation of x^{k} or T_{k}(x), which is also clear from the three-term recurrence satisfied by the (1 + q^{k} − N_{k})’s.

4.5. Geometric interpretation of elliptic cyclotomic polynomials. Despite the fact that the above expressions of elliptic cyclotomic polynomials do not have positive coefficients nor coefficients with alternating signs, we can nonetheless describe a set of geometric objects which the elliptic cyclotomic polynomials enumerate.

Theorem 7. We have

ECyc_{d} = |Ker(Cyc_{d}(π)) : C(\overline{𝔽_{q}}) → C(\overline{𝔽_{q}})|,

where π denotes the Frobenius map, and Cyc_{d}(π) is an element of End(C) = End(C(\overline{𝔽_{q}})).

Proof. One of the key properties of the Frobenius map is the fact that C(𝔽_{q^{k}}) = Ker(1 − π^{k}), where 1 − π^{k} is an element of End(C). See [17] for example. The map (1 − π^{k}) factors into cyclotomic polynomials in End(C) since the endomorphism ring contains both integers and powers of π. Since the maps Cyc_{d}(π) are each group homomorphisms, it follows that the cardinality of |Ker (Cyc_{d_{1}}Cyc_{d_{2}}(π))| equals |Ker Cyc_{d_{1}}(π)| · |Ker Cyc_{d_{2}}(π)| . Thus

∏_{d|k} ECyc_{d} = N_{k} = |Ker (1 − π^{k})| = |Ker ∏_{d|k} Cyc_{d}(π)| = ∏_{d|k} |Ker Cyc_{d}(π)|,

and since the last equation is true for all k ≥ 1, we must have the relations

(31)  ECyc_{d} = |Ker Cyc_{d}(π)|

for all d ≥ 1. □

Since

N_{k} = ∏_{d|k} ECyc_{d}(q, N_{1})

and W_{k}(q, t) = −N_{k}|_{N_{1}→−t}, it also makes sense to consider the decomposition

W_{k}(q, t) = ∏_{d|k} W Cyc_{d}(q, t),

where W Cyc_{d}(q, t) = −ECyc_{d}|_{N_{1}→−t}.

This motivates the analogous question, namely does there exist a combinatorial or geometric interpretation of these polynomials? We in fact can answer this in the affirmative and do so in [15, Chap. 6] as well as in a forthcoming paper.

Remark 8. The coefficients of the W Cyc_{d}’s are always integers, but not necessarily positive, as seen in the constant coefficient, as well as in the counter-example W Cyc_{105}. Nonetheless, plugging in specific integers q ≥ 0 and t ≥ 1 do in fact result in positive expressions, which factor W_{k}(q, t). It is these values that we are interested in understanding.

5. Conclusions and open problems

The new combinatorial formula for N_{k} presented in this write-up appears fruitful. It leads one to ask how spanning trees of the wheel graph are related to points on elliptic curves. For instance, is there a reciprocity that explains combinatorially why the bivariate integral polynomial formulas for counting points on elliptic curves and counting spanning trees of the wheel graph are equivalent except for the appearance of alternating signs? Such reciprocities occur frequently in combinatorics. For example given the chromatic polynomial χ(λ) of a graph G = (V, E), the expression (−1)^{|V |}χ(−1) provides a formula for the number of acyclic orientations of G [19].

The fact that the Fibonacci and Lucas numbers also enter the picture is also exciting since these numbers have so many different combinatorial interpretations, and there is such an extensive literature about them. Perhaps these combinatorial interpretations will lend insight into why N_{k} depends only on the finite data of N_{1} and q for an elliptic curve, and how we can associate points over higher extension fields to points on C(𝔽_{q}).

The elliptic cyclotomic polynomials provide an additional source of new questions. What is the spanning tree interpretation of W_{k}(q, N_{1})’s factorization? Is there a combinatorial interpretation of W_{mk}(q, t) = W_{m}(q^{k}, W_{k}(q, t))? What is a combinatorial interpretation of the integral polynomials Q_{i,d}, and what does the fact their coefficients are almost all positive mean? We will tackle some of these problems in a forthcoming paper in which we compare more thoroughly the structures of elliptic curves and spanning trees.

Acknowledgements. The author would like to thank Adriano Garsia for many useful conversations and his invaluable guidance through the author’s graduate school. I would also like to thank the referees for their valuable reports in leading to a clearer exposition. In particular, the connection to orthogonal polynomials, including the statement of Theorem 6, was indicated by one of the referees, as were the observations that several of the propositions have direct algebraic proofs. Additionally, Thomas Shemanske brought the significance of the number 105, with respect to ordinary cyclotomic polynomials, to our attention. Section 2 of this paper was presented at FPSAC 2006 and the author would like to thank the conference referees for their edits. This work was supported by the NSF, grant DMS-0500557.

References

[1] A. Benjamin and C. Yerger, Combinatorial Interpretations of Spanning Tree Identities, Bull. Inst. Combin. Appl., to appear.

[2] H. D. Block and H. P. Thielman, Commutative Polynomials. Quart. J. Math. Oxford Ser. 2 2 (1951), 241–243.

[3] F. Boesch and H. Prodinger, Spanning Tree Formulas and Chebyshev Polynomials. Graphs Combin. 2 (1986), no. 3, 191–200.

[4] P. Borwein and T. Erdélyi, Polynomials and Polynomial Inequalities, volume 161 of Graduate Texts in Mathematics, Springer–Verlag, New York (1995).

[5] O. Eğecioğlu and J. Remmel, Brick Tabloids and the Connection Matrices Between Bases of Symmetric Functions, Discrete Appl. Math., 34 (1991), 107–120.

[6] G. Frey, Applications of Arithmetical Geometry to Cryptographic Constructions. Finite Fields and Applications (Augsburg, 1999), Springer, Berlin, (2001), 128–161.

[7] A. Garsia and G. Musiker, Basics on Hyperelliptic Curves over Finite Fields, in progress.

[8] M. Golin, X. Yong, Y. Zhang, Chebyshev Polynomials and Spanning Tree Formulas for Circulant and Related Graphs. Discrete Math., 298 (2005), no. 1–3, 334–364.

[9] H. Hasse, Abstrakte Begründung der komplexen Multiplikation und Riemannsche Vermutung in Funktionenkörpern, Abhandlungen aus dem mathematischen Seminar der Hamburgischen Universität, 10 (1934), 325–348.

[10] M. E. H. Ismail, H. Prodinger and D. Stanton, Schur’s Determinants and Partition Theorems. Sém. Lothar. Combin., 44 (2000), Art. B44a.

[11] N. Loehr, G. Warrington, and H. Wilf, The Combinatorics of a Three-Line Circulant Determinant. Israel J. Math., 143 (2004), 141–156.

[12] I. Macdonald, Symmetric Functions and Hall Polynomials, second ed., Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York, (1995).

[13] C. Moreno, Algebraic Curves over Finite Fields, Cambridge Tracts in Mathematics, vol. 97, Cambridge University Press, Cambridge (1991).

[14] B. R. Myers, Number of Spanning Trees in a Wheel, IEEE Trans. Circuit Theory, 18 (1971), 280–282.

[15] G. Musiker, A Combinatorial Comparison of Elliptic Curves and Critical Groups of Graphs, Ph.D. thesis, UCSD, 2007.

[16] G. Musiker and J. Propp, Combinatorial Interpretations for Rank-Two Cluster Algebras of Affine Type, Electron. J. Combin., 14 (2007), no. 1, Research Paper 15, 23 pp.

[17] J. Silverman, The Arithmetic of Elliptic Curves, Volume 106 of Graduate Texts in Mathematics, Springer–Verlag, New York (1986).

[18] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences,

http://www.research.att.com/∼njas/sequences/index.html.

[19] R. P. Stanley, Acyclic Orientations of Graphs. Discrete Math., 5 (1973), 171–178.

[20] R. P. Stanley, Enumerative Combinatorics Vol. 2, Volume 62 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge (1999).

[21] L. Washington, Elliptic Curves: Number Theory and Cryptography. Discrete Mathematics and its Applications, Chapman & Hall/CRC, Boca Raton, (2003).

[22] A. Weil, Sur les courbes algébriques et les variétés qui s’en déduisent, Hermann, Paris (1948).

[23] A. Zelevinsky, Semicanonical Basis Generators of the Cluster Algebra of Type A_{1}^{(1)}, Electron. J. Combin., 14 (2007), no. 1, Note 4, 5 pp.

Mathematics Department, University of California, San Diego

E-mail address: gmusiker@math.ucsd.edu