8
$\begingroup$

Is the identity map the only map $f$ from the positive integers $\mathbb{Z}_{+}$ to itself that satisfies all three of the following properties?

  1. $f(mn)=f(m)f(n)$ for all positive integers $m$ and $n$ (which implies that $f(1)=1$)
  2. $f(m)<f(n)$ whenever $m<n$ (which implies that $f$ is injective)
  3. $f(p)$ is prime for any prime number $p$

The above three properties (actually, for property 2, the weaker assumption that $f$ is injective suffices) imply that applying $f$ to any positive integer will not change the prime signature, because all that happens with $f(n)$ is that each prime $p$ dividing $n$ is replaced with $f(p)$ while maintaining the same exponent.

Here are some examples that suggest that the answer might be "Yes" (because they only satisfy properties 1 and 3 and injectivity, but are not order-preserving on all positive integers, although they are order-preserving on prime numbers):

  • Let $f(p)$ be the next prime following $p$, with $f$ extended to composite numbers using (complete) multiplicativity. Then, $8<9$, while $f(8)=f(2^3)=f(2)^3=3^3=27>25=5^2=f(3)^2=f(3^2)=f(9)$.
  • Let $f$(the $n$th prime) be the $(2n)$th prime. Then, $27<32$, while $f(27)=f(3^3)=f(3)^3=7^3=343>243=3^5=f(2)^5=f(2^5)=f(32)$.
  • Let $f(p)$ be the $p$th prime. Then, $f(8)=27>25=f(9)$, as in the first example.
  • Let $f$(the $n$th prime) be the $(n^2)$th prime. Then, $3<4$, while $f(3)=7>4=2^2=f(2)^2=f(2^2)=f(4)$.

But of course, specific examples (using inductive reasoning) are not enough to conclude that the answer is in fact "Yes".

$\endgroup$
6
$\begingroup$

Building on the discussion in the comments of Teresa's answer, this follows from the six exponentials theorem. I will try to write a self-contained answer here.

First, as you say the given conditions imply that $f$ restricts to some strictly monotonic function on the primes, and is determined by its values on the primes. If $p_1, \dots p_k$ is any finite set of distinct primes, then strict monotonicity of $f$ means that if $\prod p_i^{e_i} < \prod p_i^{f_i}$ then $\prod f(p_i)^{e_i} < \prod f(p_i)^{f_i}$. Taking logarithms and subtracting, this gives

$$\sum q_i \log p_i < 0 \Rightarrow \sum q_i \log f(p_i) < 0, q_i \in \mathbb{Q}.$$

In other words, $f$ induces a strictly order-preserving linear map $F$ from the $\mathbb{Q}$-subspace of $\mathbb{R}$ spanned by $\{ \log p_i \}$ to the $\mathbb{Q}$-subspace of $\mathbb{R}$ spanned by $\{ \log f(p_i) \}$. This implies that $F$ is continuous (with respect to the subspace topology coming from $\mathbb{R}$), which gives that it must in fact be given by multiplication by some fixed real number $r$. Said another way:

Corollary: For real coefficients $r_i$, we have $\sum r_i \log p_i = 0 \Leftrightarrow \sum r_i \log f(p_i) = 0$. Equivalently, there is some $r$ such that $\log f(p_i) = r \log p_i$ for all primes $p_i$.

This is quite a strong condition. It's equivalent to the condition that $\frac{\log f(p)}{\log p} = \frac{\log f(q)}{\log q}$ for distinct primes $p, q$, which assuming Schanuel's conjecture (which implies that the logarithms of the primes are algebraically independent) gives $f(p) = p, f(q) = q$. (We can also assume the weaker four exponentials conjecture instead.)

But actually we can avoid Schanuel's conjecture by considering three distinct primes $p, q, r$ instead. The six exponentials theorem implies that if $f(p) \neq p$ then (using that unique prime factorization implies that the logarithms of the primes are linearly independent over $\mathbb{Q}$) the matrix

$$\left[ \begin{array}{cc} \log p & \log q & \log r \\ \log f(p) & \log f(r) & \log f(r) \end{array} \right]$$

has rank $2$. But we showed above that the second row must be a multiple of the first, so this matrix has rank $1$; taking contrapositives, it follows that $f(p) = p$, and since the argument works for any three distinct primes we get $f(p) = p$ for all primes $p$.

$\endgroup$
1
  • $\begingroup$ I see , you've written up the SET argument very clearly. +1 $\endgroup$ Jan 11 at 20:31
