Upper bound on the distance of two products

175 Views Asked by At

Let $(a_1,\ldots,a_n)\in[0,1]^n$ and $(b_1,\ldots,b_n)\in[0,1]^n$.

Let $\epsilon\in[0,1]$ and assume $\forall i:|a_i-b_i|\leq\epsilon$ and $\forall i,j:|a_i-a_j|\leq\epsilon$.

Question: Is $\left|\prod_{i\in[n]}a_i-\prod_{i\in[n]}b_i\right|\leq n\epsilon$? (A proof would be appreciated.)

1

There are 1 best solutions below

0
On BEST ANSWER

Here's a proof . . .

Fix a positive integer $n$, and let $\epsilon \in [0,1]$.

Suppose we have a pair $(a,b)$, with $a,b\in [0,1]^n$ such that
\begin{align*} &{\small{\bullet}}\;\;|a_i - b_i|\le \epsilon,\;\text{for all}\;i\\[7pt] &{\small{\bullet}}\;\;|a_i - a_j|\le \epsilon,\;\text{for all}\;i,j\\[3pt] &{\small{\bullet}}\;\;\left|\prod_{i=1}^n a_i-\prod_{i=1}^n b_i\right| > n\epsilon\\[3pt] \end{align*} In other words, assume the pair $(a,b)$ is a counterexample to the claim.

Without loss of generality, we can assume $$a_1 \le \cdots \le a_n$$ Since, by assumption, $$\left|\prod_{i=1}^n a_i-\prod_{i=1}^n b_i\right| > n\epsilon$$ we can't have $$\prod_{i=1}^n b_i=\prod_{i=1}^n a_i$$ Consider two cases . . .

Case $(1)$:$\;\;{\displaystyle{\prod_{i=1}^n b_i > \prod_{i=1}^n a_i}}$.

Given any such counterexample, we can replace it with one satisfying $$b_i = \min(1,a_i+\epsilon),\;\text{for all}\;i$$ Thus, assume the above condition is satisfied.

It follows that $b_1 \le \cdots \le b_n$.

Suppose $b_1 < b_n$.

Then, letting $w=b_n-b_1$, we can replace \begin{align*} &{\small{\bullet}}\;\;a_1\;\text{by}\;a_1+w\\[4pt] &{\small{\bullet}}\;\;b_1\;\text{by}\;b_1+w=b_n\\[4pt] \end{align*} and we would still have a case $(1)$ counterexample.

Iterating these replacements, we can get a case $(1)$ counterexample for which \begin{align*} &{\small{\bullet}}\;\;b_1 = \cdots = b_n = x\\[4pt] &{\small{\bullet}}\;\;a_1 = \cdots = a_n = y\\[4pt] \end{align*} where $0 \le x-y \le \epsilon$.

Then, noting that $0 \le x,y \le 1$, we get

\begin{align*} \left|\prod_{i=1}^n a_i-\prod_{i=1}^n b_i\right| &=\prod_{i=1}^n b_i-\prod_{i=1}^n a_i\\[4pt] &=x^n-y^n\\[4pt] &=(x^{n-1}+x^{n-2}y + \cdots + xy^{n-2}+y^{n-1})(x-y)\\[4pt] &\le(x^{n-1}+x^{n-2}y + \cdots + xy^{n-2}+y^{n-1})\epsilon\\[4pt] &\le n\epsilon \end{align*} contradiction.

Hence, for case $(1)$, no counterexample is possible.

Case $(2)$:$\;\;{\displaystyle{\prod_{i=1}^n a_i > \prod_{i=1}^n b_i}}$.

Given any such counterexample, we can replace it with one satisfying $$b_i = \max(0,a_i-\epsilon),\;\text{for all}\;i$$ Thus, assume the above condition is satisfied.

It follows that $b_1 \le \cdots \le b_n$.

Suppose $b_1 < b_n$.

Then, letting $w=b_n-b_1$, we can replace \begin{align*} &{\small{\bullet}}\;\;a_1\;\text{by}\;a_1+w\\[4pt] &{\small{\bullet}}\;\;b_1\;\text{by}\;b_1+w=b_n\\[4pt] \end{align*} and we would still have a case $(2)$ counterexample.

Iterating these replacements, we can get a case $(2)$ counterexample for which \begin{align*} &{\small{\bullet}}\;\;a_1 = \cdots = a_n = x\\[4pt] &{\small{\bullet}}\;\;b_1 = \cdots = b_n = y\\[4pt] \end{align*} where $0 \le x-y \le \epsilon$.

Then, noting that $0 \le x,y \le 1$, we get

\begin{align*} \left|\prod_{i=1}^n a_i-\prod_{i=1}^n b_i\right| &=\prod_{i=1}^n a_i-\prod_{i=1}^n b_i\\[4pt] &=x^n-y^n\\[4pt] &=(x^{n-1}+x^{n-2}y + \cdots + xy^{n-2}+y^{n-1})(x-y)\\[4pt] &\le (x^{n-1}+x^{n-2}y + \cdots + xy^{n-2}+y^{n-1})\epsilon\\[4pt] &\le n\epsilon \end{align*} contradiction.

Hence, for case $(2)$, no counterexample is possible.

Thus, in both cases, no counterexample is possible, which completes the proof of the claim.