Find all functions $f$ such that $f(x-f(y)) = f(f(x)) - f(y) - 1$

Question

Find all functions $f : \mathbb{Z} \to \mathbb{Z}$ such that $f(x-f(y)) = f(f(x)) - f(y) - 1$.

So far, I've managed to prove that if $f$ is linear, then either $f(x) = x + 1$ or $f(x) = -1$ must be true. I did this by plugging in $x=0$ to the above equation, which yields $$ f(-f(y)) = f(f(0)) - f(y) - 1$$ and plugging in $x$ instead of $y$ and subtracting, this becomes $$ f(-f(y)) - f(-f(x)) = f(x) - f(y)$$ Assuming $f(x) = ax + b$ then gives \begin{align*} f(-ay-b) - f(-ax-b) = ax - ay &\Rightarrow -a^2y - ab + a^2x + ab = a(x-y) \\&\Rightarrow a^2(x-y) = a(x-y) . \end{align*} Thus $a=1$ or $a=0$. If $a=0$, then the original equation becomes $b = b - b - 1$, thus $b=-1$. If $a=1$, the original equation becomes $$ x-y-b+b = x+2b-y-b-1 \Longrightarrow b=1.$$

I briefly tried finding a quadratic function that works but didn't find anything. So my question is: how can I either show that $f$ must be linear or find all other representations?

Answer 1

I think $f$ has to be linear. You derived the expression

$$ f(-f(y)) = f(f(0)) - f(y) -1. $$ Now let $a=f(0)$ and $t=-f(y)$. Then

$$ f(t) = f(a)+t-1 $$

Edit: plugging in $t=0$ we obtain $f(a)=a+1$, while plugging in $t=a$ we find $a=1$, which gives $f(t)=t+1$, in agreement with what you found.

Edit: As pointed out by Najib Idrissi I did not check for constant solutions. The only constant solution is clearly $f(t)=-1$ as it is promptly inferred from the original equation. However, I believe the expression $f(t) = f(0)+t$ is still the general expression of any non constant solution, regardless of surjectivity. As a matter of fact, we are only interested to see what's the action of $f$ on its range (cause we need to be able to apply $f$ twice). If $f(f(x)) = g(f(x))$ for every $x$, then $f=g$ on $Range(f)$. If after finding $g(x)$ we see that $Range(g)=\mathbb{Z}$, then $f(x)=g(x)$ on $\mathbb{Z}$.

Edit: I finally get completely the point of Najib and Mattia. The expression I found works only if $t$ is in the Range of $f$. Unfortunately, there is no way from there to infer how big $Range(f)$ is. As a matter of fact, it could consist of simply one point. Please, disregard this answer (but keep it as an example of bad reasoning!).

Answer 2

if we can say that $f$ is polynomial, then since $f(-f(y))-f(-f(x))=f(x)-f(y)$, we can say that $f(-f(y))+f(y)=f(-f(x))+f(x)$ for any $x,y \in Z$. Hence, $f(-f(x))+f(x)$ is constant for all $x \in Z$.

If $deg(f) >0$ then $f$ has infinitely many values, so we can say $f(-x)+x$ is constant, say $f(-x)+x=c$.

Then $f(-x)=c-x$, or $f(x)=c+x$

If $deg(f)=0$ then $f$ is constant and you know the answer.

Answer 3

If the functions attains $0$ at some point, it is linear and $f(n)=n+1$.

Suppose $f(y)=0$, for some $y \in \mathbb{Z}$ then we find for $x \in \mathbb{Z}$ $$f(x)=f(x-f(y))=f(f(x))-f(y)-1 = f(f(x))-1$$ So in particular $x=y$ gives $f(0)= 1$.
Now, if $f(n)=n+1$, then $x=n$ gives $$n+1 = f(n) =f(f(n))-1= f(n+1)-1$$ So $f(n+1) = n+2$, thus for $n \in \mathbb{N}$ we have $f(n) = n+1$.
For the other way, let $x=0$ and $y=n-1$ then $$f(-n) = f(x - f(n-1)) = f(f(x)) -f(n-1) -1 =f(1) - n-1 =-n+1$$ So we see that if $f(y) =0$ for some $y \in \mathbb{Z}$, we have $f(x) = x+1$.

So we can now assume $f(x) \neq 0$ for all $x \in \mathbb{Z}$.
If there exists an $y \in \mathbb{Z}$ such that $y=f(y)$, then $f(x) =-1$.

Suppose there exists an $y \in \mathbb{Z}$ such that $f(y)=y$, then with $x=y$ $$f(0) = f(y-f(y)) = f(f(y)) - f(y) - 1 = y-y-1 =-1$$ So we have $f(0)=-1$. Then we have if $f(y+n)=y$ for $n \ge 0$ that $$f(y+n+1) = f(y+n-f(0)) = f(f(y+n)) -f(0)-1 = f(y) =y$$ So we see that $f(y+n) = y$ for every $n \in \mathbb{N}$.
Now, if $y>0$, we would find with $x=2y$ $$y = f(y)=f(2y -f(y)) = f(f(2y))-f(y)-1 = f(y)-f(y)-1 =-1$$ So $y <0$, and then we have $-1 = f(0) = f(y +(-y)) =y$ and so we find $y=-1$.

Now, we have for all $x \in \mathbb{Z}$ $$-1 = f(0) = f(f(x) -f(x)) = f(f(f(x))) - f(x)-1$$ And so $f(x) = f(f(f(x)))$, and so if $f(-1-k)=-1$ for $k\ge 0$ we have $$ f(-1-k) = f(-1-k-1 -f(0)) = f(f(-1-k-1)) -f(0)-1 = f(f(-1-k-1))$$ Then we let $f$ act on both sides and we get $$-1 = f(-1) = f(f(-1-k)) = f(f(f(-1-(k+1)))) = f(-1-(k+1))$$ So we see $f(-1-n)=-1$ for all $n \in \mathbb{N}$.
So we have $f(x) = -1$ for all $x \in \mathbb{Z}$.

Answer 4

Let $f\colon \Bbb Z\to \Bbb Z$ be a any function function with $$\tag0f(x-f(y)) = f(f(x)) - f(y) - 1$$ for all $x,y\in\Bbb Z$. Letting $y=f(x)$ we find $$f(x-f(f(x)))=-1. $$ So for $a=-f(f(0))$ we have $f(a)=-1$. Then with $y=a$, $$\tag1f(x+1)=f(f(x)) $$ Then $(0)$ becomes $$\tag2 f(x-f(y))=f(x+1)-f(y)-1 $$ Or with $g(x):=f(x)+1$ (and $x\leftarrow x-1$) $$\tag3g(x-g(y))=g(x)-g(y)$$ From $(3)$ we see that the image of $g$ is a subgroup of $\Bbb Z$, hence it is either $\{0\}$ (in which case $f(x)=-1$), or $c\Bbb Z$ for some $c\ge 1$. In that case, for $n\in\Bbb Z$ we find $y$ with $g(y)=nc$ and so have $g(x+ nc)=g(x)+nc$. Thus $g$ is determined by the values $g(0),\ldots, g(c-1)$. On the other hand, these values can indeed be chosen freely. In other words:

Claim 1. Let $c\in\Bbb N$ and $b_0,\ldots, b_{c-1}\in\Bbb Z$. Then the function $g$ given by $$ g(x)= (n+b_r)c$$ where $x=nc+r$, $0\le r<c$ is a solution to $(3)$, and all non-zero solutions of $(3)$ are obtained this way.

Proof. Let $x=nc+r$, $y=mc+s$ with $0\le r,s<c$. Then $$\begin{align}g(x-g(y))&=g(nc+r-(m+b_s)c)\\ &=g((n-m-b_s)c+r)\\ &=(n-m-b_s+b_{r})c\\ &=(n+b_r)c-(m+b_s)c\\&=g(x)-g(y)\end{align}$$ That all non-zero solutions are of this form has been shown above. $\square$

Then the solutions $f$ of $(2)$ (apart from $f(x)=-1$) are precisely those of the form $f(x)=g(x)-1$ with $g$ as in Claim 1. Such $f$ is a solution to the original $(0)$ if and only if we additionally have $(1)$ for all $x$. Note that for $x=nc+r$, $0\le r<c$, we have $f(x)=g(x)-1=(n+b_r)c-1=(n+b_r-1)c+c-1$ so that $$f(f(x))=(n+b_r-1+b_{c-1})c-1.$$ On the other hand, $$f(x+1)=g(x+1)-1=\begin{cases}(n+b_{r+1})c-1&\text{if }r<c-1\\(n+1+b_0)c-1&\text{if }r=c-1\end{cases}$$ We conclude that $b_{r+1}=b_r+b_{c-1}-1$ for $0\le r<c-1$, and that $2b_{c-1}-1=b_0+1$. From the first we see that $b_r=b_0+rb_{c-1}-r$, so $$\begin{align}b_{c-1}&=b_0+1+(c-1)b_{c-1}-c\\ &=2b_{c-1}-1+(c-1)b_{c-1}-c\\ &=(c+1)b_{c-1}-c-1\end{align}$$ and finally $$b_{c-1} = \frac {c+1}c.$$ This is an integer only for $c=1$ and in that case we arrive at $b_0=2$ Thus the only solutions to $(0)$ apart from $f(x)=-1$ is $$f(x)=x+1.$$

Answer 5

Here's a partial solution.

If $0$ is a possible value of $f$, then by taking $f(y) = 0$ we get $f(f(x)) = f(x) + 1$. That is, $f(t) = t + 1$ for $t \in f(\mathbb Z)$, and in particular $f(\mathbb Z)$ contains all nonnegative integers. If we define $g(x) = f(x) - x$, the equation becomes $$ g(x - f(y)) = g(x) + g(x + g(x)) - 1$$ But note that the right side does not depend on $y$. Thus, since $f(y)$ can be any nonnegative integer, $g$ must be constant, and taking $x = 0$ we see that this constant must be $1$. So the only solution where $0$ is a possible value of $f$ is $f(x) = x + 1$.