2
$\begingroup$

Consider the following polynomial :

$P[x,y]:=a_{11}+a_{12}y+a_{13}y^2+a_{21}x+a_{22}x y+a_{23}x y^2+a_{31}x^2+a_{32}x^2 y+a_{33}x^2 y^2$

where the $a_{ij}$ are either $1$ or $-1$. Thus there are $2^9=512$ possible polynomials. I want to find out of these 512, how many are factorable (or alternatively how many are irreducible). Instead of going through each case of coefficients, is there an algorithm or some way to do this in Mathematica?

Improve this question
$\endgroup$
4
  • $\begingroup$ Why not just go through each of the 512 polynomials and test Factor on each? Why is such a solution unacceptable to you? $\endgroup$
    – David G. Stork
    Commented May 31, 2016 at 23:23
  • $\begingroup$ I guess I could, however I'd also like to consider polynomials of higher degree with more coefficients so there will be much more to test factor. For example, the next polynomial Id like to test will have 16 coefficients so $2^{16}=65,536$ possible polynomials. I'm not sure If I could test each one in a normal timespan. $\endgroup$
    – David_Shmij
    Commented May 31, 2016 at 23:30
  • 2
    $\begingroup$ @David_Shmij Agreed, testing all those polynomials would be time-prohibitive at the speed of the code shown in my answer below (it would take approximately 2 years, for serial code, probably a bit better with parallelization). However, I think your problem becomes a mathematical one then, rather than one concerning Mathematica per se... $\endgroup$
    – MarcoB
    Commented May 31, 2016 at 23:33
  • $\begingroup$ Indeed, I will look into the mathematical side of this. Thanks for the detailed and perfect help with the case of 9 coefficients! $\endgroup$
    – David_Shmij
    Commented May 31, 2016 at 23:40

1 Answer 1

Reset to default
6
$\begingroup$

The number of polynomials is not so great in your original case: just generate them all programmatically, and test each one for irreducibility using IrreduciblePolynomialQ, which seems faster than actually doing the factorization using Factor:

p[x_, y_] = Total[Table[a[i, j] x^(i - 1) y^(j - 1), {i, 1, 3}, {j, 1, 3}], 2];
polynomials = p[x, y] /. Thread[Flatten[Array[a, {3, 3}]] -> #] & /@ Tuples[{1, -1}, {9}];

# -> IrreduciblePolynomialQ[#] & /@ polynomials

(* Out:

{1 + x + x^2 + y + x y + x^2 y + y^2 + x y^2 + x^2 y^2 -> False, 
 1 + x + x^2 + y + x y + x^2 y + y^2 + x y^2 - x^2 y^2 -> True, 
 1 + x + x^2 + y + x y - x^2 y + y^2 + x y^2 + x^2 y^2 -> True, 
 1 + x + x^2 + y + x y - x^2 y + y^2 + x y^2 - x^2 y^2 -> True, 
 1 + x - x^2 + y + x y + x^2 y + y^2 + x y^2 + x^2 y^2 -> True, 
 ...
}
*)

The process is relatively fast with this relatively small number of expression:

# -> IrreduciblePolynomialQ[#] & /@ polynomials; // RepeatedTiming

(* Out: {0.383, Null} *)
Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Exactly what I had in mind. (+1). $\endgroup$
    – David G. Stork
    Commented May 31, 2016 at 23:36
  • 1
    $\begingroup$ @DavidG.Stork Thank you! I estimated the time it would take to scale this to the size of the larger problem he mentioned, however, and it becomes prohibitive. I don't know of a faster brute-force approach (barring significant gains using parallelization). $\endgroup$
    – MarcoB
    Commented May 31, 2016 at 23:39
  • 3
    $\begingroup$ You can certainly eliminate half the polynomials from consideration (because they are related by a factor of -1 to others tested). And when I parallelize the question as asked, it takes 0.133 seconds on a 8-core Mac. $\endgroup$
    – David G. Stork
    Commented May 31, 2016 at 23:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.