Reversible Computation as Clone Theory

For the past few months I have had the pleasure of working closely with my colleague Erhard Aichinger on a project that  he has been keeping in a lower drawer for some time. I am not sure if he planned it that way, but the project was right up my alley.

The core of the project was to take the ideas developed by Tom Toffoli in a very old paper (that I cannot point to online, it seems not to exist. Even the link from wikipedia is dead!) about reversible computation and see how we could formalise this algebraically. Switching theory and boolean algebra have been formalised in may ways, one of the most important being clone theory. Erhard was wondering whether we might find a way to do something similar with Toffoli’s work. This required a few strange starting points; luckily I seem to have the right combination of strangenesses in my head.

Reversible computation is something that I have been aware of for a long time, ever since Günter Pilz asked me whether changing a semigroup into a group (and thus a seminearring into a seminearfield) made any sense when modelling certain types of computation. It turns out that reversible computation is not only possible but actually useful, for instance as all quantum processes are reversible until the last point of measurement, so quantum computation requires the understanding of reversible computation.

The other area is clone theory, a special area of universal algebra, which is a special area of abstract algebra, which is a special area of algebra, which is a special area of pure mathematics. It also happens to be Erhard’s main area of work and he has published a few quite important papers over the years, often with our mutual colleague Peter Mayr. So that was great, having a clone theorist on hand and some experience with reversible computation, perhaps something could emerge. Clone Theory  could be summarised as  generalising Emil Post’s work from  1941 about all arbitrary arity mappings of the set {0,1} to itself.

It turns out that Toffoli’s work has been fundamental in a bunch of related areas, so much so that the “controlled-controlled-not” gate that he introduced in 1979 is now known as the Toffoli gate. There is a quantum version as well. As we dived into this project, we became aware that a group at MIT around Scott Aaronson, had been looking into the same area, but decided that generalising Post’s work was going to be too hard. So Scott, along with Daniel Grier and Luke Schaeffer, did a version of his original work and found some very interesting results on the structure of possible closed collections of reversible maps on {0,1}.

We did not try to extend this work, rather to look at the general situation in more detail. Perhaps we can find ways to avoid the huge amount of work they did (66 pages!) as we look at reversible mappings on higher order sets. Perhaps we can find a way to use Emil Jeřábek’s insights to make the analysis easier. We wanted to build a basis for a theory of reversible clones, or closed systems of mappings is we wanted to look at arbitrary mappings from A^m to A^n for A some finite set.

It turned out that looking at higher order base sets was the trick. On the arXiv the paper can be dived into, or one could wait for the proper publication. There are three interesting new results. One is that we can write the “wiring” of reversible gates as an algebra with a finite number of finitary operations. Which means that the lattice of subalgebras (i.e. closed systems of mappings by generation) is algebraic and thus well structured. Later in the paper we look at other forms of closure , for instance related to results about “ancilla” bits, and show that there are four distinct and relevant forms of closure, related to Toffolis notions of realisation(the three others correspond to temporary storage, strong temporary storage and general realisation). Because the generation closure is the most general closure, giving the smallest closed set, the lattices of closed sets of reversible mappings might also be algebraic lattices, which would be good. Aaronson’s work uses one of these (ancilla bits, or realisation with temporary storage). We were able to generalise Toffoli’s result about nongeneration from order 2 to arbitrary even ordered sets. But more importantly, we were able to show that for odd order sets, his result does not generalise. Four small Toffoli gates are enough to generate all reversible mappings. This is a pleasant surprise, as it indicates that odd order state sets might give us more power in creating reversible circuits.

So this work has found some surprising things and given us some results. But it also throws up a whole spectrum of other questions, which might be good to look at.

  • What are the appropriate generalisations of relations as used in the clone theory Pol-Inv results? Will Lehtonen’s clusters be useful?
  • Are the commutative monoid weight function introduced by Emil Jeřábek the best tool for the Pol-Inv description? These do not work outside the realm of reversible computation, but that might be fine. They are also very tempting from the “Physics of Computation” point of view – the sums of weights are a conserved quantity.
  • What are the linear reversible clones? Can these be easily described, better than just including the permutation matrices? We know from clone theory that linearity can be described as the preservation of a 4-ary relation, is there something similar to be used here?
  • Can we prove Aaronson et al’s observation that if a reversible clone closed under temporary storage is finitely generated, then it is generated by a single function?
  • Under the operation of full composition, a reversible clone forms an inverse semigroup that is a semilattice (actually a chain isomorphic to the natural numbers) of groups. Can this observation be made use of?
  • Are the lattices of closed reversible clones under the other closures also algebraic?
  • Can we find a smaller generating set as hoped for in Yang, Song, Perkowski and Wu’s paper?

