Sum of three bijections - MathOverflow

Sum of three bijections

2011-02-23T18:59:35Z

Let $\bf N$ be the set of positive integers and let $\bf Q$ be the set of all rational numbers. Consider all functions $f:{\bf Z}\to{\bf Q}$. We say $f$ is a sum of $q_1,q_2,\dots,q_s$ if for all positive integer $n$ the equality $f(n)=q_1(n)+q_2(n)+\dots+q_s(n)$ holds. How can one prove that for each $f:{\bf Z}\to{\bf Q}$ there exist bijections $q_1,q_2,q_3:{\bf Z}\to{\bf Q}$ such that $f=q_1+q_2+q_3$? Is there an easy example of $f$ which is not presentable as a sum of two bijections?

Answer by Fedor Petrov for Sum of three bijections

2011-02-23T19:41:47Z

I guess, Z is N here. We define partial injections $q_1,q_2,q_3$ inductively, on each step they are injections on some finite set. There are different possible steps: 1) add some new positive integer $m$ to the common domain of $q_1,q_2,q_3$. Define $q_1(m)$, $q_2(m)$, $q_3(m)$ so that $q_1$, $q_2$, $q_3$ remain injective and $q_1(m)+q_2(m)+q_3(m)=f(m)$. 2) add given rational $r$ to the range of, say, $q_1$. For this choose some $m$ not from the domain of $q_i$'s and define $q_1(m)=r$, $q_2(m)$ very large, $q_3(m)=f(m)-r-q_2(m)$. So, step by step we construct bijections.

Answer by Jason for Sum of three bijections

2011-02-24T00:12:52Z

One key observation is that with $3$ functions, we are free to have one of them assume any rational value at any Natural number. This is not possible when we only have $2$ functions where after we select the value for $q_1(n)$, we have $q_2(n)$ completely determined by $f(n) - q_1(n)$ and visa versa. The other key observation is that we can split $\mathbb{N}$ into the $3$ disjoint infinite subsets $A_1, A_2, A_3$ with each subset consisting of the set of indices where we make the $q_i$ assume the "next" rational value it has not already assumed according to some bijective enumeration. Specifically:

Fix an arbitrary function $f: \mathbb{N} \rightarrow \mathbb{Q}$ and an arbitrary bijection $e: \mathbb{N} \rightarrow \mathbb{Q}$. The function $e$ induces a well-order, $<_e$ on the set of rational numbers defined by $r\text{ }<_e\text{ }s$ exactly when $e^{-1}(r) < e^{-1}(s)$ (i.e., $r$ is listed before $s$). It also induces a well-order $<_e^*$ on pairs of rationals defined by $\langle r, s\rangle <_e^* \langle t, u\rangle$ exactly when $r\text{ }<_e\text{ }t$ or both $r = t$ and $s\text{ }<_e\text{ }u$ (so-called lexicographical ordering).

We can then define each of the $q_i$ by induction as follows:

If $n \equiv i \pmod 3$, define $q_i(n)$ to be the $<_e$-least rational value not already assumed by $q_i(m)$ for $m < n$.

Then for the $j$ and $k$ such that $n \not\equiv j \pmod 3$ and $n \not\equiv k \pmod 3$, let $\langle r_j, r_k\rangle$ be the $<_e^*$-least pair such that $r_j$ was not assumed by any of the $q_j(m)$ and $r_k$ was not assumed by any of the $q_k(m)$ for $m < n$ and $r_j + r_k = f(n) - q_i(n)$. Note that there is such a pair since there are infinitely many pairs $\langle r_j, r_k\rangle$ satisfying the equality and only finitely many pairs excluded from consideration. Then define $q_j(n) = r_j$ and $q_k(n) = r_k$.

Answer by Gerry Myerson for Sum of three bijections

2011-02-24T01:09:04Z

A simple example of a function which can't be written as a sum of two bijections is given by $f(0)=1$, $f(n)=0$ for $n\ne0$. If there were such bijections $q_1$ and $q_2$, then restricted to $n\ge1$ each would have range missing exactly one rational, and if (the restricted) $q_1$ is missing $r$ then $-r$ can't be in the range of (the restricted) $q_2$ so it must be the missing rational for $q_2$. But then $q_1(0)+q_2(0)=r+-r=0\ne1$.

A related question was asked by Funar in Richard Guy's Unsolved Problems column in the Monthly in 1986, and progress was discussed by Guy in his column in 1987.