* [10] S. Marmi, P. Moussa, J.-C. Yoccoz, _The cohomological equation for Roth-type interval exchange maps_ , J. Amer. Math. Soc. 18 (2005), 823-872.
  * [11] S. Marmi, P. Moussa, J.-C. Yoccoz, _Linearization of generalized interval exchange maps_ , Ann. of Math. (2) 176 (2012), 1583-1646.
  * [12] Y. Minsky and B. Weiss, _Cohomology classes represented by measured foliations, and Mahler’s question for interval exchanges_ , Ann. Sci. Éc. Norm. Supér. (4) 47 (2014), 245-284.
  * [13] M. Pnueli, V. Rom-Kedar, _On near integrability of some impact systems_ , SIAM J. Appl. Dyn. Syst. 17 (2018), 2707-2732.
  * [14] M. Pnueli, V. Rom-Kedar, _On the structure of Hamiltonian impact systems_ , Nonlinearity 34 (2021), 2611-2658.
  * [15] M. Pnueli, V. Rom-Kedar, _Near tangent dynamics in a class of Hamiltonian impact systems_ , SIAM J. Appl. Dyn. Syst. 21 (2022), 2000–2046.
  * [16] G. Sansone, J. Gerretsen, _Lectures on the theory of functions of a complex variable. I. Holomorphic functions._ P. Noordhoff, Groningen 1960 xii+488 pp.
  * [17] M.P. Wojtkowski, _A system of one-dimensional balls with gravity_ , Comm. Math. Phys. 126 (1990), 507-533.
  * [18] M. Viana, Dynamics of Interval Exchange Transformations and Teichmüller Flows, lecture notes available from http://w3.impa.br/~viana/out/ietf.pdf
  * [19] O. Yaniv, V. Rom-Kedar, _Quantum pseudointegrable Hamiltonian impact system_ , Phys. Rev. E 107 (2023), Paper No. 054221, 9 pp.
  * [20] J.-Ch. Yoccoz, _Interval exchange maps and translation surfaces_ , Homogeneous flows, moduli spaces and arithmetic, 1-69, Clay Math. Proc., 10, Amer. Math. Soc., Providence, RI, 2010.
  * [21] V. Zharnitsky, _Invariant tori in Hamiltonian systems with impacts_ , Comm. Math. Phys. 211 (2000), 289-302.
  * [22] A. Zorich, Flat surfaces, Frontiers in number theory, physics, and geometry. I, Springer, Berlin (2006), 437-583.


$\displaystyle\lVert\mathbf{U}\circ\mathbf{T}-\mathbf{U}\rVert_{0,{\Omega}}\leq\vartheta^{\frac{1}{2}}\lVert\mathbf{T}-\operatorname{\mathsf{I}}\rVert_{\bm{L}^{\infty}(\Upsilon)}\lVert\mathbf{U}\rVert_{1,{\Upsilon}}\leq(\vartheta^{\frac{1}{2}}+1)\lVert\mathbf{T}-\operatorname{\mathsf{I}}\rVert_{\bm{L}^{\infty}(\Upsilon)}\lVert\mathbf{U}\rVert_{1,{\Upsilon}}.$

The statement for $s=1$ follows by density of
$\bm{\mathcal{C}}^{\infty}(\Upsilon)$ in $\bm{H}^{1}(\Upsilon)$. The result
for real $s\in(0,1)$ follows by applying real interpolation in Sobolev spaces
(_cf._ [39, Lem. 22.3]). ∎

## References

  * [1] G.S. Alberti and Y. Capdeboscq.  Elliptic regularity theory applied to time harmonic anisotropic Maxwell’s equations with less than Lipschitz complex coefficients.  SIAM J. Math. Anal., 46(1):998–1016, 2014.
  * [2] Titu Andreescu and Bogdan Enescu.  Mathematical Olympiad Treasures.  Birkhäuser Boston, 2012.
  * [3] D. N. Arnold and S. W. Walker.  The Hellan–Herrmann–Johnson method with curved elements.  SIAM J. on Numer. Anal., 58(5):2829–2855, 2020.
  * [4] R. Aylwin and C. Jerez-Hanckes.  The effect of quadrature rules on finite element solutions of Maxwell variational problems.  Numer. Math., 2021.
  * [5] R. Aylwin, C. Jerez-Hanckes, C. Schwab, and J. Zech.  Domain uncertainty quantification in computational electromagnetics.  SIAM/ASA J. Uncertain. Quantif., 8(1):301–341, 2020.
  * [6] Rubén Aylwin, Carlos Jerez-Hanckes, and José Pinto.  On the properties of quasi-periodic boundary integral operators for the Helmholtz equation.  Integral Equations and Operator Theory, 92(2):1–41, 2020.
  * [7] Ivo Babuška and Jan Chleboun.  Effects of uncertainties in the domain on the solution of Dirichlet boundary value problems.  Numerische Mathematik, 93(4):583–610, feb 2003.
  * [8] Ivo Babuška and Benqi Guo.  Optimal estimates for lower and upper bounds of approximation errors in the p-version of the finite element method in two dimensions.  Numerische Mathematik, 85(2):219–255, apr 2000.
  * [9] P. K. Bhattacharyya and N. Nataraj.  On the combined effect of boundary approximation and numerical integration on mixed finite element solution of 4th order elliptic problems with variable coefficients.  ESAIM: Math. Model. and Numer. Anal., 33(4):807–836, 1999.
  * [10] J. H. Bramble and J. T. King.  A robust finite element method for nonhomogeneous Dirichlet problems in domains with curved boundaries.  Math. Comput., 63(207):1–17, 1994.
  * [11] A. Buffa, M. Costabel, and D. Sheen.  On traces for ${\bf H}({\bf curl},\Omega)$ in Lipschitz domains.  J. Math. Anal. Appl., 276(2):845–867, 2002.
  * [12] A. Buffa and R. Hiptmair.  Galerkin boundary element methods for electromagnetic scattering.  In Topics in computational wave propagation, volume 31 of Lect. Notes Comput. Sci. Eng., pages 83–124. Springer, Berlin, 2003.
  * [13] A. Buffa, R. Hiptmair, T. von Petersdorff, and C. Schwab.  Boundary element methods for Maxwell transmission problems in Lipschitz domains.  Numer. Math., 95(3):459–485, 2003.
  * [14] S.N. Chandler-Wilde, D.P. Hewett, A. Moiola, and J. Besson.  Boundary element methods for acoustic scattering by fractal screens.  Numer. Math., pages 1–53, 2021.
  * [15] P. G. Ciarlet and P. A. Raviart.  The combined effect of curved boundaries and numerical integration in isoparametric finite element methods.  In The mathematical foundations of the finite element method with applications to partial differential equations, pages 409–474. Elsevier, 1972.
  * [16] P. G. Ciarlet and P. A. Raviart.  Interpolation theory over curved elements, with applications to finite element methods.  Comput. Methods Appl. Mech. Eng., 1(2):217–249, 1972.
  * [17] D. Daners.  Dirichlet problems on varying domains.  J. Differ. Equ., 188(2):591–624, 2003.
  * [18] M. C. Delfour and J.-P. Zolésio.  Shapes and geometries, volume 22 of Advances in Design and Control.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, second edition, 2011.  Metrics, analysis, differential calculus, and optimization.
  * [19] D. A. Di Pietro and J. Droniou.  A third Strang lemma and an Aubin–Nitsche trick for schemes in fully discrete formulation.  Calcolo, 55(3):40, 2018.
  * [20] P. Dular and C. Geuzaine.  GetDP reference manual: the documentation for GetDP, a general environment for the treatment of discrete problems.
  * [21] A. Ern and J.L. Guermond.  Analysis of the edge finite element approximation of the Maxwell equations with low regularity solutions.  Comput. Math. Appl., 75(3):918–932, 2018.
  * [22] Christophe Geuzaine and Jean-François Remacle.  Gmsh: A 3-D finite element mesh generator with built-in pre-and post-processing facilities.  International journal for numerical methods in engineering, 79(11):1309–1331, 2009.
  * [23] E. Hernández and R. Rodríguez.  Finite element approximation of spectral problems with Neumann boundary conditions on curved domains.  Math. Comput., 72(243):1099–1115, 2003.
  * [24] Ralf Hiptmair, Jingzhi Li, and Jun Zou.  Convergence analysis of finite element methods for $\bm{H}(\operatorname{\mathbf{curl}};\Omega)$-elliptic interface problems.  Numer. Math., 122(3):557–578, 2012.
  * [25] C. Jerez-Hanckes, C. Schwab, and J. Zech.  Electromagnetic wave scattering by random surfaces: Shape holomorphy.  Math. Model. Meth. Appl. Sci., 27(12):2229–2259, 2017.
  * [26] A. Johnen, J.-F. Remacle, and C. Geuzaine.  Geometrical validity of curvilinear finite elements.  Journal of Computational Physics, 233:359–372, jan 2013.
  * [27] M. Lee, S. Choo, and S. Chung.  Curved domain approximation in Dirichlet’s problem.  J. Korean Math. Soc., 40(6):1075–1083, 2003.
  * [28] M. Lenoir.  Optimal isoparametric finite elements and error estimates for domains involving curved boundaries.  SIAM J. Numer. Anal., 23(3):562–580, 1986.
  * [29] P. Monk and D. Leszek.  Discrete compactness and the approximation of Maxwell’s equations in $\mathbb{R}^{3}$.  Math. Comput., 70(234):507–523, 2001.
  * [30] Peter Monk.  Finite element methods for Maxwell’s equations.  Oxford University Press, 2003.
  * [31] U. Mosco.  Convergence of convex sets and of solutions of variational inequalities.  Adv. Math., 3(4):510–585, 1969.
  * [32] U. Mosco.  An introduction to the approximate solution of variational inequalities.  In Constructive Aspects of Functional Analysis, pages 497–682. Springer, 1971.
  * [33] Jean-Claude Nédélec.  Acoustic and Electromagnetic Equations.  Springer New York, 2001.
  * [34] O. Pironneau.  Optimal Shape Design for Elliptic Systems.  Springer Berlin Heidelberg, 1984.
  * [35] S. A. Sauter and C Schwab.  Boundary element methods, volume 39 of Springer Series in Computational Mathematics.  Springer-Verlag, Berlin, 2011.  Translated and expanded from the 2004 German original.
  * [36] Gerardo Silva-Oelker, Rubén Aylwin, Carlos Jerez-Hanckes, and Patrick Fay.  Quantifying the impact of random surface perturbations on reflective gratings.  IEEE Transactions on Antennas and Propagation, 66(2):838–847, 2017\.
  * [37] J. Sokolowski and J.P. Zolesio.  Introduction to Shape Optimization.  Springer Berlin Heidelberg, 1992.
  * [38] G. Strang and A. E. Berger.  The change in solution due to change in domain.  In Proceedings of the Symposia in Pure Mathematics, volume 23, pages 199–205. as, 1973.
  * [39] L. Tartar.  An introduction to Sobolev spaces and interpolation spaces, volume 3.  Springer Science & Business Media, 2007.
  * [40] V. Thomée.  Polygonal domain approximation in Dirichlet’s problem.  IMA J. Appl. Math., 11(1):33–44, 02 1973.
  * [41] M. Vanmaele and A. Ženíšek.  The combined effect of numerical integration and approximation of the boundary in the finite element method for eigenvalue problems.  Numer. Math., 71(2):253–273, 1995.
  * [42] M. Zlámal.  Curved elements in the finite element method. II.  SIAM J. Numer. Anal., 11(2):347–362, 1974.


# Triangle Percolation on the Grid

Igor Araujo Bryce Frederickson Robert A. Krueger
Bernard Lidický Tyrrell B. McAllister Florian Pfender
Sam Spiro Eric Nathan Stucky Department of Mathematics, University of Illinois
at Urbana-Champaign, Urbana, IL. Email<EMAIL_ADDRESS>Research
partially supported by UIUC Campus Research Board RB 22000.Department of
Mathematics, Emory University, Atlanta, GA, E-mail:
<EMAIL_ADDRESS>of Mathematics, University of Illinois at Urbana-
Champaign, Urbana, IL. Email<EMAIL_ADDRESS>Research supported the NSF
Graduate Research Fellowship Program Grant No. DGE 21-4675.Department of
Mathematics, Iowa State University, Ames, IA. E-mail<EMAIL_ADDRESS>Research of this author is supported in part by NSF grant DMS-2152490 and
Scott Hanna fellowship.Department of Mathematics and Statistics, University of
Wyoming, Laramie, WY. E-mail<EMAIL_ADDRESS>of Mathematical and
Statistical Sciences, University of Colorado Denver. E-mail:
<EMAIL_ADDRESS>Research is partially supported by NSF grant
DMS-2152498.Department of Mathematics, Rutgers University, Piscataway, NJ.
Email<EMAIL_ADDRESS>Research supported by the NSF
Mathematical Sciences Postdoctoral Research Fellowships Program under Grant
DMS-2202730.E-mail<EMAIL_ADDRESS>Research partially supported by Czech
Science Foundation grant 21-00420M, administered through Charles University,
Faculty of Mathematics and Physics, Department of Algebra.

