Skip to main content
3 of 3
added 1043 characters in body

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}$.