Find all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ such that for any two positive integers $m,n$ we have : $$f(n)+1400m^2|n^2+f(f(m))$$
Problem
Source: Iranian TST 2021, second exam day 1, problem 2
Tags: function, number theory
20.05.2021 19:13
Here is my solution Let: $$P(m,n)=f(n)+1400m^2|n^2+f(f(m))$$we have from $P(n,1)$ that $$f(n) \le n^2+f(f(1))-1400$$Lets have : $$g(m,n)(f(n)+1400m^2)=n^2+f(f(m))$$so it is trivial that : $$f(a)+1400m^2 | a^2-n^2+g(m,n)(f(n)-f(a))$$so we have : $$(f(a)+1400m^2)(f(n)+1400m^2) \le (a^2-n^2)(f(n)+1400m^2)+n^2+f(m)^2+f(f(1))-1400$$Which gives that there are $a,b$ such that : $$m^2+f(f(1))-1400 \ge f(m) \ge am^2+b$$Now we have: $$g(m,n)=\frac{1+\frac{f(f(m))}{n^2}}{\frac{f(n)}{n^2}+\frac{1400m^2}{n^2}}$$so for big enough $n$ we have : $$g(m,n)=[\frac{n^2}{f(n)}]$$so we have : $$[\frac{n^2}{f(n)}]f(n)+1400[\frac{n^2}{f(n)}]m^2 \le n^2+f(f(m))$$so for big enough $n$ we have $$f(f(1))-1400[\frac{n^2}{f(n)}]=f(f(2))-1400[\frac{n^2}{f(n)}]4$$so this means for big enough $n$ we have$ [\frac{n^2}{f(n)}]$ is a fixed positive integer. so $$f(f(m))-1400[\frac{n^2}{f(n)}]m^2=C$$which is clearly false. since $$f(f(m))= O(m^4)$$so $$f(f(m))-1400[\frac{n^2}{f(n)}]m^2=O(m^4)$$so it cant be constant.
20.05.2021 19:30
where can I learn about $O(n)$ ?
20.05.2021 19:59
Mr.C wrote: so it is trivial that : $$f(a)+1400m^2 | a^2-n^2+g(m,n)(f(n)-f(a))$$so we have : $$(f(a)+1400m^2)(f(n)+1400m^2) \le (a^2-n^2)(f(n)+1400m^2)+n^2+f(m)^2+f(f(1))-1400$$ How to you get inequality directly from the divisibility? What if $RHS$ is negative or even $0$ ? Also $f(n)=f(a)$ could happen.
20.05.2021 20:07
NTstrucker wrote: Mr.C wrote: so it is trivial that : $$f(a)+1400m^2 | a^2-n^2+g(m,n)(f(n)-f(a))$$so we have : $$(f(a)+1400m^2)(f(n)+1400m^2) \le (a^2-n^2)(f(n)+1400m^2)+n^2+f(m)^2+f(f(1))-1400$$ How to you get inequality directly from the divisibility? What if $RHS$ is negative or even $0$ ? Also $f(n)=f(a)$ could happen. It was trivial enough that i didnt mention it. if $f(a)=f(b)$ we have a contradiction by looking at $$p(a+b,a),p(a+b,b)$$also if it is negative it wont effect us. since we take an absolute value and we only care about the constants that clearly exist
20.05.2021 21:34
How do you exclude the case $RHS=0$ ?
20.05.2021 21:50
NTstrucker wrote: How do you exclude the case $RHS=0$ ? There exists $a,n$ such that $$a^2-n^2$$is not divisible by $f(n)-f(a)$ which is enough for us it is getting crowded here if you have other questions or think that i am miss taking in somewhere please write me a dm
24.05.2021 18:22
Solved with p_square, L567 Let $P(m,n)$ denote the given assertion. $f(n)+1400m^2 \mid n^2 + f(f(m))$ $P(n,1) \Longrightarrow f(n)+1400 \mid n^2+f(f(1)) \Longrightarrow f(n) \leq n^2+f(f(1))-1400$ - (1) $P(f(n),n) \Longrightarrow f(f(n))+1400n^2 \mid f(n)^2+f(f(n)) \Longrightarrow f(n) \geq \sqrt{1400}n$ - (2) Substituting $n=f(m)$ in (1), we get $f(f(m)) \leq f(m)^2+f(f(1))-1400 \leq O(m^4)$-(3) [by (1)] Now let $q(m,n)=\frac{n^2+f(f(m))}{f(n)+1400m^2}$. Substituting $n=m^2$, we get : $q(m,m^2)=\frac{n^2+f(f(m))}{f(n)+1400m^2}=\frac{n^2+f(f(m))}{f(m^2)+1400n}$. Simplifying, we get $n^2-1400q(m,m^2)n+q(m,m^2)f(m^2)-f(f(m))=0$. So now, consider the quadratic polynomial: $$P(x)=x^2-1400q(m,m^2)x+q(m,m^2)f(m^2)-f(f(m))=0$$ From above we know $x=n$ is a root of $P(x)$. Let $u$ be the other root. By Vieta's formulae: $m^2+u=1400q(m,m^2)$ and $m^2u=q(m,m^2)f(m^2)-f(f(m))$. Now suppose $f(n)=O(n^{\alpha})$. By (1),(2), we know $1 \leq \alpha \leq 2$. So $q(m,m^2) \leq O(m^{4-2{\alpha}})$ by (1),(2) and (3). Now if $\alpha >1, 1400 q(m,m^2) < O(m^2)$. So $u=1400q(m,m^2)-m^2<0 \Longrightarrow m^2u<0 \Longrightarrow q(m,m^2)f(m^2)-f(f(m))<0 \Longrightarrow \frac{m^4f(m^2)-1400m^2f(f(m))}{f(m^2)+1400m^2} \leq 0 \Longrightarrow m^2f(m^2) \leq f(f(m))$. But now we have $m^2f(m^2) \geq O(m^{2+2{\alpha}})$ and $f(f(m)) \leq O(m^4)$. So the above can occur only if $2+2{\alpha} \leq 4 \Longrightarrow \alpha \leq 1$. But by our assumption earlier, $\alpha > 1$, a contradiction. $\Longrightarrow \alpha=1$. So $f(n)=O(n)$. But then for large m, $q(m,1)=\frac{1+f(f(m))}{f(1)+1400m^2}=O(\frac{1}{m})$. But then $q(m,1)$ is not an integer, a contradiction to the problem statement. So there are no such functions.
24.05.2021 18:39
PUjnk wrote: Now suppose $f(n)=O(n^{\alpha})$. You need to first prove that there exists $\alpha$ such that $\lim_{n \to \infty} \frac{f(n)}{n^\alpha} $ exists, before simply assuming this.
24.05.2021 18:40
It has already been proved that $f(n) \le n^2 + f(f(1)) - 1400 = O(n^2)$ and so such a limit does exist
24.05.2021 19:01
OK, what I said above is the definition of $\Theta( \cdot) $. But assume that you mean $\mathcal{O} (\cdot)$ , wikipedia says, Wikipedia wrote: Let $f$ be a real or complex valued function and $g$ a real valued function. Let both functions be defined on some unbounded subset of the positive real numbers, and $g(x)$ be strictly positive for all large enough values of $x$. One writes $$ f(x)=\mathcal{O}(g(x)) ~ \text{as} ~ x \to \infty $$ if the absolute value of $f(x)$ is at most a positive constant multiple of $g(x)$ for all sufficiently large values of $x$. That is, $f(x)=\mathcal{O}(g(x))$ if there exists a positive real number $M$ and a real number $x_0$ such that $$ |f(x)|\leq Mg(x) ~ \text{ for all } ~ x\geq x_{0} $$ So the first you assertion you used here cannot be derived, because you don't have a $\ge$ PUjnk wrote: But now we have $m^2f(m^2) \geq O(m^{2+2{\alpha}})$ and $f(f(m)) \leq O(m^4)$.
24.05.2021 19:11
Here when I am saying $f(n)=O(n^{\alpha})$, I mean there are constants C and D such that $Cn^{\alpha} \leq f(n) \leq Dn^{\alpha}$. So the last assertion works.
24.05.2021 19:13
If so, you actually mean $\Theta( n^\alpha)$. But please provide a proof to PUjnk wrote: there are constants C and D such that $Cn^{\alpha} \leq f(n) \leq Dn^{\alpha}$
07.06.2021 13:10
here’s my solution in the exam: Lemma: Let $h,g: N\rightarrow N$, such that $lim _{n\rightarrow \infty} h,g =\infty$ and $\exists k; k>\frac{h(n)}{g(n)^2}$. Then if $a,b,c,d\in N$,There exists $k’$ such that: $$\mid T(n) \mid=\mid \frac{h(n) +a}{g(n)+b}-\frac{h(n)+c}{g(n) +d} \mid <k’$$Proof: $$\mid T(n) \mid =\mid \frac{(d-b)h(n) +(a-c)g(n) +ad-bc}{(g(n)+b)(g(n)+d)} \mid \leq \mid \frac{(d-b)h(n)}{(g(n)+b)(g(n)+d} \mid +\mid \frac{(a-c)g(n)+ad-bc}{(g(n)+b)(g(n)+d)} \mid $$$$\leq |d-b|k +\mid \frac{(a-c)g(n)+ad-bc}{(g(n)+b)(g(n)+d)} \leq |d-b|k +|a-c| +|ad-bc|=k’$$So the lemma is proven Back to the problem: Part 1: taking properties: Let $p(n,m)$ be the assertion of the problem. Setting $p(f(m),m)$ we get $f(f(m))+1400m^2 \mid f(f(m)) f(m)^2$. Knowing that $1400m^2\neq f(m)^2$ we conclude that $f(m)^2 +f(f(m)) \geq 2(f(f(m)) +1400m^2)$ so: $f(m)^2>f(f(m))$ (1) $f(m) >\sqrt{2800} m$ (2) Setting $p(1,m)$ we easily get $f(f(m))>1400m^2$ (3) Setting $p(n,1)$ we get that there is a $l\in R^+$ such that $n^2 >l \cdot f(n)$. (4) If $f(a)=f(b)$ then by checking $p(a,m), p(b,m)$ for large $m$ gives us that $a=b$ so $f$ is injective (5) Part 2: using the lemma: In the lemma, for a constant $n$ and variable $m$ set: $$h= f(f(m)), g=1400m^2, a=n^2, b=f(n), c=(n+1)^2, d=f(n+1)$$The first condition is a direct consequence of (3) and for the second condition: $$g(m)^2 \geq(1400m^2)^2>1400^2 l^2 f(m)^2>1400^2 c^3 f(f(m)) \Rightarrow k>\frac{h(m)}{g(m)^2}$$so the second condition is also true. Now we can use the lemma: $T(m)<k’$ now note that according to $p(n,m), p(n+1,m)$ both fractions that make $T(m)$ are actually natural numbers so $T(m)$ is an integer. Beacuse $T(m)<k’$ then there exists an integer $v$ such that $T(m)=v$ has infinitely many solutions (by the pigeonhole principle). Let $A$ be the set of $m$ such that $T(m)=v$. Let $m\in A$ then: $$\frac{f(f(m))+n^2}{1400m^2 +f(n)} -\frac{f(f(m))+(n+1)^2}{1400m^2 +f(n+1)}=v$$then by rearranging the equality we get that $f(f(m))=am^4+bm^2+c$ where $a,b,c\in Q$ Now we look at $p(n,m)$ for $m\in A$ and any $n$: $f(n)+1400m ^2\mid n^2 am^4+bm^2+c$ so we multiply the right hand side by $1400^2 u$ such that $ua,ub,uc$ are integers so now by replacing any $1400m^2$ in the right hand side with $-f(n)$ we get that: $f(n) +1400m^2\mid r n^2 +a’f(n)^2+ b’f(n) +c’$ Such that $r,a’,b’,c’\in Q$ and $a’=0 \Leftrightarrow a=0$ (It’s easy to check this). By increasing $m$ (Because there are infinitely many such $m$) we get that the right hand side must be 0. So there are $a”,b”,c”\in Q$ such that for all $n$ we have $n^2=a”f(n)^2+b”f(n)+c”$ and $a”=0\Leftrightarrow a=0$ (also easy to check). (6) Now for an $m\in A$ set $f(m)$ and $m$ in (6) and combine: $$m^2=a”(a”(am^4+bm^2+c)^2+b”(am^4+bm^2 +c) +c”) +b”\sqrt{a”(am^4+bm^2+c)^2 +b”(am^4+bm^2+c) +c”} +c”$$Now if $a\neq 0$ then the RHS is degree $8$ so by increasing $m$ we get a contradiction. So $a=0$ then $a”=0$ so: $$m^2= b”\sqrt{b”(bm^2+c) +c”} +c”$$But now the LHS is degree 2 but the RHS is at most degree 1. Still a contradiction. So No such function exists.