###### Abstract

We consider a geometric percolation process partially motivated by recent work
of Hejda and Kala. Specifically, we start with an initial set
$X\subseteq\mathbb{Z}^{2}$, and then iteratively check whether there exists a
triangle $T\subseteq\mathbb{R}^{2}$ with its vertices in $\mathbb{Z}^{2}$ such
that $T$ contains exactly four points of $\mathbb{Z}^{2}$ and exactly three
points of $X$. In this case, we add the missing lattice point of $T$ to $X$,
and we repeat until no such triangle exists. We study the limit sets $S$, the
sets stable under this process, including determining their possible densities
and some of their structure.

##  1 Introduction

Bootstrap percolation is a well-studied model in graph theory that describes
how vertices in a network propagate information to their neighbors. Initiated
over 40 years ago by physicists to study models of magnetization in
statistical mechanics (see, e.g., [1, 15]), it has also been applied in
sociology and computer science. The underlying theory has also attracted
mathematical study; see, e.g., [6, 9] for early examples of the graph-
theoretic formulation for this model, and the introductions of [3, 7] for
contemporary work.

More recently, bootstrap percolation has been implemented on network
structures beyond graphs. In particular, the pioneering paper by Balogh,
Bollobás, Morris and Riordin [8] defined the following variant of the model
for hypergraphs. Given a hypergraph $H$ with vertex set $V$ and hyperedge set
$E$, for any subset $X$ of vertices, we define

$p_{H}(X)=X\cup\Big{\\{}v\in V:\exists e\in E\text{ such that }v\in e\text{
and }e\subseteq X\cup\\{v\\}\Big{\\}}.$

In other words we grow $X$ by adding vertices that “complete a hyperedge”. We
let $p_{H}^{n}(X)=p_{H}(\cdots p_{H}(X)\cdots)$, iterated $n$ times, and we
say that a subset $S$ is $H$-stable (or simply, stable) if $S=p_{H}(S)$. That
original paper considered hypergraphs with vertices in a finite grid whose
hyperedges are products of intervals and computed a well-studied invariant in
the graph case: the smallest size of a set $X$ such that
$p_{H}^{\infty}(X)=V$.

This led to an active study on a class of translation-invariant hypergraphs on
$\mathbb{Z}^{d}$, written in the language of cellular automata [17] and the
“update families” of Bollobás, Smith, and Uzzell [13]. Their paper spawned a
great deal of interest in the update family formulation (see, e.g., [4, 5, 12,
18, 19]). Other developments in this field have had a more geometric flavor,
considering hypergraphs arising from lines in $\mathbb{Z}^{d}$ [2] and finite
projective planes [16].

We continue this geometric theme. The configurations that we consider are of
the form $\Delta\cap\mathbb{Z}^{2}$ where $\Delta\subseteq\mathbb{R}^{2}$ is a
lattice triangle, that is, the convex hull in $\mathbb{R}^{2}$ of three non-
collinear points in $\mathbb{Z}^{2}$. Such a triangle is determined by the set
of integer-lattice points that it contains. Accordingly, we abuse terminology
a bit and call a subset $T\subseteq\mathbb{Z}^{2}$ a triangle when $T$ is the
set of integer-lattice points in some lattice triangle
$\Delta\subseteq\mathbb{R}^{2}$. Thus, in our terminology, the triangle $T$ is
a finite set containing at least three points. We call $T$ a minimal triangle
if $T$ contains exactly four points. A minimal triangle is either a border or
an internal triangle, depending on whether the fourth point (in addition to
the vertices) appears on the boundary or the interior of the triangle.

In this paper, we study stable sets with respect to three hypergraphs $B,I$,
and $BI$ on the vertex set $\mathbb{Z}^{2}$, whose hyperedges are all of the
border, internal, and minimal triangles, respectively. The triangles that
define this percolation are simple structures, but they allow for long-
distance effects to occur in just one step of the process, because the
triangles may be extremely thin (see Figure 10).

Our results are framed in a somewhat different language because our original
motivation for this study came instead from recent developments in the theory
of universal quadratic forms. While attempting to improve certain dimension
bounds in [11], Hejda and Kala [20] obtained a remarkable result about the
totally positive integers $\mathcal{O}_{K}^{+}$ for (totally positive)
quadratic number fields $K$: the abstract isomorphism type of the semigroup
$\mathcal{O}_{K}^{+}$ already suffices to determine the quadratic extension
$K$. The argument in their proof can be reframed as follows: a canonical
choice of generators $(\dotsc,x_{-1},x_{0},x_{1},\dotsc)$ comes with relations
of the form $x_{i-1}+x_{i+1}=c_{i}x_{i}$ for all $i$. Once any two consecutive
points are fixed, successively applying these relations fixes all the other
points, which determines all relations among them. In this sense, all
relations among these generators are determined by “local” ones.

For number fields of higher rank, the analogous generators
$\mathcal{O}_{K}^{+}$ are much more elusive, and not much is known about the
relations (see, e.g., [14, 21, 22]). Nonetheless, it is natural to wonder if
there is an abstract Hejda–Kala type argument showing that only some initial
data and the “local” relations could determine the entire semigroup structure
of $\mathcal{O}_{K}^{+}$. However, note that at each stage it must be possible
to determine at least one additional point from those which have already been
determined; in $\mathbb{R}^{1}$ (rank 2) this is certainly possible, but in
higher dimensions the situation is less clear. Our stable sets may be
understood roughly as a worst-case analysis of such combinatorial obstructions
in rank 3.

###  1.1 Definitions and results

As mentioned before, we call a subset $T\subseteq\mathbb{Z}^{2}$ a triangle if
$T$ is the set of integer-lattice points in the convex hull $\Delta$ in
$\mathbb{R}^{2}$ of three noncollinear points in $\mathbb{Z}^{2}$. Such a
triangle $T$ uniquely determines $\Delta$ (which is a triangle in the
conventional sense) so we may speak of the area, vertices, boundary points,
and interior points of $T$. The triangle $T$ is unimodular if the vertices are
an affine basis of the lattice $\mathbb{Z}^{2}$ over $\mathbb{Z}$.
Equivalently, the unimodular triangles are the triangles that have area $1/2$.
Pick’s formula $A=i+b/2-1$ expresses the area $A$ of $T$ in terms of the
number $b$ of lattice points on its boundary and the number $i$ of lattice
points in its interior. From this relation, unimodular triangles are easily
recognized as precisely the triangles that contain exactly $3$ points. Recall
also that a minimal triangle is a triangle that contains exactly $4$ points,
and it is either a border or an internal triangle, depending on whether the
non-vertex point appears on the triangle’s boundary or the interior. From
Pick’s formula, the border triangles are precisely the triangles of area $1$,
and every internal triangle has area $3/2$ (though some triangles of area
$3/2$ are not internal triangles).

A unimodular transformation of $\mathbb{Z}^{2}$ is an affine-linear bijection
from $\mathbb{Z}^{2}$ to $\mathbb{Z}^{2}$. Equivalently, the unimodular
transformations of $\mathbb{Z}^{2}$ are the maps of the form $x\mapsto Mx+b$,
where $M$ is a $2\times 2$ matrix with integer entries and determinant $\pm
1$, and $b\in\mathbb{Z}^{2}$. Note that unimodular transformations also
preserve the number of lattice points on a line segment. Thus unimodular
transformations preserve the property of a triangle being unimodular, border,
or internal.

Let $S$ be a subset of $\mathbb{Z}^{2}$. We say that $S$ is B-stable if no
border triangle has exactly three of its points in $S$. We call $S$ I-stable
if no internal triangle has exactly three of its points in $S$. Finally, we
call $S$ BI-stable if $S$ is both B-stable and I-stable. Since
$\mathbb{Z}^{2}$ itself is BI-stable, we say that a proper subset $S$ of
$\mathbb{Z}^{2}$ is a maximal B/I/BI-stable set if $S$ is B/I/BI-stable and no
B/I/BI-stable proper subset of $\mathbb{Z}^{2}$ properly contains $S$.

Not I-stable

Not B-stable

Figure 1: Configurations that are not stable. Specifically, if a set contains
only the three blue points in one of the minimal triangles but not the red
cross in that triangle, then that triangle demonstrates that the set is not
stable in the indicated sense.

Roughly speaking, our results fall into two categories: results regarding the
possible densities of B/I/BI-stable sets and results regarding the existence
and uniqueness of B/I/BI-stable subsets that satisfy various conditions, such
as maximality or the presence of particular point-configurations.

Our first two theorems summarize our results on the densities of stable sets.
We define the (upper) density of a subset $X\subseteq\mathbb{Z}^{2}$ to be

$\overline{\delta}(X)\mathrel{\coloneqq}\limsup_{n\to\infty}\frac{\left\lvert
X\cap[-n,n]^{2}\right\rvert}{\left\lvert[-n,n]^{2}\right\rvert},$

where, here and throughout, $[a,b]$ denotes the interval of integers
$\left\\{i\in\mathbb{Z}\,:\,a\leq i\leq b\right\\}$. While
$\overline{\delta}(X)$ is a fairly natural way to define the density of a
subset $X\subseteq\mathbb{Z}^{2}$, it is not always true that
$\overline{\delta}(\varphi(X))=\overline{\delta}(X)$ for every unimodular
transformation $\varphi$. As an illustration, the set
$\\{(x,y)\in\mathbb{Z}^{2}:xy>0\\}$ is mapped to
$\\{(x,y)\in\mathbb{Z}^{2}:x(y-x)>0\\}$ under the unimodular map
$(x,y)\mapsto(x,x+y)$, and while the former has density $1/2$, the latter has
density $1/4$. However, density is preserved under unimodular transformation
for sets $X$ that are periodic in two independent directions, which will be
the case for most of the subsets $X\subseteq\mathbb{Z}^{2}$ that we consider.
Our first theorem gives the possible values of these densities for stable sets
(periodic or aperiodic).

######  Theorem 1.1.

Let $S\subsetneq\mathbb{Z}^{2}$.

  1. (a)

If $S$ is B-stable, then $\overline{\delta}(S)\leq 1/4$. Moreover, for every
$\delta\leq 1/4$, there exists a BI-stable set $S$ with
$\overline{\delta}(S)=\delta$; for instance, every subset of
$2\mathbb{Z}^{2}\coloneqq 2\mathbb{Z}\times 2\mathbb{Z}$ is BI-stable.

  2. (b)

If $S$ is I-stable, then $\overline{\delta}(S)\leq 1/2$. Moreover, for every
$\delta\leq 1/2$, there exists an I-stable set $S$ with
$\overline{\delta}(S)=\delta$; for instance, every subset of $\mathbb{Z}\times
2\mathbb{Z}$ is I-stable.

The two upper bounds in 1.1 are proved in Propositions 3.5 and 4.12,
respectively. The BI-stability of $2\mathbb{Z}^{2}$ and its subsets is 2.2,
and the I-stability of $\mathbb{Z}\times 2\mathbb{Z}$ and its subsets is 4.3.

For B-stable sets (and in particular for BI-stable sets), the upper bound in
1.1 is attained by $2\mathbb{Z}^{2}$. Our next theorem shows that any stable
set that is “structurally far” from $2\mathbb{Z}^{2}$ must have a
significantly lower density. That is, the maximally dense construction for
B-stable sets is “stable” in the sense commonly used in extremal
combinatorics. In order to state this result precisely, we define the (lower)
consecutive density $\underline{\gamma}(X)$ of a set
$X\subseteq\mathbb{Z}^{2}$ as follows: Let $\Gamma(X)$ denote the set of
points $(x,y)\in X$ such that $(x+1,y)\in X$, and let

$\underline{\gamma}(X)\mathrel{\coloneqq}\liminf_{n\to\infty}\frac{\left\lvert\Gamma(X)\cap[-n,n]^{2}\right\rvert}{\left\lvert[-n,n]^{2}\right\rvert}.$

Note that $\underline{\gamma}(2\mathbb{Z}^{2})=0$. Thus, the consecutive
density provides one measure of the “distance” between a set
$X\subseteq\mathbb{Z}^{2}$ and $2\mathbb{Z}^{2}$. We show that, for B-stable
proper subsets $S\subsetneq\mathbb{Z}^{2}$, if $\underline{\gamma}(S)$ is
large, then $\overline{\delta}(S)$ must be correspondingly smaller than the
maximum given by 1.1. The following is proved in Section 3.1.

######  Theorem 1.2.

If $S\subsetneq\mathbb{Z}^{2}$ is B-stable (in particular, if $S$ is BI-
stable), then $\underline{\gamma}(S)\leq 1/9$ and
$\overline{\delta}(S)\leq(1-\underline{\gamma}(S))/4$. Moreover, there is a
BI-stable sets $S$ with $\underline{\gamma}(S)=1/9$ and
$\overline{\delta}(S)=2/9$, and a BI-stable set $S^{\prime}$ with
$\underline{\gamma}(S^{\prime})=0$ and $\overline{\delta}(S^{\prime})=1/4$.

