# Proving that a discrete valuation-like function $w: \mathbb{Z}\backslash\{0\} \rightarrow \mathbb{N}$ is a $p$-adic valuation

This problem is from Birkhoff and Maclane, A Survey of Modern Algebra, pg 21, problem 4*.

Given a function $w: \mathbb{Z}\backslash\{0\} \rightarrow \mathbb{N}$ that behaves like a discrete valuation function, i.e.,

(1) $w(ab) = w(a) + w(b)$

(2) $w(a+b) \geq \min(w(a), w(b)).$

Show that it is either

1. constant $0$ function, $w(a) = 0$ or
2. a multiple of a $p$-adic valuation, in other words $w(a) = k v_p(a)$ for some $p, k$ with $v_p(p^nd) = n$ when $(p, d) = 1$.

More interesting is the variant of this problem described here.

-

## migrated from mathoverflow.netOct 11 '13 at 13:48

This question came from our site for professional mathematicians.

the condition (2) should have either the inequality the other way around or you should use maximum instead of minimum. –  Andrew Stout Oct 11 '13 at 13:09
Did you fix it? it looks correct. en.wikipedia.org/wiki/Discrete_valuation –  Ben Kavanagh Oct 11 '13 at 13:39
You never used the assumption that $w$ takes integer values, but this is needed to exclude the archimedean valuation $w(a)=\log a$. –  Emil Jeřábek Oct 11 '13 at 13:43
The type of w is $\mathbb{N}^+ \rightarrow \mathbb{N}$. This means that it maps each positive natural number $n\in\mathbb{N}. n \ge 0$ to $w(n) \in \mathbb{N}$ so the problem statement includes the constraint. –  Ben Kavanagh Oct 11 '13 at 13:51
@YACP Ok. I just split the questions as you suggested –  Ben Kavanagh Oct 12 '13 at 10:48

From $(1)$ we have $w(1)=w(1)+w(1)$, hence $w(1)=0$. Then we have $w(1)=w(-1)+w(-1)$, hence $w(-1)=0$. So we have $w(-n)=w(-1)+w(n)=w(n)$ and need only check positive integers.Also, this allows us to generalize $(2)$ to $$\tag{2'}w(a\pm b)\ge\min\{w(a),w(b)\}\qquad\text{if }a\pm b\ne 0.$$

Let $a$ be the smallest positive integer with $w(a)>0$ (if no such $a$ exists, then $w=0$ and we are done). Clearly, $a>1$ as $w(1)=0$. Thus $a$ is either composite or prime. If $a$ is composite, $a=a_1a_2$ with $1<a_1,a_2<a$, then $w(a)=w(a_1)+w(a_2)$ implies that one of $w(a_1),w(a_2)$ is nonzero, contradicting minimality. Hence $a$ is (once again) a prime.

Let $b$ be the smallest positive integer with $w(b)\ne v_a(b)$ (if no such $b$ exists, we have $w=v_a$ and are done). If $a|b$ then $w(\frac ba)=w(b)-w(a)\ne v_a(b)-v_a(a)=v_a(\frac ba)$ contradicting minimality of $b$. Therefore $v_a(b)=0$ and hence $w(b)>0$. By minimality of $a$ we have $b>a$, hence $b-a>0$. Now $w(b-a)\ge \min\{w(b),w(-1)+w(a)\}>0$. Since $a\not\mid b-a$ we conclude $w(b-a)\ne v_a(b-a)$ contradicting minimality of $b$.

-

Clearly, since $w$ obeys (1) by the unique factorization theorem it is determined by its value on the primes, $w(p_i^{\alpha_i}\cdots p_m^{\alpha_m}) = \alpha_i w(p_i)+\cdots+\alpha_m w(p_m)$. If we show that there exists at most one prime $p$ such that $w(p) \neq 0$ then we have the result with $k=w(p)$.

If for all $a\in \mathbb{N}^+$, $w(a) = 0$ we are done. Otherwise let $n \in \mathbb{N}^+$ be the first natural number such that $w(n) \neq 0$. We have that $n$ is a prime otherwise by (1) we have a contradiction.

Need to show that for all primes $p \neq n$, $w(p)=0$.

If $p, n$ primes and $p \neq n$ then $(p, n) = 1$ and so there exists $s, t\in\mathbb Z$ s.t. $sp + tn = 1$. Therefore by (2) $\min(w(s)+w(p), w(t)+w(n)) \le 0$ and since $w(n) \gt 0$ we have that $w(s) + w(p) = 0$ and so $w(s) = w(p) = 0$.

We can also show that $w(p) = 0$ by extending $w$ to be defined over $\mathbb{Z}$ by defining $w'(a)=\infty$ if $a=0$, $w'(a) = w(a)$ otherwise. This turns the set $\{a:w(a)≥0\}$ into an ideal, which gives the result. This problems is stated in Maclane prior to ideals and related concepts so the answer essentially comes from the proof that $\mathbb Z$ is a PID.

-