divisibilità?

[ma_go]

siano $ n $ un intero non-negativo, e $ p $ un primo.
dimostrare che $ \displaystyle n! \mid \prod_{k=0}^{n-1} (p^n - p^k) $.

[HiTLeuLeR]

Fissati $ n\in\mathbb{N} $ e un primo intero $ p > 0 $, si tratta di provare che, per ogni $ q \in \mathfrak{P} $: [*] $ \displaystyle v_q(n!) \le \sum_{k=0}^{n-1} v_q(p^n - p^k) = $ $ \displaystyle\frac{n(n-1)}{2} v_q(p) + \sum_{k=1}^{n} v_q(p^k - 1) $, ove $ v_q(\cdot) $ indica una valutazione $ q $-adica. La tesi è banale se $ n = 0 $ oppure $ n = 1 $ o se ancora $ q > n $. Perciò ammettiamo per il seguito $ 2 \le q \le n $. In base all'identità di Legendre-De Polignac $ \displaystyle v_q(n!) = \sum_{k=1}^{\lfloor \log_q n\rfloor} \left\lfloor \frac{n}{q^k}\right\rfloor \le \frac{n(n-1)}{q(q-1)} \le \frac{n(n-1)}{2} $, con uguaglianza soddisfatta sse $ n = q = 2 $. Onde dedurne che la [*] è chiaramente verificata se $ q = p $. Sia perciò d'ora innanzi $ q \neq p $, i.e. $ \gcd(p,q) = 1 $. In tal caso $ v_q(p) = 0 $, e si è così riportati a dimostrare che [**] $ \displaystyle v_q(n!) \le \sum_{k=1}^{n} v_q(p^k - 1) $. Sia $ \omega := \mbox{ord}_q(p) $. Risulta $ 1 \le \omega \le q-1 \le n-1 $ e $ \displaystyle \sum_{k=1}^{n} v_q(p^k - 1) = $ $ \displaystyle \sum_{k=1}^{\lfloor n/\omega \rfloor } v_q(p^{\omega k} - 1) = $ $ \displaystyle v_q(p^\omega - 1) \cdot \left\lfloor\frac{n}{\omega}\right\rfloor + \sum_{k=1}^{\lfloor n/\omega \rfloor } v_q(k) $ $ \displaystyle > \sum_{k=1}^{\lfloor n/q \rfloor } v_q(k) = v_q(n!) $. Da qui la tesi, q.e.d.

[HiTLeuLeR]

Davvero un bel problema, ma_go. Per caso sai dirmi chi n'è l'autore? O comunque hai qualche referenza che ne indichi la provenienza?! E poi... com'è che l'hai sdoganato qui, nel subforum di MNE?

[ma_go]

per evitare soluzioni illeggibili e contose, e per far capire un tantinello di matematica seria
comunque il problema mi era stato proposto da alefig lo scorso anno, chiedendomi una decente soluzione elementare (cosa che mi sconsiglia di proporgli la tua), e quest'anno mi è capitata più o meno per caso addosso la soluzione...
molto molto bella, come ossido e G possono confermare...
se nessuno trova questa soluzione, magari do qualche hint...

[HiTLeuLeR]

Ah, non ti pare elementare? Boh, eppure non c'è alcun riferimento a risultati profondi dell'algebra o dell'analisi, ma sola teoria dei numeri elementare (anzi olimpica). Sono un po' confuso, sai?! Uh, vorrà dire che attenderò impaziente di vedere la tua. D'altra parte, tu ci hai messo un anno a risolverlo (ipse dixisti!), moi l'avrò letto appena tre quarti d'ora fa, sicché... ho qualche attenuante dalla mia, no?!

[ma_go]

un'altra soluzione elementare, made in modena, da una nota matricola...

dunque, chiamiamo $ \displaystyle R = \prod_{k=0}^{n-1} \left(p^n - p^k\right) $
ora osserviamo che, per ogni $ q \neq p $ primo, se $ q^\alpha \| n! $, allora $ \displaystyle\alpha = \sum_{k=1}^{\infty} \left[\frac{n}{q^k}\right] < \sum_{k=1}^{\infty} \frac{n}{q^k} = \frac{n}{q-1} $.
d'altro canto, $ q\mid \left(p^{k(q-1)} - 1\right) \mid \left(p^n - p^{n-k(q-1)}\right) $.
quindi $ q^{\beta} \| R $ implica $ \displaystyle\beta \ge \left[\frac{n}{q-1}\right] $.
quindi per ogni $ q \neq p $, $ \alpha < \beta $.
d'altro canto, è evidente che $ \displaystyle\frac{n}{p-1} \le \frac{n(n-1)}{2} $ per ogni $ n>2 $ o per ogni $ p>2 $. i casi particolari si lasciano al lettore, e quindi otteniamo la tesi..

