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.
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.
For many non-normal but still abelian subgroups, the distortion of the normal core gives a strong lower bound.
[1] 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.
[8] 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]