Fixed points, normalizers, and the enumeration of cyclic matroids

A matroid on a finite set \(E\) is determined by its rank function \(r\colon 2^E\to\mathbb Z_{\ge 0}\). The rank axioms can be written as

\[ r(\varnothing)=0,\qquad 0\le r(A)\le |A|, \]

\[ A\subseteq B\Longrightarrow r(A)\le r(B), \]

and

\[ r(A)+r(B)\ge r(A\cup B)+r(A\cap B). \]

Thus the matroids on \(E\) are precisely the integral points of the bounded polytope cut out by these inequalities. If a permutation group \(G\leq S_E\) acts on \(E\), then a \(G\)-invariant matroid is simply an integral rank function in the fixed-point subspace. This elementary observation becomes useful when \(G\) has few orbits on the Boolean lattice.

Here I specialize to the regular cyclic group. Put

\[ E_n=\mathbb Z/n\mathbb Z,\qquad C_n=\langle\tau\rangle,\qquad \tau(x)=x+1. \]

I will call a matroid in which this specified cycle is an automorphism a standard cyclic matroid. This distinction matters: a matroid may admit a regular cyclic automorphism without being presented with this particular cyclic action.

The terminology and the structural study of matroids admitting an \(n\)-cycle are due to Alfarano, Khathuria, and Tinani, On cyclic matroids and their applications. The fixed-point and normalizer discussion below is not meant as a new theory; it is the form in which the general theory of cyclic or circulant objects appears for matroid rank functions. For the general isomorphism problem for circulant objects, see Muzychuk and Ponomarenko, Testing isomorphism of circulant objects in polynomial time.

The point of this post is computational: the fixed-point description gives a small exact integer system, and the normalizer action tells us exactly which quotient the obvious modular-multiplier calculation computes.

1. Orbit coordinates for invariant rank functions

Let \(G\leq S_E\). A \(G\)-invariant rank function is constant on every \(G\)-orbit in \(2^E\). Hence the fixed subspace has one coordinate for every orbit of nonempty subsets. If \(c(g)\) is the number of cycles of \(g\) on \(E\), then \(g\) fixes exactly \(2^{c(g)}\) subsets. Burnside’s lemma therefore gives

\[ d_G=\frac1{|G|}\sum_{g\in G}2^{c(g)}-1 \]

nonempty subset-orbits.

For the regular cyclic group this becomes

\[ d_n=\frac1n\sum_{k=0}^{n-1}2^{\gcd(k,n)}-1. \]

The following SageMath code compares the Burnside count with the orbit count obtained directly from bit masks. I stop at \(n=8\) throughout this post.

from functools import lru_cache
from math import gcd

MAX_N = 8


def popcount(mask):
    return int(mask).bit_count()


def cyclic_shift(mask, n):
    full = (1 << n) - 1
    return ((mask << 1) | (mask >> (n - 1))) & full


@lru_cache(None)
def cyclic_orbit_data(n):
    """Return the nonempty C_n-orbits of subsets and the orbit lookup table."""
    full = (1 << n) - 1
    sub_to_orbit = [-1] * (full + 1)
    orbits = []

    for mask in range(1, full + 1):
        if sub_to_orbit[mask] != -1:
            continue

        orbit_index = len(orbits)
        orbit = []
        current = mask

        while sub_to_orbit[current] == -1:
            sub_to_orbit[current] = orbit_index
            orbit.append(current)
            current = cyclic_shift(current, n)

        orbits.append(tuple(orbit))

    return tuple(orbits), tuple(sub_to_orbit)


def burnside_dimension(n):
    return sum(2 ** gcd(k, n) for k in range(n)) // n - 1


print(" n | full coordinates | cyclic orbit coordinates")
print("---+------------------+-------------------------")
for n in range(1, MAX_N + 1):
    direct = len(cyclic_orbit_data(n)[0])
    burnside = burnside_dimension(n)
    assert direct == burnside
    print(f"{n:2d} | {2**n - 1:16d} | {direct:23d}")

 n | full coordinates | cyclic orbit coordinates
---+------------------+-------------------------
 1 |                1 |                       1
 2 |                3 |                       2
 3 |                7 |                       3
 4 |               15 |                       5
 5 |               31 |                       7
 6 |               63 |                      13
 7 |              127 |                      19
 8 |              255 |                      35

For prime \(p\) the formula simplifies to

\[ d_p=\frac{2^p-2}{p}+1. \]

