Math(s)! Currently: Homomorphic Encryption

Discussion in 'General Chatter' started by Exohedron, Mar 14, 2015.

  1. evilas

    evilas Sure, I'll put a custom title here

    the second one is obtained from the first one by switching the center and right points, the third one is obtained by switching the center and the top, the fourth one by switching the center and top left, and so on. So they're all related through switching 2 points from the first one.

    From that all I can say is "this is a representation of a symmetry group" lol. But hey, at least I figured out the relationship between the figures?

    EDIT: is it all the ways to interconnect 6 points such that no node has 2 connecting lines of the same colors? Is this related to graph theory? Wait but no, the 6 images would be a bit redundant if that were the case. Not to mention all the other permutations of the nodes. There should be 6!, right? Unless you didn't count permuting the colors or rotating. Or maybe mirroring? Eh, I guess that's repeating some patterns, and I'm gonna guess there are exactly 6 left.
    Last edited: Jun 4, 2017
  2. syntheme

    syntheme Active Member

    Exohedron got it in 1, haha. evilas, try permuting any pair on all six graphs.
  3. Exohedron

    Exohedron Doesn't like words

    You should write a post about it, @syntheme, or I could do it if you prefer.
  4. syntheme

    syntheme Active Member

    I'll do so, haha
  5. Exohedron

    Exohedron Doesn't like words

    The Dirac Belt Trick

    Take a long belt, or a tie, or something long and flat-ish. It should probably be pretty thin and flexible, too.
    Attach one end to like a table or something so that it can't move. Then take the other end and twist it around 360 degrees.
    Now, holding the end you twisted pretty close to the table to give you some slack, try to undo the twist without moving either end of the belt.
    As you might expect, you can't. But it's fun to try for a little while.

    Now give the belt another full twist.
    It turns out that, with two full twists, you can actually undo both twists without moving either end of the belt.
    This is often given as a demonstration of a particular mathematical fact (that the fundamental group of SO(3) is Z/2Z). I will attempt to explain it.

    The basic object of study here is SO(3), the group of rotations in 3-dimensions that keep a particular point fixed. This group has a natural geometry to it; it's the one that you get when you say "rotations by the same amount around slightly offset axes are close to each other, and rotations around the same axis by slightly different amounts are close to each other".
    And in this geometry, we can talk about connectedness, or more specifically simple-connectedness. See the post on the Poincare conjecture. It is not the case that if you draw a loop on SO(3), you can always shrink the loop to a point without leaving SO(3). SO(3) is not simply-connected. This is related to the fact that if you twist the belt once all the way around, you can't necessarily just undo the twist.
    However, if you go around the loop twice, you trace out a doubled loop, and this doubled loop can be shrunk to a point. This corresponds to being able to untwist the twice-twisted belt without moving the ends.
    A bit more work tells us that if you take two loops that are individually unshrinkable and which start and end at the same point, and make a composite loop by going around one loop and then around the other, the composite loop is shrinkable. More shortly, π1(SO(3)) = Z/2Z.

    The fact that we have this non-simple-connectedness tells us a bit about SO(3), namely that there is another group G that is simply connected and we have a map G -> SO(3) such that the map is a homomorphism (preserves the multiplication in G), and a surjection (every point of SO(3) gets hit) and the map is locally injective (if two points in G get mapped to the same point in SO(3), the two points have to be far apart). Moreover, because π1(SO(3)) = Z/2Z, we get that the map sends two points of G to each point of SO(3).
    So what is G?
    It's the unit quaternions, i.e. the quaternions of the form a + bi + cj + dk where a2 + b2 + c2 + d2 = 1.
    I don't remember if I explained how you can rotate things using the quaternions, but here's how it works:
    Pick an axis of rotation in 3-space, given by a unit-length vector (a, b, c). Pick an angle to rotate around, call it t. Write C for cos(t/2) and S for sin(t/2). Then make a quaternion q = C + aSi + bSj + cSk. Note that q* = C - aSi - bSj - cSk.
    Now suppose you have a point (x, y, z) in 3-space. You turn it into an imaginary quaternion p = xi + yj + zk.
    To find out where the rotation by angle t around the axis (a, b, c) takes the (x, y, z), compute qpq*. This is also an imaginary quaternion, so you can extract the coefficients and get the answer.
    Note that qpq* = (-q)p(-q*), so we have that two distinct unit quaternions, q and -q, do the same thing when applied to p. Hence the map that turns unit quaternions into rotations in 3-space is 2-to-1.
    In particular, setting q = -1 gives a rotation that sends any point (x, y, z) to itself, i.e. the do-nothing rotation.
    But note that unit quaternions also can do rotations in 4-dimensional space, by taking a point (w, x, y, z), computing q(w + xi + yj + zk) and extracting the coefficients, and this operation with q = -1 does not send (w, x, y, z) to itself, but to (-w, -x, -y, -z). We say that these 4-dimensional vectors transform as spinors.

    So we see that the belt is more like 4-dimensional points than the 3-dimensional ones. Other things that have this property include fermions (electrons, protons, the particles that make up matter) which is why Dirac is involved; he rediscovered the quaternions (sort of) when hunting for a relativistic description of the electron and found that the wavefunction of the electron ought to pick up a minus sign when you rotate the coordinates by 360 degrees.

    * To use a big hammer on a small nail
    • Informative x 1
  6. syntheme

    syntheme Active Member

    The Outer Automorphism of S6

    First, I need to discuss my avatar, the first of the six images in the row I posted:

    As you can see there are five colors, and in each color three lines pairing off the six elements of our set. In really old-timey math terminology, each pairing off is called a syntheme and the splitting of the fifteen pairs into five synthemes is called a pentad.

    Now the interesting thing about a pentad is that it is very highly symmetric. There is no nontrivial symmetry that preserves each color (try to find one yourself!) but there are a lot of symmetries that interchange the colors; in fact, every permutation of the colors can be matched to a permutation of the six points.

    There are five symmetries, including the identity, that you can see just by rotating the diagram. With one weird projective trick, you can expand to half the symmetries: imagine each point as a pair of opposite points on a sphere and each line as a full great circle; then the diagram becomes the graph of an icosahedron(with some extra segments) and can be rotated in a full sixty ways, halfway to 5!=120.

    To get the rest of the way there, you need to find another trick. If you started with the icosahedron and know a lot about it, one trick would be to swap the two square roots of 5, but if you know that you probably already understand S6, so instead I'll note you can mark infinity on the center, 0 through 4 around the edges, and then multiply by 2 mod 5; this will get you an order-4 permutation of the five colors, which together with the icosahedral trick gets you all 120.

    Now let's think back to the full set of 6 pentads.

    Try doing any permutation of the six elements. It shouldn't take you much convincing that any syntheme goes to another syntheme and any pentad goes to another pentad. And by numerical coincidence you can show that there shouldn't be more than six distinct pentads, so every permutation of the points gives a permutation of the pentads. This takes permutations to permutations in a distinct way (try permuting two points), and it turns out you can only do this with six points.
  7. evilas

    evilas Sure, I'll put a custom title here

    Wait, huh? I tried permuting, say, the two top-right points of the first one and I can't find which one it goes to. I'm not fully understanding the symmetry of the thing.
  8. syntheme

    syntheme Active Member

    Remember that the colors only matter in that they're different from each other within each figure.

    (it goes to the fifth)
  9. evilas

    evilas Sure, I'll put a custom title here

    Ok, see I was seeing "permuting the colors" as a different transformation altogether. That makes sense!

    EDIT: Yeah, I had misread.
    EDIT 2: But wait, switching the middle one in the first one with any of them does preserve the colors! There's several permutations that preserve colors!
    Last edited: Jun 11, 2017
  10. syntheme

    syntheme Active Member

    That's an artifact of the code I used to make them. I could've used a different set of five colors for each pentad...
  11. evilas

    evilas Sure, I'll put a custom title here

    wait, what? Then what does "there is no nontrivial symmetry that preserves each color" mean? I'm confused.
  12. evilas

    evilas Sure, I'll put a custom title here

    hang on, let me clear something up.
    By "permuting the colors", do you mean "red goes to green, green goes to purple, etc"?
  13. syntheme

    syntheme Active Member

    Yeah, and a symmetry preserving each color is a permutation of the points keeping red red, green green, etc.
  14. evilas

    evilas Sure, I'll put a custom title here

    so these are 2 different transformations.

    Take the first one. Switch the top and the top-right points, and you get the fifth one with the colors permuted.
    However, take the first one and switch the middle and bottom-left points, and you get the fifth one without the colors permuted.

    That's what I'm not fully getting, tbh.
    Last edited: Jun 11, 2017
  15. syntheme

    syntheme Active Member

    Now try swapping both at once... ;)
  16. evilas

    evilas Sure, I'll put a custom title here

    ooh! Okay, I get it. Still not entirely grasp the full thing but I get it now! It's cool!
  17. syntheme

    syntheme Active Member

    Heh, I didn't entirely grasp the outer automorphism of S6 the first time I learned about it as an undergrad but I could tell that it's cool
    • Agree x 1
  18. Exohedron

    Exohedron Doesn't like words

    Exceptional Outer Automorphisms

    Suppose we have a set S and some operation * that takes two elements of S and returns an element of S. For instance, consider the integers with addition, +. You can add two integers and get another integer.

    Now suppose you have a function f that takes elements in S and returns elements of T, where S and T have operations *S and *T respectively, and you want f to respect the operations, i.e.
    f(a) *T f(b) = f(a *S b).
    We call such a function a homomorphism. In general, if S and T have several operations that correspond to each other, then we want a homorphism to respect all of the operations.

    Now suppose you want f to be a bijection, i.e. for any element y of T there is some element x of S such that f(x) = y, and for any pair of elements a and b, if f(a) = f(b) then a = b. If f is both a bijection and a homomorphism, we call it an isomorphism. S and T having an isomorphism, or being isomorphic for short, means that they essentially have the same form, that everything S does, T also does, and vice-versa.

    Now suppose that S and T are the same set, and the operations are the same. Then a homomorphism from S to itself is called an endomorphism, and an isomorphism from S to itself is called an automorphism.

    Automorphisms are essentially the symmetries of the object S with its operation, the same way that rotations are symmetries of a sphere.
    Like symmetries of a sphere, automorphisms form a group, often written Aut(S).

    Now suppose that S is a group, for instance the group of symmetries of a cube. For any element g in the group, we can form an automorphism Adg, which takes an element h in the group to Adg(h) = ghg-1. You can check that this is an automorphism of S for any g in S. We call these inner automorphisms because they're made using elements inside of S. The collection Inn(S) of inner automorphisms of S forms a group inside of Aut(S).
    But Aut(S) can be bigger than Inn(S). Consider our example of the integers with addition. You can show that the only automorphisms of the integers with addition are the identity map, which sends each integer to itself, and the negation map, which sends each integer to negative itself. But there is no integer a where a + b + -a = -b for all elements b, so the negation map isn't an inner automorphism. In this case, Inn(S) is boring because for any integer,
    a + b + -a = b,
    so the only element of Inn(S) is the identity.

    One would expect to call an automorphism that isn't inner an outer automorphism, but there's some technical stuff that makes this not the best notion of outer automorphism, so we're stuck with non-inner automorphism.

    So now consider the ways to rearrange n distinct objects. These rearrangements form a group Sn, called the symmetric group or the permutation group on n elements. A fun fact about Sn is that, if n > 2, there is an isomorphism from Sn to Inn(Sn) by sending g to Adg, and a funner fact is that if n is not 6, then Inn(Sn) = Aut(Sn).
    But the funnest fact is that Aut(S6) is strictly bigger than Inn(S6). In fact, twice as big.
    So there must be a map f from S6 to itself that is an automorphism, but such that there's no g in S6 such that f = Adg.

    How do we do this? We need some way to take an element of S6, which is a way to rearrange 6 things, and turn it into a way to rearrange a different 6 things in a fundamentally different manner.
    The synthemes and pentads provided above give one such way. Each pentad has six dots in it, and the dots are connected by colored lines. There are five colors, and each color breaks the six dots into three pairs. So a pentad really encodes five triples of pairs.
    For reasons I'm not going to get into, we'll label the middle dot by ∞, and the rest of them by 0 through 4, starting at the right and going counterclockwise.
    Also we're going to label the pentads A through F.
    So the pentad A is the quintet of triples of pairs:
    Now suppose you swapped 0 and 1. Then you get the following triplet of pairs:
    which corresponds to the pentad E, and E gets sent to A. Similarly, B gets swapped with F, and C with D.
    So we started with a single swap, 0 ↔ 1, and ended up with three swaps, A ↔ E, B ↔ F and C ↔ D.
    So that's how we take rearrangements of one set of six objects, the set {0, 1, 2, 3, 4, ∞}, and turn them into rearrangements of another set, {A, B, C, D, E, F}, and this map is an isomorphism (not an automorphism yet, because the rearrangements are acting on different sets). And then we just have some way of matching the two sets to get an actual automorphism f*.

    Now, is this map an inner automorphism, or a non-inner automorphism? Well, the important thing about inner automorphisms of Sn is that they can be achieved by just relabeling your objects. If your element g is the swap 0 ↔ 1, then Adg(h) is what you get if you swap the labels on 0 and 1, performed the rearrangement h, and then relabeled 0 and 1 again. In particular, h and Adg(h) move the same number of elements around.
    But in our map above, 0 ↔ 1 only moves two elements, but in terms of the pentads, all six pentads moved. So this can't be achieved by just an inner automorphism! So f is an actual, genuine non-inner automorphism!

    And only for n = 6 does Sn have such a non-inner automorphism! For this reason, we say that S6 has an exceptional outer automorphism, exceptional because no other permutation group has one.

    A similar case of an exceptional outer automorphism is for the groups SO(2n) of rotations in n dimensions. Recall that the rotation groups fix the origin, and then describe all of the rotations that you can do around the origin.
    If you pick a direction, and then talk about reflections in that direction that keep the origin fixed in place, then you can make an non-inner automorphism of SO(2n) by first reflecting, performing whatever rotation, and then reflecting back. I won't prove it, but this is not an inner automorphism.
    So Aut(SO(2n)) is at least twice as big as Inn(SO(2n)), and for n not equal to 4, Aut(SO(2n)) is in fact twice as big as Inn(SO(2n)).

    But the fun case is when n = 4. Then there are twice as many automorphisms as inner automorphisms**. There's the stuff you get by reflecting, but there are a bunch of other automorphisms that only appear for n = 4.

    If you slog through my posts on ADE classifications, you'll find that the Dynkin diagram for SO(2n) is a string of dots, with one end branching into two branches of length 1 each. The usual non-inner automorphism for SO(2n) corresponds to the symmetry of the diagram, where you can swap the two branches.
    When n = 4, the diagram looks like a single dot with three length 1 branches coming off of it. Then the factor of 6 is the number of ways to rearrange those three branches.
    So there's another case of exceptional outer automorphisms: SO(2n) has Aut(SO(2n)) being twice as big as Inn(SO(2n)), except when n = 4.

    As always, mathematicians want to understand these exceptional cases, whether there's something deep going on or whether it's just numerical coincidence. I can say that in the case of SO(8), there is something deeper going on: the octonions. I may explain the exact connection in another post, but it's a little complicated so I'm not going to do so here.

    * This is why we don't call non-inner automorphisms "outer automorphisms". The choice of matching between the sets {0, 1, 2, 3, 4, ∞} and {A, B, C, D, E, F} yield different automorphisms f, and in fact for f and f ' two such automorphisms, they differ by some inner automorphism Adg, i.e.
    f(h) = Adg(f '(h)).
    So to get rid of this dependence on the matching, we say that two automorphisms f and f ' are equivalent if there is such a g such that f(h) = Adg(f '(h)) for all h, and an outer automorphism is a set of equivalent automorphisms. Then we denote the set of outer automorphisms by Out(S).
    Note that the number of outer automorphisms is the number of automorphisms divided by the number of inner automorphisms, so we can say that Sn has 1 outer automorphism except when n is 6, where S6 has two outer automorphisms, and so on.

    ** Technically we have to move to a group called Spin(8), which is like SO(8) but with twice as many "rotations". It's still the case that Spin(2n) has two outer automorphisms for n not equal to 4, but Out(Spin(8)) has size 6.
  19. Exohedron

    Exohedron Doesn't like words

    Gray codes!

    Consider a cube. Can you find a way to start at a corner, go along edges, visit each other corner exactly once, and return to the start?
    The answer is yes. I'll let you puzzle out how to do it.
    What about a hypercube? Can you start at a corner, go along edges, visit each other corner exactly once, and return to the start?
    What about an n-dimensional hypercube?

    Such paths are called Hamiltonian cycles or circuits, not to be confused with Euler circuits, which go along each edge exactly once.

    Now suppose you have a friend to whom you want to send a sequence of three digits where each digit is 0 or 1. But for reasons* you can only send a number between 0 and 7 inclusive. The obvious thing to do is to use binary, so that "000" becomes "0", "001" becomes "1", "010" becomes "2", "011" becomes "3", and so on.
    And so if you want to send "011", you turn that into "3", and you send "3", and your friend receives "3" and turns that into "011". Great, you have successfully transmitted "011".
    But what if the way you send numbers is kind of unreliable and sometimes gets the number off by 1, so that if you send "3", sometimes your friend receives "2" or "4" instead?
    If your friend receives "2", then they turn that into "010", which is almost "011" but the last digit is wrong. 2 out of 3 isn't bad.
    But if your friend receives "4", then they turn that into "100" instead of "011", and so every digit is wrong!
    It would be nice if there were a way to assign 3-digit strings to numbers between 0 and 7 inclusive such that two numbers that differ by 1 correspond to strings that differ in only one digit, to minimize the effects of the unreliability: an off-by-one error in the numbers only makes the corresponding strings differ by one digit. We'd also like the strings assigned to 0 and to 7 to only differ by one digit. Can you come up with an assignment that fits these criteria?
    What about 4-digit strings of 0s and 1s? Is there an assignment to the numbers 0 through 15 inclusive such that two numbers that differ by 1 correspond to strings that differ in only one digit?

    We call such an assignment a "Gray code", named after Edward Gray who popularized them for telecommunications. So the assignment of 3-digit strings to the numbers 0 through 7 is a 3-bit Gray code, and the assignment of 4-digit strings to the numbers 0 through 15 is a 4-bit Gray code, and you can imagine longer Gray codes.

    0: 000
    1: 001
    2: 011
    3: 010
    4: 110
    5: 111
    6: 101
    7: 100

    Now back to the first question: if you haven't already, can you find a Hamiltonian cycle on a cube?

    * The reason is that the use case is in turning digital signals into analogue waveforms. Given a "reference" waveform, we can change its phase (think angle) to send signals; the receiver gets this phase-modulated waveform, compares it to the reference waveform, and extracts the phase change as an angle, hence a number, in the case given, the angle is a multiple of 2π/8, and so the angle 6π/8 turns into the number "3".
    Sometimes the wave gets messed up during transmission because of interference, so that the phase that the receiver sees is slightly off, and the receiver has to guess a bit at which multiple of 2π/8 was sent. This is where the off-by-1 error comes in, and also why the string corresponding to 0 and the string corresponding to 7 should differ in only one digit, because an angle of 7*2π/8 is close to an angle of 0.
    Last edited: Jun 23, 2017
    • Like x 1
  20. evilas

    evilas Sure, I'll put a custom title here

    I was gonna say "find a path around a square, connect it to the opposite square face, draw another path" - and I think that's extendable to n-dimensional cubes by induction, but as long as you can find a Gray code for n digits, you can find a Hamiltonian cycle on an n-dimensional cube, just placing it on a coordinate grid and going from one point to the other in the Grey code order.

    As a matter of fact, you could actually use the first method to find n-digit Grey codes, couldn't you? Like, that Grey code is the one gotten by finding the path around the square with X coordinate 0, jumping across to X coordinate 1, and repeating it in reverse, right?

    Edit: Let me try to find an n=4 Gray code using this method: Gray code with 0's, then flip the first bit to a 1, then go in reverse

    0: 0000
    1: 0001
    2: 0011
    3: 0010
    4: 0110
    5: 0111
    6: 0101
    7: 0100
    8: 1100
    9: 1101
    10: 1111
    11: 1110
    12: 1010
    13: 1011
    14: 1001
    15: 1000
    Last edited: Jun 23, 2017
    • Like x 1
  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice