Combining finite/rational fields

[Michael Orlitzky]

I just opened,

http://trac.sagemath.org/sage_trac/ticket/13720

intending to submit a patch a few minutes later, but I've hit a problem.
The current examples feature,

sage: legendre_P(3, GF(11)(5))
8

which works due to a quirk in Maxima's string representation of the
polynomial:

sage: maxima.eval('legendre_p(%s,x)'%ZZ(3))
'-6*(1-x)-5*(1-x)^3/2+15*(1-x)^2/2+1'

In Sage, this becomes,

sage: -6*(1-x)-5*(1-x)^3/2+15*(1-x)^2/2+1
5/2*(x - 1)^3 + 15/2*(x - 1)^2 + 6*x - 5

with division (in Maxima) replaced by rational multiplication in Sage.
This kills the last example:

sage: GF(11)(5) / 2
8

sage: (1/2) * GF(11)(5)
----------------------------------------------------------------------
TypeError
...
TypeError: unsupported operand parent(s) for '*': 'Rational Field'
and 'Finite Field of size 11'

So, substituting GF(11)(5) into the equation before converting it to
Sage works. But doing the entire computation in Sage fails.

How easy would this be to fix? I could convert my polynomials to Maxima
and back I guess, but that seems a little goofy.

[Robert Bradshaw]

How about doing

sage: f = legendre_P(3, GF(11)['x'].gen()); f
8*x^3 + 4*x
sage: parent(f)
Univariate Polynomial Ring in x over Finite Field of size 11
sage: f(5)
8

However, the implementation (manipulating strings) is pretty horrid.

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To post to this group, send email to sage-...@googlegroups.com.
> To unsubscribe from this group, send email to sage-devel+...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel?hl=en.
>
>

[Nils Bruin]

On Nov 17, 9:28 pm, Robert Bradshaw <rober...@math.washington.edu>
wrote:

> How about doing
>
> sage: f = legendre_P(3, GF(11)['x'].gen()); f
>  8*x^3 + 4*x
> sage: parent(f)
>  Univariate Polynomial Ring in x over Finite Field of size 11
> sage: f(5)
>  8
>
> However, the implementation (manipulating strings) is pretty horrid.

That can be cleaned up quite a bit if this were rewritten to use
maxima_lib. In that case the multiplications would probably be actual
sage multiplications too, so would likely lead to the same errors as
in Sage, though.

The issue really is whether "rational number"*"finite field element"
should be supported. The problem is of course that there is no common
parent for *all* possible element pairs, so the coercion framework
rightfully refuses. It would be awfully convenient if it were allowed
when it makes sense (and just throw a ZeroDivision otherwise).

Conversion does do the right thing,you just need to phrase your
problem in a way that allows conversion rules come into play:

sage: Qx.<x>=QQ[]
sage: Fy.<y>=GF(101)[]
sage: f=legendr
legendre_P legendre_Q legendre_symbol
sage: f=legendre_P(3,x)
sage: f
5/2*x^3 - 3/2*x
sage: Fy(f)
53*y^3 + 49*y

After that you can of course evaluate the converted polynomial. The
issue of course is that Legendre polynomials cannot be defined this
way in all characteristics:

sage: Fz.<z>=GF(2)[]
sage: Fz(f)
ZeroDivisionError: Inverse does not exist.

[Dima Pasechnik]

Can Sage work with Z_{(11)} ? It makes perfect sense to talk about the
product of an element of Z_{(p)} and an element of GF(p), as GF(p) is an
Z_{(p)}-module.
Conceivably, one could implement the product of a rational number and an
element of GF(p) (or even GF(p^k)) this way.

Well, this is probably a huge overkill of the problem at hand.

[David Roe]

I don't think Sage currently supports localizations, though it would make a nice project for a student....
David

[Michael Orlitzky]

