1 Plus 1 Equals 0

dedicated to the memory of Elwyn Berlekamp

The mistaken formula ( x + y ) ^two = 10 ² + y ^two is sometimes called the Showtime Year Student'southward Dream, but I think that's a bad proper name for iii reasons. First, ( x + y ) ² = x ² + y ² is not exactly a rookie mistake; it's more of a sophomoric mistake based on overgeneralizing the valid formula 2( ten + y ) = 2 x + 2 y . (Run across Endnote #1 .) 2nd, nearly high-school and college first-twelvemonth students' nocturnal imaginings aren't about equations. Tertiary, the Dream is not a mere dream — it's a visitor from a co-operative of mathematics that more than people should know about. The First Year Educatee'south Dream is a formula that's valid and useful in the written report of fields of feature two .

FIELDS: THE Better NUMBER SYSTEMS

What'due south a field? At the virtually not-technical level, a field is a playground where things that behave similar numbers get to romp nether the influence of operations that behave like addition, subtraction, multiplication, and partitioning. The Wikipedia page for fields has a more technical definition. The most famous fields are the rational number system ( ℚ ), the existent number system ( ℝ ), and the complex number system ( ℂ ); they're the envy of many other number systems because of how nicely subtraction and division work out in those three realms. The prepare of integers ( ℤ ) doesn't get to be a field (lamentable, ℤ !), even though it tries really difficult. ℤ 'southward got the whole subtraction game down cold, but when yous divide one integer by another (nonzero) integer, the reply isn't ever an integer.

We oft write the operations in a field using the conventional symbols +, −, etc. even when the elements of the field aren't numbers in the ordinary sense. Every field has two special elements called 0 and 1 that behave a lot similar the familiar numbers 0 and ane; for instance, the formulas x + 0 = x and ten × 1 = x and ten × 0 = 0 are valid for all elements x of the field. (Meet Endnote #ii .) Here's an example of field with but three elements, called a , b , and c , with the operations of add-on and multiplication divers by tables:

In this field, a is the 0-element (because x + a = ten for all x in the field) and b is the 1-element (because x × b = x for all ten in the field), then it'd exist better manners to call a "0" and to phone call b "one" (and to phone call c "ii" while we're at it).

THE FIELD WITH Two ELEMENTS

What does it mean for a field to "have characteristic two"? It means that in that field, one+ane = 0 and more broadly ten + 10 = 0 for all elements of the field. (The three-element field I only showed you does non have characteristic two considering 1 + 1 isn't 0, that is, because b + b isn't a .) If Noah had lived in a world of characteristic two, he would take been extremely vexed when trying to load his ark: every time he paired upward two animals in preparation for boarding, they'd mutually demolish. (Only see Endnote #three .) In characteristic ii, adding an odd number of 1's gives i, while calculation an even number of 1'due south gives 0.

The smallest field of characteristic two has but 0 and ane every bit elements; it's called 𝔽 _ii (or GF(two)), and its add-on and multiplication tables look similar this:

The just entry in either of these tables that looks foreign is one+1 = 0; the rest are soothingly familiar. And even 1+ane = 0 might be familiar to you if you've seen modular arithmetics; what we've called "+" and "×" here are mod-two addition and mod-two multiplication. Modern-2 add-on is the kind of addition that applies when 2 wrongs make a right, when the enemy of your enemy is your friend, when cancelling your cancellation of an appointment ways you lot programme to prove up afterwards all, and in other existent-globe situations that I'm hoping some of you lot volition contribute in the Comments.

THE FIELD WITH 4 ELEMENTS

Things get a bit stranger when we move on to the adjacent field of feature two, 𝔽 ₄ , which has four elements that I'll write every bit 0, ane, α , and α +1. (That alphabetic character is intended to exist an alpha, though in some fonts it might look more like an a.) Hither's how they play together under the influence of + and ×.

