If $p\in\Bbb Z[X]$ show that: $\max\limits_{x\in [0,1]}\left|p(x) \right| > \frac{1}{e^{n}}.$

This is problem 10 from the International Mathematical Competition for University Students of 2015, from day 2, in Bulgaria. I think it is an interesting problem!

Let $n$ be a positive integer, and $p(x)$ be a polynomial of degree $n$ with integer coefficients. Prove that $$\max_{x\in [0,1]}\left|p(x) \right| > \frac{1}{e^{n}}.$$

Proposed by Géza Kós, Eötvös University, Budapest.

• Here is a solution found on Math Links: artofproblemsolving.com/community/c7h1122156_imc2015_problem_10
– user235708
Jul 31, 2015 at 20:29
• See participants' scores here. No one got more than 4 out of 10 for this problem... Oct 30, 2017 at 12:29

Let $M = \max_{x\in [0,1]}\left|p(x) \right|$ we know that

$$M = \max_{x\in [0,1]}\left|p(x)\right| =\lim_{j\to \infty}\left(\int_0^1 \left|p(x)\right|^j dx\right)^{\frac{1}{j}}=\lim_{j\to \infty}\left(\int_0^1 \left|p(x)\right|^{2j} dx\right)^{\frac{1}{2j}}$$

We then consider $$M_{j} =\int_0^1 \left|p(x)\right|^{2j} dx$$

since $\deg p= n$ then it follows that , $\deg p^{2j}= 2jn$. so, If we Can write it as, $$p^{2j}(x) = \sum_{k=0}^{2jn} a_{j,k}x^k$$

Therefore, $$M_{j} =\int_0^1 \left|p(x)\right|^{2j} dx \ge\left|\int_0^1 p(x)^{2j} dx \right| = \left|\sum_{k=0}^{2jn} \frac{a_{j,k}}{i+1}\right|$$ Let $\color{blue}{\operatorname{lcm}(1,2,3,\cdots, 2jn+1)}$ be the least common factor of $(1,2,3,\cdots, 2jn)$. Then since $a_{k,i}\in \Bbb Z$ we have,

$$M_{j}\ge \left|\sum_{k=0}^{2jn} \frac{a_{j,k}}{i+1}\right|\ge \frac{1}{lcm(1,2,3,\cdots, 2jn+1)}$$ We get from this that, $$\color{red}{\log (\color{blue}{\operatorname{lcm}(1,2,3,\cdots, 2jn+1)})\sim 2jn+1}$$

hence for $\varepsilon>0$ and for $j$ large enough we have,

$$\color{blue}{\operatorname{lcm}(1,2,3,\cdots, 2jn+1)}\le \exp((1+\varepsilon)(2jn+1) )$$ which implies that

$$\left(\int_0^1 \left|p(x)\right|^{2j} dx\right)^{\frac{1}{2j}} = M_j^{1/2j} \ge \left(\frac{1}{\color{blue}{\operatorname{lcm}(1,2,3,\cdots, 2jn+1)}}\right)^{\frac{1}{2j}} \ge \frac{1}{\exp((1+\varepsilon)(n+\frac{1}{2j}) ) }$$

Taking $j\to \infty$ we get

$$M = \max_{x\in [0,1]}\left|p(x)\right| = \lim_{j\to \infty}\left(\int_0^1 \left|p(x)\right|^{2j} dx\right)^{\frac{1}{2j}} \ge \frac{1}{\exp((1+\varepsilon)n ) }~~~\forall ~~\varepsilon>0$$

That is $$\color{blue}{M = \max_{x\in [0,1]}\left|p(x)\right| \ge \frac{1}{e^n }}$$

• Why ? How can that be possible I don't see . please clarify Oct 30, 2017 at 15:53
• You need a $\geqslant$ rather than a $=$ there at the end. $M = f(\varepsilon)$ for all $\varepsilon > 0$ doesn't make sense unless $f$ is constant. Besides, it's the limit as $j \to \infty$, not $n$. Oct 30, 2017 at 16:01
• ::))) I see it is just typo your right. I taught It is a huge mistake Oct 30, 2017 at 17:10
• @GuyFsone Very interesting solution! Is it possible to prove $lcm(1,\ldots,2jn) \leq \exp((1+\varepsilon)2nj)$ without appealing to the prime number theorem? Oct 30, 2017 at 17:48
• Honestly I am not an expert in number theory but I just find that in mathoverflow. It could be nice question in math stark exchange. that was gift. but here we have this result in more general set up: math.stackexchange.com/questions/2496226/…. I hope it will be reopen. I just updated it. Oct 30, 2017 at 18:09

I have to remark that the given inequality is fairly simple to prove if we replace $e$ with $4$.
Since the shifted Legendre polynomials provide an orthogonal base of $L^2(0,1)$ with respect to the standard inner product, we have $$\min_{\deg q<n}\int_{0}^{1}\left(x^n+q(x)\right)^2\,dx = \frac{1}{(2n+1)\binom{2n}{n}^2}$$ hence $p(x)\in\mathbb{Z}[x]$ and $\deg p=n$ imply $$\max_{x\in[0,1]}\left| p(x) \right| \geq \frac{1}{\binom{2n}{n}\sqrt{2n+1}} >\frac{1}{4^n}.$$

• Am I missing something, or does your inequality on $\max_{x\in[0,1]}\left| p(x) \right|$ hold only when $p$ is monic of degree $n$ ? Not for all $p$. Nov 4, 2017 at 17:35
• @EwanDelanoy: if $p$ is not monic, then $\max|p(x)|$ is bounded below by $\frac{C}{4^n}$ where $C$ is the absolute value of the leading (integer) coefficient. Nov 4, 2017 at 18:03
• Ah yes, and $|C| \geq 1$ because $C$ is an integer. I see Nov 4, 2017 at 18:33

Not a full answer, but adding to Colm's answer, we begin by noting that if the condition is being violated for any polynomial P(x), P(0) must be zero as must be P(1).

This is because both P(0) and P(1) are necessarily integral and will always exceed e^(-n) where n is as defined.

Hence, such a polynomial will always be expressible as x(x-1)g(x). By induction, we see that if |g(x)| reaches its maxima in a range lying in [1/2-k,1/2+k] such that the value of k allows x(x-1) to exceed e^(-2) in absolute value, we will have our contradiction and the solution.

Not a full answer Just a (fairly obvious) idea for tackling this.

The case for $n = 1$ is just short of trivial. Let the polynomial be $ax + b$. Then if $|b| > \frac{1}{e}$, we can choose $x = 0$ and we're done. Else $|b| \leq \frac{1}{e}$. So choosing $x = 1$ we get $|ax + b| = |a + b| > 1 - \frac{1}{e} > \frac{1}{e}$. The last inequality chain holds because $a$ must be an integer.

Idea from here: Induction on $n$. The inductive hypothesis gives us two results:

• The "sub-polynomial" of degree $n - 1$ reaches a value greater than $\frac{1}{e^{n - 1}}$ at some stage
• The derivative, which is of degree $n - 1$ reaches a value greater than $\frac{1}{e^{n - 1}}$ at some stage.

Maybe also the Taylor series expansion for $e^{-nx}$ would be useful here, because then we're comparing polynomials with polynomials.