Generate basis elements of the Steenrod algebra

Question

The Steenrod algebra is an important algebra that comes up in algebraic topology. The Steenrod algebra is generated by operators called "Steenrod squares," one exists for each positive integer i. There is a basis for the Steenrod algebra consisting of "admissible monomials" in the squaring operations. It is our goal to generate this basis.

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, [3,2] is not admissible because \$3 < 2*2\$. (In topology we would write \$\mathrm{Sq}^7 \mathrm{Sq}^2\mathrm{Sq}^1\$ for the sequence [7,2,1]).

The degree of a sequence is the total of it's entries. So for instance, the degree of [7,2,1] is \$7 + 2 + 1 = 10\$. The excess of an admissible sequence is the first element minus the total of the remaining elements, so [7,2,1] has excess \$7 - 2 - 1 = 4\$.

Task

Write a program that takes a pair of positive integers (d,e) and outputs the set of all admissible sequences of degree d and excess less than or equal to e. The output is a set so the order of the admissible sequences doesn't matter.

Examples:

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

Here we are looking for admissible sequences with total 3. There are two options, [3] and [2,1]. ([1,1,1] and [1,2] have sum 3 but are not admissible). The excess of [3] is 3 and the excess of [2,1] is \$2-1 = 1\$. Thus, the only sequence with excess \$\leq1\$ is [2,1].

Input: 6, 6
Output: [[6], [5, 1], [4, 2]] (or any reordering, e.g., [[5,1],[4,2],[6]])

Since excess is always less than or equal to degree, we have no excess condition. Thus, we're just trying to find all admissible sequences of degree 6. The options are [6], [5, 1], and [4, 2]. (These have excess \$6\$, \$5-1 = 4\$, and \$4-2=2\$.)

Input: 10, 5
Output: [[7,3], [7,2,1], [6,3,1]]

The admissible sequences of degree 10 are:

[[10], [9,1], [8,2], [7,3], [7,2,1], [6,3,1]]

These have excess \$10\$, \$9-1 = 8\$, \$8-2 = 6\$, \$7-3 = 4\$, \$7-2-1 = 4\$, and \$6-3-1=2\$ respectively, so the last three all work.

Scoring

This is code golf: Shortest solution in bytes wins.

Test cases:

Any reordering of the output is equally good, so for input (3, 3), outputs [[3],[2,1]] or [[2,1],[3]] are equally acceptable (however [[1,2],[3]] isn't).

Input: 1, 1
Output: [[1]]

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

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

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

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

Input: 6, 1
Output: []

Input: 7, 7
Output: [[7], [6,1], [4,2,1], [5,2]]

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

Input: 10, 10
Output: [[10], [9,1], [7,2,1], [6,3,1], [8,2], [7,3]]

Input: 10, 5
Output: [[7,3], [7,2,1], [6,3,1]]

Input: 26, 4
Output: [15, 7, 3, 1]

Input: 26, 6
Output: [[16, 7, 2, 1], [16, 6, 3, 1], [15, 7, 3, 1], [16, 8, 2], [16, 7, 3]]

Answer 1

05AB1E, 16 12 bytes

Saved 4 bytes thanks to Grimy

Åœíʒx¦@P}ʒÆ@

Try it online!

Explanation

Ŝ              # integer partitions
  í             # reverse each
   ʒ    }       # filter, keep only elements true under:
    x           # each element doubled
     ¦          # remove the first element in the doubled list
      @         # compare with greater than or equal with the non-doubled
       P        # product
         ʒ      # filter, keep only elements true under:
          Æ     # reduce by subtraction
           @    # compare with greater than or equal to second input

Answer 2

Wolfram Language (Mathematica), 67 62 bytes

