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.


  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.

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

1 Answer 1


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.

  • 2
    $\begingroup$ 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? $\endgroup$
    – dvitek
    Mar 21, 2020 at 2:43
  • $\begingroup$ 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. $\endgroup$
    – dvitek
    Mar 21, 2020 at 2:44
  • $\begingroup$ 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)}.$$ $\endgroup$
    – dvitek
    Mar 21, 2020 at 2:48
  • $\begingroup$ @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)}?$$ $\endgroup$ Mar 21, 2020 at 14:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – dvitek
    Mar 21, 2020 at 19:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .