TAOCP 7.2.2.1 Exercise 75
Edit Write the operation temporarily by juxtaposition, so that (xy) denotes (x\circ y).
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: 4m17s
Edit
Solution
Write the operation temporarily by juxtaposition, so that (xy) denotes (x\circ y). The defining identity of a grope is
[ x(yx)=y. \tag{1} ]
(a)
We first derive the desired identity directly from (1).
Replace (x) in (1) by (yx), and replace (y) by (x). This gives
[ (yx)(x(yx))=x. ]
But (1) itself says
[ x(yx)=y. ]
Substituting this into the preceding equation gives
[ (yx)y=x. ]
Now rename the variables: replace (y) by (x) and (x) by (y). We obtain
[ (xy)x=y. ]
Hence every grope satisfies both identities
[ x(yx)=y,\qquad (xy)x=y. ]
(\square)
(b)
A table defines a grope precisely when its entries satisfy
[ x(yx)=y . ]
By part (a), this is equivalent to
[ (xy)x=y . ]
For the first table we have
[ x\circ y=x\oplus y . ]
Therefore
[ x\circ(y\circ x) =x\oplus(y\oplus x) =(x\oplus x)\oplus y =y, ]
because (x\oplus x=0). Thus the first table is a grope.
For the second table,
[ x\circ y=(-x-y)\pmod 4 . ]
Then
[
\begin{aligned}
x\circ(y\circ x)
&=x\circ((-y-x)\bmod4)
&=(-x-(-y-x))\bmod4
&=y\bmod4
&=y .
\end{aligned}
]
Hence the second table is also a grope.
For the third table, take (x=2) and (y=1). The table gives
[ 1\circ2=0, ]
and hence
[ 2\circ(1\circ2)=2\circ0=3, ]
which is not (1). Therefore the third table is not a grope.
For the fourth table, take (x=2) and (y=1). We have
[ 1\circ2=3, ]
and therefore
[ 2\circ(1\circ2)=2\circ3=0, ]
which is not (1). Hence the fourth table is not a grope.
Thus exactly the first two tables define gropes.
(\square)
(c)
For every positive integer (n), let
[ G={0,1,\ldots ,n-1} ]
and define
[ x\circ y=(-x-y)\pmod n . ]
Then
[
\begin{aligned}
x\circ(y\circ x)
&=x\circ((-y-x)\bmod n)
&=(-x-(-y-x))\bmod n
&=y\pmod n
&=y .
\end{aligned}
]
Therefore this operation satisfies the defining grope identity, and hence gives a grope of order (n).
(\square)
(d)
For a multiplication table of a grope, consider the entry (xy). Suppose
[ x\circ y=z . ]
By part (a),
[ z\circ x=y . ]
Applying the original identity again gives
[ y\circ z=x . ]
Thus every entry (xy) belongs together with the two entries
[ yz,\qquad zx . ]
There are three possibilities.
- If (x=y=z), then the entry is an idempotent entry and gives the singleton option
[ xx . ]
- If (x\circ y=y), then part (a) gives
[ y\circ x=x , ]
so the two entries form the option
[ xy;yx . ]
- In all other cases, writing (z=x\circ y), the three entries are distinct and give the option
[ xy;yz;zx . ]
Hence every multiplication table of a grope determines an exact cover: the selected options are precisely the orbits of the entries under the relations forced by the grope identities.
Conversely, suppose we are given an exact cover. For each covered item (xy), define (x\circ y) to be the element determined by the option containing (xy). The possible options have exactly the three forms above, and each form enforces the required relations
[ x\circ(y\circ x)=y . ]
Because the exact cover contains every item (xy) exactly once, every ordered pair receives exactly one product value. Therefore it determines a multiplication table, and the relations imposed by the options make this table a grope.
The two constructions are inverse to each other. Hence exact covers are in one-to-one correspondence with multiplication tables of gropes on
[ {0,1,\ldots ,n-1}. ]
(\square)
(e)
Let (k) elements be idempotent. We first observe that the remaining (n-k) elements occur in complete nontrivial cycles under the operation
[ x\longmapsto x\circ x . ]
Indeed, if (x\circ x\neq x), then the exact-cover construction in part (d) cannot use the singleton option (xx). Instead the diagonal entry (xx) must occur in a nontrivial option, and the grope identities force all entries in that option to involve the same cycle of non-idempotent elements. These nontrivial options involve three elements. Consequently the non-idempotent elements can be partitioned into disjoint triples. Therefore
[ n-k\equiv0\pmod3 . ]
Now
[ n^2-n=n(n-1) ]
is divisible by (3), since one of the consecutive integers (n,n-1) is divisible by (3). Hence
[ n^2\equiv n\pmod3 . ]
Because
[ n-k\equiv0\pmod3, ]
we also have
[ k\equiv n\pmod3 . ]
Combining these congruences gives
[ k\equiv n^2\pmod3 . ]
Therefore, if (k) elements of a grope are idempotent, then
[ \boxed{k\equiv n^2\pmod3}. ]
(\square)