# Using extended group rings for combinatorial generating functions

In work of mine recently, I have come to investigate generalised recurrence relations. The generalisation I have in mind is where, instead of natural numbers or integers, the recurrence is over some other ring - my particular case being the cyclotomic integers.

One particular case of interest for me is a generalisation of the Fibonacci numbers. The classic recurrence may be written in the form:

$$f_{j} = f_{j+1} + (-1)f_{j-1}$$

where j is an integer. The specific series of Fibonacci includes the initial data the $f_0=0$ and $f_1=1$.

I write it this way because I am interested in the generalisation given by:

$$f_{n,\alpha} = \sum_{k=0}^{n-1} \omega_{n}^{k} f_{n,\alpha+\omega_{n}^{k}}$$

where

$ω_n=e^{2πi/n}$ (an nth root of unity).

The $\alpha$ here can now be any order-n cyclotomic integer. The n=2 case gives the classic Fibonacci.

As a way to solve this, I tried some standard generatingfunctionology. Instead of power series, though, I use the extended group ring over the cyclotomics (so I expand with terms that include x^(ω_n^k ) and terms generated from them). I need to first define the boundary conditions for this, which is more complex than the n=2 case but I can keep the derivation very general here. In other words, I decide to look at generating function

$$G_{n}(x) = \sum_{\alpha \in C_{n}} f_{n, \alpha} x^{\alpha}$$

over the cyclotomic integers $C_n$.

This gives a result that I seem to be able to extract information from:

$$G_{n}(x) = \frac{H_{n}$B(f_{n}); x$ - \sum_{j=0}^{n-1} \omega_{n}^{j} x^{-\omega_{n}^{j}} H_{n}$\overline{I(f_{n}) + \omega_{n}^{j}}; x$ }{1 - \sum_{j=0}^{n-1} \omega_{n}^{j} x^{\omega_{n}^{j}}}$$

Where I have defined the sum over set S

$$H_{n}$S;x$ = \sum_{\alpha \in S} f_{n,\alpha} x^{\alpha}$$

such that the set $B(f_{n})$ is the set of boundary value places defined for the problem, $I(f_{n})$ is the set of interior places determined by the boundary set, and the overbar indicates complement with respect to the cyclotomic integers. In other words, I can find how the generating function will look using formal manipulations on the group ring that accounts for the different initial value choices that might be given for the problem.

But here is my problem: I don’t know if those formal manipulations are completely valid. When looking at these extended group rings, there are equivalent expansions that make it much more risky to blindly do formal manipulations than with traditional power series. An easy example is the formal extended Laurent series

$$...+x^{-4}+x^{-3}+x^{-2}+x^{-1}+1+x+x^2+x^3+x^4+...$$

If we try to expand this as two geometric series, we might expand this into the generating function

$$\frac{1}{1-x} + \frac{x^{-1}}{1 - x^{-1}}$$

But if you do this and simplify, you get 0! It's clear that such a function would formally obey xf=f if we ignore convergence issues. Obviously 0 isn’t a good generating function for the infinite vector of 1s! And the same for an infinite vector of any constant. Such problems with simple manipulations don’t arise in the power series case. So one big caveat is that such generalised structures have formally distinct representations with the same behavior, and manipulation may switch between them.

Interestingly, the case for n=2 with standard boundary at 0 and 1 gives:

$$G_{2}(x) = \frac{-1}{1+x-x^{-1}}$$

from which I can extract the standard generating functions on either side of the boundary by multiplying by $\frac{x}{x}$ or $\frac{x^{-1}}{x^{-1}}$. Similarly can I extract meaningful values from my solution along subset regions for higher n.

Here are two pictures (one, two) of the formal manipulations I used to obtain the result above (rather than typing the whole thing out). I don’t have any familiarity with actual references on what formal manipulations on extended group rings are considered “valid” for generating functions (i.e. which ones will maintain the generated values) and where caution is needed. I understand that some of these concerns are why group rings are typically defined with finite support and why Laurent series are typically only finitely extended along one of the rays, but there is good combinatorics done with bilateral series and the generalisation does seem to give good extractable information.

Any help with references that explore these areas would be greatly appreciated! If you know of rules or explicit manipulations that fail or are guaranteed to work, that would help me start to get a handle on this. Also, any other methods for solving such generalised recurrence relations would be appreciated. I have looked at operator theory and directional differences, but they have a much deeper set of relations and I seem to get lost trying to apply them constructively here. But any algebraic techniques would really help out.

[As a note: the above recurrence may seem arbitrary and unmotivated. However, it is directly related to work I have done on generalised Chebyshev “polynomials”, which arise from the natural generalisation of trigonometry. These generalised Fibonacci actually “occur in the wild”, so to speak.]

-
Guoce Xin has some papers that seem relevant. See for instance front.math.ucdavis.edu/0409.5190 and front.math.ucdavis.edu/0504.5425. –  Richard Stanley Apr 24 '13 at 1:15
Your double-ended power series can be viewed as a formal distribution, i.e., a functional on the Laurent polynomial ring. This sort of calculation appears a lot in "formal calculus", which is often used in papers by J. Lepowsky and his students. –  S. Carnahan Apr 24 '13 at 5:07
Professor Stanley, thank you very much for your references. I was unfamiliar with Malcev-Neumann series and see that they get us past the finite support by requiring only a well-ordering. I found Xin's thesis "The Ring of Malcev-Neumann Series and the Residue Theorem" which has a lot more detail and combinatorial applications. I've only begun reading the various papers, but they clearly approach a number of my concerns. –  ex0du5 Apr 24 '13 at 6:09
Professor Carnahan, I really appreciate your comment. This has led me to the book by Li and Lepowsky "Introduction to Vertex Operator Algebras and Their Representations" which has a chapter on formal calculus which gives criteria for when multiplying these formal doubly infinite Laurent series can be multiplied, along with other good caveats and details. I think there is a good portion here that may be generalised to the other series I consider. –  ex0du5 Apr 24 '13 at 6:25