Search

We prove that the power word problem for certain metabelian subgroups of G L (2 , ℂ) (including the solvable Baumslag–Solitar groups BS (1 , q) = 〈 a , t | t a t − 1 = a q 〉) belongs to the circuit complexity class T C 0 . In the power word problem, the input consists of group elements g 1 , ... , g d and binary encoded integers n 1 , ... , n d and it is asked whether g 1 n 1 ⋯ g d n d = 1 holds. Moreover, we prove that the knapsack problem for BS (1 , q) is N P -complete. In the knapsack problem, the input consists of group elements g 1 , ... , g d , h and it is asked whether the equation g 1 x 1 ⋯ g d x d = h has a solution in ℕ d . For the more general case of a system of so-called exponent equations, where the exponent variables x i can occur multiple times, we show that solvability is undecidable for BS (1 , q). [ABSTRACT FROM AUTHOR]

The normaliser problem takes as input subgroups G and H of the symmetric group S n , and asks one to compute N G (H). The fastest known algorithm for this problem is simply exponential, whilst more efficient algorithms are known for restricted classes of groups. In this paper, we will focus on groups with many orbits. We give a new algorithm for the normaliser problem for these groups that performs many orders of magnitude faster than previous implementations in GAP. We also prove that the normaliser problem for the special case G = S n is at least as hard as computing the group of monomial automorphisms of a linear code over any field of fixed prime order. [ABSTRACT FROM AUTHOR]

Let G be a finite solvable group, given through a refined consistent polycyclic presentation, and α an automorphism of G , given through its images of the generators of G. In this paper, we discuss algorithms for computing the order of α as well as the cycle length of a given element of G under α. We give correctness proofs and discuss the theoretical complexity of these algorithms. Along the way, we carry out detailed complexity analyses of several classical algorithms on finite polycyclic groups. [ABSTRACT FROM AUTHOR]

We introduce a new framework for solving an important class of computational problems involving finite permutation groups, which includes calculating set stabilisers, intersections of subgroups, and isomorphisms of combinatorial structures. Our techniques are inspired by and generalise 'partition backtrack', which is the current state-of-the-art algorithm introduced by Jeffrey Leon in 1991. But, instead of ordered partitions, we use labelled directed graphs to organise our backtrack search algorithms, which allows for a richer representation of many problems while often resulting in smaller search spaces. In this article we present the theory underpinning our framework, we describe our algorithms, and we show the results of some experiments. An implementation of our algorithms is available as free software in the GraphBacktracking package for GAP. [ABSTRACT FROM AUTHOR]

The error threshold of a one-parameter family of quantum channels is defined as the largest noise level such that the quantum capacity of the channel remains positive. This in turn guarantees the existence of a quantum error correction code for noise modeled by that channel. Discretizing the single-qubit errors leads to the important family of Pauli quantum channels; curiously, multipartite entangled states can increase the threshold of these channels beyond the so-called hashing bound, an effect termed superadditivity of coherent information. In this work, we divide the simplex of Pauli channels into one-parameter families and compute numerical lower bounds on their error thresholds. We find substantial increases of error thresholds relative to the hashing bound for large regions in the Pauli simplex corresponding to biased noise, which is a realistic noise model in promising quantum computing architectures. The error thresholds are computed on the family of graph states, a special type of stabilizer state. In order to determine the coherent information of a graph state, we devise an algorithm that exploits the symmetries of the underlying graph, resulting in a substantial computational speed-up. This algorithm uses tools from computational group theory and allows us to consider symmetric graph states on a large number of vertices. Our algorithm works particularly well for repetition codes and concatenated repetition codes (or cat codes), for which our results provide the first comprehensive study of superadditivity for arbitrary Pauli channels. In addition, we identify a novel family of quantum codes based on tree graphs. The error thresholds of these tree graph states outperform repetition and cat codes in large regions of the Pauli simplex, and hence form a new code family with desirable error correction properties. [ABSTRACT FROM AUTHOR]

