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 generate group, and let be an overgroup for generated by . Then each generating set defines a word metric on the corresponding group; the distortion of in is the asymptotic equivalence class of the function where is the ball of radius about center in and is the diameter of .
A subgroup with bounded distortion is called undistorted, and is the same thing as a quasi-isometrically embedded subgroup.[3]
For example, consider the infinite cyclic group, embedded as a normal subgroup of the Baumslag–Solitar group . With respect to the chosen generating sets, the element is distance from the origin in, but distance from the origin in . In particular, is at least exponentially distorted with base .
On the other hand, any embedded copy of in the free abelian group on two generators is undistorted, as is any embedding of into itself.
In a tower of groups, the distortion of in is at least the distortion of in .
A normal abelian subgroup has distortion determined by the eigenvalues of the conjugation overgroup representation; formally, if acts on with eigenvalue, then 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.
Every computable function with at most exponential growth can be a subgroup distortion,[4] but Lie subgroups of a nilpotent Lie group always have distortion for some rational .[5]
The denominator in the definition is always ; for this reason, it is often omitted.[6] 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.[7]
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 . The transmitter then encodes as an element with word length . In a public overgroup with that distorts, the element has a word of much smaller length, which is then transmitted to the receiver along with a number of "decoys" from, to obscure the secret subgroup . The receiver then picks out the element of, re-expresses the word in terms of generators of, and recovers .[8]