Let $f : \mathbb{Z} \rightarrow \mathbb{Z}$ be a bijective function. Prove that you can find two other bijective functions $u$, $v$ from $\mathbb{Z}$ to $\mathbb{Z}$ such that $f(x) = u(x) + v(x)$, $\forall x \in \mathbb{Z}$.
Update (23/03/2008): Solution posted! (show solution)
A solution was written in the comments (in italian), but i will still post the "official" solution because it is short and instructive. Chose an inductive ordering for $\mathbb{Z}$ (for instance $0<-1<1<-2<2<...$). Suppose now that we have defined $u$ and $v$ on a finite set $A\in\mathbb{Z}$ such that they are injective and $f(x) = u(x) + v(x)$, $\forall x \in A$, and start with $A=\emptyset$. Now we can:
Extend the domain: chose the smallest (w.r.t the ordering) $x \in \mathbb{Z}\backslash A$, and define $u(x)$ and $v(x)$ with $f(x) = u(x) + v(x)$ and so that $u$ and $v$ are still injective .We have infinite possible choices for $u(x)$ that automatically also determine $v(x) = f(x) - u(x)$, and they are all good but a finite number (those that make $u$ or $v$ no longer injective).Extend the image of $u$: let's chose the smallest $y \in \mathbb{Z}\backslash u(A)$, and look for an $x \in \mathbb{Z}\backslash A$ such that we can define $u(x) = y$, $v(x) = f(x)-u(x)$ keeping $u$ and $v$ injective. Again, we have infinite $x$ that we can try ($f(x)$ are all different!), this choice also determines $v(x)$, and only a finite number of them is bad.The same as 2, but with $v$ in the place of $u$.After applying any rule the functions will stay injective. Note that if we apply the rule 1 infinite times, we cannot be sure that $u$ and $v$ are sujective, if we apply 2 infinite times, $u$ will be surjective, but possibly not defined everywhere, and similarly for 3 (w.r.t. $v$). But if we apply all them infinite times as 1,2,3,1,2,3,1... we can be sure that $u$ and $v$ are defined everywhere and that they are surjective, because any missing value would be definitively caught by the right rule.
5 comments:
Io proverei cosi': preso il set dei primi dispari ovviamente indicizzati {p_i} proietterei il problema su F_(p_i) definendo
m_i := (p-1)/2
u_(p_i)(n) = m_i (n+1) (mod p_i)
v_(p_i)(n) = m_i (n-1) (mod p_i)
Per ogni n si ha
f(n) = u_(p_i)(n) + v_(p_i)(n) (mod p_i)
e qualunque sia f(n) in Z, conoscere
u_(p_i)(n), v_(p_i)(n)
per ogni i che va da 1 a (abbondiamo)
ceiling(log(f(n))^2)
implica conoscere, per il teorema cinese, l'immagine di n, secondo f, in Z. E' dunque possibile definire due applicazioni da Z in Z che sollevano u_(p_i) e v_(p_i) per i che varia nell'opportuno set di indici. In sostanza risolviamo il problema in F_(p_i) (semplice) e poi liftiamo.
E' corretto? -Jack
No, con gli F_p non funziona. Riprovo:
a meno di comporre con l'inversa di f
basta provare che esistono u,v
bigezioni di Z tali che per ogni n
n = u(n) + v(n)
Ovvero che esiste un insieme J in ZxZ
tale per cui
pi_x(J)=pi_y(J)=Z
e per ogni k esiste un solo elemento
(u,v) di J tale per cui u+v = k.
Preso un ordinamento su Z con minimo,
tipo 0,1,-1,2,-2,3,-3,... possiamo
costruire J induttivamente.
Imponiamo (0,0) in J, e il caso k=0
e' a posto. Guardiamo cosa possiamo
legalmente prendere sulla diagonale
u+v=1 e inseriamo in J l'elemento
con norma-1 |u|+|v| minima (se ce ne
sono due prendiamo quello con |u| piu'
piccola).
Cosi' arriviamo a
k=0 -> (0,0)
k=1 -> (-1,2)
k=-1 -> (1,-2)
k=2 -> (3,-1)
k=-2 -> (-3,1)
k=3 -> (-2,5)
k=-3 -> (2,-5)
k=4 -> (7,-3)
k=-4 -> (-7,3)
...
Con J simmetrico rispetto all'origine,
contenuto nel secondo e nel quarto
quadrante. Notiamo che le curve di
livello della norma |u|+|v|
sono ortogonali rispetto alle diagonali
{u+v = k}, e questo dovrebbe bastare
a garantire la suriettivita' su Z
delle proiezioni di J sugli assi, anche
se devo ancora convincere per bene
me stesso.
J{-} = {(u,v) in J con u<17}
J{+} = {(u,v) in J con u>17}
Credo tu abbia dimenticato di dire che richiedi anche che $J$ abbia fibra di un solo punto per le proiezioni (a propri potrebbe essere piu' grande). Nei termini del problema stai costruendo il grafico della funzione $uv^{-1} :\mathbb{Z} \rightarrow \mathbb{Z}$
In realta' le curve di livello di questa norma sono parallele (e non ortogonali) alle diagonali alle diagonali ${x+y = k}$ nel primo e terzo quadrante (ovvero $(x,y) \in \mathbb{Z}\times\mathbb{Z}$ con entrambi $x$ e $y$ positivi, o entrabi negativi), e ortogonali negli altri due quadranti. In parole povere formano dei quadrati ruotati di 45 gradi, e non mi sembra chiaro come si possa dimostrare usando questa norma che prima o poi vengono presi tutti i valori di $\mathbb{Z}$.
Credo che con qualche piccolo aggiustamento la tua idea si possa far funzionare, magari scegliendo una "euristica" migliore per far funzionare l'algoritmo, che non sia la norma 1 (non ho verificato, ma sono convinto che se minimizzi la quantita' $min(|x|, |y|)$ tutto dovrebbe funzionare nel modo giusto).
J sta tutto nel secondo e nel quarto quadrante; dalla regia mi dicono che il trucchetto di considerare min(|x|,|y|) funziona ed è detto "proprietà del va e vieni"; funziona tuttavia anche la norma-1: supposto che la riga x=37 sia sempre vuota, a patto di andare piuttosto lontano con la norma si ha che la scelta di un punto sulla riga x=37 risulta conveniente rispetto ad ogni altra possibilità, da cui la suriettività; anche perché si ha che P=(u,v) in J implica 37(u+v) < ||P||_1.
Interessante.
Avevo visto che era abbastanza facile dimostrare la surgettività con $min(|u|,|v|)$, ma effettivamente anch'io parlandone con Nicolò mi sono convinto che la norma $1$ andava bene e l'algoritmo di Jack sembrava riempire tutto, e che le scelte dovevano essere nel secondo e quarto quadrante.
Mi piacerebbe però sapere perché, ed inoltre non trovo del tutto convincente la tua dimostrazione per $x=37$, va bene che definitivamente le scelte con $37$ sarebbero convenienti, non mi è chiaro perché non possano essere tutte proibite (ovvero non posso prendere $x+y=n$ con $x=37$ perché $y$ è già stato preso, e questo ogni volta).
Ciao!
Post a Comment