Entropy Lower Bound in Terms of $\ell_2$ norm Define
$$
\begin{align}
H(p_1, \dots, p_n) &= \sum_{i=1}^n p_i\log1/p_i\\
&=\log n+\sum_{i=1}^n\sum_{k=2}^\infty (-1)^{k + 1} n^{k - 1} \frac{(p_i - 1/n)^k}{k (k - 1)},
\end{align}
$$
where $p_1,\dots,p_n\ge0$ sum to $1$.
Then we have the classic inequality
$H(p_1,p_2)\ge(\log2)(1-2((p_1-1/2)^2+2(p_2-1/2)^2))=(\log 2)(1-2\|p-1/2\|^2)$, and we might wonder if that could be extended for $n>2$.
In particular with something like
$$\begin{align}
H(p_1,\dots,p_n)&\ge(\log n)(1-c_n\|p-1/n\|^2_2).
\end{align}$$
From experiments with $n=3$, it seems like
$c_n\ge\frac{2 n (\log n/2)}{(n-2) \log n}=2(1-O(1/\log n))$ suffices, but I don't have a proof of this. It is also slightly inconvenient that it can go below $0$, something that wasn't the case with the $n=2$ case.
Bounding the terms individually, we can get $H(p_1,\dots,p_n)\ge-2+4\sum_{i=1}^n\frac{p_i}{1+p_i}$, which is non-negative, but not as relatable to the $\ell_2$ norm. We can also bound $H\ge n/4-\|p-1/2\|_2^2$, but somehow bounding centered in $1/n$ seems more natural.
Is there a well known lower bound like this, relating $H(p)$ with $\|p\|_2$? Ideally, one that is asymptotically tight at $p_1=\dots=p_n=1/n$ and is always positive.
 A: Defining $p_i=1/n+q_i$ we get (using nats):
$$\begin{align}
H({\bf p}) &=-\sum p_i \log(p_i)\\
 &=-\sum (1/n +q_i) \log(1/n +q_i)\\
 &=-\sum ( 1/n +q_i) [\log(1/n ) + \log(1+ n q_i )]\\
 &= \log(n) -\sum ( 1/n +q_i) \log(1+ n q_i)\\
 &\ge \log(n) -\sum ( 1/n +q_i) n q_i\\
 & = \log(n) - n\sum q_i^2\\
 & = \log(n) - n \, \lVert{\bf p}- 1/n\rVert^2_2\\
