Can you multiply if all you know is squaring?

Question

I am interested in this problem as a novelty; in the direction of constructing known things (which are usually taken to be somewhat fundamental) in terms of other, less-orthodox-to-call 'fundamental' things.

In particular, suppose the function $s(x) = x^2$ is taken to be known, or "effectively calculable" (consider this a problem over the integers). I am interested then if it is possible to recover $f(x,y) = xy$ given only in terms of $s$ and other "simpler" operations, like addition or negation.

One attempt is given by the identity $(x+y)^2 -x^2 - y^2 = 2xy$. If the map $x \mapsto x/2$ were effectively calculable then we would be done in this case, but somehow this is unsatisfying to me. I would like to not 'give up' any amount of the "higher order" division or general multiplication operations.

I believe I can formalize my question in the following way.

Let $P \subseteq \mathbb Z [x,y]$ be the smallest collection of integer polynomials satisfying the following conditions. \begin{equation*} \begin{array}{l} x \in P,\, y \in P\\ p(x,y),\, q(x,y) \in P \implies mp(x,y) + nq(x,y) \in P \quad \forall m,n \in \mathbb Z\\ p(x,y) \in P \implies (p(x,y))^2 \in P \end{array} \end{equation*} Question: is $xy \in P$?

We can see that it is the case that $2xy \in P$, but I wonder if removing the extraneous scalar $2$ will be impossible.

Answer 1

No polynomial formed with linear combinations only does contain the term $xy$.

A polynomial obtained by squaring a linear combination has an even coefficient of $xy$.

The property "has an even coefficient of $xy$" is preserved both by linear combinations and squarings.

(This is also true of affine combinations.)

Answer 2

Instead of working in a situation where $x \mapsto x/2$ is not 'effectively calculable', why not work in a situation where it is impossible - i.e., in characteristic $2$?

By reducing modulo $2$, you may consider all your polynomials as elements of $\mathbb{F}_2(x,y)$. Squaring is the Frobenius endomorphism in characteristic $2$; i.e., we have $$ (p + q)^2 = p^2 + q^2 $$ for any polynomials $p,q \in \mathbb{F}_2(x,y)$. From this, we can deduce by induction that any polynomial in your set $P$, when reduced modulo $2$, is a linear combination of powers of $x$ and $y$ (indeed, a linear combinataion of terms of the form $x^{2^a}$ or $y^{2^b}$). $xy$ is not of that form when reduced modulo $2$.