If I have an generating function (GF) --- ordinary or exponential --- defining a series with at least one coefficient equal to zero, is there a general method to find the "inverse GF", i.e., the GF defining the series which only includes those zeros?

For example [a very simplified one!], if I have the "odd number exponential GF"

$EG(2n+1;x) = x^1 + x^3 + x^5 + x^7 + \dots,$

how can I use it to derive the "even number exponential GF"

$EG'(2n;x) = 1 + x^2 + x^4 + \dots$


Thanks! Kieren.

Addendum: For my trivial example, above, the inversion is (d'oh!) simply to subtract that series from the "unit series" (where all coefficients are 1), i.e.,

$(1 + x^1 + x^2 + x^3 + x^4 + x^5 + \dots) - (x^1 + x^3 + x^5 + \dots) = 1 + x^2 + x^4 + \dots.$

Ergo, this "inversion" is trivial to implement --- and the problem is reduced to the open question referenced below (i.e., to determine whether either the original GF or its "inverse" has any zeros).

Now my question is more specific: For arbitrary coefficients, is there a reasonable algorithm to derive the "inverted GF"?

  • $\begingroup$ Why would you want to do this? $\endgroup$ Aug 27 '13 at 2:01
  • 2
    $\begingroup$ @Qiaochu Yuan I have the opposite objection: it seems that such an operation (if efficient to implement) would be too useful to actually exist $\endgroup$ Aug 27 '13 at 2:11
  • $\begingroup$ What do you want as coefficients for the zero terms? Do you always want 1? $\endgroup$ Aug 27 '13 at 2:13
  • $\begingroup$ Benjamin: Ultimately, it would be useful --- perhaps, as John points out, too useful to actually exist --- if the coefficients of the original sequence could be arbitrary (as opposed to all 1, as in my simple example), and the inversion would be all 1s. However, any inversion would be quite useful, in my opinion. Do you have an idea for an inversion algorithm? $\endgroup$ Aug 27 '13 at 3:15

It is an open problem to determine whether there even exists an algorithm which determines whether a rational generating function has a coefficient equal to zero. See this blog post by Terence Tao.

  • $\begingroup$ This is an interesting related question. Thank you for the link! $\endgroup$ Aug 27 '13 at 3:12
  • 1
    $\begingroup$ For rational power series in noncommuting variables it is undecidable whether there is a non-zero coefficient. See mathoverflow.net/questions/139715/… $\endgroup$ Aug 27 '13 at 13:34
  • $\begingroup$ Note Tao's post is a proof that in one variable the support always is a regular language. $\endgroup$ Aug 27 '13 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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