%%a Plain TeX file of an article A. Robertson and D. Zeilberger \font\smcp=cmcsc8 \font\mcp=cmcsc10 \headline={\ifnum\pageno>1 {\smcp the electronic journal of combinatorics 5 (1998), \#R19\hfill\folio} \fi} %begin macros \def\L{{\cal L}} \baselineskip=14pt \parskip=10pt \def\Tilde{\char126\relax} \def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule height0.15cm width 0.01cm}} \font\eightrm=cmr8 \font\sixrm=cmr6 \font\eighttt=cmtt8 \font\tenrm=cmr10 \magnification=\magstephalf \def\lheading#1{\bigbreak \noindent {\bf#1} } \parindent=0pt \overfullrule=0in %end macros \bf \centerline {A 2-COLORING OF $[1,N]$ CAN HAVE $(1/22)N^2+O(N)$ MONOCHROMATIC} \centerline {SCHUR TRIPLES, BUT NOT LESS!} \rm \bigskip \centerline{ {\mcp Aaron Robertson and Doron Zeilberger\footnote{$^1$} {\eightrm \raggedright Supported in part by the NSF.}}} \centerline{{Department of Mathematics, Temple University, Philadelphia, PA 19122, USA}} \centerline{{\tenrm aaron@math.temple.edu, zeilberg@math.temple.edu}} \centerline{{\it Submitted: March 3, 1998; Accepted: March 25, 1998}} {}\footnote{}{\eightrm \raggedright Mathematics Classification Numbers: Primary: 05D10, 05A16; Secondary: 04A20} {\smcp {\bf Abstract}: We prove the statement of the title, thereby solving a \$100 problem of Ron Graham. This was solved independently by Tomasz Schoen.} {\bf Tianjin, June 29, 1996}: In a fascinating invited talk at the SOCA 96 combinatorics conference organized by Bill Chen, Ron Graham proposed (see also [GRR], p. 390): {\bf Problem (\$100)}: Find (asymptotically) the least number of monochromatic Schur triples $\{i,j,i+j\}$ that may occur in a 2-coloring of the integers $1,2, \dots , n$. By naming the two colors $0$ and $1$, the above is equivalent to the following {\bf Discrete Calculus Problem}: Find the minimal value of $$ F(x_1, \dots, x_n):= \sum_{{1 \leq i < j \leq n} \atop {i+j \leq n}} \left [ \,\, x_i x_j x_{i+j} + (1-x_i)(1-x_j)(1-x_{i+j}) \,\, \right ] , $$ over the $n$-dimensional (discrete) unit cube $\{ (x_1, \dots , x_n) \vert x_i=0,1 \}$. We will determine {\it all} local minima (with respect to the Hamming metric), then determine the global minimum. {\bf Partial Derivatives:} For any function $f(x_1, \dots , x_n)$ on $\{0,1\}^n$ define the discrete {\it partial derivatives} $\partial_r f$ by $ \partial_r f(x_1, \dots , x_r , \dots , x_n):= f(x_1, \dots , x_r , \dots , x_n)- f(x_1, \dots , 1-x_r , \dots , x_n). $ If $(z_1, \dots , z_n )$ is a local minimum of $F$, then we have the $n$ inequalities: $$ \partial_r F(z_1, \dots, z_n) \leq 0 \quad, \quad 1 \leq r \leq n. $$ A purely routine calculation shows that (below $\chi(S)$ is 1(0) if $S$ is true(false)) $$ \partial_r F(x_1, \dots , x_n)= $$ $$ (2x_r-1) \! \left \{ \sum_{i=1}^{n} \!x_i + \! \sum_{i=1}^{n-r} x_i -(n \! - \! \left \lfloor{{r} \over {2}} \right \rfloor)-{\chi}(r\!>\! {{n} \over {2}})- (2x_r\!-\!1)+\! x_r {\chi}(r\!> \!{{n} \over {2}}) + 1 - (x_{{{r} \over {2}}}\!+\!x_{2r}) {\chi}(r \!\leq \!{{n} \over {2}} )\right \} . $$ Since we are only interested in the {\it asymptotic} behavior, we can modify $F$ by any amount that is $O(n)$. In particular, we can replace $F(x_1, \dots , x_n)$ by $$ G(x_1, \dots , x_n) = F(x_1, \dots , x_n) + \sum_{i=1}^{n/2} x_i (x_{2i} -1) - {{1} \over {2}}\sum_{i=1}^{n} x_i. $$ Noting that $(2x_r-1)^2 \equiv 1$ and $(2x_r-1)x_r \equiv x_r$ on $\{0,1\}^n$, we see that for $1 \leq r \leq n$, $$ \partial_r G(x_1, \dots , x_n)= (2x_r-1) \left \{ \sum_{i=1}^{n} x_i + \sum_{i=1}^{n-r} x_i -(n- \left \lfloor {{r} \over {2}} \right \rfloor) - {{1} \over {2}} {\chi}(r \leq n/2) \right \} -{{1} \over {2}} {\chi}(r \leq n/2) - 1/2. $$ Let $k=\sum_{i=1}^{n} x_i$. By symmetry we may assume that $k\geq n/2$. Since at a local minimum $(z_1, \dots, z_n)$ we have $\partial_r G(z_1, \dots, z_n) \leq0$, it follows that any local minimum $(z_1, \dots, z_n)$ satisfies the {\bf Ping-Pong Recurrence}: Let $$ H_c(y):=\cases{0,& if $y\geq c$;\cr 1,& if $y < c$.\cr} $$ For $r=n, n-1 , \dots, n-\lfloor n/2 \rfloor + 1$ $$ z_{r}=H_{1/2}\left(k-n+ \left \lfloor {{r} \over {2}} \right \rfloor + \sum_{j=1}^{n-r} z_j\right) , \eqno(Right\,Volley) $$ $$ z_{n-r+1}=H_1\left(2k-n-1/2+ \left \lfloor {{n-r+1} \over {2}} \right \rfloor- \sum_{j=r}^{n} z_j\right) , \eqno(Left \,Volley) $$ and if $n$ is odd then $z_{(n+1)/2}=H_{1/2}(k-n+\lfloor {{n+1} \over {4}} \rfloor + \sum_{j=1}^{(n-1)/2} z_j)$. These equations uniquely determine $z$ (if it exists), in the order $z_n,z_1,z_{n-1},z_2, \dots $. When we solve the Ping-Pong recurrence we forget the fact that $\sum_{i=1}^{n} z_i=k$. Most of the time, the unique solution will not satisfy this last condition, but when it does, we have a genuine local minimum. Note that {\it any} local minimum must show up in this way. {\bf The Solution of the Ping-Pong Recurrence:} By playing around with the Maple package {\tt RON} (available from either author's website), we were able to find the following {\it explicit} solution, for $n$ sufficiently large, to the Ping-Pong recurrence. As usual, for any word (or letter) $W$, $W^m$ means `$W$ repeated $m$ times'. Let $w=2k-n$, $k > n/2$ (the case $k=n/2$ is treated seperately). Then $0