Bijection = bijection + bijection on symmetric integer intervals

Observation: It is sufficient to resolve the question for $f(n)=n$.

Proof idea: If $n=g(n)+h(n)$ for all $n$, then $f(n)=g(f(n))+h(f(n))$. Conversely, if $f(n)=g(n)+h(n)$ then $n=f(f^{-1}(n))=g(f^{-1}(n))+h(f^{-1}(n))$.

So, if some $f$ can be decomposed into two bijections $h$ and $g$, then every $f$ can be decomposed.

So resolving this question amounts to finding a permutation $g$ of $\mathbb{Z}$ for which $n \mapsto g(n)-n$ is also a permutation. Such permutations are called orthomorphisms.

UPDATE: I asked both Ian Wanless and Tony Evans about this, and they simultaneously pointed out that the existence of such an orthomorphism was proved in:

MR0040293 (12,670f) Bateman, P. T. A remark on infinite groups. Amer. Math. Monthly 57, (1950). 623–624. 20.0X

So we can conclude that, yes, it's always possible.

Firstly, consider the case when we are not obliged to have the equation 0=0+0.

The question becomes: given $n \geq 1$ does there exist two permutations $g,h$ of $A:=\{-n,-n+1,\ldots,n\}$ such that $n=g(i)+h(i)$ where addition is addition over the integers (and therefore is not closed on $A$).

We can interpret an instance of this question as a set of $n$ non-attacking semiqueens on an $(2n+1) \times (2n+1)$ chessboard (with rows and columns indexed by $A$) such that no semiqueen is in cell $(i,j)$ whenever $i+j \not\in A$. [semiqueens move up-and-down, left-and-right and along one diagonal]

So the instance you cite above is illustrated by this figure:

Just as with orthomorphisms of $\mathbb{Z}_n$ we can find linear constructions:

So we can take the equations

• $0=n+(-n)$, $1=(n-1)+(-n+2)$, up to $n=0+n$, along with
• $-1=-n+(n-1)$, $-2=(-n+1)+(n-3)$, up to $-n=-1+(-n+1)$.

So, g(n) takes the values $\{n,n-1,\ldots,0\}$ in the first step and $\{-n,-n+1,\ldots,-1\}$ in the second and h(n) takes the values $\{-n,-n+2,\ldots,n\}$ in the first step and $\{n-1,n-3,\ldots,-n+1\}$ in the second step. Hence both g and h are bijections of $A$, and we can clearly see that $i \mapsto g(i)-h(i)$ is also a bijection.

So, yes, I guess it is easy in this case.

Warning: Although the motivation for this question was to prove the existence of an orthomorphism of $\mathbb{Z}$, this is insufficient to prove it.

Now lets consider the case when the equation 0=0+0 is required. We can generate some small random examples, for example, in GAP.

RandomPermutationList:=function(n)
  local A,i,j,temp;
  A:=List([1..n],k->k);
  i:=n;
  while(i>=2) do
    j:=Random([1..i]);
    if(j<i) then
      temp:=A[i];
      A[i]:=A[j];
      A[j]:=temp;
    fi;
    i:=i-1;
  od;
  return A;
end;;

TripleJQuestion2:=function(n)
  local A,B,p,q;
  A:=Concatenation([-n..-1],[1..n]);
  B:=List([1..2*n+1],i->-n-1+i);
  while(true) do
    q:=RandomPermutationList(2*n);
    p:=Concatenation(List([1..n],i->A[q[i]]),[0],List([1..n],i->A[q[n+i]]));
    if(Set(List([1..2*n+1],i->p[i]-B[i]))=B and p[n+1]=0) then return p; fi;
  od;
  return fail;
end;;

This was successful for $4 \leq n \leq 8$:

So, combined with the fact that there are many orthomorphisms of $\mathbb{Z}_n$, it seems very likely that an instance of the desired construction exists for all $n \geq 3$.

But, continuing further (i.e. finding a constructions for all $n \geq 3$) could require considerable effort. If you're really keen on resolving this problem, you could generate lots of random examples, and hope you could generalise enough of them to cover all $n \geq 3$. But why would you want to do this? It's not likely to give a surprising result, and it seems to be a fairly contrived problem (yes, the problem is harder if we assume the equation 0=0+0 is required, but why would anyone be interested in this problem?). And also, unless you somehow build these constructions recursively, you're probably not going to solve the orthomorphisms of $\mathbb{Z}$ existence question.