🔢 mathematics

Monochromatic products in random integer sets

This paper investigates the threshold probability at which a random subset of integers almost surely contains a monochromatic solution to the equation $ab=c$ under a 2-coloring, establishing bounds between $n^{-1/9-o(1)}$ and $n^{-1/11}$ and demonstrating that the behavior and proof techniques for such non-linear equations differ substantially from those of linear ones.

Original authors: Roger Lidón, Darío Martínez, Patrick Morris, Miquel Ortega

Published 2026-01-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Roger Lidón, Darío Martínez, Patrick Morris, Miquel Ortega

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant bag of numbered tiles, from 1 to $n$ . You decide to pick a random handful of these tiles to keep, flipping a coin for each one: heads, you keep it; tails, you toss it. The probability of keeping a tile is $p$ .

Now, imagine you have a bucket of paint with $r$ different colors. You want to paint every tile in your random handful. The big question is: Is it possible to paint them in a way that avoids creating a "monochromatic product"?

A "monochromatic product" is a trio of tiles $(a, b, c)$ that are all the same color, where $a \times b = c$ . For example, if you have tiles 2, 3, and 6, and they are all painted red, you have a "red product" because $2 \times 3 = 6$ .

This paper is a mathematical detective story about finding the exact tipping point (the threshold) where it becomes impossible to avoid these matching-colored trios, no matter how cleverly you paint.

The Background: The Sum vs. The Product

Mathematicians have known for a long time that if you have enough numbers, you can't avoid a "monochromatic sum" (where $a + b = c$ ). This is a famous result called Schur's Theorem.

In the 1990s, researchers asked: "What if our bag of numbers is very sparse? How many numbers do we need to pick before we are guaranteed to find a monochromatic sum?" They found the answer: if you pick numbers with a probability roughly equal to $1/\sqrt{n}$ , you are guaranteed to find a sum. If you pick fewer, you can usually avoid it.

This paper asks the same question, but for products ( $a \times b = c$ ) instead of sums.

The Main Discovery: A New Tipping Point

The authors found that the rules for products are very different from the rules for sums.

The "Sum" Rule: For sums, the tipping point is around $n^{-1/2}$ (1 over the square root of $n$ ).
The "Product" Rule: For products, the tipping point is much lower. The authors proved that for a random set of numbers to be guaranteed to have a monochromatic product, the probability of picking a number must be somewhere between $n^{-1/9}$ and $n^{-1/11}$ .

The Analogy:
Think of the "Sum" problem as trying to find a specific shape in a pile of sand. You need a moderate amount of sand to be sure the shape is there.
The "Product" problem is like looking for a specific, very rare crystal formation. Because multiplication grows so fast (2 times 3 is 6, but 10 times 10 is 100), the "crystals" (the triplets $a, b, c$ ) are much harder to form. You need a much denser pile of numbers (a higher probability $p$ ) to guarantee you'll find one, but paradoxically, the math shows the threshold is actually lower in terms of the exponent because the structure of multiplication is so sparse and irregular compared to addition.

How They Solved It: The Two-Pronged Attack

To find this threshold, the authors had to prove two things:

1. The "Bad News" (The Lower Bound):
They showed that if you pick numbers too sparsely (below $n^{-1/9}$ ), you can almost always paint them with two colors (say, Red and Blue) so that no Red trio and no Blue trio exists.

The Method: They used a "Greedy Algorithm." Imagine you are painting the numbers in order from smallest to largest. You try to paint a number Red. If painting it Red would create a Red product with numbers you've already painted, you paint it Blue instead. If painting it Blue would create a Blue product, you're stuck.
The Result: They proved that if the set is sparse enough, this greedy painting process almost never gets stuck. You can successfully color the whole set without making a monochromatic product.

2. The "Good News" (The Upper Bound):
They showed that if you pick numbers densely enough (above $n^{-1/11}$ ), you are guaranteed to find a monochromatic product, no matter how you paint them.

The Method: Instead of trying to color the whole set, they looked for a tiny, specific "trap" pattern. They found a small collection of 15 numbers that, if they all appear in your random set, cannot be colored without creating a monochromatic product. It's like a mathematical puzzle that has no solution.
The Result: They proved that if your probability $p$ is high enough, your random set will almost certainly contain this "trap" pattern. Once the trap is there, the monochromatic product is unavoidable.

Why This Matters

This paper is significant because it breaks the mold. For decades, mathematicians thought that the rules for random sets with sums and products were similar. This paper shows they are fundamentally different.

Sums are regular and predictable.
Products are chaotic and irregular.

The tools mathematicians usually use to solve these problems (which rely on the regularity of sums) failed for products. The authors had to invent new, more creative ways to count the possibilities and build their "traps."

The Multi-Color Twist

The paper also looked at what happens if you have 3, 4, or more colors.

For sums, the number of colors doesn't change the tipping point much.
For products, the number of colors drastically changes the threshold. The more colors you have, the harder it is to force a monochromatic product, and the threshold moves significantly.

Summary

In short, this paper tells us that if you randomly pick numbers from a huge list, there is a very specific "Goldilocks zone" for the probability of picking them.

If you pick too few, you can dodge the "product trap" by painting carefully.
If you pick enough, the universe forces a monochromatic product to appear, no matter how you try to avoid it.

The authors have narrowed this zone down to a specific range, showing that the world of random multiplication is far more complex and interesting than the world of random addition.

Technical Summary: Monochromatic Products in Random Integer Sets

