Subgroup distortion

Add links
Source: Wikipedia, the free encyclopedia.

In

word problem.[1] Like much of geometric group theory, the concept is due to Misha Gromov, who introduced it in 1993.[2]

Formally, let S generate group H, and let G be an overgroup for H generated by S ∪ T. Then each generating set defines a

asymptotic equivalence
class of the function
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 

Subgroups with constant distortion are called quasiconvex.[3]

Examples

For example, consider the

infinite cyclic group ℤ = ⟨b⟩, embedded as a normal subgroup of the Baumslag–Solitar group
BS(1, 2) = ⟨a, b⟩. Then
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.[2][4]

Similarly, the same infinite cyclic group, embedded in the free abelian group on two generators ℤ2, has linear distortion; the embedding in itself as 3ℤ only produces constant distortion.[2][4]

Elementary properties

In a

tower of groups
K ≤ H ≤ G, the distortion of K in G is at least the distortion of H in G.

A

normal core gives a strong lower bound.[1]

Known values

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.

superadditive distortion; conversely every superadditive function (up to asymptotic equivalence) can be found this way.[8]

In cryptography

The simplification in a word problem induced by subgroup distortion suffices to construct a

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]

References

  1. ^
    S2CID 7665268
    .
  2. ^
    OCLC 842851469
    .
  3. ^ Minasyan, Ashot (2005). On quasiconvex subgroups of hyperbolic groups (PhD). Vanderbilt. p. 1.
  4. ^
    Universitat de Barcelona
    . Retrieved 13 September 2022.
  5. S2CID 250919942
    .
  6. S2CID 122842195
    .
  7. ^ Farb, Benson (1994). "The extrinsic geometry of subgroups and the generalized word problem". Proc. London Math. Soc. 68 (3): 578. We should note that this notion of distortion differs from Gromov's definition (as defined in [18]) by a linear factor.
  8. ^
    arXiv:1212.5208v1 [math.GR
    ].
Retrieved from "https://en.wikipedia.org/w/index.php?title=Subgroup_distortion&oldid=1121140381"