due bastano

[ma_go]

ufficialmente, questo è un IMC, quindi lo metto in MNE...
però mi pare fattibile anche da chi l'università la guarda da molto distante (salvo metterla in termini un pochino meno tecnici).

versione "universitaria"
dunque, siano $ X $ un insieme, $ G = S_X $ l'insieme delle bigezioni su $ X $, e $ H $ l'insieme delle bigezioni di ordine al più$ 2 $ su $ X $ (*).
dimostrare che $ H^2 = G $.

versione "olimpica" (la lascio in bianco, senza LaTeX)
dato un'insieme X, e f bigettiva su X esistono g,h su X tali che g(g(x)) = h(h(x)) = x per ogni x, e f = h(g).


$ H = G^{(2)} = \{f\in S_X | f\circ f = e\} $, dove $ e $ è la mappa identica su $ X $..
$ H $ si chiama componente di 2-torsione, forse? la notazione $ G^{(2)} $ è standard? chiedo illuminazione...

EDIT: mi faccio notare (grazie al mio omonimo) che ho scritto due cose diverse...

[Marco]

Che è $ H^2 $? L'insieme dei prodotti $ h_1 \circ h_2 $?
EDIT: ah, ok. Ho visto la versione "olimpica"...

[Nonno Bassotto]

Ho appena letto il problema, quindi rispondo solo alla questione terminologica. L'insieme che definisci tu si chiama effettivamente componente di 2 torsione, con alcune precisazioni.

La prima e' che di solito si parla di componente di torsione solo per gruppi abeliani (altrimenti non e' un sottogruppo e la nozione non e' molto utile). La seconda e' che alcuni chiamano componente di p torsione, per un certo primo p, gli elementi non necessariamente di ordine p, ma di ordine una potenza di p, quindi bisogna stare attenti quando si legge. Io seguo la tua convenzione: la 2 torsione consiste solo degli elementi di ordine 2.

Infine la notazione usuale per la componente di n torsione in un gruppo abeliano A e' A[n].
Ciao

[ma_go]

danke schoen, nonno bassotto
ora, una mini-postilla riguardo al problema...
la soluzione che ho trovato io è alquanto pallosa da scrivere, quindi si accettano anche sketch più o meno approfonditi della soluzione: l'idea di fondo mi pare abbastanza semplice, e spero si capisca abbastanza da quella...

[Marco]

Non è poi così lungo da scrivere... Ci vuole l'Assioma di Scelta e ad occhio direi che per insiemi arbitrari, AC sia strettamente necessario.

Step 1. Ricondursi ad un gruppo ciclico.

Non è restrittivo supporre che X sia un gruppo ciclico (eventualmente infinito: Z) e f sia la traslazione di 1: f(z) = z+1.

Infatti: basta considerare la partizione in orbite indotta da applicazioni successive di f. Le orbite sono o finite o numerabili. Scelgo arbitrariamente un rappresentante in ogni orbita, che chiamo 0. Sull'orbita induco una struttura additiva con la relazione z+1 := f(z). In tal modo il gruppo ciclico generato da f risulta isomorfo in modo naturale all'orbita, vista come gruppo additivo. []

Se trovo g e h indipendentemente su ogni orbita, ho finito.

Step 2: esibire g e h per il caso ciclico.

g(z) = -z (simmetria rispetto allo 0)
h(z) = 1-z (simmetria rispetto ad "1/2")

verificano le ipotesi. []

[Marco]

Ah.... e giusto per fare il pignolo inutilmente e rompere un po' le scatole, la tesi è falsa se X ha un solo elemento...

[nella mia dimostrazione, occorrerebbe dire due parole sulle orbite di cardinalità 1. (altrimenti gli ordini di g e h collassano a 1). Se però ci sono almeno due punti fissi, siamo salvi.]

[ma_go]

uh, che carina
l'hai scritta davvero bene... sono quasi emozionato!
io avevo fatto un casino per il caso di orbite finite.. va bene che sono miope, ma non pensavo così tanto!

