search

flintlib / flint

FLINT (Fast Library for Number Theory)
http://www.flintlib.org
GNU Lesser General Public License v3.0
401 stars 235 forks source link

fix leading coefficient bug in fmpz_mpoly_factor #2000

Closed tthsqe12 closed 1 month ago

tthsqe12 commented 1 month ago

fixes https://github.com/flintlib/flint/issues/1998 short description: ZZ is not a field

long description fmpz_mpoly_factor_irred_wang is called on A = 3*x1^3*x2^3*x3^3*x4^3+9*x1^3*x2^3*x3^3*x4^2+9*x1^3*x2^3*x3^3*x4+3*x1^3*x2^3*x3^3+x1^3*x2^3*x3^2*x4^4+5*x1^3*x2^3*x3^2*x4^3+9*x1^3*x2^3*x3^2*x4^2+7*x1^3*x2^3*x3^2*x4+2*x1^3*x2^3*x3^2-4*x1^3*x2^2*x3^3*x4^3-4*x1^3*x2^2*x3^3*x4^2+4*x1^3*x2^2*x3^3*x4+4*x1^3*x2^2*x3^3-4*x1^3*x2^2*x3^2*x4^3-2*x1^3*x2^2*x3^2*x4^2+8*x1^3*x2^2*x3^2*x4+6*x1^3*x2^2*x3^2+2*x1^3*x2^2*x3*x4^2+4*x1^3*x2^2*x3*x4+2*x1^3*x2^2*x3-6*x1^3*x2*x3^3*x4^2-5*x1^3*x2*x3^3*x4+x1^3*x2*x3^3-13*x1^3*x2*x3^2*x4^2-11*x1^3*x2*x3^2*x4+2*x1^3*x2*x3^2-8*x1^3*x2*x3*x4^2-7*x1^3*x2*x3*x4+x1^3*x2*x3-x1^3*x2*x4^2-x1^3*x2*x4-2*x1^3*x3^3*x4-6*x1^3*x3^2*x4-6*x1^3*x3*x4-2*x1^3*x4-x1^2*x2^3*x3^2*x4^4-5*x1^2*x2^3*x3^2*x4^3-9*x1^2*x2^3*x3^2*x4^2-7*x1^2*x2^3*x3^2*x4-2*x1^2*x2^3*x3^2+x1^2*x2^2*x3^3*x4^3-5*x1^2*x2^2*x3^3*x4^2-13*x1^2*x2^2*x3^3*x4-7*x1^2*x2^2*x3^3+2*x1^2*x2^2*x3^2*x4^3-6*x1^2*x2^2*x3^2*x4^2-18*x1^2*x2^2*x3^2*x4-10*x1^2*x2^2*x3^2-4*x1^2*x2^2*x3*x4^2-8*x1^2*x2^2*x3*x4-4*x1^2*x2^2*x3+8*x1^2*x2*x3^3*x4^2+2*x1^2*x2*x3^3*x4-6*x1^2*x2*x3^3+21*x1^2*x2*x3^2*x4^2+11*x1^2*x2*x3^2*x4-10*x1^2*x2*x3^2+16*x1^2*x2*x3*x4^2+12*x1^2*x2*x3*x4-4*x1^2*x2*x3+3*x1^2*x2*x4^2+3*x1^2*x2*x4+5*x1^2*x3^3*x4-x1^2*x3^3+16*x1^2*x3^2*x4-2*x1^2*x3^2+17*x1^2*x3*x4-x1^2*x3+6*x1^2*x4+2*x1*x2^2*x3^2*x4^3+8*x1*x2^2*x3^2*x4^2+10*x1*x2^2*x3^2*x4+4*x1*x2^2*x3^2+2*x1*x2^2*x3*x4^2+4*x1*x2^2*x3*x4+2*x1*x2^2*x3-2*x1*x2*x3^3*x4^2+3*x1*x2*x3^3*x4+5*x1*x2*x3^3-7*x1*x2*x3^2*x4^2+3*x1*x2*x3^2*x4+10*x1*x2*x3^2-8*x1*x2*x3*x4^2-3*x1*x2*x3*x4+5*x1*x2*x3-3*x1*x2*x4^2-3*x1*x2*x4-4*x1*x3^3*x4+2*x1*x3^3-14*x1*x3^2*x4+4*x1*x3^2-16*x1*x3*x4+2*x1*x3-6*x1*x4-x2*x3^2*x4^2-3*x2*x3^2*x4-2*x2*x3^2-2*x2*x3*x4-2*x2*x3+x2*x4^2+x2*x4+x3^3*x4-x3^3+4*x3^2*x4-2*x3^2+5*x3*x4-x3+2*x4 the true factorization of A has two factors and looks like A = ((x2*x3*x4+x2*x3+x3+1)*x1 + ...) *((3*x2^2*x3^2*x4^2+6*x2^2*x3^2*x4+3*x2^2*x3^2+x2^2*x3*x4^3+4*x2^2*x3*x4^2+5*x2^2*x3*x4+2*x2^2*x3-4*x2*x3^2*x4^2-3*x2*x3^2*x4+x2*x3^2-5*x2*x3*x4^2-4*x2*x3*x4+x2*x3-x2*x4^2-x2*x4-2*x3^2*x4-4*x3*x4-2*x4)*x1^2 + ...) evaluation is tried at x2 = 1 x3 = 2 x4 = 1 which produces A = 4*(3*x1 - 1)*(x1 - 1)*(7*x1 - 3) modulo (x2 - 1, x3 - 2, x4 - 1) Since the number of factor is wrong, we already known lifting will not succeed, but let's see what else goes wrong first. Lifting does not alter the leading coefficients, so they have to be - in some sense - correct before lifting proceeds. The point of lcc is to find divisors of the leading coefficients of the factors of A assuming that the univariate factorization lifts (aka no extraneous factors). Since we had three univariate factors, assume that they lift to corresponding multivariate factors F1, F2, F3. lcc returns with (lc := lc_x1) lc(F1) is divisible by 1 lc(F2) is divisible by 3*x2^2*x3^2*x4^2+6*x2^2*x3^2*x4+3*x2^2*x3^2+x2^2*x3*x4^3+4*x2^2*x3*x4^2+5*x2^2*x3*x4+2*x2^2*x3-4*x2*x3^2*x4^2-3*x2*x3^2*x4+x2*x3^2-5*x2*x3*x4^2-4*x2*x3*x4+x2*x3-x2*x4^2-x2*x4-2*x3^2*x4-4*x3*x4-2*x4 lc(F3) is divisible by x2*x3*x4+x2*x3+x3+1 Since the product of these three divisors is exactly lc(A), there is nothing left over, m in the code is 1, and we will simply impose exactly these leading coefficients, i.e. lc(F1) = 1 lc(F2) = 3*x2^2*x3^2*x4^2+6*x2^2*x3^2*x4+3*x2^2*x3^2+x2^2*x3*x4^3+4*x2^2*x3*x4^2+5*x2^2*x3*x4+2*x2^2*x3-4*x2*x3^2*x4^2-3*x2*x3^2*x4+x2*x3^2-5*x2*x3*x4^2-4*x2*x3*x4+x2*x3-x2*x4^2-x2*x4-2*x3^2*x4-4*x3*x4-2*x4 lc(F3) = x2*x3*x4+x2*x3+x3+1 when lifting against A. The contradiction is already clear: the factor 3*x1 - 1 cannot possibly lift to an F1 with lc(F1) = 1 and the code tries to divexact(1,3). More specifically, evaluation at x2 = 1, x3 = 2, x4 = 1, produces lc(F1) = 1 modulo (x2 - 1, x3 - 2, x4 - 1) lc(F2) = 12 "" lc(F3) = 7 "" Therefore, the leading coefficients of the univariate factorizations are coerced to these as 1*x1 - 1/3 12*x1 - 12 7*x1 - 3 which isn't so good over ZZ. This would be fine to do over QQ, where the lifting would eventually just fail. **** Why lcc returns what it does **** lcc is the hairiest part of mpoly factor. Kaltofen is used here which looks at bivariate factorizations of A(x1, x2, 2, 1) = (288*x2^3+48*x2^2-198*x2-54)*x1^3 + (-96*x2^3-352*x2^2+174*x2+126)*x1^2 + (112*x2^2+54*x2-90)*x1^1 + (-30*x2+18)*x1^0 A(x1, 1, x3, 1) = (12*x3^3+4*x3^2-12*x3-4)*x1^3 + (-16*x3^3-20*x3^2+24*x3+12)*x1^2 + (4*x3^3+20*x3^2-12*x3-12)*x1^1 + (-4*x3^2+4)*x1^0 A(x1, 1, 2, x4) = (4*x4^4-4*x4^3-45*x4^2+19*x4+110)*x1^3 + (-4*x4^4-4*x4^3+75*x4^2+11*x4-226)*x1^2 + (8*x4^3-27*x4^2-51*x4+146)*x1^1 + (-3*x4^2+21*x4-30)*x1^0 The last two have content as polys in x1, so they are thrown away. Everything is deduced from the factorization A(x1, x2, 2, 1) = ( (3)*x1^1 + (-1)*x1^0 )* ( (12*x2^2-7*x2-3)*x1^1 + (-5*x2+3)*x1^0 )* ( (4*x2+3)*x1^1 + (-3)*x1^0 ) Note the leading coefficient of the first factor is a constant. What we have is a factorization of lc(A) modulo (x3 - 2, x4 - 1): lc(A) = (3)*(12*x2^2-7*x2-3)*(4*x2+3) modulo (x3 - 2, x4 - 1) This factorization happens to lift [only trivial lcc is applied recursively :)] and so the lifted factors can be safely assumed to be divisors of the lc(Fi)
fredrik-johansson commented 1 month ago

Terrific!

short description: ZZ is not a field

I had long suspected this.