Notice what has, and has not, happened. We have reduced the ambient coordinate space from one coordinate for every nonempty subset to one coordinate for every cyclic orbit of subsets. We have not replaced the Boolean lattice by a quotient lattice: the orbits of \(A\) and \(B\) do not by themselves determine the orbit of \(A\cap B\) or \(A\cup B\). Relative position still matters. Therefore all induced submodularity inequalities must be retained.

2. The fixed-point integer system

Let \(\Omega_1,\ldots,\Omega_d\) be the nonempty \(C_n\)-orbits in \(2^{E_n}\) and write \(y_i\) for the common rank of the subsets in \(\Omega_i\). The matroid axioms become the following finite integer system:

\(0\leq y_i\leq |A|\) for \(A\in\Omega_i\);
\(y_i\leq y_j\) whenever some \(A\in\Omega_i\) and \(B\in\Omega_j\) satisfy \(A\subseteq B\);
for every pair \(A,B\subseteq E_n\), \[ y_{\Omega(A)}+y_{\Omega(B)}\ge y_{\Omega(A\cup B)}+y_{\Omega(A\cap B)}, \] where \(y_{\Omega(\varnothing)}=0\).

Conversely, every integral solution gives a matroid rank function, because the expanded function on \(2^{E_n}\) satisfies the ordinary rank axioms. Thus this system describes the fixed-point set

\[ X_n:=\mathfrak M_n^{C_n} \]

exactly, where \(\mathfrak M_n\) is the set of matroids on the labeled ground set \(E_n\).

The implementation below is a pure Sage/Python branch-and-bound search. It has no Z3 dependency. Monotonicity inequalities are used immediately to narrow the range of the variable currently being assigned. Each submodularity inequality is stored at the largest variable index occurring in it, so it is checked as soon as all of its variables have been assigned.

@lru_cache(None)
def cyclic_constraint_system(n):
    orbits, sub_to_orbit = cyclic_orbit_data(n)
    full = (1 << n) - 1
    d = len(orbits)

    bounds = tuple(popcount(orbit[0]) for orbit in orbits)

    # Monotonicity constraints.  For each variable i we retain exactly the
    # constraints involving i and an earlier variable, since variables are
    # assigned in increasing order.
    lower = [set() for _ in range(d)]
    upper = [set() for _ in range(d)]

    for A in range(1, full + 1):
        oA = sub_to_orbit[A]
        for B in range(1, full + 1):
            if A == B or (A & B) != A:
                continue
            oB = sub_to_orbit[B]
            if oA == oB:
                continue
            if oA < oB:
                lower[oB].add(oA)       # y_oB >= y_oA
            else:
                upper[oA].add(oB)       # y_oA <= y_oB

    lower = tuple(tuple(sorted(s)) for s in lower)
    upper = tuple(tuple(sorted(s)) for s in upper)

    # Submodularity constraints, deduplicated in orbit coordinates and
    # bucketed by the last variable needed to evaluate them.
    submod_at = [[] for _ in range(d)]
    seen = set()

    for A in range(1, full + 1):
        for B in range(A + 1, full + 1):
            union = A | B
            intersection = A & B

            oA = sub_to_orbit[A]
            oB = sub_to_orbit[B]
            oU = sub_to_orbit[union]
            oI = sub_to_orbit[intersection] if intersection else -1

            if oA > oB:
                oA, oB = oB, oA

            constraint = (oA, oB, oU, oI)
            if constraint in seen:
                continue
            seen.add(constraint)

            last = max(oA, oB, oU, oI)
            submod_at[last].append(constraint)

    submod_at = tuple(tuple(bucket) for bucket in submod_at)
    return bounds, lower, upper, submod_at


@lru_cache(None)
def standard_cyclic_matroids(n):
    """All rank vectors fixed by the standard regular C_n action."""
    bounds, lower, upper, submod_at = cyclic_constraint_system(n)
    d = len(bounds)
    assignment = [-1] * d
    solutions = []

    def search(index):
        if index == d:
            solutions.append(tuple(assignment))
            return

        low = 0
        high = bounds[index]

        for predecessor in lower[index]:
            low = max(low, assignment[predecessor])

        for successor in upper[index]:
            high = min(high, assignment[successor])

        for value in range(low, high + 1):
            assignment[index] = value
            valid = True

            for oA, oB, oU, oI in submod_at[index]:
                vA = assignment[oA]
                vB = assignment[oB]
                vU = assignment[oU]
                vI = assignment[oI] if oI >= 0 else 0

                if vA + vB < vU + vI:
                    valid = False
                    break

            if valid:
                search(index + 1)

        assignment[index] = -1

    search(0)
    return tuple(solutions)

