1 L, as a dynamical system (Notes from Assignment #2) We take our definition of dynamical system to be an "object" along with a specific set of modifications that can be performed (dynamically) upon this object. In this case, the object is a bi-infinite straight road with a lamp post at every street corner and a marked lamp (the position of the lamplighter). There are two possible types of modifications: the lamplighter can walk any distance in either direction from a starting point and the lamplighter can turn the lamps "on" or "off." At any given moment the lamplighter is at a particular lamp post and a finite number of lamps are illuminated while the rest are not. We refer to such a moment, or configuration as a state" of the road (not to be confused with the "state" of an automaton). Any time the configuration changes, the road is in a new state. The road's state is changed over time by the lamplighter either walking to a different lamp post or turning lamps on or off (or both) In Figure 1, the bi-infinite road indexed by the integers. Lamps that are on are indicated by stars; lamps that are off by circles. The position of the lamplighter is indicated by an arrow pointing to an integer. The current state of the road is called the lampstand is represented by a number line; the lamps are -3 -2 1023 Figure 1: A lampstand where two lamps are illuminated and the lamplighter stands at 2. Let us call the set of all possible lampstands 2. Now that we have a visual image, we can formalize the dynamics of changing a lampstand by specifying distinct tasks which the lamplighter can perform on any element of 1. Move right to the next lamp 2. Move left to the next lamp We were unable to transcribe this image-3 -2-1 0 2 3 Figure 3: The lampstand Starting with the empty lampstand e, we can apply a composition of functions t, τ-1, σ and I to achieve 11. For instance the composition τσττστ-1 (or τοσο το τοσο τ-1) applied to e yields the lampstand configuration h. In keeping with standard function notation, the order of the composition is such that τ-1 is applied to e first and so on, reading from right to left. Figure 4 shows the details of the transformation from e to We were unable to transcribe this imagealways have the same output. It doesn't matter that there are different function compositions representing the same lampstand, since two functions are defined to be the same function as long as the domains are the same and the outputs are the same. However, some function compositions are clearly "shorter" than others. Here "shorter" refers to the number of tasks in the function composition. This begs the question, is there a "shortest" function composition for a given lampstand configuration? You explored this in Assignment #2 earlier in the semester. We are now ready to define our lamplighter group L2. Each element of L2 is a particular configuration of the road (i.e., an element of ); however, the lampstands can be identified (bijectively) with the set of all function compositions of σ,τ, and τ-1, evaluated at the empty lampstand. Thus, τ is identified with τ(e), and σ is identified with σ(e) (see Figure 5). Rather than draw a picture, we will usually refer to each lampstand by identifyingt with a function composed of the building blocks τ, τ-1 and σ-This allows us to define -3 -2 1 02 3 -3 -2 023 Figure 5: The lampstands τ(e) (above) and σ(e) (below) the identity element I(e), which we wil simply call "e" (since group elements are lampstands). We must also define the group multiplication. It is difficult to imagine "multiplying" two lampstands together, but thinking of our elements as functions, it is easy. The binary operation is function composition. If and l2 are in L2, then their product l1/2 is the composite function /2 followed by l. Since the composition of bijective functions is also bijective, the group operation is well defined, and inverses exist. Associativity follows since the group operation is function composition. Example 2. Let h-τστ2στ-1 and 12-τστ; then Looking at it dynamically, and working from right to eft, we start with /2: a lamplighter, whose name is Gilbert, starts at 0 on the lampstand and moves one step to the right (t) to 1, turns on the lamp (o), then moves one more step to the right (t) to 2 and stops. Gilbert is now standing at 2 on the lampstand, which becomes the new home base as he performs the moves for . For , he moves one step to the left, from 2 to 1, and turns off the lamp, then moves two steps right to 3 and turns on the lamp before finally moving one step to the right, ending up at 4. Note that the same configuration is achieved if we use the reduced form of l2, removing all pinches. 1 0 23 4 he lampstand ll2 At this point we can see that L2 forms a group. It has identity element e and is generated by and ơ. Inverse elements are easy to find. For example, the inverse of the element 11-τστ-στ-1 is 1--(τστ. στ-1)-I-τστ-2στ-1 and its lampstand configuration is shown in Figure 7. This completes the check that L2 is group. Figure 7: The lampstand l Given a particular lampstand, there is a visual method for finding its inverse without having to work out the dynamics of the configuration. For the lamplighter positioned at n, and a particular configuration of lighted lamps, reflect the lamp- lighter from n to -n, and translate the set of lighted lamps -n units along the number line (compare Figure 3 with Figure 7). 2 L2 with ordered pair elements, using an infinite direct sum (Notes for Assignment #3) Another way of representing the lampstand elements of L2 rather than by func- tions is by using an ordered pair. The first entry represents the location of the lamplighter and the second entry makes use of an infinite sum construction to indicate which lamps are illuminated. This allows us to encode the important information of a particular lampstand configuration concisely The elements of L2 can be represented by lez The Fare infinite tuples in which each entry is assigned a value of 0 or 1. However since only finitely many entries of the 3 can have value 1, we introduce pointer notation. X-(x1: . . . ,xp} is a finite set of pointers corresponding to the positions of the entries in the infinite tuple whose value is 1. For example, (12,,3)) means the lamplighter is standing at 12 and the lamps at -1 and 3 are lit. In order to add to y, we use the corresponding sets of pointers X and Y and calculate their symmetric difference, XA. Since addition is taking place in Z2, if an integer k appears in both X and Y, indicating that the kth entry of both and y is 1, the integer k drops out from the set XAY. Any integer that appears in exactly one of the pointer lists will appear in X△Y as well. For instance, if X--4,-1,7, 12) and Y -3,-1,5,7, 12) then XAY -4,-3,5) For two elements ll,h E L2, with 11 (a, X) and 12 = (b. Y), the group operation is where the expression X +b represents a new pointer set obtained by adding the integer b to each element of set X To illustrate, let us consider the elements g and configurations are given in Figures 8 and 9 of L2, whose lampstand -3 -2-1 0 2 3 Figure 8: The lampstand g -3 -21 02 3 Figure 9: The lampstand h Using the ordered pair notation, g corresponds to the ordered pair (-1,0·1,3)) and h corresponds to the ordered pair -2,1,3]). According to our formula, You may wonder why the group multiplication involves a “shift" in the second component of the ordered pair re h can be represented dynamically as a sequence of tasks performed on the empty lampstand, τ-1 στιστ-2 στ3 for g and τ-1 στ-4στ3 for h. Once the tasks for h are performed on the empty lampstand, the lamplighter is standing at -2, which becomes the new home base as we perform the moves for g! To visualize this "shift" followed by addition (mod 2), consider Figure 10, where the lighted lamps of the lampstand for h appear, followed by the lighted lamps of g shifted 2 units left, which is denoted as 'g-shift. Once we "add (mod 2) straight down" and calculate the new position of the lamplighter, the result is gh. presenting g. Recall from Section 1 that g and -3 -2023 h lamps g-shift lamps -3 -2 023 -3 -2-1 02 3 Figure 10: g*h Like the dynamical system, this representation describes lampstands; however, our elements are ordered pairs. The empty lampstand is represented by e (0,0) The esponding to ơ and T, are (0, [o)) andr (1,0). The inverse of s is s, and11,0) 3 Assignment #3 This assignment is due on Thursday 4/4/2019 at 10 am. You may submit it electronically as a pdf document or as a hard copy. Assignments late by 1 day will be penalized by 25%, 2 days late 50%, 3 days late 75% and any later they will no longer be accepted. Please be sure this writing is your own do NOT borrow from a friend you must submit your own work. I want to hear your own voice, not read a copy and paste of some other source!!! Exercise 1. Let g = τ-3στσ. [ 10 points each] a. Find g-1 b. Draw g as an element of c. Draw g as an element of . d. Write g and g as ordered pairs as described in Section 2 1 L, as a dynamical system (Notes from Assignment #2) We take our definition of dynamical system to be an "object" along with a specific set of modifications that can be performed (dynamically) upon this object. In this case, the object is a bi-infinite straight road with a lamp post at every street corner and a marked lamp (the position of the lamplighter). There are two possible types of modifications: the lamplighter can walk any distance in either direction from a starting point and the lamplighter can turn the lamps "on" or "off." At any given moment the lamplighter is at a particular lamp post and a finite number of lamps are illuminated while the rest are not. We refer to such a moment, or configuration as a state" of the road (not to be confused with the "state" of an automaton). Any time the configuration changes, the road is in a new state. The road's state is changed over time by the lamplighter either walking to a different lamp post or turning lamps on or off (or both) In Figure 1, the bi-infinite road indexed by the integers. Lamps that are on are indicated by stars; lamps that are off by circles. The position of the lamplighter is indicated by an arrow pointing to an integer. The current state of the road is called the lampstand is represented by a number line; the lamps are -3 -2 1023 Figure 1: A lampstand where two lamps are illuminated and the lamplighter stands at 2. Let us call the set of all possible lampstands 2. Now that we have a visual image, we can formalize the dynamics of changing a lampstand by specifying distinct tasks which the lamplighter can perform on any element of 1. Move right to the next lamp 2. Move left to the next lamp -3 -2-1 0 2 3 Figure 3: The lampstand Starting with the empty lampstand e, we can apply a composition of functions t, τ-1, σ and I to achieve 11. For instance the composition τσττστ-1 (or τοσο το τοσο τ-1) applied to e yields the lampstand configuration h. In keeping with standard function notation, the order of the composition is such that τ-1 is applied to e first and so on, reading from right to left. Figure 4 shows the details of the transformation from e to always have the same output. It doesn't matter that there are different function compositions representing the same lampstand, since two functions are defined to be the same function as long as the domains are the same and the outputs are the same. However, some function compositions are clearly "shorter" than others. Here "shorter" refers to the number of tasks in the function composition. This begs the question, is there a "shortest" function composition for a given lampstand configuration? You explored this in Assignment #2 earlier in the semester. We are now ready to define our lamplighter group L2. Each element of L2 is a particular configuration of the road (i.e., an element of ); however, the lampstands can be identified (bijectively) with the set of all function compositions of σ,τ, and τ-1, evaluated at the empty lampstand. Thus, τ is identified with τ(e), and σ is identified with σ(e) (see Figure 5). Rather than draw a picture, we will usually refer to each lampstand by identifyingt with a function composed of the building blocks τ, τ-1 and σ-This allows us to define -3 -2 1 02 3 -3 -2 023 Figure 5: The lampstands τ(e) (above) and σ(e) (below) the identity element I(e), which we wil simply call "e" (since group elements are lampstands). We must also define the group multiplication. It is difficult to imagine "multiplying" two lampstands together, but thinking of our elements as functions, it is easy. The binary operation is function composition. If and l2 are in L2, then their product l1/2 is the composite function /2 followed by l. Since the composition of bijective functions is also bijective, the group operation is well defined, and inverses exist. Associativity follows since the group operation is function composition. Example 2. Let h-τστ2στ-1 and 12-τστ; then Looking at it dynamically, and working from right to eft, we start with /2: a lamplighter, whose name is Gilbert, starts at 0 on the lampstand and moves one step to the right (t) to 1, turns on the lamp (o), then moves one more step to the right (t) to 2 and stops. Gilbert is now standing at 2 on the lampstand, which becomes the new home base as he performs the moves for . For , he moves one step to the left, from 2 to 1, and turns off the lamp, then moves two steps right to 3 and turns on the lamp before finally moving one step to the right, ending up at 4. Note that the same configuration is achieved if we use the reduced form of l2, removing all pinches. 1 0 23 4 he lampstand ll2 At this point we can see that L2 forms a group. It has identity element e and is generated by and ơ. Inverse elements are easy to find. For example, the inverse of the element 11-τστ-στ-1 is 1--(τστ. στ-1)-I-τστ-2στ-1 and its lampstand configuration is shown in Figure 7. This completes the check that L2 is group. Figure 7: The lampstand l Given a particular lampstand, there is a visual method for finding its inverse without having to work out the dynamics of the configuration. For the lamplighter positioned at n, and a particular configuration of lighted lamps, reflect the lamp- lighter from n to -n, and translate the set of lighted lamps -n units along the number line (compare Figure 3 with Figure 7). 2 L2 with ordered pair elements, using an infinite direct sum (Notes for Assignment #3) Another way of representing the lampstand elements of L2 rather than by func- tions is by using an ordered pair. The first entry represents the location of the lamplighter and the second entry makes use of an infinite sum construction to indicate which lamps are illuminated. This allows us to encode the important information of a particular lampstand configuration concisely The elements of L2 can be represented by lez The Fare infinite tuples in which each entry is assigned a value of 0 or 1. However since only finitely many entries of the 3 can have value 1, we introduce pointer notation. X-(x1: . . . ,xp} is a finite set of pointers corresponding to the positions of the entries in the infinite tuple whose value is 1. For example, (12,,3)) means the lamplighter is standing at 12 and the lamps at -1 and 3 are lit. In order to add to y, we use the corresponding sets of pointers X and Y and calculate their symmetric difference, XA. Since addition is taking place in Z2, if an integer k appears in both X and Y, indicating that the kth entry of both and y is 1, the integer k drops out from the set XAY. Any integer that appears in exactly one of the pointer lists will appear in X△Y as well. For instance, if X--4,-1,7, 12) and Y -3,-1,5,7, 12) then XAY -4,-3,5) For two elements ll,h E L2, with 11 (a, X) and 12 = (b. Y), the group operation is where the expression X +b represents a new pointer set obtained by adding the integer b to each element of set X To illustrate, let us consider the elements g and configurations are given in Figures 8 and 9 of L2, whose lampstand -3 -2-1 0 2 3 Figure 8: The lampstand g -3 -21 02 3 Figure 9: The lampstand h Using the ordered pair notation, g corresponds to the ordered pair (-1,0·1,3)) and h corresponds to the ordered pair -2,1,3]). According to our formula, You may wonder why the group multiplication involves a “shift" in the second component of the ordered pair re h can be represented dynamically as a sequence of tasks performed on the empty lampstand, τ-1 στιστ-2 στ3 for g and τ-1 στ-4στ3 for h. Once the tasks for h are performed on the empty lampstand, the lamplighter is standing at -2, which becomes the new home base as we perform the moves for g! To visualize this "shift" followed by addition (mod 2), consider Figure 10, where the lighted lamps of the lampstand for h appear, followed by the lighted lamps of g shifted 2 units left, which is denoted as 'g-shift. Once we "add (mod 2) straight down" and calculate the new position of the lamplighter, the result is gh. presenting g. Recall from Section 1 that g and -3 -2023 h lamps g-shift lamps -3 -2 023 -3 -2-1 02 3 Figure 10: g*h Like the dynamical system, this representation describes lampstands; however, our elements are ordered pairs. The empty lampstand is represented by e (0,0) The esponding to ơ and T, are (0, [o)) andr (1,0). The inverse of s is s, and11,0) 3 Assignment #3 This assignment is due on Thursday 4/4/2019 at 10 am. You may submit it electronically as a pdf document or as a hard copy. Assignments late by 1 day will be penalized by 25%, 2 days late 50%, 3 days late 75% and any later they will no longer be accepted. Please be sure this writing is your own do NOT borrow from a friend you must submit your own work. I want to hear your own voice, not read a copy and paste of some other source!!! Exercise 1. Let g = τ-3στσ. [ 10 points each] a. Find g-1 b. Draw g as an element of c. Draw g as an element of . d. Write g and g as ordered pairs as described in Section 2