Combinatorial Bounds on the Peterson Hit Problem via Certified Matrix Minors

Abstract

The Peterson hit problem seeks a minimal set of generators for the polynomial algebra ${\mathcal{P}}_k={\mathbb{F}}_2[x_1,\dots ,x_k]$ as a module over the mod--2 Steenrod algebra. While completely resolved for $k\le 4$, the unrestricted problem remains widely open for $k\ge 5$, where the combinatorial explosion of basis elements renders exact algorithmic computation intractable. To bypass full Gaussian elimination, we model the degree--$d$ hit space via a sparse matrix driven by the Cartan formula and Lucas's theorem, shifting the focus to the construction of certified matrix minors. We first prove that strict spike monomials exactly characterize the zero rows, establishing a hard structural limit on coordinate-level annihilators. To bound the matrix rank from above (cohit lower bound), we derive exact zero-column formulae, which are strictly refined by the exact homology of the ${\mathrm{Sq}}^1$-layer and systematic linear dependencies induced by Adem relations. To bound the rank from below (cohit upper bound), we extract explicit independent column families: singleton columns yield permutation minors, acyclic pivot systems optimize triangular minors across all row orders, and $q$-support columns are formalized through hypergraph incidence. Crucially, we identify a congruence family that decomposes precisely into simplicial boundary matrices over ${\mathbb{F}}_2$, yielding a sharp closed-form rank formula. The resulting two-sided bounds are universally computable for every $k\ge 1$ and $d\ge 0$. Significantly, these results establish the absolute limits of purely combinatorial approaches to the hit problem, cleanly separating universal discrete certificates from the degree-specific resolutions provided by representation theory and weight filtrations.

43 pages. We welcome constructive comments/feedback