Now seriously: what is a polynomial?

[Roberto Bagnara]

Christian Bauer wrote:
>>The point here is to decide _exactly_ for which class of expressions
>>are the functions degree(), ldegree(), coeff(), lcoeff(), tcoeff(),
>>expand(), collect(), quo(), rem(), prem(), gcd(), lcm(), sqrfree()
>>and so forth guaranteed to work.
> 
> 
> An exact specification of the maximal classes of expressions that these
> functions can operate on and the exact results they produce would require
> more work than I'm willing to invest (that's partly because GiNaC was
> designed for a bunch of physicists to "get some work done", not as a
> collection of rigorously defined functions).
> 
> I'd be more comfortable if you could propose a set of specifications for
> these functions (for the cases you need), where I can say "Yes, this will
> work in all future versions of GiNaC", even if these are not the 'maximal'
> specifications.

Here is a formal definition of what is, for our application, a polynomial
in `x'.  The first (auxiliary) function defines scalars for `x', the other
function defines the real thing.  Notice that this is written referring
to the layer of software we have put on top of GiNaC, but the concepts
should be easily recognizable anyway.

//! \brief
//! Returns <CODE>true</CODE> if \p e is a scalar rapresentation for \p x;
//! returns <CODE>false</CODE> otherwise.
/*!
   This function realizes the definition of <EM>scalar representation
   for \f$ x \f$</EM>, where \f$ x \f$ is any symbol.
   This is more briefly written <EM>scalar</EM> and defined inductively
   as follows:
   - every number is a scalar;
   - every symbolic constant is a scalar;
   - every parameter different from \f$ x \f$ is a scalar;
   - if \f$ f \f$ is any unary function and \f$ x \f$ is a
     scalar representation, then \f$ f(x) \f$ is a scalar;
   - if \f$ a \f$ and \f$ b \f$ are scalars then
     \f$ a+b \f$, \f$ a*b \f$, and \f$ a^b \f$ are scalars.
*/
bool
is_scalar_representation(const Expr& e, const Symbol& x) {
   if (e.is_a_number())
     return true;
   else if (e.is_a_constant())
     return true;
   else if (e.is_a_symbol() && !e.is_equal(x))
     return true;
   else if (e.is_a_power())
     return is_scalar_representation(e.op(0), x)
       && is_scalar_representation(e.op(1), x);
   else if (e.is_a_function())
     return is_scalar_representation(e.op(0), x);
   else if (e.is_a_add() || e.is_a_mul()) {
     for (unsigned i = e.nops(); i-- > 0; )
       if (!is_scalar_representation(e.op(i), x))
	return false;
     return true;
   }
   return false;
}

//! \brief
//! Returns <CODE>true</CODE> if \p e is a polynomial in \p x;
//! returns <CODE>false</CODE> otherwise.
/*!
   This function realizes the definition of <EM>polynomial in \f$ x \f$</EM>,
   where \f$ x \f$ is any symbol.
   This is more briefly written <EM>polynomial</EM> and defined inductively
   as follows:
   - every scalar representation for \f$ x \f$ is a polynomial;
   - \f$ x \f$ is a polynomial;
   - if \f$ a \f$ is a polynomial in \f$ x \f$ and \f$ b \f$ is a positive
     integer, then \f$ a^b \f$ is a polynomial;
   - if \f$ a \f$ and \f$ b \f$ are polynomials then
     \f$ a + b \f$ and \f$ a * b \f$ are polynomials.
*/
bool
is_polynomial(const Expr& e, const Symbol& x) {
   if (is_scalar_representation(e, x))
     return true;
   else if (e.is_equal(x))
     return true;
   else if (e.is_a_power()) {
     if (is_polynomial(e.op(0), x))
       if (e.op(1).is_a_number()) {
	Number exponent = e.op(1).ex_to_number();
	if (exponent.is_positive_integer())
	  return true;
       }
   }
   else if (e.is_a_add() || e.is_a_mul()) {
     for (unsigned i = e.nops(); i-- > 0; )
       if (!is_polynomial(e.op(i), x))
	return false;
     return true;
   }
   return false;
}

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