Opened 8 years ago

Last modified 4 years ago

#15709 new defect

Powering with IntegerMod/GF exponents

Reported by: ppurka Owned by:
Priority: major Milestone: sage-6.4
Component: coercion Keywords:
Cc: mmezzarobba, jakobkroeker Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps: wrongAnswerMarker

Status badges

Description (last modified by jdemeyer)

From the google notebook bug reports

# I lost several hours because Sage silently converted a number defined mod n to an integer 
# when it appeared as an exponent.
# I was working in a different cyclotomic field, but the problem is right here in the complex numbers.
# I believe I should have to explicitly convert to an integer unless the answer only depends on the value mod n.
a=Mod(3,2)
print type(a),a,2*a,(i^2)^a,i^(2*a)

Output:
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'> 1 0 -1 1

This must surely have been discussed before. I would have tried to look up the discussion if I thought there was any hope that someone could convince me that this is not actually a bug.

Related, Nils Bruin reported on #11797:

sage: p=7
sage: k=GF(p)
sage: k(2)^k(p)
1
sage: (GF(7)(2))^(GF(5)(2))
4
sage: k(2)^p
2

It looks like it's simply quietly lifting the exponent to the integers, which it shouldn't do because there is no coercion in that direction (only a conversion):

sage: k.<a>=GF(p^2)
sage: k(2)^k(p)
1
sage: k(2)^k(a)
TypeError: not in prime subfield
sage: ZZ(k(1))
1
sage: ZZ(k(a))
TypeError: not in prime subfield

There is one side-effect of this that does look elegant:

sage: R=Integers(p-1)
sage: (k(2))^(R(p))
2

but in general I'd say an error should result from exponentiations like this.

Change History (13)

comment:1 follow-up: Changed 8 years ago by ppurka

Actually, I don't see what is the problem with the output. 2*a = 0 mod 2, so i^0 is 1. And i^2 = -1, so the outputs seem correct. Was the OP expecting an error from taking the power?

comment:2 in reply to: ↑ 1 Changed 8 years ago by nbruin

Replying to ppurka:

Actually, I don't see what is the problem with the output. 2*a = 0 mod 2, so i^0 is 1. And i^2 = -1, so the outputs seem correct. Was the OP expecting an error from taking the power?

I think his issue is with the last entry, i^(2*a)==1. I think he expected an error because the exponent is in Z/2Z and not in Z/4Z.

It would indeed be nicer if sage would refuse to let Z/nZ act on the right on rings by exponentiation. It's not well-defined, unless you're looking at an d-th root of unity, where d is a divisor of n.

comment:3 follow-up: Changed 8 years ago by ppurka

So, I suppose this should be fixed for complex numbers and some cyclotomic fields. Where the __pow__ method raises ValueError if the exponent does not belong to (ZZ, int, float, RR, RDF, CC, CDF) - can there be any other field in that tuple?

comment:4 in reply to: ↑ 3 Changed 8 years ago by nbruin

Replying to ppurka:

So, I suppose this should be fixed for complex numbers and some cyclotomic fields. Where the __pow__ method raises ValueError if the exponent does not belong to (ZZ, int, float, RR, RDF, CC, CDF) - can there be any other field in that tuple?

Is the code that specific? For a general ring, we'd probably want that the exponent is coercible into ZZ. For rings where fractional exponents are meaningful it would be QQ (but multivaluedness of the result is always an issue of course). For some analytic objects we can support even more general exponents. So in SR the issue probably remains, because one can wrap an element of ZZ/2ZZ in a symbolic expression.

What happens now is probably that the code asks whether the exponent can be *turned into* an integer (i.e., asks for a conversion). Of course there is a conversion from ZZ/2ZZ to ZZ.

comment:5 Changed 8 years ago by ppurka

Yes, the __pow__ method seems different between RR, CC, QQ, number fields -- and these are the ones I checked just now. I have no idea how to fix this method in general.

comment:6 Changed 8 years ago by mmezzarobba

  • Cc mmezzarobba added

comment:7 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:8 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:9 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:10 Changed 7 years ago by jdemeyer

  • Summary changed from silent conversion of mod to int to Powering with IntegerMod exponents

comment:11 Changed 7 years ago by jdemeyer

  • Description modified (diff)
  • Summary changed from Powering with IntegerMod exponents to Powering with IntegerMod/GF exponents

comment:12 Changed 5 years ago by jakobkroeker

  • Cc jakobkroeker added
  • Stopgaps set to wrongAnswerMarker

In addition I suggest to print for each result its parent (or related type) like Macaulay2 does:

i1 : QQ[x]
o1 = QQ[x]
o1 : PolynomialRing
i2 : x
o2 = x
o2 : QQ[x]
}}

comment:13 Changed 4 years ago by jdemeyer

I added a pointer from #24247 to here. Disallowing powering by IntegerMod elements is easy.

The hard part is allowing x ^ Mod(a, n) only where it makes sense. If we do that, ideally it should be done using generic code. Something like:

def pow_intmod(x, a, n):
    if x^n != 1:
        raise ArithmeticError("power not defined")
    return x^a

The problem is that checking x^n != 1 costs performance and that it might not work properly in non-exact rings.

Note: See TracTickets for help on using tickets.