The lower tail: Poisson approximation revisited

Introduction

counts the number of sets $Q(\alpha)$ that are entirely contained in $\Gamma_{{\mathbf{p}}}$. We write $\alpha\sim\beta$ if $Q(\alpha)\cap Q(\beta)\neq\emptyset$ and $\alpha\neq\beta$, which intuitively means that there are ‘dependencies’ between $I_{\alpha}$ and $I_{\beta}$. Let

(We write $\mu(X)$, $\Pi(X)$, $\Lambda(X)$ and $\delta(X)$ in case of ambiguity.) Note that $\delta$ measures how dependent the indicators $I_{\alpha}$ are (with $\delta=0$ in the case of independent summands), and that $\operatorname{Var}X\leqslant\Lambda$ holds. In the first author proved the following lower tail analogue (often called Janson’s inequality, see, e.g., ) of the Bernstein and Chernoff bounds for sums of independent indicators (the case $\delta=0$): with $\varphi(x)=(1+x)\log(1+x)-x$, for all $\varepsilon\in$ we have

where $\varphi(-1)=1$, $\varepsilon^{2}/2\leqslant\varphi(-\varepsilon)\leqslant\varepsilon^{2}$ and $\varphi(-\varepsilon)=\varepsilon^{2}/2+O(\varepsilon^{3})$ for $\varepsilon\in$. As discussed in , inequality (2) is quite attractive because it (i) yields Poisson-like tail estimates in the weakly dependent case $\delta=O(1)$, (ii) usually corresponds to a (one-sided) exponential version of Chebyshev’s inequality, and (iii) often qualitatively matches the tail behaviour suggested by the central limit theorem. For example, it is well-known (and not hard to check) that $\Lambda=\Theta(\operatorname{Var}X)$ if $\widehat{p}=\max\{\Pi,\max_{i}p_{i}\}$ is bounded away from one, that $\widehat{p}\to 0$ implies $\Lambda\sim\operatorname{Var}X$, and that $\delta,\Pi\to 0$ implies $\Lambda\sim\mu\sim\operatorname{Var}X$.

The inequality (2) is nowadays a widely used tool in probabilistic combinatorics (see, e.g., and the references therein), which makes it important to understand how ‘sharp’ it is, i.e., whether the exponential rate of decay given by (2) is best possible. For sums of independent Bernoulli random variables we have $\delta=0$ and (2) coincides with the Chernoff bounds, where the exponent is well-known to be best possible if $\max_{i}p_{i}=o(1)$. However, it is doubtful whether such examples are of any significance for concrete applications with $\delta>0$. Fortunately, whenever $\Pi<1$, Harris’ inequality gives, as noted in ,

In this paper we prove that “Janson’s inequality” (2) is close to best possible in many situations of interest. Our first result shows that, for large deviations, the rate of decay of (2) is optimal for any random variable $X$ of type (1) that is approximately Poisson, i.e., whenever $\delta,\Pi\to 0$ (see ).

With $\varphi(-1)=1$ in mind, note that (4) qualitatively extends the lower bound (3) resulting from Harris’ inequality to general $\varepsilon$. Here the condition $\varepsilon^{2}\mu=\Omega(1)$ is natural in the context of exponentially small probabilities since $(1+\xi)\varphi(-\varepsilon)=\Theta(\varepsilon^{2})$. As discussed, our favourite range is when $\delta,\Pi\to 0$. For large deviations, i.e., when $\varepsilon^{2}\mu\to\infty$ holds, (2) and (4) then yield

Our second result yields a related conclusion when $\delta=O(1)$ and $\Pi$ is bounded away from one. More precisely, in this ‘weakly dependent’ case Theorem 2 shows that the decay of the inequality (2) is best possible up to constant factors in the exponent.

A key feature of (5) is that it holds for any $\Pi<1$ (and that the dependence of $K$ on $\Pi$ is explicit). Note that usually $K=\Theta(1)$. Whenever $\delta=O(1)$, inequalities (2) and (5) then yield

where the implicit constants differ by a factor of at most $2K(1+\delta)^{2}=O(1)$. This subsumes the folklore fact that Chernoff bounds (where $\delta=0$) are sharp up to constants in the exponent if $\max_{i}p_{i}$ is bounded away from one. While the numerical value of $K$ is often immaterial, better constant factors can typically be obtained, if desired, by reworking the proof (optimizing certain parameters to the situation at hand).

The proofs of Theorem 1 and 2 hinge on Hölder’s inequality and several estimates of the Laplace transform (which in turn are based on correlation inequalities), see Section 2. In fact, an inspection of the proofs reveals that Theorem 1 and 2 (as well as (3), Theorem 6 and Lemma 7) remain valid for the more general correlation conditions (and setup) stated by Riordan and Warnke . It would be interesting to know whether similar results also hold under the weaker dependency assumptions of Suen’s inequality .

2 Main example

From an applications point of view it is important to also understand the sharpness of (2) in the case $\delta=\Omega(1)$, i.e., when $X$ is no longer close to Poisson. In Section 3 we present correlation-inequality based bootstrapping approaches which often allow us to deal with this remaining ‘strongly dependent’ case. The punchline seems to be that, in the presence of certain symmetries, the inequality (2) is oftentimes best possible up to constant factors in the exponent.

