$n \mid i^{\sigma(i)}-j^{\sigma(j)}$

[jordan]

Own. Sia fissato un intero $n \ge 2013$ divisibile per almeno $3$ fattori primi distinti, e sia $\{\sigma(1),\sigma(2),\ldots,\sigma(n)\}$ una qualunque permutazione di $\{1,2,\ldots,n\}$.

Dimostrare che esistono due interi $1\le i < j \le n$ tale che \[ n \mid i^{\sigma(i)}-j^{\sigma(j)} \]

[dario2994]

Piccolo avvertimento al lettore che non credo mai ci sarà: ho scritto il tutto in maniera molto involuta e di conseguenza risulta difficile capire il senso generale della dimostrazione, quindi lo scrivo qui. Mi accorgo che elevare a potenza trasforma i numeri in maniera non reversibile... È un po' come dire prendo una classe di bimbi e aspetto 1 anno... possibile che in qualche ordine alla fine abbiano la stessa altezza che all'inizio? Ovviamente no perchè sono "tutti cresciuti" e stesso ragionamento (cioè il lemma mononota) uso per dimostrare prima il lemma sotto casa e poi il lemma di Evelyne. Questa è in qualche senso la prima idea... l'idea ulteriore che serve (questa è tra le prime cose da tentare dopo aver dimostrato il lemma di Evelyne) è quella che si nasconde dietro il lemma di Dedalo: cioè considerare le valutazioni degli ordini (in particolare per il problema serviva contare quanti ordini dovevano essere pari e accorgersi che sono troppi). Da lì in poi si vede che si riuscirà a concludere purchè muniti di una sufficiente dose di pazienza.

Prendo $n$ tale che esista una permutazione $\sigma$ tale che: $\forall 1\le i < j \le n:\ n\nmid i^{\sigma(i)}-j^{\sigma(j)}$.
Dimostrerò che $n\le 18$ oppure esiste un primo $p$ tale che $p-1$ è squarefree e $n=p$ o $n=2p$. (che implica banalmente quanto richiesto dal problema)

Innanzitutto detta $\tau(i)=i^{\sigma(i)}\pmod{n}$ ho che $\tau$ è una permutazione.

Lemma mononota: Data $f:\mathbb{N}\to \mathbb{Z}$ tale che:

• $\forall x,t\ge 1:\ f(x^t)\ge f(x)$
• $x\equiv y\pmod n \Rightarrow f(x)=f(y)$

Vale che $\forall 1\le i \le n:\ f(i)=f(\tau(i))$
Dim. Poichè $\tau$ è una permutazione vale $\sum_{i=1}^nf(i)=\sum_{i=1}^nf(\tau(i))$.
Ma dalle 2 ipotesi su $f$ so che vale anche $\forall 1\le i\le n:\ f(i)\le f(\tau(i))$.
Unendo questi due fatti ottengo facilmente la tesi.

Lemma sotto casa: $n$ è squarefree oppure $n=4$.
Dim. Assumo per assurdo che $q^2|n$ con $q$ primo. Allora definisco $u_q:\mathbb{N}\to \mathbb{N}$ come $u_q(x):= \min(\upsilon_q(x),\upsilon_q(n))$.
Vale facilmente che $u_q$ rispetta le ipotesi del lemma mononota e quindi ne ricavo $\forall 1\le i \le n:\ u_q(i)=u_q(\tau(i))$.
Ma preso $x$ tale che $\upsilon_q(x)=1$ e $x\le n$ ottengo che $u_q(x)=u_q(x^{\sigma(x)}) \Rightarrow \sigma(x)=1$. Quindi se avessi almeno 2 elementi $x_1,x_2$ che rispettano queste ipotesi avrei un assurdo visto che $\sigma(x_1)=1=\sigma(x_2)$. E questi due elementi li ho banalmente a meno che $n=4$.

