Opened 3 years ago

Closed 3 years ago

#21723 closed defect (fixed)

Inconsistency in the interface between fields and vector spaces

Reported by: klee Owned by:
Priority: minor Milestone: sage-7.5
Component: finite rings Keywords:
Cc: Merged in:
Authors: Vincent Delecroix, Kwankyu Lee Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: c1748cf (Commits) Commit: c1748cfb2971237d3bd8c6e49197479f500e9317
Dependencies: Stopgaps:

Description (last modified by klee)

There is an inconsistency in the interface between fields and vector spaces.

sage: F.<a>=GF(9)
sage: V=F.vector_space()
sage: V(a)
(0, 1)
sage: G.<b>=GF(3)
sage: W=G.vector_space()
sage: W(b)
...
TypeError: can't initialize vector from nonzero non-list

The cause is

sage: a._vector_()
(0, 1)
sage: b._vector_()
...
AttributeError: 'sage.rings.finite_rings.integer_mod.IntegerMod_int' object has no attribute '_vector_'

Adding a _vector_ method to the GF(p) elements will be a simple fix.

Along the way, we also clean up _vector_ and _matrix_ methods in the class FinitePolyExtElement.

Attachments (2)

trac21723_klee.patch (1.8 KB) - added by klee 3 years ago.
Alternative light-footed patch
trac21723_matrix_.patch (2.8 KB) - added by klee 3 years ago.
Fix a bug in reversed _matrix_

Download all attachments as: .zip

Change History (36)

comment:1 Changed 3 years ago by vdelecroix

Note that the following also works

sage: K = GF(9)
sage: V = VectorSpace(K, 1)
sage: V(K.an_element())
(0)

Hence I guess that a default _vector_ at the category level would actually make sense.

comment:2 Changed 3 years ago by vdelecroix

  • Authors set to Vincent Delecroi
  • Branch set to u/vdelecroix/21723
  • Commit set to d2b48ad53dcb0c730a17be08a52c88047baa3a87

three lines fix... let us see how much it breaks Sage.


New commits:

d2b48ad21723: make a default _vector_ for ring elements

comment:3 Changed 3 years ago by git

  • Commit changed from d2b48ad53dcb0c730a17be08a52c88047baa3a87 to 520b20f811427452742c9c1d46acb28ae932c9f0

Branch pushed to git repo; I updated commit sha1. New commits:

520b20f21723: more appropriate doctest

comment:4 Changed 3 years ago by klee

Two comments:

(1) For elements of many other parents, the code is k.vector_space()(lst) where k is the parent. Hence for further consistency, we may consider add vector_space parent method as well. But then Rings category is not the right one...

(2) The docstring does not have an initial one-line summary.

comment:5 Changed 3 years ago by klee

I fear that using the category framework right might be complicated in reality, contrary to the theory.

An alternative (old-fashioned :-) path is to add element_prime_modn.py, in which we subclass IntegerMod for modulo p case and add _vector_ method therein. I think this fits in the current organization of finite fields machinery. We may also need to add vector_space method to FiniteField_prime_modn class..

comment:6 Changed 3 years ago by git

  • Commit changed from 520b20f811427452742c9c1d46acb28ae932c9f0 to 52a283023818054591c5f87b770ab330d136d88e

Branch pushed to git repo; I updated commit sha1. New commits:

52a283021723: add a vector_space methods to fields

comment:7 follow-up: Changed 3 years ago by vdelecroix

The _vector_ method for elements has no link to the vector_space method for parents.

I fear that using the category framework right might be complicated in reality, contrary to the theory.

This is not an argument. Moreover using category allows to have these methods available for any rings or fields.

comment:8 Changed 3 years ago by vdelecroix

  • Authors changed from Vincent Delecroi to Vincent Delecroix
  • Status changed from new to needs_review

comment:9 in reply to: ↑ 7 Changed 3 years ago by klee

Replying to vdelecroix:

This is not an argument. Moreover using category allows to have these methods available for any rings or fields.

