Groups with context-free Diophantine problem (Q6566725)

Let \(G\) be a finitely generated group, \(A\) be a finite symmetric generating set for \(G\) and let \(X= \{ x_{1}, x_{1}^{-1}, \ldots, x_{n}, x_{n}^{-1} \}\) be a set of formal variables and their inverses. An \(n\)-ary polynomial over \((G, A)\) is a word from \(P_{n}(G,A)= (A\cup X)^{\ast}\). A tuple \((g_{1},\ldots,g_{n})\in G^{n}\) is a solution of the polynomial \(\alpha \in P_{n}(G,A)\) if \(\iota (\alpha)(g_{1}, \ldots ,g_{n})=e\) for some interpretation \(\iota: P_{n}(G,A) \rightarrow G^{n}\) of \(n\)-ary polynomials. The word problem in \((G,A)\) is the formal language \(\mathrm{Id}(G,A)=\{\alpha \in P_{0}(G, A) \mid \iota(\alpha)=e\}\).\N\NIt is well known that \(\mathrm{Id}(G,A)\) is regular if and only if \(G\) is finite [\textit{A. V. Anisimov}, Kibernetika, Kiev 1971, No. 4, 18--24 (1971; Zbl 0241.68034)], \(\mathrm{Id}(G,A)\) is recursively enumerable if and only if \(G\) is a subgroup of a finitely presented group [\textit{G. Higman}, Proc. R. Soc. Lond., Ser. A 262, 455--475 (1961; Zbl 0104.02101)] and \(\mathrm{Id}(G, A)\) is context-free if and only if \(G\) is virtually free [\textit{D. E. Muller} and \textit{P. E. Schupp}, J. Comput. Syst. Sci. 26, 295--310 (1983; Zbl 0537.20011)].\N\NThe \(n\)-ary Diophantine problem over \((G,A)\) is the language \(\mathrm{Eq}_{n}(G,A)\) of all polynomials from \(P_{n}(G,A)\) that have a solution, in particular \(\mathrm{Eq}_{0}(G,A)=\mathrm{Id}(G,A)\).\N\NThe main result of the article under review is the following: \N\NTheorem 1.1. Suppose that \(G\) is a finitely generated group and \(A\) is a finite symmetric generating set for \(G\). Then the following statements are equivalent: \begin{enumerate}\N\item The \(n\)-ary Diophantine problem is context-free for some \(n \geq 1\); \N\item The \(n\)-ary Diophantine problem is context-free for all \(n \geq 1\); \N\item \(G\) is finite.\N\end{enumerate}\N\NSimilar results are proved (see Section 3) for groups with regular Diophantine problems (they are exactly all finite groups) and for groups with recursively enumerable Diophantine problems (they are exactly all finitely generated subgroups of finitely presented groups).