D'ora in poi userò implicitamente la tesi del lemma sotto casa ($n$ squarefree) e inoltre con la lettera $p$ identificherò sempre un numero primo.
Definisco $O:\mathbb{N}\to \mathbb{N}$ come $O(x):=lcm\{Ord_p(x):\ p|n\}$, definendo per consistenza che $Ord_p(0)=1$.
Lemma di Evelyne: Vale $\forall 1\le i \le n:\ gcd(O(i),\sigma(i))=1$
Dim. Risulta che la funzione $-O$ rispetta le ipotesi del lemma mononota e ne ricavo perciò $\forall 1\le i \le n:\ O(i)=O(i^{\sigma(i)})$.
Ma vale più o meno facilmente che $O(x^t)=\frac{O(x)}{gcd(O(x),t)}$. E unendo queste ultime 2 uguaglianze ricavo: $gcd(O(i),\sigma(i))=1$.

Lemma di Dedalo: Dato $q$ primo vale:
$ \displaystyle \prod_{p|n}\left(\frac{(p-1)}{q^{\upsilon_q(p-1)}}+1\right)\ge \frac{n}{q}-1 $
Dim. Definisco $S_q=\{i:\ 1\le i\le n \wedge q\nmid O(i)\}$, $T_q=\{i:\ 1\le i\le n \wedge q\mid\sigma(i)\}$.
Il lemma di Evelyne implica $|S_q|\ge |T_q|$, ed ora scriverò esplicitamente $|S_q|,|T_q|$.
Banalmente si ricava $|T_q|=\lfloor \frac{n}{q} \rfloor \ge \frac{n}{q}-1$ poichè $\sigma$ è una permutazione.
Per esprimere $|S_q|$ fattorizzo $n=\prod_{j=1}^kp_j$ (uso il lemma sotto casa) e associo ad $i$ una $k$-upla di interi $(a_1,a_2,\dots , a_k)$ tali che $i\equiv a_j\pmod{p_j}\forall 1\le j\le k$.
Allora risulta $i\in S_q \iff q\nmid O(i) \iff \forall 1\le j \le n:\ q\nmid Ord_{p_j}(a_j)$.
Ma per lemma più o meno noto (si dimostra usando un pizzico di generatori) $a_j$ può assumere $\frac{(p_j-1)}{q^{\upsilon_q(p_j-1)}}+1$ valori.
E ora applicando il teorema cinese del resto ricavo che $i$ può assumere questo numero di valori:
$ \displaystyle |S_q|=\prod_{p|n}\left(\frac{(p-1)}{q^{\upsilon_q(p-1)}}+1\right) $
Quindi sostituendo quanto trovato in $|S_q|\ge |T_q|$ ottengo la tesi del lemma.

Lemma di cip: Per $x>a\ge 1$ interi vale $\frac{x-1}{a}+1\le \frac{2x}{a+1}$.
Dim. $ \displaystyle \frac{2x}{a+1}-\frac{x-1}{a}=\frac{x(a-1)+a+1}{a(a+1)} \ge \frac{(a+1)(a-1)+a+1}{a(a+1)}=1 $
E questa portando dalla parte giusta le cose è la tesi.

