Multiplication in the Steenrod Algebra

Question

Here's yet another Steenrod algebra question. Summary of the algorithm: I have a procedure that replaces a list of positive integers with a list of lists of positive integers. You need to repeatedly map this procedure over a list of lists and flatten the output until you reach a fixed point. Then for each sublist, if it appears an odd number of times, delete all but one occurrence. If it appears an even number of times, delete all occurrences. There is reference code at the bottom. The procedure for replacing a list with a list of lists is determined by a formula called the "Adem relation."

In order to represent an algebra, we need to know a basis for the algebra and also how to multiply things. From my previous question, we know the basis of the Steenrod algebra. In this question we're going to learn how to multiply Steenrod squares. The Steenrod algebra is generated by Steenrod squares \$\mathrm{Sq}^{i}\$ for \$i\$ a positive integer. It has a basis consisting of "admissible monomials" in the Steenrod squares.

A sequence of positive integers is called admissible if each integer is at least twice the next one. So for instance [7,2,1] is admissible because \$7 \geq 2*2\$ and \$2 \geq 2*1\$. On the other hand, [2,2] is not admissible because \$2 < 2*2\$. So \$\mathrm{Sq}^7\mathrm{Sq}^2\mathrm{Sq}^1\$ is an admissible monomial, but \$\mathrm{Sq}^2\mathrm{Sq}^2\$ is not.

Every inadmissible Steenrod monomial can be expressed as a sum of admissible Steenrod monomials. For example \$\mathrm{Sq}^2\mathrm{Sq}^2 = \mathrm{Sq}^3\mathrm{Sq}^1\$, where we see that the right hand side is admissible because \$3>2*1\$. As another example, \$\mathrm{Sq}^2\mathrm{Sq}^3 = \mathrm{Sq}^5 + \mathrm{Sq}^4\mathrm{Sq}^1\$.

Our goal is to express inadmissible Steenrod monomials as sums of admissible ones. There is a formula to express an inadmissible product of two Steenrod squares as a sum of admissible monomials called the Adem relation:

\$\displaystyle\mathrm{Sq}^{a}\mathrm{Sq}^{b} = \sum_{j=0}^{a/2} \binom{b-j-1}{a-2j} \mathrm{Sq}^{a+b-j}\mathrm{Sq}^{j} \quad\text{for a < 2*b}\$

where it's understood that \$\mathrm{Sq}^{a+b}\mathrm{Sq}^0 = \mathrm{Sq}^{a+b}\$ and where the binomial coefficients are taken mod 2. In fact all arithmetic on Steenrod monomials is computed mod 2, so for instance \$\mathrm{Sq}^2\mathrm{Sq}^1 + \mathrm{Sq}^2\mathrm{Sq}^1 = 0\$.

The algorithm to express a Steenrod monomial as a sum of admissible ones is to repeatedly find the location of an inadmissible pair, apply the Adem relation and get a sum of monomials and recurse on the resulting sum.

Goal:

Take as input a list representing a Steenrod monomial. Output the set of the admissible Steenrod monomials that appear in the reduced sum. This can be represented as a list without repeats or as any sort of set / dictionary / map, where presence of a key in the map determines whether a monomial is in the set. This is code golf so shortest code wins.

Helpful Formulas for Mod 2 Binomial coefficients

\$\displaystyle\binom{n}{k} =\begin{cases} 1 & n | k = n\\ 0 & \text{else}\end{cases} = \begin{cases} 1 & (n-k) \& k = 0\\ 0 & \text{else}\end{cases}\$ where \$|\$ and \$\&\$ are bit-or and bit-and.

Examples:

Input: [4,2]
Output: [[4,2]]

Since \$4 \geq 2*2\$ the sequence is already admissible and nothing needs to be done.