_vector_ is anyhow related with some vector space, the precise meaning of which would depend on the kind of rings. For GF(9), it is a 2-dimensional vector space over GF(3) while for GF(3), it is a vector space over itself. You implemented _vector_ assuming that the parent ring is seen as a vector space over itself, disregarding the kind of of the ring. As a principle, methods in a category should be meaningful and useful for all parents in the category. So I think the Rings category is not the right category to put your _vector_ implementation. On the other hand, it seems tricky to find the right category in the current Sage. [I expected finite fields belong to a finite-dimensional algebras category. But not true.]

comment:10 Changed 3 years ago by vdelecroix

The part that was missing in the current implementation is the basic construction ring -> one dimensional vector space over this ring. This construction makes sense for any ring and hence makes sense in Sage category framework.

You are right that for *some* specific ring, there might be other natural vector spaces. In this case it is possible to add more specialized implementations. And this is exactly what is being done for finite fields.

comment:11 Changed 3 years ago by vdelecroix

And something more general that could be done is to see GF(2^4) as a vector space over GF(2^2). But the current interface does not allow it.

comment:12 Changed 3 years ago by git

  • Commit changed from 52a283023818054591c5f87b770ab330d136d88e to bc95cacd4a8140a12e729286a21d8e85fdf50a68

Branch pushed to git repo; I updated commit sha1. New commits:

bc95cac21723: simplify _vector_ and _matrix_ of finite field elements

comment:13 Changed 3 years ago by klee

(1) You added vector_space method to the fields category. How can this be useful at all? You can always construct the vector spaces directly by QQ*n.

(2) About _matrix_ method: Its docstring says "Return the matrix of right multiplication by the element on the power basis 1, x, x^2, \ldots, x^{d-1} for the field extension. Thus the \emph{rows} of this matrix give the images of each of the x^i." So we have

sage: b=a^10
sage: v=b._vector_()
sage: m=a._matrix_()
sage: w=(a*b)._vector_()
sage: m*v == w
True

Shouldn't this be called the "matrix of left multiplication by the element a"? And the columns of this matrix give the images of x^i?

(3) The reverse argument for _matrix_ method corresponds to reverseed _vector_. Therefore I expect m*v == w still holds with reversed versions. But

sage: v=b._vector_(reverse=True)
sage: m=a._matrix_(reverse=True)
sage: w=(a*b)._vector_(reverse=True)
sage: m*v == w
False
sage: m*v
(1, 1, 1, 1)
sage: w
(1, 1, 1, 0)
sage: 

I think this is a bug. Why does transposing the matrix gives what we want? The correct way would be reversing all columns and all rows.

By the way, you changed the docstring for reverse argument. But the original one makes more sense.

comment:14 follow-up: Changed 3 years ago by klee

Prime finite fields already have vector_space method.

sage: F=GF(3)
sage: V=F.vector_space()
sage: V([F.gen()])
(1)

So the bug dealt with the present ticket is just in the prime finite field. I still think that touching the Rings category is not the right way.

comment:15 in reply to: ↑ 14 ; follow-up: Changed 3 years ago by vdelecroix

Replying to klee:

So the bug dealt with the present ticket is just in the prime finite field. I still think that touching the Rings category is not the right way.

Why?

comment:16 in reply to: ↑ 15 Changed 3 years ago by klee

Replying to vdelecroix:

Replying to klee:

So the bug dealt with the present ticket is just in the prime finite field. I still think that touching the Rings category is not the right way.

Why?

Before:

sage: K.<a>=QQ.extension(x^2-2)
sage: K.vector_space()

(Vector space of dimension 2 over Rational Field, Isomorphism map:
   From: Vector space of dimension 2 over Rational Field
   To:   Number Field in a with defining polynomial x^2 - 2, Isomorphism map:
   From: Number Field in a with defining polynomial x^2 - 2
   To:   Vector space of dimension 2 over Rational Field)
sage: a.vector()
(0, 1)
sage: vector(a)
(0, 1)

After your patch:

sage: a.vector()
(0, 1)
sage: vector(a)
(a)

So .vector() and ._vector_() should be context-sensitive.

comment:17 Changed 3 years ago by tscrim

