# max of an exponential sum

1. What is the max of $$\sum\limits_{i=1}^n e^{x_i}$$ as $$(x_1,...,x_n)$$ ranges over a sphere of given radius in $$R^n$$ ? Lagrange multipliers yields $$n$$ different candidates. Which of them is the max ?
2. Analogous question for $$\sum 2^{x_i}$$ with $$x_i$$ INTEGERS in a given integral ball $$\sum x_i^2\leq A$$.

More on #1: There are $$n$$ (or fewer if the radius $$R$$ is small) candidate solutions $$(x_1,...,x_n)$$, all of the form (a,..,a,b,...,b) where $$0 and $$e^a/a=e^b/b$$. For each of those, you have a bordered Hessian, as in the comment below: [ M=$$\begin{matrix}0&-2x_1&...&-2x_n\\ -2x_1&2\lambda(x_1-1)&0...&0\\ \vdots&\vdots&\vdots&\vdots\\ -2x_n&0&...&2\lambda(x_n-1)\end{matrix}$$] For a max, this needs to be positive-definite, i.e. have all eigenvalues positive. Then, among all candidates yielding a positive-definite bordered hessian (if more than one), you need to maximize $$\sum e^{x_i}$$. So what's the answer ? My hunch is that (for large $$n, R$$) the max occurs for a vector of the form $$(a,...,a,b)$$ (SINGLE $$b$$): because for this the value is roughly $$e^R$$; for the opposite extreme, with all $$x_i$$ equal, the value is $$ne^{R/\sqrt{n}}$$ which is much smaller.

