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.

  • $\begingroup$ 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\}$ $\endgroup$ Oct 12 '13 at 16:52
  • $\begingroup$ 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. $\endgroup$
    – Slade
    Oct 13 '13 at 1:23
  • $\begingroup$ @user33433 Well, maybe you assume $p$ and $q$ coprime, or even better (in this case), distinct primes. $\endgroup$
    – user26857
    Oct 13 '13 at 7:10
  • $\begingroup$ @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$. $\endgroup$
    – Slade
    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$.

  • $\begingroup$ 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) ... $\endgroup$ Oct 14 '13 at 19:55
  • $\begingroup$ ... $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. $\endgroup$ Oct 14 '13 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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