Fwd: factoring, finite fields, and future developments
Sherm Ostrowsky
From: Sherm Ostrowsky <sher...@gmail.com>
Date: Mon, Oct 3, 2011 at 10:33 PM
Subject: factoring, finite fields, and future developments
To: mathri...@googlegroups.com
I have been studying in detail the code written by the Yacas Team (YT) for their BinaryFactors() function, which we have taken over almost unchanged for MathPiper. They also included a great Essay on how this algorithm (a new one, apparently, not previously published elsewhere) works. Between the essay, the code, and running the function with a LOT of debug printout, I am beginning to gain some understanding of the clever tricks they included to make it run more efficiently. Very interesting. The code is definitely not self-explanatory.
In support of this effort, I have also been re-reading many old papers and as many new ones as I could find, as well as several books, which have bearing on Polynomial Factoring algorithms and methods.
In the process, I have become aware of some points which I would like to bring up here.
Almost all current CASs use versions of the same algorithms for factoring univariate polynomials, except of course for new refinements added by YT. One of the important steps begins by expressing the input polynomial (over ZZ or QQ) over a finite field of small dimension (usually F2). If a solution is found in this very restricted field (a very easy job), that solution can be "lifted" into higher-dimensional finite fields, until eventually it is known in ZZ (or QQ). This idea made me begin to study Finite Fields, about which there is an enormous literature, so I could understand how these algorithms work. Base Fields, like Fp (where p is a prime number), and polynomial rings over these base fields, but modulo also an irreducible prime polynomial of appropriate degree (these extended fields are called F(p^m) or GF(p^m)) are interesting in their own right. So my studies have expanded to include these subjects, too.
This is not just idle description. In addition to the fact that I (at least) need to understand how these things work, I now believe that MathPiper's usefulness for its intended Student audiences would be enhanced if we could "teach" MathPiper how to work seamlessly in various Groups, Fields, and Ring structures. These subjects, after all, are being taught to students, who might like to be able to try out the (somewhat abstract) stuff they are learning, by working in MathPiper.
And THAT leads me back into a topic of recent interest to this Group, namely how to handle unbound variables in MathPiper. My ideas on that subject are in the process of becoming clarified as I continue to read and study.
I see that this note is already becoming rather long, so I probably should defer my conclusions on this specific topic till a later time. However, I do want to bring up one interesting comment which I think is very relevant to our project. I found it while reading the Manual for a Mathematica package called Galois Fields Package. In his introduction, the author, Ryoh Fuji-Hara, said the following:
"When we implement an algebraic system like a group, a ring or a finite field within an existing symbolic computational language, then there are three possible approaches:
(1) define new operators: for example; if we define an operator %+% for addition on a finite field, then we could operate in the following fashion: 2 %+% 4 .
(2) change mode: for example; if we write ChangeAlgebra[GF,7], then every computation is done over GF(7) until we change to some other algebra.
(3) use the same operations within the existing system (i.e. +,-,*,/ ): for this we have to identify constants and variables to be in a certain algebra. In this method a lot of original functions of the system become available to the new algebra.
Due to the fact that Mathematica is an object based language it facilitates the adaptation of the third method cited above. Thus, the package allows us to use many functions of Mathematica over finite fields without any modification, i.e.; solving linear equations, inverses, determinants, derivations, resultants, etc."
I think that is right to the point. We are trying to what he was, namely implement one or more Algebraic systems within an existing Symbolic Computational framework -- MathPiper. We, too, have essentially the same three routes to consider, and I believe that any of them could be implemented in MathPiper with minimal difficulty. But, like the Package author, I believe that the third alternative would be the most productive for future extensions. So we come to the point mentioned in earlier notes to this Group,
In a computer program or function, variables may (or must, depending on the language) be Declared before use. This kind of declaration helps to prevent misspelled variable names from causing obscure bugs. It may also be used to Localize variables to a specific program block, thereby controlling their Scope. If, in addition, the Kind of the variable (e.g. integer, float, string, etc) is also declared, this is usually to make things easier for the Compiler or Interpreter to do its job.
This may indeed be a subject under discussion for MathPiper, but it is not the subject I want to talk about. I am now referring the the declaration of "variables" -- really "symbols" -- which are thereafter to be assumed to represent objects belonging to a particular Mathematical Type, such as Units, Group, Field, Ring, etc. Every symbol thus declared should be considered to represent an object of this type, whether or not it has been bound to any value. Any operations carried out in respect to any such symbol shall be carried out using operations (if any) specific to this domain. And the MathPiper system should do this automatically as long as the symbol's Type declaration remains in effect.
Thus, for example, if we declare the symbols "x", "y", and "z" to be of Type ZZ5, all arithmetic operations involving these symbols and any numbers or other (not declared as such) numerical variables, will be done Modulo 5. I don't as yet know exactly what syntax we will be using for such a declaration, and it remains to be decided what the Scope of such declarations ought to be. But this is the kind of new context I would like to see MathPiper have.
I am still evolving this concept. Please feel free to comment, add suggestions, etc.
Sherm
Sherm Ostrowsky
I recall that MathPiper has a built-in ability to create a wrapper of LocalSymbols() [ ... ] about a program block, in which all the "named" symbols are "decorated" (in the sense that term is used in C++ implementations) inside the enclosed block, transparently to the programmer.
I don't know how that is implemented in MathPiper, but I think some extension of the same technique might serve to let us at least prototype a Typing system such as I described in the previous note. By adding suitable "decorations" (invisible to the user/programmer inside the block), the Type information fore that symbol might be attached. Example : x is an element of Galois Field GF(7), and it appears internally as x$GF_7 or some such.
I say that this could be used for prototyping, mainly because it might be too slow for a final implementation. Each variable would have to be parsed by each function and operator using it, to see which variant overloaded function or operator should be called explicitly. In a compiled language like C++ this is not a problem, since this examination and determination only has to be done once, at compile time. In an interpreted language like MathPiper, it could cause considerable slowdown. But there might be ways to have our cake and eat it too, though I don't know enough about the implementation details of mathpiper to speculate on this any further.
Just throwing this out for comment.
Sherm
Ted Kosan
> An idea has occurred to me since I wrote this.
>
> I recall that MathPiper has a built-in ability to create a wrapper of
> LocalSymbols() [ ... ] about a program block, in which all the "named"
> symbols are "decorated" (in the sense that term is used in C++
> implementations) inside the enclosed block, transparently to the programmer.
>
> I don't know how that is implemented in MathPiper, but I think some
> extension of the same technique might serve to let us at least prototype a
> Typing system such as I described in the previous note. By adding suitable
> "decorations" (invisible to the user/programmer inside the block), the Type
> information fore that symbol might be attached. Example : x is an element
> of Galois Field GF(7), and it appears internally as x$GF_7 or some such.
>
> I say that this could be used for prototyping, mainly because it might be
> too slow for a final implementation. Each variable would have to be parsed
> by each function and operator using it, to see which variant overloaded
> function or operator should be called explicitly. In a compiled language
> like C++ this is not a problem, since this examination and determination
> only has to be done once, at compile time. In an interpreted language like
> MathPiper, it could cause considerable slowdown. But there might be ways to
> have our cake and eat it too, though I don't know enough about the
> implementation details of mathpiper to speculate on this any further.
I have been pondering your original post all day and before I submit
my thoughts on it I have a question. What assumptions do the existing
MathPiper rules make about unbound variables? For example, what type
are they assumed to be?
Ted
Sherm Ostrowsky
sherm
Ted Kosan
> as far as i know, unbound variables have no type, do they? does mathpiper
> have types? if so, what are they, and how can you query this? well, i
> guess String is a type. what are others? if bound to a different object,
> variable acquires type. But unbound...?
The rules that use unbound variables must make some implicit
assumptions about what these variables represent. What are these
implicit assumptions?
Ted
Sherm Ostrowsky
Bind() doesn't seem to care whether the variable was previously bound or not; it just attaches a new "object" to the symbol.
Unbind(), on the other hand, has to leave something (a symbol) in some kind of state, but that is not mentioned in the documentation. Perhaps the java code for Unbind() will tell you what kind of thing is left after using Unbind() on a symbol.
All this kind of reminds me of the way Python handles "variables".
Sherm
grzesiek
On Wednesday, October 5, 2011 7:02:25 AM UTC+2, tkosan wrote:
I have been pondering your original post all day and before I submit
my thoughts on it I have a question. What assumptions do the existing
MathPiper rules make about unbound variables?
For example, what type
are they assumed to be?
grzesiek
On Wednesday, October 5, 2011 7:41:40 PM UTC+2, shermo wrote:
Bind() doesn't seem to care whether the variable was previously bound or not; it just attaches a new "object" to the symbol.
Unbind(), on the other hand, has to leave something (a symbol) in some kind of state, but that is not mentioned in the documentation. Perhaps the java code for Unbind() will tell you what kind of thing is left after using Unbind() on a symbol.
grzesiek
On Wednesday, October 5, 2011 6:47:19 AM UTC+2, shermo wrote:
I recall that MathPiper has a built-in ability to create a wrapper of LocalSymbols() [ ... ] about a program block, in which all the "named" symbols are "decorated" (in the sense that term is used in C++ implementations) inside the enclosed block, transparently to the programmer.
I don't know how that is implemented in MathPiper,but I think some extension of the same technique might serve to let us at least prototype a Typing system such as I described in the previous note. By adding suitable "decorations" (invisible to the user/programmer inside the block), the Type information fore that symbol might be attached. Example : x is an element of Galois Field GF(7), and it appears internally as x$GF_7 or some such.
I say that this could be used for prototyping, mainly because it might be too slow for a final implementation. Each variable would have to be parsed by each function and operator using it, to see which variant overloaded function or operator should be called explicitly.
Ted Kosan
> The notion of type does does not, strictly speaking, apply here.
Here is what "The Handbook of Mathematical Discourse" by Charles Wells
(www.abstractmath.org/Handbook/handbook.pdf) has to say about the type
of a symbol:
-----------------------------------------------------------------------------------------------------------------------------------
TYPE - The type of a symbol is the kind of value it is allowed to have
in the current context.
Example 1: In the assertion "If f is differentiable and f (x) = 0 then
x is a critical point of f ."
we may deduce that f is of type function and x is (probably) of type
real, even if the author
does not say this.
This sort of type deduction requires both math-
ematical knowledge and knowledge of conventions; in
the present example one convention is that complex
numbers are more commonly written z instead of x.
Mathematical knowledge (as well as convention) tells us
that x cannot be of type integer.
TYPES AND SETS - One could dispense with the concept of type and refer
to the set of possible
values of the symbol. It appears to me however that "type" is
psychologically different from
"set". Normally one expects the type to be a natural and homogeneous
kind such as "function"
or "real number", not an arbitrary kind such as "real number bigger
than 3 or integer divis-
ible by 4". One has no such psychological constraint on sets
themselves. This needs further
investigation.
TYPE LABELING: means giving the type of a symbol along with the symbol. It is
a form of redundancy.
Example 2: If it has been established on some early page of a text
that S3 denotes the
symmetric group on 3 letters. A later reference to it as "the group S3
" or "the symmetric group
S3 " is an example of type labeling.
Remark 1: Russian mathematical authors seem to do this a lot, although
that may be
because one cannot attach grammatical endings to symbols.
References: Jeffrey Ullman, in a guest appearance in [Knuth, Larrabee
and Roberts,
1989], flatly recommends always giving the type of a symbol. Using
explicit typing in teaching is
advocated in [Wells, 1995]. See also [Bagchi and Wells, 1998a].
Difficulties: Students commonly make type mistakes
(talking about 2π being divisible by 2, for example); it
would be helpful to refer to the concept explicitly as a
way of raising consciousness. This is discussed in [Wells,
1995]. Citations: (HebMckWea89.47),(KulMir86.36).
581
Note 1:
Mathematicians do not use the word
"type" much in the sense used here.
When they do use it it typically refers
to a classification of structures in a
particular field, as in for example differ-
ential equations of hyperbolic type.
Note 2:
The discussion here is about using
the concept of type in communicating
mathematics, not its use in logic or
foundations. It is not inconsistent to
believe both of these statements:
* In mathematical teaching and
writing, it is helpful to mention
the type of a variable.
* Formal mathematical logic is best
done using untyped variables.
pages 580-581
-----------------------------------------------------------------------------------------------------------------------------------
Adding a "type labelling" capability for unbound symbols to MathPiper
(as described above) may be one way to solve the problem we are
discussing.
Ted
Sherm Ostrowsky
Further thoughts on this subject. Empirical determination of what MathPiper (user language) and MathPiper-Java(underlying language) and perhaps MathPiper-Lisp-on-top-of-Java (effective language) consider to be the "type" of a symbol (not "variable" -- I agree with Grzesiek here).
Start a new instance of MathPiper.
Just enter a few symbol names, with no meaning attached.
What does MathPiper say about these? Is there any MathPiper predicate or function that can distinguish these from one another. Best guess -- NO.
What does Jave say about these? Is there any Java predicate or function that can distinguish these from one another? Best guess -- NO.
Bind them to different objects of different kinds, e.g., x:= 2; y := Sqrt(2.0); z := "this is a string".
What does MathPiper say about these? Is there any MathPiper predicate or function that can distinguish these from one another. Best guess -- OF COURSE. MathPiper can inquire if Bound, and find answer is Yes. MathPiper can determine that z is bound to a string object. MathPiper can determine that x is bound to an Integer object. MathPiper can determine that y is bound to a Real (Float? or whatever) object. But this is not meaningful for our question, because the information concerns not the symbol but only the object it is bound to.
What does Jave say about these? Is there any Java predicate or function that can distinguish these from one another? Best guess -- OF COURSE. Exactly the same comments as above!
Now, Unbind each of these.
Can either MathPiper of Java distinguish a symbol which has never been bound from one that was bound and then unbound? Can Java? My guess (but the experiment should be made) is NO. In that case, an unbound symbol has NO STATE that can be measured or determined. Period.
If it should happen that the answer is YES in any of the 3 cases mentioned above, then that would say a lot about the possibility that an unbound symbol may have a State. But I would be very surprised.
Bottom line: pending proof to the contrary, I would say that an unbound symbol has no State; only an object which can be bound to this symbol has a State, and the symbol loses any such state (which "it" -- the symbol -- never really "had") when that connection is severed.
Or is all this completely missing some subtle point that I am blind to?
Sherm
Ted Kosan
> Further thoughts on this subject. Empirical determination of what
> MathPiper (user language) and MathPiper-Java(underlying language) and
> perhaps MathPiper-Lisp-on-top-of-Java (effective language) consider to be
> the "type" of a symbol (not "variable" -- I agree with Grzesiek here).
"A Handbook of Mathematical Discourse"
(http://www.abstractmath.org/Handbook/handbook.pdf) has the following
definition for a variable:
"The noun variable in mathematical discourse generally refers to a
variate symbol." p. 604.
> Now, Unbind each of these.
>
> Can either MathPiper or Java distinguish a symbol which has never been bound
> from one that was bound and then unbound? Can Java? My guess (but the
> experiment should be made) is NO. In that case, an unbound symbol has NO
> STATE that can be measured or determined. Period.
>
> If it should happen that the answer is YES in any of the 3 cases mentioned
> above, then that would say a lot about the possibility that an unbound
> symbol may have a State. But I would be very surprised.
>
> Bottom line: pending proof to the contrary, I would say that an unbound
> symbol has no State; only an object which can be bound to this symbol has a
> State, and the symbol loses any such state (which "it" -- the symbol --
> never really "had") when that connection is severed.
>
> Or is all this completely missing some subtle point that I am blind to?
I think that Grzesiek's explanation of what an unbound variable
usually means in MathPiper is a good one:
"In most cases they belong to a field, either complex or real.
Unfortunately, it depends on the particular rule which field is
assumed, and there is some inconsistency in the
standard set of rules."
Your are correct in your thought that unbound variables in MathPiper
have no extra information associated with them. The people who wrote
most of the rules in MathPiper simply _assumed_ that all unbound
variables belonged to the real field or the complex field and this
assumption was then encoded into the logic of the rules.
Ted
Sherm Ostrowsky
I do not understand this. In what sense does an unbound "variable" belong to ANY kind of "field" or anything else, when it has no State? Like a Black Hole, it has "no hair". So you are saying that all the "expectations" concerning its "properties" are embodied in the hodgepodge of rules, written by different people at different times and, as you say, undoubtedly inconsistent in many places. If that is so, then we are ALREADY starting from an unknown condition, and that situation only grows worse as each new rule is added.
But it all works! Almost always! Except of course for "bugs", which have proved to be findable and fixable. So "by their fruits ye shall know them" -- this inconsistent and unknowable starting state, whether real or virtual (a-la quantum field theory) is not there in any practical sense. Pending an equivalent of the E.R.P. experiment for MathPiper, if it has no measurable effect, it doesn't exist.
Sherm
Sherm Ostrowsky
Forget about the idea of "typing" symbols in a general CAS, and focus specifically on MathPiper as a Primarily Rule-Based CAS. This, I think is consistent with Grzesiek's approach. I don't know for sure, but I suspect that MathPiper is more thoroughly Rule-Based than other general CAS, and the only other major one I can think of off hand is RUBI, which is directed at a specific subset of problems, but is very well developed.
The set of rules in MathPiper is not invoked in a random way, nor yet in a systematic way, if that term means that you start with no idea of where you are going, and just let the rules and their predicates create a path. Rather, in MathPiper, the User serves as the initial "pilot", directing MathPiper to look into a specific subset of the rules; he does this by his choice of which Function he calls. If he is doing Integration, he calls the Integrate function with his input, and that already picks out a sub-set of the rules to work in. Similarly for Differentiate, Factor, Solve, etc.
These rule-sets are probably not disjoint, and in fact I doubt that it would be possible to make them so. But what I am saying here is that the User plays a role -- a man-in-the-loop, if you will. So, instead of trying to place types on the symbols themselves, with all the issues previously discussed here, why not let the user impose types in his calling function. He doesn't just call Function(), he calls Function_Subclass(), and that call, during its setup phase, imposes restrictions on the symbols -- restrictions which will remain in force only during the scope of that function call.
I have not even begun to think this through, yet, but I want to throw out the idea for discussion.
Sherm
grzesiek
On Thursday, October 6, 2011 1:15:02 AM UTC+2, tkosan wrote:
Grzesiek wrote:> The notion of type does does not, strictly speaking, apply here.
Here is what "The Handbook of Mathematical Discourse" by Charles Wells
(www.abstractmath.org/Handbook/handbook.pdf) has to say about the type
of a symbol:-----------------------------------------------------------------------------------------------------------------------------------
TYPE - The type of a symbol is the kind of value it is allowed to have
in the current context.
TYPE LABELING: means giving the type of a symbol along with the symbol. It is
a form of redundancy.Example 2: If it has been established on some early page of a text
that S3 denotes the
symmetric group on 3 letters. A later reference to it as "the group S3
" or "the symmetric group
S3 " is an example of type labeling.Remark 1: Russian mathematical authors seem to do this a lot, although
that may be
because one cannot attach grammatical endings to symbols.
Adding a "type labelling" capability for unbound symbols to MathPiper
(as described above) may be one way to solve the problem we are
discussing.
Sherm Ostrowsky
It seems simple to me. A student in college is learning about Finite Fields. She wants to be able to play around with it, using MathPiper as an educational tool. She wants to declare that she is working in, say, F7, and have all calculations subsequently be made in F7, so that if she types 3 * 6 the answer should be 4, rather than 18. She wants to say that x is an unbound variable over F7, so that the polynomial multiplication (2*x^2-3)*(5*x+6) would automatically be done mod 7 on the coefficients (I think this would be 3*x^3+5*x^2+6*x+3, but don't hold me to it!). At a more advanced level, she might eventually want to be able to perform polynomial arithmetic modulo a specified "prime" polynomial.
Maybe in fact this is simply outside the scope of MathPiper as we see it, but to me that would be a pity. I am not aiming at professional mathematicians here, but students who need to practice and be assured the the answers will be correct.
Comments?
grzesiek
On Friday, October 7, 2011 12:41:17 AM UTC+2, shermo wrote:
I cannot get my mind around the -- to me -- overly subtle distinctions you are making.
Ted Kosan
> You guys are completely losing me. I cannot get my mind around the -- to me
> -- overly subtle distinctions you are making. Perhaps that just means I
> have too concrete a mind to be in this business.
>
> It seems simple to me. A student in college is learning about Finite
> Fields. She wants to be able to play around with it, using MathPiper as an
> educational tool. She wants to declare that she is working in, say, F7, and
> have all calculations subsequently be made in F7, so that if she types 3 * 6
> the answer should be 4, rather than 18. She wants to say that x is an
> unbound variable over F7, so that the polynomial multiplication
> (2*x^2-3)*(5*x+6) would automatically be done mod 7 on the coefficients (I
> think this would be 3*x^3+5*x^2+6*x+3, but don't hold me to it!). At a more
> advanced level, she might eventually want to be able to perform polynomial
> arithmetic modulo a specified "prime" polynomial.
>
> Maybe in fact this is simply outside the scope of MathPiper as we see it,
> but to me that would be a pity. I am not aiming at professional
> mathematicians here, but students who need to practice and be assured the
> the answers will be correct.
>
> Comments?
At this point I think it would be helpful if we looked at how some of
the other CASs implement the capabilities you would like to add to
MathPiper. My thought is that Axiom, Sage, Maxima, and Reduce would be
good ones to use.
We can start with the F7 example you have provided. Do you have any
other examples in mind that can be used for the comparison?
Ted
Ted Kosan
> Right. It went too far for no good reason. Sorry for the noise.
So far I have found the discussion we have been having to be helpful.
I think that we have just begun to scratch the surface of this issue
and it is going to take significantly more discussion and research
before we resolve it :-)
Ever since MathPiper was forked from Yacas in 2008, Sherm and I have
been putting off truly trying to understand how MathPiper works at it
deepest levels until we had gained a reasonable understanding of how
it works at shallower levels. If we are going to attempt to implement
the capabilities that Sherm is proposing, I don't see how we can do it
without (finally!) completely figuring out how MathPiper works first.
Sherm, earlier in this discussion you wrote:
"So you are saying that all the "expectations" concerning its
"properties" are embodied in the hodgepodge of rules, written by
different people at different times and, as you say, undoubtedly
inconsistent in many places."
My understanding is that most of the rules in MathPiper were written
by just two people (Ayal Pinkus and Sergei Winitzki) and they worked
closely together over a number of years creating the MathPiper
rulebases. As you suggested earlier, turning our attention to the
details of how the MathPiper rules system works may be a good way to
proceed.
I can put together a description of my current understanding of how
the MathPiper rule system works as a way to begin this discussion.
What do both of you think about this idea?
Ted