Pregunta B6 Putnam 2011

Question

Quiero pedir hoy Putnam problema B6:

Supongamos $p$ es una extraña prime. Demostrar que para $n\in \{0,1,2...p-1\}$, al menos $\frac{p+1}{2}$ número de $\sum^{p-1}_{k=0} k! n^{k}$ no es divisble por $p$.

Por ejemplo, para$p=3$, $(0,1,2)$ corresponde a $(0, 1+1+2,1+2+2*4)$. Para$p=5$, $(0,1,2,3,4)$ corresponde a $(0,1+1+2+6+24,1+2+2*4+6*8+24*16..)$.

Es de esperar que una solución oficial se puede encontrar en algún lugar (el de Putnam archivo, American Mathematical Monthly, AOPS, etc). Mi punto de elevar a esta pregunta es no pedir una solución, porque no estoy interesado en técnicas de solución de problemas. En lugar de ello quiero hacer las siguientes preguntas:

1) Es la función de $\sum\limits_{k=0} ^{p-1} k! n^{k}$ conocido? Puede ser expresado en alguna forma cerrada a través de la generación de funciones u otras combinatorical herramientas? Mi combinatorical fondo es muy débil, así que creo que debería preguntar a los demás.

2) En general, ¿cómo de fuerte que la afirmación es? Por ejemplo, para $p$ bastante grande, de cuantos elementos en $\mathbb{Z}_{p}$ tienden a satisfacer $\sum \limits_{k=0} ^{p-1} k! n^{k}=0$?

3) es posible ver el problema a través de algunos de 'alto nivel' prueba? (Sé que David Speyer se encuentra de este tipo de cosas). Porque no estoy especializado en teoría de números, el número limitado de la teoría del conocimiento que tengo en los dominios de Dedekind y valoraciones que parece ser bastante irrelevante para este problema. Pero creo que debe haber alguna manera este pequeño problema se generaliza a algo más interesante para un experto.

Answer 1

Editar: le Preguntó sobre Desbordamiento: Hay algunos muy buena respuesta en la que se puede encontrar aquí donde se explican algunos de los más profundo significado: http://mathoverflow.net/questions/82648/truncated-exponential-series-modulo-p-deeper-meaning-for-a-putnam-question

Siento que mirar a $\sum_{k=0}^{p-1} k!n^k$ sin cambiar su forma es la manera equivocada de abordar este problema, y si hay más profunda de las soluciones van a venir por la modificación de esta primera. Después de algunos reordenamientos modulo $p$, lo que estamos realmente viendo es la exponencial truncada de la serie.

Reformular la pregunta: En primer lugar, permite ignorar $n=0$, como en este caso la suma es sólo $1$, y en lugar de considerar sólo el grupo multiplicativo. Dejando $k=p-1-l$ y el uso de Wilsons y teorema de Fermats poco teorema podemos reescribir nuestra suma como $$\sum_{k=0}^{p-1}k!n^{k}\equiv\sum_{l=0}^{p-1}(p-1-l)!n^{p-1-l}\equiv-\sum_{l=0}^{p-1}\frac{1}{(p-l)(p-l+1)\cdots(p-1)}n^{-l} $$ $$\equiv -\sum_{l=0}^{p-1}(-1)^{l}\frac{n^{-l}}{l!}.$$ Using the fact that $n\rightarrow p-n $ and $n\rightarrow n^{-1}$ are isomorphisms of the multiplicative group, we have reduced the problem to considering for which $n$ we have $$-\sum_{l=0}^{p-1}\frac{x^{l}}{l!}=0.$$ This means that the original problem is equivalent to bounding the number of zeros modulo $p$ of the truncated exponential function $$E(z)=\sum_{l=0}^{p-1}\frac{z^{l}}{l!}.$$

La prueba de la pregunta: Considerar $$Q(z)=z^{p}-z+\sum_{l=0}^{p-1}\frac{z^{l}}{l!}.$$ Then for each integer $Q(n)=E(n).$ However, $$Q^{'}(z)\equiv E^{'}(z)-1=E(z)-\frac{z^{p-1}}{(p-1)!}-1\equiv E(z)+z^{p-1}-1.$$ Then, if $Q(n)=0$ for $n\neq0$ , we must also have $P^{'}(n)=0$ so that $n$ is a double root of $P(n).$ Since $\deg Q(n)=p$, we see that at most half of the integers $p\en\left\{ 1,2,\dots,p-1\right\}$ satisfy $E(n)=0.$ Since $E(0)=1$, llegamos a la conclusión de que el resultado deseado.

Motivación: La primera idea que me había mirado a $E(z)-E(-z)$, pero si se llevara a cabo los cálculos que sólo se puede mostrar que, al menos, $\frac{p-1}{4}$ son distintos de cero. En lugar de eso, le acaba de mirar la derivada de $E(z)$$E(z)+z^{p-1}$. Sabiendo que varios ceros son lo que queremos, ya que significa menos ceros total, debemos añadir una función cuya derivada es $-1$ ya que esta será la fuerza de varios ceros. La opción obvia es, a continuación,$x^p-x$, como se deja el original polinomio invariante.

Nota: Si usted pregunta acerca de la exponencial truncada, hay muchos artículos en existencia y, probablemente, un alto nivel de forma de ver el problema. Por ejemplo, ver la primera parte de http://www.science.unitn.it/~mattarei/Ricerca/Memorias/AH.pdf

Answer 2

No estoy seguro acerca de una generalización completa, pero me acerqué a desde un punto general parcial en el que cumplí todos los términos después de 1 + n en una suma parcial que fue siempre incluso. Con algunos básico aritmética modular la declaración apareció bastante bien cerrada, aunque para los números primos muy grandes es incógnita.

Como la prueba todavía funciona hasta mañana para excepciones religiosas aún no soy cómodo escribir mis soluciones. Te doy mi respuesta el mañana por la noche.