\end{align}$$
Or, if you prefer
$$ H({\bf p}) \ge \log(n)\left(1 - \frac{n}{\log n}\sum q_i^2 \right) $$
Of course, the bound is useless if $\sum q_i^2\ge \frac{\log(n)}{n} $.
A: Let $(X,\upsilon)$ be a finite measure space. Let $\sigma=\frac{\upsilon}{V}$ be the uniform probability distribution on $X$ ($V=\upsilon(X)$). Let $\rho$ be an absolutely continuous probability distribution with density $p$. Then the inequality 
$$\begin{align}-h(p)+\ln V&\leq V\lVert p-\tfrac{1}{V}\rVert_2^2\\
h(p)&\stackrel{\mathrm{def}}{=}-\int_X p(x)\ln p(x)\mathrm{d}\upsilon_{x}\\
\lVert p-q\rVert^2_2&\stackrel{\mathrm{def}}{=}\int_X\lvert p(x)-q(x)\rvert^2\mathrm{d}\upsilon_x
\end{align}$$
is exactly the inequality between the $\chi^2$-divergence and the KL divergence
$$\begin{align}D(\rho\parallel\sigma)&\leq \chi^2(\rho\parallel\sigma)\text{,}\\
D(\rho\parallel\sigma)&\stackrel{\text{def}}{=}\int_X\left(\frac{\mathrm{d}\rho}{\mathrm{d}\sigma}\ln\frac{\mathrm{d}\rho}{\mathrm{d}\sigma}-\frac{\mathrm{d}\rho}{\mathrm{d}\sigma}+1\right)\mathrm{d}\sigma_x\\
\chi^2(\rho\parallel\sigma)&\stackrel{\text{def}}{=}\int_X\left(\frac{\mathrm{d}\rho}{\mathrm{d}\sigma}-1\right)^2\mathrm{d}\sigma_x\text{;}
\end{align}$$
this inequality in turn follows from
$$t\ln t - t + 1 \leq (t-1)^2\text{.}$$
A: To complement Leon Bloy's answer and show the bound he (and K B Dave) obtained cannot be significantly improved upon (i.e., that $c_n = \Omega\!\left(\frac{n}{\log n}\right)$ is necessary): Fix $\varepsilon \in (0,1]$, and assume without loss of generality that $n=2m$ is even. Define $\mathbf{p}^{(\varepsilon)}$ as the probability mass function (over $\{1,\dots,n\}$) such that
$$
\mathbf{p}^{(\varepsilon)}_i = \begin{cases} \frac{1+\varepsilon}{n} & \text{ if } i \leq m \\ 
\frac{1-\varepsilon}{n} & \text{ if } i > m 
\end{cases}
$$
Note that
$$\begin{align}
H(\mathbf{p}^{(\varepsilon)}) &= \sum_{i=1}^m \frac{1+\varepsilon}{n}\log \frac{n}{1+\varepsilon}
+ \sum_{i=m+1}^n \frac{1-\varepsilon}{n}\log \frac{n}{1-\varepsilon} \\
&= \log n - \frac{1}{2}\left((1+\varepsilon)\log(1+\varepsilon) + (1-\varepsilon)\log(1-\varepsilon)\right) \\
&= \log n - \frac{\varepsilon^2}{2} + o(\varepsilon^3) \tag{1}
\end{align}$$
while
$$
\lVert \mathbf{p}^{(\varepsilon)} - \mathbf{u}_n\rVert_2^2 = \frac{\varepsilon^2}{n} \tag{2}
$$
so that
$$
H(\mathbf{p}^{(\varepsilon)}) = \log n \left(1 - \left(1/2+o_\varepsilon(1)\right)\cdot\frac{n}{\log n}\lVert \mathbf{p}^{(\varepsilon)} - \mathbf{u}_n\rVert_2^2\right) \tag{3}
$$
If you want to avoid the asymptotics as $\varepsilon \to 0$, you can still fix $\varepsilon = 1$ (for instance) and get that  $$H(\mathbf{p}^{(\varepsilon)}) = \log n \left(1 - c'_\varepsilon\frac{n}{\log n}\lVert \mathbf{p}^{(\varepsilon)} - \mathbf{u}_n\rVert_2^2\right)$$ for some constant $c'_\varepsilon > 0$.
A: This is just scribbling down some observations in the comments, to have them more, well, visible.

As observed by K B Dave, the inequality of leonbloy is an instance of $\mathrm{KL} \le \chi^2.$ This can thus be improved by using a tighter inequality of this form. Note that the resulting inequality was mentioned by Clement in the original comments.
We have $$\mathrm{KL}(P\|Q) = \int \log \frac{\mathrm{d}P}{\mathrm{d}Q} \,\mathrm{d}P \le \log \int \left( \frac{\mathrm{d}P}{\mathrm{d}Q}\right) \,\mathrm{d}P = \log \int \left( \frac{\mathrm{d}P}{\mathrm{d}Q}\right)^2 \,\mathrm{d}Q = \log (1 + \chi^2(P\|Q)), $$ where the inequality follows by the concavity of $\log$ and Jensen's inequality. Applying the above to this case yields $$H(P) = \log n - \mathrm{KL}(P\|\mathbf{1}/n) \ge \log n - \log(1 + \sum_x  \frac{(P_x - 1/n)^2}{1/n}) = \log n - \log (1 +  n\|P - \mathbf{1}/n\|_2^2).$$
Note that if $n\|P - \mathbf{1}/n\|_2^2 \ll 1,$ we may use $\log (1 + x) \approx x$ for small values of $x$ to recover the original bound.
We may also state the above bound in the following equivalent way: Observe that $1 + \chi^2(P\|Q) = \mathbb{E}_Q[ ({\mathrm{d}P}/{\mathrm{d}Q})^2].$ Again plugging in $Q$ uniform on $n$ letters yields that the latter expectation is simply $n\|P\|_2^2,$ and we get that 
$$ H(P) \ge - \log \|P\|_2^2,$$ the form stated by Clement. Note that $\|P\|_2 \le 1$ for every distribution, so the form above makes it obvious that the inequalities are non-trivial (in that the RHS is $\ge$ 0) for every $P$.
