0
$\begingroup$

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"?

Improve this question
$\endgroup$
4
  • $\begingroup$ Why would you want to do this? $\endgroup$
    – Qiaochu Yuan
    Aug 27, 2013 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$
    – John Wiltshire-Gordon
    Aug 27, 2013 at 2:11
  • $\begingroup$ What do you want as coefficients for the zero terms? Do you always want 1? $\endgroup$
    – Benjamin Steinberg
    Aug 27, 2013 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$
    – Kieren MacMillan
    Aug 27, 2013 at 3:15

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This is an interesting related question. Thank you for the link! $\endgroup$
    – Kieren MacMillan
    Aug 27, 2013 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$
    – Benjamin Steinberg
    Aug 27, 2013 at 13:34
  • $\begingroup$ Note Tao's post is a proof that in one variable the support always is a regular language. $\endgroup$
    – Benjamin Steinberg
    Aug 27, 2013 at 13:35

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.