Permutazione di residui modulo p

[jordan]

E' un problema di cui non conosco la soluzione, nè so' se esiste; per cui mi scuso nel caso risultasse una perdita di tempo..


Siano fissato un primo dispari e due insiemi A=B={1,2,...,2p-1}/{p}.

Esiste una funzione bigettiva f da A in B tale che {1f(1),2f(2),...,(p-1)f(p-1)} e {(p+1)f(p+1),(p+2)f(p+2),...,(2p-1)f(2p-1)} rappresentano entrambi tutti i residui non nulli modulo p?


Edit: per p=3 e p=5 tale f esiste..

[fph]

Non capisco la tua notazione... Cos'è {1,2,...,2p-1}/{p}? Perché lo stesso insieme si chiama sia A che B?

[EvaristeG]

Credo che il problema sia:

dati un primo dispari $p$ e l'insieme $X=\{1,\ldots, 2p-1\}\setminus\{p\}$
Esiste una permutazione $f:X\to X$ tale che {1f(1),2f(2),...,(p-1)f(p-1)} e {(p+1)f(p+1),(p+2)f(p+2),...,(2p-1)f(2p-1)} rappresentano entrambi tutti i residui non nulli modulo p?

[jordan]

Sì, esatto; se si prende $X$ come $k$ dispari volte $\{1,2,...,p-1\}$ il problema (in questo caso, molto conosciuto) non ha soluzione..

Il problema qui è per $k=2$: tale $f$ esiste sempre?

[Troleito br00tal]

Intanto se $p \equiv 3$ modulo $4$ possiamo dire $f(x)=x$ se $0<x<\frac{p}{2}$, $f(x)=2p-x$ se $\frac{p}{2}<x<p$, $f(x)=2p-x$ se $p<x<\frac{3p}{2}$ e $f(x)=x$ se $\frac{3p}{2}<x<2p$, che è biettiva e funziona.

[Troleito br00tal]

Induzione su $b$.

Per $p \equiv 1$ modulo $4$. Sia $v_2(p-1)=b$. Sia $i^{b-1} \equiv -1$ modulo $p$. Allora io posso esprimere ${1,...,p-1}$ come unione dei residui modulo $p$ $A=(1^2,2^2,...,(\frac{p-1}{2})^2)$ e $B=(i1^2,i2^2,...,i(\frac{p-1}{2})^2)$, che sono tra l'altro insiemi disgiunti. Tenendo conto che io posso scegliere due volte ogni residuo (sono gli stessi anche per $(p+1,...,2p-1)$), se io ora scelgo $f(x)$ per $0<x<p$ appartenente sempre in $A$ oppure sempre in $B$, ottengo due insiemi disgiunti, un insieme di residui quadratici e un insieme di non residui quadratici, che come visto sopra si può esprimere come un insieme di residui quadratici moltiplicato per $i$. A questo punto io ho ottenuto due classi di resto $quasi$ moltiplicative (totalmente moltiplicative se isoliamo $i$): la cardinalità del mio insieme $(1,...,p-1)$ si è esattamente dimezzato, di conseguenza mi basta dimostrare che esiste una funzione per $b-1$ (poiché in realtà non è necessario che $\frac{p+1}{2}$ sia primo, ma mi basta che le classi di resto possano essere rese per omotetia un insieme in cui la moltiplicazione è interna).

Il passo base è sopra.

Spero si capisca, anche perché l'idea è davvero brute force.

[jordan]

Grazie per averci provato, per prima cosa

Intanto se $p \equiv 3$ modulo $4$ possiamo dire $f(x)=x$ se $0<x<\frac{p}{2}$, $f(x)=2p-x$ se $\frac{p}{2}<x<p$, $f(x)=2p-x$ se $p<x<\frac{3p}{2}$ e $f(x)=x$ se $\frac{3p}{2}<x<2p$, che è biettiva e funziona.

Funziona, very good. (Anzi, no, speravo fosse il contrario! xd)

Induzione su $b$. Per $p \equiv 1$ modulo $4$. Sia $v_2(p-1)=b$. Sia $i^{b-1} \equiv -1$ modulo $p$. Allora io posso esprimere ${1,...,p-1}$ come unione dei residui modulo $p$ $A=(1^2,2^2,...,(\frac{p-1}{2})^2)$ e $B=(i1^2,i2^2,...,i(\frac{p-1}{2})^2)$, che sono tra l'altro insiemi disgiunti.

Ok, mi sono fermato qui: poniamo che esiste un $k$ dispari e un intero $b\ge 1$ tale $p=k2^b+1$. Ora come viene definito l'intero $i$? Dobbiamo avere $i^{b-1} \equiv -1 \bmod p$: in particolare $\text{gcd}(i,p)=1$, per cui esiste $j \in \{1,2,\ldots,p-1\}$ e $g$ generatore di $\mathbb{Z}/p\mathbb{Z}$ tale che $g^j \equiv i \bmod p$. Allora la condizione è che, fissato un primo $p\equiv 1\bmod 4$ valga: \[ g^{j(b-1)} \equiv i^{b-1} \equiv -1 \equiv g^{\frac{1}{2}(p-1)} \equiv g^{k2^{b-1}} \bmod p \]
che è equivalente a $j(b-1) \equiv k2^{b-1} \bmod{p-1} \equiv k2^{b-1} \bmod{k2^b}$. Ora $k$ e $b$ sono fissati, è sufficiente prendere $k\mid j$ e $\upsilon_2(j)+\upsilon_2(b-1)=b-1$, il che mi sembra possibile, per tcr. In particolare, è vero per:
\[ j:=k2^{b-1-\upsilon_2(b-1)} \] Bene, $i$ è ben definito.
Ora, perchè $A$ e $B$ sono disgiunti e rappresentano tutti i residui non nulli modulo $p$? $A$ rappresenta tutti i residui quadratici non nulli, bien. $B$ dovrebbe rappresentare quindi tutti i residui non quadratici: $ix^2$ è residuo non quadratico se e solo se $i$ è non quadratico: assunto che $p=k2^b+1\equiv 1 \bmod 4$ per cui $b\ge 2$, dobbiamo mostrare che $\left(\frac{i}{p}\right)=\left(\frac{g^{k2^{b-1-\upsilon_2(b-1)}}}{k2^b+1}\right)=-1$.. ? Si sta quindi cercando di definire un $i$ residuo non quadratico in funzione di $b$..?

Ora, un intero x non multiplo di p tale che $x\equiv g^y\bmod p$ per qualche $y \in \{1,2,\ldots,p-1\}$ è residuo non quadratico se e solo se $y$ è dispari. Nel nostro caso $i=g^{k2^{b-1-\upsilon_2(b-1)}}$ è residuo non quadratico se e solo se $k2^{b-1-\upsilon_2(b-1)}$ è dispari, i.e. se e solo se $b-1=\upsilon_2(b-1) \le \ln_2(b-1) = \mathcal{O}(\ln b)$, che non mi pare molto vera per $b$ abbastanza grande..

[Troleito br00tal]

Sono un enorme idiota, in realtà per $i$ vale:
\begin{equation}
i^{2^{b-1}} \equiv -1
\end{equation}

Altrimenti effettivamente non aveva molto senso (tra l'altro chi mi garantiva che io potessi dividere $b$ per $2$ fino a ricondurmi al passo base?)!

Grazie per la correzione , prova a rivederla ora!