Variatiuni la problema 3 SEEMOUS 2009

Victor Vuletescu · Post by **Victor Vuletescu** » Sat Mar 14, 2009 8:39 pm

Fie \( n\geq 2 \) si \( N=\prod_{i=0}^{n-1}(2^n-2^i) \). Sa se arate ca nu exista \( A,\ B,\ C \in SL_n({\mathbb Z}) \) a.i. \( A^N+B^N=C^N. \)

Victor Vuletescu · Post by **Victor Vuletescu** » Sat Mar 14, 2009 8:43 pm

Am pus topicul aici ca mi s-a parut ca se potriveste (pfuu...oarecum!) cu precedentul subiect de discutie. A, si mi s-a parut ne-fair-play sa pun doar cazul \( n=6 \), i.e. "aratati ca ecuatia \( A^6+B^6=C^6 \) nu are solutii in \( SL_2({\mathbb Z}). \)"

Dragos Fratila · Post by **Dragos Fratila** » Sat Mar 14, 2009 11:04 pm

Mă uit la grupul \( GL_2(\mathbb{F}_2) \) (\( \mathbb{F}_2 \) corpul cu 2 elemente) care are ordinul \( (2^n-1)(2^n-2)...(2^n-2^{n-1}) = N \) şi privesc matricele A, B, C în acest grup.
Avem atunci \( A^N=B^N=C^N=I_2 \) (adica \( A^N=B^N=C^N=I_2 \) modulo 2).
O soluţie a ecuaţiei ar implica \( I_2+I_2 = I_2 \) modulo 2, ceea ce este o contradicţie.

Se ştie care este exponentul grupului \( GL_n(\mathbb{F}_q) \) ? (măcar pentru \( q=2 \)

)

Victor Vuletescu · Post by **Victor Vuletescu** » Sun Mar 15, 2009 12:29 am

Cateva scurte povestioare, inainte sa inchidem topicul.
Asa cum am spus, enuntul e inspirat de problema 3 de la SEEMOUS. Cand am vazut prima oara acea problema, m-am gandit intai la chestiunile discutate in topicul anterior: mi-am zis ca probabil se poate face cumva utilizand cei doi generatori "standard" ai lui \( SL_2({\mathbb Z}) \) (S si T in -de exemplu- notatiile lui Silverman din "Advanced topics..."). Apoi mi-am dat seama ca se rezolva mult mai usor "scolareste", utilizand Trace-uri, Hamilton-Cayley, etc. Apoi, pe parcursul corecturii, am vazut doua lucrari interesante, care incercau sa abordeze problema prin reductie; una, modulo 2, iar alta modulo 3. Reductia modulo 2 nu merge (repet, ecuatia de la SEEMOUS era \( A^4+B^4=C^4 \)), iar pentru reductia modulo trei, recunosc ca n-am un raspuns (merita scris un programel; \( SL_2({\mathbb F}_3) \) are 24 de elemente, deci prea mult timp de rulare nu ia!).

Vlad Matei · Post by **Vlad Matei** » Sun Mar 15, 2009 7:16 pm

Eu o sa ma limitez la o variatiune pe \( SL_{2}(\mathbb{Z}) \), anume ca ecuatia \( A^{2k+1}+B^{2k+1}=C^{2k+1} \) are o infinitate de solutii peste \( SL_{2}(\mathbb{Z}) \).

Victor Vuletescu · Post by **Victor Vuletescu** » Sun Mar 15, 2009 8:20 pm

Aha.. 5:5, poarta in casa, Vlad!
Dar, sa nu uitam ca mai e o "problemutza" ratacita pe acest topic; exponentul grupului \( GL_n({\mathbb F}_q) \) de care vorbea Dragos mai sus! Uite, eu am incercat cate ceva pentru cazul n=2, si pare sa fie \( q(q^2-1) \) (eventual supra 2)...O fi asa?

