12

Is it possible to define multiplication of two positive integers only using addition and squaring? Of course I have $5 \cdot 3 = 5 + 5 + 5$ but I would like something without saying do this $n$-times.

Peano Arithmetic has the following two axioms:

  1. $x \cdot 0 = 0$
  2. $x \cdot y = x \cdot (y-1) + x$

So I could also write $3 \cdot 5 = 3 \cdot (5-1) + 3 = 3^2 + 3 + 3$ but again I don't "know" how often I need to apply the $2$nd axiom.

I tried a few things and noticed that one has:

$$2xy = (x+y)^2-x^2-y^2 \text{ and } 4xy = (x+y)^2-(x-y)^2$$

Close to $xy$ but still not what I am looking for. And actually this uses subtraction...

Edit: As clarified in the comments: I am asking how to define multiplication inside the structure $(\mathbb{N}, +, \cdot^2)$.

Sqyuli
  • 600
  • 2
    In order to define mult with squaring, you have to provide a def of squaring that does not rely of mult... – Mauro ALLEGRANZA Mar 04 '19 at 15:49
  • 2
    Does one need to define squaring? In a simple case one could have a calculator with a squaring button but times button broken, maybe add still works. – coffeemath Mar 04 '19 at 16:06
  • 4
    @MauroALLEGRANZA Or just take squaring as primitive - e.g. ask whether multiplication is definable in the structure $(\mathbb{N}; +, \cdot^2)$. That's a perfectly sensible question. (Actually, that specific question is a bit silly - $xy$ is the unique number $\alpha$ satisfying $x^2+y^2+\alpha+\alpha=(x+y)^2$ - so to make the question nontrivial we have to pin down a more limited notion of "define." But my point stands.) – Noah Schweber Mar 04 '19 at 16:30
  • @NoahSchweber Acutally that is my original question. I know that multiplication is definable in the structure (\mathbb{N}, +, \cdot^2) but not how. It is just written this "weird" because I wanted to avoid talking about structures. – Sqyuli Mar 04 '19 at 16:45
  • @Sqyuli Oh, so does my comment answer the question? If so I'll turn it into an answer. – Noah Schweber Mar 04 '19 at 16:46
  • @NoahSchweber I see that I can say that $\alpha := xy$ is the element satisfying $(x + y)^2 = \alpha + \alpha +x^2 +y^2$ and I can also state this inside the structure $(\mathbb{N}, +, \cdot^2)$. I hoped that there is more a construction of $\alpha$. I don't know, if you understand what I mean. Feel free to turn your comment to an answer and if there will be nothing "nicer" I am happy to accept your answer. – Sqyuli Mar 04 '19 at 16:50
  • An interesting variation on this problem is: can you write an algorithm that finds the most efficient way to do exponentiation if you have multiplication and square? For example, suppose we wish to compute $x^{10}$. We could compute $xxxxxxxxxx$ in nine steps but $(x^2)^2(x^2)^2x^2$ is only six steps and $((x^2)^2)^2x^2$ is only five. – Eric Lippert Mar 05 '19 at 01:43
  • @EricLippert Don't know if this is the most efficient but my numerical analysis course provided binary exponentiation for this task. It's $\mathcal{O}(log(n))$ – Sqyuli Mar 05 '19 at 08:21