## rational function identity

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

I just had to make use of an elementary rational function identity (below). The proof is a straightforward exercise, but that isn't the point. First, "my" identity is almost surely not original, but I don't have a reference for it. Perhaps someone knows it (like a lost cat without a collar) or, more likely, could spot this as a special case of a more general identity. Second, the obvious proof is not much of an explanation: a combinatorial identity often arises for a conceptual reason, and I'd be happy to hear if anyone sees mathematics behind this one.

Let $f(x_1,\ldots,x_n)=\prod_{p=1}^n\big(\sum_{i=p}^n x_i\big)^{-1}$. Then $$f(x_1,\ldots,x_n)+f(x_2,x_1,x_3,\ldots,x_n)+\cdots+f(x_2,\ldots,x_n,x_1)=\big(\sum_{i=1}^n x_i\big)/x_1\cdot f(x_1,\ldots,x_n),$$ where $x_1$ appears as the $i$th argument to $f$ in the $i$th summand on the left side, for $1\leq i\leq n$. But why?

-

7
+1 for the lost cat. See, mathematics is not only about finding black cats in dark rooms - sometimes it is about finding the owner. – darij grinberg Aug 31 2011 at 13:55

## 4 Answers

I have seen a cat of a similar breed in the representation theory of symmetric groups. Out of habit, let me quote a lemma attributed to Littlewood in

Donald Knutson, $\lambda$-rings and the Representation Theory of the Symmetric Group, Springer 1973 (LNM #308), Chapter III, section 2, p. 149:

$\sum\limits_{\sigma\in S_n} f\left(x_{\sigma\left(1\right)},x_{\sigma\left(2\right)},...,x_{\sigma\left(n\right)}\right) = \frac{1}{x_1x_2...x_n}$.

At the moment, neither does this cat imply yours, nor the other way round. But can we cross them?

Let me try. The left paw side of your cat is $\sum\limits_{\sigma\in \mathrm{Sh}\left(1,n-1\right)} f\left(x_{\sigma^{-1}\left(1\right)},x_{\sigma^{-1}\left(2\right)},...,x_{\sigma^{-1}\left(n\right)}\right)$, where $\mathrm{Sh}\left(a,b\right)$ is defined as the subgroup

$\left\lbrace \sigma \in S_{a+b} \mid \sigma\left(1\right) < \sigma\left(2\right) < ... < \sigma\left(a\right) \text{ and } \sigma\left(a+1\right) < \sigma\left(a+2\right) < ... < \sigma\left(a+b\right) \right\rbrace$

of the symmetric group $S_{a+b}$. (The elements of this subgroup $\mathrm{Sh}\left(a,b\right)$ are known as $\left(a,b\right)$-shuffles.) Now I suspect tat

$\sum\limits_{\sigma\in \mathrm{Sh}\left(a,b\right)} f\left(x_{\sigma^{-1}\left(1\right)},x_{\sigma^{-1}\left(2\right)},...,x_{\sigma^{-1}\left(a+b\right)}\right) = f\left(x_1,x_2,...,x_a\right) f\left(x_{a+1},x_{a+2},...,x_{a+b}\right)$

for any $a$ and $b$ and any $x_i$.

This generalizes your cat. Does it generalize Littlewood's? Yes, at least if we generalize it even further, to the so-called *$\left(a_1,a_2,...,a_k\right)$-multishuffles* (which are permutations $\sigma\in S_{a_1+a_2+...+a_k}$ increasing on each of the intervals $\left[a_i+1,a_{i+1}\right]$, where $a_0=0$ and $a_{k+1}=n$). This is not much of a generalization, since it follows from the $\left(a,b\right)$-shuffle version by induction over $k$, but applying it to $\left(1,1,...,1\right)$-multishuffles (which are simply all the elements of $S_n$) yields Littlewood's cat.

Now I see that Littlewood's cat even follows from yours, if we notice that every permutation $\sigma\in S_n$ can be written uniquely as a product $t_1t_2...t_{n-1}$, where each of the $t_k$ moves the $k$ some places to the right. (This is one of the stupid sorting algorithms.)

Oh, and I don't have a proof of my cat, but it can catch mice, so it's a good cat, isn't it?

-
I enjoy the cat comparisons. They will get a fifth vote from my voting account. (If the moderators let me, I would add 6 more to it.) Gerhard "Yes, I'm A Cat Person" Paseman, 2011.08.31 – Gerhard Paseman Aug 31 2011 at 16:20
Yes, that's an excellent cat!! So Darij conjectures that, more generally, $f$ satisfies this "shuffle-coproduct" identity for any $(a,b)$. (Which, Frédéric points out, makes $f$ into a "symmetral mould", if I understand correctly, but I'm kind of fuzzy about operads.) Is it perhaps possible to prove this using, say, some clever trick like Tom proposed for the $(1,n-1)$ case? – Graham Denham Aug 31 2011 at 19:17

