Very large gaps between consecutive primes (Q1355089)

Let \(G(x)=\max p_{n+1}-p_n\) for primes \(p_n\leq x\). Then it is shown that \[ G(x)\geq (2e^\gamma+o(1)) \frac{(\log x)(\log\log x)(\log\log\log\log x)}{(\log \log\log x)^2}. \] This improves results of \textit{R. A. Rankin} [Proc. Edinb. Math. Soc., II. Ser. 13, 331-332 (1963; Zbl 0121.04705)] (with constant \(e^\gamma\)) and \textit{H. Maier} and \textit{C. Pomerance} [Trans. Am. Math. Soc. 322, 201-237 (1990; Zbl 0706.11052)] (with constant \((1.312\dots)e^\gamma)\). In both these papers one arrives at a set \(R\) of integers that must be covered by congruences \(a_p\pmod p\) for suitable primes \(p\). The numbers \(a_p\) are free to be chosen. Rankin essentially uses each prime \(p\) to cover one element of \(R\). Maier and Pomerance show that one can often delete two elements of \(R\) with the same prime \(p\). The present paper shows that one can almost always delete two elements of \(R\) for each prime. The result and its proof are phrased in terms of colourings of graphs. The existence of a suitable colouring is established by a probabilistic argument.