The upper bound of (6) follows from (2) via standard calculations (see, e.g., or Lemma 22), and so the real content of this theorem is the ‘matching’ lower bound. A key feature of Theorem 3 is that $\varepsilon$ is not fixed, but may depend on $n$. In the context of exponentially decaying probabilities, note that the $\varepsilon^{2}\Phi_{H}=\Omega(1)$ condition is natural (unless $p\approx 1$). In applications $p$ is typically bounded away from one (in fact, $p=o(1)$ is often standard), in which case (6) yields

determining the large deviation rate function of $X_{H}$ up to constants factors. For the special case $\varepsilon=1$ (and $k=2$) this was established more than 25 years ago by Janson, Łuczak and Ruciński , and for $\varepsilon\geqslant\varepsilon_{0}$ an analogous statement is nowadays easily deduced from (2) and (3), see also (73). By contrast, the case $\varepsilon\to 0$ seems to have eluded further attention, and Theorem 3 rectifies this (surprising) gap in the literature.

Let $H$ be a $k$-graph with $e_{H}\geqslant 1$. If $p=p(n)=o(1)$ and $\varepsilon=\varepsilon(n)\in$ satisfy $p=\omega(n^{-1/m_{k}(H)})$ and $\varepsilon^{2}\binom{n}{k}p=\omega(1)$, then we have

Here our main contributions are the tight lower bound of (9), and the case $\varepsilon=o(1)$ of (10). Theorem 4 is a natural extension of earlier work of Janson, Łuczak and Ruciński for the special case $\varepsilon=1$ (and $k=2$). Theorem 5 partially solves an open problem of , but in the relevant case $\varepsilon=1$ inequality (10) is a fairly simple consequence of the recent ‘hypergraph container’ results of Saxton and Thomason , see also Lemma 23. With $\varphi(-\varepsilon)=\Theta(\varepsilon^{2})$ in mind the conditions involving $\varepsilon^{2}$ are natural in both results – up to the logarithmic term in case of Theorem 4, which seems to be an artefact of our proof (we leave its removal as an open problem, see Section 3.2). The form of the exponent in Theorem 5 differs in an intriguing way for $\varepsilon=o(1)$ and $\varepsilon=1-o(1)$. In particular, (10) provides a natural example where the inequality (2) does not always give the correct constants in the exponent when $\delta=\omega(1)$: in the case $\varepsilon=1-o(1)$, the ‘extremal’ structural properties of $H$-free graphs come into play. We leave it as an open problem to determine the finer behaviour of the exponent (i.e., with explicit constants) in the ‘intermediate’ range $\varepsilon=\Theta(1)$. This seems of particular interest since Theorem 4 and 5 nearly cover all edge probabilities $p$ for balanced $k$-graphs with $e_{H}\geqslant 2$ and $m_{k}(H)=(e_{H}-1)/(v_{H}-k)$, where $G=H$ for $p=o(n^{-1/m_{k}(H)})$; for $k=2$ (when this class usually is called 2-balanced) this class includes, e.g., trees, cycles, complete graphs, complete $r$-partite graphs $K_{t,\ldots,t}$ and the $d$-dimensional cube.

The rest of the paper is organized as follows. First, in Section 2, we prove Theorem 1 and 2. Next, in Section 3, we present several bootstrapping approaches that yield lower bounds for the lower tail, which are subsequently illustrated in Section 4. Namely, in Section 4.1 we apply them to the number of arithmetic progressions in random subsets of the integers, and in Section 4.2 we apply them to subgraph counts in random hypergraphs and prove Theorems 3–5.

Lower bounds for the lower tail

In this section we prove Theorem 1 and 2, i.e., establish lower bounds for the lower tail. Since our core argument breaks down when $\varepsilon$ is very close to one, en route to Theorem 1 we establish the following (slightly sharper) complementary estimates.

with $\xi=135\max\{\Pi^{1/4},\delta^{1/4},[e(1-\varepsilon)\varepsilon^{2}\mu]^{-1/2}\}$.

with $\zeta=10\max\{\sqrt{1-\varepsilon},\Pi/(1-\Pi)\}$.

While Lemma 7 follows from (3) via calculus (see Lemma 11), the remaining proofs are not a mere refinement of , but contain several new ideas and ingredients. This includes integrating the logarithmic derivative of the Laplace transform over the interval $[r,t]$ instead of the usual $[0,t]$ (see the proof of Lemma 9), using Hölder’s inequality with parameter $p\to 1$ instead of the Cauchy–Schwarz inequality (see Section 2.2), and a careful treatment of second order error terms (see, e.g., Lemma 8 and 14).

We first collect some basic estimates of the Laplace transform of $X$ as defined in Section 1.

For all $s\geqslant 0$ satisfying $\lambda=\Pi(1-e^{-s})<1$ we have

The FKG inequality (or Harris’s inequality ) yields

For all $t\geqslant r\geqslant 0$ we have

