Skip to main content
2 of 3
deleted 10 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 algebraic structure $\mathcal{X}^{\mathcal{M}}$ is $\mathcal{M}\setminus\mathcal{L}$-close to $\mathcal{Y}^{\mathcal{M}}$ 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})$.

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)$?