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; Revised: May 3, 1998

Abstract: We prove that the minimum number (asymptotically) of monochromatic Schur triples that a 2-coloring of [1, n] can have is \frac{n^{2}}{22} + O(n). This revised version fills in a minor and subtle gap discovered by M. Primak. (The revision also corrects (at no extra cost) a discrepancy between the solution in the paper and the solution obtained by Maple. In the paper H_{1/2} should be H_{0} and H_{1} should be H_{1/2} for the solutions to agree.)

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 renaming 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 (applicable Maple routines: diff1, dif) 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})\} .

1 Supported by NSF.

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

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}.

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}. 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: Choose a, b ∈ {0, 1} arbitrarily each time Ĥ or H̃ is used, where Ĥ and H̃ are the following functions:

Ĥ(y) := \{ \begin{matrix}0, & if y > 1/2; \\ 1, & if y < 0; \\ a, & if 0 ≤ y ≤ 1/2. \end{matrix}

H̃(y) := \{ \begin{matrix}0, & if y > 1; \\ 1, & if y < −1; \\ b, & if −1 ≤ y ≤ 1. \end{matrix}

Then we must have, for r = n, n − 1, …, n − ⌊n/2⌋ + 1,

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

z_{n−r+1} = H̃ (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} = Ĥ(k − n + ⌊\frac{n+1}{4}⌋ + ∑_{j=1}^{(n−1)/2} z_{j}).

These equations determine a solution (depending upon the choices of the a’s and b’s made along the way), 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 a 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.

Solutions of the Ping-Pong Recurrence: By playing around with the Maple routine ptor2 in our Maple package RON (available from either author’s website), we were able to find the following solutions, 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 (this case must be dealt with separately). By symmetry we may assume that k ≥ n/2. 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/8 ≤ w < n/2 then the solutions are:

0^{⌊ \frac{n}{2} ⌋}1^{n−⌊ \frac{n}{2} ⌋−w−c_{1}}0^{w+c_{1}}

where c_{1} ∈ {−1, 0, 1}.

Case II: If n/(12s + 8) ≤ w < n/(12s + 2) then the solutions are

\{ \begin{matrix}0^{4w+c_{1}}1^{⌊n/2⌋−4w−c_{1}}0^{n−⌊n/2⌋−7w−(c_{2}+c_{3}+c_{4})}1^{6w+c_{3}}0^{w+c_{4}} & for s = 1; \\ 0^{4w+c_{4}}(1^{6w+c_{5}^{s_{i}}} 0^{6w+c_{6}^{s_{i}}})^{s/2}Q(0^{6w+c_{7}^{s_{i}}} 1^{6w+c_{8}^{s_{i}}})^{s/2}0^{w+c_{9}} & for s > 1. \end{matrix}

where the c_{j}’s and c_{j}^{s_{i}}’s are bounded constants (independent of n) and Q can be an (almost) arbitrary mix of r zeroes and ones (where r is the unique integer such that the length of this interval is n). Further, the number of ones in Q is at most 12w. Notation: (1) the c_{j}^{s_{i}}’s can be different constants with i ranging from 1 to s/2; (2) if s is odd (ab)^{s/2} is (ab)^{(s−1)/2}a.

Case III: If n/(12s + 14) ≤ w < n/(12s + 8) then the solutions are

\{ \begin{matrix}0^{4w+d_{1}}1^{n−5w−(d_{1}+d_{2})}0^{w+d_{2}} & for s = 0; \\ 0^{4w+d_{3}}(1^{6w+d_{4}^{s_{i}}} 0^{6w+d_{5}^{s_{i}}})^{s/2}Q(0^{6w+d_{6}^{s_{i}}} 1^{6w+d_{7}^{s_{i}}})^{s/2}0^{w+d_{8}} & for s > 0. \end{matrix}

where the d_{j}’s and d_{j}^{s_{i}}’sare bounded constants (independent of n) and Q can be an (almost) arbitrary mix of r zeroes and ones, with the number of ones in Q at most 6w.

Case IV: if w = 0 (i.e. s = ∞), the solutions are:

0^{g_{1}}(1^{g_{2}^{n_{i}}} 0^{g_{3}^{n_{i}}})^{n/(2G_{1})}Q(0^{g_{4}^{n_{i}}} 1^{g_{5}^{n_{i}}})^{n/(2G_{2})}

where g_{1} ∈ {0, 1, 2}, the other g_{i}’s and g_{i}^{n_{i}}’s are bounded between 3 and 11, Q is an (almost) arbitrary mix of r zeroes and ones with the number of ones bounded between 0 and 22, G_{1} = ∑_{i}(g_{2}^{n_{i}} + g_{3}^{n_{i}}), and G_{2} = ∑_{i}(g_{4}^{n_{i}} + g_{5}^{n_{i}}).

Proof: Routine verification!

Now it is time to impose the extra condition that ∑_{i=1}^{n} z_{i} = k (= (w + n)/2). With Cases I and II a routine calculation yields a contradiction of the applicable range of w when n is sufficiently large. For Case III, a routine calculation yields a local minimum of w = n/11 if s = 0. If s > 0 argue as follows. Let t be the number of 1’s in Q. Recall that r is the total number of 0’s and 1’s in Q. Let w_{c}(s) = n/(12s + c) where we must have 8 ≤ c ≤ 14. Since we need ∑_{i=1}^{n} z_{i} = k (= (w +n)/2), we see that 6w_{c}(s)s+t = n(12s+c+1)/(24s+2c) gives t = (c+1)w_{c}(s)/2. Further, since the number of 1’s in Q is bounded by 6w_{c}(s), we find that we must have c ≤ 11. We also must have r = n − w_{c}(s)(12s + 5), by the definition of r. Using the simple inequality r ≥ t, we have n − w_{c}(s)(12s + 5) ≥ (c + 1)w_{c}(s)/2. From this deduce that c ≥ 11. Hence we must have c = 11 at a local minimum. Thus the local minimums for Case III, s > 0, are w_{s} = n/(12s + 11). Case IV gives infinitely many local minimums. Hence

The Local Minima Are Asymptotically Equivalent (mod O(n)) to:

\{ \begin{matrix}Z_{s} := 0^{4w_{s}}(1^{6w_{s}}0^{6w_{s}})^{\frac{s}{2}} 1^{6w_{s}}(0^{6w_{s}}1^{6w_{s}})^{\frac{s}{2}} 0^{w_{s}} & for 0 ≤ s < ∞ (where w_{s} := \frac{n}{12s+11}), \\ Z_{∞}^{t} = (0^{t}1^{t})^{n/(2t)} & for 3 ≤ t ≤ 11 \end{matrix}

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_{∞}^{t}) = (1/16)n^{2} + O(n) for any natural number t.

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

An Extension Here we note that our result implies a good upper 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}.

Note: Tomasz Schoen[S], a student of Tomasz Luczak, has independently solved this problem.

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.

[RZ] 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].