# A valuation-like function $w: \mathbb{N}^{+} \rightarrow \mathbb{N}$ is a $p$-adic valuation?

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

Given a function $w: \mathbb{N}^+ \rightarrow \mathbb{N}$ that behaves like a 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 $\forall a \in \mathbb{N}^+, w(a) = k v_p(a)$ for some $p, k$ with $v_p(p^\alpha d) = \alpha$ when $(p, d) = 1$.

Note that this problem is relatively simple if $w$ is defined over $\mathbb{Z}\backslash \{0\}$ instead of $\mathbb{N}^+$ which is the problem listed in the book. My question is whether the stronger statement above is also true.

My current proof attempt is incomplete.

If $\forall a,\ w(a) = 0$ we are done. Otherwise let $n$ be the least number s.t. $w(n) \neq 0$. Easy to show from (1) that $n \neq 1$ since $w(1) = 0$ and that $n$ is prime.

By unique factorisation theorem and (1) to get the result I need only prove that for all primes $p$, $p\neq n \implies w(p) = 0$.

I tried to proceed using well founded induction. If $p \lt n$ done. Otherwise $p \gt n$. If $n \gt 2$ then $n, p$ are odd and $n+p$ is even hence $n+p=2q$. Now $n \nmid p$ so $n \nmid n + p$. If $n \gt 2$ we have $n \nmid q$. Since $q \lt p$ the induction hypothesis gives us $w(q) = 0$ and since $n \gt 2$, $w(2) = 0$. Thus $w(n+p) = w(2q) = w(2) + w(q) = 0 \ge \min(w(n), w(p))$. This gives us that $w(p) = 0$.

I can't see how to solve the $n=2$ case. Is the case where $n=2$ solvable or is there a counterexample?

Some perhaps useful facts.

