(************** Content-type: application/mathematica ************** CreatedBy='Mathematica 5.2' 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[ 70438, 2300]*) (*NotebookOutlinePosition[ 71758, 2343]*) (* CellTagsIndexPosition[ 71687, 2337]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell["Divisibility and State-Complexity ", "Title"], Cell["Klaus Sutner", "Author"], Cell["\<\ Carnegie Mellon University 5000 Forbes Avenue Pittsburgh, PA 15213 sutner@cs.cmu.edu\ \>", "TextAboutAuthor"], Cell[CellGroupData[{ Cell[TextData[StyleBox["Requirements", FontColor->RGBColor[0, 0, 1]]], "Subsubsection"], Cell[TextData[{ "Most of the computations in this notebook depend on ", StyleBox["Automata", "MR"], ", a large package that implements finite state machines. The package is \ freely available at ", ButtonBox["www.cs.cmu.edu/~sutner", ButtonData:>{ URL[ "http://www.cs.cmu.edu/~sutner"], None}, ButtonStyle->"Hyperlink"], " and contains installation instructions. " }], "Text"], Cell[BoxData[{ \(Needs["\"]\), "\[IndentingNewLine]", \(Get["\"]\), "\[IndentingNewLine]", \(Get["\"]\), "\[IndentingNewLine]", \(MakeAbbrevs[]\), "\[IndentingNewLine]", \(Off[General::spell]\), "\[IndentingNewLine]", \(Off[General::spell1]\)}], "InputOnly", CellLabel->"In[1]:="] }, Open ]], Cell[CellGroupData[{ Cell["Automaticity and State-Complexity", "Section"], Cell[CellGroupData[{ Cell["Automaticity", "Subsection"], Cell[TextData[{ "A sequence ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["a", FontWeight->"Bold"], " ", "=", " ", \((a\_n)\)}], TraditionalForm]]], " is ", Cell[BoxData[ \(TraditionalForm\`B\)]], "-automatic if it can be recognized by a finite state machine in the sense \ that, on input ", Cell[BoxData[ \(TraditionalForm\`n\)]], ", the machine outputs ", Cell[BoxData[ \(TraditionalForm\`a\_n\)]], ". Here ", Cell[BoxData[ \(TraditionalForm\`n\)]], " is usually written in standard base ", Cell[BoxData[ \(TraditionalForm\`B\)]], " notation, though other numeration systems are also considered. A typical \ example is the Morse-Thue sequence ", Cell[BoxData[ \(TraditionalForm\`\((t\_n)\)\)]], " which is usually defined in terms of iterated morphisms. However, there \ is an alternative characterization that shows that ", Cell[BoxData[ \(TraditionalForm\`t\_n\)]], " is the digit-sum of the binary expansion of ", Cell[BoxData[ \(TraditionalForm\`n\)]], " modulo 2. Thus, the Morse-Thue sequence is 2-automatic. The study of \ automaticity has lately attracted a lot of attention, see the excellent book \ by Allouche and Shallit ", StyleBox["[AS]", "Reference"], ".\n\nAlas, little is known about the state complexity of the finite state \ machines in question: given an automatic sequence, what is the size ", Cell[BoxData[ FormBox[ RowBox[{"\[Mu]", "(", StyleBox["a", FontWeight->"Bold"], ")"}], TraditionalForm]]], " of the smallest machine that recognizes it? Often there is a canonical \ machine that witnesses the automaticity of a sequence and provides an upper \ bound on ", Cell[BoxData[ FormBox[ RowBox[{"\[Mu]", "(", StyleBox["a", FontWeight->"Bold"], ")"}], TraditionalForm]]], ", but the inherent complexity of the minimization process often makes it \ very difficult to pin down the exact state-complexity of the sequence. Using \ a suitable computational environment one can generate sample data that can \ lead to plausible conjectures. More computation can then help to prune false \ assumptions and produce answers, at least in a few selected cases. This is \ particulary important since the combinatorics of our problem will turn out to \ be fairly complicated so that in general no simple closed form solutions are \ available. " }], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["Divisibility and Horner Automata", "Subsection"], Cell[TextData[{ "In this paper we will study the state complexity of machines recognizing \ the set ", Cell[BoxData[ \(TraditionalForm\`m\ \[DoubleStruckCapitalN]\)]], " of all multiples of a fixed modulus ", Cell[BoxData[ \(TraditionalForm\`m\)]], ". It is not hard to see that ", Cell[BoxData[ \(TraditionalForm\`m\ \[DoubleStruckCapitalN]\)]], " is indeed ", Cell[BoxData[ \(TraditionalForm\`B\)]], "-recognizable for any base ", Cell[BoxData[ \(TraditionalForm\`B \[GreaterEqual] \ 1\)]], " (we will focus on the interesting case ", Cell[BoxData[ \(TraditionalForm\`B \[GreaterEqual] \ 2\)]], " in what follows). We denote the digit alphabet ", Cell[BoxData[ \(TraditionalForm\`{0, 1, \[Ellipsis], B - 1}\)]], " by ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\_B\)]], ". There is a canonical DFA ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalA]\ = \ \[ScriptCapitalA]\_\(m, \ B\)\)]], " that accepts all strings ", Cell[BoxData[ \(TraditionalForm\`w\ \[Element] \ \[CapitalSigma]\_B\%\(\(\ \)\(*\)\)\ \)]], " that denote numbers in base ", Cell[BoxData[ \(TraditionalForm\`B\)]], " notation that are divisible by ", Cell[BoxData[ \(TraditionalForm\`m\)]], ". The state set of ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalA]\)]], " is the set ", Cell[BoxData[ \(TraditionalForm\`\((m)\)\ = \ {0, 1, \[Ellipsis], m - 1}\)]], " of modular numbers and the right action is given by\n\t", Cell[BoxData[ \(TraditionalForm\`p\ \[CenterDot]\ a\ = \ B\ p\ + \ a\ \ mod\ m\)]], ". \nIf we fix the initial state to ", Cell[BoxData[ \(TraditionalForm\`q\_0 = 0\)]], " we have ", Cell[BoxData[ \(TraditionalForm\`q\_0\ \[CenterDot]\ w\ = \ \ \(\[Nu](w)\)\ \ mod\ \ m\)]], " for any word ", Cell[BoxData[ \(TraditionalForm\`w\)]], ". \nHere ", Cell[BoxData[ \(TraditionalForm\`\[Nu](w)\)]], " denotes the value of ", Cell[BoxData[ \(TraditionalForm\`w\)]], ": the value of word ", Cell[BoxData[ \(TraditionalForm\`w\ = \ \(w\_\(k - 1\)\) \(w\_\(k - 2\)\) \[Ellipsis]\ \(w\_1\) w\_0\)]], " is \n\t", Cell[BoxData[ \(TraditionalForm\`\[Nu]( w)\ = \ \[CapitalSigma]\_\(\(\ \)\(i\ < \ k\)\)\ \(w\_i\) B\^\(\(\ \)\(i\)\)\)]], ".\nThus, the action corresponds to the standard Horner scheme of \ evaluating polynomials and we will refer to these machines as Horner \ automata. Hera are some sample Horner automata." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(m\ = \ 5; \ B\ = \ 2;\), "\[IndentingNewLine]", \(M\ = \ DivisibilityDFA[\ m, B, Full \[Rule] True]\)}], "Input", CellLabel->"In[7]:="], Cell[BoxData[ TagBox[ RowBox[{"DFA", "[", RowBox[{"5", ",", \(-2\), ",", TagBox[\({{1, 3, 5, 2, 4}, {2, 4, 1, 3, 5}}\), (Short[ #, 4]&)], ",", TagBox["1", (Short[ #, 4]&)], ",", TagBox[\({1}\), (Short[ #, 4]&)]}], "]"}], HoldForm]], "Output", CellLabel->"Out[8]="] }, Open ]], Cell["\<\ We generate all words in the acceptance language of length 6 and \ compute their numerical values.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(LanguageFA[M, 6]\)], "Input", CellLabel->"In[9]:="], Cell[BoxData[ \({"000000", "000101", "001010", "001111", "010100", "011001", "011110", "100011", "101000", "101101", "110010", "110111", "111100"}\)], "Output",\ CellLabel->"Out[9]="] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(\(WordToNumber[B]\)[%]\)], "Input", CellLabel->"In[10]:="], Cell[BoxData[ \({0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60}\)], "Output", CellLabel->"Out[10]="] }, Open ]], Cell["\<\ As required, the moduli are all 0. Other useful information about \ the associated language can be extracted from the automaton. For example, we \ can obtain generating function for the growth rate.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(Clear[x]\), "\[IndentingNewLine]", \(gs\ = \ GrowthSeriesDFA[M, x]\)}], "Input", CellLabel->"In[11]:="], Cell[BoxData[ \(\(1 - 2\ x + x\^2 - x\^3\)\/\(1 - 3\ x + 3\ x\^2 - 3\ x\^3 + 2\ \ x\^4\)\)], "Output", CellLabel->"Out[12]="] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(Series[\ gs, \ {x, 0, 10}\ ]\)], "Input", CellLabel->"In[13]:="], Cell[BoxData[ InterpretationBox[ RowBox[{ "1", "+", "x", "+", \(x\^2\), "+", \(2\ x\^3\), "+", \(4\ x\^4\), "+", \(7\ x\^5\), "+", \(13\ x\^6\), "+", \(26\ x\^7\), "+", \(52\ x\^8\), "+", \(103\ x\^9\), "+", \(205\ x\^10\), "+", InterpretationBox[\(O[x]\^11\), SeriesData[ x, 0, {}, 0, 11, 1], Editable->False]}], SeriesData[ x, 0, {1, 1, 1, 2, 4, 7, 13, 26, 52, 103, 205}, 0, 11, 1], Editable->False]], "Output", CellLabel->"Out[13]="] }, Open ]], Cell["A different base and modulus.", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(m\ = \ 20; \ B\ = \ 15;\), "\[IndentingNewLine]", \(M\ = \ DivisibilityDFA[\ m, B, Full \[Rule] True]\)}], "Input", CellLabel->"In[14]:="], Cell[BoxData[ TagBox[ RowBox[{"DFA", "[", RowBox[{"20", ",", \(-15\), ",", TagBox[\({{1, 16, 11, 6, 1, 16, 11, 6, 1, 16, 11, 6, 1, 16, 11, 6, 1, 16, 11, 6}, {2, 17, 12, 7, 2, 17, 12, 7, 2, 17, 12, 7, 2, 17, 12, 7, 2, 17, 12, 7}, \[LeftSkeleton]12\[RightSkeleton], {15, 10, 5, 20, 15, 10, 5, 20, 15, 10, 5, 20, 15, 10, 5, 20, 15, 10, 5, 20}}\), (Short[ #, 4]&)], ",", TagBox["1", (Short[ #, 4]&)], ",", TagBox[\({1}\), (Short[ #, 4]&)]}], "]"}], HoldForm]], "Output", CellLabel->"Out[15]="] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(\(WordToNumber[B]\)[LanguageFA[M, 2]]\)], "Input", CellLabel->"In[16]:="], Cell[BoxData[ \({0, 20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220}\)], "Output", CellLabel->"Out[16]="] }, Open ]], Cell[TextData[{ "Horner automata provide an upper bound for the state complexity of \ divisibility: ", Cell[BoxData[ \(TraditionalForm\`\[Mu](\ m\ \[DoubleStruckCapitalN]\ )\ \[LessEqual] \ m\)]], ", regardless of the base ", Cell[BoxData[ \(TraditionalForm\`B\)]], ". Alas, the bound is usually far from tight." }], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["Minimal Divisibility Recognizers", "Subsection"], Cell[CellGroupData[{ Cell["Pinning Down Behavioral Equivalence", "Subsubsection"], Cell[TextData[{ "Though the canonical Horner DFAs fail to be minimal in general they are \ still helpful in determining the structure of the minimal recognizers. \ Recall that any DFA for a regular language covers the minimal DFA, so we need \ to determine the fibers of the covering map. Abstractly, we can describe the \ corresponding partition as follows. Let \n\t", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalN]\_\(\(\ \)\(k, \ B\)\)\ = \ \ {\ c\ \[Element] \ \[DoubleStruckCapitalN]\ | \ 0\ \[LessEqual] \ c\ < \ B\^\(\(\ \)\(k\)\)\ }\)]], ". \nIt is well known that for radix ", Cell[BoxData[ \(TraditionalForm\`B\)]], " representation automaticity of divisibility follows from the fact that \ the following equivalence relation has finite index when ", Cell[BoxData[ \(TraditionalForm\`X\ = \ m\ \[DoubleStruckCapitalN]\)]], ": \n\n\t", Cell[BoxData[ FormBox[ FormBox[\(x\ \ \( \[Congruent] \_\(m, B\)\)\ y\ \ \ \[DoubleLongLeftRightArrow]\ \ \(\[ForAll] \ k\ \[GreaterEqual] \ 0\), \ c\ \[Element] \ \[DoubleStruckCapitalN]\_\(k, B\)\ \((\ \ \ \(B\^\(\(\ \)\(k\)\)\) x\ + \ c\ \[Element] \ X\ \[LongLeftRightArrow]\ B\^\(\(\ \)\(k\)\) y\ + \ c\ \[Element] \ X\ )\)\), "TraditionalForm"], TraditionalForm]]], ",\n\t\nsee [BHMV]. The index of this equivalence relation is none other \ than the state complexity we are interested in.\nHowever, this \ characterization does not readily produce a reasonable description of the \ state complexity.", Cell[BoxData[ FormBox[Cell[""], TraditionalForm]]], "\n\nBy applying a standard minimization algorithm to our Horner automata \ we can generate some data that will guide the search for a description of the \ state complexity. In the following table ", Cell[BoxData[ \(TraditionalForm\`m\)]], " is the row-index and ", Cell[BoxData[ \(TraditionalForm\`B\)]], " is the column-index." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(tab\ = \ Table[\ Size[ MinimizeFA[DivisibilityDFA[m, B, Full \[Rule] True]]], {m, 12}, {B, 16}];\)\), "\n", \(TableForm[\ tab, \ TableHeadings \[Rule] Automatic, TableSpacing \[Rule] {1, 1}]\)}], "Input", CellLabel->"In[17]:="], Cell[BoxData[ TagBox[GridBox[{ {"\<\"\"\>", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16"}, {"1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"}, {"2", "2", "2", "2", "2", "2", "2", "2", "2", "2", "2", "2", "2", "2", "2", "2", "2"}, {"3", "3", "3", "2", "3", "3", "2", "3", "3", "2", "3", "3", "2", "3", "3", "2", "3"}, {"4", "4", "3", "4", "2", "4", "3", "4", "2", "4", "3", "4", "2", "4", "3", "4", "2"}, {"5", "5", "5", "5", "5", "2", "5", "5", "5", "5", "2", "5", "5", "5", "5", "2", "5"}, {"6", "6", "4", "3", "4", "6", "2", "6", "4", "3", "4", "6", "2", "6", "4", "3", "4"}, {"7", "7", "7", "7", "7", "7", "7", "2", "7", "7", "7", "7", "7", "7", "2", "7", "7"}, {"8", "8", "4", "8", "3", "8", "5", "8", "2", "8", "5", "8", "3", "8", "5", "8", "2"}, {"9", "9", "9", "3", "9", "9", "4", "9", "9", "2", "9", "9", "4", "9", "9", "4", "9"}, {"10", "10", "6", "10", "6", "3", "6", "10", "6", "10", "2", "10", "6", "10", "6", "3", "6"}, {"11", "11", "11", "11", "11", "11", "11", "11", "11", "11", "11", "2", "11", "11", "11", "11", "11"}, {"12", "12", "5", "5", "4", "12", "3", "12", "4", "5", "7", "12", "2", "12", "7", "5", "4"} }, RowSpacings->1, ColumnSpacings->1, RowAlignments->Baseline, ColumnAlignments->{Left}], Function[ BoxForm`e$, TableForm[ BoxForm`e$, TableHeadings -> Automatic, TableSpacing -> {1, 1}]]]], "Output", CellLabel->"Out[18]//TableForm="] }, Open ]], Cell[TextData[{ "We will write ", Cell[BoxData[ \(TraditionalForm\`\[Mu](m, B)\)]], " for the size of the minimal DFA that recognizes numbers divisible by ", Cell[BoxData[ \(TraditionalForm\`m\)]], " in base ", Cell[BoxData[ \(TraditionalForm\`B\)]], " notation. If we disregard ", Cell[BoxData[ \(TraditionalForm\`B = 1\)]], " the table suggests that ", Cell[BoxData[ \(TraditionalForm\`\[Mu](m, m) = 2\)]], ". Moreover, for ", Cell[BoxData[ \(TraditionalForm\`m\)]], " and ", Cell[BoxData[ \(TraditionalForm\`B\)]], " coprime we have ", Cell[BoxData[ \(TraditionalForm\`\[Mu](m, B) = m\)]], " so that the Horner automaton is already minimal. Both observations are \ easy to prove. \n\nFor the remaining cases, note that for any word ", Cell[BoxData[ \(TraditionalForm\`w\ \[Element] \ \[CapitalSigma]\_B\%\(\(\ \)\(k\)\)\ \)]], " we have in \[ScriptCapitalA]: \n\t", Cell[BoxData[ \(TraditionalForm\`p\ \[CenterDot]\ w\ = \ \(B\^\(\(\ \)\(k\)\)\) p\ + \ \(\(\[Nu](w)\)\(\ \ \ \)\((mod\ \ m)\)\(\ \)\)\)]], ".\nThe behavior of state ", Cell[BoxData[ \(TraditionalForm\`p\)]], " in \[ScriptCapitalA] is therefore \n\t", Cell[BoxData[ \(TraditionalForm\`\(\({\ w\ \[Element] \ \ \[CapitalSigma]\_B\%\(\(\ \)\(*\)\) | \ \ B\^\(\(|\ \)\(w\)\(|\)\)\ p\ + \ \[Nu](w)\ = \ 0\ \ \((mod\ m)\)\ }\)\(\ \)\)\)]], ".\nDefine the witness for ", Cell[BoxData[ \(TraditionalForm\`p\)]], " to be the length-lex minimal word ", Cell[BoxData[ \(TraditionalForm\`w\)]], " in the behavior of ", Cell[BoxData[ \(TraditionalForm\`p\)]], ". " }], "Text"], Cell[TextData[{ StyleBox["Proposition", FontWeight->"Bold"], ": Two states are behaviorally equivalent if, and only if, they have the \ same witness. " }], "Text"], Cell[TextData[{ "Suppose ", Cell[BoxData[ \(TraditionalForm\`p\)]], " has a witness of length ", Cell[BoxData[ \(TraditionalForm\`k\)]], ". Then ", Cell[BoxData[ \(TraditionalForm\`p\)]], " is a solution of the linear equation " }], "Text"], Cell[TextData[{ "\t", Cell[BoxData[ \(TraditionalForm\`B\^\(\(\ \)\(k\)\)\ x\ + \ c\ = \ 0\ \ \((mod\ m)\)\)]] }], "NumberedEquation", CellTags->"B-eq"], Cell[TextData[{ "where the additive coefficient is bounded as ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] \ c\ \ < \ B\^\(\(\ \)\(k\)\)\)]], ". Thus, in order to determine equivalence of states, we have to \ characterize the solution sets of this equation. Let\n\n\t", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalS]\_\(k, c\)\)]], ": the set of all solutions to equation (1)\nand\n\t", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalS]\_\(k, c\)\%\[Prime]\)]], ": the set of all solutions to equation (1) which are not in ", Cell[BoxData[ \(TraditionalForm\`\(\[Union]\_\(\(\ \)\(l < k\)\)\ \[DoubleStruckCapitalS]\_\(l, c\)\)\)]], ".\n\nWe will refer to these solution sets as cumulative versus strict. \ Note that ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalS]\_\(k, c\) \[SubsetEqual] \ \ \[DoubleStruckCapitalS]\_\(k + 1, \ B\[VeryThinSpace]c\)\)]], ". Since the length of the behavioral witness matters, rather than just \ the associated numerical value ", Cell[BoxData[ \(TraditionalForm\`c = \[Nu](w)\)]], ", we have to consider strict rather than just cumulative solution sets. \ Our goal is to determine the number of solution sets and the levels at which \ they appear. As it turns out, the combinatorics are somewhat complicated so \ that the easy availability of sample data is crucial." }], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["Examples", "Subsubsection"], Cell[TextData[{ "Here are some examples of solution sets. We use a little wrapper function \ ", StyleBox["SolveModEq", "MR"], " that solves modular equations in a useful format. The strict version \ removes solutions from lower levels. For coprime modulus and base all \ solution sets have size one; all parameters ", Cell[BoxData[ \(TraditionalForm\`c\)]], " are feasible in the sense that equation (1) has a solution at some level \ ", Cell[BoxData[ \(TraditionalForm\`k\)]], "." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(m\ = \ 10; \ B\ = \ 3;\), "\[IndentingNewLine]", \(ColumnForm[\ Table[\ SolveModEq[\ m, \ B, \ k\ ], \ {k, 0, 2}\ ]\ ]\)}], "Input", CellLabel->"In[19]:="], Cell[BoxData[ InterpretationBox[GridBox[{ {\({{0}}\)}, {\({{0}, {3}, {6}}\)}, {\({{0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}}\)} }, GridBaseline->{Baseline, {1, 1}}, ColumnAlignments->{Left}], ColumnForm[ {{{0}}, {{0}, {3}, {6}}, {{0}, {1}, {2}, {3}, {4}, {5}, { 6}, {7}, {8}}}], Editable->False]], "Output", CellLabel->"Out[20]="] }, Open ]], Cell[TextData[{ "Here modulus and base are not coprime. The size of the solution sets \ reaches a plateau at level ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\ = 2\)]], "." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(m\ = \ 15; \ B\ = \ 3;\), "\[IndentingNewLine]", \(ColumnForm[\ Table[\ Sort@SolveModEq[\ m, \ B, \ k\ ], \ {k, 0, 3}\ ]\ ]\)}], "Input",\ CellLabel->"In[21]:="], Cell[BoxData[ InterpretationBox[GridBox[{ {\({{0}}\)}, {\({{0, 5, 10}}\)}, {\({{0, 5, 10}, {1, 6, 11}, {3, 8, 13}}\)}, {\({{0, 5, 10}, {1, 6, 11}, {2, 7, 12}, {3, 8, 13}, {4, 9, 14}}\)} }, GridBaseline->{Baseline, {1, 1}}, ColumnAlignments->{Left}], ColumnForm[ {{{0}}, {{0, 5, 10}}, {{0, 5, 10}, {1, 6, 11}, {3, 8, 13}}, {{0, 5, 10}, {1, 6, 11}, {2, 7, 12}, {3, 8, 13}, {4, 9, 14}}}], Editable->False]], "Output", CellLabel->"Out[22]="] }, Open ]], Cell[TextData[{ "Note that the solution sets are of the form ", Cell[BoxData[ \(TraditionalForm\`a\_0 + \ i\ d\)]], " for ", Cell[BoxData[ \(TraditionalForm\`i\ = \ 0, 1, \ \[Ellipsis]\)]], " We refer to ", Cell[BoxData[ \(TraditionalForm\`d\)]], " as the stride of the solution set. In the example, ", Cell[BoxData[ \(TraditionalForm\`d = 5\)]], ". \nHere the the size of the solution sets increases till all of ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalZ]\_m\)]], " appears as a solution somewhere." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(m\ = \ 16; \ B\ = \ 6;\), "\[IndentingNewLine]", \(ColumnForm[\ Table[\ Sort@SolveModEq[\ m, \ B, \ k\ ], \ {k, 0, 4}\ ]]\)}], "Input", CellLabel->"In[23]:="], Cell[BoxData[ InterpretationBox[GridBox[{ {\({{0}}\)}, {\({{0, 8}, {2, 10}, {5, 13}}\)}, {\({{0, 4, 8, 12}, {1, 5, 9, 13}, {2, 6, 10, 14}, {3, 7, 11, 15}}\)}, {\({{0, 2, 4, 6, 8, 10, 12, 14}, {1, 3, 5, 7, 9, 11, 13, 15}}\)}, {\({{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}}\)} }, GridBaseline->{Baseline, {1, 1}}, ColumnAlignments->{Left}], ColumnForm[ {{{0}}, {{0, 8}, {2, 10}, {5, 13}}, {{0, 4, 8, 12}, {1, 5, 9, 13}, {2, 6, 10, 14}, {3, 7, 11, 15}}, {{0, 2, 4, 6, 8, 10, 12, 14}, {1, 3, 5, 7, 9, 11, 13, 15}}, {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}}}], Editable->False]], "Output", CellLabel->"Out[24]="] }, Open ]], Cell["\<\ Now the same examples with strict solutions. The coprime case is \ trivial, so we skip it. \ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(m\ = \ 15; \ B\ = \ 3;\), "\[IndentingNewLine]", \(ColumnForm[\ Table[\ Sort@ SolveModEq[\ m, \ B, \ k, \ Mode \[Rule] Strict, \ Full \[Rule] False\ ], \ {k, 0, 3}\ ]]\)}], "Input", CellLabel->"In[25]:="], Cell[BoxData[ InterpretationBox[GridBox[{ {\({{0}}\)}, {\({{5, 10}}\)}, {\({{1, 6, 11}, {3, 8, 13}}\)}, {\({{2, 7, 12}, {4, 9, 14}}\)} }, GridBaseline->{Baseline, {1, 1}}, ColumnAlignments->{Left}], ColumnForm[ {{{0}}, {{5, 10}}, {{1, 6, 11}, {3, 8, 13}}, {{2, 7, 12}, { 4, 9, 14}}}], Editable->False]], "Output", CellLabel->"Out[26]="] }, Open ]], Cell[TextData[{ "Note how the size of some of the strict solutions sets deviates from ", Cell[BoxData[ \(TraditionalForm\`gcd(B\^\(\(\ \)\(k\)\), m)\)]], "." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(m\ = \ 16; \ B\ = \ 6;\), "\[IndentingNewLine]", \(ColumnForm[\ Table[\ Sort@ SolveModEq[\ m, \ B, \ k, \ Mode \[Rule] Strict, \ Full \[Rule] False\ ], \ {k, 0, 2}\ ]]\)}], "Input", CellLabel->"In[27]:="], Cell[BoxData[ InterpretationBox[GridBox[{ {\({{0}}\)}, {\({{8}, {2, 10}, {5, 13}}\)}, {\({{1, 9}, {4, 12}, {6, 14}, {3, 7, 11, 15}}\)} }, GridBaseline->{Baseline, {1, 1}}, ColumnAlignments->{Left}], ColumnForm[ {{{0}}, {{8}, {2, 10}, {5, 13}}, {{1, 9}, {4, 12}, {6, 14}, {3, 7, 11, 15}}}], Editable->False]], "Output", CellLabel->"Out[28]="] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Counting Cumulative Solutions", "Subsubsection"], Cell[TextData[{ "Let us tacitly assume that parameter ", Cell[BoxData[ \(TraditionalForm\`c\)]], " is feasible, i.e., that ", Cell[BoxData[ \(TraditionalForm\`gcd(B\^\(\(\ \)\(k\)\), m)\ | \ c\)]], " in which case the cardinality of ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalS]\_\(k, c\)\)]], " is ", Cell[BoxData[ \(TraditionalForm\`gcd(B\^\(\(\ \)\(k\)\), m)\)]], "; the empty solution set will be dealt with separately. There are two \ natural parameters that are important for the description of all solution \ sets. First, the depth \[Kappa] of ", Cell[BoxData[ \(TraditionalForm\`m\)]], " and ", Cell[BoxData[ \(TraditionalForm\`B\)]], " is the least level ", Cell[BoxData[ \(TraditionalForm\`k\)]], " for which ", Cell[BoxData[ \(TraditionalForm\`\(\[Union]\_\(\(\ \)\(c\)\)\[DoubleStruckCapitalS]\_\ \(k, c\)\)\ = \ \[DoubleStruckCapitalZ]\_m\)]], ". Second, the saturation value \[Sigma] is the least ", Cell[BoxData[ \(TraditionalForm\`\(\(k\)\(\ \)\)\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`gcd(B\^\(\(\ \)\(k\)\), m)\ = \ gcd(B\^\(\(\ \)\(k + 1\)\), m)\)]], ". Note that \n\n\t", Cell[BoxData[ \(TraditionalForm\`\[Kappa]\ = \ \[LeftCeiling]\ \(log\_B\) m\ \[RightCeiling]\)]], ".\n\nLetting ", Cell[BoxData[ \(TraditionalForm\`\[Gamma](a, b)\ = \ a/\(gcd(a, b)\)\)]], ", at level ", Cell[BoxData[ \(TraditionalForm\`k\)]], " there are ", Cell[BoxData[ \(TraditionalForm\`\[Gamma](B\^\(\(\ \)\(k\)\), m)\)]], " solution sets of size ", Cell[BoxData[ \(TraditionalForm\`gcd(B\^\(\(\ \)\(k\)\), m)\)]], " each. Within each solution set the elements satisfy ", Cell[BoxData[ \(TraditionalForm\`x\ = \ y\ \ \((\ mod\ \ \(\[Gamma](m, B\^k)\)\ )\)\)]], ".\n\n", StyleBox["Lemma", FontWeight->"Bold"], ": Let ", Cell[BoxData[ \(TraditionalForm\`l\ = \ min(\[Kappa], \[Sigma] - 1)\)]], " and set ", Cell[BoxData[ \(TraditionalForm\`N\ = \ \[Sum]\_\(\(\ \)\(k = 0\)\)\%\(\(\ \ \)\(l\)\ \)\ \[Gamma](\ B\^\(\(\ \)\(k\)\), m)\ \ + \ \(\(\[Sum]\_\(\(\ \)\(k = l + 1\)\)\%\(\(\ \ \)\(\[Sigma]\)\)\)\(\ \ \)\(\[Gamma](m, B\^\(\(\ \)\(k\)\))\)\(\ \)\)\)]], ". \nIf ", Cell[BoxData[ \(TraditionalForm\`m\)]], " and ", Cell[BoxData[ \(TraditionalForm\`B\)]], " are coprime then the total number of distinct solutions sets is ", Cell[BoxData[ \(TraditionalForm\`N\)]], ", otherwise it is ", Cell[BoxData[ \(TraditionalForm\`N\ + 1\)]], ". \n\nWe skip the proof." }], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["Examples", "Subsubsection"], Cell[TextData[{ "We can get a short overview of the structure of the solution hierarchy \ with the command ", StyleBox["ProfilemB", "MR"], ". The command prints out the key parameters, the stride of the solution \ sets, the number of solution sets and the size of the solution sets. Here is \ a case where ", Cell[BoxData[ \(TraditionalForm\`\[Sigma] < \[Kappa]\)]], ". " }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(m\ = \ 15; \ B\ = \ 3;\), "\[IndentingNewLine]", \(ProfilemB[\ m, \ B\ \ ]\)}], "Input", CellLabel->"In[29]:="], Cell[BoxData[ InterpretationBox[\("m: "\[InvisibleSpace]15\[InvisibleSpace]" B: "\ \[InvisibleSpace]3\[InvisibleSpace]" \[Sigma]: "\[InvisibleSpace]1\ \[InvisibleSpace]" \[Kappa]: "\[InvisibleSpace]2\), SequenceForm[ "m: ", 15, " B: ", 3, " \[Sigma]: ", 1, " \[Kappa]: ", 2], Editable->False]], "Print", CellLabel->"From In[29]:="], Cell[BoxData[ TagBox[GridBox[{ {"\<\"\"\>", "\<\"stride\"\>", "\<\"# coeffs\"\>", "\<\"# \ sols\"\>"}, {"0", "15", "1", "1"}, {"1", "5", "1", "3"}, {"2", "5", "3", "3"}, {"3", "5", "9", "3"} }, RowSpacings->1, ColumnSpacings->3, RowAlignments->Baseline, ColumnAlignments->{Left}], Function[ BoxForm`e$, TableForm[ BoxForm`e$, TableHeadings -> {{0, 1, 2, 3}, {"stride", "# coeffs", "# sols"}}]]]], "Output", CellLabel->"Out[30]//TableForm="] }, Open ]], Cell["A sanity check.", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(ColumnForm[\ Table[\ SolveModEq[m, B, k], {k, 0, 3}\ ]]\)], "Input", CellLabel->"In[31]:="], Cell[BoxData[ InterpretationBox[GridBox[{ {\({{0}}\)}, {\({{0, 5, 10}}\)}, {\({{0, 5, 10}, {3, 8, 13}, {1, 6, 11}}\)}, {\({{0, 5, 10}, {1, 6, 11}, {2, 7, 12}, {3, 8, 13}, {4, 9, 14}}\)} }, GridBaseline->{Baseline, {1, 1}}, ColumnAlignments->{Left}], ColumnForm[ {{{0}}, {{0, 5, 10}}, {{0, 5, 10}, {3, 8, 13}, {1, 6, 11}}, {{0, 5, 10}, {1, 6, 11}, {2, 7, 12}, {3, 8, 13}, {4, 9, 14}}}], Editable->False]], "Output", CellLabel->"Out[31]="] }, Open ]], Cell[TextData[{ "And here is ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\ > \ \[Kappa]\)]], ". " }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(m\ = \ 16; \ B\ = \ 6;\), "\[IndentingNewLine]", \(ProfilemB[\ m, \ B\ \ ]\)}], "Input", CellLabel->"In[32]:="], Cell[BoxData[ InterpretationBox[\("m: "\[InvisibleSpace]16\[InvisibleSpace]" B: "\ \[InvisibleSpace]6\[InvisibleSpace]" \[Sigma]: "\[InvisibleSpace]4\ \[InvisibleSpace]" \[Kappa]: "\[InvisibleSpace]1\), SequenceForm[ "m: ", 16, " B: ", 6, " \[Sigma]: ", 4, " \[Kappa]: ", 1], Editable->False]], "Print", CellLabel->"From In[32]:="], Cell[BoxData[ TagBox[GridBox[{ {"\<\"\"\>", "\<\"stride\"\>", "\<\"# coeffs\"\>", "\<\"# \ sols\"\>"}, {"0", "16", "1", "1"}, {"1", "8", "3", "2"}, {"2", "4", "9", "4"} }, RowSpacings->1, ColumnSpacings->3, RowAlignments->Baseline, ColumnAlignments->{Left}], Function[ BoxForm`e$, TableForm[ BoxForm`e$, TableHeadings -> {{0, 1, 2}, {"stride", "# coeffs", "# sols"}}]]]], "Output", CellLabel->"Out[33]//TableForm="] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Counting Strict Solutions", "Subsubsection"], Cell[TextData[{ "Let \[Sigma] be the least ", Cell[BoxData[ \(TraditionalForm\`k\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`gcd(B\^\(\(\ \)\(k\)\), m)\ = \ gcd(B\^\(\(\ \)\(k + 1\)\), m)\)]], " and let ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\)]], ", the rank of ", Cell[BoxData[ \(TraditionalForm\`m\)]], " and ", Cell[BoxData[ \(TraditionalForm\`B\)]], ", be the maximum ", Cell[BoxData[ \(TraditionalForm\`k\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalS]\_\(k, c\) \[NotEqual] \ \ \[EmptySet]\)]], " for some ", Cell[BoxData[ \(TraditionalForm\`c\)]], ". It is easy to see that if ", Cell[BoxData[ \(TraditionalForm\`m\)]], " is a power of ", Cell[BoxData[ \(TraditionalForm\`B\)]], " we have ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ = \ \[Kappa]\)]], ", and ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ = \ \[Kappa]\ + \ 1\)]], " otherwise; hence it suffices to consider levels ", Cell[BoxData[ \(TraditionalForm\`k\ \[LessEqual] \ \[Rho]\)]], ". Up to level ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], " the solution sets grow exponentially in size, so ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalS]\_\(k, c\) \[NotEqual] \ \ \[EmptySet]\)]], " for all feasible coefficients and there are ", Cell[BoxData[ \(TraditionalForm\`\[Gamma](B\^\(\(\ \)\(k\)\), m)\)]], " solution sets at level ", Cell[BoxData[ \(TraditionalForm\`k\)]], ". \n\nHowever, for ", Cell[BoxData[ \(TraditionalForm\`k > \[Sigma]\)]], " we have to contend with potentially empty solution sets. Recall that ", Cell[BoxData[ \(TraditionalForm\`\[Kappa]\ = \ \[LeftFloor]\(log\_B\) m\[RightFloor]\)]], ". Whenever ", Cell[BoxData[ \(TraditionalForm\`k\ > \ \[Kappa]\)]], " then the number of feasible coefficients ", Cell[BoxData[ \(TraditionalForm\`c\)]], " at level ", Cell[BoxData[ \(TraditionalForm\`k\)]], " is ", Cell[BoxData[ \(TraditionalForm\`\[Gamma](m, B\^\(\(\ \)\(\[Kappa]\)\))\)]], " rather than ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\[Gamma](\ B\^\(\(\ \)\(\[Kappa]\)\), m)\)\)\)]], ".\n", "\n", StyleBox["Lemma", FontWeight->"Bold"], ": Let ", Cell[BoxData[ \(TraditionalForm\`l\ = \ min(\[Kappa], \[Sigma] - 1)\)]], " and set ", Cell[BoxData[ \(TraditionalForm\`N\ = \ \(\(\[Sum]\_\(\(\ \)\(k = 0\)\)\%\(\(\ \ \ \)\(l\)\)\ \[Gamma](\ B\^\(\(\ \)\(k\)\), m)\)\(\ \ \)\(+\)\(\ \ \)\(min(\ \[Gamma](m, B\^\(\(\ \)\(\[Kappa]\)\)) - \ \[Gamma](\ B\^\(\(\ \)\(\[Kappa]\)\), m)\ , \ \[Gamma](m, B\^\(\(\ \)\(\[Kappa] + 1\)\)))\)\(\ \)\)\)]], ". \n\nIf ", Cell[BoxData[ \(TraditionalForm\`\[Kappa]\ \[GreaterEqual] \ \[Sigma]\)]], " then the number of disjoint solutions sets is ", Cell[BoxData[ \(TraditionalForm\`N\)]], ", otherwise it is ", Cell[BoxData[ \(TraditionalForm\`N\ + \ \[Gamma](\ B\^\(\(\ \)\(\[Kappa]\)\), m)\)]], ". \n", "\n", StyleBox["Corollary", FontWeight->"Bold"], ": The size of the minimal DFA recognizing numbers in base ", Cell[BoxData[ \(TraditionalForm\`B\)]], " that are divisible by ", Cell[BoxData[ \(TraditionalForm\`m\)]], " is given by \n", Cell[BoxData[ \(TraditionalForm\`\[Mu](m, B)\ = \ N\)]], " or ", Cell[BoxData[ \(TraditionalForm\`\[Mu](m, B)\ = \ \(\(N\)\(\ \)\(+\)\(\ \)\(\[Gamma](\ B\^\(\(\ \)\(\[Kappa]\)\), m)\)\(\ \)\)\)]], " depending on whether ", Cell[BoxData[ \(TraditionalForm\`\[Kappa]\ \[GreaterEqual] \ \[Sigma]\)]], ". \n", "\n", StyleBox["Corollary", FontWeight->"Bold"], ": The length of the longest witness for any state in \[ScriptCapitalA] \ is ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\)]], ". \n", "\n", "B. Alexeev has found a way to avoid following the hierarchy of solution \ sets all the way to the end, at least in some cases. Let \[Alpha] be the \ least ", Cell[BoxData[ \(TraditionalForm\`k\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`\[Gamma](m, B\^\(\(\ \)\(k\)\))\ - \ \[Gamma](m, B\^\(\(\ \)\(k + 1\)\))\ < \ \[Gamma](B\^\(\(\ \)\(k\)\), m)\)]], ". Note that ", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\ \[LessEqual] \ \[Sigma]\)]], " and it may well happen that ", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\ < \ \[Sigma]\)]], ". \n\n", StyleBox["Lemma", FontWeight->"Bold"], ": The number of disjoint solutions sets is ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\[Sum]\_\(\(\ \)\(k = 0\)\)\%\(\(\ \ \)\(\ \[Alpha] - 1\)\)\ \[Gamma](\ B\^\(\(\ \)\(k\)\), m)\ \ + \ \ \ \[Gamma](m, B\^\(\(\ \)\(\[Alpha]\)\))\)\)\)]], ". \n\nFor a proof see [A]." }], "Text"] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Reverse Base B", "Section"], Cell[CellGroupData[{ Cell["Brute Force", "Subsection"], Cell[TextData[{ "For reverse base ", Cell[BoxData[ FormBox[ RowBox[{"B", Cell[""]}], TraditionalForm]]], " notation the construction of the minimal DFA ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalB]\ = \ \[ScriptCapitalB]\_\(m, \ B\)\)]], " that accepts all strings ", Cell[BoxData[ \(TraditionalForm\`w\ \[Element] \ \[CapitalSigma]\_B\%\(\(\ \)\(*\)\)\ \)]], " that denote numbers divisible by ", Cell[BoxData[ \(TraditionalForm\`m\)]], " is somewhat more complicated. One possible choice of a canonical, though \ not necessarily minimal, DFA is to use as state set the Cartesian product ", Cell[BoxData[ \(TraditionalForm\`\((m)\)\ \[Cross]\ P\)]], " where ", Cell[BoxData[ \(TraditionalForm\`P\)]], " is the the multiplicative submonoid of ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalZ]\_m\)]], " generated by ", Cell[BoxData[ \(TraditionalForm\`B\)]], ". The right action is given by\n\n\t", Cell[BoxData[ \(TraditionalForm\`\((p, q)\)\ \[CenterDot]\ a\ = \ \((\ q\ p\ + \ a, \ B\ q\ )\)\ \ \ mod\ m\)]], ",\n\t\nthe initial state is ", Cell[BoxData[ \(TraditionalForm\`\((0, 1)\)\)]], " and the final states are of the form ", Cell[BoxData[ \(TraditionalForm\`\((0, _)\)\)]], ". Thus, the first component maintains the numerical value of the input \ string, modulo ", Cell[BoxData[ \(TraditionalForm\`m\)]], ", and the second provides the appropriate multiplier for the next digit." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(m\ = \ 10; B\ = \ 5;\), "\[IndentingNewLine]", \(M\ = \ DivisibilityDFA[m, B, Full \[Rule] True, Direction \[Rule] Backward]\)}], "Input", CellLabel->"In[34]:="], Cell[BoxData[ TagBox[ RowBox[{"DFA", "[", RowBox[{"20", ",", \(-5\), ",", TagBox[\({{2, 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, 14, 14, 16, 16, 18, 18, 20, 20}, \[LeftSkeleton]3\[RightSkeleton], {10, 2, 12, 4, 14, 6, 16, 8, 18, 10, 20, 12, 2, 14, 4, 16, 6, 18, 8, 20}}\), (Short[ #, 4]&)], ",", TagBox[\({1}\), (Short[ #, 4]&)], ",", TagBox[\({1, 2}\), (Short[ #, 4]&)]}], "]"}], HoldForm]], "Output", CellLabel->"Out[35]="] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(\(LanguageFA[M, 4]\ \ // \ WordReverse\)\ // \ WordToNumber[B]\)], "Input", CellLabel->"In[36]:="], Cell[BoxData[ \({0, 250, 500, 150, 400, 50, 300, 550, 200, 450, 100, 350, 600, 130, 380, 30, 280, 530, 180, 430, 80, 330, 580, 230, 480, 10, 260, 510, 160, 410, 60, 310, 560, 210, 460, 110, 360, 610, 140, 390, 40, 290, 540, 190, 440, 90, 340, 590, 240, 490, 20, 270, 520, 170, 420, 70, 320, 570, 220, 470, 120, 370, 620}\)], "Output", CellLabel->"Out[36]="] }, Open ]], Cell[TextData[{ "Note that the size of this automaton is a multiple of ", Cell[BoxData[ \(TraditionalForm\`m\)]], " and may be close to ", Cell[BoxData[ \(TraditionalForm\`m\^2\)]], ". When ", Cell[BoxData[ \(TraditionalForm\`m\)]], " is prime and ", Cell[BoxData[ \(TraditionalForm\`B\)]], " is a generator of the multiplicative subgroup ", Cell[BoxData[ \(TraditionalForm\`\[DoubleStruckCapitalZ]\_m\%\(\(\ \)\(*\)\)\)]], " the machine will have ", Cell[BoxData[ \(TraditionalForm\`m(m - 1)\)]], " states." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(M\ = \ DivisibilityDFA[11, 2, Full \[Rule] True, Direction \[Rule] Backward];\)\), "\[IndentingNewLine]", \(M\ \ // \ Size\)}], "Input", CellLabel->"In[37]:="], Cell[BoxData[ \(110\)], "Output", CellLabel->"Out[38]="] }, Open ]], Cell["\<\ However, the minimal DFA here is much smaller.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(\(M\ // \ MinimizeFA\)\ // \ Size\)], "Input", CellLabel->"In[39]:="], Cell[BoxData[ \(11\)], "Output", CellLabel->"Out[39]="] }, Open ]], Cell[TextData[{ "Some more computation suggests that indedd ", Cell[BoxData[ \(TraditionalForm\`\(\[Mu]\^R\)(m, B)\)]], " is bounded by ", Cell[BoxData[ \(TraditionalForm\`m + 1\)]], "." }], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["The Canonical Nondeterministic Automaton", "Subsection"], Cell[TextData[{ "We write ", Cell[BoxData[ \(TraditionalForm\`\(\[Mu]\^R\)(m, B)\)]], " for the size of the minimal DFA that recognizes numbers divisible by ", Cell[BoxData[ \(TraditionalForm\`m\)]], " in reverse base ", Cell[BoxData[ \(TraditionalForm\`B\)]], " notation. Since the deterministic machine from the last section appears \ to be overly large, it is tempting to consider a nondeterministic one in an \ effort to determine ", Cell[BoxData[ \(TraditionalForm\`\(\[Mu]\^R\)(m, B)\)]], ": the reversal of the canonical DFA ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalA]\ = \ \[ScriptCapitalA]\_\(m, \ B\)\)]], " for standard base ", Cell[BoxData[ \(TraditionalForm\`B\)]], ". This machine has size ", Cell[BoxData[ \(TraditionalForm\`m\)]], " and the transitions again are determined by linear equations modulo ", Cell[BoxData[ \(TraditionalForm\`m\)]], ". Recall that in ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalA]\)]], " the transitions given by ", Cell[BoxData[ \(TraditionalForm\`p\[CenterDot]\ a\ = \ B\ p\ + \ a\ \ \((mod\ m)\)\)]], ". Hence we have in ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalA]\^R\)]], ":" }], "Text"], Cell[TextData[{ "\t", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(q\ \[Element] \ \ \(\[Delta](p, w\^R)\)\ \ \ \[DoubleLongLeftRightArrow]\ \ \ q\ \ \ solves\ \ \ \ \ \(B\^\(\(\ \)\(\(|\)\(w\)\(|\)\)\)\) x\ + \ \[Nu](w)\ - p\ \ \ = \ 0\ \ \((mod\ m)\)\)\)\)]] }], "NumberedEquation"], Cell[TextData[{ "Thus, the reachable states in the full power automaton of ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalA]\^R\)]], " are going to be the solution sets of ", Cell[BoxData[ \(TraditionalForm\`\(B\^\(\(\ \)\(k\)\)\) x\ + \ c\ \ \ \ \((mod\ m)\)\)]], " where ", Cell[BoxData[ \(TraditionalForm\`c\ < \ B\^\(\(\ \)\(k\)\)\)]], ". Note that this time we are dealing with cumulative solutions, not the \ strict hierarchy from the first section." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(m\ = \ 15; \ B\ = \ 3;\), "\[IndentingNewLine]", \(\(M\ = \ ReverseFA@ DivisibilityDFA[m, B, Full \[Rule] True];\)\), "\[IndentingNewLine]", \(MM\ = \ ToDFA[\ M, \ Normalize \[Rule] 2\ ]\)}], "Input", CellLabel->"In[40]:="], Cell[BoxData[ TagBox[ RowBox[{"DFA", "[", RowBox[{"7", ",", \(-3\), ",", TagBox[\({{2, 2, 3, 5, 7, 4, 6}, {3, 4, 3, 6, 2, 5, 7}, {3, 5, 3, 7, 4, 6, 2}}\), (Short[ #, 4]&)], ",", TagBox["1", (Short[ #, 4]&)], ",", TagBox[\({1, 2}\), (Short[ #, 4]&)]}], "]"}], HoldForm]], "Output", CellLabel->"Out[42]="] }, Open ]], Cell[TextData[{ "The command ", StyleBox["DivisibilityDFA", "MR"], " with option ", StyleBox["Full->True", "MR"], " preserves the structure of the state set: " }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(States[MM]\)], "Input", CellLabel->"In[43]:="], Cell[BoxData[ \({{0}, {0, 5, 10}, {}, {3, 8, 13}, {1, 6, 11}, {4, 9, 14}, {2, 7, 12}}\)], "Output", CellLabel->"Out[43]="] }, Open ]], Cell[TextData[{ "which state set is none other than the solution sets for equation (1). \ Since function ", StyleBox["SolveModEq[m,B,k]", "MR"], " disregards the empty set as a possible solution set we only get 6 states \ out of 7 in the next computation." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Union@\(FlattenOne@Table[\ SolveModEq[m, B, k], {k, 0, 3}]\)\)], "Input",\ CellLabel->"In[44]:="], Cell[BoxData[ \({{0}, {0, 5, 10}, {1, 6, 11}, {2, 7, 12}, {3, 8, 13}, {4, 9, 14}}\)], "Output", CellLabel->"Out[44]="] }, Open ]], Cell[TextData[{ "When ", Cell[BoxData[ \(TraditionalForm\`m\)]], " and ", Cell[BoxData[ \(TraditionalForm\`B\)]], " are coprime there is no sink since the equation has a solution for all \ choices of the coefficients. " }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(\(\(DivisibilityDFA[11, 6, Full \[Rule] True]\ // \ ReverseFA\)\ // \ ToDFA\)\ // \ TrapStatesFA\)], "Input", CellLabel->"In[45]:="], Cell[BoxData[ \({}\)], "Output", CellLabel->"Out[45]="] }, Open ]], Cell["\<\ Otherwise there are one or two trap states, in the latter case only \ one of the two is final.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(\(\(DivisibilityDFA[6, 4, Full \[Rule] True]\ // \ ReverseFA\)\ // \ ToDFA\)\ // \ TrapStatesFA\)], "Input", CellLabel->"In[46]:="], Cell[BoxData[ \({3}\)], "Output", CellLabel->"Out[46]="] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(\(\(DivisibilityDFA[8, 6, Full \[Rule] True]\ // \ ReverseFA\)\ // \ ToDFA\)\ // \ TrapStatesFA\)], "Input", CellLabel->"In[47]:="], Cell[BoxData[ \({3, 8}\)], "Output", CellLabel->"Out[47]="] }, Open ]], Cell["\<\ Since we need not be concerned with the strict hierarchy it is \ actually a little easier to count the number of all solution sets in this \ case.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(m\ = \ 45; B = 3;\), "\[IndentingNewLine]", \(ProfilemB[m, B]\)}], "Input", CellLabel->"In[48]:="], Cell[BoxData[ InterpretationBox[\("m: "\[InvisibleSpace]45\[InvisibleSpace]" B: "\ \[InvisibleSpace]3\[InvisibleSpace]" \[Sigma]: "\[InvisibleSpace]2\ \[InvisibleSpace]" \[Kappa]: "\[InvisibleSpace]3\), SequenceForm[ "m: ", 45, " B: ", 3, " \[Sigma]: ", 2, " \[Kappa]: ", 3], Editable->False]], "Print", CellLabel->"From In[48]:="], Cell[BoxData[ TagBox[GridBox[{ {"\<\"\"\>", "\<\"stride\"\>", "\<\"# coeffs\"\>", "\<\"# \ sols\"\>"}, {"0", "45", "1", "1"}, {"1", "15", "1", "3"}, {"2", "5", "1", "9"}, {"3", "5", "3", "9"}, {"4", "5", "9", "9"} }, RowSpacings->1, ColumnSpacings->3, RowAlignments->Baseline, ColumnAlignments->{Left}], Function[ BoxForm`e$, TableForm[ BoxForm`e$, TableHeadings -> {{0, 1, 2, 3, 4}, {"stride", "# coeffs", "# sols"}}]]]], "Output", CellLabel->"Out[49]//TableForm="] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(ColumnForm[\ SolveModEq[\ m, \ B, \ Range[0, 4]\ ]\ \ ]\)], "Input", CellLabel->"In[50]:="], Cell[BoxData[ InterpretationBox[GridBox[{ {\({{0}}\)}, {\({{0, 15, 30}}\)}, {\({{0, 5, 10, 15, 20, 25, 30, 35, 40}}\)}, {\({{0, 5, 10, 15, 20, 25, 30, 35, 40}}\)}, {\({{0, 5, 10, 15, 20, 25, 30, 35, 40}}\)} }, GridBaseline->{Baseline, {1, 1}}, ColumnAlignments->{Left}], ColumnForm[ {{{0}}, {{0, 15, 30}}, {{0, 5, 10, 15, 20, 25, 30, 35, 40}}, {{0, 5, 10, 15, 20, 25, 30, 35, 40}}, {{0, 5, 10, 15, 20, 25, 30, 35, 40}}}], Editable->False]], "Output", CellLabel->"Out[50]="] }, Open ]], Cell[TextData[{ "As before let \[Sigma] be the least ", Cell[BoxData[ \(TraditionalForm\`k\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`gcd(B\^\(\(\ \)\(k\)\), m)\ = \ gcd(B\^\(\(\ \)\(k + 1\)\), m)\)]], " and let ", Cell[BoxData[ \(TraditionalForm\`\[Kappa]\ = \ \[LeftFloor]\(log\_B\) m\[RightFloor]\)]], ". Also let ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\)]], " be the maximum ", Cell[BoxData[ \(TraditionalForm\`k\)]], " such that some new solution appears at level ", Cell[BoxData[ \(TraditionalForm\`k\)]], ". Thus if ", Cell[BoxData[ \(TraditionalForm\`m\)]], " is a power of ", Cell[BoxData[ \(TraditionalForm\`B\)]], " we have ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ = \ \[Kappa]\)]], ", and ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\ = \ \[Kappa]\ + \ 1\)]], " otherwise." }], "Text"], Cell[TextData[{ StyleBox["Lemma", FontWeight->"Bold"], ": Let ", Cell[BoxData[ \(TraditionalForm\`l\ = \ min(\[Kappa], \[Sigma] - 1)\)]], " and set ", Cell[BoxData[ \(TraditionalForm\`N\ = \ \[Sum]\_\(\(\ \)\(k = 0\)\)\%\(\(\ \ \)\(l\)\ \)\ \[Gamma](\ B\^\(\(\ \)\(k\)\), m)\ \ + \ \(\(\[Sum]\_\(\(\ \)\(k = l + 1\)\)\%\(\(\ \ \)\(\[Sigma]\)\)\)\(\ \ \)\(\[Gamma](m, B\^\(\(\ \)\(k\)\))\)\(\ \)\)\)]], ". \n\nIf ", Cell[BoxData[ \(TraditionalForm\`m\)]], " and ", Cell[BoxData[ \(TraditionalForm\`B\)]], " are coprime then the number of solutions sets is ", Cell[BoxData[ \(TraditionalForm\`N\)]], ", otherwise it is ", Cell[BoxData[ \(TraditionalForm\`N\ + 1\)]], ". " }], "Text"], Cell[TextData[{ StyleBox["Corollary", FontWeight->"Bold"], ": The size of the power automaton obtained from ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalA]\_\(m, B\)\%R\)]], " is ", Cell[BoxData[ \(TraditionalForm\`N\)]], " or ", Cell[BoxData[ \(TraditionalForm\`N + 1\)]], " depending on whether ", Cell[BoxData[ \(TraditionalForm\`m\)]], " and ", Cell[BoxData[ \(TraditionalForm\`B\)]], " are coprime." }], "Text"], Cell[TextData[{ StyleBox["Corollary", FontWeight->"Bold"], ": The length of the longest witness for any state in ", Cell[BoxData[ \(TraditionalForm\`pow(\[ScriptCapitalA]\_\(m, B\)\%R)\)]], " is ", Cell[BoxData[ \(TraditionalForm\`\[Rho]\)]], ". " }], "Text"] }, Open ]], Cell[CellGroupData[{ Cell["Minimal Recognizers", "Subsection"], Cell[TextData[{ "We claim that the power automaton obtained from ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalA]\^R\)]], " is always reduced and thus already minimal. To see this, call a state ", Cell[BoxData[ \(TraditionalForm\`p\)]], " in a machine ", Cell[BoxData[ \(TraditionalForm\`M\)]], " rich if its behavior contains at least one word not in the behavior of ", Cell[BoxData[ \(TraditionalForm\`Q - {p}\)]], ". Clearly, any state ", Cell[BoxData[ \(TraditionalForm\`P\ \[SubsetEqual] \ Q\)]], " in the power automaton of ", Cell[BoxData[ \(TraditionalForm\`M\)]], " that contains a rich state cannot be equivalent to any other state. \ Hence it suffices to prove the following." }], "Text"], Cell[TextData[{ StyleBox["Lemma", FontWeight->"Bold"], ": All states in ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalA]\^R\)]], " are rich.\n\nProof: \nLet ", Cell[BoxData[ \(TraditionalForm\`p\)]], " be any state in ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalA]\^R\)]], " and choose a word ", Cell[BoxData[ \(TraditionalForm\`w\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`\[Nu](w)\ \ = \ p\ \ \((mod\ m)\)\)]], ", whence ", Cell[BoxData[ \(TraditionalForm\`w\^R\)]], " is in the behavior of ", Cell[BoxData[ \(TraditionalForm\`p\)]], " in ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalA]\^R\)]], ". Suppose ", Cell[BoxData[ \(TraditionalForm\`w\^R\)]], " lies also in the behavior of state ", Cell[BoxData[ \(TraditionalForm\`q\)]], ". Then ", Cell[BoxData[ \(TraditionalForm\`0\)]], " solves ", Cell[BoxData[ \(TraditionalForm\`\(B\^\(\(\ \)\(\(|\)\(w\)\(|\)\)\)\) x\ + \ \[Nu]( w)\ - q\ \ \ = \ 0\ \ \((mod\ m)\)\)]], " and ", Cell[BoxData[ \(TraditionalForm\`p = q\)]], ", as required. " }], "Text"], Cell[TextData[{ StyleBox["Corollary", FontWeight->"Bold"], ": The power automaton obtained from ", Cell[BoxData[ \(TraditionalForm\`\[ScriptCapitalA]\_\(m, B\)\%R\)]], " is minimal." }], "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Fibonacci Base", "Section"], Cell[CellGroupData[{ Cell["Fibonacci Base", "Subsection"], Cell[TextData[{ "Any strictly increasing sequence ", Cell[BoxData[ \(TraditionalForm\`\((U\_n)\)\)]], " of positive integers where ", Cell[BoxData[ \(TraditionalForm\`U\_0 = 1\)]], " gives rise to a numeration system. In order to keep the number of \ distinct digits finite one usually imposes the condition that ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(sup\ U\_\(n + 1\)/U\_n\)\)\)]], " be bounded. The digits in this case can be chosen to be ", Cell[BoxData[ \(TraditionalForm\`\[CapitalSigma]\_D = {0, 1, \[Ellipsis], D - 1}\)]], " where ", Cell[BoxData[ \(TraditionalForm\`D - 1\)]], " is the largest integer less than the supremum. In general, numbers will \ admit multiple representations in such a numeration system and one can define \ the normalized representation to be the one obtained by the natural greedy \ algorithm.\n\nA classical example is given by the Fibonacci sequence \ (starting at the third term): ", Cell[BoxData[ \(TraditionalForm\`\((U\_n)\)\ = \ 1, 2, 3, 5, 8, 13, \ \[Ellipsis]\)]], " In this case ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(lim\ U\_\(n + 1\)/U\_n\)\)\)]], " is the Golden Ratio, ", Cell[BoxData[ \(TraditionalForm\`\(\(\ \)\(\[Phi]\ = \ \(1 + \@5\)\/2\)\)\)]], ". Hence there are only digits ", Cell[BoxData[ \(TraditionalForm\`{0, 1}\)]], " and one can compute the normalized representation as follows. We need a \ little auxiliary function that returns the largest Fibonacci number not \ greater than a given number. " }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(n\ = \ RandomInteger[10^4];\)\), "\[IndentingNewLine]", \(LargestFibonacci[n]\)}], "Input", CellLabel->"In[51]:="], Cell[BoxData[ \(17\)], "Output", CellLabel->"Out[52]="] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(Fibonacci[%]\ \[LessEqual] \ n\ < \ Fibonacci[% + 1]\)], "Input", CellLabel->"In[53]:="], Cell[BoxData[ \(True\)], "Output", CellLabel->"Out[53]="] }, Open ]], Cell["\<\ Then a standard greedy algorithm will produce the Fibonacci \ representation of a number. \ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(FibonacciDigitsRaw[1001]\), "\[IndentingNewLine]", \(FibonacciDigits[1001]\)}], "Input", CellLabel->"In[54]:="], Cell[BoxData[ \({16, 7, 2}\)], "Output", CellLabel->"Out[54]="], Cell[BoxData[ \({1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}\)], "Output", CellLabel->"Out[55]="] }, Open ]], Cell[TextData[{ "A famous open problem related to the Fibonacci sequence is to determine \ the period length of the sequence modulo ", Cell[BoxData[ \(TraditionalForm\`m\)]], ". These numbers are sometimes referred to as Pisano numbers, see Sloane's \ database of sequences at ", ButtonBox["A001175", ButtonData:>{ URL[ "http://www.research.att.com/projects/OEIS?Anum=A001175"], None}, ButtonStyle->"Hyperlink"], ". ", "\n", "We write ", Cell[BoxData[ \(TraditionalForm\`per(m)\)]], " for the length of the sequence modulo ", Cell[BoxData[ \(TraditionalForm\`m\)]], ". It is easy to see that the function is multiplicative. It seems that \ for primes ", Cell[BoxData[ \(TraditionalForm\`p\)]], " we have ", Cell[BoxData[ \(TraditionalForm\`per(p\^e)\ = \ \(p\^\(e - 1\)\) \(per(p)\)\)]], " but no proof is known. Moreover, the behavior of ", Cell[BoxData[ \(TraditionalForm\`per\)]], " on primes is not well-understood either. It is known that ", Cell[BoxData[ \(TraditionalForm\`per(p)\ = \ p - 1\)]], " exactly when there is a primitive root \[Alpha] modulo ", Cell[BoxData[ \(TraditionalForm\`p\)]], " such that ", Cell[BoxData[ \(TraditionalForm\`\[Alpha]\^2 = \ \[Alpha]\ + \ 1\ \ \((mod\ p)\)\)]], ". Also, ", Cell[BoxData[ \(TraditionalForm\`per(m) = m\)]], " if and only if ", Cell[BoxData[ \(TraditionalForm\`m\ = \ 24\ \[CenterDot]\ 5\^\(\(\ \)\(e\)\)\)]], "." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Pisano[{11, 19, 31, 41}]\)], "Input", CellLabel->"In[56]:="], Cell[BoxData[ \({10, 18, 30, 40}\)], "Output", CellLabel->"Out[56]="] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Brute Force", "Subsection"], Cell[TextData[{ "The obvious brute-force construction of a finite state machine for numbers \ in Fibonacci base (not necessarily normalized) that are divisible by ", Cell[BoxData[ \(TraditionalForm\`m\)]], " is to use as state set the Cartesian product ", Cell[BoxData[ \(TraditionalForm\`Q\ = \ {0, 1, \[Ellipsis], m - 1}\ \[Cross]\ {0, 1, \[Ellipsis], n - 1}\)]], " where ", Cell[BoxData[ \(TraditionalForm\`n\ = \ per(m)\)]], " is the Pisano number of ", Cell[BoxData[ \(TraditionalForm\`m\)]], ". The right action on ", Cell[BoxData[ \(TraditionalForm\`Q\)]], " is given by \n\n\t\t", Cell[BoxData[ \(TraditionalForm\`\((p, q)\)\ \[CenterDot]\ 0\ = \ \((p, q - 1\ mod\ n)\)\)]], " and \n\t\t", Cell[BoxData[ \(TraditionalForm\`\((p, q)\)\ \[CenterDot]\ 1\ = \ \((\ r\ + F\_\(q + 1\)\ mod\ m, q - 1\ \ mod\ n\ )\)\)]], "\n\t\t\nwhere ", Cell[BoxData[ \(TraditionalForm\`F\_n\)]], " denotes the ", Cell[BoxData[ \(TraditionalForm\`n\)]], "th Fibonacci number. It is straightforward to construct this automaton, \ assuming for the time being that ", Cell[BoxData[ \(TraditionalForm\`\((0, 0)\)\)]], " is the initial and final state. The method employed below is based on \ the construction of a cyclic semi-module which is then interpreted as a DFA. \ ", StyleBox["Automata", "MR"], " contains a command ", ButtonBox["GenerateDFA", ButtonStyle->"AddOnsLink"], " that implements the necessary machinery." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(Clear[dot]\), "\n", \(\(m\ = \ 3;\)\), "\n", \(\(n\ = \ Pisano[m];\)\), "\n", \(\(P0\ = \ Mod[RotateRight[Reverse@\(Fibonacci@Range[0, n - 1]\), 2], m];\)\), "\[IndentingNewLine]", \(\(dot[{p_, q_}, "\<0\>"]\ := \ {\ p, Mod[q + 1, n]\ };\)\), "\n", \(\(dot[{p_, q_}, "\<1\>"]\ := \ {\ \ Mod[\ p\ + P0[\([q + 1]\)], m], Mod[q + 1, n]\ };\)\), "\n", \(\(q0\ = \ \ {0, 0};\)\), "\n", \(M\ = \ GenerateDFA[\ q0, dot, \(-2\), # === q0 &, \ Normalize \[Rule] 1\ ]\)}], "Input", CellLabel->"In[57]:="], Cell[BoxData[ TagBox[ RowBox[{"DFA", "[", RowBox[{"24", ",", \(-2\), ",", TagBox[\({{2, 4, 5, 6, 7, 9, 11, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20, 1, 22, 21, 3, 23, 24, 8}, {3, 4, 5, 7, 8, 10, 9, 11, 13, 14, 12, 15, 16, 17, 19, 20, 18, 21, 1, 22, 23, 2, 24, 6}}\), (Short[ #, 4]&)], ",", TagBox["1", (Short[ #, 4]&)], ",", TagBox[\({1}\), (Short[ #, 4]&)]}], "]"}], HoldForm]], "Output", CellLabel->"Out[64]="] }, Open ]], Cell[TextData[{ "At present, the automaton only accepts words of length a multiple of ", Cell[BoxData[ \(TraditionalForm\`8\ = \ per(3)\)]], ". " }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(LanguageFA[M, \(-40\), SizeOnly \[Rule] True]\)], "Input", CellLabel->"In[65]:="], Cell[BoxData[ \({1, 0, 0, 0, 0, 0, 0, 0, 88, 0, 0, 0, 0, 0, 0, 0, 21856, 0, 0, 0, 0, 0, 0, 0, 5592448, 0, 0, 0, 0, 0, 0, 0, 1431655936, 0, 0, 0, 0, 0, 0, 0, 366503876608}\)], "Output", CellLabel->"Out[65]="] }, Open ]], Cell["\<\ In order to get words of arbitrary length we need to add more \ initial states. \ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(PositionList[\ \ States[M], \ Cases[\ States[M], {0, _}]\ ];\)\), "\n", \(MM = \ SetInitialFA[\ M, \ %\ ]\)}], "Input", CellLabel->"In[66]:="], Cell[BoxData[ TagBox[ RowBox[{"FA", "[", RowBox[{"24", ",", \(-2\), ",", TagBox[\({{1, 1, 2}, {2, 1, 4}, {3, 1, 5}, {4, 1, 6}, {5, 1, 7}, {6, 1, 9}, {7, 1, 11}, {8, 1, 10}, {9, 1, 12}, \[LeftSkeleton]30\[RightSkeleton], {16, 2, 20}, {17, 2, 18}, {18, 2, 21}, {19, 2, 1}, {20, 2, 22}, {21, 2, 23}, {22, 2, 2}, {23, 2, 24}, {24, 2, 6}}\), (Short[ #, 4]&)], ",", TagBox[\({1, 2, 4, 6, 9, 12, 15, 18}\), (Short[ #, 4]&)], ",", TagBox[\({1}\), (Short[ #, 4]&)]}], "]"}], HoldForm]], "Output", CellLabel->"Out[67]="] }, Open ]], Cell["\<\ A small sanity check: the numerical values are all multiples of 3 \ -- and all such values seem to appear.\ \>", "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(FromFibonacciWord[LanguageFA[\ MM, \ \(-6\)\ ]]\)], "Input", CellLabel->"In[68]:="], Cell[BoxData[ \({{0}, {0}, {0, 3}, {0, 3, 3, 6}, {0, 3, 3, 6, 6, 9}, {0, 3, 3, 6, 6, 9, 9, 12, 15, 18}, {0, 3, 3, 6, 6, 9, 9, 12, 15, 18, 15, 18, 18, 21, 21, 24, 21, 24, 24, 27, 27, 30}}\)], "Output", CellLabel->"Out[68]="] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["A Canonical Automaton", "Subsection"], Cell[TextData[{ "The automaton ", StyleBox["MM", "MR"], " from the last section is nondeterministic because of its multiple initial \ states though all transitions are deterministic. The question arises what \ the size of the corresponding power automaton and minimal automaton might \ be." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(MM\ // \ ToDFA\)], "Input", CellLabel->"In[69]:="], Cell[BoxData[ TagBox[ RowBox[{"DFA", "[", RowBox[{"9", ",", \(-2\), ",", TagBox[\({{1, 3, 4, 6, 2, 8, 5, 9, 7}, {2, 4, 5, 7, 8, 1, 3, 6, 9}}\), (Short[ #, 4]&)], ",", TagBox["1", (Short[ #, 4]&)], ",", TagBox[\({1, 4, 7}\), (Short[ #, 4]&)]}], "]"}], HoldForm]], "Output", CellLabel->"Out[69]="] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(\(MM\ // \ MinimizeFA\)\ // \ Size\)], "Input", CellLabel->"In[70]:="], Cell[BoxData[ \(9\)], "Output", CellLabel->"Out[70]="] }, Open ]], Cell[TextData[{ "The power automaton is already minimal and much smaller than one might \ expect. To see why, note that ", StyleBox["MM", "MR"], " is a permutation automaton. Hence the size of all the states in the power \ automaton is ", Cell[BoxData[ \(TraditionalForm\`n\)]], ", the Pisano number of ", Cell[BoxData[ \(TraditionalForm\`m\)]], " and the number of initial states. In fact, all these state contain \ exactly one element ", Cell[BoxData[ \(TraditionalForm\`\((p, r)\)\)]], " for each ", Cell[BoxData[ \(TraditionalForm\`0\ \[LessEqual] p\ < \ n\)]], ". " }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(ToDFA[\ MM, \ Normalize \[Rule] 2] // \ States\)], "Input", CellLabel->"In[71]:="], Cell[BoxData[ \({{{0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6}, {0, 7}}, {{1, 1}, {0, 2}, {1, 3}, {2, 4}, {2, 5}, {0, 6}, {2, 7}, {1, 0}}, {{1, 1}, {1, 2}, {0, 3}, {1, 4}, {2, 5}, {2, 6}, {0, 7}, {2, 0}}, {{0, 0}, {1, 2}, {1, 3}, {0, 4}, {1, 5}, {2, 6}, {2, 7}, {2, 1}}, {{0, 1}, {1, 2}, {2, 3}, {2, 4}, {0, 5}, {2, 6}, {1, 7}, {1, 0}}, {{0, 1}, {1, 3}, {1, 4}, {0, 5}, {1, 6}, {2, 7}, {2, 0}, {2, 2}}, {{0, 0}, {1, 1}, {2, 3}, {0, 4}, {2, 5}, {1, 6}, {1, 7}, {2, 2}}, {{0, 2}, {2, 3}, {1, 4}, {1, 5}, {0, 6}, {1, 7}, {2, 0}, {2, 1}}, {{0, 3}, {2, 4}, {1, 5}, {1, 6}, {0, 7}, {1, 0}, {2, 1}, {2, 2}}}\)], "Output", CellLabel->"Out[71]="] }, Open ]], Cell[TextData[{ "But then we might as well use sequences of length ", Cell[BoxData[ \(TraditionalForm\`n\)]], " of remainders modulo ", Cell[BoxData[ \(TraditionalForm\`m\)]], " as states. The action on these sequences can be chosen to be \n\n\t", Cell[BoxData[ \(TraditionalForm\`P\ \[CenterDot]\ 0\ = \ rot(P)\)]], "\n\t", Cell[BoxData[ \(TraditionalForm\`P\[CenterDot]\ 1\ \ = \ rot(P)\ + \ F\ \ \((mod\ m)\)\)]], "\n\t\nwhere ", Cell[BoxData[ \(TraditionalForm\`F\ = \ \((F\_0, F\_1, \[Ellipsis], F\_\(n - 1\))\)\ \ mod\ m\)]], " is a period of the Fibonacci sequence modulo ", Cell[BoxData[ \(TraditionalForm\`m\)]], " and ", Cell[BoxData[ \(TraditionalForm\`rot\)]], " indicates a cyclic shift to the left. It is straightforward to implement \ this automaton, using again the command ", ButtonBox["GenerateDFA", ButtonStyle->"AddOnsLink"], " from ", StyleBox["Automata", "MR"], "." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(M\ = \ FibonacciDivDFA[\ 3\ ]\)], "Input", CellLabel->"In[72]:="], Cell[BoxData[ TagBox[ RowBox[{"DFA", "[", RowBox[{"9", ",", \(-2\), ",", TagBox[\({{1, 3, 4, 6, 2, 8, 5, 9, 7}, {2, 4, 5, 7, 8, 1, 3, 6, 9}}\), (Short[ #, 4]&)], ",", TagBox["1", (Short[ #, 4]&)], ",", TagBox[\({1, 4, 7}\), (Short[ #, 4]&)]}], "]"}], HoldForm]], "Output", CellLabel->"Out[72]="] }, Open ]], Cell[TextData[{ "While the states of these automata depend on the Pisano numbers, the size \ of the automata appears simply to be ", Cell[BoxData[ \(TraditionalForm\`m\^2\)]], "." }], "Text"], Cell[CellGroupData[{ Cell[BoxData[ \(Table[\ {k, Size@FibonacciDivDFA[k]}, \ {k, 2, 6}]\ // \ TableForm\)], "Input", CellLabel->"In[73]:="], Cell[BoxData[ TagBox[GridBox[{ {"2", "4"}, {"3", "9"}, {"4", "16"}, {"5", "25"}, {"6", "36"} }, RowSpacings->1, ColumnSpacings->3, RowAlignments->Baseline, ColumnAlignments->{Left}], Function[ BoxForm`e$, TableForm[ BoxForm`e$]]]], "Output", CellLabel->"Out[73]//TableForm="] }, Open ]], Cell[TextData[{ "It is easy to establish this conjecture. The states are all Fibonacci \ type sequences modulo ", Cell[BoxData[ \(TraditionalForm\`m\)]], " but with different initial conditions. All initial conditions occur since \ the standard sequence has the form ", Cell[BoxData[ \(TraditionalForm\`\((0, 1, \[Ellipsis], 1)\)\)]], ". ", "\n", "It follows that the minimal automaton can have size at most ", Cell[BoxData[ \(TraditionalForm\`m\^2\)]], " and to show that this bound is tight it suffices to prove that the \ canonical automaton is already reduced. To this end, write ", Cell[BoxData[ \(TraditionalForm\`2\)]], " for the input ", Cell[BoxData[ \(TraditionalForm\`\(0\^\(n - 1\)\) 1\)]], ", so that ", Cell[BoxData[ \(TraditionalForm\`P\ \[CenterDot]\ 2\ = \ P\ + \ F\ \ \((mod\ m)\)\)]], ". Letting ", Cell[BoxData[ \(TraditionalForm\`P\ = \ \((p\_0, p\_1, \[Ellipsis], p\_\(n - 1\))\)\)]], " we have ", Cell[BoxData[ \(TraditionalForm\`P\ \[CenterDot]\ 0\^\(\(\ \)\(i - 1\)\) 2\^\(\(\ \)\(j\)\)\ 0\^\(\(\ \)\(n - 1\)\)\)]], " is final iff ", Cell[BoxData[ \(TraditionalForm\`p\_i = \(-j\)\ \ \((mod\ m)\)\)]], ". Hence all states have distinct behavior and we are done." }], "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["References", "Section"], Cell["\<\ AS\tJ.-P. Allouche, J. Shallit, Automatic Sequences: Theory, \ Applications, Generalizations; Cambridge UP 2003. A\tB. Alexeev, Minimal DFAs for Testing Divisibility, to appear in JCSS. BH\tV. Bruy\[EGrave]re, G. Hansel, Recognizable Sets of Numbers in \ Nonstandard Bases, LNCS 911 1995, 167-197. BHMV\tV. Bruy\[EGrave]re, G. Hansel, C. Michaux. R. Villmaire, Logic and \ p-recognizable Sets of Integers, Bull. Belg. Math. Soc., 1994 (1) 191--238. S\tK. Sutner, Automata: a Hybrid System for Computational Automata Theory, \ Proceedings CIAA 2002, \tJ-M. Champarnaud, D. Maurel, eds., 2002, 217-222.\ \>", "Text"] }, Open ]] }, Open ]] }, FrontEndVersion->"5.2 for X", ScreenRectangle->{{0, 1920}, {0, 1200}}, WindowSize->{1159, 996}, WindowMargins->{{34, Automatic}, {Automatic, 25}}, PrintingPageRange->{Automatic, Automatic}, PageHeaders->{{ Inherited, Inherited, Cell[ "Klaus Sutner", "Header"]}, { Cell[ "Divisibility and State-Complexity", "Header"], Inherited, Inherited}}, PrintingOptions->{"PaperSize"->{612, 792}, "PaperOrientation"->"Portrait", "PostScriptOutputFile":>FrontEnd`FileName[{$RootDirectory, "home", "papegay", \ "ims06", "eproc", "articles"}, "Sutner.nb.ps", CharacterEncoding -> \ "iso8859-1"], "Magnification"->1}, ShowSelection->True, ShowCellLabel->False, Magnification->1, StyleDefinitions -> "IMS2006styles.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->{ "B-eq"->{ Cell[18758, 567, 175, 6, 32, "NumberedEquation", CellTags->"B-eq"]} } *) (*CellTagsIndex CellTagsIndex->{ {"B-eq", 71583, 2330} } *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[1776, 53, 51, 0, 78, "Title"], Cell[1830, 55, 30, 0, 22, "Author"], Cell[1863, 57, 119, 5, 79, "TextAboutAuthor"], Cell[CellGroupData[{ Cell[2007, 66, 89, 1, 42, "Subsubsection"], Cell[2099, 69, 403, 10, 44, "Text"], Cell[2505, 81, 382, 7, 131, "InputOnly"] }, Open ]], Cell[CellGroupData[{ Cell[2924, 93, 52, 0, 62, "Section"], Cell[CellGroupData[{ Cell[3001, 97, 34, 0, 54, "Subsection"], Cell[3038, 99, 2489, 62, 188, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[5564, 166, 54, 0, 54, "Subsection"], Cell[5621, 168, 2624, 77, 152, "Text"], Cell[CellGroupData[{ Cell[8270, 249, 166, 3, 56, "Input"], Cell[8439, 254, 360, 11, 41, "Output"] }, Open ]], Cell[8814, 268, 122, 3, 26, "Text"], Cell[CellGroupData[{ Cell[8961, 275, 73, 2, 40, "Input"], Cell[9037, 279, 197, 4, 41, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[9271, 288, 80, 2, 40, "Input"], Cell[9354, 292, 109, 2, 41, "Output"] }, Open ]], Cell[9478, 297, 223, 4, 26, "Text"], Cell[CellGroupData[{ Cell[9726, 305, 132, 3, 56, "Input"], Cell[9861, 310, 131, 3, 61, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[10029, 318, 86, 2, 40, "Input"], Cell[10118, 322, 513, 11, 43, "Output"] }, Open ]], Cell[10646, 336, 45, 0, 26, "Text"], Cell[CellGroupData[{ Cell[10716, 340, 169, 3, 56, "Input"], Cell[10888, 345, 664, 16, 57, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[11589, 366, 95, 2, 40, "Input"], Cell[11687, 370, 113, 2, 41, "Output"] }, Open ]], Cell[11815, 375, 360, 10, 26, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[12212, 390, 54, 0, 54, "Subsection"], Cell[CellGroupData[{ Cell[12291, 394, 60, 0, 42, "Subsubsection"], Cell[12354, 396, 2056, 43, 224, "Text"], Cell[CellGroupData[{ Cell[14435, 443, 299, 7, 56, "Input"], Cell[14737, 452, 1820, 37, 269, "Output"] }, Open ]], Cell[16572, 492, 1732, 53, 152, "Text"], Cell[18307, 547, 172, 5, 26, "Text"], Cell[18482, 554, 273, 11, 26, "Text"], Cell[18758, 567, 175, 6, 32, "NumberedEquation", CellTags->"B-eq"], Cell[18936, 575, 1430, 28, 171, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[20403, 608, 33, 0, 42, "Subsubsection"], Cell[20439, 610, 524, 14, 44, "Text"], Cell[CellGroupData[{ Cell[20988, 628, 192, 4, 56, "Input"], Cell[21183, 634, 414, 11, 77, "Output"] }, Open ]], Cell[21612, 648, 199, 6, 26, "Text"], Cell[CellGroupData[{ Cell[21836, 658, 199, 5, 56, "Input"], Cell[22038, 665, 530, 12, 95, "Output"] }, Open ]], Cell[22583, 680, 584, 17, 44, "Text"], Cell[CellGroupData[{ Cell[23192, 701, 195, 4, 56, "Input"], Cell[23390, 707, 773, 16, 113, "Output"] }, Open ]], Cell[24178, 726, 116, 3, 26, "Text"], Cell[CellGroupData[{ Cell[24319, 733, 264, 6, 56, "Input"], Cell[24586, 741, 428, 12, 95, "Output"] }, Open ]], Cell[25029, 756, 181, 5, 26, "Text"], Cell[CellGroupData[{ Cell[25235, 765, 264, 6, 56, "Input"], Cell[25502, 773, 424, 11, 77, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[25975, 790, 54, 0, 42, "Subsubsection"], Cell[26032, 792, 2740, 81, 230, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[28809, 878, 33, 0, 42, "Subsubsection"], Cell[28845, 880, 401, 10, 44, "Text"], Cell[CellGroupData[{ Cell[29271, 894, 141, 3, 56, "Input"], Cell[29415, 899, 360, 7, 28, "Print"], Cell[29778, 908, 573, 17, 125, "Output"] }, Open ]], Cell[30366, 928, 31, 0, 26, "Text"], Cell[CellGroupData[{ Cell[30422, 932, 113, 2, 40, "Input"], Cell[30538, 936, 530, 12, 95, "Output"] }, Open ]], Cell[31083, 951, 122, 5, 26, "Text"], Cell[CellGroupData[{ Cell[31230, 960, 141, 3, 56, "Input"], Cell[31374, 965, 360, 7, 28, "Print"], Cell[31737, 974, 538, 16, 107, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[32324, 996, 50, 0, 42, "Subsubsection"], Cell[32377, 998, 5082, 159, 414, "Text"] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[37520, 1164, 33, 0, 62, "Section"], Cell[CellGroupData[{ Cell[37578, 1168, 33, 0, 54, "Subsection"], Cell[37614, 1170, 1569, 44, 134, "Text"], Cell[CellGroupData[{ Cell[39208, 1218, 208, 5, 56, "Input"], Cell[39419, 1225, 579, 15, 57, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[40035, 1245, 129, 3, 40, "Input"], Cell[40167, 1250, 391, 6, 57, "Output"] }, Open ]], Cell[40573, 1259, 583, 20, 26, "Text"], Cell[CellGroupData[{ Cell[41181, 1283, 211, 5, 56, "Input"], Cell[41395, 1290, 62, 2, 41, "Output"] }, Open ]], Cell[41472, 1295, 70, 2, 26, "Text"], Cell[CellGroupData[{ Cell[41567, 1301, 93, 2, 40, "Input"], Cell[41663, 1305, 61, 2, 41, "Output"] }, Open ]], Cell[41739, 1310, 222, 8, 26, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[41998, 1323, 62, 0, 54, "Subsection"], Cell[42063, 1325, 1298, 39, 62, "Text"], Cell[43364, 1366, 324, 7, 31, "NumberedEquation"], Cell[43691, 1375, 519, 13, 44, "Text"], Cell[CellGroupData[{ Cell[44235, 1392, 292, 7, 72, "Input"], Cell[44530, 1401, 427, 13, 41, "Output"] }, Open ]], Cell[44972, 1417, 181, 6, 26, "Text"], Cell[CellGroupData[{ Cell[45178, 1427, 68, 2, 40, "Input"], Cell[45249, 1431, 137, 3, 41, "Output"] }, Open ]], Cell[45401, 1437, 275, 6, 44, "Text"], Cell[CellGroupData[{ Cell[45701, 1447, 120, 3, 40, "Input"], Cell[45824, 1452, 133, 3, 41, "Output"] }, Open ]], Cell[45972, 1458, 253, 9, 26, "Text"], Cell[CellGroupData[{ Cell[46250, 1471, 166, 3, 40, "Input"], Cell[46419, 1476, 61, 2, 41, "Output"] }, Open ]], Cell[46495, 1481, 118, 3, 26, "Text"], Cell[CellGroupData[{ Cell[46638, 1488, 165, 3, 40, "Input"], Cell[46806, 1493, 62, 2, 41, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[46905, 1500, 165, 3, 40, "Input"], Cell[47073, 1505, 65, 2, 41, "Output"] }, Open ]], Cell[47153, 1510, 170, 4, 26, "Text"], Cell[CellGroupData[{ Cell[47348, 1518, 127, 3, 56, "Input"], Cell[47478, 1523, 360, 7, 28, "Print"], Cell[47841, 1532, 609, 18, 143, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[48487, 1555, 113, 2, 40, "Input"], Cell[48603, 1559, 585, 14, 113, "Output"] }, Open ]], Cell[49203, 1576, 949, 34, 45, "Text"], Cell[50155, 1612, 815, 26, 67, "Text"], Cell[50973, 1640, 484, 19, 26, "Text"], Cell[51460, 1661, 290, 10, 26, "Text"] }, Open ]], Cell[CellGroupData[{ Cell[51787, 1676, 41, 0, 54, "Subsection"], Cell[51831, 1678, 771, 21, 44, "Text"], Cell[52605, 1701, 1193, 44, 98, "Text"], Cell[53801, 1747, 214, 7, 26, "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[54064, 1760, 33, 0, 62, "Section"], Cell[CellGroupData[{ Cell[54122, 1764, 36, 0, 54, "Subsection"], Cell[54161, 1766, 1596, 37, 127, "Text"], Cell[CellGroupData[{ Cell[55782, 1807, 145, 3, 56, "Input"], Cell[55930, 1812, 61, 2, 41, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[56028, 1819, 112, 2, 40, "Input"], Cell[56143, 1823, 63, 2, 41, "Output"] }, Open ]], Cell[56221, 1828, 114, 3, 26, "Text"], Cell[CellGroupData[{ Cell[56360, 1835, 139, 3, 56, "Input"], Cell[56502, 1840, 69, 2, 41, "Output"], Cell[56574, 1844, 104, 2, 41, "Output"] }, Open ]], Cell[56693, 1849, 1543, 46, 98, "Text"], Cell[CellGroupData[{ Cell[58261, 1899, 82, 2, 40, "Input"], Cell[58346, 1903, 75, 2, 41, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[58470, 1911, 33, 0, 54, "Subsection"], Cell[58506, 1913, 1580, 44, 152, "Text"], Cell[CellGroupData[{ Cell[60111, 1961, 607, 14, 152, "Input"], Cell[60721, 1977, 568, 15, 57, "Output"] }, Open ]], Cell[61304, 1995, 170, 5, 26, "Text"], Cell[CellGroupData[{ Cell[61499, 2004, 103, 2, 40, "Input"], Cell[61605, 2008, 227, 4, 41, "Output"] }, Open ]], Cell[61847, 2015, 105, 3, 26, "Text"], Cell[CellGroupData[{ Cell[61977, 2022, 181, 4, 56, "Input"], Cell[62161, 2028, 685, 16, 57, "Output"] }, Open ]], Cell[62861, 2047, 130, 3, 26, "Text"], Cell[CellGroupData[{ Cell[63016, 2054, 105, 2, 40, "Input"], Cell[63124, 2058, 247, 4, 57, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[63420, 2068, 43, 0, 54, "Subsection"], Cell[63466, 2070, 310, 7, 44, "Text"], Cell[CellGroupData[{ Cell[63801, 2081, 73, 2, 40, "Input"], Cell[63877, 2085, 419, 13, 41, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[64333, 2103, 94, 2, 40, "Input"], Cell[64430, 2107, 60, 2, 41, "Output"] }, Open ]], Cell[64505, 2112, 632, 19, 44, "Text"], Cell[CellGroupData[{ Cell[65162, 2135, 104, 2, 40, "Input"], Cell[65269, 2139, 752, 11, 105, "Output"] }, Open ]], Cell[66036, 2153, 1013, 31, 134, "Text"], Cell[CellGroupData[{ Cell[67074, 2188, 88, 2, 40, "Input"], Cell[67165, 2192, 419, 13, 41, "Output"] }, Open ]], Cell[67599, 2208, 203, 6, 26, "Text"], Cell[CellGroupData[{ Cell[67827, 2218, 132, 3, 40, "Input"], Cell[67962, 2223, 388, 14, 125, "Output"] }, Open ]], Cell[68365, 2240, 1337, 37, 80, "Text"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[69751, 2283, 29, 0, 62, "Section"], Cell[69783, 2285, 627, 11, 116, "Text"] }, Open ]] }, Open ]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)