Dragos Fratila · Post by **Dragos Fratila** » Mon Mar 16, 2009 9:41 pm

Dacă \( q=p^n \) şi \( r \) este minim astfel încât \( p^r\ge n \), atunci exponentul lui \( GL_n(q) \) este \( p^r LCM(q-1,q^2-1,...,q^n-1) \) unde LCM = c.m.m.m.c.

În particular, pentru \( n=2 \), exponentul lui \( GL_2(q) \) este \( p(q^2-1) \).

Rezultatul aparţine lui Ivan Niven "Fermat's Theorem for Matrices" Duke 1948, 15, 823-826 (e un articol scurt de 3 pagini, dar nu l-am gasit de downloadat pe internet - am vazut doar prima pagina...)

Victor Vuletescu · Post by **Victor Vuletescu** » Mon Mar 16, 2009 9:51 pm

Tocmai cand editam si eu un reply, a venit postul lui Dragos. Fain ca ai gasit acel articol, Dragos! Acum, hai sa si demonstram acel enunt; e o joaca amuzanta cu Frobenius versus forma canonica Jordan (a, si faptul ca extinderile de corpuri finite sunt separabile...cred).
A, si pentru Vlad; pentru q=2 cred ca \( Gl_2({\mathbb F}_2) \) e iso cu \( S_3 \)...nu?

Vlad Matei · Post by **Vlad Matei** » Tue Mar 17, 2009 9:52 pm

Ok, o demonstratie pentru \( GL_2(F_q) \). Nu o sa tratez \( q=2 \).

Voi scrie matricea \( \displaystyle A=\frac{\tr(A)}{2} \cdot I_2+X \). Din Hamilton-Cayley \( X^2=-\det(X)\cdot I_2, \) deoarece \( \tr(X)=0 \). Folosind binomul lui Newton \( \displaystyle A^q=\frac{\tr^q(A)}{2^q} \cdot I_2+X^q \).
Acum daca \( \det(X)=0 \) avem \( \displaystyle A^q=\frac{\tr(A)}{2} \cdot I_2 \) si cum \( A \) este inversabila \( \tr(A)\neq 0 \). De aici \( A^{q(q-1)}=I_2 \).
Daca \( \det (X)\neq 0 \) avem \( A^q=A-X+X^q \), de unde \( A^q-A=X^q-X \). Mai ridicam la puterea \( q \), de unde \( A^{q^2}-A^q=X^{q^2}-X^q \). Se obtine usor \( X^{q^2-1}=I_2 \), de unde \( A^{q^2}-A^q=X-X^q=A-A^q \). Asadar \( A=A^{q^2} \) si cum \( A \) este inversabila \( A^{q^2-1}=I_2 \).
Cele doua cazuri ne furnizeaza astfel exponentul \( q(q^2-1) \).

Victor Vuletescu · Post by **Victor Vuletescu** » Wed Mar 18, 2009 10:02 am

Okay...si, generalizare la \( n\geq 3 \)? Hai sa incercam si altfel. O sa fac eu un "draft', tot pentru n=2, pe care poate l-o prelucra "cineva" cat sa devina o demonstratie in general.
Intai sa observam ca ordinul unui element intr-un grup e invariant la adjunctie. Ne uitam la polinomul caracteristic al unei matrici arbitrare. Distingem mai multe cazuri:
- ambele radacini sunt in \( {\mathbb F}_q \) si \( A \) e diagonalizabila; putem deci presupune ca \( A \) este chiar diagonala, \( A=\left(\begin{array}{ccc}\lambda_1&0\\0&\lambda_2\end{array}\right) \) cu \( \lambda_1,\lambda_2\in{\mathbb F}_q \). Gasim ca ordinul maxim posibil al lui \( A \) este \( q-1 \).
- ambele radacini sunt in \( {\mathbb F}_q \) si \( A \) dar \( A \) nu este diagonalizabila. Deci \( A \) poate fi presupusa de forma \( A=\left(\begin{array}{ccc}\lambda&a\\0&\lambda\end{array}\right) \) cu \( \lambda, a\in {\mathbb F}_q \). Deducem \( A^p=\left(\begin{array}{ccc}\lambda^p&0\\0&\lambda^p\end{array}\right) \) de unde mai departe gasim ca ordinul maxim posibil este \( p(q-1) \).
-in singurul caz ramas, avem ca ambele radacini sunt in \( {\mathbb F}_{q^2} \) si sunt distincte (mmm..oare? poate ma insel la acest punct...ma ajuta cineva?). Okay, atunci matricea noastra este conjugata peste \( {\mathbb F}_{q^2} \) cu o matrice diagonala (ca la primul caz), de unde deducem ca ordinul maxim posibil in acest caz este \( q^2-1 \).