It is useful to verify the returned vectors by expanding them back to all subsets and checking the rank axioms independently of the branch-and-bound bookkeeping.

def expand_rank_vector(n, solution):
    orbits, sub_to_orbit = cyclic_orbit_data(n)
    full = (1 << n) - 1
    rank = [0] * (full + 1)
    for mask in range(1, full + 1):
        rank[mask] = solution[sub_to_orbit[mask]]
    return tuple(rank)


def is_matroid_rank_vector(n, solution):
    full = (1 << n) - 1
    rank = expand_rank_vector(n, solution)

    if rank[0] != 0:
        return False

    for A in range(full + 1):
        if not (0 <= rank[A] <= popcount(A)):
            return False

    for A in range(full + 1):
        for B in range(full + 1):
            if (A & B) == A and rank[A] > rank[B]:
                return False
            if rank[A] + rank[B] < rank[A | B] + rank[A & B]:
                return False

    return True


for n in range(1, MAX_N + 1):
    solutions = standard_cyclic_matroids(n)
    assert all(is_matroid_rank_vector(n, solution) for solution in solutions)
    print(f"n={n:2d}: {len(solutions)} standard cyclic matroids")

n= 1: 2 standard cyclic matroids
n= 2: 3 standard cyclic matroids
n= 3: 4 standard cyclic matroids
n= 4: 6 standard cyclic matroids
n= 5: 6 standard cyclic matroids
n= 6: 13 standard cyclic matroids
n= 7: 12 standard cyclic matroids
n= 8: 34 standard cyclic matroids

This count is

\[ a_n:=|X_n|. \]

It is a count on a fixed labeled cyclic set: the standard subgroup \(C_n\leq S_n\) has been chosen in advance.

3. Duality as a consistency check

Duality preserves cyclic invariance. If \(M\) has rank function \(r\) and full rank \(r(E_n)\), then

\[ r^*(A)=|A|-r(E_n)+r(E_n\setminus A). \]

The next block constructs the dual rank vector in orbit coordinates and checks that the computed solution set is closed under duality.

def dual_rank_vector(n, solution):
    orbits, sub_to_orbit = cyclic_orbit_data(n)
    full = (1 << n) - 1
    full_orbit = sub_to_orbit[full]
    total_rank = solution[full_orbit]

    dual = []
    for orbit in orbits:
        A = orbit[0]
        complement = full - A
        complement_rank = 0 if complement == 0 else solution[sub_to_orbit[complement]]
        dual.append(popcount(A) - total_rank + complement_rank)

    return tuple(dual)


for n in range(1, MAX_N + 1):
    solutions = standard_cyclic_matroids(n)
    solution_set = set(solutions)
    assert all(dual_rank_vector(n, solution) in solution_set for solution in solutions)
    print(f"n={n:2d}: duality check passed")

n= 1: duality check passed
n= 2: duality check passed
n= 3: duality check passed
n= 4: duality check passed
n= 5: duality check passed
n= 6: duality check passed
n= 7: duality check passed
n= 8: duality check passed

We can also display the rank distribution without inserting any numerical data by hand.

from collections import Counter

for n in range(1, MAX_N + 1):
    solutions = standard_cyclic_matroids(n)
    _, sub_to_orbit = cyclic_orbit_data(n)
    full = (1 << n) - 1
    full_orbit = sub_to_orbit[full]
    distribution = Counter(solution[full_orbit] for solution in solutions)
    print(f"n={n:2d}: {sorted(distribution.items())}")

n= 1: [(0, 1), (1, 1)]
n= 2: [(0, 1), (1, 1), (2, 1)]
n= 3: [(0, 1), (1, 1), (2, 1), (3, 1)]
n= 4: [(0, 1), (1, 1), (2, 2), (3, 1), (4, 1)]
n= 5: [(0, 1), (1, 1), (2, 1), (3, 1), (4, 1), (5, 1)]
n= 6: [(0, 1), (1, 1), (2, 3), (3, 3), (4, 3), (5, 1), (6, 1)]
n= 7: [(0, 1), (1, 1), (2, 1), (3, 3), (4, 3), (5, 1), (6, 1), (7, 1)]
n= 8: [(0, 1), (1, 1), (2, 3), (3, 5), (4, 14), (5, 5), (6, 3), (7, 1), (8, 1)]

4. The normalizer of the regular cycle

The natural first attempt at removing labels is to quotient by relabelings that preserve the chosen regular cyclic subgroup. Its normalizer is

\[ N_{S_n}(C_n) \cong C_n\rtimes\operatorname{Aut}(C_n) \cong \mathbb Z/n\mathbb Z\rtimes(\mathbb Z/n\mathbb Z)^\times. \]

