Comments on Accumulated Evidence: Bijective function

Interessante.Avevo visto che era abbastanza facile...

2008-03-20T16:51:00.000-07:00

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!

J sta tutto nel secondo e nel quarto quadrante; da...

2008-03-20T15:32:00.000-07:00

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.

Credo tu abbia dimenticato di dire che richiedi an...

2008-03-20T14:04:00.000-07:00

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

No, con gli F_p non funziona. Riprovo: a meno di c...

2008-03-16T09:51:00.000-07:00

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}

Io proverei cosi': preso il set dei primi dispari ...

2008-03-15T10:27:00.000-07:00

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