How many elements can the set $S(f)=\{f(x+y)-f(x)-f(y)\ |\ x,y\in R\}$ have？

Question:

For a surjective function $f：\mathbb R\to \mathbb R$,where $\mathbb R$ denotes the set of real numbers, define the set $$S(f)=\{f(x+y)-f(x)-f(y)\ |\ x,y\in \mathbb R\}\ .$$ Assume that $S(f)$ is finite and $|S(f)|\neq 1$. Find the possible values of $|S(f)|$.

I think $|S(f)|=2$ is possible because of the example $$f(x)=\dfrac{1}{2}(\lfloor x\rfloor-\{x\})\ .$$

It is clear $f$ is surjective,because for any $t\in R$, if we let $x=2t+2\{-2t\}$, then we have $$f(x)=\dfrac{1}{2}(2t+2\{-2t\}-2\{-2t\})=t\ ,$$ and we then have $$S(f)=f(x+y)-f(x)-f(y)=\{x\}+\{y\}-\{x+y\}=\{0,1\}\ ,$$ so we have$$|S(f)|=2\ .$$

Using this method, Can we find examples such that $|S(f)|=3,4,5,\ldots$? Maybe there are other methods to solve this problem.

• What is the definition of $f$? Is $R$ the set of real numbers or something else? What is $T$? – amrsa Apr 18 '17 at 10:32
• @amrsa,sorry,I have edit it. – function sug Apr 18 '17 at 10:37
• what is a $R$? The real numbers? – user321268 Apr 18 '17 at 11:41
• @mayer_vietoris,yes, it's it – function sug Apr 18 '17 at 11:59

One example for more than 2.

$f(x) = \begin{cases} 1 &\text{if } x = \frac12 \\ 2 &\text{if } x = \frac14 \\ 4x &\text{if } x \neq \frac12, \frac14 \end{cases}$

$f(x) = 4x\operatorname{sgn}\left|x-\frac12\right|\operatorname{sgn}\left|x-\frac14\right| + 1(1 - \operatorname{sgn}\left|x-\frac12\right|) + 2(1 - \operatorname{sgn}\left|x-\frac12\right|)$ $S(f) = \{-3, -1, 0, 1, 2\}$

And the method to generate more of these functions with finite $|S(f)|$ values.

Given surjective real function $g: \mathbb{R} \to \mathbb{R}$, such that $\left|S(g)\right| = 1$, and a finite permutation on real numbers $h: \mathbb{R} \to \mathbb{R}$ with $n > 0$ values permuted, and the composition surjective real function $f(x) = g(h(x))$, the value $\left|S(f)\right|$ is finite, at least 2 and with the upper bound $1 + \frac12 n(n+5)$. (Working at the bottom)

Looking at your function and the other answer, I think the kinds of functions $F$ such that $S(F)$ is finite can be defined by composition of linear functions, finite permutations and surjective sawtooth functions.

$F = f_1 \circ \ldots \circ f_n$

where for each $i = 1, \ldots, n$, surjection is assumed and one of the following is true:

• $\exists m,c \in \mathbb{R} : m \neq 0 \land \forall x \in \mathbb{R} : f_i(x) = mx + c$ (linear)
• $\exists b \in \mathbb{R}_{>0} : \forall x \in \mathbb{R} : f_i(x) = x + (x {\%} b)$ (surjective sawtooth)
• $\left|\{x \in \mathbb{R} \mid f_i(x) \neq x \}\right| < \aleph_0 \land \forall y \in \mathbb{R}: \exists! x \in \mathbb{R}: f_i(x) = y$ (finite permutation)

