Subgroup distortion

Template:Short description 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 Template:Mvar generate group Template:Mvar, and let Template:Mvar be an overgroup for Template:Mvar generated by Template:Math. Then each generating set defines a word metric on the corresponding group; the distortion of Template:Mvar in Template:Mvar is the asymptotic equivalence class of the function $$R\mapsto \frac{{\mathrm{diam}}_H(B_G(0,R)\cap H)}{{\mathrm{diam}}_H(B_H(0,R))}\text{,}$$ where Template:Math is the ball of radius Template:Mvar about center Template:Mvar in Template:Mvar and Template:Math is the diameter of Template:Mvar.Template:Rp

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 Template:Math, embedded as a normal subgroup of the Baumslag–Solitar group Template:Math. With respect to the chosen generating sets, the element $$b^{2^n}=a^{n}b{a}^{-n}$$ is distance Template:Math from the origin in Template:Math, but distance Template:Math from the origin in Template:Math. In particular, Template:Math is at least exponentially distorted with base Template:Math.

On the other hand, any embedded copy of Template:Math in the free abelian group on two generators Template:Math is undistorted, as is any embedding of Template:Math into itself.

Elementary properties

In a tower of groups Template:Math, the distortion of Template:Mvar in Template:Mvar is at least the distortion of Template:Mvar in Template:Mvar.

A normal abelian subgroup has distortion determined by the eigenvalues of the conjugation overgroup representation; formally, if Template:Math acts on Template:Math with eigenvalue Template:Math, then Template:Mvar is at least exponentially distorted with base Template:Math. 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 Template:Math for some rational Template:Mvar.

The denominator in the definition is always Template:Math; 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 Template:Mvar. The transmitter then encodes Template:Mvar as an element Template:Math with word length Template:Mvar. In a public overgroup Template:Mvar with that distorts Template:Mvar, the element Template:Mvar has a word of much smaller length, which is then transmitted to the receiver along with a number of "decoys" from Template:Math, to obscure the secret subgroup Template:Mvar. The receiver then picks out the element of Template:Mvar, re-expresses the word in terms of generators of Template:Mvar, and recovers Template:Mvar.