We remark that no analogous result is possible for I-stable sets. For example,
there exist two very different I-stable sets $I_{2}$ and $J_{1/2}$ that both
have the maximum possible density $1/2$. (See Constructions 4.1 and 4.4 below
for the definitions of $I_{2}$ and $J_{1/2}$, respectively.)

Our next two theorems summarize our results regarding the existence and
uniqueness of stable sets under various conditions. The next theorem shows
that, if a stable set $S$ contains certain small configurations, then $S$ must
be one of a very few different sets. For the definitions of the sets $J_{1/4}$
and $J_{1/2}$ referred to in the theorem, see Construction 4.4 and Figure 6
below.

######  Theorem 1.3.

Let $S\subseteq\mathbb{Z}^{2}$.

  1. (a)

If $S$ is B-stable and contains any three points of a border triangle, then
$S=\mathbb{Z}^{2}$.

  2. (b)

If $S$ is BI-stable and contains any three points of a minimal triangle, then
$S=\mathbb{Z}^{2}$.

  3. (c)

If $S$ is I-stable and contains any three points of an internal triangle,
then, up to a unimodular transformation, $S$ is one of $J_{1/4}$, $J_{1/2}$,
or $\mathbb{Z}^{2}$.

######  Remark 1.4.

In the language of bootstrap percolation, this theorem implies that our models
are “supercritical” in the classification of Bollobás, Smith, and Uzzell [13].
Indeed, they admit finite _percolating sets_ (i.e. finite $X$ with
$p_{H}^{\infty}(X)=\mathbb{Z}^{2}$); these have minimum size 3 for the
hypergraphs B and BI, and 5 for I.

Parts (a) and (b) of 1.3 are proved in Proposition 3.1, while Part (c) follows
from 4.10. Note that, in particular, if $S$ contains a unimodular triangle,
then $S$ meets all of the “contains any three points of …” conditions in 1.3.

Our final theorem summarizes our results regarding maximal stable sets. The
first two parts of this theorem show that the study of stable sets reduces to
the study of maximal stable sets.

######  Theorem 1.5.

  1. (a)

If $S$ is a B/BI-stable proper subset of $\mathbb{Z}^{2}$, then every subset
of $S$ is B/BI-stable (of the same stability type).

  2. (b)

If $S$ is an I-stable subset of $\mathbb{Z}^{2}$ that is not, up to unimodular
transformation, either $J_{1/4}$, $J_{1/2}$, or $\mathbb{Z}^{2}$, then every
subset of $S$ is I-stable.

  3. (c)

Every B/I/BI-stable proper subset of $\mathbb{Z}^{2}$ is contained in a
maximal B/I/BI-stable set (of the same stability type).

  4. (d)

There exist non-periodic maximal B/I/BI-stable sets.

Part (a) of 1.5 is proved in 3.2. Part (b) follows from 4.11. Part (c) is
proved in Proposition 5.3, and Part (d) is proved in Propositions 5.4 and 5.5.

This paper is organized as follows. In Sections 2, 3, LABEL:, and 4 we
consider BI-stable, B-stable, and I-stable sets respectively. In Section 5 we
study maximal stable sets. We conclude with some open problems in Section 6.

##  2 BI-stable Sets

In this section we give several constructions of BI-stable sets. Here and
throughout, we use the standard notations

$\displaystyle nX$ $\displaystyle\mathrel{\coloneqq}\left\\{nx\,:\,x\in
X\right\\},$ $\displaystyle X+Y$
$\displaystyle\mathrel{\coloneqq}\left\\{x+y\,:\,\text{$x\in X$ and $y\in
Y$}\right\\},$ $\displaystyle X+z$
$\displaystyle\mathrel{\coloneqq}X+\left\\{z\right\\},$

for integers $n\in\mathbb{Z}$, subsets $X,Y\subseteq\mathbb{Z}^{2}$, and
points $z\in\mathbb{Z}^{2}$. We will also write $[n]$ for the interval
$[1,n]=\left\\{1,\dotsc,n\right\\}$ of integers.

Our first construction is the set $n\mathbb{Z}^{2}$; see Figure 2 for the case
$n=2$.

Figure 2: The blue points denote $2\mathbb{Z}^{2}$, a BI-stable set of density
$1/4$.

######  Proposition 2.1.

Let $n\geq 2$. Every minimal triangle intersects $n\mathbb{Z}^{2}$ in at most
$2$ points. In particular, every subset of $n\mathbb{Z}^{2}$ is BI-stable.

###### Proof.

The line segment between any two points of $n\mathbb{Z}^{2}$ contains at least
$n+1\geq 3$ lattice points including the endpoints, so any triangle containing
at least three points of $n\mathbb{Z}^{2}$ will contain at least $2n+1>4$
lattice points and thus cannot be a border or internal triangle. ∎

With this lemma we can prove the existence statement of 1.1(a) for BI-stable
sets with small density.

######  Corollary 2.2.

For every $\delta\leq 1/4$, there exists a set $S\subseteq 2\mathbb{Z}^{2}$
with $\overline{\delta}(S)=\delta$ that is BI-stable (and hence also B-stable
and I-stable).

###### Proof.

Let $X^{(0)}\mathrel{\coloneqq}\emptyset$, and iteratively define
$X^{(n)}\subseteq 2\mathbb{Z}^{2}\cap[-n,n]^{2}$ to be any set containing
$X^{(n-1)}$ and which has exactly
$\min\left\\{\left\lfloor\delta(2n+1)^{2}\right\rfloor,\left\lvert
2\mathbb{Z}^{2}\cap[-n,n]^{2}\right\rvert\right\\}$ points of
$2\mathbb{Z}^{2}$. Let $S\mathrel{\coloneqq}\bigcup_{i\geq 0}X^{(i)}$. By
construction we have $\overline{\delta}(S)=\delta$. Since $S$ is a subset of
$2\mathbb{Z}^{2}$, $S$ is BI-stable by Proposition 2.1. ∎

We know of no other maximal BI-stable sets with upper density $1/4$ besides
$2\mathbb{Z}^{2}$ and its unimodular transforms; see 6.1 for more on this. In
fact, 1.2 shows that any BI-stable set that is “far” from $2\mathbb{Z}^{2}$
(in a certain precise sense) has density strictly smaller than $1/4$. The
following gives an example of a BI-stable set that is “far” from
$2\mathbb{Z}^{2}$ and which still has a relatively large density of $2/9$. See
Figure 3 for an illustration.

######  Construction 2.3.

Let $S_{2/9}^{*}\mathrel{\coloneqq}\\{(0,0),(1,0)\\}$ and
$S_{2/9}=S_{2/9}^{*}+3\mathbb{Z}^{2}$.

Figure 3: The blue points are from $S_{2/9}$, a BI-stable set of density $2/9$
defined in Construction 2.3.

######  Proposition 2.4.

The set $S_{2/9}$ is BI-stable with $\overline{\delta}(S_{2/9})=2/9$.

###### Proof.

First, recall that the area of a triangle with vertices $(a_{1},a_{2})$,
$(b_{1},b_{2})$, and $(c_{1},c_{2})$ is

$\frac{1}{2}\det\begin{bmatrix}b_{1}-a_{1}&b_{2}-a_{2}\\\
c_{1}-a_{1}&c_{2}-a_{2}\end{bmatrix}.$

When these vertices are in $S_{2/9}$, the second column of this matrix is a
multiple of 3, and thus the area of any such triangle is a multiple of $3/2$.

Thus $S_{2/9}$ contains neither any unimodular triangle nor the vertices of
any border triangle. Therefore, it intersects any border triangle in at most
$2$ points and so is B-stable.

Moreover, by the pigeonhole principle, among any three points in $S_{2/9}$
there must be at least two points that are in the same equivalence class
modulo $3\mathbb{Z}^{2}$. These two points have at least two additional
lattice points on the line segment joining them. Therefore, $S_{2/9}$ does not
contain the vertices of any internal triangle. As noted before, $S_{2/9}$ also
does not contain a unimodular triangle, and thus $S_{2/9}$ intersects any
internal triangle in at most $2$ points. Therefore, $S_{2/9}$ is also
I-stable. ∎

The proofs in this section showed that the relevant sets $S$ are BI-stable by
using a stronger property, namely that $S$ contains at most two points of any
minimal triangle. This is not a coincidence; as we shall soon see (Proposition
3.1(b) below), this property is equivalent to BI-stability for proper subsets
of the integer lattice.

##  3 B-stable Sets

In this section we establish our bounds on B-stable sets, namely that
$\overline{\delta}(S)\leq 1/4$ whenever $S\subsetneq\mathbb{Z}^{2}$ is a
B-stable set. Our most important structural result towards this end is the
following.

######  Proposition 3.1.

Let $S\subsetneq\mathbb{Z}^{2}$. Then $S$ is:

  1. (a)

B-stable if and only if $S$ contains at most $2$ points from any border
triangle, and

  2. (b)

BI-stable if and only if $S$ contains at most $2$ points from any minimal
triangle.

###### Proof.

We begin with part (a). Evidently, if $S$ contains at most $2$ points from any
border triangle, then by definition $S$ is B-stable. Conversely, assume that
$S$ is B-stable but contains at least $3$ points from a border triangle, which
implies $S$ contains all $4$ points of this border triangle. Applying a
unimodular transformation to $S$, we may assume without loss of generality
that this triangle is $\\{(0,0),(1,0),(2,0),(0,1)\\}$. Observe that, for each
$t\in\mathbb{Z}$, each of the border triangles $\\{(0,0),(1,0),(2,0),(t,1)\\}$
intersects $S$ in at least three points, and so the B-stability of $S$ implies
that $S$ contains every point of the form $(t,1)$. Thus, $S$ intersects each
of the triangles $\\{(0,1),(1,1),(2,1),(t,2)\\}$ in at least three points, and
hence contains every point of the form $(t,2)$. Iterating this procedure, both
up and down $\mathbb{Z}^{2}$, we conclude that $S=\mathbb{Z}^{2}$, completing
the proof of part (a).

We will show that part (b) follows from part (a). As before, containing at
most two points from any minimal triangle immediately implies BI-stability.
Conversely, if $S\subsetneq\mathbb{Z}^{2}$ is BI-stable, then $S$ contains at
most $2$ points from any border triangle by part (a); if $S$ contains at least
$3$ points from an internal triangle, then $S$ contains that internal
triangle. Applying a unimodular transformation, we may assume without loss of
generality that this triangle has points $\\{(0,0),(1,0),(-1,-1),(0,1)\\}$.
But then this triangle contains $3$ points $(0,0),(1,0),(0,1)$ from a border
triangle, a contradiction. ∎

######  Corollary 3.2.

If $S\subsetneq\mathbb{Z}^{2}$ is a B-stable set, then any subset of $S$ is
also B-stable. Similarly, if $S\subsetneq\mathbb{Z}^{2}$ is a BI-stable set,
then any subset of $S$ is also BI-stable.

3.2 follows immediately from Proposition 3.1 and yields a large supply of
examples. We note that the situation for I-stable sets is somewhat more
complicated (see 4.10).

With Proposition 3.1 we can also quickly derive the following.

######  Lemma 3.3.

If $S\subsetneq\mathbb{Z}^{2}$ is B-stable, then $\left\lvert
S\cap([3]\times[2])\right\rvert\leq 2$.

###### Proof.

Let $S\subsetneq\mathbb{Z}^{2}$ be B-stable. If $S$ contains at least three
points of $[3]\times[2]$, then without loss of generality we can assume it
contains at least two points from the set
$X\mathrel{\coloneqq}\\{(1,1),(2,1),(3,1)\\}$. If $S$ contains $X$, then $S$
contains three points of a border triangle, contradicting Proposition 3.1.
Otherwise, $S$ contains two points of $X$ and some point of the form $(x,2)$,
and so again $X$ contains three points of a border triangle. ∎

From this result, it follows that $\overline{\delta}(S)\leq 1/3$ for any
B-stable set $S\subsetneq\mathbb{Z}^{2}$. To see this, note first that any
translate of $S$ is also B-stable, and therefore $S$ contains at most two
points of any translate of $[3]\times[2]$. Now cover $[-n,n]^{2}$ by
$\lceil\frac{2n+1}{3}\rceil^{2}$ translates of $[3]\times[2]$. By the previous
lemma we know that $S$ contains at most a third of the points from each of
these translates, giving the bound.

We prove the optimal bound $\overline{\delta}(S)\leq 1/4$ similarly, using the
following more subtle replacement of 3.3.

######  Lemma 3.4.

If $S\subsetneq\mathbb{Z}^{2}$ is B-stable, then $\left\lvert
S\cap[6]^{2}\right\rvert\leq 9$.

We provide two proofs of this result. The first uses a computer search, the
code for which may be found in the supplementary files. For this we simply
exhaustively checked that all B-stable subsets of $[6]^{2}$ are either
$[6]^{2}$ or have at most $9$ points. However, we also give a human-readable
proof, which can be found in the appendix.

We now prove our main result for this section, which together with 2.2
completes the proof of 1.1(a).

######  Proposition 3.5.

If $S\subsetneq\mathbb{Z}^{2}$ is B-stable, then $\overline{\delta}(S)\leq
1/4$.

###### Proof.

