Defining a sign of square roots in GF(p)

Question

$\DeclareMathOperator\GF{GF}$Consider the following expression:

$$ \sqrt{a_1} \pm \sqrt{a_2} \pm \dots \pm \sqrt{a_n} = 0, $$

where $a_1, \dots, a_n$ are positive integers. We want to find the number of ways to change each $\pm$ into $+$ or $-$, so that the equation is true.

One way to approach this problem is to pick a sufficiently large random prime number $p$, then find all the square roots in $\GF(p^2)$ (they always exist), and then count the number of ways to satisfy the equation in $\GF(p^2)$.

With high probability, the answer in $\GF(p^2)$ will be the same as in $\mathbb R$. But at the same time, it seems much harder to actually recover such combinations in $\mathbb R$ if they're known in $\GF(p^2)$.

That being said, assume that you know for sure that a particular combination of square roots in $\GF(p^2)$ satisfies the equation. Is there any way to, using this information, recover any such combination that satisfies it in $\mathbb R$?

I guess, what I'm actually asking is, given $p$, I want to algorithmically map each number from $1$ to $p-1$ to one of its two square roots in $\GF(p^2)$ so that by substituting each $\sqrt{a_i}$ via this mapping in the expression above, I will be able to check with high probability that this specific way of changing $\pm$ to $+$ or $-$ is also valid in $\mathbb R$.

Answer 1

I'm not sure why you emphasize linear combinations with coefficients $\pm 1$ to the exclusion of other possible rational coefficients.

In any case, the degree $d=[\mathbf Q(\sqrt{a_1},\ldots,\sqrt{a_n}):\mathbf Q]$ is the order of $\langle a_1,\ldots,a_n\rangle$ in $\mathbf Q^\times/(\mathbf Q^\times)^2$, so it is a power of $2$ that is basically counting how multiplicatively independent the $a_i$'s are modulo rational squares. An approach to proving that multiplicative independence of $a_i$'s mod squares implies their square roots are linearly independent over $\mathbf Q$ by using reduction mod $p$ for a large prime $p$ can be read here.

(Update) In the ring $\mathbf Z[\sqrt{a_1},\ldots,\sqrt{a_n}]$, each nonzero prime ideal $\mathfrak p$ gives us a quotient ring $\mathbf Z[\sqrt{a_1},\ldots,\sqrt{a_n}]/\mathfrak p$, which is a finite field whose characteristic $p$ is the prime number such that (i) $\mathfrak p \cap \mathbf Z = p\mathbf Z$ or (ii) $(p)\subset\mathfrak p$ as ideals (these are equivalent properties). That finite field is called the residue field at $\mathfrak p$. Because $\sqrt{a_i}^2 = a_i$ in the ring, we have $\sqrt{a_i}^2 \equiv a_i \bmod \mathfrak p$ in the residue field. The residue field at $\mathfrak p$ is generated as a ring by all $\sqrt{a_i} \bmod \mathfrak p$, so this field is either $\mathbf F_p$ or $\mathbf F_{p^2}$, and it is $\mathbf F_p$ if and only if all $a_i \bmod p$ are squares in $\mathbf F_p$. The density of primes $p$ such that all $a_i \bmod p$ are squares in $\mathbf F_p$ is $1/d$ where $d$ is the degree $[\mathbf Q(\sqrt{a_1},\ldots,\sqrt{a_n}):\mathbf Q]$ I mentioned earlier (a certain power of $2$).

Any $\mathbf Z$-linear relation $c_1\sqrt{a_1}+\ldots+c_n\sqrt{a_n}=0$ in the ring leads to an $\mathbf F_p$-linear relation $c_1\sqrt{a_1}+\ldots+c_n\sqrt{a_n} \equiv 0 \bmod \mathfrak p$ in the residue field at $\mathfrak p$. This is a good way to carry out the process of turning a relation in characteristic $0$ into a relation in characteristic $p$.

