Search

The relational complexity of a subgroup 퐺 of Sym ⁢ (Ω) is a measure of the way in which the orbits of 퐺 on Ω k for various 푘 determine the original action of 퐺. Very few precise values of relational complexity are known. This paper determines the exact relational complexity of all groups lying between PSL n ⁢ (F) and PGL n ⁢ (F) , for an arbitrary field 픽, acting on the set of 1-dimensional subspaces of F n . We also bound the relational complexity of all groups lying between PSL n ⁢ (q) and P ⁢ Γ ⁢ L n ⁢ (q) , and generalise these results to the action on 푚-spaces for m ≥ 1 . [ABSTRACT FROM AUTHOR]

An irredundant base of a group G$G$ acting faithfully on a finite set Γ$\Gamma$ is a sequence of points in Γ$\Gamma$ that produces a strictly descending chain of pointwise stabiliser subgroups in G$G$, terminating at the trivial subgroup. Suppose that G$G$ is Sn$\operatorname{S}_{n}$ or An$\operatorname{A}_{n}$ acting primitively on Γ$\Gamma$, and that the point stabiliser is primitive in its natural action on n$n$ points. We prove that the maximum size of an irredundant base of G$G$ is On$O\left(\sqrt {n}\right)$, and in most cases O(logn)2$O\left((\log n)^2\right)$. We also show that these bounds are best possible. [ABSTRACT FROM AUTHOR]

We say that a finite group G satisfies the independence property if, for every pair of distinct elements x and y of G, either { x , y } is contained in a minimal generating set for G or one of x and y is a power of the other. We give a complete classification of the finite groups with this property, and in particular prove that every such group is supersoluble. A key ingredient of our proof is a theorem showing that all but three finite almost simple groups H contain an element s such that the maximal subgroups of H containing s, but not containing the socle of H, are pairwise non-conjugate. [ABSTRACT FROM AUTHOR]

The standard (n, k, d) model of random groups is a model where the relators are chosen randomly from the set of cyclically reduced words of length k on an n-element generating set. Gromov's density model of random groups considers the case where n is fixed, and k tends to infinity. We instead fix k, and let n tend to infinity. We prove that for all k ≥ 2 at density d > 1∕2 a random group in this model is trivial or cyclic of order two, whilst for d < 1 2 such a random group is infinite and hyperbolic. In addition, we show that for d < 1 k such a random group is free, and that this threshold is sharp. These extend known results for the triangular ( k = 3 ) and square ( k = 4) models of random groups. [ABSTRACT FROM AUTHOR]

We show that given generators for subgroups G and H of Sn, if G is primitive then generators for NH(G) may be computed in quasipolynomial time, namely 2O(log3n). The previous best known bound was simply exponential. [ABSTRACT FROM AUTHOR]

The generating graph $\unicode[STIX]{x1D6E4}(H)$ of a finite group $H$ is the graph defined on the elements of $H$, with an edge between two vertices if and only if they generate $H$. We show that if $H$ is a sufficiently large simple group with $\unicode[STIX]{x1D6E4}(G)\cong \unicode[STIX]{x1D6E4}(H)$ for a finite group $G$, then $G\cong H$. We also prove that the generating graph of a symmetric group determines the group. [ABSTRACT FROM AUTHOR]

Abstract: Let be a quasisimple classical group in its natural representation over a finite vector space , and let . We construct the projection from to and provide fast, polynomial-time algorithms for computing the image of an element. Given a discrete logarithm oracle, we also represent as a group with at most 3 generators and 6 relations. We then compute canonical representatives for the cosets of . A key ingredient of our algorithms is a new, asymptotically fast method for constructing isometries between spaces with forms. Our results are useful for the matrix group recognition project, can be used to solve element conjugacy problems, and can improve algorithms to construct maximal subgroups. [ABSTRACT FROM AUTHOR]

In this article we show that the isomorphism type of certain semilinear classical groups may depend on the choice of form matrix, as well as the dimension and the field size. When there is more than one isomorphism type, we count them and present effective polynomial-time algorithms to determine whether two such groups are isomorphic. [ABSTRACT FROM AUTHOR]

The maximal subgroups of the finite classical groups are divided by a theorem of Aschbacher into nine classes. In this paper, the authors show how to construct those maximal subgroups of the finite classical groups of linear, symplectic or unitary type that lie in the first eight of these classes. The ninth class consists roughly of absolutely irreducible groups that are almost simple modulo scalars, other than classical groups over the same field in their natural representation. All of these constructions can be carried out in low-degree polynomial time. [ABSTRACT FROM PUBLISHER]

In this paper we describe all known instances of primitive soluble groups of affine type which have a single self-paired nondiagonal orbital. We show how to construct representations of the point stabiliser that are imprimitive, semilinear, subfield, or tensor decomposable. As a corollary we give a constructive proof that there exist groups with arbitrarily large numbers of orbitals, only two of which are self-paired. [ABSTRACT FROM AUTHOR]

In this paper we complete the classification of the primitive permutation groups of degree less than 1000 by determining the irreducible subgroups of GL(n,p) for p prime and pn<1000. We also enumerate the maximal subgroups of GL(8,2), GL(4,5) and GL(6,3). [Copyright &y& Elsevier]

It is undecidable in general whether a given finitely presented group is word hyperbolic. We use the concept of pregroups , introduced by Stallings (1971) , to define a new class of van Kampen diagrams, which represent groups as quotients of virtually free groups. We then present a polynomial-time procedure that analyses these diagrams, and either returns an explicit linear Dehn function for the presentation, or returns fail, together with its reasons for failure. Furthermore, if our procedure succeeds we are often able to produce in polynomial time a word problem solver for the presentation that runs in linear time. Our algorithms have been implemented, and when successful they are many orders of magnitude faster than KBMAG , the only comparable publicly available software. [ABSTRACT FROM AUTHOR]