Group Theory (math.GR)

  • PDF
    We generalize the notions of elliptic pseudoprimes and elliptic Carmichael numbers introduced by Silverman to analogues of Euler-Jacobi and strong pseudoprimes. We investigate the relationships among Euler Elliptic Carmichael numbers , strong elliptic Carmichael numbers, products of anomalous primes and elliptic Korselt numbers of Type I: The former two of these are introduced in this paper, and the latter two of these were introduced by Mazur (1973) and Silverman (2012) respectively. In particular, we expand upon a previous work of Babinkostova et al. by proving a conjecture about the density of certain elliptic Korselt numbers of Type I that are products of anomalous primes.
  • PDF
    Direct powers of perfect groups admit more concise presentations than one might naively suppose. If $H_1G=H_2G=0$, then $G^n$ has a presentation with $O(\log n)$ generators and $O(\log n)^3$ relators. If, in addition, there is an element $g\in G$ that has infinite order in every non-trivial quotient of $G$, then $G^n$ has a presentation with $d(G) +1$ generators and $O(\log n)$ relators. The bounds that we obtain on the deficiency of $G^n$ are not monotone in $n$; this points to potential counterexamples for the Relation Gap Problem.
  • PDF
    We prove that each solenoidal lamination with leaves isometric to the real-hyperbolic n-space and transitive homeomorphism group, is homeomorphic to the inverse limit of the system of finite covers of a compact hyperbolic n-manifold.
  • PDF
    Let $G$ be the first Grigorchuk group. We show that the commutator width of $G$ is $2$: every element $g\in [G,G]$ is a product of two commutators, and also of six conjugates of $a$. Furthermore, we show that every finitely generated subgroup $H\leq G$ has finite commutator width, which however can be arbitrarily large, and that $G$ contains a subgroup of infinite commutator width. The proofs were assisted by the computer algebra system GAP.
  • PDF
    We classify the groups quasi-isometric to a group generated by finite-order elements within the class of one-ended hyperbolic groups which are not Fuchsian and whose JSJ decomposition over two-ended subgroups does not contain rigid vertex groups. To do this, we characterize which JSJ trees of a group in this class admit a cocompact group action with quotient a tree. The conditions are stated in terms of two graphs we associate to the degree refinement of a group in this class. We prove there is a group in this class which is quasi-isometric to a Coxeter group but is not abstractly commensurable to a group generated by finite-order elements. Consequently, the subclass of groups in this class generated by finite-order elements is not quasi-isometrically rigid. We provide necessary conditions for two groups in this class to be abstractly commensurable. We use these conditions to prove there are infinitely many abstract commensurability classes within each quasi-isometry class within this class that contains a group generated by finite-order elements.
  • PDF
    Recent results by Alagic and Russell have given some evidence that the Even-Mansour cipher may be secure against quantum adversaries with quantum queries, if considered over other groups than $(\mathbb{Z}/2)^n$. This prompts the question as to whether or not other classical schemes may be generalized to arbitrary groups and whether classical results still apply to those generalized schemes. In this thesis, we generalize the Even-Mansour cipher and the Feistel cipher. We show that Even and Mansour's original notions of secrecy are obtained on a one-key, group variant of the Even-Mansour cipher. We generalize the result by Kilian and Rogaway, that the Even-Mansour cipher is pseudorandom, to super pseudorandomness, also in the one-key, group case. Using a Slide Attack we match the bound found above. After generalizing the Feistel cipher to arbitrary groups we resolve an open problem of Patel, Ramzan, and Sundaram by showing that the 3-round Feistel cipher over an arbitrary group is not super pseudorandom. We generalize a result by Gentry and Ramzan showing that the Even-Mansour cipher can be implemented using the Feistel cipher as the public permutation. In this result, we also consider the one-key case over a group and generalize their bound. Finally, we consider Zhandry's result on quantum pseudorandom permutations, showing that his result may be generalized to hold for arbitrary groups. In this regard, we consider whether certain card shuffles may be generalized as well.
  • PDF
    We prove structure theorems for the moduli stack of elliptic curves equipped with $G$-structures, where $G$ is a finite 2-generated metabelian group. In particular, we show that if $G$ has exponent $e$, then there is a subgroup $H\le GL_2(\mathbb{Z}/e)$ such that $G$-structures on elliptic curves $E$ are equivalent to "congruence structures of level $H$". Our methods are almost entirely group theoretic. Let $\widehat{M}$ denote the free profinite metabelian group of rank 2, then along the way we prove a decomposition of $Out(\widehat{M})$ as an internal semi-direct product of the subgroup of "braid-like outer automorphisms" with the subgroup of "IA" outer automorphisms which induce the identity on the abelianization. We also show a surprising result that all IA-automorphisms leave every open normal subgroup stable.
  • PDF
    We investigate the structure of root data by considering their decomposition as a product of a semisimple root datum and a torus. Using this decomposition we obtain a parameterisation of the isomorphism classes of all root data. By working at the level of root data we introduce the notion of a smooth regular embedding of a connected reductive algebraic group, which is a refinement of the commonly used regular embeddings introduced by Lusztig. In an unpublished manuscript Asai proved three key reduction techniques that are used for reducing statements about arbitrary connected reductive algebraic groups, equipped with a Frobenius endomorphism, to those whose derived subgroup is simple and simply connected. By using our investigations into root data we give new proofs of Asai's results and generalise them so that they are compatible with Steinberg endomorphisms. As an illustration of these ideas, we answer a question posed to us by Olivier Dudas concerning unipotent supports.
  • PDF
    Let $q=2^f$, and let $G=\mathrm{SO}_8^+(q)$ and $U$ be a Sylow $2$-subgroup of $G$. We first describe the fusion of the conjugacy classes of $U$ in $G$. We then use this information to prove the unitriangularity of the $\ell$-decomposition matrices of $G$ for all $\ell \ne 2$ by inducing certain irreducible characters of $U$ to $G$; the characters of $U$ of degree $q^3/2$ play here a major role. We then determine the $\ell$-decomposition matrix of $G$ in the case $\ell \mid q+1$, when $\ell \ge 5$ and $(q+1)_\ell>5$, up to two non-negative indeterminates in one column.
  • PDF
    This paper concerns finite groups of class (at most) two and of odd prime exponent $p$. Such a group is called special if the center lies within its derived group. Every group of class 2 and exponent $p$ can be uniquely expressed as the direct product of an elementary abelian group and a special group. This reduces the isomorphism problem to special groups. The special groups having $G'$ cyclic are well known. Groups having $|G'|=p^2$ are known to be generated by two abelian subgroups. As such, they can be described by a pair of Scharlau Matrices which we will define. Using these, Vishnevetskii ([1], [2]) classified the special groups which are not central products of groups of smaller order. We call these Vishnevetskii indecomposable. All decomposable groups are central products of two or more indecomposable groups. By Theorem 2 of [2], if $G$ is a special group with derived group of order $p^2$ then the indecomposable central factors of $G$, together with their multiplicities, form a set of invariants for $G$. However these invariants do not determine $G$, since (as we will show below) two nonisomorphic groups can have the same indecomposable central factors. The groups of exponent $p$ and order dividing $p^8$ are already in the literature. In this paper we prove that there are six isomorphism types of special groups of order $p^9$ having $|G'|=p^2$, and we list them. We will also introduce a way of representing groups of class 2 having exponent $p$ by using digraphs with flows on the edges. The digraph is compact and gives, on sight, a great deal of structural information about the group and completely defines the group. Some group invariants will also be described which are easy to compute from the digraphs and which can readily be used to distinguish the isomorphism types for small orders.
  • PDF
    Let $\sigma =\{\sigma_{i} | i\in I\}$ be a partition of the set of all primes $\Bbb{P}$ and $G$ a finite group. Let $\sigma (G)=\{\sigma _{i} : \sigma _{i}\cap \pi (G)\ne \emptyset$. A set ${\cal H}$ of subgroups of $G$ is said to be a complete Hall $\sigma $-set of $G$ if every member $\ne 1$ of ${\cal H}$ is a Hall $\sigma _{i}$-subgroup of $G$ for some $i\in I$ and $\cal H$ contains exactly one Hall $\sigma _{i}$-subgroup of $G$ for every $i$ such that $\sigma _{i}\in \sigma (G)$. We say that $G$ is $\sigma$-full if $G$ possesses a complete Hall $\sigma $-set. A complete Hall $\sigma $-set $\cal H$ of $G$ is said to be a $\sigma$-basis of $G$ if every two subgroups $A, B \in\cal H$ are permutable, that is, $AB=BA$. In this paper, we study properties of finite groups having a $\sigma$-basis. In particular, we prove that if $G$ has a a $\sigma$-basis, then $G$ is generalized $\sigma$-soluble, that is, $G$ has a complete Hall $\sigma $-set and for every chief factor $H/K$ of $G$ we have $|\sigma (H/K)|\leq 2$. Moreover, answering to Problem 8.28 in [A.N. Skiba, On some results in the theory of finite partially soluble groups, Commun. Math. Stat., 4(3) (2016), 281--309], we prove the following Theorem A. Suppose that $G$ is $\sigma$-full. Then every complete Hall $\sigma$-set of $G$ forms a $\sigma$-basis of $G$ if and only if $G$ is generalized $\sigma$-soluble and for the automorphism group $G/C_{G}(H/K)$, induced by $G$ on any its chief factor $H/K$, we have either $\sigma (H/K)=\sigma (G/C_{G}(H/K))$ or $\sigma (H/K) =\{\sigma _{i}\}$ and $G/C_{G}(H/K)$ is a $\sigma _{i} \cup \sigma _{j}$-group for some $i\ne j$.
  • PDF
    High dimensional expanders is a vibrant emerging field of study. Nevertheless, the only known construction of bounded degree high dimensional expanders is based on Ramanujan complexes, whereas one dimensional bounded degree expanders are abundant. In this work we construct new families of bounded degree high dimensional expanders obeying the local spectral expansion property. A property that implies, geometric overlapping, fast mixing of high dimensional random walks, agreement testing and agreement expansion. The construction also yields new families of expander graphs which are close to the Ramanujan bound, i.e., their spectral gap is close to optimal. The construction is quite elementary and it is presented in a self contained manner; This is in contrary to the highly involved construction of the Ramanujan complexes. The construction is also strongly symmetric; The symmetry of the construction could be used, for example, to obtain good symmetric LDPC codes that were previously based on Ramanujan graphs.
  • PDF
    This work continues the study of the properties of finitely constrained groups of binary tree automorphisms in terms of their Hausdorff dimension. We prove that there are exactly $2^{2d-3}$ finitely constrained groups of binary tree automorphisms with pattern size $d$ and having Hausdorff dimension $1 - \frac{2}{2^{d-1}}$. As part of this proof, we describe the finite patterns that can define such groups, which leads to the fact that all finitely constrained groups of nearly maximal Hausdorff dimension have additive portraits. Additionally, we give an upper bound, in terms of the pattern size $d$, on the number of topologically finitely generated instances with nearly maximal Hausdorff dimension for a given $d$, by applying corollaries of the criteria of Bondarenko and Samoilovych. We also construct a new family of examples of finitely constrained, topologically finitely generated groups with nearly maximal Hausdorff dimension. We conclude by positing several open questions.
  • PDF
    For every group $G$, we introduce the set of hyperbolic structures on $G$, denoted $\mathcal{H}(G)$, which consists of equivalence classes of (possibly infinite) generating sets of $G$ such that the corresponding Cayley graph is hyperbolic; two generating sets of $G$ are equivalent if the corresponding word metrics on $G$ are bi-Lipschitz equivalent. Alternatively, one can define hyperbolic structures in terms of cobounded $G$-actions on hyperbolic spaces. We are especially interested in the subset $\mathcal{AH}(G)\subseteq \mathcal{H}(G)$ of acylindrically hyperbolic structures on $G$, i.e., hyperbolic structures corresponding to acylindrical actions. Elements of $\mathcal{H}(G)$ can be ordered in a natural way according to the amount of information they provide about the group $G$. The main goal of this paper is to initiate the study of the posets $\mathcal{H}(G)$ and $\mathcal{AH}(G)$ for various groups $G$. We discuss basic properties of these posets such as cardinality and existence of extremal elements, obtain several results about hyperbolic structures induced from hyperbolically embedded subgroups of $G$, and study to what extent a hyperbolic structure is determined by the set of loxodromic elements and their translation lengths.
  • PDF
    We introduce the notion of metrically systolic simplicial complexes. We study geometric and large-scale properties of such complexes and of groups acting on them geometrically. We show that all two-dimensional Artin groups act geometrically on metrically systolic complexes. As direct corollaries we obtain new results on two-dimensional Artin groups and all their finitely presented subgroups: we prove that the Conjugacy Problem is solvable, and that the Dehn function is quadratic. We also show several large-scale features of finitely presented subgroups of two-dimensional Artin groups, lying background for further studies concerning their quasi-isometric rigidity.

Recent comments

Jalex Stark Apr 06 2017 22:46 UTC

However, one should note that I_3322 may be able to do something that this paper doesn't. William's work leaves open the question of whether there are games with infinite-dimensional tensor product strategies but no finite-dimensional ones. Some of us might expect that I_3322 has this property.

Laura Mančinska Mar 28 2017 13:09 UTC

Great result!

For those familiar with I_3322, William here gives an example of a nonlocal game exhibiting a behaviour that many of us suspected (but couldn't prove) to be possessed by I_3322.

Robert Raussendorf Jan 24 2017 22:29 UTC

Regarding Mark's above comment on the role of the stabilizer states: Yes, all previous works on the subject have used the stabilizer states and Clifford gates as the classical backbone. This is due to the Gottesman-Knill theorem and related results. But is it a given that the free sector in quantum

...(continued)
Planat Jan 24 2017 13:09 UTC

Are you sure? Since we do not propose a conjecture, there is nothing wrong. A class of strange states underlie the pentagons in question. The motivation is to put the magic of computation in the permutation frame, one needs more work to check its relevance.

Mark Howard Jan 24 2017 09:59 UTC

It seems interesting at first sight, but after reading it the motivation is very muddled. It boils down to finding pentagons (which enable KCBS-style proofs of contextuality) within sets of projectors, some of which are stabilizer states and some of which are non-stabilizer states (called magic stat

...(continued)