Cases[IntegerPartitions@#,a_/;2a[[1]]-#<=#2>Max@Ratios@a<=.5]&

Try it online!

-4 bytes by @attinat

• IntegerPartitions@d : Get all lists of integers summing to d
• Cases[,...]: Filter by the following condition:
  • 2#& @@# - d <= e &&: Twice the first element minus the sum is less than e, and...
  • Max@Ratios@#<=.5: Ratios of successive elements of the list are all less than 1/2.

Because e is less than .5, we can turn this into a chained inequality.

For a few extra bytes, this is significantly faster: Try it online!

Answer 3

Jelly,  16  15 bytes

-1 thanks to Erik the Outgolfer (a smart adjustment to the checking allowing a single filter)

:Ɲ;_/>¥’Ạ
ŒṗUçƇ

A dyadic link accepting a positive integer, d, on the left and a positive integer, e, on the right which yields a list of lists of positive integers.

Try it online! (the footer formats the results to avoid list the implicit list formatting Jelly does as a full program)

How?

:Ɲ;_/>¥’Ạ - Link 1: admissible and within excess limit? descending list, L; excess limit, e
 Ɲ        - neighbour-wise:
:         -   integer division  -- admissible if all these are >1
      ¥   - last two links as a dyad - i.e. f(L,e):
    /     -   reduce (L) by:
   _      -     subtraction
     >    -   greater than (e)? (vectorises)  -- within excess if all these are ==0
  ;       - concatenate
       ’  - decrement (vectorises)
        Ạ - all (non-zero)?

ŒṗUçƇ - Main link: integer, d; integer, e
Œṗ    - partitions (of d)
  U   - reverse each
    Ƈ - filter keep those (v in that) for which:
   ç  -   call last Link (1) as a dyad - i.e. f(v, e)

Answer 4

Haskell, 59 58 54 bytes

1 byte saved thanks to nimi

4 bytes saved thanks to xnor

0#_=[[]]
d#m=do i<-[1..div(m+d)2];(i:)<$>(d-i)#(2*i-d)

Try it online!

Answer 5

Python 3, 213 bytes

Giant list comprehension. Most likely not the best way to do this, but I can't figure out how to skip the if statements

import itertools as z
f=lambda d,e:[c for c in [[b for b in list(z.permutations(range(1,d+1),i)) if sum(b)==d and b[0]-sum(b[1:i])<=e and all([b[i]>=b[i+1]*2 for i in range(len(b)-1)])] for i in range(1,5)] if c]

Python 3, 172 bytes

from itertools import*
r=range
f=lambda d,e:filter(len,[[b for b in permutations(r(1,d+1),i)if d==sum(b)and~e<d-2*b[0]and all(i>=j*2for i,j in zip(b,b[1:]))]for i in r(5)])

Try it online!

As according to edits by @Jonas Ausevicius

Answer 6

JavaScript (V8),  88 87  81 bytes

Takes input as (e)(d). Prints the sequences to STDOUT.

e=>g=(d,s=x=d,a=[])=>s>0?d&&g(d-1,s,a,g(d>>1,s-d,[...a,d])):a[s]*2-x<=e&&print(a)

Try it online!

Commented

e =>                  // e = maximum excess
  g = (               // g is a recursive function taking:
    d,                //   d   = expected degree; actually used as the next candidate
                      //         term of the sequence in the code below
    s =               //   s   = current sum, initialized to d; we want it to be equal
                      //         to 0 when a sequence is complete
    x = d,            //   x   = copy of the expected degree
    a = []            //   a[] = current sequence
  ) =>                //
    s > 0 ?           // if s is positive:
      d &&            //   if d is not equal to 0:
        g(            //     outer recursive call:
          d - 1,      //       decrement d
          s,          //       leave s unchanged
          a,          //       leave a[] unchanged
          g(          //       inner recursive call:
            d >> 1,   //         update d to floor(d / 2)
            s - d,    //         subtract d from s
            [...a, d] //         append d to a[]
          )           //       end of inner recursive call
        )             //     end of outer recursive call
    :                 //   else:
      a[s] * 2 - x    //     s if either 0 (success) or negative (failure)
                      //     if s is negative, a[s] is undefined and this expression
                      //     evaluates to NaN, forcing the test to fail
      <= e            //     otherwise, we test whether the excess is valid
      && print(a)     //     and we print a[] if it is

Answer 7

Pyth, 23 bytes

f!>-FTvzf!<#2/MCtBT_M./

Try it online!

f!>-FTvzf!<#2/MCtBT_M./Q   Implicit: Q=input 1, vz=input 2
                           Trailing Q inferred
                     ./Q   Generate partitions of Q (ordered lists of integers which sum to Q)
                   _M      Reverse each
        f                  Filter keep elements of the above, as T, where:
               CtBT          Pair the set with itself without the first element and transpose
                             This yields all adjacent pairs of values
             /M              Integer divide each pair
           #                 Filter keep elements...
          < 2                ... less than 2
                             For admissible sequences this will be empty
         !                   Logical NOT - maps [] to true, populated lists to false
                           Result of filter are all admissible sequences
f                          Filter keep the above, as T, where:
   -FT                       Reduce T by subtraction to get degree
 !>   vz                     Is the above not greater than vz?
                           Implicit print

Answer 8

Charcoal, 42 bytes

Ｆθ⊞υ⟦⊕ι⟧ＦυＦ…·⊗§ι⁰θ⊞υ⁺⟦κ⟧ιＩΦυ›⁼Σιθ‹η⁻⊗§ι⁰Σι

Try it online! Link is to verbose version of code. Explanation:

Ｆθ⊞υ⟦⊕ι⟧

First create a list of lists from [1]..[d].

ＦυＦ…·⊗§ι⁰θ⊞υ⁺⟦κ⟧ι

For each list create new lists by prefixing all the numbers from the doubled first number up to d and append those lists to the list of lists to be processed. This ensures that all admissible sequences containing numbers not greater than d are created.

ＩΦυ›⁼Σιθ‹η⁻⊗§ι⁰Σι

Output only those lists whose degree is d and excess is not greater than e. (The sum of the degree and excess is equal to twice the first number of the list.)

Answer 9

Python 3, 156 bytes

lambda d,e:[x for y in range(5)for x in permutations(range(1,d+1),y)if all(i>=j*2for i,j in zip(x,x[1:]))and d==sum(x)and~e<d-2*x[0]]
from itertools import*

takes d,e as input; outputs list of tuples

Similar to @OrangeCherries answer and help from comments; but more bytes saved

Try it online!

Answer 10

Jelly, 18 bytes

ŒṗU:Ɲ’ẠƊƇUṪ_SƊ’<ʋƇ

Try it online!

Answer 11

Ruby, 78 bytes

g=->(d,e,m=1){d<m ?[]:g[d-m,e+m,m*2].map{|q|q+[m]}+g[d,e,m+1]|(d>e ?[]:[[d]])}

Try it online!