Given positive integer $n$, find the largest real number $\lambda=\lambda(n)$, such that for any degree $n$ polynomial with complex coefficients $f(x)=a_n x^n+a_{n-1} x^{n-1}+\cdots+a_0$, and any permutation $x_0,x_1,\cdots,x_n$ of $0,1,\cdots,n$, the following inequality holds $\sum_{k=0}^n|f(x_k)-f(x_{k+1})|\geq \lambda |a_n|$, where $x_{n+1}=x_0$.
Problem
Source:
Tags: algebra, polynomial, inequalities, floor function, triangle inequality, inequalities unsolved
11.09.2010 18:20
agzqu wrote: Given positive integer $n$, find the largest real number $\lambda=\lambda(n)$, such that for any degree $n$ polynomial with complex coefficients $f(x)=a_n x^n+a_{n-1} x^{n-1}+\cdots+a_0$, and any permutation $x_0,x_1,\cdots,x_n$ of $0,1,\cdots,n$, the following inequality holds $\sum_{k=0}^n|f(x_k)-f(x_{k+1})|\geq \lambda |a_n|$, where $x_{n+1}=x_0$. Is this the correct answer? For $n=2k,\quad\ \ \ \lambda=2k!^2$ For $n=2k+1,\ \lambda=2k!(k+1)!$
04.08.2012 08:43
I think the answer is $\lambda(n) = \frac{n!}{2^{n-2}}$. Let $f(k)=t_k$ for $k=0,1,\ldots,n$ so matching leading coefficients from Lagrange interpolation (note that $\deg{f}<n+1$) we have \[f(x)=\sum_{k=0}^{n}t_k\prod_{j\ne k}\frac{x-j}{k-j}\implies a_n=\sum_{k=0}^{n}\frac{t_k(-1)^{n-k}}{k!(n-k)!}.\](Clearly $\deg{f}=n$ iff $a_n\ne 0$.) This gives us our equality case easily: letting $t_k=(-1)^k$ and \[(x_0,\ldots,x_n) = (0,2,\ldots,2\lfloor{n/2}\rfloor,1,3,\ldots,2\lfloor{(n-1)/2}\rfloor+1),\]we have \[\frac{\sum_{k=0}^{n}|f(x_k)-f(x_{k+1})|}{|a_n|}=\frac{\sum_{k=0}^{n}|t_{x_k}-t_{x_{k+1}}|}{|\sum_{k=0}^{n}\frac{t_k(-1)^{n-k}}{k!(n-k)!}|}=\frac{2|1-(-1)|n!}{2^n}=\frac{n!}{2^{n-2}},\]where we note that $a_n=\pm 2^n\ne 0$. So it remains to show that \[\sum_{k=0}^{n}2^{n-2}|t_{x_k}-t_{x_{k+1}}|\ge \left| \sum_{k=0}^{n}t_k(-1)^k\binom{n}{k} \right|\]always holds. By the triangle inequality, it suffices to show that there exist reals $\alpha_0,\ldots,\alpha_n$ such that $|\alpha_k|\le 2^{n-2}$ and $\alpha_k-\alpha_{k-1}=(-1)^{x_k}\binom{n}{x_k}$ for all $k$. Indeed, we would then have \[\sum_{k=0}^{n}t_{x_k}(-1)^{x_k}\binom{n}{x_k} = \sum_{k=0}^{n}t_{x_k}(\alpha_k-\alpha_{k-1}) = \sum_{k=0}^{n}\alpha_k(t_{x_k}-t_{x_{k+1}}).\]But this is easy: let $m=\min_{0\le k\le n}\sum_{i=1}^{k}(-1)^{x_i}\binom{n}{x_i}$ and $M=\max_{0\le k\le n}\sum_{i=1}^{k}(-1)^{x_i}\binom{n}{x_i}$, and observe that $0\le M-m\le 2^{n-1}$. So taking \[\alpha_k=\frac{-m-M}{2}+\sum_{i=1}^{k}(-1)^{x_i}\binom{n}{x_i}\]for all $k$, we get $\alpha_k-\alpha_{k-1}=(-1)^{x_k}\binom{n}{x_k}$ and \[-2^{n-2}\le\frac{m-M}{2}\le \frac{-m-M}{2}+m\le \alpha_k \le \frac{-m-M}{2}+M = \frac{M-m}{2}\le 2^{n-2},\]as desired.