Subgroup distortion

Last updated

In geometric group theory, a discipline of mathematics, subgroup distortion measures the extent to which an overgroup can reduce the complexity of a group's word problem. [1] Like much of geometric group theory, the concept is due to Misha Gromov, who introduced it in 1993. [2]

Contents

Formally, let S generate group H, and let G be an overgroup for H generated by S ∪ T. Then each generating set defines a word metric on the corresponding group; the distortion of H in G is the asymptotic equivalence class of the function where BX(x, r) is the ball of radius r about center x in X and diam(S) is the diameter of S. [2] : 49 

A subgroup with bounded distortion is called undistorted, and is the same thing as a quasi-isometrically embedded subgroup. [3]

Examples

For example, consider the infinite cyclic group ℤ = ⟨b⟩, embedded as a normal subgroup of the Baumslag–Solitar group BS(1, 2) = ⟨a, b⟩. With respect to the chosen generating sets, the element is distance 2n from the origin in ℤ, but distance 2n + 1 from the origin in BS(1, 2). In particular, ℤ is at least exponentially distorted with base 2. [2] [4]

On the other hand, any embedded copy of ℤ in the free abelian group on two generators ℤ2 is undistorted, as is any embedding of ℤ into itself. [2] [4]

Elementary properties

In a tower of groups K ≤ H ≤ G, the distortion of K in G is at least the distortion of H in G.

A normal abelian subgroup has distortion determined by the eigenvalues of the conjugation overgroup representation; formally, if g ∈ G acts on V ≤ G with eigenvalue λ, then V is at least exponentially distorted with base λ. For many non-normal but still abelian subgroups, the distortion of the normal core gives a strong lower bound. [1]

Known values

Every computable function with at most exponential growth can be a subgroup distortion, [5] but Lie subgroups of a nilpotent Lie group always have distortion n ↦ nr for some rational r. [6]

The denominator in the definition is always 2R; for this reason, it is often omitted. [7] [8] In that case, a subgroup that is not locally finite has superadditive distortion; conversely every superadditive function (up to asymptotic equivalence) can be found this way. [8]

In cryptography

The simplification in a word problem induced by subgroup distortion suffices to construct a cryptosystem, algorithms for encoding and decoding secret messages. [4] Formally, the plaintext message is any object (such as text, images, or numbers) that can be encoded as a number n. The transmitter then encodes n as an element g ∈ H with word length n. In a public overgroup G with that distorts H, the element g has a word of much smaller length, which is then transmitted to the receiver along with a number of "decoys" from G \ H, to obscure the secret subgroup H. The receiver then picks out the element of H, re-expresses the word in terms of generators of H, and recovers n. [4]

Related Research Articles

<span class="mw-page-title-main">Nilpotent group</span> Concept in group theory of mathematics

In mathematics, specifically group theory, a nilpotent groupG is a group that has an upper central series that terminates with G. Equivalently, it has a central series of finite length or its lower central series terminates with {1}.

In the mathematical subject of geometric group theory, the growth rate of a group with respect to a symmetric generating set describes how fast a group grows. Every element in the group can be written as a product of generators, and the growth rate counts the number of elements that can be written as a product of length n.

<span class="mw-page-title-main">Geometric group theory</span> Area in mathematics devoted to the study of finitely generated groups

Geometric group theory is an area in mathematics devoted to the study of finitely generated groups via exploring the connections between algebraic properties of such groups and topological and geometric properties of spaces on which these groups can act non-trivially.

In mathematics, a unipotent elementr of a ring R is one such that r − 1 is a nilpotent element; in other words, (r − 1)n is zero for some n.

<span class="mw-page-title-main">Systolic geometry</span> Form of differential geometry

In mathematics, systolic geometry is the study of systolic invariants of manifolds and polyhedra, as initially conceived by Charles Loewner and developed by Mikhail Gromov, Michael Freedman, Peter Sarnak, Mikhail Katz, Larry Guth, and others, in its arithmetical, ergodic, and topological manifestations. See also Introduction to systolic geometry.

<span class="mw-page-title-main">Hyperbolic group</span> Mathematical concept

