I am asking this question on behalf of a colleague of mine who does not have an MO account. Nevertheless I am also interested in the answer.
The question concerns relationships between Hilbert's 10th Problem (over $\mathbb{Z}$ and over $\mathbb{Q}$) and the Equations Problem (EP) in certain groups. The EP in a group $G$ is (apparently; I am not an expert here) to algorithmically decide whether an equation with parameters in a group has a solution. In other words, let $G$ be a countably infinite group and let $\{g_n\}_{n=1}^{\infty}$ be an enumeration of the elements of $G$. An equation in $G$ is a word in the $g_i$'s and in some formal variables $x_1,\ldots,x_N$ and their inverses, which is set equal to $1$. The EP is whether there is an algorithm which upon being given an equation, decides whether the equation has a solution in $G$, i.e., whether we can evaluate the indetermines to elements of $G$ so as to get a true identity. (Maybe this depends on the enumeration of the elements of $G$. If $G$ has a solvable word problem — which I think is true for the groups which are coming — then it shouldn't matter.)
Added: It seems I didn't get the formalism right. Let's restrict to finitely presented groups with solvable word problem, and enumerate the elements as distinct words in the generators with respect to some reasonable lexicographic ordering. Or, if you like, part of the question is to ask exactly what EP means in this context: certainly it means something, as it has been studied by many people.
More formally, in the language of groups augmented by a constant for each element $g_i$ of $G$, the EP is asking whether the positive existential theory of $G$ is decidable.
The questions concern a much-cited 1979 paper of Romankov:
Romanʹkov, V. A.
Universal theory of nilpotent groups. (Russian)
Mat. Zametki 25 (1979), no. 4, 487–495, 635.
A feature of the situation is that I haven't been able to get my hands on the entire paper, so but here is the MathReview by O.V. Belegradek:
A finitely generated nilpotent group has a decidable theory if and only if it is abelian-by-finite [Ju. L. Eršov, Dokl. Akad. Nauk SSSR 203 (1972), 1240–1243; MR0297840 (45 #6892)]. The author gives an example of a finitely generated 4-step nilpotent group with undecidable universal theory. The proof depends on Matijasevič's undecidability result for the universal theory of the ring of integers. A. I. Malʹcev [Mat. Sb. (N.S.) 50 (92) (1960), 257–266; MR0118677 (22 #9448)] showed the undecidability of the theory of a free 2-step nilpotent group. The author proves that the decidability of the universal part of this theory is equivalent to the decidability of the universal theory of the field of rationals. {Reviewer's remark: A. M. Slobodskoĭ and È. I. Fridman [5th All-Union Conference on Mathematical Logic, p. 140, Akad. Nauk SSSR Sibirsk. Otdel., Inst. Mat., Novosibirsk, 1979] have announced the decidability of the universal theory of the field of rationals.}
First Question: There are many free $2$-step nilpotent groups: one such group, call it $N(2,m)$ for each rank $m \geq 1$. Thus e.g. $N(2,2)$ is the standard Heisenberg group over $\mathbb{Z}$. Which group(s) does Romankov's decidability result refer to?
My guess on this: it should refer to $N(2,\infty)$, the free $2$-step nilpotent group of countably infinite rank. I also guess that it shouldn't matter much, in that the universal theories of $N(2,n)$ should be the same for all $2 \leq n \leq \infty$: I saw very similar results in the literature with solvable groups, and it seems very plausible.
Transition to the Second Question: There are many places in the literature where Romankov's result is characterized as: "Solving the equations problem in a free $2$-step nilpotent group is equivalent to Hilbert's 10th Problem over $\mathbb{Q}$." Here are some instances:
Page 1 of this arxiv preprint, which has since been published.
In the MathScinet reivew of a 1995 paper: MR1351615. The reviewer is Romankov.
But now I'm a little confused. Hilbert's 10th problem (over any ring) concerns the positive existential theory of that ring: it's about whether solutions exist to polynomial equations. Similarly for the EP. If we could omit the word "positive" then, sure, the full existential theory of any structure is decidable iff the full universal theory is, since
$\exists x P(x)$ is true exactly when $\forall x \ \neg P(x)$ is false.
So let's define E/IP to be the group theory problem with equations or inequations. So it seems to me that Romankov's result is rather that decidability of E/IP for $N(2,\infty)$ (and so perhaps also for $N(2,2)$ is my guess at Q1 is correct) is equivalent to the decidability of all polynomial equations and inequations over $\mathbb{Q}$. It seems to me though that "H10 over $\mathbb{Q}$" concerns equations only, so I wonder whether these inequations are actually necessary.
This question is equivalent to the definability of the set $R^{\bullet} = R \setminus \{0\}$ by a positive existential formula. Over $\mathbb{Z}$ this is well known to be the case: via Lagrange's Theorem that set is defined by
$\{y \mid \exists x_1,x_2,x_3,x_4 \ x_1^2 + x_2^2 + x_3^2 + x_4^2 +1= y^2\}$
I found in a survey article of T. Pheidas that for $R = \mathbb{C}[[t]]$, $R^{\bullet}$ is not positively existentially definable. But what about over $\mathbb{Q}$?
Second Question: Is it really true that EP for $H(2,2)$ is equivalent to H10/$\mathbb{Q}$? Or just that E/IP is equivalent to the undecidability of polynomial equations and inequations over $\mathbb{Q}$?
Best Answer
This is more of a comment than an answer, since I want to engage only with some of the issues you mention at the very beginning of your post. I believe that you need to take more care in formulating the Equations Problem.
Specifically, I claim that with your way of describing the equations problem, every infinite group has an enumeration for which the EP is not decidable. So this property can depend on the enumeration, even when the group has another presentation with a decidable word problem. This is because we may find an enumeration $g_0,g_1,g_2,\ldots$ of the elements of the group for which the group operation $g_ig_j=g_k$ is not decidable (equivalently, the function $(i,j)\mapsto k$ is not computable). To find such an enumeration, we simply diagonalize against the possible programs that might compute the group operation: any given finite partial enumeration can be extended so as to disagree with the next program offered as a candidate for computing the operation. And if we have enumerated the group in such a way that the group operation is not computable, then we cannot decide the corresponding EP, since we cannot decide whether $x^{-1}x g_ig_j=g_k$ has a solution or not.
This suggests that you probably want to insist on having a computable presentation of your group, in the sense of computable model theory. So you should only consider enumerations where the group operation is computable. It follows that the inverse operation is also computable, since for any element we can search for the element that multiplies with it to the identify (a fixed parameter of the algorithm).