CoCoA » CoCoALib

This change does mean that the following could give false:

/**/ L := [.. some ringelems...];
/**/ I := ideal(L);
/**/ gens(I) = L;       // might give false
/**/ EqSet(gens(I), L); // might give false

Would we even want to allow some further "cleaning" of the generators?
For example, we could suppress duplicates.
Maybe even ideal(x, -x) could have generators just [x]?

Anna has some doubts.
So far we had the simple rule that L = gens(ideal(L)).

Also the fn SyzOfGens is defined to be the same as syz(gens(I)).
JAA thinks that SyzOfGens is semantically "a bit dodgy" (because the gens are not uniquely defined, and are often viewed as a set (so order not uniquely defined)).

Certainly the idea to remove zeroes (and possibly make other changes to the list of gens) is not backward compatible.
Would this really cause trouble? Anna is concerned that it might (and how could we check that it won't even in the CoCoA-5 packages?).

I have just spoken to Florian about this issue.
His initial reaction was that he wanted gens(ideal(L)) to be an identity operation,
but after saying that we are planning to introduce a syz function (to avoid having
to do SyzOfGens(ideal(L))), he then seemed to think it was no longer so important.

He also made a suggestion that there could be a separate "cleaning" function which
one would call explicitly: e.g. ideal(CleanGens(L)).

Another suggestion from Florian would be to interreduce the given gens, and then take
that as the "definitive gens" -- JAA is concerned that this may make the gens "bigger"
(i.e. greater sum of NumTerms).

I like the "separate concept" of "generator cleaning", and it would be nice to make it available as a function.
I am less convinced that the user should be obliged to write ideal(CleanGens(L)) rather than just ideal(L):
i.e. I am still in favour of ideal(L) calling CleanGens automatically.

We could also have two ways of creating ideals: e.g. ideal(L) and ideal_DoNotCleanGens(L)
[of course the name is more-or-less a "joke"]

John Abbott wrote:

We could also have two ways of creating ideals: e.g. ideal(L) and ideal_DoNotCleanGens(L)

Maybe ideal_KeepGens? I like that!
for the rare case in which one really wants the 0's, it would still be possible.
That, of course, does not save us the work of tracking 0's in the generators.

After brief consideration, I have decided to keep in this issue discussion related to what "cleaning generators" might mean (even though I also think that it could reasonably be made explicitly callable as a separate function... or does it suffice to do gens(ideal(L)) if you want a "cleaned" version of L?)

1. cleaning removes all zeroes
2. cleaning removes duplicates
3. cleaning returns just a subset (incl. maybe an empty list?? -- loses ring info!!)
4. cleaning can rescale polynomials by invertible factors (think also of ZZ[x,y,z])
5. cleaning may perform some steps of interreduction (e.g. by monomials and binomials)
6. cleaning should not make the list significantly longer than the original input
7. cleaning could also perform gcd of univariate polynomials

1. [0]
2. [x+1, x+1]
3. [x, -x]
4. [x, 2*x]
5. [x^99, x-2] interreduction would give [2^99, x-2] or [1] over a field
6. [x*y, 2*x*y*z]

• implement a new function (probably in CoCoA-5 since it is a prototype) with some/most/all of the features in comment 9 above;
• experiment with this new function (incl. varying what operations "cleaning" may perform)
• assemble a test suite of inputs (incl. also examples where some operation proves to prove "undesirable" output)
• when we are reasonably happy then we can implement in C++

We should also consider what "cleaning" may mean for other ideals in other rings:
e.g. ZZ and k[x] are both PIDs, so it may be reasonable just compute the single generator?

Following KISS strategy, I would avoid (possibly) costly operations: e.g. interreduction, duplicates (think of a monomial ideal with 1000 generators).
But even linear, like monic

I would do just these:
1 - remove 0
2 - if it contains a constant, make it ideal(1)

Anna: recover ideas, read it all, decide, implement, and close!

• remove zeroes
• collect all monomial gens, compute GBasis -- this is beginning of "cleaner gens"
• collect binomial gens: reduce them mod "cleaner gens" (so still binomial or monomial or zero); adjoin reduced versions to "cleaner gens"; probably best to work in order of incr degree
• all remaining gens: reduce mod "cleaner gens": if reduced version is monomial then adjoin to "cleaner gens" & recompute monomial RGB; if reduced is binomial, maybe use it to reduce binomials in "cleaner gens" then adjoin it; o/w just adjoin the reduced version to "cleaner gens"
• need to something clever about scalar factors (e.g. make monic over a field)

I think this heuristic should be reasonably fast while also detecting most "obvious simplifications". NB it is better not to compute RGB of monomials as that can be large (I believe).

Which ideal operations could benefit from CleanGens?
Sum, product, maybe colon. Radical?

It might make sense to compute some RGB elements with a low time-out; not sure how to organize this though.

Here is an example where the resulting gens could clearly be cleaned up:

/**/ I  := ideal(x-y-z, y^4*z^2+2*y^3*z^3+y^2*z^4);
/**/ saturate(I, ideal(x*y*z));
ideal(x -y -z,  1)

Should we also have that ideal(zero(R)) has empty list of generators?
I think so.
And that would be handy, if we do not add ideal(R) with that meaning (see #1763; in CoCoA-5 we have ideal(R,[]), where the empty list is more readable than in C++)

Modified

SparsePolyRingBase::IdealImpl::IdealImpl(P, gens)

John Abbott wrote:

Here is an example where the resulting gens could clearly be cleaned up:
[...]

This is still open: I need to similarly fix the sum I + J (added test to exbugs)

I remind you of the function IsConstant which should be helpful in this case (if IsField(CoeffRing)).

John Abbott wrote:

After brief consideration, I have decided to keep in this issue discussion related to what "cleaning generators" might mean (even though I also think that it could reasonably be made explicitly callable as a separate function... or does it suffice to do gens(ideal(L)) if you want a "cleaned" version of L?)

Some potential properties to consider:

1. cleaning removes all zeroes
2. cleaning removes duplicates
3. cleaning returns just a subset (incl. maybe an empty list?? -- loses ring info!!)
4. cleaning can rescale polynomials by invertible factors (think also of ZZ[x,y,z])
5. cleaning may perform some steps of interreduction (e.g. by monomials and binomials)
6. cleaning should not make the list significantly longer than the original input
7. cleaning could also perform gcd of univariate polynomials

Here are some simple test cases to consider:

1. [0]
2. [x+1, x+1]
3. [x, -x]
4. [x, 2*x]
5. [x^99, x-2] interreduction would give [2^99, x-2] or [1] over a field
6. [x*y, 2*x*y*z]

Add a function CleanupGens making some more easy checks?

List in #1647-9

Anna Maria Bigatti wrote:

Add a function CleanupGens making some more easy checks?

Moved into dedicated issue #1797

Sum is clever -- if HasGBasis(I) and is ideal(1)
Do it also for product.

use QQ[x,y,z];
I := ideal(x, x-1); GBasis(I); 
ideal(y) + I;
ideal(y) * I;