Re: Question about "polynomial evaluations"

On Jun 17, 11:51 pm, Brian Chandler <imaginator...@xxxxxxxxxxxxx>
wrote:
Arturo Magidin wrote:
On Jun 17, 2:16 pm, Brian Chandler <imaginator...@xxxxxxxxxxxxx>
wrote:

<snipped>

Yes; what I think you were aiming for is what I mentioned elsewhere:
polynomial functions as opposed to polynomials.

Ah, yes. Thanks -- your explanation made a lot of it clearer.

In fact, one can prove that if R is *any* finite field, then *every*
element of F(R) is a polynomial function; in particular, since F(R) is
finite, the map eval cannot be one-to-one.

Is this proof trivial?

It's one of those proofs that once you see it you realize it was
trivial, but may not occur to you otherwise.

It looks as though you can just "construct" a
polynomial for any function, given an unlimited amount of "space" to
play with. Intuitively, it ought to be possible to make a polynomial
(function) that maps p to q, and everything except p to 0, then you
just add them together. [?]

Yes, that's exactly the way it goes; the easiest is to simply define a
polynomial which is 0 at all elements of the field but one, and that
is 1 at that; this can be done as with Lagrange interpolation. For
example, if the elements are a1,..., aq, then define the polynomial as

p1(x) = (x-a2)(x-a3)...(x-aq)/(a1-a2)(a1-a3)...(a1-aq).

Then the polynomial has value 1 at a1, and 0 elsewhere. Do that for
each element of the field. Then take your favorite function, and
simply express is as a suitable sum of scalar multiples of these
polynomials.


x=0  x=1  "Evaluation"
 0    0    0
 1    1    1
 0    1    S (for 'same')
 1    0    D (for 'different')

OK, so I could rewrite these as the polynomial functions 0, 1, x, x+1,
but I'll leave the single character identifiers for ASCIIvenience, and
repeat the multiplication table for these polynomial functions:

To be honest, I'm not entirely sure what it is you are trying to
capture with these tables...


* 0 1 S D
0 0 0 0 0
1 0 1 S D
S 0 S S 0
D 0 D 0 D

Is this right? I suppose this reminds me how feeble my grasp is on
what a ring homomorphism is. There's a "shape-preserving" map from
polynomials (which certainly don't have zero divisors) to polynomial
functions (which do?) Hmm, so it means that the "zero-
polynomials"

Presumably, you mean "the polynomials that map to the zero
function"...

(like x^2+x) are an ideal, which doesn't do much except
remind me how feeble my grasp is on what an ideal is.

Yes; the collection of all polynomials that map to the zero function
are the kernel of the ring homomorphism, and therefore are an ideal
(in fact, ideals can be characterized as the kernels of ring ring
homomorphism, much like normal subgroups are precisely the kernels of
group homomorphisms).

For a field of p elements, p a prime, it is easy to see that two
polynomials of degree strictly less than p will yield the same
function if and only if they are identical (consider their difference,
which has degree strictly less than p, but has p distinct roots). From
some bit of work using long division, one can show that every ideal of
F[X] consists exactly of all multiples of some particular (monic)
polynomial. So the kernel of the map eval must be of the form alll
multiples of p(x)" for some suitable p(x). Since no polynomial of
degree less than p works, the polynomial x^p - x maps to the zero
function (this is Fermat's Little Theorem), then a bit of work yields
that the polynomials that map to the zero function are precisely the
(polynomial) multiples of x^p-x.

In the case of the field of 2 elements, this is the same as the
polynomial x^2+x; a polynomial with coefficients in F_2 yields the
zero function F_2-->F_2 if and only if it is a (polynomial) multiple
of x^2+x.

--
Arturo Magidin

--
Arturo Magidin
.

Relevant Pages

  • Re: A "How would you do this"-type of question. not Java-specific.
    ... a dot will appear on the map to indicate where that ZIP code ... coords and extrapolate those to x,y coords on your graphic map? ... arbitrary encoding -- some large-scale patterns are evident ... evaluating such high-degree polynomials with useful accuracy! ...
    (comp.lang.java.help)
  • Re: Fields and transcendentals
    ... homomorphism fails to be an isomorphism it's because t is ... since Kis formed by the inclusion of all polynomials in t, ... there be some elements of Kthat map to 0. ... and find a polynomial having t as a root. ...
    (sci.math)
  • Re: A "How would you do this"-type of question. not Java-specific.
    ... Eric Sosman wrote: ... a dot will appear on the map to indicate where that ZIP code ... evaluating such high-degree polynomials with useful accuracy! ...
    (comp.lang.java.help)
  • Re: A question on countability proof
    ... I defined the map T to map a polynomial with integer ... coefficients to its coordinate vector representation using the standard ... polynomials is countable, the set of algebraic numbers is countable? ... You have a countable union of finite sets (the finite sets are the ...
    (sci.math)
  • Re: The Algebraic Set
    ... why is the cardinality of A_n less than ... > polynomials, wouldn't the cardinality of A_n be larger than or equal to ... Let be n infinite sequences ... Map to nk + i. ...
    (sci.math)