Find all functions $f:\mathbb{Z}\to \mathbb{Z}_{>0}$ for which \[f(x+f(y))^2+f(y+f(x))^2=f(f(x)+f(y))^2+1\]holds for any $x,y\in \mathbb{Z}$.
Problem
Source: 2023 Israel TST Test 1 P3
Tags: TST, functional equation, algebra, function
bora_olmez
25.03.2023 03:53
Pretty nice, especially the "proof" of injectivity (of course at the end of the day $f$ will be seen not to be injective). We claim that $f \equiv 1$ is the only solution. As usual, let $f^k(x) = f(f^{k-1}(x))$ The proof will proceed in the following steps, none of them too unnatural but not too straight forward either. $\textbf{Lemma 1:}$ $$f(f^k(x)+f(y)) \geq f(x+f(y))$$for all $x,y \in \mathbb{Z}$, $k \in \mathbb{Z}_{\geq 0}$
We will prove that $f(f(x)+f(y)) \geq f(x+f(y))$, then taking $x \to f^k(x)$ and inducting will suffice.
Notice that $$(f(f(x)+f(y))-f(x+f(y)))(f(f(x)+f(y))+f(x+f(y)) = f(y+f(x))^2-1 \geq 0$$and $f(f(x)+f(y))+f(x+f(y))>0$ implies $f(f(x)+f(y)) \geq f(x+f(y))$, as desired. $\blacksquare$
$\textbf{Lemma 2:}$ If $f$ is bounded over $\mathbb{Z}_{>0}$ or $\mathbb{Z}$, then $f \equiv 1$
Notice that if $f$ is bounded, then there exists some $x \in \mathbb{Z}_{>0}$, $k \in \mathbb{Z}_{>0}$ such that $f^k(x) = x$, then $$f(f^k(x)+f(y) \geq f(f^{k-1}(x)+f(y)) \geq \cdots \geq f(f(x)+f(y)) \geq f(x+f(y))$$by $\textbf{Lemma 1}$ implies that all of these are equalities meaning that $f(f(x)+f(y)) = f(x+f(y))$, then going back to our initial assertion, we have that $f(y+f(x)) = 1$ for all $y \in \mathbb{Z}$ where $x \in \mathbb{Z}$ is fixed, in particular, $y+f(x)$ is surjective in $\mathbb{Z}$ meaning that $f \equiv 1$. $\blacksquare$
Let $S \subseteq \mathbb{Z}$ be $\textit{good}$ if there exists some $c \in \mathbb{Z}_{>0}$ such that for all $s \in \mathbb{S}$, $f(s)=c$, that is $S \subseteq f^{-1}(c)$ for some positive integer $c$. $\textbf{Lemma 3 (important):}$ Let $a \in Im(f)$, then if $S$ is a good set, $S+a$ is also a good set.
Take a $y=s$ for some $s \in \mathbb{S}$ and notice that as $a \in Im(f)$, there exists some $x \in \mathbb{Z}$ such that $f(x)=a$, and take this $x$. Then $$f(s+a)=f(s+f(x)) = \sqrt{f(f(x)+f(s))^2+1-f(x+f(s))} = \sqrt{f(a+c)^2+1-f(x+c)}$$where $S \subseteq f^{-1}(c)$ and $x,a,c$ are fixed meaning that $f(s+a)$ is a constant independent of $s$, in particular $S+a$ is a good set. $\blacksquare$
$\textbf{Lemma 4:}$ If $1 \in Im(f)$, then $f \equiv 1$
Assume that $f(a) = 1$ as $1 \in Im(f)$. Then take $x = a-f(y)$ which gives $f(y+f(a-f(y)) = f(f(y)+f(a-f(y))$. Now, we split into two cases.
$\textbf{Case 1)}$ $f$ is injective
Then, the above relation gives us that $f(y) = y$ for all $y \in \mathbb{Z}$ which is clearly not a solution. $\square$
$\textbf{Case 2)}$ $f$ is not injective
Then, there exist $a<b$ such that $f(a) = f(b)$, in particular, there is a good set $S$ of cardinality at least $2$. We know that $1 \in Im(f)$ meaning that $S+i$ is good for all $i \in \mathbb{Z}_{>0}$. This implies that $f$ is eventually periodic with period $d = b-a$ and hence bounded over $\mathbb{Z}_{>0}$ which allows us to finish using $\textbf{Lemma 2}$. $\square$
Having concluded both cases, this resolves the lemma. $\blacksquare$
We can now work on generalizing the approach for $\textbf{Lemma 4}$. $\textbf{Lemma 5}$ There exists some $m \in \mathbb{Z}_{>0}$ and $a_1, \cdots, a_m \in Im(f)$ such that $gcd(a_1,a_2, \cdots, a_m) = 1$
Notice firstly that there does not exist any $d \in \mathbb{Z}_{>0}, d>1$ such that $d \mid f(x)$ for all $x \in \mathbb{Z}$ by looking at the original equation because in that case, we would have that $0 \equiv LHS \equiv 1 \pmod{d}$ which means that $d=1$. Now, take some arbitrary $a_1 \in Im(f)$ with prime divisors $p_1, \cdots, p_k$ and take $b_i$ to be such that $b_i \in Im(f)$, $p_i \nmid b_i$ which must exist because otherwise $p_i \mid f(x)$ for all $x \in \mathbb{Z}$. Then take $\{a_1, \cdots, a_m\}$ to be the set (not superset), $\{a_1,b_1, \cdots, b_k\}$ and notice that $gcd(a_1, a_2, \cdots, a_m) = gcd(a_1,b_1,b_2, \cdots, b_k) = 1$, as desired. $\blacksquare$
$\textbf{Lemma 6}$ If $f$ is non-injective, then $f \equiv 1$
Notice by $\textbf{Lemma 3}$, that if $S$ is good, and $t_1, t_2, \cdots, t_k$ are elements of $Im(f)$, then $S+t_1+t_2+ \cdots t_k$ is good by inducting on the number of variables. In particular, we know by Chicken Mcnugget that all sufficiently large positive integers can be expressed in the form $\sum_{i=1}^{m} x_ia_i$ for $x_i \geq 0$ and $a_i$ as in $\textbf{Lemma 5}$ and we therefore get that for $S$ good, $S+i$ is good for all sufficiently large $i$, again, assuming non-injectivity and defining the first "sufficiently large" $i$ such that $A = S+i$, we have that $A, A+1, \cdots, $ are all good where $|A| \geq 2$, say $a,b \in S$, then we again get that $f$ is eventually periodic with period $|b-a|$ and bounded over $\mathbb{Z}_{>0}$ which finishes by $\textbf{Lemma 2}$.
$\textbf{Lemma 7}$ $f$ is non-injective
Assume for the sake of contradiction that $f$ is injective. Now, fix some $c \in \mathbb{Z}$ and take $x = c-f(y)$, we get that $$M = f(c)^2-1 = f(f(y)+f(c-f(y))^2-f(y+f(c-f(y)))^2$$
Now, notice that $T_c = \{y+f(c-f(y))|y \in \mathbb{Z}\}$ has arbitrarily large elements (take $y \to \infty$) meaning that $f(T_c)$ is unbounded. However, we know that $1 \not\in Im(f)$ because of $\textbf{Lemma 4}$ and hence $M \neq 0$. Then we have $M = a^2-b^2$ for some $a,b \in \mathbb{Z}_{>0}$ and therefore $$M = a^2-b^2 = (a-b)(a+b) \geq a+b \geq b$$Therefore $M \geq f(y+f(c-f(y))$ means that $f(T_c)$ cannot be unbounded, a contradiction, as desired. $\blacksquare$
Now, combining $\textbf{Lemma 6}$ and $\textbf{Lemma 7}$, we get that $f \equiv 1$, as desired. $\blacksquare$ $\blacksquare$
gghx
25.03.2023 10:54
Gorgeous!! Case 1: $f$ is not injective. Suppose $f(a)=f(b)$, then we easily get $f(a+f(y))=f(b+f(y))$. Repeating this, we have $f(a+\sum f(y_i))=f(b+\sum f(y_i))$ for any collection of $y_i$s. Since $2f(x+f(x))^2=f(2f(x))^2+1$ we can find two coprime values in the range of $f$, hence by chicken mcnugget, $f(a+N)=f(b+N)$ for all sufficiently large $N>C$ ($C$ constant). Note that this means $f(\mathbb{Z}_{>0})$ can take finitely many values, hence since $f(x)+f(y)>0$, the RHS can take finitely many values, which means the same for the LHS as well, thus $f$ is bounded. Thus we can find $f(a)=f(b)$ where $a,b$ are arbitrarily large negative numbers. This means that $f$ is periodic, and further that within a period all $f$ are distinct (if they are not we can find a smaller period). Let the period be $T$. The previous result means that $f(a)=f(b)\implies T|a-b$. Taking $x+f(y)$ such that $f(x+f(y))$ is maximal, we have $f(y+f(x))=1$, so there exists $f(k)=1$. Now for any $x$, take $y=k-f(x)$, which means $f(x+f(y))=f(f(x)+f(y))$. Hence, $T|f(x)-x$, so $f(x)\equiv x \pmod{T}$. Taking the entire equation $\pmod{T}$, $2(x+y)^2\equiv (x+y)^2+1\pmod{T}$, hence $T=1$ (else take $x=-y$). Since $T=1$, $f$ is constant, hence $f\equiv 1$. Case 2: $f$ is injective. Take some $f(a)\ne 1$ and consider $P(a-f(y),y): f(a)^2+f(y+f(a-f(y)))^2=f(f(a-f(y))+f(y))^2+1$. There are finitely many solutions for $f(a)^2+m^2=n^2+1$, hence one of them appear infinitely many times. By injectivity, this means there exists constants $c_1,c_2$, such that $y+f(a-f(y))=c_1$ and $f(a-f(y))+f(y)=c_2$ for infinitely many negative $y$. Subtracting, $f(y)=y+c_2-c_1$ for infinitely many negative $y$, and by taking sufficiently negative $y$ we get $f(y)<0$, contradiction.
oVlad
05.04.2023 12:41
Phorphyrion wrote: Find all functions $f:\mathbb{Z}\to \mathbb{Z}_{>0}$ for which \[f(x+f(y))^2+f(y+f(x))^2=f(f(x)+f(y))^2+1\]holds for any $x,y\in \mathbb{Z}$. Suppose that $f(a)=f(b)$ for some $a\neq b$. Then, $P(x,a)$ and $P(x,b)$ give us $f(a+f(x))=f(b+f(x))$ for any $x{}$. Doing this repeatedly, it follows that for any $x_1,x_2,\ldots,x_k$ (some values may repeat), we have \[f\left(a+\sum_{i=1}^kf(x_i)\right)=f\left(b+\sum_{i=1}^kf(x_i)\right).\]By looking at $P(x,x)$ we infer that there exist $\alpha{}$ and $\beta$ for which $\gcd(f(\alpha),f(\beta))=1$. That being said, if we choose the $x_i$ to be either $\alpha{}$ or $\beta$ with the adequate muliplicities, for any positive integer $n>N$ we have $f(a+n)=f(b+n)$. Hence, $f$ has period $|a-b|$ on large enough integers. Let $\delta$ be the smallest positive difference between two integers at which $f$ gives the same value. By the above property, $f$ is eventually periodical of period $\delta$. That being said, if there exist $a,b$ with $f(a)=f(b)$ and $\delta\nmid|a-b|$ then $f{}$ would eventually be periodical with period $|a-b$, so it will eventually be periodical with period $\gcd(\delta,|a-b|)<\delta$, contradiction. Hence, $f(a)=f(b)$ implies $\delta\mid |a-b|$. Note that $f$ takes finitely many values on the positive integers. Letting $y=1$ and $x\mapsto x-f(1)$ we get \[f(x)^2=f(f(x-f(1))+f(1))^2+1-f(1+f(x))^2.\]The right-hand side takes finitely many values (as the inputs are positive), and thus so does the left-hand side. Therefore, the image of $f$ is finite. Let's choose $M{}$ to be the the element of the image of $f$ with the greatest absolute value (ties broken arbitrarily) and $\lambda$ such that $f(\lambda)=M$. Now, if we let $y\mapsto \lambda-f(x)$ it follows that $f(f(\lambda-f(x))+x)=1$, so there exists $\lambda'$ suh that $f(\lambda')=1$. Letting $y\mapsto \lambda'-f(x)$ we now get that $f(f(\lambda-f(x))+x)^2=f(f(\lambda-f(x))+f(x))^2$ hence $f(x)\equiv x\bmod{\delta}$. Reducing $P(x,y)$ modulo $\delta$ it follows that $\delta=1$ hence $f$ is eventually constant from where we can easily get that $f\equiv 1$. Now, if $f$ is injective, choose $\lambda$ such that $f(\lambda)\neq 1$ (if it exists) and let $y\mapsto \lambda-f(x)$. Then, we get \[0\neq f(\lambda)^2-1=f(f(\lambda-f(x))+f(x))^2-f(f(\lambda-f(x))+x)^2,\]but the equation $0\neq T=n^2-m^2$ has finitely many solutions, thus for infinitely many $x{}$ and some $C_1,C_2$ we have \[\begin{cases}f(\lambda-f(x))+f(x)=C_1 \\ f(\lambda-f(x))+x=C_2\end{cases}\]so $f(x)=x+C_1-C_2$. We get a contradiction after some bash.
bhan2025
23.10.2023 01:40
Intuitively very straightforward but a bit annoying to rigorously prove. Let $g$ be the gcd over all numbers in $f(\mathbb{Z})$. $g \mid 1$ so $g = 1$. Thus, there exist some $p \neq q$ such that $gcd(f(p),f(q)) = 1$. Let $l = f(p)f(q)$. Main Claim) If there exists $a < b$ such that $f(a) = f(b)$, if we let $k = b-a$ then $f$ is $k$-periodic in $(a+l,\infty)$ pf) $P(a,x)$ vs $P(b,x)$: $f(a+f(x)) = f(b+f(x))$ Plugging this back in, $f(a+f(x)+f(y)) = f(b+f(x)+f(y))$ Recursively applying this gives us $f(a+nf(p)+mf(q)) = f(b+nf(p)+mf(q))$ for all $(n,m) \in (\mathbb{Z}^+)^2$ Thus, for all $n > l$, $f(a+n) = f(b+n)$ $\therefore$ for all $n > a+l$, $f(n) = f(n+k)$ Claim 1) $f$ is not injective Assume it is injective. This implies that $\lim_{x \to \infty} f(x) = \infty$ $P(-f(y),y)$: $f(0)^2 + f(y+f(-f(y)))^2 = f(f(y)+f(-f(y)))^2 + 1$ Thus, $f(y+f(-f(y)))^2 - f(f(y) + f(-f(y)))^2$ is some constant implying $f(y+f(-f(y)))$ has an upper bound as both are integers. Sending $y \to \infty$ gives an immediate contradiction. Thus, there exists some $N$ and $k$ such that $f$ is $k$-periodic in $(N,\infty)$ Claim 2) $f$ is not injective in $(-\infty,M)$ for any integers $M$ pf) Assume that there exists some $M \in \mathbb{Z}$ that contradicts this statement. This implies that $\lim_{x \to -\infty} f(x) = \infty$ Send $(x,y) \to (-\infty,\infty)$. These three things happen: $x+f(y) \to -\infty$, $f(x+f(y)) \to \infty$ $y+f(x) \to \infty$, $f(y+f(x))$ is bounded $f(x) + f(y) \to \infty$, $f(f(x)+f(y))$ is also bounded This creates a contradiction as it implies $\infty$ is bounded. Claim 3) $f$ is periodic over $\mathbb{Z}$ pf) For any $a < b$ such that $f(a) = f(b)$, $f$ is periodic over $(a+l,\infty)$ by the main claim. Sending $a \to -\infty$ by Claim 2 gives us that $f$ is periodic over all integers. We now finish the problem. Let the minimum period of $f$ be $k$. Pick $x$ such that $f(x+f(y))$ takes on the maximum value of $f$. Then, since $f(x+f(y)) \geq f(f(x)+f(y))$, $f(y+f(x)) = 1$. $\therefore 1 \in f(\mathbb{Z})$ Let $f(a) = 1$ $P(a-f(y),y)$: $f(y+f(a-f(y))) = f(f(y) + f(a-f(y)))$ Thus, $y \equiv f(y)$ (mod $k$) for all $y \in \mathbb{Z}$ Therefore, since the value of $f$ solely depends on the $k$-residue of its input, $f(x+f(y)) = f(y+f(x)) = f(f(x)+f(y)) \Rightarrow f \equiv 1$ Comments: A part of this proof that might cause some confusion is the notion that $\lim_{x \to \infty} f(x) = \infty$ if $f$ is injective. This is true because $f$ is bounded below by $0$ and is over the range of integers, and is not true for all functions in general. Overall, very unique FE that mixes elements of algebra and number theory. I do think it is way too easy for a TST P3, should be more like a fun P2 or hard P1.
megarnie
09.08.2024 17:16
The answer is $f\equiv 1$, which clearly works. Now we show it's the only one. Let $P(x,y)$ denote the given assertion. Clearly $1$ is the only constant solution, so assume $f$ isn't constant. Claim: If $f$ is bounded on $(a, \infty) $, then $f$ is also bounded on $(-\infty, \infty)$. Proof: Suppose the opposite was true. Then $f$ would be bounded on $(a, \infty)$, but unbounded on $(-\infty, \infty)$. Note this implies that $f$ is also bounded on $[0,\infty)$. Suppose $f(x) \le M \forall x \ge 0$. Now choose $x,y$ in the equation such that $f(x + f(y)) > M$ (clearly possible since $f$ is unbounded). The LHS is more than $M^2 + 1$, so $f(f(x) + f(y)) > M$, contradiction since $f(x) + f(y) > 0$. $\square$ Claim: $f$ is unbounded. Proof: Suppose $f$ was bounded. Let $M$ be the largest possible value of $f$. Choose $r$ with $f(r) = M$. Setting $y = r - f(x)$, we see that $f(x + f(r - f(x)))^2 + M^2 = f(f(x) + f(r-f(x)) )^2 + 1$. The RHS is at most $M^2 + 1$, so $f(x + f(r - f(x))) = 1$ and $f(f(x) + f(r-f(x))) = M$. Setting $x \to f(x)$, we get that $f(f(x) + f(r - f(f(x)) )) = 1$. Now $P(x, r - f(f(x)))$ gives that both $f(x + f(r - f(f(x))) = 1$ and $f(r + f(x) - f(f(x))) = 1$. Hence $f(r) = M \implies f(r + f(x) - f(f(x))) = 1$. $P(f(x), r - f(x)): M^2 + f(r + f(f(x)) - f(x))^2 = f(f(f(x)) + f(r - f(x)))^2 + 1$. Since the LHS is at least $M^2 + 1$, we must have $f(f(f(x)) + f(r-f(x))) = M$. Now this implies that $f(f(f(x)) + f(r-f(x)) + (f(x) - f(f(x))) = 1$, so $f(f(x) + f(r-f(x))) = 1$, but this also equals $M$, so $M = 1$ and thus $f$ is constant, contradiction. $\square$ Claim: $f$ is injective. Proof: Suppose that $f(a) = f(b)$ for some $a \ne b$. Notice that $P(a,y)$ compared with $P(b,y)$ gives that $f(a + f(y)) = f(b + f(y))$. We can repeatedly apply this and get $f(a + f(c_1) + f(c_2) + \cdots + f(c_k)) = f(b + f(c_1) + f(c_2) + \cdots + f(c_k))$ for any integers $c_1, c_2, \ldots, c_k$ and $k \ge 1$. Now let $m = f(f(0)), n = f(2f(0))$. Notice that $P(0,0)$ gives that $2m^2 = n^2 + 1$, so $\gcd(m,n) = 1$. Additionally, we have $f(a + xm + yn) = f(b + xm + yn)$ for any nonnegative integers $x,y$. By Chicken-McNugget theorem, $xm + yn$ takes all large enough positive integers. Hence $f(a + t) = f(b + t) $ for all large enough positive integers $t$, implying that $f(x) = f(x + (b-a))$ for all $x \ge N$ for some constant $N$. However, this means $f$ is bounded on $[N, \infty)$, so $f$ is also bounded overall, a contradiction. $\square$ Claim: $1$ isn't in the image of $f$. Proof: Suppose otherwise. For any integer $y$, choose $x$ such that $f(x + f(y)) = 1$. $P(x,y)$ gives that $f(y + f(x))^2 = f(f(x) + f(y))^2$, so $f(y + f(x)) = f(f(x) + f(y))$, implying that $f(y) = y$. However, the identity function does not work. $\square$ Claim: For any integer $n \ne 0$, there are only finitely many pairs of positive integers $(a,b)$ with $a^2 - b^2 = n$. Proof: Notice that $a^2 - b^2 = (a-b)(a+b)$, so if $a^2 - b^2 = n$, then $a - b$ and $a + b$ divide $n$. Since $a + b$ is positive, this means that $a + b \le |n|$, so both $a,b$ are at most $|n|$, implying that there are finitely many such pairs $(a,b)$. $\square$ $P(-f(y), y): f(0)^2 + f(y + f(-f(y)))^2 = f(f(-f(y)) + f(y))^2 + 1$. Now this implies that $f(y + f(-f(y)))^2 - f(f(-f(y)) + f(y))^2 = 1 - f(0)^2$. Now, since $f(0) \ne 1$, we have $f(0)^2 \ne 1$, so $1 - f(0)^2$ is nonzero, implying by our earlier claim that $f(y + f(-f(y)))$ can only take finitely many values. Now, let $a_1, a_2, \ldots, a_k$ be all the different possible values of $f(y + f(-f(y)))$. Since all the $a_i$ are in the image of $f$, let for each $a_i$, let $b_i$ be the unique value such that $f(b_i) = a_i$. Then for any $x$ not in the sequence $b_1, b_2, \ldots, b_k$, we have that $f(x)$ is not in $a_1, a_2, \ldots, a_k$. Now fix $y > \max(b_1, b_2, \ldots, b_k)$. Notice that $f(-f(y))$ is positive, so $y + f(-f(y)) > \max(b_1, b_2, \ldots, b_k)$ and thus is not in $b_1, b_2, \ldots, b_k$. Hence $f(y + f(-f(y)))$ is not in $a_1, a_2, \ldots, a_k$, but this is a contradiction.