Cover $[-n,n]^{2}$ by $\lceil\frac{2n+1}{6}\rceil^{2}$ pairwise disjoint
translates of $[6]\times[6]$. By 3.4, each of these translates contains at
most $9$ points of $S$, for a total of at most

$9\left\lceil\frac{2n+1}{6}\right\rceil^{2}\leq
9\left(\frac{2n+1}{6}+\frac{5}{6}\right)^{2}=\frac{1}{4}((2n+1)^{2}+20n+35)$

points in $S\cap[-n,n]^{2}$. ∎

######  Remark 3.6.

The $[6]\times[6]$ translates used in the proof of Proposition 3.5 are the
smallest translates that are able to prove the theorem this way. Indeed, for
every $a<6$ and every $b$, at least one of the B-stable sets $2\mathbb{Z}^{2}$
or $S_{2/9}$ from Construction 2.3 has more than $1/4$ of the points in
$[0,a-1]\times[0,b]$.

###  3.1 Consecutive pairs in B-stable sets

Here we prove 1.2, which roughly says that if a B-stable set has many
consecutive pairs, then its density cannot be close to the maximum of $1/4$.
For this we need two lemmas concerning $\Gamma(S)$, which we recall is the set
of points $(x,y)\in S$ such that $(x+1,y)\in S$.

######  Lemma 3.7.

Let $S\subsetneq\mathbb{Z}^{2}$ be a B-stable set. Then
$\left\lvert\Gamma(S)\cap[3]^{2}\right\rvert\leq 1$.

###### Proof.

Suppose $(x,y)\in\Gamma(S)\cap[3]^{2}$, which means $(x,y),(x+1,y)\in S$.
Checking all the cases, we easily see that any additional point
$(x^{\prime},y^{\prime})$ with $|x-x^{\prime}|\leq 2$ and $|y-y^{\prime}|\leq
2$ other than $(x-2,y)$ is in a border triangle with $(x,y)$ and $(x+1,y)$, so
$(x^{\prime},y^{\prime})\notin S$ by Proposition 3.1, and thus
$(x^{\prime},y^{\prime})\notin\Gamma(S)$. Finally, $(x-2,y)\notin\Gamma(S)$
since $(x-1,y)\notin S$. ∎

We obtained the next result by computer search, similar to 3.4. The code we
used may be found in the supplementary files.

######  Lemma 3.8.

Let $S\subsetneq\mathbb{Z}^{2}$ be a B-stable set. If
$\Gamma(S)\cap([6]\times[12])\neq\emptyset$, then

$\left\lvert S\cap([6]\times[12])\right\rvert\leq 16.$

We note that 3.4 implies that for any $S\subsetneq\mathbb{Z}^{2}$ which is
B-stable, $|S\cap([6]\times[12])|\leq 18$, so 3.4 says we have a stronger
bound provided $\Gamma(S)\cap([6]\times[12])\neq\emptyset$. We can now prove
1.2.

###### Proof of 1.2.

Let $S\subsetneq\mathbb{Z}^{2}$ be B-stable. To prove that
$\underline{\gamma}(S)\leq 1/9$, we use a similar argument as in the proof of
Proposition 3.5. Cover $[-n,n]^{2}$ by
$\left\lceil\frac{2n+1}{3}\right\rceil^{2}$ translates of $[3]^{2}$, each of
which contains at most one point of $\Gamma(S)$ by 3.7. This implies the
desired result.

Now we prove that
$\overline{\delta}(S)\leq\frac{1}{4}(1-\underline{\gamma}(S))$. Let
$\varepsilon>0$, and choose $n$ large enough such that

$\left\lvert\Gamma(S)\cap[-n,n]^{2}\right\rvert\geq(\underline{\gamma}(S)-\varepsilon)(2n+1)^{2}\geq(\underline{\gamma}(S)-\varepsilon)4n^{2}.$
(1)

Call a translate of $[6]\times[12]$ deficient if it contains a point in
$\Gamma(S)$. By 3.8, such a deficient translate contains at most $16$ points
in $S$. Since $[6]\times[12]$ can be covered by $8$ translates of $[3]^{2}$,
we have by 3.7 that every translate of $[6]\times[12]$ contains at most $8$
points in $\Gamma(S)$.

Cover $[-n,n]^{2}$ with $2\left\lceil\frac{2n+1}{12}\right\rceil^{2}$
translates of $[6]\times[12]$. Using (1), this implies that there are at least
$\frac{1}{2}(\underline{\gamma}(S)-\varepsilon)n^{2}$ deficient translates
among these. Therefore,

$\displaystyle\left\lvert S\cap[-n,n]^{2}\right\rvert$ $\displaystyle\leq$
$\displaystyle 18\times
2\left\lceil\frac{2n+1}{12}\right\rceil^{2}-2\times\frac{1}{2}(\underline{\gamma}(S)-\varepsilon)n^{2}$
$\displaystyle\leq$
$\displaystyle(1-\underline{\gamma}(S)+\varepsilon)n^{2}+12n+36$
$\displaystyle<$
$\displaystyle\frac{1}{4}(1-\underline{\gamma}(S)+\varepsilon)(2n+1)^{2}+12n+36.$

Since $\varepsilon>0$ was chosen arbitrarily, this shows that
$\overline{\delta}(S)\leq(1-\underline{\gamma}(S))\frac{1}{4}$.

The bound $\underline{\gamma}(S)\leq 1/9$ is best possible, as exhibited by
$S_{2/9}$ from Construction 2.3. Similarly the bounds on
$\overline{\delta}(S)$ are best possible when
$\underline{\gamma}(S)\in\\{0,1/9\\}$ by considering $2\mathbb{Z}^{2}$ and
$S_{2/9}$, respectively. ∎

######  Remark 3.9.

As with 3.6, the $[6]\times[12]$ translates used in the proof of 1.2 are the
smallest translates which work for this purpose. Indeed, by 3.6 such an
$[a]\times[b]$ window should have $a$ and $b$ divisible by $6$, but there are
B-stable sets $S\subseteq[6]\times[6]$ with $\Gamma(S)\neq\emptyset$ and
$\left\lvert S\right\rvert=9$, as shown in Figure 13.

######  Remark 3.10.

We do not expect the bound
$\overline{\delta}(X)\leq(1-\underline{\gamma}(X))\frac{1}{4}$ for B-stable
$X\subsetneq\mathbb{Z}^{2}$ to be sharp for all values of
$\underline{\gamma}(X)$. In fact, we can not rule out that having even a
single consecutive pair in $X$ decreases its density by a fixed constant; see
6.2.

###  3.2 B-stability without BI-stability

Most of the constructions of B-stable sets that we know of are also BI-stable.
However, the following gives an example of a set of positive density which is
B-stable but not BI-stable.

######  Construction 3.11.

Let $B_{1/12}^{*}\mathrel{\coloneqq}\\{(1,0),(0,1),(-1,-1)\\}$ and
$B_{1/12}\mathrel{\coloneqq}B_{1/12}^{*}+6\mathbb{Z}^{2}$; see Figure 4.

Figure 4:  The blue points are from $B_{1/12}$, a B-stable set of density
$1/12$ that is not I-stable. See Construction 3.11.

######  Proposition 3.12.

The set $B_{1/12}$ is B-stable, but not I-stable, with
$\overline{\delta}(B_{1/12})=1/12$.

###### Proof.

First note that $B_{1/12}$ is not I-stable, since $B_{1/12}^{*}$ are the three
vertices of an internal triangle, but $B_{1/12}$ does not contain the fourth
point, $(0,0)$. It is easy to check that
$\overline{\delta}(B_{1/12})=3/36=1/12$.

To check that $B_{1/12}$ is B-stable, we let $x$, $y$, and $z$ be three points
in $B_{1/12}$ and prove that they are not contained in the same border
triangle. To do this, it suffices to confirm they are not all consecutive
lattice points in any line, and also that they do not form a triangle of area
$1$ or $1/2$.

By way of contradiction, suppose first that $x$, $y$ and $z$ are collinear and
consecutive. In particular this means that, without loss of generality,
$x+y=2z$. Since $(1,0)$, $(0,1)$, and $(-1,-1)$ do not satisfy this relation
in any permutation, $x$, $y$, and $z$ cannot all be distinct mod
$6\mathbb{Z}^{2}$. But if, say, $x$ and $y$ are equal mod $6\mathbb{Z}^{2}$,
there are at least $5$ lattice points on the line between them; only one of
these could be $z$ and hence $x$, $y$, and $z$ are not consecutive.

Suppose instead that $x$, $y$, and $z$ are vertices of a triangle. The area of
that triangle is, up to sign, half the determinant of the matrix with columns
$y-x$ and $z-x$. Thus, we need to show that this determinant is never $\pm 1$
or $\pm 2$. If any two points are equal mod $6\mathbb{Z}^{2}$ then this
determinant is divisible by $6$. Otherwise, modulo $6$, this determinant (up
to sign) is

$\det\begin{bmatrix}2&1\\\ 1&2\end{bmatrix}=3\pmod{6}.$

Thus the determinant is not $\pm 1$ or $\pm 2$, so $x$, $y$, and $z$ are not
contained together in any border triangle. ∎

##  4 I-stable Sets

We start our analysis of I-stable sets by giving a construction which achieves
upper density 1/2.

######  Construction 4.1.

For $n\geq 1$, let $I_{n}\mathrel{\coloneqq}\mathbb{Z}\times(n\mathbb{Z})$.
See Figure 5 for $I_{2}$.

Figure 5: The I-stable set $I_{2}$ from Construction 4.1.

######  Lemma 4.2.

If $n\neq 1,3$, then every internal triangle intersects $I_{n}$ in at most two
points.

###### Proof.

From Pick’s theorem, it is easy to see that every three points of an internal
triangle have a convex hull of area $1/2$ or $3/2$. We also recall that the
area of the convex hull of $(0,0)$, $(a,b)$ and $(c,d)$ is

$\frac{1}{2}\begin{vmatrix}a&b\\\ c&d\end{vmatrix}=\frac{ad-bc}{2}.$

Thus the area of the convex hull of any three points of $I_{n}$ is an integral
multiple of $\frac{n}{2}$. Since $n\neq 1,3$, we conclude that no internal
triangle intersects three points of $I_{n}$. ∎

Since every subset of $I_{n}$ also intersects every internal triangle in at
most two points, we conclude that every subset of $I_{n}$ is I-stable, which
gives the following corollary.

######  Corollary 4.3.

For every $\delta\leq 1/2$, there exists an I-stable set $I$ with
$\overline{\delta}(I)=\delta$.

We now work towards proving that every I-stable set has density at most $1/2$.
The analogue of Proposition 3.1 for I-stable sets does not hold, and in
particular there exist I-stable sets that contain a unimodular triangle.
However, these sets turn out to be highly structured. For this we need the
following constructions.

######  Construction 4.4.

Let
$J_{1/4}^{*}\mathrel{\coloneqq}\left\\{(0,0),(1,0),(0,1),(-1,-1)\right\\}$.
Define $J_{1/4}\mathrel{\coloneqq}J_{1/4}^{*}+4\mathbb{Z}^{2}$ and
$J_{1/2}\mathrel{\coloneqq}J_{1/4}\cup(J_{1/4}+(2,2))$. See Figure 6.

$J_{1/4}$

$J_{1/2}$

Figure 6: The sets $J_{1/4}$ and $J_{1/2}$ from Construction 4.4.

We will see below that $J_{1/4}$ and $J_{1/2}$ are I-stable. Indeed, we show
that every I-stable set that contains a unimodular triangle must contain some
unimodular transformation of $J_{1/4}$; containing any other point in addition
to $J_{1/4}$ forces the containment of a unimodular transformation of
$J_{1/2}$; and containing any other point in addition to $J_{1/2}$ forces the
I-stable set to be the entire grid $\mathbb{Z}^{2}$.

######  Lemma 4.5.

Let $S$ be an I-stable set containing $\left\\{(0,0),(0,1),(1,0)\right\\}$.
Then $J_{1/4}\subseteq S$.

###### Proof.

Let $S$ be the intersection of all I-stable sets that contain
$\left\\{(0,0),(0,1),(1,0)\right\\}$. Since an intersection of I-stable sets
is I-stable, $S$ is an I-stable set, and so $S$ is minimal under inclusion
among the I-stable sets containing $\left\\{(0,0),(0,1),(1,0)\right\\}$. Note
that $(-1,-1)\in S$ since $S$ contains the other three points of the internal
triangle $J_{1/4}^{*}$, so $J_{1/4}^{*}\subseteq S$.

By the minimality of $S$, if a unimodular map $U$ fixes $J_{1/4}^{*}$, then
$U$ also fixes $S$. Note that the unimodular maps

$x\mapsto\begin{bmatrix}[r]0&-1\\\ 1&-1\end{bmatrix}x\quad\text{ and }\quad
x\mapsto\begin{bmatrix}[r]-1&1\\\ -1&0\end{bmatrix}x$

