Skip to main content
n=8 finally finished
Source Link
Peter Taylor
  • 7.2k
  • 1
  • 21
  • 29

On my desktop machine, with the pypy3 implementation of Python, this computes up to $n=7$ inclusive in under ten seconds. It's been running for over 13 hours without finishing, and $n=8$; by extrapolation I estimate that it should be on the order of $2 \times 10^{10}$, so if the calculation time is roughly linear in the number of solutions (which I doubt) then it might take on the order ofabout 36 hours. I'll leave it running for a few days, absent accidents, but this direct enumeration technique certainly isn't going to scale beyond $n=8$.

n systems
0 1
1 1
2 2
3 5
4 19
5 137
6 3708
7 1506404
8 230328505024

On my desktop machine, with the pypy3 implementation of Python, this computes up to $n=7$ inclusive in under ten seconds. It's been running for over 13 hours without finishing $n=8$; by extrapolation I estimate that it should be on the order of $2 \times 10^{10}$, so if the calculation time is roughly linear in the number of solutions (which I doubt) then it might take on the order of 36 hours. I'll leave it running for a few days, absent accidents, but this direct enumeration technique certainly isn't going to scale beyond $n=8$.

n systems
0 1
1 1
2 2
3 5
4 19
5 137
6 3708
7 1506404

On my desktop machine, with the pypy3 implementation of Python, this computes up to $n=7$ inclusive in under ten seconds, and $n=8$ in about 36 days.

n systems
0 1
1 1
2 2
3 5
4 19
5 137
6 3708
7 1506404
8 230328505024
Source Link
Peter Taylor
  • 7.2k
  • 1
  • 21
  • 29

We can compute the number of Dynkin systems for small $n$ using an almost-brute-force method. For efficient computation we represent a set ${a_i}$ as a binary number $\sum_i 2^{a_i}$; then $\Omega = \{0, 1, 2, \ldots, n-1\}$ is represented by $2^n - 1$ and we can compute the complement with bitwise exclusive or by $2^n - 1$. This numeric representation also gives a straightforward total ordering to the subsets of $\Omega$.

The computational state consists of three sets: a subset of $\Omega$ which is included in the system; a subset which is excluded from the system; and a subset which is as yet undecided. Initially the included set is $\{ \emptyset, \Omega \}$, the excluded set is empty, and the undecided set contains the rest of the powerset of $\Omega$. At each stage we case split on the condition of the least (in the total ordering) undecided subset: either it is in the included set, in which case we apply the closure properties and verify that they don't require an excluded subset; or it isn't, in which case we add it (and its complement) to the excluded set.

I did have some ideas for approaches which should be more efficient asymptotically, but at the sizes which are practical to calculate they slow the computation down.

Python code, considerably optimised over the version I posted earlier in a comment:

def extend_closure(omega, included, extension, excluded):
    # We start with a closure which we want to extend
    closure = set(included)

    # Use a queue
    q = set([extension])
    while q:
        x = next(iter(q))
        q.remove(x)
        closure.add(x)

        # Ensure the complement closure too
        if (omega ^ x) not in closure:
            # Shortcut contradictions
            if (omega ^ x) in excluded:
                return None

            q.add(omega ^ x)

        for y in closure:
            if (x & y) == 0 and (x | y) not in closure:
                # Shortcut contradictions
                if (x | y) in excluded:
                    return None

                q.add(x | y)

    return closure


def enumerate_dynkin(n):
    omega = (1 << n) - 1

    def inner(included, lb, excluded):
        yield included

        for min in range(lb, (omega + 1) >> 1):
            if min in included or min in excluded:
                continue

            # Consider the implications of adding min
            ninc = extend_closure(omega, included, min, excluded)
            if ninc:
                for sys in inner(ninc, min + 1, set(excluded)):
                    yield sys

            # Consider systems without min
            excluded.add(min)
            excluded.add(omega ^ min)

    for sys in inner(set([0, omega]), 1, set()): yield sys


for n in range(9):
    print(n, sum(1 for _ in enumerate_dynkin(n)))

On my desktop machine, with the pypy3 implementation of Python, this computes up to $n=7$ inclusive in under ten seconds. It's been running for over 13 hours without finishing $n=8$; by extrapolation I estimate that it should be on the order of $2 \times 10^{10}$, so if the calculation time is roughly linear in the number of solutions (which I doubt) then it might take on the order of 36 hours. I'll leave it running for a few days, absent accidents, but this direct enumeration technique certainly isn't going to scale beyond $n=8$.

Results:

n systems
0 1
1 1
2 2
3 5
4 19
5 137
6 3708
7 1506404

In principle the same approach could be extended to handle relabelling: in the branch of the case split where we exclude a subset, we could also exclude all subsets which are equivalent to it under relabelling. But actually calculating that gets a bit tricky. It might actually be easier to generate, group by basic statistics like the number of subsets of each cardinality, and then test for relabelling equivalence within each group. I haven't implemented either approach.