If $w(2) \neq 0$ and any other $w(p')=0$ for $p'$ prime, $p'\neq 2$ then $w(p) =0$ for all primes $p\neq2$. Easy to prove since every prime $p$ is an even multiple less than some power $r$ of $p'$ and by (1) $w(p^r) = 0$ and then by (2) $w(p) = 0$.

It can't be the case that $w$ behaves identically on all primes, i.e. $w(p) = k$ for all primes $p$ since it is easy to compute counterexamples, e.g. $2^2*5^2 + 3^5 = 7^3$ that will contradict (2).

Thus it must be distinct at some two primes $p_1, p_2$. This gives two distinct relatively prime numbers where w is equal, $p_1^{w(p_2)}$ and $p_2^{w(p_1)}$. I hoped that this would lead to a contradiction but haven't found a way forward yet.

• Yes. $\mathbb{N}$ is the natural/counting numbers, i.e. $\mathbb{N} = \{n \in \mathbb{Z} \mid n \ge 0\}$ and $\mathbb{N}^+ = \{n \in \mathbb{N} \mid n \gt 0\}$ Oct 12 '13 at 16:52
• If $w(p)\neq 0$ and $w(q)\neq 0$ for any two positive integers $p$ and $q$, then any integer $\geq pq-p-q$ can be written $ap+bq$ for $a,b\geq 0$. So, for any positive integer $r$, and sufficiently large $k$, $w(r^k) \geq \min\{w(p),w(q)\}$, so $w(r) > 0$. So if $w$ isn't a p-adic valuation, then $w(n)>0$ for all $n\in\mathbb{N}^+$. I haven't gotten anywhere from here, but this seems like an important fact. Oct 13 '13 at 1:23
• @user33433 Well, maybe you assume $p$ and $q$ coprime, or even better (in this case), distinct primes.
– user26857
Oct 13 '13 at 7:10
• @YACP Yes, thanks for pointing that out. I was originally just going to say that $p$ and $q$ were distinct primes, then I thought I'd be clever... anyway, the conclusion still holds—if $w$ is not a p-adic valuation, then it must be nonzero on all integers $\geq 2$. Oct 13 '13 at 7:29

Let $w$ be as in the question, and assume it is nonzero for two distinct primes. As already mentioned by user33433 in the comments, this implies $w(n)>0$ for all $n>1$, since every sufficiently large number is a positive linear combination of the two primes. We can in fact use a similar argument to estimate the rate of growth of $w$:

Lemma 1: If $a,b>1$ are coprime and $n>1$, then $$\frac{\log n}{w(n)}\le\frac{\log a}{w(a)}+\frac{\log b}{w(b)}.$$

Proof: Let $k$ be a large integer, and $l=\lceil k(w(b)\log a+w(a)\log b)/\log n\rceil$. Since $a^{w(b)k}$ and $b^{w(a)k}$ are coprime, and $n^l\ge a^{w(b)k}b^{w(a)k}$, there are $u,v\ge0$ such that $n^l=ua^{w(b)k}+vb^{w(a)k}$, thus $$\left(1+\frac{k(w(b)\log a+w(a)\log b)}{\log n}\right)w(n)>w(n^l)\ge \min\{w(a^{w(b)k}),w(b^{w(a)k})\}=kw(a)w(b).$$ Multiplying by $(\log n)/kw(a)w(b)w(n)$, we obtain $$\frac{\log n}{kw(a)w(b)}+\frac{\log a}{w(a)}+\frac{\log b}{w(b)}>\frac{\log n}{w(n)}.$$ The lemma follows by letting $k$ go to infinity. QED

Consequently, $c:=\sup\{(\log n)/w(n):n>1\}$ is finite (and positive), we have $$w(n)\ge\frac{\log n}c$$ for every $n$, and $$w(p)\le\frac{2\log p}c$$ for all but possibly one prime $p$.

This is about as far as I got. The problem seems rather difficult to me, and it seems to be connected more to additive number theory (such as the Waring–Goldbach problem) than to valuation theory. As a case in point, let $\alpha>1$ be a real constant, and define $$w_\alpha(p)=\lceil\alpha\log p\rceil$$ for all primes $p$, extended to $\mathbb N^+$ using (1). Note that $\alpha\log n\le w_\alpha(n)\le\alpha\log n+\Omega(n)$ for every $n$, where $\Omega(n)\le\log_2n$ is the number of prime divisors of $n$. Does $w_\alpha$ satisfy (2)? Unlikely, because one can presumably find a prime $q$ that can be written as $q=a+b$, where $a,b$ are of similar magnitude, and each of them has many prime factors $p$ for which $\alpha\log p$ is not close to an integer, in which case the errors add up to get $w_\alpha(a),w_\alpha(b)>w_\alpha(q)$. However, I’m not sure how to prove this formally, and it is even more unclear how to generalize it to arbitrary $w$ of roughly logarithmic growth. I wouldn’t be surprised if a counterexample exists after all.

EDIT: The $w(n)=\lceil\alpha\log n\rceil$ example is in fact ruled out by the following additional properties. Let \begin{align*} \alpha_0&=\liminf_{\substack{p\to\infty\\p\text{ prime}}}\frac{w(p)}{\log p},\\ \alpha_1&=\limsup_{\substack{p\to\infty\\p\text{ prime}}}\frac{w(p)}{\log p}. \end{align*}

Lemma 2: $w(n)\ge\alpha_0\log n$ for every $n$.

Proof: It suffices to show $w(p)/\log p\ge\alpha_0$ for every prime $p$. Let $\epsilon>0$ and $m\in\mathbb N$, we will prove that there is a prime $q\ge m$ such that $$\frac{w(q)}{\log q}\le(1+\epsilon)\frac{w(p)}{\log p}.$$ Let $s$ be the product of all primes below $m$ distinct from $p$. Fix $k$ such that $k>3w(2)/\epsilon w(p)$, and $p^k>3s/\epsilon$. Put $a_0=p^k-s$, $a_1=p^k+s$. Then $a_0+a_1=2p^k$, hence by (2), $$(1+\tfrac\epsilon3)\frac{w(p)}{\log p}\ge \frac{w(2)+kw(p)}{k\log p}\ge\min\left\{\frac{w(a_0)}{k\log p},\frac{w(a_1)}{k\log p}\right\}\ge(1+\tfrac\epsilon3)^{-1}\min\left\{\frac{w(a_0)}{\log a_0},\frac{w(a_1)}{\log a_1}\right\},$$ hence $$(1+\epsilon)\frac{w(p)}{\log p}\ge\frac{w(a_i)}{\log a_i}$$ for some $i=0,1$. Since $w(a_i)/\log a_i$ is a convex combination of the values $w(q)/\log q$ for prime divisors $q$ of $a_i$, we have $$(1+\epsilon)\frac{w(p)}{\log p}\ge\frac{w(q)}{\log q}$$ for some $q\mid a_i$. Moreover, the choice of $a_i$ ensures that $a_i$ is coprime to $p$ and $s$, hence $q\ge m$. QED

Lemma 3: $w(p)\le\alpha_1\log p$ for all but possibly one prime $p$.

Proof: Let $p\ne q$ be primes, $\epsilon>0$, and $m\in\mathbb N$, we will find a prime $r\ge m$ such that $$(1+\epsilon)\frac{w(r)}{\log r}\ge\min\left\{\frac{w(p)}{\log p},\frac{w(q)}{\log q}\right\}.$$ Let $s$ be the product of primes below $m$ other than $p,q$. Choose a sufficiently large $k$, let $l$ be such that $p^k\le sq^l\le p^{k+1}$, and consider $a=p^k$, $b=sq^l$, $n=a+b$. Note that $$\frac{\log n}{\log p^k},\frac{\log n}{\log q^l} \le\frac{\log n}{\log(p^k/s)}\le1+\frac{\log((p+1)s)}{k\log p-\log s}\le1+\epsilon$$ if $k$ is large enough, in which case $$\frac{w(n)}{\log n}(1+\epsilon)\ge\min\left\{\frac{kw(p)}{k\log p},\frac{lw(q)}{l\log q}\right\}.$$ As in the proof of Lemma 2, the same inequality is then satisfied by a prime divisor $r\mid n$, which is coprime to $pqs$, hence $r\ge m$. QED

Lemmas 2 and 3 tell us that all but one $w(p)$ are sandwiched between the curves $\alpha_0\log p$ and $\alpha_1\log p$, which they both approach arbitrarily close infinitely often, hence $w(p)$ oscillates. Also, if $\lim_{p\to\infty}w(p)/\log p$ exists (i.e., $\alpha_0=\alpha_1$), we must have $w(n)=\alpha\log n+\beta v_{p_0}(n)$ for some $\alpha,\beta\ge0$ and a prime $p_0$; this function does indeed satisfy (1) and (2), but most of its values are not integers. Thus, integer-valued $w(n)$ must have $\alpha_0<\alpha_1$.

• I should also mention the Frobenius problem (en.wikipedia.org/wiki/Frobenius_problem) somewhere. The Lemma is based on the solution of F.p. for two numbers. As mentioned in the Wikipedia article, numerical evidence suggests that $g(a_1,a_2,a_3)$ is of the order $\sqrt{a_1a_2a_3}$; if true, this would imply a version of the lemma with $\frac{\log}{w(n)}\le\frac12\left(\frac{\log a_1}{w(a_1)}+\frac{\log a_2}{w(a_2)}+\frac{\log a_3}{w(a_3)}\right)$, in particular $w(p)\le\frac{3\log p}{2c}$ for all but two primes. And if (as a sweeping generalization without any supporting evidence) ... Oct 14 '13 at 19:55
• ... $g(a_1,\dots,a_d)\le O((a_1\cdots a_d)^{1/(d-1)})$ for every $d$, then $(\log p)/w(p)$ converges to $c$ sufficiently fast that it contradicts $w(p)$ being an integer. Whether this sort of speculation can be useful to actually prove anything, I have no idea. Oct 14 '13 at 20:00