Project

General

Profile

Support #977

"universal denominator" (related with GroebnerFanIdeals)

Added by Anna Maria Bigatti over 1 year ago. Updated about 1 month ago.

Status:
In Progress
Priority:
Normal
Assignee:
-
Category:
CoCoA-4 function to be added
Target version:
Start date:
17 Nov 2016
Due date:
% Done:

20%

Estimated time:
Spent time:

Description

[Coming from our recent work on MinPoly]
It would be interesting to investigate the "universal denominator" of an ideal.

[21-nov-2016: separated this from issue about GroebnerFanIdeals output]


Related issues

Related to CoCoA-5 - Feature #903: New function CallOnGroebnerFanIdeals: call function on GFan idealsClosed2016-07-04

Related to CoCoA-5 - Feature #978: CommonDenom: for polys and lists?New2016-11-21

Related to CoCoALib - Feature #979: SmallestNonDivisor -- new fnClosed2016-11-21

Related to CoCoA-5 - Slug #405: ReducedGBasis not memorized in an idealClosed2013-10-09

Related to CoCoA-5 - Design #984: GroebnerFanIdeals: order matrices sometimes have "large" entriesNew2016-11-26

Copied from CoCoA-5 - Support #973: GroebnerFanIdeals: verbosity and output styleClosed2016-11-17

History

#1 Updated by Anna Maria Bigatti over 1 year ago

  • Copied from Support #973: GroebnerFanIdeals: verbosity and output style added

#2 Updated by Anna Maria Bigatti over 1 year ago

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!)

#3 Updated by Anna Maria Bigatti over 1 year ago

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.

#4 Updated by Anna Maria Bigatti over 1 year ago

  • Subject changed from GroebnerFanIdeals: universal denominator to GroebnerFanIdeals and "universal denominator"

I copied John's code for further experiments in our working dir MinPoly2016, file Deltone.cocoa5. CVS-ed

#5 Updated by Anna Maria Bigatti over 1 year ago

  • Related to Feature #903: New function CallOnGroebnerFanIdeals: call function on GFan ideals added

#6 Updated by John Abbott over 1 year ago

  • Related to Feature #978: CommonDenom: for polys and lists? added

#7 Updated by John Abbott over 1 year ago

  • Related to Feature #979: SmallestNonDivisor -- new fn added

#8 Updated by Anna Maria Bigatti over 1 year ago

  • % Done changed from 10 to 20

The other functions should be called UniversalDenominator(I) and SmallestExcellentPrime(I).

#9 Updated by John Abbott over 1 year ago

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 :-/

#10 Updated by Anna Maria Bigatti over 1 year ago

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?

#11 Updated by John Abbott over 1 year ago

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?

#12 Updated by Anna Maria Bigatti over 1 year ago

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!

#13 Updated by John Abbott over 1 year ago

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?

#14 Updated by John Abbott over 1 year ago

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.

#15 Updated by John Abbott over 1 year ago

  • Related to Slug #405: ReducedGBasis not memorized in an ideal added

#16 Updated by John Abbott about 1 year ago

  • Related to Design #984: GroebnerFanIdeals: order matrices sometimes have "large" entries added

#17 Updated by Anna Maria Bigatti 10 months ago

  • Target version changed from CoCoA-5.2.0 spring 2017 to CoCoA-5.2.2

I think we are going to do more work on this topic. Postponing to next release.

#18 Updated by Anna Maria Bigatti 5 months ago

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

#19 Updated by John Abbott 5 months ago

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).

#20 Updated by Anna Maria Bigatti 5 months ago

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 ;-)

#21 Updated by Anna Maria Bigatti 3 months ago

  • Subject changed from GroebnerFanIdeals and "universal denominator" to "universal denominator" (related with GroebnerFanIdeals)
  • Target version changed from CoCoA-5.2.2 to CoCoA-5.2.4

#22 Updated by John Abbott about 1 month ago

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 US itself.

This is related to GCDFreeBasis.

Also available in: Atom PDF