fix $J_{1/4}^{*}$ and map $J_{1/4}^{*}+(4,0)$ to $J_{1/4}^{*}+(0,4)$ and
$J_{1/4}^{*}+(-4,-4)$, respectively. Thus if we show that $S$ contains
$J_{1/4}^{*}+(4,0)$, then $S$ must contain $J_{1/4}^{*}+(0,4)$ and
$J_{1/4}^{*}+(-4,-4)$. By similar reasoning, $S$ must contain
$J_{1/4}^{*}+(0,4)+(-4,-4)=J_{1/4}^{*}+(-4,0)$ and
$J_{1/4}^{*}+(4,0)+(-4,-4)=J_{1/4}^{*}+(0,-4)$, and thus $S$ contains
$J_{1/4}$.

The following inferences demonstrate that $S$ contains $J_{1/4}^{*}+(4,0)$
(see Figure 7):

$\displaystyle(0,0),\,(1,0),\,(0,1)\in S$
$\displaystyle\qquad\Longrightarrow\qquad(-1,-1)\in S,$
$\displaystyle(0,0),\,(1,0),\,(0,1)\in S$
$\displaystyle\qquad\Longrightarrow\qquad(3,-1),\,(-1,3)\in S,$
$\displaystyle(0,0),\,(1,0),\,(-1,-1)\in S$
$\displaystyle\qquad\Longrightarrow\qquad(4,1)\in S,$
$\displaystyle(0,0),\,(0,1),\,(-1,3)\in S$
$\displaystyle\qquad\Longrightarrow\qquad(1,-4)\in S,$
$\displaystyle(1,-4),\,(3,-1),\,(4,1)\in S$
$\displaystyle\qquad\Longrightarrow\qquad(4,0)\in S,$
$\displaystyle(3,-1),\,(4,1),\,(4,0)\in S$
$\displaystyle\qquad\Longrightarrow\qquad(5,0)\in S.\qed$

0001223456 Figure 7: An I-stable set $S$ containing
$\left\\{(0,0),(0,1),(1,0)\right\\}$ (in red) must contain $J_{1/4}^{*}$ and
$J_{1/4}^{*}+(4,0)$. The points are labeled according to the order in which
their membership in $S$ is demonstrated in the proof of Lemma 4.5.

The preceding lemma already shows that any I-stable set containing a
unimodular triangle contains a unimodular transformation of $J_{1/4}$, since
any unimodular triangle is the image of $\left\\{(0,0),(0,1),(1,0)\right\\}$
under some unimodular transformation. The following lemma with $J_{1/2}$
appears more modest, but see 4.10 for the analogous conclusion.

######  Lemma 4.6.

Let $S$ be an I-stable set containing
$\left\\{(0,0),(0,1),(1,0),(1,1)\right\\}$. Then $J_{1/2}\subseteq X$.

###### Proof.

We immediately have that $J_{1/4}\subseteq S$ by Lemma 4.5. In addition,
$J_{1/4}^{*}+(2,2)\subseteq S$ because

$\displaystyle(0,0),\,(1,0),\,(1,1)\in S$
$\displaystyle\qquad\Longrightarrow\qquad(2,3)\in S,$
$\displaystyle(0,0),\,(0,1),\,(1,1)\in S$
$\displaystyle\qquad\Longrightarrow\qquad(3,2)\in S,$
$\displaystyle(1,0),\,(0,1),\,(1,1)\in S$
$\displaystyle\qquad\Longrightarrow\qquad(2,2)\in S.$

Thus, again by Lemma 4.5, we have that
$J_{1/4}+(2,2)=J_{1/4}^{*}+(2,2)+4\mathbb{Z}^{2}\subseteq S$. ∎

We prove below that $J_{1/4}$ and $J_{1/2}$ are in fact I-stable. The case
analyses in these proofs will make frequent use of the following elementary
lemma. Given vectors $a,b\in\mathbb{Z}^{2}$, we write $\det(a,b)$ for the
determinant of the $2\times 2$ matrix with first column $a$ and second $b$.

######  Lemma 4.7.

Let $\left\\{a,b,c,d\right\\}\subseteq\mathbb{Z}^{2}$ be an internal triangle,
and let $a_{0}\equiv a$, $b_{0}\equiv b$, $c_{0}\equiv c$, and $d_{0}\equiv
d$, modulo $4\mathbb{Z}^{2}$. Then $a_{0}+b_{0}+c_{0}+d_{0}\equiv 0\mod
4\mathbb{Z}^{2}$ and $\det(b_{0}-a_{0},c_{0}-a_{0})\equiv\pm 1\mod 4$.

Note that the points $a_{0},b_{0},c_{0},d_{0}$ in 4.7 are not necessarily
uniformly translated copies of $a,b,c,d$, so they may no longer form a minimal
triangle.

###### Proof of 4.7.

Let $T\mathrel{\coloneqq}\left\\{a,b,c,d\right\\}$. It is not difficult to
show that for any internal triangle, the lattice points that it contains are
its centroid (i.e., arithmetic mean) and its vertices. If, without loss of
generality, $a$ is the centroid of $T$, then $3a=b+c+d$, and so
$a_{0}+b_{0}+c_{0}+d_{0}\equiv a+b+c+d\equiv 0\mod 4\mathbb{Z}^{2}$.

To prove the second claim, note that, modulo $4$,
$\det(b_{0}-a_{0},c_{0}-a_{0})\equiv\det(b-a,c-a)\in\left\\{\pm 1,\pm
3\right\\}$ since if $a,b,c$ form a unimodular triangle, then the determinant
is $\pm 1$, and otherwise, $a,b,c$ are the vertices of $T$ so the determinant
is $\pm 3$. ∎

We now prove that $J_{1/4}$ and $J_{1/2}$ are stable.

######  Proposition 4.8.

The set $J_{1/4}$ is I-stable with $\overline{\delta}(J_{1/4})=1/4$.

###### Proof.

Let $T$ be an internal triangle that intersects $J_{1/4}$ in at least three
points $a$, $b$, and $c$. We show that the fourth point $d$ of $T$ is in
$J_{1/4}$.

By construction, the points $a,b,c$ are respectively congruent modulo
$4\mathbb{Z}^{2}$ to points $a_{0},b_{0},c_{0}$ in $J_{1/4}^{*}$. By 4.7, the
points $a_{0},b_{0},c_{0}$ are pairwise distinct and $d$ is congruent to a
point $d_{0}$ in $[-1,2]^{2}$ that satisfies the congruence
$a_{0}+b_{0}+c_{0}+d_{0}\equiv 0\mod 4\mathbb{Z}^{2}$. By checking each of the
four subsets of $J_{1/4}^{*}$ that may equal
$\left\\{a_{0},b_{0},c_{0}\right\\}$, one finds in each case that this
congruence forces $d_{0}\in J_{1/4}^{*}$, and so $d\in J_{1/4}$, as desired.

That $\overline{\delta}(J_{1/4})=1/4$ follows from the fact that $J_{1/4}$
contains $4$ of the $16$ points in the window $[-1,2]^{2}$. ∎

######  Proposition 4.9.

The set $J_{1/2}$ is I-stable with $\overline{\delta}(J_{1/2})=1/2$.

###### Proof.

Let $T$ be an internal triangle that intersects $J_{1/2}$ in at least three
points $a$, $b$, and $c$, and let $d$ be the fourth point of $T$. Let
$a_{0},b_{0},c_{0},d_{0}$ be the points in $[-1,2]^{2}$ that are congruent to
$a,b,c,d$, respectively, modulo $4\mathbb{Z}^{2}$.

By rotating $T$ by 90 degrees about the rational point
$(\frac{1}{2},\frac{1}{2})$ some integer number of times, and then adding the
vector $(2,2)$ if necessary, we may assume without loss of generality that
$a_{0}=(0,0)$. If $b_{0},c_{0}\in[-1,2]^{2}\cap J_{1/4}$, then the claim
follows from Proposition 4.8, so assume without loss of generality that
$c_{0}\in[-1,2]^{2}\cap J_{1/2}\setminus J_{1/4}$; see Figure 8.

Figure 8: Blue circles indicate the points in $[-1,2]^{2}\cap J_{1/4}$. Green
squares indicate the points in $[-1,2]^{2}\cap J_{1/2}\setminus J_{1/4}$.

If $b_{0}\in[-1,2]^{2}\cap J_{1/4}$, then, after reflecting about the line
$x=y$ if necessary, we have that $b_{0}\in\left\\{(1,0),(-1,-1)\right\\}$. If
$b_{0}=(1,0)$, then the condition that $\det(b_{0},c_{0})\equiv\pm 1\mod 4$
forces $c_{0}\in\left\\{(2,-1),(1,1)\right\\}$, while if $b_{0}=(-1,-1)$, then
(after reflecting about the line $x=y$ if necessary), we likewise have that
$c_{0}=(2,-1)$.

On the other hand, if $b_{0}\in[-1,2]^{2}\cap J_{1/2}\setminus J_{1/4}$, then,
up to reflection about the line $x=y$, we have that
$b_{0}\in\left\\{(1,1),(2,2),(2,-1)\right\\}$. However, $b_{0}=(2,2)$ is
impossible because no value of $c_{0}\in[-1,2]^{2}\cap J_{1/2}\setminus
J_{1/4}$ satisfies $\det((2,2),c_{0})\equiv\pm 1\mod 4$, so in fact
$b_{0}\in\left\\{(1,1),(2,-1)\right\\}$ in this case. If $b_{0}=(1,1)$, then,
up to reflection about the line $x=y$, $c_{0}=(2,-1)$, while if
$b_{0}=(2,-1)$, then $c_{0}\in\left\\{(1,1),(-1,2)\right\\}$.

In summary, the following table gives the possible values of $b_{0},c_{0}$
that we must consider, together with the corresponding values of $d_{0}$
forced by the condition that $a_{0}+b_{0}+c_{0}+d_{0}\equiv 0\mod
4\mathbb{Z}^{2}$.

$\begin{array}[]{lll}b_{0}&c_{0}&d_{0}\\\ \hline\cr(1,0)&(2,-1)&(1,1)\\\
(1,0)&(1,1)&(2,-1)\\\ (-1,-1)&(2,-1)&(-1,2)\\\ (1,1)&(2,-1)&(1,0)\\\
(2,-1)&(1,1)&(1,0)\\\ (2,-1)&(-1,2)&(-1,-1)\end{array}$

In each case, we find that $d_{0}\in[-1,2]^{2}\cap J_{1/2}$, so that $d\in
J_{1/2}$, as required.

That $\overline{\delta}(J_{1/2})=1/2$ follows from the fact that $J_{1/2}$
contains $8$ of the $16$ points in the window $[-1,2]^{2}$. ∎

As an aside, this last result implies that there are two very different
I-stable sets $S$ with $\overline{\delta}(S)=1/2$, namely $J_{1/2}$ and
$I_{2}$. This is quite far from the situation for B-stable and BI-stable sets,
where the only stable sets that we know of which achieve the maximum value
$\overline{\delta}(S)=1/4$ are subsets of $2\mathbb{Z}^{2}$ (see 6.1).

Combining all of these results gives the following.

######  Corollary 4.10.

Let $S$ be an I-stable set.

  1. (a)

If $S$ contains a unimodular triangle, then $S$ contains a unimodular
transformation of $J_{1/4}$.

  2. (b)

If $S$ properly contains $J_{1/4}$, then $S$ contains a unimodular
transformation of $J_{1/2}$.

  3. (c)

If $S$ properly contains $J_{1/2}$, then $S=\mathbb{Z}^{2}$.

In particular, the only I-stable sets which contain a unimodular triangle are
unimodular transformations of $J_{1/4}$, unimodular transformations of
$J_{1/2}$, and $\mathbb{Z}^{2}$.

###### Proof.

Observe that $J_{1/4}$ and $J_{1/2}$ are I-stable by Propositions 4.8 and 4.9,
respectively. By Lemma 4.5, any I-stable set containing a unimodular triangle
contains a unimodular transformation of $J_{1/4}$.

We show that if $S$ is an I-stable set containing both $J_{1/4}$ and also a
point not in $J_{1/4}$, then $S$ contains a unimodular transformation of
$J_{1/2}$. Up to translation and reflection, we may assume that $S$ contains
some $(x,y)$ with $0\leq x\leq y\leq 3$ not in $J_{1/4}$, so there are 7
points to consider. We split these into three cases (see Figure 9).

Figure 9: Adding a yellow diamond point to the top left picture will generate
all yellow diamond points, given in the bottom left picture, and so on for
each color/shape. Thus, the only I-stable proper supersets of $J_{1/4}$ are
the three in the second row, which are unimodular transformations of
$J_{1/2}$.

Case I: $S$ contains $(1,3)$. If $(1,3)\in S$, then $S$ contains
$\\{(0,4),(1,3),(0,5),(1,4)\\}$, which is the image of
$\\{(0,0),(1,0),(0,1),(1,1)\\}$ under a unimodular transformation. This is the
bottom left picture in Figure 9.

Case II: $S$ contains $(1,2)$, $(0,2)$ or $(0,3)$. If $(1,2)\in S$, then since
$(0,1),(3,3)\in S$, we have $(0,2)\in S$. If $(0,2)\in S$, then since
$(1,0),(-1,3)\in S$, we have $(0,3)\in S$. If $(0,3)\in S$, then $S$ contains
$\\{(-1,3),(0,3),(0,4),(1,4)\\}$, which is the image of
$\\{(0,0),(1,0),(0,1),(1,1)\\}$ under a unimodular transformation. This is the
bottom middle picture in Figure 9.