Next, we state some technical estimates of $\varphi(-\varepsilon)=(1-\varepsilon)\log(1-\varepsilon)+\varepsilon$ for later reference (these can safely be skipped on first reading). Following standard conventions, for $k\in\{1,2\}$ we have $0\log^{k}(0)=\lim_{\varepsilon\nearrow 1}(1-\varepsilon)\log^{k}(1-\varepsilon)=0$, so that $\varphi(-1)=1$.

For all $1-e^{-1}\leqslant\varepsilon\leqslant 1$ we have

For all $\varepsilon\in$ and $A\in[0,\infty)$ we have, with $\gamma=A-1$,

The elementary proofs of Lemma 10–12 are deferred to Appendix A.

2 Proof strategy

Noting that $q=q/p+1=1/(p-1)+1$, we infer

So, using Lemma 9 together with $\delta\to 0$, we expect that (replacing the difference quotient by the derivative), as $p\to 1$,

The point is that $1-e^{-s}-se^{-s}\to\varphi(-\varepsilon)$ as $s\to z$. So, if (20) and (21) essentially determine the right hand side of (19), then our previous considerations suggest

Luckily, our later calculations confirm that (for suitable choices of $p$ and $s$) we can indeed essentially ignore the first term on the right hand side of (19) for large deviations, i.e., when $\varepsilon^{2}\mu\to\infty$ holds.

3 Proofs of Theorem 2 and 6

Assume that $\varepsilon,\tau\in(0,1)$ and $\sigma\in(0,\infty)$. Let

so that $p,q\in(1,\infty)$ and $1/p+1/q=1$. Furthermore, let

With (19) in mind, the following two lemmas are at the heart of our argument.

With definitions as above, if $\Pi(1-e^{-s})\leqslant 1/2$, then

with $\eta=2p^{2}(\sigma+p\delta+\Pi)+2p\sigma$.

Since $f(x)=-e^{-x}$ satisfies $f^{\prime}(x)=e^{-x}$, the mean value theorem implies that there is $\zeta\in[1,p]$ such that

Furthermore, since $g(x)=e^{-x}$ satisfies $g^{\prime}(x)=-e^{-x}$ and $g^{\prime\prime}(x)=e^{-x}\geqslant 0$, using Taylor’s theorem with remainder, we obtain

Note that $(1+\delta)p-1=\sigma+p\delta$. Furthermore, since $s=-p\log(1-\varepsilon)$, Bernoulli’s inequality yields

So, by combining Lemmas 8 and 9 with (25)–(27), using $\Pi(1-e^{-s})\leqslant 1/2$, it follows that

Let $g(x)=1-e^{-x}-xe^{-x}$, and note that $g(z)=\varphi(-\varepsilon)$. Furthermore, for $z\leqslant x\leqslant s$ we have $g^{\prime}(x)=xe^{-x}\leqslant se^{-z}$. So, using Taylor’s theorem with remainder, we deduce that

Consequently, since $s=pz\geqslant z$, we obtain

where $\eta_{1}=p^{2}(\sigma+p\delta)+p\sigma$ and $\eta_{2}=p^{2}\Pi$. Finally, recalling $z=-\log(1-\varepsilon)$, the point is that Lemma 10 yields $\max\{z^{2}e^{-z},\varepsilon^{2}\}\leqslant 2\varphi(-\varepsilon)$, yielding the result with $\eta=2\eta_{1}+2\eta_{2}$. ∎

With definitions as above, if $\lambda=\Pi(1-e^{-s})<1$ and $(1-\tau)\sigma^{2}(1-\varepsilon)^{p}\geqslant p^{2}\Pi/(1-\lambda)+\delta/(1+\delta)$, then

Let $t=z/(1+\delta)$. Recalling $\varphi(-\varepsilon)=(1-\varepsilon)\log(1-\varepsilon)+\varepsilon$, note that

So, using $t\leqslant s$ and Lemma 9 (with $r=0$), it follows that

Set $h(x)=(1-\varepsilon)x-(1-e^{-x})$, and note that $h(z)=-\varphi(-\varepsilon)$ and $h^{\prime}(z)=0$. Furthermore, for $x\leqslant s$ we have $h^{\prime\prime}(x)=e^{-x}\geqslant e^{-s}$. So, using Taylor’s theorem with remainder, we obtain

Recalling $p=1+\sigma$, $s=pz$ and $\lambda=\Pi(1-e^{-s})$, by combining Lemma 8 with (30), (31) and $(1-e^{-s})^{2}\leqslant s^{2}$, we infer

Since Lemma 10 gives $\varphi(-\varepsilon)\leqslant\log^{2}(1-\varepsilon)/2=z^{2}/2$, we have, by assumption,

Now, inserting (32) into (29), using the fact that $e^{-x}+e^{-1/x}\leqslant 1$ for $x>0$ (as in the proof of Theorem 2 in ), we obtain

Finally, recalling $z=-\log(1-\varepsilon)$, Lemma 10 yields $z^{2}\geqslant\varepsilon^{2}$ and $1\leqslant 2\varphi(-\varepsilon)/\varepsilon^{2}$. ∎

