3

Given a generating function (ordinary, exponential, or otherwise) such as $$ G(a_n;\, x) := \sum_{n=0}^\infty a_nx^n $$ where one or more $a_n = 0$, is there any way to prove that $G$ does or does not have an infinite number of zeros (i.e., there is no maximum $m$ such that $a_m=0$)?

For example, let's say I have a $G$ which yields $$ G(a_n;\, x) = a_2x^2 + a_3x^3 + a_5x^5 + a_6x^6 + a_7x^7 + a_8x^8 + a_{10}x^{10} + \dotsb $$ where the gaps (“zeros”) are exactly when $n$ is an integer square — leaving aside for the moment the obvious fact that this clearly isn't the best way to generate the set of squares in a power series, can the definition of $G$ be used to prove that the set of integer squares is infinite?

Greg Martin
  • 78,820
Kieren MacMillan
  • 7,889
  • 2
  • 28
  • 70
  • 1
    To clarify: when you say "an infinite number of zeros", you are talking about coefficients $a_n$ equaling zero, as opposed to inputs $x$ such that $G(x)=0$ - is that right? – Greg Martin Oct 09 '14 at 22:03
  • Correct. I have edited the question to try to clarify. – Kieren MacMillan Oct 09 '14 at 22:04
  • Maybe you should consider, that the gaps are nothing special! Your question seems to be equivalent to ask for a proof, if infinitely many coefficients of a series have a specific value $a$. So, in some way you have to prove, that the number of coefficients taking this value exceeds all bounds, which seems plausible only for specific cases. – Markus Scheuer Oct 13 '14 at 07:26
  • @MarkusScheuer: That's a fair point… However, zeros tend to be easier to find than nonzeros, because of their “vanishing” property (imagine, for example, trying to find all points in the Riemann zeta function equalling some $r \ne 0$, rather than trying to find the zeros). I was hoping the zero might allow something special to be done. – Kieren MacMillan Oct 13 '14 at 14:44
  • @KierenMacMillan: Yes, i'm with you. Zero has a specific role due to it's nice additive and multiplicative properties. So it seems plausible, that some things could be treated easier. Although your example maybe somewhat misleading, because evaluating a generating function at a specific point and checking the result in the codomain is different to extracting coefficients. But this is clear to both of us of course! Best regards, – Markus Scheuer Oct 13 '14 at 15:48

1 Answers1

1

In the broadest sense, no, there cannot be such a procedure. Let's assume it were decidable whether there is a maximal $m$ such that $a_m = 0$. Then we could take a generic enumeration of all Turing Machines and define a generating function $A(z)$ via $a_m = 0$ if the $m$th machine $M_m $ halts on input $M_m$, and $1$ otherwise.
Now if we could decide whether there can be a maximal such $a_m$, we could also solve the Halting Problem.

Nevertheless, there will be many cases when you can decide that there is a maximal zero coefficient. Mostly that will happen by a simple recurrence relation on the coefficients (think of the recurrence relation for the Fibonacci or Catalan numbers), but in its broadest sense you are asking whether it's decidable if a general number sequence has a finite number of zeros, and that problem is undecidable.

john_leo
  • 733
  • So, to clarify: if there is a recursion equation on the coefficients, it may be or will always be possible to decide if there is a maximal zero coefficient? – Kieren MacMillan Oct 10 '14 at 13:27
  • 1
    I think you need a strong restriction on the recurrence relation (e.g. linear recurrence, or maybe something like that) for the problem to be decidable. I don't know how far one could go; maybe that's an interesting question in its own respect. Something along the line "Which type of recurrence relation guarantees that it's decidable whether there is a maximal zero coefficient". – john_leo Oct 10 '14 at 14:28
  • That sounds MO-hard… so I'm going to post it there. Thanks! – Kieren MacMillan Oct 11 '14 at 13:07
  • Sounds good. I'm looking forward to the question. It might be nice if you post a link here. Glad I could help. – john_leo Oct 11 '14 at 16:39