My research and investigations

Finite Fields – more Models

The story starts here.
———————————————————————–
X: My roommate suggests another model for GF(2).

X: It is based on binary arithmetic used in computers.
G: What are computers?

X: Don’t you use a computer to surf the Net?
G: I surf in the Net. You see, I’ve logged off from your real world long time ago.

X: Oh yes. Computers are the machines we use to connect to the Net.
G: Ah, those stops of the Net that take and send packets! I always get shocks there. How do computers work?

X: Computers process information by electronic bits — that’s why you get the shocks.
G: What is a bit?

X: “Bit” stands for for a “Binary digit“, a digit in the binary system.
G: I know the binary system — it is based on the number 2.

X: Similar to the base-10 system with 10 digits, the base-2 system has only two digits: 0 and 1.
G: I see, the same two symbols of GF(2)!

X: Instead of counting in bunches of 10 in decimal system, binary system counts in bunches of 2.

Counting Decimal Binary Base-3 Base-4 Base-5 Note
zero 0 0 0 0 0 all have zero
one 1 1 1 1 1 all have one
two 2 10 2 2 2 run out of symbols in Base-2, carry to next bunch
three 3 11 10 3 3 run out of symbols in Base-3, carry to next bunch
four 4 100 11 10 4 run out of symbols in Base-4, carry to next bunch
five 5 101 12 11 10 run out of symbols in Base-5, carry to next bunch
six 6 110 20 12 11
seven 7 111 21 13 12
eight 8 1000 22 20 13
nine 9 1001 100 21 14
ten 10 1010 101 22 20 finally run out of symbols in Base-10, carry to next bunch

G: In binary arithmetic, once the digit reaches 2 it is promoted as carry to the next position: 1+1=10 base 2.

X: Yes. 10 base 2 = 1×2+0 = 2.
G: How do these relate to GF(2)?

X: Assume an electronic component with only 1 bit. It won’ have room to store the number 2.
G: It will be forced to drop the carry bit, and store only the remaining bit, which is 0.

X: Thus giving 1+1=0 in base-2 carry-free arithmetic!
G: Excellent! Shall we draw up the computations in bits and have a look?

X: I can do that in my head. The 8 easy computations are:

Bit Computations
Binary add, ignore carry Binary 0 Binary 1
Binary 0 Binary 0 Binary 1
Binary 1 Binary 1 Binary 0

Binary multiply Binary 0 Binary 1
Binary 0 Binary 0 Binary 0
Binary 1 Binary 0 Binary 1

G: So what are the dictionaries to make this a model of GF(2)?
X: The dictionaries for the symbols and operations are:

Bit Model of GF(2)
Symbol Meaning
0 Binary bit 0
1 Binary bit 1

Operation Meaning
× Binary multiply

G: The check is simple: the bit and the symbol are the same. This Bit model for GF(2) is verified correct. Well Done!
X: Now we have two models for GF(2): the Parity model and the Bit model.

G: Excuse my eavesdropping, but this is child’s play!
G: Who’s talking?

G: Johann Carl Friedrich Gauss (1777-1855), from Germany.
G: Ah, the Prince of Mathematics!

G: And you mention my name in your last letter.
G: Indeed. But master, why do you consider our models for GF(2) child’s play?

G: How do you check the parity of a number?
G: Check whether it is divisible by 2, of course.

G: And the possible remainders of division by 2 are?
G: 0 and 1. Oh-oh.

G: And you, how do you convert a number from decimal to binary?
X: By counting in bunches of 2, which is successive division by 2 whenever the amount exceeds 2.

G: For 1 bit, you’ll perform only one division by 2, and the possible results?
X: 0 and 1. Oh-oh.

G: So you see, both your models for GF(2) are nothing but my Modulo 2 model of GF(2).

G: Haven’t you read my book?
X: Which book?
G: Your classic Disquisitiones Arithmeticae (Investigations on Arithmetic) of 1801, I’ve read that.

G: I wrote that at the age of 21. The first chapter is on modular arithmetic.
X: What is modular arithmetic?

G: Fix a number n, called the modulo, then perform add and multiply of numbers as usual, but any result will be divided by the modulo n, keeping only the remainder. I even invent a notation for that.
G: x+y ≡ z mod n is x+y, then keep only the remainder z of division by n. Similar expressions for other arithmetic operations.
X: Let me try an example. For modulo n=3, 2+2=4 ≡ 1 mod 3 because 4 divided by 3 gives remainder 1.