This works with the current legendre_P (as does Robert's solution)
thanks to the string magic, but wouldn't work with my scaled
implementation that tries to multiply/divide `x` by terms involving the
endpoints of the interval.

Ultimately it works if I stick to ZZ, and I was able to work around this
one regression by checking for the special case where the endpoints are
in ZZ. I just had to rearrange the terms a bit to avoid creating a rational.

These both work:

sage: ZZ(5) * GF(11)(5)
3
sage: GF(11)(5) / ZZ(8)
2

but this doesn't:

sage: (ZZ(5)/ZZ(8)) * GF(11)(5)

...
TypeError: unsupported operand parent(s) for '*': 'Rational Field'

and 'Finite Field of size 11'

I think it might as well be allowed, since this is:

sage: GF(2)(1) / ZZ(2)
...

ZeroDivisionError: Inverse does not exist.

I left the case with rational endpoints unhandled; I don't think anyone
is evaluating Legendre polynomials in GF(11), but I didn't want to cause
an unnecessary regression.

[Dima Pasechnik]

On 2012-11-18, Nils Bruin <nbr...@sfu.ca> wrote:
> On Nov 17, 9:28 pm, Robert Bradshaw <rober...@math.washington.edu>
> wrote:
>> How about doing
>>
>> sage: f = legendre_P(3, GF(11)['x'].gen()); f
>>  8*x^3 + 4*x
>> sage: parent(f)
>>  Univariate Polynomial Ring in x over Finite Field of size 11
>> sage: f(5)
>>  8
>>
>> However, the implementation (manipulating strings) is pretty horrid.
>
> That can be cleaned up quite a bit if this were rewritten to use
> maxima_lib. In that case the multiplications would probably be actual
> sage multiplications too, so would likely lead to the same errors as
> in Sage, though.
>
> The issue really is whether "rational number"*"finite field element"
> should be supported. The problem is of course that there is no common
> parent for *all* possible element pairs, so the coercion framework
> rightfully refuses. It would be awfully convenient if it were allowed
> when it makes sense (and just throw a ZeroDivision otherwise).

How different is "rational number"*"finite field element"
from division, which is also a partial operation?
(Well, I admit I don't know Sage's coersion model at all...)

Dima

[Nils Bruin]

On Nov 18, 9:22 am, Dima Pasechnik <dimp...@gmail.com> wrote:

> How different is "rational number"*"finite field element"
> from division, which is also a partial operation?
> (Well, I admit I don't know Sage's coersion model at all...)

Robert is probably more qualified to explain, but I'll try for now.
Both
<finite field element> * <rational number>
and
<finite field element> / <integer>
fit the pattern
<element of A> <binary operation> <element of B>

In order to make sense of this, sage tries to find/construct a
"minimal" common parent C into which both A and B coerce. Integers
coerce into finite fields; all of them. It's the operation that later
fails.

Rationals don't coerce into finite fields and that's probably a good
thing.

How damaging would it be to borrow the same mechanism as scalar
multiplication for this, i.e., define a "partial" action of Q on
GF(p)?

How much would we gain by doing so? If we don't automatically get a
"partial" action of Q on GF(p)['x'] and VectorSpace(GF(p),3) it's
probably not worth the effort.

[Dima Pasechnik]

On 2012-11-18, Nils Bruin <nbr...@sfu.ca> wrote:

> On Nov 18, 9:22 am, Dima Pasechnik <dimp...@gmail.com> wrote:
>
>> How different is "rational number"*"finite field element"
>> from division, which is also a partial operation?
>> (Well, I admit I don't know Sage's coersion model at all...)
>
> Robert is probably more qualified to explain, but I'll try for now.
> Both
><finite field element> * <rational number>
> and
><finite field element> / <integer>
> fit the pattern
><element of A> <binary operation> <element of B>
>
> In order to make sense of this, sage tries to find/construct a
> "minimal" common parent C into which both A and B coerce. Integers
> coerce into finite fields; all of them. It's the operation that later
> fails.
>
> Rationals don't coerce into finite fields and that's probably a good
> thing.
>

why? E.g. in GAP it's pefectly possible:
gap> Z(11)*(5/7);
Z(11)^8

(and, certainly,
gap> Z(11)*(5/11);
Error, ModRat: for <r>/<s> mod <n>, <s>/gcd(<r>,<s>) and <n> must be
coprime in...)

What does Sage win by not allowing this coersion?
It's obvious what is loses - flexibility.

> How damaging would it be to borrow the same mechanism as scalar
> multiplication for this, i.e., define a "partial" action of Q on
> GF(p)?
>
> How much would we gain by doing so? If we don't automatically get a
> "partial" action of Q on GF(p)['x'] and VectorSpace(GF(p),3) it's
> probably not worth the effort.

if I understand it right, if we define the minimal parent of
elements of GF(p^k) and QQ to be GF(p^k), then we get all this for free.

Dima

[Nils Bruin]

On Nov 18, 6:28 pm, Dima Pasechnik <dimp...@gmail.com> wrote:

> if I understand it right, if we define the minimal parent of
> elements of GF(p^k) and QQ to be GF(p^k), then we get all this for free.

Yes, but the problem is that there is NOT a natural morphism QQ ->
GF(p^k); only a partial map. I don't know how much code breaks if
coercions exist, but fail on particular applications. I'd err towards
mathematical correctness and rigour on this one.

Anyway, if you really want to, you can have it anyway.

sage: F=GF(5)
sage: F.register_coercion(QQ)
sage: F(2)*1/2
1
sage: F(2)*1/5

ZeroDivisionError: Inverse does not exist.

There was orginally an idea to have a context manager to temporarily
install more controversial coercions, a la:

with coercion(F.convert_map_from(QQ)):
<do something that needs special coercions>

I don't know whether that has ever happened, but it would strike the
perfect balance for situations like this: Convenience when you want
it, without breaking mathematical rigour by default.

[Dima Pasechnik]

On 2012-11-19, Nils Bruin <nbr...@sfu.ca> wrote:
> On Nov 18, 6:28 pm, Dima Pasechnik <dimp...@gmail.com> wrote:
>
>> if I understand it right, if we define the minimal parent of
>> elements of GF(p^k) and QQ to be GF(p^k), then we get all this for free.
>
> Yes, but the problem is that there is NOT a natural morphism QQ ->
> GF(p^k); only a partial map. I don't know how much code breaks if
> coercions exist, but fail on particular applications. I'd err towards
> mathematical correctness and rigour on this one.

I can only imagine broken doctests, testing that such a coersion
does not exist. :-)

