Almost solutions of equations in permutations. (Q1026963)

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.