🔢 mathematics

Monochromatic products in random integer sets

Este artigo investiga a probabilidade de limiar na qual um subconjunto aleatório de inteiros contém quase certamente uma solução monocromática para a equação $ab=c$ sob uma 2-coloração, estabelecendo limites entre $n^{-1/9-o(1)}$ e $n^{-1/11}$ e demonstrando que o comportamento e as técnicas de prova para tais equações não lineares diferem substancialmente das de equações lineares.

Autores originais: Roger Lidón, Darío Martínez, Patrick Morris, Miquel Ortega

Publicado 2026-01-15

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Roger Lidón, Darío Martínez, Patrick Morris, Miquel Ortega

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você tem um saco gigante de peças numeradas, de 1 a $n$ . Você decide pegar um punhado aleatório dessas peças para guardar, jogando uma moeda para cada uma: cara, você a guarda; coroa, você a descarta. A probabilidade de guardar uma peça é $p$ .

Agora, imagine que você tem um balde de tinta com $r$ cores diferentes. Você quer pintar todas as peças do seu punhado aleatório. A grande questão é: é possível pintá-las de uma forma que evite a criação de um "produto monocromático"?

Um "produto monocromático" é um trio de peças $(a, b, c)$ que são todas da mesma cor, onde $a \times b = c$ . Por exemplo, se você tiver as peças 2, 3 e 6, e todas forem pintadas de vermelho, você tem um "produto vermelho" porque $2 \times 3 = 6$ .

Este artigo é uma história de detetive matemática sobre encontrar o ponto de virada exato (o limiar) onde se torna impossível evitar esses trios de cores iguais, não importa o quão habilidosamente você pinte.

O Contexto: A Soma vs. O Produto

Matemáticos sabem há muito tempo que, se você tiver números suficientes, não conseguirá evitar uma "soma monocromática" (onde $a + b = c$ ). Este é um resultado famoso chamado Teorema de Schur.

Na década de 1990, pesquisadores perguntaram: "E se o nosso conjunto de números for muito esparso? Quantos números precisamos escolher antes de estarmos garantidos a encontrar uma soma monocromática?" Eles descobriram a resposta: se você escolher números com uma probabilidade aproximadamente igual a $1/\sqrt{n}$ , você está garantido a encontrar uma soma. Se escolher menos, você geralmente consegue evitá-la.

Este artigo faz a mesma pergunta, mas para produtos ( $a \times b = c$ ) em vez de somas.

A Descoberta Principal: Um Novo Ponto de Virada

Os autores descobriram que as regras para produtos são muito diferentes das regras para somas.

A Regra da "Soma": Para somas, o ponto de virada é em torno de $n^{-1/2}$ (1 sobre a raiz quadrada de $n$ ).
A Regra do "Produto": Para produtos, o ponto de virada é muito mais baixo. Os autores provaram que, para um conjunto aleatório de números ter a garantia de possuir um produto monocromático, a probabilidade de escolher um número deve estar em algum lugar entre $n^{-1/9}$ e $n^{-1/11}$ .

A Analogia:
Pense no problema da "Soma" como tentar encontrar uma forma específica em uma pilha de areia. Você precisa de uma quantidade moderada de areia para ter certeza de que a forma está lá.
O problema do "Produto" é como procurar por uma formação de cristal muito rara. Como a multiplicação cresce muito rápido (2 vezes 3 é 6, mas 10 vezes 10 é 100), os "cristais" (os trios $a, b, c$ ) são muito mais difíceis de se formar. Você precisa de uma pilha de números muito mais densa (uma probabilidade $p$ mais alta) para garantir que encontrará um, mas, paradoxalmente, a matemática mostra que o limiar é na verdade menor em termos de expoente porque a estrutura da multiplicação é tão esparsa e irregular comparada à adição.

Como Eles Resolveram: O Ataque de Duas Frentes

Para encontrar esse limiar, os autores tiveram que provar duas coisas:

1. A "Má Notícia" (O Limite Inferior):
Eles mostraram que, se você escolher números de forma muito esparsa (abaixo de $n^{-1/9}$ ), você quase sempre pode pintá-los com duas cores (digamos, Vermelho e Azul) de modo que nenhum trio vermelho e nenhum trio azul exista.

O Método: Eles usaram um "Algoritmo Ganancioso" (Greedy Algorithm). Imagine que você está pintando os números em ordem, do menor para o maior. Você tenta pintar um número de Vermelho. Se pintar um número de Vermelho criaria um produto vermelho com números que você já pintou, você o pinta de Azul em vez disso. Se pintar de Azul criasse um produto azul, você fica travado.
O Resultado: Eles provaram que, se o conjunto for esparso o suficiente, esse processo de pintura ganancioso quase nunca trava. Você consegue colorir todo o conjunto sem criar um produto monocromático.

