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 \cup 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 $R\mapsto {\frac {\operatorname {diam} _{H}(B_{G}(0,R)\cap H)}{\operatorname {diam} _{H}(B_{H}(0,R))}}{\text{,}}$ where $B X (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 $b^{2^{n}}=a^{n}ba^{-n}$ is distance $2 n$ from the origin in $ℤ$ , but distance $2 n + 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 \leq H \leq 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 \in G$ acts on $V \leq 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 \mapsto n r$ for some rational $r$ .^[6]

The denominator in the definition is always $2 R$ ; 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 \in 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

^ ^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.
^ ^a ^b ^c ^d Gromov, M. (1993). Asymptotic Invariants of Infinite Groups. London Mathematical Society lecture notes 182. Cambridge University Press. OCLC 842851469.
^ Druţu, Cornelia; Kapovich, Michael (2018). Geometric Group Theory. American Mathematical Society, Providence, RI. p. 285. ISBN 978-1-4704-1104-6.
^ ^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.
^ 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.
^ Osin, D. V. (2001). "Subgroup distortions in nilpotent groups". Communications in Algebra. 29 (12): 5439–5463. doi:10.1081/AGB-100107938. S2CID 122842195.
^ 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.
^ ^a ^b Davis, Tara C.; Olshanskii, Alexander Yu. (October 29, 2018). "Relative Subgroup Growth and Subgroup Distortion". arXiv:1212.5208v1 [math.GR].