heap

A heap is a non-empty set $H$ with a ternary operation $f:H^3\to H$, such that

1. $f(f(r,s,t),u,v)=f(r,s,f(t,u,v))$ for any $r,s,t,u,v\in H$, and

2. $f(r,s,s)=f(s,s,r)=r$ for any $r,s\in H$.

Heaps and groups are intimately related. Every group has the structure of a heap:

Given a group $G$, if we define $f:G^3\to G$ by

$$f(a,b,c)=a{b}^{-1}c,$$

then $(G,f)$ is a heap, for $f(f(r,s,t),u,v)=(r{s}^{-1}t)u^{-1}v=r{s}^{-1}(t{u}^{-1}v)=f(r,s,f(t,u,v))$, and $f(r,s,s)=r{s}^{-1}s=r=s{s}^{-1}r=f(s,s,r)$.

The associated heap structure on a group is the associated heap of the group.

Conversely, every heap can be derived this way:

Proposition 1.

Given a heap $\mathrm{(}H\mathrm{,}f\mathrm{)}$, then $\mathrm{(}H\mathrm{,}\mathrm{\cdot }\mathrm{)}$ is a group for some binary operation $\mathrm{\cdot }$ on $H$, such that $f\mathit{}\mathrm{(}a\mathrm{,}b\mathrm{,}c\mathrm{)}\mathrm{=}a\mathrm{\cdot }{b}^{\mathrm{-}\mathrm{1}}\mathrm{\cdot }c$.

Proof.

Pick an arbitrary element $r\in H$, and define a binary operation $\cdot$ on $H$ by

$$a\cdot b:=f(a,r,b).$$

We next show that $(H,\cdot )$ is a group.

First, $\cdot$ is associative: $(a\cdot b)\cdot c=f(f(a,r,b),r,c)=f(a,r,f(b,r,c))=a\cdot (b\cdot c)$. This shows that $(H,\cdot )$ is a semigroup. Second, $r$ is an identity with respect to $\cdot$: $a\cdot r=f(a,r,r)=a$ and $r\cdot a=f(r,r,a)=a$, showing that $(H,\cdot )$ is a monoid. Finally, given $a\in H$, the element $b=f(r,a,r)$ is a two-sided inverse of $a$: $a\cdot b=f(a,r,b)=f(a,r,f(r,a,r))=f(f(a,r,r),a,r)=f(a,a,r)=r$ and $b\cdot a=f(b,r,a)=f(f(r,a,r),r,a)=f(r,a,f(r,r,a))=f(r,a,a)=r$, hence $(H,\cdot )$ is a group.

Finally, by a direction computation, we see that $a\cdot b^{-1}\cdot c=af(r,b,r)c=f(a,r,f(r,b,r))c=f(f(a,r,r),b,r)c=f(a,b,r)c=f(f(a,b,r),r,c)=f(a,b,f(r,r,c))=f(a,b,c)$. ∎

From the proposition above, we see that any element of $H$ can be chosen, so that the associated group operation turns that element into an identity element for the group. In other words, one can think of a heap as a group where the designation of a multiplicative identity is erased, in much the same way that an affine space is a vector space without the origin (additive identity):

An immediate corollary is the following: for any element $r$ in a heap $(H,f)$, the equation

$$f(x,y,z)=r$$

in three variables $x,y,z$ has exactly one solution in the remaining variable, if two of the variables are replaced by elements of $H$.

Remarks.

1. A heap is also known as a flock, due to its application in affine geometry, or as an abstract coset, because, as it can be easily shown, a subset $H$ of a group $G$ is a coset (of a subgroup of $G$) iff it is a subheap of $G$ considered as a heap (see example above).

   Proof.

   First, notice that we have two equations

   $$f(ar,as,at)=af(r,s,t)\mathit{\hspace{1em}\hspace{1em}}\text{and}\mathit{\hspace{1em}\hspace{1em}}f(ra,sa,ta)=f(r,s,t)a.$$

   From this, we see that if $H=aK$ or $H=Ka$ for some subgroup $K$ of $G$, then $f(H,H,H)\subseteq H$, whence $H$ is a subheap of $G$. On the other hand, suppose that $H$ is a subheap of $G$, and let $K=\{r{s}^{-1}\mid r,s\in H\}$. We want to show that $K$ is a subgroup of $G$ (and hence $H$ is a coset of $K$). Certainly $e=r{r}^{-1}\in K$. If $r{s}^{-1}\in K$, then $s{r}^{-1}={(r{s}^{-1})}^{-1}\in K$. Finally, if $r{s}^{-1}$ and $t{u}^{-1}$ are both in $K$, then $r{s}^{-1}t{u}^{-1}=f(r,s,t)u^{-1}$, which is in $K$ because both $f(r,s,t)$ and $u$ are in $H$. ∎

2. More generally, a structure $H$ with a ternary operation $f$ satisfying only condition $1$ above is known as a heapoid, and a heapoid satisfying the condition

   $$f(f(r,s,t),u,v)=f(r,f(u,t,s),v)$$

   is called a semiheap. Every heap is a semiheap, for, by Proposition 1 above:

   $$f(r,f(u,t,s),v)=r{(u{t}^{-1}s)}^{-1}v=r{s}^{-1}t{u}^{-1}v=f(r{s}^{-1}t,u,v)=f(f(r,s,t),u,v).$$

3. Let $(H,f)$ be a heap. Then $(H,f)$ is a $3$-group (http://planetmath.org/PolyadicSemigroup) iff $f(u,t,s)=f(s,t,u)$. First, if $(H,f)$ is a $3$-group, then $f$ is associative, so $f(r,f(u,t,s),v)=f(r,f(s,t,u),v)$ since a heap is a semiheap. By the corollary above, we get the equation $f(u,t,s)=f(s,t,u)$. On the other hand, the equation shows that $f$ is associative, and together with the corollary, $(H,f)$ is a $3$-group.

4. Suppose now that $(H,f)$ is a $3$-group such that $f(u,t,s)=f(s,t,u)$. Then $(H,f)$ is a heap iff $f(r,r,r)=r$ for all $r\in H$. The first condition of a heap is automatically satisfied since $f$ is associative. Now, if $(H,f)$ is a heap, then $f(r,r,r)=r$ by condition 2. Conversely, $f(r,s,s)=f(s,s,r)=t$ by the given equation above. So $f(s,t,s)=f(s,f(r,s,s),s)=f(s,r,f(s,s,s))=f(s,r,s)$. As a $3$-group, it has a covering group, so $t=r$ as a result.

Title	heap
Canonical name	Heap1
Date of creation	2013-03-22 18:41:50
Last modified on	2013-03-22 18:41:50
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	9
Author	CWoo (3771)
Entry type	Definition
Classification	msc 20N10
Synonym	flock
Synonym	abstract coset
Defines	semiheap
Defines	heapoid