comment 0

Some Recent Advances in Cylindric Partitions

Studying theory of partitions, I come across many natural and exotic definitions. Cylindric partitions is one of those that is both. I don’t know how but it somehow is. Informally cylindric partitions encodes information about non-intersecting lattice walks and that is clearly natural. However, it is also a finite vector of partitions that can be put together in such a way that you can wrap this shifted arrangement around a cylinder. I don’t think that as something I would be able to come up, so I find it quite exotic in that sense. Thankfully we have great visionaries around such as Ira Gessel and Christian Krattenthaler in this case.

Cylindric partitions are actually really nice. An integer partition is a finite list of non-increasing natural numbers. So given a partition \lambda = (\lambda_1,\lambda_2,\dots), we have an order relation that the parts satisfy: \lambda_i \geq \lambda_{i+1}. In the cylindric partitions, we start with a finite list of partitions (\lambda^{(1)}, \dots, \lambda^{(k)}) and a list of non-negative integers called a profile c = (c_1,c_2,\dots,c_k) where the parts \lambda^{(i)}_j of the partitions \lambda^{(i)} satisfy an interlacing order relation \lambda^{(i)}_{j} \geq \lambda^{(i+1)}_{j+c_i}, where \lambda^{(k+1)} = \lambda^{(1)}.

Why do I/we care? Most classical partition identities gets realized as analytic identities where one side is an infinite sum and the other side is an infinite product. Number theoretically, to me, this is a bone chilling structural finding. We see that an infinite series can be completely factored. In the classical results, the sums are easier to find and easier to associate with the partition theory. However, it is quite hard to prove (and unclear to do so) that this sum is equal to a product even when the numerics provides indubitable evidence.

In cylindric partitions, all thanks to Alexei Borodin, we already know that the generating function for the number of such objects is an infinite product. To be precise, generating function for the number of cylindric partitions with profile c = (c_1,c_2,\dots,c_k) (and t=c_1+c_2+\dots+c_k +k) is

 \displaystyle\frac{1}{(q^t;q^t)_\infty} \prod_{i=1}^k \prod_{j=i}^k \prod_{m=1}^{c_i} \frac{1}{(q^{m+j-i+s(i+1,j)};q^t)_\infty} \prod_{i=2}^k \prod_{j=2}^i \prod_{m=1}^{c_i} \frac{1}{(q^{t-m+j-i-s(j,i-1)};q^t)_\infty}

*This product of products is written using q-Pochhammer symbols. Later we will also use q-Binomial coefficients.

This goes against the grain of classical results. This time we have the product representations for these generating functions for free but we have no idea what the infinite series are supposed to look like. For the profile sizes k=2, we know the cylindric partitions’ related products coincide with the Andrews-Gordon and Bressoud products, so the sum sides are known through these powerful theorems. However, the k=3 cases are still filled with unknowns and conjectures for the sum representation of the generating functions, most advancements are at this level now. k\geq 4 is a mystery. That is the product generating functions are there, but we don’t know the closed formula sum representations.

The recent k=3 journey starts with a paper by Sylvie Corteel and Trevor Welsh. Their idea is simple and that is what makes it extra brilliant. In simple words, we know the interlacing order relations the cylindric partitions have to satisfy. Therefore, we know at what location or locations the largest part of a cylindric partition can be; that is once given the profile c. If those largest parts are removed from the object, a new cylindric partition with a new profile c^* emerges. So we can derive recurrences for the generating functions and associate them with generating functions for different profiles. The number of generating functions involved in such a construction is finite so we are not churning water.

Sylvie and Trevor used this recurrence relations to find the sum generating functions for k=3 cylindric partitions with c_1+c_2+c_3=4. They coincided with Andrews-Schilling-Warnaar‘s A2 Rogers-Ranaujan identities plus found an identity that was not identified before. Later, Sylvie, Jehanne Dousse and I come together and identified the k=3 case with c_1+c_2+c_3 = 5 in this paper.

As a side note, it is not easy to guess these sum representations at all. They are infinite multisums with 3 and 4 variables in the cases mentioned above, respectively. Once guessed/identified, it is not easy to prove that these objects satisfy the recurrences the generating functions for the number of cylindric partitions with certain products is not easy either due to the high number of variables.

Sylvie and Jehanne were the ones who were able to identify the 4-fold sum generating functions. I cannot take any credit in that miraculous find. I was working on the qFunctions package and as a part of that I was implementing the (coupled) recurrence system of Corteel-Welsh. My objective was to carry this system to a computer algebra system so that we can use other this in conjunction with other symbolic computation tools to prove (or disprove) guessed identities in the spirit of Corteel-Welsh paper.

This was a perfect match. Once we combined our powers, we proved 7 sum-product formulas such as the following.