commento personale: molto molto carina, e semplice. bravo mr.sisto...

ehm.. scusate gli edit, piccoli typos, e un rompiscatole che sa fare il suo mestiere..

[HiTLeuLeR]

[...] d'altro canto, è evidente che $ \displaystyle\frac{n}{p-1} \le \frac{n(n-1)}{2} $, quindi otteniamo la tesi.

i) Stesso approccio. ii) La disuguaglianza qui sopra è falsa se p = 2. E dire che non le avrò dato più di una lettura in volata...

[HiTLeuLeR]

[...] d'altro canto, è evidente che $ \displaystyle\frac{n}{p-1} \le \frac{n(n-1)}{2} $ per ogni $ n>2 $ o per ogni $ p>2 $. i casi particolari si lasciano al lettore, e quindi otteniamo la tesi.

ehm.. scusate gli edit, piccoli typos, e un rompiscatole che sa fare il suo mestiere..

Bene, ma_go, a fronte dei tuoi commenti, lascia che ti dica apertamente come la penso. Punto i): è chiaro che non hai capito una cippa (e forse non sei il solo!) della soluzione che ho proposto qualche post più su. In tal caso, non essere timido e chiedi pure tutte le delucidazioni che ti servono: sta' certo che qualcuno, qui in giro, saprà rendertele! Se ci rifletti, concorderai tu stesso che quest'è detto con assoluta cognizione di causa, visto che non ti ha neppure minimamente sfiorato l'idea che le due soluzioni potessero essere sostanzialmente identiche (come di fatto accade, a parte trascurare che la seconda è fallata). Punto ii): il meglio che ti riesce di fare per rimediare ad una grave lacuna implicita nei tuoi argomenti dimostrativi è quello di affidarti all'usurata formula per cui vien detto che "i dettagli si rimandano al lettore". Ebbene, il tentativo è encomiabile. Peccato soltanto che, ad un esame più attento, si riveli in effetti decisamente bookish e altrettanto patetico. D'altro canto... contento tu! Che proprio la lacuna segnalata costituisce la ragione di fondo per cui moi non ha usato (come invece avrebbe suggerito lo standard in questi casi!) la disuguaglianza alla base della soluzione (ahite', parziale!) che hai pensato bene di riproporci. Ma poi tu saresti un matematico ed io, invece, un rompiscatole che sa fare bene il suo mestiere... Vabbè, che posso aggiungere?! Confido ciecamente nell'intelligenza del lettore.

P.S.: soltanto una postilla... La leggi la firma qui sotto?! Beh, sei giusto tu fra quei matematici che l'hanno ispirata.

[Marco]

siano $ n $ un intero non-negativo, e $ p $ un primo.
dimostrare che $ \displaystyle n! \mid \prod_{k=0}^{n-1} (p^n - p^k) $.

Sentite questa soluzione geometrico-combinatoria da due righe:

Prendete uno spazio vettoriale su $ \mathbf F_p $ di dimensione $ n $. Dico che quella produttoria a secondo membro è il numero di basi che è possibile costruire, contate considerando l'ordine.

Infatti: il primo elemnto della base deve essere scelto non nullo, ossia può essere scelto in $ p^n-p^0 $ modi. Il secondo ha come unico vincolo di essere indipendente dal primo, ossia di non appartenere al sottospazio generato ($ p^n - p^1 $ scelte possibili), ecc... fino a $ p^n-p^{n-1} $.

Quante sono le basi a meno dell'ordine? Ogni base viene contata esattemente $ n! $ volte, perché permutandola si ottiene ancora una base. Quindi $ n! \mid \prod_{k=0}^{n-1} (p^n - p^k) $. []

[HiTLeuLeR]

Meravigliosa! Certo poco elementare, però meravigliosa!!! E poi di grande effetto...

[Marco]

Ghiii, questi applausi a scena aperta mi emozionano...

Comunque, come corollario, si prova che il risultato è vero anche se $ p $ è una potenza di un primo.

[ma_go]

ok, era circa la dimostrazione che volevo che utenti "meno esperti" trovassero
in realtà, l'idea originale era un tantinello diversa...
Sicuramente si ha $ S_n < GL_n(\mathbb{F}_p) $, perché le permutazioni (di elementi della base) possono essere viste come un sottogruppo delle applicazioni lineari, ma basta calcolare le due cardinalità per avere il risultato...