In geometric group theory, a discipline of

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern 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 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 In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior. As an illustration, suppose that we are interested in the properties of a function as becomes very large. If , then as beco ...

class of the function

R\mapsto\frac\text

where is the

ball A ball is a round object (usually spherical, but can sometimes be ovoid) with several uses. It is used in ball games, where the play of the game follows the state of the ball as it is hit, kicked or thrown by players. Balls can also be used f ...

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.

Examples

For example, consider the infinite cyclic group , embedded as a normal subgroup of the

Baumslag–Solitar group In the mathematical field of group theory, the Baumslag–Solitar groups are examples of two-generator one-relator groups that play an important role in combinatorial group theory and geometric group theory as (counter)examples and test-cases. ...

. With respect to the chosen generating sets, the element

b^=a^nba^

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 In mathematics, a free abelian group is an abelian group with a basis. Being an abelian group means that it is a set with an addition operation that is associative, commutative, and invertible. A basis, also called an integral basis, is a subse ...

on two generators is undistorted, as is any embedding of into itself.

Elementary properties

In a tower of groups , the distortion of in is at least the distortion of in . A normal

abelian subgroup In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is comm ...

has distortion determined by the

eigenvalues In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...

of the

conjugation Conjugation or conjugate may refer to: Linguistics * Grammatical conjugation, the modification of a verb from its basic form * Emotive conjugation or Russell's conjugation, the use of loaded language Mathematics * Complex conjugation, the chang ...

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 In group theory, a branch of mathematics, a core is any of certain special normal subgroups of a group. The two most common types are the normal core of a subgroup and the ''p''-core of a group. The normal core Definition For a group ''G'', the nor ...

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 for some rational . The denominator in the definition is always ; for this reason, it is often omitted. In that case, a subgroup that is not locally finite has

superadditive In mathematics, a function f is superadditive if f(x+y) \geq f(x) + f(y) for all x and y in the domain of f. Similarly, a sequence \left\, n \geq 1, is called superadditive if it satisfies the inequality a_ \geq a_n + a_m for all m and n. The ter ...

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 In cryptography, a cryptosystem is a suite of cryptographic algorithms needed to implement a particular security service, such as confidentiality (encryption). Typically, a cryptosystem consists of three algorithms: one for key generation, one for ...

, 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 .Protocol I in Although Protocol II in the same paper contains a fatal error, Scheme I is feasible; one such group/overgroup pairing is analyzed in An expository summary of both works is

References

{{Reflist Geometric group theory Low-dimensional topology