Perhaps the coersion system itself might be a bit confused, but
it looks like here we talk rigour for the sake of rigour, without
any benefits.

Conceptually, field division is a partial map too.

Dima

[Nils Bruin]

On Nov 19, 6:22 am, Dima Pasechnik <dimp...@gmail.com> wrote:

> Perhaps the coersion system itself might be a bit confused, but
> it looks like here we talk rigour for the sake of rigour, without
> any benefits.

One benefit is error detection and picking proper normalizations. For
instance, if you create a "reduction map" from a projective variety to
one over GF(p), denominators need to be cleared. First you need to
clear them from the equations, but assuming you did that, it's also
important that you properly clear denominators from the
representatives for your projective points (i.e, the projective point
(1:1/p) should be represented by (p:1) before it gets mapped over).

However, projective points over Q usually do normalized with a 1 in a
given coordinate, forcing denominators elsewhere. With an automatic
coercion you may well succeed in defining a map, only to find it
doesn't evaluate in points where you thought it should.

Nasty complications with the coercion framework always happen a couple
of levels removed from the source of the problems, so I've given up on
only guarding against problems I can "imagine" and prefer the more
defensive stance of sticking with what is mathematically guaranteed to
work. If we ensure there are reasonable ways to loosen the stringent
defaults I think we can still end up with a workable system.

> Conceptually, field division is a partial map too.

Yes, and it always is. So assuming it's not will surely be a bug.

[Dima Pasechnik]

On 2012-11-19, Nils Bruin <nbr...@sfu.ca> wrote:

> On Nov 19, 6:22 am, Dima Pasechnik <dimp...@gmail.com> wrote:
>
>> Perhaps the coersion system itself might be a bit confused, but
>> it looks like here we talk rigour for the sake of rigour, without
>> any benefits.
>
> One benefit is error detection and picking proper normalizations. For
> instance, if you create a "reduction map" from a projective variety to
> one over GF(p), denominators need to be cleared. First you need to
> clear them from the equations, but assuming you did that, it's also
> important that you properly clear denominators from the
> representatives for your projective points (i.e, the projective point
> (1:1/p) should be represented by (p:1) before it gets mapped over).
>
> However, projective points over Q usually do normalized with a 1 in a
> given coordinate, forcing denominators elsewhere. With an automatic
> coercion you may well succeed in defining a map, only to find it
> doesn't evaluate in points where you thought it should.

hmm, I don't think this example will fly. If you happen to have a
divisior of p in the denominator then you get a point with every
nonzero coordinate divisible by p. So the reduction of it is
(0:0..:0) -- oeps --- a runtime error sowieso...

