# Asymptotics of the Steenrod algebra / $s$-partitions?

Recall that an $$s$$-partition is a partition of a natural number $$n$$ such that each part is of the form $$2^r-1$$. By a fundamental theorem of Milnor, the number $$p_s(n)$$ of $$s$$-partitions of $$n$$ counts the dimension of the mod-2 Steenrod algebra in degree $$n$$. I'm interested in the asymptotics of the function $$p_s(n)$$, as well as related functions for the odd-primary Steenrod algebras.

Questions:

1. Does the number of $$s$$-partitions $$p_s(n)$$ grow subexponentially in $$n$$?

2. If so, are there effective constants $$p_s(n) \leq C_\epsilon (1+\epsilon)^n$$?

3. What about the dimension of the odd-primary Steenrod algebras?

The OEIS page (here's the link again) leads to this paper which gives an asymptotic formula for $$\ln p_s(n)$$, and all the terms are indeed sublinear in $$n$$, except possibly for the term involving a handicrafted function $$W(z)$$, whose growth I don't know how to estimate.

As for the odd-primary Steenrod algebras, Milnor showed that for $$p$$ an odd prime, the dual Steenrod algebra at the prime $$p$$ is the tensor product $$P(\xi_1,\xi_2,\dots) \otimes E(\tau_0,\tau_1,\tau_2,\dots)$$ where $$deg(\xi_i) = 2p^i - 2$$, $$deg(\tau_i = 2p^i - 1)$$, and $$P, E$$ denote polynomial and exterior algebras respectively, over $$\mathbb F_p$$. So counting the dimension reduces to a combinatorial partition problem of a similar flavor.

• But even the number of all partitions is subexponential. $p_s(n)$ grows as $\exp(c(\log n)^2)$. – Fedor Petrov Nov 25 '19 at 23:54
• Oh wow. Duh, of course! So I guess that leaves at most the effective bounds as a potentially interesting question... – Tim Campion Nov 26 '19 at 0:31
• The end of Theorem 2 in that paper says that $W(z)$ is bounded on the real line. – MTyson Nov 26 '19 at 0:53
• @MTyson Ah, thanks. I misread the bound $|y| \leq M$ (with $y = \Im z$) as $|z| \leq M$. – Tim Campion Nov 26 '19 at 4:04

My original answer, below the horizontal rule, was based on a misunderstanding. I'm preserving it so that the comments make sense.

For a fixed odd prime $$p$$, the generating function for the corresponding partitions is $$\frac{\prod_{i\ge0}(1+x^{2p^i-1})}{\prod_{i\ge1} (1-x^{2p^i-2})}.$$ @Dvitek in the comments explains nicely why we want the $$2p^i-1$$ parts to appear at most once while the $$2p^i-2$$ parts can be repeated arbitrarily often.

For instance, for $$p = 3$$ the first 30 coefficients (from $$n=1$$) are $$1, 0, 0, 1, 2, 1, 0, 1, 2, 1, 0, 1, 2, 1, 0, 2, 4, 2, 0, 2, 5, 4, 1, 2, 5, 4, 1, 2, 5, 4.$$

There's a variant of the Frobenius problem here: $$x^{19}$$ is the highest power with coefficient 0. In other words, 19 is the largest positive integer that cannot be made with parts 1, 5, 17 appearing at most once and parts 4 and 16 with no restrictions. For $$p=5$$, I verified that the last 0 occurs for $$n=39{,}047$$. For $$p=7$$, I believe the corresponding number is $$659{,}108{,}891$$. (If that's an interesting value to find in general, I can explain my thinking.)

A near(ish) miss on (3) that's too long for a comment but might still be helpful as more than a cautionary tale.

I put the generating function $$\frac{1}{(1-x) \prod_{p,i} (1-x^{2p^i-2})(1-x^{2p^i-1})}$$ into Mathematica, with odd primes $$p$$ and exponents $$i \ge 1$$. (The $$(1-x)$$ factor handles the $$i=0$$ case of $$(1-x^{2p^i-1})$$.) The sequence begins $$1,1,1,2,3,3,3,5,7,8,8,11,15,17,18,23,30,35,37,45$$ which matches OEIS A035362. That sequence has a much simpler description: partitions with parts $$4k$$ or $$4k+1$$. Why should that be the same?

Fortunately, before thinking too much about the connection, I computed more terms and realized that, in fact, the sequences do not match. The first discrepancy happens at $$n=28$$. The parts for the partitions counted here are everything of the form $$4k$$ or $$4k+1$$ up to 25, but not 28, which is a part for the OEIS description. That is, 28 is the smallest positive multiple of 4 that cannot be written as $$2p^i-2$$ for some prime $$p$$ and integer $$i \ge 0$$.

Back to your question, the asymptotics of the partitions you care about are bounded above by the partitions with parts of the form $$4k$$ and $$4k+1$$. The OEIS page includes an asymptotic expression for those given by Vaclav Kotesovec.

• I'm confused as to why you're varying $p$ in the product and fixing $i$. Shouldn't it be the other way around to compute the dimensions of the mod $p$ dual Steenrod algebra? – dvitek Mar 21 '20 at 2:43
• In addition, it seems like your generating function does not handle the difference between the polynomial and exterior algebras. I think the exterior algebra terms should have a plus sign, not a minus sign, and go in the numerator. – dvitek Mar 21 '20 at 2:44
• To be completely explicit, it seems like you should have one generating function for each odd prime $p$ whose coefficients are the dimension of the appropriately-graded piece of the mod $p$ dual Steenrod algebra. That g.f. $d_p(z)$ should satisfy $$d_p(z) = \frac{\prod_{i \ge 0}\left(1+x^{2p^i-1}\right)}{\prod_{i \ge 1}\left(1-x^{2p^i-2}\right)}.$$ – dvitek Mar 21 '20 at 2:48
• @dvitek Thanks, I didn't understand that $p$ is fixed. I did allow $i$ to vary, but only put that in the text, not the formula. For your explicit generating function, why do the $\tau_i$ terms each appear at most once, while the $\xi_i$ terms can appear with repetition? I.e., why isn't the generating function $$\frac{1}{\left(\prod_{i\ge0}(1-x^{2p^i-1})\right)\left(\prod_{i\ge1}(1-x^{2p^i-2})\right)}?$$ – Brian Hopkins Mar 21 '20 at 14:14
• The $\tau_i$ terms appear at most once because they live in an exterior algebra, not a polynomial algebra like the $\xi_i$ terms. In an exterior algebra the square of any element is zero (and in this particular case we don't have any funny characteristic-2 business to worry about either) so the $\tau_i$ appear at most once. – dvitek Mar 21 '20 at 19:13