On 12/4/09, rcs@xmission.com <rcs@xmission.com> wrote:
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
Yes indeed (and better expressed than I had managed ...) But Gene raises an interesting point when he asks for the meaning of X_C_k when X is non-integral (and in \F_q say, q a prime power ... or maybe X p-adic). Regarding many variables: I suppose one could always bottle out a la NURBS, and just replace monomials X^i Y^j ... by (X_C_i)(X_C_j) ... But it's not very interesting without some evidence that --- say --- it permits a more uniform treatment of difference equations etc in many dimensions. I did look at the latter (rather arcane) subject a couple of decades or so in the past, but have at the moment forgotten everything I knew. Except that it's (as you might by now have guessed) a good deal trickier than one dimension! Fred Lunnon
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun