Timeline for Positive definite quadratic form algorithm
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 14, 2023 at 5:47 | comment | added | Watson Ladd | This is a norm equation for $\mathbb{Q}[\sqrt{p}]$. So I would consider looking at the factorization of $m$ in the ring of integers and taking possible products, then screening out the ones that don't form integers. This is tedious to do and there's a bunch of fun if not a PID, but with Pari shouldn't be hard to sort out. | |
| Oct 18, 2023 at 13:23 | comment | added | ReverseFlowControl | @NoamD.Elkies Sorry, it need NOT be deterministic. G.Melfi the number of "unique" solutions is roughly proportional to the number of factors of $m$, something like that, that is why the condition that $m$ have at least two prime factors. Of course, two odd prime factors....we don't care for $2$ as a factor. | |
| Oct 18, 2023 at 12:35 | comment | added | G. Melfi | In certain cases there is no a second solution. Let's take $x^2+3y^2=63$. The only solution is $(x,y)=(\pm6,\pm3)$. So possibly the algorithm, if it exists, is supposed to find a second solution OR to find that there are no other solutions. | |
| Oct 17, 2023 at 22:51 | history | edited | YCor | CC BY-SA 4.0 |
removed capitals from title
|
| Oct 17, 2023 at 22:44 | comment | added | ReverseFlowControl | @NoamD.Elkies Integer solutions. The algorithm need to be deterministic, but better than $\mathcal{O}(m^2)$ or even $\mathcal{O}(x_0y_0)$ would be very nice. | |
| Oct 17, 2023 at 22:40 | history | edited | ReverseFlowControl | CC BY-SA 4.0 |
Spicifying solution space and algorithm requirements.
|
| Oct 17, 2023 at 21:09 | comment | added | Noam D. Elkies | are you looking for integer or rational solutions? Must the algorithm be determinstic? | |
| Oct 17, 2023 at 20:52 | comment | added | Mastrem | Draw a line between $(x_0,y_0)$ and an arbitrary second point, and compute the intersection between this line and the ellipse $x^2+py^2=m$? You should be able to parameterize all solutions using this approach, I think. | |
| Oct 17, 2023 at 20:39 | history | asked | ReverseFlowControl | CC BY-SA 4.0 |