In group theory, more precisely in geometric group theory, a hyperbolic group, also known as a word hyperbolic group or Gromov hyperbolic group, is a finitely generated group equipped with a word metric satisfying certain properties abstracted from classical hyperbolic geometry. The notion of a hyperbolic group was introduced and developed by Mikhail Gromov. The inspiration came from various existing mathematical theories: hyperbolic geometry but also low-dimensional topology, and combinatorial group theory. In a very influential chapter from 1987, Gromov proposed a wide-ranging research program. Ideas and foundational material in the theory of hyperbolic groups also stem from the work of George Mostow, William Thurston, James W. Cannon, Eliyahu Rips, and many others.

In mathematics, a nilmanifold is a differentiable manifold which has a transitive nilpotent group of diffeomorphisms acting on it. As such, a nilmanifold is an example of a homogeneous space and is diffeomorphic to the quotient space , the quotient of a nilpotent Lie group N modulo a closed subgroup H. This notion was introduced by Anatoly Mal'cev in 1949.

In mathematics, especially in the area of abstract algebra that studies infinite groups, the adverb virtually is used to modify a property so that it need only hold for a subgroup of finite index. Given a property P, the group G is said to be virtually P if there is a finite index subgroup such that H has property P.

<span class="mw-page-title-main">Quasi-isometry</span> Function between two metric spaces that only respects their large-scale geometry

In mathematics, a quasi-isometry is a function between two metric spaces that respects large-scale geometry of these spaces and ignores their small-scale details. Two metric spaces are quasi-isometric if there exists a quasi-isometry between them. The property of being quasi-isometric behaves like an equivalence relation on the class of metric spaces.

In mathematics, a group is called boundedly generated if it can be expressed as a finite product of cyclic subgroups. The property of bounded generation is also closely related with the congruence subgroup problem.

Bass–Serre theory is a part of the mathematical subject of group theory that deals with analyzing the algebraic structure of groups acting by automorphisms on simplicial trees. The theory relates group actions on trees with decomposing groups as iterated applications of the operations of free product with amalgamation and HNN extension, via the notion of the fundamental group of a graph of groups. Bass–Serre theory can be regarded as one-dimensional version of the orbifold theory.

In the mathematical area of group theory, the Grigorchuk group or the first Grigorchuk group is a finitely generated group constructed by Rostislav Grigorchuk that provided the first example of a finitely generated group of intermediate growth. The group was originally constructed by Grigorchuk in a 1980 paper and he then proved in a 1984 paper that this group has intermediate growth, thus providing an answer to an important open problem posed by John Milnor in 1968. The Grigorchuk group remains a key object of study in geometric group theory, particularly in the study of the so-called branch groups and automata groups, and it has important connections with the theory of iterated monodromy groups.

In the mathematical subject of geometric group theory, a Dehn function, named after Max Dehn, is an optimal function associated to a finite group presentation which bounds the area of a relation in that group in terms of the length of that relation. The growth type of the Dehn function is a quasi-isometry invariant of a finitely presented group. The Dehn function of a finitely presented group is also closely connected with non-deterministic algorithmic complexity of the word problem in groups. In particular, a finitely presented group has solvable word problem if and only if the Dehn function for a finite presentation of this group is recursive. The notion of a Dehn function is motivated by isoperimetric problems in geometry, such as the classic isoperimetric inequality for the Euclidean plane and, more generally, the notion of a filling area function that estimates the area of a minimal surface in a Riemannian manifold in terms of the length of the boundary curve of that surface.

In mathematics, the concept of a relatively hyperbolic group is an important generalization of the geometric group theory concept of a hyperbolic group. The motivating examples of relatively hyperbolic groups are the fundamental groups of complete noncompact hyperbolic manifolds of finite volume.

In mathematics, and more precisely in topology, the mapping class group of a surface, sometimes called the modular group or Teichmüller modular group, is the group of homeomorphisms of the surface viewed up to continuous deformation. It is of fundamental importance for the study of 3-manifolds via their embedded surfaces and is also studied in algebraic geometry in relation to moduli problems for curves.

Non-commutative cryptography is the area of cryptology where the cryptographic primitives, methods and systems are based on algebraic structures like semigroups, groups and rings which are non-commutative. One of the earliest applications of a non-commutative algebraic structure for cryptographic purposes was the use of braid groups to develop cryptographic protocols. Later several other non-commutative structures like Thompson groups, polycyclic groups, Grigorchuk groups, and matrix groups have been identified as potential candidates for cryptographic applications. In contrast to non-commutative cryptography, the currently widely used public-key cryptosystems like RSA cryptosystem, Diffie–Hellman key exchange and elliptic curve cryptography are based on number theory and hence depend on commutative algebraic structures.