In fact, all ways of picking a square root of each $a_i \bmod p$ in $\mathbf F_{p^2}$ that are consistent with all relations among the numbers $\sqrt{a_1},\ldots,\sqrt{a_n}$ arise from some choice of prime ideal $\mathfrak p$ where $(p) \subset \mathfrak p$. There is a unique ring homomorphism $$ \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$. Let $I$ be its kernel, an ideal, so we get an induced ring isomorphism $$ \mathbf Z[x_1,\ldots,x_n]/I \to \mathbf Z[\sqrt{a_1},\ldots,\sqrt{a_n}]. $$

The ideal $I$ contains $x_i^2-a_i$ for all $i$, so $I$ contains $(x_1^2-a_1,\ldots,x_n^2-a_n)$, and $I$ could be bigger. Two examples: $\mathbf Z[\sqrt{2},\sqrt{3}] \cong \mathbf Z[x,y]/(x^2-2,y^2-3)$ and $\mathbf Z[\sqrt{2},\sqrt{8}] \cong \mathbf Z[x,y]/(x^2-2,y^2-8,2x-y)$.) The polynomials in $I$ are all polynomials in $x_1,\ldots,x_n$ that vanish when we set $x_i = \sqrt{a_i}$ for all $i$, so $I$ tells us all the algebraic relations among $\sqrt{a_1},\ldots,\sqrt{a_n}$. A set of generators of $I$ is a set of relations among those square roots that explain all other relations among those square roots. In the ideal (ha-ha) situation that $a_1,\ldots,a_n$ are independent modulo squares, $I = (x_1^2-a_1,\ldots,x_n^2-a_n)$ by a counting argument whose details I omit.

Now let's try to work out what the ring homomorphisms $\mathbf Z[\sqrt{a_1},\ldots,\sqrt{a_n}] \to \mathbf F_{p^2}$ are. A subtlety is that we may not be able to send each $\sqrt{a_i}$ to either square root of $a_i \bmod p$ in $\mathbf F_{p^2}$ independently because relations among the numbers $\sqrt{a_i}$ might not be preserved among their images. As an example, say we're trying to build a ring homomorphism $\mathbf Z[\sqrt{2},\sqrt{8}] \to\mathbf F_{p^2}$. Since $\sqrt{8} = 2\sqrt{2}$, we have to make sure that the square roots of $2$ and $8$ that we use as target values in $\mathbf F_{p^2}$ have the same relation "$\beta = 2\alpha$". Being careless about which square roots we use $\mathbf F_{p^2}$ might not have this relation hold (perhaps $\beta = -2\alpha$).

This is why it is convenient to use the ring isomorphism $$ \mathbf Z[x_1,\ldots,x_n]/I \to \mathbf Z[\sqrt{a_1},\ldots,\sqrt{a_n}]. $$ The ring homomorphisms $\mathbf Z[\sqrt{a_1},\ldots,\sqrt{a_n}] \to \mathbf F_{p^2}$ can be viewed as the ring homomorphisms $\mathbf Z[x_1,\ldots,x_n]/I \to \mathbf F_{p^2}$, which are the same thing as the ring homomorphisms $\varphi : \mathbf Z[x_1,\ldots,x_n] \to \mathbf F_{p^2}$ that are $0$ on $I$. Every ideal in $\mathbf Z[x_1,\ldots,x_n]$ is finitely generated, and when $I = (f_1,\ldots,f_r)$, having $\varphi = 0$ on all of $I$ is the same thing as having $\varphi(f_j) = 0$ for $j = 1,\ldots,r$.

Using generators of the ideal $I$, we can say exactly which choices of square roots of $a_i$ in the finite field $\mathbf F_{p^2}$ occur as images of $\sqrt{a_i}$.

Theorem. Let $I = (f_1,\ldots,f_r)$. Then for each choice of $\alpha_i \in \mathbf F_{p^2}$ such that $\alpha_i^2 = a_i$, there is a ring homomorphism $\mathbf Z[\sqrt{a_1},\ldots,\sqrt{a_n}] \to \mathbf F_{p^2}$ such that $\sqrt{a_i} \mapsto \alpha_i$ if and only if $f_j(\alpha_i,\ldots,\alpha_n) = 0$ in $\mathbf F_{p^2}$ for $j=1,\ldots,r$.

