## [Reduce-algebra-developers] factorization issue...

 [Reduce-algebra-developers] factorization issue... From: Michael Tuexen - 2011-11-17 08:03:34 ```Dear all, using the svn version of yesterday on Mac OS X Lion gives: [mba:~/Documents/reduce-algebra/trunk] tuexen% bin/redcsl -w Reduce (Free CSL version), 16-Nov-11 ... 1: setmod 2; on modular; 1 3: factorize(x^2+1); {{x + 1,0}} I would expect {{x + 1,2}}. Another try: 4: factorize(x^4+x^3+x+1); 2 {{x + x + 1,1},{x + 1,0}} where I would expect 2 {{x + x + 1,1},{x + 1,2}} However, 5: factorize(x^3+1); 2 {{x + x + 1,1},{x + 1,1}} works. So it looks like the modular reduction is also done for the multiplicities of the factors. Is this a bug or am I making a mistaking in using reduce? Best regards Michael ```

 [Reduce-algebra-developers] factorization issue... From: Michael Tuexen - 2011-11-17 08:03:34 ```Dear all, using the svn version of yesterday on Mac OS X Lion gives: [mba:~/Documents/reduce-algebra/trunk] tuexen% bin/redcsl -w Reduce (Free CSL version), 16-Nov-11 ... 1: setmod 2; on modular; 1 3: factorize(x^2+1); {{x + 1,0}} I would expect {{x + 1,2}}. Another try: 4: factorize(x^4+x^3+x+1); 2 {{x + x + 1,1},{x + 1,0}} where I would expect 2 {{x + x + 1,1},{x + 1,2}} However, 5: factorize(x^3+1); 2 {{x + x + 1,1},{x + 1,1}} works. So it looks like the modular reduction is also done for the multiplicities of the factors. Is this a bug or am I making a mistaking in using reduce? Best regards Michael ```
 Re: [Reduce-algebra-developers] factorization issue... From: Arthur Norman - 2011-11-18 22:42:22 ```> [mba:~/Documents/reduce-algebra/trunk] tuexen% bin/redcsl -w > Reduce (Free CSL version), 16-Nov-11 ... > > 1: setmod 2; on modular; > > 1 > > > 3: factorize(x^2+1); > > {{x + 1,0}} > > I would expect {{x + 1,2}}. > > So it looks like the modular reduction is also done for the multiplicities > of the factors. Is this a bug or am I making a mistaking in using reduce? > This is neither specific to the CSL version (as distinct to the PSL one) nor to a version built on a Macintosh. As you imagine, this is because with "on modular" everything end up reduced mod the specified prime, even things like the multiplicties here. If you go "tr factorize;" and repeat your examples you will find that the factorizer itself is handing back what you expect - it is just some processing after that doing the damage. Right now I can not think of a good trick that will preserve the multiplicites as returned at present - since as far as Reduce is concerned you just have a kist of lists there. This is obviously a mess - does anybody else have a good idea as to how we could fix it? I guess I could imagine that in the case of "on modular" the factorizer could replicate repeated factors rather than give then counts, so you would get factorize(x^1+1) => {{x+1,1}, {x+1,1}}; [supposing that for consistency the repeat count field was left in there] and that would at least be closer to a correct answer. Any better thoughts anybody? Arthur ```
 Re: [Reduce-algebra-developers] factorization issue... From: Arthur Norman - 2011-11-19 12:51:19 ```>> 3: factorize(x^2+1); >> >> {{x + 1,0}} >> >> I would expect {{x + 1,2}}. I have now just checked in a tiny extension so if you update from subversion and rebuild you should be able to go factorize!-mod!-p(x^2+1, 2); where the second argument is the prime you wish to use. At present it may misbehave randomly if you do not pass a PRIME. But at the top level you do not set a modulus or go "on modular" and so the bad reduction of the multiplicities does not happen. At least this gives a way ahead in some cases? Arthur ```
 Re: [Reduce-algebra-developers] factorization issue... From: Michael Tuexen - 2011-11-19 17:28:03 ```On Nov 19, 2011, at 1:51 PM, Arthur Norman wrote: >>> 3: factorize(x^2+1); >>> {{x + 1,0}} >>> I would expect {{x + 1,2}}. > > I have now just checked in a tiny extension so if you update from subversion and rebuild you should be able to go > > factorize!-mod!-p(x^2+1, 2); OK, that works. However, the commands I used were based on the documentation. So let me ask one more question: Reduce (Free CSL version), 19-Nov-11 ... 1: setmod 2; on modular; tr factorize; 1 (factorize) 4: factorize(x^2+x+1); Entering factorize (1 arg) Arg1: (plus (expt x 2) x 1) factorize = (list (list (!*sq ((((x . 2) . 1) ((x . 1) . 1) . 1) . 1) t) 1)) 2 {{x + x + 1,1}} So the exponent of x is not reduced modulo 2. Can't we avoid the multiplicity being reduced? This would allow to use reduce as described in the handbook. Of course, one can add your new function and change the handbook. Best regards Michael > > where the second argument is the prime you wish to use. At present it may misbehave randomly if you do not pass a PRIME. But at the top level you do not set a modulus or go "on modular" and so the bad reduction of the multiplicities does not happen. > > At least this gives a way ahead in some cases? > > Arthur > > ```
 Re: [Reduce-algebra-developers] factorization issue... From: Arthur Norman - 2011-11-19 19:57:51 ```> OK, that works. However, the commands I used were based on the documentation. Indeed they were - and in my first reply you see I was asking of other developers had bright ideas for how to provide a full fix. The documentation is in some sense right - just it does not express the awkward fact that multiplicities might be subject to the reduction-mod-p. That is liable to be an inelegancy (to say the least) that has been there ever since that capability went in > > So let me ask one more question: > > Reduce (Free CSL version), 19-Nov-11 ... > > 1: setmod 2; on modular; tr factorize; > 1 > (factorize) > 4: factorize(x^2+x+1); > Entering factorize (1 arg) > Arg1: (plus (expt x 2) x 1) > factorize = (list (list (!*sq ((((x . 2) . 1) ((x . 1) . 1) . 1) . 1) t) 1)) > > 2 > {{x + x + 1,1}} > > So the exponent of x is not reduced modulo 2. > Can't we avoid the multiplicity being > reduced? This would allow to use reduce as described in the handbook. > Exponents live in a different place in the internal data-structures and so are kept safe! The multiplicities are safe WITHIN the factoriser code, but outside that the design handed them back in simple lists. You in general want list elements to be reduced mod p. Hence this horror. So to survive that the system has to "know" a bit more that it does not have quite such a global "mod p" setting but that these bits need protecting. Right now I do not believe that that can be done while preserving backwards compatibility! For instance try setmod 3; on modular; for i := 1:10 do write i,":",i+1,":",x+i; and the value of i in the context "x+i" gets reduced mod 3, while the "i" alone and the "i+1" do not. OOOOOh! So this is NOT merely an issue with modular factorisation! > Of course, one can add your new function and change the handbook. Yup, I implemented my new function but have not (yet?) updated the documentation! Sorry. I hope that some of the other developers will join in to see if there is a good rational way ahead that will keep not just this one case happy but happiness in greater generality! Arthur > Best regards > Michael >> >> where the second argument is the prime you wish to use. At present it may misbehave randomly if you do not pass a PRIME. But at the top level you do not set a modulus or go "on modular" and so the bad reduction of the multiplicities does not happen. >> >> At least this gives a way ahead in some cases? >> >> Arthur >> >> > > ```
 Re: [Reduce-algebra-developers] factorization issue... From: Michael Tuexen - 2011-11-19 20:23:40 ```On Nov 19, 2011, at 8:57 PM, Arthur Norman wrote: >> OK, that works. However, the commands I used were based on the documentation. > > Indeed they were - and in my first reply you see I was asking of other developers had bright ideas for how to provide a full fix. The documentation is in some sense right - just it does not express the awkward fact that multiplicities might be subject to the reduction-mod-p. That is liable to be an inelegancy (to say the least) that has been there ever since that capability went in > >> >> So let me ask one more question: >> >> Reduce (Free CSL version), 19-Nov-11 ... >> >> 1: setmod 2; on modular; tr factorize; >> 1 >> (factorize) >> 4: factorize(x^2+x+1); >> Entering factorize (1 arg) >> Arg1: (plus (expt x 2) x 1) >> factorize = (list (list (!*sq ((((x . 2) . 1) ((x . 1) . 1) . 1) . 1) t) 1)) >> >> 2 >> {{x + x + 1,1}} >> >> So the exponent of x is not reduced modulo 2. >> Can't we avoid the multiplicity being >> reduced? This would allow to use reduce as described in the handbook. >> > Exponents live in a different place in the internal data-structures and so are kept safe! The multiplicities are safe WITHIN the factoriser code, but outside that the design handed them back in simple lists. You in general want list elements to be reduced mod p. Hence this horror. > > So to survive that the system has to "know" a bit more that it does not have quite such a global "mod p" setting but that these bits need protecting. Right now I do not believe that that can be done while preserving backwards compatibility! > > For instance try > setmod 3; > on modular; > for i := 1:10 do write i,":",i+1,":",x+i; > and the value of i in the context "x+i" gets reduced mod 3, while the "i" alone and the "i+1" do not. OOOOOh! So this is NOT merely an issue with modular factorisation! OK, I see. > >> Of course, one can add your new function and change the handbook. > > Yup, I implemented my new function but have not (yet?) updated the documentation! Sorry. I didn't expect an updated documentation. Just wanted to make sure that there is no easy way to extend to code to work like it is currently documented. I understood that you asked other developers if they come up with an idea. > > I hope that some of the other developers will join in to see if there is a good rational way ahead that will keep not just this one case happy but happiness in greater generality! Thank you very much for your fast support! BTW: I used reduce years ago and it was running within Common Lisp (I think it was PSL being implemented in Common Lisp. Is this still available? (I think I took the code at that time and ported it to Macintosh Common Lisp....) Best regards Michael > > Arthur > >> Best regards >> Michael >>> >>> where the second argument is the prime you wish to use. At present it may misbehave randomly if you do not pass a PRIME. But at the top level you do not set a modulus or go "on modular" and so the bad reduction of the multiplicities does not happen. >>> >>> At least this gives a way ahead in some cases? >>> >>> Arthur >>> >>> >> >> > ```