# Can one optimize the probability that an identity is satisfied until the probability is $1$?

I wonder how well one can obtain algebraic structures that satisfy interesting algebraic identities by simply slowly modifying those algebraic structures until they satisfy the required identities. I have used this technique to come up with multiplication tables on semigroup, and I have used a similar technique for endowing the classical Laver tables with compatible linear orderings and compatible lattice orderings, but I wonder if these are cases where this technique always converges.

Suppose that $$\mathcal{L},\mathcal{M}$$ are algebraic languages. All algebraic structures in this post are assumed to be finite.

We say that an $$\mathcal{M}$$-structure $$\mathcal{X}$$ is $$\mathcal{M}\setminus\mathcal{L}$$-close to an $$\mathcal{M}$$-structure $$\mathcal{Y}$$ if $$\mathcal{X},\mathcal{Y}$$ have the same underlying set $$X$$ and there exists a function symbol $$f\in\mathcal{M}\setminus\mathcal{L}$$ of arity $$n\geq 0$$ along with $$x_{1},\dots,x_{n}\in X$$ where $$g^{\mathcal{X}}=g^{\mathcal{Y}}$$ whenever $$g\in\mathcal{M}\setminus\{f\}$$ and where $$f^{\mathcal{X}}(y_{1},\dots,y_{n})=f^{\mathcal{Y}}(y_{1},\dots,y_{n})$$ whenever $$(y_{1},...,y_{n})\neq(x_{1},...,x_{n})$$. In other words, $$\mathcal{X}$$ is $$\mathcal{M}\setminus\mathcal{L}$$-close to $$\mathcal{Y}$$ precisely when $$\mathcal{X}$$ and $$\mathcal{Y}$$ differ only on at most one input on one fundamental operation.

Suppose that $$u_{1},\dots,u_{n},v_{1},\dots,v_{n}$$ are terms in the language $$\mathcal{M}$$. Suppose that $$\alpha_{1},\dots,\alpha_{n}$$ are natural numbers. Let $$u=(u_{1},\dots,u_{n}),v=(v_{1},\dots,v_{n}),\alpha=(\alpha_{1},\dots,\alpha_{n})$$. Let $$\mathcal{X}$$ be a $$\mathcal{M}$$-structure. Let $$\beta_{i}$$ be the cardinality of the set of all all $$x_{1},\dots,x_{r}$$ such that $$u_{i}^{\mathcal{X}}(x_{1},\dots,x_{r})\neq v_{i}^{\mathcal{X}}(x_{1},\dots,x_{r})$$. Then the $$(u,v,\alpha)$$-score of $$\mathcal{X}$$ is the sum $$\alpha_{1}\beta_{1}+\dots+\alpha_{n}\beta_{n}$$.

We say that an algebra $$\mathcal{X}$$ is a local $$(u,v,\alpha)$$ minimum over $$\mathcal{L}$$ if whenever $$\mathcal{Y}$$ is $$\mathcal{M}\setminus\mathcal{L}$$-close to $$\mathcal{X}$$ and $$\mathcal{X}$$ has $$(u,v,\alpha)$$-score $$\beta_{\mathcal{X}}$$ and $$\mathcal{Y}$$ has $$(u,v,\alpha)$$-score $$\beta_{\mathcal{Y}}$$ then $$\beta_{\mathcal{X}}\leq\beta_{\mathcal{Y}}$$.

Then we say that $$(\mathcal{R},u,v,\alpha)$$ is convergent if the only algebras $$\mathcal{X}$$ with $$\mathcal{X}|_{\mathcal{L}}=\mathcal{R}$$ that are local $$(u,v,\alpha)$$ minimum over $$\mathcal{L}$$ are the algebras that satisfies the identities $$u_{1}=v_{1},\dots,u_{n}=v_{n}$$.

If $$(\mathcal{R},u,v,\alpha)$$ is convergent, then the following algorithm may be used to construct algebras $$\mathcal{X}$$ that satisfy the identities $$u_{1}=v_{1},\dots,u_{n}=v_{n}$$ and where $$\mathcal{R}=\mathcal{X}|_{\mathcal{L}}$$.

Step $$0$$: Let $$\mathcal{X}_{0}$$ be randomly generated algebra such that $$\mathcal{R}=\mathcal{X}_{0}|_{\mathcal{L}}$$.

Step $$n+1$$: If $$\mathcal{X}_{n}$$ satisfies the identities $$u_{1}=v_{1},\dots,u_{n}=v_{n}$$, then return $$\mathcal{X}_{n}$$. Otherwise, let $$\mathcal{X}_{n+1}$$ be an algebra which is $$\mathcal{M}\setminus\mathcal{L}$$ close to $$\mathcal{X}_{n+1}$$ but where the $$(u,v,\alpha)$$-score of $$\mathcal{X}_{n+1}$$ is lower than the $$(u,v,\alpha)$$-score of $$\mathcal{X}_{n}$$. One may need to do a brute force search to find a suitable algebra $$\mathcal{X}_{n+1}$$.

What are some examples of convergent tuples $$(\mathcal{R},u,v,\alpha)$$?

Example:

Let $$u_{1}(x,y)=x\wedge y,u_{2}(x,y)=x\vee y,u_{3}(x)=x\wedge x,u_{4}(x)=x\vee x,u_{5}(x,y,z)=(x\wedge y)\wedge z,u_{6}(x,y,z)=(x\vee y)\vee z,u_{7}(x,y)=(x\wedge y)\vee x,u_{8}(x,y)=(x\vee y)\wedge x ,v_{1}(x,y)=y\wedge x,v_{2}(x,y)=y\vee x,v_{3}(x)=x,v_{4}(x)=x,v_{5}(x,y,z)=x\wedge(y\wedge z),v_{6}(x,y,z)=x\vee(y\vee z),v_{7}(x,y)=x,v_{8}(x,y)=x$$. Let $$u=(u_{1},...,u_{8}),v=(v_{1},...,v_{8})$$.

An algebra $$(X,\wedge,\vee)$$ is a lattice if and only if it satisfies the identities $$u_{i}=v_{i}$$ for $$i\in\{1,\dots,8\}$$.

Define $$\alpha=(n^{-2},n^{-2},n^{-1},n^{-1},n^{-3},n^{-3},n^{-2},n^{-2})$$. Then the $$(u,v,\alpha)$$-score of an algebra $$(X,\vee,\wedge)$$ is the sum $$P_{1}+....+P_{n}$$ where $$P_{i}$$ is the probability that $$u_{i}(\mathbf{x})\neq v_{i}(\mathbf{x})$$ for randomly selected inputs $$\mathbf{x}$$.

• Ugh, that's a lot of ellipsis. Can you give an example with groups (where the inverse is one of the operations)? Jan 27, 2019 at 8:04
• The quantifier in "there is some $f \in \mathcal{M} \setminus \mathcal{L}$" is unclear. Did you mean "there exists $f \in \mathcal{M} \setminus \mathcal{L}$" or "for every $f \in \mathcal{M} \setminus \mathcal{L}$"? Actually, that entire sentence is unclear. "Along with where"? Jan 27, 2019 at 8:05
• For the example, I chose lattices instead of groups since this technique for constructing algebras works better for lattices than for groups. I had a hard time making an example that is more readable than the question itself. Jan 27, 2019 at 16:43