5
$\begingroup$

Start with $f(2) = p$ for some prime $p$. Then, we need a choice for $f(3)$. We certainly need that whenever $3^q > 2^l$ then $f(3^q) > f(2^l)$ i.e. $f(3)^q > f(2)^l$ i.e. $f(3) > f(2)^{\frac lq}$.

However, we also need that whenever $3^x < 2^y$ then $f(3) < f(2)^{\frac yx}$.

Therefore, we are constrained to have $\frac lq < \log_{f(2)} f(3) < \frac yx$ for all pairs of (positive, doesn't really matter) rationals $\log_2 3 > \frac lq$ and $\log_2 3 < \frac yx$. By density of rationals in the reals, we are forced to have $\log_{f(2)} f(3) = \log_2 3$, and therefore $f(3) = f(2)^{\log_2 3}$.

Now, we can write this as $f(3) = 3^{\log_2 f(2)}$.

I don't think there's anything special about $2$ and $3$ in the argument above, so doing it for any pair of primes gives you that $f(q) = f(p)^{\log_p q}$ for any pair of primes $p$ and $q$.

This is severely restrictive of all values of $f$,since given just $f(2)$ we get all the other values. So we have a partial answer : everything is decided by $f(2)$, since $f(q) = f(2)^{\log_2 q}$.

Let us write this in beneficial fashion : for the existence of such a function, we require that for all primes $p,q$ we have , using the fact that $\frac{\ln p}{\ln q} = \log_q p$, the relation $\ln f(r) \ln s = \ln f(r) ln s$ for any primes $r,s$.


Now, the point is that we are expecting that $f(q)$ is an integer only when $f(2) = 2$ so that $f(q) = q$. But this is not a "given", since we don't know if $f(2)$ could be a prime so that $f(q)$ were in fact a valid prime integer for every $q$!

To answer this question, we need to get to "quadratic relations between logarithms of algebraic numbers".

Now, usually when we prove that things involving logarithms aren't integers and so on, we usually break them into "relations" involving logarithms. Then we use results known for logarithms and exploit them for our purposes.

Now, there are nice theorems for "linear" relations involving logarithms. These lead to the transcendence of numbers such as $\log_2 3$, and $2^{\sqrt 2}$ (try to see that if they were rational, it breaks into a linear relation between logarithms).

However, the relation we have , of the form $\ln q \ln r = \ln s \ln t$, is called a quadratic relation between logarithms. It turns out that for quadratics , we have a series of conjectures, along with a nice theorem which I state first!


First, let us use the six exponentials theorem. We call a subset $\{z_1,...,z_n\}$ of complex numbers as rationally independent if for any rationals $r_1,...,r_n$ we have $r_1z_1+...+r_nz_n \neq 0$ if at least one of the $r_i$ is non-zero.

Six Exponentials Theorem : Suppose that $x_1,x_2,x_3,y_1,y_2,y_3$ are complex numbers such that :

  • $x_1,x_2,x_3$ are rationally independent over the integers
  • $x_1,y_1$ are rationally independent over the integers.
  • Furthermore, each of $e^{x_i}$ and $e^{y_j}$ are algebraic numbers (read this and transcendental numbers up). Then the matrix : $$ \begin{pmatrix}x_1&x_2&x_3 \\ y_1 & y_2 & y_3\end{pmatrix} $$ is of rank $2$. In particular, at least one of : $$ x_1y_2 \neq x_2y_1, x_1y_3 \neq x_3y_1,x_2y_3 \neq x_3y_2 $$ is true.

Let us see how to use this. Suppose that $f(2) = p \neq 2$. Note that automatically, $f(s) \neq s$ for all primes $s$. Choose a prime $r$ such that $f(r) \neq p, r \neq p$. Choose a prime $s$ so that $s,f(s) \notin \{2,p,r,f(r)\}$. Note that $\ln 2 , \ln r , \ln s$ are linearly independent over the rationals (using an argument via prime factorization) and $\ln 2 , \ln f(r)$ are also rationally independent. Consequently, let the $x_i$ be $\ln 2 , \ln r,\ln s$ and $y_i$ be $\ln p ,\ln f(r),\ln f(s)$. Then, all conditions are satisfied (the third one trivially, since integers are algebraic).

As a conclusion, one of $\ln 2 \ln f(r) = \ln r \ln p$, $\ln 2 \ln f(s) = \ln s \ln p$ or $\ln f(r) \ln s= \ln f(s) \ln r$ must be false. But none of these can be false! Consequently, we get that $f(2) = 2$, for that's the only way in which I can violate such a situation which provided our $x_i$ and $y_i$.


Next we use the conjecture :

Four exponentials conjecture : (Read up all unknown terminology) let $a,b,c,d$ each be logarithms of some complex numbers, with $\frac ab$ and $\frac cd$ non-zero and irrational. Then $\frac ab \neq \frac cd$.

Sounds logical : it's saying that a relation $ad = bc$ can't exist between "incompatible" logarithmic quantities $a,b,c,d$.

To use this for our problem : we know that if $f(3) = q$ a prime, then $\ln 2 \ln q = \ln 3 \ln p$. But note that if $p \neq 2$ then $q \neq 3$ and $\frac{\ln 2}{\ln p}$ and $\frac{\ln 3}{\ln q}$ are irrational (use prime factorization), so they are not equal by the conjecture, contradicting the premise. Thus $f(2)=2$, $f(3) = 3$ and we can do this for any pair of primes.


Next, another conjecture of Schaunel, which is also nice. We start with $n$ complex numbers which are linearly independent over the rational numbers i.e. no rational combination of them is zero. To perform this argument, we first choose an $r$ prime with $r \neq p, f(r) \neq p$ so that $\ln 2, \ln r , \ln p$ and $\ln f(r)$ (we are assuming $p \neq 2$) so that they are all linearly independent over the rationals (once again, you can use prime factorization to get this result).

The conjecture is, stated in simple words :

If there are $n$ complex numbers linearly independent over the rationals, say $z_1,...,z_n$ then consider the subset $\{z_1,...,z_n,e^{z_1},...,e^{z_n}\}$. There is a subset $S$ consisting of $n$ of these elements, say $\{s_1,...,s_n\}$, such that if I take any polynomial in $n$ variables $f(x_1,...,x_n)$ with rational coefficients, then $f(s_1,...,s_n)\neq 0$. This is equivalent to saying that the transcendence degree of the extension of the rationals by all of $\{z_1,...,z_n,e^{z_1},...,e^{z_n}\}$ is at least $n$.

Now, do this with our subset ,and because each of the exponentials of elements of $\{\ln 2 , \ln r, \ln f(r) , \ln p\}$ are $2,r,f(r),p$ which are already rational so they don't add to the transcendence degree of the extension. Thus, using the conjecture, these four elements are therefore algebraically independent! But then, the polynomial $f(w,x,y,z) = wx-yz$ cannot be zero at $w=\ln 2, x = \ln f(r), y = r, z = \ln p$, and therefore $\ln 2 \ln f(r) \neq \ln r \ln f(p)$, a contradiction. So $f(2) = 2$.


All these results/conjectures are very helpful in solving these existence problems, as I have shown.

Links :

1 . The Six Exponentials theorem

2 . The Four exponentials theorem

3 . Schanuel's conjecture

$\endgroup$
10
  • 1
    $\begingroup$ Nitpickery: it's certainly TRUE, but do we know that $3^{\log_2(p)}$ can't be a whole number for other prime $p$? IIRC this sort of problem is notoriously sticky. $\endgroup$ Jan 11 at 18:17
  • $\begingroup$ @StevenStadnicki Right, I will look into it, it did look sticky but I did some handwaving in my head and left it as an exercise. I will look into it. $\endgroup$ Jan 11 at 18:18
  • 1
    $\begingroup$ I think the most fruitful approach is likely to be what you mention in the last paragraph — make the same argument for many sets of primes and derive a contradiction in there somewhere, possibly using something like the six exponentials theorem. $\endgroup$ Jan 11 at 18:19
  • 1
    $\begingroup$ This argument works conditional on Schanuel's conjecture, which implies that the logarithms of the primes are algebraically independent and so $\frac{\log f(p)}{\log f(q)} = \frac{\log p}{\log q}$ implies $f(p) = p, f(q) = q$: en.wikipedia.org/wiki/Schanuel%27s_conjecture $\endgroup$ Jan 11 at 18:32
  • 1
    $\begingroup$ @QiaochuYuan Thank you! I was just editing that into the answer, since I can't answer this using the six exponentials theorem. I realize that the SET is for "linear relations" between logarithms. "Quadratic relations" require Schanuel's conjecture. I will edit this is as well, thank you. $\endgroup$ Jan 11 at 18:34

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.