The paper in question.

Quick introduction to the problem: suppose that $F$ is a finite field of characteristic 2 (for purposes of this post $F = \mathbb{F}_2$ will suffice) and let $F[t]$ and $F(t)$ be its ring of polynomials (polynomials over a finite field are clearly finite enumerable objects) and field of rational functions respectively. Let $P_1, P_2, \ldots P_m$ be polynomials of variables $x_1, \ldots, x_n$ with coefficients in $F[t]$.

Hilbert's tenth problem for $F(t)$ asks whether existence of $x_1, \ldots, x_n \in F(t)$ such that $P_1 (x_1, x_2, \ldots, x_n) = P_2 (x_1, x_2, \ldots, x_n) = \ldots = P_m (x_1, x_2, \ldots, x_n) = 0$ is decidable (clearly, $n, m$ and $P_i$ are finite enumerable objects, so the problem is well-posed). Understandably, this problem is often called the diophantine problem for $F(t)$ and equations $P_i (x_1, x_2, \ldots, x_n) = 0$ are called diophantine.

Paper in question supposedly proves that answer is indeed "undecidable" by reducing a undecidable problem in some first-order logic (that is not relevant to the question, I guess) to the diophantine problem over $F(t)$.

Well, preliminaries end here. I believe that lemma 2.1 (and its proof, of course) is incorrect. I will quote its statement here:

Let $x \in F(t)$. Then $x \in \{ t^{2^s} : s \geqslant 1 \} \Leftrightarrow \exists u, v, w, s \in F(t)$ such that: \begin{equation} x + t = u^2 + u \end{equation} \begin{equation} u = w^2 + t \end{equation} \begin{equation} x^{-1} + t^{-1} = v^2 + v \end{equation} \begin{equation} v = s^2 + t^{-1} \end{equation}

Well, following values of $u, v, x, s, w$ seem to be a counterexample to this lemma (clearly, $x$ is not a polynomial, let alone $t^{2^k}$ for some $k \geqslant 0$):

\begin{equation} u = \frac{t^1+t^5+t^6+t^7}{1+t^4+t^6} \end{equation} \begin{equation} v = \frac{1+t^1+t^2+t^6}{t^1+t^3+t^7} \end{equation} \begin{equation} x = \frac{t^2+t^6+t^{14}}{1+t^8+t^{12}} \end{equation} \begin{equation} s = \frac{1}{1+t^1+t^3} \end{equation} \begin{equation} w = \frac{t^3}{1+t^2+t^3} \end{equation}

Moreover, conditions $2$ and $4$ from the lemma look a bit fishy: $x + t = u^2 + u, u = w^2 + t \Leftrightarrow x + t = (w^2 + t)^2 + (w^2 + t) = (w^4 + t^2) + (w^2 + t) = w^4 + w^2 + t^2 + t \Leftrightarrow x = (w^2 + w + t)^2$ (here I use that $(a + b)^2 = a^2 + b^2$ in characteristic 2). In the same way $x^{-1} = (s^2 + s + t^{-1})^2$. Basically, they are rewritten in the form $x = y^2, y = (w^2 + w + t), y^{-1} = (s^2 + s + t^{-1})$ or $x = y^2, y + t = w^2 + w, y^{-1} + t^{-1} = s^2 + s$ (here I use that $a^2 = b^2 \Leftrightarrow a = b$ in $F(t)$). For $y$ we get just conditions $1$ and $3$ from the lemma. As it is said in paper itself (an explicit counterexample is given, on which the counterexample above is based) it is possible to choose $y \notin \{ t^{2^k} | k \geqslant 0 \}$ that it satisfies conditions $1$ and $3$. Then $x = y^2$ also does not lie in $\{t^{2^k} | k \geqslant 0 \}$.

And finally, an error in the proof seems to be in the following line (this requires actually reading the proof though): "if $q \not | ~n$ then there exists nonconstant polynomial $p$ such that $p | q, p | b, p \not | ~n$". This does not sound correct, because if, for example $b | n$ (I can't see why this can't happen), there is no such $p$. Moreover $q \not | ~n$ does not imply that a situation like $b = n, q | n^3$ can't happen ($q$ itself is not necessarily a prime).

You may wonder why I am asking this here. The reason is that I already talked about this issue with my scientific adviser and have written a letter to the author ($1,5$ months ago), who have not responded yet and I am not expecting response at all. So I am asking: are my doubts true? And what should I do about this situation?

  • $\begingroup$ Well, a month and a half is very short time. $\endgroup$ – Pasten Jun 26 '18 at 22:39
  • 1
    $\begingroup$ The article is also available at ams.org/journals/proc/1994-120-01/home.html $\endgroup$ – Pierre-Yves Gaillard Jun 26 '18 at 23:55
  • $\begingroup$ It could be anything from a typo to a fatal error, and as said above one month and a half is not a long time at all. I believe it is a bad idea to publicly express mere doubts on a specific paper. If you are sure that it is a fatal error, engage your own responsibility by asserting so, and publish it or mention it in one of your papers. If you are not, do not mention it until you are sure of it. $\endgroup$ – js21 Jun 27 '18 at 8:58
  • 2
    $\begingroup$ a month and a half is a very short time to answer an email? $\endgroup$ – Francesco Polizzi Jun 27 '18 at 10:17
  • 1
    $\begingroup$ Well, the thing is that I asked Videla and apparently he never received the email (maybe due to some spam filter?). This is something that can happen and ---if after no response one does not follow-up--- a month and a half is not enough time to decide to ask the community instead of trying again to contact the author. In any case, by now, even if that particular computation does not quite work there is enough technology in the field to address this technical point in a number of different ways. (By the way, Videla told me he will look into the issue after vacations.) $\endgroup$ – Pasten Jun 28 '18 at 3:20

Your Answer

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

Browse other questions tagged or ask your own question.