{ "cells": [ { "cell_type": "markdown", "id": "60423e50-8960-429f-8d69-d05f2dd232d9", "metadata": {}, "source": [ "We implement the dynamical system known as $q$-difference Painlevé one,\n", "\\begin{equation*}\n", " q\\textrm{P}_{\\textrm{I}}:\\quad (x,y,t)\\mapsto (\\overline{x},\\overline{y},\\overline{t}),\\quad\n", "\\begin{cases}\n", "\\displaystyle\\overline{x}=\\frac{t}{x-s^{-1}y}, & \\\\\n", "\\displaystyle\\overline{y}=\\frac{s\\, x}{y}, & \\\\\n", "\\displaystyle\\overline{t}=s\\,t. &\n", "\\end{cases}\n", "\\end{equation*}\n", "Here $s$ is a fixed nonzero constant usually denoted by $q$ in the $q$-difference literature. the variable $t$, also nonzero, is referred to by time and we are interested in the dynamics of $(x,y)$ as time evolves in steps $t\\mapsto s\\,t$.\n", "\n", "This dynamical system is regularised through eight number of blow-ups of $\\{(x,y)\\in\\mathbb{P}^1\\times \\mathbb{P}^1\\}$, and by afterwards removing an invariant closed subspace, results in a algebraic surface $X_{t,s}$, the initial value space, such that\n", "\\begin{equation*}\n", "X_{t,s}\\rightarrow X_{\\overline{t},s},(x,y)\\mapsto (\\overline{x},\\overline{y}),\n", "\\end{equation*}\n", "is an isomorphism.\n", "\n", "\n", "\n", "The initial value space can be covered by five charts,\n", "\\begin{equation}\n", "\\begin{aligned}\n", " x&=x_0, & y&=y_0,\\\\\n", " x&=\\frac{1}{x_1}, & y&=1+x_1y_1,\\\\\n", " x&=x_2(t+x_2y_2), & y&=\\frac{1}{x_2},\\\\\n", " x&=x_3(t+x_3y_3), & y&=x_3^2(t+x_3y_3),\\\\\n", " x&=\\frac{1}{x_4(s+x_4y_4)}, & y&=\\frac{1}{x_4}.\n", "\\end{aligned}\n", "\\end{equation}\n", "\n", "For now, we work over a general field $\\mathbf{k}$.\n", "\n", "\n", " A state is a tuple\n", "\\begin{equation*}\n", " (j,x,y,t,s),\n", "\\end{equation*}\n", "where $0\\leq j\\leq 4$ an integer indicating the relevant chart, $t,s\\in \\mathbf{k}^*$ and \n", "\\begin{equation*}\n", " \\begin{cases}\n", " (x,y)\\in \\mathbb{F}_q^*\\times \\mathbf{k}^* & \\text{if $j=0$,}\\\\\n", " (x,y)\\in \\{0\\}\\times \\mathbf{k} & \\text{if $1\\leq j\\leq 4$.}\n", " \\end{cases}\n", "\\end{equation*} \n", "\n", "\n", "The dynamical system is hard-coded below. You input a state,\n", "\\begin{equation*}\n", "\\operatorname{state}=(j,x,y,t,s),\n", "\\end{equation*}\n", "and it will output the evolution of that state,\n", "\\begin{equation*}\n", "\\overline{\\operatorname{state}}=(\\overline{j},\\overline{x},\\overline{y},s\\,t,s).\n", "\\end{equation*}\n", "The $x,y,t,s$ need to be from the same field $\\mathbf{k}$, and $t,s\\in \\mathbf{k}^*$. If $j=0$, then $x,y\\in \\mathbf{k}^*$, else $x_j=0$ and $y_j\\in \\mathbf{k}$." ] }, { "cell_type": "code", "execution_count": 1, "id": "f301cf7e-3d67-44af-98c6-8ac03243a7f9", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "//Input a state, which is a tuple of the form , where j an integer between 0 and 4, t,s nonzero elements of a field k and\n", "//if j=0, then x,y nonzero elements of k;\n", "//if j=1,2,3 or 4, then x=0 and y an element of k.\n", "//Outputs the result of applying qPI to input state.\n", "evolution := function(state)\n", " j := state[1];\n", " x := state[2];\n", " y := state[3];\n", " t := state[4];\n", " s := state[5];\n", " tnew := s*t;\n", " snew := s;\n", " if j eq 0 then\n", " if s*x-y eq 0 then\n", " jnew := 1;\n", " xnew := 0;\n", " ynew := t/x; \n", " else\n", " jnew := 0;\n", " xnew := s*t/(s*x-y);\n", " ynew := s*x/y; \n", " end if;\n", " elif j eq 1 then\n", " jnew := 2;\n", " xnew := 0;\n", " ynew := -s*t*(s*y-1); \n", " elif j eq 2 then\n", " jnew := 3;\n", " xnew := 0;\n", " ynew := s*y; \n", " elif j eq 3 then\n", " jnew := 4;\n", " xnew := 0;\n", " ynew := s*(s*y-t)/t; \n", " elif j eq 4 then\n", " if y eq 0 then\n", " jnew := 1;\n", " xnew := 0;\n", " ynew := 0; \n", " else\n", " jnew := 0;\n", " xnew := -s^2*t/y;\n", " ynew := 1; \n", " end if;\n", " end if;\n", " return ;\n", "end function;" ] }, { "cell_type": "markdown", "id": "4978d06e-bf75-485b-8bdc-539e05615efc", "metadata": {}, "source": [ "From here on, we consider the dynamical system over finite fields $\\mathbb{F}_{q}$, $q=p^n$." ] }, { "cell_type": "markdown", "id": "0b28ccb1-e664-445f-90a7-4a938ad69e97", "metadata": {}, "source": [ "Example of a state and its evolution." ] }, { "cell_type": "code", "execution_count": 2, "id": "d254bfd1-6ed5-48cf-953d-af6d146a5801", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "<1, 0, 3, 6, 2>\n" ] } ], "source": [ "//Construct prime field of order 7\n", "F := GF(7);\n", "examplestate := <0,F!1,F!2,F!3,F!2>;\n", "evolution(examplestate);" ] }, { "cell_type": "markdown", "id": "b14236f4-fe20-45c7-bac3-64220a05513c", "metadata": {}, "source": [ "Let's compute the full orbit." ] }, { "cell_type": "code", "execution_count": 3, "id": "d13056d1-8bb1-47a1-aaf0-04fb43b0e069", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "<0, 1, 2, 3, 3>\n", "<0, 2, 5, 2, 3>\n", "<0, 6, 4, 6, 3>\n", "<1, 0, 1, 4, 3>\n", "<2, 0, 4, 5, 3>\n", "<3, 0, 5, 1, 3>\n", "<4, 0, 0, 3, 3>\n", "<1, 0, 0, 2, 3>\n", "<2, 0, 6, 6, 3>\n", "<3, 0, 4, 4, 3>\n", "<4, 0, 6, 5, 3>\n", "<0, 3, 1, 1, 3>\n", "<0, 3, 2, 3, 3>\n", "<1, 0, 1, 2, 3>\n", "<2, 0, 2, 6, 3>\n", "<3, 0, 6, 4, 3>\n", "<4, 0, 0, 5, 3>\n", "<1, 0, 0, 1, 3>\n", "<2, 0, 3, 3, 3>\n", "<3, 0, 2, 2, 3>\n", "<4, 0, 6, 6, 3>\n", "<0, 5, 1, 4, 3>\n", "<1, 0, 5, 5, 3>\n", "<2, 0, 0, 1, 3>\n", "<3, 0, 0, 3, 3>\n", "<4, 0, 4, 2, 3>\n", "<0, 6, 1, 6, 3>\n", "<0, 6, 4, 4, 3>\n", "<1, 0, 3, 5, 3>\n", "<2, 0, 6, 1, 3>\n", "<3, 0, 4, 3, 3>\n", "<4, 0, 2, 2, 3>\n", "<0, 5, 1, 6, 3>\n", "<1, 0, 4, 4, 3>\n", "<2, 0, 1, 5, 3>\n", "<3, 0, 3, 1, 3>\n", "<4, 0, 3, 3, 3>\n", "<0, 5, 1, 2, 3>\n", "<1, 0, 6, 6, 3>\n", "<2, 0, 2, 4, 3>\n", "<3, 0, 6, 5, 3>\n", "<4, 0, 5, 1, 3>\n", "<0, 1, 1, 3, 3>\n", "<0, 1, 3, 2, 3>\n", "<1, 0, 2, 6, 3>\n", "<2, 0, 1, 4, 3>\n", "<3, 0, 3, 5, 3>\n", "<4, 0, 1, 1, 3>\n", "<0, 5, 1, 3, 3>\n", "<1, 0, 2, 2, 3>\n", "<2, 0, 5, 6, 3>\n", "<3, 0, 1, 4, 3>\n", "<4, 0, 1, 5, 3>\n", "<0, 4, 1, 1, 3>\n", "<0, 6, 5, 3, 3>\n", "<0, 5, 5, 2, 3>\n", "<0, 2, 3, 6, 3>\n", "<0, 6, 2, 4, 3>\n", "<0, 6, 2, 5, 3>\n", "<0, 4, 2, 1, 3>\n", "<0, 1, 6, 3, 3>\n", "<0, 4, 4, 2, 3>\n", "<0, 6, 3, 6, 3>\n", "<0, 4, 6, 4, 3>\n", "<0, 2, 2, 5, 3>\n", "<0, 2, 3, 1, 3>\n", "<0, 1, 2, 3, 3>\n", "66\n" ] } ], "source": [ "orbit := AssociativeArray(Integers());\n", "orbit[0] := <0,F!1,F!2,F!3,F!3>;\n", "orbit[1] := evolution(orbit[0]);\n", "i := 1;\n", "orbit[0];\n", "orbit[1];\n", "while (not orbit[i] eq orbit[0]) and i le 1000 do\n", " i := i + 1;\n", " orbit[i] := evolution(orbit[i-1]);\n", " orbit[i];\n", "end while;\n", "i;" ] }, { "cell_type": "markdown", "id": "fd93ad70-fe1c-47ea-993d-92cca6a5b0bf", "metadata": {}, "source": [ "We formalise the initial value space simply as the set of all states with given values of $t,s\\in \\mathbb{F}_q^*$. We implement a corresponding function that returns the initial value space below." ] }, { "cell_type": "code", "execution_count": 4, "id": "548d1c10-ee1c-4be3-915e-c19f14330d17", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "//Input a prime power q and integers tindex and sindex between 1 and q-1.\n", "//Output the (set of rational points on the) initial value space,\n", "//i.e. the set of all possible states over F_q for fixed t and s defined by corresponding indices.\n", "invalspace := function(q,tindex,sindex)\n", " F := GF(q);\n", " Fstar := [f : f in F | f ne 0];\n", " t := Fstar[tindex];\n", " s := Fstar[sindex];\n", " FstarCrosFstar := {<0, x, y, t, s> : x in Fstar, y in Fstar};\n", " L1 := {<1, F!0, y, t, s> : y in F};\n", " L2 := {<2, F!0, y, t, s> : y in F};\n", " L3 := {<3, F!0, y, t, s> : y in F};\n", " L4 := {<4, F!0, y, t, s> : y in F};\n", " TheParts := [FstarCrosFstar, L1, L2, L3, L4];\n", " InitialValueSpace := &join TheParts; \n", " return InitialValueSpace;\n", "end function;" ] }, { "cell_type": "markdown", "id": "48b72af2-874f-4ab8-a1de-27535df03bf5", "metadata": {}, "source": [ "An example" ] }, { "cell_type": "code", "execution_count": 5, "id": "3ddff604-4b55-4d1a-b541-123f6a131d74", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{ <0, $.1^3, $.1^7, 1, $.1>, <0, $.1, $.1, 1, $.1>, <0, $.1^7, $.1^2, 1, $.1>, <0, 2, 2, 1, $.1>, <0, $.1^6, $.1^3, 1, $.1>, <0, $.1^2, $.1^7, 1, $.1>, <0, $.1, $.1^5, 1, $.1>, <0, $.1^5, $.1^3, 1, $.1>, <0, $.1^3, $.1^5, 1, $.1>, <1, 0, 1, 1, $.1>, <0, $.1^7, $.1^7, 1, $.1>, <4, 0, $.1^2, 1, $.1>, <0, $.1^2, 2, 1, $.1>, <0, $.1^5, $.1^7, 1, $.1>, <0, $.1, 2, 1, $.1>, <4, 0, 1, 1, $.1>, <0, 2, $.1^2, 1, $.1>, <2, 0, 0, 1, $.1>, <2, 0, 1, 1, $.1>, <0, 1, $.1^3, 1, $.1>, <0, $.1^3, 1, 1, $.1>, <0, $.1^5, 2, 1, $.1>, <4, 0, 2, 1, $.1>, <2, 0, $.1^7, 1, $.1>, <4, 0, 0, 1, $.1>, <0, $.1^7, $.1, 1, $.1>, <0, $.1^7, $.1^3, 1, $.1>, <3, 0, $.1^2, 1, $.1>, <0, $.1^5, $.1, 1, $.1>, <0, $.1^3, $.1, 1, $.1>, <0, $.1^5, 1, 1, $.1>, <0, $.1^3, 2, 1, $.1>, <1, 0, $.1^5, 1, $.1>, <0, 1, $.1, 1, $.1>, <1, 0, 2, 1, $.1>, <0, $.1^7, 1, 1, $.1>, <0, 1, $.1^7, 1, $.1>, <0, 2, $.1^5, 1, $.1>, <1, 0, 0, 1, $.1>, <1, 0, $.1^6, 1, $.1>, <0, 2, 1, 1, $.1>, <0, $.1^2, $.1, 1, $.1>, <0, $.1^2, $.1^2, 1, $.1>, <0, 1, $.1^6, 1, $.1>, <0, $.1, $.1^2, 1, $.1>, <0, $.1^6, $.1^6, 1, $.1>, <1, 0, $.1^3, 1, $.1>, <0, 1, 1, 1, $.1>, <0, $.1^2, 1, 1, $.1>, <2, 0, $.1^2, 1, $.1>, <3, 0, $.1^7, 1, $.1>, <0, $.1^6, $.1^7, 1, $.1>, <3, 0, 2, 1, $.1>, <1, 0, $.1, 1, $.1>, <0, $.1^7, 2, 1, $.1>, <0, $.1^5, $.1^6, 1, $.1>, <0, $.1^5, $.1^5, 1, $.1>, <2, 0, $.1^6, 1, $.1>, <3, 0, 1, 1, $.1>, <1, 0, $.1^2, 1, $.1>, <3, 0, $.1^3, 1, $.1>, <4, 0, $.1, 1, $.1>, <0, $.1^2, $.1^3, 1, $.1>, <0, $.1^3, $.1^3, 1, $.1>, <0, 1, $.1^2, 1, $.1>, <0, $.1^2, $.1^5, 1, $.1>, <0, 1, $.1^5, 1, $.1>, <2, 0, $.1^3, 1, $.1>, <0, $.1^7, $.1^6, 1, $.1>, <0, $.1^5, $.1^2, 1, $.1>, <2, 0, 2, 1, $.1>, <0, $.1^2, $.1^6, 1, $.1>, <3, 0, $.1^6, 1, $.1>, <0, 2, $.1^6, 1, $.1>, <0, 2, $.1^3, 1, $.1>, <0, 1, 2, 1, $.1>, <0, $.1^3, $.1^6, 1, $.1>, <0, $.1, 1, 1, $.1>, <0, $.1^6, $.1^5, 1, $.1>, <0, $.1^6, 2, 1, $.1>, <0, $.1^6, $.1, 1, $.1>, <0, $.1^7, $.1^5, 1, $.1>, <4, 0, $.1^6, 1, $.1>, <3, 0, $.1^5, 1, $.1>, <0, $.1, $.1^3, 1, $.1>, <0, $.1^6, 1, 1, $.1>, <2, 0, $.1^5, 1, $.1>, <2, 0, $.1, 1, $.1>, <1, 0, $.1^7, 1, $.1>, <4, 0, $.1^5, 1, $.1>, <0, 2, $.1^7, 1, $.1>, <0, $.1, $.1^6, 1, $.1>, <0, 2, $.1, 1, $.1>, <0, $.1, $.1^7, 1, $.1>, <4, 0, $.1^7, 1, $.1>, <3, 0, 0, 1, $.1>, <3, 0, $.1, 1, $.1>, <0, $.1^3, $.1^2, 1, $.1>, <4, 0, $.1^3, 1, $.1>, <0, $.1^6, $.1^2, 1, $.1> }\n", "100\n" ] } ], "source": [ "intspace := invalspace(9,1,2);\n", "intspace;\n", "# intspace;" ] }, { "cell_type": "markdown", "id": "6433fbca-3a5d-4931-aa4c-461da1dfef62", "metadata": {}, "source": [ "We define an orbit as a sequence of states,\n", "\\begin{equation*}\n", " (\\operatorname{state}_1,\\operatorname{state}_2,\\ldots,\\operatorname{state}_m), \n", "\\end{equation*}\n", "with $\\operatorname{state}_{k+1}=\\overline{\\operatorname{state}}_k$ for $1\\leq k\\leq m-1$ and $\\operatorname{state}_{1}=\\overline{\\operatorname{state}}_m$. The last equality implies $t=s^{m+1}t$, so that the length $m$ of the orbit must be a multiple of $r$, the multiplicative order of $s$. We call $\\frac{m}{r}\\in\\mathbb{Z}_{\\geq 1}$ the reduced length of the orbit." ] }, { "cell_type": "code", "execution_count": 6, "id": "02caab04-e8dc-411c-82ff-e766f274c888", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "//Input a state.\n", "//Output the orbit with the input state as first state.\n", "orbitlist := function(state)\n", " orbit := AssociativeArray(Integers());\n", " orbit[0] := state;\n", " orbit[1] := evolution(orbit[0]);\n", " i := 1;\n", " while (not orbit[i] eq orbit[0]) do\n", " i := i + 1;\n", " orbit[i] := evolution(orbit[i-1]);\n", " end while;\n", " output := [orbit[j] : j in [0..i-1]];\n", " return output;\n", "end function;" ] }, { "cell_type": "markdown", "id": "29482eb3-37f3-4f69-a2f3-6273375a3fa8", "metadata": {}, "source": [ "Some examples" ] }, { "cell_type": "code", "execution_count": 7, "id": "aadbee9e-1d8a-4933-87ee-68dcb67ccc67", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{ <2, 0, 0, 1, 1>, <4, 0, 1, 1, 1>, <4, 0, 0, 1, 1>, <3, 0, 0, 1, 1>, <2, 0, 1, 1, 1>, <1, 0, 1, 1, 1>, <0, 1, 1, 1, 1>, <3, 0, 1, 1, 1>, <1, 0, 0, 1, 1> }\n", "9\n", "[ <0, 1, 1, 1, 1>, <1, 0, 1, 1, 1>, <2, 0, 0, 1, 1>, <3, 0, 0, 1, 1>, <4, 0, 1, 1, 1> ]\n", "[ <1, 0, 0, 1, 1>, <2, 0, 1, 1, 1>, <3, 0, 1, 1, 1>, <4, 0, 0, 1, 1> ]\n" ] } ], "source": [ "intspace := invalspace(2,1,1);\n", "intspace;\n", "# intspace;\n", "F := GF(2);\n", "examplestate := <0,F!1,F!1,F!1,F!1>;\n", "orbitlist(examplestate);\n", "examplestate := <1,F!0,F!0,F!1,F!1>;\n", "orbitlist(examplestate);" ] }, { "cell_type": "code", "execution_count": 8, "id": "9d322b5c-b829-4327-9d2f-e1b006cca054", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{ <2, 0, 2, 1, 2>, <2, 0, 0, 1, 2>, <1, 0, 0, 1, 2>, <4, 0, 2, 1, 2>, <0, 1, 2, 1, 2>, <1, 0, 2, 1, 2>, <0, 2, 2, 1, 2>, <3, 0, 0, 1, 2>, <2, 0, 1, 1, 2>, <3, 0, 2, 1, 2>, <4, 0, 0, 1, 2>, <0, 2, 1, 1, 2>, <0, 1, 1, 1, 2>, <1, 0, 1, 1, 2>, <4, 0, 1, 1, 2>, <3, 0, 1, 1, 2> }\n", "16\n" ] } ], "source": [ "intspace := invalspace(3,1,2);\n", "intspace;\n", "# intspace;" ] }, { "cell_type": "code", "execution_count": 9, "id": "05914054-9604-4043-aeb3-1cf2e4bff12b", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Finite field of size 2^2\n", "[ 0, 1, a, a^2 ]\n", "$.1^2 + $.1 + 1\n", "[ <0, a, a, 1, a>, <0, a, a, a, a>, <0, a^2, a, a^2, a>, <0, a, a^2, 1, a>, <1, 0, a^2, a, a>, <2, 0, 0, a^2, a>, <3, 0, 0, 1, a>, <4, 0, a, a, a>, <0, a^2, 1, a^2, a>, <1, 0, 1, 1, a>, <2, 0, 1, a, a>, <3, 0, a, a^2, a>, <4, 0, 0, 1, a>, <1, 0, 0, a, a>, <2, 0, a^2, a^2, a>, <3, 0, 1, 1, a>, <4, 0, 1, a, a>, <0, 1, 1, a^2, a> ]\n" ] } ], "source": [ "F := GF(2^2);\n", "F;\n", "[x : x in F];\n", "DefiningPolynomial(F);\n", "orbitlist(<0, F!a, F!a, F!1, F!a>);" ] }, { "cell_type": "code", "execution_count": 10, "id": "5ad3bd80-8e16-454f-9a53-c5bb539baa14", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "//Input a prime power q and integers tindex and sindex between 1 and q-1. \n", "//Output the set of all orbits generated by states in initial value space.\n", "fulldecompsets := function(q,tindex,sindex)\n", " intspace := invalspace(q,tindex,sindex); \n", " orbits := {};\n", " while # intspace gt 0 do\n", " state := Rep(intspace); \n", " orbit := orbitlist(state); \n", " orbits := orbits join {orbit}; \n", " intspace := intspace diff Set(orbit); \n", " end while;\n", " return orbits;\n", "end function;" ] }, { "cell_type": "markdown", "id": "b0e23892-13c2-4bab-a60d-71b2ad4bb0c4", "metadata": {}, "source": [ "Let's look at an example." ] }, { "cell_type": "code", "execution_count": 11, "id": "c810ce61-4d3d-44e3-84db-26a830e3df09", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[ 2, 24, 8, 30, 20, 22, 28, 10, 18, 8, 10, 20 ]\n" ] } ], "source": [ "decomp := fulldecompsets(9,2,5);\n", "[# orbit : orbit in decomp]; //List of lengths of orbits" ] }, { "cell_type": "code", "execution_count": 12, "id": "16c76d51-d8eb-4081-973a-78673cdff09f", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[ 14, 10, 8 ]\n", "{\n", "[ <3, 0, 2, 1, 2>, <4, 0, 0, 2, 2>, <1, 0, 0, 1, 2>, <2, 0, 2, 2, 2>, <3, 0, 1, 1, 2>, <4, 0, 2, 2, 2>, <0, 2, 1, 1, 2>, <1, 0, 2, 2, 2>, <2, 0, 0, 1, 2>, <3, 0, 0, 2, 2>, <4, 0, 1, 1, 2>, <0, 2, 1, 2, 2>, <1, 0, 1, 1, 2>, <2, 0, 1, 2, 2> ],\n", "[ <2, 0, 2, 1, 2>, <3, 0, 1, 2, 2>, <4, 0, 0, 1, 2>, <1, 0, 0, 2, 2>, <2, 0, 1, 1, 2>, <3, 0, 2, 2, 2>, <4, 0, 2, 1, 2>, <0, 1, 1, 2, 2>, <0, 1, 2, 1, 2>, <1, 0, 1, 2, 2> ],\n", "[ <0, 1, 1, 1, 2>, <0, 2, 2, 2, 2>, <0, 2, 2, 1, 2>, <0, 1, 2, 2, 2>, <1, 0, 2, 1, 2>, <2, 0, 0, 2, 2>, <3, 0, 0, 1, 2>, <4, 0, 1, 2, 2> ]\n", "}\n" ] } ], "source": [ "decomp := fulldecompsets(3,1,2);\n", "[# orbit : orbit in decomp];\n", "decomp;" ] }, { "cell_type": "code", "execution_count": 13, "id": "4330366d-6c71-4107-8ca0-c524fef07dfb", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[ 9, 8, 4, 6, 5, 4 ]\n", "[ 16, 36, 24, 32, 20, 16 ]\n", "[ 16, 20, 32, 36, 24, 16 ]\n", "[ 8, 10, 8, 12, 18, 16 ]\n" ] } ], "source": [ "decomp := fulldecompsets(5,1,1);\n", "[# orbit : orbit in decomp];\n", "decomp := fulldecompsets(5,1,2);\n", "[# orbit : orbit in decomp];\n", "decomp := fulldecompsets(5,1,3);\n", "[# orbit : orbit in decomp];\n", "decomp := fulldecompsets(5,1,4);\n", "[# orbit : orbit in decomp];" ] }, { "cell_type": "code", "execution_count": 14, "id": "9a88ecb4-8355-4b6d-8cf9-df501efdcbe1", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[ 12, 15, 18, 18, 12 ]\n", "{\n", "[ <1, 0, a, 1, a>, <2, 0, a^2, a, a>, <3, 0, 1, a^2, a>, <4, 0, a^2, 1, a>, <0, 1, 1, a, a>, <0, 1, a, a^2, a>, <1, 0, a^2, 1, a>, <2, 0, 0, a, a>, <3, 0, 0, a^2, a>, <4, 0, a, 1, a>, <0, a, 1, a, a>, <0, a, a^2, a^2, a> ],\n", "[ <2, 0, 1, 1, a>, <3, 0, a, a, a>, <4, 0, 1, a^2, a>, <0, a, 1, 1, a>, <0, 1, a^2, a, a>, <0, a^2, a^2, a^2, a>, <0, a^2, a, 1, a>, <0, a^2, a^2, a, a>, <0, a, a, a^2, a>, <0, 1, a, 1, a>, <1, 0, 1, a, a>, <2, 0, a, a^2, a>, <3, 0, a^2, 1, a>, <4, 0, 0, a, a>, <1, 0, 0, a^2, a> ],\n", "[ <0, 1, a^2, 1, a>, <0, a, a^2, a, a>, <1, 0, 1, a^2, a>, <2, 0, a^2, 1, a>, <3, 0, 1, a, a>, <4, 0, 0, a^2, a>, <1, 0, 0, 1, a>, <2, 0, a, a, a>, <3, 0, a^2, a^2, a>, <4, 0, 1, 1, a>, <0, a^2, 1, a, a>, <1, 0, a^2, a^2, a>, <2, 0, 0, 1, a>, <3, 0, 0, a, a>, <4, 0, a, a^2, a>, <0, 1, 1, 1, a>, <0, a^2, a, a, a>, <0, 1, a^2, a^2, a> ],\n", "[ <3, 0, 1, 1, a>, <4, 0, 1, a, a>, <0, 1, 1, a^2, a>, <0, a, a, 1, a>, <0, a, a, a, a>, <0, a^2, a, a^2, a>, <0, a, a^2, 1, a>, <1, 0, a^2, a, a>, <2, 0, 0, a^2, a>, <3, 0, 0, 1, a>, <4, 0, a, a, a>, <0, a^2, 1, a^2, a>, <1, 0, 1, 1, a>, <2, 0, 1, a, a>, <3, 0, a, a^2, a>, <4, 0, 0, 1, a>, <1, 0, 0, a, a>, <2, 0, a^2, a^2, a> ],\n", "[ <0, a^2, 1, 1, a>, <1, 0, a, a, a>, <2, 0, 1, a^2, a>, <3, 0, a, 1, a>, <4, 0, a^2, a, a>, <0, a, 1, a^2, a>, <0, a^2, a^2, 1, a>, <0, 1, a, a, a>, <1, 0, a, a^2, a>, <2, 0, a, 1, a>, <3, 0, a^2, a, a>, <4, 0, a^2, a^2, a> ]\n", "}\n" ] } ], "source": [ "decomp := fulldecompsets(4,1,2);\n", "[# orbit : orbit in decomp];\n", "decomp;" ] }, { "cell_type": "code", "execution_count": 15, "id": "e289d1c1-760d-409e-80b8-47ddd479d93b", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "//Input a prime power q and integers tindex and sindex between 1 and q-1.\n", "//Output list with lengths of all orbits for these parameter values.\n", "fulldecompnumbers := function(q,tindex,sindex)\n", " intspace := invalspace(q,tindex,sindex);\n", " orbitlengths := [];\n", " while # intspace gt 0 do\n", " state := Rep(intspace);\n", " orbit := orbitlist(state);\n", " Append(~orbitlengths, # orbit);\n", " intspace := intspace diff Set(orbit);\n", " end while;\n", " Sort(~orbitlengths);\n", " return orbitlengths;\n", "end function;" ] }, { "cell_type": "code", "execution_count": 16, "id": "48ec013a-9f8e-4a04-9493-a3633beb33f6", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[ 32, 32, 32, 32, 40, 40, 40, 48, 48, 56, 56, 56, 56, 56, 88, 88 ]\n" ] } ], "source": [ "fulldecompnumbers(9,1,2);" ] }, { "cell_type": "code", "execution_count": 17, "id": "4f40c5ef-d9ad-4c00-8f7f-bb5ffe55d850", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "//Input a prime power q and integer sindex between 1 and q-1. Spits out list of index representatives of GF(q)^*/mult s.\n", "findinequivalentt := function(q,sindex)\n", " F := GF(q);\n", " Flistnonz := [x : x in F | x ne 0];\n", " s := Flistnonz[sindex];\n", " n := Order(s);\n", " tspacereps := [];\n", " tspace := {x : x in F | x ne 0};\n", " while # tspace gt 0 do\n", " trep := Rep(tspace);\n", " Append(~tspacereps, trep);\n", " multorbit := {s^i*trep : i in [1..n]};\n", " tspace := tspace diff multorbit;\n", " end while;\n", " tindexreps := [tindex : tindex in [1..q-1] | Flistnonz[tindex] in tspacereps ];\n", " Sort(~tindexreps);\n", "return tindexreps;\n", "end function;" ] }, { "cell_type": "code", "execution_count": 18, "id": "45923bec-6dc1-4687-be62-985aa8c394f1", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Finite field of size 3^2\n", "[ 0, 1, a, a^2, a^3, 2, a^5, a^6, a^7 ]\n", "[ 1, 2, 3, 4 ]\n" ] } ], "source": [ "F := GF(3^2);\n", "F;\n", "[x : x in F];\n", "findinequivalentt(9,5)" ] }, { "cell_type": "code", "execution_count": 19, "id": "cfae9fbe-470a-4126-8f71-d8717b0937ac", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "//Input a prime power q and integer sindex between 1 and q-1. Spits out all orbitlengths, for all inequivalent values of t under multiplication by s, as a list.\n", "orbitlengthss := function(q,sindex)\n", " tvals := findinequivalentt(q,sindex);\n", " listoflistsoforbitlengths := [fulldecompnumbers(q,tindex,sindex) : tindex in tvals];\n", " orbitlengthsflat := [ length : length in sublist, sublist in listoflistsoforbitlengths];\n", " Sort(~orbitlengthsflat);\n", " return orbitlengthsflat;\n", "end function;" ] }, { "cell_type": "code", "execution_count": 20, "id": "d226b245-0a8d-4ac6-bd09-de4d78d87d41", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[ 2, 2, 2, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 12, 12, 12, 12, 14, 14, 14, 14, 14, 16, 16, 18, 18, 20, 20, 20, 20, 22, 22, 22, 22, 22, 22, 24, 24, 26, 26, 28, 28, 30, 30 ]\n" ] } ], "source": [ "orbitlengthss(9,5);" ] }, { "cell_type": "code", "execution_count": 21, "id": "1802be55-329b-466f-84fe-b6696b60ca98", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "//Input a prime power q and positive integer r, spits out all reduced orbit lengths as a list, for s's with multiplicative order r.\n", "redorbitlengthsgivenorder := function(q,r)\n", " F := GF(q);\n", " Flistnonz := [x : x in F | x ne 0];\n", " Fmult, phi := MultiplicativeGroup(F); // phi: Fmult → F*\n", " Fmultnpre := {phi(s) : s in Fmult | Order(s) eq r};\n", " Fmultn := [sindex : sindex in [1..q-1] | Flistnonz[sindex] in Fmultnpre ];\n", " listoflistsoforbitlengths := [orbitlengthss(q,sindex) : sindex in Fmultn ];\n", " orbitlengthsflat := [ length/r : length in sublist, sublist in listoflistsoforbitlengths];\n", " Sort(~orbitlengthsflat);\n", " return orbitlengthsflat;\n", "end function;" ] }, { "cell_type": "code", "execution_count": 22, "id": "2133eb0e-7686-4efd-8868-52c4fc006f89", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[ 1, 1, 1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15 ]\n" ] } ], "source": [ "redorbitlengthsgivenorder(9,2);" ] }, { "cell_type": "code", "execution_count": 23, "id": "e916deca-cda8-4af0-a383-20537b24540a", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "//Input a list, outputs a list of pairs (elem, freq), where freq the the number of times elem occurs in list\n", "listtofrequency :=function(list)\n", " counts := AssociativeArray(Integers());\n", " for elem in list do\n", " if not IsDefined(counts, elem) then\n", " counts[elem] := 0;\n", " end if;\n", " counts[elem] := counts[elem] + 1;\n", " end for;\n", " countlist := [[elem,counts[elem]] : elem in Sort(SetToSequence(Keys(counts)))];\n", " return countlist;\n", "end function;" ] }, { "cell_type": "code", "execution_count": 24, "id": "3231921d-dbeb-44d4-8ebf-e18b321fa031", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[\n", "[ 1, 3 ],\n", "[ 4, 10 ],\n", "[ 5, 10 ],\n", "[ 6, 4 ],\n", "[ 7, 5 ],\n", "[ 8, 2 ],\n", "[ 9, 2 ],\n", "[ 10, 4 ],\n", "[ 11, 6 ],\n", "[ 12, 2 ],\n", "[ 13, 2 ],\n", "[ 14, 2 ],\n", "[ 15, 2 ]\n", "]\n" ] } ], "source": [ "listtofrequency(redorbitlengthsgivenorder(9,2));" ] }, { "cell_type": "code", "execution_count": 25, "id": "61dbfcb9-59e5-4599-b308-b09ae2f37b79", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "//Input a prime power q, output an associative array with as keys the divisors of q-1, \n", "//and values all reduced orbit lengths for all choices of t and s, with multiplicative order of s specified by key.\n", "redorbitlengthsfreqbyorder := function(q)\n", " orders := Divisors(q-1);\n", " output := AssociativeArray(orders);\n", " for r in orders do\n", " output[r] := listtofrequency(redorbitlengthsgivenorder(q,r));\n", " end for;\n", " return output;\n", "end function;" ] }, { "cell_type": "code", "execution_count": 26, "id": "b2d04411-a32f-4a05-aa4f-5f0d6ffd75ac", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{ 1, 2, 4, 8 }\n", "[\n", "[ 1, 3 ],\n", "[ 4, 10 ],\n", "[ 5, 10 ],\n", "[ 6, 4 ],\n", "[ 7, 5 ],\n", "[ 8, 2 ],\n", "[ 9, 2 ],\n", "[ 10, 4 ],\n", "[ 11, 6 ],\n", "[ 12, 2 ],\n", "[ 13, 2 ],\n", "[ 14, 2 ],\n", "[ 15, 2 ]\n", "]\n" ] } ], "source": [ "data := redorbitlengthsfreqbyorder(9);\n", "Keys(data);\n", "data[2];" ] }, { "cell_type": "markdown", "id": "119d18ff-3e2b-41b0-bc2a-866ae3b68d10", "metadata": {}, "source": [ "Data will be analysed in Mathematica. To convert lists from Magma to Mathematica, square brackets need to be replaced by curley brackets." ] }, { "cell_type": "code", "execution_count": 27, "id": "cec55ab3-ad36-4e9c-9603-b2a54c16808f", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "//Input a string, output string with ['s replaced by {'s and ]'s replaced by }'s.\n", "bracketreplacer := function(str)\n", " output := \"\";\n", " for i in [1..#str] do\n", " ch := str[i];\n", " if ch eq \"[\" then\n", " output := output cat \"{\";\n", " elif ch eq \"]\" then\n", " output := output cat \"}\";\n", " else\n", " output := output cat ch;\n", " end if;\n", " end for;\n", " return output;\n", "end function;" ] }, { "cell_type": "code", "execution_count": 28, "id": "c741f742-2197-47a3-a268-2281dab1e0cb", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "//The following procedure takes as input a list of prime powers\n", "//It computes, for every element, all the reduced orbit lengths and saves the data in a txt file.\n", "getdatapw := procedure(primepowers)\n", " for q in primepowers do\n", " q;\n", " filename := \"qPI_data_q=\" cat Sprint(q) cat \".txt\";\n", " txtfile := Open(filename, \"w\");\n", " data := redorbitlengthsfreqbyorder(q);\n", " outputstring := \" { \";\n", " countouter := 1;\n", " for r in Keys(data) do\n", " datastring := \"{ \" cat Sprint(r) cat \" , {\";\n", " count := 1;\n", " for freqel in data[r] do\n", " if count eq 1 then\n", " datastring := datastring cat bracketreplacer(Sprint(freqel));\n", " else\n", " datastring := datastring cat \",\" cat bracketreplacer(Sprint(freqel));\n", " end if;\n", " count := count + 1;\n", " end for;\n", " datastring := datastring cat \"}}\";\n", " if countouter eq 1 then\n", " outputstring := outputstring cat datastring;\n", " else\n", " outputstring := outputstring cat \" , \" cat datastring;\n", " end if;\n", " countouter := countouter + 1;\n", " end for; \n", " outputstring := outputstring cat \" }\";\n", " fprintf txtfile, outputstring;\n", " end for;\n", "end procedure;" ] }, { "cell_type": "markdown", "id": "c5fd9114-de4e-458a-9ad0-14dab05a2c99", "metadata": {}, "source": [ "The following will compute all reduced orbit lengths for the prime powers 4 and 9 and store the data in the current directory." ] }, { "cell_type": "code", "execution_count": 29, "id": "1e658b5e-293d-4491-a2de-2a7c0e897726", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "4\n", "9\n" ] } ], "source": [ "getdatapw([4,9]);" ] }, { "cell_type": "code", "execution_count": 30, "id": "c779412d-4a9e-4ded-a2f3-d9e9312eb1d6", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[ 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97, 101, 103, 107, 109, 113, 121, 125, 127, 128, 131, 137, 139, 149, 151, 157, 163, 167, 169, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 243, 251, 256, 257, 263, 269, 271, 277, 281, 283, 289, 293, 307, 311, 313, 317, 331, 337, 343, 347, 349, 353, 359, 361, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 512, 521, 523, 529, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 625, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 729, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 841, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 961, 967, 971, 977, 983, 991, 997 ]\n" ] } ], "source": [ "primepowers1000 := [];\n", "\n", "for p in PrimesUpTo(1000) do\n", " n := 1;\n", " while p^n le 1000 do\n", " Append(~primepowers1000, p^n);\n", " n +:= 1;\n", " end while;\n", "end for;\n", "Sort(~primepowers1000);\n", "primepowers1000;" ] }, { "cell_type": "markdown", "id": "61575013-b3f5-4928-acf7-dd1cbb9ea2b3", "metadata": {}, "source": [ "Evaluating the code below will compute all reduced orbit lengths for all prime powers below 1000, after removing the \"//\"." ] }, { "cell_type": "code", "execution_count": 31, "id": "1466a7c5-474c-43b8-9a7e-5f07ffd500e5", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [] } ], "source": [ "//getdatapw(primepowers1000);" ] } ], "metadata": { "kernelspec": { "display_name": "Magma", "language": "magma", "name": "magma" }, "language_info": { "codemirror_mode": "pascal", "file_extension": ".m", "mimetype": "text/x-pascal", "name": "magma", "version": "2.28-5\r" } }, "nbformat": 4, "nbformat_minor": 5 }