Motivated by the success of quotient algorithms, such as the well-known p -quotient or solvable quotient algorithms, in computing information about finite groups, we describe how to compute finite extensions H ˜ of a finite group H by a direct sum of isomorphic simple Z p H -modules such that H and H ˜ have the same number of generators. Similar to other quotient algorithms, our description will be via a suitable covering group of H. Defining this covering group requires a study of the representation module, as introduced by Gaschütz in 1954. Our investigation involves so-called Fox derivatives (coming from free differential calculus) and, as a by-product, we prove that these can be naturally described via a wreath product construction. An important application of our results is that they can be used to compute, for a given epimorphism G → H and simple Z p H -module V , the largest quotient of G that maps onto H with kernel isomorphic to a direct sum of copies of V. For this we also provide a description of how to compute second cohomology groups for the (not necessarily solvable) group H , assuming a confluent rewriting system for H. To represent the corresponding group extensions on a computer, we introduce a new hybrid format that combines this rewriting system with the polycyclic presentation of the module. [ABSTRACT FROM AUTHOR]

The generating sets of have been enumerated which consist of integral four‐dimensional vectors with components −1, 0, 1 and allow Cayley graphs without edge intersections in a straight‐edge embedding in a four‐dimensional Euclidean space. Owing to computational restrictions the valency of enumerated graphs has been fixed to 10. Up to isomorphism 58 graphs have been found and characterized by coordination sequences, shortest cycles and automorphism groups. To compute automorphism groups, a novel strategy is introduced that is based on determining vertex stabilizers from the automorphism group of a sufficiently large finite ball cut out from an infinite graph. Six exceptional, rather 'dense' graphs have been identified which are locally isomorphic to a five‐dimensional cubic lattice within a ball of radius 10. They could be built by either interconnecting interpenetrated three‐ or four‐dimensional cubic lattices and therefore necessarily contain Hopf links between quadrangular cycles. As a consequence, a local combinatorial isomorphism does not extend to a local isotopy. [ABSTRACT FROM AUTHOR]

For each family of finite classical groups, and their associated simple quotients, we provide an explicit presentation on a specific generating set of size at most 8. Since there exist efficient algorithms to construct this generating set in any copy of the group, our presentations can be used to verify claimed isomorphisms between representations of the classical group. The presentations are available in Magma. [ABSTRACT FROM AUTHOR]

An algorithm for the computation of the complete set of primitive orthogonal idempotents of the centralizer ring of the permutation representation of the wreath product of finite groups is described. This set determines the decomposition of the representation into irreducible components. In the quantum mechanics formalism, the primitive idempotents are projection operators onto irreducible invariant subspaces of the Hilbert space describing the states of many-particle quantum systems. The proposed algorithm uses methods of computer algebra and computational group theory. The C implementation of this algorithm is able to construct decompositions of representations of high dimensions and ranks into irreducible components. [ABSTRACT FROM AUTHOR]

We show that the problem of determining if the identity matrix belongs to a finitely generated semigroup of 2 × 2 matrices from the General Linear Group GL 2 (Z) is solvable in NP. We extend this to prove that the membership problem is decidable in NP for GL 2 (Z) and for any arbitrary regular expression over matrices from the Special Linear group SL 2 (Z). We show that determining if a given finite set of matrices from SL 2 (Z) or the modular group PSL 2 (Z) generates a group or a free semigroup are decidable in NP. Previous algorithms, shown in 2005 by Choffrut and Karhumäki, were in EXPSPACE. Our algorithm is based on new techniques allowing us to operate on compressed word representations of matrices without explicit expansions. When combined with known NP -hard lower bounds, this proves that the membership problem over GL 2 (Z) is NP -complete, and the group problem and the non-freeness problem in SL 2 (Z) are NP -complete. 1 [ABSTRACT FROM AUTHOR]

Abstract We describe an algorithm for computing Schur indices of irreducible characters of a finite group G , based on computations within G and its subgroups and with their character tables. The algorithm has been implemented within Magma and examples of its use are given. We also compare the output of the algorithm on groups associated with sporadic simple groups with the results of W. Feit. The differences are considered. [ABSTRACT FROM AUTHOR]

