Re: Improving PolynomialQ
- To: mathgroup at smc.vnet.net
- Subject: [mg16690] Re: Improving PolynomialQ
- From: Daniel Lichtblau <danl>
- Date: Sat, 20 Mar 1999 02:09:01 -0500
- Organization: Wolfram Research, Inc.
- References: <7ct1fu$81n@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Jack Goldberg wrote:
>
> Hi Group,
>
> Here is a programming challange: Design a predicate
>
> NewPolynomialQ[ expr ]
>
> which takes an expression "expr" as an SINGLE argument
> and returns True if expr is a polynomial and False if it
> is not. The argument "expr" may contain any number of
> variables and the variables may have any names.
>
> (This makes the problem much more difficult than those
> handled by PolynomialQ which requires the names of the
> variables.) From some experimentation I did, here are a
> small group of test expr's which are not handled well by
> PolynomailQ
>
> x, x+(-1)^y, x+Cos[Pi x], 2^x
>
> If this challange is too difficult (I have a sneaking
> suspicion that it just might well be insoluble) how
> about a "semi" predicate
>
> NewPolynomial[ expr ]
>
> which returns True only when it is manifestly clear that
> expr is a polynomial in all its variables and returns
> NewPolynomial[ expr] otherwise - much like Positive[ expr ]?
>
> While trying out various possibilities, I ran into some unexpected
> outputs from Variables[ expr ]. Compare, for instance,
>
> Variables[x+(-1)^y]
> with
> Variables[x+Cos[y]]
This is both complicated and difficult to defend; as I am the person who
maintains the relevant code I'll give it a go. First, Mathematica does
not go inside second arguments when the head is Power or accept as
"variables" things with such heads. We do not go inside the second
argument because in that case the input is manifestly transcendental in
the exponent (rather than polynomial). We do not encapsulate the entire
subexpression for the same reason we do not encapsulate things with head
of Plus or Times; these are arithmetic heads.
In contrast, we accept as encapsulated "variables" things with other
heads, hence Cos[y] is returned in the second list. This may not be
optimal if the head has the NumericFunction attribute, though clearly(?)
you would want to encapsulate x[1] as a variable.
> Since Variables[expr] is designed to work only with polynomials, one
> might argue that Mathematica is not responsible for its misuse as above. However,
> if the argument to variables is not a polynomial, shouldn't Variables
> be designed to return Variables[expr] instead of a misleading answer?
For reasons I hint at above and below, I support your statement that
Mathematica is not responsible in this instance because it cannot
possibly do something that is self-consistent across the spectrum of
reasonable inputs (basically, it is not a well-defined task).
> So, one should reprogram Variables[expr] to detect whether expr is
> a polynomial... ah ha! so that's the motivation behind the challange.
>
> Jack
As for the general challenge, it is only insoluble if you hail from the
Brittish Commonwealth; for the rest of us it is merely unsolvable.
Actually the sticky point is that it is not a well-defined problem; it
hinges on the question of "What is a variable?" This rears its hideous
head in-house at least annually (several years ago when we scheduled a
meeting on the topic, I said I'd be sick that day. With good reason.)
Anyway, this apparently has different answers for different functions,
and I believe this is for good reason. So it will deoend on your
specific purposes as to what you might choose to call a 'variable," Let
me note some of the issues, and then show one approach to your desired
functionality.
If a subexpression has head of List, perhaps you want the function to
thread over the arguments. So you might make it Listable. Or maybe you
want the entire thing to be "encapsulated" so that the "variables"
inside Pi + {3,c} would be {{3,c}} rather than {c}? For that matter, how
should we treat NumericQ entities such as Pi or Cos[1]? What of
Union[...] or GCD[a,b]? In other words, do we go inside these heads and
extract innards, just encapsulate the entire thing as a "variable", or
ignore them entirely? The function you want will depend on how you
answer these questions.
That said, I'll show some code that looks for variables only inside
expressions with heads that have NumericFunction attribute, and excludes
from consideration as a variable everything that is NumericQ. Even this
is imperfect in the sense that there are functions that are "numeric"
but for technical reasons do not have the NumericFunction attribute
(usually due to restrictions on the domain). That said, here goes.
allVariables[expr_] := Module[
{vars={}},
If [NumericQ[expr], Return[{}]];
If [AtomQ[expr], Return[{expr}]];
If [!MemberQ[Attributes[Evaluate[Head[expr]]],NumericFunction],
Return[{expr}]];
Do [vars = {allVariables[expr[[j]]],vars}, {j,Length[expr]}];
Union[Flatten[vars]]
]
In[9]:= allVariables[x+(-1)^y - Exp[Pi]]
Out[9]= {x, y}
newPolynomialQ[expr_] := PolynomialQ[expr,allVariables[expr]]
In[10]:= newPolynomialQ[x+(-1)^y]
Out[10]= False
In[11]:= newPolynomialQ[x+Exp[Pi]]
Out[11]= True
Daniel Lichtblau
Wolfram Research