# Colouring Positive Integers

Does anyone know any reference or proof for the following problem?

Let $$m$$ and $$n$$ be positive integers, $$m,n \geq 2$$. Each positive integer is coloured in one of $$m$$ different colours. Is it possible to find $$n$$ positive integers $$x_1, x_2, ..., x_n$$ such that all positive numbers of the form $$\sum_{i=1}^n \epsilon_ix_i,$$ where $$\epsilon_i \in \{0,1\},$$ have the same colour, when:

a) $$n \leq m$$?
b) $$n>m$$?

Any help would be appreciated.

## 2 Answers

Yes. This is a weak form of Hindman's theorem. See, for example, https://en.wikipedia.org/wiki/IP_set .

We understand completely which finite homogeneous linear structures are guaranteed to appear in one colour class whenever the natural numbers are finitely coloured. Suppose first that we'd like to find a monochromatic solution to $Ax=0$ where $A$ has rational entries. Rado proved that this is possible if and only if $A$ has the columns property. Write $A = \begin{pmatrix}c^{(1)} & \cdots & c^{(n)}\end{pmatrix}$. Then $A$ has the columns property if and only if there is a partition $[n] = I_1 \cup \cdots \cup I_t$ such that

• $\sum_{i \in I_1} c^{(i)} = 0$, and
• $\sum_{i \in I_s} c^{(i)} \in \langle c^{(j)} : j \in I_1 \cup \cdots \cup I_{s-1}\rangle$,

where $\langle \cdot \rangle$ denotes rational linear span.

Your problem has this form by taking $A$ to be the matrix corresponding to the equations $$y_I = \sum_{i \in I} x_i$$ for each $\emptyset \subset I \subseteq [n]$. This matrix has a block structure, with $-1$ times the $(2^n-1) \times (2^n-1)$ identity matrix in the left half and a $(2^n-1) \times n$ right half with all non-zero rows containing only $1$'s and $0$'s. It's easy to check that this matrix has the columns property.

We were lucky here that the expressions you wanted to be monochromatic included the single variables $x_i$, allowing the problem to be rephrased in terms of a monochromatic solution to a system of linear equations. We might reasonably seek monochromatic structures of the form $Ax$, where we care only about the colours of the entries of the image vector, and not $x$ itself. The situation is closely related to Rado's theorem but more complicated; the first necessary and sufficient conditions were described by Hindman and Leader.