Punand cap la cap aceste cazuri, gasim ca exponentul grupului este \( p(q^2-1) \).

Victor Vuletescu · Post by **Victor Vuletescu** » Wed Mar 18, 2009 10:16 am

Ok, sa va spun si ce revelatie mai avui (poate il va ajuta pe truditorul care va redacta solutia generala). Pentru cazul general, L.C.M.-ul din post-ul lui Dragos pare sa fie cel mai mic numar natural \( m \) cu proprietatea ca orice polinom de grad \( n \) definit peste \( {\mathbb F}_q \) are toate radacinile in \( {\mathbb F}_{q^m}. \)

Ca o digresiune; eu fiind din generatia anilor '80, m-am intrebat un timp cum o arata Lord Vader (episoadele 1-3 nu aparusera pe atunci). Okay, acum stiu adevarul gol-golut; pacat ca n-am avut atunci ideea sa ii scriu d-lui Lucas sa ii faca cinste cu f'o doua Becks ghiavolului cela de Sith!

Vlad Matei · Post by **Vlad Matei** » Wed Mar 18, 2009 10:35 am

Am zis sa pastrez solutia cu forma Jordan pe cazul general. Practic pentru matricea \( A=C^{-1}JC \) avem \( A^k=C^{-1}J^k C \). Acum practic trebuie sa ne uitam doar la matricea Jordan. Daca o ridicam la o putere e ca si cum am ridica blocurile componente la acea putere. Deci este suficient sa ne uitam la matrici de gen \( \displaystyle T= \left (\begin{array}{cccc} \lambda & 1& 0& \cdots& 0\\0&\lambda &1&\cdots&0\\ \cdots&\cdots&\cdots&\cdots\\0&0&\cdots &\lambda \end{array} \right) \) cu \( \lambda \) valoare proprie a lui A.
Avem ca \( T^{q^r}= \left (\begin{array}{cccc} \lambda^{q^r}& 0&\cdots&0\\0&\lambda^{q^r}&\cdots&0\\\cdots&\cdots&\cdots&\cdots\\0&0&\cdots &\lambda^{q^r} \end{array} \right) \) unde \( r \) este dimensiunea matricei si de aici e nevoie doar sa ne uitam unde pot fi aceste valori proprii.
Acum ideea e ca \( \lambda \) verifica un polinom de grad \( n \) peste \( F_q \).Avem asadar \( \lambda ^n=a_{n-1} \lambda ^{r-1}+\cdots+a_{1}\lambda+a_{0} \).Daca ridicam la \( q \) relatia avem \( \lambda ^{nq}=a_{n-1} \lambda^{q(n-1)}+...+a_{1} \lambda^{q}+a_{0} \).De aici si \( \lambda ^q \) este radacina a polinomului.
Astfel multimea \( \{\lambda,\lambda^q,...,\lambda ^{q^{n+1}} \} \) este o multime de radacini ale polinomului dar polinomul are cel mult \( n \) radacini peste orice corp asadar.De aici \( \lambda^{q^i}=\lambda^{q^j} \) de unde \( \lambda^{q^{i}(q^{j-i}-1)}=1 \).
Le punem cap la cap si obtinem rezultatul cerut.

