CoCoA » CoCoA-5

By John Abbott:
Does this code correctly compute the "universal denominator" for the ideal I?

use P::=QQ[x,y,z];
I := ideal(x^4-3*y^2*z+x*y*z-2, y^2-2*z+5, z^2-2*x+7*y);
println "IsZeroDim: ", IsZeroDim(I);
GF := GroebnerFanIdeals(I);
J := [ReducedGBasis(I) | I in GF];

define DEN(L)
  if type(L) = RINGELEM then
    return lcm([AsINT(den(c)) | c in coefficients(L)]);
  endif;
  return lcm([DEN(f) | f in L]);
enddefine; -- DEN

DENJ := [DEN(RGB) | RGB in J];

N := lcm(DENJ);
FloatStr(N);
facs := SmoothFactor(N,10000000);
println "RemainingFactor = ", FloatStr(facs.RemainingFactor);
IsProbPrime(facs.RemainingFactor); --> false

println "Known bad primes: ", facs.factors;

If the code is correct then the "universal denominator" is very large -- I have already made some attempt to make it smaller (the first ideal I tried, not much more complicated than this one, gave a "universal denominator" with almost 7000 digits!)

By John Abbott:

Robbiano suggested that it could be interesting to find the first (or at least a smallish) good prime.

An interim solution could be to use SmoothFactor: call it first with a limit of (say) 100, and if no good primes are found, double the limit and call SmoothFactor again. Asymptotically this is not so efficient, but it seems unlikely that one will often encounter such highly factorizable numbers that several iterations of the loop will be needed.

I have implemented SmallestNonDivisor (see #979).

I'm still hoping to find a better name than UniversalDenominator; I feel that it ought to contain "Groebner" somewhere, but then the name becomes even longer :-/

John Abbott wrote:

I'm still hoping to find a better name than UniversalDenominator; I feel that it ought to contain "Groebner" somewhere, but then the name becomes even longer :-/

UniversalRGBDenominator?

The name UniversalRGBDenominator is OK for me.

I note that there are already two "denominator" functions: den and CommonDenom.
So we have not been consistent about use of an abbreviated form :-/

Also using the abbreviation RGB to mean "reduced Groebner basis" is inconsistent with ReducedGBasis.
We could offer RGBasis but that is definitely less clear than ReducedGBasis.

How about UniversalRGBDenom?

John Abbott wrote:

The name UniversalRGBDenominator is OK for me.

I note that there are already two "denominator" functions: den and CommonDenom.
So we have not been consistent about use of an abbreviated form :-/

That's not too bad: the first is a single word.

Also using the abbreviation RGB to mean "reduced Groebner basis" is inconsistent with ReducedGBasis.
We could offer RGBasis but that is definitely less clear than ReducedGBasis.

Now ReducedGBasis (I'm about to check in) is identical to GBasis.
(I just needed to make it monic). This is handy, but I'm not 100% sure we don't risk badly in some examples (obviously there are trivial pathological example, but in general?)

How about UniversalRGBDenom?

perfect!

I wonder how "universal" UniversalRGBDenom is? Does it also apply to all Janet Bases? And Pommaret Basis (if it exists)?
Border bases may be different; though perhaps they are covered if they contain a G-basis?

I now think that the "universal" denominator is valid for any monic basis which contains a RGB as subset (since the other elements of the basis are of the form LPP - NF, and we know that the coeffs of the LPP are in ZZ_\Delta).

I presume it is not true in general for border bases, since there are ideals having border bases which do not contain a RGB as subset. Nevertheless there are only finitely many distinct border bases (assuming we require the set of PPs outside the span of the LPPs of the basis elements to be factor-closed or connected to 1), so we could also define a "universal denominator" for border bases -- this will be a (possibly trivial) multiple of the universal RGB denominator.

Should UniversalDenominator return INT or RingElem?
We should also choose its name: UniversalDen?

Currently UniversalRGBDenom returns a RingElem, used to be INT.
Related functions: CommonDenom, DEN

JAA prefers INT to RINGELEM (at least for the moment).

If the coeff ring is not QQ but is FracField then I'm not sure how sensible it is to make a GFan.
Shouldn't it be a Comprehensive GFan? Or something similar?

Anyway INT is more convenient for further operations (at least on the examples we have tried so far).

John Abbott wrote:

JAA prefers INT to RINGELEM (at least for the moment).

OK, I'll change it back.

If the coeff ring is not QQ but is FracField then I'm not sure how sensible it is to make a GFan.
Shouldn't it be a Comprehensive GFan? Or something similar?

Not really, that's another setting.

Anyway INT is more convenient for further operations (at least on the examples we have tried so far).

That's true (that's why I realized I made the change ;-)

I wonder whether it might be nice to have a function which returns a "partly factorized" universal denom. I used the partly factorized form when trying to understand the prime factors of the UD of the large example in the paper. Actually we are interested in the radical of the UD rather than the UD itself.

This is related to GCDFreeBasis CoprimeFactorBasis.

What is the status of this issue? It is written in a way which suggests that an implementation exists somewhere, but I do not seem to have it.