polinomio buffo: dara' sempre valori interi?

Polinomi, disuguaglianze, numeri complessi, ...
Rispondi
piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

polinomio buffo: dara' sempre valori interi?

Messaggio da piever » 12 dic 2007, 22:55

Per farmi perdonare che rovino subito i problemi belli, ne posto uno carino anche se facile. Per favore chi e' esperto non posti subito, senno' poi dovra' farsi perdonare anche lui eccetera...

Allora, sia $ \displaystyle p(x_1,\dots ,x_n)=\prod_{1\le i<j\le n}\frac{x_j-x_i}{j-i} $

Dimostrare che se gli $ x_i $ sono interi, allora anche $ p(x_1,\dots ,x_n) $ e' intero...

Bonne chance...
"Sei la Barbara della situazione!" (Tap)

Avatar utente
wolverine
Messaggi: 59
Iscritto il: 11 nov 2007, 12:35

Messaggio da wolverine » 13 dic 2007, 20:40

Garantisco soluzione oschura, chi ne posta una elementare (che non so fare) ?
I'm the best there is at what I do. But what I do best isn't very nice.

Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Messaggio da julio14 » 13 dic 2007, 22:00

Allora, il denominatore è banalmente $ $\prod_{1\le k<n} (n-k)^k $ (per esempio il fattore $ $n-2 $ lo otteniamo da $ $j=n $ e $ $i=2 $ o da $ $j=n-1 $ e $ $i=1 $)
I piccioni dicono che al numeratore abbiamo almeno $ $k $ coppie di $ $x_i $ con la stessa congruenza modulo $ $n-k $ quindi la loro differenza è congrua a 0 modulo $ $n-k $, quindi abbiamo per ogni fattore $ d $ al denominatore un fattore $ $m $ al numeratore tali che $ $d|m $ quindi $ $p(x_1,\dots,x_n) $ è intero.
Il tutto modulo errori stupidi.

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 13 dic 2007, 22:36

Non è chiaro come usi il principio dei piccioni, poi stai attento al fatto che se ad ogni fattore cattivo del denominatore associ un fattore buono del numeratore che lo annulla, se a tanti fattori cattivi associ lo stesso fattore buono poi non torna... cioè, sarà anche giusto, ma con sto raffreddore io non ci capisco niente :?

Avatar utente
julio14
Messaggi: 1208
Iscritto il: 11 dic 2006, 18:52
Località: Berlino

Messaggio da julio14 » 13 dic 2007, 23:02

Per i piccioni: al numeratore abbiamo n $ $x_i $, mentre le classi di congruenza di $ $n-k $ sono $ $n-k $ quindi ci sono k $ $x_i $ di troppo, ognuno di essi forma una coppia con un un'altra $ $x_j $ appartenente alla stessa classe di congruenza. Per il seccondo punto ora che mi ci fai pensare hai ragione... ora però sono troppo stanco per pensarci, domani vedo se riesco a metterci una pezza :D

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 14 dic 2007, 11:02

@ julio 14: non metterti a discutere con edriv alle 11 di sera, a un certo punto iniziera' a farti credere che ogni problema del forum coimplica l'assioma della scelta...

@wolverine: quanto oschura? Se non ti secca troppo scriverla in LaTeX magari mandamela per mp..

ciaociao
"Sei la Barbara della situazione!" (Tap)

Avatar utente
wolverine
Messaggi: 59
Iscritto il: 11 nov 2007, 12:35

Messaggio da wolverine » 14 dic 2007, 12:36

E' cosi' oSCHURa e non-olimpica che posso anche metterla qui in chiaro... di sicuro non toglie a nessuno il gusto di cercare una soluzione elementare

