# Examples of bijections from $\mathbb Z\to\mathbb Z$ such that their sum is a bijection?

What are some simple examples of functions $f,g\colon \mathbb Z\to\mathbb Z$ which are bijective and their sum is also bijective?

Unless I am missing something, it is not difficult show that such functions exist by induction. (We simply order $\mathbb Z=\{z_n; n=0,1,2,\dots\}$ in some way. And we can define $f$, $g$, $h$ by induction in such way that we make sure that after $n$-th step: a) $f$ and $g$ are defined for the integers from some set $A_n$; b) $f$, $g$ and $h=f+g$ are injective on $A_n$; c) $z_n\in A_n$; d) $z_n$ belongs to $f[A_n]$, $g[A_n]$, $h[A_n]$. If needed, I can try to make this more precise and post inductive construction in an answer; of course, if somebody wants to post such an answer, you're more than welcome to do so. Especially if you can suggest some more elegant way than what I sketched here.)

But I have doubts that there is a bijection given by a simple formula. (Although I admit that the words "simple formula" are rather vague.)

So, as an additional question, is there example of bijections $f$, $g$ such that $f+g$ is also bijection, and these functions are "nice"? (For some reasonable meaning of the word "nice".) Or can we show that such example cannot be found if we restrict $f$, $g$ to some reasonably behaved class of functions?

Basically the motivation for this question came from a course that I am TA-ing. As an exercise, to help them acquainted with the notion of bijection, the students were asked to find an example of two bijections from $\mathbb Z$ to $\mathbb Z$ such that their sum is not a bijection. A colleague, who is also TA at the same course, asked me whether I can think of example where the sum is bijection, since for the most natural examples that one typically thinks for (such as $x\mapsto x+d$ or $x\mapsto -x+d'$) you never get a bijection.

• I'll bet any bijection $f:\mathbb Z\to\mathbb Z$ can be written as the sum of two bijections. – bof Oct 21 '17 at 11:02
• @bof to check that claim I guess it suffices and is necessary to decompose the identity. – Mr. Chip Oct 21 '17 at 11:15
• A little bit related: math.stackexchange.com/questions/2092547 – Watson Oct 21 '17 at 11:29
• Unless I misunderstand your problem, multiplications by $a$ and by $b$, such that $a,b\ne 0$, $a\ne b$, satisfy this property. – Bernard Oct 21 '17 at 12:02
• @Bernard A function given by $f(x)=ax$ is a bijection from $\mathbb Z$ to $\mathbb Z$ if and only if $a=\pm1$. (Of course, with $\mathbb R$ instead of $\mathbb Z$, this would be entirely different question.) – Martin Sleziak Oct 21 '17 at 14:32

Any bijection $\mathbb{Z} \to \mathbb{Z}$ can be decomposed as a sum, I believe. I'm going to make a geometric/visual argument for this.

We prove that $\text{id}: \mathbb{Z} \to \mathbb{Z}$ can be written $f + g$ for some bijections $f, g: \mathbb{Z} \to \mathbb{Z}$. By precomposing $f + g = \text{id}$ with any bijection $h$, this proves the claim for all $h$.

We can reformulate the problem as follows: consider the integer lattice $\mathbb{Z} \times \mathbb{Z}$ in the plane, and draw in all the lines $x = n$ and $y = m$ through this lattice for $m, n \in \mathbb{Z}$. Draw in also the lines $x + y = k$ for $k \in \mathbb{Z}$. It suffices to show that we can select points in the lattice such that each one of these lines contains exactly one selected point. Indeed, if $(x_k,y_k)$ is the point on the line $x + y = k$, we then define $f(k) = x_k$ and $g(k) = y_k$.

To do this, apply the following algorithm. There are three types of lines to deal with: diagonal, vertical, and horizontal. Let $\ell \ge 0$.

• On step $3 \ell$, find $k$ minimising $|k|$ for which no point on $x + y = k$ has been selected; if you have two choices, pick randomly. Then choose any still-available point $(m,n)$ with $m + n = k$. Erase the lines $x = m$, $y = n$, $x + y = k$.
• On step $3 \ell + 1$, find $m$ minimising $|m|$ for which no point on $x = m$ has been selected; if you have two choices, pick randomly. Then choose any still-available point $(m,n)$, with (say) $m + n = k$. Erase the lines $x = m$, $y = n$, $x + y = k$.
• Ditto on step $3 \ell + 2$, but with horizontal lines $y = n$.

This algorithm evidently misses no lines (by each step, we've only made finitely many erasures, so there's always a suitable choice), and it produces a set of points as desired, so we're done. Similar ideas are expressed in the solutions here.