Case III: $S$ contains $(2,3)$, $(2,2)$, or $(1,1)$. If $(2,3)\in S$, then
since $(0,1),(3,3)\in S$, we have $(2,2)\in S$. If $(2,2)\in S$, then since
$(0,1),(1,0)\in S$, we have $(1,1)\in S$. If $(1,1)\in S$, then $S$ contains
$\\{(0,0),(1,0),(0,1),(1,1)\\}$. This is the bottom right picture in Figure 9.

In any of these cases, $S$ must contain a unimodular transformation of
$J_{1/2}$ by 4.6.

Finally, we show that if $S$ is an I-stable set containing $J_{1/2}$ and also
some point not in $J_{1/2}$, then $S=\mathbb{Z}^{2}$. Up to translation and
rotation, we may assume that $(2,0)\in S$. Then

$\displaystyle(1,0),\,(2,-1),\,(2,0)\in S$
$\displaystyle\qquad\Longrightarrow\qquad(3,1)\in S,$
$\displaystyle(1,0),\,(2,2),\,(3,1)\in S$
$\displaystyle\qquad\Longrightarrow\qquad(2,1)\in S,$
$\displaystyle(2,-1),\,(4,0),\,(3,1)\in S$
$\displaystyle\qquad\Longrightarrow\qquad(3,0)\in S.$

Thus, since $S$ contains $\\{(2,0),(3,0),(2,1),(3,1)\\}$, we have that $S$
contains $J_{1/2}+(2,0)=\mathbb{Z}^{2}\setminus J_{1/2}$. We conclude that
$S=\mathbb{Z}^{2}$ by 4.6. ∎

We summarize these structural observations in the following corollary.

######  Corollary 4.11.

A set $S\subsetneq\mathbb{Z}^{2}$ is I-stable if and only if we have one of
the following:

  1. (a)

$S$ is a unimodular transformation of $J_{1/4}$;

  2. (b)

$S$ is a unimodular transformation of $J_{1/2}$;

  3. (c)

$S$ contains at most 2 points from every internal triangle.

###### Proof.

By Proposition 4.8 and Proposition 4.9, $S$ is I-stable in cases (a) and (b);
case (c) is immediate.

Conversely, if $S\subsetneq\mathbb{Z}^{2}$ is I-stable and contains at least 3
points from an internal triangle, then $S$ contains an internal triangle, and
thereby contains a unimodular triangle. By 4.10, $S$ is a unimodular
transformation of $J_{1/4}$ or $J_{1/2}$. ∎

We now prove our main density result for this section, which together with 4.3
completes the proof of 1.1(b). (We recall that (a) was proven in Section 3.)

######  Proposition 4.12.

If $S\subsetneq\mathbb{Z}^{2}$ is I-stable, then $\overline{\delta}(S)\leq
1/2$.

###### Proof.

By 4.10, if $S$ contains a unimodular triangle then it is a unimodular
transformation of $J_{1/4}$, $J_{1/2}$, or $\mathbb{Z}^{2}$; since
$S\neq\mathbb{Z}^{2}$, we have $\overline{\delta}(S)\leq 1/2$. If $S$ does not
contain a unimodular triangle, then $S$ intersects every $2\times 2$ square in
at most $2$ points. Tiling $\mathbb{Z}^{2}$ by $2\times 2$ squares, we have
$\overline{\delta}(S)\leq 1/2$. ∎

##  5 Maximal Stable sets

Up to this point we have established a number of structural results about
stable sets. 3.2 states that every subset of a B-stable set
$S\subsetneq\mathbb{Z}^{2}$ is B-stable and every subset of a BI-stable set
$S\subseteq\mathbb{Z}^{2}$ is BI-stable. Similarly, from 4.11, every subset of
an I-stable set $S$ is I-stable, unless $S$ is a unimodular transformation of
$J_{1/4}$, $J_{1/2}$, or $\mathbb{Z}^{2}$ (see Figure 9). In view of this,
classifying all stable sets is equivalent to classifying all maximal stable
sets, that is, stable sets $S\subsetneq\mathbb{Z}^{2}$ such that $S$ and
$\mathbb{Z}^{2}$ are the only stable sets containing $S$. In this section we
consider some constructions that are maximal stable and give some
nonconstructive existence results.

We begin with I-stable sets. We recall that
$I_{n}\coloneqq\mathbb{Z}\times(n\mathbb{Z})$ is I-stable for every $n\neq
1,3$ by 4.2.

######  Proposition 5.1.

Let $I_{n}\coloneqq\mathbb{Z}\times(n\mathbb{Z})$. Then $I_{n}$ is maximal
I-stable if and only if either $n=9$ or $n$ is a prime number other than $3$.

###### Proof.

If $n\geq 2$ is composite and not $9$, then we can write $n=pq$ with $p\neq
1,3$ and $q>1$. As $I_{pq}\subseteq I_{p}$, we have that $I_{n}$ is not a
maximal I-stable set in this case. Also, $I_{3}$ is not I-stable (see Figure
11). It suffices to prove then that $I_{n}$ is maximal I-stable for prime
$n\neq 3$ and for $n=9$.

Consider the set $X$ consisting of $I_{n}$ with an extra added point, which we
may assume to be of the form $(0,a)$ with $1\leq a\leq n-1$ without loss of
generality. We claim that the only I-stable set containing $X$ is
$\mathbb{Z}^{2}$. Let us first assume $n\neq 3$ is a prime number. Since
$\gcd(a,p)=1$, there are integers $t_{1},t_{2}>0$ such that $pt_{1}-at_{2}=1$.
Hence, the area of the triangle with vertices
$(t_{1},0),(t_{1}-t_{2},p),(0,a)$ is

$\frac{1}{2}\det\begin{bmatrix}-t_{2}&p\\\
-t_{1}&a\end{bmatrix}=\frac{pt_{1}-at_{2}}{2}=\frac{1}{2},$

which implies that $\left\\{(t_{1},0),(t_{1}-t_{2},p),(0,a)\right\\}$ is a
unimodular triangle with all vertices in $X$ (see Figure 10). Because $n$ is
prime and thus not divisible by $4$, every unimodular transformation of
$J_{1/4}$ and $J_{1/2}$ fails to contain $I_{n}$ (see Figure 9 for the only
unimodular transformation of $J_{1/4}$ and the two unimodular transformations
of $J_{1/2}$ up to rotation and translation), we conclude by 4.10 that the
only I-stable set containing X is $\mathbb{Z}^{2}$.

Let us now assume $n=9$. The previous argument yields the desired result
whenever the additional point $(0,a)$ has $\gcd(a,9)=1$. If $a\in\\{3,6\\}$,
$X$ contains 3 points of an internal triangle, which forces a unimodular
triangle (see Figure 11), and we can conclude this case as before. ∎

Figure 10: The sets $I_{7}\cup\\{(0,4)\\}$ and $I_{5}\cup\\{(0,2)\\}$ contain
a unimodular triangle.

Figure 11: $I_{9}$ is maximal I-stable, but $I_{3}$ is not I-stable. The
addition of the red pentagonal points to $I_{9}$ either creates a unimodular
triangle or the three vertices of an internal triangle, which forces a
unimodular triangle.

We recall
$S_{2/9}\mathrel{\coloneqq}\left\\{(0,0),(1,0)\right\\}+3\mathbb{Z}^{2}$ from
Construction 2.3.

######  Proposition 5.2.

The set $S_{2/9}$ is maximal B-stable, maximal I-stable, and maximal BI-
stable.

###### Proof.

By Proposition 2.4, we know that $S_{2/9}$ is BI-stable. Let $X$ be the set
obtained after adding one extra point to $S_{2/9}$. Then either $X$ contains a
unimodular triangle or has 5 points in a row. By Proposition 3.1, the only
B-stable set containing $X$ is $\mathbb{Z}^{2}$. Therefore, $S_{2/9}$ is
maximal B-stable and maximal BI-stable.

Furthermore, every I-stable set containing $X$ also contains a unimodular
triangle (see Figure 12). As every unimodular transformation of $J_{1/4}$ and
$J_{1/2}$ fails to contain the set $S_{2/9}$ (see Figure 9 for the only
unimodular transformation of $J_{1/4}$ and the two unimodular transformations
of $J_{1/2}$ up to rotation and translation), we conclude by 4.10 that the
only I-stable set containing $X$ is $\mathbb{Z}^{2}$. ∎

Figure 12: The set $S_{2/9}$ is a maximal I-stable set. The addition of the
yellow diamond point creates a unimodular triangle, and the addition of the
red pentagonal point forces such a yellow diamond point.

All of the constructions we considered in this paper are periodic, i.e. of the
form $X+k\mathbb{Z}^{2}$ for some finite set $X$ and positive integer $k$.
Although we have not explicitly constructed a (maximal) aperiodic stable set,
it follows from Zorn’s Lemma that such sets must exist as well. For this, we
need a simple lemma.

######  Proposition 5.3.

Let $S\subsetneq\mathbb{Z}^{2}$ be B/I/BI-stable. Then there exists a maximal
B/I/BI-stable set (of the same stability type as $S$) that contains $S$.

###### Proof.

We give the proof for I-stable sets. The reasoning is nearly identical for
B-stable and BI-stable sets.

Let $\Sigma$ be the collection of all I-stable proper subsets of
$\mathbb{Z}^{2}$ containing $S$. Then $\Sigma$ is nonempty since $S\in\Sigma$.
Let $\mathcal{C}\subseteq\Sigma$ be a chain with respect to inclusion, and let
$\overline{S}=\bigcup_{T\in\mathcal{C}}T$.

We claim that $\overline{S}$ is I-stable. Suppose it is not. Then there exist
four distinct points $x_{1},x_{2},x_{3},y\in\mathbb{Z}^{2}$ forming an
internal triangle, with $x_{1},x_{2},x_{3}\in\overline{S}$ and
$y\notin\overline{S}$. For each $i=1,2,3$, let $T_{i}\in\mathcal{C}$ contain
$x_{i}$. Since $\mathcal{C}$ is a chain, we may assume $T_{1}\subseteq
T_{2}\subseteq T_{3}$ without loss of generality, which means that
$x_{1},x_{2},x_{3}\in T_{3}$. But $y$ cannot be in $T_{3}$ since
$y\notin\overline{S}$, contradicting I-stability of $T_{3}$.

Next, we show that $\overline{S}$ is a proper subset of $\mathbb{Z}^{2}$. If
not, then by the same reasoning as in the previous paragraph, some
$T\in\mathcal{C}$ must contain every point in $[4]^{2}$. Since $T$ is
I-stable, we have that $T=\mathbb{Z}^{2}$ by 4.11 (or Proposition 3.1 for
B-stable and BI-stable sets), contradicting that $T$ is a proper subset of
$\mathbb{Z}^{2}$.

Thus, $\overline{S}\in\Sigma$ is an upper bound of $\mathcal{C}$. By Zorn’s
lemma, $\Sigma$ contains a maximal element. ∎

Now we can now give a nonconstructive proof that there exist maximal aperiodic
stable sets.

######  Proposition 5.4.

There exists a maximal I-stable set $S\subseteq\mathbb{Z}^{2}$ that is not
periodic.

###### Proof.

Let $S_{0}=\\{(x,0)\,:\,x\geq 10\\}\cup\\{(0,y)\,:\,y\geq 10\\}$. The set
$S_{0}$ is I-stable since any triangle with vertices in $S_{0}$ has area at
least $5$. By Proposition 5.3, $S_{0}$ is contained in a maximal I-stable set
$S$. Suppose that $S$ is periodic. Then the intersection of $S$ with the
$x$-axis $\left\\{(x,0)\,:\,x\in\mathbb{Z}\right\\}$ is periodic. Since the
infinite ray $\left\\{(x,0)\,:\,x\in\mathbb{Z},\,x\geq 10\right\\}$ is in this
periodic intersection, all of $\left\\{(x,0)\,:\,x\in\mathbb{Z}\right\\}$ is
in $S$. Likewise, $S$ contains the entire $y$-axis
$\left\\{(0,y)\,:\,y\in\mathbb{Z}\right\\}$. Thus, $S$ contains the three
points $(0,0),(-1,0),(0,-1)$ and hence, by I-stability, $(1,1)\in S$. Now
$\\{(0,0),(1,0),(0,1),(1,1)\\}\subseteq S$, so by 4.6, $S$ contains $J_{1/2}$.
But $J_{1/2}$ is maximal I-stable by 4.10 and does not contain the set
$\\{(x,0):x\in\mathbb{Z}\\}\cup\\{(0,y):y\in\mathbb{Z}\\}\subseteq S$, which
is a contradiction. Thus $S$ is an aperiodic maximal I-stable set. ∎

######  Proposition 5.5.

There exists a maximal B-stable set $S\subseteq\mathbb{Z}^{2}$ that is not
periodic. There also exists a maximal BI-stable set $S\subseteq\mathbb{Z}^{2}$
that is not periodic.

