On Friday, August 22, 2014 2:04:35 PM UTC-7, Bill Hart wrote:
>
>
> RJF said...
>> I don't know about canonical maps. The term "canonical representation"
>> makes sense to me.
>>
>
> He means this. In algebra Z/nZ is actually a ring modulo an ideal. Z is
> the ring, nZ is the ideal.
>
> The elements of Z/nZ are usually written a + nZ. It means precisely this:
>
> a + nZ = { x in Z such that x = a +nk for some k in Z }
>
> So it is a *set* of numbers (actually, in algebra it is called a coset).
>
> When you write Mod(a, n) you really mean a + nZ if you are an algebraist,
> i.e. the *set* of numbers congruent to a modulo n.
>
> So Z/nZ consists of (co)sets of the form C = Mod(a, n) = a + nZ. If you
> like Z/nZ is a set of sets (actually a group of cosets in algebra).
>
> There is a canonical map from Z to Z/nZ: we map b in Z to the (co)set C in
> Z/nZ that contains b.
>
> If a = b mod n then C = mod(a, n) is the *only* one of these sets which
> contains b. So the map is canonical. We only have one choice.
>
> But there is no canonical map going the other way. For any such (co)set C,
> which element of Z are you going to pick? Any of the elements of C will do.
>
> You can make an arbitrary choice, e.g. pick the unique element of C in the
> range [0, n). Or you could pick the unique element in the range (-n/2,
> n/2]. But that is not a canonical choice. You had to make an arbitrary
> choice. Someone else may have made a different choice. (Indeed some people
> use the latter choice because some algorithms, such as gcd and Jacobi
> symbols run faster with this choice.)
>
> So canonical map means there is only one way you could define the map. You
> don't need to tell anyone what your map is, because they *have* to make the
> same choice as you, as there are no alternatives. That's the meaning of
> canonical in mathematics.
>
> It's probably not a terminology they teach in Computer Algebra,
>
There are few courses in Computer Algebra. But the term canonical is used
differently. In fact, two systems could
have different canonical forms (e.g. in your example, [0,n-1] or
[-(n-1)/2, (n-1)/2] for representatives of the numbers mod n.
Just as one system could have 1+x+x^2 and another x^2+x+1.
But for each system with a canonical form for polynomials, all polynomials
in its canonical form would be
identical bit patterns. Some systems e.g. Maple go further and have all
canonical and equal forms stored
at the same machine address.
> but it is taught to undergraduates around the world in pure mathematics.
>
Um, some English speaking students who take, um, certain electives?
>
> The whole argument here is that because only one direction gives a
> canonical map, coercion must only proceed in that direction. Otherwise your
> computer algebra system is making a choice that someone else's computer
> algebra system does not.
>
But that is perfectly all right. canoncality is with respect to a
particular computer system. At least
my kind of canonicality.
Otherwise we could not live with BigEndian and LittleEndian computers. But
we do.
>
>>
>>
>> ... big snip
RJF
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
