%%%% THIS FILE IS AUTOMATICALLY GENERATED
%%%% DO NOT EDIT THIS FILE DIRECTLY,
%%%% ONLY EDIT THE SOURCE, tom-34/document.tex.
%%%%
%% Standard package list
\documentclass[letterpaper]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english]{babel}
\usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{amsmath,amssymb,amsthm,wasysym}
\usepackage{nicefrac,booktabs}
\usepackage{mathptmx}
\usepackage{cite}
\usepackage[colorlinks=true]{hyperref}

%% Various helpers for Tom's papers
\newcommand{\gs}{\textnormal{gs}}
\newcommand{\ord}{\textnormal{ord}}
\newcommand{\Exp}{\textnormal{Exp}}
\newcommand{\Log}{\textnormal{Log}}
\newcommand{\lcm}{\textnormal{lcm}}
\newcommand{\range}{\textnormal{range}}
\newcommand{\NR}{\textnormal{NR}}
\newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)}

\newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle}
\newcommand{\summ}[1]{\sum_{k=1}^m{#1}}
\newcommand{\bt}[1]{{{#1}\mathbb{N}}}
\newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}}
\newcommand{\intv}[1]{{\left[1,{#1}\right]}}


%% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name
%% This lets me do things like "Theorem A" and have the references work properly.
\makeatletter
\let\@old@begintheorem=\@begintheorem
\def\@begintheorem#1#2[#3]{%
  \gdef\@thm@name{#3}%
  \@old@begintheorem{#1}{#2}[#3]%
}
\def\namedthmlabel#1{\begingroup
   \edef\@currentlabel{\@thm@name}%
   \label{#1}\endgroup
}
\makeatother
% end lift

\newtheoremstyle{namedthrm}
  {}{}{}{}{}{}{ }  % This last space needs to be there
  {\bf\thmname{#1} \thmnote{#3}.}
%% End reference hack


%% Document start
\date{}
\begin{document}

%% Content start


\newtheorem{cor}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{thm}{Theorem}[section]
\newtheorem{q}{Problem}
\theoremstyle{definition}
\newtheorem*{defn}{Definition}
\newtheorem*{remark}{Remark}

\title{Monochromatic Solutions to Equations with Unit Fractions}
\author{Tom C. Brown and Voijtech R\"{o}dl}
\date{}
\maketitle
\begin{center}{\small {\bf Citation data:} T.C. {Brown} and V.~R\"odl, \emph{Monochromatic solutions to equations with
  unit fractions}, Bull. Aus. Math. Soc. \textbf{43} (1991), 387--392.}\bigskip\end{center}

Our main result is that if $G(x_1,\dots,x_n) = 0$ is a system of homogeneous equations such that for every partition of the positive integers into finitely many classes there are distinct $y_1,\dots,y_n$ in one class such that $G(x_1,\dots,x_n) = 0$, then, for every partition of the positive integers into finitely many classes there are distinct $z_1,\dots,z_n$ in one class such that 
\[ G\left( \frac{1}{z_1}, \dots,\frac{1}{z_n} \right) = 0. \]
In particular, we show that if the positive integers are split into $r$ classes, then for every $n \geq 2$ there are distinct positive integers $x_0,x_1,\dots,x_n$ in one class such that 
\[ \frac{1}{x_0} = \frac{1}{x_1} + \cdots + \frac{1}{x_n}. \]
We also show that if $[1,n^6 - (n^2 - n)^2]$ is partitioned into two classes, then some class contains $x_0,x_1,\dots,x_n$ such that 
\[ \frac{1}{x_0} = \frac{1}{x_1} + \cdots + \frac{1}{x_n}.\]
(Here $x_0,x_1,\dots,x_n$ are not necessarily distinct.)

\section{Introduction} \label{sec: 1}

\footnotetext{Received 29 May 1990 \\ The first author was partially supported by NSERC.}

In their monograph~\cite{erdos+graham1980}, Erd\H{o}s and Graham list a large number of questions concerned with equations with unit fractions. In fact, a whole chapter is devoted to this topic. One of their questions, still open, is the following.

In the positive integers, let 
\[ H_m = \left\{ \{x_1,\dots,x_m\}: \sum_{k=1}^m 1/x_k = 1, 0 < x_1< \cdots < x_m \right\}, \]
and let $H$ denote the union of all the $H_m, m \geq 1$. Now arbitrarily split the positive integers into $r$ classes. Is it true that some element of $H$ is contained entirely in one class? 

In this note we show (Corollary~\ref{cor: 2.3} below) that if one does not require \emph{all} the $x_k$'s to be distinct, but only \emph{many} of the $x_k$'s to be distinct, then the answer to the corresponding question is yes. More precisely, we show that if the positive integers are split into $r$ classes, then for every $n$ there exist $m \geq n$ and $x_1,\dots,x_m$ (not necessarily distinct) in one class such that $|\{x_1,\dots,x_m\}| \geq n$ and $\sum_{k=1}^m 1/x_k = 1$.

We actually show (Corollary~\ref{cor: 2.2} below) something stronger, namely that if the positive integers are split into $r$ classes, then for every $n \geq 2$ there are \emph{distinct} positive integers $x_0,x_1,\dots,x_n$ in one class such that 
\[ \frac{1}{x_0} = \frac{1}{x_1} + \cdots + \frac{1}{x_n}. \]
(The preceding result then follows by taking $x_0$ copies of each of $x_1,\dots,x_n$.)

Our main result (Theorem~\ref{thm: 2.1}) is that if $G(x_1,\dots,x_n) = 0$ is a system of homogeneous equations such that for every partition of the positive integers into finitely many classes there are distinct $y_1,\dots,y_n$ in one class such that $G(x_1,\dots,x_n) = 0$, then, for every partition of the positive integers into finitely many classes there are distinct $z_1,\dots,z_n$ in one class such that 
\[ G\left( \frac{1}{z_1}, \dots,\frac{1}{z_n} \right) = 0. \]
In particular, we show that if the positive integers are split into $r$ classes, then for every $n \geq 2$ there are distinct positive integers $x_0,x_1,\dots,x_n$ in one class such that 
\[ \frac{1}{x_0} = \frac{1}{x_1} + \cdots + \frac{1}{x_n}. \]

We also prove (Theorem~\ref{thm: 2.3}) the following quantitative result. Let $f(n)$ be the smallest $N$ such that if $[1,N]$ is partitioned into \emph{two} classes, then some class contains $x_0,x_1,\dots,x_n$ such that $1/x_0 = 1/x_1 + \cdots + 1/x_n$. (Here, $x_0,x_1,\dots,x_n$ are not necessarily distinct.) Then 
\[ f(n) \leq n^6 - (n^2 - n)^2. \]

\section{Results} \label{sec: 2}

From now on we shall use the terminology of \emph{colourings} rather than \emph{partitions}. That is, instead of ``partition into $r$" classes we say ``$r$-colouring," and instead of ``there are distinct $y_1,\dots,y_n$ in one class such that $G(y_1,\dots,y_n) = 0$" we say ``there is a monochromatic solution of $G(y_1,\dots,y_n) = 0$ in distinct $y_1,\dots,y_n$".

\begin{thm} \label{thm: 2.1} 
Let $G(x_1,\dots,x_n) = 0$ be a system of homogeneous equations such that for every finite colouring of the positive integers there is a monochromatic solution of $G(y_1,\dots,y_n) = 0$ in distinct $y_1,\dots,y_n$. Then for every finite colouring of the positive integers there is a monochromatic solution of $G(1/z_1,\dots,1/z_n) = 0$ in distinct $z_1,\dots,z_n$.
\end{thm}

\begin{proof}
Let $r$ be given, and consider a system $G(x_1,\dots,x_n) = 0$ of homogeneous equations such that for every $r$-colouring of the positive integers there is a monochromatic solution of $G(y_1,\dots,y_n) = 0$ in distinct $y_1,\dots,y_n$. By a standard compactness argument, there exists a positive integer $T$ such that if $[1,T]$ is $r$-coloured, there is a monochromatic solution to $G(y_1,\dots,y_n) = 0$ in distinct $y_1,\dots,y_n$.

Let $S$ denote the least common multiple of $1,2,\dots,T$. We show that for every $r$-colouring of $[1,S]$ there is a monochromatic solution of $G(1/z_1,\dots,1/z_n) = 0$ in distinct $z_1,\dots,z_n$.

To do this, let 
\[ c: [1,S] \to [1,r] \]
be an arbitrary $r$-colouring of $[1,S]$.

Define an $r$-colouring $\bar{c}$ of $[1,T]$ by setting 
\[ \bar{c}(x) = c(S/x), 1 \leq x \leq T. \]

By the definition of $T$, there is a solution of $G(y_1,\dots,y_n) = 0$ in distinct $y_1,\dots,y_n$ such that 
\[ \bar{c}(y_1) = \bar{c}(y_2) = \cdots = \bar{c}(y_n). \]
By the definition of $\bar{c}$, this means that 
\[ c(S/y_1) = c(S/y_2) = \cdots = c(S/y_n). \]
Setting $z_i = S/y_i, 1 \leq i \leq n$, we have that $z_1,\dots,z_n$ are distinct, are monochromatic relative to the colouring $c$ of $[1,S]$, and that 
\[ G\left(\frac{1}{z_1}, \dots, \frac{1}{z_n} \right) = 0. \qedhere \]
\end{proof}

Omitting all references to distinctness, one gets the following.

\begin{thm} \label{thm: 2.2} Let $G(x_1,\dots,x_n) = 0$ be a system of homogeneous equations such that for every finite colouring of the positive integers there is a monochromatic solution of $G(x_1,\dots,x_n) = 0$. Then, for every finite colouring of the positive integers there is monochromatic solution of $G(1/z_1,\dots,1/z_n) = 0$.
\end{thm}

\begin{cor} \label{cor: 2.1}
Let $a_1,\dots,a_m,b_1,\dots,b_n$ be positive integers such that
\begin{enumerate}
\item some non-empty subset of the $a_i$'s has the same sum as some non-empty subset of the $b_j$'s and 
\item there exist distinct integers $u_1,\dots,u_m,v_1,\dots,v_n$ such that $a_1u_1 + \cdots + a_mu_m = b_1v_1 + \cdots + b_nv_n$.
\end{enumerate}
Then, given any $r$-colouring of the positive integers, there is a monochromatic solution of 
\[ \frac{a_1}{x_1} + \cdots + \frac{a_m}{x_m} = \frac{b_1}{x_1} + \cdots + \frac{b_n}{y_n}. \]
in distinct $x_1,\dots,x_m,y_1,\dots,y_n$.
\end{cor}

\begin{proof}
Let $a_1,\dots,a_m,b_1,\dots,b_n$ satisfy conditions 1. and 2. According to Rado's theorem~\cite{rado1933} (also see~\cite[p.\ 59]{graham+rothschild+spencer1980}), the equation 
\[ a_1x_1 + \cdots + a_mx_m = b_1y_1 + \cdots + b_ny_n \]
will always have a monochromatic solution $x_1,\dots,x_m, y_1, \dots, y_n$, for every $r$-colouring of the positive integers, because of condition 1. The additional condition 2. is enough (see~\cite[p.\ 62 Corollary 8$\frac{1}{2}$]{graham+rothschild+spencer1980}) to ensure that the equation
\[ a_1x_1 + \cdots + a_mx_m = b_1y_1 + \cdots + b_ny_n \]
will always have a monochromatic solution $x_1,\dots,x_m$, $y_1,\dots,y_n$, in \emph{distinct} $x_1,\dots,x_m,y_1,\dots,y_n$. Theorem~\ref{thm: 2.1} now applies.
\end{proof}

\begin{cor} \label{cor: 2.2}
Let an arbitrary $r$-colouring of the positive integers be given. Let $n,a$ be positive integers, with $n \geq 2$, and $1 \leq a \leq n$. Then the equation
\[ \frac{a}{x_0} = \frac{1}{x_1} + \cdots + \frac{1}{x_n} \]
has a monochromatic solution in distinct $x_0,x_1, \dots, x_n$.
\end{cor}

\begin{proof} This follows immediately from Corollary~\ref{cor: 2.1}.
\end{proof}

\begin{cor} \label{cor: 2.3}
Let an arbitrary colouring of the positive integers be given. Then for every $n$ there exist $m \geq n$ and monochromatic $x_1,\dots,x_m$ (not necessarily distinct) such that $|\{x_1,\dots,x_m\}| \geq n$ and $\sum_{k=1}^m 1/x_k = 1$.
\end{cor}

\begin{proof} Apply Corollary~\ref{cor: 2.2} (with $a = 1$) and take $x_0$ copies of each of $x_1,\dots,x_m$.
\end{proof}

\begin{thm} \label{thm: 2.3}
For each $n \geq 2$, let $f(n)$ be the smallest $N$ such that if $[1,N]$ is partitioned into two classes, then some class contains $x_0,x_1,\dots,x_n$ such that 
\[ \frac{1}{x_0} = \frac{1}{x_1} + \cdots + \frac{1}{x_n}. \]
(Here, $x_0,x_1,\dots,x_n$ are not necessarily distinct.) Then
\[ f(n) \leq n^6 - (n^2 - n)^2. \]
\end{thm}

\begin{proof} The proof is by contradiction. Fix $n \geq 2$, let $N = n^6 - (n^2 - n)^2$, and suppose throughout the proof that $c: [1,N] \mapsto \{1,2\}$ is some fixed $2$-colouring of $[1,N]$ for which there does \emph{not} exist any monochromatic solution of 
\[ \frac{1}{x_0} = \frac{1}{x_1} + \cdots + \frac{1}{x_n}. \]

\begin{lemma} \label{lemma: 2.1}
(a) If $nx \leq N$ then $c(nx) \ne c(x)$.

(b) If $n^2x \leq N$ then $c(n^2x) = c(x)$.
\end{lemma}

\begin{proof}
Part (a) follows from $1/x = 1/(nx) + \cdots + 1/(nx)$. Part (b) follows from part (a).
\end{proof}

\begin{lemma} \label{lemma: 2.2}
If $n^2(n^2 + n - 1)x \leq N$, then $c((n^2 + n - 1)x) \ne c(x).$
\end{lemma}

\begin{proof} This follows from 
\[ \frac{1}{n^2x} = \frac{1}{n^2 + n - 1}x + (n-1)\frac{1}{n^2(n^2 + n - 1)x} \]
and Lemma~\ref{lemma: 2.1}.
\end{proof}

\begin{lemma} \label{lemma: 2.3}
If $n^2(n^2 - n + 1)x \leq N$, then $c((n^2 - n + 1)x) \ne c(x)$.
\end{lemma}

\begin{proof} This follows from 
\[ \frac{1}{(n^2 - n + 1)x} = \frac{1}{n^2x} + (n-1)\frac{1}{n^2(n^2 - n + 1)x} \]
and Lemma~\ref{lemma: 2.1}.
\end{proof}

\begin{lemma} \label{lemma: 2.4}
If $n^2(n^2 + n -1)x \leq N$, then $c((n + 1)x) = c(x)$.
\end{lemma}

\begin{proof} This follows from 
\[ \frac{1}{n(n + 1)x} = \frac{1}{(n^2 + n - 1)(n + 1)x} + (n-1)\frac{1}{(n^2 + n - 1)nx}, \]
and Lemmas~\ref{lemma: 2.1} and~\ref{lemma: 2.2}.
\end{proof}

\begin{lemma} \label{lemma: 2.5}
If $n^2(n^2 + n - 1)(n^2 - n + 1)x \leq N$, then $c(2x) = c(x)$.
\end{lemma}

\begin{proof}
This follows from 
\[ \frac{1}{(n^2 - n + 1)2x} = \frac{1}{(n^2 + n - 1)2x} + (n - 1) \frac{1}{(n^2 + n - 1)(n^2 - n + 1)x} \]
and Lemmas~\ref{lemma: 2.2} and~\ref{lemma: 2.3}.
\end{proof}

Finally, Theorem~\ref{thm: 2.3} is proved by observing that
\[ \frac{1}{2 \cdot 1} = \frac{1}{(n + 1)\cdot 1} + (n - 1)\frac{1}{2(n + 1)\cdot 1}, \]
and by Lemmas~\ref{lemma: 2.4} and~\ref{lemma: 2.5}, $c(2 \cdot 1) = c((n + 1)\cdot 1) = c(2(n + 1)\cdot 1) = c(1)$, a contradiction.
\end{proof}

\begin{remark} The authors have learned that Hanno Lefmann (Bielefeld) has independently obtained results which include our Theorem~\ref{thm: 2.2}.
\end{remark}


\bibliographystyle{amsplain}
\bibliography{tom-all}
\end{document}