[PURRS-devel] Re: The specification of sqrfree()

[Roberto Bagnara]

Richard.Kreckel at Uni-Mainz.DE
> Pondering again about that definition.  Forget my remarks, they were 
> probably just confused.  However, I think it is still problematic because 
> the definition of `=' is unclear.
>
>  Maybe, this is better:
>  A polynomial p(X) in Q[X] is said <EM>square-free</EM>
>  if, whenever any two polynomials q(X) and r(X) in Q[X]
>  are such that expand(p(X)) == expand(q(X)^2*r(X)),
>  q(X) is constant.
>
> Do you think this is okay?  If so, we'll happily apply this immediately.


Dear Richard,

the definition of square-free polynomial we have in mind
is semantic, not syntactic.  In other words, we believe
it is unnecessary to expand() the lhs and rhs of

   p(X) = q(X)^2*r(X)

since what is meant is that the lhs and the rhs are the
same function.

We have also thought about a definition of square-free
decomposition that could safely accommodate both the
univariate and the multivariate case.  Here is a summary
of what we would like to add to GiNaC's documentation
(both the tutorial and the developer's reference)
just before the introduction of the sqrfree() function.

======================================================================

Definition 1
------------

A polynomial p(X) in C[X] is said <EM>square-free</EM>
if, whenever any two polynomials q(X) and r(X) in C[X]
are such that p(X) = q(X)^2*r(X), q(X) is constant.

Note: we mean that p(X) has no repeated factors, apart 
      eventually from constants. 

Definition 2
------------

Given a polynomial p(X) in C[X], we say that the 
decomposition 

  p(X) = b * p_1(X)^a_1 * p_2(X)^a_2 * ... * p_r(X)^a_r

is a <EM>square-free decomposition</EM> of p(X) if the 
following conditions hold: 

1) b is a non-zero constant; 

2) a_j is a positive integer for j=1, ..., r;

3) the degree of the polynomial p_j is strictly positive 
   for j=1, ..., r; 

4) the polynomial p_1(X) * p_2(X) * ... * p_r(X) is square-free.

Note: this need not be unique. For example, if 
      a_j is even, we could change the polynomial p_j(X)
      into (-p_j(X)).  We do not ask that the factors
      p_j(X) are irreducible polynomials. 

Specification of sqrfree()
--------------------------

Given a polynomial p(X) in C[X], the function sqrfree() returns
a square-free decomposition of p(X).

======================================================================

If you agree, we would adapt this for the two different contexts,
translate it into Doxygen and LaTeX and provide a patch against
GiNaC 1.0.3.

    the PURRS team

-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it