1
Actually this cat is no longer a conjecture, because the proof is completely straightforward: Every $\sigma \in \mathrm{Sh}\left(a,b\right)$ satisfies either $\sigma^{-1}\left(1\right)=1$ or $\sigma^{-1}\left(1\right)=a+1$. Thus, the sum splits into two parts, each of which can be handled by induction (once for $\left(a-1,b\right)$ instead of $\left(a,b\right)$, and once for $\left(a,b-1\right)$ instead of $\left(a,b\right)$). – darij grinberg Aug 31 2011 at 22:32

2
Like every proof related to shuffles, this proof is very simple but nigh impossible to formalize. We really need a reasonable shuffle calculus. Maybe dendriform dialgebras can be of use here. – darij grinberg Aug 31 2011 at 22:34

1
For me, they come from the shuffle Hopf algebra. ;) – darij grinberg Sep 1 2011 at 7:32
show 1 more comment

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

This property ( or rather the generalized version by Darij using (a,b)-shuffles ) means that f is what is called a "symmetral mould" in the context of Ecalle's theory of moulds. There is a related notion of "alternal mould" where the right hand side is 0 rather than a product of two f.

Here is just one reference among many : page 591 of

Jean Ecalle; Bruno Vallet The arborification-coarborification transform: analytic, combinatorial, and algebraic aspects

This may not be transparent when looking at this article. Maybe page 2 of my article

The anticyclic operad of moulds

would be more clear, but it only defines "alternal moulds".

ADDED

• The symmetral property is really a property of sequence of functions $f_n$, with $f_n$ a function of $n$ variables $x_1,\dots,x_n$.

• The notions of alternal and symmetral moulds, when considered under some specific point of view, turn into the notion of primitive and group-like element in a Hopf algebra.

-

A simple proof of the Sh(a,b) cat, using iterated integrals, is as follows. Note that $$f(x_1,\ldots,x_n)=\int_{1>t_1>\cdots>t_n>0} dt_1\cdots dt_n \ t_1^{x_1-1}\cdots t_n^{x_n-1}\ .$$ Littlewood's identity follows from changing variables using the permutation so as to keep the integrand fixed. Then one has a sum of simplices (corresponding to all possible relative orderings of the variables) which recombines into a cube of integration $[0,1]^n$. The proof of the Sh(a,b) identity follows the same idea. Here the total volume of integration is a product of simplices which is broken into a union of simplices. This is probably well known to people working with moulds, operads, etc.

An additional remark: Littlewood's identity follows from Lemma II.2 in my article "Trees forests and jungles: a botanical garden for cluster expansions" with V. Rivasseau. To see this, extract the coefficient of the highest degree monomial in the v variables (notations of that article), then specialize the u variables to the case where $u_{i, i+1}=x_i$ and all other pair variables are zero (killing all edges of the complete graph which are not in a `spanning chain'). The Lemma in our article is related to many other topics in mathematical physics such as the Wilson-Polchinski renormalization group equation, see e.g. these slides.

-

So Graham was right, it was a stray cat from the land of topology. (Incidentally, Damien Calaque answered another question of mine about shuffles using your integral: mathoverflow.net/questions/63923/… .) – darij grinberg Sep 1 2011 at 19:35
I think the cat is too feral to belong to one particular land... – Abdelmalek Abdesselam Sep 1 2011 at 19:40
A geometric argument!  That's very nice too. – Graham Denham Sep 3 2011 at 14:03

I'm not sure whether my answer is conceptual in your sense, but here is a relatively short proof. First of all, your definition of $f$ suggests the notation $$s_p := \sum_{i=p}^n x_i.$$ Now consider the following telescopic sum: \begin{equation}\label{eq} (1 - z_2) + z_2(1 - z_3) + z_2 z_3 (1 - z_4) + \dotsm + z_2 \dotsm z_{n-1} (1 - z_n) + z_2 \dotsm z_n = 1. \quad (*) \end{equation} For each $i \in {2,\dots,n}$, take $$z_i = \frac{s_i}{x_1 + s_i},$$ hence $$1 - z_i = \frac{x_1}{x_1 + s_i},$$ and plug this into the telescopic sum $(*)$. Divide both sides of the equation by $x_1 \cdot s_2 s_3 \dotsm s_n$ to get the desired expression.

-

2
That's nicer than my argument (namely: just rewrite in terms of $s_i$'s, clear denominators, and collapse). It's possible, I guess, that my identity can only be seen as an obscured form of (*), in which case I should not expect too much from it. But I'll remain optimistic for a while. – Graham Denham Aug 31 2011 at 14:26
You say the definition of f suggests the notation s_i = ..., but s_i makes no sense: the i on the right side is the index of summation. You meant s_p, not s_i. – KConrad Sep 2 2011 at 12:50
@KConrad: Sorry for the obvious typo; I will correct it. Thanks for noticing :) – Tom De Medts Sep 3 2011 at 17:31
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 53, "mathjax_display_tex": 5, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9107353687286377, "perplexity_flag": "middle"}