Suppose one has a generating function $$F(z) = \sum_{k\ge 0} f(k) z^k$$ for some $f:\mathbb{Z}\rightarrow \mathbb{Z}$. Is there a way to express an iteration of $f$ in terms of $F(z)$. E.g., $$G(z) = \sum_{k\ge 0} f(f(k)) z^k$$ Can $G(z)$ be expressed in terms of $F(z)$?
1
-
1$\begingroup$ Note that there can be many functions $f(k)$ that give rise to the same $f(f(k))$, so the answer is "probably not". $\endgroup$– Greg MartinCommented Jun 13, 2022 at 0:12
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
8
That seems really unlikely.
For example, $$F(z)=\sum_{k=0}^\infty 2^kz^k = \frac{1}{1-2z}$$ is a rational function, but $$G(z)=\sum_{k=0}^\infty 2^{2^k}z^k$$ has radius of convergence $0$.
answered Jun 12, 2022 at 0:31
-
1$\begingroup$ @Gupta "What does convergence have to do with formal power series?" Probably the most important reason for using generating functions is that a generating function turns an algebraic list of quantities into a function, which can be studied using the additional techniques of analysis. Recursion relations for coefficients become differential equations for the generating function, etc. $\endgroup$– BuzzCommented Jun 12, 2022 at 1:57
-
4$\begingroup$ Gupta, you're being pretty aggressive to someone who is just trying to help you answer your question. Gerald's answer looks very reasonable to me: often what's most useful about power series is moving between formal and analytic perspectives. In a literal sense, the answer to your question "can G(z) be expressed in terms of F(z)" is yes because the coefficients determine the power series and you defined the coefficients of G in terms of those of F. So ultimately you have to be willing to accept soft/subjective answers like Gerald's. $\endgroup$ Commented Jun 12, 2022 at 17:53
-
1$\begingroup$ @SamHopkins Is saying an answer is wrong being aggressive? Am I suppose to pretend it is right? He is claiming that a power series that has a radius of convergence of 0 means somehow it can't have some algebraic relationships(He doesn't explicitly state why fails but the implication is that "it almost surely cannot work in any way"). But again, this is wrong because convergence doesn't mean anything in formal series. It's a non-sequitur. Sorry if pointing it out sounds aggressive but the truth doesn't need and shouldn't have a sugar coating so it is more palatable. $\endgroup$– GuptaCommented Jun 12, 2022 at 17:59
-
3$\begingroup$ I think this question is fine but Gerald's answer is also very reasonable. I'm leaving it at that because the way you're responding is unpleasant. $\endgroup$ Commented Jun 12, 2022 at 18:04
-
6$\begingroup$ @Gupta If a power series $F$ has positive convergence radius then also any power series that can be reasonably expressed in terms of $F$ (for example as a rational function of $F$ and its derivatives and integrals and arbitrary compositions of those when they make sense) also will a positive radius of convergence. So if $G$ as zero radius of convergence, then is cannot be reasonably expressed in terms of $F$. And Gerald's example isn't just an isolated counter-example: this behaviour happens whenever $f(n)$ grows exponentially with $n$, so includes many interesting sequences. $\endgroup$– MarcCommented Jun 12, 2022 at 21:09
$\begingroup$
$\endgroup$
6
You could explore this conjecture by the following method: Suppose $f(f(k))= h(f(k))$ for different specified $h$, then look for $G(z) = H(F(z))$. So eg. $h(k) = a k + b$ gives $G(z) = a F(z) +\frac{b}{1-z}.$ Then you need to solve the functional equation $f(f(k)) = h(f(k))$, and this will give you some sets of pairs $(h, H)$ which might inform your conjecture
The example that you give in the comments on the other question is $(h,H)=(1,1)$, but this case is very simple, I don't know that I would take it to be the basis for a conjecture.
-
$\begingroup$ In general recursion of $f$ is not going to turn out to be recursion in $F$. I tried that initially and it doesn't work(although there seems to be some relationship going on. That is, regardless what your $h$ is unlikely to translate in to composition on the generating functions(clearly for the identity it works). I'd imagine whatever $G(z,F)$ it is more complex maybe involving convolutions, products, etc. $\endgroup$– GuptaCommented Jun 12, 2022 at 15:25
-
1$\begingroup$ @Gupta yes I would expect you to need $G(z) = H(z, F(z), F'(z), \int dz F(z),...)$ more generally, but if you can find some examples with $G(z) = H(z, F(z))$ it would add weight to your conjecture. Currently I'm not convinced it can be extended past the example you gave $\endgroup$– JojoCommented Jun 12, 2022 at 16:50
-
$\begingroup$ Well, clearly it can be extended past the id to any linear function as you have pointed out since they have a simple closed form of the iteration(and which is linear). $f(k) = ak+b$, $f(f(k)) = a(ak+b)+b = a^2k + ab + b = a'k + b'$ Hence $G(z) = aF(z) + \frac{b}{1-z}$. This suggests it is not impossible to find such a relationship(and it may be that there is a general relationship but simply requires a much more advanced expression of $F(z)$. Remember, I'm asking if anyone knows of an answer. Not "how likely" something is. $\endgroup$– GuptaCommented Jun 12, 2022 at 18:12
-
$\begingroup$ @Gupta Oh yes OK, I see that you have $f = a k +b, h = a^2 k + a b + b, H = a^2 F +\frac{a b + b}{1-z}$. In that case, I think this is a complex and interesting problem, and that you may be able to make some headway towards a more general rule using the method I described $\endgroup$– JojoCommented Jun 12, 2022 at 18:35
-
1$\begingroup$ @Gupta I don't quite follow your argument about the polynomial and $\int dz F/z$, but I think if you made it clearer and put it in the question it might help you get a better answer. (Also I realised that my previous comment is wrong, but what you has was correct) $\endgroup$– JojoCommented Jun 12, 2022 at 20:16