Ordinary polynomials P with integer coefficients have the property that the value of P(k) (mod M) depends only on the value of k (mod M). This is not true for binomial coefficients: Consider triangular numbers mod 2: The even-odd pattern for binom(k,2) goes eooeeooeeoo..., with period 4. As it happens, the number of polynomials, modulo a prime Q, of degree <Q, is Q^Q. This matches the possible vectors of Q residues mod Q. The polynomials are in 1-1 correspondence with the possible values of the vector [P(0),P(1),...,P(Q-1)]. [Exercise: What's the polynomial for the vector [100000...000]?] So if you tend to view a polynomial in terms of its numerical values, you can stop at degree Q-1. And if you don't take this viewpoint, then degrees >=Q come into the picture. [Exercise: What's different when Q is composite, or a prime power?] I think Fred is trying to get a better correspondence between sequences of integers and integer-coefficient combinomials. It makes going from the sequence's difference triangle to the combinomial representation trivial. It gives you a way to write sum(i=1...N, i^2) (mod 3). And you don't have to puzzle over the fact that the non-integer polynomial (x^3-x)/6 maps integers to integers. A downside is that more care is required in understanding expressions mod N. Early on, we learned that: for an expression like 3 X^2 + W Y Z - 314, when we evaluate this (mod 5), we're free to reduce all our intermediate computations or not, as convenient. Later we learn that we can use any convenient residue since they all come to the same thing, so in this case we can just use last digits. Still later we learn about things to be careful of: division & square roots, and that exponents should be reduced mod N-1 instead of N, and only when N is prime. When we introduce combinomials, the rules need some fixing up, since binom(A,B) (mod N) can't be evaluated simply from knowing the residues of A and B mod N. Fred, have I got this right? Rich ----- Quoting Eugene Salamin <gene_salamin@yahoo.com>:
From: Joshua Zucker <joshua.zucker@gmail.com>
To: math-fun <math-fun@mailman.xmission.com> Sent: Fri, December 4, 2009 9:21:46 AM Subject: Re: [math-fun] Expansion of charpoly's in terms of traces ?
On Fri, Dec 4, 2009 at 9:11 AM, Eugene Salamin <gene_salamin@yahoo.com> wrote:
I seem to be misunderstanding something here. The binomial coefficient x_C_k = x(x-1)...(x-k+1)/k! in char 0. How is it defined in finite char?
You can define it by Pascal's triangle. I think that's exactly equivalent to defining it in terms of being a binomial coefficient. The formula you give is better viewed as a consequence of the definition rather than the definition itself, in my opinion.
--Joshua Zucker _______________________________________________ I must be stupid today; I still don't understand. I can write Pascal's triangle in F_q, but what is x_C_k? -- Gene
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun