Math 433, Applied Algebra, Summer 2009
Corrections to the textbook
This document is a partial list of corrections to the book Numbers, Groups & Codes, second edition, by J. F. Humphreys and M. Y. Prest, 2007, fourth printing, Cambridge University Press. I use the following color code: red indicates errors likely to be confusing to many students; blue indicates points that may concern some students; green indicates glitches unlikely to cause confusion. For the benefit of readers with nonstandard color vision, I have additionally marked the red items with a radioactivity symbol ☢, the blue items with a caution symbol ☡ (“dangerous bend”), and the green items with a pilcrow ¶.
- Bottom of page 34
- ☡ The statement of Goldbach's
conjecture should be that every even integer greater
than 2 can be written as the sum of two prime numbers. The word
“even” is missing in the statement and in the subsequent
discussion. Evidently there are lots of odd integers, such
as 117, that cannot be
written as the sum of two prime numbers (since one of the primes
would have to be 2).
- Last paragraph on page 70
The cited URL is obsolete.
- Bottom of page 71
- ☡ The formula at the bottom of the page is not
valid without some additional restriction. The difficulty is that
the integer x might be negative, in which case the
expression mx is not an integer, and the indicated
congruence does not make sense.
One possible fix is to recast the
formula as a statement about congruence classes, for which negative
powers do make sense. Perhaps a simpler fix is to observe that the
integers x and y in equation (*) on page 71 are not
uniquely determined, and it is possible to choose x to be
positive and y to be negative; the formula at the bottom of the page
is valid for such a choice of x and y.
- Page 72
- ¶ The two cited URLs are obsolete. As of August 2, 2022,
the page about challenges in factoring
and the RSA company homepage is http://www.rsa.com.
- Page 76, exercise 1.6.10(ii)
- ☢ The number 213 in the
hint should be instead the prime number 223.
- Page 91, Example 2
- ☡ The last line of the example should conclude
“s(n)≠s(m)” (the equality sign in the book should be negated).
- Page 92, Definitions following Example 2
- ¶ The symbol idx (lowercase x) should be
idX (uppercase X). The error carries over to
Example 4 on page 94. The corresponding notation is correct,
however, on page 95.
- Page 102
- ¶ The symbol ℝ+ is used with two different meanings in Exercises 2 and 5. You can ignore the symbol and read the words.
- Page 113, Example 4
- ☡ The words “similar” and “equivalent” are
reversed from their usual meanings in linear algebra (and this
reversal carries over to Exercise 10 on page 117). In the
standard terminology that you may have learned in Math 304 or
Math 323, two square matrices A and B are similar if there
exists an invertible matrix P such that
B=P-1AP. Similar matrices represent the same linear operator with respect to different bases. Two matrices are row equivalent
if one can be converted to the other through a sequence of
elementary row operations. Two matrices are
equivalent if one can be converted to the other through
row and column operations. It is a theorem that matrices A and B are
equivalent in this sense if and only if there are invertible
matrices P and Q such that B=P-1AQ; also, matrices
A and B are equivalent if and only if they have the same rank.
- Page 139, three lines from the bottom of the page
- ☡ In the formula, one of the instances of “p” should be “q” instead.
- Page 144, last line
- ☢ The expression 5(n3+n3) should be instead 5(n4+n). In the first line on the next page, the equation n3+n2=n2(n+1) should be n4+n=n(n3+1). Two lines later, replace the parenthetical remark “in which case 2 divides n+1” by “in which case n3 is odd too, so 2 divides n3+1”.
- Page 149
- ¶ In the fourth line of the proof, line labeled “(Id)”, for “indentity” read “identity”.
- Page 158, Exercise 3
- ☡ For “Example 4.1.1” read “Exercise 4.1.1”.
- Page 160
- ¶ Three lines from the bottom of the page, a period is missing after the ellipsis dots.
- Page 164
- ¶ In the first line of the definition, there is a comma missing after the ellipsis dots in the argument of the function Δ. Two lines later, there should be a comma at the end of the displayed equation.
- Page 165
- ¶ In the line preceding the definition, the word “is” should be “in”.
- Page 167
- ¶ In the fourth line, for “permutatations” read “permutations”.
- Page 171, Example 1
- ¶ In the first line, insert a comma following “(ℤ,+)”.
- Page 175, Example 1
- ¶ At the end of the fifth line, delete the period after the word “that”.
- Page 178
- ¶ Add either a period or a colon at the end of the line preceding the table.
- Page 181, third paragraph
- ¶ In the sixth line, for “difficultly” read “difficulty”.
- Page 190
- ¶ Two lines from the bottom of the page, “(using R2))” should be “(using (R2))” with balanced parentheses.
- Page 196
- ☢ In Exercise 3(iv), the formula should say XΔY=(X\Y)∪(Y\X) with a union symbol on the right-hand side. The correct formula for the symmetric difference can be found in Exercise 2.1.4 on page 86.
- ☢ In Exercise 4(i), the formula should say x(-y)=-(xy)=(-x)y. In Exercise 4(ii), it is being assumed that the ring has a multiplicative identity element, which is denoted by 1.
- Page 197, Exercise 10
- ☡ The parenthetical remarks are confusing. In part (i), the 0 on the left-hand side is the scalar zero, but the 0 on the right-hand side is the zero vector. In part (ii), the 0 on both sides is the zero vector. Also, you should do part (iv) before part (iii).
- Page 198, Exercise 16(a)(ii)
- ☡ In answering part (i), you must already have realized that the elements 0 and 1 in the Boolean algebra are the zero element in the ring and the multiplicative identity element in the ring. Perhaps the point of the question is to identity what these elements represent in the context of algebras of sets (mentioned in the parenthetical remark).
- Page 199, Exercise 16(b)
- ☢ To specify a Boolean algebra, it is not enough to define the ∧ and ∨ operations (“meet” and “join”): the ¬ operation (“complement”) is needed too. An appropriate definition here is to set ¬a equal to 1+a, where 1 denotes the multiplicative identity (assumed to exist).
- Page 201, Example
- ☡ Throughout the paragraph, the words “right” and “left” are interchanged.
- Page 202
- ¶ In the fourth line of the proof, the symbol “G” is in the wrong font.
- Page 203, Example 2
- ☢ The proposed solution has two errors. The equation ax=b-1cb should say ax=b-1cb-1, and the final equation x=a-1b-1cb should say x=a-1b-1cb-1.
- Page 203, Corollary 5.1.2
- ¶ Notice that the last part of the statement is Exercise 4.3.2 on page 183.
- Page 203, second paragraph from the bottom of the page
- ☡ In the fourth line, for “a=b” read “a=e”.
- Page 204
- ¶ In the first line of the paragraph following the Definition, insert a comma after “for example”.
- ☡ In the proof of Theorem 5.1.3, the statement “as we verified above, gh=hg implies h-1g-1=g-1h-1” is in the wrong place: it is justification for the second step, not the third step. The “above” refers back to the Example on page 201.
- ☡ The last line on the page is incomplete. The expression (g-1)r equals g-r by definition if r is positive (or zero). If r is negative, say r=-k, then the expression equals ((g-1)-1)k, and this quantity reduces to the desired gk because (g-1)-1=g by Corollary 5.1.2.
- Page 205
- ¶ In the first line on the page, “4.2.1” means “Theorem 4.2.1”.
- ☡ The final step in case (i)(a) uses that g-sgs=e by part (iii).
- ☡ In (i)(c), “the case where both integers are positive” should say “the case where the sum of the integers is positive”.
- Page 208
- ¶ A period is missing at the end of the third line.
- ¶ In the first line of Example 3, the word “permutation” should be “permutations” (plural).
- ¶ In the last line on the page, the referent for “this result” is unclear; presumably what is intended is Theorem 5.1.5 on the top of page 207.
- Page 213
- ¶ In the last line on the page, the reference to “Section 4.1” should be to “Section 5.1”.
- Page 216
- ¶ At line 5, for “same numbers” read “same number”.
- ¶ Seven lines from the bottom of the page, the reference to “5.1.4” means “Theorem 5.1.4”.
- Page 217
- ¶ In the proof of Corollary 5.2.5, second line, “more then one” should be “more than one”.
- Page 220
- ¶ Three lines from the bottom of the page, for “and that, more generally, that” read “and, more generally, that”.
- Page 221
- ¶ In the fourth paragraph, lines 1–2, for “may be seen be” read “may be seen by”.
- ¶ In Example 2, line 5, for “even it” read “even if”
- Page 222
- ☢ The displayed formula for the multiplication operation on the direct product is wrong. It should read as follows: (g1,h1)(g2,h2) = (g1g2,h1h2).
- ¶ In the Comment, lines 2–3, for “a operation” read “an operation”.
- Page 223
- ¶ Four lines above the table, insert a comma after “Section 1.4”.
- Page 224, Theorem 5.3.3
- ¶ The numbers m and n should be relatively prime positive integers.
- ¶ In the proof, the reference to “5.1.7” means “Theorem 5.1.7”.
- Page 225, Theorem 5.3.4
- ¶ The number 1 in the statement of the theorem is supposed to be e, the identity element in the group.
- Page 227
- ☡ The parenthetical remark “necessarily” needs amplification. What has been shown so far is that if there exists a noncyclic group of order six, then the group table must have the indicated form (for some labeling of the elements). In principle, it still needs to be shown that this table really does define a group (in particular, that the binary operation is associative). Since we do know a concrete example of a noncyclic group of order six (the symmetric group), the table must in fact be a group table for the symmetric group for some labeling of the elements.
- Page 228
- ¶ Three lines from the bottom of the page, for “the alternating A(n)” read “the alternating groups A(n)”.
- Page 231
- ☡ The discussion about the ISBN covers the obsolete ISBN-10 system, which was replaced by a 13-digit system in 2007. This book itself bears an ISBN-13 identifier. The check digit for ISBN-13 has the property that its sum with the digits in the odd positions plus three times the sum of the digits in the even positions is congruent to zero modulo ten.
- Page 233
- ☡ Four lines from the bottom of the page, the probability of three or more errors actually rounds off as 0.000 000 807, for the first five digits following the six zeroes in the decimal expansion are 80687. In the next sentence, “It follows that” is misleading; the indicated conclusion follows not from the cited numbers but from a different set of numbers computed by a related calculation. The claim “about one in one hundred million” should be “less than one in one hundred million”; in round figures, the probability is closer to one in six hundred million.
- Page 234
- ☡ At lines 4–5, the claim that “Six binary digits are easily sufficient to represent the alphabet plus numerals and punctuation” is wrong in the present context of characters in a printed book, for one needs to represent both uppercase letters and lowercase letters (a total of 52 characters) in addition to 10 numeric digits and more than a dozen punctuation marks, but six bits covers only 26 or 64 characters. The last line in the paragraph should say “less than” rather than “about”.
- ¶ In the Definitions, line 8, add a comma at the end of the line after “for example”.
- Page 235, Figure 5.4
- ☡ In the upper diagram, the circled codeword in the upper left-hand corner should be 011, not 001.
- Page 236, proof of Theorem 5.4.2
- ☢ The argument shows that if the minimal distance between code words is 2k+1, then the code will not necessarily correct more than k errors, but what needs to be shown is that the code will correct k errors. (Actually somewhat more needs to be shown.) Here is a sketch of a valid proof.
Suppose first that the minimal distance between codewords is at least 2k+1. If word v is transmitted as f(v) but received as w with at most k errors (that is, the distance between f(v) and w is at most k), then the distance between w and any other codeword is at least k+1. Therefore w can be uniquely decoded as v simply by searching for the codeword at minimal distance from w.
Conversely, suppose that the minimal distance between codewords is 2k or less. Let w1 and w2 be two codewords that differ in fewer than 2k positions. Changing w1 in k of these positions (or possibly in fewer positions) produces a word w3 whose distances from w1 and from w2 are both at most k. Consequently, if a transmitted word is received as w3, then this word cannot be uniquely decoded.
- Pages 244–245, Example
- ☢ The codewords shown at the bottom of page 244 should match the top row of the table on page 245, but they do not. Apparently the table corresponds to the generating matrix obtained by changing the entry in the bottom right-hand corner of G from a 1 to a 0.
- Page 245
- ☡ The 6×3 matrix shown in the bottom half of the page is supposed to be a 5×3 matrix: the row 1 0 0 is mistakenly duplicated.
- Page 246
- ¶ A period is missing at the end of the first proof.
- Page 247
- ¶ In the last line on the page, for “16 cosets in our table” read “16 rows in our table”.
- Page 248
- ¶ Three lines from the bottom of the page, in the parenthetical remark, for “the these” read “these”.
- ☢ Two lines from the bottom of the page, the three proposed coset leaders all are incorrect; the first one is not a coset leader at all, and the other two are the wrong coset leaders. The correct coset leaders are 000000001000, 001000000000, and 100000000001. On the next page, the first two of the three decoded words are wrong: they should be 000010001100 and 111110010000.
- Page 249
- ☡ The second paragraph breaks the convention established at the bottom of page 240 that Bn denotes the target space of the coding function. Now n is a general exponent.
- Page 273, Exercise 4
- ☢ The statement should say that r(α) (not r(x)) equals f(α). The stronger conclusion stated in the book holds only if r(x) arises by applying the Division Theorem to f(x) and (x-α), in which case r(x) is guaranteed to be a constant function.
- Page 274, Theorem 6.3.4
- ☡ In the fourth line, “g1…gr” should be “g1…gs” with subscript s.
- Page 275
- ☡ In the third paragraph, the conclusion that “f can only be ‘factorised’ as a constant multiple of an irreducible g” is a correct statement, but it is not precisely the logical conclusion that follows from the preceding argument. When s=1, the deduction is that f=g1 without any constant factor, so a stronger uniqueness conclusion holds in the base case than holds in general.
- ☡ In the fourth paragraph, first line, delete the words “the fact”. An inductive hypothesis is a supposition, not a fact.
- ¶ Four lines from the bottom of the page (the last line of the proof), a comma is missing after the ellipsis dots.
- Page 276
- ¶ In the second paragraph, third line, the reference to Proposition 6.2.4 should be to Corollary 6.2.3.
- Page 277
- ☡ In the displayed equation in the fourth line, the factor (x-αn) should be (x-αm) with subscript m.
- ¶ In Example 1, line 11, a period is missing at the end of the sentence.
- Page 280
- ¶ The sentence ending just before Theorem 6.4.1 is missing the terminal period.
- Page 283
- ¶ In lines 6–7, “the previous section” actually refers to section 6.2.
- Page 284
- ☡ In the second displayed formula, all three instances of an-2xn-2 should be an-2xn-1: the exponent on x needs to be increased by 1.
- Page 285
- ☢ In the first line on the page, the claim that 0101 is not a codeword is false: this word is in fact the third item in the list at the bottom of page 284. The subsequent statement that “this code is not cyclic” is false too. In the terminology developed in the next two pages, the indicated code is the cyclic code of length 4 generated by the polynomial 1+x.
Six lines above the statement of Proposition 6.5.1, “a bijection with” means “a bijection of Bn with”.
- ¶ Two lines above the statement of Proposition 6.5.1, for “interpretations of codeword” read “interpretations of codewords” (plural).
- ¶ In the statement of Proposition 6.5.1, line 2, insert a comma following the formula.
- ¶ In the proof, lines 1–2, for “as we have seen” read “by definition”.
- Page 286
The statement of Proposition 6.5.2 should say additionally that the class [g] is in the code C. Otherwise one could achieve the conclusion without any hypothesis by taking g to be the constant function 1.
Four lines from the bottom of the page, for “one choice of generator” read “the generator”; in this example, the generator is unique.
- Page 287
- ☡ In the unindented seven-line paragraph in the bottom half of the page, second line, for “n-m by m” read “n-m by n”.
- Page 294
- ☡ The two sides of Rule (ii) appear identical. One side is supposed to be the conjugate of the product z1z2, and the other side is supposed to be the product of the conjugates of z1 and z2.
- Page 295
- ¶ The formula at line 3 is missing a plus sign following the ellipsis dots.
Answers to exercises
- Exercise 1.2.1 on page 23 (solution on page 296)
- ☡ The term 2.2n in the solution should be 2·2n with a centered dot (representing multiplication).
- Exercise 2.3.2(f) on page 115 (solution on page 302)
- ¶ The solution has a trivial typo: there is an extra comma in the definition of X.
- Exercise 5.1.3 on page 211 (solution on page 311)
The solution is confusing because the roles of x and g are reversed relative to their roles in the statement of the problem.
- Exercise 6.1.3 on page 262 (solution on page 316)
- ☡ Since the polynomial in part (i) is specified as “real”, the solution arguably should be only the real zero x=1, but the given solution includes also the pair of complex zeroes.
- ☢ The solution to part (ii) has a bad typo: for “x=7i or -i” (two solutions) read “x=7, i or -i” (three solutions).
- Exercise 6.2.1(iii) on page 272 (solution on page 316)
- ☢ The term 3x in the answer should be 4x. Also, since the problem is posed in ℤ5, the factor (x+6) can be replaced with (x+1).
- Exercise 6.3.1 on page 278 (solution on page 318)
- ¶ The letter “n” in the second line of the solution should be “r”.
- ☡ In line 4 of the solution, “the results in this section“ means Proposition 6.3.1. Thus the base case of the induction is effectively r=2, not r=1.
- Exercise 6.3.4 on page 278 (solution on page 319)
- ¶ The solution works out from scratch the factorization of x4+1 over ℤ3. But this factorization has just been computed in Example 2 on pages 277–278 immediately preceding the exercises.
- Exercise 6.4.1 on page 284 (solution on page 319)
- ¶ The numbers 9 and 8 in the statement of the problem are in parentheses for no evident reason.
- ☢ There are three errors in the multiplication table shown in the answer. The entry for (2+x)(2+x) should be 2, not 1; and the entries for (2+x)(2x+2) and (2x+2)(2+x) should both be x, not 2x.
- Exercise 6.5.2 on page 290 (solution on page 321)
- ☡ In the third line from the end of the solution, for “even length” read “even parity”.
- Exercise 6.5.3 on page 290 (solution on page 321)
In the last line of the solution, the claim that “each row is one of the above codewords” is false. Inspection of the generator matrix on page 249 shows that only the last line is one of the indicated codewords. The claim would become true if the example on page 249 were changed by making a cyclic permutation of the first three rows of the parity-check matrix.
- Exercise 6.5.4 on page 290 (solution on page 322)
The solution is incomplete. There are additionally codes with generators (x+1)(x3+x+1) and (x+1)(x3+x2+1); both of these codes have weight 4 and so detect three errors and correct one error.
- Page 326
- ¶ The web address listed at the end of the first paragraph is
not current. The MacTutor History of Mathematics archive can be
found at https://mathshistory.st-andrews.ac.uk.