Is computing distance a lesser capability than computing square roots?
Let $F$ be a field. Consider the following three abilities:
- (SQRT) Given $a\in F$, find $x\in F$ such that $a = x^2$ (when such $x$ exists).
- (NORM) Given $a,b\in F$, find $x\in F$ such that $a^2+b^2 = x^2$ (when such $x$ exists).
- (BISQ) Given $a\in F$, find $x,y\in F$ such that $a = x^2+y^2$ (when such $x,y$ exist).
Abilities NORM and BISQ together yield ability SQRT. Ability SQRT (plus the ability to perform field operations) yields ability NORM. If $F=\mathbb{R}$, then ability SQRT also yields ability BISQ (since in $\mathbb{R}$ the numbers expressible as a sum of squares are exactly the numbers expressible as squares, namely the nonnegative numbers, so we can compute $x$ using SQRT and take $y=0$), and so for $\mathbb{R}$ ability SQRT is equivalent to the combination of abilities NORM and BISQ. [This paragraph was revised after an error was pointed out by joriki.]
My question: Is NORM a strictly lesser capability than SQRT (in $\mathbb{R}$ or in any other field)?
I don't state the question formally because I don't know the right formalization. Any reasonable interpretation of the question is legit.
My observations so far:
In a field of characteristic 2, ability NORM is trivial (take $x=a+b$). It seems like SQRT should be a nontrivial ability, but I don't see how to prove that, for example, in the field of power series over $\mathbb{Z}/2\mathbb{Z}$, the square root operation cannot be performed using the field operations alone.
I had hoped to construct a field $F$ containing $\mathbb{Q}$ and closed under the operation of NORM, but not closed under SQRT (maybe using some trick related to the characterization of the integers which are representable as the sum of two squares). This would show that, in that field, NORM is a strictly lesser capability than SQRT in a very strong sense. But because every positive integer is the sum of four squares, any such field contains the square roots of all positive integers (if $n = a^2+b^2+c^2+d^2$ then $\sqrt n = \sqrt{(\sqrt{a^2+b^2})^2 + (\sqrt{c^2+d^2})^2}$), hence the square roots of all positive rationals ($\sqrt{p/q} = \sqrt{pq}/q$), so it doesn't seem very hopeful.
(The origin of the question is that a computer programmer I know was wondering whether there was a way to perform NORM without having to invoke the computationally expensive SQRT operation. I doubt that this question has a positive practical answer, but the theoretical aspect struck my curiosity.)
Solution 1:
The following could be considered evidence that NORM is a strictly lesser ability than SQRT. There are fields that are closed under NORM but are not closed under SQRT.
The simplest example is $\mathbb{Z}_3$. Indeed, if $p$ is any odd prime, then every element of $\mathbb{Z}_p$ is the sum of two squares, while $(p-1)/2$ elements are non-squares. For let $q$ be a quadratic residue modulo $p$ such that $q+1$ is a quadratic non-residue $w$. Every quadratic non-residue can be obtained by multiplying $w$ by a suitable quadratic residue. But $q+1$ times a quadratic residue is a sum of two quadratic residues, that is, a sum of two squares in $\mathbb{Z_p}$.
A more interesting class of examples is given by the Pythagorean fields which are not Euclidean. They come up quite naturally in geometry.
The simplest such field is usually called the Hilbert field. It is the closure of $\mathbb{Q}$ under the ordinary arithmetical operations and the operation $\sqrt{1+x^2}$. (It is easy to see that this makes it closed under your operation NORM.)
But the Hilbert field is not closed under SQRT. It can be shown, for example, that $\sqrt{1+\sqrt{2}}$ is not an element of the Hilbert field.
Another class of examples: Let $P$ be the set of odd primes, and let $D$ be a non-principal ultrafilter on the index set $P$. Let $F$ be the ultraproduct $\mathbb{Z}_p^P/D$. By a standard result of Model Theory, $F$ is a field. It is infinite and has characteristic $0$.
Because NORM and SQRT are first-order properties of fields, we can transfer the result about the $\mathbb{Z}_p$ to $F$. So $F$ has property NORM but not the property SQRT. By varying the ultrafilters, we can use the ultraproduct construction to produce many non-isomorphic fields. For example, we can choose to put in the ultrafilter the set of primes that have a specific $k$ as a quadratic residue.
We can form arbitrarily large ultraproducts by following essentially the above recipe, mixing in at will other fields. All very non-constructive, of course, but in a sense that strengthens the case that NORM is a strictly lesser ability than SQRT, since the wider the collection of fields that have one property but not the other, the less we can use "special properties."
Solution 2:
When talking about taking the closure of some field $F$ under NORM or SQRT, you have to make sure to specify in which (larger) field you're looking for the square root $x$. Of course it could be the algebraic closure of $F$, but in this case NORM and SQRT are equivalent, unless $F$ has characteristic 2.
Indeed, if -1 is a square in $F$, then given some $a\in F$ we can write $$\sqrt{a} = \sqrt{\left(a+1/2\right)^2 + \left(\sqrt{-1}\sqrt{a^2+\left(1/2\right)^2}\right)^2}$$ which belongs to $F$ if $F$ is closed under NORM. So NORM implies SQRT.
When -1 is not a square, André Nicolas explained how there are examples of fields that satisfy NORM but not SQRT. A straightforward example containing $\mathbb{Q}$ could be the smallest subfield $F$ of $\mathbb{Q}(\sqrt{\sqrt2})$ closed under NORM and containing $\mathbb{Q}$ (hence also $G = \mathbb{Q}(\sqrt2)$). If it is distinct from $G$, at some point we must have used NORM to write $$a^2+b^2=x^2$$ with $a,b\in G$ and $x\notin G$. We can write $x = u+v\sqrt{\sqrt2}$ with $u,v\in G$ and $v\ne 0$: $$a^2+b^2-u^2-v^2\sqrt{2}=2uv\sqrt{\sqrt2}$$ Necessarily $u=0$ since the RHS must belong to $G$. Writing $a/v=a'+a''\sqrt2$, $b/v=b'+b''\sqrt2$: $$(a'+a''\sqrt2)^2+(b'+b''\sqrt2)^2=\sqrt{2}$$ $$a'^2+2a''^2+b'^2+2b''^2=0$$ Hence $a'=a''=b'=b''=0$, a contradiction. So $F=G$, which is not closed under $\textrm{SQRT}_{\mathbb{Q}(\sqrt{\sqrt2})}$.
Edit: For your power series example, I'm not sure if that's what you had in mind but $\mathbb{Z}/2\mathbb{Z}(X)$ is closed under $\textrm{SQRT}_{\mathbb{Z}/2\mathbb{Z}((X))}$. Suppose $$p/q=a^2$$ with $p$ and $q$ polynomials over $\mathbb{Z}/2\mathbb{Z}$ and $a$ a formal Laurent series. Then $$pq=(aq)^2$$ $$pq=\sum_{i=-p}^\infty b_{i}x^{2i}$$ and the sum is finite and has non-negative valuation since $pq$ is a polynomial. Thus $$pq=\left(\sum_{i=0}^n b_ix^i\right)^2=b^2$$ $$a^2=p/q=(b/q)^2$$ where $b$ and $q$ are polynomials.
Obviously you could construct more contrived examples such as the closure of $\mathbb{Z}/2\mathbb{Z}(X^2)$: $X$ can only be constructed through $\textrm{SQRT}_{\mathbb{Z}/2\mathbb{Z}((X))}$, proving that it is non-trivial unlike $\textrm{NORM}_{\mathbb{Z}/2\mathbb{Z}((X))}$.
Solution 3:
In a field of characteristic 2, ability NORM is trivial (take x=a+b).
It seems like SQRT should be a nontrivial ability, but I don't see how
to prove that, for example, in the field of power series over Z/2Z, the
square root operation cannot be performed using the field operations alone
Let $x \in \mathbb{F_2}((t))$ be transcendental over $\mathbb{F}_2$ with a square root. The set of all Laurent series you can produce using $1$, $x$, and field operations is $\mathbb{F}_2(x)$, which is isomorphic to the function field $\mathbb{F}_2(s)$, by sending $x \mapsto s$. However, $\sqrt{s} \not\in \mathbb{F}_2(s)$, and so $\sqrt{x} \not\in \mathbb{F}_2(x)$.
I claim you can't even answer the simpler question "does $x$ have a square root?" using field operations and limits too, since the squares are the field $\mathbb{F_2}((t^2))$, which is isomorphic to $\mathbb{F_2}((t))$.