Search

We prove that finite entropy random walks on the torsion-free Baumslag group in dimension $d=2$ have non-trivial Poisson boundary. This is in contrast with the torsion case where the situation for simple random walks on Baumslag groups is the same as for the lamplighter groups of the same dimension. Our proof uses the realization of the Baumslag group as a linear group. We define and study a class of linear groups associated with multivariable polynomials which we denote $G_k(p)$. We show that the groups $G_3(p)$ have non-trivial Poisson boundary for all irreducible finite entropy measures, under a condition on the polynomial $p$ which we call the spaced polynomial property. We show that the Baumslag group has $G_3(1+x-y)$ as a subgroup, and that the polynomial $p = 1+x-y$, satisfies this property. Given any upper-triangle group of characteristic zero, we prove that one of the following must hold: 1) all finite second moment symmetric random walks on $G$ have trivial boundary 2) the group admits a block, which has a $3$ dimensional wreath product as a subgroup, and all non-degenerate random walks on $G$ have non-trivial boundary. 3) $G$ has a group $G_3(p)$ as a subgroup. We give a conjectural characterisation of all polynomials satisfying the spaced polynomial property. If this is confirmed, our result provides a characterisation of linear groups $G$ which admit a finitely supported symmetric random walk with non-trivial boundary., Comment: 19 pages

Given a finitely generated group, the well-known Stability Problem asks whether the non-triviality of the Poisson-Furstenberg boundary (which is equivalent to the existence of non-constant bounded harmonic functions) depends on the choice of simple random walk on the group. This question was far from being understood even in the class of linear groups. Given an amenable group, e.g. a solvable group, there is no known characterisation, even a conjectural one, of when it admits a simple random walk with non-trivial boundary. We provide a characterisation of groups with non-trivial boundary for finitely generated linear groups of characteristic $p$. We prove in particular that the Stability Problem has a positive answer in this class of groups. For linear groups of characteristic $0$, we prove a sufficient condition for the triviality of the boundary which does not depend on the choice of a simple random walk. We conjecture that our sufficient condition is also necessary. Our arguments are based on a new comparison criterion for group extensions, on new $\Delta$-restriction entropy estimates and a criterion for boundary non-triviality, and on a new "cautiousness" criterion for triviality of the boundary., Comment: 58 pages, 8 figures V2: abstract revised, some typos corrected, reference Schapira [53] added

We prove that all spaces of finite Assouad-Nagata dimension admit a good order for Travelling Salesman Problem, and provide sufficient conditions under which the converse is true. We formulate a conjectural characterisation of spaces of finite $AN$-dimension, which would yield a gap statement for the efficiency of orders on metric spaces. Under assumption of doubling, we prove a stronger gap phenomenon about all orders on a given metric space., Comment: 27 pages. This paper appeared originally as the second part of first versions of arXiv:2011.01732. Now the paper is split it two parts, the first one "Spaces that can be ordered effectively: virtually free groups and hyperbolicity" arXiv:2011.01732, and the second part here

We prove the law of large numbers for the drift of random walks on the two-dimensional lamplighter group, under the assumption that the random walk has finite $(2+\epsilon)$-moment. This result is in contrast with classical examples of abelian groups, where the displacement after $n$ steps, normalised by its mean, does not concentrate, and the limiting distribution of the normalised $n$-step displacement admits a density whose support is $[0,\infty)$. We study further examples of groups, some with random walks satisfying LLN for drift and other examples where such concentration phenomenon does not hold, and study relation of this property with asymptotic geometry of groups.

We study asymptotic invariants of metric spaces, defined in terms of the travelling salesman problem, and our goal is to classify groups and spaces depending on how well they can be ordered in this context. We characterize virtually free groups as those admitting an order which has some efficiency on $4$-point subsets. We show that all $\delta$-hyperbolic spaces can be ordered extremely efficiently, for the question when the number of points of a subset tends to $\infty$., Comment: 33 pages. This is the first part of the paper, which appeared on arxiv in previous versions. The paper is split in two parts, and the second one appears now as "Assouad-Nagata dimension and gap for ordered metric spaces"

For any countable group with infinite conjugacy classes we construct a family of forests on the group. For each of them there is a random walk on the group with the property that its sample paths almost surely converge to the geometric boundary of the forest in a way that resembles the simple random walks on trees. It allows us to identify the Poisson boundary of the random walk with the boundary of the forest and to show that the group action on the Poisson boundary is free (which, in particular, implies non-triviality of the Poisson boundary). As a consequence we obtain that any countable group carries a random walk such that the stabilizer of almost every point of the Poisson boundary coincides with the hyper-FC-centre of the group, and, more generally, we characterize all normal subgroups which can serve as the pointwise stabilizer of the Poisson boundary of a random walk on a given countable group. Our work is a development of a recent result of Frisch - Hartman - Tamuz - Vahidi Ferdowsi who proved that any group which is not hyper-FC-central admits a measure with a non-trivial Poisson boundary.

