Soficity, short cycles, and the Higman group

Helfgott, Harald; Juschenko, Kate

doi:10.1090/tran/7534

Soficity, short cycles, and the Higman group
HTML articles powered by AMS MathViewer

by Harald A. Helfgott and Kate Juschenko PDF

Trans. Amer. Math. Soc. 371 (2019), 2771-2795 Request permission

Abstract:

This is a paper with two aims. First, we show that the map from $\mathbb {Z}/p\mathbb {Z}$ to itself defined by exponentiation $x\to m^x$ has few $3$-cycles—that is to say, the number of cycles of length $3$ is $o(p)$. This improves on previous bounds.

Our second objective is to contribute to an ongoing discussion on how to find a nonsofic group. In particular, we show that, if the Higman group were sofic, there would be a map from $\mathbb {Z}/p\mathbb {Z}$ to itself, locally like an exponential map, yet satisfying a recurrence property.

References

Goulnara Arzhantseva and Pierre-Alain Cherix, Quantifying metric approximations of groups (unpublished).
Goulnara Arzhantseva and Liviu Păunescu, Almost commuting permutations are near commuting permutations, J. Funct. Anal. 269 (2015), no. 3, 745–757. MR 3350728, DOI 10.1016/j.jfa.2015.02.013
Yves Cornulier, A sofic group away from amenable groups, Math. Ann. 350 (2011), no. 2, 269–275. MR 2794910, DOI 10.1007/s00208-010-0557-8
Yves Cornulier, Sofic profile and computability of Cremona groups, Michigan Math. J. 62 (2013), no. 4, 823–841. MR 3160544, DOI 10.1307/mmj/1387226167
Ken Dykema, David Kerr, and Mikaël Pichot, Sofic dimension for discrete measured groupoids, Trans. Amer. Math. Soc. 366 (2014), no. 2, 707–748. MR 3130315, DOI 10.1090/S0002-9947-2013-05987-9
Gábor Elek and Endre Szabó, On sofic groups, J. Group Theory 9 (2006), no. 2, 161–171. MR 2220572, DOI 10.1515/JGT.2006.011
Gábor Elek and Endre Szabó, Sofic representations of amenable groups, Proc. Amer. Math. Soc. 139 (2011), no. 12, 4285–4291. MR 2823074, DOI 10.1090/S0002-9939-2011-11222-X
Lev Glebsky, $p$-quotients of the G. Higman group, http://arxiv.org/abs/1604.06359 (2016).
Lev Glebsky, Cycles in repeated exponentiation modulo $p^n$, Integers 13 (2013), Paper No. A66, 7. MR 3118384
Oded Goldreich and Vered Rosen, On the security of modular exponentiation with application to the construction of pseudorandom generators, J. Cryptology 16 (2003), no. 2, 71–93. MR 1982971, DOI 10.1007/s00145-002-0038-7
Lev Glebsky and Igor E. Shparlinski, Short cycles in repeated exponentiation modulo a prime, Des. Codes Cryptogr. 56 (2010), no. 1, 35–42. MR 2644246, DOI 10.1007/s10623-009-9339-2
Graham Higman, A finitely generated infinite simple group, J. London Math. Soc. 26 (1951), 61–64. MR 38348, DOI 10.1112/jlms/s1-26.1.61
Joshua Holden and Margaret M. Robinson, Counting fixed points, two-cycles, and collisions of the discrete exponential function using $p$-adic methods, J. Aust. Math. Soc. 92 (2012), no. 2, 163–178. MR 2999154, DOI 10.1017/S1446788712000262
D. L. Johnson, Presentations of groups, 2nd ed., London Mathematical Society Student Texts, vol. 15, Cambridge University Press, Cambridge, 1997. MR 1472735, DOI 10.1017/CBO9781139168410
Vivian Kuperberg, Martin Kassabov, and Tim Riley, Soficity and variations on Higman’s group, https://arxiv.org/abs/1712.07191 (2017). Based in part on V. Kuperberg’s senior thesis, under the direction of T. Riley.
David Kerr and Hanfeng Li, Soficity, amenability, and dynamical entropy, Amer. J. Math. 135 (2013), no. 3, 721–761. MR 3068400, DOI 10.1353/ajm.2013.0024
S. V. Konjagin, Letter to the editors: “The number of solutions of congruences of the $n$th degree with one unknown” [Mat. Sb. (N.S.) 109(151) (1979), no. 2, 171–187, 327; MR 80k:10013a], Mat. Sb. (N.S.) 110(152) (1979), no. 1, 158 (Russian). MR 548524
V. S. Konjagin, The number of solutions of congruences of the $n$th degree with one unknown, Mat. Sb. (N.S.) 109(151) (1979), no. 2, 171–187, 327 (Russian). MR 542556
Donald S. Ornstein and Benjamin Weiss, Entropy and isomorphism theorems for actions of amenable groups, J. Analyse Math. 48 (1987), 1–141. MR 910005, DOI 10.1007/BF02790325
Vladimir G. Pestov, Hyperlinear and sofic groups: a brief guide, Bull. Symbolic Logic 14 (2008), no. 4, 449–480. MR 2460675, DOI 10.2178/bsl/1231081461
Sarvar Patel and Ganapathy S. Sundaram, An efficient discrete log pseudo-random generator, Advances in cryptology—CRYPTO ’98 (Santa Barbara, CA, 1998) Lecture Notes in Comput. Sci., vol. 1462, Springer, Berlin, 1998, pp. 304–317. MR 1670959, DOI 10.1007/BFb0055737
Paul E. Schupp, Small cancellation theory over free products with amalgamation, Math. Ann. 193 (1971), 255–264. MR 291298, DOI 10.1007/BF02052566
Andreas Thom, About the metric approximation of Higman’s group, J. Group Theory 15 (2012), no. 2, 301–310. MR 2900231, DOI 10.1515/jgt.2011.102
A. M. Vershik and E. I. Gordon, Groups that are locally embeddable in the class of finite groups, Algebra i Analiz 9 (1997), no. 1, 71–97 (Russian); English transl., St. Petersburg Math. J. 9 (1998), no. 1, 49–67. MR 1458419