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. Like much of geometric group theory, the concept is due to Misha Gromov, who introduced it in 1993. 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 R ↦ diam H ( B G ( 0 , R ) ∩ H ) diam H ( B H ( 0 , R ) ) , {\displaystyle R\mapsto {\frac {\operatorname {diam} _{H}(B_{G}(0,R)\cap H)}{\operatorname {diam} _{H}(B_{H}(0,R))}}{\text{,}}} where BX(x, r) is the ball of radius r about center x in X and diam(S) is the diameter of S. A subgroup with bounded distortion is called undistorted, and is the same thing as a quasi-isometrically embedded subgroup.
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 b a − n {\displaystyle b^{2^{n}}=a^{n}ba^{-n}} 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. 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.
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.
Known values Every computable function with at most exponential growth can be a subgroup distortion, but Lie subgroups of a nilpotent Lie group always have distortion n ↦ nr for some rational r. The denominator in the definition is always 2R; for this reason, it is often omitted. 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.
In cryptography The simplification in a word problem induced by subgroup distortion suffices to construct a cryptosystem, algorithms for encoding and decoding secret messages. 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.
References