Input: [2,4]
Ouput: [[6], [5,1]] (order doesn't matter)

\$2 < 2*4\$ and the sequence has length 2 so we just need to apply the Adem relation once. We get

\$\mathrm{Sq}^2\mathrm{Sq}^4 = \displaystyle\sum_{j=0}^{1} \binom{3-j}{2-2j} Sq^{6-j}Sq^j = \binom{3}{2}\mathrm{Sq}^6 + \binom{2}{0}\mathrm{Sq}^5\mathrm{Sq}^1 = \mathrm{Sq}^6 + \mathrm{Sq}^5\mathrm{Sq}^1\$ where we used \$3\%2=1\$.

Input: [2,4,2]
Output: [[6, 2]]

The pair [2,4] or \$\mathrm{Sq}^2\mathrm{Sq}^4\$ is inadmissible so applying the Adem relation there we get \$\mathrm{Sq}^2\mathrm{Sq}^4\mathrm{Sq}^2 = \mathrm{Sq}^6\mathrm{Sq}^2 + \mathrm{Sq}^5\mathrm{Sq}^1\mathrm{Sq}^2\$. Now \$6>2*2\$ so \$\mathrm{Sq}^6\mathrm{Sq}^2\$ is admissible and can be left alone. On the other hand, \$1 < 2*2\$ so there is more work to do on the other term. \$\mathrm{Sq}^1\mathrm{Sq}^2 = \mathrm{Sq}^3\$ so \$\mathrm{Sq}^5\mathrm{Sq}^1\mathrm{Sq}^2 = \mathrm{Sq}^5\mathrm{Sq}^3\$.

Since \$5<2*3\$ this can be reduced again and in fact \$\mathrm{Sq}^5\mathrm{Sq}^3 = 0\$. So \$\mathrm{Sq}^2\mathrm{Sq}^4\mathrm{Sq}^2 = \mathrm{Sq}^6\mathrm{Sq}^2\$.

Input: [2, 3, 2]
Output: []

Both [2,3] and [3,2] are inadmisible pairs so we can start in either location here. \$\def\Sq{\mathrm{Sq}}\Sq^3\Sq^2=0\$, so if we start in the second position, we immediately see the output is empty. Starting in the first position, we have \$\Sq^2\Sq^3 = \Sq^5 + \Sq^4\Sq^1\$. Then \$\Sq^5\Sq^2\$ is admissible, but \$\Sq^4\Sq^1\Sq^2\$ isn't.

\$\Sq^4\Sq^1\Sq^2 = \Sq^4\Sq^3 = \Sq^5\Sq^2\$ so the answer is \$\Sq^5\Sq^2 + \Sq^5\Sq^2 = 0\$ (all of our arithmetic is reduced mod 2).

Test cases:

Input: [1, 1]
Output: []

Input: [2,2]
Output: [[3,1]]

Input: [2, 2, 2]
Output: [[5,1]]

Input: [2,2,2,2]
Output: []

Input: [4, 2, 4, 2]
Output: [[8,3,1], [10,2]] (Again, order doesn't matter)

Input: [2, 4, 2, 4]
Output: [[8,3,1],[9,2,1],[9,3],[10,2],[11,1]]

Input: [6, 6, 6]
Output: [[12, 5, 1], [13, 4, 1], [13, 5]]

Input: [6,6,6,6]
Output: []

Input: [4, 2, 1, 4, 2, 1, 4, 2, 1]
Output: [[15,5,1],[17,3,1]]

Input: [4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1]
Output: []

Reference Implementations:

There is a javascript calculator here, which is an easy way to get more test cases. https://math.berkeley.edu/~kruckman/adem/

Here is a python implementation:

def make_mono_admissible(result, mono):
    """Reduce a Steenrod monomial into a linear combination of admissible Steenrod monomials
       "mono" should be a tuple representing your Steenrod monomial.
       Writes answer into "result" which should be an empty dictionary.
    """
    inadmissible_indices = [j for j in range(len(mono) - 1) if mono[j] < 2*mono[j+1]]
    if not inadmissible_indices:
        if mono in result:
            del result[mono]
        else:
            result[mono] = 1
        return
    i = inadmissible_indices[0]
    a = mono[i]
    b = mono[i + 1]
    # Do adem relation for Sq^a Sq^b
    for j in range(1 + a//2):
        # check if binom(b - j - 1, a - 2j) % 2 == 1
        if (b - a + j - 1) & (a-2*j) == 0: 
            new_pair = (a+b-j, j) if j>0 else (a+b,)
            make_mono_admissible(result, mono[:i] + new_pair + mono[i+2:])

As I was trying to make a TLDR, I made the following Mathematica code:

makeMonoAdmissibleStep[{a___Integer}] := {{a}}
(* If a < 2b for consecutive entries we can apply Adem relation *)
makeMonoAdmissibleStep[{start___, {p___, a_, b_, q___}, rest___}] /; a < 2 b := 
{start, 
   Sequence@@
     (* If the mod 2 binomial coefficient is 1, 
        add a new list with a, b replaced by a+b-#, # *)
     If[Mod[Binomial[b - # - 1, a - 2 #], 2] == 1, {p, a + b - #, # , q}, 0]&
         /@ Range[0, a/2], 
 rest}] /. 0 -> Sequence[]
(* If the same list appears twice, drop it *)
makeMonoAdmissibleStep[{a___, x_List, b___, x_List, c___}] := {a, c}
(*If we can't do anything else, we're done *)
makeMonoAdmissibleStep[x_] := x 
makeMonoAdmissible[l_] := FixedPoint[makeMonoAdmissibleStep, l]

Answer 1

Wolfram Language (Mathematica), 225 218 206 203 200 196 bytes

q=SetAttributes
{p,s}~q~Flat
s~q~Orderless
a_~s~a_:=s[]
p@0:=p[]
f=FixedPoint[#~Distribute~s&/@#/.a_~p~b_/;a<2b:>s@@(If[BitAnd[b+#-a-1,a-2#]<1,p[a+b-#,#],s[]]&)/@Range[0,a/2]&,s[p@@#]]/.s|p->List&

Try it online!

We represent the intermediate list as an expression with [[15,5,1],[17,3,1]] being s[p[15,5,1], p[17,3,1]]. In this format, Mathematica's expression engine does some heavy lifting, and allows us to use Distribute. However, it takes some work to convert between this format and lists.