Recent MathOverflow Questions

Reversible varieties

Math Overflow Recent Questions - Sat, 01/26/2019 - 19:57

We say that a variety $V$ is reversible if for each $n>0$ and $n$-ary fundamental operation $f$, there is some $m\geq n$ and $r$ along with terms $T_{2},\dots,T_{r},S_{1},\dots,S_{m}$ such that $G,H$ are inverses where

  1. $G(x_{1},\dots,x_{m})=(f(x_{1},\dots,x_{n}),T_{2}(x_{1},\dots,x_{m}),\dots,T_{r}(x_{1},\dots,x_{m})),$ and

  2. $H(y_{1},\dots,y_{r})=(S_{1}(y_{1},\dots,y_{r}),\dots,S_{m}(y_{1},\dots,y_{r})).$

The following varieties are reversible:

  1. Groups.

  2. Racks,quandles, and biracks.

  3. Jonsson-Tarski algebras.

  4. The variety consisting of all algebras $(X,f,g)$ where $f,g:X\rightarrow X$ are inverse functions.

  5. The variety of all heaps.

  6. The variety of quasigroups.

  7. The variety $K_{X}$ where $K_{X}$ is generated by the algebra $(X,\mathcal{F})$ where $\mathcal{F}$ consists of all functions $f:X^{n}\rightarrow X$ where $|f^{-1}[\{a\}]|=|f^{-1}[\{b\}]|$ for each $a,b\in X$.

  8. The variety consisting of sets without any fundamental operations.

In addition to these varieties, one can artificially create (hopefully non-trivial) reversible varieties since the fact that $G,H$ are inverses is clearly axiomatized by identities. Also, every subvariety of a reversible variety is reversible. It is therefore quite easy to contrive new reversible varieties from old ones.

If $X$ is a finite algebra in a reversible variety and $f$ is an $n$-ary fundamental operation and $a\in X$, then $$|\{(x_{1},\dots,x_{n})\in X^{n}\mid f(x_{1},\dots,x_{n})=a\}|=|X|^{n-1}.$$

Observe that the reversible varieties are the varieties consisting of algebras that are “almost groups” in the sense that one often associates these algebras with canonical groups and because these algebras feel like groups.

What are some more examples of reversible varieties that occur naturally and in practice and are not just constructed for the sole purpose of being reversible? Is there a good reference for reversible varieties?

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

Math Overflow Recent Questions - Sat, 01/26/2019 - 17:38

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

One matrix inequality

Math Overflow Recent Questions - Sat, 01/26/2019 - 14:00

Assume $A$ is a $n\times n$ positive matrix, whose eigenvalues are $a_1\ge a_2\ldots \ge a_n>0;$ $B$ is a $p \times p$ positive matrix, whose eigenvalues are $b_1\ge b_2\ldots \ge b_p>0.$ For $n\times p$ matrix $X$ with $n\ge p,$

Question: Is there a similar inequality, such that $$|X'AX+B|\ge c(X)\prod_{i=1}^p(a_i+b_{p-i+1}),$$ or $$|X'AX+B|\ge c(X)\prod_{i=1}^p(a_{p-i+1}+b_i)$$ or something else.

where $c(X)$ is constant, only denpends on $X.$

Coordinate free expression for the determinant of a $2 \times 2$ matrix

Math Overflow Recent Questions - Sat, 01/26/2019 - 07:39

Let $E\rightarrow X$ be a rank two vector bundle on a variety $X$. How can one write an abstract map $Sym^2(E)\rightarrow (\wedge^2 E)^{\otimes 2}$ that in local coordinates, when we fix a frame of $E$, gives the determinant of a $2\times 2$ symmetric matrix?

Pages

Subscribe to curious little things aggregator