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

Solution 1:

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.