• Hi user677727, welcome to MSE! What have you tried? This is not a forum where people just do your HW for you. Please see math.meta.stackexchange.com/questions/9959/… Jul 1, 2019 at 19:05
• My interest is in question 2 which is motivated by a research problem in Algebraic Geometry. Question 1 is supposed to be an intermediate step and would yield an upper bound. As I said Lagrange multipliers yields a list of n candidates and the problem is which one yields the max. It looks simple but even though I asked several analysts (I'm not one), nobody could answer. This is not- to my knowledge- any homework problem. Jul 2, 2019 at 20:10
• Thanks for clarification. Perhaps a tag of 'analysis' will help it find the right audience? I'm also more of an algebraic/arithmetic geometer, and I think I'll have to pass on this one Jul 2, 2019 at 21:48
• Can you show your work on these $n$ different candidates/at least write what they are?
– J.G
Jul 3, 2019 at 22:42
• These are, up to permutation $(a,...,a, b,...,b)$ where $0<a<1<b$ and $e^a/a=e^b/b$. This is direct from Lagrange multipliers. Jul 4, 2019 at 23:08

The answer to the first question depends on the radius $$R$$.

Let's demonstrate this with two variables. Let $$F = e^x + e^y + \lambda (R^2- x^2 - y^2)$$.

Since the extremum occurs at $$\frac{e^x}{x} = \frac{e^y}{y}$$, we need to inspect the function $$\frac{e^x}{x}$$ which is convex and has a minimum at $$x=1$$. Hence the equation $$\frac{e^x}{x} = \frac{e^y}{y}$$ can only have different solutions $$x \ne y$$ if $$x <1$$ and $$y > 1$$ (or permuted).

We have to discuss cases:

Using the bordered Hessian condition for constrained maximization we have to show that for $$x \ne y$$ to be a maximum,

$$\det \begin{bmatrix} 0 & \dfrac{\partial (R^2- x^2 - y^2)}{\partial x} & \dfrac{\partial (R^2- x^2 - y^2)}{\partial y} \\[2.2ex] \dfrac{\partial (R^2- x^2 - y^2)}{\partial x} & \dfrac{\partial^2 F}{\partial x^2}& \dfrac{\partial^2 F}{\partial x y} \\[2.2ex] \dfrac{\partial (R^2- x^2 - y^2)}{\partial y} & \dfrac{\partial^2 F}{\partial x y} & \dfrac{\partial^2 F}{\partial y^2} \end{bmatrix} > 0$$
which is $$x^2(y-1) + y^2(x-1) > 0$$.

Let $$y = ax$$ then this is $$(ax-1) + a^2(x-1) > 0$$ or $$x >\frac{1+a^2}{a^2+a}$$ and we must have for a maximum:

$$R^2 = x^2 + y^2 = x^2(1+a^2) > \frac{(1+a^2)^3}{(a^2+a)^2} = g(a)$$

Now $$g(a)$$ has a minimum at $$g(a=1) = 2$$. Hence only for $$R^2 > 2$$ will there be a maximum with $$x \ne y$$, whereas the case $$x=y$$ will constitute a minimum.

Conversely, for $$R^2 < 2$$, there will be only the one extremum for $$x=y$$ which will be a maximum.

For more than two variables, this discussion will extend to more intervals of $$R$$.

EDIT 2019-07-25:

Now let's solve the general case. As stated in bordered Hessian condition for constrained maximization, conditions for a maximum are obtained from the leading principal minors (determinants of upper-left-justified sub-matrices) of the bordered Hessian, for which the first 2 leading principal minors are neglected, the smallest minor consisting of the truncated first 3 rows and columns, the next consisting of the truncated first 4 rows and columns, and so on, with the last being the entire bordered Hessian. A sufficient condition for a local maximum is that these minors alternate in sign with the smallest one having positive sign.

Evaluating these minors gives for any $$n$$ (!), when expanding by the last column

$$\det M_n \\ = \det \begin{bmatrix}0&-2x_1&...&-2x_n\\ -2x_1&2\lambda(x_1-1)&0...&0\\ \vdots&\vdots&\vdots&\vdots\\ -2x_n&0&...&2\lambda(x_n-1)\end{bmatrix}\\ = 2\lambda(x_n-1) \det M_{n-1} \\ - 2x_n (-1)^{n+1} \det \begin{bmatrix} -2x_1&2\lambda(x_1-1)&0...&0&0\\ \vdots&\vdots&\vdots&\vdots&0\\ -2x_{n-1}&0&...&0&2\lambda(x_{n-1}-1)\\ -2x_n&0&...&0&0\end{bmatrix}$$ Now the last determinant can be evaluated by expanding by the last row. Since the last row has just one entry $$2x_n$$, the first column and last row can be eliminated and what remains is the product of remaining diagonals. Hence:

$$\det M_n = 2\lambda(x_n-1) \det M_{n-1} + (2x_n)^2 \prod_{i=1}^{n-1}(2\lambda(x_i-1))$$

Solving this recursion gives $$\det M_n = \prod_{i=1}^{n}(2\lambda(x_i-1)) \, \cdot \, \sum_{i=1}^{n} \frac{(2x_i)^2}{2\lambda(x_i-1)}$$

It is already known that candidate solutions $$(x_1,...,x_n)$$ are all of the form (a,..,a,b,...,b) where $$0 and $$e^a/a=e^b/b$$. Note that the convention $$a >1$$ has been adopted! Suppose there are $$k$$ many $$a$$'s and $$n-k$$ many $$b$$'s. Since the task is symmetric, we can assume that the $$k$$ many $$a$$'s are the first variables.

Then we have for the $$n$$th principal minor:

$$\det M_n = 2^{n+1} (\lambda)^{n-1} (a-1)^k (b-1)^{n-k} \Big( k \frac{a^2}{(a-1)} + (n-k) \frac{b^2}{(b-1)} \Big)$$

Reducing the order of the minors accounts for removing $$b$$'s. The $$k$$th principal minor is

$$\det M_k = 2^{k+1} (\lambda)^{k-1} (a-1)^k \Big( k \frac{a^2}{(a-1)} \Big) = 2^{k+1} (\lambda)^{k-1} (a-1)^{k-1} k a^2$$

Now, as we go further to the $$(k-1)$$th principal minor, we observe that $${\rm sign} \det M_k ={\rm sign} \det M_{k-1}$$, as $$\lambda >0$$ and $$a >1$$. This is a contradiction to the condition that, for a maximum, the minors must alternate in sign.

So, for a maximum, this situation mustn't occur. The way to achieve is is to make $$k=1$$. As the two-dimensional discussion above shows, this is only possible if the radius is large enough. Let us suppose this is the case. The large radius assures that the term $$\Big( k \frac{a^2}{(a-1)} + (n-k) \frac{b^2}{(b-1)} \Big)$$ will not change in sign if $$n$$ changes.

Then indeed, as $$b-1 < 0$$, the minors will alternate in sign, as for a change from the $$q$$th minor to the $$(q+1)$$th minor, always one additional product term $$(b-1)$$ is multiplied. This completes the proof. $$\qquad \Box$$

So, as the OP already hypothesized, indeed the maximum occurs for a vector of $$x_i$$ where $$n-1$$ entries are of the smaller value $$<1$$, solving $$e^a/a=e^b/b$$.

• Thank you for pointing out the bordered Hessian condition which nicely settles the $n=2$ case and seems relevant more generally. But for large $n$- my case of interest- I don't see that the problem is solved. See below. Jul 23, 2019 at 22:16
• @user677727 I now added a proof for the general case, which shows that the hypothesis you set up in the question is indeed true. Jul 25, 2019 at 18:02
• Beautiful solution. Thank you very much Andreas. Jul 27, 2019 at 22:18
• Thanks to Andreas, Problem 1 may be considered solved. This suggests but, think, doesn't prove, that the max for problem 2 for large $A$ is attained at $([\sqrt{A}], 0,...,0)$. Jul 29, 2019 at 16:44