2
$\begingroup$

Suppose that $(X,*,1)$ satisfies the following identities: $x*(y*z)=(x*y)*(x*z),1*x=x,x*1=1$. Define the Fibonacci terms $t_{n}(x,y)$ for $n\geq 1$ by letting $$t_{1}(x,y)=y,t_{2}(x,y)=x,t_{n+2}(x,y)=t_{n+1}(x,y)*t_{n}(x,y)$$ for $n\geq 1$. We say that $(X,*,1)$ is permutative if for each $x,y\in X$, there is some $n$ where $t_{n}(x,y)=1$. If $(X,*,1)$ is permutative, then we say that $\mathrm{crit}(x)\leq\mathrm{crit}(y)$ if there is some $n\geq 0$ where $x^{n}*y=1$ where we define $x^{0}*y=y$ and $x^{n+1}*y=x*(x^{n}*y)$. We say $\mathrm{crit}(x)=\mathrm{crit}(y)$ if $\mathrm{crit}(x)\leq\mathrm{crit}(y)$ and $\mathrm{crit}(y)\leq\mathrm{crit}(x)$ and $\mathrm{crit}(x)<\mathrm{crit}(y)$ if $\mathrm{crit}(x)\leq\mathrm{crit}(y)$ and $\mathrm{crit}(x)\neq\mathrm{crit}(y)$. The ordering $\{\mathrm{crit}(x)\mid x\in X\}$ is always a linear ordering.

Define $x^{[1]}=x$ and $x^{[n+1]}=x*x^{[n]}$ for $n\geq 1$. Then it is easy to show that $x^{[n+1]}=x^{[n]}*x^{[n]}$ for all $n\geq 1$.

Suppose that $n$ is a natural number. Then does there exist a permutative algebra $(X,*,1)$ along with some $x,y\in X$ where $$\mathrm{crit}(x*y)<\mathrm{crit}(x^{[2]}*y)<\dots<\mathrm{crit}(x^{[n]}*y)?$$ What if we also require $(X,*,1)$ to be finite?

$\textbf{Remark:}$ From an affirmative answer, we can easily conclude that the free self-distributive algebra on arbitrary number of generators embeds into an inverse limit of finite self-distributive algebras, a fact whose only known proof requires very large cardinals. However, permutative algebras $(X,*,1)$ where $\mathrm{crit}(x*y)<\mathrm{crit}((x*x)*y)$ cannot arise from large cardinals.

$\endgroup$
7
  • $\begingroup$ is the inequality strict in your question? If so, how do you define strict inequality as opposed to non strict one, i.e., what is the fundamental difference between $crit(x)<crit(y)$ and $crit(x)\le crit(y)$? $\endgroup$
    – vidyarthi
    Commented Mar 2, 2019 at 11:00
  • $\begingroup$ In addition, I think your algebra is associative $\endgroup$
    – vidyarthi
    Commented Mar 2, 2019 at 11:02
  • 1
    $\begingroup$ The algebra $(X,*,1)$ is not associative whenever $|X|>1$. If $x\neq 1$, then $(x*x)*x\neq x*(x*x)$, and $\mathrm{crit}((x*x)*x)=\mathrm{crit}(x)$ while $\mathrm{crit}(x*(x*x))>\mathrm{crit}(x)$. Mathematicians need to see more examples of non-associative algebraic structures. $\endgroup$ Commented Mar 2, 2019 at 13:22
  • $\begingroup$ so, I think this is somewhat related to self distributive cryptosystems $\endgroup$
    – vidyarthi
    Commented Mar 2, 2019 at 17:57
  • 1
    $\begingroup$ If $n>5$ and $\mathrm{crit}(x^{[n]}*y)>\mathrm{crit}(x*y)$, then $x^{[n]}\neq 1$. The problem is that if $x^{[n]}\neq 1$, then $(X,*)$ must be exceedingly large. Therefore, these large algebras where $\mathrm{crit}(x^{[n]}*y)>\mathrm{crit}(x*y)$ do not serve a cryptographic purpose. The only way that I see one using permutative algebras for cryptographic purposes is to start with a finite permutative algebra $(X,*,1)$ (one could even have $|X|<100$) and an operation $t:X^{2}\rightarrow X$ where $x*t(y,z)=t(x*y,x*z)$ and produce an endomorphic Laver table out of $(X,*,1,t)$. $\endgroup$ Commented Mar 2, 2019 at 20:45

0

You must log in to answer this question.

Browse other questions tagged .