Almost solutions of equations in permutations.
\(\varepsilon\)-solutionsapproximate solutions of equationsequations in symmetric groupsnormalized Hamming metricresidually finite groupsroots of permutationssofic groupssystems of equations
General theory for finite permutation groups (20B05) Symmetric groups (20B30) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Algebraic geometry over groups; equations over groups (20F70)
Let \(u(x_1,\dots,x_k)=w(x_1,\dots,x_k)\) be an equation problem in permutations \(x_i\in S_n\). \((f_1,\dots,f_k)\) is called an \(\varepsilon\)-solution of such a problem if the normalized Hamming distance \(h(u,w)\) between \(u(f_1,\dots,f_k)\) and \(w(f_1,\dots,f_k)\) is at most \(\varepsilon\). Corresponding definitions for systems of equations are also introduced. The main results are the following. Theorem 1. For any integer \(p>0\) there exists a sequence \(\delta_n>0\), \(\lim_{n\to\infty}\delta_n=0\) such that for any \(f\in S_n\) there exists a permutation \(g\in S_n\) with \(h(g^p,f)\leq\delta_n\). Theorem 2. Let \(G=\langle x_1,\dots,x_k\mid w_i(x_1,\dots,x_k)=u_i(x_1,\dots,x_k),\;i=1,\dots,r\rangle\). \(\bullet\) If the group \(G\) is finite then the system \(w_i=u_i\), \(i=1,\dots,r\), is stable in permutations. \(\bullet\) If the group \(G\) is sofic but not residually finite then the system \(w_i=u_i\), \(i=1,\dots,r\), is unstable in permutations. Here the system \(w_i=u_i\), \(i=1,\dots,r\) is called stable (in permutations) iff there exists \(\delta_\varepsilon\), \(\lim_{\varepsilon\to 0}=0\) such that for any \(\varepsilon\)-solution \((f_1,\dots,f_k)\) in \(S_n\) of the system there exists an exact solution \((\widetilde f_1,\dots,\widetilde f_k)\) in \(S_n\) such that \(h(f_i,\widetilde f_i)<\delta_\varepsilon\) for all \(i\) (note that \(\delta_\varepsilon\) is independent of \(n\)). The notion of a sofic group is rather complicated, see Definitions 2 and 3 of the paper.
- Constraint metric approximations and equations in groups
- Systems of equations in free groups which are approximated in the class of finite Abelian groups of s-periodic permutations of positive integers.
- Approximations of groups, characterizations of sofic groups, and equations over groups
- On the universality of systems of words in permutation groups
- Equations in unknown permutations
- Stability of group relations under small Hilbert-Schmidt perturbations
- Constraint metric approximations and equations in groups
- \(C^\ast\)-stability of discrete groups
- Stability for product groups and property \(( \tau )\)
- Group stability and property (T)
- Almost commuting permutations are near commuting permutations
- Uncountably many permutation stable groups
- Systems of equations in free groups which are approximated in the class of finite Abelian groups of s-periodic permutations of positive integers.
- Infinitely presented permutation stable groups and invariant random subgroups of metabelian groups
- Approximations of groups, characterizations of sofic groups, and equations over groups
- Symbolic solution of certain problems in permutations
- Stability of approximate group actions: uniform and probabilistic
- Virtually free groups are stable in permutations
- Testability in group theory
- Flexible Hilbert-Schmidt stability versus hyperlinearity for property (T) groups
- Local permutation stability
- Free metabelian groups are permutation stable
- Characters of diagonal products and Hilbert-Schmidt stability
- Rank-stability of polynomial equations
- Geometric structures in group theory. Abstracts from the workshop held February 9--14, 2025
- Optimal linear sofic approximations of countable groups
- Stability of homomorphisms, coverings and cocycles. I: Equivalence
- Surface groups are flexibly stable
- Stability of homomorphisms, coverings and cocycles. II: Examples, applications and open problems
- Local Hilbert-Schmidt stability
- On L^1-approximation of groups
This page was built for publication: Almost solutions of equations in permutations.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1026963)
