Lemma 1.
For any $x$ in the ring $F[t,t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$), $x$ is a power of $t$ if and only if $x$ divides $1$ and $t-1$ divides $x-1$ (the divisibilities are meant, of course, in $F[t, t^{-1}]$).
Lemma 2.
$t^n-1$ divides $t^m-1$ in $F[t, t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$) if and only if $n$ divides $m$ in $\mathbb{Z}$.
Lemma 3.
Assume that the characteristic of $F$ is $p$ and $p>2$. Then $(t^m-1)/(t^n-1)$ is a square in $F[t, t^{-1}]$ ($F[t,t^{-1}]$: the polynomials in $t$ and $t^{-1}$ with coefficients in the field $F$) if and only if $(\exists s \in \mathbb{Z}) m=np^s$.
THEOREM.
Assume that $F$ has characteristic $p>2$. Then the existential theory of $F[t, t^{-1}]$ is undecidable.
PROOF.
We think of the powers of $t$ as representing the integers; thus, $t^n$ represents the integer $n$. By Lemma $1$, the set of powers of $t$ is existentially definable.
Addition of integers $m+n$ corresponds to multiplication of the corresponding powers of $t$, $t^mt^n$.
By Lemma $2$, the relation "$n$ divides $m$" (where $n$ and $m$ are given through their corresponding powers $t^n$ and $t^m$) is existentially definable.
Moreover, the relation $(\exists s \in \mathbb{Z})m=p^sn$, by Lemma $3$, is also existentially definable.
Therefore, if we had an algorithm to answer existential questions over $F[t, t^{-1}]$, we could convert it to an algorithm to answer existential questions in $\mathbb{Z}$ with the structure of addition, divisibility, and the relation $(\exists s \in \mathbb{Z})m=p^sn$.
In an other paper it is shown that the last structure has undecidable positive existential theory (more accurately, one can define multiplication in a positive existential way in it, and therefore, the complexity of its positive existential theory is the same as the complexity of the positive existential theory of $\mathbb{Z}$ with addition and multiplication).
It follows that the existential theory of $F[t, t^{-1}]$ is undecidable.
$$$$
How exactly do we conclude from the lemmas to the following? I haven't really understood it... Could you explain it to me?
Therefore, if we had an algorithm to answer existential questions over $F[t, t^{-1}]$, we could convert it to an algorithm to answer existential questions in $\mathbb{Z}$ with the structure of addition, divisibility, and the relation $(\exists s \in \mathbb{Z})m=p^sn$.
$$$$
EDIT1 :
The language is $\{+,\cdot , 0,1,t\}$.
I read again the proof and I undetstood the following:
We suppose that the existential theory of $F[t,t^{-1}]$ is decidable, that means that there is an algorithm that answers existential questions over $F[t,t^{-1}]$.
We want to reduce it to the existential theory of $\mathbb{Z}$ with the structure of addition, divisibility, and the relation $(\exists s\in\mathbb{Z})m=p^sn$, which is undecidable.
To do so, we do the following:
One part of the "translation" of the reduction is the mapping $t^n\mapsto n$.
So, the set "powers of t" corresponds to "integers".
So, we have to be able to "filter out" the powers of $t$ from all the other elements of $F[t, t^{-1}]$ in an existential way, according to Lemma $1$, permitted by the language.
We have that $t^mt^n=t^{m+n}\mapsto m+n$ so $\mathbb{Z}$ has the structure of addition.
By Lemma $2$ , $\mathbb{Z}$ has the structure of divisibility.
And by Lemma $3$, $\mathbb{Z}$ has the structure of the relation $(\exists s\in \mathbb{Z})m=np^s$.
Is that the idea of reduction? Have I understood it correctly?
$$$$
EDIT2:
I am reading again the proof and I got stuck at the following point:
We say that by Lemma $2$, $\mathbb{Z}$ has the structure of divisibility.
Do we conclude to that because this lemma can be written as an existential formula which is true in $F[t,t^{-1}]$ ?
But the language does not consist of the divisibility. How is this existential formula?
$$$$
EDIT3:
Why doesn't the theorem stand also for $p=2$ ?
I have had a chance to look at the paper now. Your description of the reduction and your understanding of the argument is perfectly correct. Your restatement of Lemma 1 is not quite right as explained by quid in acomment above.