(************** Content-type: application/mathematica ************** CreatedBy='Mathematica 5.0' Mathematica-Compatible Notebook This notebook can be used with any Mathematica-compatible application, such as Mathematica, MathReader or Publicon. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. *******************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 145995, 4838]*) (*NotebookOutlinePosition[ 153192, 5097]*) (* CellTagsIndexPosition[ 151881, 5043]*) (*WindowFrame->Normal*) Notebook[{ Cell["\[Copyright] 2003 K. Sutner ", "SmallText"], Cell[CellGroupData[{ Cell["Functions", "Title", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:1"], Cell[CellGroupData[{ Cell["Functions", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:2"], Cell[CellGroupData[{ Cell[" Motivation", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:3"], Cell[CellGroupData[{ Cell["Calculus", "Subsubsection", CellTags->"c:4"], Cell[TextData[{ "\nIn calculus, functions are typically given by expressions, something \ like \n\n\t", Cell[BoxData[ \(TraditionalForm\`f(x)\ = 2\ x\^2 - \ 5\ x\ + \ 3\)]], ",\nor\n\t", Cell[BoxData[ \(TraditionalForm\`g(x)\ = \ \(x + 1\)\/\(x - 1\)\)]], ",\nor\n\t", Cell[BoxData[ \(TraditionalForm\`h(x)\ = \ sin(x)\ + \ cos(x)\)]], ".\n\t\nOne nice feature of these functions is that one can plot them:" }], "Text"], Cell["Plot[ 2 x^2 - 5 x + 3, {x,-10,10},PlotStyle->Blue ];", "Input"], Cell["Plot[ 2 x^2 - 5 x + 3, {x,0,2},PlotStyle->Blue ];", "Input"], Cell["Plot[ Sign[x], {x,-1,1},PlotStyle->Blue ];", "Input"], Cell["Plot[ Sin[x]+Cos[x], {x,-2Pi,2Pi},PlotStyle->Blue ];", "Input"], Cell["Plot[Exp[-x^2] Sin[10 x],{x,-Pi,Pi},PlotStyle->Blue];", "Input"], Cell["Plot[ (x+1)/(x-1), {x,-1,2},PlotStyle->Blue ];", "Input"], Cell["Plot3D[ Sin[x y], {x,0,4}, {y,0,4}, PlotPoints->50 ];", "Input", AspectRatioFixed->True], Cell["\<\ Plot3D[ x y / (x^2 + y^2 ), {x,-1,1}, {y,-1,1}, \t\tPlotPoints -> 50 ];\ \>", "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Programming", "Subsubsection", CellTags->"c:5"], Cell["\<\ In programming, functions are a key concept. In fact, in C a \ program is in essence just a collection of functions that call each other in \ some well-organized way. You have seen examples such as \ \>", "Text"], Cell["\<\ \tint sum( int n ) \t{ \t\tint s = 0,i; \t\tfor(i=1;i<=n;i++) \t\t\ts = s + i; \t\treturn s; \t}\ \>", "Program"], Cell[TextData[{ "albeit perhaps in a slightly different syntax. \nNote that this is really \ very similar to functions in calculus: instead of a simple expression we now \ have a piece of code in some programming language. The only difference is \ that the rules for evaluation are a bit more complicated. In calculus, we \ only use ordinary arithmetic, plus a few special functions such as ", Cell[BoxData[ \(TraditionalForm\`sin(x)\)]], " or ", Cell[BoxData[ \(TraditionalForm\`log(x)\)]], ". In programming, there are in addition logical control structures, \ loops, recursion and such like. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Intensional versus Extensional", "Subsubsection", CellTags->"c:6"], Cell[TextData[{ "In either case, the description is intensional: we are given a method to \ compute the value ", Cell[BoxData[ \(TraditionalForm\`y = \ f(x)\)]], " of the function. The problem with this approach is that many different \ methods can produce the same output. For example, the last program could also \ have been written as " }], "Text"], Cell["\<\ \tint sum( int n ) \t{ \t\treturn n*(n+1)/2; \t}\ \>", "Program"], Cell[TextData[{ "The code is completely different, but the output is the same. \nMore \ generally, if one were to try to define what a function is, one would point \ out some method to transform input values into output values. Thus, a \ function is a kind of rule, an algorithm. Note that in order to really \ specify a function, one also should say what the admissible input values are, \ and what the output values are. Othewise one runs into difficulties with \ \"definitions\" such as \n\t", Cell[BoxData[ \(TraditionalForm\`g(x)\ = \ \(x + 1\)\/\(x - 1\)\)]], ".\nThe ", Cell[BoxData[ \(TraditionalForm\`x\)]], " here supposedly ranges over the reals, but what happens at ", Cell[BoxData[ \(TraditionalForm\`x = 1\)]], "? Should the function be undefined, or should the output value be \ something like ", Cell[BoxData[ \(TraditionalForm\`\[Infinity]\)]], " ? \nOr how about \n\t", Cell[BoxData[ \(TraditionalForm\`g(x)\ = \ \((x - 1)\)\^2\/\(x - 1\)\)]], " ?\nIs that the same as ", Cell[BoxData[ \(TraditionalForm\`g(x)\ = \ x + 1\)]], " ?" }], "Text"], Cell["\<\ We now give a definition that construes functions as a special type of \ relation. This definition is much broader, and allows for many functions that \ are not as computational as one is used to from programming. This turns out \ to be valuable in both mathematics and CS. Our definition of what a function is will be completely extensional, the only \ thing that matters is the connection between input and output. How the \ latter is calculated is irrelevant. In fact, as we will see, in most cases \ there is no method to compute the output given the input. \ \>", "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Definitions", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:7"], Cell[CellGroupData[{ Cell["Total Functions", "Subsubsection", CellTags->"c:8"], Cell[TextData[{ "Let ", Cell[BoxData[ \(TraditionalForm\`\(\(A\)\(\ \)\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`B\)]], " be two sets. A ", StyleBox["function ", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`f\)]], StyleBox[" from ", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`A\)]], " ", StyleBox[" to ", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`B\)]], " is a relation from ", Cell[BoxData[ \(TraditionalForm\`A\)]], " to ", Cell[BoxData[ \(TraditionalForm\`B\)]], " that satisfies the following conditions (we are writing the relation is \ infix notation): \n\n\t\[Bullet] totality: ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ x\ \[Element] \ \(\(A\)\(\ \ \ \)\(\[Exists] \ y\ \[Element] \ B\ \((\ \ x\ f\ y\ )\)\)\(\ \)\)\)]], ".\n\t\[Bullet] single-valuedness: ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ x\ \[Element] \ A\ \ \ \(\[ForAll] \ y\), y\^\[Prime]\ \[Element] \ \(\(B\)\(\ \)\((\ \ x\ f\ y\ \ \[And] \ x\ f\ y\^\[Prime]\ \[DoubleLongRightArrow]\ \ y\ = \ y\^\[Prime])\)\(\ \)\)\)]], ".\n\t\nIn other words, for all ", Cell[BoxData[ \(TraditionalForm\`x\)]], " in ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", there is a unique ", Cell[BoxData[ \(TraditionalForm\`y\)]], " in ", Cell[BoxData[ \(TraditionalForm\`B\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`x\ f\ y\)]], " holds. Note that we are thinking of ", Cell[BoxData[ \(TraditionalForm\`f\)]], " as a relation here, so ", Cell[BoxData[ \(TraditionalForm\`x\ f\ y\)]], " means that ", Cell[BoxData[ \(TraditionalForm\`x\)]], " and ", Cell[BoxData[ \(TraditionalForm\`y\)]], " are related by ", Cell[BoxData[ \(TraditionalForm\`f\)]], ". Traditionally, this is always written in the form \n\t", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ y\)]], "\nand we will use only this notation from now on. Even worse would be to \ write the relation ", Cell[BoxData[ \(TraditionalForm\`f\)]], " in the form ", Cell[BoxData[ \(TraditionalForm\`f(x, y)\)]], ", since this would produce endless confusion with functions of two \ arguments. A function is generally indicated by \n\t ", Cell[BoxData[ \(TraditionalForm\`f\ : \ A\ \[LongRightArrow]\ B\)]], ". \nThe set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " is the ", StyleBox["domain", FontColor->RGBColor[0, 0, 1]], " of ", Cell[BoxData[ \(TraditionalForm\`f\)]], ", and ", Cell[BoxData[ \(TraditionalForm\`B\)]], " is the ", StyleBox["codomain", FontColor->RGBColor[0, 0, 1]], " of ", Cell[BoxData[ \(TraditionalForm\`f\)]], ". The set of elements of ", Cell[BoxData[ \(TraditionalForm\`B\)]], " that are images of an element of ", Cell[BoxData[ \(TraditionalForm\`A\)]], " under ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is called the ", StyleBox["range", FontColor->RGBColor[0, 0, 1]], " of ", Cell[BoxData[ \(TraditionalForm\`f\)]], ": \n\t", Cell[BoxData[ \(TraditionalForm\`rg(f)\ = \ {\ y\ \[Element] \ B\ | \ \ \[Exists] \ x\ \[Element] \ A\ \((\ \ f(x)\ = \ y\ )\)\ \ }\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "A function ", Cell[BoxData[ FormBox[ RowBox[{" ", FormBox[\(f\ : \ A\ \[LongRightArrow]\ B\), "TraditionalForm"]}], TraditionalForm]]], " is meant to be applied to arguments in ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", but it is often convenient to apply the function to whole subsets of ", Cell[BoxData[ \(TraditionalForm\`A\_0 \[SubsetEqual] A\)]], ":\n\t", Cell[BoxData[ \(TraditionalForm\`f( A\_0)\ = \ {\ \ f(x)\ | \ \ x\ \[Element] \ A\ }\ \[SubsetEqual] \ B\)]], ". \nSo, we can think of ", Cell[BoxData[ \(TraditionalForm\`\(\(f\)\(\ \)\)\)]], " also as a function ", Cell[BoxData[ \(TraditionalForm\`\(\[ScriptCapitalP]( A)\)\ \[LongRightArrow]\ \(\[ScriptCapitalP](B)\)\)]], ". Also important is a kind of inverse, applied to subsets ", Cell[BoxData[ \(TraditionalForm\`B\_0\ \[SubsetEqual] \ B\)]], " of the codomain:\n\t", Cell[BoxData[ \(TraditionalForm\`\(f\^\(-1\)\)( B\_0)\ = \ {\ \ \ x\ \[Element] \ A\ | \ f(x)\ \[Element] \ B\_0}\ \[SubsetEqual] \ A\)]], ". \nThus, ", Cell[BoxData[ \(TraditionalForm\`f\^\(-1\)\)]], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\(:\)\(\ \)\(\(\[ScriptCapitalP]( B)\)\ \[LongRightArrow]\ \(\[ScriptCapitalP](A)\)\)\)\)\)]], ". Note that ", Cell[BoxData[ \(TraditionalForm\`\(\(\(f\^\(-1\)\)({b})\)\(\ \)\)\)]], " may well be empty, or contain several elements, so we do not in general \ obtain a function from ", Cell[BoxData[ \(TraditionalForm\`B\)]], " to ", Cell[BoxData[ \(TraditionalForm\`A\)]], " this way. " }], "Text"], Cell[TextData[{ "From a computational point of view, functions are often given as \ algorithms, and we can apply the algorithm to input ", Cell[BoxData[ \(TraditionalForm\`x\)]], " to obtain output ", Cell[BoxData[ \(TraditionalForm\`y\)]], ". The totality condition says that the algorithm must work for all \ elements of the domain, and the single-valuedness conditions says that the \ output must always be the same for a fixed input. \nNote, though, that our \ definition does not require the existence of an algorithm to compute ", Cell[BoxData[ \(TraditionalForm\`f\)]], ", as long as ", Cell[BoxData[ \(TraditionalForm\`y\)]], " is uniquely determined by ", Cell[BoxData[ \(TraditionalForm\`x\)]], ", we have a (partial) function. Figuring out how to compute ", Cell[BoxData[ \(TraditionalForm\`f(x)\)]], " given ", Cell[BoxData[ \(TraditionalForm\`x\)]], " may be very difficult. In fact, there are many functions where it is \ simply impossible: there is no algorithm to compute the value of certain \ functions. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Partial Functions", "Subsubsection", CellTags->"c:9"], Cell[TextData[{ "Sometimes one considers functions ", Cell[BoxData[ \(TraditionalForm\`f\ : \ A\ \[LongRightArrow]\ B\)]], " that are not defined for all elements of ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", but only for some subset ", Cell[BoxData[ \(TraditionalForm\`A\_0\ \[SubsetEqual] \ A\)]], ". In other words, one considers relations that only satisfy the \ single-valuedness condition, but not necessarily the totality condition. We \ will refer to these functions as ", StyleBox["partial functions", FontColor->RGBColor[0, 0, 1]], ". Partial functions are quite natural. For example, the logarithm function \ is not defined on all reals, but only on the positive reals. Likewise, the \ inverse operation ", Cell[BoxData[ \(TraditionalForm\`1\/x\)]], " is defined for all reals other than 0. The operation ", StyleBox["Rest", "SmallText"], " is defined for all lists, except the empty list. \nUnfortunately, the \ set ", Cell[BoxData[ \(TraditionalForm\`A\_\(\(0\)\(\ \)\) \[SubsetEqual] \ A\)]], " is also called the domain of ", Cell[BoxData[ \(TraditionalForm\`f\)]], ", for ", Cell[BoxData[ \(TraditionalForm\`f\)]], " a partial function. \nA function for us is by default total, but there \ are texts that assume functions to be partial in general, and refer \ specifically to total functions whenever the totality condition is satisfied. \ " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "The standard way to specify a function, say, in calculus, is to write \ something like\n\t", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\(\[DoubleStruckCapitalR]\ \ \[LongRightArrow]\ \ \[DoubleStruckCapitalR]\)\(\ \)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ x\^3 + \ 1\)]], ".\nHere the domain and codomain are both \[DoubleStruckCapitalR], and \ there is no problem. But, you might also see \n\t", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\(\[DoubleStruckCapitalR]\ \ \[LongRightArrow]\ \ \[DoubleStruckCapitalR]\)\(\ \)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ \(x\ + \ 1\)\/\(x\ - \ 1\)\)]], ",\nand then ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is really a partial function with domain ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalR]\ - {0}\)]], ". Likewise, \n\t", Cell[BoxData[ \(TraditionalForm\`Rest\ : \ Lists\ \[LongRightArrow]\ Lists\)]], ", ", Cell[BoxData[ \(TraditionalForm\`Rest(\((a\_1, \[Ellipsis], a\_n)\))\ = \ \((a\_2, \[Ellipsis], a\_n)\)\)]], " \ndefines a partial function since the definition makes no sense for ", Cell[BoxData[ \(TraditionalForm\`n = 0\)]], ", the empty list. " }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell["Dummy Variables", "Subsubsection", CellTags->"c:10"], Cell[TextData[{ "Note that in all these definitions ", Cell[BoxData[ \(TraditionalForm\`\(\(x\)\(\ \)\)\)]], " is just a dummy variably and could be replaced by any other variable. \ More importantly, we actually have attached a name to the function, namely ", Cell[BoxData[ \(TraditionalForm\`f\)]], ". As we have seen, in programming it is on occasion preferable not to \ define a name for a function, and ", StyleBox["Mathematica", FontSlant->"Italic"], " has a special mechanism to do so. There is a similar device in \ mathematics, called ", Cell[BoxData[ \(TraditionalForm\`\[Lambda]\)]], "-abstraction. The cubic polynomial from above could be written as ", Cell[BoxData[ \(TraditionalForm\`\[Lambda]\ x\ \((\ x\^3 + \ 1\ )\)\)]], ". Or the function which returns the second of its arguments is written ", Cell[BoxData[ \(TraditionalForm\`\[Lambda]\ x, y\ \((\ y\ )\)\)]], ". There is a whole calculus of such ", Cell[BoxData[ \(TraditionalForm\`\[Lambda]\)]], "-expressions, but we will use them only in rare cases. \nNote that in \ Mathematica we can model \[Lambda] expressions as\n\t\tFunction[ x, ...x... \ ].\nAgain, ", Cell[BoxData[ \(TraditionalForm\`x\)]], " is just a placeholder, a dummy variable that could be replaced by \ others." }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Properties of Functions", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:11"], Cell["\<\ As with relations, functions may have special properties that make \ them particularly interesting.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[CellGroupData[{ Cell[" Surjectivity", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:12"], Cell[TextData[{ "A function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\(A\ \[LongRightArrow]\ \ B\)\(\ \)\)\)]], " is ", StyleBox["surjective (onto) ", FontColor->RGBColor[0, 0, 1]], " iff ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] \ y\ \[Element] \ B\ \ \ \(\[Exists] \ x\ \[Element] \ A\ \((\ \ f(x)\ = \ y\ )\)\)\)]], ". \nIn other words, the range of ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is all of ", Cell[BoxData[ \(TraditionalForm\`B\)]], ". \n\n\n", StyleBox["Examples", FontWeight->"Bold"], ": \nThe identity relation ", Cell[BoxData[ \(TraditionalForm\`I\_A\)]], " is in particular a function, the identity function on ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". It is surjective. \nThe function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\(\[DoubleStruckCapitalR]\ \ \[LongRightArrow]\ \ \[DoubleStruckCapitalR]\)\(\ \)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ x\^3\)]], ", on the reals is surjective, but ", Cell[BoxData[ \(TraditionalForm\`g\ : \ \(\(\[DoubleStruckCapitalR]\ \ \[LongRightArrow]\ \ \[DoubleStruckCapitalR]\)\(\ \)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`g(x)\ = \ x\^2\)]], ", is not. \nNote that it is crucial here that the domain of ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalR]\)]], ", the set of real numbers. If we replace ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalR]\)]], " by ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalQ]\)]], ", the set of rational numbers, the function is no longer surjective. \ For example, there is no ", Cell[BoxData[ \(TraditionalForm\`\(\(x\)\(\ \)\(\[Element]\)\(\ \)\(\ \[DoubleStruckCapitalQ]\)\(\ \)\)\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ 2\)]], ". Right?\nThe function ", StyleBox["Rest", FontFamily->"Courier"], " from all non-empty lists to all lists is surjective. Note, though, that \ if we insist on thinking of ", StyleBox["Rest", FontFamily->"Courier"], " as a function from lists to lists, it will have to partial." }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Injectivity", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:13"], Cell[TextData[{ "A function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\(A\ \[LongRightArrow]\ \ B\)\(\ \)\)\)]], " is ", StyleBox["injective (1-1) ", FontColor->RGBColor[0, 0, 1]], " iff ", Cell[BoxData[ \(TraditionalForm\`\[ForAll] x\ , \ x\^\[Prime] \[Element] \ A\ \((\ \ f( x)\ = \ \(\(f( x\^\[Prime])\)\ \ \[DoubleLongRightArrow]\ \ x\ = \ x\^\[Prime]\)\ )\)\)]], ". \nIn other words, given ", Cell[BoxData[ \(TraditionalForm\`\(\(y\)\(\ \)\)\)]], "in the range of ", Cell[BoxData[ \(TraditionalForm\`f\)]], " we can determine what the corresponding ", Cell[BoxData[ \(TraditionalForm\`x\)]], " is: there is a unique ", Cell[BoxData[ \(TraditionalForm\`x\)]], " in ", Cell[BoxData[ \(TraditionalForm\`A\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ y\)]], ". \n\n\n", StyleBox["Examples", FontWeight->"Bold"], ": \nThe identity function ", Cell[BoxData[ \(TraditionalForm\`I\_A\)]], " is injective. \nThe function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\(\[DoubleStruckCapitalR]\ \ \[LongRightArrow]\ \ \[DoubleStruckCapitalR]\)\(\ \)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ x\^3\)]], ", on the reals is injective, but ", Cell[BoxData[ \(TraditionalForm\`g\ : \ \(\(\[DoubleStruckCapitalR]\ \ \[LongRightArrow]\ \ \[DoubleStruckCapitalR]\)\(\ \)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`g(x)\ = \ x\^2\)]], ", is not. \nThe function ", StyleBox["Rest", FontFamily->"Courier"], " from all non-empty lists to all lists not injective, but the function ", StyleBox["Reverse", "SmallText"], " from lists to lists is injective (it is also total). \n" }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Bijectivity and Permutations", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:14"], Cell[TextData[{ "A function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\(A\ \[LongRightArrow]\ \ B\)\(\ \)\)\)]], " is ", StyleBox["bijective (1-1 and onto) ", FontColor->RGBColor[0, 0, 1]], " iff ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is both injective and surjective. \n\nA bijection establishes a strict \ correspondence between the elements in ", Cell[BoxData[ \(TraditionalForm\`A\)]], " and the elements in ", Cell[BoxData[ \(TraditionalForm\`B\)]], ", everybody in one set has exactly one partner in the other set. \nA \ bijection whose domain is the same as the codomain is often called a ", StyleBox["permutation", FontColor->RGBColor[0, 0, 1]], ", in particular when the domain is finite. \n\n", StyleBox["Examples", FontWeight->"Bold"], ": \nThe identity function is bijective. \nThe function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\(\[DoubleStruckCapitalR]\ \ \[LongRightArrow]\ \ \[DoubleStruckCapitalR]\)\(\ \)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ x\^3\)]], ", on the reals is bijective, but ", Cell[BoxData[ \(TraditionalForm\`g\ : \ \(\(\[DoubleStruckCapitalR]\ \ \[LongRightArrow]\ \ \[DoubleStruckCapitalR]\)\(\ \)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`g(x)\ = \ x\^2\)]], ", is not. \nThe logarithm function ", Cell[BoxData[ \(TraditionalForm\`log\ : \ \(\[DoubleStruckCapitalR]\^+\)\ \[LongRightArrow]\ \[DoubleStruckCapitalR]\)]], " is a bijection between the positive reals and all reals.\nThe successor \ function on the integers is a bijection, but on the natural numbers it fails \ to be surjective. \nThe function ", StyleBox["Rest", FontFamily->"Courier"], " from all non-empty lists to all lists not bijective, but ", StyleBox["Reverse", "SmallText"], " is a bijection." }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Classes of Functions", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:15"], Cell[TextData[{ "We will write \n\t\t", Cell[BoxData[ \(TraditionalForm\`Func(A, B)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(Inj(A, B)\)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`Surj(A, B)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`Bij(A, B)\)]], " \n\t\t\nfor the set of all functions from ", Cell[BoxData[ \(TraditionalForm\`A\)]], " to B, all injective such functions, all surjective such functions, and \ all bijective such functions, respectively. \nNote the ", Cell[BoxData[ \(TraditionalForm\`Bij(A, B)\ \ \ = \ Inj(A, B)\ \ \ \[Intersection] \ \ Surj(A, B)\ \ \ \[SubsetEqual] \ \ Func(A, B)\)]], ". \n\nFor finite domains and codomains one has the following lemma. \n", StyleBox["Lemma", FontWeight->"Bold"], ": For any two finite sets ", Cell[BoxData[ \(TraditionalForm\`A, \ B\)]], " of equal size", StyleBox[": ", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`Bij(A, B)\ \ \ = \ \ \(Inj(A, B)\ \ \ = \ \ Surj(A, B)\)\)]], ". \nProof:\nWe may safely assume that the set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " in question is of the form ", Cell[BoxData[ \(TraditionalForm\`\([n]\)\ \ = \ {1, 2, \[Ellipsis], n}\)]], ", otherwise we can just rename the elements. \nNow consider an injective \ function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\(A\ \[LongRightArrow]\ \ B\)\(\ \)\)\)]], " . Since ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(i < j\ \[DoubleLongRightArrow]\ \ \(f(i)\)\ \[NotEqual] \ f(j)\)\)\)]], ", the range of ", Cell[BoxData[ \(TraditionalForm\`f\)]], ", ", Cell[BoxData[ \(TraditionalForm\`rg(f)\ \[SubsetEqual] \ B\)]], ", must have size ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". But then ", Cell[BoxData[ \(TraditionalForm\`rg(f)\ = \ B\)]], ", so that ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is also surjective. \nOn the other hand, suppose ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is surjective. If we had ", Cell[BoxData[ \(TraditionalForm\`f(i)\ = \ f(j)\)]], " for some ", Cell[BoxData[ \(TraditionalForm\`i\ < \ j\)]], ", then the size of ", Cell[BoxData[ \(TraditionalForm\`rg(f)\)]], " would be at most ", Cell[BoxData[ \(TraditionalForm\`n - 1\)]], ", contradicting surjectivity. Hence, ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is injective. \nThus, ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is injective iff ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is surjective, and either property implies bijectivity. \n\ \[EmptySquare]", StyleBox["\n", FontWeight->"Bold"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Note that the last lemma is emphatically false for infinite sets. As a \ standard example, consider the successor function ", Cell[BoxData[ \(TraditionalForm\`S\ : \ \[DoubleStruckCapitalN]\ \[LongRightArrow]\ \ \[DoubleStruckCapitalN]\)]], " defined by ", Cell[BoxData[ \(TraditionalForm\`S(x)\ = \ x + 1\)]], ". Clearly, ", Cell[BoxData[ \(TraditionalForm\`S\)]], " is injective but not surjective. On the other hand, g : \ \[DoubleStruckCapitalN] \[LongRightArrow] \[DoubleStruckCapitalN] defined by \ ", Cell[BoxData[ \(TraditionalForm\`g(x)\ = \ \[LeftFloor]\ x\/2\ \[RightFloor]\)]], " is surjective, but not injective. \nAs a matter of fact, there is a \ bijection between the interval ", Cell[BoxData[ \(TraditionalForm\`\([0, 1]\)\ \ \[Subset] \ \[DoubleStruckCapitalR]\)]], ", the unit interval on the real line, and ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalR]\^2\)]], ", the points in the plane. This is rather counter intuitive, since the \ unit interval appears to be very small subset of the whole plane, so it \ should be of much smaller size. \nIn general, dealing with functions on \ infinite sets is quite a bit more complicated, and we will focus on functions \ on finite sets. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Some Pictures", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:16"], Cell[TextData[{ "The plotting routines we used for relations (represented as lists of \ pairs), are really ideal for functions: there is exactly one line starting at \ each point in the left column, so the pictures don't get too crowded. \nHere \ are the pictures of some typical functions from ", Cell[BoxData[ \(TraditionalForm\`\([8]\)\)]], " to ", Cell[BoxData[ \(TraditionalForm\`\([8]\)\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[f,g,h] f[x_] := Min[ x+1, 8 ] g[x_] := Mod[ x^2, 8 ] + 1; h[x_] := Mod[ x+3, 8 ] + 1;\ \>", "InputOnly", AspectRatioFixed->True], Cell["\<\ First, the generic picture that one finds in all text books. The \ dots on the left indicate the domain, and the ones on the right the codomain. \ \ \>", "Text"], Cell["PlotFunction[ f, 8, 1 ];", "Input", AspectRatioFixed->True], Cell["We can label the points:", "Text"], Cell["PlotFunction[ f, 8, 1, LabelGrid->Automatic ];", "Input", AspectRatioFixed->True], Cell[TextData[{ "Note that the points in the codomain are rendered blue when they are not \ in the range of ", Cell[BoxData[ \(TraditionalForm\`f\)]], ", and red otherwise. So, the last function is neither surjective nor \ injective." }], "Text"], Cell["Now for the other functions. ", "Text"], Cell["g[x_] := Mod[ x^2, 8 ] + 1;", "InputOnly", AspectRatioFixed->True], Cell["PlotFunction[ g, 8, 1 ];", "Input", AspectRatioFixed->True], Cell["h[x_] := Mod[ x+3, 8 ] + 1;", "InputOnly", AspectRatioFixed->True], Cell["PlotFunction[ h, 8, 2 ];", "Input", AspectRatioFixed->True], Cell[TextData[{ "Thus, ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is almost injective: the only place where injectivity fails is ", Cell[BoxData[ \(TraditionalForm\`f(7)\ = \ \(8\ = \ f(8)\)\)]], ". Function ", Cell[BoxData[ \(TraditionalForm\`h\)]], " is wildly non-injective, and function ", Cell[BoxData[ \(TraditionalForm\`h\)]], " is injective, and therefore bijective. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Operations on Functions", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:17"], Cell["\<\ Since functions are in particular relations, all the operations we \ have for relations also apply to functions. However, one is mostly interested \ in operations that produce functions, rather than arbitrary relations when \ applied to functions. Here are the most important cases. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[CellGroupData[{ Cell[" Composition of Functions", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:18"], Cell[TextData[{ "Suppose we have functions ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\(A\ \[LongRightArrow]\ \ B\)\(\ \)\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`g\ : \(\(B\ \[LongRightArrow]\ C\)\(\ \)\)\)]], ". It is easy to see that for functions, the relational product ", Cell[BoxData[ \(TraditionalForm\`h\ = \ f\ \[SmallCircle]\ g\)]], " is a new function ", Cell[BoxData[ \(TraditionalForm\`h\ : \ \(\(A\ \[LongRightArrow]\ \ C\)\(\ \)\)\)]], " defined by ", Cell[BoxData[ \(TraditionalForm\`h(x)\ = \ g(f(x))\)]], ". To see this, recall the definition of relational product: \n\t", Cell[BoxData[ \(TraditionalForm\`\(\(x\)\(\ \)\((\ f\ \[SmallCircle]\ g)\)\(\ \)\(y\)\(\ \ \)\)\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`\[Exists] \ \(\(z\)\(\ \)\((\ \ x\ f\ z\ \[And] \ z\ g\ y\ )\)\(\ \)\)\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`\[Exists] \ \(\(z\)\(\ \)\((\ f(x) = \(z\ \[And] \ g(z)\ = \ y\))\)\(\ \)\)\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`y\ = \ g(f(x))\)]], ". \nNote that the order changes, ", Cell[BoxData[ \(TraditionalForm\`h\ = \ f\ \[SmallCircle]\ g\)]], " but ", Cell[BoxData[ \(TraditionalForm\`h(x)\ = \ g(f(x))\)]], ". This could be fixed by changing our notation for function application, \ but we try to keep things reasonable close to ", StyleBox["Mathematica", FontSlant->"Italic"], " syntax. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Warning", FontColor->RGBColor[1, 0, 0]], "\nThere are countless texts, including your book, that adhere to the \ ancient convention that ", Cell[BoxData[ \(TraditionalForm\`g\ \[SmallCircle]\ f\)]], " stands for the function ", Cell[BoxData[ \(TraditionalForm\`g(f(x))\)]], ". That's a real horror because it creates a completely uneccessary \ division between functions and relations.\nThis is an eternal sore spot, and \ some authors prefer to write function application on the right, as in ", Cell[BoxData[ \(TraditionalForm\`x\ f\)]], ". Then everything works out since ", Cell[BoxData[ \(TraditionalForm\`\((f\[SmallCircle]g)\) \((x)\)\ = \ x\ f\ g\)]], ". However, we will only use application on the left, since this is the \ convention used in ", StyleBox["Mathematica", FontSlant->"Italic"], " as well as C/C++. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "The next lemma is obvious from the definitions. \n\n", StyleBox["Lemma", FontWeight->"Bold"], ": Composition of functions is associative: for any three functions \ ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\(A\ \[LongRightArrow]\ \ B\)\(\ \)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`g\ : \(\(B\ \[LongRightArrow]\ C\)\(\ \)\)\)]], ", and ", Cell[BoxData[ \(TraditionalForm\`h\ : \ C\ \[LongRightArrow]\ D\)]], " we have \n\t\t", Cell[BoxData[ \(TraditionalForm\`f\ \[SmallCircle]\ \((g\ \[SmallCircle]\ h)\)\ = \ \((f\ \[SmallCircle]\ g)\)\ \[SmallCircle]\ h\)]], ".\nFurthermore, ", Cell[BoxData[ \(TraditionalForm\`f\ \[SmallCircle]\ Id\_B\ = \ f\)]], " and ", Cell[BoxData[ \(TraditionalForm\`Id\_A\ \[SmallCircle]\ f\ = \ f\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "\n", StyleBox["Lemma", FontWeight->"Bold"], ": Consider two functions ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\(A\ \[LongRightArrow]\ \ B\)\(\ \)\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`g\ : \(\(B\ \[LongRightArrow]\ A\)\(\ \)\)\)]], ". \n(1) ", Cell[BoxData[ \(TraditionalForm\`f\ \[SmallCircle]\ g\ = \ I\_A\)]], " implies that ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is injective, and ", Cell[BoxData[ \(TraditionalForm\`g\)]], " is surjective. \n(2) ", Cell[BoxData[ \(TraditionalForm\`g\ \[SmallCircle]\ f\ = \ I\_B\)]], " implies that ", Cell[BoxData[ \(TraditionalForm\`g\)]], " is injective, and ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is surjective. \n(3) ", Cell[BoxData[ \(TraditionalForm\`f\ \[SmallCircle]\ g\ = \ I\_A\)]], " and ", Cell[BoxData[ \(TraditionalForm\`g\ \[SmallCircle]\ f\ = \ I\_B\)]], " imply that both ", Cell[BoxData[ \(TraditionalForm\`g\)]], " and ", Cell[BoxData[ \(TraditionalForm\`f\)]], " are bijective. \n\nProof: \nIt clearly suffices to show (1). So assume \ ", Cell[BoxData[ \(TraditionalForm\`f(a)\ = \ f(b)\)]], ". Then \n\t", Cell[BoxData[ \(TraditionalForm\`a\ = \ \(\((f\[SmallCircle]g)\) \((a)\)\ = \ \(g( f(a))\ = \ \(g( f(b))\ = \ \(\((f\[SmallCircle]g)\) \((b)\)\ = \ b\)\)\)\)\)]], ".\nHence, ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is injective.\nFor surjectivity, suppose ", Cell[BoxData[ \(TraditionalForm\`a\)]], " is in ", Cell[BoxData[ \(TraditionalForm\`A\)]], " and let ", Cell[BoxData[ \(TraditionalForm\`b\ = \ f(a)\)]], ". Then ", Cell[BoxData[ \(TraditionalForm\`a\ = \ \(\((f\ \[SmallCircle]g)\) \((a)\)\ = \ \(g( f(a))\ = \ g(b)\)\)\)]], ". Hence ", Cell[BoxData[ \(TraditionalForm\`g\)]], " is surjective and we are done. \n\[EmptySquare]\n" }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Inverting Functions", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:19"], Cell[TextData[{ "For any injective function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ A\ \[LongRightArrow]\ B\)]], " the converse of ", Cell[BoxData[ \(TraditionalForm\`f\)]], " (as a relation) is a partial function from ", Cell[BoxData[ \(TraditionalForm\`B\)]], " to ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", called the ", StyleBox["inverse", FontColor->RGBColor[0, 0, 1]], " of ", Cell[BoxData[ \(TraditionalForm\`f\)]], ". It is often written ", Cell[BoxData[ \(TraditionalForm\`f\^\(-1\)\)]], " , rather than ", Cell[BoxData[ \(TraditionalForm\`f\^c\)]], ". If ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is in particular a bijection, then the inverse is a total function from \ ", Cell[BoxData[ \(TraditionalForm\`B\)]], " to ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". \n\nIt is important to realize that for any function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ A\ \[LongRightArrow]\ B\)]], " (and indeed for any relation from ", Cell[BoxData[ \(TraditionalForm\`A\)]], " to ", Cell[BoxData[ \(TraditionalForm\`B\)]], ") the converse ", Cell[BoxData[ \(TraditionalForm\`f\^c\)]], " is always a well-defined relation from ", Cell[BoxData[ \(TraditionalForm\`B\)]], " to ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". However, in general this relation fails to be a function, or even a \ partial function. To obtain a partial function, we need ", Cell[BoxData[ \(TraditionalForm\`f\)]], " to be injective, and to obtain a total function we need a bijection. \n\n\ ", StyleBox["Examples:", FontWeight->"Bold"], " \nThe inverse of the logarithm function is the exponential function. The \ proper domains and codomains here are ", Cell[BoxData[ \(TraditionalForm\`\(\[DoubleStruckCapitalR]\^+\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalR]\)]], ". \nThe inverse of the successor function on the integers is the \ predecessor function (subtract 1). \n\n", StyleBox["Lemma", FontWeight->"Bold"], ": Consider functions ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\(A\ \[LongRightArrow]\ \ B\)\(\ \)\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`g\ : \(\(B\ \[LongRightArrow]\ A\)\(\ \)\)\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`f\ \[SmallCircle]\ g\ = \ I\_A\)]], " and ", Cell[BoxData[ \(TraditionalForm\`g\ \[SmallCircle]\ f\ = \ I\_B\)]], ". Then both ", Cell[BoxData[ \(TraditionalForm\`f\)]], " and ", Cell[BoxData[ \(TraditionalForm\`g\)]], " are bijections, and ", Cell[BoxData[ \(TraditionalForm\`f\^\(-1\) = \ g\)]], ".\n\nNote that the Mathematica command ", StyleBox["Inverse", "SmallText", FontFamily->"Courier", FontSize->14], " is designed to compute the inverse of a matrix, it has no direct \ connection to the problem of inverting a function. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Unary and Binary Operations", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:20"], Cell[TextData[{ "For many applications one considers functions of the form \n\t ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\(A\ \ \[LongRightArrow]\ \ A\)\(\ \ \)\)\)]], " or ", Cell[BoxData[ \(TraditionalForm\`f\ : \ A\ \[Cross]\(\(A\ \[LongRightArrow]\ \ A\)\(\ \)\)\)]], ".\nThese are often referred to as ", StyleBox["unary", FontColor->RGBColor[0, 0, 1]], " and ", StyleBox["binary operations", FontColor->RGBColor[0, 0, 1]], " on ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", in particular when ", Cell[BoxData[ \(TraditionalForm\`A\)]], " carries some interesting structure. Binary operations are often written \ in infix notation, for example we might write ", Cell[BoxData[ \(TraditionalForm\`x\ + \ y\)]], " or ", Cell[BoxData[ \(TraditionalForm\`x\ \[CirclePlus]\ y\)]], " or ", Cell[BoxData[ \(TraditionalForm\`x\ \[CircleTimes]\ y\)]], " rather than ", Cell[BoxData[ \(TraditionalForm\`f(x, y)\)]], ". \nThere are countless examples of such operations in math and CS: unary \ minus, reciprocals, roots, reversal, addition, subtraction, multiplication, \ exponentiation, join of lists, concatenation of strings, matrix \ multiplication, union and intersection of sets, composition of relations, \ composition of functions. \nWe have already mentioned important properties of \ such binary operations. Here they are again.\n\n(1) ", StyleBox["Associativity\t", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`f(x, f(y, z))\ = \ f(f(x, y), z)\)]], ".\n(2) ", StyleBox["Commutativity\t", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`f(x, y)\ = \ f(y, x)\)]], ".\n\nThus, for an associative operation \[CirclePlus] we can simply write \ ", Cell[BoxData[ \(TraditionalForm\`x\_1\ \[CirclePlus]\ x\_2\[CirclePlus]\ \[Ellipsis]\ \[CirclePlus]\ x\_n\)]], " for any number of arguments: we can add parentheses in arbitrary \ places, and evaluate correspondingly, we will always get the same result. \ For example, we could evaluate ", Cell[BoxData[ \(TraditionalForm\`x\_1\ \[CirclePlus]\ x\_2\[CirclePlus]\ \[Ellipsis]\ \[CirclePlus]\ x\_n\)]], " as ", Cell[BoxData[ \(TraditionalForm\`\((\((\[Ellipsis]( x\_1\ \[CirclePlus]\ x\_2)\[CirclePlus]\ x\_3)\) \[Ellipsis]\ \[CirclePlus]\ x\_n)\)\)]], ".\n\n", StyleBox["Exercise", FontWeight->"Bold"], ": \nGo through the list of the binary operations above, and determine for \ each one whether it is associative and/or commutative. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Functions and Programs", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:21"], Cell[TextData[{ "How well does this definition fit together with the kind of function one \ knows from programming? Quite well, the only complication is that in programs \ the domain and codomain are often very complicated data types. But, since we \ allow any set whatsoever as domain/codomain the ones that are of interest in \ CS are certainly included. \nFor example, consider the operation of inserting \ an element in some position into a list. This is a function of the type \n\t\ ", Cell[BoxData[ \(TraditionalForm\`insert\ : \ Lists\ \[Cross]\ Elements\ \[Cross]\ Positions\ \[LongRightArrow]\ Lists\)]], ". \nIt is a partial function, since not all positions make sense for a \ given list (we could also return some default value in this case, say, the \ empty list, or we could append dummy elements to the lists so that the \ insertion makes sense, or \[Ellipsis] ). Whatever the details, we have a \ function in the mathematical sense of the word. \nNote that this function is \ neither surjective (though nearly so) nor injective. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "There is in fact another complication: in some programming languages such \ as C/C++ functions are allowed to change the value of input parameters \ (call-by-reference as opposed to call-by-value). For example, the typical pop \ operation on a stack returns a stack element, and modifies the input stack. \ We can still model this type of program function by a mathematical function \ of the form\n\t", Cell[BoxData[ \(TraditionalForm\`pop\ : \ Stacks\ \ \[LongRightArrow]\ Stacks\ \[Cross]\ Elements\)]], "\nbut in general we do not want to get involved in semantics issues." }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Iteration", "Section", CellTags->"c:22"], Cell[CellGroupData[{ Cell[" Powers of a Function: Iteration", "Subsection", CellTags->"c:23"], Cell[CellGroupData[{ Cell["The Definition", "Subsubsection", CellTags->"c:24"], Cell[TextData[{ "One of the most important applications of relational composition is the \ construction of powers ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\^\(\(\ \)\(k\)\)\)]], " of a relation, and the construction of the transitive closure based on \ these powers. Analogously we can define the powers of a function: apply the \ same function over and over.\nMore precisely, suppose we have a function \ ", Cell[BoxData[ \(TraditionalForm\`f\ : \ A\ \[LongRightArrow]\ \ A\)]], ". Since the domain and codomain are the same, we can compose ", Cell[BoxData[ \(TraditionalForm\`f\)]], " with itself to obtain a new function ", Cell[BoxData[ \(TraditionalForm\`f\^\(2\ : \ A\ \[LongRightArrow]\ A\)\)]], ", which can in turn be composed with ", Cell[BoxData[ \(TraditionalForm\`f\)]], " to yield ", Cell[BoxData[ \(TraditionalForm\`f\^3\)]], ", and so forth. This process is called ", StyleBox["iteration", FontColor->RGBColor[0, 0, 1]], ", and we will give a very detailed analysis of iteration shortly. For the \ time being, let us just define functions \n\n\t", Cell[BoxData[ \(TraditionalForm\`f\^\(\(0\)\(\ \)\) = \ Id\_A\)]], ",\n\t", Cell[BoxData[ \(TraditionalForm\`f\^\(n + 1\)\ = \ f\[SmallCircle]f\^\(\(n\)\(\ \)\)\)]], ".\n\t\nThus, ", Cell[BoxData[ \(TraditionalForm\`\(f\^n\)(a)\ = \ f(f(\[Ellipsis]\ \(f(a)\) \[Ellipsis]))\)]], " where ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is applied ", Cell[BoxData[ \(TraditionalForm\`n\)]], " times. Note that the we could have adopted this as our definition, but \ the two equations above are superior description: they essentially are a \ program to compute the iterates of a function.\nAlso observe that our \ definition says\n\t", Cell[BoxData[ \(TraditionalForm\`\(f\^\(\(\ \)\(n + 1\)\)\)(x)\ = \ \(f\^n\)( f(x))\)]], ". \nWe will see shorly that we also could have defined ", Cell[BoxData[ \(TraditionalForm\`f\^\(n + 1\)\ = \ f\^n\[SmallCircle]\ f\)]], ", yielding \n\t", Cell[BoxData[ \(TraditionalForm\`\(f\^\(\(\ \)\(n + 1\)\)\)(x)\ = \ f(\(f\^n\)(x))\)]], ", \n it makes no difference. \nThe ", StyleBox["orbit", FontColor->RGBColor[0, 0, 1]], " of a point ", Cell[BoxData[ \(TraditionalForm\`x\)]], " under ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is the sequence \n\t", Cell[BoxData[ \(TraditionalForm\`x, \ f(x), \ \(f\^2\)(x), \ \[Ellipsis], \(f\^n\)(x), \ \[Ellipsis]\)]], " \nWe will have more to say about the structure of orbits in particular \ when ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is a finite function in a while. This is very similar to taking the \ transitive reflexive closure, but the difference here is that we are \ interested in the order in which the elements of the orbit appear, not just \ the set of all such points. " }], "Text"], Cell["\<\ Let's consider again the sample functions from above, but this time \ iterated a few times. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(ClearAll[f, g, h]\), "\[IndentingNewLine]", \(\(f[x_] := Min[x + 1, 8];\)\), "\n", \(\(g[x_] := Mod[x\^2, 8] + 1;\)\), "\n", \(\(h[x_] := Mod[x, 8] + 1;\)\)}], "InputOnly", AspectRatioFixed->True], Cell["\<\ PlotFunction[ f, 8, LabelGrid\[Rule]Automatic ];\ \>", "Input", AspectRatioFixed->True], Cell[TextData[{ "By tracing orbits, the picture shows that for any ", Cell[BoxData[ \(TraditionalForm\`x\)]], ": ", Cell[BoxData[ \(TraditionalForm\`\(f\^7\)(x)\ = \ 8\)]], ". \nIf one is particularly interested in the orbit ", Cell[BoxData[ \(TraditionalForm\`x, \ f(x), \ \(f\^2\)(x), \ \[Ellipsis]\)]], " of a particular point ", Cell[BoxData[ \(TraditionalForm\`x\)]], ", we can single out that particular point to be traced." }], "Text"], Cell["\<\ PlotFunction[ f, 8, 8, \t\tLabelGrid\[Rule]Automatic, \t\tDoTrace\[Rule]{2} ];\ \>", "Input", AspectRatioFixed->True], Cell["\<\ Next, we trace the orbits of 2 and 4 (which merge after 6 steps), \ but we show all the other potential orbits in outline.\ \>", "Text"], Cell["\<\ PlotFunction[ f, 8, 8, \t\tLabelGrid\[Rule]Automatic, \t\tDoTrace\[Rule]{2,4}, \t\tFull\[Rule]True ];\ \>", "Input", AspectRatioFixed->True], Cell["\<\ Here are the functions g and h from above, iterated 8 times. \ \>", \ "Text"], Cell["PlotFunction[ g, 8 ];", "Input", AspectRatioFixed->True], Cell["PlotFunction[ h, 8 ];", "Input", AspectRatioFixed->True], Cell[TextData[{ "Note that the last picture really shows that ", Cell[BoxData[ \(TraditionalForm\`h\^8 = \ Id\_A\)]], ": just trace all the orbits, and after 8 steps you will be back to where \ you started. \nThe previous picture is a little harder to read: ", Cell[BoxData[ \(TraditionalForm\`\(g\^2\)(x)\ \[Element] \ {2, 5}\)]], ", and from then on 2 and 5 are interchanged at each application of ", Cell[BoxData[ \(TraditionalForm\`g\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["The Laws of Iteration", "Subsubsection", CellTags->"c:25"], Cell[TextData[{ StyleBox["What general conclusions can one draw from the definitions? For \ the following, suppose ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f\ : \ A\ \[LongRightArrow]\ A\)]], " is an arbitrary function, without any special properties whatsoever. \ First, we will prove that our definition is equivalent to the alternative \ version mentioned above." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Lemma 1", FontFamily->"Times", FontWeight->"Bold"], StyleBox[": For all ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\ \[GreaterEqual] \ 0\)]], ": ", Cell[BoxData[ \(TraditionalForm\`\(f\^n\)(f(x))\ = \ \(\(f\^\(n + 1\)\)(x)\ = \ f(\(f\^n\)(x))\)\)]], ".\nProof:\nThe first equation is just the definition of ", Cell[BoxData[ \(TraditionalForm\`f\^\(\(\ \)\(n + 1\)\)\)]], ". The second equation can be proved by induction on ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". \nBase case: ", Cell[BoxData[ \(TraditionalForm\`n = 0\)]], ". \n", Cell[BoxData[ \(TraditionalForm\`\(f\^\(0 + 1\)\)( x)\ = \ \(f(x)\ = \(f(Id(x))\ = \ \ f(\ \(f\^0\)(x))\)\)\)]], ". \nInduction step:\n", Cell[BoxData[ \(TraditionalForm\`\(f\^\(\((n + 1)\) + 1\)\)( x)\ = \ \(\(f\^\(n + 1\)\)( f(x))\ = \ \(\(f\)\((\)\(\(f\^n\)(f(x))\ = \ f(\(f\^\(n + 1\)\)(x))\)\)\)\)]], ". \n\[EmptySquare]" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["What happens if we compose iterates of a function? Or if we \ iterate iterates?\n", FontFamily->"Times"], StyleBox["Lemma 2:", FontFamily->"Times", FontWeight->"Bold"], StyleBox[" For all ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n, m\ \[GreaterEqual] \ 0\)]], ":\n\t ", Cell[BoxData[ \(TraditionalForm\`\(f\^n\)(\(f\^m\)(x))\ = \ \(\(f\^\(n + m\)\)( x)\ = \ \(f\^m\)(\(f\^n\)(x))\)\)]], ", and \n\t ", Cell[BoxData[ \(TraditionalForm\`\(\((f\^n)\)\^m\) \((x)\)\ = \ \(\(f\^\(n\ \[CenterDot]m\)\)(x)\ = \ \(\((f\^m)\)\^n\) \((x)\)\)\)]], ".\nProof: Exercise. \[EmptySquare]" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["You may have noticed, there is rather striking similarity between \ these laws of iteration, and the customary laws of exponentiation.\n\t(0) ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`a\^0\ = \ 1\)]], ",\n\t(1) ", Cell[BoxData[ \(TraditionalForm\`a\^n\[CenterDot]\ a\^m = \ a\^\(n + m\)\)]], ",\n\t(2) ", Cell[BoxData[ \(TraditionalForm\`\((a\^n)\)\^m = \ a\^\(n\ m\)\)]], ".", StyleBox["\nAs a matter of fact, exponentiation is just a special case of \ iteration. Can you see what the function ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f\)]], StyleBox[" is here? ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["A Performance Guarantee", "Subsubsection", CellTags->"c:26"], Cell[TextData[{ "Iteration is so important that there is a special ", StyleBox["Mathematica", FontSlant->"Italic"], " command to perform repeated application in a simple command:" }], "Text"], Cell[BoxData[{ \(\(Clear[f, a];\)\), "\n", \(Nest[\ f, \ a, \ 5\ ]\), "\n", \(NestList[f, a, \ 5]\)}], "Input"], Cell[TextData[{ "As usual, there is not much of an explanation given as to how this command \ works. If WRI were to attach a general warranty to its product, what kind of \ claims would it have to make for ", StyleBox["Nest", "SmallText"], "?\nJust the following, a literal translation of the defining equations we \ gave:\n\t\[Bullet] ", Cell[BoxData[ \(TraditionalForm\`Nest[\ f, \ x, \ 0\ ]\ = \ x\)]], " and \n\t\[Bullet] ", Cell[BoxData[ \(TraditionalForm\`Nest[\ f, \ x, \ n + 1\ ]\ = \ \ Nest[\ f, \ f(x), \ n\ ]\)]], ". \nOf course, these two equations amount to a recursive program that we \ could also use to implement the ", StyleBox["Nest", "SmallText"], " function by ourselves:" }], "Text"], Cell[BoxData[{ \(Clear[f, x, n]\), "\n", \(\(nest[f_, x_, 0]\ := \ x;\)\), "\n", \(\(nest[f_, x_, n_]\ := \ nest[f, f[x], n - 1];\)\)}], "Input"], Cell[BoxData[ \(nest[\ f, x, 5\ ]\)], "Input"], Cell["\<\ This is one of the primary reasons for exact, albeit fastidious \ definitions: they often translate directly into executable code. \ \>", "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Orbits: Cycles, Transients and Periods", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:27"], Cell[CellGroupData[{ Cell["The Basics", "Subsubsection", CellTags->"c:28"], Cell[TextData[{ StyleBox["As before, consider a function ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f\ : \ A\ \[LongRightArrow]\ A\)]], ". ", StyleBox["A ", FontFamily->"Times"], StyleBox["fixed point", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[" of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f\)]], StyleBox[" is a point ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(x\ \[Element] \ A\)\)\)]], StyleBox[" such that ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ x\)]], StyleBox[" (don't take the term point here too literal, any object can be \ a point). As we will see shortly, fixed points can be very useful in \ computational tasks. You may recall that we already used fixed points once \ before in the computation of the transitive closure of a relation.\nBut first \ a bit more terminology. There is a natural generalization of fixed points, \ namely cycles. A ", FontFamily->"Times"], StyleBox["cycle of ", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], Cell[BoxData[ \(TraditionalForm\`f\)]], StyleBox[" is a sequence ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(x\_0, \ x\_1, \[Ellipsis], x\_\(n - 1\)\)\)\)]], StyleBox[" of points such that ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(x\_i)\ = \ x\_\(i + 1\)\)]], StyleBox[", where the index is computed modulo ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[". ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[" is the ", FontFamily->"Times"], StyleBox["length", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[" of the cycle; it is also customary to speak of an ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox["-cycle", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[". The elements of a cycle are called ", FontFamily->"Times"], StyleBox["cyclic points", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[". So, a fixed point is simply a cyclic point that lies on a cycle \ of length 1. Numbering the element of a cycle from 0 to ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n - 1\)]], " is often more convenient than the usual numbering scheme, that is why we \ have used it right away in the definition. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["The ", FontFamily->"Times"], StyleBox["orbit", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[" of a point ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\_0 \[Element] \ A\)]], StyleBox[" under ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f\)]], StyleBox[" is the infinite sequence \n\n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(orb\_f\)(x\_0)\ = \ \ x\_0, \ f(x\_0), \ \(f\^2\)(x\_0), \ \[Ellipsis], \ \(f\^i\)( x\_0), \ \[Ellipsis]\)]], "\n\t", StyleBox["\nYou can think of the orbit as representing the evolution of a \ system where time is discrete: at time ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`t = 0\)]], " we are in some state ", Cell[BoxData[ \(TraditionalForm\`x\_0\)]], ". The general behavior of the system is described by the function ", Cell[BoxData[ \(TraditionalForm\`f\)]], ": if the system is in state ", Cell[BoxData[ \(TraditionalForm\`x\)]], " at time ", Cell[BoxData[ \(TraditionalForm\`t\)]], ", then it will be in state ", Cell[BoxData[ \(TraditionalForm\`f(x)\)]], " at time ", Cell[BoxData[ \(TraditionalForm\`t + 1\)]], ". Thus, the sequence of states the system runs through starting at ", Cell[BoxData[ \(TraditionalForm\`x\_0\)]], " is none other than the orbit of ", Cell[BoxData[ \(TraditionalForm\`x\_0\)]], " under ", Cell[BoxData[ \(TraditionalForm\`f\)]], ". For example, ", Cell[BoxData[ \(TraditionalForm\`x\)]], " could describe the position and velocity of a particle or several \ particles. In this case, ", Cell[BoxData[ \(TraditionalForm\`f\)]], " describes the motion of the particles. \nLet's take the simple case where \ there is only one particle, and there is a constant force acting on it (e.g., \ gravitation). " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(f[{s_, v_}] := {s + v, v - 1}\)], "Input"], Cell[BoxData[ \(orb = NestList[f, {0, 10}, 30]\)], "Input"], Cell[BoxData[ \(ListPlot[orb, PlotStyle \[Rule] {Blue, PointSize[0.03]}]; \)], "Input"], Cell["\<\ In the plot, the horizontal axis is position, and the vertical axis \ is velocity. The movement itself is just one-dimensional. \ \>", "Text"], Cell[TextData[{ StyleBox["Many of the basic concepts in the analysis of orbits come from \ physical examples such as the last one, but we will see that they also make \ sense in different contexts. \nFirst off, note that an orbit can contain at \ most one cycle. In fact, if ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\_t = \ \(f\^t\)(x\_\(\(0\)\(\ \)\))\)]], StyleBox[" is the first point on a cycle, then the rest of the orbit \ simply consists of repeated traversals of the cycle. So, in a sense, orbits \ that contain cycles are finite: after an initial segment, the so-called ", FontFamily->"Times"], StyleBox["transient part", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[", we hit a cycle, and then we stay on that cycle, the ", FontFamily->"Times"], StyleBox["periodic part", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[" of the orbit. Therefore, these orbits are called ", FontFamily->"Times"], StyleBox["ultimately periodic", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[". In particular, a ", FontFamily->"Times"], StyleBox["periodic", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[" orbit is one where the very first point is already on a cycle, \ so that the transient part is empty. \nThe length of the cycle in an \ ultimately periodic orbit is called the ", FontFamily->"Times"], StyleBox["period length", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[" (or simply period) of the orbit, and the length of the transient \ part the ", FontFamily->"Times"], StyleBox["transient length", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[". \n", FontFamily->"Times"], "Again, be aware that we are usually thinking of the orbit as a sequence, \ not as a set ", Cell[BoxData[ \(TraditionalForm\`{\ \(f\^i\)(x\_0)\ | \ i\ \[GreaterEqual] \ 0\ }\)]], ". It is easy to see that the underlying set of an orbit is finite iff the \ orbit is ultimately periodic. It is always clear from context what is meant. \ For example, when we say that two orbits are disjoint we mean that the \ underlying sets are disjoint. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Simple Examples", "Subsubsection", CellTags->"c:29"], Cell[TextData[{ StyleBox["Here is a simple example: the successor function on ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\((11)\)\ = \ {0, 1, \[Ellipsis], 10}\)]], " with the value computed modulo 10", StyleBox[". That is, ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f\ : \ \((11)\)\ \[LongRightArrow]\ \((11)\)\)]], " where ", StyleBox[" ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ x + 1\)]], " for ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ x\ < \ 10\)]], " but ", Cell[BoxData[ \(TraditionalForm\`f(10)\ = \ 0\)]], ". By the way, there is a fairly standard notation for ", Cell[BoxData[ \(TraditionalForm\`{1, 2, \[Ellipsis], n}\)]], ", namely ", Cell[BoxData[ \(TraditionalForm\`\([n]\)\)]], ", but there is not a similarly accepted notation for ", Cell[BoxData[ \(TraditionalForm\`{0, 1, \[Ellipsis], n - 1}\)]], ". We have taken the liberty to use ", Cell[BoxData[ \(TraditionalForm\`\((n)\)\)]], " for this purpose. Not great, but workable. If you have a better idea, let \ me know." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[f]\), "\n", \(\(f[x_] := Mod[x + 1, 11];\)\), "\n", \(NestList[f, 0, 40]\)}], "Input"], Cell[TextData[{ "We can see that the orbit of ", Cell[BoxData[ \(TraditionalForm\`x\_0 = \ 0\)]], " under ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is periodic with period 11. In fact, any starting point leads to this \ orbit. There are obvious modifications:" }], "Text"], Cell[BoxData[{ \(Clear[f]\), "\n", \(\(f[x_] := Mod[x + 5, 11];\)\), "\n", \(NestList[f, 0, 40]\)}], "Input"], Cell["\<\ The structure of the orbits is precisely the same as before. \ \>", \ "Text"], Cell[TextData[{ "Here is a more complicated function ", Cell[BoxData[ \(TraditionalForm\`g\ : \ \ \((11)\)\ \[LongRightArrow]\ \((11)\)\)]], ". The orbit of ", Cell[BoxData[ \(TraditionalForm\`x\_0 = \ 10\)]], " under ", Cell[BoxData[ \(TraditionalForm\`g\)]], " is ultimately periodic, with period 6, and transient length 5. The orbit \ of ", Cell[BoxData[ \(TraditionalForm\`x\_0 = \ 0\)]], " under ", Cell[BoxData[ \(TraditionalForm\`g\)]], " is periodic, with period 6. " }], "Text"], Cell[BoxData[{ \(Clear[g]\), "\n", \(g[x_] := If[x < 5, Mod[x - 1, 6], \ x - 1]\), "\n", \(NestList[g, 10, 40]\), "\n", \(NestList[g, 0, 40]\)}], "Input"], Cell["\<\ It is no longer clear what structure the orbits have, so we should \ take a look at all of them. \ \>", "Text"], Cell[BoxData[ \(TableForm[\ \(NestList[g, #, 10] &\)\ /@ \ Range[0, 10], \n\t TableSpacing \[Rule] {1, 1}]\)], "Input"], Cell[TextData[{ "The orbits are different, but they all lead to the same cycle in the end: \ ", Cell[BoxData[ \(TraditionalForm\`{5, 4, 3, 2, 1, 0, 5, \[Ellipsis]}\)]], " and really differ only in the transient part. " }], "Text"], Cell[TextData[{ "By contrast, the following function ", Cell[BoxData[ \(TraditionalForm\`h\ : \ \((11)\)\ \[LongRightArrow]\ \((11)\)\)]], " has one fixed point, and all orbits end in this fixed point." }], "Text"], Cell[BoxData[{ \(Clear[h]\), "\n", \(h[x_] := Min[x + 1, 10]\)}], "Input"], Cell[BoxData[ \(TableForm[\ \(NestList[h, #, 10] &\)\ /@ \ Range[0, 10], \n\t TableSpacing \[Rule] {1, 1}]\)], "Input"], Cell["\<\ Here are the pictures for these three functions. Make sure you \ understand how the pictures correspond to the raw data we just computed. \ \ \>", "Text"], Cell[BoxData[ \(PlotFunction[f, Range[0, 10], 11, LabelGrid \[Rule] Range[0, 10]]; \)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(PlotFunction[f, Range[0, 10], 11, \[IndentingNewLine]\t LabelGrid \[Rule] Range[0, 10], DoTrace \[Rule] {1}];\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(PlotFunction[g, Range[0, 10], 11, LabelGrid \[Rule] Range[0, 10]]; \)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(PlotFunction[g, Range[0, 10], 11, \[IndentingNewLine]\t LabelGrid \[Rule] Range[0, 10], DoTrace \[Rule] {1, 11}];\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(PlotFunction[h, Range[0, 10], 11, LabelGrid \[Rule] Range[0, 10]]; \)], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Rotating Lists", "Subsubsection", CellTags->"c:30"], Cell[TextData[{ "Functions on numbers are perhaps the most natural example for orbits, but \ our concepts make sense for other domains as well. Consider, for example, \n\ \n\t", Cell[BoxData[ \(TraditionalForm\`A\)]], " = all lists of natural numbers of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], ",\n\t", Cell[BoxData[ \(TraditionalForm\`f\)]], " = the operation rotate left. \n" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "As an example consider the orbit of the list ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\({1, 2, 3, ... , 6}\)\(\ \)\)\)]], " under ", StyleBox["RotateLeft", "SmallText"], "." }], "Text"], Cell[BoxData[{ \(\(orb\ = \ NestList[RotateLeft, Range[6], 15];\)\), "\n", \(TableForm[\ orb, \ TableSpacing \[Rule] {1, 1}]\)}], "Input"], Cell["In pictures:", "Text"], Cell[BoxData[ \(\(PlotMatrix[\ orb\ ];\)\)], "Input"], Cell["\<\ Clearly, the orbit is periodic with period 6. In fact, all orbits \ must be periodic with period at most 6, since rotating a list of length 6 \ times brings it back into its original state. Do all lists of length 6 have \ period 6? \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(TableForm[NestList[RotateLeft, Mod[Range[6], 2], 15]]\), "\n", \(TableForm[NestList[RotateLeft, Mod[Range[6], 3], 15]]\)}], "Input", AspectRatioFixed->True], Cell["\<\ No, we can have periods 2 and 3. And, of course, we can have fixed \ points.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(TableForm[NestList[RotateLeft, Table[1, {6}], 15]]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["How about period 4? Suppose \n ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(Nest[\ RotateLeft, \ L, \ 4\ ]\ = \ L\)\)\)]], "\n", StyleBox["for some list ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\)]], StyleBox[" of length 6. What does that mean for the list elements? Make a \ list with symbolic elements, rotate it, and compare entries. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[a]\), "\n", \(L = Array[a\_# &, {6}]\), "\n", \(LL = Nest[RotateLeft, L, 4]\), "\n", \(TableForm[Thread[{L, LL}]]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["So, ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`a\_1 = \ a\_5\)]], StyleBox[", ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`a\_5 = a\_3\)]], StyleBox[", ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`a\_\(\(3\)\(\ \)\) = \ a\_1\)]], StyleBox[", and therefore ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`a\_1 = \ \(a\_3 = a\_5\)\)]], StyleBox[". Likewise, ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`a\_2 = \ \(a\_4 = a\_6\)\)]], StyleBox[". But then the period is at most 2. A similar argument shows \ that period 5 is also impossible, so that 1, 2, 3 and 6 are the only \ possible periods. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[StyleBox["A few more calculations on lists of other lengths \ suggest the following conjecture. ", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Conjecture", FontFamily->"Times", FontWeight->"Bold"], StyleBox[": The possible periods of a list of length ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[" under the operation \[Rho]", FontFamily->"Times"], StyleBox[" (rotate left)", "SmallText", FontFamily->"Times"], StyleBox[" are the exactly the divisors of", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(n\)\)\)]], StyleBox[". ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[StyleBox["We will postpone the proof for a moment and first \ look at some other functions that will be helpful in the argument. ", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Addition Modulo m", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:31"], Cell[TextData[{ "Let ", Cell[BoxData[ \(TraditionalForm\`\((m)\)\ = \ {0, 1, ... , m - 1}\)]], " and define functions \n\n\t", Cell[BoxData[ \(TraditionalForm\`f\_\(m, s\)\)]], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\(:\)\(\ \)\(\((m)\)\ \[LongRightArrow]\ \ \((m)\)\)\)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\(f\_\(m, s\)\)( x)\ = \ \ \((x\ + \ s)\)\ \ mod\ m\)]], ". \n\nIn ", StyleBox["Mathematica", FontSlant->"Italic"], ", it is most convenient to define a functional with two parameters ", Cell[BoxData[ \(TraditionalForm\`m\)]], " and ", Cell[BoxData[ \(TraditionalForm\`s\)]], " that returns the function ", Cell[BoxData[ \(TraditionalForm\`f\_s\)]], " as output." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[f]\), "\n", \(\(F[m_, s_]\)[x_] := Mod[x + s, m]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "We may safely assume that ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ s\ < \ m\)]], ". \nHere is the orbit of 0 under ", Cell[BoxData[ \(TraditionalForm\`f\_\(11, 2\)\)]], " (or rather, the first 30 terms)." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(m = 12;\)\), "\n", \(\(s = 2;\)\), "\n", \(orb = NestList[F[m, s], 0, 40]\), "\n", \(\(ListPlot[orb, PlotStyle \[Rule] Blue, PlotJoined \[Rule] True];\)\)}], "Input", AspectRatioFixed->True], Cell["It appears that the orbit of 0 is periodic. ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotFunction[F[m, s], Range[0, m - 1], LabelGrid \[Rule] Range[0, m - 1]];\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(PlotFunction[F[m, s], Range[0, m - 1], m, DoTrace \[Rule] {1}];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["Try some other combinations of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`m\)]], StyleBox[" and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`s\)]], StyleBox[", and other starting values for the orbit. Experimentation will \ ultimately produce a conjecture along the lines of the following lemma. Note \ that the GCD of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`a\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\)]], " is the greatest number that divides ", Cell[BoxData[ \(TraditionalForm\`a\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\)]], ". ", StyleBox["\n\n", FontFamily->"Times"], StyleBox["Lemma", FontFamily->"Times", FontWeight->"Bold"], StyleBox[": The orbit of any point ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\ \[Element] \ \((m)\)\)]], StyleBox[" under ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(f\_\(m, s\)\)( x)\ = \ \ \((x\ + \ s)\)\ \ mod\ m\)]], StyleBox[" is periodic, and has period ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`m\/\(gcd(m, s)\)\)]], StyleBox[". \nProof.\n", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f\_\(m, s\)\)]], StyleBox[" is clearly injective, and therefore a permutation of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\((m)\)\)]], StyleBox[". Hence, all orbits must be periodic. The period of the orbit of \ ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\)]], StyleBox[" is the least ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`p\)]], StyleBox[" such that ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\ + \ p\[CenterDot]s\ \[Congruent] \ x\ \ \((mod\ m)\)\)]], StyleBox[", i.e., ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(p\[CenterDot]s\ = \ 0\ \ \((mod\ m)\)\)\)\)]], StyleBox[". Therefore, the period is ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`m\/\(gcd(m, s)\)\)]], StyleBox[". It follows that all orbits have the same size.\n\[EmptySquare]\ \n\nIt follows from the lemma that there are ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`gcd(m, s)\)]], StyleBox[" many disjoint orbits, and each orbit has the same size ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`m/\(gcd(m, s)\)\)]], StyleBox[". How can we pick an element in each orbit? For example, what is \ the least number in each orbit? We call this number the representative of the \ orbit, since we can generate all the other points in the orbit from it. \ Certainly, 0 is the representative of the orbit of 0. If there is only one \ orbit, we are done. So suppose there is at least one other orbit. What is the \ least number not in the orbit of 0? The answer is 1, but this is far from \ obvious. \n\n", FontFamily->"Times"], StyleBox["Claim", FontFamily->"Times", FontWeight->"Bold"], StyleBox[": The orbits of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f\_\(m, s\)\)]], StyleBox[" have representatives ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`0, 1, \[Ellipsis], gcd(m, s) - 1\)]], StyleBox[". \nProof.\nLet ", FontFamily->"Times"], StyleBox[" ", "Input", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ a\ < \ b\ < \ d\ = gcd(m, s)\)]], StyleBox[" and suppose that ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`b\)]], StyleBox[" lies in the orbit of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`a\)]], StyleBox[". Then ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`b\ \[Congruent] \ a\ + \ i\ \[CenterDot]s\ \((mod\ m)\)\)]], " for some integer ", Cell[BoxData[ \(TraditionalForm\`i\)]], StyleBox[", and therefore ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`i\ s\ \[Congruent] \ c\ \((mod\ m)\)\)]], StyleBox[" where ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`c\ = \ b - a\)]], StyleBox[", ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ c\ < \ d\)]], StyleBox[". But then ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`i\ s\ - \ j\ m\ = \ c\)]], " for some integer ", Cell[BoxData[ \(TraditionalForm\`j\)]], ", and therefore ", Cell[BoxData[ \(TraditionalForm\`d\)]], " divides ", Cell[BoxData[ \(TraditionalForm\`c\)]], ", a ", StyleBox["contradiction. \n\[EmptySquare]\nLet's check. First a case where \ ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`m\)]], " and ", Cell[BoxData[ \(TraditionalForm\`s\)]], " are coprime. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(m = 11;\)\), "\n", \(\(s = 2;\)\), "\n", \(\(len\ = \ m/GCD[m, s]\ - \ 1;\)\)}], "Input", AspectRatioFixed->True], Cell["Here is the orbit of 1, in this case the only orbit. ", "Text"], Cell[BoxData[ \(NestList[F[m, s], 1, len]\)], "Input", AspectRatioFixed->True], Cell["Some other examples, this time with multiple orbits.", "Text"], Cell[BoxData[{ \(m = 10; \), "\n", \(s = 6; \), "\n", \(\(len = m/GCD[m, s] - 1;\)\), "\n", \(\(allorb = \((NestList[F[m, s], #1, len] &)\) /@ Range[0, GCD[m, s] - 1];\)\), "\n", \(TableForm[allorb]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(m = 20; \), "\n", \(s = 15; \), "\n", \(\(len = m/GCD[m, s] - 1;\)\), "\n", \(\(allorb = \((NestList[F[m, s], #1, len] &)\) /@ Range[0, GCD[m, s] - 1];\)\), "\n", \(TableForm[allorb]\)}], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Rotating Lists contd.", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:32"], Cell[TextData[StyleBox["We can now give a simple proof of our conjecture \ about lists under rotation.", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Lemma", FontFamily->"Times", FontWeight->"Bold"], StyleBox[": The possible periods of a list of length ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[" under the operation ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\(g\)\(\ \)\(=\)\)\(\ \)\)\)]], StyleBox["rotate left ", "SmallText", FontFamily->"Times"], StyleBox[" are exactly the divisors of", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(n\)\)\)]], StyleBox[". ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ StyleBox["Proof. \nIt is easy to check that the list \n ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`{1, 2, \[Ellipsis], s, 1, 2, \[Ellipsis], s, \ \[Ellipsis]\ , 1, 2, \[Ellipsis], s\ }\)]], StyleBox["\nhas period ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`s\)]], StyleBox[" under ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f\)]], StyleBox[" whenever ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`s\)]], StyleBox[" divides ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[". So suppose the orbit of some list ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\)]], StyleBox[" has period ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`s\)]], StyleBox[". We may safely assume that ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`s\ < \ n\)]], StyleBox[", since ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`g\^\(\(\ \)\(t\)\) = \ g\^\(\(\ \)\(t\ mod\ n\)\)\)]], StyleBox[". So, we have ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(g\^s\)(L)\ = \ L\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\(\(\(g\)\(\ \)\)\^i\) \((L)\)\ \[NotEqual] \ L\)]], " for all ", Cell[BoxData[ \(TraditionalForm\`i\ < \ s\)]], ". In other words, \n\t", Cell[BoxData[ \(TraditionalForm\`L\_\(\(\ \)\(i\)\)\ = \ \ L\_\(\(\ \)\(i\ + \ \ s\)\)\)]], ", for all ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ i\ < n\)]], ". ", StyleBox["\nNote that we assume 0-indexing here, ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\ = \ {L\_0, L\_1, \ \[Ellipsis], \ L\_\(n - 1\)}\)]], StyleBox[". Also, we really should take all the indices modulo ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], StyleBox[". From the discussion of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f\_\(m, s\)\)]], StyleBox[" above, we know that we can partition the elements of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\)]], StyleBox[" into ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`d\ = gcd(n, s)\)]], StyleBox[" classes:\n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(L\_0\)\(\ \)\(=\)\(\ \)\(L\_s\ = \ \(L\_\(2 \ s\) = \ \[Ellipsis]\)\)\(\ \)\)\)]], StyleBox["\n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(L\_1\)\(\ \)\(=\)\(\ \)\(L\_\(s + 1\)\ = \ \(\(\ \(L\)\(\ \)\)\_\(2 s + 1\) = \ \[Ellipsis]\)\)\(\ \)\)\)]], StyleBox["\n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\[VerticalEllipsis]\)]], StyleBox["\n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(L\_\(d - 1\)\)\(\ \)\(=\)\(\ \)\(L\_\(s + d - 1\)\ = \ \(\(\(L\)\(\ \ \)\)\_\(2 s + d - 1\) = \ \[Ellipsis]\)\)\(\ \)\)\)]], StyleBox["\nBut this simply means that ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\)]], StyleBox[" is a repetition of the basic block ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\({L\_0, L\_1, \ \[Ellipsis], \ L\_\(\(\ \)\(d - 1\)\)}\)\)\)]], StyleBox[", and there are ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n/d\)]], StyleBox[" such blocks. But then the period of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\)]], " under the operation rotate left is ", Cell[BoxData[ \(TraditionalForm\`d\)]], ", and it follows that ", Cell[BoxData[ \(TraditionalForm\`d\ = \ \(gcd(n, s)\ = \ s\)\)]], ", so that ", Cell[BoxData[ \(TraditionalForm\`s\)]], " must divide ", Cell[BoxData[ \(TraditionalForm\`n\)]], ". ", StyleBox["\n\[EmptySquare]\nNote that the block ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\({L\_0, L\_1, \ \[Ellipsis], \ L\_\(\(\ \)\(d - 1\)\)}\)\)\)]], " ", StyleBox["must be a so-called ", FontFamily->"Times"], StyleBox["primitive", FontFamily->"Times", FontColor->RGBColor[0, 0, 1]], StyleBox[" list, i.e., a list that can not be written as a repetion of some \ copies of a shorter list, otherwise the period of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`L\)]], StyleBox[" would be less than ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`s\)]], StyleBox[". A very good problem is to count all primitive lists of a fixed \ length ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`n\)]], " ", StyleBox["with elements chosen from ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\([k]\)\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Multiplication Modulo m", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:33"], Cell[TextData[{ "Inspired by our addition modulo ", Cell[BoxData[ \(TraditionalForm\`m\)]], " example, it is natural to aks what happens to our orbits if we use \ multiplication instead. Define \n\n\t", Cell[BoxData[ \(TraditionalForm\`g\_\(m, s\)\)]], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\(:\)\(\ \)\(\((m)\)\ \[LongRightArrow]\ \ \((m)\)\)\)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\(g\_\(m, s\)\)(x)\ = x\ \[CenterDot]s\ \ mod\ m\)]], ". \n\nAgain we implement these functions in ", StyleBox["Mathematica", FontSlant->"Italic"], " as a functional with two parameters ", Cell[BoxData[ \(TraditionalForm\`m\)]], " and ", Cell[BoxData[ \(TraditionalForm\`s\)]], " that returns the function ", Cell[BoxData[ \(TraditionalForm\`g\_\(m, s\)\)]], " as output." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[G]\), "\n", \(\(G[m_, s_]\)[x_] := Mod[s\ x, m]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "This time, the orbit of 0 is trivially periodic, with period length 1. \ Also, ", Cell[BoxData[ \(TraditionalForm\`s\ = \ 0\)]], " is of no interest: all orbits end in the fixed point 0, and the transient \ length is at most 1. The general case, however, is surprisingly complicated.\n\ Let us consider only ", Cell[BoxData[ \(TraditionalForm\`0\ < \ s\ < \ m\)]], ", and starting points other than 0. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(m = 11;\)\), "\n", \(\(s = 2;\)\), "\n", \(orb = NestList[G[m, s], 1, 40]\), "\n", \(\(ListPlot[orb, PlotStyle \[Rule] Blue, PlotJoined \[Rule] True];\)\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "Looks periodic. \n\nThis is not surprising since ", Cell[BoxData[ \(TraditionalForm\`m\ = \ 11\)]], " is prime, so ", Cell[BoxData[ \(TraditionalForm\`s\ = \ 2\)]], " has a multiplictive inverse modulo ", Cell[BoxData[ \(TraditionalForm\`m\)]], ", and the function ", Cell[BoxData[ \(TraditionalForm\`g\_\(m, s\)\)]], " must be injective: ", Cell[BoxData[ \(TraditionalForm\`\(g\_\(m, s\)\)(x)\ = \ \(g\_\(m, s\)\)(y)\)]], " means ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(s\ x\ \[Congruent] \ s\ y\ \((mod\ m)\)\)\)\)]], ", and therefore ", Cell[BoxData[ \(TraditionalForm\`x\ \[Congruent] \ y\ \((mod\ m)\)\)]], " since we can multiply by ", Cell[BoxData[ \(TraditionalForm\`1\/s\)]], ".\nBut, because of 0, the permutation ", Cell[BoxData[ \(TraditionalForm\`g\_\(m, s\)\)]], " now has 2 cycles (one fixed point, and one cycle of length ", Cell[BoxData[ \(TraditionalForm\`m - 1\)]], "). " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(m = 11;\)\), "\n", \(\(s = 2;\)\), "\n", \(\(PlotFunction[G[m, s], Range[m] - 1, 5, LabelGrid \[Rule] Range[0, 10]];\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(\(m = 12;\)\), "\n", \(\(s = 8;\)\), "\n", \(\(PlotFunction[G[m, s], Range[m] - 1, 5, LabelGrid \[Rule] Range[0, m - 1]];\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(\(m = 11;\)\), "\n", \(\(s = 2;\)\), "\n", \(\(PlotFunction[G[m, s], Range[m] - 1];\)\)}], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(PlotFunction[G[m, s], Range[m] - 1, 20, LabelGrid \[Rule] Range[0, 10], DoTrace \[Rule] {11}];\)\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "You can now see the period fairly clearly. \nFor ", Cell[BoxData[ \(TraditionalForm\`m\)]], " non-prime, the picture changes, in particular when ", Cell[BoxData[ \(TraditionalForm\`gcd(m, s)\ > \ 1\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(m = 10;\)\), "\n", \(\(s = 4;\)\), "\n", \(\(PlotFunction[G[m, s], Range[m] - 1];\)\)}], "Input", AspectRatioFixed->True], Cell["\<\ This function is 2-to-1: every point has exactly two preimages. \ \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotFunction[G[m, s], Range[m] - 1, 1];\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[ \(\(PlotFunction[G[m, s], Range[m] - 1, \ 10, DoTrace \[Rule] {2}];\)\)], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(m = 10; s = 3\), "\n", \(TableForm[\(({#, AnalyzeOrbit[G[m, s], #]} &)\) /@ Range[0, 9], \n\t TableDepth \[Rule] 2]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["The situation is much more complicated that for the \ addition-based function ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f\_\(m, s\)\)]], StyleBox[" from the last section. We will only deal with the easy case \ where ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`m\)]], StyleBox[" and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`s\)]], StyleBox[" are coprime, that is, when ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`m\)]], " and ", Cell[BoxData[ \(TraditionalForm\`s\)]], " have no common prime factors. Even in that restricted case we need a new \ idea: the so-called multiplicitave order of a number. We will come back to \ this in our discussion of cryptography, for the moment just take for granted \ the following: if a number ", Cell[BoxData[ \(TraditionalForm\`s\)]], ", ", Cell[BoxData[ \(TraditionalForm\`1\ \[LessEqual] \ s\ < \ m\)]], ", is coprime with ", Cell[BoxData[ \(TraditionalForm\`m\)]], ", then we can find an exponent ", Cell[BoxData[ \(TraditionalForm\`e\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`s\^\(\(\ \)\(e\)\)\ \[Congruent] \ 1\ \((mod\ m)\)\)]], ". The least such exponent is called the multiplicative order of ", Cell[BoxData[ \(TraditionalForm\`s\)]], " modulo ", Cell[BoxData[ \(TraditionalForm\`m\)]], ".\nLet's just check for ", Cell[BoxData[ \(TraditionalForm\`m = 20\)]], ". Here, some numbers have order 2 and others have order 4 (of course, 1 \ always has order 1)." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(cop\ = \ Select[\ Range[20], \ GCD[m, #] == 1 &\ ]\)], "Input"], Cell[BoxData[{ \(Mod[\ cop^2, 20]\), "\n", \(Mod[\ cop^4, 20]\)}], "Input"], Cell["We can easily compute the order.", "Text"], Cell[BoxData[ \(\(order[s_, m_] := \[IndentingNewLine]Module[{e = 1, ss = s}, \[IndentingNewLine]\t While[Mod[ss, m] =!= 1, ss = s\ ss; \(e++\)]; \[IndentingNewLine]e\[IndentingNewLine]];\)\ \)], "Input"], Cell[BoxData[ \(Map[\ order[#, 20] &, \ cop\ ]\)], "Input"], Cell["\<\ Now we can check that the periods really are related to \ multiplicative orders.\ \>", "Text"], Cell[BoxData[{ \(m = 12; s = 5;\), "\[IndentingNewLine]", \(order[s, m]\), "\n", \(Table[{x, \(AnalyzeOrbit[G[m, s], x]\)\[LeftDoubleBracket]2\[RightDoubleBracket], order[s, m/\ GCD[m, x]]}, {x, m - 1}\ ]\ // \ \(Curry[TableForm]\)[ TableDepth \[Rule] 2]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["In fact, the following lemma holds.\n\n", FontFamily->"Times"], StyleBox["Lemma", FontFamily->"Times", FontWeight->"Bold"], StyleBox[": \nLet ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`m\)]], StyleBox[" and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`s\)]], StyleBox[" be two coprime numbers. \nThe orbit of any point ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\)]], ", ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ x\ < \ m\)]], ",", StyleBox[" under ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`g\_\(m, s\)\)]], StyleBox[" is periodic, and its period length is the multiplicative order \ of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`s\)]], StyleBox[" modulo ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`m\/\(gcd(m, s)\)\)]], StyleBox[". \n\nProof:\nConsider some point ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\)]], StyleBox[", ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`0\ < \ x\ < \ m\)]], StyleBox[", and let ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`p\)]], StyleBox[" be minimal such that ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\ s\^p\ \[Congruent] \ x\ \((mod\ m)\)\)]], StyleBox[", or, equivalently, \n\t\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\ \((s\^p\ - \ 1)\)\ \[Congruent] \ 0\ \((mod\ m)\)\)]], StyleBox[". \nLet ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`d\ = \ gcd(m, s)\)]], StyleBox[", and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\ = \ x\^\[Prime]\ d\)]], StyleBox[", ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`m\ = \ m\^\[Prime]\ d\)]], StyleBox[", so that ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\^\[Prime]\)]], StyleBox[" and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`m\^\[Prime]\)]], StyleBox[" are coprime. Then\n\t\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\^\[Prime]\ \((s\^p\ - \ 1)\)\ \[Congruent] \ 0\ \((mod\ m\^\[Prime])\)\)]], StyleBox[". \nBut since ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\^\[Prime]\)]], StyleBox[" has an inverse modulo ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`m\^\[Prime]\)]], StyleBox[", that implies ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`s\^p\ \[Congruent] \ 1\ \((mod\ m\^\[Prime])\)\)]], StyleBox[", so that ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`p\)]], StyleBox[" is the multiplicative order of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`s\)]], StyleBox[" w.r.t. ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`m\^\[Prime]\)]], StyleBox[".\n\nConversely, since ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`m\)]], StyleBox[" and ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`s\)]], StyleBox[" are coprime, there always is such a ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`p\)]], StyleBox[", and so all orbits must be periodic with period ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`order(s, gcd(m, x))\)]], StyleBox[". \n\[EmptySquare]", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Computing Transients and Periods", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:34"], Cell[TextData[{ StyleBox["The question arises how one can actually determine the transient \ length and the period of a given point ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\_0\)]], StyleBox[" under some function ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f\)]], StyleBox[". The obvious approach is to begin to enumerate the orbit \n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\(orb\_f\)(x\_0)\ = \ \ x\_0\)\(,\)\(\ \)\(f( x\_0)\)\(,\)\(\ \)\(\(f\^2\)( x\_0)\)\(,\)\(\ \)\(\[Ellipsis]\)\(,\)\(\ \)\(\(f\^t\)( x\_0)\)\(,\)\(\ \)\(\[Ellipsis]\)\(\ \)\)\)]], StyleBox[". \nIf a point ever appears twice in this sequence, it must be \ cyclic and we are essentially done. If the orbit of ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\_0\)]], StyleBox[" is in fact ultimately periodic, then this method will always \ work, at least in principle. In general, however, there is no hope to \ identify non-periodic orbits: after a finite computation, we only know a few \ initial values of the orbit, and if we have not found any cyclic points yet, \ that really means nothing. Perhaps the transient part is very long. Or, \ perhaps, the orbit is in fact non-periodic; we simply cannot tell. \nSo, here \ is a more modest goal: suppose we know that the orbit is ultimately periodic; \ compute the transient length and the period. \nThe following function \ determines the transient part and the periodic part. In order to make this \ function a little more safe to use we truncate the computation if after 500 \ steps no cyclic point has appeared. The bound is handed over as the third \ parameter, with default value 500. \nNote that all the parameters are \ untyped, so we can use this command for all kinds of universes and \ operations. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[analyzeOrbit] analyzeOrbit[ff_,x0_,bnd_:500]:= Module[{orb,t,x,p}, \t\tx = ff[x0]; \t\tt = 0; \t\torb = {x0}; \t\tWhile[\[InvisibleSpace]!(MemberQ[orb,x])&&t", "InputOnly", AspectRatioFixed->True], Cell["Here are some simple tests. ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(Clear[F, G]\), "\n", \(\(F[m_, s_]\)[x_] := Mod[x + s, m]\), "\n", \(\(G[m_, s_]\)[x_] := Mod[x\ s, m]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(analyzeOrbit[F[11, 2], 5]\), "\n", \(analyzeOrbit[G[20, 2], 1]\)}], "Input", AspectRatioFixed->True], Cell["And this tests the emergency break.", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(analyzeOrbit[# + 1 &, 0]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Actually, automata has a function ", StyleBox["AnalyzeOrbit", "Input"], " that returns the length of the transient and periodic parts, and the \ entry point of the cycle. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(AnalyzeOrbit[F[11, 2], 5]\), "\n", \(AnalyzeOrbit[G[20, 2], 1]\)}], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(multsub[n_]\ := \ Select[\ Range[n - 1], GCD[#, n] \[Equal] 1 &\ ]\), "\n", \(\(n\ = \ 20;\)\), "\n", \(x\ = \ 2; \), "\n", \(ZS\ = \ multsub[n]\), "\n", \(\(Last@AnalyzeOrbit[G[n, #], x] &\)\ /@ \ ZS\), "\n", \(\(MultiplicativeOrder[#, 20] &\)\ /@ \ ZS\)}], "Input"], Cell[TextData[{ "So, the output format differs slightly. However, the important difference \ between ", StyleBox["analyzeOrbit", "Input"], " and ", StyleBox["AnalyzeOrbit", "Input"], " is this: the latter uses ", Cell[BoxData[ \(TraditionalForm\`O(1)\)]], " memory for the computation, and is thus much more suitable if the \ transients or periods are very long. Note that it is not particularly clear \ how one can computet transients and periods if one is not allowed to use more \ than a constant amount of memory (meaning that one cannot simply store a part \ of the orbit). " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Iteration in Calculus", "Subsection", CellTags->"c:35"], Cell["\<\ For our purposes, iteration is mostly of interest when the \ functions in question are defined on a finite set, or perhaps on infinite but \ discrete set as the natural numbers, the integers, lists of integers and so \ forth. However, one should point out that iteration also plays a fundamental \ role in classical mathematics and in particular in analysis. \ \>", "Text"], Cell["\<\ In fact, approximation methods such as Newton's are usually the \ first place where one encounters the notions of iteration, orbits and fixed \ points. However, because of the eternal problems with numerical accuracy, it \ is actually easier to see what is going on when on deals with discrete \ objects. At any rate, here is the classical example. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[CellGroupData[{ Cell[TextData[{ "Computing ", Cell[BoxData[ \(TraditionalForm\`\@2\)]] }], "Subsubsection", CellTags->"c:36"], Cell[TextData[{ StyleBox["A standard problem in calculus is to compute the roots of an \ equation\n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ 0\)]], ",", StyleBox["\nand in particular a polynomial equation such as\n\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\^2\ - \ 2\ = \ 0\)]], ".", StyleBox["\nBy computing the root we mean to find a numerical value that is \ at least approximately correct", FontFamily->"Times"], StyleBox[". ", FontFamily->"Courier", FontWeight->"Bold"], StyleBox["Of course, in Mathematica we can solve this equation directly, \ symbolically or numerically. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(ClearAll[x]\), "\[IndentingNewLine]", \(Solve[x\^2 - 2 == 0, x]\), "\n", \(NSolve[x\^2 - 2 == 0, x]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "But how can we get a numerical value without using all this complicated \ machinery hidden behind ", StyleBox["Solve", "SmallText"], " or ", StyleBox["NSolve", "SmallText"], "?" }], "Text"], Cell[TextData[{ StyleBox["Here is a clever method due to Newton. ", FontFamily->"Times"], "The fundamental idea is very simple: replace the problem of finding a root \ of \n\t", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ 0\)]], " \nby the problem of finding a fixed point of some associated function ", Cell[BoxData[ \(TraditionalForm\`g\)]], ":\n\t", Cell[BoxData[ \(TraditionalForm\`g(x)\ = \ x\)]], ".\nTo get the fixed point, start with some initial guess ", Cell[BoxData[ \(TraditionalForm\`x\_0\)]], ", and keep applying ", Cell[BoxData[ \(TraditionalForm\`g\)]], " until the fixed point is reached, or at least sufficiently close." }], "Text"], Cell[TextData[{ StyleBox["To compute ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\@2\)]], ", first pick some ", StyleBox["approximation ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\_0\)]], StyleBox[" to ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\@2\)]], ", say ", Cell[BoxData[ \(TraditionalForm\`x\_0 = \ 1.0\)]], StyleBox[". Let ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`g(x)\ = \ x\/2 + 1\/x\)]], ". ", StyleBox["Then ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\_1 = \ g(x\_0)\)]], StyleBox[" is a better approximation:", FontFamily->"Times"] }], "Text"], Cell[BoxData[{ \(\(Clear[g];\)\), "\n", \(\(g[x_] := x\/2 + 1\/x;\)\), "\n", \(\(x0 = 1.0;\)\), "\n", \(x1 = g[x0]\)}], "Input"], Cell[TextData[{ StyleBox["Of course, 1.5 is still not a particularly good approximation to \ ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\@2\)]], StyleBox[". We repeat the procedure to get closer:", FontFamily->"Times"] }], "Text"], Cell[BoxData[ \(x2 = g[x1]\)], "Input"], Cell[BoxData[ \(x3 = g[x2]\)], "Input"], Cell[BoxData[ \(x4 = g[x3]\)], "Input"], Cell["Perfect, given 6 digit precision. ", "Text"], Cell[BoxData[ \(N[\@2]\)], "Input"], Cell[TextData[{ "There is no need to keep all the intermediate values around, we can use ", StyleBox["Nest", "SmallText"], " instead. " }], "Text"], Cell[BoxData[ \(Nest[g, x0, 5]\)], "Input"], Cell[BoxData[ \(NestList[g, x0, 5]\)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["A Warning", "Subsubsection", CellTags->"c:37"], Cell[TextData[StyleBox["There is a little glitch in this, unfortunately. \ Since we are dealing with floating point numbers, things that appear to be \ equal need not be:", FontFamily->"Times"]], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(orb\ = \ NestList[g, 1.0, 5]\), "\n", \(orb\[LeftDoubleBracket]\(-1\)\[RightDoubleBracket]\), "\n", \(orb\[LeftDoubleBracket]\(-2\)\[RightDoubleBracket]\), "\n", \(% == %%\)}], "Input", AspectRatioFixed->True], Cell["\<\ The problem is that Mathematica displays only 6 digits, but \ internally it keeps a few more.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(N[orb[\([\(-2\)]\)], $MachinePrecision]\), "\n", \(N[orb[\([\(-1\)]\)], $MachinePrecision]\)}], "Input", AspectRatioFixed->True], Cell["\<\ As one can see, the hidden digits don't all agree. However, the \ last value is a fixed point. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(\(x5 = orb\[LeftDoubleBracket]\(-1\)\[RightDoubleBracket];\)\), "\n", \(x5 == g[x5]\)}], "Input", AspectRatioFixed->True], Cell["\<\ Thus, convergence is quite fast: only 5 steps for 16 correct \ digits. \ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(TableForm[N[NestList[g, 1.0, 6], 16]]\)], "Input", AspectRatioFixed->True], Cell[TextData[{ "Mathematica provides a command ", StyleBox["FixedPoint", "SmallText"], " that will iterate automatically until a fixed point is reached. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(FixedPoint[g, 1.0]\), "\n", \(N[%, 16]\)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "You have to be a little careful with ", StyleBox["FixedPoint", "SmallText"], ", though. If there is no fixed point, your computation will continue \ indefinitely, and may crash your session. You can add a third parameter that \ limits the maximum number of iteration steps. Once you are convinced that \ there really is a fixed point, just delete the third parameter. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(FixedPoint[g, 1.0, 100]\)], "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Reciprocals", "Subsubsection", CellTags->"c:38"], Cell[TextData[{ StyleBox["Here is another example, which is extremely important for high \ precision calculations: reciprocals via Newton iteration. We are given a \ positive number ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`a > 0\)]], StyleBox[" with many digits, and we have to calculate its inverse ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`1\/a\)]], StyleBox[". The equation is here ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(1\/x - \ a\ = \ 0\)\)\)]], StyleBox[", and the appropriate function to iterate is ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`g(x) = \ x\ \ + \ x\ \((1\ - \ a\ \[CenterDot]x)\)\)]], StyleBox[". Below, we calculate with 30 digits accuracy. Note that the \ convergence is quite good. ", FontFamily->"Times"] }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(g[x_] := N[x + x\ \((1 - a\ x)\), 30];\)\)], "Input", AspectRatioFixed->True], Cell["\<\ We invert an approximation to \[DoubledPi]. \ \>", "Text"], Cell[BoxData[ \(a = N[\[Pi], 40]\)], "Input", AspectRatioFixed->True], Cell[BoxData[{ \(\(val = NestList[g\ , N[1\/3, 40], 5];\)\), "\n", \(TableForm[val]\), "\n", \(N[1\/a, 30]\)}], "Input", AspectRatioFixed->True], Cell["\<\ By the way, 40 digits of \[DoubledPi] suffice to calculate the \ circumference of an object the size of the Milky Way to withing one proton \ diameter - sufficient for most practical applications. \ \>", "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[" Newton's Method (optional)", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:39"], Cell[CellGroupData[{ Cell[" A General Approach to Root Finding", "Subsubsection", CellTags->"c:40"], Cell[TextData[{ StyleBox["The question is: how does one find the iteration function ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`g\)]], " given an equation ", Cell[BoxData[ \(TraditionalForm\`f(x) = \ 0\)]], ". ", StyleBox["In Newton's method one chooses\n\t\t", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`g(x)\ = \ x\ - \ \(f(x)\)\/\(\(f\^\[Prime]\)(x)\)\)]], ".", StyleBox["\nClearly a root ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`x\_0\)]], " of ", Cell[BoxData[ \(TraditionalForm\`f\)]], " translates into a fixed point of ", Cell[BoxData[ \(TraditionalForm\`g\)]], ", and conversely. So, the iteration process is given by " }], "Text"], Cell[TextData[{ "\n\twhile( error too large )\n\t\t", Cell[BoxData[ \(TraditionalForm\`x\ = \ g(x)\)]], ";\n\t" }], "InlineInput"], Cell[TextData[{ StyleBox["In the square root of 2 example case, ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ x\^2 - \ 2\)]], ", so ", Cell[BoxData[ \(TraditionalForm\`\(f\^\[Prime]\)(x)\ = \ 2 x\)]], " ", StyleBox["and we get \n ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(g( x)\)\(\ \)\(=\)\(\ \ \)\(x\ - \ \(x\^2 - \ 2\)\/\(2 x\)\ = \ \ x\ \/2\ + 1\/x\)\(\ \ \)\)\)]], "." }], "Text"], Cell[TextData[{ "The motivation for this method is purely geometric: consider the point ", Cell[BoxData[ \(TraditionalForm\`\((x, f(x))\)\)]], " on the curve ", Cell[BoxData[ \(TraditionalForm\`f\)]], ", and draw a tangent through that point. Then the intersection of the \ tangent and the ", Cell[BoxData[ \(TraditionalForm\`x\)]], "-axis is a better approximation for the root of ", Cell[BoxData[ \(TraditionalForm\`f\)]], ". " }], "Text"], Cell[TextData[{ "Of course, this simple approach does not always work. For example, if we \ start at some ", Cell[BoxData[ \(TraditionalForm\`x\_0\)]], "such that ", Cell[BoxData[ \(TraditionalForm\`\(f\^\[Prime]\)(x\_0)\)]], " is 0, or even just small, our iteration will not converge. But under the \ right circumstances (", Cell[BoxData[ \(TraditionalForm\`f\)]], " sufficiently smooth, initial guess sufficiently close to a single root, \ derivative well-behaved) the convergence of Newton's method is quadratic: the \ error after ", Cell[BoxData[ \(TraditionalForm\`t + 1\)]], " steps is at most ", Cell[BoxData[ \(TraditionalForm\`\[Epsilon]\^2\)]], ", where \[Epsilon] is the error after ", Cell[BoxData[ \(TraditionalForm\`t\)]], " steps. That means that the number of correct digits more or less doubles \ at each step. There are better methods where the number of correct digits \ increases, for example, by a factor of 10 at each step. " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" Pretty Pictures", "Subsubsection", CellTags->"c:41"], Cell["\<\ It is best to look at some pictures. First, a simple parabola. \ \ \>", "Text"], Cell[BoxData[{\(Clear[f];\), "\n", \(f[x_] := x\^2 - 2;\), "\n", \(x0 = 2;\), "\n", \(y0 = f[x0];\), "\n", RowBox[{ RowBox[{"x1", "=", RowBox[{"First", "[", RowBox[{"x", "/.", RowBox[{"Solve", "[", RowBox[{ RowBox[{ RowBox[{ RowBox[{ RowBox[{ SuperscriptBox["f", "\[Prime]", MultilineFunction->None], "[", "x0", "]"}], " ", \((x - x0)\)}], "+", "y0"}], "==", "0"}], ",", "x"}], "]"}]}], "]"}]}], ";"}]}], "Input"], Cell[BoxData[ RowBox[{ RowBox[{"Plot", "[", RowBox[{ RowBox[{"{", RowBox[{\(f[x]\), ",", RowBox[{ RowBox[{ RowBox[{ SuperscriptBox["f", "\[Prime]", MultilineFunction->None], "[", "x0", "]"}], " ", \((x - x0)\)}], "+", "y0"}]}], "}"}], ",", \({x, \(-1\), 3}\), ",", \(PlotStyle \[Rule] {Blue, Red}\), ",", \(AspectRatio \[Rule] 1\)}], "]"}], ";"}]], "Input"], Cell[BoxData[{ RowBox[{ RowBox[{"gr1", "=", RowBox[{"Plot", "[", RowBox[{ RowBox[{"{", RowBox[{\(f[x]\), ",", RowBox[{ RowBox[{ RowBox[{ SuperscriptBox["f", "\[Prime]", MultilineFunction->None], "[", "x0", "]"}], " ", \((x - x0)\)}], "+", "y0"}]}], "}"}], ",", \({x, .5, 2.1}\), ",", \(PlotStyle \[Rule] {Blue, Red}\), ",", \(AspectRatio \[Rule] 1\), ",", \(DisplayFunction \[Rule] Identity\)}], "]"}]}], ";"}], "\n", \(gr2 = Graphics[{PointSize[0.02], Point[{x0, 0}], Point[{x0, y0}], Point[{x1, 0}]}];\), "\n", \(Show[{gr1, gr2}, DisplayFunction \[Rule] $DisplayFunction];\)}], "Input"], Cell["\<\ After a few steps, the tangents become indistinguishable from the \ curve. Here is a little helper function that performs the approximation \ process, which is explained in the next section.\ \>", "Text"], Cell[BoxData[{ \(ClearAll[approx]\), "\n", \(\(approx[ff_, x0_, n_] := \((next = Function[x, Evaluate[N[x - ff[x]\/\[PartialD]\_x ff[x]]]]; NestList[next, x0, n])\);\)\)}], "Input"], Cell[BoxData[{ \(\(gr1 = Plot[f[x], {x, .5, 2.1}, PlotStyle \[Rule] {Blue}, AspectRatio \[Rule] 1, DisplayFunction \[Rule] Identity];\)\), "\n", \(\(xval = approx[f, 2, 5];\)\), "\n", \(\(tab = Flatten[\(({{#1, 0}, {#1, f[#1]}} &)\) /@ xval, 1];\)\), "\n", \(\(gr2 = Graphics[Join[{Red}, {Line[tab]}]];\)\), "\n", \(\(Show[{gr1, gr2}, DisplayFunction \[Rule] $DisplayFunction];\)\)}], "Input"], Cell[TextData[{ StyleBox[" \nThe same pictures for the cosine \ function. Note how the iteration jumps around for a while before settling \ down on the root ", FontFamily->"Times"], Cell[BoxData[ \(TraditionalForm\`\(\(-3\)\/2\) \[Pi]\ \[TildeTilde] \ \(-4.71\)\)]], ". ", StyleBox[" The initial guess is ", FontFamily->"Times"], StyleBox[" ", FontFamily->"Times", FontWeight->"Bold"], Cell[BoxData[ \(TraditionalForm\`x\_0 = \ 3\)]], StyleBox[".", FontFamily->"Times"] }], "Text"], Cell[BoxData[{\(Clear[f];\), "\n", \(f[x_] := Cos[x];\), "\n", \(x0 = 3;\), "\n", \(y0 = f[x0];\), "\n", RowBox[{ RowBox[{"x1", "=", RowBox[{"First", "[", RowBox[{"x", "/.", RowBox[{"Solve", "[", RowBox[{ RowBox[{ RowBox[{ RowBox[{ RowBox[{ SuperscriptBox["f", "\[Prime]", MultilineFunction->None], "[", "x0", "]"}], " ", \((x - x0)\)}], "+", "y0"}], "==", "0"}], ",", "x"}], "]"}]}], "]"}]}], ";"}]}], "Input"], Cell[BoxData[ RowBox[{ RowBox[{"Plot", "[", RowBox[{ RowBox[{"{", RowBox[{\(f[x]\), ",", RowBox[{ RowBox[{ RowBox[{ SuperscriptBox["f", "\[Prime]", MultilineFunction->None], "[", "x0", "]"}], " ", \((x - x0)\)}], "+", "y0"}]}], "}"}], ",", \({x, \(-6\), 4}\), ",", \(PlotStyle \[Rule] {Blue, Red}\), ",", \(AspectRatio \[Rule] 1\)}], "]"}], ";"}]], "Input"], Cell[BoxData[{ \(\(gr1 = Plot[f[x], {x, \(-6\), 4}, PlotStyle \[Rule] {Blue}, AspectRatio \[Rule] 1, DisplayFunction \[Rule] Identity];\)\), "\n", \(xval = approx[f, 3.0, 5]\), "\n", \(\(tab = Flatten[\(({{#1, 0}, {#1, f[#1]}} &)\) /@ xval, 1];\)\), "\n", \(\(gr2 = Graphics[Join[{Red}, {Line[tab]}]];\)\), "\n", \(\(Show[{gr1, gr2}, DisplayFunction \[Rule] $DisplayFunction];\)\)}], "Input"] }, Closed]], Cell[CellGroupData[{ Cell[" Automatic Newton", "Subsubsection", CellTags->"c:42"], Cell["\<\ Since Mathematica knows how to differentiate, we can even automate \ this process. \ \>", "Text"], Cell[BoxData[{ \(Clear[f, next]\), "\n", \(\(f[x_] := x\^2 - 2;\)\)}], "Input"], Cell[BoxData[ \(next = Function[x, Evaluate[x - f[x]\/\[PartialD]\_x f[x]]]\)], "Input"], Cell[BoxData[ \(NestList[next, 1, 5]\)], "Input"], Cell["No good, we need approximate reals, not rationals.", "Text"], Cell[BoxData[ \(next = N[Function[x, Evaluate[x - f[x]\/\[PartialD]\_x f[x]]]]\)], "Input"], Cell[BoxData[ \(NestList[next, 1, 5]\)], "Input"], Cell[TextData[{ "We can even write a little program that performs these calculations. It is \ not terribly useful in this simple form, but you get the idea. Note the use \ of ", StyleBox["Evalutate", "SmallText"], " in the definition of function ", StyleBox["next", "SmallText"], ", without it the derivative would be computed anew during each call to ", StyleBox["next", "SmallText"], ", a terrible waste of time. " }], "Text"], Cell[BoxData[{ \(ClearAll[approx]\), "\n", \(\(approx[ff_, x0_, n_] := \((\ next = Function[x, Evaluate[N[x - ff[x]\/\[PartialD]\_x ff[x]]]]; \n\t\t\tNestList[ next, x0, n])\);\)\)}], "Input"], Cell[BoxData[{ \(approx[f, 2, 5]\), "\n", \(N[\@2]\)}], "Input"], Cell[BoxData[{ \(approx[Cos, .5, 5]\), "\n", \(N[\[Pi]\/2]\)}], "Input"], Cell["\<\ Needless to say, this method does not always work (just think about cases \ where the derivative is very small, or even 0). \ \>", "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell["Permutations", "Section", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:43"], Cell[CellGroupData[{ Cell[" Counting Permutations", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:44"], Cell[TextData[{ "A permutation according to our definitions is a bijection from some set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " to itself. Suppose ", Cell[BoxData[ \(TraditionalForm\`A\ = \ {a, b, c, d}\)]], ". Any function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ A\ \[LongRightArrow]\ A\)]], " can be given by a table such as \n\n\t", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"f", ":", " ", GridBox[{ {"a", "b", "c", "d"}, {"a", "a", "d", "c"} }]}], " "}], TraditionalForm]]], "\n \nmeaning that ", Cell[BoxData[ \(TraditionalForm\`f(a)\ = \ \(f(b)\ = \ a\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(c)\ = \ d\)]], ", and ", Cell[BoxData[ \(TraditionalForm\`f(d) = \ c\)]], ". Actually, if we agree to keep the order ", Cell[BoxData[ \(TraditionalForm\`a, \ b, \ c, \ d\)]], " in ", Cell[BoxData[ \(TraditionalForm\`A\)]], " fixed, we can simply represent ", Cell[BoxData[ \(TraditionalForm\`f\)]], " by the list of values:\n\n ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(f : \ \ \ \ \ {\ a, \ a, \ d, \ c\ }\)\)\)]], "\n\nThe last function ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is not a bijection, since both ", Cell[BoxData[ \(TraditionalForm\`a\)]], " and ", Cell[BoxData[ \(TraditionalForm\`b\)]], " are mapped to ", Cell[BoxData[ \(TraditionalForm\`a\)]], ". But \n\n ", Cell[BoxData[ \(TraditionalForm\`g : \ \ \ {\ b, \ a, \ d, \ c\ }\)]], " \n \nis a bijection. As one can see, one can also think of a \ bijection from ", Cell[BoxData[ \(TraditionalForm\`A\)]], " to ", Cell[BoxData[ \(TraditionalForm\`A\)]], " as a rearrangement of ", Cell[BoxData[ \(TraditionalForm\`A\)]], ". Every rearrangement corresponds to exactly one bijection, and vice \ versa. The term \"permutation\" is often used in this sense. \nHere are \ all permutations of ", Cell[BoxData[ \(TraditionalForm\`A\)]], ": " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ Clear[a,b,c,d] Permutations[{a,b,c,d}] % // Length\ \>", "Input", AspectRatioFixed->True], Cell[TextData[{ StyleBox["\nLemma", FontWeight->"Bold"], ": There are ", Cell[BoxData[ \(TraditionalForm\`\(n\[VeryThinSpace]!\)\)]], " permutations of a set of ", Cell[BoxData[ \(TraditionalForm\`n\)]], " elements. \n\nProof: \nConsider an arbitrary permutation ", Cell[BoxData[ \(TraditionalForm\`f\)]], " on ", Cell[BoxData[ \(TraditionalForm\`A\ = \ {a\_1, ... , a\_n}\)]], ". There are ", Cell[BoxData[ \(TraditionalForm\`n\)]], " choices for ", Cell[BoxData[ \(TraditionalForm\`f(a\_1)\)]], ", but only ", Cell[BoxData[ \(TraditionalForm\`n - 1\)]], " choices for ", Cell[BoxData[ \(TraditionalForm\`f(a\_2)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`\(\(n\)\(-\)\(2\)\(\ \)\)\)]], "for ", Cell[BoxData[ \(TraditionalForm\`f(a\_3)\)]], ", and so on ( ", Cell[BoxData[ \(TraditionalForm\`\(\(f(a\_n)\)\(\ \)\)\)]], "is completely determined by the other values). Hence, there are ", Cell[BoxData[ \(TraditionalForm\`n\[CenterDot]\((n - 1)\)\ \[CenterDot]\ \[Ellipsis]\ \[CenterDot]1\ = \ \(n\ \ !\)\)]], " many ways to construct a permutation of ", Cell[BoxData[ \(TraditionalForm\`A\)]], ".\n\[EmptySquare]\n\nThus, the number of permutations of, say, ", Cell[BoxData[ \(TraditionalForm\`\([n]\)\)]], " gets out of hand very quickly. Any algorithm that relies on testing all \ possible permutations of some data is bound to fail for rather small inputs. \ " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["Factorial[ Range[20] ]", "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" The Inner Life of Permutations", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:45"], Cell[TextData[{ "Since a permutation ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is a function from some set ", Cell[BoxData[ \(TraditionalForm\`A\)]], " to itself, it can be iterated. What can we say about the orbit of a point \ in ", Cell[BoxData[ \(TraditionalForm\`A\)]], " under ", Cell[BoxData[ \(TraditionalForm\`f\)]], "? Now if ", Cell[BoxData[ \(TraditionalForm\`A\)]], " is finite, any orbit\n\t", Cell[BoxData[ \(TraditionalForm\`\(orb\_f\)( x)\ = \ \((\ \(f\^i\)(x)\ | \ i\ \[GreaterEqual] \ 0\ )\)\)]], "\nmust be eventually periodic, say, ", Cell[BoxData[ \(TraditionalForm\`\(f\^n\)(a)\ = \ \(f\^m\)(a)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ m\ < \ n\)]], ". Since ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is injective, every point ", Cell[BoxData[ \(TraditionalForm\`a\ \[Element] A\)]], " must have a unique predecessor under ", Cell[BoxData[ \(TraditionalForm\`f\)]], ", namely ", Cell[BoxData[ \(TraditionalForm\`\(f\^\(-1\)\)(a)\)]], ". But then the orbit must be periodic: ", Cell[BoxData[ \(TraditionalForm\`m\ = \ 0\)]], " and there is no transient part (see the lemma below for a more detailed \ argument). \nSo, the orbit of any point is simply a cycle. Now consider the \ relation\n\t", Cell[BoxData[ \(TraditionalForm\`\(\[Rho](x, y)\)\ \ \ iff\ \ \(\[Exists] \ n\ \[GreaterEqual] \ 0\ \((\ \ \(f\^n\)(x)\ = \ y\ )\)\)\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "In other words, ", Cell[BoxData[ \(TraditionalForm\`y\)]], " is related to ", Cell[BoxData[ \(TraditionalForm\`x\)]], " iff ", Cell[BoxData[ \(TraditionalForm\`y\)]], " lies in the orbit of ", Cell[BoxData[ \(TraditionalForm\`x\)]], " under ", Cell[BoxData[ \(TraditionalForm\`f\)]], ". Did you really think you were done with relations? " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "\n", StyleBox["Lemma", FontWeight->"Bold"], ": \[Rho] is an equivalence relation. \nProof: \nReflexivity is obvious: \ ", Cell[BoxData[ \(TraditionalForm\`\(f\^0\)(x)\ = \ \(Id(x)\ = \ x\)\)]], ". \nTransitivity is also straightforward: suppose ", Cell[BoxData[ \(TraditionalForm\`\(f\^n\)(x)\ = \ y\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\(f\^m\)(y)\ = \ z\)]], ". Then ", Cell[BoxData[ \(TraditionalForm\`\(f\^\(n + m\)\)(x)\ = \ y\)]], ", so ", Cell[BoxData[ \(TraditionalForm\`z\)]], " is in the orbit of ", Cell[BoxData[ \(TraditionalForm\`x\)]], ", and we are done. \nBut how about symmetry? If ", Cell[BoxData[ \(TraditionalForm\`\(f\^n\)(x)\ = \ y\)]], ", how do we know there is an ", Cell[BoxData[ \(TraditionalForm\`m\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`\(f\^m\)(y)\ = \ x\)]], " ? Since the carrier set of ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is finite, there must be some ", Cell[BoxData[ \(TraditionalForm\`s\ \[GreaterEqual] \ 0\)]], " such that there is a positive ", Cell[BoxData[ \(TraditionalForm\`t\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`\(f\^\(\(\ \)\(s\)\)\)( x)\ = \ \(f\^\(\(\ \)\(s + t\)\)\)(x)\)]], ". Let ", Cell[BoxData[ \(TraditionalForm\`s\_0\)]], " be minimal such, and let ", Cell[BoxData[ \(TraditionalForm\`t\_0\)]], " be minimal such that ", Cell[BoxData[ \(TraditionalForm\`\(f\^s\_0\)(x)\ = \ \(f\^\(s\_0 + t\_0\)\)(x)\)]], ".\nClaim: ", Cell[BoxData[ \(TraditionalForm\`s\_0 = \ 0\)]], ". \nFor suppose ", Cell[BoxData[ \(TraditionalForm\`s\_0\ > \ 0\)]], ", and let ", Cell[BoxData[ \(TraditionalForm\`a\ = \ \(f\^\(\(\ \)\(s\_0 - 1\)\)\)(x)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(b\ = \ \(f\^\(\(\ \)\(s\_0 + t\_0 - 1\)\)\)(x)\)\)\)]], ". Then we have ", Cell[BoxData[ \(TraditionalForm\`f( a)\ = \ \(\(f\^\(\(\ \)\(s\_0\)\)\)( x) = \ \(\(f\^\(\(\ \)\(s\_0 + t\_0\)\)\)(x)\ = \ f(b)\)\)\)]], ". Since ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is injective it follows that ", Cell[BoxData[ \(TraditionalForm\`a\ = \ b\)]], ", contradicting the minimality of ", Cell[BoxData[ \(TraditionalForm\`s\_0\)]], ".\nSo, ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(x = \ \(f\^\(\(\ \)\(t\_0\)\)\)( x)\)\)\)]], ". But then ", Cell[BoxData[ \(TraditionalForm\`\(f\^\(\(\ \)\(n\)\)\)( x)\ = \ \(f\^\(\(\ \)\(n\ mod\ t\_0\)\)\)(x)\)]], " for all ", Cell[BoxData[ \(TraditionalForm\`n\ \[GreaterEqual] \ 0\)]], ", so we may safely assume that ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ n\ < \ t\_0. \)]], " But then ", Cell[BoxData[ \(TraditionalForm\`m\ = \ t\_0\ - \ n\)]], " is as required: \n\t", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\(f\^\(\(\ \)\(t\_0 - n\)\)\)( y) = \ \(\(f\^\(\(\ \)\(t\_0 - n\)\)\)(\(f\^\(\(\ \)\(n\)\)\)( x)) = \ \(\(f\^\(\(\ \)\(t\_0\)\)\)(x)\ = x\)\)\)\)\)]], ".\n\[EmptySquare]\n\nNote that the last proof is somewhat unusual: in \ general it is easy to show that a given relation is reflexive and symmetric, \ and transitivity is the hard part. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "\nHence we can partition all of ", Cell[BoxData[ \(TraditionalForm\`A\)]], " into a number of disjoint cycles of ", Cell[BoxData[ \(TraditionalForm\`f\)]], ". Not surprisingly, this is called the ", StyleBox["cycle decomposition", FontColor->RGBColor[0, 0, 1]], " of ", Cell[BoxData[ \(TraditionalForm\`f\)]], ". On the other hand, given a list of disjoint cycles in ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", whose union is all of ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", we can construct a permutation that has precisely these cycles as \ orbits. \n\nHere is an example. The macro ", StyleBox["AssignFunction", FontFamily->"Courier", FontSize->14], " turns the first argument into a function as described by the following \ lists (domain and values). " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["AssignFunction[ f, Range[6], {2,3,4,1,6,5} ] ", "Input", AspectRatioFixed->True], Cell["\<\ f[2] Map[ f, Range[6] ]\ \>", "Input"], Cell["PlotFunction[ f, 6, 6, LabelGrid->Automatic ];", "Input", AspectRatioFixed->True], Cell[TextData[{ "In the package ", StyleBox["DiscreteMath`Permutations`", "SmallText"], " algorithms are defined that can extract the cycles from a given a \ permutation, or turn given cycles back into a permutation. There is a clash \ with some already defined functions, ignore the error message." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["<True], Cell["ToCycles[ {2,3,4,1,6,5} ]", "Input", AspectRatioFixed->True], Cell["% // FromCycles", "Input", AspectRatioFixed->True], Cell[TextData[{ "It is a good exercise to implement the ", StyleBox["ToCycles", "SmallText"], " and ", StyleBox["FromCycles", "SmallText"], " functions by hand (without first looking at the code in the package).\nAn \ example of a random permutation (another good question: how does one \ construct a random permutation?). " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ ran = RandomPermutation[10] ToCycles[ran] FromCycles[%]\ \>", "Input", AspectRatioFixed->True], Cell["\<\ AssignFunction[ f, Range[10], ran ] PlotFunction[ f, 10, 10 ];\ \>", "Input", AspectRatioFixed->True], Cell["Headache-inducing. Here is a trace of just a single orbit.", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["PlotFunction[ f, 10, 10, DoTrace->{1} ];", "Input", AspectRatioFixed->True], Cell["\<\ To prettify the whole picture we have to reaarange the universe \ [10] so that points on a cycle are consecutive.\ \>", "Text", Evaluatable->False, AspectRatioFixed->True], Cell["A = Flatten@ToCycles[ran]", "Input"], Cell["PlotFunction[ f, A, 10 ];", "Input", AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell[" The Inverse of a Permutation ", "Subsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:46"], Cell[TextData[{ "Consider some permutation ", Cell[BoxData[ \(TraditionalForm\`p\ : \ A\ \[LongLeftRightArrow]A\)]], ". Since ", Cell[BoxData[ \(TraditionalForm\`p\)]], " is bijective, there must be an inverse permutation ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(q\ = \ p\^\(-1\)\)\)\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`q(p(x))\ = \ \(p(q(x))\ = x\)\)]], " for all ", Cell[BoxData[ \(TraditionalForm\`x\ \[Element] A\)]], ". How does one actually compute ", Cell[BoxData[ \(TraditionalForm\`q\)]], "? \nFirst note that it actually suffices to get just one of the \ identities.\n\n", StyleBox["Lemma", FontWeight->"Bold"], ": Let ", Cell[BoxData[ \(TraditionalForm\`p, q\ : \ A\ \[LongLeftRightArrow]\ A\)]], " be two permutations. Then ", Cell[BoxData[ \(TraditionalForm\`p\ \[SmallCircle]\ q\ = \ Id\)]], " implies ", Cell[BoxData[ \(TraditionalForm\`q\ = \ p\^\(-1\)\)]], ". \nProof.\nWe need to show that ", Cell[BoxData[ \(TraditionalForm\`q\ \[SmallCircle]\ p\ = \ Id\)]], ". Let ", Cell[BoxData[ \(TraditionalForm\`x\ = \ p(z)\)]], " arbitrary (since ", Cell[BoxData[ \(TraditionalForm\`p\)]], " is surjective, we can always find the apropriate ", Cell[BoxData[ \(TraditionalForm\`z\)]], ", regardless of ", Cell[BoxData[ \(TraditionalForm\`x\)]], "). Then \n\t", Cell[BoxData[ \(TraditionalForm\`\((q\ \[SmallCircle] p)\) \((x)\)\ = \ \(\((p\ \[SmallCircle]\ q\ \[SmallCircle]\ p)\) \((z)\)\ = \ \(\((Id\ \[SmallCircle]\ p)\) \((z)\)\ = \ \(p(z)\ = \ x\)\)\)\)]], ", \nand we are done. \n\[EmptySquare]\n" }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[CellGroupData[{ Cell["Computing Tables", "Subsubsection", CellTags->"c:47"], Cell[TextData[{ "For the sake of simplicity, consider a permutation ", Cell[BoxData[ \(TraditionalForm\`p\ : \ \([n]\)\ \[LongLeftRightArrow]\([n]\)\)]], ". We only have to assing the value ", Cell[BoxData[ \(TraditionalForm\`i\)]], " to ", Cell[BoxData[ \(TraditionalForm\`q(p(i))\)]], " for all ", Cell[BoxData[ \(TraditionalForm\`i\ \[Element] \ \([n]\)\)]], ". Thus, a simple loop does the job: " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ \tDo[ q[ p[i] ] = i, {i,n} ]; \t\ \>", "InlineInput", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "That's all. By brute force we then have ", Cell[BoxData[ \(TraditionalForm\`p\ \[SmallCircle]\ q\ = \ Id\)]], ", and by the lemma ", Cell[BoxData[ \(TraditionalForm\`q\ = \ p\^\(-1\)\)]], ". Here is an example. We start with a random permutation (as a list), \ convert it into a real function using the macro ", StyleBox["AssignFunction", "SmallText"], ", and the run the loop to get the inverse function. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["perm = RandomPermutation[10]", "Input"], Cell["AssignFunction[ p, Range[10], perm ]", "Input"], Cell["??p", "Input"], Cell["Do[ q[ p[i] ] = i, {i,10} ];", "Input"], Cell[TextData[{ "Let's verify that ", Cell[BoxData[ \(TraditionalForm\`q\)]], " works as advertised. " }], "Text"], Cell["Map[ q[p[#]]&, Range[10] ]", "Input"], Cell[TextData[{ "An almost identical loop deals with case when the permutation is given as \ list rather than a function. So suppose ", Cell[BoxData[ \(TraditionalForm\`p\)]], " is a list, some rearragement of ", Cell[BoxData[ \(TraditionalForm\`\([n]\)\)]], ". How can we get the list that corresponds to the inverse of ", Cell[BoxData[ \(TraditionalForm\`p\)]], "? All we need to do is to replace function calls ", StyleBox["p[i]", "SmallText"], " by ", StyleBox["Part", FontFamily->"Courier"], " operations ", StyleBox["p\[LeftDoubleBracket]i\[RightDoubleBracket]", "SmallText"], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ \tDo[ q[[ p[[i]] ]] = i,{i,n} ]; \t\t\ \>", "InlineInput", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "Actually, for this to work in ", StyleBox["Mathematica", FontSlant->"Italic"], ", ", Cell[BoxData[ \(TraditionalForm\`q\)]], " has to be a list of the right length, even before the loop is executed, \ otherwise Mathematica complains bitterly. The list can have arbitrary \ elements. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ p = {2,3,1,5,4}; q = {0,0,0,0,0}; Do[ q[[ p[[i]] ]] = i, {i,5} ] q\ \>", "Input", AspectRatioFixed->True], Cell["p[[q]] == Range[5] == q[[p]]", "Input", AspectRatioFixed->True], Cell[TextData[{ "Works. \nHere is a picture of the composition of ", Cell[BoxData[ \(TraditionalForm\`p\)]], " and ", Cell[BoxData[ \(TraditionalForm\`q\)]], " (using the macro ", StyleBox["PlotRelation", "SmallText"], ")." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(\(PlotRelation[{Pairs[Range[5], p], Pairs[Range[5], q]}, \n\t\t\t5, \ LabelGrid -> Automatic\ ];\)\)], "Input"], Cell[TextData[{ "Note that the inverse is but a mirror image of the permutation itself: \ everything that is moved by ", Cell[BoxData[ \(TraditionalForm\`p\)]], " is put back into its original position by ", Cell[BoxData[ \(TraditionalForm\`q\)]], ". " }], "Text", Evaluatable->False, AspectRatioFixed->True] }, Closed]], Cell[CellGroupData[{ Cell["Inverse via Sorting", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:48"], Cell[TextData[{ "Here is a much more interesting way of computing the inverse of a \ permutation, given as a list: we sort the list, after attaching the number \ ", Cell[BoxData[ \(TraditionalForm\`i\)]], " to ", Cell[BoxData[ \(TraditionalForm\`p\[LeftDoubleBracket]i\[RightDoubleBracket]\)]], ", and then we delete the first component of each pair. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["\<\ p = RandomPermutation[10] pp = Pairs[ p, Range[10] ] Sort[pp] q = Map[ Last, % ]\ \>", "Input", AspectRatioFixed->True], Cell[TextData[{ "Check that ", Cell[BoxData[ \(TraditionalForm\`q\)]], " is indeed the inverse of ", Cell[BoxData[ \(TraditionalForm\`p\)]], ": " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["p[[q]] == q[[p]] == Range[10]", "Input", AspectRatioFixed->True], Cell["Can you see what is going on here? ", "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(PlotRelation[{Pairs[Range[10], p], Pairs[Range[10], q]}, 10, LabelGrid \[Rule] Automatic]; \)], "Input"] }, Closed]], Cell[CellGroupData[{ Cell["Inverse via Cycle Decomposition", "Subsubsection", Evaluatable->False, AspectRatioFixed->True, CellTags->"c:49"], Cell[TextData[{ "Back to the bijection ", Cell[BoxData[ \(TraditionalForm\`h\ : \ \([8]\)\ \[LongRightArrow]\ \([8]\)\)]], " from the previous examples. We already know that ", Cell[BoxData[ \(TraditionalForm\`h\^8 = \ Id\)]], "." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(h[x_] := Mod[x, 8] + 1; \), "\n", \(PlotFunction[h, 8, 8, DoTrace \[Rule] {1}, Full \[Rule] True]; \)}], "Input", AspectRatioFixed->True], Cell[TextData[{ "By our lemma, that really means that ", Cell[BoxData[ \(TraditionalForm\`h\^7\)]], " is the inverse of ", Cell[BoxData[ \(TraditionalForm\`h\)]], ": ", Cell[BoxData[ \(TraditionalForm\`h\ \[SmallCircle]\ h\^7 = \ \(h\^7\[SmallCircle]\ h\ = \ \(h\^8\ = \ Id\)\)\)]], ". \n\nOf course, it is not true in general that one can simply iterate a \ function to obtain its inverse, just think about the function ", Cell[BoxData[ \(TraditionalForm\`f\ : \ \(\(\[DoubleStruckCapitalR]\ \ \[LongRightArrow]\ \ \[DoubleStruckCapitalR]\)\(\ \)\)\)]], ", ", Cell[BoxData[ \(TraditionalForm\`f(x)\ = \ x\^3\)]], ", on the real numbers. ", Cell[BoxData[ \(TraditionalForm\`f\)]], " is indeed bijective: " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[ \(Plot[x\^3, {x, \(-2\), 2}, PlotRange \[Rule] All, PlotStyle \[Rule] Blue]; \)], "Input", AspectRatioFixed->True], Cell[TextData[{ "But ", Cell[BoxData[ \(TraditionalForm\`\(f\^k\)(x)\ = \ x\^\(3\^k\)\)]], ", and there clearly is no positive ", Cell[BoxData[ \(TraditionalForm\`k\)]], " for which ", Cell[BoxData[ \(TraditionalForm\`f\^k\)]], " is the inverse of ", Cell[BoxData[ \(TraditionalForm\`f\)]], ". Incidentally, in this case ", Cell[BoxData[ \(TraditionalForm\`k\ = \ \(-1\)\)]], " works (with appropriate conventions for the 3rd root of a negative real), \ but unless one has a closed form for ", Cell[BoxData[ \(TraditionalForm\`f\^k\)]], " life is not so easy. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[TextData[{ "\nThe surprising fact is: if ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(f\)\)\)]], " is a permutation of a finite set ", Cell[BoxData[ \(TraditionalForm\`A\)]], ", then there always is some positive ", Cell[BoxData[ \(TraditionalForm\`k\)]], " such ", Cell[BoxData[ \(TraditionalForm\`f\^k = \ f\^\(-1\)\)]], ". To see this consider the cycle decomposition of some permutation. " }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell[BoxData[{ \(p = {3, 6, 4, 8, 9, 7, 2, 10, 5, 1}\), "\n", \(cyc = ToCycles[p]\)}], "Input", AspectRatioFixed->True], Cell["\<\ If we plot the permutation as usual, the cycles structure is not \ particularly visible. \ \>", "Text"], Cell["\<\ AssignFunction[fp,Range[10],p] PlotFunction[ fp, Range[10] ];\ \>", "Input"], Cell["\<\ But if we reorder the univers according to the cycle decomposition, \ the picture becomes very clear. This method of reordering the universe to get \ better pictures should sound very familiar by now. \ \>", "Text"], Cell["PlotFunction[ fp, Flatten[cyc] ];", "Input"], Cell[TextData[{ "In this case, there is one cycle of length 5, 3, and 2 each. Hence, ", Cell[BoxData[ \(TraditionalForm\`p\^30\)]], " is the identity permutation: the element on the first cycle just move \ around the full cycle 6 times, the elements from the second cycle 10 times, \ and from the last cycle 15 times. \nBut then ", Cell[BoxData[ \(TraditionalForm\`p\^29\)]], " must be the inverse of ", Cell[BoxData[ \(TraditionalForm\`p\)]], "! Stare at the next line of code for a while, it's a real beauty." }], "Text", Evaluatable->False, AspectRatioFixed->True], Cell["q = Nest[ #[[p]]&, Range[10], 29 ]", "Input", AspectRatioFixed->True], Cell["q[[p]] == Range[10] == p[[q]]", "Input", AspectRatioFixed->True] }, Closed]] }, Closed]] }, Closed]] }, Closed]] }, FrontEndVersion->"5.0 for X", ScreenRectangle->{{0, 1280}, {0, 1024}}, AutoGeneratedPackage->None, WindowToolbars->{}, CellGrouping->Automatic, WindowSize->{996, 914}, WindowMargins->{{4, Automatic}, {Automatic, 0}}, PrintingStartingPageNumber->211, PrivateNotebookOptions->{"ColorPalette"->{RGBColor, 128}}, ShowCellLabel->True, ShowCellTags->False, RenderingOptions->{"ObjectDithering"->True, "RasterDithering"->False}, CharacterEncoding->Automatic, Magnification->1.5, StyleDefinitions -> "Classic.nb" ] (******************************************************************* Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. *******************************************************************) (*CellTagsOutline CellTagsIndex->{ "c:1"->{ Cell[1828, 55, 93, 3, 110, "Title", Evaluatable->False, CellTags->"c:1"]}, "c:2"->{ Cell[1946, 62, 95, 3, 88, "Section", Evaluatable->False, CellTags->"c:2"]}, "c:3"->{ Cell[2066, 69, 100, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:3"]}, "c:4"->{ Cell[2191, 76, 52, 1, 42, "Subsubsection", CellTags->"c:4"]}, "c:5"->{ Cell[3378, 117, 55, 1, 42, "Subsubsection", CellTags->"c:5"]}, "c:6"->{ Cell[4458, 155, 74, 1, 42, "Subsubsection", CellTags->"c:6"]}, "c:7"->{ Cell[6747, 220, 101, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:7"]}, "c:8"->{ Cell[6873, 227, 59, 1, 42, "Subsubsection", CellTags->"c:8"]}, "c:9"->{ Cell[13424, 445, 61, 1, 42, "Subsubsection", CellTags->"c:9"]}, "c:10"->{ Cell[16334, 527, 60, 1, 42, "Subsubsection", CellTags->"c:10"]}, "c:11"->{ Cell[17791, 568, 114, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:11"]}, "c:12"->{ Cell[18104, 582, 107, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:12"]}, "c:13"->{ Cell[20609, 664, 106, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:13"]}, "c:14"->{ Cell[22661, 735, 123, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:14"]}, "c:15"->{ Cell[24770, 797, 115, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:15"]}, "c:16"->{ Cell[29192, 935, 104, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:16"]}, "c:17"->{ Cell[31441, 1021, 114, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:17"]}, "c:18"->{ Cell[31938, 1037, 118, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:18"]}, "c:19"->{ Cell[37744, 1221, 113, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:19"]}, "c:20"->{ Cell[41015, 1333, 118, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:20"]}, "c:21"->{ Cell[43918, 1415, 113, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:21"]}, "c:22"->{ Cell[45853, 1459, 48, 1, 88, "Section", CellTags->"c:22"]}, "c:23"->{ Cell[45926, 1464, 74, 1, 42, "Subsection", CellTags->"c:23"]}, "c:24"->{ Cell[46025, 1469, 59, 1, 42, "Subsubsection", CellTags->"c:24"]}, "c:25"->{ Cell[51329, 1638, 66, 1, 42, "Subsubsection", CellTags->"c:25"]}, "c:26"->{ Cell[54543, 1741, 68, 1, 28, "Subsubsection", CellTags->"c:26"]}, "c:27"->{ Cell[56122, 1792, 129, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:27"]}, "c:28"->{ Cell[56276, 1799, 55, 1, 42, "Subsubsection", CellTags->"c:28"]}, "c:29"->{ Cell[63771, 2024, 60, 1, 42, "Subsubsection", CellTags->"c:29"]}, "c:30"->{ Cell[68381, 2185, 59, 1, 42, "Subsubsection", CellTags->"c:30"]}, "c:31"->{ Cell[72809, 2339, 110, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:31"]}, "c:32"->{ Cell[80933, 2613, 114, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:32"]}, "c:33"->{ Cell[86993, 2815, 116, 3, 28, "Subsubsection", Evaluatable->False, CellTags->"c:33"]}, "c:34"->{ Cell[98260, 3203, 123, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:34"]}, "c:35"->{ Cell[102803, 3335, 64, 1, 42, "Subsection", CellTags->"c:35"]}, "c:36"->{ Cell[103702, 3358, 121, 5, 44, "Subsubsection", CellTags->"c:36"]}, "c:37"->{ Cell[107380, 3502, 54, 1, 42, "Subsubsection", CellTags->"c:37"]}, "c:38"->{ Cell[109744, 3585, 56, 1, 42, "Subsubsection", CellTags->"c:38"]}, "c:39"->{ Cell[111436, 3643, 118, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:39"]}, "c:40"->{ Cell[111579, 3650, 80, 1, 42, "Subsubsection", CellTags->"c:40"]}, "c:41"->{ Cell[114699, 3756, 61, 1, 28, "Subsubsection", CellTags->"c:41"]}, "c:42"->{ Cell[120024, 3906, 62, 1, 42, "Subsubsection", CellTags->"c:42"]}, "c:43"->{ Cell[121747, 3971, 99, 3, 88, "Section", Evaluatable->False, CellTags->"c:43"]}, "c:44"->{ Cell[121871, 3978, 113, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:44"]}, "c:45"->{ Cell[126009, 4125, 122, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:45"]}, "c:46"->{ Cell[134702, 4421, 121, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:46"]}, "c:47"->{ Cell[136686, 4486, 61, 1, 42, "Subsubsection", CellTags->"c:47"]}, "c:48"->{ Cell[140475, 4637, 112, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:48"]}, "c:49"->{ Cell[141741, 4690, 124, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:49"]} } *) (*CellTagsIndex CellTagsIndex->{ {"c:1", 146929, 4865}, {"c:2", 147031, 4869}, {"c:3", 147134, 4873}, {"c:4", 147241, 4877}, {"c:5", 147324, 4880}, {"c:6", 147408, 4883}, {"c:7", 147492, 4886}, {"c:8", 147600, 4890}, {"c:9", 147684, 4893}, {"c:10", 147770, 4896}, {"c:11", 147857, 4899}, {"c:12", 147968, 4903}, {"c:13", 148082, 4907}, {"c:14", 148196, 4911}, {"c:15", 148310, 4915}, {"c:16", 148424, 4919}, {"c:17", 148535, 4923}, {"c:18", 148647, 4927}, {"c:19", 148762, 4931}, {"c:20", 148877, 4935}, {"c:21", 148989, 4939}, {"c:22", 149101, 4943}, {"c:23", 149183, 4946}, {"c:24", 149268, 4949}, {"c:25", 149356, 4952}, {"c:26", 149444, 4955}, {"c:27", 149532, 4958}, {"c:28", 149644, 4962}, {"c:29", 149732, 4965}, {"c:30", 149820, 4968}, {"c:31", 149908, 4971}, {"c:32", 150023, 4975}, {"c:33", 150138, 4979}, {"c:34", 150253, 4983}, {"c:35", 150365, 4987}, {"c:36", 150451, 4990}, {"c:37", 150541, 4993}, {"c:38", 150630, 4996}, {"c:39", 150719, 4999}, {"c:40", 150832, 5003}, {"c:41", 150921, 5006}, {"c:42", 151010, 5009}, {"c:43", 151099, 5012}, {"c:44", 151208, 5016}, {"c:45", 151321, 5020}, {"c:46", 151434, 5024}, {"c:47", 151547, 5028}, {"c:48", 151636, 5031}, {"c:49", 151752, 5035} } *) (*NotebookFileOutline Notebook[{ Cell[1754, 51, 49, 0, 40, "SmallText"], Cell[CellGroupData[{ Cell[1828, 55, 93, 3, 110, "Title", Evaluatable->False, CellTags->"c:1"], Cell[CellGroupData[{ Cell[1946, 62, 95, 3, 88, "Section", Evaluatable->False, CellTags->"c:2"], Cell[CellGroupData[{ Cell[2066, 69, 100, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:3"], Cell[CellGroupData[{ Cell[2191, 76, 52, 1, 42, "Subsubsection", CellTags->"c:4"], Cell[2246, 79, 456, 12, 273, "Text"], Cell[2705, 93, 69, 0, 50, "Input"], Cell[2777, 95, 66, 0, 50, "Input"], Cell[2846, 97, 59, 0, 50, "Input"], Cell[2908, 99, 69, 0, 50, "Input"], Cell[2980, 101, 70, 0, 50, "Input"], Cell[3053, 103, 63, 0, 50, "Input"], Cell[3119, 105, 96, 1, 50, "Input"], Cell[3218, 108, 123, 4, 70, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[3378, 117, 55, 1, 42, "Subsubsection", CellTags->"c:5"], Cell[3436, 120, 223, 5, 93, "Text"], Cell[3662, 127, 124, 8, 155, "Program"], Cell[3789, 137, 632, 13, 143, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[4458, 155, 74, 1, 42, "Subsubsection", CellTags->"c:6"], Cell[4535, 158, 363, 8, 93, "Text"], Cell[4901, 168, 76, 5, 95, "Program"], Cell[4980, 175, 1126, 27, 309, "Text"], Cell[6109, 204, 589, 10, 193, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[6747, 220, 101, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:7"], Cell[CellGroupData[{ Cell[6873, 227, 59, 1, 42, "Subsubsection", CellTags->"c:8"], Cell[6935, 230, 3540, 125, 418, "Text", Evaluatable->False], Cell[10478, 357, 1750, 50, 218, "Text"], Cell[12231, 409, 1156, 31, 193, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[13424, 445, 61, 1, 42, "Subsubsection", CellTags->"c:9"], Cell[13488, 448, 1513, 38, 248, "Text", Evaluatable->False], Cell[15004, 488, 1293, 34, 198, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[16334, 527, 60, 1, 42, "Subsubsection", CellTags->"c:10"], Cell[16397, 530, 1345, 32, 243, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[17791, 568, 114, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:11"], Cell[17908, 573, 171, 5, 43, "Text", Evaluatable->False], Cell[CellGroupData[{ Cell[18104, 582, 107, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:12"], Cell[18214, 587, 2358, 72, 318, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[20609, 664, 106, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:13"], Cell[20718, 669, 1906, 61, 293, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[22661, 735, 123, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:14"], Cell[22787, 740, 1946, 52, 343, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[24770, 797, 115, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:15"], Cell[24888, 802, 2876, 93, 493, "Text", Evaluatable->False], Cell[27767, 897, 1376, 32, 223, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[29192, 935, 104, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:16"], Cell[29299, 940, 484, 13, 93, "Text", Evaluatable->False], Cell[29786, 955, 146, 6, 92, "InputOnly"], Cell[29935, 963, 171, 4, 68, "Text"], Cell[30109, 969, 67, 1, 50, "Input"], Cell[30179, 972, 40, 0, 43, "Text"], Cell[30222, 974, 89, 1, 50, "Input"], Cell[30314, 977, 258, 7, 68, "Text"], Cell[30575, 986, 45, 0, 43, "Text"], Cell[30623, 988, 74, 1, 32, "InputOnly"], Cell[30700, 991, 67, 1, 50, "Input"], Cell[30770, 994, 74, 1, 32, "InputOnly"], Cell[30847, 997, 67, 1, 50, "Input"], Cell[30917, 1000, 487, 16, 68, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[31441, 1021, 114, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:17"], Cell[31558, 1026, 355, 7, 93, "Text", Evaluatable->False], Cell[CellGroupData[{ Cell[31938, 1037, 118, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:18"], Cell[32059, 1042, 1617, 44, 168, "Text", Evaluatable->False], Cell[33679, 1088, 971, 25, 193, "Text", Evaluatable->False], Cell[34653, 1115, 924, 27, 168, "Text", Evaluatable->False], Cell[35580, 1144, 2127, 72, 368, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[37744, 1221, 113, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:19"], Cell[37860, 1226, 3106, 101, 496, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[41015, 1333, 118, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:20"], Cell[41136, 1338, 2745, 72, 518, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[43918, 1415, 113, 3, 28, "Subsection", Evaluatable->False, CellTags->"c:21"], Cell[44034, 1420, 1139, 20, 293, "Text", Evaluatable->False], Cell[45176, 1442, 628, 11, 168, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[45853, 1459, 48, 1, 88, "Section", CellTags->"c:22"], Cell[CellGroupData[{ Cell[45926, 1464, 74, 1, 42, "Subsection", CellTags->"c:23"], Cell[CellGroupData[{ Cell[46025, 1469, 59, 1, 42, "Subsubsection", CellTags->"c:24"], Cell[46087, 1472, 2999, 79, 618, "Text"], Cell[49089, 1553, 164, 5, 43, "Text", Evaluatable->False], Cell[49256, 1560, 234, 5, 118, "InputOnly"], Cell[49493, 1567, 99, 3, 50, "Input"], Cell[49595, 1572, 487, 14, 93, "Text"], Cell[50085, 1588, 130, 5, 90, "Input"], Cell[50218, 1595, 146, 3, 68, "Text"], Cell[50367, 1600, 153, 6, 110, "Input"], Cell[50523, 1608, 87, 3, 43, "Text"], Cell[50613, 1613, 64, 1, 50, "Input"], Cell[50680, 1616, 64, 1, 50, "Input"], Cell[50747, 1619, 545, 14, 118, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[51329, 1638, 66, 1, 42, "Subsubsection", CellTags->"c:25"], Cell[51398, 1641, 461, 11, 93, "Text", Evaluatable->False], Cell[51862, 1654, 1121, 34, 218, "Text", Evaluatable->False], Cell[52986, 1690, 752, 22, 143, "Text", Evaluatable->False], Cell[53741, 1714, 765, 22, 168, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[54543, 1741, 68, 1, 28, "Subsubsection", CellTags->"c:26"], Cell[54614, 1744, 201, 5, 68, "Text"], Cell[54818, 1751, 125, 3, 97, "Input"], Cell[54946, 1756, 752, 17, 193, "Text"], Cell[55701, 1775, 161, 3, 97, "Input"], Cell[55865, 1780, 50, 1, 51, "Input"], Cell[55918, 1783, 155, 3, 68, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[56122, 1792, 129, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:27"], Cell[CellGroupData[{ Cell[56276, 1799, 55, 1, 42, "Subsubsection", CellTags->"c:28"], Cell[56334, 1802, 2643, 78, 268, "Text", Evaluatable->False], Cell[58980, 1882, 2035, 65, 293, "Text", Evaluatable->False], Cell[61018, 1949, 62, 1, 51, "Input"], Cell[61083, 1952, 63, 1, 51, "Input"], Cell[61149, 1955, 91, 1, 51, "Input"], Cell[61243, 1958, 152, 3, 68, "Text"], Cell[61398, 1963, 2336, 56, 343, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[63771, 2024, 60, 1, 42, "Subsubsection", CellTags->"c:29"], Cell[63834, 2027, 1237, 37, 143, "Text", Evaluatable->False], Cell[65074, 2066, 123, 3, 97, "Input"], Cell[65200, 2071, 297, 9, 68, "Text"], Cell[65500, 2082, 123, 3, 97, "Input"], Cell[65626, 2087, 87, 3, 43, "Text"], Cell[65716, 2092, 545, 18, 68, "Text"], Cell[66264, 2112, 173, 4, 120, "Input"], Cell[66440, 2118, 121, 3, 43, "Text"], Cell[66564, 2123, 130, 2, 74, "Input"], Cell[66697, 2127, 242, 6, 68, "Text"], Cell[66942, 2135, 228, 5, 43, "Text"], Cell[67173, 2142, 83, 2, 74, "Input"], Cell[67259, 2146, 130, 2, 74, "Input"], Cell[67392, 2150, 165, 4, 68, "Text"], Cell[67560, 2156, 133, 3, 51, "Input"], Cell[67696, 2161, 180, 3, 74, "Input"], Cell[67879, 2166, 133, 3, 51, "Input"], Cell[68015, 2171, 193, 4, 74, "Input"], Cell[68211, 2177, 133, 3, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[68381, 2185, 59, 1, 42, "Subsubsection", CellTags->"c:30"], Cell[68443, 2188, 485, 15, 168, "Text", Evaluatable->False], Cell[68931, 2205, 222, 7, 43, "Text"], Cell[69156, 2214, 148, 2, 74, "Input"], Cell[69307, 2218, 28, 0, 43, "Text"], Cell[69338, 2220, 57, 1, 51, "Input"], Cell[69398, 2223, 305, 7, 68, "Text", Evaluatable->False], Cell[69706, 2232, 184, 3, 74, "Input"], Cell[69893, 2237, 148, 5, 43, "Text", Evaluatable->False], Cell[70044, 2244, 109, 2, 51, "Input"], Cell[70156, 2248, 545, 16, 118, "Text", Evaluatable->False], Cell[70704, 2266, 195, 5, 120, "Input"], Cell[70902, 2273, 845, 27, 93, "Text", Evaluatable->False], Cell[71750, 2302, 193, 4, 43, "Text", Evaluatable->False], Cell[71946, 2308, 597, 20, 68, "Text", Evaluatable->False], Cell[72546, 2330, 226, 4, 68, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[72809, 2339, 110, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:31"], Cell[72922, 2344, 841, 29, 168, "Text", Evaluatable->False], Cell[73766, 2375, 120, 3, 74, "Input"], Cell[73889, 2380, 319, 10, 68, "Text", Evaluatable->False], Cell[74211, 2392, 239, 6, 120, "Input"], Cell[74453, 2400, 108, 2, 43, "Text", Evaluatable->False], Cell[74564, 2404, 146, 3, 51, "Input"], Cell[74713, 2409, 135, 3, 51, "Input"], Cell[74851, 2414, 5109, 162, 684, "Text", Evaluatable->False], Cell[79963, 2578, 150, 4, 97, "Input"], Cell[80116, 2584, 69, 0, 43, "Text"], Cell[80188, 2586, 84, 2, 51, "Input"], Cell[80275, 2590, 68, 0, 43, "Text"], Cell[80346, 2592, 273, 7, 143, "Input"], Cell[80622, 2601, 274, 7, 143, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[80933, 2613, 114, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:32"], Cell[81050, 2618, 185, 4, 43, "Text", Evaluatable->False], Cell[81238, 2624, 657, 22, 68, "Text", Evaluatable->False], Cell[81898, 2648, 5058, 162, 543, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[86993, 2815, 116, 3, 28, "Subsubsection", Evaluatable->False, CellTags->"c:33"], Cell[87112, 2820, 920, 30, 193, "Text", Evaluatable->False], Cell[88035, 2852, 119, 3, 74, "Input"], Cell[88157, 2857, 506, 13, 118, "Text", Evaluatable->False], Cell[88666, 2872, 239, 6, 120, "Input"], Cell[88908, 2880, 1098, 35, 173, "Text", Evaluatable->False], Cell[90009, 2917, 200, 5, 97, "Input"], Cell[90212, 2924, 203, 5, 97, "Input"], Cell[90418, 2931, 156, 4, 97, "Input"], Cell[90577, 2937, 166, 3, 74, "Input"], Cell[90746, 2942, 308, 10, 68, "Text", Evaluatable->False], Cell[91057, 2954, 156, 4, 97, "Input"], Cell[91216, 2960, 139, 5, 43, "Text", Evaluatable->False], Cell[91358, 2967, 102, 2, 51, "Input"], Cell[91463, 2971, 135, 3, 51, "Input"], Cell[91601, 2976, 187, 4, 97, "Input"], Cell[91791, 2982, 1720, 54, 218, "Text", Evaluatable->False], Cell[93514, 3038, 84, 1, 51, "Input"], Cell[93601, 3041, 84, 2, 74, "Input"], Cell[93688, 3045, 48, 0, 43, "Text"], Cell[93739, 3047, 255, 6, 143, "Input"], Cell[93997, 3055, 63, 1, 51, "Input"], Cell[94063, 3058, 104, 3, 43, "Text"], Cell[94170, 3063, 343, 7, 120, "Input"], Cell[94516, 3072, 3695, 125, 476, "Text", Evaluatable->False] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[98260, 3203, 123, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:34"], Cell[98386, 3208, 1973, 39, 393, "Text", Evaluatable->False], Cell[100362, 3249, 425, 17, 321, "InputOnly"], Cell[100790, 3268, 92, 2, 43, "Text", Evaluatable->False], Cell[100885, 3272, 173, 4, 97, "Input"], Cell[101061, 3278, 128, 3, 74, "Input"], Cell[101192, 3283, 99, 2, 43, "Text", Evaluatable->False], Cell[101294, 3287, 83, 2, 51, "Input"], Cell[101380, 3291, 257, 7, 68, "Text", Evaluatable->False], Cell[101640, 3300, 128, 3, 74, "Input"], Cell[101771, 3305, 326, 7, 166, "Input"], Cell[102100, 3314, 666, 16, 143, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[102803, 3335, 64, 1, 42, "Subsection", CellTags->"c:35"], Cell[102870, 3338, 383, 6, 118, "Text"], Cell[103256, 3346, 421, 8, 118, "Text", Evaluatable->False], Cell[CellGroupData[{ Cell[103702, 3358, 121, 5, 44, "Subsubsection", CellTags->"c:36"], Cell[103826, 3365, 767, 23, 168, "Text", Evaluatable->False], Cell[104596, 3390, 170, 4, 112, "Input"], Cell[104769, 3396, 216, 7, 68, "Text"], Cell[104988, 3405, 711, 20, 193, "Text"], Cell[105702, 3427, 729, 28, 73, "Text"], Cell[106434, 3457, 147, 4, 154, "Input"], Cell[106584, 3463, 266, 8, 43, "Text"], Cell[106853, 3473, 43, 1, 51, "Input"], Cell[106899, 3476, 43, 1, 51, "Input"], Cell[106945, 3479, 43, 1, 51, "Input"], Cell[106991, 3482, 50, 0, 43, "Text"], Cell[107044, 3484, 39, 1, 66, "Input"], Cell[107086, 3487, 153, 4, 43, "Text"], Cell[107242, 3493, 47, 1, 51, "Input"], Cell[107292, 3496, 51, 1, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[107380, 3502, 54, 1, 42, "Subsubsection", CellTags->"c:37"], Cell[107437, 3505, 254, 5, 68, "Text", Evaluatable->False], Cell[107694, 3512, 248, 5, 120, "Input"], Cell[107945, 3519, 165, 5, 43, "Text", Evaluatable->False], Cell[108113, 3526, 156, 3, 74, "Input"], Cell[108272, 3531, 167, 5, 43, "Text", Evaluatable->False], Cell[108442, 3538, 149, 3, 74, "Input"], Cell[108594, 3543, 143, 5, 43, "Text", Evaluatable->False], Cell[108740, 3550, 96, 2, 51, "Input"], Cell[108839, 3554, 221, 6, 43, "Text", Evaluatable->False], Cell[109063, 3562, 104, 3, 74, "Input"], Cell[109170, 3567, 452, 9, 93, "Text", Evaluatable->False], Cell[109625, 3578, 82, 2, 51, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[109744, 3585, 56, 1, 42, "Subsubsection", CellTags->"c:38"], Cell[109803, 3588, 944, 25, 128, "Text", Evaluatable->False], Cell[110750, 3615, 101, 2, 51, "Input"], Cell[110854, 3619, 68, 2, 43, "Text"], Cell[110925, 3623, 75, 2, 51, "Input"], Cell[111003, 3627, 160, 4, 160, "Input"], Cell[111166, 3633, 221, 4, 68, "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[111436, 3643, 118, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:39"], Cell[CellGroupData[{ Cell[111579, 3650, 80, 1, 42, "Subsubsection", CellTags->"c:40"], Cell[111662, 3653, 774, 26, 127, "Text"], Cell[112439, 3681, 144, 5, 96, "InlineInput"], Cell[112586, 3688, 513, 16, 79, "Text"], Cell[113102, 3706, 484, 15, 93, "Text"], Cell[113589, 3723, 1073, 28, 168, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[114699, 3756, 61, 1, 28, "Subsubsection", CellTags->"c:41"], Cell[114763, 3759, 89, 3, 43, "Text"], Cell[114855, 3764, 647, 15, 147, "Input"], Cell[115505, 3781, 531, 13, 74, "Input"], Cell[116039, 3796, 845, 19, 143, "Input"], Cell[116887, 3817, 214, 4, 68, "Text"], Cell[117104, 3823, 225, 5, 174, "Input"], Cell[117332, 3830, 458, 9, 166, "Input"], Cell[117793, 3841, 553, 17, 98, "Text"], Cell[118349, 3860, 645, 15, 143, "Input"], Cell[118997, 3877, 531, 13, 74, "Input"], Cell[119531, 3892, 456, 9, 166, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[120024, 3906, 62, 1, 42, "Subsubsection", CellTags->"c:42"], Cell[120089, 3909, 107, 3, 43, "Text"], Cell[120199, 3914, 88, 2, 78, "Input"], Cell[120290, 3918, 92, 1, 83, "Input"], Cell[120385, 3921, 53, 1, 51, "Input"], Cell[120441, 3924, 66, 0, 43, "Text"], Cell[120510, 3926, 102, 2, 83, "Input"], Cell[120615, 3930, 53, 1, 51, "Input"], Cell[120671, 3933, 442, 10, 93, "Text"], Cell[121116, 3945, 239, 5, 174, "Input"], Cell[121358, 3952, 73, 2, 89, "Input"], Cell[121434, 3956, 82, 2, 102, "Input"], Cell[121519, 3960, 167, 4, 93, "Text"] }, Closed]] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[121747, 3971, 99, 3, 88, "Section", Evaluatable->False, CellTags->"c:43"], Cell[CellGroupData[{ Cell[121871, 3978, 113, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:44"], Cell[121987, 3983, 2217, 73, 486, "Text", Evaluatable->False], Cell[124207, 4058, 101, 5, 90, "Input"], Cell[124311, 4065, 1593, 52, 293, "Text", Evaluatable->False], Cell[125907, 4119, 65, 1, 50, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[126009, 4125, 122, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:45"], Cell[126134, 4130, 1633, 51, 218, "Text", Evaluatable->False], Cell[127770, 4183, 472, 19, 68, "Text", Evaluatable->False], Cell[128245, 4204, 3551, 108, 518, "Text", Evaluatable->False], Cell[131799, 4314, 916, 28, 198, "Text", Evaluatable->False], Cell[132718, 4344, 88, 1, 50, "Input"], Cell[132809, 4347, 48, 3, 70, "Input"], Cell[132860, 4352, 89, 1, 50, "Input"], Cell[132952, 4355, 367, 8, 93, "Text", Evaluatable->False], Cell[133322, 4365, 72, 1, 50, "Input"], Cell[133397, 4368, 68, 1, 50, "Input"], Cell[133468, 4371, 58, 1, 50, "Input"], Cell[133529, 4374, 395, 10, 118, "Text", Evaluatable->False], Cell[133927, 4386, 106, 5, 90, "Input"], Cell[134036, 4393, 114, 4, 70, "Input"], Cell[134153, 4399, 122, 2, 43, "Text", Evaluatable->False], Cell[134278, 4403, 83, 1, 50, "Input"], Cell[134364, 4406, 185, 5, 43, "Text", Evaluatable->False], Cell[134552, 4413, 42, 0, 50, "Input"], Cell[134597, 4415, 68, 1, 50, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[134702, 4421, 121, 3, 42, "Subsection", Evaluatable->False, CellTags->"c:46"], Cell[134826, 4426, 1835, 56, 318, "Text", Evaluatable->False], Cell[CellGroupData[{ Cell[136686, 4486, 61, 1, 42, "Subsubsection", CellTags->"c:47"], Cell[136750, 4489, 508, 16, 68, "Text", Evaluatable->False], Cell[137261, 4507, 112, 6, 75, "InlineInput", Evaluatable->False], Cell[137376, 4515, 515, 13, 93, "Text", Evaluatable->False], Cell[137894, 4530, 45, 0, 50, "Input"], Cell[137942, 4532, 53, 0, 50, "Input"], Cell[137998, 4534, 20, 0, 50, "Input"], Cell[138021, 4536, 45, 0, 50, "Input"], Cell[138069, 4538, 127, 5, 43, "Text"], Cell[138199, 4545, 43, 0, 50, "Input"], Cell[138245, 4547, 702, 21, 93, "Text", Evaluatable->False], Cell[138950, 4570, 117, 6, 75, "InlineInput", Evaluatable->False], Cell[139070, 4578, 381, 12, 68, "Text", Evaluatable->False], Cell[139454, 4592, 117, 6, 110, "Input"], Cell[139574, 4600, 71, 1, 50, "Input"], Cell[139648, 4603, 310, 12, 68, "Text", Evaluatable->False], Cell[139961, 4617, 140, 2, 74, "Input"], Cell[140104, 4621, 334, 11, 68, "Text", Evaluatable->False] }, Closed]], Cell[CellGroupData[{ Cell[140475, 4637, 112, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:48"], Cell[140590, 4642, 438, 12, 68, "Text", Evaluatable->False], Cell[141031, 4656, 132, 6, 110, "Input"], Cell[141166, 4664, 227, 10, 43, "Text", Evaluatable->False], Cell[141396, 4676, 72, 1, 50, "Input"], Cell[141471, 4679, 99, 2, 43, "Text", Evaluatable->False], Cell[141573, 4683, 131, 2, 74, "Input"] }, Closed]], Cell[CellGroupData[{ Cell[141741, 4690, 124, 3, 42, "Subsubsection", Evaluatable->False, CellTags->"c:49"], Cell[141868, 4695, 316, 10, 43, "Text", Evaluatable->False], Cell[142187, 4707, 172, 4, 74, "Input"], Cell[142362, 4713, 852, 25, 118, "Text", Evaluatable->False], Cell[143217, 4740, 141, 3, 59, "Input"], Cell[143361, 4745, 689, 23, 98, "Text", Evaluatable->False], Cell[144053, 4770, 505, 16, 93, "Text", Evaluatable->False], Cell[144561, 4788, 130, 3, 74, "Input"], Cell[144694, 4793, 113, 3, 43, "Text"], Cell[144810, 4798, 86, 3, 70, "Input"], Cell[144899, 4803, 225, 4, 68, "Text"], Cell[145127, 4809, 50, 0, 50, "Input"], Cell[145180, 4811, 608, 15, 118, "Text", Evaluatable->False], Cell[145791, 4828, 77, 1, 50, "Input"], Cell[145871, 4831, 72, 1, 50, "Input"] }, Closed]] }, Closed]] }, Closed]] }, Closed]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)