Timeline for Defining a sign of square roots in GF(p)
Current License: CC BY-SA 4.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 25, 2023 at 20:06 | comment | added | KConrad | I made an error in an earlier comment when describing squarefree parts. What you call "squarefree core" is what the term "squarefree part" means. see oeis.org/A007913, for instance. What I had mistakenly called the squarefree part above (the product of all the different primes factors of a positive integer) is really called its radical. | |
| Nov 25, 2023 at 18:50 | comment | added | KConrad | The main algorithmic issue is determining generators of $I$. The other part of the theorem (checking $f_j(\alpha_1,\ldots,\alpha_n) = 0$ for all $j$) just has to be checked for each list of $\alpha_i$'s to see if all those evaluations at them vanish. When working over a field, a standard way to determine a generating set for an ideal is to use Grobener bases. Look around to see if that idea can be extended to polynomials over a PID like $\mathbf Z$. | |
| Nov 25, 2023 at 18:43 | history | edited | KConrad | CC BY-SA 4.0 |
added 4 characters in body
|
| Nov 25, 2023 at 18:34 | comment | added | Oleksandr Kulkov | Thanks, I think it's a significant improvement! Is there some feasible algorithmic way to find generators of $I$ and choose $\alpha_i$ in a way that the theorem condition is satisfied? | |
| Nov 25, 2023 at 17:46 | comment | added | KConrad | I rewrote the later part of my answer, starting in paragraph 5, to pay more attention to the ideal $I$ of relations among the square roots (i.e., the kernel of the evaluation map $\mathbf Z[x_1,\ldots,x_n]\to\mathbf Z[\sqrt{a_1},\ldots,\sqrt{a_n}]$ where $x_i\mapsto \sqrt{a_i}$ for all $i$). The method I describe for building ring homomorphisms $\mathbf Z[\sqrt{a_1},\ldots,\sqrt{a_n}]\to\mathbf F_{p^2}$ using generators of the ideal $I$ is applicable to all choices of $a_1,\ldots,a_n$. The description I had before was really only applicable when $a_1,\ldots,a_n$ are independent mod squares. | |
| Nov 25, 2023 at 17:37 | history | edited | KConrad | CC BY-SA 4.0 |
added 3313 characters in body
|
| Nov 25, 2023 at 16:39 | comment | added | KConrad | Ok, the squarefree core is the complement to the largest square divisor of a number. | |
| Nov 25, 2023 at 10:40 | comment | added | Oleksandr Kulkov | No, I mean that if $a = x^2 y$, where $x$ is the largest possible, then $y$ is the squarefree core. So, for $600$ it would be $3$. I essentially mean that we can pick square roots in the larger domain, and then define the remaining stuff to be consistent with them. | |
| Nov 25, 2023 at 3:19 | comment | added | KConrad | I ask because those squarefree parts don't have to have their square roots in $\mathbf Z[\sqrt{a_1},\ldots,\sqrt{a_n}]$. This already happens when $n = 1$, e.g., $\sqrt{2} \not\in \mathbf Z[\sqrt{8}]$. But as long as a prime $p$ doesn't divide the product $A := a_1\ldots a_n$ (e.g., when $p > A$), a ring homomorphism $\mathbf Z[\sqrt{a_1},\ldots,\sqrt{a_n}] \to \mathbf F _{p^2}$ extends uniquely to a ring homomorphism $\mathbf Z[1/A][\sqrt{a_1},\ldots,\sqrt{a_n}] \to \mathbf F _{p^2}$ and that larger domain does contain $\sqrt{d}$ when $d$ is any divisor of $A$. | |
| Nov 25, 2023 at 3:13 | comment | added | KConrad | Does "squarefree core" mean squarefree part, e.g., $600 = 2^3 \cdot 3 \cdot 5^2$ has squarefree part $2 \cdot 3 \cdot 5 = 30$? | |
| Nov 25, 2023 at 0:59 | vote | accept | Oleksandr Kulkov | ||
| Nov 25, 2023 at 0:59 | comment | added | Oleksandr Kulkov | Ah, I see what you meant now. Yeah, that makes sense. And to make a homomorphism from $\mathbb Z[\sqrt{a}, \sqrt{b}, \sqrt{c}]$ it seems possible to workaround with square-free cores and their prime divisors of $a,b,c$. Thanks, I think my understanding of what's going on here advanced a lot :) | |
| Nov 25, 2023 at 0:28 | comment | added | KConrad | The possible failure of a ring isomorphism at the end is entirely due to possible multiplicative relations among $a, b, c$ modulo squares. | |
| Nov 25, 2023 at 0:26 | comment | added | KConrad | Using $n=3$, there is total freedom in writing down ring homs $\varphi : \mathbf Z[x,y,z]\to\mathbf F_9$ by sending $x$, $y$, and $z$ anywhere. Pick $a,b,c$ in $\mathbf Z$ and then $\alpha,\beta,\gamma\in\mathbf F_9$ so $\alpha^2=a$, $\beta^2=b$, and $\gamma^2=c$ in $\mathbf F_9$. Then we get a ring hom $\overline{\varphi} : \mathbf Z[x,y,z]/(x^2-a,y^2-b,z^2-c)\to\mathbf F_9$ where $\overline{\varphi}(x)=\alpha$, $\overline{\varphi}(y)=\beta$, and $\overline{\varphi}(z)=\gamma$. The catch: $\mathbf Z[x,y,z]/(x^2-a,y^2-b,z^2-c)$ may not be isomophic to $\mathbf Z[\sqrt{a},\sqrt{b},\sqrt{c}]$ | |
| Nov 25, 2023 at 0:16 | comment | added | Oleksandr Kulkov | I guess what we really want here is to choose (any) square root in $\mathbb F_{p^2}$ for each square-free equivalence class representative from $\langle a_1, \dots, a_n \rangle$ in $\mathbb Q^\times / (\mathbb Q^\times)^2$, and define the remaining part of the homomorphism to be consistent with it, rather than picking square roots for $a_1, \dots, a_n$ directly? Or maybe even choose the square root for each prime number occuring in $a_1, \dots, a_n$ to be safe... | |
| Nov 24, 2023 at 23:25 | comment | added | Oleksandr Kulkov | Or, rather, for any $\alpha_i$ the homomorphism is unique if it exists, but it might as well not exist at all for a given choice of $\alpha_i$ (i.e. the condition $\alpha_i^2 = a_i$ is not sufficient for it to exist)? | |
| Nov 24, 2023 at 23:20 | comment | added | Oleksandr Kulkov | Yes, $\mathbb F_3[x]$, sorry. What I mean is, ring homomorphism should preserve additive relations, right? That is, $f(\sqrt{2}+\sqrt{8}-\sqrt{18}) = f(\sqrt{2})+f(\sqrt{8})-f(\sqrt{18})$. But here we have $\sqrt{2}+\sqrt{8}-\sqrt{18}=0$, while $f(a)+f(b)-f(c)=\alpha_1+\alpha_2-\alpha_3=2x \neq 0$. So, when we map to $\alpha_i$ chosen this way, the resulting map is, in fact, not a homomorphism, it seems? Because it doesn't map $0$ to $0$. I probably missed something, but I can't see what. | |
| Nov 24, 2023 at 23:12 | comment | added | KConrad | You meant $\mathbf F_3[x]/(x^2-2)$, not $\mathbf F_3/(x^2-2)$. Anyway, reread what I wrote: I did not pick a linear relation first. I picked $\alpha_i$ where $\alpha_i^2 = a_i$ for all $i$ and then got a ring hom $\mathbf Z[\sqrt{2},\sqrt{8},\sqrt{18}] \to \mathbf F_9$ where $\sqrt{a_i} \mapsto \alpha_i$ first. If you want certain relations among $\alpha_i$ to occur, then you have to hunt around for a suitable choice of ring homomorphism. | |
| Nov 24, 2023 at 22:38 | comment | added | Oleksandr Kulkov | Thanks for the clarification! Let's say that $p=3$. Consider $a_1 = 2, a_2 =8, a_3 = 18$. Then, $\sqrt{a_1} + \sqrt{a_2}-\sqrt{a_3} = 0$. Now, let's say that $\mathbb F_{9}$ is represented as $\mathbb F_3 / (x^2-2)$. Consider $\alpha_1 = \alpha_2 = x$ and $\alpha_3 = 0$, then $\alpha_k^2 = a_k$ for all $k$, but $\alpha_1 + \alpha_2 - \alpha_3 = 2x \neq 0$ in $\mathbb F_{9}$. Thus, we can't just use any $\alpha_k$ to construct the homomorphism. Is there any way to decide between $\alpha_k$ and $-\alpha_k$ for each $k$, so that the result is, in fact, a homomorphism? | |
| Nov 24, 2023 at 15:58 | comment | added | KConrad | See the three paragraphs I added at the end. Every mapping of the square roots $\sqrt{a_i}$ to $\mathbf F_{p^2}$ that preserves all additive and multiplicative relations among the square roots comes from a choice of prime ideal $\mathfrak p$ containing $p$ in the ring $\mathbf Z[\sqrt{a_1},\ldots,\sqrt{a_n}]$. This is not as concrete as you may wish, but it is a very useful to think about how all the mappings that interest you arise. | |
| Nov 24, 2023 at 15:48 | history | edited | KConrad | CC BY-SA 4.0 |
added 2520 characters in body
|
| Nov 24, 2023 at 12:16 | comment | added | Oleksandr Kulkov | Thanks, but I don't think it answers the question? What I'm asking is, to find a mapping from $\{\sqrt{a_1},\dots,\sqrt{a_n}\}$ into $\operatorname{GF}(p^2)$ such that it preserves certain identities (e.g. if original linear combination is zero, so must be the one after the mapping is applied). Unfortunately the stuff that you mention doesn't seem to be constructive (i.e. it proves that there is some equivalence, but doesn't seem to give it explicitly). | |
| Nov 24, 2023 at 2:34 | history | answered | KConrad | CC BY-SA 4.0 |