Concretely, its permutations are the affine maps

\[ x\longmapsto ax+b\pmod n, \qquad a\in(\mathbb Z/n\mathbb Z)^\times. \]

The translation subgroup \(C_n\) already fixes every element of \(X_n\), so the effective action on rank vectors is just the multiplier group \((\mathbb Z/n\mathbb Z)^\times\).

def units_mod_n(n):
    if n == 1:
        return (1,)
    return tuple(a for a in range(1, n) if gcd(a, n) == 1)


def multiply_mask(mask, a, n):
    result = 0
    for bit in range(n):
        if mask & (1 << bit):
            result |= 1 << ((a * bit) % n)
    return result


@lru_cache(None)
def multiplier_maps(n):
    orbits, sub_to_orbit = cyclic_orbit_data(n)
    maps = []

    for a in units_mod_n(n):
        mapping = []
        for orbit in orbits:
            image = multiply_mask(orbit[0], a, n)
            mapping.append(sub_to_orbit[image])
        maps.append(tuple(mapping))

    return tuple(maps)


def multiplier_image(solution, mapping):
    # Depending on left/right action conventions one may use the inverse
    # mapping instead.  Since all units and their inverses occur, the orbit
    # and hence the canonical representative are the same.
    return tuple(solution[mapping[i]] for i in range(len(mapping)))


def normalizer_canonical_form(n, solution):
    return min(multiplier_image(solution, mapping)
               for mapping in multiplier_maps(n))


@lru_cache(None)
def normalizer_classes(n):
    classes = {}
    for solution in standard_cyclic_matroids(n):
        canonical = normalizer_canonical_form(n, solution)
        classes.setdefault(canonical, []).append(solution)
    return tuple((canonical, tuple(members))
                 for canonical, members in sorted(classes.items()))

The quotient computed here is

\[ b_n:=|X_n/N_{S_n}(C_n)|. \]

The following is the main numerical summary of this post. Every entry is computed when the file is processed.

print(" n | orbit variables | fixed by standard C_n | normalizer classes")
print("---+-----------------+-----------------------+-------------------")
for n in range(1, MAX_N + 1):
    d = len(cyclic_orbit_data(n)[0])
    a_n = len(standard_cyclic_matroids(n))
    b_n = len(normalizer_classes(n))
    print(f"{n:2d} | {d:15d} | {a_n:21d} | {b_n:17d}")

 n | orbit variables | fixed by standard C_n | normalizer classes
---+-----------------+-----------------------+-------------------
 1 |               1 |                     2 |                 2
 2 |               2 |                     3 |                 3
 3 |               3 |                     4 |                 4
 4 |               5 |                     6 |                 6
 5 |               7 |                     6 |                 6
 6 |              13 |                    13 |                13
 7 |              19 |                    12 |                10
 8 |              35 |                    34 |                29

For a more detailed view, we can ask how large the normalizer orbits are.

for n in range(1, MAX_N + 1):
    orbit_sizes = sorted(len(members) for _, members in normalizer_classes(n))
    print(f"n={n:2d}: normalizer-orbit sizes = {orbit_sizes}")

n= 1: normalizer-orbit sizes = [1, 1]
n= 2: normalizer-orbit sizes = [1, 1, 1]
n= 3: normalizer-orbit sizes = [1, 1, 1, 1]
n= 4: normalizer-orbit sizes = [1, 1, 1, 1, 1, 1]
n= 5: normalizer-orbit sizes = [1, 1, 1, 1, 1, 1]
n= 6: normalizer-orbit sizes = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
n= 7: normalizer-orbit sizes = [1, 1, 1, 1, 1, 1, 1, 1, 2, 2]
n= 8: normalizer-orbit sizes = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 4]

5. Why normalizer classes are not ordinary isomorphism classes

This is the conceptual point at which one has to be careful.

Let \(S_n\) act on all labeled matroids on \(E_n\), and let \(C_n\) be the standard regular cyclic subgroup. An ordinary isomorphism between two members of \(X_n\) need not normalize this chosen copy of \(C_n\). Consequently there is a natural surjection

\[ X_n/N_{S_n}(C_n) \longrightarrow \{\text{ordinary isomorphism classes of matroids admitting an }n\text{-cycle}\}, \]

but there is no reason for this map to be injective.

There is a clean group-theoretic interpretation. The quotient \(X_n/N_{S_n}(C_n)\) classifies matroids together with a distinguished regular cyclic subgroup of their automorphism group, up to isomorphism of such pairs. After forgetting the distinguished subgroup, several normalizer classes can collapse to a single ordinary matroid isomorphism class.

