Proof of a lemma with inequalities

Question

I read a paper about keyword search and just cannot understand the lemma. Please help me to understand it, thanks.

Lemma 1: Let $v_1,v_2,\ldots,v_r$ be $r$ non-descending integers in the range from $1$ to $\lambda\ge 1$. Gap-keeping requires at most $O(r\log(\lambda/r))$ bits to encode all of them.

Proof: Denote $u_1=v_i-v_{i-1}$ for $i\in[2,r]$, and $u_1=v_1$. Note that $\{u_1,u_2,\ldots,u_r\}$ is exactly the set of values gap-keeping stores. Each $u_1$ $(1\le i\le r)$ occupies $O(\log u_i)$ bits. Hence, recording all of $u_1,u_2,\ldots,u_r$ requires at most

$$O(\log u_1+\log u_2+\ldots+\log u_r)=O\left(\log\left(\prod_{i=1}^ru_1\right)\right)\qquad(6)$$

bits. A crucial observation is that

$$1\le u_1+u_2+\ldots+u_r\le\lambda$$

as all of $v_1,v_2,\ldots,v_r$ are between $1$ and $\lambda$. Therefore, $\prod_{i=1}^ru_i$ is at most $(\lambda/r)^r$. It thus follows that Equation 6 is bounded by $O(r\log(\lambda/r))$. $\square$

I can not understand why the product of $u_i$'s is at most $(\lambda/r)^r$. Is there an inequality or formula about this?

Answer 1

The product $\prod_{i=1}^r u_i$ is at a maximum when the $v_i$'s are as far apart as possible. (If the $v_i$'s are close together, then their gaps $u_i$ would be smaller.) The only way for the $v_i$'s to be as far apart as possible is if they are spaced $\frac{\lambda}{r}$ apart. Thus, $\prod_{i=1}^r u_i$ is at most $\prod_{i=1}^r\frac{\lambda}{r}=\left(\frac{\lambda}{r}\right)^r$.

Answer 2

Given $\lambda$ and $r$, consider all possible combinations of $r$ integers that have a sum that does not exceed $\lambda$. What is the maximum possible product?

This maximum is attained when the sum is equal to $\lambda$: suppose otherwise, that $\sum_i u_i < \lambda$, where $\prod_i u_i$ is a maximum. Then just replace $u_1$ with $u_1+1$. This gives a sum that is $\le \lambda$, but a bigger product, contradiction.

So the question ends up being "given $r$ integers that sum to $\lambda$, what is the largest product attainable?" If the question involved $r$ real numbers instead of integers, then we see that the maximum happens when all of the $u_i$ equal $\lambda/r$, giving a product $(\lambda/r)^r$. So if we restrict the problem to its original state ($r$ integers instead of real numbers), the product cannot exceed $(\lambda/r)^r$, so it is still a valid upper bound.