Wednesday, September 23, 2009

n-expressible integers

A positive integer is called $n$-expressible if it can be written as a sum of $n$ or less squares.

Prove that the product of two $n$-expressible integers is $\frac{n^2-n+2}{2}$-expressible

Solution

The problem is an immediate consequence of the identity:

$(a_1^2 + \cdots + a_n^2)(b_1^2 + \cdots + b_n^2)$

$= (a_1b_1 + \cdots + a_nb_n)^2 + \sum_{i > j}(a_ib_j - a_jb_i)^2$

Remark: the identity also serves as a one-line proof to the Cauchy Schwarz inequality.