heap


A heap is a non-empty set H with a ternary operation f:H3H, such that

  1. 1.

    f(f(r,s,t),u,v)=f(r,s,f(t,u,v)) for any r,s,t,u,vH, and

  2. 2.

    f(r,s,s)=f(s,s,r)=r for any r,sH.

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

Given a group G, if we define f:G3G by

f(a,b,c)=ab-1c,

then (G,f) is a heap, for f(f(r,s,t),u,v)=(rs-1t)u-1v=rs-1(tu-1v)=f(r,s,f(t,u,v)), and f(r,s,s)=rs-1s=r=ss-1r=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 (H,f), then (H,) is a group for some binary operationMathworldPlanetmath on H, such that f(a,b,c)=ab-1c.

Proof.

Pick an arbitrary element rH, and define a binary operation on H by

ab:=f(a,r,b).

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

First, is associative: (ab)c=f(f(a,r,b),r,c)=f(a,r,f(b,r,c))=a(bc). This shows that (H,) is a semigroupPlanetmathPlanetmath. Second, r is an identityPlanetmathPlanetmathPlanetmath with respect to : ar=f(a,r,r)=a and ra=f(r,r,a)=a, showing that (H,) is a monoid. Finally, given aH, the element b=f(r,a,r) is a two-sided inverseMathworldPlanetmath of a: ab=f(a,r,b)=f(a,r,f(r,a,r))=f(f(a,r,r),a,r)=f(a,a,r)=r and ba=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,) is a group.

Finally, by a direction computation, we see that ab-1c=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 elementMathworldPlanetmath for the group. In other words, one can think of a heap as a group where the designation of a multiplicative identityPlanetmathPlanetmath 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. 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 subgroupMathworldPlanetmathPlanetmath 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)  and  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)H, whence H is a subheap of G. On the other hand, suppose that H is a subheap of G, and let K={rs-1r,sH}. We want to show that K is a subgroup of G (and hence H is a coset of K). Certainly e=rr-1K. If rs-1K, then sr-1=(rs-1)-1K. Finally, if rs-1 and tu-1 are both in K, then rs-1tu-1=f(r,s,t)u-1, which is in K because both f(r,s,t) and u are in H. ∎

  2. 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(ut-1s)-1v=rs-1tu-1v=f(rs-1t,u,v)=f(f(r,s,t),u,v).
  3. 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. 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 rH. 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.

References

  • 1 R. H. Bruck, A Survey of Binary Systems, Springer-Verlag, 1966
  • 2 H. Prüfer, Theorie der Abelschen Gruppen, Math. Z. 20, 166-187, 1924
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