>
> Nasty complications with the coercion framework always happen a couple
> of levels removed from the source of the problems, so I've given up on
> only guarding against problems I can "imagine" and prefer the more
> defensive stance of sticking with what is mathematically guaranteed to
> work. If we ensure there are reasonable ways to loosen the stringent
> defaults I think we can still end up with a workable system.
>
>> Conceptually, field division is a partial map too.
>
> Yes, and it always is. So assuming it's not will surely be a bug.

Don't you think it's totally inconsequent that Sage
can divide an element of GF(p) by an integer (and sometimes get a
runtime error, sure), but Sage cannot multiply by the inverse of this
integer? This looks like a bug, actually, IMHO.

[P Purkayastha]

In fact, the behavior in Sage is *inconsistent*, and I think in this
particular case, the inconsistency should get priority of getting fixed
over trying to enforce rigor.:


sage: GF(7)(4)*2/3
5
sage: 2/3*GF(7)(4)

TypeError: unsupported operand parent(s) for '*': 'Rational Field' and

'Finite Field of size 7'


By following precedence in evaluation, the first one works while the
second one doesn't. Mathematically speaking, if the first one gives a
particular answer, then the second one should also give the same answer,
as should

sage: GF(7)(4)*(2/3)

which also fails because of precedence in the evaluation.

It is not like it is hard to coerce the numbers into the finite field,
because the numerator and the denominators can be individually accessed
by doing (2/3).numerator() and (2/3).denominator().

[Simon King]

Hi all!

On 2012-11-21, P Purkayastha <ppu...@gmail.com> wrote:
> In fact, the behavior in Sage is *inconsistent*, and I think in this
> particular case, the inconsistency should get priority of getting fixed
> over trying to enforce rigor.:

I wouldn't think it is a fix, *unless* it is done in a rigorous way.

What's the problem here? We can devide the elements of one integral domain
R1 by some elements of another integral domain R2, but (for good reasons!)
we can't multiply elements of R1 with elements of the fraction field of R2.

A potential solution (and it could be that this is what you suggested)
is to say: If there is a coercion map phi of R2 into R1, then Frac(R2)
acts on R1 by multiplication, via (p/q)*r1 = phi(p)*r1/phi(q).

I do think this would comply with Sage's category framework. I don't
recall the name of the methods that need to be provided for implementing
an action (act_on?), but I think it would be possible to provide a
generic implementation for fraction field elements.

Cheers,
Simon

[P Purkayastha]

On 11/21/2012 10:53 PM, Simon King wrote:
> Hi all!
>
> On 2012-11-21, P Purkayastha <ppu...@gmail.com> wrote:
>> In fact, the behavior in Sage is *inconsistent*, and I think in this
>> particular case, the inconsistency should get priority of getting fixed
>> over trying to enforce rigor.:
>
> I wouldn't think it is a fix, *unless* it is done in a rigorous way.
>
> What's the problem here? We can devide the elements of one integral domain
> R1 by some elements of another integral domain R2, but (for good reasons!)
> we can't multiply elements of R1 with elements of the fraction field of R2.
>
> A potential solution (and it could be that this is what you suggested)
> is to say: If there is a coercion map phi of R2 into R1, then Frac(R2)
> acts on R1 by multiplication, via (p/q)*r1 = phi(p)*r1/phi(q).

What I am asking for is quite simple. If I see a fractional element f =
p/q during multiplication or division (like p/q*alpha) then in the
appropriate operation, I would simply run

self(f.numerator())/self(f.denominator())*alpha.

Probably there are more efficient ways of doing this. This brings me to
the last problem:

GF(5)(3) + 2/3 or 2/3 + GF(5)(3), both result in errors. If we allow
multiplication, then again there is an inconsistency with addition and
subtraction. Any ideas what should be done here? Is it always correct to
coerce to the finite field?

[Dima Pasechnik]

On 2012-11-21, Simon King <simon...@uni-jena.de> wrote:
> Hi all!
>
> On 2012-11-21, P Purkayastha <ppu...@gmail.com> wrote:
>> In fact, the behavior in Sage is *inconsistent*, and I think in this
>> particular case, the inconsistency should get priority of getting fixed
>> over trying to enforce rigor.:
>
> I wouldn't think it is a fix, *unless* it is done in a rigorous way.
>
> What's the problem here? We can devide the elements of one integral domain
> R1 by some elements of another integral domain R2, but (for good reasons!)
> we can't multiply elements of R1 with elements of the fraction field of R2.

