19
$\begingroup$

Given the Taylor series $\sum a_k (x - x_0)^k$ of an analytic function, it is possible to determine whether the function is periodic more-or-less directly from the coefficients $a_0, a_1, \ldots$ of the series (equivalently, the derivatives $f'(x_0), f''(x_0), \ldots$ of $f$ at $x_0$)?

(For simplicity, I'm happy to restrict if necessary to the case that the series converges on all of $\mathbb{R}$. Note too that it's no real loss of generality to take $x_0 = 0$.)

(This was motivated by this related question.)

$\endgroup$
  • $\begingroup$ Does "apply the Fourier transform and test whether it has non-zero value only at integer multiples of some frequency $\omega$" count as more-or-less-directly? $\endgroup$ – HTFB Dec 8 '14 at 10:46
  • 1
    $\begingroup$ To make it more precise, how about requiring at most finitely many evaluations of inequalities between convergent infinite sums of terms in the Taylor coefficients each determined by some (primitive recursive/decidable/something) algorithm? $\endgroup$ – HTFB Dec 8 '14 at 10:52
  • $\begingroup$ I was originally going to suggest "countably many" tests but that would allow you to use the intermediate value theorem to find an $a$ at which to test whether all the Taylor coefficients of $f(x-a)$ equalled those of $f(x)$, at least if you were allowed to choose your tests in the light of previous results. $\endgroup$ – HTFB Dec 8 '14 at 10:56
  • $\begingroup$ @HTFB Re the Fourier approach, I suppose it depends on the resulting form of the test. I would certainly be happy with a solution of the form you propose in "To make it more precise..." $\endgroup$ – Travis Willse Dec 8 '14 at 11:02
2
$\begingroup$

Just to summarise as an answer the line of thought in the comments: determining whether a function is periodic requires looking at an infinite number of its coefficients, since any finite Taylor series can be the initial segment of a periodic function, and indeed a periodic function with arbitrary period. So there is no decision algorithm for the question if the Taylor series is provided by an oracle giving one coefficient at a time.

On the other hand if you can evaluate $f(q)$ at every rational number, you can find all members of the discrete countable set of zeros of $f$ in $\mathbb{R}$; then testing whether $f(x-z) - f(x) \equiv 0$ at each such zero $z$ gives you an infinitary method relying only on the most obviously natural operations on the whole series $(a_n)$ and making a countable number, (as an ordinal, $2 \cdot \omega$) of decisions, to come to an answer.

Clearly this cannot count as "reasonably direct" because that would be a deeply uninteresting answer to an interesting question. So to make the question precise we would have to frame it in a way that lies between these two cases. What that should be, I have no idea.

$\endgroup$
1
$\begingroup$

Sorry, this should probably be a comment but my reputation is too low so I will try and turn it into an answer.

Polynomial multiplication is convolution in the Fourier domain. The linearity of the fourier transform together with that fact and that a polynomial is a linear combination of monomials gives us a good tool to attack this. Of course it turns out others have already done fast algorithms for this.

A recursive FFT algorithm for polynomials explained here http://web.cecs.pdx.edu/~maier/cs584/Lectures/lect07b-11-MG.pdf

Then for a function to be periodic all values in it's fourier transform except at position $k\omega$ for some integer $k$ should be very small in some suitable norm. We can test this by summing the norms of all the coefficients and comparing it to sums of the equally spaced subsets $k\omega$ for different integers k.

I guess this does not qualify as a very "direct" method, but it's the best I can think of. The FFT is fast and the testing for equal spacing should also be.

$\endgroup$

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.