The ._vector_() in that case should be an alias of .vector(). What the vector(a) is doing is calling list(a) and then interpreting that as a vector. I'm +1 for putting something generic in Rings since it helps realize that any ring is a 1-dim free module over itself. Although we should put some specification in the docstring; something along the lines of "Return self as a vector in some natural module."

comment:18 Changed 3 years ago by vdelecroix

But as Kwankyu mentioned it is not what we want for field extensions. We should found a consistent way of doing the identification ring = one-dimensional free module but without overlap with the existing field extension business.

comment:19 Changed 3 years ago by tscrim

It's a similar problem to what we have with gens being ambiguous, but for gens, we could get out of it by being more explicit about what type of generators. For _vector_, we don't have the option of specializing the name of the method, but we can be very careful with the specs. In particular, by saying "some natural module," we give the option for subclasses to specify what that natural module is, which could change. So in the generic case, it is the 1-dim module over itself, but for field extensions, the natural module is the one over the base field.

Changed 3 years ago by klee

Alternative light-footed patch

comment:20 Changed 3 years ago by klee

Adding _vector_ to a category level would incur much work to make existing parents conform to the new organization. It may be possible and in the long run is a way to go. But in this particular case, I think that the gain is small compared to the needed efforts.

I uploaded an alternative simple way to fix the bug. This just does a small thing to squeeze the bug. If you agree, then you may merge it with your other changes.

comment:21 Changed 3 years ago by vdelecroix

I agree that your patch might fix the symptom. As discussed with Travis, the real problem is that _vector_ and vector do not have a fixed semantic. I am in favor of including your patch in this ticket alone and try to fix the _vector_/vector issue in some other tickets. Travis?

comment:22 Changed 3 years ago by vdelecroix

comment:23 Changed 3 years ago by klee

I like the changes you made to _vector_ and _matrix_ methods in element_base.pyx modulo my comments above. If you are ok, I may take it to fix the bug in _matrix_ method that I mentioned above. Anyway, do you agree with my comments on the _matrix_ method?

Changed 3 years ago by klee

Fix a bug in reversed _matrix_

comment:24 Changed 3 years ago by tscrim

I'm good with moving the general problem to another ticket and fixing the symptom here. Kwankyu, could you upload your fix as a new branch?

comment:25 Changed 3 years ago by klee

  • Branch changed from u/vdelecroix/21723 to public/21723
  • Commit bc95cacd4a8140a12e729286a21d8e85fdf50a68 deleted

comment:26 Changed 3 years ago by git

  • Commit set to aa1ff7b2a9278674834d424d555aad89801bc62b

Branch pushed to git repo; I updated commit sha1. New commits:

4b17ccdAdd _vector_ method to IntegerMod elements
aa1ff7bFix a bug in reversed _matrix_

comment:27 Changed 3 years ago by klee

  • Authors changed from Vincent Delecroix to Vincent Delecroix, Kwankyu Lee

comment:28 Changed 3 years ago by klee

  • Description modified (diff)

comment:29 Changed 3 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

One little thing: Example:: -> EXAMPLES:: and then I'm happy setting a positive review.

comment:30 Changed 3 years ago by git

  • Commit changed from aa1ff7b2a9278674834d424d555aad89801bc62b to 0b0935c4db214f7fa53c595d9df8c3eb4f1bf32d

Branch pushed to git repo; I updated commit sha1. New commits:

0b0935cRefined docstrings

comment:31 Changed 3 years ago by git

  • Commit changed from 0b0935c4db214f7fa53c595d9df8c3eb4f1bf32d to c1748cfb2971237d3bd8c6e49197479f500e9317

Branch pushed to git repo; I updated commit sha1. New commits:

c1748cfCorrected minor typos in docstrings

comment:32 Changed 3 years ago by klee

Travis?

comment:33 Changed 3 years ago by tscrim

  • Status changed from needs_review to positive_review

Thanks.

comment:34 Changed 3 years ago by vbraun

  • Branch changed from public/21723 to c1748cfb2971237d3bd8c6e49197479f500e9317
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.