Polynomial Factorization Service

[kohlhase]

I have been talking to Thomas Sturm at ACA today and together we had the following idea, which we should discuss, since it opens up a fully new field of applications for the MWS stystem.

The application is a polynomial factorization service:

• whenever a CAS factors a polynomial, it submits the polynomial P and its factors F to MWS(PF)
• MWS(PF) indexes P and stores F in the DB
• When another CAS wants to factor another polynomial P', it looks up whether MWS(PF) has the factors F' already. This is likely to be much quicker than

Why is this interesing for us? It generalizes the "signature" of MWS: from Formula Schema -> URI to Formula Schema -> Value. This should open many new applications for the system. Even more so, if Value contains the same parameters the indexed formulae contain.

I think we should look into just cobbling up a system that does this and announce it. The main problem is what to use as an input language. This is probably a string language for CAS, which we need to be able to parse. I will try to find out the best syntax to start here, maybe @JamesHDavenport advise on this.

@m-iancu @alexglont @Jazzpirate @florian-rabe

[kohlhase]

Actually, James and I had a little chat on this, we should probably start with something simpler: An exact factorization service based on hashing. Here is the idea:

• We do not use MWS, but just use a database (the one under MWS should be fine) for the factors, which stores triples (H,P,F), where H is a hash (James will supply the hashing function; the current suggestion is the multiset of the absolute value of coefficients of the highest-order monomials).
• querying is by Hash (at least as an imperfect filter: you send a hash query QH and the MWS(PF) will either tell you whether it has factors for this (actually for one of the polynomials that have hash QH).
• if the hash is so loose, then we can have a sequence of increasingly tight hash functions that restrict the queries further. And at any times we can just ask for all the factorizations (P,H) where P hashes to QH.
• we use OpenMath in MathML3 encoding (gzipped) for the representation of polynomials (according to James there is no good accepted syntax for polynomials in the CAS world). There are two CDs that are relevant here: polyr.ocd for recursive polynomials and polyd.ocd We should allow both representations and probably hold both versions in the data base and allow the query to specify which version they are expecting.

We should really just build this system and bet a community together. Once we have the data, we can use it for lots of things, e.g. a more MWS-like query language. Maybe @alexglont (the nlab stuff takes precedence though) can start this together with @tkw1536 for help with the web services involved

[kohlhase]

side note: this service is a very good example for the necessity of OpenMath. The normal envisioned use cases of OpenMath where CAS ask each other for partial results are relatively unrealistic. But such a database service is much more natural.

[JamesHDavenport]

How do we start writing a paper on this? Will this GitHub work?

[kohlhase]

we use our GitLab for that, I made a repos at https://gl.kwarc.info/mws/factorization-service for this. If you log into https://gl.kwarc.info/mws/ then I can give you access.

[kohlhase]

I should probably clarify, you should log in via your github credentials https://gl.kwarc.info/users/auth/github

[jbs1]

You should go to https://gl.kwarc.info/users/sign_in not to /users/auth/github and click on the "Sign in with Github" button.
If you go directly to auth/github the whole OAuth process doesn't work, because some requests were skipped.

[florian-rabe]

This seems closely related to a question we encountered in the context of LMFDb (and similar databases) and Tom's ongoing MSc project on querying: queries about atomic mathematical objects (e.g., numbers).

The substitution tree index of MWS is great for complex objects (i.e., objects with subobjects including even free variables). For atomic objects (which are essentially the literals, i.e., the values of the mathematical universe), it's good to complement MWS with a database based on some standard encoding and hashes.

Now a tricky problem is that atomic-complex is not as clear-cut a distinction as one might think. For example, polynomials, integer sequences, or Tannakian symbols can be seen as both complex objects and atomic values. The distinction may depend on the context of the content and/or the query.

I suggest Tom builds a database for mathematical values (a valuebase?) and their occurrences. The underlying datatype of values should contain numbers, lists of values, and tuples (records?) of values. (So maybe JSON is a good candidate format.)

Storing factorizations of polynomials (or integers) would then be a special case, just like storing OEIS sequences, or the recurring numbers/polynomials in LMFDb.

[JamesHDavenport]

Thanks. I went to the web page and it said I was already logged int. But I can’t persuade my Git client to talk to it. I am not convinced that James H Davenport is a valid user id, or at least that my system is grokking it correctly. So I’ve tried using the web interface to upload files. James

From: Jeremy Byron Schulz [mailto:notifications@github.com] Sent: 03 August 2016 12:40 To: KWARC/mws Cc: James Davenport; Mention Subject: Re: [KWARC/mws] Polynomial Factorization Service (#102)

You should go to https://gl.kwarc.info/users/sign_in not to /users/auth/github and click on the "Sign in with Github" button.

If you go directly to auth/github the whole OAuth process doesn't work, because some requests were skipped.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHubhttps://github.com/KWARC/mws/issues/102#issuecomment-237214014, or mute the threadhttps://github.com/notifications/unsubscribe-auth/AGvameO0_BXDIdI7aGWzuYh_72r7Uuqhks5qcH4dgaJpZM4JaZCM.