For every positive integer n with prime factorization n=∏ki=1pαii, define ℧(n)=∑i:pi>10100αi.That is, ℧(n) is the number of prime factors of n greater than 10100, counted with multiplicity. Find all strictly increasing functions f:Z→Z such that ℧(f(a)−f(b))≤℧(a−b)for all integers a and b with a>b. Proposed by Rodrigo Sanches Angelo, Brazil
Problem
Source: IMO 2015 Shortlist, N8
Tags: inequalities, number theory, prime factorization, function, IMO Shortlist
08.07.2016 03:00
This problem was proposed by Rodrigo Sanches Angelo from Brazil, rsa365 here at Mathlinks.
08.07.2016 06:52
Here is a solution given by one of our contestants during training. For convenience let ℧(n)=S(n). Call primes larger than 10100 to be large and otherwise small. First, sum up both sides to get ∑1≤b<a≤NS(f(a)−f(b))≤∑1≤b<a≤NS(a−b) for all natural N. Now we will show that for any prime power pk, the number of f(a)−f(b) that are divisible by pk is at least that of a−b when N is fixed. Let g(i) denote the number of f(m)'s which are ≡i mod pk. Then the number of f(a)−f(b) that are divisible by pk is simply \sum \binom{g(i)}{2}. Since \binom{n}{2} is convex, it is minimized when the g(i) are equidistributed, which is exactly the case for consecutive naturals and we hence conclude. As a result, we have \sum_{1 \leq b < a \leq N} S(f(a) - f(b)) \geq \sum_{1 \leq b < a \leq N} S(a-b)since both sides is simply the sum of the number of f(a)-f(b) / a - b which are divisible by p^k where p > 10^{100}, which implies that equality holds. This also means that equality holds for every inequality we added up, giving us S(f(a)-f(b)) = S(a-b). A simple and boring induction will tell us that for a fixed a,b. f(a) - f(b) = k(a-b), in particular f(n) =kn + f(0), where k is some rational number made up of primes less than 10^{100}. Let L(n) denote the product of small primes dividing n. Let w(n) be the maximal v_p(n) where p is a small prime and let p_n denote this prime. Then we have v_{p_{f(i)-f(j)}} (f(i) - f(j)) \geq \frac{1}{10^{100}} \log_{10^{100}} L(f(i)-f(j))since there are at most 10^{100} small primes. Now, if j is small compared to i, we have that \frac{f(i)-f(j)}{i-j} is roughly equal to \frac{f(i)}{i}. We aim to show that for any n, \frac{f(n)-f(0)}{n} = k is bounded. Assume otherwise, then we have that \frac{f(i)}{i} is unbounded and hence there exists arbitrarily large i such that \frac{f(i) - f(j)}{i - j} is large too where j ranges from 0,1,2,\ldots,10^{100}. Note that \frac{f(i)-f(j)}{i-j} is at least L(f(i) - f(j)) and hence the RHS of our inequality can be made to be as large as we want. Let it be at least C for some real. Then since there are at most 10^{100} - 1 small primes, by pigeonhole, we must have 0 < j_1,j_2, < 10^{100} such that p_{f(i) -f(j_1)} = p_{f(i) - f(j_2)}. p_{f(i)-f(j)}^C | f(i) - f(j_1) , f(i) - f(j_2) \implies p_{f(i)-f(j)}^C | f(j_1) - f(j_2)but C can be made to grow as large as we want while f(j_1) - f(j_2) is a non-zero fixed value - a contradiction. Hence \frac{f(i)}{i} is bounded and so is k. Now take i = p where p is some large prime. Then f(p) - f(0) = kp where k is a rational number made up of small primes but if p is larger than 10^{100}, the denominator of k must be just 1 and hence k is integer. Since k is bounded above, it takes on only finitely many values and hence by pigeonhole, we must have an infinite sequence a_1,a_2,\ldots such that f(a_i) = ka_i + f(0) for some fixed integer k. Now, for any natural j, let f(j) = kj + c where c is an integer since f(j),kj are integers. Then we have that f(a_i) - f(j), a_i - j share large prime factors and hence k(a_i - j) + c , k(a_i - j) must also share large prime factors. But these primes must divide c and hence if p > c, it cannot divide both of them. Hence we have that kx + c, kx are made up of finitely many primes for infinitely many x and hence the equation x-y = c has infinitely many solutions where the prime factors of a,b belong to some finite set. Rewrite each such solution into the form ax^3 - by^3 = c where a,b are cube-free. There are only finitely many such forms and hence by pigeonhole one of them has infinitely many solutions - a contradiction to Thue's theorem. Finally, we have that f(n) = kn + c for some integers k,c. Easy to check as long as k have small prime factors, it will satisfy the conditions.
05.08.2016 23:39
Let U(n)=\mho(n) and V(n) = \prod_{p_i>10^{100}} p_i^{a_i}. We claim that V(f(a)-f(b))=V(a-b). Let S=\{q_1,q_2,...\} with q_1<q_2<... such that q_i=p_i^{a} where p_i is a prime greater than 10^{100} and a is a positive integer. We will prove, by strong induction on i, that q_i\mid a-b\iff q_i\mid f(a)-f(b). For the base case, consider the numbers f(a), f(a+1),..., f(a+q_1). By the Pigeonhole principle, some two are equal \pmod{q_1}. Suppose f(x)\equiv f(y)\pmod{q_1} such that 0<|x-y|<q_1. Note that 1\le U(f(x)-f(y)) \le U(x-y) = 0, contradiction! Therefore, it follows that f(a)\equiv f(a+q_1)\pmod{q_1}, and that f(a)\not\equiv f(a+j)\pmod{q_1} where 0<j<q_1. This proves the base case. For the inductive step, suppose the claim is true for q_j for j<i. We prove it holds for q_i. Consider f(a),f(a+1),..., f(a+q_i). Once again, by Pigeonhole some two are equal \pmod{q_i}. Suppose f(x)\equiv f(y)\pmod{q_i} and 0<|x-y|<q_i. Note by the inductive hypothesis, if q_j\mid x-y then q_j\mid f(x)-f(y) since x-y < q_i. On the other hand, q_i\mid f(x)-f(y) as well, while q_i\nmid x-y. Thus S(f(x)-f(y))\ge S(x-y)+1, contradiction! Therefore f(a)\equiv f(a+q_i)\pmod{q_i} and f(a)\not\equiv f(a+j)\pmod{q_i} for 0<j<q_i. This completes the inductive step. It follows from our induction that V(a-b) = V(f(a)-f(b)). WLOG f(0) = 0. Next, we claim that \frac{fx)}{x} is bounded; in other words, there is an absolute constant K such that \frac{f(x)}{x}\le K. Suppose that it wasn't bounded; in particular, the fraction was arbitrarily large. Let Q=\prod_{p_i < 10^{100}} p_i. Note that since \frac{f(x)}{x} is unbounded, so must the fraction \frac{f(Q^n)}{Q^n}. For n large, note that \frac{f(Q^n)}{Q^n}\approx \frac{f(Q^n)-f(j)}{Q^n-j}. We also have that \frac{f(Q^n)-f(j)}{Q^n-j} = \frac{g(n, j)}{j} where V(g(n, j)) = 1 since \frac{f(Q^n)-f(j)}{g(n,j)} = V(f(Q^n)-f(j)) = V(Q^n-j) = \frac{Q^n-j}{j}. Because this tends to infinity as n grows large, there exists a prime p_{n,j}<10^{100} such that v_{p_{n,j}}(g(n, j))\rightarrow\infty as n\rightarrow\infty. Doing this for enough small j with V(j) = 1 (say all j between 0 and q_1) gives us p_{n,j} = p_{n, j'} by Pigeonhole. In particular, for n large there is a prime p such that p\mid g(n,j) and p\mid g(n, j'). On the other hand, v_p(g(n,j)) and v_p(g(n, j')) can be arbitrarily large. Since g(n,j)\mid f(Q^n)-f(j), this means that v_p(f(Q^n)-f(j)) and v_p(f(Q^n)-f(j')) is arbitrarily large. Thus v_p(f(j)-f(j')) is arbitrarily large, which is an obvious contradiction because |j-j'|<q_1. Thus \frac{f(x)}{x} is bounded. Note that \frac{f(q_i)}{q_i} is always an integer. Thus let R=\max \left(\frac{f(q_i)}{q_i}\right) with V(R) = 1. We claim that f(x) = Rx for all x. First, we will show that f(Q^n) = R\cdot Q^n for n sufficiently large. Note that no prime less than 10^{100} can divide Q^n-q_i. Thus V(f(Q^n)-f(q_i)) = V(Q^n-q_i) = Q^n-q_i. Since f(q_i) = R\cdot q_i, we have f(Q^n) - R\cdot q_i = k(Q^n-q_i). Thus f(Q^n) = k\cdot Q^n + (R-k)\cdot q_i where k is a bounded integer. Suppose R>k. We claim that for n large enough, V(k\cdot Q^n+(R-k)\cdot q_i)>1 when R\neq k. First define -V(x) = V(-x). Note that k\cdot Q^n+(R-k)\cdot q_i = \frac{R-k}{V(R-k)}\left[\frac{k\cdot Q^n}{\left(\frac{R-k}{V(R-k)}\right)} + q_i\cdot V(R-k)\right] = \frac{R-k}{V(R-k)}\cdot MFor n sufficiently large, Q\mid \frac{Q^n}{(R-k)/V(R-k)} for all k since k is bounded. Therefore Q\nmid M. This means that V(M) = M>1, and thus V(f(Q^n)) > 1, contradiction! Hence for n large enough, f(Q^n) = R\cdot Q^n. Finally, we will show that f(x) = Rx for all x. Take x = V(x)\cdot x'. For n large, V(Q^n-x) = V(Q^n - V(x)\cdot x') = V\left(\frac{Q^n}{x'} - V(x)\right) = \frac{Q^n}{x'} - V(x) = V(f(Q^n) - f(x)). Thus f(Q^n)-f(x) = R\cdot Q^n - f(x) = k\left(\frac{Q^n}{x'}-V(x)\right)Taking mod \frac{Q^n}{x'} gives us f(x)\equiv k\cdot V(x). By taking n large and noting that k is bounded, we have f(x) = k\cdot V(x). Subbing in for f(x), we get R\cdot Q^n = k\cdot Q^n/x'. Thus k = Rx', so f(x) = Rx'V(x) = Rx, as desired. Since we WLOGed that f(0) = 0, it follows all solutions are of form \boxed{f(x) = Rx+c} with R an integer and V(R) = 1. \square
02.11.2019 11:30
This question shows that the hypothesis can be significantly weakened (to f is a bijection modulo \mathbb{Z}/p\mathbb{Z} for every prime p > 10^{100}). (The above solutions show that the hypothesis of the original problem is equivalent to f being a bijection modulo \mathbb{Z}/p^e\mathbb{Z} for all such p and any e, which is stronger.)
02.01.2020 13:07
Finally solved this really beautiful and difficult problem. The answer is f(x) = ax+b where a,b are integers such that a>0 and \mho(a) = 0. It's obvious that this solution works. The main point is to show that these are all solutions. WLOG f(0)=0 by shifting. First we setting up some notation. Let M=10^{100}. Call a positive integer tasty if and only if all of its prime factors are larger than M. Let T(n) denote the largest tasty divisor of n. We divide the solution into three parts. Part A: Strengthening the condition Claim: For any tasty integer t, t divides f(a)-f(b) if and only if t divides a-b. In particular, T(f(a)-f(b)) = T(a-b). Proof: We induct on the size of t with the trivial base case t=1. Suppose that the claim is true for any tasty number t' < t. Consider t consecutive integers f(a+1), f(a+2),\hdots f(a+t).If two of them, say f(r) and f(r+d) have the same residue modulo t, then f(r+d)-f(r) divides \mathrm{lcm}(t, T(d)) by induction hypothesis. Therefore by the functional equation, \mho(d) \geq \mho(f(r+d)-f(r)) \geq \mho(\mathrm{lcm}(t,T(d)) \geq \mho(T(d)) = \mho(d)Hence all inequalities must be equality. Since \mathrm{lcm}(t,T(d)) and T(d) are both large, we get t\mid T(d) which contradicts the induction hypothesis. After a long discussion, we get that f(a+1), f(a+2),\hdots f(a+t)is complete residue system modulo t. Similarly, we get f(a), f(a+1), \hdots, f(a+t-1) is complete residue system modulo t. Hence by taking difference, t\mid f(a+t)-f(t). This is enough to conclude the induction. Part B: Proving that f is bounded by linear function (in \mathbb{Z}^+) This is the hardest part (but somehow shortest). Fix a positive integer n>M^{2020}. Let K = \mathrm{lcm}_{1\leq i < j \leq M} (f(j)-f(i)). For each prime p<M, we call the index \in\{1,2,\hdots,M\} p-murine if and only if \nu_p(f(n)-f(i)) > \nu_p(K). Claim: For each prime p<M, there exists at most one p-murine index. Proof: Indeed, if i,j are both p-murine, then p^{\nu_p(K)+1}\mid f(i)-f(j) which gives contradiction. \blacksquare By the claim, there exists an index k which is not p-murine for any prime p<M. Now we are happy since f(n) - f(k) = T(n-k)\cdot \prod_{p<M} p^{\nu_p(K)} < Kn.so f(n) < Kn+f(M). Part C: Conclusion By Part B, let f(n) < Kn for all positive integer n. Take a prime q > K^{2020}. First, we show a weaker result. Claim: There exists constant c such that \mho(c)=0 and f(n)=cn for any tasty n\equiv 1\pmod q. Proof: By Dirichlet, take a prime p\equiv 1\pmod q and let f(p)=cp for c<K. Suppose that f(n) = c'n where c'\ne c. Then we have q \mid n-p \text{ and } q\mid f(n)-f(p) = c'n - cpthus q\mid (c-c')p which is contradiction since p>q>c. \blacksquare Now we take any other prime r>\max\{M,n\}. By CRT and Dirichlet, there exist a prime p such that p\equiv 1\pmod q and p\equiv n\pmod r. Then note that r\mid n-p \implies r\mid f(n)-cp \implies r\mid f(n)-cnsince this works for any n and any sufficiently large prime r, we get f(n)=cn as desired.
29.01.2020 14:49
CantonMathGuy wrote: This question shows that the hypothesis can be significantly weakened (to f is a bijection modulo \mathbb{Z}/p\mathbb{Z} for every prime p > 10^{100}). (The above solutions show that the hypothesis of the original problem is equivalent to f being a bijection modulo \mathbb{Z}/p^e\mathbb{Z} for all such p and any e, which is stronger.) Can you provide me an article which proves the S unit equation has only finitely many solutions?
24.11.2021 16:37
CantonMathGuy wrote: For every positive integer n with prime factorization n = \prod_{i = 1}^{k} p_i^{\alpha_i}, define \mho(n) = \sum_{i: \; p_i > 10^{100}} \alpha_i.That is, \mho(n) is the number of prime factors of n greater than 10^{100}, counted with multiplicity. Find all strictly increasing functions f: \mathbb{Z} \to \mathbb{Z} such that \mho(f(a) - f(b)) \le \mho(a - b) \quad \text{for all integers } a \text{ and } b \text{ with } a > b. Proposed by Rodrigo Sanches Angelo, Brazil Excellent problem! Solved with small help from MathLuis. Solution Set The solution set to this functional inequality is f(n)=kn+cwhere k is a positive integer such that \mho(k)=0 and c is an integral constant. Note. Since f is a solution implies that f+c is a solution too, we shall assume that f(0)=0. Notations For brevity, let C denote 10^{100}. We also say that a positive integer s is superfluous if all it's prime divisors are strictly larger than C. Finally, let S(n) denote the largest superfluous divisor of n (if there exists one). Solution The problem is solved in three key claims. Claim 1. S(a-b)=S(f(a)-f(b)). Proof. Let S(a-b)=s. We need to show that s\mid f(x+s)-f(x) for all integers x. We begin by proving that the set \{f(x+1),f(x+2),\hdots,f(x+s)\}forms a complete residue system modulo s. Assume not. Then there exists 1\leq i<j\leq s so that f(x+i) and f(x+j) leave the same remainder upon division by s. Then, as \mho(f(x+j)-f(x+i))\leq\mho(j-i)we have s\mid j-i, a contradiction. Therefore, the desired set forms a complete residue system. Analogously, the set \{f(x),f(x+1),\hdots,f(x+s-1)\}forms a residue system too, implying that s\mid f(x+s)-f(x) as desired. \blacksquare Note. Define \omega_{C}(n) to be the product of all prime divisors of n which are strictly greater than C. Then we have \omega_{C}(f(a))=\omega_{C}(a). Claim 2. f is bounded above by a linear function in \mathbb{N}. Proof. Let \Omega=\prod_{1\leq j<i\leq C}(f(i)-f(j)) and let n>C be a positive integer. Then note that the number of integers 1\leq k\leq C such that p^{\nu_p(\Omega)+1}\mid f(n)-f(k) for each prime p is at most one, because if there were two, then p^{\nu_p(\Omega)+1} would divide f(i)-f(j), contradicting the definition of \Omega. And since \pi(\Omega)<\Omega, there exists a positive integer 1\leq m\leq C so that f(n)-f(m) is not divisible by p^{\nu_p(\Omega)+1} for all primes p<C. Also, let f(a)-f(b)=S(a-b)(x_{a,b}). Then from what we got above, x_{n,m}\leq\prod_{p<C}p^{\nu_p(\Omega)}<\Omegaand also S(n-m)<n, implying that f(n)<\Omega n+f(m)\leq n+f(C). Therefore, we see that for all n>C, f is bounded above by a linear function. Also since f is strictly increasing, there exists a finitely large constant \mu for which f(n)<\mu n for all n\in\mathbb{N}, as claimed. \blacksquare Claim 3. f(n)=kn for all positive integers n. Proof. From the note of claim 1, if a is a square-free superfluous number, then a\mid f(a). Now, let S be the set of all superfluous primes p congruent to 1 modulo another prime q>\mu. Then, from claim 2, there exists a positive integer k<\mu so that f(p)=kp for infinitely many primes p in S. Call this infinite set T. Assume that for some \alpha\in S, f(\alpha)=k_0\alpha where k_0\neq k. Then, we see that q\mid (k-k_0)pgiving us a contradiction, implying that all primes p\equiv1\pmod{q} are in T. Therefore, by CRT, there exists a prime p\in S such that p\equiv n\pmod{r} where r is another superfluous prime. From this, we see that r\mid p-n\implies~r\mid f(p)-f(n)\implies~r\mid f(n)-knimplying that f(n)=kn for all positive integers n as desired. \blacksquare Plugging this back into the original inequality, we see that \mho(k)=0, yielding us the solutions presented above, solving the problem.
I would like to thank CANBANKAN for nudging us into the first claim!
26.11.2021 20:52
CantonMathGuy wrote: For every positive integer n with prime factorization n = \prod_{i = 1}^{k} p_i^{\alpha_i}, define \mho(n) = \sum_{i: \; p_i > 10^{100}} \alpha_i.That is, \mho(n) is the number of prime factors of n greater than 10^{100}, counted with multiplicity. Find all strictly increasing functions f: \mathbb{Z} \to \mathbb{Z} such that \mho(f(a) - f(b)) \le \mho(a - b) \quad \text{for all integers } a \text{ and } b \text{ with } a > b. Proposed by Rodrigo Sanches Angelo, Brazil Solution by CANBANKAN which he solved two years ago Let C=10^{100}. We split this into three parts: Part 1: Let L(i)=\prod_{i: ; p_i > C} p_i^{e_i}. Claim: L(a-b)=L(f(a)-f(b)) Proof We proceed by induction. Call a number large if all of its prime divisors are greater than C. The smallest large number greater than C must be prime, call p0. For any n, consider f(i){i=n}^{n+p_0}. By pigeonhole principle, two are congruent modulo p_0. If they are not (n,n+p_0), then their difference is less than p0, contradicting the condition in the problem. We proceed by strong induction. Assume all large numbers less than x, which is also a large number, satisfy the above property. Consider f(i){i=n}^{n+x}. By pigeonhole principle, two are congruent modulo x. If they are not (n,n+x), then their difference, d is less than x. By Inductive Hypothesis, L(d)=d, but x>d, contradiction. The second step is the key to solving this problem (now having bounded big primes we bound small primes): I claim there exist a constant c such that f(x)\le cx for all x. For a prime p<C, let X(p)=max_{j<i<C} \nu_p(f(i)-f(j)). If there exist 2 indices, i,j such that \nu_p(f(n)-f(i)), \nu_p(f(n)-f(j))>X(p) then \nu_p(f(i)-f(j))>X(p) contradiction. Hence we can see there f(n)-f(j)\le L(n-j)\cdot \prod{p<M} p^{X(p)} for all p<C. To finish, we can see that f(p)=c_p\cdot p for all large primes p. Let c st f(x)\le cx. Suppose the difference of two primes much greater than c, and contain another big prime factor. We then quickly see that c_p=c_q. We can fill big primes this way. For numbers much smaller, by dirichlet, we're done.
17.06.2022 15:09
We claim that the functions that satisfy are f(n)=nx+y where x>0 and V(x)=0. Clearly this works. WLOG f(0)=0. Call any integer huge if it's prime divisors are larger than 10^{100}. Let L(x) be the largest huge divisor of x. Lemma 1: L(u-v)=L(f(u)-f(v)) for all u>v. Proof. We show, by induction, that any huge x\mid u-v iff x\mid f(u)-f(v), this is essentially the claim. Since it's true for x=1, assume it's true for all x_0<x. Notice that in the sequence f(u+1), f(u+2), \dots ,f(u+x) if f(v)\equiv f(v+y)\pmod{x} then f(v+y)-f(v)\mid lcm(L(y),x). Therefore V(y)=V(L(y))=V(lcm (L(y),x))=V(f(v+y)-f(v)). This implies x\mid f(y), absurd. Thus our sequence is a complete residue system mod x. Our initial claim easily follows. \blacksquare Lemma 2: \forall n we have f(n)\leq nx. Proof. Let x=100^{100^{100}}. And let X=lcm(f(u)-f(v)) with not huge non negative u>v. If for any small prime we have \nu_p(X)< \nu_p(f(x)-f(u)) and \nu_p(X)< \nu_p(f(x)-f(v)). Then \nu_p (f(u)-f(v))> \nu_p(X), absurd. So this is true for only one, say u. It follows that f(x)- f(v)=\prod p \cdot L(x-v)< xX. This finishes the lemma. \blacksquare Lemma 3: f(n)=nx for all n. Proof. For any prime p> 10^{100^{100}} we have f(q)=cq for any prime q\equiv 1\pmod p with c not huge. Assume that f(x)=dx with c\neq d. Then we force p\mid cp-dp, absurd. By Chinese Remainder Theorem, exists x\equiv 1\pmod {10^{100^{100}}} and y\equiv x\pmod z. Then f(y)\equiv f(x)=cx\equiv cy\pmod{z}. The claim follows and we are done with the problem by shifting back. \blacksquare
19.08.2022 01:58
What an adventure! Let s(n) = \prod_{p_i < 10^{100}} p_i^{\alpha_i}. By inducting up over all numbers such that s(n) = 1, it is easy to see that any n consecutive numbers always form a complete residue set, hence it follows that the condition is equivalent to the strong condition that v_p(f(a)-f(b)) = v_p(a-b) for all p > 10^{100}. WLOG f(0) = 0. Now, since there is a finite number of solutions x, y such that s(x) = 1, s(y) = 1 and x-y = 1 by Kobayashi's theorem, it follows that \frac{f(n)}{n} when f(n) = 1 is bounded above by the maximum value of y when n is of the form \left(\prod_{p_i < 10^{100}} p_i\right)^k+1, since in those cases it must be that s\left(\frac{f(n}{n}\right) = \frac{f(n)}{n} from the condition on 0, n and 1, n to obtain the desired result since s(n)=1, s(n-1) = n-1. Now consider the set S of numbers congruent to -1 \pmod {\prod_{p_i < 10^{100}} p_i}. It follows from the previous result that \frac{f(n)}{n} is bounded above for arbitrary n since all elements of S satisfy the previous result and S is exponentially spaced. We loosen the strong condition to be v_p(f(a)-f(b)) \geq v_p(a-b), then it follows that the set of solutions forms a \mathbb{Z}-module, so we can mod out {x \choose 0}, {x \choose 1}, {x \choose 2} so that f(0) = f(1) = f(2) = 0 while losing the increasing condition but bounding below by a quadratic. Then it follows that for all s \in S, \frac{s(s-1)(s-2)}{6} \mid f(s), so since f(s) is bounded linearly and since S is evenly spaced, it follows that f(s) = 0 for all large s. Thus returning to the original f, it follows that f is quadratic over large S. By Schur's theorem, we reach contradiction if \frac{f(x)}{x} is nonconstant, so it follows that f is linear over large S. Now, inducting down on the residues modulo \prod_{p_i < 10^{100}} p_i, it follows by Dirichlet's theorem that f(n) is linear over all sufficiently large n. Hence by Dirichlet's theorem again, it follows that f(n) is linear over all integers, so it is clear that f(n) = cn for c > 0 such that s(c) = c is the solution set. Now undoing the f(0) = 0 condition, the answer is f(n) = cn+d for c \in \mathbb{N} such that s(c) = c, and d \in \mathbb{Z}.
19.05.2023 08:26
Solved with starchan. First, we actually claim that v_p(f(a) - f(b)) = v_p(a-b) for all primes p > 10^{100} and distinct integers a and b. The proof is by induction. Let S be the set of all prime powers of big primes and enumerate them in ascending order as s_1, s_2, \cdots. Induct to claim that s \mid f(a) - f(b) \iff s \mid a-b for any s \in S. Suppose we're at s_m = p^k now. If k = 1, then consider f(1), f(2), \cdots, f(p), they must all be distinct modulo p since i - j for i,j \in \{1,2,\cdots,p\} has only prime power divisors smaller than p by induction and for those, the v_q matches exactly. Similarly f(0), f(2), \cdots, f(p-1) is a complete residue class. So p \mid f(p) - f(0), and in general p \mid f(a) - f(b) \iff p \mid a-b. If k \geqslant 2, using also the fact that the statement is true for p, p^2, \cdots, p^{k-1}, a similar argument works. Now, shift f to assume f(0) = 0, so v_p(f(n)) = v_p(n) for all big primes p, taking a = n and b = 0. Next, we claim that if f(n) < Cn for some positive constant C, then we are done. Pick a sufficiently large prime p and pick a prime q \equiv 1 \bmod p by Dirichlet (or just cyclotomic polynomials). Since f(q) has big part only q, it must equal f(q) = kq for some k with only small prime divisors. Now pick some integer n \equiv 1 \bmod p. Then p \mid n-q and so p \mid f(n) - f(q). Now, if n has all big prime factors, then f(n) = \ell n for some integer \ell. So p \mid \ell n - kq \equiv q(\ell - k) \implies p \mid \ell - k. But since \ell and k are bounded above by C, picking p > \max(C,10^{100}) causes a contradiction unless \ell = k. So we actually get that for any number n \equiv 1 \bmod p with all big prime divisors, f(n) = kn. To extend this to all numbers, fix a number n, and pick a big prime q. We would like to find a b such that q \mid n-b and so q \mid f(n) - f(b). So we want b to be a big number congruent to 1 \bmod p and itself have big factors. But we can just pick b to be a prime, by Dirichlet, requiring b \equiv n \bmod q and b \equiv 1 \bmod p. Then we get that q \mid f(n) - f(b) = f(n) - kb \equiv f(n) - kn. Since q can be made arbitrarily large, this means that f(n) = kn for all n. So it suffices to show the existence of such a C. Let M = \pi(10^{100}) + 1 and let Z = \prod_{i > j} (f(i) - f(j)) for i,j < M. Since f is strictly increasing, note that this is positive. I claim now that f(n) < Zn + \max(f(1), f(2), \cdots, f(M)) for all n. To prove this, assume not, then f(n) - f(i) > Zn for all i = 1,2,\cdots,M. Therefore, for each i, there must be a small prime, say p_i such that v_{p_i}(f(n) - f(i)) > v_p(Z). But since M is more than the number of small primes, this forces that by PHP, some two indices exist such that p_i = p_j = p, say. But then v_p(Z) \geqslant v_p(f(i) - f(j)) = v_p(f(n) - f(i) - (f(n) - f(j))) \geqslant \min(v_p(f(n) - f(i)), v_p(f(n) - f(j))) > v_p(Z), a contradiction. Therefore, we do get the existence of such a C, and by the middle part of the solution, we obtain that f(n) = kn for some n with k having all small prime factors. Since we had shifted earlier, we can shift back to get the solution set to be f(n) = kn + \ell for some integer \ell and integer k such that all prime factors of k are smaller than 10^{100}, and these functions clearly work, so we're done. \blacksquare
09.10.2023 04:32
Beautiful problem! This is a very good equality problem that features classic functional NT ideas as well. Smooth f so that f(0)=0. We claim that f(n)=kn for any natural k such that \mho(k)=0 is the solution set. Let \varepsilon(n) denote the largest divisor of n such that all of its prime divisors are at least 10^{100}. Lemma: For any (a, b) with a > b, \varepsilon(f(a)-f(b))=\varepsilon(a-b). Proof. Look at the set S_a = \{f(a+1), f(a+2), \dots, f(a+k)\} of consecutive terms. We will show that for any positive integer k with all prime divisors at least 10^{100}, k \mid a - b iff k \mid f(a) - f(b), which is sufficient. I contend that S_a is a complete residue system modulo k. Assume not. Then there exists two elements f(a+r), f(a+s) of S_a such that r>s and they are congruent modulo k. Note that \mho(f(a+r)-f(a+s)) \le \mho(r-s) by the problem condition, but this implies that k \mid r-s, which is impossible. Thus S_a is a complete residue system modulo k. Now shift S_a by one element to S_{a+1}, and since both sets are complete residue systems modulo k we have k \mid f(a+k+1)-f(a+1), and we conclude. Claim: f has an upper bound given by a linear function over the naturals. Proof. Let M = \operatorname{lcm}_{(i, j) \in [1, 10^{100}]^2, i>j} \: [f(i)-f(j)]. Note that by the prior lemma, \frac{f(a)-f(b)}{\varepsilon(a-b)} = \frac{f(a)-f(b)}{\varepsilon(f(a)-f(b))} < M, and since \varepsilon(a-b) \le a-b, we have f(a)-f(b) \le (a-b)M. Thus f(n) \le M \cdot n for all n \in \mathbb{N}, as required. Claim: For some fixed k with \mho(k)=0, f(n)=kn for all natural n. Proof. Call a prime huge if it is at least 10^{100}. Fix a huge prime p. Then for any prime q \equiv 1\pmod{p}, we have f(q)=kq for some constant k by the second claim. Suppose that for some huge prime x \equiv 1 \pmod{p}, f(x)=k'x for some k' \neq k. Then p \mid (k-k')q for all q \equiv 1\pmod{p}, a contradiction. For each n \in \mathbb{N}, there exists a huge prime p such that p-n has a huge prime divisor t. But then t \mid p-n implies t \mid f(n)-kn, so f(n)=kn. Now \mho(k(a-b)) \le \mho(a-b) whenever a>b, but this means that \mho(k)=0, as desired. It is easy to check that all k with \mho(k)=0 produce valid solutions, and we conclude. Edit: the above solution shows the desired results for naturals, but it works out in general since letting n be any integer instead of a natural number does not break any logic. In particular, the solution extends very easily to integers.
14.08.2024 02:23
We claim the only solutions are of the form f(a)=kx+c where \Omega(k)=0. It suffices to show the following claim: Quote: Let f:\mathbb{Z} \rightarrow \mathbb{Z} be a strictly increasing function such that f(0)=0 and \Omega(f(a)-f(b))\le \Omega(a-b)for all a>b. Then, there exists k\in \mathbb{Z}_{>0} with \mho(k)=0 such that f(x)\equiv kx. Let \alpha be the product of every prime under 10^{100}. For a positive integer n with prime factorization n = \prod_{i = 1}^{k} p_i^{\alpha_i}, let \omega(n) = \prod_{i: \; p_i > 10^{100}} p_i^{\alpha_i}. Claim: Let n=p^r for some prime p>10^{100}. Then, for all x, f(x), f(x+1), \dots, f(x+n-1) covers every residue class mod n once, which implies that f(x) \pmod{n} only depends on x \pmod{n}. Proof: It suffices to show this claim for x=0. We will prove this by induction on n. Assume toward a contradiction that for some 0\le a, b < n, f(a) \equiv f(b) \pmod{n}. Let \omega(f(a)-f(b)) = p_1^{a_1}p_2^{a_2}\dots p_m^{a_m} where p_1,\dots, p_m are distinct primes. Then, p_1^{a_1}, p_2^{a_2}, \dots, p_m^{a_m} < n.So, by induction, f(a) \equiv f(b) \pmod{p_i^{a_i}} for all 1\le i\le m. Therefore, \text{lcm}(n, p_1^{a_1}p_2^{a_2}\dots p_m^{a_m})\mid f(a) - f(b). So, \mho(f(a) - f(b)) \ge \mho(\text{lcm}(n, p_1^{a_1}p_2^{a_2}\dots p_m^{a_m})) > \mho(p_1^{a_1}p_2^{a_2}\dots p_m^{a_m}) = \mho(a-b),a contradiction. Claim: There exists a constant C such that for sufficiently high x, f(x) \le Cx. Proof: Let p_1, p_2, \dots, p_m be the primes under 10^{100}. Let x_i be the maximum value of \nu_{p_i}(f(a)-f(b)) for 0\le b<a\le m. Let M be the maximum value of f(a) for 0\le a \le m. Let n>M be a positive integer. Assume toward a contradiction that \nu_{p_i}(f(n)-f(a)), \nu_{p_i}(f(n)-f(b)) > x_i for 0\le b<a\le m. Then, p^{x_i+1}\mid f(a)-f(b), a contradiction. So, \nu_{p_i}(f(n)-f(a))> x_i for at most one value 0\le a \le m. So, for some 0\le a \le m, \nu_{p_i}(f(n)-f(a)) \le x_i for all i. So, f(n)-f(a) \le p_1^{x_1}\dots p_m^{x_m} \omega(n-a) \le p_1^{x_1}\dots p_m^{x_m}nf(n) \le p_1^{x_1}\dots p_m^{x_m}n + M \le (p_1^{x_1}\dots p_m^{x_m}+1)n. Claim: There exists k \in \mathbb{Z}_{>0} such that for sufficiently high x, f(\alpha x + 1) = k(\alpha x + 1). Proof: We have previously shown \omega(f(\alpha x + 1)) = \omega(\alpha x + 1). Therefore, f(\alpha x + 1) is an integer multiple of \alpha x + 1. Let f(\alpha x + 1) = g(x)(\alpha x + 1). Then, g(x) is bounded. Let k be the highest positive integer such that g(x)=k for arbitrarily high x. For sufficiently high x, (k-1)(\alpha (x+1)+1) < k(\alpha x + 1). So, after that point, g(x) cannot go from being at least k to being below k. So, for sufficiently high x, g(x) = k. Claim: For all x, f(x) = kx. Proof: Let x be a positive integer. Then, for sufficiently high y, \omega(\alpha y + 1 - x) = \omega(f(\alpha y + 1) - f(x))\omega(\alpha y + 1 - x) \mid k(\alpha y + 1) - f(x)\omega(\alpha y + 1 - x) \mid kx - f(x).Because \omega(\alpha y + 1 - x) can be arbitrarily high, f(x)=kx.