I am interested in writing a program to extend the sequence Number of commutative rings with 1 containing n elements. This sequence is not as well linked-to as the other three of its type, which is perhaps why it ends at 31, rather than 63, even though it should be easier.

I hope to extend it to at least 127 and hopefully 255. The powers of two are the hardest steps along the way, particularly because of the number of isomorphism classes of rings with additive group $(\mathbb{Z}/2\mathbb{Z})^n.$ Since this group has $n$ generators, a naïve algorithm would arbitrarily determine $n(n-1)/2$ products from among $2^n$ possibilities and check for associativity (supposing we use the multiplicative identity as a generator). Since associativity comes down to $n(n-1)(n-2)/3$ equations, and each one requires $4n^2$ lookups, we're looking at $$\frac{4n^3(n-1)(n-2)}32^{(n^3-n^2)/2}$$ computations, which is already 2.3 quintillion in the case of $(\mathbb{Z}/2\mathbb{Z})^5.$

The Question

Clearly this can be improved immensely, depending on how much ring theory knowledge one wishes to give the computer. In particular, we know that there is one field, and nonlocal rings are enumerated easily from the calculations from lower powers of two, so this leaves the local case. Thus the question in full generality is

What is a computationally effective way to enumerate isomorphism classes of local commutative rings with additive group $(\mathbb{Z}/2\mathbb{Z})^n,$ given a list of all commutative rings with additive group $(\mathbb{Z}/2\mathbb{Z})^k$ for lower $k$?

In particular, would organizing the search (and sorting the generators) on the basis of the number of subrings it has of order $(\mathbb{Z}/2\mathbb{Z})^k$ for each $k$ be efficient, slow, or very difficult to program? Would the size of the maximal ideal be a better place to start? Quotients of polynomial rings by reducible/irreducible polynomials? Or something else entirely?


I'll write what I've thought of in case someone has something better.

The nontrivial part is enumerating the local rings. For a local ring $R$ with additive group $(\mathbb{Z}/2\mathbb{Z})^n,$ its maximal ideal $\mathfrak{m}$ must have precisely half the elements of the ring by zcn's answer here. And any maximal ideal is a not necessarily unital ring, so one should get the list of all non-unital commutative rings $\mathfrak{m}$ with additive group $(\mathbb{Z}/2\mathbb{Z})^{n-1}.$ Since we know $1\not\in \mathfrak{m},$ we can use 1 as the last basis element of $R,$ for which we know the whole multiplication table.

In each case, we must check that no other ideal of size $2^{n-1}$ exists in the resulting ring.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.