Proof of SLLL Using GLLL

To derive SLLL from GLLL, set xi=1d+1x_i = \frac{1}{d+1} for all ii (noting that 1d+1<1\frac{1}{d+1} < 1 for d≥0d \geq 0). Then, for each ii,

∏j∈Γ(i)(1−xj)=(1−1d+1)∣Γ(i)∣≥(1−1d+1)d=1(d+1)d⋅(1+1/d)d≥1(d+1)d⋅e \prod_{j \in \Gamma(i)} (1 - x_j) = \left(1 - \frac{1}{d+1}\right)^{|\Gamma(i)|} \\\geq \left(1 - \frac{1}{d+1}\right)^d = \frac{1}{(d+1)^d \cdot (1 + 1/d)^d} \geq \frac{1}{(d+1)^d \cdot e}

where the last inequality uses the fact that (1+1/d)d≤e(1 + 1/d)^d \leq e for all d≥1d \geq 1 (and holds trivially for d=0d=0).

Thus,

xi∏j∈Γ(i)(1−xj)≥1d+1⋅1(d+1)d⋅e=1e(d+1)d+1. x_i \prod_{j \in \Gamma(i)} (1 - x_j) \geq \frac{1}{d+1} \cdot \frac{1}{(d+1)^d \cdot e} = \frac{1}{e (d+1)^{d+1}}.

The condition of SLLL is ep(d+1)≤1e p (d+1) \leq 1, which rearranges to p≤1e(d+1)p \leq \frac{1}{e (d+1)}. However, to match the GLLL bound, note that the standard SLLL condition is actually sufficient for a slightly stronger bound, but for the common form ep(d+1)≤1e p (d+1) \leq 1, it ensures p≤1e(d+1)p \leq \frac{1}{e (d+1)}, so

p≤1e(d+1)≤1e(d+1)d+1⋅(d+1)d≤xi∏j∈Γ(i)(1−xj), p \leq \frac{1}{e (d+1)} \leq \frac{1}{e (d+1)^{d+1}} \cdot (d+1)^d \leq x_i \prod_{j \in \Gamma(i)} (1 - x_j),

satisfying the GLLL hypothesis. Therefore, by GLLL,

Pr⁡(⋂i=1nAi‾)≥∏i=1n(1−1d+1)=(dd+1)n>0. \Pr\left( \bigcap_{i=1}^n \overline{A_i} \right) \geq \prod_{i=1}^n \left(1 - \frac{1}{d+1}\right) = \left(\frac{d}{d+1}\right)^n > 0.

This completes the proof.