Per prima cosa osserviamo che $ p(x_1+k,x_2+k,\dots,x_n+k)=p(x_1,x_2,\dots,x_n) $ e dunque possiamo supporre che tutti gli $ x_i $ siano negativi, e che permutare tra loro le $ x_i $ cambia $ p(x_1,x_2,\dots,x_n) $ moltiplicandolo per $ \pm1 $ (+1 o -1 a seconda se la permutazione e' pari o dispari). Dunque non e' restrittivo supporre $ 1-x_1\geq2-x_2+\cdots n-x_n\geq0 $. A questo punto poniamo $ \lambda_j=j-x_j $, indichiamo con $ s_{\lambda_1,\dots,\lambda_n}(z_1,\dots,z_n) $ il polinomio di Schur associato alla successione decrescente di interi positivi $ \lambda_1\geq\lambda_2\geq\cdots\geq \lambda_n\geq0 $, e ci ricordiamo che i polinomi di Schur sono polinomi simmetrici a coefficienti interi e che vale la formula (si trova dimostrata su qualunque libro di teoria delle rappresentazioni)

$ \displaystyle{s_ {\lambda_1,\dots,\lambda_n}(1,1,\dots,1)=\prod_{1\leq i<j\leq n}\frac{\lambda_i-\lambda_j+j-i}{j-i} $
ovvero, ricordandoci che $ \lambda_j=j-x_j $,
$ \displaystyle{s_ {\lambda_1,\dots,\lambda_n}(1,1,\dots,1)= \prod_{1\leq i<j\leq n}\frac{x_j-x_i}{j-i} $
I'm the best there is at what I do. But what I do best isn't very nice.

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 14 dic 2007, 14:37

A julio: quando una dimostrazione non funziona perchè dividendi e divisori si confondono troppo tra di loro, spesso il problema si risolve facendo lo stesso ragionamento per le potenze di primi (e assumendo tacitamente l'assioma della scelta, ma forse qui dovrei non dirlo). In particolare, mi pare che qui funzioni, ma serve qualche stima più dettagliata di quella che hai fatto.

P.S. Detesto le soluzioni non olimpiche!

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 14 dic 2007, 20:58

@ wolverine: ahhhhhhhhhhh, non avevo colto il gioco di parole (forse perche' ignoro completamente cosa sia un polinomio di Schur :roll: ), comunque non pensavo fosse cosi' tanto oscura la soluzione...

@ julio: per stavolta (ma solo per stavolta) da' retta al buon edriv

@ edriv: lol
"Sei la Barbara della situazione!" (Tap)

Avatar utente
wolverine
Messaggi: 59
Iscritto il: 11 nov 2007, 12:35

Messaggio da wolverine » 15 dic 2007, 10:24

Non e' difficile definire i polinomi di Schur, ne' dimostrare l'identita'

$ \displaystyle{S_{\lambda_1,\dots,\lambda_n}(1,1,\dots,1)=\prod_{1\leq i< j\leq n} \frac{\lambda_i-\lambda_j+j-i}{j-i}}, $

ma per farlo serve la nozione di determinante di una matrice ed e' utile avere familiarita' con il concetto di limite di una funzione (in effetti qui serve solamente un limite molto semplice:

$ \displaystyle{ \lim_{x\to 1}\frac{x^a-1}{x^b-1}=\frac{a}{b}} $

). Quando ho un po' di tempo posto un po' di esercizi mirati in Matematica non elementare.
I'm the best there is at what I do. But what I do best isn't very nice.

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Re: polinomio buffo: dara' sempre valori interi?

Messaggio da piever » 18 dic 2007, 15:26

piever ha scritto:Per favore chi e' esperto non posti subito...
Fa molto piacere essere ascoltato, pero' $ \mbox{dopo una settimana}\neq\mbox{subito} $, quindi chiunque trova una soluzione olimpica puo' postare..

Tra un po' metto la mia.
"Sei la Barbara della situazione!" (Tap)

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 18 dic 2007, 16:03

L'idea della mia soluzione è questa: in questo problema la divisibilità funziona non come un budino ma come un panino. Vediamo di spiegare meglio il concetto :D

Siano $ ~ a_1,\ldots,a_n, b_1,\ldots,b_m $ interi nonnulli.
Se, per ogni potenza di primo $ ~ p^{\alpha} $, gli $ ~ a_i $ che sono divisibili per $ ~ p^{\alpha} $ sono minori o uguali dei $ ~ b_i $ che sono divisibili per $ ~ p^{\alpha} $, allora:
$ ~ a_1a_2\cdots a_n \mid b_1b_2 \cdots b_m $
(attenzione: non è un se e solo se!)

Visto che è facile e che se lo dimostro rischiate di non capirlo, lo lascio dimostrare a voi. Vogliamo applicare questo lemma al problema. Da una parte abbiamo:
$ ~ \prod (i-j) $
e dall'altra:
$ ~ \prod (x_i - x_j) $
Fissiamo la nostra potenza di primo (anzi, a noi bastano le potenze di primo, ma vale per un generico k) e dividiamo $ ~ \{1,2,\ldots, n\} $ e $ ~ \{x_1,\ldots,x_n\} $ nelle classi di congruenza modulo k.
Chiaramente $ ~ \{x_1,\ldots,x_n\} $ sono distribuiti a caso, ma invece $ ~ \{1,2,\ldots, n\} $ sono distribuiti nella maniera più omogenea possibile (i.e., la differenza tra le cardinalità di due classi è al più 1). Il numero di elementi è lo stesso. Useremo l'AM-GM per far vedere che il modo omogeneo minimizza il numero di coppie congrue modulo n.

Cioè:
Siano $ ~ a_1,\ldots,a_n $ il numero di elementi di $ ~ \{1,2,\ldots, n\} $ rispettivamente congrui a 1,2,...,n modulo n.
Siano $ ~ b_1,\ldots,b_n $ il numero di elementi di $ ~ \{x_1,x_2,\ldots, x_n\} $ rispettivamente congrui a 1,2,...,n modulo n.
Quanti fattori del divisore sono divisibili per n?
Beh, sono esattamente:
$ \displaystyle d_1 = {a_1 \choose 2} + \ldots + {a_n \choose 2} $
Mentre i fattori del divisore divisibili per n sono:
$ \displaystyle d_2 = {b_1 \choose 2} + \ldots + {b_n \choose 2} $
Inoltre abbiamo la condizione che $ ~ \sum a_i = \sum b_i $. Vogliamo far vedere che $ ~ d_2 \ge d_1 $. Sviluppando i binomiali, moltiplicando per 2 e semplificando la parte lineare che resta (perchè $ ~ \sum a_i = \sum b_i $) resta da far vedere che:
$ \displaystyle \sum b_i^2 \ge \sum a_i^2 $
Questo funziona perchè gli a_i sono ben distribuiti. Lo dimostriamo così: se due b_i hanno differenza maggiore di 1, possiamo alzare di 1 il più grande e abbassare di 1 il più piccolo facendo calare LHS. Ma se due b_i hanno differenza al più 1, possiamo far vedere che le n-uple $ ~ (a_1,\ldots,a_n),(b_1,\ldots,b_m) $ sono uguali a meno di permutazioni.

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 18 dic 2007, 17:29

Uhm, mi sfugge il ruolo del panino, ma vabbeh, edriv e' edriv :P

Se invece foste stati a conoscenza del lemma 0: "ogni problema di piever e' corollario di un precedente problema di piever", avreste potuto usare un lemma che ho postato da qualche parte quest'estate e che non trovo, comunque e' questo:

LEMMA PRECEDENTE:

Sia $ p(x_1,\dots ,x_n) $ un polinomio a coefficienti in $ \mathbb{C} $ di grado $ g_i $ nella variabile $ x_i $

Se esistono $ a_1,\dots ,a_n\in\mathbb{Z} $ tali che $ \forall x\in\{ a_1,a_1+1,\dots, a_1+g_1\}\times\dots\times\{ a_n,a_n+1,\dots ,a_n+g_n\}\; $$ p(x)\in\mathbb{Z} $ allora $ \forall x\in\mathbb{Z}^n\;p(x)\in\mathbb{Z} $

Dimostrazione del problema:

usando il LEMMA PRECEDENTE, notiamo che $ g_i=n-1 $, poniamo $ a_i=1 $ per ogni $ i $ e ci rimane da dimostrare che il nostro polinomiaccio da' risultati interi quando gli $ x_i $ sono interi da 1 a n. Se $ x_i=x_j $ con $ i\neq j $, allora il polinomiaccio si annulla e siamo felici... Se invece gli $ x_i $ sono tutti distinti, allora la funzione che ad $ i $ associa $ x_i $ e' una permutazione, e il polinomiaccio fa $ \pm 1 $ a seconda del segno della permutazione, e siamo ancora piu' felici, perche' abbiamo detto la parola "permutazione" e potevamo farne a meno.


Ma questo e' molto piu' incasinato dela soluzione di edriv, e non ho neanche dimostrato il LEMMA PRECEDENTE ma vabbeh, edriv e' edriv... :D
"Sei la Barbara della situazione!" (Tap)

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 18 dic 2007, 18:08

Ho capito il tuo piano diabolico... volevi sfidarci a trovare una soluzione elementare quando poi tiravi fuori dal cappello da mago la banana cubica... peccato che wolverine è uscito con una banana più cubica della tua :D

Che poi il lemma precedente non l'ho mai visto... ricorda vagamente un IMO di non mi ricordo che anno ma potrei sbagliarmi.

Rispondi