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.

  • 1
    $\begingroup$ But even the number of all partitions is subexponential. $p_s(n)$ grows as $\exp(c(\log n)^2)$. $\endgroup$ – Fedor Petrov Nov 25 '19 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 '19 at 0:31
  • 3
    $\begingroup$ The end of Theorem 2 in that paper says that $W(z)$ is bounded on the real line. $\endgroup$ – MTyson Nov 26 '19 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 '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.

  • 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 '20 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 '20 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 '20 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$ – Brian Hopkins Mar 21 '20 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 '20 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.