4
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.