2. A "Boa Notícia" (O Limite Superior):
Eles mostraram que, se você escolher números de forma densa o suficiente (acima de $n^{-1/11}$ ), você encontrará garantidamente um produto monocromático, não importa como você os pinte.

O Método: Em vez de tentar colorir todo o conjunto, eles procuraram por um padrão de "armadilha" pequeno e específico. Eles encontraram uma pequena coleção de 15 números que, se todos aparecerem no seu conjunto aleatório, não podem ser coloridos sem criar um produto monocromático. É como um quebra-cabeça matemático que não tem solução.
O Resultado: Eles provaram que, se sua probabilidade $p$ for alta o suficiente, seu conjunto aleatório conterá quase certamente esse padrão de "armadilha". Uma vez que a armadilha está lá, o produto monocromático é inevitável.

Por Que Isso Importa

Este artigo é significativo porque ele quebra o molde. Por décadas, matemáticos pensaram que as regras para conjuntos aleatórios com somas e produtos eram semelhantes. Este artigo mostra que elas são fundamentalmente diferentes.

As Somas são regulares e previsíveis.
Os Produtos são caóticos e irregulares.

As ferramentas que os matemáticos costumam usar para resolver esses problemas (que dependem da regularidade das somas) falharam para os produtos. Os autores tiveram que inventar maneiras novas e mais criativas de contar as possibilidades e construir suas "armadilhas".

A Reviravolta das Múltiplas Cores

O artigo também analisou o que acontece se você tiver 3, 4 ou mais cores.

Para somas, o número de cores não altera muito o ponto de virada.
Para produtos, o número de cores altera drasticamente o limiar. Quanto mais cores você tem, mais difícil é forçar um produto monocromático, e o limiar se desloca significativamente.

Resumo

Em suma, este artigo nos diz que, se você escolher números aleatoriamente de uma lista enorme, existe uma "zona de ouro" muito específica para a probabilidade de escolha.

Se você escolher poucos demais, você pode esquivar-se da "armadilha do produto" pintando cuidadosamente.
Se você escolher o suficiente, o universo força o aparecimento de um produto monocromático, não importa o quanto você tente evitá-lo.

Os autores estreitaram essa zona para um intervalo específico, mostrando que o mundo da multiplicação aleatória é muito mais complexo e interessante do que o mundo da adição aleatória.

Resumo Técnico: Produtos Monocromáticos em Conjuntos de Inteiros Aleatórios

Enunciado do Problema
Este artigo investiga o limiar de probabilidade $p = p(n)$ no qual o subconjunto binomial aleatório $[n]_p$ (onde cada elemento de $\{1, \dots, n\}$ é incluído independentemente com probabilidade $p$ ) possui quase certamente (a.a.s.) a propriedade "product-Schur". Um conjunto $A$ é definido como $r$ -product-Schur se qualquer $r$ -coloração de $A$ produz uma solução monocromática para a equação $ab = c$ com $a, b, c \in A$ . Embora os limiares para equações lineares (como o teorema de Schur para $a+b=c$ ) sejam bem compreendidos via o teorema de Rado e princípios de transferência subsequentes, o comportamento de equações não lineares como $ab=c$ em conjuntos aleatórios permanece amplamente inexplorado. Os autores visam determinar a densidade crítica $p^*$ onde o conjunto aleatório transiciona de quase certamente não ser product-Schur para quase certamente ser product-Schur.

Metodologia
O artigo emprega estratégias de prova distintas para o limite inferior (a declaração $(0)$ ) e o limite superior (a declaração $(1)$ ), observando que ferramentas padrão da teoria Ramsey aleatória são insuficientes para o cenário não linear.

