14
$\begingroup$

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.

This 1997 paper

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}$?

$\endgroup$
  • 1
    $\begingroup$ Here is Romankov's paper: dropbox.com/s/kb64c0xe5z0idcd/… $\endgroup$ – Nick Gill Oct 4 '13 at 8:39
  • 1
    $\begingroup$ Here is a proposition from the paper: Decidability of the universal theory of a free two-step nilpotent group is equivalent to decidability of the universal theory of the field of rational numbers $Q$. $\endgroup$ – Nick Gill Oct 4 '13 at 8:42
  • 1
    $\begingroup$ (I don't know if that proposition answers your question because I know diddly about decidability. Sounds promising though, eh?) $\endgroup$ – Nick Gill Oct 4 '13 at 8:43
  • 2
    $\begingroup$ For the second question: units are positively existentially definable in any commutative ring by $\{x:\exists y\,(xy=1)\}$. $\endgroup$ – Emil Jeřábek Oct 4 '13 at 10:13
  • 3
    $\begingroup$ Folks: I just wanted to mention that the first question is still open. Actually, this is the question my colleague asked me; it was I who got distracted by exisential/universal/positive/whatever. $\endgroup$ – Pete L. Clark Oct 4 '13 at 18:39
7
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ This argument also shows that for the version of the EP you mention about the positive existential theory (in the language with constants for elements), the EP question depends on the way that one assigns Godel codes to those constants, and every infinite group has a presentation in that sense for which the positive existential theory is not decidable. $\endgroup$ – Joel David Hamkins Oct 4 '13 at 3:42
  • $\begingroup$ For example, one would only want to consider presentations of the group for which the atomic diagram was decidable (which is another way to say that one has a computable group), before asking about the positive existential theory. $\endgroup$ – Joel David Hamkins Oct 4 '13 at 3:51
  • 1
    $\begingroup$ This is surely a comment rather than an answer. It doesn't have anything to do with the main questions. $\endgroup$ – HJRW Oct 4 '13 at 8:36
  • $\begingroup$ @HJRW, yes, I agree with that, and I have edited to make this more clear. $\endgroup$ – Joel David Hamkins Oct 4 '13 at 11:29
  • $\begingroup$ @JoelDavidHamkins, I think the edit improves things enormously. To be clear, I think your point is worth making, and no doubt Pete appreciates it for the same reasons. $\endgroup$ – HJRW Oct 6 '13 at 8:35
6
$\begingroup$

For question 2: Over any field, every existential formula is equivalent to a positive existential one. Indeed, every negative basic formula $$\exists x_1,\dots,x_n[P(x_1,\dots,x_n) \neq 0]$$ is equivalent to the positive basic formula $$\exists x_0,x_1,\dots,x_n [x_0 \cdot P(x_1,\dots,x_n) - 1 = 0].$$ As you point out, the decidability of the existential and universal theories are equivalent problems, and with the above trick this is equivalent to the decidability of the positive existential theory ("H10") over a field.

$\endgroup$
  • $\begingroup$ Actually, I just saw that Emil had made essentially the same remark in a comment. $\endgroup$ – François G. Dorais Oct 4 '13 at 12:20
  • 1
    $\begingroup$ Great: that was easy! Come to think of it, this is very familiar: it's the same trick that shows that $\operatorname{GL}_n$ is an affine algebraic variety. $\endgroup$ – Pete L. Clark Oct 4 '13 at 12:50
  • $\begingroup$ For the same question over (some) other rings, see my 2007 paper (msp.org/ant/2007/1-3/ant-v1-n3-p04-s.pdf), or on my web page. $\endgroup$ – Laurent Moret-Bailly Nov 14 '13 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.