Tópico: Método Probabilístico

Uma importante ferramenta em várias áreas da matemática, tais como Teoria dos Números, Combinatória e Teoria da Computação é o que chamamos de Método Probabilístico.

Em várias situações, nós precisamos de mostrar a existência de objetos satisfazendo determinadas propriedades, mas não temos informação suficiente ou capacidade para construí-los explicitamente. Nesse caso, podemos recorrer ao Método Probabilístico, que simplesmente nos sugere tomar um objeto aleatório de uma maneira esperta e mostrar que com probabilidade positiva as propriedades desejadas serão satisfeitas. Esse método, apesar de muito ingênuo, é muito eficiente e em diversos casos provê os melhores exemplos conhecidos de certos objetos (para embaraço da comunidade científica).

Nessa seção daremos um exemplo em Teoria dos Números provido primeiramente por Erdõs¹¹ 1 Somos gratos a Robert Morris por sugerir esse teorema como exemplo do Método Probabilístico..

{theorem}

[Erdös] Para todo conjunto finito $A\subset\mathbb{N}$ , existe um sub-conjunto $B\subseteq A$ satisfazendo

a)

$\#B\geq\frac{\#A}{3}$ e tal que
b)

não existem $x,y$ e $z\in B$ com $x+y=z$ .

A propriedade $b)$ acima é o que chamamos de um conjunto ser livre de somas.

Certamente não temos muita informação sobre $A$ , então vamos usar o método probabilístico para a prova desse teorema.

Demonstração.

Fixamos $p$ um número primo maior que três vezes o maior elemento de $A$ e considere o espaço $\mathbb{Z}_{p}$ dos inteiros módulo $p$ . Seja $X$ um elemento aleatório de $\mathbb{Z}_{p}$ com distribuição uniforma, isto é $U_{\{0,\dots,p-1\}}$ . {exercise} Mostre que para todo $a\in A$ , a multiplicação por $a$ é uma bijeção em $\mathbb{Z}_{p}$ , ou seja

\mathbb{Z}_{p}\cdot a=\mathbb{Z}_{p}.

(2.3)

onde o produto $\mathbb{Z}_{p}\cdot a$ é entendido elemento a elemento. Conclua que

P\Big{[}X\cdot a\in\big{[}\tfrac{p}{3},\tfrac{2p}{3}\big{)}\Big{]}\geq\frac{1}% {3}-\frac{1}{p}.

(2.4)

Definimos o conjunto aleatório

\mathcal{B}=\{a\in A\ |X\cdot a\in[\tfrac{p}{3},\tfrac{2p}{3})\}.

(2.5)

Esse conjunto é livre de soma: se $X=0$ o conjunto é vazio e, nos outros casos, se $a,b\in\mathcal{B}$ então

X(a+b)\in[\tfrac{2p}{3},\tfrac{4p}{3})

(2.6)

que é o complemento de $[\tfrac{p}{3},\tfrac{2p}{3})$ em $\mathbb{Z}_{p}$ .

Basta portanto mostrar que com probabilidade positiva $\#\mathcal{B}\geq\tfrac{\#A}{3}$ , que segue do seguinte argumento. Note inicialmente que

\int\#\mathcal{B}\d{P}=\int\sum_{a\in A}\1_{\big{[}X\cdot a\in[p/3,2p/3)\big{]% }}\d{P}\\ =\sum_{a\in A}P\Big{[}X\cdot a\in\big{[}\tfrac{p}{3},\tfrac{2p}{3}\big{)}\Big{% ]}\geq\frac{\#A}{3}-\frac{\#A}{p}>\frac{\#A-1}{3},

mas, para qualquer variável aleatória, $P[Y\geq\int Y\d{P}]>0$ . Nesse caso, isso implica

P[\#\mathcal{B}\geq\tfrac{\#A}{3}]=P[\#\mathcal{B}>\tfrac{\#A-1}{3}]\geq P\Big% {[}\#\mathcal{B}>\int\#\mathcal{B}\d{P}\Big{]}>0.

(2.7)

∎

¹¹todo: 1 Adicionar contexto histórico: citar artigo Erdos e o Annals of Math que mostra que não é possível com

\#A(1/3+\varepsilon)