proof of equivalence of definitions of valuation

We will start with a lemma:

Lemma Let $|\cdot |$ be a valuation according to the definition of the parent entry with constant $C\le 2$. Then $\left|{\sum }_{i=1}^n{x}_i\right|\le 2n{\max }_{i=1}^n|x_i|$.

Proof:   We will start with the case where $n$ is a power of two: $n=2^r$ We shall prove that $\left|{\sum }_{i=1}^{2^r}{x}_i\right|\le 2^r{\max }_{i=1}^n|x_i|$ by induction. The assertion is certainly true when $n=2$ by hypothesis. Assume that it also holds when $n=2^{r-1}$. Then we have

$$\left|\sum _{i=1}^n{x}_i\right|=\left|\sum _{i=1}^{2^{r-1}}{x}_i+\sum _{i=2^{r-1}+1}^{2^r}{x}_i\right|\le 2\cdot 2^{r-1}\underset{i=1}{\overset{2^{r-1}}{\max }}|x_i|+2\cdot 2^{r-1}\underset{i=2^{r-1}+1}{\overset{2^r}{\max }}|x_i|\le 2\cdot 2^r\underset{i=1}{\overset{2^r}{\max }}|x_i|$$

To deal with the case where $n$ is not a power of two, we shall pad the sum with zeros. That is to say, we shall define $x_i=0$ when $i>n$. Let $r$ be the greatest integer such that $2^r\le n$. Then $2n>2^r$ and we have

$$\left|\sum _{i=1}^n{x}_i\right|=\left|\sum _{i=1}^{2^r}{x}_i\right|\le 2^r\underset{i=1}{\overset{2^r}{\max }}|x_i|\le 2n\underset{i=1}{\overset{n}{\max }}|x_i|$$

Q.E.D.

Corollary Let $|\cdot |$ be a valuation according to the definition of the parent entry with constant $C\le 2$. Then, if $n$ is a positive integer, .

Proof:   Write $n={\sum }_{i=1}^{n}1$. Then, by the lemma,

However, since $|\cdot |$ is a valuation $|1|\ne 0$ since $1\ne 0$ and $|1|=|1|\cdot |1|$ so $|1|=1$, hence

$$|n|\le 2n.$$

Q.E.D.

Having established this lemma, we will now use it to prove the main theorem:

Theorem If $|\cdot |$ is a valuation according to the definition of the parent entry with constant $C\le 2$, then $|\cdot |$ satisfies the identity

$$|x+y|\le |x|+|y|.$$

Proof:   Let $n$ be a positive integer. Then we have

$${|x+y|}^n=|{(x+y)}^n|=\left|\sum _{m=0}^n\left(\genfrac{}{}{0pt}{}{n}{m}\right)x^m{y}^{n-m}\right|$$

Using the lemma, we can bound this:

$${|x+y|}^n\le 2(n+1)\underset{m=0}{\overset{n}{\max }}\left|\left(\genfrac{}{}{0pt}{}{n}{m}\right)x^m{y}^{n-m}\right|$$

Using the corollary to the lemma, we can bound the binomial coefficient to obtain

$${|x+y|}^n\le 4(n+1)\underset{m=0}{\overset{n}{\max }}\left(\genfrac{}{}{0pt}{}{n}{m}\right){|x|}^m{|y|}^{n-m}$$

Using the obvious inequality

$$\underset{m=0}{\overset{n}{\max }}\left(\genfrac{}{}{0pt}{}{n}{m}\right){|x|}^m{|y|}^{n-m}\le \sum _{m=0}^n\left(\genfrac{}{}{0pt}{}{n}{m}\right){|x|}^m{|y|}^{n-m},$$

we obtain

$${|x+y|}^n\le \sum _{m=0}^{n}4(n+1)\left(\genfrac{}{}{0pt}{}{n}{m}\right){|x|}^m{|y|}^{n-m}=4(n+1){(|x|+|y|)}^n.$$

If either $x=0$ or $y=0$, then the theorem to be proven is trivial. If not, then $|x|+|y|\ne 0$ and we can divide by ${(|x|+|y|)}^n$ to obtain

$${\left(\frac{|x+y|}{|x|+|y|}\right)}^n\le 4(n+1)$$

By the theorem on the growth of exponential function, it follows that this inequality could not hold for all $n$ unless

$$\frac{|x+y|}{|x|+|y|}\le 1,$$

in other word, unless $|x+y|\le |x|+|y|$.

Q.E.D.

Title	proof of equivalence of definitions of valuation
Canonical name	ProofOfEquivalenceOfDefinitionsOfValuation
Date of creation	2013-03-22 14:56:00
Last modified on	2013-03-22 14:56:00
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	12
Author	rspuzio (6075)
Entry type	Proof
Classification	msc 11R99
Classification	msc 12J20
Classification	msc 13A18
Classification	msc 13F30