G: When the modulo n=2, there are only 2 remainders: 0 mod 2 and 1 mod 2.
G: In modul0 2 arithmetic, the 8 easy computations are:

Modulo 2 arithmetic
Add mod 2 0 mod 2 1 mod 2
0 mod 2 0 mod 2 1 mod 2
1 mod 2 1 mod 2 0 mod 2

Multiply mod 2 0 mod 2 1 mod 2
0 mod 2 0 mod 2 0 mod 2
1 mod 2 0 mod 2 1 mod 2

X: Let me check: for modulo 2, 1+1=2 ≡ 0 mod 2.
G: Hence the Modulo 2 model of GF(2) is:

Modulo 2 (Z2) Model of GF(2)
Symbol Meaning
0 0 mod 2
1 1 mod 2

Operation Meaning
x+y x+y mod 2
x×y x×y mod 2

G: Again the modulo 2 remainders and symbols match. This Modulo 2 model of GF(2) is verified correct.

G: This is such a natural model for GF(2). How come I miss that?
X: I think that’s why you said I can treat the symbols as numbers if I wanted to.

G: The modulo 2 system is denoted by Z2, and your Parity model is implicitly Z2.
X: What is Z?
G: Zahlen in German, or Numbers in English. The modulo is the subscript.

G: Nice meeting you, Gauss. It’s dinner time, shall we find a place to eat and discuss my last letter?
G: Glad to. Let me find a good place using my mobile app.

B: Don’t go. I have another model of GF(2)!
E: Me, too! I have yet another model of GF(2).
G: Long time no see!

G: Shall we continue after dinner?
X: Arrrh — I’m going to log back on after dinner, don’t start without me!
G: Sure.

———————————————————————–
Z: Are you staying for dinner? We have Chinese take-away tonight.

X: No. I’m heading back to Al-GBar right after dinner.
Z: What’s the hurry?

X: The prince and his friends are waiting.
Z: The real Prince? Or the artist formerly known as Prince?

X: No and no, I’ll explain later. My instant noodles are ready.
———————————————————————–
Next

Refreshing Childhood Math

To most people, math is something they learned in the days gone by.

I suppose children like math, especially the smart ones. Then the math puzzles become more puzzling, the math problems become more problematic. Struggling on, the flood of math formula is overflowing, any initial interest in math is washed away. When calculations turn into calculus, most will surrender. By the time we can exit from the education system, we are glad to say goodbye to math.

Life goes on. We don’t need calculus to find a job. There’s no formula to remember in daily matters. The tax calculations may pose a challenge, but now you’ve got a calculator. Most likely you’ve picked up a Rubik’s Cube, then put it down. In spare time you may enjoy a game of Sudoku. Isn’t life wonderful?

The world also moves on. Space travel requires complex calculations, but how to squeeze a computer, which can occupy a very big room in the 60s, into tiny spacecrafts? How to get pictures without films? How to communicate with a tiny robot millions of miles away with a dying battery? These are some of the challenges to scientists, and the solutions, by applying a lot of math, give birth to the current technology of laptops, digital cameras, image formats like JPEG, error-correction codes and the wireless communication network. Isn’t math wonderful?

To revive your childhood interest in math, physics and astronomy, you may like this recent (October 2010) Einstein Public Lecture by Terence Tao.

He described the lecture in his blog: The Cosmic Distance Ladder (version 4.1). There you can download the lecture in PDF or PPT, even his earlier versions. If your internet connection can handle the bandwidth, you can watch this lecture video. Being a public lecture, detailed calculations are omitted. If you need to see them there is a link from his earlier lecture in 2007.

Terence Tao (陶哲軒) has won many honors and awards, including a Fields Medal in 2006 – the math Nobel prize.

If you’d like to take a look at his current research (in math), click “Home” in his blog.

I did that, but didn’t get anything into my head. But then I sit back, and think, “What a nice idea, a blog talking about your own research.” When I start my research, I immediately sign up for WordPress.

What Exactly Are You Doing

People close to me are excited by my pursue of PhD, and this is the question they’d like to know the answer.

Imagine a group of people gather around me. When I say “It’s a math topic”, half will leave. When I add “in automated reasoning”, another half will leave.