Example. When $a_1,\ldots,a_n$ are independent modulo squares, so $I = (x_1^2-a_1,\ldots,x_n^2-a_n)$, every choice of $\alpha_i$ in $\mathbf F_{p^2}$ such that $\alpha_i^2 = a_i$ can be used to define a ring homomorphism $\mathbf Z[\sqrt{a_1},\ldots,\sqrt{a_n}] \to \mathbf F_{p^2}$.

Example. We have $\mathbf Z[\sqrt{2},\sqrt{8}]\cong \mathbf Z[x,y]/(x^2-2,y^2-8,2x-y)$, so a choice of $\alpha$ and $\beta$ in $\mathbf F_{p^2}$ such that $\alpha^2 = 2$ and $\beta^2 = 8$ can be used to define a ring homomorphism $\mathbf Z[\sqrt{2},\sqrt{8}] \to \mathbf F_{p^2}$ if and only if $2\alpha = \beta$.

In the general case, once we have a ring homomorphism $$ \mathbf Z[\sqrt{a_1},\ldots,\sqrt{a_n}]\to \mathbf F_{p^2} $$ where $\sqrt{a_i} \mapsto \alpha_i$ for all $i$, its kernel has to be a nonzero prime ideal, say $\mathfrak p$, so we get an induced ring embedding $$ \mathbf Z[\sqrt{a_1},\ldots,\sqrt{a_n}]/\mathfrak p \hookrightarrow \mathbf F_{p^2} $$ with image $\mathbf F_p$ or $\mathbf F_{p^2}$ in which $\sqrt{a_i} \bmod \mathfrak p$ is mapped to $\alpha_i$ for all $i$. This does not just preserve additive relations among all $\sqrt{a_i}$ when going from characteristic zero to characteristic $p$, but all multiplicative relations as well (it is a ring homomorphism).

Answer 2

@KConrad provided a lot of useful details in his answer that also helped me better understand what's going on here and what I want from the problem exactly. I'd like to use a separate answer to summarize what I find most relevant to this specific question, and also provide a bit more details on the algorithmic part.

In essence, what I was looking for boils down to finding a non-trivial homomorphism $$ f: \mathbb Z\sqrt{a_1}+ \dots+ \mathbb Z\sqrt{a_n} \to \mathbb F_{p^2}. $$ The original question only bothers about preservation of additive expressions (so, like a module homomorphism), so to simplify the answer I won't consider preservation of multiplicative properties here.

It simplifies the situation somewhat, because the rank of $\mathbb Z\sqrt{a_1}+ \dots+ \mathbb Z\sqrt{a_n}$ as a $\mathbb Z$-module is equal to the number of distinct square-free cores of $a_1, \dots, a_n$. In terms of $\mathbb Q^\times / (\mathbb Q^\times)^2$, as I understand, it would mean the size of $\{a_1,\dots, a_n\}$ rather than $\langle a_1, \dots, a_n \rangle$.

In any case, one way to construct such a homomorphism is, for each distinct square-free core $x$ of $a_i$, to pick one of at most $2$ its possible square roots in $\mathbb F_{p^2}$ (any choice should do), and then for each $a_i = y^2 x$ to define $f(\sqrt{a_i}) = y f(\sqrt x)$, then it's possible to define $f$ on other arguments naturally.

Finally, for the algorithmic part of the process, it's worthwhile to note that we do not need to actually find the square-free cores, and thus we do not need to factorize input numbers. This is because $a_i$ and $a_j$ have the same square-free core if and only if $a_i a_j$ is the full square. Then, in each group of $a_i$ that has the same square-free core, we can choose any square root for one element, and then define $$ f(\sqrt{a_j}) = \sqrt{\frac{a_j}{a_i}} f(\sqrt{a_i}), $$ which will be well-defined because $\sqrt{\frac{a_i}{a_j}}$ is rational if $a_i$ and $a_j$ have the same core.