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.

  • $\begingroup$ 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}$. $\endgroup$ – 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))} $$

  • $\begingroup$ 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. $\endgroup$ – Rogelio Molina May 10 '15 at 21:59
  • $\begingroup$ 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$. $\endgroup$ – pre-kidney May 11 '15 at 4:59
  • $\begingroup$ 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 }$ $\endgroup$ – Rogelio Molina May 11 '15 at 6:34
  • $\begingroup$ 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). $\endgroup$ – pre-kidney May 11 '15 at 22:48
  • $\begingroup$ I see. I had misunderstood your statement. So you want a bound independent of $n$ on your original sum? $\endgroup$ – Rogelio Molina May 11 '15 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.