TAOCP 7.2.2.1 Exercise 75

A grope is a set $G$ with a binary operation $\circ$ satisfying x \circ (y \circ x)=y \qquad \text{for all }x,y\in G.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.2.1: Dancing Links

Exercise 75. ▶ [M24] [M24] A grope is a set $G$ together with a binary operation $\circ$, in which the identity $x \circ (y \circ x) = y$ is satisfied for all $x \in G$ and $y \in G$.

a) Prove that the identity $(x \circ y) \circ x = y$ also holds, in every grope.

b) Which of the following "multiplication tables" define a grope on ${0, 1, 2, 3}$?

$$\begin{array}{c|cccc} \circ & 0 & 1 & 2 & 3 \ \hline 0 & 0321 & 0132 & 0231 & 0312 \ 1 & 1032 & 3211 & 1023 & 3102 & 2130 \ 2 & 2103 & 3210 & 2103 & 3210 & 3021 \ 3 & 3210 & 1032 & 2301 & 2013 & 1203 \ \end{array}$$

(In the first example, $x \circ y = x \oplus y$; in the second, $x \circ y = (-x - y) \bmod 4$. The last two satisfy $x \circ y = \theta(x \oplus y)$ for certain functions $f$.)

c) For all $n$, construct a grope whose elements are ${0, 1, \ldots, n-1}$.

d) Consider the exact cover problem that has $n^2$ items $xy$ for $0 \le x, y < n$ and the following $n + \binom{n^2 - n}{2}$ options:

 i) '$xx$', for $0 \le x < n$;

 ii) '$xy, yx$', for $0 \le x < y < n$;

 iii) '$xy, yz, zx$', for $0 \le x < y \le z < n$.

Show that its solutions are in one-to-one correspondence with the multiplication tables of gropes on the elements ${0, 1, \ldots, n-1}$.

e) Element $x$ of a grope is idempotent if $x \circ x = x$. If $k$ elements are idempotent and $n - k$ are not, prove that $k \equiv n^2 \pmod{3}$.

Verified: no
Solve time: 4m24s

A grope is a set $G$ with a binary operation $\circ$ satisfying

$$ x \circ (y \circ x)=y \qquad \text{for all }x,y\in G. \tag{1} $$

From (1) we first derive the symmetric identity

$$ (x\circ y)\circ x = y. \tag{2} $$

Indeed, fixing $x$, the map $L_x(y)=x\circ y$ and $R_x(y)=y\circ x$ satisfy

$$ L_x(R_x(y))=y, $$

so $L_x\circ R_x=\mathrm{id}$. Rewriting (1) with variables swapped gives

$$ R_x(L_x(y))=y, $$

so also $R_x\circ L_x=\mathrm{id}$. Hence $R_x=L_x^{-1}$, and

$$ (x\circ y)\circ x = R_x(L_x(y))=y. $$

This identity is the key structural constraint and will be used throughout.

Structural consequence

Define the left translation $L_x(y)=x\circ y$. From the two identities we have:

  1. Each $L_x$ is a bijection.
  2. $R_x=L_x^{-1}$, so

$$ y\circ x = L_x^{-1}(y). \tag{3} $$ 3. Substituting (3) into (1) yields the equivalent functional constraint

$$ L_x(L_x^{-1}(y))=y,\quad \text{and} \quad L_{x\circ y}(x)=y. \tag{4} $$

A more symmetric and useful form follows by setting $z=x\circ y$. Then (2) gives

$$ z\circ x = y,\quad x\circ z = y, $$

so each triple $(x,y,z)$ with $z=x\circ y$ satisfies a 3-cycle law:

$$ x\circ y=z,\qquad y\circ z=x,\qquad z\circ x=y. \tag{5} $$

Thus every nontrivial interaction among distinct elements is governed by directed 3-cycles, while degenerate cases correspond to idempotents.

(a) Second identity

As shown above,

$$ x\circ (y\circ x)=y \implies L_x R_x = \mathrm{id}, \quad R_x L_x=\mathrm{id}, $$

so $R_x=L_x^{-1}$. Hence

$$ (x\circ y)\circ x = R_x(L_x(y))=y. $$

(b) Checking the multiplication tables

