Find all functions $f:\mathbb{N} \to \mathbb{N}$ so that for any distinct positive integers $x,y,z$ the value of $x+y+z$ is a perfect square if and only if $f(x)+f(y)+f(z)$ is a perfect square.
Problem
Source: Iranian third round 2019 Fianls number theory exam problem 1
Tags: number theory
15.08.2019 17:55
The only such functions are $f(x) \equiv k^2x$, where $k$ is some positive integer. It's obvious that these functions indeed work, so let's now show that they are the only ones. Lemma 1. $f$ is injective. Proof. Suppose that $f(a) = f(b)$ for some positive integers $a, b.$ Then, for any integers $x, y$ such that $a+x+y$ is a perfect square, we have that $f(a) + f(x) + f(y)$ is a perfect square, and hence so is $f(b) + f(x) + f(y)$, and hence so is $b+x+y.$ Hence, if we let $x+y$ be $t^2-a$ for some large positive integer $t> 10^{10^{10^{10}}} \cdot \max(a, b)$, we obtain that $a = b.$ Hence, $f$ is injective. $\blacksquare$ Lemma 2. $f(a) + f(b) = f(c) + f(d)$ when $a+b = c+d$, $a < c < d < b.$ Proof. Notice that since $f$ is injective, the set $S$ of positive integers $\alpha$ satisfying $f(\alpha) \le \max(f(a), f(b), f(c), f(d))^2 \cdot 10^{10^{10^{10}}}$ is finite. Now, let's select some $t > a+b+c+d + \max_{e \in S} e$ such that $t+a+b$ is a perfect square. Then, we have that $f(t) + f(a) + f(b)$ and $f(t) + f(c) + f(d)$ are both perfect squares. If we let $n = f(a) + f(b) + f(c) + f(d)$, then we know that $f(t) + f(a) + f(b)$ and $f(t) + f(c) + f(d)$ are both perfect squares which are at least $10^{10^{10}} \cdot t^2$ and differ by at most $t$. This is easily seen to imply that they equal, and so therefore the lemma is proven. $\blacksquare$ As a result of Lemma $2$, we have that $f(x+1) + f(1) = f(x) + f(2)$ for any $x \ge 3.$ Thus, if we let $d = f(2) - f(1)$, then $f(a+1) - f(a) = d$ for all $a \in \mathbb{N} / \{2\}.$ Now, by another application of Lemma $2$, we obtain $f(3) - f(2) = f(11298347284)-f(11298347283) = d$, and so in fact $f(a+1) - f(a) = d \forall a \in \mathbb{N}.$ As a result, $f$ can be written in the form $dx+c$ for some integers $d, c,$ with $d, d+c$ both positive. Now, observe that if $m = dx+c + dy+c + dz+c$ is a square for some distinct $x, y, z \in \mathbb{N}$, then so is x+y+z, and hence so is 4x+4y+4z, and finally so is $4dx+c + 4dy + c + 4dz+c = 4m-3c.$ Since $4m$ is also a square, we either have that $c = 0$ or that $m \le 10^{10^{10^{10}}} \cdot c^2.$ Since the above holds for $m = d \cdot 1 + c + d \cdot 2 + c + d \cdot (t^2-3) + c$ for arbitrarily large positive integers $t$, the second option is absurd and so therefore $c = 0.$ As a result, we know that our function is of the form $dx$ for some $d \in \mathbb{N}.$ From here, it's clear that $d$ is a perfect square, and so hence $f(x) \equiv k^2x$ for $k \in \mathbb{N}$ are indeed our only solutions, as desired. $\square$
03.11.2019 19:36
Taha1381 wrote: Find all functions $f:\mathbb{N} \to \mathbb{N}$ so that for any distinct positive integers $x,y,z$ the value of $x+y+z$ is a perfect square if and only if $f(x)+f(y)+f(z)$ is a perfect square. Claim. For each $m>2$, the sequence $\{f(t^2-m)\}_{t>m}$ is unbounded. Proof. Assume to the contrary, say $f(t^2-m) \leqslant M$ for all $t>m$. For each $1 \leqslant k \leqslant M$, let $(t_n^{(k)})_{n \ge 1}$ be the subset of natural numbers $s$ for which $f(s^2-m)=k$. By pigeonhole principle, there exists an index $k_0$ for which the associated sequence is infinite. Say $k_0=A$ and $(a_n)_{n \ge 1}$ is the corresponding sequence. Observe that for each $n, j \ge 1$ we have $f(a_n^2-m)=f(a_j^2-m)$, so we see that $f(a_n^2-m)+f(2a_j)+f(m+1)$ is a perfect square for all $n>j>m$. Thus, $a_n^2+2a_j+1$ is a perfect square, between $a_n^2$ and $(a_n+1)^2$, a contradiction! The claim follows. $\blacksquare$ Fix $n$ and let $s=t^2-(n+2)$ with $t>100n$ be an integer. Then $f(n)+f(2)+f(s)$ and $f(n+1)+f(1)+f(s)$ are perfect squares. Suppose they are not equal. Then, $$1+|f(n)+f(2)-f(n+1)-f(1)| \ge 2\operatorname{min}(\sqrt{f(n)+f(2)+f(s)}, \sqrt{f(n+1)+f(1)+f(s)})$$which fails since $f(s)$ is unbounded. Thus, $f(n+1)=f(n)+(f(2)-f(1))$ so $f(x)=Cx+D$ for $C, D$ integers. Finally, note that $Ct^2+3D$ is a perfect square for all $t$, hence it is the square of a linear polynomial. In particular, we get $C=a^2$ for some integer $a$ and $D=0$. Clearly, all such functions $x \mapsto a^2x$ satisfy the condition, so we are done.
01.03.2022 03:53
Let $P(x,y,z)$ be the assertion Claim 1: $f$ is injective Proof Suppose that there exists $a , b$ such that $f(a)=f(b)$ Then choose $x,y$ such that $x+y+a$ is a perfect square, then we have $$ f(x)+f(y)+f(a) = f(x)+f(y)+f(b) \text{ is a perfect square } \implies x+y+b \text{ is a perfect square } $$ Let $x+y+a =g(x,y,a)^2$, $x+y+b=g(x,y,b)^2$ we have $$ |a-b| = |g(x,y,a)^2 -g(x,y,b)^2| \ge | g(x,y,a)+g(x,y,b) | $$But since $g(x,y,a),g(x,y,b)$ tends to infinity when $x,y$ tends to infinity, then we have $|a-b|=0 \implies a=b$ Claim 2: $f(x+1)-f(x)=f(y+1)-f(y)$ Proof Take $a$ such that $a^2>x+y+1$ \[\begin{array}{l} P({a^2} - x - y - 1,x,y + 1):f({a^2} - x - y - 1) + f(x) + f(y + 1) = {h^2}\\ \\ P({a^2} - x - y - 1,x + 1,y):f({a^2} - x - y - 1) + f(x + 1) + f(y) = {k^2} \end{array}\]This implies that $$ |f(x)+f(y+1)-f(x+1)-f(y)|=|h^2-k^2| \ge |h+k| $$But since $f$ is injective from claim 1, we have $h,k$ tends to infinity when $a$ tends to infinity This means $ |f(x)+f(y+1)-f(x+1)-f(y)| = 0 \implies f(x+1)-f(x)=f(y+1)-f(y)$ Now from claim $2$, we have $$ f(n+1)-f(n)=f(n)-f(n-1)=f(n-1)-f(n-2)= \ldots = f(2)-f(1) = c \implies f(n)=an+b $$Then the condition is equivalent to $$ an+b \text{ is a perfect square iff } n \text{ is a perfect square } $$ Let $an^2+b=x_n^2$ then $x_n = \sqrt{an^2+b}$ is a positive integer Consider $$ y_n=2x_n-x_{2n} = 2\sqrt{an^2+b} - \sqrt{4an^2+b} = \frac{ 4(an^2+b)-(4an^2+b) }{ 2\sqrt{an^2+b} + \sqrt{4an^2+b}} = \frac{ 3b }{ 2\sqrt{an^2+b} + \sqrt{4an^2+b}} $$Then \[\mathop {\lim }\limits_{n \to + \infty } {y_n} = \mathop {\lim }\limits_{n \to + \infty } (2{x_n} - {x_{2n}}) = \mathop {\lim }\limits_{n \to + \infty } \frac{{3b}}{{2\sqrt {a{n^2} + b} + \sqrt {4a{n^2} + b} }} = 0\] But since $y_n \in N$ , we have $x_{2n}=2x_n$ for a large enough $n$, which means $$2\sqrt{an^2+b}= \sqrt{4an^2+b} \implies 4an^2+4b=4an^2+b \implies b=0 $$Then $a=k^2$. Hence all the solutions are $$ f(x) \equiv k^2 \cdot x $$