29:null 2a:["$","title",null,{"children":"Images of monomials over Z_p mod n (Fork for the forums) | Jeremy Ashkenas | Observable"}] 2f:[] 2d:{"id":"3a27be966fb4d01f","slug":"images-of-monomials-over-z_p-mod-n-fork-for-the-forums","title":"Images of monomials over Z_p mod n (Fork for the forums)","thumbnail":"3283b4c26f63f7cb1c80a0c7e69a78bf893e999e76acdeedfd4ecf9846592ed4","access_level":"public","create_time":"$D2018-03-28T19:52:48.139Z","update_time":"$D2018-03-28T19:53:11.443Z","view_time":null,"first_public_time":"$D2018-03-28T19:53:14.894Z","has_unpublished_edits":null,"fork":{"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`}","owner":{"id":"a8afac7fc0f0a766","login":"bbischof","name":"Bryan"}},"stars":0,"starred":false,"owner":{"type":"team","id":"172cc08ef8a18a4b","login":"jashkenas","name":"Jeremy Ashkenas","avatar_url":"https://avatars-next.observableusercontent.com/fa1903f8171d4621ef49de28e0ff1fb965960ec87df175d8b543c4b09508b45b","tier":"starter_2024"},"version":545,"publish_version":545,"role":null,"authored":false,"authors":[{"type":"individual","id":"783616ba9fb55f5d","login":"jashkenas","name":"Jeremy Ashkenas","avatar_url":"https://avatars-next.observableusercontent.com/fa1903f8171d4621ef49de28e0ff1fb965960ec87df175d8b543c4b09508b45b","tier":null}],"members":[{"type":"individual","id":"783616ba9fb55f5d","login":"jashkenas","name":"Jeremy Ashkenas","avatar_url":"https://avatars-next.observableusercontent.com/fa1903f8171d4621ef49de28e0ff1fb965960ec87df175d8b543c4b09508b45b","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Images of monomials over Z_p mod n (Fork for the forums)","cells":[{"id":0,"value":"md`# Images of monomials over Z_p mod n (Fork for the forums)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":473,"value":"\ntex.block`\\text{Consider a cyclic group }\n\\mathbb{Z}_p\n\\text{, and all of it's elements as integers}\\mod n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":487,"value":"tex.block`\\text{Now consider a monomial of the form }f(x)=ax^k \n\\text{ over the group.}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":492,"value":"tex.block`\\text{Consider the images of this monomial }\\mod n\n\\text{. When do }x \\text{ and }f(x) \n\\text{have the same residue }\\mod n\n\\text{?}\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: 10,\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: 1,\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\", viewof 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: 1,\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: 1,\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":"tex.block`\\text{So, we're using the monomial: }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 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\t// let pairwise_binaries = pairs.map(function(a,b) { \n\t// return a[0]==a[1];\n\t// })\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":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":369,"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":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":385,"value":"primes_below_250 = getPrimes(250)","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: 10,\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: 1,\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: 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":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":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":509,"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":499,"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":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":"$W2f","stdlib":"1","titling":"auto"}} 2e:"$2d:body"