###### Proof.

Let $X\subseteq\mathbb{Z}$ be any set of integers satisfying the following
conditions:

  1. (1)

$X$ contains no three consecutive integers,

  2. (2)

$X\cup\\{x\\}$ contains three consecutive integers for all
$x\in\mathbb{Z}\setminus X$, and

  3. (3)

$X$ is not periodic.

Such a set can be constructed as follows. Let $0.b_{1}b_{2}\cdots$ be the
binary expansion of any irrational number in $(0,1)$. Define
$x_{0}\mathrel{\coloneqq}1$ and iteratively
$x_{i+1}\mathrel{\coloneqq}x_{i}+2+b_{i}$. Take
$X^{\prime}\mathrel{\coloneqq}\\{x_{i}\\}_{i\geq
0}\cup\\{x_{i}+1\\}_{i\,:\,b_{i}=1}$ and set
$X\mathrel{\coloneqq}X^{\prime}\cup(-X^{\prime})$. It is straightforward to
check that this set has the desired properties.

Let $S_{0}\mathrel{\coloneqq}X\times\\{0\\}\subseteq\mathbb{Z}^{2}$. By
Condition (1), $S_{0}$ intersects each border triangle in at most two points,
so it is a B-stable proper subset of $\mathbb{Z}^{2}$. By Proposition 5.3,
there exists some $S\supseteq S_{0}$ that is maximal B-stable. Observe that
$S\cap(\mathbb{Z}\times\\{0\\})=X$, as otherwise $S$ would contain three
consecutive integers by Condition (2), which by Proposition 3.1 would imply
$S=\mathbb{Z}^{2}$. Finally, $S$ is not periodic because $X$ is not periodic
by Condition (3).

For a maximal BI-stable set, we apply Proposition 5.3 to obtain $S\supseteq
S_{0}$ that is maximal BI-stable, and the rest of the argument is unchanged. ∎

##  6 Concluding Remarks and Maximal Stable Sets

In this paper we defined $S\subseteq\mathbb{Z}^{2}$ to be B/I/BI-stable if
there exists no border/internal/minimal triangle (respectively) on four points
that intersects $S$ in exactly three points. There are many ways one could
generalize these notions. When considering the number-theoretic motivation,
work in $\mathbb{Z}^{2}$ is related to degree-$3$ number fields. To handle
higher-degree fields, it is natural to consider a notion of stability with
respect to minimal simplices in $\mathbb{Z}^{d}$. However, the classification
of simplices in $\mathbb{Z}^{d}$ containing $d+2$ points is considerably more
complicated when $d\geq 3$ than when $d=2$. For example, there exist
infinitely many tetrahedra in $\mathbb{Z}^{3}$, not equivalent up to
unimodular transformation, containing exactly five points, including eight
tetrahedra containing one interior point [10, Table 1].

As discussed in Section 5, understanding stable sets is equivalent to
understanding maximal stable sets. As such, many of our open problems center
around such sets. For example, we showed that any B-stable set
$S\subsetneq\mathbb{Z}^{2}$ has $\overline{\delta}(S)\leq 1/4$, and that this
is tight by considering $S=2\mathbb{Z}^{2}$. The following asks if this is
essentially the only such set with this property.

######  Question 6.1.

Does there exist a set $S\subsetneq\mathbb{Z}^{2}$ that is maximal B-stable
with $\overline{\delta}(S)=1/4$ and that is not equal to a unimodular
transformation of $2\mathbb{Z}^{2}$?

A negative answer to this question would also imply a negative answer to the
analogous question for BI-stable sets. Here the condition that $S$ be maximal
is essential, as otherwise one can just consider $2\mathbb{Z}^{2}$ after
deleting a point. A related question is the following.

######  Question 6.2.

What is the largest value of $\overline{\delta}(S)$ for B-stable
$S\subsetneq\mathbb{Z}^{2}$ if $S$ contains $(0,0)$ and $(1,0)$?

The set $S_{2/9}$ shows that $\overline{\delta}(S)=2/9$ is achievable, and
Proposition 3.5 implies $\overline{\delta}(S)\leq 1/4$. If this latter bound
were tight, then this would imply a positive answer to 6.1, and any proof
showing $\overline{\delta}(S)=1/4$ is not possible might give insight into
proving that 6.1 has a negative answer.

It would be interesting if one could construct a stable set $S$ with positive
density that is not periodic.

######  Question 6.3.

Does there exist an aperiodic set $S\subseteq\mathbb{Z}^{2}$ with
$\overline{\delta}(S)>0$ that is maximal B/I/BI-stable?

We note that if either $\overline{\delta}(S)=0$ or $S$ is periodic, then
$\overline{\delta}(\varphi(S))=\overline{\delta}(S)$ for any unimodular
transformation $\varphi$. As such, a negative answer to this question would
imply that $\overline{\delta}(S)$ is an “intrinsically geometric” property of
maximal stable sets. The maximality condition in 6.3 is critical, as
$2\mathbb{Z}^{2}$ minus a point trivially satisfies all of the other
conditions. Similarly, Propositions 5.4 and 5.5 show that we can find such
sets if one drops the requirement $\overline{\delta}(S)>0$.

##  7 Acknowledgements

This work was started at the 2022 Graduate Research Workshop in Combinatorics,
which was supported in part by NSF grant 1953985 and a generous award from the
Combinatorics Foundation. We thank the referees for their careful reading and
useful comments that improved the presentation of this manuscript.

## References

  * [1] M. Aizenman and J. Lebowitz.  Metastability effects in bootstrap percolation.  Journal of Physics A: Mathematical and General, 21(19):3801, Oct. 1988.  doi:10.1088/0305-4470/21/19/017.
  * [2] P. Balister, B. Bollobás, J. Lee, and B. Narayanan.  Line percolation.  Random Structures & Algorithms, 52(4):597–616, 2018.  doi:10.1002/rsa.20755.
  * [3] P. Balister, B. Bollobás, R. Morris, and P. Smith.  The critical length for growing a droplet, Aug. 2023.  arXiv:2203.13808, doi:10.1090/S0002-9947-2011-05552-2.
  * [4] P. Balister, B. Bollobás, R. Morris, and P. Smith.  Subcritical monotone cellular automata.  Random Structures & Algorithms, In press, 2023.  doi:https://doi.org/10.1002/rsa.21174.
  * [5] P. Balister, B. Bollobás, M. l. Przykucki, and P. Smith.  Subcritical $\mathcal{U}$-bootstrap percolation models have non-trivial phase transitions.  Transations of the American Mathematical Society, 368(10):7385–7411, 2016.  doi:10.1090/tran/6586.
  * [6] J. Balogh and B. Bollobás.  Sharp thresholds in bootstrap percolation.  Physica A: Statistical Mechanics and its Applications, 326(3):305–312, 2003.  doi:10.1016/S0378-4371(03)00364-9.
  * [7] J. Balogh, B. Bollobás, H. Duminil-Copin, and R. Morris.  The sharp threshold for bootstrap percolation in all dimensions.  Transactions of the American Mathematical Society, 364(5):2667–2701, 2012.
  * [8] J. Balogh, B. Bollobás, R. Morris, and O. Riordan.  Linear algebra and bootstrap percolation.  Journal of Combinatorial Theory, Series A, 119(6):1328–1335, 2012\.  doi:10.1016/j.jcta.2012.03.005.
  * [9] J. Balogh, Y. Peres, and G. Pete.  Bootstrap percolation on infinite trees and non-amenable groups.  Combinatorics, Probability and Computing, 15(5):715–730, 2006.  doi:10.1017/S0963548306007619.
  * [10] M. Blanco and F. Santos.  Lattice $3$-polytopes with few lattice points.  SIAM J. Discrete Math., 30(2):669–686, 2016.  doi:10.1137/15M1014450.
  * [11] V. Blomer and V. Kala.  Number fields without $n$-ary universal quadratic forms.  Math. Proc. Cambridge Philos. Soc., 159(2):239–252, 2015.  doi:10.1017/S030500411500033X.
  * [12] B. Bollobás, H. Duminil-Copin, R. Morris, and P. Smith.  Universality for two-dimensional critical cellular automata.  Proceedings of the London Mathematical Society, 126(2):620–703, 2023.  doi:10.1112/plms.12497.
  * [13] B. Bollobás, P. Smith, and A. Uzzell.  Monotone cellular automata in a random environment.  Combinatorics, Probability and Computing, 24(4):687–722, 2015.  doi:10.1017/S0963548315000012.
  * [14] H. Brunotte.  Zur Zerlegung totalpositiver Zahlen in Ordnungen totalreeller algebraischer Zahlkörper.  Arch. Math. (Basel), 41(6):502–503, 1983.  doi:10.1007/BF01198578.
  * [15] J. Chalupa, P. L. Leath, and G. R. Reich.  Bootstrap percolation on a Bethe lattice.  Journal of Physics C: Solid State Physics, 12(1):L31–L35, Jan 1979\.  doi:10.1088/0022-3719/12/1/008.
  * [16] D. Gerbner, B. Keszegh, G. Mészáros, B. Patkós, and M. Vizer.  Line percolation in finite projective planes.  SIAM Journal on Discrete Mathematics, 32(2):864–881, 2018.  doi:10.1137/16M1087709.
  * [17] J. Gravner and D. Griffeath.  Scaling laws for a class of critical cellular automaton growth rules.  In Proceedings of the Erdős Center Workshop on Random Walks, pages 167–188, 1999.
  * [18] I. Hartarsky.  $\mathcal{U}$-bootstrap percolation: Critical probability, exponential decay and applications.  Annales de l’Institut Henri Poincaré, Probabilités and Statistiques, 57(3):1255–1280, 2021.  doi:10.1214/20-AIHP1112.
  * [19] I. Hartarsky and R. Szabó.  Subcritical bootstrap percolation via Toom contours.  Electronic Communications in Probability,, In press, 2023.  doi:10.1214/22-ecp496.
  * [20] T. Hejda and V. Kala.  Additive structure of totally positive quadratic integers.  Manuscripta Math., 163(1-2):263–278, 2020.  doi:10.1007/s00229-019-01143-8.
  * [21] V. Kala and M. Tinková.  Universal quadratic forms, small norms, and traces in families of number fields.  Int. Math. Res. Not., 2022.  doi:10.1093/imrn/rnac073.
  * [22] J. Krásenský, M. Tinková, and K. Zemková.  There are no universal ternary quadratic forms over biquadratic fields.  Proc. Edinb. Math. Soc. (2), 63(3):861–912, 2020.  doi:10.1017/s001309152000022x.

##  Appendix A Computer-assisted proofs

In this appendix, we discuss the Python code for a program that proves 3.4 and
3.8, and classifies the sets considered in 3.9. This code can be found in the
supplementary files.

The code enumerates all B-stable subsets of a given set of points using a
depth-first search. First we set up some helpful functions, including the main
recursive step. Then we give the three applications. 3.4 states every B-stable
set $S\subsetneq\mathbb{Z}^{2}$ has $|S\cap([6]\times[6])|\leq 9$ and 3.9
describes all B-stable sets $S\subseteq[6]^{2}$ with $\Gamma(S)\neq\emptyset$
and $|S|=9$ up to rotation and reflection; the code completes this calculation
in only a few seconds on a personal computer. 3.8 states that every B-stable
set $S\subsetneq\mathbb{Z}^{2}$ with
$\Gamma(S)\cap([6]\times[12])\neq\emptyset$ has $|S\cap([6]\times[12])|\leq
16$; this takes longer to calculate, about 6 minutes on the same hardware.

Figure 13: All B-stable sets $S\subseteq[6]^{2}$ with $\Gamma(S)\neq\emptyset$
and $|S|=9$, up to reflection and rotation.

##  Appendix B Computer-free proof of 3.4

In this Appendix, we prove 3.4, namely that every B-stable set
$S\subsetneq\mathbb{Z}^{2}$ intersects $[6]^{2}$ in at most 9 points, without
computer aid. A proof along similar lines should be possible for 3.8, but we
do not provide one here.

First, we show that it is enough to prove the following.

######  Lemma B.1.

Let $S\subsetneq\mathbb{Z}^{2}$ be a B-stable set. If $S\cap[6]^{2}$ contains
a pair of points $(x,y)$ and $(x+1,y)$, then $|S\cap[6]^{2}|\leq 9$.

######  Lemma B.2.

If $S\subsetneq\mathbb{Z}^{2}$ is B-stable, $S\cap[6]^{2}$ has no pair of
points at distance $1$ and $S\cap[6]^{2}$ contains two points at distance
$\sqrt{2}$, then $|S\cap[6]^{2}|\leq 9$.

###### Proof of 3.4.

Assume that $S\subsetneq\mathbb{Z}^{2}$ is a B-stable set and
$|S\cap[6]^{2}|>9$. Then, by B.1 applied to $S$ and a 90-degree rotation of
$S$, we have that $S\cap[6]^{2}$ contains no pair of points at distance 1.
Thus, by B.2, $S\cap[6]^{2}$ contains no pair of points at distance
$\sqrt{2}$. This implies that every translate of $[2]\times[2]$ intersects $S$
in at most one point, contradicting the fact that $|S\cap[6]^{2}|>9$. ∎