Combining (19) with Lemma 13 and 14, the proofs of Theorem 2 and 6 reduce to defining suitable parameters $\sigma$ and $\tau$ (our choices are somewhat ad-hoc, and yield fairly transparent error-terms).

Note that the assumption $0\leqslant\varepsilon\leqslant 1-4\max\{\Pi^{1/4},\delta^{1/4}\}$ implies $\max\{\Pi,\delta\}\leqslant 4^{-4}$, so that $\lambda=\Pi(1-e^{-s})\leqslant\Pi\leqslant 1/5$. Hence, using $e(1-\varepsilon)\varepsilon^{2}\mu\geqslant 1$, we see that $\sigma\leqslant 1$ and thus $p\leqslant 2$. Consequently, by (33), we have

and $\sigma^{2}\geqslant\max\{\Pi^{1/2},\delta^{1/2}\}$. In addition, by assumption, we have $(1-\varepsilon)^{p}\geqslant(1-\varepsilon)^{2}\geqslant 16\max\{\Pi^{1/2},\delta^{1/2}\}$. Since $16(1-\tau)=6$ and $p^{2}/(1-\lambda)\leqslant 5$, it follows that

Now, combining (19) with Lemmas 13–14 and (34), we obtain

with $\kappa=2p^{2}(\sigma+p\delta+\Pi)+2p\sigma+4e^{2}\tau^{-1}p\sigma$. Finally, using $\sigma\geqslant\sigma^{4}\geqslant\max\{\delta,\Pi\}$, $p\leqslant 2$ and $\tau=5/8$, we see that $\kappa\leqslant 135\sigma$. ∎

Let $\tau=(1-\Pi)/5$, so that, by assumption, $\tau\in(0,1/5]$. The proof distinguishes two cases, which eventually establish (5) by noting that Lemma 10 gives $\varphi(-\varepsilon)\leqslant\varepsilon^{2}$.

First, we assume $0\leqslant\varepsilon<\tau^{2}/2$. Note that then, by assumption, we have $0<\varepsilon<1/50$ and $\delta=\delta^{*}$. Let $p=2/\tau$ and $\sigma=p-1$. Analogous to (27) we have $1-e^{-s}=1-(1-\varepsilon)^{p}\leqslant p\varepsilon$, so that $\Pi\leqslant 1$ implies

which in particular yields $\lambda\leqslant 1/2$, with room to spare. Next observe that, since $\sigma/p=1-1/p$ and $\max\{2/p,p\varepsilon,\lambda\}=\tau$, by the definition of $\tau$ we have

which in turn readily yields $(1-\tau)\sigma^{2}(1-\varepsilon)^{p}\geqslant p^{2}\Pi/(1-\lambda)+\delta/(1+\delta)$. Similarly, using $\sigma\geqslant p/2=\tau^{-1}$ and $\tau\leqslant 1/2$ we obtain

Since $\varepsilon^{4}\mu^{2}\geqslant(1+\delta)^{-1}$ by assumption, analogously to the proof of Theorem 6, using (19) together with Lemmas 13–14, we obtain

with $\kappa=2p^{2}(\sigma+p\delta+\Pi)+2p\sigma+8\tau^{2}p(1+\delta)$. Now, using $\max\{\Pi,\tau\}\leqslant 1$ and $\sigma\leqslant p=2/\tau=10/(1-\Pi)$, a short calculation shows that, say,

Finally, we assume $\tau^{2}/2\leqslant\varepsilon\leqslant 1$. Using the lower bound (3) resulting from Harris’ inequality , it follows that

The point is that, by assumption, we have $2/\varepsilon^{2}\leqslant 8/\tau^{4}=5000/(1-\Pi)^{4}$, so that Lemma 10 implies $1\leqslant 5000\varphi(-\varepsilon)/(1-\Pi)^{4}$. ∎

4 Proofs of Theorem 1 and Lemma 7

The remaining proofs of Theorem 1 and Lemma 7 are straightforward.

Note that, by assumption, $5\sqrt{1-\varepsilon}\leqslant 5e^{-1/2}\leqslant 4$. So, using Lemma 11, we infer

with $\zeta=10\max\{\sqrt{1-\varepsilon},\Pi/(1-\Pi)\}$. Now an application of (3), analogous to (35), completes the proof. ∎

satisfies $\eta\in[0,e^{-1}]$. If $1-\eta\leqslant\varepsilon\leqslant 1$, then $\varepsilon\geqslant 1-e^{-1}$ and $1-\varepsilon\leqslant\eta$, so that Lemma 7 implies (4). If $0\leqslant\varepsilon<1-\eta$, then $e(1-\varepsilon)\varepsilon^{2}\mu\geqslant e\eta\varepsilon^{2}\mu\geqslant(\varepsilon^{2}\mu)^{1/2}\geqslant 1$ and $\varepsilon\leqslant 1-4\max\{\Pi^{1/4},\delta^{1/4}\}$, so that Theorem 6 establishes (4). ∎

Bootstrapping lower bounds for the lower tail