Lemma di ciop: Dati $x\ge 2,\ t\ge 0$ interi vale $\frac{(x+1)^t}{2^{t-1}} \le (x^t+1)$.
Dim. Per $t=0,1$ vale facilmente l'uguaglianza.
Se $x=t=2$ ho $9\le 10$ che è vero.
Se $x=2$ e $t\ge 3$ vale:
$ \displaystyle \left(\frac{x+1}{2x}\right)^t\le \left(\frac34\right)^3\le \frac12 \Rightarrow \frac{(x+1)^t}{2^{t-1}} \le (x^t+1) $
Se $x\ge 3$ (che è l'unico caso restante) vale:
$ \displaystyle \left(\frac{x+1}{2x}\right)^t\le \left(\frac46\right)^2\le \frac12 \Rightarrow \frac{(x+1)^t}{2^{t-1}} \le (x^t+1) $

Ebbene ora i lemmi sono finiti e non resta che unire i lemmi di Dedalo, cip e ciop ottenendo:
$ \displaystyle \frac{n}{q}-1\le \prod_{p|n}\left(\frac{(p-1)}{q^{\upsilon_q(p-1)}}+1\right) \le \prod_{p|n} \frac{2p}{q^{\upsilon_q(p-1)}+1}\le \prod_{p|n}p\cdot \left(\frac{2}{q+1}\right)^{\upsilon_q(p-1)}=n\left(\frac{2}{q+1}\right)^{\upsilon_q(\prod_{p|n} p-1)} $
Dividendo da entrambe le parti per $n$ e definendo $t=\upsilon_q(\prod_{p|n} p-1)$ ottengo: $\frac{1}{q}-\frac{1}{n}\le \left(\frac{2}{q+1}\right)^t$
Ponendo $q=2$ e assumendo $t\ge 2$ quest'ultima disuguaglianza implica $\frac12-\frac1n\le \frac49 \Rightarrow n\le 18$. Ma allora questo vuol dire che per $n>18$ non esistono 2 primi dispari che dividono $n$ (altrimenti $t\ge 2$) e questo unito al lemma sotto casa mi implica $n=p$ o $n=2p$ (userò che $n$ è di questa forma d'ora in poi). Inoltre vale anche che $4$ non divide $p-1$ altrimenti avrei $t\ge 2$.
Ponendo invece $q=2$ e assumendo $t\ge 2$ con passaggi analoghi arrivo a $n\le 12$, quindi per $n > 12$ e sfruttando quanto ottenuto alla riga precedente su $n$ ho che $p-1$ non è divisibile per 9. (altrimenti $t\ge 2$)
Infine pongo $q\ge 5$ e assumo $t\ge 2$. Allora devo avere $q^2|p-1 \Rightarrow n\ge q^2$ e quindi dalla disuguaglianza ricavo:
$ \displaystyle \frac1q-\frac1{q^2}\le \left(\frac2{q+1}\right)^2 \Rightarrow q(q+1)^2-(q+1)^2\le 4q^2 \Rightarrow 4q^2 > q^3+2q+1-q^2-2q-1 \Rightarrow 5q^2>q^3\Rightarrow 5>q $
E questo è assurdo quindi vale $t<2$ e perciò $q^2\nmid p-1$.
Unendo i fatti ottenuti ottengo $p-1$ squarefree.

P.S. Per terminare la cosa aggiungo che un pc mi ha detto che gli $n\le 18$ che rispettano sono $1,2,3,4,5,6,7,11,14$.

[jordan]

P.S. Per terminare la cosa aggiungo che un pc mi ha detto che gli $n\le 18$ che rispettano sono $1,2,3,4,5,6,7,11,14$.

Controllo la tua dimostrazione a breve; nel frattempo, senza l'aiuto di un pc, trova tutti e soli gli $n\le 61$, senza l'aiuto di un pc

Ps. Poi, se mi controlli (col pc) se funziona per $n=62$ mi faresti un favore..

[jordan]

L'ho riletta due volte con calma, fatto sta che non ho capito la tua idea di base: ho usato anch'io $|T_q|$, e una disuguaglianza con un altro insieme, ma diverso da $S_q$. Il mio problema sta comunque nella definizione di $O(\cdot)$, che per come è definito divide sempre $\varphi(\text{rad}(n))$..

[dario2994]

Il mio problema sta comunque nella definizione di $O(\cdot)$, che per come è definito divide sempre $\varphi(\text{rad}(n))$..

È vero...
In ogni caso dimmi quali passaggi non ti sono chiari e proverò a riscriverli! (o magari a confutarli )

p.s. Riguardo il caso $n=62$ purtroppo non riesco a farlo manco col pc.

[jordan]

Innanzitutto detta $\tau(i)=i^{\sigma(i)}\pmod{n}$ ho che $\tau$ è una permutazione.

Lemma mononota: Data $f:\mathbb{N}\to \mathbb{Z}$ tale che:

• $\forall x,t\ge 1:\ f(x^t)\ge f(x)$
• $x\equiv y\pmod n \Rightarrow f(x)=f(y)$

