My research and investigations

Posts tagged ‘FF’

Finite Fields – many Models

The story starts here.
———————————————————————–
G: Let the first one introduce himself.

B: George Boole (1815-1864), from England. Did you read my book?
X: Which book?
G: An Investigation of the Laws of Thought of 1854, a classic. I read it just before I logged off.

G: You have another model for GF(2)?
B: Yes, and it isn’t based on numbers.

G: Spell out the details, please.
B: It is based on simple sentences, those you can tell immediately whether it is true or false.

G: This is straight from your book!
B: I also consider simple ways to combine such sentences, only the words and, or, called connectives.

G: That’s two symbols, two operations. Interesting.
B: The connectives can join the simple sentences in 8 possible ways:

Sentence Computations  
Or false true
false false true
true true true
 
And false true
false false false
true false true

X: Exactly how do you compute with sentences?

G: Think logically. I’m here and you’re here: true or false? I’m here or I’m there: true or false?
X: I see. When connected by and, both parts must be true to have true finally. When connected by or, both parts must be false to be false finally.

G: That’s Boole’s Laws of Thoughts!
B: And it gives a model of GF(2) if we use this dictionary:

Boole’s proposed model of GF(2)  
Symbol Meaning
0 false
1 true
 
Operation Meaning
+ logical or
× logical and

X: That’s brilliant! A symbolic model for a symbolic system!

G: Not quite. This model is wrong!
G: I spot the error: in your model: true or true is true. Translate by the dictionary: 1+1=1, which is not correct in GF(2).

B: Oops! How embarrassing! I made a boolean error!
G: That’s the lesson. We need to check carefully to ensure all dictionary translations are perfect.

B: Wait a second. I can fix my error!
G: Don’t make the same mistake twice.

B: No, I won’t. Instead of or, use exclusive or, shortened to xor. I just redo all the computations:

Sentence Computations  
Xor false true
false false true
true true false
 
And false true
false false false
true false true

X: What is xor, or exclusive or?
G: It means either this or that, but not both. Tomorrow either the sun will shine or rain will fall. If tomorrow is foggy or a rainbow appears, my prediction is wrong.

B: And the Boole model of GF(2) is:

Boole model of GF(2)  
Symbol Meaning
0 false
1 true
 
Operation Meaning
+ logical xor
× logical and

G: That’s an impressive quick fix!
G: There are further check … it’s all OK, I declare the Boole model of GF(2) is verified correct.

X: Did you just invent a logical operation to fit into the model?
B: No. It’s all in my book. Using either-or to join sentences is rather common.

G: Now the second model. Your name please.
E: Euclid of Alexandria (300 BC) from Greece. Excuse me for my dates as I’ve lost count.

G,G,B: (bowing) We all read your book.
X: Which book?
G,G,B: (angry looks) Ssh!

E: My classic text Elements was the bible of geometry for more than 20 centuries, until the rise of modern math.
G: Your method of doing math is still being used in all math textbooks.

E: I try to catch up with modern math, so I’ve been doing a bit of abstract algebra lately.
G: I suppose you have a model of GF(2) based on geometry?

E: Take a non-symmetric alphabet, say the letter E in my name. There are two ways you can play with it: either leave it, or reflect it to ?.
B: See, Euclid is using my xor!

E: The first task, which is doing nothing, I call it identity. The second task, which is flipping over, I call it reverse.
B: I can see that.

E: Given two tasks, you can either do both of them, or just do the first one and ignoring the second one.
B: Another xor. First is diligent, while the second is lazy.

E: There are 8 ways to combine the tasks with the do-both or do-one operations:

Task Computations  
Do Both identity reverse
identity identity reverse
reverse reverse identity
 
Do One identity reverse
identity identity identity
reverse identity reverse

E: This gives a model of GF(2) using the following dictionary:

Euclid’s proposed model of GF(2)  
Symbol Meaning
0 identity
1 reverse
 
Operation Meaning
+ Do -Both
× Do-one

X: Another impressive feat!

G: Look carefully ¡X this model is wrong!
G: If your Do-one means to do the first one, then the Do-one table has an error: assume the verticals denote the first, we should have Do-one(reverse,identity)=reverse, not identity as shown.

E: Oops, I may not be so good in algebra!
B: We do have to check thoroughly,

E: But I think I can fix this ….. Yes, I can. Instead of Do-one meaning to do the first one, let’s change it to do the easy one, assuming the task reverse is harder than the task identity, which is doing nothing.
B: This gives the revised 8 computations:

Task Computations  
Do-them-both identity reverse
identity identity reverse
reverse reverse identity
 
Do -easy-one identity reverse
identity identity identity
reverse identity reverse

E: And with this dictionary we surely have a model of GF(2):

Euclid model of GF(2)  
Symbol Meaning
0 identity, the easy task
1 reverse, the hard task
 
