Polinomi che danno sempre valori interi...

[piever]

Visto questo problema pensavo di proporvi il seguente, che spero necessiti di meno formule tex per essere risolto:

1) Sia $ p $ un numero primo. Qual è il minimo $ d $ intero positivo per cui esisto un polinomio $ q(x) $ monico a coefficienti interi di grado d tale che: $ p^{p+1}|q(m) $ per ogni $ m $ intero?

2) Più in generale! Sia $ n $ un intero positivo. Si trovi una condizione necessaria e sufficiente su $ d $ affinché esista un polinomio $ q(x) $ monico a coefficienti interi di grado $ d $ tale che $ n|q(m) $ per ogni $ m $ intero.

Appena risolvete questi due punti posterò qualche altro rilancio...

Buon lavoro!

[paga92aren]

Non so se questo è il grado minimo ma è un buon punto di inizio:
$$q(x)=(x(x^{p-1}-1))^{p+1}$$
e ha grado $p^2+p$

EDIT: corretto un typo. ma_go.

[ma_go]

io ne ho uno di grado $p^2$, chi offre di meno?
e ho un bound in generale, però non scrivo niente per non spoilerare (il bound rivela un po' troppo per i miei gusti).

[piever]

Ho editato il primo messaggio: voglio una condizione necessaria e sufficiente sul grado del polinomio...

@paga92aren: si riesce in effetti a fare di meglio. Prova con p=2 a vedere se ne trovi di più piccoli ad esempio...

[patatone]

uno con grado $p^2$ potrebbe essere $\displaystyle\prod_{i=0}^{p-1}\prod_{k=0}^{p-1}(x+i+kp)$

[ma_go]

curioso, sei la seconda persona a cui vedo scrivere lo stesso polinomio nello stesso modo.. io lo scriverei così (nascondo, forse perché dà/mi pare che dia un hint per il punto 2):

Testo nascosto:

$\displaystyle p^2!\binom{x}{p^2}$

si attendono dimostrazioni del fatto che "più in basso di così non si può scendere". e, ovviamente, i rilanci.

[piever]

Visto che è passato un po' di tempo da quando ho messo il problema e ancora nesssuno ha scritto soluzioni, vi lascio un piccolo hint:

Testo nascosto:

se da $ q(x) $ è sempre multiplo di n, cosa si può dire del polinomio $ r(x)=q(x+1)-q(x) $?

[ma_go]

uff, sono stufo di vedere questo thread che non riparte, e sono (ancora) curioso di vedere i rilanci, quindi metto un altro hint (o meglio, espando l'ermetico suggerimento di piever).

Testo nascosto:

vogliamo dare un bound inferiore per il grado del polinomio, nel caso in cui $n=p^k$ sia una potenza di un primo.
prendiamo $q$ polinomio monico di grado minimo che soddisfa le ipotesi, allora $r(x) = q(x+1)-q(x)$ ha grado minore e soddisfa le stesse proprietà.
qual è il termine di testa di $r(x)$? quante potenze di $p$ guadagno, aumentando il grado?

[piever]

Mah, ormai è già da parecchi giorno che il problema è sul forum e non sembra aver riscosso il successo di pubblico che mi aspettavo

Scrivo uno sketch di soluzione, nel caso ci fosse qualcuno che si è cimentato e vuole sapere come si fa:

Supponiamo che esista un certo q(x) di grado d sempre divisibile per n. Pongo $ q_0(x)=q(x) $ e poi, ricorsivamente, $ q_{k+1}=q_{k}(x+1)-q_{k}(x) $

Notiamo due cose: intanto è facile vedere (per induzione su k) che per ogni k, e per ogni x, $ n|q_k(x) $

Inoltre, cosa succede al termine di testa passando da $ q_k $ a $ q_{k+1} $? Il grado si abbassa di uno e il coefficiente di testa viene moltiplicato per il grado. Dunque è facile dimostrare che $ q_d(x) $ ha grado 0 e termine di testa $ d! $

In sostanza, $ q_d(x)=d! $, dunque per quanto detto sopra, $ n|d! $

Se invece assumiamo che $ n|d! $, allora $ n|d!|x(x-1)\dots (x-d+1) $ per ogni x (la seconda divisibilità è vera in quanto i coefficienti binomiali sono interi) e dunque abbiamo trovato un polinomio monico di grado d che funziona, pertanto la condizione $ n|d! $ è necessaria e sufficiente.

[piever]

Ora il primo rilancio:

Preso $ k\in\mathbb{N} $ definiamo $ \displaystyle\binom{x}{k} = \frac{1}{k!}\prod_{i=0}^{k-1} (x-i) $

Diciamo anche $ \displaystyle\binom{x}{0}=1 $ per convenzione.

Sia $ p(x)\in \mathbb{Q}[x] $ tale che, per ogni m intero, p(m) è intero. Allora p(x) si scrive in modo unico come $ \displaystyle p(x)=\sum_{k=0}^d a_k\binom{x}{k} $ con gli $ a_k $ interi.

Dimostrate anche che un polinomio q(x) a coefficienti interi si scrive in modo unico come $ \displaystyle q(x)=\sum_{k=0}^d b_k k!\binom{x}{k} $

Buon lavoro!

[ma_go]

se ti consola, questo problema ha avuto molto (troppo) seguito (e troppe divagazioni) in lunghe conversazioni private...

comunque, bella soluzione! io e gdt abbiamo trovato un'altra soluzione seguendo il tuo hint, (un po' meno pulita della tua, ma forse più intuitiva), e una soluzione per induzione (decisamente meno pulita e meno intuitiva).
dunque, come detto nel mio ultimo post, è sufficiente (a posteriori) considerare $n=p^k$. invece di tenere $k$ fissato, teniamo $k$ variabile, e cerchiamo un polinomio $r_k$ di grado minimo che soddisfi la proprietà che vogliamo, e chiamiamo $d_k$ questo grado.

come dice pietro, consideriamo $r'_k(x) = r_k(x+1)-r_k(x)$ (notazione non proprio casuale), che ha come termine di testa $d_k x^{d_k-1}$. allora $p|d_k$ (facile), ma in realtà serve che $p$ divida $r'_k$. supponiamo che $p^\alpha \| d_k$, allora al più possiamo guadagnare $\alpha$ potenze di $p$ rispetto ai polinomi di grado più piccolo di $d_k$. casualmente, questo è lo stesso numero di potenze di $p$ che si guadagnano passando da $d_{k-1}!$ a $d_k$, e questo dice che il grado minimo è almeno $\min \{a \mid p^k | a!\}$. poi l'esempio si costruisce a mano, e (fortunosamente) risolve il caso di un prodotto di più primi (anche non distinti, con ripetizione, et cetera...).

il rilancio, comunque, è ben noto, e lo lascio ai "meno abbienti"
nel frattempo mi metto in stand by e aspetto i rilanci successivi.

[piever]

Mah, un po' di tempo è passato, metto uno sketch di soluzione...

Prima di tutto è comodo notare che ogni polinomio a coefficienti razionali è della forma $ \displaystyle\sum_{k=0}^d a_k\binom{x}{k} $ e si vede abbastanza facilmente per induzione sul grado (prima sistemo il termine di grado più alto, e poi lo so fare per ipotesi induttiva). Si vede anche facilmente che tale scrittura è unica (sempre guardando dal termine di grado più alto).

Ora, se il polinomio di partenza era a coefficienti interi, è facile vedere che $ \displaystyle\frac{a_d}{d!} $ deve essere intero, quindi posso sottrarre $ \displaystyle a_d\binom{x}{d} $ e ho ancora un polinomio a coefficienti interi e applico la tesi per induzione.

Se un polinomio dà sempre valori interi, allora per forza di cose i coefficienti sono razionali (mi basta valutarlo in d+1 punti interi, e poi fare il sistema per trovare i coefficienti che dunque verranno razionali). Quindi si scrive nella forma che dicevo all'inizio. Ora valutarlo in zero mi dice che $ a_0 $ è intero. Se lo valuto in 1 trovo che $ a_1 $ è intero e così via..

Anche i viceversa sono chiari, cioè se un polinomio è della forma $ \displaystyle\sum_{k=0}^d a_k\binom{x}{k} $ con gli $ a_k $ razionali, allora è a coefficienti razionali. Se $ a_k $ è sempre un intero multiplo di k! allora è a coefficienti interi. Se gli $ a_k $ sono interi sputa sempre valori interi, per ogni valore intero dell'incognita.

Ho scritto solo uno sketch, chi vuole può mettersi a riscriverla per bene, l'importante è capire le idee alla base e saper rifare questi ragionamenti anche in altri problemi non uguali ma simili...

[piever]

Mi preme molto di più invece postare l'ultimo e più sostanzioso rilancio...

1) Visto che ogni polinomio coefficienti interi si scrive come $ \displaystyle\sum_{k=0}^d b_k k!\binom{x}{k} $, verificare che, una volta scrittolo in questa forma, tale polinomio è divisibile per n se e solo se, per ogni k, $ n|b_k k! $

2) Rifare il problema postato a inizio pagina

3) Risolvere il problema di dario2994 che ho linkato a inizio pagina: quante funzioni ci sono da $ \mathbb{Z}_n $ a $ \mathbb{Z}_n $ che si esprimono come un polinomio a coefficienti interi? Fatelo senza l'ipotesi che in n non compaiano fattori primi al cubo o a potenze superiori. Verificate che la formula generale coincide con quella di dario2994 nel caso particolare in cui chiede di affrontare il problema.

4) Dimostrate che se un polinomio di grado d assume d+1 valori interi consecutivi, allora assume sempre valori interi.

5) Risolvete il problema numero due dei RMM, primo giorno. Per quali n esiste un polinomio f(x) tale che: f(x) è intero se e solo se x non è un multiplo di n?