Steenrod-Milnor and Tournament Sequences

Description of the problem

A (finite) sequence of positive integers \((t_n)\) is called a tournament sequence if \(t_n < t_{n+1}\leq 2t_n\) for every \(n\) for which \(t_n\) is defined.

On the other hand I will call a finite sequence of positive integers \((m_n)\) a Steenrod-Milnor sequence if \(1\leq m_{n+1} \leq \frac{m_n}{2}\). These sequences appear in the Milnor basis of the mod 2 Steenrod algebra.

Today, I will write two similar common lisp functions that will generate all tournament sequences, and all Steenrod-Milnor sequences satisfying certain constraints.

Tournament Sequences

Notice that if \((t_1,...,t_n)\) is a tournament sequence of length \(n\), then for every integer \(t_n < a\leq 2 t_n\), the augmented sequence \((t_1,...,t_n,a)\) is another tournament sequence of length \(n+1\).

Before I give my implementation, I am going to need a utility function:

(defun range (a b &optional acc)
   (if (= a b)
       (cons a acc)
       (range (1+ a) b (cons a acc))))

RANGE

Now, we can write the following recursive function:

(defun tournament (a n)
  (if (= n 1)
      (list (list a))
      (mapcar (lambda (ts) (cons a ts))
              (mapcan (lambda (m) (tournament m (1- n))) (range (1+ a) (* 2 a))))))

TOURNAMENT

Let us test. Here is the list of all tournament sequences of length 4 starting at 2:

(tournament 2 4)

((2 4 8 16) (2 4 8 15) (2 4 8 14) (2 4 8 13) (2 4 8 12) (2 4 8 11) (2 4 8 10)
 (2 4 8 9) (2 4 7 14) (2 4 7 13) (2 4 7 12) (2 4 7 11) (2 4 7 10) (2 4 7 9)
 (2 4 7 8) (2 4 6 12) (2 4 6 11) (2 4 6 10) (2 4 6 9) (2 4 6 8) (2 4 6 7)
 (2 4 5 10) (2 4 5 9) (2 4 5 8) (2 4 5 7) (2 4 5 6) (2 3 6 12) (2 3 6 11)
 (2 3 6 10) (2 3 6 9) (2 3 6 8) (2 3 6 7) (2 3 5 10) (2 3 5 9) (2 3 5 8)
 (2 3 5 7) (2 3 5 6) (2 3 4 8) (2 3 4 7) (2 3 4 6) (2 3 4 5))

Steenrod-Milnor Sequences

Similar to tournament sequences, this time if \((m_1,...,m_n)\) is a Steenrod-Milnor sequence then for every \(1\leq a\leq \frac{m_n}{2}\) the augmented sequence \((m_1,...,m_n,a)\) is another Milnor-Steenrod sequence. However, in the case \(\frac{m_n}{2}<1\), i.e. when \(m_n=1\), we can not augment the sequence by \(a\). If we have \(m_n=1\) then the sequence must terminate at that point.

(defun steenrod (n)
  (if (= n 1)
      (list (list 1))
      (mapcar (lambda (ms) (cons n ms))
              (mapcan #'steenrod (range 1 (floor n 2))))))

STEENROD

Let us test. Here is the list of all Steenrod-Milnor sequences starting at 27:

(steenrod 27)

((27 13 6 3 1) (27 13 6 2 1) (27 13 6 1) (27 13 5 2 1) (27 13 5 1)
 (27 13 4 2 1) (27 13 4 1) (27 13 3 1) (27 13 2 1) (27 13 1) (27 12 6 3 1)
 (27 12 6 2 1) (27 12 6 1) (27 12 5 2 1) (27 12 5 1) (27 12 4 2 1) (27 12 4 1)
 (27 12 3 1) (27 12 2 1) (27 12 1) (27 11 5 2 1) (27 11 5 1) (27 11 4 2 1)
 (27 11 4 1) (27 11 3 1) (27 11 2 1) (27 11 1) (27 10 5 2 1) (27 10 5 1)
 (27 10 4 2 1) (27 10 4 1) (27 10 3 1) (27 10 2 1) (27 10 1) (27 9 4 2 1)
 (27 9 4 1) (27 9 3 1) (27 9 2 1) (27 9 1) (27 8 4 2 1) (27 8 4 1) (27 8 3 1)
 (27 8 2 1) (27 8 1) (27 7 3 1) (27 7 2 1) (27 7 1) (27 6 3 1) (27 6 2 1)
 (27 6 1) (27 5 2 1) (27 5 1) (27 4 2 1) (27 4 1) (27 3 1) (27 2 1) (27 1))