5
$\begingroup$

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?

$\endgroup$
10
  • 5
    $\begingroup$ How is the infinite sequence of coefficients $a_i$ being encoded? $\endgroup$ May 11, 2014 at 15:37
  • 3
    $\begingroup$ @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? $\endgroup$ May 11, 2014 at 16:22
  • 2
    $\begingroup$ @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? $\endgroup$ May 11, 2014 at 16:35
  • 3
    $\begingroup$ 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. $\endgroup$ May 11, 2014 at 16:53
  • 4
    $\begingroup$ There surely are particular cases where the answer is positive, and it would be interesting to record those. $\endgroup$ May 11, 2014 at 17:01

2 Answers 2

13
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ May 11, 2014 at 23:15
  • 2
    $\begingroup$ @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. $\endgroup$ May 12, 2014 at 2:54
  • $\begingroup$ Michael,your answer is helpful,what I hope to know is a list of all cases that are positive,every answer is appreciated. $\endgroup$ May 13, 2014 at 1:07
  • $\begingroup$ ,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? $\endgroup$ May 13, 2014 at 9:38
  • $\begingroup$ It has not solve the problem about algebraicity of power series over field with characteristics zero $\endgroup$ Aug 25, 2014 at 10:20
12
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ So, there is a semi-algorithm that decide whether a formal power series is algebraic. $\endgroup$ Nov 19, 2014 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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