I don't follow this. Why can we divide more than multiply? What
GF(7)(5)/3 does, it multiplies GF(7)(5) by the element 1/3 of QQ. And
GF(7)(5)/14 fails at runtime just as (not yet allowed) GF(7)(5)*(1/14)
would. To be completely kosher, one might talk about GF(7)(5)*(1/3) as
multiplication of an element of GF(7) and an element of Z_{(7)}.

[I cannot resist quoting a russian joke, about policemen knowing only
two arithmetic operations: subtraction and division...]

Best,
Dima

[Dima Pasechnik]

On 2012-11-21, P Purkayastha <ppu...@gmail.com> wrote:
> On 11/21/2012 10:53 PM, Simon King wrote:
>> Hi all!
>>
>> On 2012-11-21, P Purkayastha <ppu...@gmail.com> wrote:
>>> In fact, the behavior in Sage is *inconsistent*, and I think in this
>>> particular case, the inconsistency should get priority of getting fixed
>>> over trying to enforce rigor.:
>>
>> I wouldn't think it is a fix, *unless* it is done in a rigorous way.
>>
>> What's the problem here? We can devide the elements of one integral domain
>> R1 by some elements of another integral domain R2, but (for good reasons!)
>> we can't multiply elements of R1 with elements of the fraction field of R2.
>>
>> A potential solution (and it could be that this is what you suggested)
>> is to say: If there is a coercion map phi of R2 into R1, then Frac(R2)
>> acts on R1 by multiplication, via (p/q)*r1 = phi(p)*r1/phi(q).
>
> What I am asking for is quite simple. If I see a fractional element f =
> p/q during multiplication or division (like p/q*alpha) then in the
> appropriate operation, I would simply run
>
> self(f.numerator())/self(f.denominator())*alpha.
>
> Probably there are more efficient ways of doing this. This brings me to
> the last problem:
>
> GF(5)(3) + 2/3 or 2/3 + GF(5)(3), both result in errors. If we allow
> multiplication, then again there is an inconsistency with addition and
> subtraction.

no, this is OK. The thing is that the multiplication is the action of
Z_{(5)} on Z_{(5)}/5Z_{(5)}=GF(5), i.e. GF(5) is an Z_{(5)}-module.
That's all, there is no addition correctly defined for an element of a
ring R and an element of an R-module.

Dima

[Nils Bruin]

On Nov 21, 5:15 am, Dima Pasechnik <dimp...@gmail.com> wrote:
> hmm, I don't think this example will fly. If you happen to have a
> divisior of p in the denominator then you get a point with every
> nonzero coordinate divisible by p. So the reduction of it is
> (0:0..:0) -- oeps --- a runtime error sowieso...

Not quite... the thing is, over Q, (1:p) and (1/p:1) represent the
same projective point. If we were to use coercion to reduce such
points modulo p, then (1:p) would nicely map to (1:0) in P^1(GF(p)),
but (1/p:1) would lead to an error.

I'm pretty sure sage enforces the normalization or the points {(1:p),
(p:1)} to either {(1:p),(1:1/p)} or {(1/p:1),(p:1)}, so you would
always run into the problem somewhere.

The real solution is (as sage does): There is no immediate natural
reduction concept for varieties defined over Q. You should first
choose a suitable model over Z. There is real mathematical content in
Sage not having such a coercion by default. It's not *just*
inconvenience.
Taking the inconvenience saves you from rather surprising and hard to
predict behaviour later on. If you put the coercion in here and then
fix "reduction" higher up the chain, you'll just keep stacking kludge
upon kludge.

---

GF(7)(4)*2/3 vs 2/3*GF(7)(4)

They may look the same, but thanks to "/" on ZZ changing parents, they
are not:

(GF(7)(4)*2)/3 vs (2/3)*GF(7)(4)

One is a multiplication between QQ and GF(7); the other a division
between GF(7) and ZZ. By extending "/" on ZZ we've ruined
associativity! We should probably revert that then :-). We already
have "//" anyway. This example also shows how insidious a change in
behaviour for a basic operator can be. I definitely didn't think about
this one when "/" on ZZ was extended to produce elements in QQ.

That or we modify the python parses of expressions and let it do a
tree search to find which evaluation order produces an answer and
which one raises an error and go with the value... every time the
expression gets evaluated. But then we should probably rewrite sage in
Prolog to begin with.