3
$\begingroup$

Motivated by applications of Ramsey theory, Schur's theorem states that for any partition of the positive integers into a finite number of parts, one of the parts contains three integers $x, y, z$ with $x+y = z$.

I consider 2-coloring of the first $m$ integers. I suspect that there are more distinct product triples ($z_1=x*y$) than distinct sum triples ($z_2=x+y$). I am interested in finding bounds on the number of distinct sum triples vs distinct product triples in any 2-coloring of first $m$ integers as a function of $m$.

The lower bound is the maximum number of distinct sum triples (product triples ) that exist in some color class over all possible 2-colorings . The 2-coloring is balanced (the cardinally of each color class is greater than $\epsilon *m$ for some constant $\epsilon \gt 0$).

What is known about the asymptotics of distinct sum triples vs distinct product triples?

$\endgroup$
1
  • $\begingroup$ I do not understand your question. Are looking for numbers $z_1$ that are can be written as a product $xy$ with $x,y$ of the same color? If so, then yes, this set is going to be large even if we just restrict to the largest color class. This can be seen from the bound on the multiplicative energy of $[m]$ (or simpler yet; just restrict to the primes in $[m]$). $\endgroup$
    – Boris Bukh
    Nov 23, 2017 at 18:41

1 Answer 1

2
$\begingroup$

In $\{1,2,\cdots,k\}$ there are $\lceil\frac{k^2-2k}4\rceil$ sums $x+y=z$ which might be monochromatic and less than $k(\frac{\ln k}{2})$ products $xy=z$ (with $x\lt y \lt z$.) This would seem to favor sums over products.

It certainly does when $n=2k$ and we color $\{1,2,\cdots,k\}$ red and $\{k+1,k+2,\cdots,2k\}$ green.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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