Combinatorial principles in elementary number theory (Q1182430)

It is shown that the theory \(\hbox{I}\Delta_ 0\;+\) weak version of the \(\Delta_ 0\)-Pigeonhole Principle proves the Lagrange four squares theorem. This answers positively a question of A. McIntyre (1986). The authors consider also the number-theoretical consequences of a new combinatorial principle called ``\(\Delta_ 0\)-Equipartition Principle'' \((\Delta_ 0 \hbox{EQ})\). In particular, a new proof (which can be formalized in \(\hbox{I}\Delta_ 0+\Delta_ 0 \hbox{EQ})\) of the fact that every prime of the form \(4n+1\) is the sum of two squares is given.