Subgroup distortion
{{Short description|Concept in geometric group theory}}
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.{{cite journal|journal=Commentarii Mathematici Helvetici|volume=86|year=2011|pages=537–556|doi=10.4171/CMH/233|title=Irreducible Sp-representations and subgroup distortion in the mapping class group|first1=Nathan|last1=Broaddus|first2=Benson|last2=Farb|author-link2=Benson Farb|first3=Andrew|last3=Putman|author-link3=Andrew Putman|arxiv=0707.2262|s2cid=7665268 }} Like much of geometric group theory, the concept is due to Misha Gromov, who introduced it in 1993.{{cite book |last=Gromov |first=M. |title=Asymptotic Invariants of Infinite Groups |publisher=Cambridge University Press |year=1993 |series=London Mathematical Society lecture notes 182 |oclc=842851469 |author-link=Mikhael Gromov (mathematician)}}
Formally, let {{mvar|S}} generate group {{mvar|H}}, and let {{mvar|G}} be an overgroup for {{mvar|H}} generated by {{math|S ∪ T}}. Then each generating set defines a word metric on the corresponding group; the distortion of {{mvar|H}} in {{mvar|G}} is the asymptotic equivalence class of the function where {{math|BX(x, r)}} is the ball of radius {{mvar|r}} about center {{mvar|x}} in {{mvar|X}} and {{math|diam(S)}} is the diameter of {{mvar|S}}.{{rp|49}}
A subgroup with bounded distortion is called undistorted, and is the same thing as a quasi-isometrically embedded subgroup.{{cite book |last1=Druţu |first1=Cornelia |last2=Kapovich |first2=Michael |title=Geometric Group Theory |date=2018 |publisher=American Mathematical Society, Providence, RI |isbn=978-1-4704-1104-6 |page=285}}
Examples
For example, consider the infinite cyclic group {{math|{{mathbb|Z}} {{=}} ⟨b⟩}}, embedded as a normal subgroup of the Baumslag–Solitar group {{math|BS(1, 2) {{=}} ⟨a, b⟩}}. With respect to the chosen generating sets, the element is distance {{math|2n}} from the origin in {{math|{{mathbb|Z}}}}, but distance {{math|2n + 1}} from the origin in {{math|BS(1, 2)}}. In particular, {{math|{{mathbb|Z}}}} is at least exponentially distorted with base {{math|2}}.
On the other hand, any embedded copy of {{math|{{mathbb|Z}}}} in the free abelian group on two generators {{math|{{mathbb|Z}}2}} is undistorted, as is any embedding of {{math|{{mathbb|Z}}}} into itself.
Elementary properties
In a tower of groups {{math|K ≤ H ≤ G}}, the distortion of {{mvar|K}} in {{mvar|G}} is at least the distortion of {{mvar|K}} in {{mvar|H}}.
A normal abelian subgroup has distortion determined by the eigenvalues of the conjugation overgroup representation; formally, if {{math|g ∈ G}} acts on {{math|V ≤ G}} with eigenvalue {{math|λ}}, then {{mvar|V}} is at least exponentially distorted with base {{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,{{cite journal |last=Olshanskii |first=A. Yu. |author-link=Aleksandr Olshansky |title=On subgroup distortion in finitely presented groups |journal=Matematicheskii Sbornik |year=1997 |volume=188 |issue=11 |pages=51–98|doi=10.1070/SM1997v188n11ABEH000276 |bibcode=1997SbMat.188.1617O |citeseerx=10.1.1.115.1717 |s2cid=250919942 }} but Lie subgroups of a nilpotent Lie group always have distortion {{math|n ↦ nr}} for some rational {{mvar|r}}.{{cite journal |last=Osin |first=D. V. |author-link=Denis Osin |year=2001 |title=Subgroup distortions in nilpotent groups |journal=Communications in Algebra |volume=29 |issue=12 |doi=10.1081/AGB-100107938 |pages=5439–5463|s2cid=122842195 }}
The denominator in the definition is always {{math|2R}}; for this reason, it is often omitted.{{cite journal|title=The extrinsic geometry of subgroups and the generalized word problem|first=Benson|last=Farb|author-link=Benson Farb|journal=Proc. London Math. Soc.|volume=68|issue=3|year=1994|page=578|quote=We should note that this notion of distortion differs from Gromov's definition (as defined in #{{harvid]) by a linear factor.}} 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.{{cite arXiv |eprint=1212.5208v1 |first1=Tara C. |last1=Davis |first2=Alexander Yu. |last2=Olshanskii |title=Relative Subgroup Growth and Subgroup Distortion |date=October 29, 2018|class=math.GR }}
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 {{mvar|n}}. The transmitter then encodes {{mvar|n}} as an element {{math|g ∈ H}} with word length {{mvar|n}}. In a public overgroup {{mvar|G}} with that distorts {{mvar|H}}, the element {{mvar|g}} has a word of much smaller length, which is then transmitted to the receiver along with a number of "decoys" from {{math|G \ H}}, to obscure the secret subgroup {{mvar|H}}. The receiver then picks out the element of {{mvar|H}}, re-expresses the word in terms of generators of {{mvar|H}}, and recovers {{mvar|n}}.Protocol I in {{cite journal|url=https://academicworks.cuny.edu/cgi/viewcontent.cgi?article=1298&context=ny_pubs|title=Cryptosystems Using Subgroup Distortion|year=2017|first1=Indira|last1=Chatterji|author1-link=Indira Chatterji|first2=Delaram|last2=Kahrobaei|author2-link=Delaram Kahrobaei|author3=Ni Yen Lu|journal=Theoretical and Applied Informatics|volume=29|series=1|number=2|pages=14–24|doi=10.20904/291-2014|arxiv=1610.07515|s2cid=16899700 }} Although Protocol II in the same paper contains a fatal error, Scheme I is feasible; one such group/overgroup pairing is analyzed in {{cite journal|last1=Kahrobaei|first1=Delaram|author1-link=Delaram Kahrobaei|last2=Keivan|first2=Mallahi-Karai|title=Some applications of arithmetic groups in cryptography|journal=Groups Complexity Cryptology|volume=11|number=1|year=2019|pages=25–33|doi=10.1515/gcc-2019-2002 |arxiv=1803.11528|s2cid=119676551 }} An expository summary of both works is {{cite thesis|title=Group distortion in Cryptography|publisher=Universitat de Barcelona|first=Nicolas|last=Werner|location=Barcelona|date=19 June 2021|type=grado|url=http://diposit.ub.edu/dspace/bitstream/2445/185858/1/tfg_werner_nicolas.pdf|access-date=13 September 2022}}