How does PolynomialQ work? A discussion around https://github.com/Mathics3/mathics-core/pull/1239

[rocky]

In trying to get Combinatorica V2.0.0 to work better in Mathics3, I came across a deficiency in our implementation of PolynomialQ.

Combinatorica is a package for doing combinatorics, graphs, and discrete mathematics. In the version 2 iteration, Polya's theory for counting or characterizing kinds of graphs. Polya's theory uses polynomial generating functions to create Polynomials like x[1] ^ 3 / 6 + x[3] / 3 + x[1] x[2] / 2.

Notice here we have these x functions (x[1], x[2], x[3]) that we have a polynomial over.

The implementation in master for PolynomialQ[] is simply to call sympy.is_polynomal() after converting a Mathics3 expression into a SymPy expression. The current implementation works when x is a free symbol. However when it is a function the current master branch fails and that PR is a suggested way to fix which I'd like to discuss here.

I think the key is in how we convert the Mathics3 expression into SymPy.

There are various options available in the conversion routine. The current master branch doesn't use any of these so it gets the default behavior. The expression created does not do anything special for functions and so x is noted as a "free symbol". However, when SymPy checks free symbols against the SymPy expression created, there is never a match such as in x[1] because the match is against, x and x with some sort of "one-ness". I am not sure of the details of the "one-ness" here.

There is a mode for Mathics3 to SymPy conversion that creates SymPy UndefinedFunctions when sees one like x[1]. However, when this happens the resulting expression does not contain any free variables. Furthermore, I can't figure out how to change things so it would. The function creation code in SymPy is a bit opaque me me. There is one class for the object created by x() and then another when you change this to x(1). How it is those two classes are related is a mystery to me. (I get that the two objects are different and have different properties, but how you would get to tell the first class to sublass the second object creation to use a different kind of free_symbols routine is mired in meta programming that is beyond my understanding.

So instead, in #1239, I added yet another option for converting Mathics3 expressions into SymPy that is special for PolynomialQ and it has a name that indicates that it is special for it. If it turns out we use this approach and that special case has more general application we can change the option name.

Here, what I do is treat everything like the default case, but as soon as we get to functions with parameters, the parameters are dropped.

In essence, what is seen by PolynomialQ for the expression given before is x ^ 3 / 6 + x / 3 + x x/ 2 which is not equal in algebraic terms, but in this case is equal as far as PolynomialQ is concerned. The expression is only created for and used by PolynomalQ.

So now my question is, does this give wrong results in some cases? I couldn't find a counter-example. And this helps a lot with getting CombinatoriaV2.0.0 working. Is there a better solution?