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 

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. ^ a b 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. ^ a b c d 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. ^ a b c d 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. ^ a b Davis, Tara C.; Olshanskii, Alexander Yu. (October 29, 2018). "Relative Subgroup Growth and Subgroup Distortion". arXiv:1212.5208v1 [math.GR].