Given a formal power series $$y(x)=\sum\_{i=0}^{\infty} a\_i x^i$$ Is there an algorithm that decides whether there exists a polynomial$$ P(x,y)=p\_n(x)y^n+p\_{n-1}(x)y^{n-1}+\cdots+p\_0(x)=0,p\_j(x)\in F[x]$$the series satisfies and if it exists,how to write it down?



Given a formal power series ,decide whether there exists a polynomial the series satisfies and if it exists,how to write it down?
One result in this area is Christol's theorem, which asserts that
an element of $\mathbf{F}\_p[[X]]$ is algebraic over $\mathbf{F}\_p(X)$
if and only if its sequence of coefficients is a $p$-automatic sequence,
which means that there is a finite state machine for which
the coefficient of $X^n$ is the output of this machine upon input
the base $p$ expression of $n$.


This is relevant because if an element of $\mathbf{Z}[[X]]$ is algebraic over
$\mathbf{Q}(X)$, then its reduction modulo any prime $p$ will be algebraic
over $\mathbf{F}\_p(X)$.


For further results, and applications of these theorems to prove that certain elements of $\mathbf{Z}[[X]]$ are transcendental over $\mathbf{Q}(X)$, see the book "Automatic Sequences" by Jean-Paul Allouche and Jeffrey Shallit.


