Project

General

Profile

Feature #796

CoCoALib function for radical (or SqFree) of a polynomial

Added by Anna Maria Bigatti over 8 years ago. Updated over 6 years ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
New Function
Target version:
Start date:
05 Nov 2015
Due date:
% Done:

100%

Estimated time:
Spent time:

Description

This problem is generally easier than SqFreeFactor, indeed in SqFreeFactorPosDerChar0 it is just computed by the first 3 lines.

How easy is it to extract this function out of all cases considerend in SqFreeFactor?


Related issues

Related to CoCoALib - Feature #39: Squarefree factorizationClosed2011-11-30

Related to CoCoALib - Feature #45: Squarefree factorization - univariate polynomials, char 0Closed2011-11-30

Related to CoCoALib - Feature #46: Squarefree factorization - univariate polynomials, char p > 0Closed2011-12-20

Related to CoCoALib - Feature #47: Squarefree factorization - multivariate polynomialsClosed2011-11-30

Related to CoCoALib - Feature #947: IsRadical for ideal?In Progress2016-10-18

Related to CoCoALib - Design #950: factor and SmoothFactor for integers --> FactorINT, FactorINT_TrialDiv, FactorINT_PollardRhoClosed2016-10-20

Related to CoCoALib - Feature #951: New function: IsSqFreeClosed2016-10-24

History

#1 Updated by John Abbott over 7 years ago

#2 Updated by Anna Maria Bigatti over 7 years ago

This would be quite useful. For the time being should we just add

define SqFree(f)
  return product(SqFreeFactor(f).factors);
enddefine;

?

#3 Updated by John Abbott over 7 years ago

  • Status changed from New to In Progress
  • Assignee set to John Abbott
  • Target version changed from CoCoALib-1.0 to CoCoALib-0.99560
  • % Done changed from 10 to 50

I have an implementation in CoCoALib. It took so long because of a "mysterious bug" in ContentFreeFactor.

My current implementation works only for RingZZ and a polynomial ring over QQ or over a small finite field.

Curiously it seems to be faster for polynomials over QQ than over a finite field: in the former case it can use the simple formula f/gcd(f,f') whereas in the latter it computes a squarefree factorization then multiplies the factors together.

The case of monomials is handled specially.

NOTE Other cases could be handled: e.g. polynomials with integer coeffs.

#4 Updated by John Abbott over 7 years ago

Before checking in which name should I use?

Currently I have used radical in CoCoALib, and rad in CoCoA-5 (to avoid a clash with the fn radical defined in radical.cpkg).

Suggestions?

#5 Updated by Anna Maria Bigatti over 7 years ago

John Abbott wrote:

Currently I have used radical in CoCoALib, and rad in CoCoA-5 (to avoid a clash with the fn radical defined in radical.cpkg).

we could indeed use rad(I), rad(f),... which seems quite standard in all environments.

#6 Updated by John Abbott over 7 years ago

  • Status changed from In Progress to Resolved
  • % Done changed from 50 to 60

Checked in the code. Also two new tests test-NumTheory6 and test-SparsePolyRing3.
No documentation yet.

Names not yet decided. JAA finds radical clearer than rad (but it is also longer).

#7 Updated by John Abbott over 7 years ago

  • Related to Design #950: factor and SmoothFactor for integers --> FactorINT, FactorINT_TrialDiv, FactorINT_PollardRho added

#8 Updated by Anna Maria Bigatti over 7 years ago

After spending some time thinking and writing, I realized that we would need a
IsSqFree(f) which could be considerably faster than computing and checking f=radical(f).
(especially when it isn't)

#9 Updated by John Abbott over 7 years ago

I like the idea of a fn IsSqFree; it certainly could be faster than testing equality with the radical (and also clearer?)

I find that IsSqFree is easier to understand than IsRadical for ringelems (and perhaps BigInt).
But then it is inconsistent to have IsSqFree as the test, and radical to compute the "maximal square-free factor".

Unfortunately, I also find SqFree to be a poor choice for the name of the fn which computes the "maximal square-free factor".

Not sure how to resolve this naming problem.

#10 Updated by Anna Maria Bigatti over 7 years ago

#11 Updated by John Abbott over 6 years ago

  • % Done changed from 60 to 80

It seems that this issue is practically finished except for the questoon of the name of the function.
The main choice seems to be between: rad, radical or SqFree.

Let's decide; then we can close the issue.

#12 Updated by Anna Maria Bigatti over 6 years ago

John Abbott wrote:

It seems that this issue is practically finished except for the questoon of the name of the function.
The main choice seems to be between: rad, radical or SqFree.

I vote for radical: I cannot see a similar function in Macaulay2; however in Singular it is called sqrfree and its result is by default the square free factorization (and with flag "3" the radical of the polynomial).

#13 Updated by John Abbott over 6 years ago

  • Status changed from Resolved to Closed
  • % Done changed from 80 to 100

OK, let's use radical then (both for ideals and ring elements); it is the clearest.

Closing.

Also available in: Atom PDF