0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ For $f(x) = \prod_i x_i$, what is an upper bound of $\|\nabla f(x)\|$? $\endgroup$ – user251257 Feb 23 '18 at 17:35
  • $\begingroup$ 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. $\endgroup$ – stochasticboy321 Feb 24 '18 at 5:49
  • $\begingroup$ 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. $\endgroup$ – mti Feb 24 '18 at 22:22
  • $\begingroup$ You may also post your findings as an answer. $\endgroup$ – Mehrdad Zandigohar Feb 24 '18 at 22:31
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.