/sci/ - Science & Math

[Anonymous No.5281224]

So /sci/ is anyone here familiar with Galois Theory? I get that it's used to make complex field theory problems into group theory, but when are you supposed to be using it? Can anyone give any examples?

[Anonymous No.5281306]

[Anonymous No.5281334]

Why don't you learn it and tell us.

[Anonymous No.5281389]

I only know Galois connections (which are generalization of tools from Galois theory) are used in statistical code analysis.

The idea is that you are given the control flow graph of a program in a simple programming language and you want to prove properties like "Whatever the inputs to my program are, at this point of the code, X will be a positive integer and Y will be an odd integer". The way you would like to do this would be to say something like "This loop here says [while X<=4], so when I exit it, I know X>4, and when I just entered it, I know X<=4", and then if for instance later on there is a X++ statement, you will update your knowledge (to respectively X>5 and X<=4".

You basically want to do this back and forth between statements until you have as much information as possible about the possible states of the variables at each point. The problem is that if you keep all the information you have, maybe at some point you'll know something like <span class="math">X\in\{ -3,8\}\cup \{9.3,12\} \cup \dots \cup\{32401,142857\} [/spoiler], and basically both storing that and computing on this kind of data is too complex.

Therefore the idea is the following. Currently, we stored states of variables as subsets of R. Now let us only store them as elements of the following complete partial order:
<span class="math">\{ \bot, >0,=0,<0, \geq 0,\neq 0, \leq 0, \top\}[/spoiler] where <span class="math">X=\top[/spoiler] means "I don't know anything about X". At each point, we only store the current knowledge we have.

(...)

[Anonymous No.5281390]

Galois theory is at the core of the RSA encryption (and all subsequent encryption algorithms based on RSA) specifically http://en.wikipedia.org/wiki/Finite_field

[Anonymous No.5281392]

>>5281389
(...)

Let's consider the code "x:=0; while [something] do function_call(); x++; done". The line "function_call" is first identified as a "X=0" line, then "x++" is identified as a "X>0" line, then we take the loop and go back to "function_call" and now we know X can be either ">0" or "=0", so we make it ">=0" instead. We go again to "x++", but x++ still makes X>0 (starting from X=0 or from X>=0), so it doesn't change. Our algo converged.

This is a trivial example but well, digging a bit into that field is pretty cool. So, the Galois connections are the "morphisms" between the actual knowledge space of the variables (subsets of R, or at least subsets of {1,2^(sizeof(type))}) and our abstract knowledge spaces, here my simple positive/negative/null partial order.

[Anonymous No.5281401]

>>5281389
>>5281390

That's for that. The finite field wiki is especially useful.