## Support #977

### "universal denominator" (related with GroebnerFanIdeals)

**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**

### 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

is OK for me.`UniversalRGBDenominator`

I note that there are already two "denominator" functions:

and`den`

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

to mean "reduced Groebner basis" is inconsistent with`RGB`

`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 over 1 year ago

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

#### #17 Updated by Anna Maria Bigatti about 1 year 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 9 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 9 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 9 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 8 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 6 months 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`

.