More precisely, fix an ordinary matroid \(M\) which admits an \(n\)-cycle. The fiber over the isomorphism class of \(M\) is controlled by the \(\operatorname{Aut}(M)\)-conjugacy classes of regular cyclic subgroups \(C_n\leq\operatorname{Aut}(M)\). Thus the normalizer quotient agrees with ordinary isomorphism exactly for those matroids for which all such regular cyclic subgroups are conjugate inside \(\operatorname{Aut}(M)\).

This is not peculiar to matroids. It is the classical Cayley isomorphism problem specialized to the category of matroids. Babai’s criterion expresses the CI-property in terms of conjugacy of regular subgroups, and the modern theory of circulant objects replaces the normalizer by larger solving groups when necessary. Muzychuk and Ponomarenko prove that the isomorphism problem for arbitrary circulant relational structures can be solved in polynomial time; in particular, the multiplier group is only the whole story in special orders or special categories.

The distinction suggests three separate enumerative quantities:

\[ a_n=|X_n|, \]

\[ b_n=|X_n/N_{S_n}(C_n)|, \]

and

\[ c_n= \#\{\text{ordinary matroid isomorphism classes admitting an }n\text{-cycle}\}. \]

The code in this post computes \(a_n\) and \(b_n\). It does not claim to compute \(c_n\).

6. A transparent look at one multiplier action

For a small example, take \(n=7\). The following block prints the action of each unit in \((\mathbb Z/7\mathbb Z)^\times\) on the subset-orbit coordinates. The entries are zero-based orbit indices. This is the effective normalizer action used above.

n = 7
print(f"units modulo {n}: {units_mod_n(n)}")
for a, mapping in zip(units_mod_n(n), multiplier_maps(n)):
    print(f"a={a}: {mapping}")

units modulo 7: (1, 2, 3, 4, 5, 6)
a=1: (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
a=2: (0, 2, 4, 9, 1, 5, 6, 14, 3, 8, 10, 7, 12, 15, 11, 16, 13, 17, 18)
a=3: (0, 4, 1, 8, 2, 6, 5, 11, 9, 3, 12, 14, 10, 16, 7, 13, 15, 17, 18)
a=4: (0, 4, 1, 8, 2, 5, 6, 11, 9, 3, 10, 14, 12, 16, 7, 13, 15, 17, 18)
a=5: (0, 2, 4, 9, 1, 6, 5, 14, 3, 8, 12, 7, 10, 15, 11, 16, 13, 17, 18)
a=6: (0, 1, 2, 3, 4, 6, 5, 7, 8, 9, 12, 11, 10, 13, 14, 15, 16, 17, 18)

We can also see directly which of the fixed rank vectors are identified by the normalizer by printing only the non-singleton normalizer orbits.

n = 7
for canonical, members in normalizer_classes(n):
    if len(members) > 1:
        print(f"class of size {len(members)}")
        for member in members:
            print(f"  {member}")

class of size 2
  (1, 2, 2, 3, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3)
  (1, 2, 2, 3, 2, 3, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3)
class of size 2
  (1, 2, 2, 3, 2, 3, 3, 4, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4)
  (1, 2, 2, 3, 2, 3, 3, 4, 3, 3, 4, 4, 3, 4, 4, 4, 4, 4, 4)

7. What this calculation does and does not say

The fixed-point formulation is useful because it converts cyclic matroid enumeration into an exact finite system of bounded integral submodularity constraints. The normalizer calculation is equally exact, but it answers a more structured question than ordinary matroid isomorphism: it remembers a regular cyclic subgroup.

Neither observation is intrinsically new. The cyclic action on subsets is already central in the work of Alfarano–Khathuria–Tinani, while the normalizer-versus-isomorphism distinction belongs to the general theory of Cayley and circulant objects. What the computation provides is a compact laboratory in which these general ideas can be seen directly at the level of matroid rank functions.

From a computational point of view, the benefit is substantial. Instead of searching through arbitrary matroids, we solve the rank axioms only on cyclic subset-orbit coordinates and then divide by the effective multiplier action. For the small values considered here, the entire calculation is short enough to reproduce directly in SageMath.

A genuinely matroid-specific theoretical question begins only after this point: for which \(n\) does ordinary isomorphism of cyclic matroids already imply multiplier equivalence? Equivalently, for which cyclic groups does the CI-property hold within the category of matroids? That question is not answered by the computations above, and it is the direction in which one would have to go to obtain theory beyond the general circulant-object framework.

The Kitchen Sink and Other Oddities