sábado, 22 de mayo de 2010

Polinomios ciclotomicos (Diego)

En busca de una respuesta para el problema que planteo Enrique, se me ocurrio usar polinomios ciclotomicos.(Ver links abajo)
Sea PHI_r(x) el r-esimo polinomio ciclotomico
Se tiene que
2^n-1=(multiplicacion d|n) (PHI_d(2))
y sabemos que PHI_x(2) es mayor a 1 si x es mayor a 1.
Si (con a mayor o igual a b) (PHI_a(2),PHI_b(2))=!=1 entonces a/b es una potencia de un primo.
Si n=p_1^a_1 * p_2^a_2 ... * p_m^a_m, si podemos agarrar un conjunto con P elementos tal que cada elemento del conjunto divide a n y no hay A y B (A=!=B) en el conjunto tal que A/B sea potencia de primo, entonces Tau(2^n-1) es mayor o igual a 2^P ya que habria almenos P numeros primos diferentes que dividan a 2^n-1.
Se podria agarrar el conjunto de divisores con un numero par (o impar) de factores primos diferentes. Digamos que Sigma_t es la suma de todas las posibles multiplicaciones de t-adas de primos y Sigma_t=0 si t es mayor a m. Entonces P=Sigma_1+Sigma_3+Sigma_5+...
(Llamemosle P_1 a esta suma)
o podria ser que
P=Sigma_2+Sigma_4+Sigma_6+...
(Llamemosle P_2 a esta otra)
pero tenemos que
P_1+P_2=Sigma_1+Sigma_2+...=Tau(n)-1
Asi que Max{P_1,P_2} es mayor o igual a TECHO[(P_1+P_2)/2 ]=TECHO[(Tau(n)-1)/2]
Entoncese Tau(2^n-1) es mayor o igual a 2^P que es mayor o igual a 2^TECHO[(Tau(n)-1)/2].
Bueno, no he llegado mas lejos que eso, pero creo que es un muy buen avance.



links:
Polinomio Ciclotomico

Link2

Edit (por David): Arregle los links, ahi en el Panel a la hora de hacer el post viene una opción para escribir hyperlinks

1 comentario:

Quique12 dijo...

Esta interesante tu avance. Me gusta que llegarás a que Tau(2^n -1) >= 2^((Tau(n)-1)/2).

Hay un teorema poderoso que te ayudaría a quitar el denominador 2 de tu exponente. El teorema se llama Teorema de Zsigmondy y su demostración usa ciclotómicos. El teorema dice que para todo n distinto de 6, existe un primo p que divide a 2^n - 1 que no divide a 2^d -1 para todo d < n.

Una nota sobre tu desigualdad. 2^(Tau(n)/2) > n se cumple para "pocos" números. Se cumple para infinitos, pero no para todos los múltiplos de 12 (por dar un ejemplo).

Publicar un comentario