###  B.1 Proof of B.1

Let $T=S\cap[6]^{2}$. If such $T$ contains a pair of horizontally consecutive
points in the 2nd, 3rd, 4th, or 5th rows of $[6]^{2}$, then $T$ contains at
most 8 points (see Figure 14). We may assume this is not the case, and by
symmetry that $T$ also contains no pair of vertically consecutive points in
the middle four columns.

$\leq 2$$\leq 2$$\leq 2$ Figure 14: Possible sets in which $S\cap[6]^{2}$
contains a pair of points at distance $1$ in the 2nd, 3rd, 4th, or 5th row.
Points marked with a red X cannot be included in $S$, or else $S=\mathbb{Z}$.

Now without loss of generality, the top row of $[6]^{2}$ contains a
consecutive pair from $T$. Then as we can see from Figure 15, $T$ contains at
most 4 points from row 6, no points from rows 5 and 4, and at most 6 points
total from rows 1, 2, and 3, and hence $|T|\leq 10$. Thus either $|T|\leq 9$
already, or the top row must contain exactly 4 points of $T$, and in
particular, we can assume without loss of generality that either
$(1,6),(2,6)\in T$, $(5,6),(6,6)\in T$, or $(1,6),(3,6),(4,6),(6,6)\in T$.

$\leq 2$$\leq 2$$\leq 2$$\leq 2$

$\leq 2$$\leq 2$$\leq 2$

Figure 15: Possible sets with two points at distance 1 on the 1st row of a
$6\times 6$ window.

We will break these into further cases depending on which 2 points appear in
the ‘middle $2\times 3$ window’ with coordinates $\\{3,4\\}\times\\{1,2,3\\}$,
see Figure 16 for all 15 possibilities.

Case 1Case 2Case 3Case 4Case 5Case 6Case 7Case 8Case 9Case 10Case 11Case
12Case 13Case 14Case 15 Figure 16: All possible configuration of 2 points in a
$2\times 3$ window.

From now on, we will refer to each possibility as the label included in Figure
16. By our assumption on consecutive points in middle rows and columns, we can
immediately rule out cases 1, 6, 8, 12, 13, and 15. Moreover in case 3,
regardless of the configuration in the top row, we can have at most 4 points
in the last three rows for a total of at most $8$.

The configuration $(1,6),(3,6),(4,6),(6,6)\in T$ is then relatively
straightforward. In cases 5, 9, 10, and 11, $T$ has three points of a
unimodular triangle. In cases 2, 4, 7, and 14, $T$ has three points of a
border triangle.

Finally, we handle the configuration $(1,6),(2,6)\in T$, which by symmetry,
covers the configuration $(5,6),(6,6)\in T$ as well. In cases 10 and 11, there
are three points of a unimodular triangle. In cases 2 and 7, there are three
points of a border triangle. We deal with the remaining cases of 4, 5, 9, and
14 in the following.

In cases 4, 5, and 9, we rule out new points that will create either
unimodular or border triangle with the points in $T$. A quick check shows that
$T$ has at most 9 points in these cases, as seen in the following.

$\leq 2$$\leq 2$$\leq 2$$\leq 2$

For case 14, we will need a slightly more detailed analysis. For this, we
introduce a new labeling system in pictures that will help the case checking
later on.

The points $(2,6)$ and $(4,3)$ are labeled 1 and 2 in the following figure.
They form a border triangle with the bottom-right point $(6,1)$, which forbids
$(6,1)$ from being in $T$. We notate this in the picture with a red $1,2$
label over that point. Further, the points $(4,1)$ and $(4,3)$ make it
impossible to have both points $(6,2)$ and $(6,3)$ from the ‘right $2\times 3$
window’ $\\{5,6\\}\times[3]$. We conclude that there is at most one point from
$T$ in that $2\times 3$ window. Thus we conclude that in this last case, as in
all others, $T$ has at most 9 points.

$1$$2$$1,2$$\leq 1$

###  B.2 Proof of B.2

We now assume that $S$ has no points at distance $1$ but has points at
distance $\sqrt{2}$.

Throughout this argument, in the grid $[k]^{2}$, the _main diagonal_ is the
set of $k$ lattice points $(x,y)$ for which $x-y=0$; the _main antidiagonal_
is the set of points for which $x+y=k$. Similarly, the _$d^{\text{th}}$
diagonals_ are the sets of $2(k-d)$ lattice points in $[k]$ with $x-y=\pm d$;
and the _$d^{\text{th}}$ antidiagonals_ are the ones with $x+y=k\pm d$.

We will make use of the following Claim (see Figure 17).

######  Claim B.3.

If $S$ has no points at distance 1, then an upper or lower triangular part of
the grid $[k]^{2}$ can contain at most 3 points when $k=3$, and at most 6
points when $k=5$. The only configurations achieving equality are shown in
Figure 18. Moreover, when $k=4$, if we further assume there are no points at
distance $\sqrt{2}$ on the main diagonal or antidiagonal, there are at most 3
points on such a triangular grid.

$\leq 3$$\leq 3$$\leq 6$ Figure 17: B.3: The upper or lower triangular part of
the grid $[k]^{2}$ can contain at most 3 points when $k=3,4$, and at most 6
points when $k=5$. Moreover, for $k=3$ and $k=5$, the only configurations
achieving equality are shown below. Figure 18: The “optimal” equality cases in
B.3.

###### Proof.

In each of the cases, let $[k]_{L}=\\{(x,y)\in\mathbb{Z}^{2}:1\leq y\leq x\leq
k\\}$, and $T=S\cap[k]_{L}$. The proofs for the upper triangular part are
immediate by symmetry.

For $k=3$, note that $T\cap[2]_{L}$ either contains at most one point or is
$\\{(1,1),(2,2)\\}$. Now condition on the number $t_{3}$ of points in the last
column, which is at most 2 because of the distance 1 restriction. If
$t_{3}=0$, then clearly $|T|\leq 2$. If $t_{3}=1$, then regardless of which
point of the last column is in $T$, it forms three points of a border triangle
with $(1,1)$ and $(2,2)$, and hence $|T|\leq 2$. Finally, if $t_{3}=2$, then
the second column must be empty and so either the $(1,1)$ is not in $T$ and
$|T|=2$, or it is, in which case we have the first $k=3$ case in Figure 18.

For $k=4$, we break $[4]_{L}$ into the last column and $[3]_{L}$. We condition
on the number $t_{4}$ of points of $T$ in the last column, which is at most 2
because of the distance 1 restriction. If $t_{4}=0$ then all points of $T$ are
in $[3]_{L}$, so as before $|T|\leq 3$. If $t_{4}=1$ then there can be at most
one point of $T$ in the third column, and the extra non-diagonal assumption in
this $k=4$ case implies that there is at most one point of $T$ in $[2]_{L}$,
for a total of $|T|\leq 3$. Finally, if $t_{4}=2$ then we conclude as in
Figure 19:

$\leq 1$$\leq 1$ Figure 19: The three possible locations of two points in the
last column. In the first two cases, the entire third column is forbidden by
the distance $1$ and non-diagonal assumptions, so there is only at most one
other point in $T$. In the last case, the same argument holds unless $(3,1)\in
T$, but then each point in $[2]_{L}$ is forbidden because of triangles they
form with it and $(4,2)$.

For $k=5$, we cover $[5]_{L}$ by three pieces: the triangle $[3]_{L}$, the
“top triangle” and “the square”:

$\leq 3$$\leq 3$$\leq 2$ Figure 20: Covering $[5]_{L}$ by two triangles and a
square. Note that both triangles have at most 3 points by the $k=3$ case
above, and the point $(3,3)$ is in both triangles.

We condition on the number of points $t_{s}$ in the square, which is at most 2
because of the distance 1 condition. The cases $t_{s}=0$ and $t_{s}=1$ can be
handled simultaneously. In both, $|T|\leq 5$ unless one triangle has 3 points
of $T$ and the other has at least 2 points of $T$ distinct from the first
triangle. Without loss of generality, suppose $T\cap[3]_{L}$ has 3 points;
this implies it must have the optimal $k=3$ configuration, and hence $(3,3)\in
T$. But then the top triangle must have two additional points of $T$, that is,
three points of $T$ as well, yielding the same configuration. One then easily
checks that the only point of the square which can be in $T$ is $(5,1)$, and
including it yields the second $k=5$ case in Figure 18.

$1$$2$$1,2$ Figure 21: When $t_{s}<2$, then there are enough points in $T$
only if both triangles must have the optimal $k=3$ configuration. When
$t_{s}=2$, the third row and columns have no points of $T$. In either case,
one of the optimal $k=5$ configurations is achieved.

Finally, suppose that $t_{s}=2$. Any pair of two points of the square being in
$T$ forbids the four points adjacent to the square. In particular, this
forbids the optimal $k=3$ configuration in either triangle, and so both have
at most 2 points of $T$. Thus, $|T|\leq 5$ unless both have exactly 2 points
of $T$, neither of which is $(3,3)$. This implies that the third column has no
points in $T$, which means that $T\cap[2]_{L}=\\{(1,1),(2,2)\\}$ as previously
noted. Analogously, the two points of $T$ in the upper triangle are forced to
be $(4,4)$ and $(5,5)$. Finally, these two points form a unimodular triangle
with $(4,2)$, which fixes the pair of points of $T$ in the square, and in
particular yields the first $k=5$ case in Figure 18. ∎

This claim for $k=3$ and $k=5$, together with its equality cases (Figure 18)
deal with the cases when there are points at distance $\sqrt{2}$ on the main
diagonal or a second diagonal (see Figures 22 and 23).

$\leq 3$$\leq 3$$1$$2$$3$$1,2$$1,3$$5$$6$$4$$1,5$$2,6$ Figure 22: There are
two points in $T$ at distance $\sqrt{2}$ on the main diagonal. We apply the
equality case for $k=3$ in B.3 to conclude $T$ has at most 9 points. $\leq
6$$1$$2$$1,2$$1,2$ Figure 23: There are two points in $T$ at distance
$\sqrt{2}$ on a second diagonal. We apply the equality case for $k=5$ in B.3
to conclude $T$ has at most 9 points.

Now, we assume there are no points at distance $\sqrt{2}$ either on the main
diagonal or a second diagonal. The latter assumption allows us to use of the
claim for $k=4$ when there are points at distance $\sqrt{2}$ on a first
diagonal (see Figure 24) or a third diagonal (see Figure 25).

$\leq 3$$\leq 2$ Figure 24: There are two points in $T$ at distance $\sqrt{2}$
on a first diagonal. We apply the $k=4$ case of B.3 to conclude $T$ has at
most 9 points. $\leq 2$$\leq 2$$\leq 3$ Figure 25: There are two points in $T$
at distance $\sqrt{2}$ on a third diagonal. We make use of skewed $2\times 3$
windows and the $k=4$ case of B.3 to conclude $T$ has at most 9 points.

We now make the following observation: the above cases show that $T$ cannot
have more than $9$ points unless the only points at distance $\sqrt{2}$ are
those of either a fourth diagonal or fourth antidiagonal. Without loss of
generality, let $T$ contain the two points of the upper fourth diagonal.

Suppose also that $T$ _does not_ contain the two points of the lower fourth
diagonal. We partition the grid as in Figure 26 and observe that if $|T|>9$
then each of the six windows must contain the maximum number of points. But
there are only two ways to include $2$ points in the ‘left $2\times 3$ window’
avoiding distance $1$ or $\sqrt{2}$ on a lower diagonal; neither yields enough
points.

$\leq 1$$\leq 1$$\leq 1$$\leq 1$$\leq 2$$\leq
2$$1$$2$$1,2$$1,2$$1,2$$3$$2,3$$2,3$$2,3$$4$$3,4$$3,4$$3,4$$3,4$$1$$2$$1,2$$3$$4$
Figure 26: In the first case, we conclude there cannot be 2 points in the top
$3\times 2$ window. The second case forces $3$ and $4$ to be in $T$ and so it
is analogous to the first case by symmetry.

Thus, the last remaining case is when $T$ contains both fourth diagonals, in
which case $|T|>9$ can be achieved only if at most one point missing; that is,
one of the five remaining windows can have one fewer than its maximum number
of points.

Using the notation from Figure 27, at least one of points 1 and 2 are in $T$;
by symmetry, we may say that point 1 is in $T$. Then the top $3\times 2$
window contains at most one point, and $|T|>9$ only if both 2 and 4 are in
$T$. If 2 is in $T$, then there is at most one point in both rectangular
corner windows. We conclude $|T|\leq 9$.

$\leq 1$$\leq 1$$\leq 1$$\leq 2$$\leq 2$$\leq
2$$1$$2$$3$$5$$1,3$$1,3$$1,3$$1$$4$$2,5$$2,5$$2,5$$2,5$ Figure 27: Without
loss of generality, point $1$ is in $T$. But then both the points 2 and 4 must
also be in $T$, and $|T|\leq 9$.

We thus conclude that $|T|\leq 9$ if it has any consecutive points in any
diagonal of $[6]$, as desired.