Math is one of the main subjects in education, and we do math everyday (how much is 30% off), but few are interested in math upon leaving school. Most think of math as calculations, which can be tedious. Some may be remember the tricky math problems, only the smart ones can solve them. Others may recall the frustration with math proofs, and conclude that proving math should be reserved for those with a different brain structure.

So, how am I going to explain what I’m doing to ordinary folks?

I think I’ll start with something everyone is now familiar with — sending text messages, via a mobile phone or the computer.

Once the message is sent, the words, which are symbols, are converted into numbers. There are several levels of this conversion:

• the first level is rather like old-fashion telegraph, where alphabets are coded into digital patterns. Although the details are a bit involved, they are essentially similar to putting A=1, B=2, C=3, etc.
• the second level is about secrecy. The message is supposed not to be readable by a third party, so the coded alphabets will be scrambled in a certain way, called encryption. When the numbers reach the other end, they will be unscrambled, reversing the encryption process, called decryption, so the recipient can read the message.
• the third level is about transmission. In order for the encrypted numbers to be reliably transmitted through a path that is not expected to be error-free, some extra information, or redundancy, are inserted to enable the receiving end to, at least, check if an error has occurred, and, preferably, to recover the intended numbers by a process called error-correction.

These underlying processes in message conversion clearly show that symbols are being handled as numbers, probably in ways you’ve never imagined — all these things happen at the push of a button! All these levels need math, both the theory to show why the method works, and the computations to actually carry out the processes.

On the other hand, numbers are just special symbols. Most civilizations used one-stroke for 1, two-strokes for 2, and three-strokes for 3. After that, the problem “how many more symbols should be invented?” becomes a struggle to the civilization. Even today we keep inventing prefixes – like K for kilo, M for mega, G for giga, T for tera — to describe larger and larger amounts. The name “Google” originates from a misspelling of “googol”, a number represented by a 1 followed by 100-zeros.

Looking at numbers as symbols is a shift in perspective. Once you take this view, math computations become symbolic manipulations: follow rules to move symbols around. That’s what computations really are. By doing so, computers can “compute” a lot of things: the pixels to give a picture, the sound to play a song, both color and sound to play a video. All information are symbols.

Back to math. Besides computations, math people are busy with another activity: proving theorems. On the surface, the process involves reasoning in logic; but most mathematicians hold the view that the reasoning steps can be broken down into elementary rules of moving logical symbols around. Hence, taking another shift in perspective, it is possible to do math proofs by math computations. This technique is called “automated reasoning”.

My project is to apply automated reasoning to investigate a well-known method in modern day communication. The method is used in error-correction of signal transmissions, e.g. wireless networks (Wi-Fi). The method is also used in efficient generation of random-looking bits for signal encryption (in mobile phones) as well as signal synchronization (in GPS devices). The fact that this method can be used in many different ways is fascinating. I would like to show clearly what is the shift in perspective behind the scene.

It is by shifting of perspective that researchers reveal new ways of looking at things. Sometimes these new ways of looking can lead to new ideas, enabling advance in technology. The IT revolution of the past decades is evidence of this happening — researchers solve various technical problems by shifting of perspective.

Finite Fields – first Model

The story starts here.
———————————————————————–
G: Good day. I’ve found something interesting about GF(2).

X: Didn’t you say that’s all for GF(2)?
G: There is always more.

X: What more can we say about a system with just 2 symbols?
G: The GF(2) we talked about is in the abstract. Now I’ve found a model for GF(2).

X: What is a Model?
G: A model is an interpretation of a system. It assigns meaning to the symbols and operations, thereby verifying all relationships are correct.

X: You mean like a picture?
G: Yeah, a bit. More like an analogy, a model makes an abstract thing meaningful.

X: Sounds magical, also very mysterious.
G: You’ll like this as it involves numbers. For GF(2), I can make a model like this for the symbols:

Symbol Meaning
0 An even number
1 An odd number

X: Can I change the other way round: 0 for odd and 1 for even?
G: I tried, but it won’t work, as you’ll see. Now for the operations:

Operation Meaning
+ Add the two numbers and note the parity of result
× Multiply the two numbers and note the parity of result

X: What is parity?
G: Parity of a number is whether it is even or odd.

X: This looks like a dictionary.
G: Good observation. A dictionary gives meaning to words, which are symbols.