On torsion Grigorchuk groups we construct random walks of finite entropy and power-law tail decay with non-trivial Poisson boundary. Such random walks provide near optimal volume lower estimates for these groups. In particular, for the first Grigorchuk group $G$ we show that its volume growth function $v_{G,S}(n)$ satisfies that $\lim_{n\to\infty}\log\log v_{G,S}(n)/\log n=\alpha_{0}$, where $\alpha_{0}=\frac{\log2}{\log\lambda_{0}}\approx0.7674$, $\lambda_{0}$ is the positive root of the polynomial $X^{3}-X^{2}-2X-4$.

We show that there is no iterated identity satisfied by all finite groups. For $w$ being a non-trivial word of length $l$, we show that there exists a finite group $G$ of cardinality at most $\exp(l^C)$ which does not satisfy the iterated identity $w$. The proof uses the approach of Borisov and Sapir, who used dynamics of polynomial mappings for the proof of non residual finiteness of some groups., Comment: 21 pages

We prove an isoperimetric inequality for groups. As an application, we obtain lower bound on F{\o}lner functions in various nilpotent-by-cyclic groups. Under a regularity assumption, we obtain a characterization of F{\o}lner functions of these groups. As another application, we evaluate the asymptotics of the F{\o}lner function of $Sym(\mathbb{Z})\rtimes {\mathbb{Z}}$. We construct new examples of groups with Shalom's property $H_{\mathrm{FD}}$, in particular among nilpotent-by-cyclic and lacunary hyperbolic groups. Among these examples we find groups with property $H_{\mathrm{FD}}$, which are direct products of lacunary hyperbolic groups and have arbitrarily large F{\o}lner functions., Comment: A symmetry assumption on the set T is added in Theorem 1.1

Given a $1$-cocycle $b$ with coefficients in an orthogonal representation, we show that any finite dimensional summand of $b$ is cohomologically trivial if and only if $\| b(X_n) \|^2/n$ tends to a constant in probability, where $X_n$ is the trajectory of the random walk $(G,\mu)$. As a corollary, we obtain sufficient conditions for $G$ to satisfy Shalom's property $H_{\mathrm{FD}}$. Another application is a convergence to a constant in probability of $\mu^{*n}(e) -\mu^{*n}(g)$, $n\gg m$, normalized by its average with respect to $\mu^{*m}$, for any finitely generated amenable group without infinite virtually Abelian quotients. Finally, we show that the harmonic equivariant mapping of $G$ to a Hilbert space obtained as an $U$-ultralimit of normalized $\mu^{*n}- g \mu^{*n}$ can depend on the ultrafilter $U$ for some groups., Comment: 22 pages; typos fixed (v2); Section 4 revised to cover locally compact groups (v3)

We study the neighborhoods of a typical point $Z_n$ visited at $n$-th step of a random walk, determined by the condition that the transition probabilities stay close to $\mu^{*n}(Z_n)$. If such neighborhood contains a ball of radius $C \sqrt{n}$, we say that the random walk has almost invariant transition probabilities. We prove that simple random walks on wreath products of $\mathbb{Z}$ with finite groups have almost invariant distributions. A weaker version of almost invariance implies a necessary condition of Ozawa's criterion for the property $H_{\rm FD}$. We define and study the radius of almost invariance, we estimate this radius for random walks on iterated wreath products and show this radius can be asymptotically strictly smaller than $n/L(n)$, where $L(n)$ denotes the drift function of the random walk. We show that the radius of individual almost invariance of a simple random walk on the wreath product of $\mathbb{Z}^2$ with a finite group is asymptotically strictly larger than $n/L(n)$. Finally, we show the existence of groups such that the radius of almost invariance is smaller than a given function, but remains unbounded. We also discuss possible limiting distribution of ratios of transition probabilities on non almost invariant scales.

Given word on $n$ letters, we study groups which satisfiy "iterated identity" $w$, meaning that for all $x_1, \dots, x_n$ there exists $m$ such that $m$-the iteration of $w$ of Engel type, applied to $x_1, \dots, x_n$, is equal to the identity. We define bounded groups and groups which are fractal with respect to identities. This notion of being fractal can be viewed as a self-similarity conditions for the set of identities, satisfied by a group. In contrast with torsion groups and Engel groups, groups which are fractal with respect to identities appear among finitely generated elementary amenable groups. We prove that any polycyclic, as well as any metabelian group is bounded and we compute the iterational depth for various wreath products. We study the set of iterated identities, satisfied by a given group, which is not necessarily a subgroup of a free group and not necessarily invariant under conjugation, in contrast with usual identities. Finally, we discuss another notion of iterated identities of groups, which we call solvability type iterated identities, and its relation to elementary classes of varieties of groups.

