$ $Abert, Gelander and Nikolov [AGN17] conjectured that the number of generators $d(Gamma)$ of a lattice $Gamma$ in a high rank simple Lie group $H$ grows sub-linearly with $v = mu(H / Gamma)$, the co-volume of $Gamma$ in $H$. We prove this for non-u
niform lattices in a very strong form, showing that for $2-$generic such $H$s, $d(Gamma) = O_H(log v / log log v)$, which is essentially optimal. While we can not prove a new upper bound for uniform lattices, we will show that for such lattices one can not expect to achieve a better bound than $d(Gamma) = O(log v)$.
We initiate the study of property testing problems concerning relations between permutations. In such problems, the input is a tuple $(sigma_1,dotsc,sigma_d)$ of permutations on ${1,dotsc,n}$, and one wishes to determine whether this tuple satisfies
a certain system of relations $E$, or is far from every tuple that satisfies $E$. If this computational problem can be solved by querying only a small number of entries of the given permutations, we say that $E$ is testable. For example, when $d=2$ and $E$ consists of the single relation $mathsf{XY=YX}$, this corresponds to testing whether $sigma_1sigma_2=sigma_2sigma_1$, where $sigma_1sigma_2$ and $sigma_2sigma_1$ denote composition of permutations. We define a collection of graphs, naturally associated with the system $E$, that encodes all the information relevant to the testability of $E$. We then prove two theorems that provide criteria for testability and non-testability in terms of expansion properties of these graphs. By virtue of a deep connection with group theory, both theorems are applicable to wide classes of systems of relations. In addition, we formulate the well-studied group-theoretic notion of stability in permutations as a special case of the testability notion above, interpret all previous works on stability as testability results, survey previous results on stability from a computational perspective, and describe many directions for future research on stability and testability.
A graph $X$ is defined inductively to be $(a_0,dots,a_{n-1})$-regular if $X$ is $a_0$-regular and for every vertex $v$ of $X$, the sphere of radius $1$ around $v$ is an $(a_1,dots,a_{n-1})$-regular graph. Such a graph $X$ is said to be highly regular
(HR) of level $n$ if $a_{n-1} eq 0$. Chapman, Linial and Peled studied HR-graphs of level 2 and provided several methods to construct families of graphs which are expanders globally and locally. They ask whether such HR-graphs of level 3 exist. In this paper we show how the theory of Coxeter groups, and abstract regular polytopes and their generalisations, can lead to such graphs. Given a Coxeter system $(W,S)$ and a subset $M$ of $S$, we construct highly regular quotients of the 1-skeleton of the associated Wythoffian polytope $mathcal{P}_{W,M}$, which form an infinite family of expander graphs when $(W,S)$ is indefinite and $mathcal{P}_{W,M}$ has finite vertex links. The regularity of the graphs in this family can be deduced from the Coxeter diagram of $(W,S)$. The expansion stems from applying superapproximation to the congruence subgroups of the linear group $W$. This machinery gives a rich collection of families of HR-graphs, with various interesting properties, and in particular answers affirmatively the question asked by Chapman, Linial and Peled.
The congruence subgroup problem for a finitely generated group $Gamma$ and $Gleq Aut(Gamma)$ asks whether the map $hat{G}to Aut(hat{Gamma})$ is injective, or more generally, what is its kernel $Cleft(G,Gammaright)$? Here $hat{X}$ denotes the profinit
e completion of $X$. In the case $G=Aut(Gamma)$ we denote $Cleft(Gammaright)=Cleft(Aut(Gamma),Gammaright)$. Let $Gamma$ be a finitely generated group, $bar{Gamma}=Gamma/[Gamma,Gamma]$, and $Gamma^{*}=bar{Gamma}/tor(bar{Gamma})congmathbb{Z}^{(d)}$. Denote $Aut^{*}(Gamma)=textrm{Im}(Aut(Gamma)to Aut(Gamma^{*}))leq GL_{d}(mathbb{Z})$. In this paper we show that when $Gamma$ is nilpotent, there is a canonical isomorphism $Cleft(Gammaright)simeq C(Aut^{*}(Gamma),Gamma^{*})$. In other words, $Cleft(Gammaright)$ is completely determined by the solution to the classical congruence subgroup problem for the arithmetic group $Aut^{*}(Gamma)$. In particular, in the case where $Gamma=Psi_{n,c}$ is a finitely generated free nilpotent group of class $c$ on $n$ elements, we get that $C(Psi_{n,c})=C(mathbb{Z}^{(n)})={e}$ whenever $ngeq3$, and $C(Psi_{2,c})=C(mathbb{Z}^{(2)})=hat{F}_{omega}$ = the free profinite group on countable number of generators.
By work of Belyi, the absolute Galois group $G_{mathbb{Q}}=mathrm{Gal}(overline{mathbb{Q}}/mathbb{Q})$ of the field $mathbb{Q}$ of rational numbers can be embedded into $A=mathrm{Aut}(widehat{F_2})$, the automorphism group of the free profinite group
$widehat{F_2}$ on two generators. The image of $G_{mathbb{Q}}$ lies inside $widehat{GT}$, the Grothendieck-Teichmuller group. While it is known that every abelian representation of $G_{mathbb{Q}}$ can be extended to $widehat{GT}$, Lochak and Schneps put forward the challenge of constructing irreducible non-abelian representations of $widehat{GT}$. We do this virtually, namely by showing that a rich class of arithmetically defined representations of $G_{mathbb{Q}}$ can be extended to finite index subgroups of $widehat{GT}$. This is achieved, in fact, by extending these representations all the way to finite index subgroups of $A=mathrm{Aut}(widehat{F_2})$. We do this by developing a profinite version of the work of Grunewald and Lubotzky, which provided a rich collection of representations for the discrete group $mathrm{Aut}(F_d)$.
In a 1937 paper B.H. Neumann constructed an uncountable family of $2$-generated groups. We prove that all of his groups are permutation stable by analyzing the structure of their invariant random subgroups.
We prove that all invariant random subgroups of the lamplighter group $L$ are co-sofic. It follows that $L$ is permutation stable, providing an example of an infinitely presented such a group. Our proof applies more generally to all permutational wre
ath products of finitely generated abelian groups. We rely on the pointwise ergodic theorem for amenable groups.
Ramanujan graphs are graphs whose spectrum is bounded optimally. Such graphs have found numerous applications in combinatorics and computer science. In recent years, a high dimensional theory has emerged. In this paper these developments are surveyed
. After explaining their connection to the Ramanujan conjecture we will present some old and new results with an emphasis on random walks on these discrete objects and on the Euclidean spheres. The latter lead to golden gates which are of importance in quantum computation.
This paper describes in basic terms what a Thin Group is, as well as its uses in various subjects.
We show that for a fixed k, Gromov random groups with any positive density have no non-trivial degree-k representations over any field, a.a.s. This is especially interesting in light of the results of Agol, Ollivier and Wise that when the density is
less than 1/6 such groups have a faithful linear representation over the rationals, a.a.s.