X: What’s the use of this dictionary, or model?
G: Using this model we can check our abstract system GF(2):

Abstract GF(2)
+ 0 1
0 0 1
1 1 0

× 0 1
0 0 0
1 0 1

X: I thought you said 0 is expelled from multiplication.
G: I swept it under the carpet, but now I pull it out from the carpet.

X: Must be your magic carpet. But why?
G: The system has the relationship 0×a=0 which I cannot hide, although it offends me when working with multiplication.

X: What’s so offending about 0 in multiplication?
G: That’s another rule of Fields that we’ll look at eventually. Today we’ll treat addition and multiplication as equal parts of the structure, so we’ll use the full picture.

X: What equal parts of the structure? You never mention that.
G: The structure of the Field. Add and Multiply are equally important parts.

X: What about Subtract and Divide? I remember you said all four operations must be good.
G: Recall that we’ve made symbolic subtraction work via symbolic addition: a-b=c whenever a=c+b.

X: Ah, that moving symbols around thing!
G: Yes. And we’ve made symbolic division work via symbolic multiplication: a÷b=c whenever a=c×b.

X: So, how to check GF(2) by your model?
G: Simple. Now we can compute our table entries:

Model Computations
Add numbers, note parity Even Odd
Even ? ?
Odd ? ?

Multiply numbers, note parity Even Odd
Even ? ?
Odd ? ?

X: Can we just use the dictionary to fill in the tables?
G: No! The aim is just the opposite: first compute without using the dictionary, then show that all entries matches GF(2) via the dictionary.

X: You mean we have to work through 8 entries? You said there is a symmetry rule — maybe it can help us to reduce some work.
G: No! Those rules are for the Field. When working with the Model, forget the Field for the moment. Upon completion check with the Field.

X: The actual Model is a lot harder than the abstract Field!
G: Computations are easy, even with 8 of them. You can almost feel the parity of a number. Give them a try.

X: OK. Two evens add to even. Two odds add to even. One odd and one even is still odd.
G: And even makes things even upon multiplication, only odd with odd give odd. So we’re done with the computations:

Model Computations
Add numbers, note parity Even Odd
Even Even Odd
Odd Odd Even

Multiply numbers, note parity Even Odd
Even Even Even
Odd Even Odd

G: Now check the results of computation with GF(2) via the dictionary. All entries are verified correct.

Abstract GF(2)
Add symbols: + Symbol 0 Symbol 1
Symbol 0 0 1
Symbol 1 1 0

Multiply symbols: × Symbol 0 Symbol 1
Symbol 0 0 0
Symbol 1 0 1

X: Is there a name for this model?
G: I’ll call it the Parity model of GF(2).

Parity model of GF(2)
Symbol Meaning
0 Even
1 Odd

Operation Meaning
× Multiply numbers, note parity

X: It’s a good model, giving concrete meaning to abstract symbols.
G: And concrete procedures for abstract symbolic operations.

X: I still can’t see why we don’t cheat by invoking the dictionary for the computations in the first place.
G: When we propose a model, we don’t know if it works. We do all computations purely within the model. If the results are verified correct, then we know the model works. Otherwise we have to reject the model, and try a better one.

X: In that case, what’s the use of model? After this long-winded process, all we know is the model works. It just verifies what’s already known.
G: By its nature, a model reflects exactly the abstract system; nothing more and nothing less. However, by giving meaning to abstract symbols and operations, it explains why the system works, at least in one case.

X: How do you think of a model? It comes from thin air? Who knows what abstract symbols mean?
G: That’s part of the creation process of math, you’ve got to feel the model. You guess the meaning, see if that works.

X: How to guess meanings?
G: For example, GF(2) has two symbols, and I know numbers are of two kinds: Odd and Even. So I try to see if I can match the symbols with parity of numbers.

X: You first build up a dictionary to match symbols?
G: Yes. Then I use the dictionary just for symbols to reveal what the operation tables will look like.

X: Hey, you just said we can’t cheat by invoking the dictionary for the table computations!
G: This is invention. I don’t know what the operations mean: I have to reveal them to guess what they can mean.

X: This is cunning — almost cheating.
G: When I get the dictionary even for operations, I reverse the process: show the dictionaries and compute the tables to verify the model.

X: This is cunningly clever!
G: If a model has been verified, then you can make use of the model to help you reconstruct the abstract system, in case you’ve forgotten a table entry. Generally, the model dictionaries are less demanding to remember than the whole abstract system.

