9
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I'll bet any bijection $f:\mathbb Z\to\mathbb Z$ can be written as the sum of two bijections. $\endgroup$ – bof Oct 21 '17 at 11:02
  • $\begingroup$ @bof to check that claim I guess it suffices and is necessary to decompose the identity. $\endgroup$ – Mr. Chip Oct 21 '17 at 11:15
  • $\begingroup$ A little bit related: math.stackexchange.com/questions/2092547 $\endgroup$ – Watson Oct 21 '17 at 11:29
  • $\begingroup$ Unless I misunderstand your problem, multiplications by $a$ and by $b$, such that $a,b\ne 0$, $a\ne b$, satisfy this property. $\endgroup$ – Bernard Oct 21 '17 at 12:02
  • 1
    $\begingroup$ @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.) $\endgroup$ – Martin Sleziak Oct 21 '17 at 14:32
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.