Sage: Ticket #15709: Powering with IntegerMod/GF exponents
https://trac.sagemath.org/ticket/15709
<p>
From the <a class="ext-link" href="https://spreadsheets.google.com/pub?key=pCwvGVwSMxTzT6E2xNdo5fA"><span class="icon"></span>google notebook bug reports</a>
</p>
<pre class="wiki"># 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
</pre><p>
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.
</p>
<p>
Related, Nils Bruin reported on <a class="closed ticket" href="https://trac.sagemath.org/ticket/11797" title="defect: Finite field elements are allowed in exponents (closed: duplicate)">#11797</a>:
</p>
<pre class="wiki">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
</pre><p>
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):
</p>
<pre class="wiki">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
</pre><p>
There is one side-effect of this that does look elegant:
</p>
<pre class="wiki">sage: R=Integers(p-1)
sage: (k(2))^(R(p))
2
</pre><p>
but in general I'd say an error should result from exponentiations like this.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/15709
Trac 1.1.6ppurkaThu, 23 Jan 2014 03:57:26 GMT
https://trac.sagemath.org/ticket/15709#comment:1
https://trac.sagemath.org/ticket/15709#comment:1
<p>
Actually, I don't see what is the problem with the output. <code>2*a = 0 mod 2</code>, so <code>i^0</code> is 1. And <code>i^2 = -1</code>, so the outputs seem correct. Was the OP expecting an error from taking the power?
</p>
TicketnbruinThu, 23 Jan 2014 05:47:12 GMT
https://trac.sagemath.org/ticket/15709#comment:2
https://trac.sagemath.org/ticket/15709#comment:2
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15709#comment:1" title="Comment 1">ppurka</a>:
</p>
<blockquote class="citation">
<p>
Actually, I don't see what is the problem with the output. <code>2*a = 0 mod 2</code>, so <code>i^0</code> is 1. And <code>i^2 = -1</code>, so the outputs seem correct. Was the OP expecting an error from taking the power?
</p>
</blockquote>
<p>
I think his issue is with the last entry, <code>i^(2*a)==1</code>. I think he expected an error because the exponent is in <code>Z/2Z</code> and not in <code>Z/4Z</code>.
</p>
<p>
It would indeed be nicer if sage would refuse to let <code>Z/nZ</code> act on the right on rings by exponentiation. It's not well-defined, unless you're looking at an <code>d</code>-th root of unity, where <code>d</code> is a divisor of <code>n</code>.
</p>
TicketppurkaThu, 23 Jan 2014 15:22:11 GMT
https://trac.sagemath.org/ticket/15709#comment:3
https://trac.sagemath.org/ticket/15709#comment:3
<p>
So, I suppose this should be fixed for complex numbers and some cyclotomic fields. Where the <code>__pow__</code> method raises <code>ValueError</code> if the exponent does not belong to <code>(ZZ, int, float, RR, RDF, CC, CDF)</code> - can there be any other field in that tuple?
</p>
TicketnbruinThu, 23 Jan 2014 16:36:12 GMT
https://trac.sagemath.org/ticket/15709#comment:4
https://trac.sagemath.org/ticket/15709#comment:4
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/15709#comment:3" title="Comment 3">ppurka</a>:
</p>
<blockquote class="citation">
<p>
So, I suppose this should be fixed for complex numbers and some cyclotomic fields. Where the <code>__pow__</code> method raises <code>ValueError</code> if the exponent does not belong to <code>(ZZ, int, float, RR, RDF, CC, CDF)</code> - can there be any other field in that tuple?
</p>
</blockquote>
<p>
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.
</p>
<p>
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.
</p>
TicketppurkaThu, 23 Jan 2014 16:48:07 GMT
https://trac.sagemath.org/ticket/15709#comment:5
https://trac.sagemath.org/ticket/15709#comment:5
<p>
Yes, the <code>__pow__</code> 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.
</p>
TicketmmezzarobbaSun, 26 Jan 2014 11:44:56 GMTcc set
https://trac.sagemath.org/ticket/15709#comment:6
https://trac.sagemath.org/ticket/15709#comment:6
<ul>
<li><strong>cc</strong>
<em>mmezzarobba</em> added
</li>
</ul>
Ticketvbraun_spamThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/15709#comment:7
https://trac.sagemath.org/ticket/15709#comment:7
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
Ticketvbraun_spamTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/15709#comment:8
https://trac.sagemath.org/ticket/15709#comment:8
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
Ticketvbraun_spamSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/15709#comment:9
https://trac.sagemath.org/ticket/15709#comment:9
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketjdemeyerThu, 04 Sep 2014 15:30:29 GMTsummary changed
https://trac.sagemath.org/ticket/15709#comment:10
https://trac.sagemath.org/ticket/15709#comment:10
<ul>
<li><strong>summary</strong>
changed from <em>silent conversion of mod to int</em> to <em>Powering with IntegerMod exponents</em>
</li>
</ul>
TicketjdemeyerWed, 10 Sep 2014 11:51:24 GMTdescription, summary changed
https://trac.sagemath.org/ticket/15709#comment:11
https://trac.sagemath.org/ticket/15709#comment:11
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/15709?action=diff&version=11">diff</a>)
</li>
<li><strong>summary</strong>
changed from <em>Powering with IntegerMod exponents</em> to <em>Powering with IntegerMod/GF exponents</em>
</li>
</ul>
TicketjakobkroekerFri, 03 Mar 2017 23:10:26 GMTcc changed; stopgaps set
https://trac.sagemath.org/ticket/15709#comment:12
https://trac.sagemath.org/ticket/15709#comment:12
<ul>
<li><strong>cc</strong>
<em>jakobkroeker</em> added
</li>
<li><strong>stopgaps</strong>
set to <em>wrongAnswerMarker</em>
</li>
</ul>
<p>
In addition I suggest to print for each result its parent (or related type) like Macaulay2 does:
</p>
<pre class="wiki">i1 : QQ[x]
o1 = QQ[x]
o1 : PolynomialRing
i2 : x
o2 = x
o2 : QQ[x]
}}
</pre>
TicketjdemeyerMon, 08 Jan 2018 14:54:47 GMT
https://trac.sagemath.org/ticket/15709#comment:13
https://trac.sagemath.org/ticket/15709#comment:13
<p>
I added a pointer from <a class="closed ticket" href="https://trac.sagemath.org/ticket/24247" title="enhancement: Implement __pow__ in the coercion model (closed: fixed)">#24247</a> to here. Disallowing powering by <code>IntegerMod</code> elements is easy.
</p>
<p>
The hard part is allowing <code>x ^ Mod(a, n)</code> only where it makes sense. If we do that, ideally it should be done using generic code. Something like:
</p>
<pre class="wiki">def pow_intmod(x, a, n):
if x^n != 1:
raise ArithmeticError("power not defined")
return x^a
</pre><p>
The problem is that checking <code>x^n != 1</code> costs performance and that it might not work properly in non-exact rings.
</p>
Ticket