A 2-COLORING OF [1, N] CAN HAVE (1/22)N^{2} + O(N) MONOCHROMATIC SCHUR TRIPLES, BUT NOT LESS!

Aaron Robertson and Doron Zeilberger^{1} Department of Mathematics, Temple University, Philadelphia, PA 19122, USA aaron@math.temple.edu, zeilberg@math.temple.edu Submitted: March 3, 1998; Accepted: March 25, 1998

Abstract: We prove the statement of the title, thereby solving a $100 problem of Ron Graham. This was solved independently by Tomasz Schoen.

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):

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, …, n.

By naming the two colors 0 and 1, the above is equivalent to the following

Discrete Calculus Problem: Find the minimal value of

F (x_{1}, …, x_{n}) := ∑_{{1≤i<j≤n \atop i+j≤n}} [ x_{i}x_{j}x_{i+j} + (1 − x_{i})(1 − x_{j})(1 − x_{i+j}) ] ,

over the n-dimensional (discrete) unit cube {(x_{1}, …, x_{n})|x_{i} = 0, 1}. We will determine all local minima (with respect to the Hamming metric), then determine the global minimum.

Partial Derivatives: For any function f(x_{1}, …, x_{n}) on {0, 1}^{n} define the discrete partial derivatives ∂_{r}f by ∂_{r}f(x_{1}, …, x_{r}, …, x_{n}) := f(x_{1}, …, x_{r}, …, x_{n}) − f(x_{1}, …, 1 − x_{r}, …, x_{n}).

If (z_{1}, …, z_{n}) is a local minimum of F, then we have the n inequalities:

∂_{r}F (z_{1}, …, z_{n}) ≤ 0 , 1 ≤ r ≤ n.

A purely routine calculation shows that (below χ(S) is 1(0) if S is true(false))

∂_{r}F (x_{1}, …, x_{n}) =

(2x_{r}−1)\{∑_{i=1}^{n}x_{i} +∑_{i=1}^{n−r} x_{i} − (n−⌊\frac{r}{2}⌋) − χ(r > \frac{n}{2}) − (2x_{r}−1) +x_{r}χ(r > \frac{n}{2}) + 1 − (x\frac{r}{2} +x_{2r})χ(r ≤ \frac{n}{2})\} .

Since we are only interested in the asymptotic behavior, we can modify F by any amount that is O(n). In particular, we can replace F (x_{1}, …, x_{n}) by

G(x_{1}, …, x_{n}) = F (x_{1}, …, x_{n}) + ∑_{i=1}^{n/2} x_{i}(x_{2i} − 1) − \frac{1}{2} ∑_{i=1}^{n} x_{i}.

1 Supported in part by the NSF.

Mathematics Classification Numbers: Primary: 05D10, 05A16; Secondary: 04A20

Noting that (2x_{r} − 1)^{2} ≡ 1 and (2x_{r} − 1)x_{r} ≡ x_{r} on {0, 1}^{n}, we see that for 1 ≤ r ≤ n,

∂_{r}G(x_{1}, …, x_{n}) = (2x_{r} − 1) \{∑_{i=1}^{n} x_{i} + ∑_{i=1}^{n−r} x_{i} − (n − ⌊\frac{r}{2}⌋) − \frac{1}{2}χ(r ≤ n/2)\} − \frac{1}{2}χ(r ≤ n/2) − 1/2.

Let k = ∑_{i=1}^{n} x_{i}. By symmetry we may assume that k ≥ n/2. Since at a local minimum (z_{1}, …, z_{n}) we have ∂_{r}G(z_{1}, …, z_{n}) ≤ 0, it follows that any local minimum (z_{1}, …, z_{n}) satisfies the

Ping-Pong Recurrence: Let