X: So we can use the model to cheat, after all.
G: Only if the model has been verified — that is, someone had done all the computations in the model.

X: Can someone skip the computations and prove once and for all the model works?
G: Now you’re talking math! This can certainly be done, when the theory is sufficiently developed.

X: I think I’m still not of the math-type.
G: Sometimes, quite unexpectedly, we may find two models of the same abstract structure.

X: This is just another dictionary for the symbols and operations. What’s the point of a second verification after the first verification?
G: If that works, it provides another explanation, another good example. It certainly provides further evidence of usefulness of the abstract system.

X: Usefulness, importance and significance of the abstract system.
G: And if the models are from different topics, this can be exciting if this reveals some hidden relationships between the topics.

X: Really? So another model is good?
G: Do you have another model for GF(2)?

X: I think my roommate may have suggested one. I’ll need to talk to him.
———————————————————————–
Y: How’s today?

X: He changes the subject to models.
Y: As the models parading on the cat-walks?

X: Of course not — as a model giving a concrete picture of an abstract system.
Y: How? How to go from way-up-high to way-down-low?

X: Using a dictionary to give meanings to symbols and operations. That’s an intricate idea.
Y: So you’ve found something interesting in his ideas, at last.

X: Maybe. Explain to me the binary arithmetic of computers again. That can be a model for GF(2).
———————————————————————–
Next

Finite Fields – first Example

The story starts here.
———————————————————————–
X: I was thinking: should I come again? Learning only two symbols per day will take years to learn Finite Fields.
G: That’s nothing. The math community took decades to understand my ideas.

G: Don’t worry. We shall just pick the simple stuff and enjoy.

X: Keep things simple. Recall that I have math-phobia.
G: Promise. Do you recall the building blocks of Finite Fields?

X: Building blocks? Something you said just before goodbye … the two symbols 0 and 1?
G: So you did learn something yesterday.

X: I recall that only because I can’t understand this. Somehow 0 is expelled from multiplication, so start with 1. To me they are trivial numbers — I can’t see how they can be called building blocks.
G: Symbols! 0 and 1 are the first two symbols of any Field!

X: Alright, don’t get mad. You said I can think of abstract symbols as numbers without harming the theory.
G: Did I? Well, that’s true. So try to add and multiply these two symbols — or numbers in your mind.

X: Simple and easy: 0+0=0, 0+1=1, 1+1=2, and 1×1=1 since 0 is taken out from multiplication.
G: We’ve got only two symbols 0 and 1 — there is no symbol 2.

X: Can we stop this silly argument? Why can’t a genius invent a symbol 2 for the number 2?
G: Please calm yourself. We have to play by the rules.

X: What rules?
G: The good rules of Fields.

X: There is something good in all these? I’m listening.
G: OK, the first rule for Fields is this: the result of add and multiply cannot go beyond the system.

X: Remind me what is system.
G: The set of symbols we are playing with.

X: Did you just invent a rule to prevent me from doing 1+1=2?
G: Yes and no. Gauss, Euler and Fermat, among others, had worked in such systems before me, but I’m the first to see that there is a wonderful theory for such systems following from a few good rules.

X: If you say so. Then how are you going to play the game by your own rule? There’s an ugly hole in the addition table:

+ 0 1
0 0 1
1 1 ?

G: Easy. There are only two symbols to choose from: 0 or 1.

X: What is your choice: something+something=something, or something+something=nothing, genius?
G: What do you think? I’ll take the opposite of your choice.

X: Adding something to something of course end up in at least something! I’d say in symbols: 1+1=1.
G: Add can mean anything — it is just a symbolic operation. I’d rather look at patterns. To me, 1+1=0 is pretty:

+ 0 1
0 0 1
1 1 0

X: Pretty? You do math based on pretty or not pretty? And they regard you as genius?
G: Oh yes, I single-handedly invented the theory of symmetry. Want to know?

X: Don’t you scare me with another theory! What’s so pretty about your 1+1=0?
G: With this the addition table is just so symmetrical. Look at the reflection along the diagonals!

X: This is crap. Why don’t you invent a rule for prettiness?
G: Come to think of it, you’re right. The second rule for Fields is: each symbol appears once and only once in rows or columns of tables.

