Let $\sigma=(\sigma_1,...,\sigma_m)$ be i.i.d. uniform binary 0-1 valued variables. I'm trying to figure out what is the order of $E[||\sigma||_p]$ with respect to $m$.
Jensen's inequality gives an upper bound of $(m/2)^{1/p}$, but how do I get a lower bound? (I'm hoping for a lower bound of the same order.)
$\newcommand\si\sigma$ For any real $p>0$, $$m^{-1/p}\,E\|\si\|_p=E\Big(\frac1m\sum_{j=1}^m\si_j\Big)^{1/p}.$$ By the law of large numbers, $\frac1m\sum_{j=1}^m\si_j\to2^{-1}$ in probability (as $m\to\infty$). So, by Fatou's lemma, $$\liminf_{m\to\infty}m^{-1/p}\,E\|\si\|_p\ge2^{-1/p}$$ and hence $$E\|\si\|_p\ge(1-o(1))(m/2)^{1/p}.$$ Thus, the upper bound $(m/2)^{1/p}$ is asymptotically exact for large $m$.
Let us now get an asymptotically exact explicit lower bound on $E\|\si\|_p$. Since you said "Jensen's inequality gives an upper bound of $(m/2)^{1/p}$" and "$p$-norm" is mentioned in the title of your post, one should conclude that $p\ge1$ and hence $1/p\in(0,1]$ (for $p>0$).
Note that $$E\|\si\|_p=\mu_{1/p},$$ where $\mu_q:=ES^q$ and $S:=\sum_{j=1}^m\si_j$, so that $S$ has the binomial distribution with parameters $m$ and $1/2$ and hence $\mu_1=m/2$ and $\mu_2=(m/2)^2+m/4$. Note also that $\mu_q$ is log convex in $q>0$. So, for $t:=\frac{p-1}{2p-1}\in[0,1)$ we have $\mu_1\le\mu_{1/p}^{1-t}\mu_2^t$, whence $$\mu_{1/p}\ge\mu_1^{1/(1-t)}\mu_2^{-t/(1-t)} =\Big(\frac m2\Big)^{2-1/p} \Big(\Big(\frac m2\Big)^2+\frac m4\Big)^{-1+1/p} =\Big(\frac m2\Big)^{1/p}\Big(1+\frac1m\Big)^{-1+1/p}.$$ Thus, $$E\|\si\|_p\ge L_{p,m}:=\Big(\frac m2\Big)^{1/p}\Big(1+\frac1m\Big)^{-1+1/p}.$$ Clearly, $L_{p,m}\sim(m/2)^{1/p}$ (as $m\to\infty$). Thus, we have the explicit lower bound, $L_{p,m}$, on $E\|\si\|_p$ such that $$E\|\si\|_p\sim L_{p,m}.$$
