\documentclass[11pt,a4paper]{amsart} \usepackage[utf8]{inputenc} \usepackage{amsmath,amssymb,amsthm} \usepackage[margin=2.5cm]{geometry} \usepackage{booktabs} \usepackage[hidelinks]{hyperref} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Prob}{\mathbf{P}} \newcommand{\Ber}{\mathrm{Ber}} \newcommand{\LG}{\mathrm{LG}} \title[Site percolation on the square lattice]{Computer-assisted bounds $0.556921\le p_c\le 0.6463$ for site percolation on the square lattice} \author{David Niedbala Giraudin} \address{ORCID 0009-0009-1526-1178} \date{3 November 2026} \begin{document} \begin{abstract} Let $p_c$ be the critical probability of Bernoulli site percolation on $\Z^2$. We prove $0.556921\le p_c\le 0.6463$. The previous best rigorous bounds known to us are $p_c\ge 0.5567$ (Ashton, 2026, extending van den Berg and Ermakov, 1996) and $p_c\le 0.666894$ (Wierman and Oberly, 2024). The lower bound uses the growth-process comparison of van den Berg and Ermakov with the exact posterior on the exploration tree. We reduce this posterior to a scalar interval recursion and explore the tree generation by generation, with a prescribed order among siblings. This passes the value $0.556788\ldots$ that the same scalar computation gives when the order is not used, and the value $0.556788090$ reported by Ashton as the limit of his relaxation. The upper bound uses the substitution method of Wierman, in two stages with $4\times 4$ regions, from the line graph of $\Z^2$ (site threshold $1/2$) to $\Z^2$. Both bounds are certified by short pure-Python programs in exact rational and integer arithmetic. \end{abstract} \maketitle \section{Introduction} Each vertex of a graph $G$ is open with probability $p$, independently. Let $\theta_G(p)$ be the probability that a fixed vertex lies in an infinite open cluster, and $p_c(G)=\sup\{p:\theta_G(p)=0\}$. For $G$ connected and periodic, $p_c(G)$ does not depend on the fixed vertex. For $p>p_c(G)$ an infinite open cluster exists almost surely, and for $p0$ implies that $L$ has an infinite open cluster with positive probability at parameter $p$, then $p_c(S)\ge 1-p$. \end{lemma} \begin{proof} If $\theta_S(1-p)=0$ then $p_c(S)\ge 1-p$ by definition. Otherwise $L$ percolates at $p$, so $p\ge p_c(L)\ge p_c(S^*)$ by Lemma~\ref{lem:embed}, and (F1) gives $p_c(S)\ge 1-p_c(S^*)\ge 1-p$. \end{proof} \subsection{The growth process} Let $\varepsilon(v)=(u(v),l(v))\in\{0,1\}^2$ record whether the upper and lower vertices of the column $v$ are open. The $\varepsilon(v)$ are independent with law $\pi$, $\pi(ab)=p^{a+b}q^{2-a-b}$. We write states as $00,01,10,11$, the first digit being $u$. For an edge $e=\{v,w\}$ of $S$ put \[ \eta(e)=u(\min)u(\max)\ \vee\ l(\min)l(\max)\ \vee\ u(\min)l(\max), \] so that $\eta(e)=1$ if and only if some open vertex of the column $\min$ is adjacent in $L$ to some open vertex of the column $\max$. The process assigns values $\xi(v)\in\{0,1\}$ to vertices of $\Z^2$ step by step. At step $0$, $\xi(O)=1$ if and only if $\varepsilon(O)\ne 00$. A vertex $v$ with $\xi(v)=1$ is a \emph{candidate} if some neighbour of $v$ has no value yet. At each later step a candidate $b$ is selected by a rule depending only on the values revealed so far. Its neighbours without a value become its \emph{children}, and each child $w$ receives $\xi(w)=\eta(\{b,w\})$. The process stops when there is no candidate. The edges from vertices to their children form a tree $T$ rooted at $O$; the \emph{depth} of a vertex is its distance to $O$ in $T$. A selected vertex has no unvalued neighbour afterwards, so it is selected only once. \emph{Slots.} A child $w$ of $b$ is a \emph{P-child} if $w$ is the max endpoint of $\{b,w\}$, and an \emph{M-child} otherwise. The four neighbours of $v$ are $v\pm e_1$, $v\pm e_2$: two would be P-children of $v$ and two M-children. So a non-root vertex that is a P-child of its parent has slots $(P,P,M)$, an M-child has slots $(P,M,M)$, and $O$ has slots $(P,P,M,M)$. For a non-root vertex we call the slot type opposite to its own type the \emph{minority} type. \emph{The rule.} We use the following selection rule: select a candidate of minimal depth; among these, one whose parent was selected earliest; among children of the same parent, a minority child before the majority children; between two majority children, the one first in the fixed order $e_1,e_2,-e_1,-e_2$ of the directions from the parent. A vertex stops being a candidate only when it is selected or when all its neighbours have values, and it never becomes a candidate again. The depths of the selected vertices form a nondecreasing sequence: a selection creates candidates of depth one more than the selected vertex, and all other candidates have depth at least that of the selected vertex. \begin{lemma}\label{lem:coupling} Say that a law $\mu$ on $\{0,1\}^k$ dominates $\beta$ if $\mu(A)\ge\beta(A)$ for every up-set $A$. Assume that (i) $1-q^2\ge 1-p$; (ii) given $\xi(O)=1$, the law of the values of the four children of $O$ dominates $\beta$; (iii) at every later step and for every possible history, the conditional law of the values given to the children dominates $\beta$. Then $\theta_S(1-p)>0$ implies that $L$ percolates with positive probability at $p$, and hence $p_c(S)\ge 1-p$. \end{lemma} \begin{proof} Let $(U_t)_{t\ge0}$ be independent uniform variables and $(Y(v))_{v\in\Z^2}$ independent $\Ber(1-p)$ variables, all independent of $\varepsilon$. Let $\mathcal G_{t}$ be the $\sigma$-field generated by the values revealed up to step $t$ and by $U_0,\dots,U_t$. At step $t$ the set of new children $C_t$ is $\mathcal G_{t-1}$-measurable, and, since the $U$'s are independent of $\varepsilon$, the conditional law $\nu_t$ of $\xi|_{C_t}$ given $\mathcal G_{t-1}$ is the one in (ii) or (iii). By Lemma~\ref{lem:strassen} below there is a kernel $K_t$ with $\sum_x\nu_t(x)K_t(x,\cdot)=\beta$ and $K_t(x,z)>0\Rightarrow z\le x$. Using $U_t$ we draw $\zeta|_{C_t}$ from $K_t(\xi|_{C_t},\cdot)$; at step $0$ we draw $\zeta(O)\le\xi(O)$ with $\zeta(O)\sim\Ber(1-p)$, which is possible by (i). Vertices that never receive a value get $\zeta(v)=Y(v)$. Then $\zeta\le\xi$ on every valued vertex, and given $\mathcal G_{t-1}$ the vector $\zeta|_{C_t}$ has law $\beta$. \emph{$\zeta$ is i.i.d.\ $\Ber(1-p)$.} Let $\zeta^{(m)}$ equal $\zeta$ on vertices valued at steps $\le m$, and $Y$ elsewhere. Passing from $\zeta^{(m-1)}$ to $\zeta^{(m)}$ replaces $Y|_{C_m}$ by $\zeta|_{C_m}$. Given $\mathcal G_{m-1}$, both vectors have law $\beta$, and both are independent of $Y$ off $C_m$. Since $C_m$ is $\mathcal G_{m-1}$-measurable, $\zeta^{(m)}$ and $\zeta^{(m-1)}$ have the same law. By induction every $\zeta^{(m)}$ has the law of $Y$. As $m\to\infty$, $\zeta^{(m)}\to\zeta$ pointwise, so $\zeta$ has the law of $Y$. \emph{Comparison.} If the process stops, the set $V_1$ of valued vertices with $\xi=1$ is finite and all neighbours of $V_1$ are valued. A $\zeta$-open path from $O$ starts in $V_1$, because $\zeta(O)\le\xi(O)$. Each further vertex is a neighbour of $V_1$, hence valued, and has $\xi\ge\zeta=1$, so it is again in $V_1$. Hence the $\zeta$-cluster of $O$ is finite. If the process never stops, infinitely many distinct vertices are selected, all with $\xi=1$. By induction along $T$, every open vertex of a column $v$ with $\xi(v)=1$ is joined in $L$ by an open path to an open vertex of the column $O$. The open vertices of one column are adjacent, and $\eta=1$ on each tree edge with value $1$. So $L$ has an infinite open cluster. Since $\zeta$ is site percolation on $S$ with density $1-p$, $\theta_S(1-p)>0$ forces the process to survive with positive probability. Lemma~\ref{lem:zero} concludes. \end{proof} \begin{lemma}[finite Strassen theorem]\label{lem:strassen} Let $(P,\le)$ be a finite poset and $\mu,\nu$ probability measures on $P$ with $\mu(A)\ge\nu(A)$ for every up-set $A$. Then there is a probability measure $\Gamma$ on $P\times P$ with marginals $\nu$ and $\mu$, supported on $\{(x,y):x\le y\}$. \end{lemma} \begin{proof} Consider the network with arcs $s\to x$ of capacity $\nu(x)$, $x\to y'$ of infinite capacity for $x\le y$, and $y'\to t$ of capacity $\mu(y)$, where $y'$ is a copy of $y$. A cut of finite capacity is determined by the set $A$ of $x$ kept on the side of $s$. It must then cut all $y'\to t$ with $y\in{\uparrow}A$, so its capacity is at least $\nu(P\setminus A)+\mu({\uparrow}A)\ge \nu(P\setminus A)+\nu({\uparrow}A)\ge 1$. By the max-flow min-cut theorem there is a flow of value $1$, and its values on the arcs $x\to y'$ define $\Gamma$. \end{proof} \subsection{The posterior} Fix a step at which $b\ne O$ is selected, and let $c$ be its parent. The history fixes $T$ and the values $x_e=\eta(e)$ on its edges. An unvalued vertex is an endpoint of no tree edge. Hence, given the history, the variables $\varepsilon$ of unvalued vertices are still i.i.d.\ with law $\pi$ and independent of the rest. The law of $(\varepsilon(v))_{v\text{ valued}}$ is proportional to \begin{equation}\label{eq:post} \mathbf 1[\varepsilon(O)\ne 00]\prod_{v}\pi(\varepsilon(v))\prod_{e\in T}\mathbf 1[\eta(e)=x_e], \end{equation} because the history occurs exactly when the revealed values are the observed ones (the selection rule is a function of them). When $b$ is selected its only tree neighbour is $c$. Since $T$ is a tree, \eqref{eq:post} is computed by messages. For a tree edge $\{x,y\}$ let $m_{y\to x}(\gamma)$, for $\gamma\in\{0,1\}^2$, be the total weight of the branch of $T$ at $y$ (the component of $T\setminus\{x,y\}$ containing $y$), together with the factor of the edge $\{x,y\}$, when $\varepsilon(x)=\gamma$. For a vertex $x$ and a tree neighbour $y$ let $\mu_x^{(y)}$ be the \emph{cavity law} of $\varepsilon(x)$: proportional to $\pi$ times the messages into $x$ from all tree neighbours except $y$, times $\mathbf 1[\gamma\ne00]$ if $x=O$. Then the posterior of $\varepsilon(b)$ is proportional to $w(\delta)=\pi(\delta)\sum_\gamma \mu_c^{(b)}(\gamma)\,\mathbf 1[\eta=1 \text{ on }\{c,b\}]$ (with $\varepsilon(c)=\gamma$, $\varepsilon(b)=\delta$), and the children of $b$ have independent values given $\varepsilon(b)$. The cavity laws give no mass to $00$: for $x\ne O$ the message from the parent of $x$ vanishes at $00$, since $\eta=1$ needs an open vertex in each column. A direct case check from the definition of $\eta$ gives the following lemma, where $\lambda$ and $\upsilon$ denote the probabilities that $l(\cdot)=1$ and $u(\cdot)=1$ under the indicated laws. Explicitly, $\eta=0$ if one of the two columns is $00$; otherwise $\eta=l(\max)$ if $\varepsilon(\min)=01$, and $\eta=1$ if $\varepsilon(\min)\in\{10,11\}$. \begin{lemma}\label{lem:msg} Let $y$ be a child of $x$ in $T$, and normalise messages by their value at $11$. \begin{enumerate} \item If $y$ is a P-child, then $m_{y\to x}(10)=m_{y\to x}(11)$, and the quotient $m_{y\to x}(01)/m_{y\to x}(11)$ equals $1/q$ if $\eta(\{x,y\})=0$, and $\lambda_y$ if $\eta(\{x,y\})=1$, where $\lambda_y$ is computed from the law of $\varepsilon(y)$ proportional to $\pi(\cdot)\mathbf 1[\cdot\ne00]\prod_z m_{z\to y}$ over the children $z$ of $y$. \item If $y$ is an M-child, the same holds with $01$ and $10$ exchanged and $\lambda_y$ replaced by $\upsilon_y$. \item The message from $x$ to $y$ satisfies the following. If $y$ is a P-child, then $m_{x\to y}(01)=m_{x\to y}(11)$ and $m_{x\to y}(10)/m_{x\to y}(11)=\upsilon$ computed under $\mu_x^{(y)}$; if $y$ is an M-child, $m_{x\to y}(10)=m_{x\to y}(11)$ and $m_{x\to y}(01)/m_{x\to y}(11)=\lambda$ computed under $\mu_x^{(y)}$. \end{enumerate} \end{lemma} \begin{proof} If $y$ is a P-child, then with $\varepsilon(x)=\gamma$ and $\varepsilon(y)=\delta$ we have $\eta=\mathbf 1[\delta\ne00]$ for $\gamma\in\{10,11\}$ and $\eta=l(\delta)$ for $\gamma=01$. Summing $\pi(\delta)$ against these gives (1): for $\eta=0$ the values are $q^2,q^2$ at $10,11$ and $q$ at $01$, and for $\eta=1$ the ratio is $\sum_{l(\delta)=1}/\sum_{\delta\ne00}$ of the weights of $\varepsilon(y)$. As a function of $\delta$ with $\gamma$ summed out, $\eta=u(\gamma)$ for $\delta=10$ and $\eta=\mathbf 1[\gamma\ne00]$ for $\delta\in\{01,11\}$, which gives (3). The M-case is the mirror image: if $y$ is an M-child, $\eta=\mathbf 1[\delta\ne 00]$ for $\gamma\in\{01,11\}$ and $\eta=u(\delta)$ for $\gamma=10$. \end{proof} \emph{Reduction to one scalar.} Put $\kappa=q/p=\pi(01)/\pi(11)=\pi(10)/\pi(11)$ and \[ f_l(X,Y)=\frac{X+1}{X+Y+1},\qquad f_u(X,Y)=\frac{Y+1}{X+Y+1}=f_l(Y,X). \] For a law with weights $w$ on $\{01,10,11\}$, $X=w(01)/w(11)$ and $Y=w(10)/w(11)$, the probability of $l=1$ is $f_l(X,Y)$ and that of $u=1$ is $f_u(X,Y)$. The function $f_l$ is nondecreasing in $X$ and nonincreasing in $Y$. For a child $y$ of $x$ call the non-trivial ratio of Lemma~\ref{lem:msg}(1)--(2) the \emph{ratio} $r_y$ of $y$. If $y$ has $\eta=1$, two slots of the same type as $y$ and one of the other type, then by Lemma~\ref{lem:msg} \begin{equation}\label{eq:rec} r_y=f_l(\kappa\, r_1r_2,\ \kappa\, r_3), \end{equation} where $r_1,r_2$ are the ratios of the children of $y$ in the two same-type slots and $r_3$ that of the other slot, an empty slot counting as ratio $1$. (For an M-child, $\upsilon_y=f_u(\kappa r_3,\kappa r_1r_2)=f_l(\kappa r_1r_2,\kappa r_3)$.) An unselected child with $\eta=1$ has ratio $f_l(\kappa,\kappa)=1/(1+q)$, and a child with $\eta=0$ has ratio $1/q$. Let $R_0=[1/(1+q),\,1/q]$, which contains $1$, and for $k\ge1$ let $R_k$ be the smallest interval containing $R_0$ and $f_l(\kappa R_{k-1}^2,\kappa R_{k-1})$. If $R_{k-1}=[a,b]$, its endpoints are $\min(\inf R_0,\ f_l(\kappa a^2,\kappa b))$ and $\max(\sup R_0,\ f_l(\kappa b^2,\kappa a))$. The $R_k$ increase with $k$. \begin{lemma}\label{lem:Rk} If every selected vertex in the branch at a child $y$ has depth less than $\mathrm{depth}(y)+k$, then $r_y\in R_k$. \end{lemma} \begin{proof} Induction on $k$. If $y$ is unselected (in particular if $k=0$), then $r_y=1/q$ when $\eta(\{x,y\})=0$ and $r_y=1/(1+q)$ otherwise, so $r_y\in R_0\subseteq R_k$. If $y$ is selected and $k\ge1$, its children $z$ have depth $\mathrm{depth}(y)+1$ and all selected vertices in their branches have depth less than $\mathrm{depth}(z)+(k-1)$, so their ratios lie in $R_{k-1}$ by induction; an empty slot has ratio $1\in R_0\subseteq R_{k-1}$. By \eqref{eq:rec} and the monotonicity of $f_l$, $r_y\in f_l(\kappa R_{k-1}^2,\kappa R_{k-1})\subseteq R_k$. The inclusions $R_0\subseteq R_1\subseteq\cdots$ follow by induction from $R_0\subseteq R_1$ and the monotonicity of $f_l$. \end{proof} \emph{The path scalar.} For a vertex $x$ and its child $y$ on the path from $O$ to $b$, let $\psi_x$ be the ratio $\upsilon$ (if $y$ is a P-child) or $\lambda$ (if $y$ is an M-child) of Lemma~\ref{lem:msg}(3), computed under $\mu_x^{(y)}$. Let $x_0=O,x_1,\dots,x_{n-1}=c,x_n=b$ be the path. If $x_{i}$ (with $i\ge1$) has the same type as $x_{i+1}$, its remaining slots are one slot of its own type and one of the other type, and \begin{equation}\label{eq:A} \psi_{x_i}=f_u(\kappa r,\ \kappa r'\psi_{x_{i-1}}), \end{equation} where $r$ is the ratio of the same-type sibling of $x_{i+1}$ and $r'$ that of the other one. If $x_{i+1}$ has the minority type of $x_i$, the two remaining slots are of the majority type, and \begin{equation}\label{eq:B} \psi_{x_i}=f_u(\kappa\psi_{x_{i-1}},\ \kappa r r'). \end{equation} At the root, $\psi_O=f_u(\kappa r,\kappa r'r'')$, where $r$ is the ratio of the other P-child of $O$ and $r',r''$ those of its two M-children. These formulas are written for $x_{i+1}$ a P-child; for an M-child, exchange $01$ and $10$ throughout, which leaves the formulas unchanged. Similarly, the posterior of $\varepsilon(b)$ is proportional to \begin{equation}\label{eq:rho} \rho_\psi(01)=q,\quad\rho_\psi(10)=q\psi,\quad\rho_\psi(11)=p\qquad(\psi=\psi_c) \end{equation} if $b$ is a P-child, with $01$ and $10$ exchanged if $b$ is an M-child. \emph{Use of the order.} When $b$ (of depth $n$) is selected, no vertex of depth $>n$ has been selected, since depths of selected vertices are nondecreasing. So a sibling of $x_{i+1}$ (depth $i+1$) has selected descendants only down to depth $n$, and its ratio lies in $R_{n-i}$ by Lemma~\ref{lem:Rk}. For $i=n-1$ this is $R_1$. In case \eqref{eq:B} at $i=n-1$, $b$ is the minority child of $c$. It has been a candidate since it received its value, because candidacy is never regained. So the rule selects it before its two siblings, which are of majority type, and their ratios lie in $R_0$. Let $\Psi$ be the interval obtained by the following interval computation. For each $n\le N+1$, start at the root with the siblings in $R_n$. Then apply, for $j=n-1,\dots,1$, the worse of \eqref{eq:A} and \eqref{eq:B} with siblings in $R_j$. For $j=1$, use $R_1$ in \eqref{eq:A} and $R_0$ in \eqref{eq:B}. For depths $n\ge N+2$, start instead at the vertex of depth $n-N-1$ with the trivial interval $[0,1]$ and apply the same $N$ steps $j=N,\dots,1$. Take the hull over all cases. All bounds are rounded outward. By monotonicity of $f_u$, $\psi_c\in\Psi$ at every step. \subsection{The finite check} For a P-type $b$ the children occupy slots $(P,P,M)$. Given $\varepsilon(b)=\delta$ they are independent, and the probability that a child gets value $1$ is \[ \begin{aligned} &\text{P-slot:}\quad s_P(01)=p,\quad s_P(10)=s_P(11)=1-q^2,\\ &\text{M-slot:}\quad s_M(10)=p,\quad s_M(01)=s_M(11)=1-q^2. \end{aligned} \] Neighbours of $b$ that already have a value are replaced by imaginary children with fresh $\varepsilon$. The law of the real children is a marginal of the three-slot law, and marginals preserve stochastic domination. Let $\nu_\psi$ be the mixture over $\delta\sim\rho_\psi$ of the product laws on $\{0,1\}^3$. Condition (iii) of Lemma~\ref{lem:coupling} holds if \[ M_A(\psi):=\nu_\psi(A)-\beta(A)\ge0 \] for every $\psi\in\Psi$ and every up-set $A$ of $\{0,1\}^3$. There are $18$ nontrivial ones. The unnormalised form $\sum_\delta\rho_\psi(\delta)(\nu_\delta(A)-\beta(A))$ is affine in $\psi$. So it suffices to check the two endpoints of $\Psi$. M-type vertices give the same conditions after exchanging $01\leftrightarrow10$ and $P\leftrightarrow M$. For the root, the posterior of $\varepsilon(O)$ given $\xi(O)=1$ is $\pi$ restricted to $\{01,10,11\}$, the slots are $(P,P,M,M)$, and the $166$ nontrivial up-sets of $\{0,1\}^4$ are checked. \begin{proposition}\label{prop:lowercheck} Let $p_0=443079/10^6$ and $N=60$. In exact rational arithmetic, with outward rounding to the grid $10^{-40}$, the computation above gives $\Psi\subseteq[0.3414794,0.922660]$. Moreover: $\min_A M_A(\psi)\ge 5.01\cdot10^{-8}$ at both endpoints of $\Psi$; the root margin is at least $0.01456$; and $1-q^2-(1-p_0)\ge 0.1329$. The tail computation for depths $n\ge N+2$ gives the same interval as the depths $n\le N+1$ to $15$ digits. \end{proposition} This is printed by the lower-bound program, which also certifies $p=11077/25000$ (bound $0.55692$) with margin $1.997\cdot10^{-6}$. Lemma~\ref{lem:coupling} then gives $p_c\ge 1-p_0=0.556921$. The certified interval for the ratios is $R_{61}\subseteq[0.335962,1.795587]$ at $p_0$. By bisection, the method with this order works up to $1-p=0.5569210257$. \begin{remark}[fixed order]\label{rem:fixed} If the order is not used, i.e.\ every $R_j$ is replaced by $R_{N+1}$, the threshold of the same computation is $1-p=0.5567880904\ldots$. This agrees with the limit $0.556788090$ reported in \cite{As26}. Ashton propagates cones of messages along a fixed total order, while we use a scalar recursion; the two numbers agree to ten digits. We do not claim that $0.556788\ldots$ is a limit for every analysis with a fixed order. In the program this version serves only as a self-test, at $p=0.4433$; it is not used in the proof. \end{remark} \section{The upper bound}\label{sec:upper} \subsection{Lattices} For a face $[i,i+1]\times[j,j+1]$ of $\Z^2$ we say ``add its diagonals'' for adding both edges $(i,j)(i+1,j+1)$ and $(i+1,j)(i,j+1)$. Let \begin{itemize} \item $\LG$: add the diagonals of all faces with $i\equiv j\pmod 2$; \item $H$: add the diagonals of all faces with $i$ and $j$ odd; \item $S$: the square lattice. \end{itemize} Then $S\subset H\subset\LG$. \begin{lemma}\label{lem:LG} $\LG$ is isomorphic to the line graph of $\Z^2$. Hence $p_c(\LG)=1/2$. \end{lemma} \begin{proof} Map the midpoint $(a,b)$ of an edge of $\Z^2$ to $(a+b-\tfrac12,\ b-a+\tfrac12)$. The midpoints $(x+\tfrac12,y)$ go to the points $(x+y,y-x)$ with even coordinate sum, and $(x,y+\tfrac12)$ to $(x+y,y-x+1)$ with odd coordinate sum. Two perpendicular edges sharing an endpoint become nearest neighbours. The four edges at a vertex $(x,y)$ become the corners of the face with lower left corner $(x+y-1,y-x)$. The two collinear pairs among them become its diagonals. These faces are those with $i\not\equiv j\pmod 2$, and a translation by $e_1$ gives $\LG$. Site percolation on a line graph is bond percolation on the original graph, so (F2) gives $p_c(\LG)=1/2$. \end{proof} \subsection{Regions and ghost partitions} Let $G$ be one of these lattices and $\mathcal R$ a tiling of $\Z^2$ by translates $z+B+4\Z^2$ of the box $B=\{0,1,2,3\}^2$. A \emph{crossing edge} is an edge of $G$ whose endpoints lie in different tiles. A \emph{ghost} of a tile $R$ is a pair $(v,e)$ with $v\in R$ and $e$ a crossing edge at $v$. Given the states in $R$, the \emph{ghost partition} $\Pi_R$ of the ghosts of $R$ puts $(v,e)$ and $(v',e')$ in the same block if $v$ and $v'$ are open and joined by an open path using edges of $G$ inside $R$. Ghosts at closed vertices are singletons. The partitions of different tiles are independent. We order partitions by refinement: $\pi\le\pi'$ if every block of $\pi$ is contained in a block of $\pi'$. Given partitions $\pi=(\pi_R)$, let $\mathcal A(\pi)$ be the graph whose vertices are the blocks of all tiles, with an edge between the block of $(v,e)$ and the block of $(w,e)$ for every crossing edge $e=\{v,w\}$. \begin{lemma}\label{lem:ghost} $G$ has an infinite open cluster if and only if $\mathcal A(\Pi)$ has an infinite connected component. \end{lemma} \begin{proof} If $K$ is an infinite open cluster, take an infinite self-avoiding open path in $K$. It leaves every finite tile, so it splits into finite segments inside tiles joined by crossing edges. Entry and exit ghosts of a segment are in one block, so the path gives an infinite walk in $\mathcal A(\Pi)$ through blocks of infinitely many tiles. Conversely, $\mathcal A(\Pi)$ is locally finite, so an infinite component contains an infinite simple path $B_0,B_1,\dots$, the edge $B_iB_{i+1}$ coming from a crossing edge $e_i=\{v_i,w_i\}$ with $(v_i,e_i)\in B_i$ and $(w_i,e_i)\in B_{i+1}$. For $i\ge1$ the ghosts $(w_{i-1},e_{i-1})$ and $(v_i,e_i)$ of $B_i$ are distinct, since the path is simple. So both vertices are open and joined inside their tile. Then every $e_i$ with $i\ge1$ joins two open vertices, and $w_1,v_2,w_2,v_3,\dots$ lie in one open cluster. Since the path is simple and each tile has finitely many blocks, it visits infinitely many tiles, so this cluster is infinite. \end{proof} \begin{lemma}\label{lem:subst} Let $G,G'$ be two of the lattices, with the same tiling and the same crossing edges. Suppose the law of $\Pi_R$ for $G'$ at $p'$ dominates that for $G$ at $p$ in the refinement order, for every tile $R$. If $G$ percolates at $p$, then $G'$ percolates at $p'$. \end{lemma} \begin{proof} For each tile take a coupling $(\Pi_R,\Pi'_R)$ with $\Pi_R\le\Pi'_R$, independently over tiles. The ghost sets and the edges of $\mathcal A$ are the same for $G$ and $G'$. Coarsening only merges blocks within tiles, so an infinite component of $\mathcal A(\Pi)$, which meets infinitely many tiles, is mapped into an infinite component of $\mathcal A(\Pi')$. Lemma~\ref{lem:ghost} applies to both lattices, since $\Pi$ and $\Pi'$ have the laws of the ghost-partition fields. \end{proof} The tile laws are the same for all tiles. The two stages are: \begin{itemize} \item \emph{Stage 1}: tiles $B+4\Z^2$, $G=\LG$ at $p=0.50001$, $G'=H$ at $p'=0.5755$. A face meeting two tiles has $i\equiv3$ or $j\equiv 3\pmod 4$. In $\LG$ it has diagonals only if $i\equiv j\pmod 2$, i.e.\ if $i,j$ are both odd, which is exactly the condition in $H$. So the crossing edges coincide. The extra diagonals of $\LG$ (faces with $i,j$ even) lie inside tiles. \item \emph{Stage 2}: tiles $(1,1)+B+4\Z^2$, $G=H$ at $p=0.5755$, $G'=S$ at $p'=0.6463$. A face meeting two tiles has $i\equiv0$ or $j\equiv0\pmod 4$, so it has no diagonal in $H$. The crossing edges are the nearest-neighbour ones in both lattices. \end{itemize} \subsection{Symmetry and the certificate} The dihedral group $D_4$ of the box acts on the ghosts of a tile, and in both stages it preserves the edges inside the tile and the crossing edges. So the partition laws are $D_4$-invariant (the program also checks this exactly). Let $\mathcal O$ and $\mathcal O'$ be the orbits of partitions for $G$ and $G'$, with masses $\nu(\mathcal O)$ and $\mu(\mathcal O')$. \begin{lemma}\label{lem:sym} Suppose that there is a transport plan $f(\mathcal O,\mathcal O')\ge0$ with marginals $\nu$ and $\mu$, such that $f(\mathcal O,\mathcal O')>0$ only if $x_0\le y_0$ for some $x_0\in\mathcal O$, $y_0\in\mathcal O'$. Then the law of $\Pi'_R$ dominates that of $\Pi_R$. \end{lemma} \begin{proof} For each such pair of orbits with $f>0$, spread $f(\mathcal O,\mathcal O')$ uniformly over the pairs $(gx_0,gy_0)$, $g\in D_4$. These pairs are comparable, since $g$ preserves refinement. The point $x\in\mathcal O$ receives $f\cdot|\mathrm{Stab}(x_0)|/|D_4|=f/|\mathcal O|$, and similarly for $\mathcal O'$. By invariance, the laws are uniform on each orbit, so the marginals are the two partition laws. \end{proof} The program computes the partition laws as integer polynomials in $p$, by enumerating the $2^{16}$ states of a tile with union-find. It evaluates them exactly at the rational parameters, reduces to orbits, and joins two orbits by an arc when some element of the second is coarser than a fixed element of the first. It then computes an integer maximum flow (Dinic's algorithm) with capacities equal to the scaled masses. \begin{proposition}\label{prop:uppercheck} In exact integer arithmetic: \begin{enumerate} \item Stage 1: $13823$ partitions for $H$ and $16977$ for $\LG$, in $1851$ and $2265$ orbits, with $300547$ comparability arcs. The maximum flow equals the total mass. \item Stage 2: $8051$ partitions for $S$ and $12061$ for $H$, in $1105$ and $1625$ orbits, with $135731$ arcs. The maximum flow equals the total mass. \end{enumerate} \end{proposition} By Lemmas~\ref{lem:sym} and~\ref{lem:subst}, $\LG$ percolates at $0.50001>1/2$ (Lemma~\ref{lem:LG}), hence $H$ percolates at $0.5755$, hence $S$ percolates at $0.6463$. So $p_c\le 0.6463$. Both flows were also recomputed with the maximum-flow routine of the \texttt{networkx} library (version 3.7), with the same result. \emph{Self-test.} With $2\times2$ tiles $(1,1)+\{0,1\}^2+2\Z^2$, the domination of $H$ at $0.586668$ by $S$ holds at $0.6795$ and fails at $0.6794$. This run is only a regression test of the program; it does not prove anything about \cite{Wi95}, whose chain we could not check. \emph{Sharpness.} Stage~2 fails with $S$ at $0.6462$ (deficit about $6\cdot10^{-5}$ of the total mass), while stage~1 still holds with $H$ at $0.5754$. So on the grid $10^{-4}$, $0.6463$ is the best value of this chain with $4\times4$ tiles. \subsection*{Running the programs} On our machine the lower-bound program runs in under one second, and the upper-bound program in $15$ to $25$ seconds with about $110$ MB of memory. Both print \texttt{CERTIFIE} on success. \subsection*{Acknowledgement} Technical assistance: Claude (Anthropic). \begin{thebibliography}{BE96} \bibitem[As26]{As26} C.~Ashton, $p_c^{\mathrm{site}}(\Z^2)\ge 0.5567$, computer-assisted proof, \url{https://kaust-a-laut.github.io/pdfs/z2-site-lower-bound-0.5567-proof.pdf}; dated 18 October 2026 on the author's page \url{https://kaust-a-laut.github.io/}, accessed 3 November 2026. \bibitem[BE96]{BE96} J.~van den Berg, A.~Ermakov, A new lower bound for the critical probability of site percolation on the square lattice, \emph{Random Structures Algorithms} \textbf{8} (1996), 199--212. \bibitem[Fi61]{Fi61} M.~E.~Fisher, Critical probabilities for cluster size and percolation problems, \emph{J.\ Math.\ Phys.} \textbf{2} (1961), 620--627. \bibitem[Ja15]{Ja15} J.~L.~Jacobsen, Critical points of Potts and $O(N)$ models from eigenvalue identities in periodic Temperley--Lieb algebras, arXiv:1507.03027 (2015). \bibitem[Ke80]{Ke80} H.~Kesten, The critical probability of bond percolation on the square lattice equals $\frac12$, \emph{Comm.\ Math.\ Phys.} \textbf{74} (1980), 41--59. \bibitem[MP89]{MP89} M.~V.~Menshikov, K.~D.~Pelikh, Percolation with several defect types. An estimate of critical probability for a square lattice, \emph{Mat.\ Zametki} \textbf{46} (1989), 38--47. \bibitem[OW24]{OW24} S.~P.~Oberly, J.~C.~Wierman, A new upper bound for the site percolation threshold of the square lattice, poster, Johns Hopkins University Design Day, \url{https://designday.jhu.edu/wp-content/uploads/formidable/18/Oberly-Sam_Poster_percolation_threshold-4.pdf}, accessed 3 November 2026. \bibitem[Ru81]{Ru81} L.~Russo, On the critical percolation probabilities, \emph{Z.\ Wahrscheinlichkeitstheorie verw.\ Gebiete} \textbf{56} (1981), 229--238. \bibitem[To85]{To85} B.~T\'oth, A lower bound for the critical probability of the square lattice site percolation, \emph{Z.\ Wahrscheinlichkeitstheorie verw.\ Gebiete} \textbf{69} (1985), 19--22. \bibitem[Wi95]{Wi95} J.~C.~Wierman, Substitution method critical probability bounds for the square lattice site percolation model, \emph{Combin.\ Probab.\ Comput.} \textbf{4} (1995), 181--188. \bibitem[WO24]{WO24} J.~C.~Wierman, S.~P.~Oberly, A new upper bound for the site percolation threshold of the square lattice, in: F.~Hoffman, S.~Heuss, R.~Low, J.~C.~Wierman (eds.), \emph{Combinatorics, Graph Theory and Computing} (SEICCGTC 2022), Springer Proc.\ Math.\ Stat.\ \textbf{462}, Springer, Cham, 2024, 129--138, \url{https://doi.org/10.1007/978-3-031-62166-6_9}. \end{thebibliography} \end{document}