Consider the following exercise.

Let the set $G = \{0, 1, 2, 3, 4, 5, 6, 7\}$. Suppose there is a group (Called The Nim Group) operation $\ast$ on $G$ that satisfies the following two conditions:

(a) $a\ast b \geq a + b$ for all $a, b \in G$,

(b) $a\ast a = 0$ for all $a \in G$.

Construct the multiplication table for $G$.

The exercise I found him in a document but I have a doubt if indeed the set $ G $ with the operation defined as a group.

I have a doubt with this exercise. Building the table until I get the following

enter image description here

My question is not how to continue, as should repeat elements in rows (being $ G $ a group) then it must meet that $ 1 \ast 7 = 2$ but if this is true not satisfy the condition (b) $a\ast b \geq a + b $. I appreciate your support.

  • 2
    $\begingroup$ Are you sure (a) is supposed to be regular addition, which suffices to fill out the whole table? I believe it should be bitwise XOR, in which case (b) is satisfied but redundant. I don't see how (b) gives you $a*b \ge a+b$-we don't have any order on this group. $\endgroup$ – Ross Millikan Sep 18 '13 at 17:00
  • 2
    $\begingroup$ With your new condition (a), how can $6 * 7 \ge 13$? $\endgroup$ – Ross Millikan Sep 18 '13 at 17:01
  • $\begingroup$ The group operation in NIM is usually defined recursively as follows $$ ab=\operatorname{mex}\left(\{a'*b\mid a'<a\}\cup \{ab'\mid b'<b\}\right). $$ Here $\operatorname{mex}(S)$ is defined for all proper subsets of $\mathbb{N}$ and means the smallest non-negative integer not in the set $S$ (=Minimum EXcluded number). So $0*0=0$ simply because both sets on the r.h.s. are empty. But then $0*1=\operatorname{mex}(\{0\})=1=1*0$, $1*1=\operatorname{mex}(\{1\})=0$, $0*2=\operatorname{mex}(\{0,1\})=2=2*0$, $1*2=3$, $2*2=0$ et cetera. $\endgroup$ – Jyrki Lahtonen Sep 18 '13 at 17:01
  • 2
    $\begingroup$ Can you name/link the document you found this in? $\endgroup$ – Mark S. Nov 16 '13 at 16:38
  • 2
    $\begingroup$ @RoinerSeguraCubero I think (a) should be $a*b\leq a+b$ $\endgroup$ – zed111 Feb 3 '15 at 17:49

As I'm holding the book "Contemporary Abstract Algebra" of Joseph A.Gallian 2nd edition, on exercise 27 of chapter 3, I looked up for the Nim Group, then I found your question.

So the question in the book is exactly the same as you wrote, but instead of your first condition, the condition in the exercise is $a*b\leq a+b$, which makes more sense as you pointed out.

So I think your document has a typo.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.