As discussed, Theorem 1 and 2 only give reasonable lower bounds for the lower tail if $\delta=O(1)$, i.e., as long as the dependencies are ‘weak’. In this section we present a bootstrapping strategy, which often allows us to deal with the remaining case, where $\delta=\Omega(1)$ holds.

Assuming that Theorem 1 or 2 applies to $Y$, using (36) there are constants $c_{1},c_{2}>0$ such that

although $\geqslant e^{-c_{3}\varphi(-\varepsilon)\mu^{2}/\Lambda}$ suffices for our purposes. Note that for the special case $\varepsilon=1$ this inequality is immediate in the subgraphs example (where $X_{G}=0$ implies $X_{H}=0$). Finally, by combining (37)–(39) we obtain

which qualitatively matches the upper bound of (2), as desired.

To implement this proof strategy, we need to be able to verify that (39) holds (or a related inequality). Here the main technical challenge is that, after conditioning on $\mathcal{E}$, the $i\in\Gamma$ are no longer added independently to $\Gamma_{{\mathbf{p}}}$. In Sections 3.1–3.3 we present three approaches that, in symmetric situations, allow us to routinely overcome this difficulty (each of them hinges on an event that is similar to $\mathcal{E}$). Since we are interested in large deviations (with exponentially small probabilities), here $(\varepsilon\mu)^{2}=\Omega(\Lambda)$ is a natural condition in view of (2), (40) and the fact $\varphi(-\varepsilon)=\Theta(\varepsilon^{2})$.

The first approach is motivated by the following simple observation: if $|\Gamma_{{\mathbf{p}}}|=0$, then deterministically $X=0$. Indeed, this yields

In the proof of Theorem 15 we use the following one-sided version of Chebyshev’s inequality (see, e.g., Theorem A.17 in ).

Finally, using (44) and the one-sided Chebyshev’s inequality (Claim 16) we infer that for every $0\leqslant j\leqslant m$ we have

which together with $(\varepsilon\mu)^{2}\geqslant\Lambda$ and (42) establishes (41). ∎

In applications where constant factors in the exponent are important, the following variant of Theorem 15 usually gives better results when $\varepsilon\to 0$ and $L=(\varepsilon\mu)^{2}/\Lambda\to\infty$ (by setting $\tau=6\max\{\varepsilon,L^{-1/2}\}$; see Lemma 12 with $A=(1+\tau)/k$).

If $k=1$, then $(1-\varepsilon)-(1-\lambda)^{k}=\lambda-\varepsilon=\tau\varepsilon$, and we now establish a similar bound for $k>1$. Note that $\lambda k=(1+\tau)\varepsilon\leqslant 2\varepsilon\leqslant\tau/3<1$ and

Recalling $\lambda k=(1+\tau)\varepsilon$, $\varepsilon\leqslant\tau/6$ and $\tau\leqslant 1$, a short calculation shows that

Consequently, using (46) and the one-sided Chebyshev’s inequality (Claim 16), we infer that for every $0\leqslant j\leqslant m$ we have

which together with $(\varepsilon\mu)^{2}\geqslant 4\tau^{-2}\Lambda$ and (42) establishes (45). ∎

2 Symmetric decomposition

Let ${\mathcal{H}}={\mathcal{H}}_{n}$ contain all subgraphs isomorphic to $H$ in $K_{n}$, and define $Q(\alpha)=E(\alpha)$ for all $\alpha\in{\mathcal{H}}$ (here $Q(\alpha)\neq\alpha$ is crucial to allow for isolated vertices in $H$). The key observation is that, by symmetry, there is a constant $w>0$ such that we may write

Intuitively, our approach exploits that correlation inequalities can be used to obtain a similar factorization of the conditional expected value of $X_{H}$.

With the subgraphs example in mind, the following theorem should be interpreted under the premise that the lower bound is exponentially small in $\Theta((\varepsilon\mu)^{2}/\Lambda)$. In other words, the multiplicative $\gamma\varepsilon$ error-term ought to be negligible as long as, say, $\gamma\varepsilon\geqslant e^{-(\varepsilon\mu)^{2}/\Lambda}$ holds. The crux is that this inequality is equivalent to (\varepsilon\mu)^{2}/\Lambda\geqslant\log\bigl{(}1/(\gamma\varepsilon)\bigr{)}, which matches our usual condition up to the logarithmic factor. On first reading it might be useful to consider the important special case exemplified above, where $w_{\alpha,\beta}=w>0$, $\mathcal{X}(\beta)=\{\alpha\in\mathcal{X}:Q(\beta)\subseteq Q(\alpha)\}$ and $\kappa=0$.

If $\varepsilon\nearrow 1$ or $\varepsilon=1$ holds, then, by applying Lemma 7 to $Y$, we often can improve (48) via

The proof of Theorem 18 hinges on the following simple consequence of Harris’ inequality , which was observed by Bollobás and Riordan (see Lemma 6 in ).

Let $\lambda=1+\gamma/2$. If $\mu>0$, then, using Markov’s inequality, we infer from (53)