Victor Vuletescu · Post by **Victor Vuletescu** » Wed Mar 18, 2009 12:46 pm

Vlad, p'asta cu polinoamele de grad doi care au toate radacini in \( {\mathbb F}_{q^2} \) am inteles-o pana si eu. La ce voiam o mana de ajutor era afirmatia ca daca am un poly de grad doi din \( {\mathbb F}_q[X] \) care nu are radacini in \( {\mathbb F}_q \) atunci el are radacini \( {distincte} \) in \( {\mathbb F}_{q^2} \). Imi trebuie asta ca sa conchid ca matricea mea devine diagonalizabila peste \( {\mathbb F}_{q^2} \); e drept, nu e vital, rationamentul se poate "ajusta" in acest caz, dar oricum, cazul trei din post-ul de mai sus ar fi incomplet (cel putin!).
O fi oare adevarat ca daca am un corp K si un poly ireductibil \( f\in K[X] \), atunci \( f \) are radacini distincte in inchiderea algebrica a lui \( K \)?

bae · Post by **bae** » Wed Mar 18, 2009 1:12 pm

Fara separabilitate nu prea cred.

Victor Vuletescu · Post by **Victor Vuletescu** » Wed Mar 18, 2009 1:53 pm

"Bae", mica mea intrebare "nevinovata" era pentru Vlad; mai exact, in una din variantele anterioare ale reply-ului sau de mai sus, care a "disparut" fara urma acum, era ceva care ma ducea la asta. Deci, Vlad, nu te fa ca nu ai auzit intrebarea mea; o fi adevarat ca un poly irred. are radacini distincte in inchiderea algebrica a corpului cu care lucrez? Eu nu stiu ce aia 'seprabilitate" de care vorbeste "bae", vreau un raspuns cat sa il pot intelege pana si eu: daca raspunsul e da, o demonstratie, iara daca e nu, vreau sa vad si eu un corp explicit \( K \) si un poly \( f\in K[X] \) de grad cel putin doi care sa fie ireductibil dar sa nu aiba radacini distincte in inchiderea algebrica a lui \( K \)!

Victor Vuletescu · Post by **Victor Vuletescu** » Thu Mar 19, 2009 1:00 pm

Vad ca s-a cam 'asternut tacerea"...Okay, probabil ca oamenii mai au si alte treburi de facut. Am totusi o intrebare retorica: ce m-o fi apucat sa postez in zona "algebrei", si mai ales spre "teorie galois"? Ca doar e stiut ca eu sunt cu "geometria"; de exemplu, ar trebui sa ma ocup de pilda de cate un grup fundamental, omotopie versus omologie, sau vreo varietate algebrica...nu? Ce treaba au toate astea cu polinoamele, si inca iaca, peste corpuri finite...?!

Vlad Matei · Post by **Vlad Matei** » Thu Mar 19, 2009 3:55 pm

Demonstratia nu este a mea, se regaseste in Basic Algebra de Nathan Jacobson.
Ideea e urmatoarea: corpurile de caracteristica 0 verifica proprietatea de separabilitate.
Deci trebuie sa ne uitam la un corp finit de caracteristica \( p \).

Lema Polinomul \( X^p-a \) din F[X], unde F este corp de caracteristica \( p \) si \( a \in F \), este fie ireductibil fie este o putere \( p \) in \( F[X] \).

Observatie. Daca este reductibil, atunci \( a=b^p \) cu \( b\in F \).
Acum ne uitam la corpul \( Z_p(t) \), corpul de fractii rationale intr-o nedeterminata \( t \). Se demonstreaza usor ca \( t \) nu este o putere \( p \) peste acest corp, deci daca luam polinomul din lema acesta este ireductibil si intr-o extindere va avea o bogatie de radacini multiple.