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 K in H.

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. 1 2 Broaddus, Nathan; Farb, Benson; Putman, Andrew (2011). "Irreducible Sp-representations and subgroup distortion in the mapping class group". Commentarii Mathematici Helvetici . 86 (3): 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.