X: That’s a Sudoku rule!
G: What is Sudoku?

X: Never heard of that? The popular puzzle to fill 9×9 squares with digits 1 to 9, once and only once along rows, columns or 3×3 boxes.
G: That’s a wonderful game of symbols, with a more restrictive rule than the one for Fields.

G: I’ll just need one diagonal symmetry. The third rule for Fields is: add and multiply should be symmetric.

X: Exactly what do you mean by being symmetrical?
G: For all symbols a and b in the system, a+b=b+a and a×b=b×a.

X: You’re just making up rules to get along?
G: The rules are in my head. I’ve never bother to spell them out. I guess you help me to bring them out clearly.

X: I just realize that my 1+1=1 also fits into your symmetry rule.
G: But it doesn’t fit into the Sudoku rule — that’s more powerful.

X: I can see that the Sudoku rule is more powerful.
G: I can feel the power of the Sudoku rule. Anyway, here is an example of a Field: arithmetic operations are good:

Field with 0 and 1
+ 0 1
0 0 1
1 1 0

× 1
1 1

X: What’s the big deal? You just jotted down enough rules to make an example with two symbols.
G: This is the smallest Field — a Finite Field with two elements. I shall denote it by GF(2).

X: What’s GF?
G: Galois Field.

X: You name it after yourself?
G: No. The math community just pick my name for these fields when they understand my ideas.

X: You said a Field has add, subtract, multiply and divide all good. I can see add and multiply are good here. How about the others?
G: Ah, I almost forget about them! In GF(2), subtract is the same as add, divide is the same as multiply — so both are very good.

X: What? The math genius says: a-b = a+b, and a÷b = a×b? What kind of math is this?
G: The kind of math in GF(2), that is. It just happens to be so: a-b = b-a for all a, b; and a÷b = b÷a for nonzero a, b.

X: Am I talking to a crazy genius? My math teacher will surely fail you for your crazy subtract and divide.
G: Divide and multiply are symbolic operations. They are supposed to be opposite – one undoing the other. But in GF(2) there is not much you can multiply: only 1×1=1 as 1 is the only nonzero. Therefore a/b or b/a can only be 1÷1=1, same as 1×1=1.

X: But at least there are more symbols for add and subtract, even in GF(2).
G: Just think logically. Whatever add does, subtract will undo it. What do you think 1-1 should be?

X: For numbers that’s easy: 1-1=0.
G: Does it look the same as: 1+1=0 in GF(2)? Surely if adding gives no gain, subtracting will give no loss.

X: But 1 and 0 are symbols, according to you. Can you deduce 1-1=0 as symbols, not numbers?
G: Yes. A symbol equals to itself, hence 1=1, therefore 1-1=0.

X: Hey, you are just moving symbols around!
G: There is a rule for moving symbols around in Fields.

X: That’s the same trick again — you’re just inventing rules to cover yourself.
G: All the rules are in my head, I just use them. You need to be able to move symbols around to undo things:

• a-b=c is equivalent to a=c+b;
• a÷b=c is equivalent to a=c×b.

Indeed, the Persian mathematician al-Khwa-rizmi- (780-850) described this moving symbols around as al-jabr (restoration by balancing), from which the word algebra is derived. His name is the origin of the word algorithm.

X: You’re pulling out history to back you up. What about 0-1 in symbols?
G: Use algebra to move the symbols around: 0=1+1, so 0-1=1 in GF(2).

X: That’s really crazy: -1=1 in GF(2)!
G: That’s crazy but true. That’s what makes subtraction and addition the same in GF(2).

X: Are we done? I’ve heard enough of crazy talks today.
G: That’s all. GF(2) with two symbols 0 and 1 is defined by the fact that 1+1=0, or 1=-1.
———————————————————————–
Y: How’s the meeting with the 0-1 genius?

X: He’s crazy.
Y: A crazy genius? Tell me more.

X: Any math teacher will fail a student who asserts that 1=-1.
Y: You mean he can’t tell the difference between positive and negative numbers?

X: He keeps saying that they’re symbols, not numbers. It is as if he can do anything he likes with symbols.
Y: There is something called symbolic computation in computer science. I’m interested. How comes 1=-1?

X: He insists that’s correct in GF(2).
Y: What is GF(2)?

X: Something of his own invention, with just the two symbols 0 and 1 and the special rule 1+1=0.
Y: Moving the +1 from the left side to the right side of equality, surley 1=-1.

