Wishlist: SCA TODOs

[Oleksandr]

Thanks to Simon, here are some non-commutative requests due to from ​http://groups.google.com/group/sage-devel/browse_thread/thread/497bfc40ea5f17b8?pli=1

From ​http://groups.google.com/group/sage-devel/msg/1b183a717dbd0437

I need graded commutative rings, which can be easily constructed,
provided that one has
 * Singular's "SuperCommutative" rings
 * additional degree vectors (resp. matrix orderings where the first
matrix row is interpreted as degree vector).

SuperCommutative provides precisely one block of variables that
pairwise anticommute. However, it would be even nicer to have rings
with several anticommuting blocks.
I could imagine to create it (with additional degree vector) like
that:
   sage: R.<a,b,c,d,e,f> = PolynomialRing(QQ, nc_blocks=[[0,1],[3,5]],
degrees=[1,1,2,3,3,3])

Then, R should be a graded commutative ring: two generators in degrees
1, one in degree 2, and three in degree 3, and the nc_blocks determine
that variables a,b,d,e,f are pairwise anti-commuting.

If only one anticommutative block is possible, then it could be:
  sage: R.<c,a,b,d,e,f> = PolynomialRing(QQ, nc_block=[1,5], degrees=
[2,1,1,3,3,3]) 

AFAIK: more than one block of odd variables can be avoided by reordering the variables and changing the ordering accordingly. It makes sense to allow more than one block of odd variables, e.g. due to more complicated resulting ordering...

Simon, is there something else to it? How would your ordering look like without the reordering?

From ​http://groups.google.com/group/sage-devel/msg/99e803cb4a127bc8

AFAIK, the Singular kernel has a marker for functions that are only
available in the commutative case. I think it would be nice to
distinguish not two but three cases: commutative, supercommutative,
and general G-algebras. 

This suggestion comes from the observation that many algorithms for 
commutative rings work in the supercommutative (or graded commutative) 
setting as well, but Singular refuses them since they would not work 
for general G-algebras. Therefore, in my applications I had in some 
cases to work around and implement these algorithms as library 
functions.

* Kernel/preimage of maps 
 * Hilbert polynomial/function: This certainly makes sense for 
(weighted) homogeneous ideals in graded commutative rings. 
 * AFAIK dim (Krull dimension) makes sense in the graded commutative 
case as well.
* Hilbert driven standard basis computation

Simon, could you please provide us with some more input? It would be nice to have tests with known correct results and to make your workarounds check the correctness automatically. Moreover, references to corresponding definitions in literature are much appreciated.

From ​http://groups.google.com/group/sage-devel/msg/1b8f6205ba9ebab8

After all, testing for complicated conditions
under which a function works costs time. So, why not have a very
simple test (commutative vs. non-commutative) that is immediate?

Therefore my suggestion to have markers, say ALLOW_G_ALGEBRA,
ALLOW_SC_ALGEBRA, NO_PLURAL. 

ps: my comments on this suggestion are in the original thread.

Hans, what do you think?

[levandov]

1. ALLOW THINGS VERSUS CONTEXTS

Hmmm... A long time ago there was a discussion about context-dependent functionality of a given function. In the future we'll need more flags for more noncommutative subsystems (Letterplace, Locapal are on the way). ALLOW list is definitely a solution, but having many of them is not easy to maintain.