It would be desirable to use Chebyshev’s inequality in (54), since this presumably would improve the seemingly suboptimal $\gamma\varepsilon$ term. Here one technical obstacle is that Claim 19 can, in general, not be strengthened to

Indeed, a short calculation shows that, for $\Gamma=[n]=\{1,\ldots,n\}$ and ${\mathbf{p}}=(p,\ldots,p)$ with $n\geqslant 3$ and $p\in(0,1)$, the events ${\mathcal{I}}_{i}=\{i\in\Gamma_{{\mathbf{p}}}\}$ and $\mathcal{D}=\{|\Gamma_{{\mathbf{p}}}|\leqslant 1\text{ or }\Gamma_{{\mathbf{p}}}=\{1,2\}\}$ provide a counterexample (where, moreover, equality holds in (50)). It would be interesting to know whether there is perhaps some approximate version of (55) that suffices for our purposes.

The existence of a symmetric decomposition may not always be obvious. We hope that the following two examples from additive combinatorics serve as inspiration for future applications of Theorem 18 (or its method of proof). In both we consider ${\mathbf{p}}=(p,\ldots,p)$ and $Q(\alpha)=\alpha$, and the basic idea is to ‘symmetrize’ $X$ using non-uniform ‘weights’ $w_{\alpha,\beta}$ (and $\kappa\neq 0$). In the first example, we let $\mathcal{X}$ contain all arithmetic progressions of length $k\geqslant 2$ in $\Gamma=[n]$, i.e., each $\alpha\in\mathcal{X}$ equals $\{b,b+d,\ldots,b+(k-1)d\}\subseteq[n]$ for some $b=b_{\alpha}$ and $d=d_{\alpha}$ with $b_{\alpha},d_{\alpha}\geqslant 1$. For every $\beta\in\mathcal{Y}=[n]$ we define $\mathcal{X}(\beta)$ as the set of $\alpha\in\mathcal{X}$ where $\beta=b_{\alpha}$ or $\beta=b_{\alpha}+(k-1)d_{\alpha}$, and set $w_{\alpha,\beta}=1/2$. Since each $\alpha\in\mathcal{X}$ contributes to exactly two $X_{\beta}$, we have $X=\sum_{\beta\in\mathcal{Y}}I_{\beta}X_{\beta}$. Furthermore, careful counting yields

so $\kappa=O(1/n)$ suffices. In the second example, we let $\mathcal{X}$ contain all Schur triples in $\Gamma=[n]$, i.e., each $\alpha\in\mathcal{X}$ equals $\{x,y,x+y\}\subseteq[n]$ for some $x=x_{\alpha}$ and $y=y_{\alpha}$ with $1\leqslant x_{\alpha}<y_{\alpha}$. For every $\beta\in\mathcal{Y}=[n]$ we define $\mathcal{X}(\beta)$ as the set of all $\alpha\in\mathcal{X}$ with $\beta\in\alpha$. We set $w_{\alpha,\beta}=1/2$ if $\beta=x_{\alpha}+y_{\alpha}$, and $w_{\alpha,\beta}=1/4$ otherwise. By counting triples, it is not hard to see that $X=\sum_{\beta\in\mathcal{Y}}I_{\beta}X_{\beta}$ and

so $\kappa=O(1/n)$ suffices. Finally, in both examples routine calculations (analogous to Example 3.2 in ) give $\mu^{2}/\Lambda=\Theta(\min\{\mu,np\})$. Since $\kappa=O(1/n)$ and $\mu^{2}/\Lambda=O(np)$, the natural condition $(\varepsilon\mu)^{2}=\Omega(\Lambda)$ thus implies $\kappa/\varepsilon=O(1/n\cdot\sqrt{\mu^{2}/\Lambda})=O(\sqrt{p/n})=o(1)$. In other words, the assumption $\gamma\varepsilon\geqslant 2\kappa$ in Theorem 18 is very mild, i.e., allows for $\gamma=o(1)$.

3 Vertex symmetry

The remainder of the proof is devoted to the following two inequalities, which together with (57), (58) and $(\varepsilon\mu)^{2}\geqslant\Lambda$ imply (56):

We note first that in the trivial case $\mu=0$, almost surely $X=0$ and thus $Z=0$ which implies $R_{\mathcal{U}}=Z_{\mathcal{U}}=0$; hence also $z=0$ and $r=0$ so that (59)–(60) follow trivially. We may thus assume $\mu>0$.

Turning to the conditional variance of $Z_{\mathcal{U}}$, note that, by symmetry (analogous as for $Z$), we have

Now, recalling the definitions of ${\mathcal{H}}(\beta_{1},\beta_{2})$, $X_{\beta_{1},\beta_{2}}$, $\mathcal{F}$ and $\Psi_{F}$, we infer

where the last inequality follows by comparison with (66). If $\mu>0$, then, using (65), the one-sided Chebyshev’s inequality (Claim 16) and (67), whenever $\mathcal{E}\cap\mathcal{D}$ holds we have

Inserting (68) into (64), we infer (for $\mu>0$)

which together with (63) implies (60) by definition of $\mathcal{E}$. ∎

