Permutation clones that preserve relations
Tim Boykett · 2024
Read Permutation clones that preserve relations by Tim Boykett (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-06109.txt.
Introduction
Tim Boykett, writing solo in 2024, studies a kind of symmetry crowd that sits between two older fields. His crowds are sets of shuffles of a grid of points, closed under the ways shuffles stack and rename. Some such crowds are cut out by relations, plain rules about which points may stand where; those are the quarry here. Boykett maps the whole lattice of them on a finite set and sorts its shape.
On a two-point set he finds every one: thirteen in all. A side class of crowds, the borrowing-closed kind at the top rank, turns out to be cut by relations or by a cancel rule, with no third road. Whole families of older clones fold into one when read as shuffle crowds. The piece is a map first, with the roads marked for later travelers.
Catalog record
| CREATOR | Tim Boykett |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 64 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-06109
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Permutation clones that preserve relations Tim Boykett Abstract Permutation clones generalise permutation groups and clone theory. We investigate permutation clones defined by relations, or equivalently, the automorphism groups of powers of relations. We find many structural results on the lattice of all relationally defined permutation clones on a finite set. We find all relationally defined permutation clones on two element set. We show that all maximal borrow closed permutation clones are either relationally defined or cancellatively defined. Permutation clones generalise clones to permutations of A n A^{n} . Emil Jeřábek found the dual structure to be weight mappings A k → M A^{k}\rightarrow M to a commutative monoid, generalising relations. We investigate the case when the dual object is precisely a relation, equivalently, that M = 𝔹 M={\mathbb{B}} , calling these relationally defined permutation clones. We determine the number of relationally defined permutation clones on two elements (13). We note that many infinite classes of clones collapse when looked at as permutation clones. 1 Introduction Given a finite set of logic signals, the reversible gates for these signals are the basis upon which a reversible computer can be designed and built. The number of logic signals, whether binary logic, ternary logic or some higher arity logic, will affect which gates are possible. In this paper we deepen our understanding of these gates and the ways that they can be combined to engineer reversible computer systems. In particular we will borrow strongly from clone theory, itself developed as an abstract theory of circuits. For a given finite set of logic signals A , a k -ary gate is a bijection from A^{k} to itself, that is, a permutation of A^{k} . Thus we investigate collections of permutations of A^{k} for all k , closed under natural operations of parallel and serial composition. Taking the lead from [ 11 ] we call closed systems of bijections permutation clones . We consider ancilla and borrow closure, where an extra input and output is allowed; an ancilla logic state is provided and returned in a particular state, whereas a borrowed logic state is provided and returned in an arbitrary state. In previous papers, Aaronson, Grier and Schaeffer [ 1 ] have determined all ancilla closed gates on a set of order 2, and the author, together with Kari and Salo, has investigated generating sets and other topics [ 2 , 4 ] . More related work is outlined in the next section. In this paper, we examine permutation clones that are naturally related to clones. We consider permutation clones that are defined by their components maps as clones. Clones are defined by the relations that they respect using a Galois connection. Through these results, we gain some insight into the general structure of reversible gate systems. We start Section 2 by introducing the background properties of permutation clones and the duality results from Jeřábek. We then investigate the properties of relationally defined permutation clones and investigate the various maximal classes. We conclude with some open questions and ideas for further work. 2 Background We start by introducing some clone theory and permutation group theory. In particular we are interested in co-clones or relational clones as well as automorphism groups of relations. We will then bring these together as permutation clones, and introduce weight preservation as the appropriate dual structure. Let A be a finite set. Define {\cal O}_{A}^{n} to be the set of all n -ary mappings f:A^{n}\rightarrow A . Let {\cal O}(A)=\{f:A^{n}\rightarrow A\mid n\in\mathbb{N}\}=\cup_{n}{\cal O}_{A}^{n} be the collections of multivariate mappings of A to itself. Such mappings can be transformed by 1. permuting variables: if f:A^{n}\rightarrow A and \sigma\in S_{n} is a permutation, define g:A^{n}\rightarrow A by g(x_{1},\dots,x_{n})=f(x_{\sigma^{-1}(1)},\dots,x_{\sigma^{-1}(n)}) . 2. identifying variables: if f:A^{n}\rightarrow A and n>1 , define g:A^{n-1}\rightarrow A by g(x_{1},\dots,x_{n-1})=f(x_{1},\dots,x_{n-1},x_{n-1}) . 3. composition of functions: if f:A^{n}\rightarrow A and g:A^{m}\rightarrow A , define h:A^{m+n-1}\rightarrow A by h(x_{1},\dots,x_{m+n-1})=f(g(x_{1},\dots,x_{n}),x_{n+1},\dots,x_{n+m-1}) . 4. inserting dummy variables: if f:A^{n}\rightarrow A , define g:A^{n+1}\rightarrow A by g(x_{1},\dots,x_{n+1})=f(x_{1},\dots,x_{n}) . The projection mapping \pi_{i}^{n}:A^{n}\rightarrow A is defined by \pi_{i}^{n}(x_{1},\dots,x_{n})=x_{i} . A collection of mappings C\subseteq{\cal O}(A) is called a clone if it contains all projections and is closed under the transformation operations above. A set that is closed under the operations but does not include the projections is called an iterative algebra . Let R\subseteq A^{k} be a k -ary relation on A . Let f:A^{n}\rightarrow A be a n -ary map on A . We can extend f to act on A^{k} componentwise, so f:(A^{k})^{n}\rightarrow A^{k} in a natural fashion. If f maps R to itself, then we say that f respects the relation R , written f\triangleright R . We call this a polymorphism of R . This gives rise to a Galois connection between maps and relations on A , a duality. Definition 1 ( [ 15 , Section 2.4] ) A relational clone is a collection of relations closed under the following operations: 1. permutation of entries 2. projection; ignoring one entry 3. cartesian products 4. intersection 5. includes the equality relation \{(a,a,b)\mid a,b\in A\} Lemma 1 Let C be a clone. Then there exists a relational clone {\cal R} such that for all f\in{\cal O}(A) , f\in C iff f\triangleright R for all R\in{\cal R} . The collection of maps that respect a relation R is written \operatorname{Pol}(R) , the polymorphisms of R . All clones are of the form \bigcap_{i}\operatorname{Pol}(R_{i}) for some (possibly infinite) set of relations R_{i} . We call relations the dual structure of clones. Clone theory has been well developed for several decades, see e.g. [ 13 , 15 ] for an overview. One of the classical results in clone theory is the determination of the maximal clones. Theorem 2.1 (Rosenberg) Let A be a finite set. Then the maximal subclones of {\mathcal{O}}(A) are one of the following. 1. monotone mappings, that is respecting a bounded partial order on A 2. respecting a graph of prime length loops 3. respecting a nontrivial equivalence relation 4. affine mappings for a prime p : that is, respecting the relation \{(a,b,c,d)\mid a+b=c+d\} where (A,+) is an elementary abelian group 5. respecting a central relation 6. respecting a h-generated relation Let A be a finite set. We will assume a basic understanding of permutation group theory, but clarify some terminology here, for details see e.g. [ 8 ] . Sym(A)=S_{A} is the set of permutations or bijections of A . If A=\{1,\dots,n\} we will often write S_{n} . We write permutations in cycle notation and act from the right, so we write the action of a permutation g\in G\leq Sym(A) on an element a\in A as a^{g} . Given a set A and a K -ary relation R\subseteq A^{k} , the collection \operatorname{Aut}(R)\leq S_{A} of automorphisms of that relation R is a group. For example the relation defining the edges of a square on A=\{1,2,3,4\} with R=\{(1,2),(2,3),(3,4),(4,1),(2,1),(3,2),(4,3),(1,4)\}\subseteq A^{2} (1) has \operatorname{Aut}(R) the dihedral group with 8 elements. We can speak of (A,R) as a relational structure in the same way that an operation f:A^{n}\rightarrow A gives (A,f) an algebraic structure. Let G be a group of permutations of a set A . Let n\in\mathbb{N} . The wreath product GwrS_{n} is a group of