X: That’s exactly his crazy way! Isn’t just moving symbols around to do math is something crazy? something not math, or SNM?
Y: No. Moving symbols around is math. The topic of symbolic logic is all about doing logical deductions by moving symbols around. The mathematician David Hilbert (1862-1943) was of the opinion that doing math is like a game of chess: to prove a theorem is to find the correct moves. He even claimed that all math can be reduced to such moving around of symbols, which he called formal methods.

X: Has the world turned crazy?
Z: There was this episode in physics. In 1958 Wolfgang Pauli was presenting his new theory of matter with Niels Bohr and others in the audience. At the end of the lecture Pauli asked Bohr his opinion. Bohr’s reply was, “We are convinced your theory is crazy. The question which divides us is whether it is crazy enough to be true!”

Y: Actually, this is not crazy: it’s true. 1+1=0 is what happens inside computers.

X: I can’t believe this crazy equation has applications!
Y: All modern computers are binary machines: at the lowest level they’re manipulating only two symbols 0 and 1 based on binary arithmetic.

X: What is binary arithmetic?
Y: Just like ordinary arithmetic which is based on the number 10, binary arithmetic is based on the number 2. It works like this ….
———————————————————————–
Next

Finite Fields – no Math

The story starts here.

———————————————————————–

X: What is a Finite Field? I don’t want to know the math!
G: Hey, you’re talking to a math genius!

X: OK, just the barely minimum – I’m afraid of math but I’d like to know a little bit of it.
G: In that case, it’s simple: a Finite Field is a Field that’s finite.

X: That’s the answer from a genius?
G: Well, that’s the truthful answer.

X: You are playing with words.
G: I’m playing with symbols.

X: How will you play with just one word: what is finite?
G: Finite is not infinite.

X: I’ll stop talking to you.
G: That’s the logical reply. If you don’t know finite and infinite intuitively, you’d better go home.

X: You simply haven’t answered my original question. What is a Field then?
G: Do you know how to add, subtract, multiply and divide?

X: You mean like 2+3, 5-4, 6×7 and 8÷2?
G: I’m not really thinking of numbers … but numbers are OK.

X: That’s simple and easy. I learnt them long ago — perhaps that’s the only time in my life I like math.
G: Yes, that’s math. A Field is a system within which add, subtract, multiply and divide are all good.

X: Why do you say system? That sounds abstract. Your system has numbers for the arithmetic operations, right?
G: I’m thinking of symbols, not numbers. If that sounds abstract, you can think of a system as a set of numbers — that’ll do no harm to the theory.

X: Wow! The word theory has such a strong smell of math that it scares me! Can you not mention any theory?
G: Alright, no theory. Let me start from the beginning. Can you count?

X: Everybody counts: 1, 2, 3, 4, 5, ….
G: I count from zero: 0, 1, 2, 3, 4, 5, …

X: I count with fingers: 1 finger, 2 fingers, … Nothing has nothing to count.
G: Just close all the fingers to show 0 fingers!

X: I know, I know! I don’t have all day to argue with you.
G: Come to think of it, I count in my head from 0. If I count with fingers, 1, 2, 3 seem better.

X: Hey math genius — you can’t even decide counting from 1 or 0 ?
G: Oh I’ve decided. I’ll denote the set of numbers {0,1,2,3,…} as N, and the set without zero as N* = {1,2,3,…}.

X: The word set worries me. Once my math teacher talked about set theory; at first I understand it, then I don’t.
G: Don’t worry. For me a set is just a collection of things. I’ll use a ∊ S to mean object a is in set S.

X: That’s math! That’s the scary math I’m sooooooo afraid of!
G: That’s just a symbol in the math language, like + for add and × for multiply. Alright, I’ll just say a in S, ok?

X: That’s better. So where were we? Math is really not for me.
G: I was saying that there’ll be two counting sets N and N*, with N including zero and N* excluding zero.

X: I can’t believe I’m talking to a math genius for several minutes just on how to start counting numbers!
G: No, they are symbols. I’m going to play with symbols.

X: Numbers, symbols. Potatoes, po-ta-toes. Who cares?
G: This is important: I’m going to add and multiply with symbols — that can be very different from add and multiply with numbers!

