Subgroup distortion

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]

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 

Subgroups with constant distortion are called quasiconvex.[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⟩. Then

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]

Similarly, the same infinite cyclic group, embedded in the free abelian group on two generators ℤ2, has linear distortion; the embedding in itself as 3ℤ only produces constant distortion.[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]

References
  1. 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. Gromov, M. (1993). Asymptotic Invariants of Infinite Groups. London Mathematical Society lecture notes 182. Cambridge University Press. OCLC 842851469.
  3. Minasyan, Ashot (2005). On quasiconvex subgroups of hyperbolic groups (PhD). Vanderbilt. p. 1.
  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. Davis, Tara C.; Olshanskii, Alexander Yu. (October 29, 2018). "Relative Subgroup Growth and Subgroup Distortion". arXiv:1212.5208v1 [math.GR].
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.