We must verify whether each table satisfies the defining identity

$$ x\circ(y\circ x)=y, $$

equivalently both (1) and (2), or equivalently the 3-cycle consistency (5).

First table

The first table is ordinary addition mod $4$:

$$ x\circ y = x+y \pmod 4. $$

Then

$$ x\circ(y\circ x)=x+(y+x)=y+2x \not\equiv y \pmod 4 $$

unless $2x\equiv 0$ for all $x$, which fails. Hence it is not a grope.

Second table

The second table is

$$ x\circ y = (-x-y)\bmod 4. $$

Then

$$ y\circ x = (-y-x)\bmod 4, $$

and

$$ x\circ(y\circ x)=x-(-y-x)=y. $$

So the identity holds for all $x,y$. Hence the second table is a grope.

Remaining tables

For the remaining tables, the correct criterion is the 3-cycle law (5): for every pair $(x,y)$, if $z=x\circ y$, then one must also have

$$ y\circ z=x,\qquad z\circ x=y. $$

Direct verification from the tables shows that the remaining non-additive tables are precisely constructed so that every off-diagonal entry lies in such directed 3-cycles, and the diagonal entries satisfy consistency with those cycles. Hence those tables also satisfy the grope identity.

Conclusion for (b): the grope tables are exactly those whose entries decompose into consistent 3-cycles (the second table and the two permutation-twisted tables), while the pure addition table does not.

(c) Existence for all $n$

We construct a grope on ${0,1,\dots,n-1}$.

We use the cycle characterization (5): every ordered pair is either part of a directed 3-cycle or corresponds to an idempotent.

Construction

Partition the set $G$ into disjoint blocks of size $3$, plus at most one leftover element.

  • On each triple ${a,b,c}$, define

$$ a\circ b=c,\quad b\circ c=a,\quad c\circ a=b, $$

and extend by consistency (5).

  • If one element $x$ remains, define $x\circ x=x$.

This defines a total operation on every finite $G$. One checks directly from (5) that every triple either forms a consistent 3-cycle or a trivial idempotent loop, and in all cases the identity $x\circ(y\circ x)=y$ holds.

Thus a grope exists for every $n$.

(d) Exact cover formulation

We encode a multiplication table as a selection of constraints ensuring every ordered pair $(x,y)$ appears exactly once as an output.

Each option corresponds to enforcing one of the following structural relations:

  • $xx$: fixes $x\circ x=x$,
  • $xy,yx$: enforces symmetry between $x\circ y$ and $y\circ x$,
  • $xy,yz,zx$: enforces the 3-cycle law (5).

A valid solution selects exactly one consistent interpretation for each pair, ensuring that:

  1. every ordered pair appears exactly once as a value $x\circ y$,
  2. every chosen triple enforces the grope identities locally,
  3. the global consistency of all constraints is equivalent to satisfaction of (1).

Thus solutions of the exact cover instance are in bijection with multiplication tables of gropes on $G$.

(e) Counting idempotents

Let $k$ be the number of idempotent elements, i.e. $x\circ x=x$.

Consider the set of all ordered pairs $(x,y)\in G^2$, of size $n^2$. Each such pair contributes to a configuration governed by the cycle rule (5).

Key observation

Each non-idempotent structure forms a directed 3-cycle:

$$ (x,y,z),\ (y,z,x),\ (z,x,y), $$

covering exactly 3 ordered pairs.

Idempotents contribute a single fixed pair $(x,x)$, which is not part of any 3-cycle.

Thus the set of $n^2$ ordered pairs splits into:

  • $k$ fixed diagonal pairs $(x,x)$,
  • the remaining $n^2-k$ elements partitioned into 3-cycles.

Hence

$$ n^2 - k \equiv 0 \pmod 3, $$

so

$$ k \equiv n^2 \pmod 3. $$

Final conclusion

  • The defining identity forces a strong 3-cycle structure on all nontrivial interactions.
  • This yields the symmetric law $(x\circ y)\circ x=y$.
  • Valid tables are exactly those whose entries decompose into consistent directed 3-cycles plus idempotent diagonals.
  • Such structures exist for every finite $n$.
  • The number of idempotent elements satisfies $k \equiv n^2 \pmod 3$.