Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
I actually thought of this question for a while during the exam, and sadly enough it got me nowhere good. I see that you don't look very busy during the putnam exam if you have the time to think about that kind of generalization! XD Great thoughts on it though. –  Patrick Da Silva Dec 4 '11 at 6:12
1  
@PatrickDaSilva: I spent about one hour in this problem after I solved B2,B3 and B1, but due to my poor number theory background I could not reach anywhere. –  Kerry Dec 4 '11 at 19:12
2  
@ChangweiZhou: Usually these types of modular arithmetic sum questions are very similar. Rearrangements with basic theorems is usually a good place start. Here, since it is talking about the set of all $n$, we notice that it is a question about how many zeros a polynomial has. Keeping this in mind, we try to recall facts about polynomials mod p. In a finite field, a polynomial has no more zeros then its degree, and the the gcd of the polynomial with the derivative tells us about double roots. These basic ideas are then enough to solve the question. –  Eric Naslund Dec 4 '11 at 19:22
    
@EricNaslund: I feel this problem is actually more than modular arithmetic. It is nice to see a relatively closed form in your answer, but as I stated I am more interested in how the function behaves in $\mathbb{Z}_{p}$ instead of finding techniques to solve it. I am sure there is some way to solve this without using fancy theoretical machinery as every Putnam problem, but I am more interested to understand the problem properly, not just to get why the statement is true. –  Kerry Dec 4 '11 at 20:07
    
@ChangweiZhou: It is likely that Noam Elkies could tell you everything you wanted to know about this problem, it might be worth posting on Math Overflow just to get his attention. –  Eric Naslund Dec 4 '11 at 20:26

2 Answers 2

up vote 6 down vote accepted

Edit: Asked on Overflow: There are some very good answer which can be found here which explain some deeper meaning: http://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

share|improve this answer
    
I have a technical question. Why we have $\frac{1}{\prod^{i=l}_{i=1}(p-i)}=(-1)^{l}*\frac{1}{l!}$? I cannot see this directly via Wilson's theorem (which asserts that $(p-1)!\equiv -1$(mod p). –  Kerry Dec 4 '11 at 19:32
    
@ChangweiZhou: Because $(p-i)\equiv -i \pmod{p}$. –  Eric Naslund Dec 4 '11 at 19:36
    
Thanks, this is clear. –  Kerry Dec 4 '11 at 19:37
    
My first idea was to see that if $n$ is a root then $p-n$ is not, but I only conjectured it and got me nowhere... seeing that roots are double roots is very clever. +1! –  Patrick Da Silva Dec 4 '11 at 22:00
    
@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}$. –  Eric Naslund Dec 4 '11 at 22:11

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.

share|improve this answer
3  
I think this is more appropriate as a comment instead of an "answer" at here. Could you more elaborate on the the "pretty well closed" form you found? –  Kerry Dec 4 '11 at 6:28
4  
@ChangweiZhou BeRi can't comment without having 50 reputation, although in either form I would welcome more detail in this response! –  Dylan Moreland Dec 4 '11 at 6:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.