## Support #977

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

Status:
In Progress
Priority:
Normal
Assignee:
-
Category:
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?Resolved2016-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 Bigattiover 1 year ago

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

#### #2 Updated by Anna Maria Bigattiover 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 Bigattiover 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 Bigattiover 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 Bigattiover 1 year ago

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

#### #6 Updated by John Abbottover 1 year ago

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

#### #7 Updated by John Abbottover 1 year ago

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

#### #8 Updated by Anna Maria Bigattiover 1 year ago

• % Done changed from 10 to 20

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

#### #9 Updated by John Abbottover 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 Bigattiover 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 Abbottover 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 Bigattiover 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 Abbottover 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 Abbottover 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 Abbottover 1 year ago

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

#### #16 Updated by John Abbottover 1 year ago

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

#### #17 Updated by Anna Maria Bigattiabout 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 Bigatti9 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 Abbott9 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 Bigatti9 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 Bigatti8 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 Abbott6 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`.

Also available in: Atom PDF