H_{c}(y) := \{ \begin{matrix}0, & if y ≥ c; \\ 1, & if y < c. \end{matrix}

For r = n, n − 1, …, n − ⌊n/2⌋ + 1

z_{r} = H_{1/2} (k − n + ⌊\frac{r}{2}⌋ + ∑_{j=1}^{n−r} z_{j}) ,  (Right V olley)

z_{n−r+1} = H_{1} (2k − n − 1/2 + ⌊\frac{n − r + 1}{2}⌋ − ∑_{j=r}^{n} z_{j}) ,  (Left V olley)

and if n is odd then z_{(n+1)/2} = H_{1/2}(k − n + ⌊\frac{n+1}{4}⌋ + ∑_{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}, . . .. When we solve the Ping-Pong recurrence we forget the fact that ∑_{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 any local minimum must show up in this way.

The Solution of the Ping-Pong Recurrence: By playing around with the Maple package RON (available from either author’s website), we were able to find the following 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 < w ≤ n. If w ≥ n/2 then the (only) solution is 0^{n}. If w < n/2, then let s be the (unique) integer 0 ≤ s < ∞, that satisfies n/(12s + 14) ≤ w < n/(12s + 2).

Case I: If n/(12s + 8) ≤ w < n/(12s + 2) then the unique solution is

0^{⌊ \frac{n}{2} ⌋}1^{n−⌊ \frac{n}{2} ⌋−w−1}0^{w+1}  for s = 0;
0^{4w}(1^{6w−1}0^{6w−1})^{\frac{s−1}{2}} 1^{⌊ \frac{n}{2} ⌋−(6s−2)w+s−1}0^{n−⌊ \frac{n}{2} ⌋−(6s+1)w+s−1}1^{6w−1}(0^{6w−1}1^{6w−1})^{\frac{s−1}{2}} 0^{w+1} for s odd;
0^{4w}(1^{6w−1}0^{6w−1})^{\frac{s−2}{2}} 1^{6w−1}0^{⌊ \frac{n}{2} ⌋−(6s−2)w+s−1}1^{n−⌊ \frac{n}{2} ⌋−(6s+1)w+s−1}(0^{6w−1}1^{6w−1})^{\frac{s}{2}} 0^{w+1} otherwise.

Case II: If n/(12s + 14) ≤ w < n/(12s + 8) then the unique solution is

\{ \begin{matrix}0^{4w}(1^{6w−1}0^{6w−1})^{\frac{s−1}{2}} 1^{6w−1}0^{n−(12s+5)w+2s−1}1^{6w−1}(0^{6w−1}1^{6w−1})^{\frac{s−1}{2}} 0^{w+1} & for s odd; \\ 0^{4w}(1^{6w−1}0^{6w−1})^{\frac{s}{2}} 1^{n−(12s+5)w+2s−1}(0^{6w−1}1^{6w−1})^{\frac{s}{2}} 0^{w+1} & for s even. \end{matrix}

the electronic journal of combinatorics 5 (1998), #R19 3

Case III: if w = 0 (i.e. s = ∞), the unique solution is

1(0^{3}1^{3})^{k/6}1^{2}(0^{3}1^{3})^{(k−6)/6}0^{3}  if k ≡ 0 (mod 6);
1(0^{3}1^{3})^{(k−1)/6}01^{3}(0^{3}1^{3})^{(k−7)/6}0^{3} if k ≡ 1 (mod 6);
1(0^{3}1^{3})^{(k−2)/3}0^{3}  if k ≡ 2 (mod 6);
1(0^{3}1^{3})^{(k−3)/6}0^{2}(0^{3}1^{3})^{(k−3)/6}0^{3} if k ≡ 3 (mod 6);
1(0^{3}1^{3})^{(k−4)/6}0^{3}1(0^{3}1^{3})^{(k−4)/6}0^{3} if k ≡ 4 (mod 6);
1(0^{3}1^{3})^{(k−2)/3}0^{3}  if k ≡ 5 (mod 6).

Proof: Routine verification! Now it is time to impose the extra condition that ∑_{i=1}^{n} z_{i} = k (= (w + n)/2). With Case I we get a contradiction of the applicable range of w, but Case II yields that w = \frac{n+2(s+1)}{12s+11}, which is a local minimum for n sufficiently large. Case III gives a local minimum when k ≡ 0, 1 (mod 6). Hence The Local Minima Are:

Z_{s} := 0^{4w_{s}}(1^{6w_{s}−1}0^{6w_{s}−1})^{\frac{s}{2}} 1^{6w_{s}−3}(0^{6w_{s}−1}1^{6w_{s}−1})^{\frac{s}{2}} 0^{w_{s}+1} for 0 ≤ s < ∞ (where w_{s} := \frac{n+2(s+1)}{12s+11}),
Z_{∞}^{0} = 1(0^{3}1^{3})^{k/6}1^{2}(0^{3}1^{3})^{(k−6)/6}0^{3}  for w = 0 and k ≡ 0 (mod 6), and
Z_{∞}^{1} = 1(0^{3}1^{3})^{(k−1)/6}01^{3}(0^{3}1^{3})^{(k−7)/6}0^{3}  for w = 0 and k ≡ 1 (mod 6).

A routine calculation [R] shows that for 0 ≤ s < ∞

F (Z_{s}) = \frac{12s + 8}{16(12s + 11)}n^{2} + O(n),

which is strictly increasing in s. An easy calculation shows F (Z_{∞}^{0}) = F (Z_{∞}^{1}) = (1/16)n^{2} + O(n). ...And The Winner Is: Z_{0} = 0^{4n/11}1^{6n/11}0^{n/11} setting the world-record of (1/22)n^{2} + O(n). Note: Tomasz Schoen[S], a student of Tomasz Luczak, has independently solved this problem. An Extension: Here we note that our result implies a good lower bound for the general r-coloring of the first n integers; if we r-color the integers (with colors C_{1} … C_{r}) from 1 to n then the minimum number of monochromatic Schur triples is bounded above by

\frac{n^{2}}{2^{2r−3}11} + O(n).

This comes from the following coloring:

Color(i) = C_{j}  if \frac{n}{2^{j}} < i ≤ \frac{n}{2^{j−1}} for 1 ≤ j ≤ r − 2,
Color(i) = C_{r−1} if 1 ≤ i ≤ \frac{4n}{2^{r−2}11} or \frac{10n}{2^{r−2}11} < i ≤ \frac{n}{2^{r−2}} ,
Color(i) = C_{r}  if \frac{4n}{2^{r−2}11} < i ≤ \frac{10n}{2^{r−2}11}.

REFERENCES

[GRR] R. Graham, V. Rödl, and A. Rucinski, On Schur properties of random subsets of integers, J. Number Theory 61 (1996), 388-408.

the electronic journal of combinatorics 5 (1998), #R19 4

[R] A. Robertson, On the asymptotic behavior of Schur triples, [www.math.temple.edu/~aaron].

[S] T. Schoen, On the number of monochromatic Schur triples, in preparation, [wtguest3@informatik.uni-

kiel.de].