1

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.)

quasi
  • 58,772
mti
  • 113
  • For $f(x) = \prod_i x_i$, what is an upper bound of $|\nabla f(x)|$? – user251257 Feb 23 '18 at 17:35
  • There's a much simpler proof. If $T_n$ is the term above, using the triangle inequality, $$T_n = \left| \prod_1^n a_i - b_n \prod_1^{n-1} a_i + b_n \prod_1^{n-1} a_i - \prod_1^n b_i \right| \le |a_n - b_n|\left| \prod_1^{n-1} a_i\right| + |b_n| \left| \prod_1^{n-1} a_i - \prod_1^{n-1} b_i \right|.$$ Now note that $|a_n - b_n| \le \epsilon,$ $|a_i| \le 1$ for every $i$, and $|b_n| \le 1$ to show that $T_n \le \epsilon + T_{n-1}.$ The rest should be obvious from here. – stochasticboy321 Feb 24 '18 at 05:49
  • I just found this post, which shows that $\left| \prod_{i=1}^k a_i - \prod_{i=1}^k b_i\right|\leq \sum_{i=1}^k |a_i-b_i|$. This solves my problem in a more general case with a very elegant argument. I am considering to delete my question. – mti Feb 24 '18 at 22:22
  • You may also post your findings as an answer. – Mehrdad Zandigohar Feb 24 '18 at 22:31

1 Answers1

0

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.

quasi
  • 58,772