# proof of equivalence of definitions of valuation

Lemma Let $|\cdot|$ be a valuation according to the definition of the parent entry with constant $C\leq 2$. Then $\left|\sum_{i=1}^{n}x_{i}\right|\leq 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|\leq 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|\leq 2\cdot 2^{r-1}\max_{i=1}^{2^{r-1}}|x_{i}|+2\cdot 2% ^{r-1}\max_{i=2^{r-1}+1}^{2^{r}}|x_{i}|\leq 2\cdot 2^{r}\max_{i=1}^{2^{r}}|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}\leq 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|\leq 2^{r% }\max_{i=1}^{2^{r}}|x_{i}|\leq 2n\max_{i=1}^{n}|x_{i}|$

Q.E.D.

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

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

 $|n|=\left|\sum_{i=1}^{n}1\right|<2n|1|$

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

 $|n|\leq 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\leq 2$, then $|\cdot|$ satisfies the identity

 $|x+y|\leq|x|+|y|.$

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

 $|x+y|^{n}=|(x+y)^{n}|=\left|\sum_{m=0}^{n}{n\choose m}x^{m}y^{n-m}\right|$

Using the lemma, we can bound this:

 $|x+y|^{n}\leq 2(n+1)\max_{m=0}^{n}\left|{n\choose m}x^{m}y^{n-m}\right|$

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

 $|x+y|^{n}\leq 4(n+1)\max_{m=0}^{n}{n\choose m}|x|^{m}|y|^{n-m}$

Using the obvious inequality

 $\max_{m=0}^{n}{n\choose m}|x|^{m}|y|^{n-m}\leq\sum_{m=0}^{n}{n\choose m}|x|^{m% }|y|^{n-m},$

we obtain

 $|x+y|^{n}\leq\sum_{m=0}^{n}4(n+1){n\choose m}|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|\neq 0$ and we can divide by $(|x|+|y|)^{n}$ to obtain

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

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

 ${|x+y|\over|x|+|y|}\leq 1,$

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

Q.E.D.

Title proof of equivalence of definitions of valuation ProofOfEquivalenceOfDefinitionsOfValuation 2013-03-22 14:56:00 2013-03-22 14:56:00 rspuzio (6075) rspuzio (6075) 12 rspuzio (6075) Proof msc 11R99 msc 12J20 msc 13A18 msc 13F30