Context-dependent choice might be described as follows. Given an object( say, of type matrix) over a ring, one determines the subset of the set of variables, which occur there and (in the noncommutative case) its SAGBI basis, what means plainly you complete these set to the set, which is multiplicatively closed.
Example: given the relation yx=xy+z, then {x,y} needs to be completed to {x,y,z} (note that this is NOT the case for graded commutative algebras). In many cases, however, one gets smaller subalgebras. Then a procedure will analyze the type of this context subalgebra (it's done internally) and make its decision. I like the idea of being able to factorize a univariate polynomial while sitting in any ring.

2. Recipe for Krull dimension in graded commutative case

In the noncommutative case one uses actually Gelfand-Kirillov dimension, since Krull is generalized to two-sided ideals only and it's called Krull-Rentschler-Gabriel dimension (which is scary in general). I believe that they might very well coinside on graded comm algebras (as they do in the commutative case with the only difference: GK dimension of a field containing Q is the transcendence degree of the field while Krull dimension is just zero). In the implementation in gkdim.lib, however, one does not add the dimension of the field to the result, so they are equal.)

On the contrary, Gelfand-Kirillov dimension is nice-behaving and it is already implemented in a library and someday will become a kernel procedure.

Recipe: Take your ideal I (assume it's in Groebner basis) in a graded comm algebra C. Go to the G-algebra G, such that C is isomorphic to G/T, add two ideals I and T ( =: J), set the "isSB" attribute of J to 1 (in order to avoid GB computation in the next procedure) and compute gkdim().

3. Preimage

There's PLURAL kernel command preimage, which has some limitations. More general way is of course possible (see my diss) but requires in general a lot of stuff - that's why it's not implemented on the full scale. Send me (or post here or somewhere and give me a link) the example of possible morphisms. I think for the graded comm case you'll be in the easiest case, where no severe restrictions of the general case apply. So this might be quite doable.

Best luck, Viktor

[Simon King]

Dear Viktor,

first of all, my apologies for answering so late. When you posted, I was busy with different things, and later I forgot to reply.

Replying to levandov:

1. ALLOW THINGS VERSUS CONTEXTS

Hmmm... A long time ago there was a discussion about context-dependent functionality of a given function.

Testing whether some operation is allowed in a certain context should of course be a fast decision.

ALLOW list is definitely a solution, but having many of them is not easy to maintain.

But at least in the graded commutative case, ALLOW can already be updated when the ring is created. So, for all subsequent operations, the decision will be fast.

Example: given the relation yx=xy+z, then {x,y} needs to be completed to {x,y,z} (note that this is NOT the case for graded commutative algebras). In many cases, however, one gets smaller subalgebras. Then a procedure will analyze the type of this context subalgebra (it's done internally) and make its decision. I like the idea of being able to factorize a univariate polynomial while sitting in any ring.

I wonder how general the approach should be.

My question: Is the data type in Singular for a general G-Algebra different from the data type for a SuperCommutative? ring? I guess so, since IIRC basic arithmetic for SuperCommutative? rings is much faster than for general G-Algebras.

If this is the case, then why not implement the features for that data type only? The test whether some operation is allowed will then usually boil down to the question whether an ideal is (weighted) homogeneous.

2. Recipe for Krull dimension in graded commutative case

... In the implementation in gkdim.lib, however, one does not add the dimension of the field to the result, so they are equal.)

gkdim.lib? I didn't know that library, so, I will look in the manual. Thank you!

3. Preimage

There's PLURAL kernel command preimage, which has some limitations.

Really? preimage is throwing an error when using it on graded commutative (quotient) rings.

Send me (or post here or somewhere and give me a link) the example of possible morphisms. I think for the graded comm case you'll be in the easiest case, where no severe restrictions of the general case apply. So this might be quite doable.

I have put some examples in folders ​here.

Remarks:

• The folder 'Exp_n_' contains data that occur when computing persistent group cohomology associated with the upper central series (​Theoretical Background) of SmallGroup? number 'n' of order 81, provided that the upper central series is interesting.

• Each file in such subfolder defines two graded-commutative quotient rings Q1 and Q2, with matrix ordering, and a map phi between them. I need the kernel of phi.

• If I am not mistaken (at least this is what I do in my custom implementation), the usual procedure works in this setting: Let phi:Q1->Q2 be a homomorphism of graded commutative algebras. We consider R=Q2+Q1 (i.e., elimination order, and of course one has to change variable names, should there be a name conflict), and compute a Groebner basis G of the ideal <{phi(x)-x: x generators of Q1}>. The kernel can be read off G (it is given by the elements of G that do not contain generators of Q2).

• And if I am not mistaken again, the same Groebner basis G can also be used to compute one element of the pre-image under phi for any element of Q2.

Kind regards, Simon

[Oleksandr]

Dear Simon,

Thanks for your answer. Please let me add my 0.05 euro.

Replying to SimonKing:

My question: Is the data type in Singular for a general G-Algebra different from the data type for a SuperCommutative? ring? I guess so, since IIRC basic arithmetic for SuperCommutative? rings is much faster than for general G-Algebras.

Thanks, my pleasure. But no. Singular has a single data type for all the polynomials and vectors. It's just my basic arithmetic implementation which makes the difference.

gkdim.lib? I didn't know that library, so, I will look in the manual. Thank you!

AFAIK, gkdim.lib will probably be deprecated since dim(std(I)) should work in a more or less current Singular.

Really? preimage is throwing an error when using it on graded commutative (quotient) rings.

Really? I must have missed your bug report about that... :( Oh... do you mean "Sorry, not yet implemented for noncomm. rings" message?

I have put some examples in folders ​here.

Thanks.

Regards,

Oleksandr

[Oleksandr]

Simon's workaround for "kernel" in general NC-setting.

[Simon King]

Dear Oleksandr,

Replying to motsak: [...]

Really? preimage is throwing an error when using it on graded commutative (quotient) rings.

Really? I must have missed your bug report about that... :( Oh... do you mean "Sorry, not yet implemented for noncomm. rings" message?

Yes!

I see that you uploaded my workaround; I wasn't aware that I had sent it to you. Hopefully the code is correct...

Cheers, Simon