# Bounding $\sum \exp(x_1\pm \cdots\pm x_n)^2$ in terms of $x_1^2+\cdots +x_n^2$.

Suppose that $x_1,\ldots,x_n$ are positive real numbers such that $$x_1^2+\cdots +x_n^2 < \epsilon.$$ Can we bound the quantity $$2^{-n}\sum_{b_1,\ldots,b_n\in\{\pm1\}}e^{\left(\sum_i b_ix_i\right)^2}?$$ `Bound' means the following: For all sufficiently small $\epsilon$, find a constant $C_{\epsilon}$ such that $$2^{-n}\sum_{b_1,\ldots,b_n\in\{\pm1\}}e^{\left(\sum_i b_ix_i\right)^2}\leq C_{\epsilon}.$$

Partial results: When $n=2$ and $\epsilon=1/2$, I can prove the following inequality: $$\frac{e^{(x+y)^2}+e^{(x-y)^2}}{2}\leq \left(1-2\epsilon\right)^{-1/2}.$$ I believe an inequality of the following form should hold: $$\frac{\sum_{\pm}e^{(x_1\pm x_2\pm \cdots x_n)^2}}{2^n}\leq e^{\sum_i x_i^2},$$ although I've run into some issues proving such a bound.

• If $n=3$ and $x_1=x_2=x_3 = x$ then the quantity becomes $\frac{1}{8} (6e^{x^2} + 2 e^{9x^2}) > e^{x^2}$ so your guess for the best upper bound is not correct. If you just want one upper bound then good old Cauchy-Schwarz gives $e^{n\sum x_i^2}$. – Winther May 10 '15 at 21:30

Notice that each term in the sum is bounded by

$$e^{(\sum_{i}x_i)^2} = e^{\sum_{i} x_i^2 + \sum_{i \neq j} x_i x_j} \leq e^{\epsilon + \sum_{i \neq j} x_i x_j}$$ Then observe that the vector formed by the $x_i$ lies inside a ball of radius $\epsilon$, so each $x_i < \sqrt{\epsilon}$ and we can bound the sum

$$\sum_{i \neq j} x_i x_j < \sum_{i \neq j} \epsilon =n(n-1)\epsilon$$ hence the sum above is bounded by

$$e^{(\sum_{i}x_i)^2} < e^{\epsilon(1 + n(n-1))}$$

• I should say Winther's bound is stronger as it is linear un $n$ on the exponential, I guess it is about as good as it gets. – Rogelio Molina May 10 '15 at 21:59
• I think you can do better, because most of the mass is concentrated on the largest term $2^{-n}e^{\left(\sum_i |x_i|\right)^2}\leq 2^{-n}e^{n\epsilon}\leq 1$, for $\epsilon \leq \log 2$. – pre-kidney May 11 '15 at 4:59
• Indeed, I think this was Winther's remark. Cauchy Schwarz for the vectors $b=(b_1,\cdots,b_n)$ and $x$ gives $(b \cdot x)^2 \leq b^2 x^2 = n x^2 \leq n \epsilon$ and so $e^{(\sum_i b_i x_i)^2 } \leq e^{ n \epsilon }$ – Rogelio Molina May 11 '15 at 6:34
• That's not what I meant: the Cauchy Schwarz bound still blows up as $n\to\infty$. I am claiming that there should be a bound that is independent of $n$. The idea is that only a tiny fraction of the summands will contribute, and the rest will be negligible (whereas Cauchy weights all terms equally). – pre-kidney May 11 '15 at 22:48
• I see. I had misunderstood your statement. So you want a bound independent of $n$ on your original sum? – Rogelio Molina May 11 '15 at 23:58