Where do the Maximum Absolute q-series Coefficients of (q;q)_n occur?

Dedicated to the MACH2 group, in particular to Prof. Wolfgang Schreiner and Johann Messner.

In mathematics research, some questions are too easy to ask that one cannot help but feel amazed when the answers to these questions are nowhere to be found. The title is an example of such a question, I and Alexander Berkovich (my former advisor from the University of Florida) asked in 2017. Our account on this question recently got published in Experimental Mathematics. I suggest checking the ArXiv version of this paper or the actual published article, if my explanation of the problem sparks your interest.

I want to motivate the problem by introducing a well-known q-series identity first. The Euler Pentagonal Number Theorem (EPNT)

$\displaystyle \sum_{i=-\infty}^{\infty} (-1)^i q^{\frac{i(3i-1)}{2}} = (q;q)_\infty,$

where for any non-negative integer $n$

$\displaystyle (q;q)_n := \prod_{i=1}^{n} (1-q^i)$ and $\displaystyle (q;q)_\infty = \lim_{n\rightarrow\infty} (q;q)_n$ .

When one looks at the sum side of the EPNT, it is clear that all the coefficients that appear in this formal power series are merely one of the three options: $-1$ , $0$ , or $1$ . This property is not visible from the product representation. Moreover, it is highly surprising to see such cancellations to appear in the series expansion of an infinite product!

But wait, there is more! The products $(q;q)_n$ will always have a coefficient that is

$> 1$ in size if $n\not= 0,\ 1,\ 2,\ 3,\ 5$ or $\infty$ .
$> 2$ in size if $n\not= 0,\ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9,\ 11$ or $\infty$ .
$> 3$ in size if $n\not= 0,\ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9,\ 10,\ 11,\ 13,\ 14$ or $\infty$ .
$> 4$ in size if $n\not= 0,\ 1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 8,\ 9,\ 10,\ 11,\ 12, 13,\ 14, 15$ or $\infty$ .
$...$

This is what Berkovich and I proved in 2017* using elementary observations and simple calculations.

For me, the above list highlights how special the infinite product $(q;q)_\infty$ that appears in EPNT once again. There is no way of seeing these unbelievable cancellations that lead to small coefficients of the infinite product when we look at the finite products. Furthermore, the size of the coefficients of the $(q;q)_n$ polynomials grow, and they grow exponentially. In 1964, Sudler studied the size of the maximal absolute coefficients of these products and proved their exponential growth*.

Let’s get a little more technical and write out the polynomial

$\displaystyle (q;q)_n = \sum_{i=0}^{n(n+1)/2 } a_{i,n} q^n$ .

We can observe how fast these coefficients grow with the following animation where we plot $(i, a_{i,n})$ from $n=0$ to $n=100$ in steps of $5$ . On the top of the image, you can also see the Maximum Absolute Coefficient (denoted as $M$ ) and the first location at which this coefficient appears (denoted by $L$ ).

At $n=100$ , this polynomial has $5051$ terms, about $1/3$ of which are huge and all around the place! The maximum absolute coefficient at $n=10$ is $3$ . This becomes $11,493,312$ when we reach $n=100$ . They grow really fast; just as Sudler discovered.

Whenever we have a list of integers, it is a good idea to check the On-line Encyclopedia of Integer Sequences. We already had the absolute maximum coefficients ( $M$ s) of $(q;q)_n$ for $n\leq 50$ for our 2017 paper, so we made a quick search of this sequence only to find that this sequence was already listed* and our main question-to-be was right in front of us in the comments.

This is how the website looked in 2019:

The comment is clear. People believe that the absolute maximum coefficient of $(q;q)_n$ appears at the midpoint if $n$ is even (I haven’t seen a proof of this, please contact me if you find one) and it is a mystery if $n$ is odd. Berkovich and I studied these locations by calculating all the $(q;q)_n$ for $n\leq 75,000$ . With that, now, we have confirmed the even index belief all the way up to 75,000 and we actually have a conjectural answer to the location question for the odd cases too. There are so many interesting properties of this elusive location that we supposedly found, but this is not the place to discuss those. I suggest checking the article.

