# Given a formal power series ,decide whether there exists a polynomial the series satisfies and if it exists,how to write it down?

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?

-
How is the infinite sequence of coefficients $a_i$ being encoded? –  Eric Wofsey May 11 '14 at 15:37
@XL_at_China Perhaps this is similar to what Eric was asking: If $a_0=\pi$, do we know this, or do we only know that $a_0=3.1415...$, so that we can access any of its digits if needed, but with no a priori certainty that they will not deviate from the digits of $\pi$ eventually? –  Andres Caicedo May 11 '14 at 16:22
@XL_at_China OK. Say that the sequence is $a_0=0$, $a_1=1$, $a_2=4$, $a_3=9$, $a_4=16,\dots$ Do we know whether $a_n=n^2$ for all $n$, or do we only have access to each $a_i$ without a priori knowing whether the equality always holds? –  Andres Caicedo May 11 '14 at 16:35
If the coefficients are given by an oracle, there is no algorithm as it would have to halt after reading only finitely many coefficients. If $a_i$ is a computable sequence given by a Turing machine (say), there is no algorithm because of Rice’s theorem. –  Emil Jeřábek May 11 '14 at 16:53
There surely are particular cases where the answer is positive, and it would be interesting to record those. –  Andres Caicedo May 11 '14 at 17:01

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.

-
Thanks a lot,Michael –  XL _at_China May 11 '14 at 17:03
To tell the truth,I had known Christol's theorem before you posted your answer,but I think possibly there are more general case or more cases that are positive. –  XL _at_China May 11 '14 at 23:15
@XL_at_China: what other things do you know which are related to your question? It would be helpful to tell people such things in advance, so that you can get answers which cover things you don't know rather than things you do know. –  Michael Zieve May 12 '14 at 2:54
Michael,your answer is helpful,what I hope to know is a list of all cases that are positive,every answer is appreciated. –  XL _at_China May 13 '14 at 1:07
,Excellent,I see now,your answer includes all cases.But you know I can only choose one post as answer,and Matt's post is relevant to one of my question.Are you still in Yau's Center in China? –  XL _at_China May 13 '14 at 9:38

No, there is no algorithm. Suppose there were. Consider a polynomial $q$ in $k$ variables.

Let $a_n = 1/n!$ if $n=2^{2^m}$, and $q(x)=0$ for $x$ the $m^{th}$ $k$-tuple of integers in some enumeration.

Let $a_n=0$ otherwise.

If $q$ has only finitely many roots, then the desired polynomial $p$ exists (trivially with $p_1=1, p_0=-y$). If $q$ has infinitely many roots, then no such $p$ exists, because the non-zero terms are too spread out for any polynomial identity to hold.

So an algorithm to find $p$ would also decide whether $q$ has finitely many roots or not, and there is no such algorithm by the solution to Hilbert's tenth problem.

-
Thanks a lot,Matt –  XL _at_China May 11 '14 at 17:01
So, there is a semi-algorithm that decide whether a formal power series is algebraic. –  XL _at_China Nov 19 '14 at 0:33