comunque... ehm, sì... ho scritto due cose diverse... nella definizione data di $ H $ (quella in asterisco) va bene anche la tua soluzione (nel senso che è contemplata anche l'identità, quindi il caso di $ X $ singoletto funge comunque), così come la tua soluzione va bene per la "versione olimpica"... direi che edito, quindi...

ps. mi pare che questo sia un risultato discretamente forte... nel senso, ogni permutazione può essere scritta come prodotto di due prodotti di trasposizioni disgiunte... e la cosa potrebbe risultare utile da qualche parte, no?

[MindFlyer]

[nella mia dimostrazione, occorrerebbe dire due parole sulle orbite di cardinalità 1. (altrimenti gli ordini di g e h collassano a 1). Se però ci sono almeno due punti fissi, siamo salvi.]

Non è necessario che vi siano 2 punti fissi, basta che X abbia almeno 2 elementi. Infatti le g e h descritte coincidono con l'identità solo sulle orbite di cardinalità 1.
Quindi se vi sono orbite di cardinalità >1, siamo salvi in ogni caso.
Se tutte le orbite hanno cardinalità 1 (i.e. f=e), basta prendere g=h!=e, che esiste se e solo se #X>1.

[MindFlyer]

Rilancio:
In quali casi (per quali X e f) esistono delle g e h che risolvono il problema, e tali che g(x)!=x e h(x)!=x per ogni x?

[Marco]

Rilancio:
In quali casi (per quali X e f) esistono delle g e h che risolvono il problema, e tali che g(x)!=x e h(x)!=x per ogni x?

...mmmmmmmh.... a me viene "mai". Corretto?

EDIT: no che non lo è! Basta prendere X con due elementi e f l'identità per fare un contresempio! Meglio che ci pensi un altro po'ino...

[ma_go]

uhm.. parrebbe funzionare per tutte le $ f $ tali che, per ogni $ n $ intero positivo (e anche "$ n=\infty $"), le orbite di lunghezza $ n $ siano pari o infinite.
sottolineo, parrebbe: l'ho verificato per $ n=\infty,1,2,3 $ e congetturo la costruzione funzioni anche dopo...

[Marco]

Dimostrato!

E' possibile se e solo se, per ogni possibile cardinalità, le orbite di f di data cardinalità sono in numero pari, oppure infinito.

EDIT: ah, vedo ora il messaggio dell'altro Marco: il tuo claim è quello giusto.

[ma_go]

uhm.. ne sei così sicuro?
fissa un'orbita, $ \text{orb}(x) $, e supponi $ g(x) = f^k(x) $. allora (e si dimostra per induzione) almeno una delle due tra $ g $ ed $ h $ ammette punto fisso, più precisamente $ f^m $, per un certo intero $ 0 \le |m|\le |k| $.
e questo dimostra che, in buona sostanza, il caso in cui la cardinalità di orbite di una cardinalità fissata dev'essere pari o infinita: se $ g(f^k(x)) \in \text{orb}(y) $, allora $ g(\text{orb}(x)), h(\text{orb}(x)) \subset \text{orb}(y) $, e viceversa... quindi le due orbite devono avere la stessa cardinalità, quindi se esistono tali $ g,h $ allora l'insieme delle orbite di cardinalità fissata dev'essere partizionabile in coppie.
viceversa, costruire tali $ g,h $ che "rimbalzino" da un'orbita all'altra, con le proprietà richieste è una variante della costruzione di Marco...

EDIT: mind ha cancellato il suo messaggio in mezzo, in cui supponeva che il discorso fatto da Marco valesse solo per le orbite finite, indi l'incipit del mio post...
EDIT 2: il mio discorso è assai poco dettagliato, spero non vogliate tutti i bourbakismi del caso : a me basterebbe una conferma di Marco

[Marco]

In linea di massima la dimostrazione mi torna. Manca di specificare un po' di dettagli noiosi, ma nella sostanza funziona. Ad ogni modo, durante la pausa pranzo ho scritto la dimostrazione per benino. Quando risalgo al mio PC provo a postarla e si vede. Ma l'idea e' più o meno la tua (solo che è scritta meglio ...)

[MindFlyer]

Cazzo ma_go, quel messaggio delirante è rimasto lì per meno di 2 minuti e sei riuscito a sgamarlo???
Comunque sì, concordo con le varie congetture più o meno dimostrate..