Seventeen lines and one-hundred-and-one points (Q1885913)

Motivated by an old (1788) geometric problem, proposed by Fourier (inspiring the title of the present paper) the author studies the following arithmetic problem: Given two positive integers \(S,Q\) decide whether there exist positive integers \(x_1, \dots, x_k\) with \(\sum_{i=1}^k x_i =S\)\, and \(\sum_{i=1}^k x_i^2 =Q\). Section 2 of the paper discusses some properties of the admissible pairs \((S,Q)\) (pairs with answer YES for the above problem). Based on these properties the author designs (Section 3) an algorithm that solves the problem and runs in polynomial time (in the input size \(\log S + \log Q\)). In fact the decision problem is trivial for \(S\leq Q \leq S(S-6\sqrt S)\): the answer is YES if \(S,Q\)\, have the same parity and NO otherwise. For \((S-6\sqrt S)<Q \leq S^2\)\, the algorithm acts in a recurrent way. The fourth and last section discusses some problems related with the one studied in this paper but for which however it is known or guessed that they are NP-hard.