I feel quite happy about this project and its results. Erhard asked me to look properly at some things that had been tickling me for a while and gave some excellent comments as I wandered down that path. One can only hope that other people find it interesting as well.


1 Comment

Filed under Uncategorized

Talking in Manipal

The 24th International Conference on Nearrings, Nearfields and Related Structures reached its penultimate day on Friday, after 5 days of talks, presentations, discussions, an excursion and much eating. My talk was the last plenary talk on Friday, so understandably we were all feeling a bit tired. So I tried hard to keep us on our toes.

The talk fell into four parts. Firstly I presented Gerhard Wendt’s work on 1- and 2-primitivity, recently published in Mathematica Pannonica and the Taiwanese Journal of Mathematics. I am sure I did not do it justice, but I tried to cover the essential results and point at what we hope to be attacking soon for the 0-primitive case. Then I presented our collaborative work on the 2-radical for state automata, then some results for cellular automata, which are yet to be published. Finally I presented our collaborative work on units in nearrings, looking at the nearrings in which units do one of two interesting things: act fixed point freely on the additive group of the nearring, or define a subnearfield when augmented with zero.

The talk seemed to go well, with several students finding some questions to look at afterwards. I hope to be hearing about some publications emerging from their work! One student already seems to have a new example of the class of groups used in the J_2 radical in state automata paper. Great work!

The talk is downloadable as a PDF, in case anyone cares.

(PDF will be added later, WordPress is not accepting uploads right now)

Articles referenced:

G. Wendt,  1-primitive near-rings, Mathematica Pannonica, link

G. Wendt,  0-Primitive near-rings, minimal ideals and simple near-rings, Taiwanese Journal of Mathematics, vol 19, nr 3, pp. 875-905, link.

T. Boykett and G. Wendt, Units in Nearrings, accepted to Comm. Alg, link.

T. Boykett and G. Wendt, J2 Radical in Automata Nearrings, International Journal of Foundations of Computer Science Vol. 25, No. 05, pp. 585-595 (2014), DOI: 10.1142/S0129054114500233, download linkarxiv link.

Leave a comment

Filed under conference

Some Things at the Nearring Conference in Manipal

I have had 4 days of interesting talks, strange talks, wonderful experiences and communication, sweat, rain and food in Manipal. Tomorrow I will give a talk, but I will post that after it has been presented.

It is often said that India is different. I always thought that that was sort of wrong and sort of obvious, but it is probably neither. This has been a fantastic eye opener for me and, I am sure, all of us who are visiting for this conference. I have been baffled, overwhelmed, excited and intrigued. Both inside and outside the lecture halls. Wonderful!


Lighting the lamp at the inauguration celebration.

So what has excited me? Mark Farag and Kent Neuerburg talked in their two talks about some ideas around the center of a nearring, i.e. the set {n in N | nm=mn for all m in N}. It turns out that this is only occasionally even a subnearring, even if it is additively closed (Pilz, Heatherly and Birkenmeier 1997). Farag and Aichinger have published a paper in 2004 on the question for nearrings of order p^2, determining the classes of nearrings where the center is a subnearring. Neuerburg also talked about the case for matrix nearrings and von Neumann regular nearrings. Farag followed this up with examples to explore all the possible cases of what can happen, often using so-called Malon trivial nearrings. He was concentrating upon a slightly larger class of generalised centers, defined as  GC(N) = {n in N | nm=mn for all m in N_d} where N_d is the set of distributive elements. This is always a subnearring, and matches the classical center in the case of rings.

Some good questions came out of these talks, which I enjoyed.

  • What is the center and generalised center of a planar nearring? This should be “easily” computable with our extensive knowledge of planar nearrings. These also generalise Malone trivial nearrings.
  • What other forms of generalised center exist? Are some more useful?
  • Is there something like a maximal ideal that intersects trivially with these centers? Are these centers somehow essential? Is there a form of commutator that would generate this ideal, so that N / [N,N] is isomorphic to the (generalised) center or some other maximally commutative subnearring? Does a series then emerge, a lower central series, derived series or something else?

I think we will probably spend a while thinking about these problems, I hope that there will be  some news at a later nearring meeting.

Seeing as the generalised center is a subnearring but not an ideal (it contains the identity, so it cannot be) it might be useful to look at the hypernearring ideas of Davvaz from Tehran. Hypergroups are the structure one gets when one works with cosets of subgroups instead of normal subgroups. This generalisation also works for semigroups, groupoids and other structures. So Hypernearrings might be precisely the tool needed to look at nearrings modulo generalised centers. There are some other clear questions that arose from Davvaz’ talk: are all hypernearrings embeddable in a transformation hypernearring, i.e. M_0(G) modulo some subnearring?