A variant of the proof applies to rooted copies of $H$, see, e.g., Section 3 in for a precise definition. The basic idea is to map the vertex set of the root $R$ to $[r]$, and the remaining vertices of $G$ and $H$ to $\mathcal{U}\subseteq[n]\setminus[r]$ and $[n]\setminus(\mathcal{U}\cup[r])$, respectively; we leave the details to the interested reader.

Applications

In this section we illustrate the bootstrapping approaches of Section 3 via pivotal examples from additive and probabilistic combinatorics. In Section 4.1 we consider the lower tail of the number of arithmetic progressions (and Schur triples) in random subsets of the integers. In Section 4.2 we then turn to our main example: the lower tail of subgraph counts in random hypergraphs.

If $\Psi_{k}=n^{2}p^{k}$, then Theorem 2 (with $X=X_{k}$) yields

For Schur triples, which are defined in Section 3.2, the same calculations carry over (with $k=3$; the point is that (70) holds), yielding an analogous lower tail estimate. Related results for the upper tail of arithmetic progressions and Schur triples have been established by Warnke .

2 Random hypergraphs

Finally, we consider the lower tail of the number $X_{H}=X_{H}(n,p)$ of copies of a given $k$-graph $H$ in $G^{(k)}_{n,p}$, and prove Theorems 3–5. Here the following precise analysis of $\Lambda(X_{H})$ is at the heart of our approach. In fact, Lemma 22 is essentially given in (for $k=2$), but the restriction to subgraphs from ${\mathcal{I}}_{H}$ is new and crucial for our purposes: the key point is that every copy of $G\in{\mathcal{I}}_{H}$ in $H$ is induced. Recall that $m_{k}(H)$ is defined by (8).

Let $H$ be a $k$-graph with $e_{H}\geqslant 1$. Define ${\mathcal{I}}_{H}$ as the collection of all non-isomorphic subgraphs $J\subseteq H$ which satisfy $e_{J}\geqslant\max\{e_{K},1\}$ for all $K\subseteq H$ with $v_{K}=v_{J}$. For all $p=p(n)\in(0,1]$ we have

The remaining $\varepsilon=1-o(1)$ estimate of (10) follows from Lemma 23 below and Lemma 11 since $1-p=e^{-(1+o(1))p}$ and $\varphi(-\varepsilon)=1+o(1)$ for $p=o(1)$ and $\varepsilon=1-o(1)$, respectively. ∎

The proof above used the following lemma, which follows from results of Saxton and Thomason .

Let $H$ be a $k$-graph with $e_{H}\geqslant 1$. If $p=p(n)\in$ and $\varepsilon=\varepsilon(n)\in(0,1]$ satisfy $p=\omega(n^{-1/m_{k}(H)})$ and $\varepsilon=1-o(1)$, then we have

This establishes the lower bound of (74) since $e({\mathcal{T}}_{n,H})=(\pi_{H}+o(1))\binom{n}{k}$ and $1-\pi_{H}\in(0,1]$.

Turning to the corresponding upper bound, we first consider the case $e_{H}\geqslant 2$. Let $0<\delta\leqslant(1-\pi_{H})/3$. Theorem 9.2 in implies that there is $c=c(H,\delta)>0$ such that for $n\geqslant c$ the following holds for all $q\in[n^{-1/m_{k}(H)},1/c]$: there exists $s\leqslant c$ and a mapping $T\mapsto C(T)$ of sequences $T=(T_{1},\dots,T_{s})$ with $T_{i}\subseteq E(K_{n}^{(k)})$ to sets $C(T)\subseteq E(K_{n}^{(k)})$ such that for every $k$-graph $G$ on $n$ vertices with less than $n^{v_{H}}q^{e_{H}}$ copies of $H$ there exists $T=(T_{1},\ldots,T_{s})$ such that $E(G)\subseteq C(T)$, $|C(T)|\leqslant(\pi_{H}+\delta)\binom{n}{k}=F$ and further $\sum_{1\leqslant i\leqslant s}|T_{i}|\leqslant cqn^{k}=U$ and $\bigcup_{1\leqslant i\leqslant s}T_{i}\subseteq E(G)$. (Recall that $E(K_{n}^{(k)})$ is the set of all edges in the complete $k$-graph $K_{n}^{(k)}$. The mapping $T\mapsto C(T)$ is quite complicated; the point of it is that we can bound the number of ’containers’ $C(T)$ by the number of sequences $T$.)

Hence, recalling the definitions of $F$ and $U$, for any $\theta\in(0,1]$ we obtain

Choose $\theta=q/p=o(1)$. Then $q\log(1/\theta)=p\theta\log(1/\theta)=o(p)$, $e^{p}\leqslant(1-p)^{-1}$ and (76) yield, for $n\geqslant n_{0}(c,s,\delta)$,

It follows as usual that there is some $\delta(n)\to 0$ such that (77) holds with $\delta=\delta(n)$ for $n\geqslant n_{0}$, which together with $1-\pi_{H}\in(0,1]$ establishes the upper bound of (74) when $e_{H}\geqslant 2$.

We would like to thank Andrew Thomason for giving us a draft of together with helpful comments on it.

References

