# How to prove there exists a polynomial with degree at most $100\sqrt{nk}$ satisfying this condition

Show that for arbitrary positive integers $n,k$, there exists a polynomial $p(x)$, with degree at most $100\sqrt{nk}$, such that $$p(0)>(|p(1)+|p(2)|+\cdots+|p(n)|)+(|p(-1)|+|p(-2)|+\cdots+|p(-k)|)$$

This problem is problem A.511 from Problems in Mathematics, May 2010. See here. This problem doesn't have a solution posted.

Thank you.

-
You have unbalanced absolute value signs in title and body. Please edit. – Gerry Myerson Aug 10 '13 at 6:12
oh,Thank you @GerryMyerson – math110 Aug 10 '13 at 6:38
Is the polynomial supposed to have only real coefficients? – Potato Aug 10 '13 at 19:16
@math110, how sure are we that a solution exists? If we fix $k$ and let $n$ grow, the degree requirement becomes more and more restrictive for the desired outcome. – Jonathan Y. Aug 10 '13 at 20:07
@user142526 We are sure a solution exists because this is a math contest problem. – Potato Aug 10 '13 at 20:18

Ah, this is a cutie. I'll not pay much attention to exactly how many zeroes are in the constant $100$ (this requires just being more accurate in the estimates than I'm currently willing to), but the general idea is simple.
Step 1: Assume $k\le n$. Put $A(z)=\prod_{m=1}^k(1-\frac{x^2}{m^2})$. This way we need to care only of values $P(x)$ with $k<x\le n$. Note that $|A(x)|\le \frac{2^k x^{2k}}{k!^2}\le \left(2e\frac xk\right)^{2k}$ in this range.
Step 2: If for every $N\ge 1$, we could construct a polynomial $B(z)$ of degree about $\sqrt N$ such that $B(0)=1$ and $\max_{[1,N]}|\sqrt xB(x)|< \frac 1{2e}$, we could just put $N=\sqrt{n/k}$ and $P(z)=A(z)B(z/k)^{8k}$ or something like that (assuming $k>2$, say).
Step 3: To build $B(z)$, we shall, indeed, use a Taylor polynomial. However, we'll approximate not $F(z)=\frac{\sin z}{z}$, but $F(z)=\frac{\sin 2e{\sqrt z}}{2e\sqrt{z}}$ with the standard (positive on $(0,+\infty)$) branch of $\sqrt z$, which still makes sense and is entire because $\frac{\sin z}{z}$ has only even powers in its Taylor expansion. To estimate the error of approximation in the disk $|z|<N$, just notice that $|F|\le e^{8e\sqrt N}$ in the disk $|z|<2N$ and use the standard Cauchy coefficient bound to see that the terms with powers beyond some big multiple of $\sqrt N$ do not really matter.
Consider two extremes ($k=0$ and $k=n$) first. The second case is trivial because your degree is large enough to kill all $2n$ values. The first case calls for something like what Jonathan proposed in his comment but you've got to insert the square root somewhere. Considering an even entire function of the square root of something is an old and standard complex analysis trick. Another useful function of this kind is $\cos\sqrt{z^2-R^2}$, which is bounded by $1$ outside $[-R,R]$, has exponential type $1$, but reaches the level $e^R$ at $0$, which is almost as large as it can possibly be. – fedja Aug 14 '13 at 21:30