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$
4
  • $\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, 2014 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, 2014 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, 2014 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, 2014 at 11:02

2 Answers 2

Reset to default
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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .