Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers

up vote 3 down vote accepted

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$.

share|improve this answer
    
Yep, it works perfectly! Thanks a lot! –  blanco Feb 24 '11 at 18:43
add comment

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.

share|improve this answer
    
Thanks a lot! It works, i wonder why i am so stupid... –  blanco Feb 24 '11 at 18:45
    
Many of us are stupid at times. I tried several other complex examples and missed this one. Good thing Gerry thought to post it, otherwise we might still be waiting for rescue. Gerhard "Not Lost In Thought Now" Paseman, 2011.02.24 –  Gerhard Paseman Feb 24 '11 at 20:38
add comment

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.

share|improve this answer
1  
You should mention that you vary the index on q for different invocations of step 2. That way you know you are building up the range of each function so that they will each be (eventually) bijective. Gerhard "Ask Me About System Design" Paseman, 2011.02.23 –  Gerhard Paseman Feb 23 '11 at 23:25
    
I tried to mention it by saying "say, $q_1$" instead "$q_1$". –  Fedor Petrov Feb 24 '11 at 10:20
    
Yes, and I understood that. However, I thought that some ambiguity needed to be resolved. I could also read that part as, "add a given rational to the range of q_1 each time", and decided a comment to clarify was appropriate. I like the solution, by the way. Gerhard "Ask Me About System Design" Paseman, 2011.02.24 –  Gerhard Paseman Feb 24 '11 at 20:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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