Appendix A Appendix

In this appendix we prove Lemmas 10–12 and 22.

By our conventions, (16) is trivial for $\varepsilon=1$, and so we henceforth assume $\varepsilon\in[0,1)$. First, let $f(x)=2\varphi(-x)-(1-x)\log^{2}(1-x)$. Since $f^{\prime}(x)=\log^{2}(1-x)\geqslant 0$ for $x\in[0,1)$, we infer $f(\varepsilon)\geqslant f(0)=0$. Second, let $g(x)=2\varphi(-x)-x^{2}$. Since $1-x\leqslant e^{-x}$ implies $g^{\prime}(x)=-2\log(1-x)-2x\geqslant 0$ for $x\in[0,1)$, we infer $g(\varepsilon)\geqslant g(0)=0$. Next, let $h(x)=\log^{2}(1-x)-2\varphi(-x)$. Since $h^{\prime}(x)=-2x(1-x)^{-1}\log(1-x)\geqslant 0$ for $x\in[0,1)$, we infer $h(\varepsilon)\geqslant h(0)=0$. Finally, $1-\varepsilon\leqslant e^{-\varepsilon}$ implies $\varphi(-\varepsilon)=(1-\varepsilon)\log(1-\varepsilon)+\varepsilon\leqslant\varepsilon^{2}$. ∎

As (17) is trivial otherwise, we henceforth assume $\varepsilon<1$. Since $\varphi^{\prime}(x)=\log(1+x)\leqslant 0$ for $x\in$, we infer $\varphi(-\varepsilon)\leqslant\varphi(-1)=1$, which establishes the first inequality of (17).

Next, define $y=1-\varepsilon$, and note that $y\in(0,e^{-1}]$. Let $g(x)=\phi(x-1)=1-x\log(e/x)$. Since $g^{\prime}(x)=\log x\leqslant 0$ for $x\in(0,1]$, we infer $g(y)\geqslant g(e^{-1})=(e-2)/e>0$. Let $h(x)=\sqrt{x}\log(e/x)$, and note that $h(y)>0$. Since $h^{\prime}(x)=-\log(ex)/(2\sqrt{x})\geqslant 0$ for $x\in(0,e^{-1}]$, we infer $h(y)\leqslant h(e^{-1})=2/\sqrt{e}$. It follows that

which establishes the second inequality of (17). ∎

We first consider the case $y=A\varepsilon\leqslant 1$, so that $y\in$. Since $\log(1-x)=-\sum_{j\geqslant 1}x^{j}/j\leqslant-x-x^{2}/2$ for $x\in[0,1)$, we see that $\varphi(-y)=(1-y)\log(1-y)+y\leqslant(1+y)y^{2}/2$, where the inequality is trivial for $y=1$ due to $\varphi(-1)=1$. By Lemma 10 we have $\varepsilon^{2}/2\leqslant\varphi(-\varepsilon)$, so that

Turning to the second inequality of (18) we henceforth assume $\gamma>0$ and $\varepsilon\in[0,1)$, as the claim is trivial otherwise. Let $\rho(x)=\varphi(-x)$, and note that $\rho^{\prime}(x)=-\log(1-x)$ and $\rho^{\prime\prime}(x)=1/(1-x)$. Since $\log(1-x)\geqslant-x/(1-x)$ for $x\in[0,1)$, c.f. (14), we see that $\rho^{\prime}(\varepsilon)\leqslant\varepsilon/(1-\varepsilon)$. Note that $\gamma>0$ and $3\sqrt{\gamma}\leqslant 1-\varepsilon$ imply $0<3\gamma^{3/2}\leqslant\gamma-\gamma\varepsilon\leqslant 1-(1+\gamma)\varepsilon$. So, recalling $\varepsilon^{2}/2\leqslant\varphi(-\varepsilon)$ and $A=1+\gamma$, using Taylor’s theorem with remainder it follows that $0\leqslant A\varepsilon<1$ and

Define ${\mathcal{S}}_{H}$ as the collection of all non-isomorphic subgraphs $J\subseteq H$ with $e_{J}\geqslant 1$. Let $N(n,H)$ denote the number of copies of $H$ in $K^{(k)}_{n}$. Note that $N(n,H)=\Theta(n^{v_{H}})$. By double counting pairs $(J^{\prime},H^{\prime})$ of copies of $J$ and $H$ with $J^{\prime}\subseteq H^{\prime}\subseteq K^{(k)}_{n}$, using symmetry we infer that, in $K^{(k)}_{n}$, there are exactly

Suppose that $\omega=\omega(n)\to\infty$ satisfies $1\leqslant\omega\leqslant n^{1/(2m_{k}(H)+1)}$. Using $m_{k}(H)\geqslant(e_{K}-1)/(v_{K}-k)$ when $e_{K}\geqslant 2$, note that for $p\geqslant\omega n^{-1/m_{k}(H)}$ we have

where we used (78) and that every copy of $J\in{\mathcal{I}}_{H}$ in $H$ is induced (which implies $v_{G}\geqslant v_{J}+1$). With these modifications, the lower bound of (71) follows. ∎