Stefan Veldsman’s talk was also interesting, looking at ways, as I see it, of finding out out what sort of basis can be used to define a composition ring as a concrete mapping composition ring. Gary Birkenmeier was looking at another pair of internal-external ways of looking at a class of rings, which felt the same and dealt with questions of essentiality. Stuart Scott is summarising his huge result on the n-gen problem. We can use his work to solve the question when M_0(G), G finite is generated by its units: always, up to Z_2 x Z_2, which we need to calculate. The rest we get from his work. It appears that Alan Oswald looked at the question as to when M_0(V) is additively generated by its units. Unlike in the ring case, these two properties differ.

Satyanarayana gave us an overview of some interesting work where he was using techniques from Goldie, so-called Goldie dimension and related ideas such as spanning dimension, to find useful ideas similar to the rank nullity theorems in N-groups. This affinity for ideas from high school algebra was underlined by Ambedkar, who talked about breaking Groebner Basis work and Buchberger’s algorithm down to something that can be understood by high school mathematics students playing with polynomials. He recommended Abhyankar’s “Historical Ramblings” as a suitable way to think about mathematics and the KISS principle. Simple enough, but not too simple.

Juglal and Groenewald, as well as Booth and Ayman Badawi, have given us multiple examples of primeness and generalisations thereof and exhibited their differences and implications. All these generalisations of ring concepts have left my mind in a blur, but I am sure that, given some time to look at what these mean in some particular cases, there is some good, solid theory and applicability in there.

Almost all the talks have given me something to think about, whether it is Srinivas’ Gamma-near algebras and their possible connections to hyperidentities (which I always thought were frivolous “abstract nonsense” until now) , Das’ work with some special counter example structures and Pushpalatha’s work on special boolean nearrings with their use of a commutator type identity.

Tonight there was a cultural program with a yoga demonstration. That was painful looking! There was also some singing, especially a piece sung over a Tambura, which particularly appealed to my appreciation of drones. And last but not least, a dance performance, telling the stories of local princesses, wise old women and princes, all with fantastically over articulated eyes and hands. Wonderful!

Some maths grad students exploring symmetry and storytelling.

Some maths grad students exploring symmetry and storytelling.

Leave a comment

Filed under conference

Manipal nearring conference – the Newsletter

I am in Manipal, India, for the 2015 Nearring conference. It is very interesting, hot, spicy and keeping my mind full.

Tomorrow is the “Business Meeting” where I will remind everyone who is interested to become part of the nearring mailing list. It is available here:

The mailing list is intended for all those who are interested in keeping up with current developments in nearring and related fields. Feel free to join.

Below is a picture from our excursion today. Perhaps I will post some news tomorrow!


Leave a comment

Filed under Uncategorized

Getting back to Basics

I left this blog alone almost 2 years ago as I finished my “residency” at the algebra department. I was too busy with other things to even round out what I was doing then. In case you care, a paper came out about the rectangularity property.

But I have recently (end of 2012) started visiting the department regularly and have started work with Gerhard Wendt on some aspects of straucture theory in nearrings of automata. State Automata and Cellular Automata. While I would like to summarise it all for you now, I cannot and it is proving to be less difficult than I thought but more difficult than I hoped. Which is good I suppose.

But for a quick summary:

  1. Cellular or Tesselation automata over state groups with torsion free space groups are 2-primitive as nearrings.
  2. Over torsion space groups we get “really large” Jacobson radicals
  3. The Jacobson 2-radical of a state automata nearring lies within the set of “contraction” automata, i.e. those that never respond immediately to changes. We conjecture that it is precisely this and perhaps an old paper about topological nearrings from 1967 will help us work it out.

But I hope to post once a week (only one day of algebra per week, so perhaps it is still a theorem a day?) as I go on in order to try and summaruise what is going on. No pictures this week….

Leave a comment

Filed under conjecture

Cutting down Automata

Aftre beating my head against rectangularity and the wonders of writing things up for a few days, I decided I needed to try out something new. So I took out some blank paper and decided to look at cut down automata. By this I mean automata where we only care about their effect on small sequences. This means we look at mappings from G^n to G^n that respect prefixes.
Keeping it simple I decided to look at automata on Z_2, for two time steps. Requiring 0-symmetry (as long as an initial sequence is 0, the output will be zero) meant there are 16 possibilities, of which 4 are linear (zero, identity, delay and delay+identity). I still did not want to calculate a 16 by 16 multiplication table, so I dug into Sonata, the nearring calculation package for GAP.
How do define the automata? Well, we know that they can be written as follows:

00  00
01  0a
10  bc
11  bd

