2d:null 2e:["$","title",null,{"children":"The Goresky-Klapper Conjecture: ${tex`\\hspace{-7pt}\\mod n`} residues of images of monomials over ${tex`\\mathbb{Z}_p`} | Bryan | Observable"}] 33:[] 31:{"id":"4c7453b69ff6e575","slug":"images-of-monomials-over-z_p-mod-n","title":"The Goresky-Klapper Conjecture: ${tex`\\hspace{-7pt}\\mod n`} residues of images of monomials over ${tex`\\mathbb{Z}_p`}","thumbnail":"8b3e6b4f20877dca4c4d7f4464f551722ebe53f1eef50c260983265d39ecdeb5","access_level":"public","create_time":"$D2018-03-26T00:31:39.072Z","update_time":"$D2018-11-27T02:05:27.161Z","view_time":null,"first_public_time":"$D2018-03-26T04:29:46.693Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"a8afac7fc0f0a766","login":"bbischof","name":"Bryan","avatar_url":"https://avatars-next.observableusercontent.com/c71257ace95ae262b20ea3ea4f4b2a09891e92c86bf45e64d1b97d82d212a332","tier":"starter_2024"},"version":607,"publish_version":607,"role":null,"authored":false,"authors":[{"type":"individual","id":"32ac87846a6eed40","login":"bbischof","name":"Bryan","avatar_url":"https://avatars-next.observableusercontent.com/c71257ace95ae262b20ea3ea4f4b2a09891e92c86bf45e64d1b97d82d212a332","tier":null}],"members":[{"type":"individual","id":"32ac87846a6eed40","login":"bbischof","name":"Bryan","avatar_url":"https://avatars-next.observableusercontent.com/c71257ace95ae262b20ea3ea4f4b2a09891e92c86bf45e64d1b97d82d212a332","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":1,"collection":null,"type":"notebook","body":{"title":"The Goresky-Klapper Conjecture: ${tex`\\hspace{-7pt}\\mod n`} residues of images of monomials over ${tex`\\mathbb{Z}_p`}","cells":[{"id":0,"value":"md`# The Goresky-Klapper Conjecture: ${tex`\\hspace{-7pt}\\mod n`} residues of images of monomials over ${tex`\\mathbb{Z}_p`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":564,"value":"md`The following is a exploration of the Goresky-Klapper Conjecture. No results are new. I appreciate being introduced to the problem by Vincent Pigno related to an upcoming paper of his with coauthors.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":473,"value":"md`## Problem Statement\n\nConsider a cyclic group ${tex`\\mathbb{Z}_p`}, and all of it's elements as integers ${tex`\\mod n`}.\n\nNow consider a monomial of the form ${tex`f(x)=ax^{k}`} over the group.\n\nConsider the images of this monomial ${tex`\\mod n`}. \n\n_When do ${tex`x`} and ${tex`f(x)`} have the same residue ${tex`\\mod n`} _?\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":150,"value":"viewof p = slider(\n {\n min: 1, \n max: 250, \n step: 1, \n value: 13,\n title: \"p=\", \n description: \"Order of the group\"\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":232,"value":"incdec(\"p\", viewof p)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":132,"value":"viewof n = slider(\n {\n min: 2, \n max: p-1, \n step: 1, \n value: this ? this.value : 2,\n\ttitle: \"n=\", \n \tdescription: \"Modulus number\"\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":220,"value":"incdec(\"n\", n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"viewof a = slider(\n {\n min: 1, \n max: (p-1)/2, \n step: 1, \n value: this ? this.value : 2,\n title: \"a=\", \n description: \"Monomial's coefficient\"\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":235,"value":"incdec('a', viewof a)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"viewof k = slider(\n {\n min: 1, \n max: p-1, \n step: 1, \n value: this ? this.value : 2,\n title: \"k=\", \n description: \"Monomial's exponent\"\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":237,"value":"incdec('k', viewof k)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":105,"value":"md`So, we're using the monomial: ${tex.block`f(x) = ${a}x^{${k}}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"md`The elements of this group are:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"elements = [...Array(p).keys()]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":96,"value":"md`The elements of this group modulo ${n} are:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":23,"value":"elements_residues_mod_n = elements.map(function(e) { \n return e%n;\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":100,"value":"md`The elements of this group after application of this monomial are:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"elements_image_under_monomial = elements.map(function(e) { \n return (a*(e)**k)%p;\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":102,"value":"md`Their residues modulo ${n} are:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":54,"value":"elements_images_residues_mod_n = elements_image_under_monomial.map(function(e) { \n return e%n;\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":92,"value":"md`This function preserves residues mod p? ${criterion}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":65,"value":"criterion = {\n let pairs = zip([elements_residues_mod_n, elements_images_residues_mod_n])\n function equal(pair) {\n return pair[0]==pair[1];\n\t}\n return pairs.every(equal)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":579,"value":"md`## Visualizing the results for fixed n and p`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":271,"value":"md`Here are binary grids which are size k by a, and show which values of a and k satisfy the criterion with fixed n=${n} and p=${p}. Orange is True.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":273,"value":"chart = {\n let square_size = (height*2-100)/p\n \n function color(value) {\n if (value==0) {\n\t return 'steelblue'\n }\n if (value==1) {\n \treturn 'orange'\n }\n\t};\n \n const svg = d3.select(DOM.svg(width, height))\n \n let rectangles = svg.selectAll(\"rect\")\n .data(crit_data)\n .enter()\n .append(\"rect\"); \n rectangles\n .attr(\"x\", function(d){\n return d.k * square_size; \n })\n .attr(\"y\", function(d){\n return d.a * square_size; \n })\n .attr(\"width\", square_size)\n .attr(\"height\", square_size). \n style(\"fill\", function(d){\n return color(d.criterion); \n }); \n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":329,"value":"{\n const div = html`

`\n div.appendChild(incdec(\"p\", viewof p));\n div.appendChild(incdec(\"n\", viewof n));\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":381,"value":"md`## Groups of prime order \n\nI thought it'd be interesting to only look at groups of prime order, to see how their behavior changes.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":390,"value":"viewof m = slider(\n {\n min: 1, \n max: primes_below_250.length, \n step: 1, \n value: this ? this.value : 2,\n title: \"m=\", \n description: \"index of prime\"\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":431,"value":"viewof s = slider(\n {\n min: 2, \n max: q-1, \n step: 1, \n value: this ? this.value : 2,\n\ttitle: \"s=\", \n \tdescription: \"Modulus number\"\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":409,"value":"md`Then we let q be the m'th prime: m=${m}, q=${q}, s=${s}.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":425,"value":"prime_chart = {\n let square_size = (height*2-100)/q\n \n function color(value) {\n if (value==0) {\n\t return 'steelblue'\n }\n if (value==1) {\n \treturn 'orange'\n }\n\t};\n \n const svg = d3.select(DOM.svg(width, height))\n \n let rectangles = svg.selectAll(\"rect\")\n .data(prime_crit_data)\n .enter()\n .append(\"rect\"); \n rectangles\n .attr(\"x\", function(d){\n return d.k * square_size; \n })\n .attr(\"y\", function(d){\n return d.a * square_size; \n })\n .attr(\"width\", square_size)\n .attr(\"height\", square_size). \n style(\"fill\", function(d){\n return color(d.criterion); \n }); \n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":428,"value":"{\n const div = html`

`\n div.appendChild(incdec(\"m\", viewof m));\n div.appendChild(incdec(\"s\", viewof s));\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":550,"value":"md`## Credits and Helper functions:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":553,"value":"md`Thanks to @mbostock and @jashkenas for js help. Thanks to Vincent Pigno for the inspiration.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":581,"value":"crit_data = {\n let criterion_data = []\n for (var i = 1; i <= (p-1)/2; i++) { \n for (var j = 1; j <= p-1; j++) { \n let local_elements_images_residues_mod_n = elements.map(function(e) { \n return (i*(e)**j)%p;\n }).map(function(g) { \n return g%n;\n })\n let pairs = zip([elements_residues_mod_n, local_elements_images_residues_mod_n])\n\t\tfunction equal(pair) {\n \t\treturn pair[0]==pair[1];\n\t\t}\n \n \tcriterion_data.push(\n {\n 'a': i,\n 'k': j,\n\t 'criterion': pairs.every(equal)\n }\n );\n }\n }\n return criterion_data\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":584,"value":"primes_below_250 = getPrimes(250)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":423,"value":"prime_crit_data = {\n let criterion_data = []\n for (var i = 1; i <= (q-1)/2; i++) { \n for (var j = 1; j <= q-1; j++) { \n let local_elements_images_residues_mod_s = [...Array(q).keys()].map(function(e) { \n return (i*(e)**j)%q;\n }).map(function(g) { \n return g%s;\n })\n let pairs = zip([\n [...Array(q).keys()].map(function(e) { \n\t\t\t return e%s;\n\t\t\t}), local_elements_images_residues_mod_s])\n\t\tfunction equal(pair) {\n \t\treturn pair[0]==pair[1];\n\t\t}\n \n \tcriterion_data.push(\n {\n 'a': i,\n 'k': j,\n\t 'criterion': pairs.every(equal)\n }\n );\n }\n }\n return criterion_data\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":413,"value":"q = primes_below_250[m-1]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":291,"value":"height = 350","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":516,"value":"function incdec(name, view) {\n const form = html``;\n form.inc.addEventListener(\"click\", () => update(view, view.value + 1));\n form.dec.addEventListener(\"click\", () => update(view, view.value - 1));\n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":514,"value":"function update(view, value) {\n view.input.value = value;\n view.dispatchEvent(new CustomEvent(\"input\"));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":214,"value":"function zip(arrays) {\n return arrays[0].map(function(_,i){\n return arrays.map(function(array){return array[i]})\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":383,"value":"function getPrimes(max) {\n var sieve = [], i, j, primes = [];\n for (i = 2; i <= max; ++i) {\n if (!sieve[i]) {\n // i has not been marked -- it is prime\n primes.push(i);\n for (j = i << 1; j <= max; j += i) {\n sieve[j] = true;\n }\n }\n }\n return primes;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":134,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":350,"value":"import {number} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":283,"value":"d3 = require(\"https://d3js.org/d3.v5.min.js\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W33","stdlib":"1","titling":"auto"}} 32:"$31:body"