Operation Meaning Name
x+y do x, do y. Do-them-both
x×y do easy(x,y) Do-easy-one

G: Let me do further check …. they’re OK. I declare the Euclid model of GF(2) verified correct.

G: This Euclid model inspire me to have still another model of GF(2).
X: Another model?!

G: Sure. This one is based on numbers, but not modulo 2.
G: Let hear the details.

G: Take the two numbers +1 and 1. Symbolic + is numerically multiply, and symbolic × is take the maximum.
G: This is very interesting. Let me compute:

Numeric Computations  
Multiply +1 -1
+1 +1 -1
-1 -1 +1
 
Maximum +1 -1
+1 +1 +1
-1 +1 -1

B: And use this dictionary for the model of GF(2):

Gauss model of GF(2)  
Symbol Meaning
0 +1
1 -1
 
Operation Meaning
x+y multiply(x,y)
x×y maximum(x,y)

G: Further checks are OK. This is indeed Gauss model of GF(2).

X: How to get this model from Euclid model?
G: When I see that reversing twice give identity, I recall (1)(1)=+1. Euclid used the easier task to pick the identity result in his multiplication, so I try the lesser of 1 and +1. It doesn’t work, but reverting to the bigger of 1 and +1 works.

G: Very good indeed. This inspires me to yet another model of GF(2)!
X: Still more?

G: Yes. Take the symbols 0 and 1 as numbers, but let + to mean difference, and × to mean minimum.
X: What is difference?

G: That’s subtraction without sign: always taking the smaller from the bigger.
X: Oh, I see. Let me do the computations:

Numeric Computations  
Difference 0 1
0 0 1
1 1 0
 
Minimum 0 1
0 0 0
1 0 1

G: To match GF(2), the dictionaries for symbols and operations are:

Galois model of GF(2)  
Symbol Meaning
0 Number 0
1 Number 1
 
Operation Meaning
x+y difference(x,y)
x×y minimum(x,y)

G: That’s excellent.
G: Further checks are OK in this case. This is my Galois model of GF(2).

B: It is thrilling to see so many models of GF(2).
X: Is there a most suitable one among the many choices?

G: That’s a good question. It’s too late. We’ll call it a day.
X: Yes, next time.

———————————————————————–
Y: This is way too late.

X: I learn too many models of GF(2) in one day. I’m exhausted.
———————————————————————–
Next

Finite Fields – more Models

The story starts here.
———————————————————————–
X: My roommate suggests another model for GF(2).
G: Glad to know. Tell me about it.

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 add, ignore carry
× 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).
X: Your model?

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?
G: You didn’t miss that, it’s always been in your head after reading my book.
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

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
+ Add numbers, note parity
× 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.
G: Fine. Tell me about this tomorrow.
———————————————————————–
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.

X: Decades? I don’t have many decades in my life!
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.

X: How about your pretty rule: symmetric about the diagonals?
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.
G: Good. So let’s start with two symbols: 0 and 1.

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.

A Gift to my Supervisor

As this year is coming to a close, I would like to thank my supervisor with a gift — a story on Finite Fields (FF).

Originally this is meant to be a challenge to myself — to explain FF in my own words. I feel I should be able to explain the topic in a simple way, and so I try to put down my thoughts.

My plan was to put the thoughts on this blog, but then I encounter a problem: how much math should I assume the reader will have? Since the blog is open to the world, I don’t want to exclude anyone interested in this topic. So the assumed math level keeps going down: can’t assume abstract algebra, can’t assume set theory, can’t assume logic, etc. Very quickly I’m back to the basics: assume a novice.

Explaining a math topic to a novice is not easy, but it should be easier than explaining to a theorem-prover!

There is a bit of struggle at first, since all FF books have math so densely packed that whatever is ‘simple’ are deeply hidden. Eventually I decide to abandon the usual math book format, switching to a story-style.

This sort of suits me. When I read books on my own, there are always questions I ask (why can’t it be this or that) but no answers are forthcoming. The question remains at the back of my mind until I read another book and find the answer, but by then usually more questions have been collected without answers. I always wish there is someone nearby who will tell me, or guide me to the answer when my question is first raised.

By now I certainly have read many books on FF, so I would like to start from the beginning, ask myself questions, and try to answer them myself. By doing so, I clarify my thoughts, and gain a deeper understanding of FF. I can equip myself for my research work next year.

I am still developing the storyline. So far I think I’m on the right track.

As the story unfolds, I find that I’m going towards the basics of theorem-proving. This is quite unexpected, since only FF is in my original plan for the content. Maybe my recent reading of the HOL4 manuals is having an effect on my subconscious. Anyway, the twist to theorem-proving is quite natural in these talks of FF, which is most pleasing.

Here is the story.