Comment by pfdietz
6 hours ago
Here the search wouldn't have been chosing the coefficients independently. Note that one intermediate variable is a polynomial in the input variables, and it is used in other polynomials. A search over expressions like the ones in the counterexample would have a much smaller search space.
1) How do you know this structure is the correct one a priori
2) You are starting at 10^500 possibilities. "Much" smaller is not enough, the order of magnitude of the order of magnitude needs to be changed.
3) You still need all of the other assumptions, which were completely unfounded
Impossible.
No, I’m not saying you would know in advance that it was possible, but sometimes you visit the crystal cave and the diamond is just sitting there, so why not work out the odds?
I learned from poking around that checking the invertibility of a system in C is a much, much harder problem than I thought. Nonetheless if that were no object, let’s say coefficients from -16 to 15 (5 bits) times eight terms times choosing up to cubes (64) times three equations is searchable, especially since you have only the final combination of coefficients in the determinant. It’s not impossible to generate the equations like this Fizzbuzz style.
Edit: no. 2048 possible monomials, to the 24th power, not times 24. Fine, can’t brute force it.
If I pull out the two terms 1+xy and 3 + 4xy as new variables, then make three polynomials that are <= 3 terms in each with coefficients in the range -3 to 3, then there are something like 10^19 possibilities. Multiply this by the various simple possibilities for the definitions of those two new variables.
The coefficients are mostly 1, so biasing toward that would make it much faster.