In metric geometry, asymptotic dimension of a metric space is a large-scale analog of Lebesgue covering dimension. The notion of asymptotic dimension was introduced by Mikhail Gromov in his 1993 monograph Asymptotic invariants of infinite groups in the context of geometric group theory, as a quasi-isometry invariant of finitely generated groups. As shown by Guoliang Yu, finitely generated groups of finite homotopy type with finite asymptotic dimension satisfy the Novikov conjecture. Asymptotic dimension has important applications in geometric analysis and index theory.

In the mathematical subject of group theory, a co-Hopfian group is a group that is not isomorphic to any of its proper subgroups. The notion is dual to that of a Hopfian group, named after Heinz Hopf.

In the mathematical subject of geometric group theory, an acylindrically hyperbolic group is a group admitting a non-elementary 'acylindrical' isometric action on some geodesic hyperbolic metric space. This notion generalizes the notions of a hyperbolic group and of a relatively hyperbolic group and includes a significantly wider class of examples, such as mapping class groups and Out(Fn).

<span class="mw-page-title-main">Glossary of Lie groups and Lie algebras</span>

This is a glossary for the terminology applied in the mathematical theories of Lie groups and Lie algebras. For the topics in the representation theory of Lie groups and Lie algebras, see Glossary of representation theory. Because of the lack of other options, the glossary also includes some generalizations such as quantum group.

References

  1. 1 2 Broaddus, Nathan; Farb, Benson; Putman, Andrew (2011). "Irreducible Sp-representations and subgroup distortion in the mapping class group". Commentarii Mathematici Helvetici. 86: 537–556. arXiv: 0707.2262 . doi:10.4171/CMH/233. S2CID   7665268.
  2. 1 2 3 4 Gromov, M. (1993). Asymptotic Invariants of Infinite Groups. London Mathematical Society lecture notes 182. Cambridge University Press. OCLC   842851469.
  3. ↑ Druţu, Cornelia; Kapovich, Michael (2018). Geometric Group Theory. American Mathematical Society, Providence, RI. p. 285. ISBN   978-1-4704-1104-6.
  4. 1 2 3 4 Protocol I in Chatterji, Indira; Kahrobaei, Delaram; Ni Yen Lu (2017). "Cryptosystems Using Subgroup Distortion". Theoretical and Applied Informatics. 1. 29 (2): 14–24. arXiv: 1610.07515 . doi:10.20904/291-2014. S2CID   16899700. Although Protocol II in the same paper contains a fatal error, Scheme I is feasible; one such group/overgroup pairing is analyzed in Kahrobaei, Delaram; Keivan, Mallahi-Karai (2019). "Some applications of arithmetic groups in cryptography". Groups Complexity Cryptology. 11 (1): 25–33. arXiv: 1803.11528 . doi:10.1515/gcc-2019-2002. S2CID   119676551. An expository summary of both works is Werner, Nicolas (19 June 2021). Group distortion in Cryptography (PDF) (grado). Barcelona: Universitat de Barcelona . Retrieved 13 September 2022.
  5. ↑ Olshanskii, A. Yu. (1997). "On subgroup distortion in finitely presented groups". Matematicheskii Sbornik. 188 (11): 51–98. Bibcode:1997SbMat.188.1617O. CiteSeerX   10.1.1.115.1717 . doi:10.1070/SM1997v188n11ABEH000276. S2CID   250919942.
  6. ↑ Osin, D. V. (2001). "Subgroup distortions in nilpotent groups". Communications in Algebra. 29 (12): 5439–5463. doi:10.1081/AGB-100107938. S2CID   122842195.
  7. ↑ Farb, Benson (1994). "The extrinsic geometry of subgroups and the generalized word problem". Proc. London Math. Soc. 68 (3): 578. We should note that this notion of distortion differs from Gromov's definition (as defined in [18]) by a linear factor.
  8. 1 2 Davis, Tara C.; Olshanskii, Alexander Yu. (October 29, 2018). "Relative Subgroup Growth and Subgroup Distortion". arXiv: 1212.5208v1 [math.GR].
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.