The calculation of these polynomials one by one, finding the maximum absolute coefficient and its location was a huge task. We started calculating $(q;q)_n$ s on Maple, which gave up around $n=10,000$ . We moved to Mathematica and a larger server at Research Institute for Symbolic Computation (RISC) and we got stuck around $n=15,000$ . So I abandoned all the computer algebra systems and started programming in Python and later in C++. Carrying out these calculations correctly is/was not an easy task. I doubt it will ever be in my lifetime. After using all the symmetries and simplifications, one still needs at least $\lceil n(n+1)/4 \rceil$ operations to calculate $(q;q)_{n+1}$ from $(q;q;)_n$ . There is no way of splitting the data. The numbers are growing exponentially and each calculation needed to be carried with arbitrary precision. RISC IT Ralf Wahner dealt with all my incompetence on the RISC side. I need to thank him a lot.

I attended a presentation by Wolfgang Schreiner on the MACH2 massively parallel shared-memory supercomputer project while I was struggling to make progress in my calculations. Using MACH2 was clearly what I needed. My calculations were already crashing computers with 1.5 Tb Ram at RISC. It would have been a great challenge to crash a computer with 20 Tb of shared Ram (I did crash a 10 Tb section of MACH2 once, so I can rest happily).

I contacted the MACH2 team, got an account, and gave a brief explanation of what I wanted to calculate. After a couple of emails, Johann Messner and I met in person and went through my code, line by line. I took his feedback and suggestions and started working on those. In the meantime, he started running tests with then-code. It took so much back and forth. Johann kept on asking me to parallelize my code but I didn’t want to do that in order to save used memory. I resisted as much as I can but he won. He knew the MACH2 beast the most after all. Also, he made the great point that MACH2 has slow processors but it has tons of memory at our disposal.

I didn’t know how to parallelize anything in C++ so I put it on the backburner. It was already more than a year at this point since we first started. The project could have easily sat for another couple of months… and it did. Later in the year, at a conference, I accidentally learned how to parallelize my code from a couple of numerical analysis postdocs. All of a sudden the missing link was there. After Johann’s okay, we cranked the last portion of the calculations (with lots of intermediate checks) from $n=40,000$ to $n =75,000$ . It still took 3 months even though we were using a little more than 200 cores and 10 Tb of memory.

The mathematical claims of the article came after all these crazy calculations. I came together with Prof. Berkovich at the University of Florida in October 2019. We compiled the data, looked at it left and right. In a short time, we made the best claims we can make about the elusive location. While we were at it, we refined Sudler’s growth constants as well. This ended my first 2 year-long experimental math project.

Long story short, the mathematical claims I made stand on the shoulders of many computers, so much wasted electricity, many sleepless nights, and the input of many people many of which haven’t even been mentioned here.

If you’d like to confirm or disprove that of the maximum absolute coefficient when $n=5,050,029$ appears as the coefficient of the $q^{6,375,697,892,084}$ term, be my guest. 🙂

I shared this work with some audiences:

Austrian High-Performance Computing Meeting 2020, IST Austria, Klagenfurt AUT. February 19, 2020
Where do the maximum absolute q-series coefficients of $(1-q)(1-q^2)...(1-q^{n-1})(1-q^n)$ occur? (Slides)
The 85th Seminaire Lotharingien de Combinatoire, Strobl AUT. September 6, 2020
Where do the maximum absolute q-series coefficients of $(1-q)(1-q^2)...(1-q^{n-1})(1-q^n)$ occur?
Hudson Colloquium, Georgia Southern University, Savannah GA. September 23, 2020 (Online Meeting)
Where do the maximum absolute q-series coefficients of $(1-q)(1-q^2)...(1-q^{n-1})(1-q^n)$ occur? (Pdf)

Of course there are some simple typos here and there in the article, let me address the ones I know about here:

There are two 68,324s written by accident. Those should be 62,624s as in everywhere else in the paper.

Ali K. Uncu

aku21@bath.ac.uk

Where do the Maximum Absolute q-series Coefficients of (q;q)_n occur?

Dedicated to the MACH2 group, in particular to Prof. Wolfgang Schreiner and Johann Messner.

I shared this work with some audiences:

Of course there are some simple typos here and there in the article, let me address the ones I know about here:

Leave a Reply Cancel reply

Dedicated to the MACH2 group, in particular to Prof. Wolfgang Schreiner and Johann Messner.

I shared this work with some audiences:

Of course there are some simple typos here and there in the article, let me address the ones I know about here:

Share this:

Like this:

Related

Leave a Reply Cancel reply