Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

migrated from Oct 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. – 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
up vote 1 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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