Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer
Very nice. How did you think of this solution? – Potato Aug 14 '13 at 18:54
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
It's very nice nice! Thank you +1 – math110 Aug 15 '13 at 0:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.