A Declaração $(0)$ (Limite Inferior):
Para mostrar que $[n]_p$ não é product-Schur para $p$ pequeno, os autores utilizam um algoritmo de coloração gulosa (greedy). Eles tentam particionar o conjunto aleatório em dois conjuntos livre de produtos (Vermelho e Azul) iterando através dos elementos em ordem crescente. Um elemento recebe uma cor se não formar um produto monocromático com elementos previamente coloridos.
- Análise de Obstrução: O algoritmo falha apenas se uma "configuração proibida" específica de inteiros existir dentro do conjunto aleatório. Essas configurações envolvem dependências multiplicativas complexas (ex: $c = ab = def$, $a = xyz$, $b = uvw$).
- Argumento de Contagem: Os autores realizam uma análise detalhada de caso dessas configurações proibidas, categorizando-as pelo número de elementos distintos e repetições. Eles aplicam o limite da união, utilizando limites de divisores ( $D(n) = n^{o(1)}$ ) para mostrar que, para $p \le n^{-1/9 - o(1)}$ , a probabilidade de tal configuração aparecer é $o(1)$ .
A Declaração $(1)$ (Limite Superior):
Para mostrar que $[n]_p$ é product-Schur para $p$ maior, os autores constroem um padrão específico de finite product-Schur (um pequeno conjunto de inteiros que força uma solução monocromática independentemente de uma 2-coloração).
- Construção de Padrão: Eles definem um conjunto $S_{a,b,c,d}$ contendo 14 elementos gerados por produtos de quatro inteiros base. Eles provam, via análise de caso, que qualquer 2-coloração deste conjunto produz uma solução monocromática para $xy=z$.
- Prova de Existência: Eles demonstram que, se $p = \omega(n^{-1/11})$ , o conjunto aleatório $[n]_p$ contém a.a.s. uma cópia deste padrão. Isso é alcançado revelando o conjunto aleatório em estágios e mostrando que a probabilidade de falhar em encontrar os inteiros base necessários ( $a, b, c, d$ ) e seus produtos requeridos é desprezível.
- Divergência de Métodos Padrão: Os autores explicitamente observam que princípios de transferência padrão e métodos de contêineres de hipergrafos (que dependem de "supersaturação" — a propriedade de que conjuntos densos contêm muitos soluções monocromáticas) falham aqui. Para produtos, existem colorações onde apenas uma fração evanescente das soluções é monocromática, tornando provas baseadas em supersaturação ineficazes.
Extensão para $r$ Cores:
Para $r \ge 3$ , os autores generalizam os resultados usando números de Schur ( $S(r)$ ) e números de Schur de soma dupla ( $S'(r)$ ).
- Limite Inferior: Eles constroem uma coloração baseada em intervalos escalonados por $n^{1/S'(r)}$ , evitando somas monocromáticas e somas deslocadas, o que se traduz em evitar produtos monocromáticos.
- Limite Superior: Eles utilizam o conjunto $U_x = \{x, x^2, \dots, x^{S(r)}\}$ , que não é $r$ -product-colorível pela definição de $S(r)$ . Eles mostram que para $p = \omega(n^{-1/S(r)^2})$ , tal conjunto aparece a.a.s.

Resultados Principais

Teorema 1.2 (Duas Cores): O limiar para $[n]_p$ $[n]_{p}$ ser product-Schur situa-se entre $n^{-1/9 - o(1)}$ $n^{- 1/9 - o (1)}$ e $n^{-1/11}$ $n^{- 1/11}$ . Especificamente:
- Se $p \le n^{-1/9 - o(1)}$ , $[n]_p$ é a.a.s. não product-Schur.
- Se $p \ge \omega(n^{-1/11})$ , $[n]_p$ é a.a.s. product-Schur.
Teorema 1.4 ( $r$ Cores): Para $r \ge 2$ $r \geq 2$ , o limiar $p^*_r$ $p_{r}^{*}$ satisfaz:
- $p^*_r \le n^{-1/S'(r)}$ (Limite inferior no limiar / Limite superior para $p$ de não existência).
- $p^*_r \ge n^{-1/S(r)^2}$ (Limite superior no limiar / Limite inferior para existência).
- Crucialmente, ao contrário de equações lineares onde o limiar é independente de $r$ , o limiar para produtos depende do número de cores.

Significância e Alegações
O artigo afirma ser o primeiro a explorar as propriedades Ramsey de conjuntos aleatórios em relação a equações não lineares, especificamente produtos monocromáticos. Suas principais contribuições são:

Estabelecimento de Limites de Limiar: Fornecer os primeiros limites não triviais para o limiar de product-Schur, mostrando que ele é distinto do caso linear ( $n^{-1/2}$ ).
Inovação Metodológica: Demonstrar que as técnicas de prova para propriedades Ramsey não lineares diferem substancialmente das lineares. Os autores argumentam que a falta de supersaturação em conjuntos de produtos invalida os poderosos princípios de transferência e métodos de contêineres que resolveram problemas do tipo Rado lineares, necessitando de novas abordagens como análise de coloração gulosa e incorporação de padrões específicos.
Dependência de Cores: Destacar que, para equações não lineares, o limiar depende do número de cores $r$ , contrastando com a independência de cores observada nos teoremas de Rado lineares.

Conjecturas e Direções Futuras
Os autores conjecturam que o verdadeiro limiar é $n^{-1/11}$ , correspondendo ao seu limite superior. Eles sugerem que este é determinado pela aparição da configuração específica de tamanho limitado usada em sua prova. Eles reconhecem que melhorar o limite inferior ( $n^{-1/9}$ ) provavelmente exigiria novas ideias além da coloração gulosa refinada. Finalmente, propõem que suas técnicas poderiam ser aplicadas a outras equações não lineares, como $a^2 = bc$ ou $ab = cd$.