Ansatz brainstorming

Stream: Equational

[Alex Meiburg]

For the remaining ones, I was trying to thing of other ansätze we could use for the ones that seems resistant to most existing approaches. (I am sad that PORC approach seemed to be mostly a bust.) We have a few implications that were resolved through a clever operation that was linear over involving x, y, and sign(x-y), over the naturals or integers. Trying to generalize this, maybe one could write an ansatz that is _piecewise linear_ over its domain, where the pieces are defined by linear relations. This could be over N, Z, Z^2, etc. So something like

x * y = if a11*x + a12*y > a13 then (v11*x + v12*y + v13) else
  if a21*x + a22*y > a23 then (v21*x + v22*y + v23) else ...
    ... else (vN1*x + vN2*y + vN3)

Just taking N=2 or N=3 I think already includes some interesting cases. This includes arbitrary "fixups" on small values as a special case, because one can always cut off any lattice point with enough linear relations.

There's the question of how amenable this could be to computer search, though. The ifs mean it's not easy to work with it directly to solve for the coefficients. The way I could imagine going about this is plugging in some values, committing to certain branches, and then solving the resulting integer program.

For example, with 1323, this could look like: I plug x=5 and y=10 into x = y ◇ (((y ◇ y) ◇ x) ◇ y). Each of those 4 operations, there are (with N=2) two ways for the if statements to go, so 16 possible linear expressions. The resulting equation will involve the "v" variables, and then there's 4 side conditions involving "a" and "v" variables that need to be satisfied. You do this for several points and try to find a model that satisfies all of these at once .. and, ideally, does not satisfy some other equation.

It's not a particularly easy ansatz form to work with, but I think it's still amenable to computerized search up to some moderate size, and I'm hopeful for it.

I'm titling this channel as I am because I'm wondering if anyone has other ideas for general ansätze to try on the remaining hard problems.