Maximal Products of a Given Sum

maximal_productBack in high school, I came across the following contest problem:

Question: Let S be a set of positive integers totaling 20.  What is the maximum value of

\displaystyle\prod_{x \in S} x

It’s a fun problem, so don’t rush past the spoiler tags too fast.  When you’re ready, I’ll spoil the solution to the question above, and discuss a “continuous” version of the question above.  Namely, what happens when S is allowed to include positive real numbers?

As promised, here’s one solution to the question posed before the break:

Solution: Suppose that S is a set of positive integers totaling 20.  If for somex \in S we have x > 4, then we increase our product over terms in S by replacing x by the two elements 2 and x-2.  We may therefore conclude thatx \in S is at most 4.  In fact, we may assume without loss of generality thatx \in S is at most 3, since any occurrence of 4 may just as easily be the pair {2,2}.

From the other direction, we may assume that x > 1 for all x \in S, since

1\cdot x_1 \cdots x_k < (x_1 +1)\cdot x_3 \cdots x_k.

In other words, the set S that maximizes our product consists (without loss of generality) of just 2’s and 3’s.  Moreover, the inequality

2 \cdot 2 \cdot 2 < 3 \cdot 3

tells us that 2 occurs in our maximal product at most twice.  The set S is then determined uniquely, as


For this set, our product is 1458, and this product is maximal. \square

Older readers may recognize this solution from an earlier post, where it was used to produce a crude upper bound on the maximal orders of elements in the permutation group S_n.  We won’t be heading back down that path today.  Rather, let’s turn to the following, continuous analogue of our earlier question:

Question: Let S be a set of positive real numbers totaling n > 1.  What is the maximal product of the set S, as S varies?

If we want to follow the discrete case, we quickly prove that in a maximal set we may assume that x \in S implies

x \in (1,4).

However, unlike in the discrete case, this leaves a spectrum of possibilities.  Is it obvious, for example, that our product should be bounded?  Could an optimal solution have infinitely many terms in S?

As it happens, neither of these pathologies arise, because an infinite product either has

  1. Product equal to zero, or
  2. Infinitely many terms that do not limit to zero, which contradicts our restriction on the sum of S.

With that worry at ease, we present our solution to the continuous case:

Solution: Our solution uses the general idea of perturbation theory: if x_1,x_2 are both in S, let’s consider what happens when we replace the pair x_1,x_2 with its arithmetic mean (x_1+x_2)/2, occurring twice.  Since

\left(\frac{x_1+x_2}{2}\right)^2 \geq x_1x_2 \quad \Leftrightarrow \quad \mathrm{AM}(x_1^2,x_2^2) =\frac{x_1^2+x_2^2}{2} \geq x_1x_2 = \mathrm{GM}(x_1^2,x_2^2),

and this latter inequality follows from the AM-GM inequality, it follows that we can always increase our product by averaging out the terms in S.  In a set S with maximal product, we may assume that every term in S is equal.  If S has m terms, then

S = \{n/m,\ldots,n/m\},

and the product over S is (n/m)^m.

For which integer m is this maximized?  Let t=n/m; then we seek to maximize


with t an integer multiple of 1/m.  If we relax our assumptions on t and merely assume that t > 0 is real, then t^{1/t} (and hence (t^{1/t})^n) is uniquely maximized for t=e.  Therefore, restricting to t \in n/\mathbb{Z}, our maximum is attained at one of the following two points:

t=n/\lfloor n/e \rfloor, \quad n/\lceil n/e \rceil,

which in either case gives us the maximal product

\max\left(\left(\frac{n}{\lfloor n/e \rfloor}\right)^{\lfloor n/e \rfloor},\left(\frac{n}{\lceil n/e \rceil}\right)^{\lceil n/e \rceil}\right).\quad\qquad\qquad\qquad (1)

So, which one of the terms above is largest?  Based on the work that got us this far, it stands to reason that our answer should correlate (if not correspond) to whichever one of the two approximations

\frac{n}{\lfloor n/e \rfloor}, \qquad \frac{n}{\lceil n/e \rceil}

is closer to e.  Indeed, if the function we were maximizing — namely x^{n/x} — was symmetric about its unique maximum, our answer would be this simple: take the choice that corresponds to the better approximation. While this claim fails,  our intuition in the matter nevertheless carries through.

We can prove the following result, which says that each choice in the maximum from line (1) occurs with equal probability:

Theorem: The set of integers such that the maximum in line (1) occurs with the first term has natural density 1/2.

Proof: For any \alpha <1/2, there exists a positive \epsilon >0 such that

(1+\epsilon)\left(\frac{\alpha}{n}\right)^2 \leq (1-\epsilon)\left(\frac{1-\alpha}{n}\right)^2,

for all integers n.  Let \delta_n = \{n/e\}, in which \{x\} denotes the fractional part of the real number x, and let S_\alpha denote the set of integers

S_\alpha = \{n \in \mathbb{N} : \{n/e\}<\alpha\}.

It follows that

e^{\frac{1}{e}}-\frac{1}{2}e^{1+\frac{1}{e}}(1+\epsilon)\left(\frac{\delta_n}{n}\right)^2 \geq e^{\frac{1}{e}}-\frac{1}{2}e^{1+\frac{1}{e}}(1-\epsilon)\left(\frac{1-\delta_n}{n}\right)^2

for all n \in S_\alpha.  Expanding f(x):=x^{-x} in a power series at x=1/e, we find


Therefore, there exists an interval I_\epsilon such that for all x \in I_\epsilon, we have

e^{\frac{1}{e}}-\frac{1}{2}e^{1+\frac{1}{e}}(1+\epsilon)\left(x-\frac{1}{e}\right)^2 \leq f(x) \leq e^{\frac{1}{e}}-\frac{1}{2}e^{1+\frac{1}{e}}(1-\epsilon)\left(x-\frac{1}{e}\right)^2.

Provided that n \in S_\alpha is taken large enough so that both \frac{1}{e}-\frac{\delta_n}{n} and \frac{1}{e}+\frac{1-\delta_n}{n} both lie in the interval I_\epsilon, we find that

f\left(\frac{1}{e}-\frac{\delta_n}{n}\right) \geq f\left(\frac{1}{e}+\frac{1-\delta_n}{n}\right). \qquad\qquad\qquad\qquad (2)

Thus (2) holds on a set of natural density equal to the natural density of the setS_\alpha.  But S_\alpha has natural density \alpha, by the equidistribution theorem, which gives (2) on a set of density \alpha for any \alpha <1/2.  Conversely, one may show that

\delta_n >\frac{1}{2} \quad \Longrightarrow \quad f\left(\frac{1}{e}-\frac{\delta_n}{n}\right) < f\left(\frac{1}{e}+\frac{1-\delta_n}{n}\right)\quad\qquad\qquad (3)

(see the Exercises), which implies that (2) fails for a set of natural density 1/2.  Since (2) holds for n if and only if the first term in line (1) is maximal, which gives our result. \square


Exercise: If S is a set of positive rationals totaling n, what is the maximal product over the elements in S?

Exercise: Use the degree two Taylor expansion of x^{-x} about the point x= 1/e to show that the claim in line (3) holds.

Exercise: Show that the interval I_\epsilon can be explicitly bounded from inside, and use this (plus the effective equidistribution theorem) to give an effective version of our final theorem. (Hard.)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s