\displaystyle\sum_{n_1,n_2,n_3,n_4\geq 0 } \frac{q^{n_1^2+n_2^2+n_3^2+n_4^2+n_1+n_2+n_3+n_4-n_1n_2 + n_2n_4}}{(q;q)_{n_1}} {n_1\brack n_2}_q{n_1\brack n_4}_q{n_2 \brack n_3}_q=\frac{1}{(q^2,q^3,q^3,q^4,q^4,q^5,q^5,q^6;q^8)_\infty}

Not long after we submitted our paper, Ole Warnaar was able to guess the generic sum representiton for the k=3 profile cylindric partitions with c_1+c_2+c_3\not\equiv 0 mod 3. For example, the claim is that for every j the following sum is the sum representation of the generating function for some particular cylindric partitions.

\displaystyle\sum_{\substack{n_1,\dots,n_j\geq 0\\m_1,\dots,m_{j-1}\geq 0}} \frac{q^{n_j^2+\sum_{i=1}^j}}{(q;q)_{n_1}} \prod_{i=1}^{j-1} q^{n_i^2 - n_im_i + m_i^2 + m_i} {n_i\brack n_{i+1}}_q {n_i-n_{i+1}+m_{i+1}\brack m_i}_q

If we can prove this, then sum (due to Borodin) factors completely and has a product represenatiton that we wrote above. More conjectures and many interesting results can be found in Ole’s paper.

The way Ole come up with these results is also commendable. He looked at the k=3 results that we mentioned above as well as two results from k=2 that can be viewed as initial cases of k=3 using some symmetries of cylindric partitions. There two steps were enough for him to guess the whole chain. This is an amazing advancement. I wonder if I could do this induction even if I had 20 steps on this chain… Ole only needed 2. Who knows maybe he would guess parts of the k=4, etc. chains in the future too.

Technically, we should be able to use the code in qFunctions with Christoph Koutschan‘s HolonomicFunctions package and prove these cases one by one. However, we do not have the computational power to prove that the multi-fold sums satisfy a given recurrence. This is not about physical limiting factor of a computer hardware either. We know that for these objects the theory says that Doron Zeilberger‘s creative telescoping algorithm would terminate, but we do not know when. My personal experience is that for the conjecture above with j=3, the code did not terminate in a month on a RISC server even thought the server was not having any memory shortage or anything of sorts.

There you have it. We have all these identities and conjectures, and that is just the beginning of it. We still haven’t touched anything with k\geq 4. So be my guest and/or be my collaborator. If you have a good idea on how one can guess these sums?, how we can prove Ole’s guessed sums?, etc. I’m all ears.

But wait there is more! Walter Bridges was looking at a paper about the asymptotics related to the number of cylindric partitions by Han-Xiong. He saw that they have presented Borodin like product representations for symmetric cylindric partitions and double skew shifted plane partitions. Not only that, he also observed that we can adapt Corteel-Welsh idea for all these objects. I was happy to jump in this project right away, and this led to our joint paper. We discovered many nice new sum-product identities such as

 \displaystyle\sum_{n,m \geq 0} (-1)^m q^{3{n+1 \choose 2}-3m(m+1)} \frac{(-q,-q^5;q^6)_m}{(q^6;q^6)_m(q^3;q^3)_{n-2m}}=\frac{(q^4,q^8;q^{12})_{\infty}}{(q^6;q^{12})_{\infty}}.\\

Furthermore, the more that we looked at the Borodin and Han-Xiong product generating functions and how they are constructed, the more clear it became that we can weight the counts of different diagonals (partitions) in the cylindric partitions and the product generating functions would reflect this change without the underlying structure changing. This opened us up to infinitely many combinatorial connections that we don’t know what to do with (yet). There are really cute ones, and there are the ones that were discovered before outside of the scope of cylindric partitions/skew shifted plane partitions.

For example, in our paper, we prove some Schmidt-type partition results, my favorite being the Schmidt’s theorem itself. (A great read on this with many new results by George Andrews and Peter Paule here.) The theorem says that counting the partitions into distinct parts (\lambda = (\lambda_1,\lambda_2,\dots)\in\mathcal{D} i.e. $\lambda_i>\lambda_{i+1}>\dots$) with the “every other” part counting statistic takes you to the count of all the partitions:

 \displaystyle\sum_{\lambda\in\mathcal{D}} q^{\lambda_1 + \lambda_3+\lambda_5+\dots} = \frac{1}{(q;q)_\infty}

*For any confused audience members: 1/(q;q)_\infty is the generating function for the number of all partitions.

In one of my previous papers, I proved this result without knowing that it already known. I was using a completely different technique, I am happy that it was not a full rediscovery. With Walter, I also proved this theorem using the weighted skew shifted plane partitions (see the line above Prop 5.1 here). Basically, we put distinct parts in a staircase of size two and then weight the diagonal that has the even indexed parts with 0 so that their contribution vanishes and the weighted version of Han-Xiong’s products did the work for us.

Anyway, I will leave it here. There is a lot more to discover, and next time when you have an infinite product generating function in hand check if it is a weighted cylindric partition or a skew shifted plane partition, you might just see a new combinatorial connection to your problem. We have these functionalities build in qFunctions now…

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s