where the repeated b corresponds to the prefix 1. Each of a,b,c,d can be 0 or 1. The automaton is linear when a=b and d=c+a. Our automata are sums of the 4 automata defined by having precisely one of the parameters nonzero. Then to encode them we work out what the mapping on Z_2 ^2 is. As follows:

abcd  00 01 10 11  1234
1000  00 01 00 00  1211
0100  00 00 10 10  1133
0010  00 00 01 00  1121
0001  00 00 00 01  1112

where 1234 are the indexes of the elements 00,01,10,11. So we can use the Sonata functions to define these mappings:

Z22 := GTW4_2; 
f1 := EndoMappingByPositionList(Z22,[1,2,1,1]); 
f2 := EndoMappingByPositionList(Z22,[1,1,3,3]);
f3 := EndoMappingByPositionList(Z22,[1,1,2,1]);
f4 := EndoMappingByPositionList(Z22,[1,1,1,2]);

Then we create the nearring and look at its lattice of left, right and two sided ideals:

N1 := TransformationNearRingByGenerators(Z22,[f1,f2,f3,f4]);

The lattice of left (diamonds), right (squares) and two sided (circular) ideals of the nearring of cut automata of length two on the two element group.

It seems that Sonata has a problem in calculating the radicals here; maybe it can only calculate them for the library nearrings or other special cases. I have still not really gotten my head around the ideas of nearring radicals. Too late perhaps. I have been trying to for a long time now…..
We find 4 two sided ideals here, two of order 8, one intersection of order 4 and a last one of order 2 containing the delay automaton.
Modulo the order 2 ideal we get a nearring of order 8 with all radicals equal and of order 2. If I remember my nearring theory right, we have J(N/X) = J(N)/X when X in J(N). So with any luck we can say that the Jacobson radicals of the generated nearring are all equal and of order 4, and modulo this we get a ring. This ring is a 2×2 matrix ring over Z_2 with generators the two matrices with just one nonzero entry on the diagonal. These are idempotent with sum the identity, just as we like…
Now I will have to dig into some theory and see what I can find. Maybe there is a general form for these nearrings, at least for prime groups.


Filed under conjecture, construction

A Diagram of classes

A friend and colleague, Jonathan Farley, once commented that one of the reasons he liked lattice theory so much (and he does like lattice theory so much that it is his email address) is that it is possible to prove something by drawing a diagram. This goes against what we all learnt in high school, that just because the geometry seems to match up in our picture, does not mean that it always will. Quite likely we have drawn the diagram in a certain way where everything falls into place, but when we draw a special version (one angle over 90 degrees) then our visual proof falls over. Somewhat like the way a colleague likes to harass computer science (students) logic – if they cannot imagine why it could be wrong, then it must be right.
But lattice theory has enough abstraction that sometimes you can prove something by inspection. This is nice. Category theorists like to “chase the arrows” as a proof technique as well, getting lost in their diagrams.
I like a solid algebraic proof personally, but I am a great fan of diagrams to help make sense of things. I have the priveledge of an amazing collection of diagrammatic knowledge in the head and library of Gerhard Dirmoser, things like this and this, and these diagrams help convey information but also the sense of the overwhelming amount of information that is out there.
In the RG research project this summer, I have been making scratchy diagrams in order to order my thoughts. Over and again I have realised that some part of the diagram needed to be fleshed out, only later to prove that it all collapses. Today I finally anticipated that my sketches were nearing some sense of completeness, so I decided to make a Graphviz diagram that summarised the information in the latest draft of the paper. This is what I got:

The diagram of inclusions of RG classes.

PDF version
The diagram has three types of shapes. Ovals are varieties, rectangles are quasivarieties. Actually, there are some that are rectangles but might actually be varieties. Three three classes with no borders are not necessarily anything; we know that the full RGs are not closed under taking subalgebras, so they are not even a quasivariety. They do seem to be closed under homomorphic images and products, so perhaps there is something special to be said about them.
We also see that the diagram as it stands is not a lattice: the join of the partitioned and the idempotent undirected classes is not uniquely defined.
So we have an indication that some extra class of RGs should be defined, in a natural way, to make this a sublattice of the lattice of quasivarieties of groupoids.
Similarly I added the quasivariety of square injective RGs, where we require a*a=b*b \Rightarrow a=b to hold. These form a natural generalisation of idempotent (where the square map is the identity) and matrix symmetric (where the square map is a permutation) RGs. This is a quasivariety because it is defined by two implications.
There are two arrows in the diagram; these show that the two quasivarieties generate the two indicated varieties. It would be interesting to know what other varieties are closures of the given quasivarieties.
So this diagram has helped to summarise information, has led to the creation of some more concepts and results, and aided in formulationg some questions.
Well worth it!

Leave a comment

Filed under construction, Question