Welcome to our community

Be a part of something great, join today!

Problem of the Week # 267 - Jun 12, 2017

Status
Not open for further replies.
  • Thread starter
  • Admin
  • #1

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,198
Here is this week's POTW:

-----

Let $\displaystyle f(t)=\sum_{j=1}^N a_j \sin(2\pi jt)$, where each $a_j$ is real and $a_N$ is not equal to 0. Let $N_k$ denote the number of zeroes (including multiplicities) of $\dfrac{d^k f}{dt^k}$. Prove that
\[N_0\leq N_1\leq N_2\leq \cdots \mbox{ and } \lim_{k\to\infty} N_k = 2N.\]
[Editorial clarification: only zeroes in $[0, 1)$ should be counted.]

-----

Remember to read the POTW submission guidelines to find out how to submit your answers!
 
  • Thread starter
  • Admin
  • #2

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,198
Re: Problem Of The Week # 267 - Jun 12, 2017

This was Problem B-3 in the 2000 William Lowell Putnam Mathematical Competition.

No one answered this week's POTW. The solution, attributed to Kiran Kedlaya and his associates, follows:

Let $f_k(t) = \frac{df^k}{dt^k}$. Recall Rolle's theorem: if $f(t)$ is differentiable, then between any two zeroes of $f(t)$ there exists a zero of $f'(t)$. This also applies when the zeroes are not all distinct: if $f$ has a zero of multiplicity $m$ at $t=x$, then $f'$ has a zero of multiplicity at least $m-1$ there.

Therefore, if $0 \leq a_0 \leq a_1 \leq \cdots \leq a_r < 1$ are the roots of $f_k$ in $[0,1)$, then $f_{k+1}$ has a root in each of the intervals $(a_0, a_1), (a_1, a_2), \dots, (a_{r-1}, a_r)$, so long as we adopt the convention that the empty interval $(t,t)$ actually contains the point $t$ itself. There is also a root in the "wraparound" interval $(a_r, a_0)$. Thus $N_{k+1} \geq N_k$.

Next, note that if we set $z = e^{2\pi i t}$; then
\[
f_{4k}(t) = \frac{1}{2i} \sum_{j=1}^N j^{4k} a_j (z^j - z^{-j})
\]
is equal to $z^{-N}$ times a polynomial of degree $2N$. Hence as a function of $z$, it has at most $2N$ roots; therefore $f_k(t)$ has at most $2N$ roots in $[0,1]$. That is, $N_k \leq 2N$ for all $N$.

To establish that $N_k \to 2N$, we make precise the observation that
\[
f_k(t) = \sum_{j=1}^N j^{4k} a_j \sin(2\pi j t)
\]
is dominated by the term with $j=N$. At the points $t = (2i+1)/(2N)$ for $i=0,1, \dots, N-1$, we have $N^{4k} a_N \sin (2\pi N t) = \pm N^{4k} a_N$. If $k$ is chosen large enough so that
\[
|a_N| N^{4k} > |a_1| 1^{4k} + \cdots + |a_{N-1}| (N-1)^{4k},
\]
then $f_k((2i+1)/2N)$ has the same sign as $a_N \sin (2\pi N at)$, which is to say, the sequence $f_k(1/2N), f_k(3/2N), \dots$ alternates in sign. Thus between these points (again including the "wraparound" interval) we find $2N$ sign changes of $f_k$. Therefore $\lim_{k \to \infty} N_k = 2N$.
 
Status
Not open for further replies.