Working out for the finite permutation case: \begin{align} \mathbb{F}_S &= \{f: \mathbb{R} \to \mathbb{R} \mid \forall y \in \mathbb{R}: \exists x \in \mathbb{R} : f(x) = y \} \\ \mathbb{F}_B &= \{f: \mathbb{R} \to \mathbb{R} \mid \forall y \in \mathbb{R}: \exists! x \in \mathbb{R} : f(x) = y \} \\ S &: \mathbb{F}_S \to \mathbb{R} \\ S(f) &= \{f(x+y) - f(x) - f(y) \mid x,y \in \mathbb{R} \} \\ g &\in \mathbb{F}_S \\ \left|S(g)\right| = 1 &\implies \exists c \in \mathbb{R} : \forall x,y \in \mathbb{R} : g(x+y) - g(x) - g(y) = -c \\ &\implies \exists m,c \in \mathbb{R}: \forall x \in \mathbb{R}: g(x) = mx + c \\ \left|S(g)\right| = 1 &\vdash g(x) = mx + c \land S(g) = \{-c\} \\ T &: \mathbb{F}_B \to \mathbb{R} \\ T(f) &= \{ x \in \mathbb{R} \mid f(x) \neq x \} \\ h &\in \mathbb{F}_B \\ f &\in \mathbb{F}_S \\ f(x) &= g(h(x)) \\ S_f &{:=} S(f) \\ S_g &{:=} S(g) \\ T_h &{:=} T(h) \\ 0 < \left|T_h\right| < \aleph_0 &\vdash 1 < \left|S_f\right| < \aleph_0 \\ F(x, y) &{:=} f(x+y) - f(x) - f(y) \\ G(x, y) &{:=} g(x+y) - g(x) - g(y) \\ S_f &= \{ -c \} \cup \{ F(x,y) \mid x, y \in \mathbb{R} \land F(x,y) \neq -c \} \\ F(x, y) \neq -c &\implies f(x) \neq g(x) \lor f(y) \neq g(y) \lor f(x+y) \neq g(x+y) \\ &\implies x \in T_h \lor y \in T_h \lor (x+y) \in T_h \\ &\vdash \left|S_f\right| > 1 \end{align}

\begin{align} S_f &= \{-c\} \cup P_1 \cup P_2 \cup P_3 \\ P_1 &= \left\{F(t - x, x) \mid t \in T_h \land x \in \mathbb{R} \land x \notin T_h \land t - x \notin T_h \right\} \\ &= \left\{f(t) - f(t-x) - f(x) \mid \Phi(x,t) \right\} \\ &= \left\{mh(t) + c - (m(t-x) + c + mx + c) \mid \Phi(x, t) \right\} \\ &= \left\{m(h(t) - t) - c \mid t \in T_h \right\} \\ (\forall t \in h : h(t) \neq t) &\vdash \exists x \in P_1: x \neq -c \\ &\vdash \left| \{-c\} \cup P_1 \right| > 1 \\ 0 < &\left|P_1\right| \leq \left|T_h\right| \\ P_2 &= \left\{ F(x, y) \mid x,y \in T_h \land (x > y \lor x = y) \right\} \\ &\vdash \left|P_2\right| \leq \frac12 \left|T_h\right|\left(\left|T_h\right| + 1\right) \\ P_3 &= \left\{ F(t, x) \mid t \in T_h \land x \in \mathbb{R} \setminus T_h \land t + x \notin T_h \right\} \\ &= \left\{ f(t + x) - f(t) - f(x) \mid \phi(t, x) \right\} \\ &= \left\{ m(t+x) + c - (mh(t) + c + mx + c) \mid \phi(t, x) \right\} \\ &= \left\{ m(t - h(t)) - c \mid t \in T_h \right\} \\ &\vdash \left|P_3\right| \leq \left|T_h\right| \\ \left|S_f\right| &\leq 1 + 2\left|T_h\right| + \frac12 \left|T_h\right|\left(\left|T_h\right| + 1\right) \\ &\leq 1 + \frac12 \left|T_h\right|\left( \left|T_h\right| + 5 \right) \\ 1 < &\left|S_f\right| \leq 1 + \frac12 \left|T_h\right|\left( \left|T_h\right| + 5 \right) \end{align}

incomplete

I think $$f(x)=x+\sum_{i=0}^n x\%2^i-a[x\neq0]$$ where $\%$ is the sawtooth, $[x\neq0]$ is the Iverson bracket, $n\in\mathbb{N}$ and $2^{n+1}>a\in\mathbb{N}$ satisfies $$\lvert S(f)\rvert=2^{n+1}+a.$$ However, I just can't seem to prove that $f$ is surjective. If someone can prove that $f$ is surjective, then I'll present the rest of the proof.

• I have doubt in your last line. It seems like $(x+y)\%\alpha-x\%\alpha-y\%\alpha$ can be $0$ or $-\alpha$, not anything else... – guest Apr 28 '17 at 5:31
• You're right, thanks. – Lawrence C. Apr 30 '17 at 10:35