14
$\begingroup$

I wish to ask today's Putnam problem B6:

Suppose $p$ is an odd prime. Prove that for $n\in \{0,1,2...p-1\}$, at least $\frac{p+1}{2}$ number of $\sum^{p-1}_{k=0} k! n^{k}$ is not divisble by $p$.

For example, for $p=3$, we have $(0,1,2)$ corresponds to $(0, 1+1+2,1+2+2*4)$. For $p=5$, we have $(0,1,2,3,4)$ corresponds to $(0,1+1+2+6+24,1+2+2*4+6*8+24*16..)$.

It is to be expected that an official solution can be found in somewhere (the Putnam archive, American Mathematical Monthly, AOPS, etc). My point of raising this question is not to ask a solution of it, because I am not interested in problem solving techniques. Instead I want to ask the following questions:

1) Is the function $\sum\limits_{k=0} ^{p-1} k! n^{k}$ well known? Can it be expressed in some closed form via generating functions or other combinatorical tools? My combinatorical background is very weak so I think I should ask others.

2) In general how strong the statement is? For example, for $p$ quite large, how many elements in $\mathbb{Z}_{p}$ tend to satisfy $\sum \limits_{k=0} ^{p-1} k! n^{k}=0$?

3) It is possible to see the problem via some 'high level' proof? (I know David Speyer is found of this kind of thing). Because I am not specialized in number theory, the limited number theory knowledge I have in Dedekind domains and valuations seems to be quite irrelevant to this problem. But I think there should be some way this small problem generalizes to something more interesting to an expert.

  • 0
    @ChangweiZhou: The$r$e are some good answers on overflow. Check the l$i$nk at the top of my answer.2011-12-04

2 Answers 2

6

Edit: Asked on Overflow: There are some very good answer which can be found here which explain some deeper meaning: https://mathoverflow.net/questions/82648/truncated-exponential-series-modulo-p-deeper-meaning-for-a-putnam-question

I feel that looking at $\sum_{k=0}^{p-1} k!n^k$ without changing its form is the wrong way to approach this problem, and if there are deeper solutions they will come by modifying this first. After some rearrangements modulo $p$, what we are really looking at is the truncated exponential series.

Rephrasing the question: First, let us ignore $n=0$, as in this case the sum is just $1$, and instead consider only the multiplicative group. Letting $k=p-1-l$ and using Wilsons theorem and Fermats little theorem we can rewrite our sum as $\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!}.$

Proof of the question: Consider $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 $Q^{'}(n)=0$ so that $n$ is a double root of $Q(n).$ Since $\deg Q(n)=p$, we see that at most half of the integers $p\in\left\{ 1,2,\dots,p-1\right\}$ satisfy $E(n)=0.$ Since $E(0)=1$, we conclude the desired result.

Motivation: The first idea I had looked at $E(z)-E(-z)$, but if you carry through with the computations you can only show that at least $\frac{p-1}{4}$ are non zero. Instead, lets just look at the derivative of $E(z)$ which is $E(z)+z^{p-1}$. Knowing that multiple zeros are what we want as it means less zeros total, we must add a function whose derivative is $-1$ since this will force multiple zeros. The obvious choice is then $x^p-x$, as it leaves the original polynomial invariant.

Remark: If you ask about the truncated exponential, there are many papers in existence and probably a high level way to see the problem. For example, see the first part of http://www.science.unitn.it/~mattarei/Ricerca/Preprints/AH.pdf

  • 0
    @PatrickDaSilva: That was my first idea too. I wanted to show that $E(z)+E(-z)$ or $E(z)-E(-z)$ is never zero, but I couldn't do this. I could show that it didn't have too many double zeros which isn\t great and only gives us $\frac{p-1}{4}$.2011-12-04
0

I'm not sure about a complete generalization, but I approached it from a partial-general point in which I turned all terms after 1 + n into a partial sum which was always even. With some basic modular arithmetic the statement appeared pretty well closed, though for the extremely large primes it's anyone's guess.

As the test still runs until tomorrow for religious exceptions I'm not yet comfortable writing out my solutions. I'll extend my response tomorrow night.

  • 4
    @ChangweiZhou BeRi can't comment without having 50 reputation, although in either form I would welcome more detail in this response!2011-12-04