For every metric space $\mathcal X$ in which there exists a sequence of finite groups of bounded-size generating set that does not embed coarsely, and for every unbounded, increasing function $\rho$, we produce a group of subexponential word growth all of whose imbeddings in $\mathcal X$ have distortion worse than $\rho$. This applies in particular to any B-convex Banach space $\mathcal X$, such as Hilbert space., Comment: Used to appear as first half of arXiv:1403.5584

Every countable group that does not contain a finitely generated subgroup of exponential growth imbeds in a finitely generated group of subexponential growth. This produces in particular the first examples of groups of subexponential growth containing the additive group of the rationals., Comment: Compared to v1, some typos corrected, and the part on distortion split off to arXiv:1406.5908

We consider the oriented graph whose vertices are isomorphism classes of finitely generated groups, with an edge from G to H if, for some generating set T in H and some sequence of generating sets S_i in G, the marked balls of radius i in (G,S_i) and in (H,T) coincide. Given a nilpotent group G, we characterize its connected component in this graph: if that connected component contains at least one torsion-free group, then it consists of those groups which generate the same variety of groups as G. The arrows in the graph define a preorder on the set of isomorphism classes of finitely generated groups. We show that a partial order can be imbedded in this preorder if and only if it is realizable by subsets of a countable set under inclusion. We show that every countable group imbeds in a group of non-uniform exponential growth. In particular, there exist groups of non-uniform exponential growth that are not residually of subexponential growth and do not admit a uniform imbedding into Hilbert space.

We show that there exists a finitely generated group of growth ~f for all functions f:\mathbb{R}\rightarrow\mathbb{R} satisfying f(2R) \leq f(R)^{2} \leq f(\eta R) for all R large enough and \eta\approx2.4675 the positive root of X^{3}-X^{2}-2X-4. This covers all functions that grow uniformly faster than \exp(R^{\log2/\log\eta}). We also give a family of self-similar branched groups of growth ~\exp(R^\alpha) for a dense set of \alpha\in(\log2/\log\eta,1)., Comment: small typos corrected from v2

We study the Poisson-Furstenberg boundary of random walks on permutational wreath products. We give a sufficient condition for a group to admit a symmetric measure of finite first moment with non-trivial boundary, and show that this criterion is useful to establish exponential word growth of groups. We construct groups of exponential growth such that all finitely supported (not necessarily symmetric, possibly degenerate) random walks on these groups have trivial boundary. This gives a negative answer to a question of Kaimanovich and Vershik., Comment: 24 pages

We study the geometry of a class of group extensions, containing permutational wreath products, which we call "permutational extensions". We construct for all natural number k a torsion group with growth function asymptotically $\exp(n^{1-(1-\alpha)^k}),\quad 2^{3-3/\alpha}+2^{2-2/\alpha}+2^{1-1/\alpha}=2$, and a torsion-free group with growth function asymptotically $\exp(\log(n)n^{1-(1-\alpha)^k})$. These are the first examples of groups of intermediate growth for which the growth function is known. We construct a group of intermediate growth that contains the group of finitely supported permutations of a countable set as a subgroup. This gives the first example of a group of intermediate growth containing an infinite simple group as a subgroup., Comment: Revision with a few typos fixed. to appear in Inventiones Mathematicae

We study certain self-interacting walks on the set of integers, that choose to jump to the right or to the left randomly but influenced by the number of times they have previously jumped along the edges in the finite neighbourhood of their current position (in the present paper, typically, we will discuss the case where one considers the neighbouring edges and the next-to-neighbouring edges). We survey a variety of possible behaviours, including some where the walk is eventually confined to an interval of large length. We also focus on certain "asymmetric" drifts, where we prove that with positive probability, the walks behave deterministically on large scale and move like a constant times the square root of time, or like a constant times the logarithm of time.

We investigate the asymptotic behaviour of a class of self-interacting nearest neighbour random walks on the one-dimensional integer lattice which are pushed by a particular linear combination of their own local time on edges in the neighbourhood of their current position. We prove that in a range of the relevant parameter of the model such random walkers can be eventually confined to a finite interval of length depending on the parameter value. The phenomenon arises as a result of competing self-attracting and self-repelling effects where in the named parameter range the former wins.