Vale che $\forall 1\le i \le n:\ f(i)=f(\tau(i))$
Dim. Poichè $\tau$ è una permutazione vale $\sum_{i=1}^nf(i)=\sum_{i=1}^nf(\tau(i))$.
Ma dalle 2 ipotesi su $f$ so che vale anche $\forall 1\le i\le n:\ f(i)\le f(\tau(i))$.
Unendo questi due fatti ottengo facilmente la tesi.

Ok, cominciamo dall'inizio: sebbene si capisce si capisce cosa intendi, una volta fissata una permutazione $\{\sigma(1),\ldots,\sigma(n)\}$ di $\{1,\ldots,n\}$ per qualche intero $n\ge 1$, $\tau(\cdot)$ è una funzione da $\mathbb{Z}$ in $\{1,\ldots,n\}$ tale che \[ \tau(i):=i^{\sigma(i)}+n\left(1-\left\lceil \frac{i^{\sigma(i)}}{n} \right\rceil \right) \]
Dato che per ipotesi $\{\tau(1),\ldots,\tau(n)\}$ è una permutazione di $\{1,\ldots,n\}$ allora in particolare: \[\sum_{1\le i\le n}{f(i)}=\sum_{1\le i\le n}{f(\tau(i))} \]
qualunque sia $f\colon \{1,\ldots,n\} \to \mathbb{Z}$ fissata. Ora, aggiungiamo l'ipotesi che $f(\cdot)$ sia iniettiva e che $f(a^b)\ge f(a)$ per ogni $a,b \in \mathbb{N} \setminus \{0\}$. Ora, perchè \[ f(\tau(i)) \ge f(i) \text{ per ogni } i=1,2,\ldots,n \]
?

[dario2994]

Solo dopo aver scritto tutto il messaggio credo di aver capito ciò che ha generato l'incomprensione... hai sbagliato a leggere la freccia nella seconda ipotesi del lemma mononota: cioè $x\equiv y\pmod n\Rightarrow f(x)=f(y)$. Tu hai letto la freccia al contrario, che equivaleva a chiedere l'iniettività di $f$.

qualunque sia $f:\{1,…,n\}\to\mathbb{Z}$ fissata

No, $f:\mathbb{N}\to \mathbb{Z}$.

Ora, aggiungiamo l'ipotesi che $f(\cdot)$ sia iniettiva

Non dobbiamo aggiungere quest'ipotesi.

