Timeline for Is this formal noncommutative power series identity known?
Current License: CC BY-SA 4.0
26 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 23, 2020 at 19:43 | vote | accept | Terry Tao | ||
| Jun 23, 2020 at 16:59 | answer | added | Ira Gessel | timeline score: 14 | |
| Jun 19, 2020 at 4:33 | comment | added | Ira Gessel | @darijgrinberg It is Theorem 7.3, page 30. | |
| Jun 18, 2020 at 18:10 | comment | added | darij grinberg | Where exactly is this in Carlitz/Scoville/Vaughan? | |
| Jun 17, 2020 at 17:05 | comment | added | Terry Tao | @IraGessel The Carlitz et al. reference does indeed contain the full noncommutative form of the identity! If you will post it as a formal answer to this question (also mentioning the commutative precursors of course) I will happily accept it. | |
| Jun 17, 2020 at 5:31 | comment | added | Ira Gessel | The generalization that Darij describes in his fourth comment was first proved, as far as I know (though stated in a weaker form) by Ralph Fröberg, Determination of a class of Poincaré series, Math. Scand. 37 (1975), 29–39, mscand.dk/article/view/11585. The full noncommutative version was proved (independently) shortly thereafter in L. Carlitz, R. Scoville, and T. Vaughan, Enumeration of pairs of sequences by rises, falls, and levels, Manuscripta Math. 19 (1976), 211–243 (Theorem 7.3). | |
| Jun 17, 2020 at 5:30 | comment | added | Ira Gessel | According to Goulden and Jackson (p. 76), the commutative version of the original formula is due to MacMahon, though they only refer to his book Combinatory Analysis and don't give a more specific reference. (Words with adjacent letters different are often called Smirnov words.) | |
| Jun 16, 2020 at 20:45 | comment | added | darij grinberg | Anton Mellit's proof is actually the same as the one in Goulden and Jackson (but in the noncommutative setting). | |
| Jun 16, 2020 at 20:41 | comment | added | Terry Tao | Ah, yes, this is the bijective proof I was looking for! Setting $z_i = -y_i$ the identity becomes $\sum_{k=0}^\infty \sum_{i_1 \neq \dots \neq i_k} \prod_{j=1}^k \sum_{m=1}^\infty z_{i_j}^m = \sum_{l=0}^\infty (\sum_i z_i)^l$ which is the generating function of the fact that words in the alphabet $z_i$ are in bijection with words in the alphabet $z_i^{m_i}$ in which adjacent letters in the word have different $i$ indices. | |
| Jun 16, 2020 at 20:37 | comment | added | Anton Mellit | Here is another proof. No need to think. Set $\frac{x_i}{1-x_i}=y_i$. Then $x_i=\frac{y_i}{1+y_i}$. The first series is $1+y_1+y_2+\cdots$. The second series is the alternating sum of all words in $\{y_i\}$. | |
| Jun 16, 2020 at 20:32 | comment | added | darij grinberg | Nice argument!! | |
| Jun 16, 2020 at 20:26 | comment | added | Terry Tao | ... indeed, the Woodbury identity implies the general noncommutative matrix identity $1 - V (A+UV)^{-1} U = (1+VA^{-1} U)^{-1}$, which when applied to $A = 1 - (a_{ij})$, $U = (x_i)^T$, $V = (y_i)$ and using the geometric series formula gives the previous identity. So technically the original identity is a "special case" of the Woodbury identity, though I would say that this is not explicitly obvious. | |
| Jun 16, 2020 at 20:14 | comment | added | Terry Tao | @darijgrinberg In fact there is an even more general version: the power series $1 + \sum_{m=1}^\infty \sum_{i_1,\dots,i_m} x_{i_1} a_{i_1 i_2} \dots a_{i_{m-1} i_m} y_{i_m}$ is the reciprocal of the power series $1 + \sum_{k=1}^\infty (-1)^k \sum_{i_1,\dots,i_k} x_{i_1} b_{i_1 i_2} \dots b_{i_{k-1} i_k} y_{i_k}$ for arbitrary noncommutative variables $x_i,y_j,a_{ij}, b_{ij}$ for which $a_{ij}+b_{ij}=y_i x_j$. This begins to look like some power series expansion of the Woodbury formula en.wikipedia.org/wiki/Woodbury_matrix_identity . | |
| Jun 16, 2020 at 19:57 | comment | added | darij grinberg | Section 2.4.16 of I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley 1983 also gives the commutative projection of your formula. It appears noncommutative power series were insufficiently known (or popular) back when these were written... | |
| Jun 16, 2020 at 19:55 | comment | added | LSpice | This sounds like the following vaguely Nim-ish game: Players 1 and 2 are faced with $I$ spots, and alternate choosing one of the spots, different from the previous one chosen, and placing a marker on it. Eventually they agree to stop, and then Player $\omega$ chooses a spot $i$ and a non-negative integer $m$, and places $m$ markers on spot $i$. Then there is a bijection between games (not just final states) "Player $\omega$ played after Player 2, or at the beginning of the game, but at least one of them did something" and "Player $\omega$ played after Player 1." | |
| Jun 16, 2020 at 19:52 | comment | added | darij grinberg | Note that you can replace the $\neq$ relation by any binary relation $R$ in the second series, as long as you correspondingly replace the first series by $1 + \sum_i x_i + \sum_{i S j} x_i x_j + \sum_{i S j S k} x_i x_j x_k + \cdots$, where $S$ is the relation complementary to $S$ (that is, $i S j$ holds if and only if $i R j$ does not). For example, $R$ could be $\leq$, and $S$ would then be $>$. (This would yield the antipode relation in $\operatorname{NSym}$ with the standard embedding into noncommutative power series.) | |
| Jun 16, 2020 at 19:49 | comment | added | darij grinberg | @Suvrit: Pretty sure it's not in that paper. | |
| Jun 16, 2020 at 19:48 | comment | added | darij grinberg | Chromatic symmetric functions have been lifted to the noncommutative realm in D. Gebhard and B. Sagan, A chromatic symmetric function in noncommuting variables, J. Algebraic Combin. 13 (2001), 227--255, but I don't see the formula there. | |
| Jun 16, 2020 at 19:48 | comment | added | Suvrit | I'm hoping that a version of this can be found in: arxiv.org/abs/hep-th/9407124 (Noncommutative symmetric functions, Israel Gelfand, D. Krob, Alain Lascoux, B. Leclerc, V. S. Retakh, J.-Y. Thibon), but haven't checked in there myself yet. | |
| Jun 16, 2020 at 19:41 | comment | added | darij grinberg | The commutative projection of your formula is Exercise 5.22 in Eric Egge, An Introduction to Symmetric Functions and Their Combinatorics, AMS 2019. It also appears in the Second Proof of Proposition 5.3 in Richard P. Stanley, A Symmetric Function Generalization of the Chromatic Polynomial of a Graph. I wouldn't be surprised if it goes back further to Carlitz. | |
| Jun 16, 2020 at 19:36 | comment | added | Terry Tao | Fair enough. I guess I want a different bijective proof. For instance, the second power series looks vaguely like an inclusion-exclusion formula applied to some (noncommutative) random set, so I feel like there should be some "bijection" (possibly (noncommutative) probabilistic in nature) involving some sort of residual set arising from inclusion-exclusion. Related to this, there should be a combinatorial or probabilistic proof that the second power series is non-negative whenever it converges and the $0 < x_i < 1$ are real numbers. | |
| Jun 16, 2020 at 19:29 | history | edited | LSpice | CC BY-SA 4.0 |
Minor TeX fixes
|
| Jun 16, 2020 at 19:23 | history | edited | Terry Tao | CC BY-SA 4.0 |
added 171 characters in body
|
| Jun 16, 2020 at 19:23 | comment | added | Fedor Petrov | This cancellation of terms $\pm x_i^s\cdot x_jx_k\ldots$ and $\mp x_i^{s-1}\cdot x_ix_jx_k\ldots$ is what I would call bijective. | |
| Jun 16, 2020 at 19:16 | history | edited | Terry Tao | CC BY-SA 4.0 |
added 221 characters in body
|
| Jun 16, 2020 at 19:07 | history | asked | Terry Tao | CC BY-SA 4.0 |