Chit-chat on Lagrange’s four-square theorem

Lagrange’s four-square theorem is a beautiful result in number theory. However, to the best of my knowledge, I haven’t encountered it often in theoretical computer science. Today’s entry discusses two interesting stories related to this theorem: the first about a recent project I did in cryptography, the second about an anecdote, originated from UC Berkeley, of a bug in printing. I would say the second story is more interesting.

Lagrange’s four-square theorem states that any natural number $n\in\mathbb{N}$ can be written as the sum of up to 4 perfect squares. That is, there exists $x,y,z,w\in\mathbb{Z}$ such that $n=x^2+y^2+z^2+w^2$.

Usage in proving non-negativity

In my recent research in cryptography (another entry in Chinese), the prototype protocol (different from what we present in the paper) requires that the prover prove the range of a committed value. In simple words, imagine you have a number $n$, encrypted, where the encryption scheme allows arithmetic operations to be performed inside the encryption, and you want to prove it’s at least 0 and at most $m$. What you can do is to create another encryption of $m-n$ and prove both encryptions contain a non-negative number.

How do you prove a number is non-negative? Well, the sum of squares is always non-negative. Since one can always write $n=x^2+y^2+z^2+w^2$, the prover is asked to commit to (encrypt) $x,y,z,w$ in question, and commit to $x^2,y^2,z^2,w^2$, prove these 8 encryptions are in the correct ‘format’ (that is, the $x^2,y^2,z^2,w^2$ are really squares of $x,y,z,w$ instead of some bogus values), and finally add the commitments together, which yields a commitment to (an encryption of) $n$.

When Ivan first told me the construction, I was surprised by the tricky trick! Moreover, he mentioned that the decomposition of a given number can be found in polynomial time.

Usage in working around a bug

I first came to know the anecdote of a bug in printing at UC Berkeley from this Zhihu answer (in Chinese), which points a reference into this MathOverflow post, where the top answer cites:

Oct 2: Warning: Due to a known bug, the default Linux document viewer evince prints N*N copies of a PDF file when N copies requested. As a workaround, use Adobe Reader acroread for printing multiple copies of PDF documents, or use the fact that every natural number is a sum of at most four squares.

In the Zhihu answer, I replied:

What a feature! Well, it seems to me that ‘printing’ $\left\lfloor\sqrt{n}\right\rfloor$ ‘copies’ and reducing the problem to a smaller size is another good solution.

In the reply section, Zhihu user 马云龙 thinks that the theorem guarantees the reduction stops in 4 steps, which is wrong. Greedily printing doesn’t guarantee four-square decomposition. I was having supper with Tao Meng (a classmate and friend of mine) at Taoli Dining Hall (a dining hall of Tsinghua University) when I read the wrong comment by 马云龙, and decided to work out the complexity of the reduction method, which was exactly why I decided to write this entry.

Let’s compare the two methods (reduction v.s. decomposition). Clearly, the communication complexity is minimised for the decomposition method. However, the computational complexity might not be the case.

For the decomposition method, Randomized Algorithms in Number Theory by Michael O. Rabin and Jeffery O. Shallit, which appeared in Communications on Pure and Applied Mathematics in 1986, mentions an algorithm that finds the decomposition in expected $\mathcal{O}\left(\log^2 n\right)$ time (number of arithmetic operations of numbers of length $\mathrm{poly}(\log n)$) based on ERH. (This should be the algorithm mentioned earlier by Ivan.)

For the reduction method, suppose we have $n$ copies to print, after the first step of printing, we have no more than $2\sqrt{n}+1$ copies to print. Therefore, the number of iterations (printing jobs to submit) $T$ satisfies$T(n)\leq T(2\sqrt{n}+1)+1,$which yields $T(n)=\mathcal{O}(\log\log n)$. In each step, we will compute the square root of an integer. Babylonian method (a.k.a. Newton’s method for $x^2-n=0$) converges quadratically, and the number of significant digits we require is $\mathcal{O}(n)$, therefore, at most $\mathcal{O}(\log\log n)$ arithmetic operations are required before we reach the floored square root. The computational complexity of our reduction algorithm is $\mathcal{O}(\log^2\log n)$, which is fairly good. The communication complexity is $\mathcal{O}(\log\log n)$ jobs. The best thing is that this method does not depend on ERH.