In ogni caso ecco una dimostrazione esageratamente dettagliata del lemma mononota (mantengo le mie ipotesi e chiamo la prima (1) e la seconda (2) ):
Vale \[\sum_{i=1}^n f(i)= \sum_{i=1}^n f(\tau(i))\] (e qui mi pare che siamo d'accordo).
Allora, portando tutto allo stesso membro, ottengo: \[\sum_{i=1}^n \left( f(\tau(i))-f(i) \right) =0\ \ \ \ (*)\]
Per l'ipotesi (2) ottengo $f(\tau(i))=f(i^{\sigma(i)})$.
Per l'ipotesi (1) ho $f(i^{\sigma(i)})\ge f(i)$.
Unendo questi 2 risultati arrivo a $f(\tau(i))=f(i^{\sigma(i)})\ge f(i)$
Da questa, portando tutto allo stesso membro, ricavo $f(\tau(i))-f(i)\ge 0\ \ \ (**)$
Unendo $(*),\ (**)$ mi pare scontato che si arriva alla tesi del lemma...

[jordan]

Tu hai letto la freccia al contrario, che equivaleva a chiedere l'iniettività di $f$.[...] Non dobbiamo aggiungere quest'ipotesi

Ero convinto fosse al contrario, difatti l'ho anche scritto sopra, sorry

No, $f:\mathbb{N}\to \mathbb{Z}$.

Sarebbe sufficiente definirla da $\{1,\ldots,n^n\} \to \mathbb{Z}$ per cio' che serve, ma cambia nulla..

Lemma sotto casa: $n$ è squarefree oppure $n=4$.
Dim. Assumo per assurdo che $q^2|n$ con $q$ primo. Allora definisco $u_q:\mathbb{N}\to \mathbb{N}$ come $u_q(x):= \min(\upsilon_q(x),\upsilon_q(n))$. Vale facilmente che $u_q$ rispetta le ipotesi del lemma mononota e quindi ne ricavo $\forall 1\le i \le n:\ u_q(i)=u_q(\tau(i))$. Ma preso $x$ tale che $\upsilon_q(x)=1$ e $x\le n$ ottengo che $u_q(x)=u_q(x^{\sigma(x)}) \Rightarrow \sigma(x)=1$. Quindi se avessi almeno 2 elementi $x_1,x_2$ che rispettano queste ipotesi avrei un assurdo visto che $\sigma(x_1)=1=\sigma(x_2)$. E questi due elementi li ho banalmente a meno che $n=4$.

Bien, poi vado avanti. Sono sicuro che il risultato $n \in \mathbb{P} \cup 2\mathbb{P}$ è corretto (e si puo' fare di meglio), poi metterò anche la mia

[jordan]

Definisco $O:\mathbb{N}\to \mathbb{N}$ come $O(x):=lcm\{Ord_p(x):\ p|n\}$, definendo per consistenza che $Ord_p(0)=1$.
Lemma di Evelyne: Vale $\forall 1\le i \le n:\ gcd(O(i),\sigma(i))=1$
Dim. Risulta che la funzione $-O$ rispetta le ipotesi del lemma mononota e ne ricavo perciò $\forall 1\le i \le n:\ O(i)=O(i^{\sigma(i)})$. Ma vale più o meno facilmente che $O(x^t)=\frac{O(x)}{gcd(O(x),t)}$. E unendo queste ultime 2 uguaglianze ricavo: $gcd(O(i),\sigma(i))=1$.

Ok, ma $Ord_p(kp)$ con $k \in \mathbb{N}\setminus \{0\}$?

[dario2994]

Ok, ma $Ord_p(kp)$ con $k \in \mathbb{N}\setminus \{0\}$?

$=1$

[jordan]

P.S. Per terminare la cosa aggiungo che un pc mi ha detto che gli $n\le 18$ che rispettano sono $1,2,3,4,5,6,7,11,14$.

Ho controllato il resto, e funziona tutto, bravo

Bonus: Trovare tutti e soli interi dispari che soddisfano la tesi..

[jordan]

Metto una domanda bonus piu' facile: mostrare che $\frac{n-1}{2}$ e $n$ sono entrambi primi allora $n$ è un numero tale che esiste (almeno) una suddetta permutazione.

ps. E' stato mostrato molto recentemente che esistono infiniti primi $p$ tali che $2p+1$ è anch'esso primo..

ps2. Sto aspettando che qualcuno mi corregga il mio (pessimo) inglese, prima di postare la dimostrazione

[<enigma>]

ps. E' stato mostrato molto recentemente che esistono infiniti primi $p$ tali che $2p+1$ è anch'esso primo..

[jordan]

ps. E' stato mostrato molto recentemente che esistono infiniti primi $p$ tali che $2p+1$ è anch'esso primo..

Si, manco wikipedia è aggiornata: http://www.wseas.us/e-library/transacti ... 53-517.pdf

[dario2994]

ps. E' stato mostrato molto recentemente che esistono infiniti primi $p$ tali che $2p+1$ è anch'esso primo..

Si, manco wikipedia è aggiornata: http://www.wseas.us/e-library/transacti ... 53-517.pdf

Non sono un esperto degli esperti, ma un articolo di sole 10 pagine, pubblicato nel 2011 e ancora non noto, che sembra anche semielementare, scritto non in latex, da uno che su google è introvabile (Fengsui Liu) che dimostra un problema strafamoso e aperto da chissà quanto non mi sembra il massimo dell'affidabilità
Poi se tu l'hai letto o qualcuno di importante l'ha letto e dice che è giusto ben venga, ma se è un articolo ancora da checkare aspetterei ad esultare