Problem Statement
This paper investigates the threshold probability $p = p(n)$ at which the binomial random subset $[n]_p$ (where each element of $\{1, \dots, n\}$ is included independently with probability $p$ ) almost surely (a.a.s.) possesses the "product-Schur" property. A set $A$ is defined as $r$ -product-Schur if any $r$ -colouring of $A$ yields a monochromatic solution to the equation $ab = c$ with $a, b, c \in A$ . While the thresholds for linear equations (such as Schur's theorem for $a+b=c$ ) are well-understood via Rado's theorem and subsequent transference principles, the behavior of non-linear equations like $ab=c$ in random sets remains largely unexplored. The authors aim to determine the critical density $p^*$ where the random set transitions from almost surely not being product-Schur to almost surely being product-Schur.

Methodology
The paper employs distinct proof strategies for the lower bound (the $(0)$ -statement) and the upper bound (the $(1)$ -statement), noting that standard tools from random Ramsey theory are insufficient for the non-linear setting.

The $(0)$ -Statement (Lower Bound):
To show that $[n]_p$ is not product-Schur for small $p$ , the authors utilize a greedy colouring algorithm. They attempt to partition the random set into two product-free sets (Red and Blue) by iterating through elements in increasing order. An element is assigned a colour if it does not form a monochromatic product with previously coloured elements.
- Obstruction Analysis: The algorithm fails only if a specific "forbidden configuration" of integers exists within the random set. These configurations involve complex multiplicative dependencies (e.g., $c = ab = def$, $a = xyz$, $b = uvw$).
- Counting Argument: The authors perform a detailed case analysis of these forbidden configurations, categorizing them by the number of distinct elements and repetitions. They apply the union bound, leveraging divisor bounds ( $D(n) = n^{o(1)}$ ) to show that for $p \le n^{-1/9 - o(1)}$ , the probability of any such configuration appearing is $o(1)$ .
The $(1)$ -Statement (Upper Bound):
To show that $[n]_p$ is product-Schur for larger $p$ , the authors construct a specific finite product-Schur pattern (a small set of integers that forces a monochromatic solution regardless of 2-colouring).
- Pattern Construction: They define a set $S_{a,b,c,d}$ containing 14 elements generated by products of four base integers. They prove via case analysis that any 2-colouring of this set yields a monochromatic solution to $xy=z$.
- Existence Proof: They demonstrate that if $p = \omega(n^{-1/11})$ , the random set $[n]_p$ a.a.s. contains a copy of this pattern. This is achieved by revealing the random set in stages and showing that the probability of failing to find the necessary base integers ( $a, b, c, d$ ) and their required products is negligible.
- Departure from Standard Methods: The authors explicitly note that standard transference principles and hypergraph container methods (which rely on "supersaturation"—the property that dense sets contain many monochromatic solutions) fail here. For products, there exist colourings where only a vanishing fraction of solutions are monochromatic, rendering supersaturation-based proofs ineffective.
Extension to $r$ Colours:
For $r \ge 3$ , the authors generalize the results using Schur numbers ( $S(r)$ ) and double-sum Schur numbers ( $S'(r)$ ).
- Lower Bound: They construct a colouring based on intervals scaled by $n^{1/S'(r)}$ , avoiding monochromatic sums and shifted sums, which translates to avoiding monochromatic products.
- Upper Bound: They utilize the set $U_x = \{x, x^2, \dots, x^{S(r)}\}$ , which is not $r$ -product-colourable by the definition of $S(r)$ . They show that for $p = \omega(n^{-1/S(r)^2})$ , such a set appears a.a.s.

Key Results

Theorem 1.2 (Two Colours): The threshold for $[n]_p$ $[n]_{p}$ to be product-Schur lies between $n^{-1/9 - o(1)}$ $n^{- 1/9 - o (1)}$ and $n^{-1/11}$ $n^{- 1/11}$ . Specifically:
- If $p \le n^{-1/9 - o(1)}$ , $[n]_p$ is a.a.s. not product-Schur.
- If $p \ge \omega(n^{-1/11})$ , $[n]_p$ is a.a.s. product-Schur.
Theorem 1.4 ( $r$ Colours): For $r \ge 2$ $r \geq 2$ , the threshold $p^*_r$ $p_{r}^{*}$ satisfies:
- $p^*_r \le n^{-1/S'(r)}$ (Lower bound on threshold / Upper bound on $p$ for non-existence).
- $p^*_r \ge n^{-1/S(r)^2}$ (Upper bound on threshold / Lower bound on $p$ for existence).
- Crucially, unlike linear equations where the threshold is independent of $r$ , the threshold for products depends on the number of colours.

Significance and Claims
The paper claims to be the first to explore the Ramsey properties of random sets regarding non-linear equations, specifically monochromatic products. Its primary contributions are:

Establishing Threshold Bounds: Providing the first non-trivial bounds for the product-Schur threshold, showing it is distinct from the linear case ( $n^{-1/2}$ ).
Methodological Innovation: Demonstrating that the proof techniques for non-linear Ramsey properties differ substantially from linear ones. The authors argue that the lack of supersaturation in product sets invalidates the powerful transference principles and container methods that solved linear Rado-type problems, necessitating new approaches like greedy colouring analysis and specific pattern embedding.
Dependence on Colours: Highlighting that for non-linear equations, the threshold depends on the number of colours $r$ , contrasting with the colour-independence observed in linear Rado theorems.

Conjectures and Future Directions
The authors conjecture that the true threshold is $n^{-1/11}$ , matching their upper bound. They suggest this is determined by the appearance of the specific bounded-size configuration used in their proof. They acknowledge that improving the lower bound ( $n^{-1/9}$ ) would likely require new ideas beyond refined greedy colouring. Finally, they propose that their techniques could be applied to other non-linear equations, such as $a^2 = bc$ or $ab = cd$.