22:null 23:["$","title",null,{"children":"Elliptic curves: counting solutions | Yao Liu | Observable"}] 28:T45a,md`Geometrically, we are asking if the curve passes through any integer points. You can zoom in and out to look, and you can easily spot a number of solutions: ${tex`(0,0), (0, -1), (1, 0)`}, etc. Try change the equation (say, add a \`+1\` in the code) and see if you can still see any solutions. It is easy to run a script to check, starting with small numbers, but you can't know for sure if you've found all the solutions this way as the curve clearly is going off to infinity. However, we can do a lot of numerical experiments based on a simple observation, which is at the basis of much of Diophantine analysis: if there exists an integer solution, then we could "reduce the equation modulo ${tex`n`}" for any ${tex`n`}, and obtain an equation of the "remainders" — or in fancier language, over the ring ${tex`\mathbb Z/n\mathbb Z`}. To turn it around, if there is a single ${tex`n\geq 2`} such that the equation does *not* have a solution in ${tex`\mathbb Z/n\mathbb Z`} (for which there are only finitely many pairs ${tex`(x,y)`} to check), then it can't possibly have a solution over ${tex`\mathbb Z`}. `29:T44f,data = { let primes = [], mod_n = ['0', '1'], N_p = [], a_p = [], prime_powers = [], N_q = [] yield visibility() let n = 1 while (n < max) { n++; let count = 0; for (let x=0; x\frac{3}{2}`}, ${tex`\varepsilon_p = 1`} for all but finitely many primes (and ${tex`\varepsilon_p = 0`} for those exceptions), and ${tex`a_n`} for non-prime ${tex`n`} may then be computed from the ${tex`a_p`}'s by *formally* expanding the above. If we *formally* plug in ${tex`s=1`}, we get ${tex.block`L_E(1) \sim \prod_p \frac{1}{1-a_p p^{-1} + p^{-1}} = \prod_p \frac{p}{p-a_p+1} = \prod_p \frac{p}{N_p} `} which is what Birch and Swinnerton-Dyer considered. One of consequences of the work of Wiles et al., now called the modularity theorem (that the coefficients ${tex`a_n`} come from the ${tex`q`}-expansion ${tex`\sum_n a_n q^n`} of some modular form), is that ${tex`L_E`} can be analytically continued to all ${tex`s\in\mathbb C`}, in particular near ${tex`s=1`}. Now the Birch-Swinnerton-Dyer conjecture can be stated precisely: for any elliptic curve ${tex`E`}, the rank of ${tex`E`} is equal to the order of vanishing of ${tex`L_E`} at ${tex`s=1`}. `2b:[] 26:{"id":"93ecec773dbee40e","slug":"elliptic-curves-counting-solutions/3","title":"Elliptic curves: counting solutions","thumbnail":"55d24c756badd35c8fe86fb369aded549cbfeb84ba451e976bad68a32e36e1d0","access_level":"public","create_time":"$D2018-03-28T21:05:32.013Z","update_time":"$D2019-09-14T14:20:03.302Z","view_time":null,"first_public_time":"$D2018-03-28T21:09:17.305Z","has_unpublished_edits":null,"fork":true,"stars":5,"starred":false,"owner":{"type":"team","id":"490427fcc4ec2c1d","login":"liuyao12","name":"Yao Liu","avatar_url":"https://avatars-next.observableusercontent.com/895964f8b86922c183ea757cd86944e8e9d463ef5ba08171fab539d4dc087c54","tier":"starter_2024","bio":""},"version":1730,"publish_version":1730,"role":null,"authored":false,"authors":[{"type":"individual","id":"ae908de8dd38723a","login":"liuyao12","name":"Yao Liu","avatar_url":"https://avatars-next.observableusercontent.com/895964f8b86922c183ea757cd86944e8e9d463ef5ba08171fab539d4dc087c54","tier":null,"bio":""}],"members":[{"type":"individual","id":"ae908de8dd38723a","login":"liuyao12","name":"Yao Liu","avatar_url":"https://avatars-next.observableusercontent.com/895964f8b86922c183ea757cd86944e8e9d463ef5ba08171fab539d4dc087c54","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":{"id":"a9b28604131db162","slug":"number-theory","title":"prime numbers","owner":{"id":"490427fcc4ec2c1d","login":"liuyao12","name":"Yao Liu"}},"type":"notebook","body":{"titling":"auto","title":"Elliptic curves: counting solutions","cells":[{"id":0,"value":"md`# Elliptic curves: counting solutions\n\nHave you seen this meme?\n\n![](https://qph.fs.quoracdn.net/main-qimg-5b0690e302a38cf2a8068158199e7a21-c)\n\nGo read [Alon Amit's answer on Quara](http://qr.ae/TU8mdu). I don't want to just repeat everything there in an interactive fashion, so this will go down a somewhat different direction.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":223,"value":"md`## Diophantine equations\n\nNamed after Diophantus of Alexandria, a Diophantine equation is an algebraic equation (of any number of unknowns) in which one is only concerned with *integer* solutions. One of the first famous examples was solved by Euclid, who gave a simple procedure (almost certainly known to Babylonians) to generate *all* Pythagorean triples:\n${tex.block`x^2+y^2=z^2`}\nand there are infinitely many solutions.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"md`In hindsight, it comes down to the \"geometric\" fact that quadratic curves such as ${tex`x^2+y^2=1`} are *rational* (aka genus 1), in the sense that they can be parametrized by rational functions (of another variable): ${tex.block`x=\\frac{2t}{1+t^2} \\qquad y=\\frac{1-t^2}{1+t^2}`}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":63,"value":"texmd`That is not to say all questions about quadratic equations are easy to answer. For example, given a (large) number $n$, how do we know if it can be written as the sum of two squares: $n=x^2+y^2$? There is a simple criterion if we know $n$ is prime (or know its factorization) to decide yes or no instantly (attributed to Fermat, and many proofs have been given—starting with Euler and Gauss, and more recently Zagier), but when yes, it's a lot harder to find the $x$ and $y$.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":847,"value":"texmd`It would be a sin not to mention Fermat's Last Theorem, which asserts that there are no (nonzero) integer solutions to $$x^n + y^n = z^n$$ when $n>2$. It was one of the most famous unsolved problems in mathematics until Andrew Wiles and Richard Taylor settled it in 1995 by proving a certain remarkable conjecture about elliptic curves (that is too technical to explain). It just shows how a simple-looking Diophantine equation can be extremely difficult.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1416,"value":"md`The following are some of the standard questions one may ask about a Diophantine equation, with varying degrees of difficulty:\n\n1. Does the equation have a solution?\n2. Does it have a \"non-trivial\" solution?\n3. How many solutions does it have (finite or infinite)?\n4. How do we find *all* of them?\n5. Any good algorithms to answer any of the above?`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":132,"value":"md`## Elliptic curves\n\nA lot of interests are centered on cubic equations (of two unknowns) that are not rational, e.g. \n${tex.block`y^2+y=x^3-x`}\n(In words: \"Does the product of two consecutive numbers ever equal the product of three consecutive numbers?\")`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1089,"value":"{\n let target = DOM.element('div');\n functionPlot({\n xAxis: {domain: [-3, 3]},\n grid: true,\n data: [{\n fn: 'y^2 + y - (x^3 - x)',\n fnType: 'implicit'\n }],\n target\n });\n return target;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":942,"value":"$28","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":238,"value":"md`Here's the script that counts the number of solutions modulo ${tex`n`} for ${tex`n\\leq ${max}`}, and you can change the equation to anything you want. (Not necessarily cubic; and, with simple modification, even in three or more variables).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":913,"value":"max = 1000","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":93,"value":"$29","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":456,"value":"{ \n var composite_plot = {\n x: [...data.mod_n.keys()],\n y: data.mod_n,\n name: 'composite',\n mode: 'markers',\n type: 'scatter',\n hovermode: 'closest'\n }\n \n var prime_plot = {\n x: data.primes,\n y: data.N_p,\n name: 'prime',\n mode: 'markers',\n type: 'scatter'\n }\n \n var prime_power_plot = {\n x: data.prime_powers,\n y: data.N_q,\n name: 'prime power',\n mode: 'markers',\n type: 'scatter'\n }\n var layout = {\n width: 800,\n title: \"# of solutions mod n\"\n }\n \n const div = DOM.element('div');\n Plotly.newPlot(div, [composite_plot, prime_plot, prime_power_plot], layout);\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":113,"value":"md`What happens if you don't see any zeros? It would be \"strong evidence\" that the equation does have an integer solution (and the calculation probably already found it), but that's no guarantee. The only thing you can be certain of is that there are only finitely many integer solutions; that's a theorem of Siegel, but unfortunately it doesn't tell us where to search for them. For specific curves, there are various things that could help us find all the integer solutions conclusively. According to [LMFDB dabase](http://www.lmfdb.org/EllipticCurve/Q/37/a/1), our example has exactly 10 solutions.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":187,"value":"md`You might say that most of these solution counts are fake if the equation only has 10 actual solutions in ${tex`\\mathbb Z`}. But these data turn out to hold important information about the elliptic curve. As you can see, when ${tex`n=p`} is prime (the ring ${tex`\\mathbb Z/p\\mathbb Z`} is a field, often denoted ${tex`\\mathbb F_p`}), the solution counts are a lot more orderly, following closely the straight line of slope 1. If we just look at the deviation from the line, we'd see this:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":663,"value":"Hasse = { \n var a_p_plot = {\n x: data.primes,\n y: data.a_p.map(x => -x),\n name: 'N_p - p',\n mode: 'markers',\n type: 'scatter',\n color: 'orange'\n }\n \n \n let X = []\n let Y = []\n for (let x=max; x>=0; x--) X.push(x), Y.push(-2*Math.sqrt(x))\n for (let x=0; x<=max; x++) X.push(x), Y.push(2*Math.sqrt(x))\n \n var parabola = {\n x: X,\n y: Y,\n name: '±2√p',\n mode: 'line',\n line: {\n dash: 'solid',\n width: 1,\n color: 'DeepSkyBlue'\n },\n hoverinfo: 'none'\n }\n \n var layout = {\n width: 800,\n xaxis: {domain: [0, max]}\n }\n \n const div = DOM.element('div');\n Plotly.newPlot(div, [parabola, a_p_plot], layout);\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":691,"value":"md`Let ${tex`N_p`} denote the number of solutions modulo ${tex`p`}, then Hasse proved in 1933 that\n\n${tex.block`|N_p - p| \\leq 2 \\sqrt p `}\n\nfor *all* primes ${tex`p`}. The error term, for some reason defined as ${tex`a_p := p - N_p`}, turns out to be more interesting than it might seem at first. (You might see elsewhere that the definition of ${tex`a_p`} comes with an extra ${tex`+1`}; that is when the count ${tex`N_p`} is taken to include the \"point at infinity.\") `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":349,"value":"md` ## Sato-Tate\n\nOne might then ask how the numbers ${tex`a_p`} are distributed within the Hasse bound, or in other words how\n${tex`\\dfrac{a_p}{2\\sqrt p}`} are distributed between ${tex`\\pm 1`}. I'm running a separate script that computes ${tex`a_p`} for primes up to 10000, and put the values in a histogram: `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":795,"value":"Sato_Tate = {\n let n = 1, primes = [], ap_normalized = [], BSD = 1, BSDs = [];\n yield visibility()\n while (n < 100) {\n n++;\n \n let n_is_prime = true;\n let sqrt = Math.floor(Math.sqrt(n))\n for (let i = 0; i < primes.length & primes[i] <= sqrt; i++) {\n if (n % primes[i] == 0) {\n n_is_prime = false;\n break;\n }\n }\n if (n_is_prime) {\n let p = n\n primes.push(p)\n let count = 0;\n for (let x=0; x p`} would happen more often sooner, such that the product\n${tex.block`\\prod_p \\frac{N_p}{p}`}\ntends to infinity. Their computations led them to the conjecture that\n${tex.block`\\prod_{p