X: Add and multiply symbols, not numbers? Are you out of your mind? Can I say #+%, @*! ?
G: Don’t be rude. Add and multiply are just symbolic operations. This is how Romans add: III + IV = VII.

X: These are Roman symbols for numbers. They are just doing arithmetic on numbers with weird symbols.
G: I shall use numbers as symbols, and perform arithmetic on symbols denoted by familiar-looking numbers.

X: Can’t argue with a genius who must have a twisted mind.
G: You’ll see this is the heart of Finite Fields. Let’s start with the first two symbols: 0 and 1

X: Why not just start with one symbol 0? I know how to add and multiply this symbol: 0+0=0, 0×0=0.
G: That’s not a Field.

X: I thought you’d say “that’s trivial”. Why is it not a Field?
G: You still recall what a Field means?

X: You said something about a Field is all good — I can’t recall all the details.
G: A Field is a system within which add, subtract, multiply and divide are all good.

X: I don’t know about system!
G: A Field is a set of symbols within which add, subtract, multiply and divide are all good.

X: So a system is a set of symbols?
G: Now you know what a system is!

X: But I can add my zero: 0+0=0, multiply my zero: 0×0=0, aren’t they all good?
G: I like zero for adding, not for multiplying. I’ll just acknowledge 0×(anything)=0 and then sweep it under the carpet.

X: Out of sight, out of mind?
G: In fact, from now on I’ll just multiply non-zero symbols. So just a zero will have no multiplication — that’s why it’s not a field.

X: Is this how a genius do math — just depends on whether he likes it or not?
G: No. Symbolic multiplication involving zero is just no good, as you’ll see.

X: I can sense that there is a lot more behind your simple good.
G: Ah, I haven’t define my good — that’s the beginning of the theory.

X: Arrh …. no theory please. If it’s good for you, it’ll be good for me.

X: I feel hungry. Don’t you need to eat something after all this talk?
G: I’ll need to top up my energy level, too. We can continue tomorrow.

X: What have I learned today? Just 0 and 1!
G: They are the building blocks of Fields. See ya.
———————————————————————–
Y: What have you learned today?

X: It’s a waste of time — I just learned how to count.
Y: To learn counting from a genius? What’s new?

X: Genius? He can’t even decide whether to count from 1 or 0!
Y: There is a popular rumor in computer science: those who count from 1 prefer Pascal, while those who count from 0 prefer C.

X: Eventually he decided to count from 0 when adding, but to count from 1 when multiplying.
Y: If he were a programmer, he will be mastering both Pascal and C! Quite a genius.

X: This genius can’t explain Finite; his words: Finite is not infinite — what a jerk!
Y: That’s in the same spirit as recursive acronym, very common nowadays. For example, GNU stands for GNU Not Unix.

Z: The Chinese linguist/humorist Lin Yutang (林語堂) was once posed with this question, “What is the definition of an ideal husband?”. His reply, “The husband of an ideal wife”. No one raised the next question, since everyone knew the answer. A burst of laughter followed.
———————————————————————–
Next

Finite Fields – A conversation with Galois

This is a story about Finite Fields (有限域), or Galois Fields in honor of Évariste Galois (1811-1832).

This conversation is, of course, a fiction. Galois was barely 20 when he dies. Except for a few letters, manuscripts (some were lost) and published papers, there are not much written records from Galois, let alone conversations.

Galois is recognized as a math genius, during his lifetime and long after his death. However, his ideas are so far ahead of his time that his contemporaries could not understand his claims. Galois was not keen in organizing or explaining his thoughts, resulting in several frustrating episodes, ultimately leading to his early tragic death. It was not until 1843 that Joseph Liouville gave the first exposition of his remarkable ideas.

Conversation with a genius is always fascinating, even though this is imaginary. As the fire of youth subsides, he would have consolidated his ideas, and more willing to share his thoughts. While the talk is a fantasy, the contents – all the maths – are real good: logically true and with real applications.

By developing the theory of Finite Fields through chatting with Galois, his genius will be recognized, and the beauty of the theory will shine through.

In the conversation, G is Évariste Galois. X is the Unknown student (you and me), Y is his roommate, studying computer science, and Z is his Chinese friend. Other characters will pop in and out, from time to time. They meet on the Internet, at a place where all sorts of information can readily be found. The popular site, with a big logo G, is depicted as a bar, owned by Al, the Al-GBar.

Here is the talk.