Re: [math-fun] Expansion of charpoly's in terms of traces ?
<< . . . [O]ne of the many ways in which mathematicians conventionally complicate their lives is by defining polynomials over finite fields in an avoidably clumsy fashion. Restricting oneself to linear combinations of powers excludes a lot of functions which ought to be polynomial, but fail to do so on account of the Fermat little theorem x^p = x mod p.
I'm not aware of mathematicians who define polynomials over finite fields with respect to Fermat's Little Theorem. I thought the ring of polynomials over any field F is defined as all expressions of the form P(X) = c_n X^n + . . . + c_1 X + c_0, where all the c_k belong to F, and n is some nonnegative integer. With the natural addition and multiplication. (And such that two polynomials are equal precisely when all their coefficients c_k are equal.) No? Or am I misunderstanding something here? --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele
On 12/4/09, Dan Asimov <dasimov@earthlink.net> wrote:
<< . . . [O]ne of the many ways in which mathematicians conventionally
complicate their lives is by defining polynomials over finite fields in an avoidably clumsy fashion. Restricting oneself to linear combinations of powers excludes a lot of functions which ought to be polynomial, but fail to do so on account of the Fermat little theorem x^p = x mod p.
I'm not aware of mathematicians who define polynomials over finite fields with respect to Fermat's Little Theorem.
Indeed they don't --- that's exactly the problem!
I thought the ring of polynomials over any field F is defined as all expressions of the form
P(X) = c_n X^n + . . . + c_1 X + c_0,
where all the c_k belong to F, and n is some nonnegative integer. With the natural addition and multiplication. (And such that two polynomials are equal precisely when all their coefficients c_k are equal.)
Hm. On the face of it, I can't see that it makes any difference to the formal properties regarding algebraic extension etc if we substitute for the traditional P(X) = c_k X^k + . . . + c_1 X + c_0 (*) the alternative P(X) = c_k (x_C_k) + . . . + c_1 X + c_0 (**) where x_C_k denotes binomial coefficient. Has anybody out there thought about this question in more detail? On the other hand, when it comes to considering difference equations, linear recurrences and the like, we gain a completeness lacking before: the theory becomes much the same for both finite fields and rationals. Fred Lunnon
The misprint fairy's been visiting again --- for
P(X) = c_k (x_C_k) + . . . + c_1 X + c_0 (**)
read
P(X) = c_k (X_C_k) + . . . + c_1 X + c_0 (**)
[changing Dan's n to k to avoid clash with my previous n = Dan's X ...]. WFL
Addition of these forms is easy enough. Multiplication by X is a tad complicated, and multiplication of two forms is complicated. It looks like the division algorithm, where the divisor is monic, will have a wee bit of difficulty. Summation from 1...X is easier than with regular polys; integration & differentiation look doable but not neat. Shifting X -> X+1 looks easy; X -> 2X not so easy; nor X -> X^2 (or -> (X 2)). Composition P(Q(X)) is closed, and was never easy. End-for-end coefficient reversal for regular polynomials gets you X^D P(1/X); and the product of reversed polynomials is the reverse of the product; and the product of palindromic polynomials is a polyndrome. These all seem to fail for combinomials. What will you do for multivariate? Rich -------------- Quoting Fred lunnon <fred.lunnon@gmail.com>:
On 12/4/09, Dan Asimov <dasimov@earthlink.net> wrote:
<< . . . [O]ne of the many ways in which mathematicians conventionally
complicate their lives is by defining polynomials over finite fields in an avoidably clumsy fashion. Restricting oneself to linear combinations of powers excludes a lot of functions which ought to be polynomial, but fail to do so on account of the Fermat little theorem x^p = x mod p.
I'm not aware of mathematicians who define polynomials over finite fields with respect to Fermat's Little Theorem.
Indeed they don't --- that's exactly the problem!
I thought the ring of polynomials over any field F is defined as all expressions of the form
P(X) = c_n X^n + . . . + c_1 X + c_0,
where all the c_k belong to F, and n is some nonnegative integer. With the natural addition and multiplication. (And such that two polynomials are equal precisely when all their coefficients c_k are equal.)
Hm. On the face of it, I can't see that it makes any difference to the formal properties regarding algebraic extension etc if we substitute for the traditional
P(X) = c_k X^k + . . . + c_1 X + c_0 (*)
the alternative
P(X) = c_k (x_C_k) + . . . + c_1 X + c_0 (**)
where x_C_k denotes binomial coefficient. Has anybody out there thought about this question in more detail?
On the other hand, when it comes to considering difference equations, linear recurrences and the like, we gain a completeness lacking before: the theory becomes much the same for both finite fields and rationals.
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 12/4/09, rcs@xmission.com <rcs@xmission.com> wrote:
Addition of these forms is easy enough. Multiplication by X is a tad complicated, and multiplication of two forms is complicated. It looks like the division algorithm, where the divisor is monic, will have a wee bit of difficulty. Summation from 1...X is easier than with regular polys; integration & differentiation look doable but not neat. Shifting X -> X+1 looks easy; X -> 2X not so easy; nor X -> X^2 (or -> (X 2)). Composition P(Q(X)) is closed, and was never easy. End-for-end coefficient reversal for regular polynomials gets you X^D P(1/X); and the product of reversed polynomials is the reverse of the product; and the product of palindromic polynomials is a polyndrome. These all seem to fail for combinomials.
Might be a nice project for somebody here ...
What will you do for multivariate?
Ouch! Very good question, which I have never yet had to consider ... An obvious approach would attempt to replace a basis of monomials (homogeneous in m variables, say) by a basis of m-nomial coefficients: for m-1 = 2 variables, try somehow involving the trinomial coefficients (when i+j+k >= 0) T_ijk = 1 for i = j = k = 0; 0 for i < 0 or j < 0 or k < 0; T_{i-1,j,k} + T_{i,j-1,k} + T_{i,j,k-1} otherwise. There may be an analogy here with Bezier curves (standard curve-modelling technique for for computer graphics, etc). It's easy to interpolate 1-dimensional smooth curves, using what is essentially a glorified version of Pascal's triangle; but the direct generalisation to more dimensions appears so esoteric that the current standard (NURBS) bottles out of it, relying instead on Cartesian products of 1-dimensional interpolations. [A relevant paper from long ago lies buried somewhere in my paper files, whence it might be disinterred on request.] Should this be the case --- I'm outta there! Fred Lunnon
Hm. On the face of it, I can't see that it makes any difference to the formal properties regarding algebraic extension etc if we substitute for the traditional
P(X) = c_k X^k + . . . + c_1 X + c_0 (*)
the alternative
P(X) = c_k (x_C_k) + . . . + c_1 X + c_0 (**)
where x_C_k denotes binomial coefficient. Has anybody out there thought about this question in more detail?
On the other hand, when it comes to considering difference equations, linear recurrences and the like, we gain a completeness lacking before: the theory becomes much the same for both finite fields and rationals.
Fred Lunnon
_______________________________________________ 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
From: Fred lunnon <fred.lunnon@gmail.com> To: Dan Asimov <dasimov@earthlink.net>; math-fun <math-fun@mailman.xmission.com> Sent: Thu, December 3, 2009 5:45:48 PM Subject: Re: [math-fun] Expansion of charpoly's in terms of traces ? On 12/4/09, Dan Asimov <dasimov@earthlink.net> wrote:
<< . . . [O]ne of the many ways in which mathematicians conventionally
complicate their lives is by defining polynomials over finite fields in an avoidably clumsy fashion. Restricting oneself to linear combinations of powers excludes a lot of functions which ought to be polynomial, but fail to do so on account of the Fermat little theorem x^p = x mod p.
I'm not aware of mathematicians who define polynomials over finite fields with respect to Fermat's Little Theorem.
Indeed they don't --- that's exactly the problem!
I thought the ring of polynomials over any field F is defined as all expressions of the form
P(X) = c_n X^n + . . . + c_1 X + c_0,
where all the c_k belong to F, and n is some nonnegative integer. With the natural addition and multiplication. (And such that two polynomials are equal precisely when all their coefficients c_k are equal.)
Hm. On the face of it, I can't see that it makes any difference to the formal properties regarding algebraic extension etc if we substitute for the traditional P(X) = c_k X^k + . . . + c_1 X + c_0 (*) the alternative P(X) = c_k (x_C_k) + . . . + c_1 X + c_0 (**) where x_C_k denotes binomial coefficient. Has anybody out there thought about this question in more detail? On the other hand, when it comes to considering difference equations, linear recurrences and the like, we gain a completeness lacking before: the theory becomes much the same for both finite fields and rationals. Fred Lunnon ________________________________ 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? -- Gene
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
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
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
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
If I've got an element X of F(2^4), like X = g^3 + g + 1, where g is a generator, what is X_C_3? Or are you only considering prime fields? On Fri, Dec 4, 2009 at 12:16 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
From: Fred lunnon <fred.lunnon@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Fri, December 4, 2009 12:16:25 PM Subject: Re: [math-fun] Expansion of charpoly's in terms of traces ? 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
________________________________ Polynomials wear two hats. On the one hand, they are elements of a certain ring R[x] generated by an indeterminate x and a coefficient ring R, and on the other hand they are functions from R to R. When R is a finite field of order q, a polynomial p as a function uniquely determines a polynomial p as ring element only mod the ideal (x^q-x). Furthermore, according to the Lagrange interpolation theorem, every function F_q --> F_q is the same as some polynomial function of degree less than q. So perhaps this notion of combinomials is useful only over infinite rings. -- Gene
On 12/4/09, Eugene Salamin <gene_salamin@yahoo.com> wrote:
Polynomials wear two hats. On the one hand, they are elements of a certain ring R[x] generated by an indeterminate x and a coefficient ring R, and on the other hand they are functions from R to R. When R is a finite field of order q, a polynomial p as a function uniquely determines a polynomial p as ring element only mod the ideal (x^q-x). Furthermore, according to the Lagrange interpolation theorem, every function F_q --> F_q is the same as some polynomial function of degree less than q. So perhaps this notion of combinomials is useful only over infinite rings.
-- Gene
More accurately, when the domain is distinct from the range --- in the application I used this for (sequences over a prime field) , the domain is \N and the range \F_p. WFL
On Fri, Dec 4, 2009 at 3:28 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
the domain is \N and the range \F_p. WFL
OK, that makes all the difference in the world. -- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
At which point, it suddenly becomes obvious that this notion doesn't help in the slightest with modifying Henry's char poly expansion to meet Gene's criticism in finite characteristic. Ah well --- apologies for a big fat red herring, everybody! Does Victor have a reference for the BCH decoding material mentioned earlier? I'm intrigued now to know just how this problem can be sorted out properly. WFL On 12/5/09, Mike Stay <metaweta@gmail.com> wrote:
On Fri, Dec 4, 2009 at 3:28 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
the domain is \N and the range \F_p. WFL
OK, that makes all the difference in the world.
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
_______________________________________________
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
From: Fred lunnon <fred.lunnon@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Sent: Sat, December 5, 2009 1:32:54 AM Subject: Re: [math-fun] Expansion of charpoly's in terms of traces ? At which point, it suddenly becomes obvious that this notion doesn't help in the slightest with modifying Henry's char poly expansion to meet Gene's criticism in finite characteristic. Ah well --- apologies for a big fat red herring, everybody! Does Victor have a reference for the BCH decoding material mentioned earlier? I'm intrigued now to know just how this problem can be sorted out properly. WFL On 12/5/09, Mike Stay <metaweta@gmail.com> wrote:
On Fri, Dec 4, 2009 at 3:28 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
the domain is \N and the range \F_p. WFL
OK, that makes all the difference in the world.
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
This discussion has been quite useful. It led to this concept. Definition: A polynomial p(x) with rational coefficients is said to be "almost integer" if p(n) is an integer for all integers n. Example: x(x+1)/2. Conjecture: If f is a periodic function from the integers to the integers mod n, then f(k) = p(k) mod n for some almost integer polynomial p. This idea can also be extended to multivariate polynomials. -- Gene
On Sat, 5 Dec 2009, Eugene Salamin wrote:
Definition: A polynomial p(x) with rational coefficients is said to be "almost integer" if p(n) is an integer for all integers n. Example: x(x+1)/2.
It appears that such polynomials have been considered previously under the name "integer polynomials". It is interesting that they form a free abelian group with basis: t(t - 1)...(t - k + 1)/k!, k = 0,1,2,... according to: http://en.wikipedia.org/wiki/Integer-valued_polynomial I encounted them recently when I learned of "Schinzel's hypothesis H" http://en.wikipedia.org/wiki/Schinzel's_hypothesis_H.
An interesting way of approaching this might be via the p-adic Gamma function of Morita. It's basically a slightly fixed up version of the ordinary Gamma function: Instead of always using the recursion Gamma(x+1) = x Gamma(x), make the recursion Gamma(x+1) = Gamma(x) if x is an integer divisible by p. The amazing thing is that the resulting function is a p-adic analytic function (since the integers are dense in the p-adic integers, it extends uniquely to a p-adic continuous function), and whose value is always a p-adic unit, so it can be unambiguously reduced modulo. You can then use that to make a p-adic beta function (the beta function being the right generalization of the binomial coefficient). Victor On Sat, Dec 5, 2009 at 3:11 PM, Edwin Clark <eclark@math.usf.edu> wrote:
On Sat, 5 Dec 2009, Eugene Salamin wrote:
Definition: A polynomial p(x) with rational coefficients is said to be "almost integer" if p(n) is an integer for all integers n. Example: x(x+1)/2.
It appears that such polynomials have been considered previously under the name "integer polynomials". It is interesting that they form a free abelian group with basis: t(t - 1)...(t - k + 1)/k!, k = 0,1,2,... according to:
http://en.wikipedia.org/wiki/Integer-valued_polynomial
I encounted them recently when I learned of "Schinzel's hypothesis H"
http://en.wikipedia.org/wiki/Schinzel's_hypothesis_H.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
If your goal is to find the char-poly modulo a small prime, you _can_ use the trace expansion: Just compute over the rationals. Work modulo several larger primes (> matrix size N), reconstruct the rational solution, reduce mod the small prime of interest. Alternatively, you can just work modulo a power of the small prime; I think the exponent need only exceed the degree to which the small prime divides N!. [N/(p-1)]+1 should do. General finite fields look harder: Maybe use (symbolic) algebraic numbers, over the rationals, then reduce the final answer mod the small prime. For example, phi is a root of X^2 = X+1, and A + B phi models GF[2^2] when A and B are taken mod 2. Rich -------------- Quoting Fred lunnon <fred.lunnon@gmail.com>:
At which point, it suddenly becomes obvious that this notion doesn't help in the slightest with modifying Henry's char poly expansion to meet Gene's criticism in finite characteristic.
Ah well --- apologies for a big fat red herring, everybody!
Does Victor have a reference for the BCH decoding material mentioned earlier? I'm intrigued now to know just how this problem can be sorted out properly.
WFL
On 12/5/09, Mike Stay <metaweta@gmail.com> wrote:
On Fri, Dec 4, 2009 at 3:28 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
the domain is \N and the range \F_p. WFL
OK, that makes all the difference in the world.
-- Mike Stay - metaweta@gmail.com http://math.ucr.edu/~mike http://reperiendi.wordpress.com
_______________________________________________
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
participants (8)
-
Dan Asimov -
Edwin Clark -
Eugene Salamin -
Fred lunnon -
Joshua Zucker -
Mike Stay -
rcs＠xmission.com -
victor miller