Conformers of trans-[MX2(AB)4], cis-[MX2(AB)4], trans-[MX2(ABC)4], and cis-[MX2(ABC)4] complexes have been enumerated on the basis of computational group theory, where M is the central metal ion, while X, AB, and ABC are the monoatomic, diatomic, and bent triatomic ligands, respectively, bound to M through X or A. For the trans-[MX2(AB)4] complex, 11 bisected diastereomers have been found as 1 S4, 1 C2h, 2 C2, 1 Ci and 6 C1. Based on the 11 diastereomers of the trans-MX2(AB)4 core unit, 673 diastereomers have been found for the trans-[MX2(ABC)4] complex, which are assigned to six point groups, 3 S4, 3 C2h, 24 C2, 3 Cs, 12 Ci, 628 C1. On the other hand, for the cis-[MX2(AB)4] complex, 35 bisected diastereomers have been found as 6 C2, 4 Cs and 25 C1. Based on the 35 diastereomers of the cis-MX2(AB)4 core unit, 2511 diastereomers have been found for the cis-[MX2(ABC)4] complex, which are assigned to three point groups, 54 C2, 108 Cs, and 2349 C1. [ABSTRACT FROM AUTHOR]

A proper subsemigroup of a semigroup is maximal if it is not contained in any other proper subsemigroup. A maximal subsemigroup of a finite semigroup has one of a small number of forms, as described in a paper of Graham, Graham, and Rhodes. Determining which of these forms arise in a given finite semigroup is difficult, and no practical mechanism for doing so appears in the literature. We present an algorithm for computing the maximal subsemigroups of a finite semigroup S given knowledge of the Green's structure of S , and the ability to determine maximal subgroups of certain subgroups of S , namely its group H -classes. In the case of a finite semigroup S represented by a generating set X , in many examples, if it is practical to compute the Green's structure of S from X , then it is also practical to find the maximal subsemigroups of S using the algorithm we present. In such examples, the time taken to determine the Green's structure of S is comparable to that taken to find the maximal subsemigroups. The generating set X for S may consist, for example, of transformations, or partial permutations, of a finite set, or of matrices over a semiring. Algorithms for computing the Green's structure of S from X include the Froidure–Pin Algorithm, and an algorithm of the second author based on the Schreier–Sims algorithm for permutation groups. The worst case complexity of these algorithms is polynomial in | S | , which for, say, transformation semigroups is exponential in the number of points on which they act. Certain aspects of the problem of finding maximal subsemigroups reduce to other well-known computational problems, such as finding all maximal cliques in a graph and computing the maximal subgroups in a group. The algorithm presented comprises two parts. One part relates to computing the maximal subsemigroups of a special class of semigroups, known as Rees 0-matrix semigroups. The other part involves a careful analysis of certain graphs associated to the semigroup S , which, roughly speaking, capture the essential information about the action of S on its J -classes. [ABSTRACT FROM AUTHOR]

We study discrete logarithms in the setting of group actions. Suppose that G is a group that acts on a set S . When r , s ∈ S , a solution g ∈ G to r g = s can be thought of as a kind of logarithm. In this paper, we study the case where G = S n and develop analogs to Shanks' baby-step / giant-step procedure for ordinary discrete logarithms. Specifically, we compute two sets A , B ⊆ S n such that every permutation of S n can be written as a product ab of elements a ∈ A and b ∈ B . Our deterministic procedure is optimal up to constant factors, in the sense that A and B can be computed in optimal asymptotic complexity, and | A | and | B | are a small constant from n ! in size. We also analyze randomized “collision” algorithms for the same problem. [ABSTRACT FROM AUTHOR]

Conformers of [ $$\hbox {MX(AB)}_{5}$$ ] and [ $$\hbox {MX(ABC)}_{5}$$ ] complexes have been enumerated on the basis of computational group theory, where M is the central metal, X is the monoatomic ligand, and AB and ABC are the diatomic and bent triatomic ligands, respectively, which bound to M through A. For the [ $$\hbox {MX(AB)}_{5}$$ ] complex, 35 bisected diastereomers have been found as 2 $$C_{s}$$ , and 33 $$C_{1}$$ . Based on the 35 diastereomers of the $$\hbox {MX(AB)}_{6}$$ core unit, 8271 conformers have been found for the [ $$\hbox {MX(ABC)}_{5}$$ ] complex, which are assigned to two point groups, 18 $$C_{s}$$ , and 8253 $$C_{1}$$ . [ABSTRACT FROM AUTHOR]

The architecture of infinite structures with non-crystallographic symmetries can be modelled via aperiodic tilings, but a systematic construction method for finite structures with non-crystallographic symmetry at different radial levels is still lacking. This paper presents a group theoretical method for the construction of finite nested point sets with non-crystallographic symmetry. Akin to the construction of quasicrystals, a non-crystallographic group G is embedded into the point group of a higher-dimensional lattice and the chains of all G-containing subgroups are constructed. The orbits of lattice points under such subgroups are determined, and it is shown that their projection into a lower-dimensional G-invariant subspace consists of nested point sets with G-symmetry at each radial level. The number of different radial levels is bounded by the index of G in the subgroup of . In the case of icosahedral symmetry, all subgroup chains are determined explicitly and it is illustrated that these point sets in projection provide blueprints that approximate the organization of simple viral capsids, encoding information on the structural organization of capsid proteins and the genomic material collectively, based on two case studies. Contrary to the affine extensions previously introduced, these orbits endow virus architecture with an underlying finite group structure, which lends itself better to the modelling of dynamic properties than its infinite-dimensional counterpart. [ABSTRACT FROM AUTHOR]

A deterministic polynomial-time algorithm constructs an isomorphism between PGL ( 2 , 2 e ) and a black box group to which it is isomorphic. [ABSTRACT FROM AUTHOR]

Let G be a finite simple group of Lie type in characteristic 2, and t ∈ G an involution. We provide a lower bound for the proportion of elements g ∈ G such that t t g has odd order. This has applications to the theory of recognition algorithms for such groups. [ABSTRACT FROM AUTHOR]

Python implementation of permutations is presented. Two classes are introduced: Perm for permutations and Group for permutation groups. The class Perm is based on Python dictionaries and utilize cycle notation. The methods of calculation for the perm order, parity, ranking and unranking are given. A random permutation generation is also shown. The class Group is very simple and it is also based on dictionaries. It is mainly the presentation of the permutation groups interface with methods for the group order, subgroups (normalizer, centralizer, center, stabilizer), orbits, and several tests. The corresponding Python code is contained in the modules perms and groups. [ABSTRACT FROM AUTHOR]

Abstract: We present a heuristic extension to the product replacement algorithm, called the Prospector. The aim is to find hopefully good quality ‘random’ elements with short straight line programs in the given generators. This is achieved by saving the random state at certain points and later restoring it. Statistical tests are employed in order to determine when to save the state. We also give evidence for the surprisingly good effect of using an accelerator. The Prospector has been implemented in , and experimental evidence is provided which indicates that it is a very practical method. [Copyright &y& Elsevier]

Abstract: This paper introduces some relations about Cayley graphs and -graphs. We present a sufficient condition to recognize when a -graph is a Cayley graph. The relation between -graphs and Cayley graphs allows us to consider some applications to the hamiltonicity of Cayley graphs. In the last section we illustrate our results by showing that some new classes of Cayley graphs are hamiltonian. [Copyright &y& Elsevier]

Abstract: Constructing regular graphs with a given girth, a given degree and the fewest possible vertices is hard. This problem is called the cage graph problem and has some links with the error code theory. -graphs can be used in many applications: symmetric and semi-symmetric graph constructions, (Bretto and Gillibert (2008) ), hamiltonicity of Cayley graphs, and so on. In this paper, we show that -graphs can be a good tool to construct some upper bounds for the cage problem. For odd prime we construct -graphs which are -graphs with orders and , when the Sauer bound is equal to . We construct also --graphs with orders and , while the Sauer upper bound is equal to . [Copyright &y& Elsevier]

Abstract: We investigate the possibility of interpreting the degeneracy of the genetic code, i.e., the feature that different codons (base triplets) of DNA are transcribed into the same amino acid, as the result of a symmetry breaking process, in the context of finite groups. In the first part of this paper, we give the complete list of all codon representations (64-dimensional irreducible representations) of simple finite groups and their satellites (central extensions and extensions by outer automorphisms). In the second part, we analyze the branching rules for the codon representations found in the first part by computational methods, using a software package for computational group theory. The final result is a complete classification of the possible schemes, based on finite simple groups, that reproduce the multiplet structure of the genetic code. [Copyright &y& Elsevier]