(Run into Endnote #4 .)

What are α and α +one? They don't really have meaning, or rather, they don't take meaning independent of the system 𝔽 _four they belong to — and 𝔽 ₄ just acquires significant if we play with it (says the pure mathematician) or if we find uses for it (says the applied mathematician) and get comfortable with information technology. If the analogy helps, yous can think of α as something similar the number i that we come across when we progress from the existent number organisation to the circuitous number system; where i has the defining belongings i ⁱⁱ = −one, α has the defining property α ^two = α + 1.

Speaking of −one, if I'd given you the subtraction table for 𝔽 _four , you would have noticed that the subtraction tabular array is the same as the addition table! In characteristic ii, every chemical element x satisfies x + x = 0, and so every chemical element is its own additive inverse; and − ten = x implies that subtracting x is the same as adding 10 .

This brings u.s. dorsum to the First Twelvemonth Pupil's Dream. In both ordinary algebra and the characteristic-two kind, ( x + y ) ^two = x ² + xy + xy + y ⁱⁱ , but nosotros handle the repetition of that xy in different ways. In ordinary algebra, nosotros collect them to go xy + xy = 2 xy ; in characteristic ii, nosotros abolish them to go xy + xy = 0.

In one case you lot've taught your brain how to dance to the music of feature ii, the addition table for 𝔽 ₄ doesn't look very mysterious; when you add 2 elements, the 1's and α 'due south cancel in pairs, just like the annihilating animals in the characteristic-ii version of Genesis.

The multiplication table for 𝔽 ₄ looks wonkier, simply every chemical element other than 0 has an alias of the form α ⁱ for some integer i , and these aliases make the multiplication table simpler while making the addition table harder. We tin write 1 equally α ⁰ , α as α ¹ , and α +1 as α ² .

When yous multiply elements of 𝔽 _four , if one of the factors is 0, then the product is 0, but if both factors are non-zero and we write them as α ⁱ and α ^j where each of i , j is 0, 1, or 2, and then the product is α ^k where thousand is i + j mod 3 (that is, k is the remainder you get when i + j is divided by 3). So for instance α ² times α ² is α ⁱ since 2+2=4 which leaves residuum i when you divide information technology by 3.

ERROR-CORRECTING CODES

For every number q of the form p ^k , where p is a prime and k is a positive integer, there's a finite field of size q , called 𝔽 _q or GF( q ). The "G" is for Galois, the French mathematician who invented finite fields in his pioneering work on abstract algebra earlier participating in a senseless duel and dying of a gunshot wound at the age of 20. Little did Galois realize that Galois fields of size 2,4,viii,16,… would play a vital role in advice technology a century and a half after.

Suppose I want to send digital information over a noisy channel. The information consists of iv bits, each a 0 or a 1. The nigh obvious thing to do is to transport each bit once, but the noise on the channel tin flip a 0 to a 1 or vice versa, resulting in the recipient receiving the wrong message. What to do? I can't go rid of the channel dissonance, simply I can endeavor to overcome it by building more than redundancy into my transmission.

For case, I could transmit each bit twice in a row, so that the message 1011 gets transmitted equally 11 00 eleven 11 (where I've inserted spaces to make it easier for you lot to parse the string into pairs). If the recipient knows that I'chiliad using this protocol, and if the aqueduct introduces at nigh i error, the recipient can detect the occurrence of a mistake. For instance, if the recipient receives xi 00 11 ten, and believes that at most 1 error occurred, then she can conclude that at that place was a corrupted bit in either the last position or the 2d-to-last position, so that the transmitted bit-pattern was actually either 11 00 eleven 00 or eleven 00 xi xi. Merely which was it?

To build more resiliency into the protocol, I could transmit each chip three times, so that the message 1011 gets transmitted every bit 111 000 111 111. If the recipient knows that I'm using this protocol, and if the channel introduces at virtually 1 mistake, the recipient can notice and correct the error past using a simple "majority vote" within each triple of $.25: if all three $.25 in a triple agree, in that location was no corruption of that part of the message by dissonance; if the bits don't agree, the bit that disagrees with the other two is the corrupted chip. This protocol is robust under the supposition that at most one of the twelve transmitted bits gets corrupted. That is, our repetition protocol is a single-error correcting code .

That'southward an constructive way to gainsay error, but one pays a steep cost: for every four bits of actual meaningful data, the protocol requires that I transmit eight extra bits. This means that the transmission process will take three times as long equally it would have without the repetition. That wouldn't be a problem if the bulletin really was just 4 bits long, merely more likely my bulletin is a movie consisting of gigabytes of data, divided up into 4-fleck packets (or, in realistic applications, longer packets), then that increment of manual time by a factor of three is a major pain.

Fortunately at that place's a clever fashion to go the same single-error-correcting robustness with transmissions that use just three extra transmitted $.25 instead of eight. It requires the 8-chemical element finite field 𝔽 _eight . Only every bit the elements of 𝔽 _iv tin be written as degree-one polynomials in α , the element of 𝔽 ₈ can be written as caste-2 polynomials in some element β . Here are the nonzero elements of 𝔽 ₈ , along with their aliases:

( β ⁷ is simply ane again. For more about 𝔽 ₈ , run into Endnote #5 .)

To add together elements of 𝔽 ₈ , use the left-hand alias and add together just every bit you lot would ordinarily add together polynomials, but with the cancellation rules 1 + i = 0 and β + β = 0 and β ² + β ² = 0. For instance, β ² + β plus β ² + 1 is simply β + i (the β ² 'south cancel). To multiply nonzero elements of 𝔽 _eight , use the right-mitt alias and add the exponents mod vii. For example, β ⁴ times β ⁶ is β ^iv+six which is β ³ .

𝔽 ₈ gives me a mode to pad my four-chip payload with three extra cheque-bits to get a seven-scrap manual that'southward robust against single-bit corruptions. Say that my message $.25 are b ₁ , b ₂ , b ₃ , and b ₄ . Thinking of those 0's and 1'southward as elements of 𝔽 _eight , I course the element b ₁ β ^{half dozen} + b _two β ^v + b ₃ β ⁴ + b ₄ β ³ ; information technology can be rewritten every bit a degree-2 polynomial in β , say b ₅ β ² + b ₆ β ^ane + b ₇ β ⁰ . If I transmit the bits b ₁ , b ₂ , b ₃ , b _iv , b ₅ , b ₆ , b ₇ and an mistake occurs in whatsoever unmarried one of the 7 positions, the recipient can use 𝔽 _eight arithmetics to detect the occurrence of an error, to diagnose where the fault occurred, and to prepare the error, obtaining precisely the 7-bit packet I transmitted, whose start 4 bits are the message I was trying to send. (See Endnote #6 .)

The information-transmission protocol I've just described was invented by Richard Hamming, who didn't recollect of it in terms of finite fields. Later researchers in the theory of error-correcting codes figured out that Hamming's construction, and other, even more powerful ways of building resiliency into digital advice, were related to the mathematics Galois had invented over a century earlier. Nowadays Galois fields play a role not but in making communication noise-resistant but in making it secure from snooping.

I teach college math, so almost of my students already accept learned not to write ( ten + y ) ⁱⁱ = x ² + y ² , and hopefully have actual understanding of what the equation ( x +y) ² = ten ² + 2 xy + y ² ways and why information technology's true. I don't teach pre-college algebra, then I have no feel helping students transition from ( x + y ) ² = x ² + y ² to ( x + y ) ² = x ⁱⁱ + 2 xy + y ^two . Equally a teacher I try to observe the kernel of truth in students' wrong answers, and so if I were in a high school classroom and someone fell for the Kickoff Yr Student's Dream, I might say something like "In abstract algebra, where x and y don't count or mensurate things, there are situations where mathematicians really do write ( x + y ) ^two = ten ² + y ⁱⁱ !" before bringing the course dorsum to the mundane world where x and y are ordinary numbers. Only perchance the detour would be distracting or only plain confusing. It might be best to just focus students on the significant of x and y and the meaning of ( ten + y ) ² . However, I can imagine things going badly. (Meet Endnote #7 .)

Thanks to Jeremy Cote, Sandi Gubin, Joe Malkevitch, Evan Romer and Glen Whitney.

Next month: The Positive Side of Impossible.

ENDNOTES

#ane. The truthful newbie'due south delusion, I think, is that if you take an expression similar 2+3×4, it doesn't matter whether you do the multiplication first or the improver first. Later all, 2+3+4 is the same whether it's (two+three)+iv or ii+(3+four), and 2×3×4 is the aforementioned whether it's (ii×iii)×iv or 2×(iii×4). And so you might retrieve that the order of operations in mixed expressions shouldn't matter either. But since (2+3)×4 = twenty while 2+(three×four) = fourteen, the start year student learns that lodge matters.

Information technology'due south the sophomore who, having learned the distributive police force ( a + b )× c = a × c + b × c , mistakenly overgeneralizes the underlying principle and slips into thinking that ( a + b )↑ c = a ↑ c + b ↑ c (where I've somewhat unconventionally written exponentiation as ↑, for reasons that the side by side sentence will make articulate). It doesn't help that mathematical convention has us write these formulas as ( a + b ) c = a c + b c and ( a + b ) ^c = a ^c + b ^c ; it's hard to focus i'south awareness on the deviation betwixt the properties of multiplication and the properties of exponentiation when the formulas don't contain symbols corresponding to the ii operations.

#2. A comical property of abstruse algebra is that part of the definition is 0 ≠ 1. This might seem like a strange affair to see in a math book written for advanced undergraduates; I mean, who arrives at higher not knowing that 0 and 1 are different numbers? But in the abstruse setting, where the elements of a field might not fifty-fifty be numbers at all, and 0 and one could be quite strange beasts, it needs to exist said equally part of the definition of a field that nosotros crave that 0 and 1 not be the same beast.

#3. Of grade, in the sort of universe where the formula a + a =0 rules and everything is 1-of-a-kind, the whole idea of sexual reproduction makes no sense, and Noah would need only one creature of each kind anyhow.

#4. If you've seen modular arithmetic, yous've seen modernistic-4 arithmetic, whose operation tables look similar this:

The Junior'southward Dream (I'm simply making up this nomenclature as I get) is that the field with 4 elements is just modern-four arithmetic, but this is false. In a field, every element besides 0 has a multiplicative inverse; that is, for every x ≠ 0, there'due south a y such that x × y = 1. But in mod-4 arithmetic, 2 doesn't take a reciprocal, and then mod-4 arithmetic doesn't give united states a field.

What is true is that whenever p is a prime, mod- p arithmetic gives a field with p elements called 𝔽 _p . In fact, the outset finite field mentioned in this article (with elements called a , b , and c ) was just mod-3 arithmetic in disguise. When q is of the form p ^k for prime p with exponent k > one, the finite field 𝔽 _q is more complicated to describe. (In example yous were wondering, when q = p ^k , the field 𝔽 _q has characteristic p , meaning that if y'all add together ane to itself p times yous get 0. Also, in 𝔽 _q the First Year Student's Dream works with exponent p ; that is, all elements of 𝔽 _q satisfy ( x + y ) ^p = x ^p + y ^p .)

#v. The field with 2 elements sits within the field with 4 elements, so yous might think that the field with 4 elements sits within the field with 8 elements. But that'south what nosotros might call the Senior'south Dream. A finite field with q elements sits within a finite field with r elements whenever r is a power of q , but eight isn't a power of iv.

#6. If the recipient receives the bit-string c _ane , c ₂ , c ₃ , c ₄ , c ₅ , c _six , c ₇ , and so she can use those $.25 to compute the element c _i β ^six + c _ii β ⁵ + c ₃ β ⁴ + c ₄ β ³ + c ₅ β ^two + c ₆ β ⁱ + c ₇ β ⁰ in 𝔽 _eight ; if information technology'south 0, then no bit was corrupted, and if information technology's one of the seven nonzero elements of 𝔽 ₈ , so which particular element of 𝔽 ₈ it is determines which of the seven positions in the flake-string is the location of the corrupt bit. One time the receiver knows which fleck got corrupted, she tin correct it, reconstructing the transmitted message, whose first four bits are the bodily payload.

#7. Here's my morbid fantasy well-nigh the First Year Educatee'due south Dream. A student comes upwardly to me and says "Teacher, I know you say that ( x + y ) ² = x ² + y ⁱⁱ is wrong, simply I don't see why."

I reply "Well, let'due south try information technology with numbers. What does ( 10 + y ) ² become when we replace x by 2 and y by 3?"

The student answers "two+three is 5, so (2+three) ² is 5 ⁱⁱ which is 25."

"Right!" I say. "And what does x ⁱⁱ + y ⁱⁱ become when we replace x past 2 and y by 3?"

"That's 2 ² + three ² , which is iv plus 9, which is 13."

"Correct!" I say. "A different number."

The student nods.

"Permit'south try drawing a motion picture," I say. I draw this pic:

"What's the surface area of the square?"

"The side length is x + y , and so the area is ten + y squared."

"Great!" I say. "Now permit's compute the surface area a different way by dividing that foursquare up into pieces." I draw this moving-picture show:

"What are the areas of the pieces?"

"Well, there's an x -by- ten square at the upper left, which has area x ² , and there'south a y -past- y square at the lower right, which has area y ² , and there are ii rectangles left over."

"Great! So when you say x + y squared equals x squared plus y squared, y'all're on the right rails, just you're leaving out these ii rectangles."

"I encounter information technology!" says the student. "Those ii rectangles each accept surface area x times y . And then that'south the 2 xy that I was leaving out."

"Excellent! So, what have y'all just learned?"

The student says "I learned that ( x + y ) ² = ten ² + y ² isn't true for numbers and isn't true for geometry. Only I nevertheless retrieve it's true for algebra."