# Two-dimensional ferroelectricity induced by octahedral rotation distortion
in perovskite oxides

Ying Zhou  School of Materials Science and Physics, China University of Mining
and Technology, Xuzhou 221116, China  Shuai Dong  School of Physics, Southeast
University, Nanjing 211189, China  Changxun Shan  Ke Ji  Junting Zhang
<EMAIL_ADDRESS>School of Materials Science and Physics, China
University of Mining and Technology, Xuzhou 221116, China

###### Abstract

Two-dimensional (2D) ferroelectricity has attracted extensive attention since
its discovery in the monolayers of van der Waals materials. Here we show that
2D ferroelectricity induced by octahedral rotation distortion is widely
present in the perovskite bilayer system through first-principles
calculations. Perovskite tolerance factor plays a crucial role in the lattice
dynamics and ground-state structure of the perovskite monolayers and bilayers,
thus providing an important indicator for screening this hybrid improper
ferroelectricity. Generally, the ferroelectric switching via an orthorhombic
twin state has the lowest energy barrier. Epitaxial strain can effectively
tune the ferroelectric polarization and ferroelectric switching by changing
the amplitude of octahedral rotation and tilt distortion. The increasing
compressive strain causes a polar to non-polar phase transition by suppressing
the tilt distortion. The cooperative effect of octahedral distortion at the
interface with the substrate can reduce the energy barrier of reversing
rotation mode, and even change the lowest-energy ferroelectric switching path.

##  I Introduction

The two-dimensionalization of ferroelectricity has attracted considerable
interest in recent years due to its potential applications in high-density
nonvolatile memory, low energy consumption and miniaturization of electronic
devices [1, 2, 3, 4, 5]. However, the existence of two-dimensional (2D)
ferroelectricity has been a long open question [1]. Conventional ferroelectric
films, especially those with out-of-plane ferroelectricity desired in devices,
generally exhibit critical thickness effect due to the depolarization fields
or surface and interface effects [6, 7, 8]. For example, ferroelectricity
disappears when some perovskite ferroelectric films are reduced to the
thickness of a few unit cells [7, 8]. However, some theoretical and
experimental studies have shown the possible absence of critical thickness, in
which the multi-domain states, and the interface effect with a conducting
electrode or insulating substrate have been found to be crucial for
neutralizing the depolarization field and stabilizing the ferroelectricity in
ultrathin films [9, 10, 11]. Very recently, 2D ferroelectricity down to the
monolayer limit has been demonstrated in van der Waals materials [12, 13, 14].
Some novel ferroelectric mechanisms and phenomena have emerged in these 2D
materials, such as switchable spontaneous polarization in elemental monolayers
and 2D metals [15, 16, 17].

It is of great significance to achieve 2D ferroelectricity beyond van der
Waals materials, since conventional ferroelectrics are mostly concentrated in
transition-metal oxides, especially perovskite oxides [1, 2]. Recently, the
successful growth of the freestanding perovskite oxides down to the monolayer
limit has paved the way for the design of some functional properties based on
2D perovskite oxides [18, 19]. This also provides an opportunity to resolve
some controversial issues involving 2D ferroelectricity, such as whether the
conventional ferroelectric mechanisms can be maintained to the 2D limit [10],
or whether a novel ferroelectric mechanism emerges in the 2D perovskite
oxides.

In perovskite, the proper ferroelectricity is usually derived from an
electronic mechanism, the second-order Jahn-Teller effect, which is commonly
present in perovskite oxides with $d^{0}$-configuration transition-metal ions
at the _B_ site [20]. The hybrid improper ferroelectricity, _i.e_., octahedral
rotation-induced ferroelectricity, originates from structural geometry effects
and thus has no restriction on the electronic configuration of _B_ -site ions
[21, 22]. This improper ferroelectricity has been demonstrated in layered
perovskites and perovskite superlattice [23, 24, 25, 26, 27, 28], but is
absent in perovskite bulks due to the preservation of inversion symmetry by
octahedral rotation. Until recently, theoretical studies suggested that
octahedral-rotation induced ferroelectricity can occur in 2D perovskites [29,
30, 31]. However, there are still some remaining issues to be resolved, such
as the key influencing factors and the universality of this ferroelectricity.

In this paper, a series of perovskite monolayers and bilayers with formula
$A_{2}B{\rm O}_{4}$ and $A_{3}B_{2}{\rm O}_{7}$ (_A_ =Ca, Sr; _B_ = Ti, Zr,
Si, Ge, Sn), respectively, are selected to study the 2D ferroelectricity based
on perovskite oxides. The divalent alkaline-earth metal ions are selected at
_A_ site to form a non-polar surface, and the tetravalent transition-metal
ions with $d^{0}$ configuration (Ti, Zr) and group-IV ions (Si, Ge, Sn) are
selected at _B_ site for comparison. We study their lattice dynamics,
structure, ferroelectricity, as well as strain and interface effects by using
first-principles calculations. We reveal the correlation between lattice
dynamics and ground-state structure, and the role of perovskite tolerance
factor. We show that the proper ferroelectricity is absent in these 2D
perovskite oxides, while the hybrid improper ferroelectricity is widely
present in the perovskite bilayers with small tolerance factors and can be
significantly tuned by epitaxial strain. The interface effect can also have a
significant impact on the ferroelectric switching.

##  II Computational details

The first-principles calculations based on density functional theory (DFT)
were performed using the projector-augmented wave (PAW) method [32], as
implemented in the Vienna _ab initio_ simulation package (VASP6.1) [33]. The
Ca $3s3p4s$, Sr $4s4p5s$, Ti $3p3d4s$, Zr $4p4d5s$, Si $3s3p$, Ge $4s4p$, Sn
$5s5p$, and O $2s2p$ electrons were treated as valence electrons in the PAW
potentials. The Perdew-Burke-Ernzerhof functional modified for solids (PBEsol)
[34] was used as the exchange-correlation functional. The
$\sqrt{2}\times\sqrt{2}\times 1$ and $\sqrt{2}\times\sqrt{2}\times 2$
perovskite supercells were used to construct distorted structures caused by
various octahedral rotation for the perovskite monolayers and bilayers,
respectively. A vacuum space of 20 Å was imposed in order to avoid interaction
between neighboring periodic images. We used a plane-wave cutoff energy of 600
eV for the plane-wave expansion, and a $\varGamma$-centered $7\times 7\times
1$ _k_ -point mesh for the Brillouin zone integration. The in-plane lattice
constants and internal atomic coordinates of each structural phase were
relaxed until the Hellman-Feynman force on each atom is less than 0.01 eV/Å. A
convergence threshold of $10^{-6}$ eV was used for the electronic self-
consistency loop. Phonon band structures were calculated using density
functional perturbation theory (DFPT) [35]. The phonon frequencies and
corresponding eigenmodes were calculated on the basis of the extracted force-
constant matrices, as implemented in the PHONOPY code [36]. The non-analytical
term correction was used to calculate the LO-TO splitting of phonon frequency
[35]. In order to confirm the thermodynamic stability of the ground-state
phases, the _ab_ initio molecular dynamics simulations at 300 K were performed
in a canonical ensemble, and a large supercell containing 216 atoms was used
to minimize the constraint of periodic boundary conditions. The Born effective
charge was calculated using DFPT method, and the ferroelectric polarization
was calculated based on the Born effective charge obtained. The climbing
nudged elastic band method [37] was used to determine the energy barrier of
different ferroelectric switching paths. The ISOTROPY tool [38] was used to
aid with the group-theoretical analysis.

##  III results and discussion

###  III.1 Lattice dynamics

Figure 1:  (a) Ferroelectric (FE), polar (P), and antipolar (AP) soft modes
appearing in perovskite monolayers. The arrow represents the direction of ion
displacement. (b) The energy of the distorted structure caused by each soft
mode as a function of the mode amplitude. The ion displacement of the soft
mode is along the [100] and [110] directions, respectively.

We first studied the lattice dynamics of the selected 2D perovskite oxides and
revealed its correlation with perovskite tolerance factor. The phonon spectra
of the prototype phases (space group $P4/mmm$) of the perovskite monolayers
are shown in Fig. S1 of the Supplemental Material [39]. Only the prototype
phase of the Sr2SiO4 monolayer with a maximum tolerance factor ($t=1.127$)
exhibits dynamic stability. The remaining monolayers all appear unstable modes
at the high symmetry _M_ point of the Brillouin zone, where the soft mode with
the lowest frequency represents the octahedral rotation distortion. Note that
the octahedral rotation distortion can be divided into rotation and tilt modes
in 2D perovskites, which represent the octahedral rotation around the out-of-
plane and in-plane axes, respectively. The lowest-frequency soft mode belongs
to the rotation mode, while the tilt mode is stable for all monolayers. The
rest of the soft modes involves the deformation of the octahedron. The
monolayers with $t>1$ and $t<1$ respectively exhibit single and multiple soft
modes at _M_ point, expect for the Ca2GeO4 monolayer with $t=1.012$ (see Table
I). In addition, the monolayers with $t<1$ (except Sr2SnO4) also show some
soft modes in the center of the Brillouin zone, involving ferroelectric, polar
and antipolar modes, as shown in Fig. 1(a). For the polar and antipolar modes,
the ion displacements in the upper and lower surfaces are the same and
opposite respectively. Interestingly, the ferroelectric soft mode appears in
the Ca2SnO4 monolayer without transition-metal ion. Therefore, the
ferroelectric soft mode may not be driven by the electronic mechanism related
to the second-order Jahn-Teller effect [20], but rather related to structural
geometric effect, namely cation size mismatch.

Then we calculated the energy gain caused by the freezing of each soft mode.
Among the soft modes appearing at _M_ point, only the rotate mode can reduce
the energy of the system (see Fig. S2 [39]). In addition, although the tilt
mode is stable, its freezing can also cause a slightly reduction in energy.
For all the soft modes appearing at $\varGamma$ point, only the ferroelectric
mode of the Ca2TiO4 monolayer shows a typical double-well type energy curve,
while the remaining soft modes show a parabolic energy curve, as shown in
Fig.1 (b). Therefore, not all soft modes can generate energy gain, which may
be related to the fact that the anharmonic effect is not considered in the
calculation of phonon band structures. Similar phenomena have also been found
in other perovskite and layered perovskite oxides [40, 30, 31].

Table 1:  Tolerance factor, soft modes of prototype phase, octahedral rotation
and space group of ground-state structure, and Born effective charge of _B_
-site ions of the peprovskite monolayers. The symbols
”$\scriptstyle{\blacksquare}$” and ”$\times$” respectively represent the
presence and absence of the soft mode at the corresponding high symmetry
points, and ”$\scriptstyle{\blacksquare\blacksquare}$” represents the presence
of multiple soft modes at _M_ point.

For the perovskite bilayers, only the prototype phase of the Sr3Si2O7 bilayer
exhibits dynamic stability (see Fig. S3 [39]), similar to the monolayer
system. The remaining bilayers show soft modes at _M_ point, and the bilayers
with relatively small tolerance factor show multiple soft modes. The lowest-
frequency soft modes involve almost degenerate in-phase (IR) and out-of-phase
(OR) octahedral rotation modes. The bilayers with $t<1$ (except Sr3Sn2O7) show
multiple soft modes at $\varGamma$ point, involving ferroelectric, polar and
antipolar modes [see Fig. 2(a)], similar to their monolayers. The structural
distortion caused by the rotation or tilt mode can reduce the energy of the
bilayer (see Fig. S2 [39]), similar to the monolayer system. However,
different from the monolayer system, the $Q_{\varGamma}$ soft modes of the
bilayers generally show double-well type energy curve, as shown in Fig. 2(b).
Their maximum energy gain is inversely proportional to the tolerance factor,
for example, the largest energy gain occurs in the Ca3Zr2O7 bilayer with the
smallest tolerance factor.

Figure 2:  (a) Ferroelectric (FE), polar (P), and antipolar (AP) soft modes
appearing in peroovskite bilayers. (b) The energy of the distorted structure
caused by each soft mode as a function of the mode amplitude. Table 2:
Tolerance factor, soft modes of prototype phase, octahedral rotation and space
group of ground-state structure, the lowest energy barrier of ferroelectric
switching, and ferroelectric polarization of the peprovskite bilayers. The
symbol ”-” represents the absence of ferroelectricity in the ground-state
phase.

###  III.2 Ground-state structure

Next, in order to determine the ground-state structure, we considered the
possible coupling between different structural distortion modes. For the
perovskite monolayer, in the presence of octahedral rotation ($Q_{M_{2}^{+}}$)
or tilt ($Q_{M_{5}^{+}}$) mode, the ferroelectric ($Q_{\varGamma_{5}^{-}}$),
polar ($Q_{\varGamma_{5}^{-}}$) and antipolar ($Q_{\varGamma_{5}^{+}}$) modes
will not reduce the energy of the system. In addition, in the distorted
structure established by $Q_{M_{2}^{+}}$ (or $Q_{M_{5}^{+}}$) $\oplus$
$Q_{\varGamma_{5}^{-}}$ (or $Q_{\varGamma_{5}^{+}}$) modes, the latter
basically disappears after structural optimization. However, in the distorted
structure caused by $Q_{M_{2}^{+}}\oplus Q_{M_{5}^{+}}$ modes, the antipolar
$Q_{\varGamma_{5}^{+}}$ mode can coexist with them. This can be attributed to
the trilinear coupling $Q_{M_{2}^{+}}Q_{M_{5}^{+}}Q_{\varGamma_{5}^{+}}$
allowed by symmetry.

Then we analyzed the structural symmetry of various octahedral rotation types,
and calculated the energy of each structural phase (see Tables S1 and S2 [39])
by optimizing the atomic coordinates and the in-plane lattice constants under
fixed symmetry. As shown in Table I, only the ground-state structure of the
Sr2SiO4 monolayer maintains the prototype phase, consistent with the results
of lattice dynamics. The ground-state structure of the remaining monolayers
are divided into two categories, basically with the tolerance factor $t=1$ as
the boundary, that is, when the tolerance factor is greater than and less than
1, the ground-state structure becomes the $P4/mbm$ ($a^{0}a^{0}c$ type
octahedral rotation) and $P2_{1}/c$ ($a^{-}a^{-}c$ type) phases, respectively.
The only exception is the Ca2GeO4 monolayer, which has a tolerance factor
($t=1.012$) slightly greater than 1, but shows $a^{-}a^{-}c$ type octahedral
rotation. This exception is consistent with the results of its lattice
dynamics. When the prototype phase shows single (_i.e._ , only rotate mode)
and multiple soft modes at _M_ points, the ground-state phase exhibits only
rotation ($a^{0}a^{0}c$) and rotation plus tilt ($a^{-}a^{-}c$) distortion,
respectively.

For the perovskite bilayers, only the ground-state structure of the Sr3Si2O7
bilayer does not show any structural distortion (see Table 2), similar to its
monolayer. The ground-state structure of the bilayers with $t>1$ (except
Ca3Ge2O7) exhibits the $P4/nbm$ phase caused by a single OR ($Q_{M_{4}^{-}}$)
mode, while the ground-state structure of the bilayers with $t<1$ is the polar
$Pmc2_{1}$ phase established by IR ($Q_{M_{2}^{+}}$) plus tilt
($Q_{M_{5}^{-}}$) distortion. The octahedral rotation type ($a^{-}a^{-}c^{+}$)
of these polar bilayers is not reconstructed with respect to their perovskite
bulk and layered bulk phases [25, 26, 27, 28]. In this polar ground-state
phase, the polar mode ($Q_{\varGamma_{5}^{-}}$) [see Fig. 2(a)] emerges and is
coupled with the IR and tilt modes, which is a manifestation of the trilinear
coupling $Q_{M_{2}^{+}}Q_{M_{5}^{-}}Q_{\varGamma_{5}^{-}}$. This polar mode is
also essential for maintaining the octahedral rotation distortion of this
ground-state phase (see Fig. S4 [39]). There is another trilinear coupling for
the perovskite bilayers, $Q_{M_{4}^{-}}Q_{M_{5}^{-}}Q_{\varGamma_{5}^{+}}$.
This trilinear coupling is responsible for the hybrid improper
antiferroelectricity, which has been demonstrated in layered perovskites with
Ruddlesden-Popper phase [27].

###  III.3 Ferroelectricity

The transition-metal ions with $d^{0}$ configuration (Ti4+ and Zr4+) in the 2D
perovskites show abnormally large Born effective charge (see Table. I),
similar to the perovskite bulks [41], indicating the possible existence of the
proper ferroelectricity. In fact, this proper ferroelectricity related to the
_B_ -site ion with empty _d_ orbital has been predicted to exist in 2D
perovskites [29]. However, the structural phase caused by ferroelectric or
polar mode individually does not become the ground-state phase of these
selected perovskite monolayers and bilayers (see Tables S1 and S2 [39]). In
the perovskite monolayer, each octahedral distortion mode retains the
inversion center at the center of the octahedron, which rules out the
possibility of ferroelectricity caused by octahedral distortion. When extended
to the perovskite bilayer, the combination of two octahedral distortion modes
with different inversion centers, such as IR plus tilt modes, can break the
inversion symmetry, leading to the appearance of polar phase.

Figure 3:  (a) Ion-resolved and (b) layer-resolved polarization of the polar
perovskite bilayers.

We next focused on the polar ground-state phase of the perovskite bilayers.
The phonon spectrum calculation and the first-principles molecular dynamics
simulation respectively confirmed its dynamic and thermodynamic stability (see
Fig. S5 [39]). Although the IR plus tilt modes can directly establish a polar
phase in the absence of polar mode, the polar distortion is responsible for
the appearance of ferroelectric polarization. The ferroelectric polarization
disappears if we remove the polar distortion from the ground-state structure
and retain the octahedral rotation distortion. In contrast, if we remove the
octahedral rotation distortion and keep the polar distortion unchanged, the
calculated polarization does not change, confirming that the ferroelectric
polarization originates entirely from the polar distortion.

Figure 3 shows the contribution of different ions and atomic layers to the
ferroelectric polarization. The polar displacements of cations and anions
induces the opposite polarization, and the polarization induced by the _A_ and
_B_ cations is close. This indicates that the polarization originates from the
polar mode rather than the ferroelectric mode shown in Fig. 2(a). In general,
the perovskite bilayers with smaller tolerance factor have larger polarization
induced by _A_ and O ions. The polarization induced by the two surface _A_ -O
layers is opposite to and much larger than that of the intermediate _A_ -O
layer, and the polarization induced by the _B_ -O layers is rather weak, as
shown in Fig. 3(b), indicating that the ferroelectric polarization is mainly
derived from the ion displacement of the surface layer. Note that unlike other
polar bilayers, the polarization induced by the _B_ -O layers in the Ca3Ti2O7
bilayer is considerable and in the same direction as that of the _A_ -O layer,
which may be the reason for its maximum polarization among these bilayers. The
magnitude of total ferroelectric polarization does not show an obvious
dependence on the tolerance factor (see Table II). For example, the
polarization values of the Ca3Ti2O7 and Ca3Zr2O7 bilayers are very close
despite the large differences of tolerance factor. The calculated polarization
is greater than that of the corresponding layered perovskite bulk phases [25,
26, 27, 28].

The reversal of polarization can be caused by switching the senses of rotation
of IR or tilt mode individually. Both modes can be reversed by a one-step (OS)
or multi-steps (MS) switching [30, 31]. The reversal of IR mode via MS refers
to the change of the octahedral rotation direction in the upper and lower
layers sequentially, so it undergoes a nonpolar phase established by OR plus
tilt modes. For the MS switching of reversing tilt mode, the tilt axis
undergoes a 180∘ rotation in the _ab_ plane, so that it passes through an
orthogonal twin state with tilt axis perpendicular to its initial direction.
Previous experiments have shown that the low switching barrier of the bulk
ferroelectric Ca3Ti2O7 is related to the appearance of orthogonal twin domains
[26]. We calculated the energy barrier of different switching paths for the
perovskite bilayers with polar ground-state phase (see Fig. 4). The results
show that the MS switching path always has a lower energy barrier than the
corresponding OS switching path. The MS switching of reversing tilt mode
generally has the lowest energy barrier, which may be attributed to the fact
that this switching path always maintains IR plus tilt distortion. However,
for the Ca3Zr2O7 and Ca3Sn2O7 bilayers with smaller tolerance factors, the MS
switching path of reversing IR mode has close or even degenerate energy
barrier with respect to this lowest-energy switching path.

Figure 4:  Total energy of each polar perovskite bilayer as a function of
switching coordinate along different ferroelectric switching paths, involving
reversing the IR and tilt modes via one step (OS) or multi steps (MS). The
panels on the right show the variation of the polarization component along the
lowest-energy ferroelectric switching path.

The lowest energy barrier is proportional to the amplitude of tilt distortion.
For example, the Ca3Zr2O7 and Ca3Sn2O7 bilayers have relatively large
amplitude of tilt distortion, resulting in very high energy barrier (see Table
II). Therefore, their electric polarization is difficult to be reversed by the
electric field. Other polar bilayers have relatively small energy barrier
($<100$ meV/f.u.), of which the Sr3Sn2O7 bilayer has the lowest energy barrier
(49 meV/f.u.). The ferroelectricity of some of their corresponding layered
bulk phases including Ca3Ti2O7 [26], Sr3Sn2O7 [28], and Sr3Zr2O7 [27] have
been demonstrated experimentally, and the ferroelectric switching barrier of
the Ca3Ti2O7 bilayer is very close to the calculated value (82 meV/f.u.) of
its layered bulk phase [42].

The variation of polarization component during the lowest-energy ferroelectric
switching is shown in Fig. 4. The direction of polarization changes
continuously in the _ab_ plane during the ferroelectric switching. In
addition, the magnitude of polarization undergoes a significant change, that
is, it is greatly reduced when approaching the barrier phase. This change in
polarization stems from the variation of tilt and polar modes during
ferroelectric switching, which exhibit similar change trend (see Fig. S6
[39]). The above results indicate that the octahedral rotation-induced
ferroelectricity can be maintained in the perovskite bilayer. This hybrid
improper ferroelectricity is likely to be widespread in this 2D system since
it is derived from purely geometric effect rather than electronic mechanism.
The magnitudes of ferroelectric polarization and the ferroelectric switching
barrier can be optimized by selecting cation combinations.

###  III.4 Strain and interface effect

It is known that the octahedral rotation can be significantly affected by the
epitaxial strain in the epitaxially grown perovskite films [43, 44]. Then we
studied the strain effect of the perovskite bilayers grown on a square
substrate. The in-plane lattice parameters are fixed to be the same as those
of the substrate due to epitaxial matching. For the Ca3Zr2O7 and Ca3Sn2O7
bilayers with smaller tolerance factors, the polar $Pmc2_{1}$ phase is always
the ground-state phase in the entire strain range, that is, the epitaxial
strain does not change their octahedral rotation type, as shown in Fig. 5.
However, for the remaining four polar bilayers with relatively large tolerance
factors, the ground-state structure gradually changes from the polar
$Pmc2_{1}$ phase to the non-polar $P4/nbm$ phase with increasing compressive
strain, which can be attributed to the suppression of tilt distortion by
compressive strain (see Fig. S7 [39]). This polar to nonpolar transition has
been demonstrated theoretically in some layered $A_{3}B_{2}$O7 type perovskite
oxides [43]. The energy curves of these polar bilayers show similar change
trend with strain. The energy difference between different structural phases
(except the two phases with only tilt distortion) gradually decreases with the
increase of compressive strain. The polar ground-state phase is absent in the
strained bilayers with larger tolerance factor, that is, the epitaxial strain
fails to induce the polar phase in the non-polar bilayers. The ground-state
phase ($P4/mmm$) of the strained Sr3Si2O7 bilayer remains the same as its
unstrained state. However, for the remaining three non-polar bilayers, the
ground-state structure changes from $P4/nbm$ ($a^{0}a^{0}c^{-}$ type
octahedral rotation) to $Pmma$ phase ($a^{-}a^{-}c^{0}$) with the increase of
tensile strain. This transition is related to the suppression of rotation
distortion and the enhancement of tilt distortion by the increasing tensile
strain. Similar strain effects on octahedral rotation have been found in
perovskite oxide heterostructures [45, 46].

Figure 5:  Change in energy of all structural phases with epitaxial strain.
The energy curves of the prototype phase and the structural phases caused by
the $Q_{\varGamma}$ mode alone are not shown due to their high energy. The
strain value is defined as $\varepsilon=(d-d_{0})/d_{0}$, where _d_ and
$d_{0}$ are the in-plane lattice constants of the strained and unstrained (the
prototype phase) bilayers, respectively. The ground-state phases are marked
and their ranges are color-coded.

The significant variation of the amplitude of the octahedral rotation
distortion with strain (see Fig. S7 [39]) indicates that the epitaxial strain
can be used as an effective means to tailor the octahedral rotation-induced
ferroelectricity. In the case of the most commonly used SrTiO3 substrate, the
Ca3Ti2O7 and Ca3Sn2O7 bilayers grown on this substrate are subjected to
tensile ($+2.6\%$) and compressive ($-2.2\%$) strain, respectively. For the
Ca3Ti2O7 bilayer, this tensile strain lowers and raises the energy barrier of
reversing rotation and tilt modes, respectively. This causes the MS switching
of reversing IR mode to become the lowest-energy ferroelectric switching path
[see Fig. 6(a)]. In contrast, the compressive strain reduces the energy
barrier of reversing tilt mode for the Ca3Sn2O7 bilayer, resulting in the
lowest energy barrier for the MS switching of reversing tilt mode (see Fig. S8
[39]). Its ferroelectric polarization is also correspondingly reduced due to
the attenuation of the amplitude of the tilt mode.

Figure 6:  (a) Change in energy along different ferroelectric switching paths
for the tensile strained Ca3Ti2O7 bilayer, whose in-plane lattice constants
are fixed to that of the SrTiO3 substrate. The upper subgraph illustrates the
MS path of reversing the IR mode. The curved arrow represents the rotation
direction of the octahedron around the _c_ axis. (b) Change in energy along
different ferroelectric switching paths for the heterostructure
Ca3Ti2O7/(SrTiO${}_{3})_{4}$, and the schematic of the MS path of reversing
the IR mode.

Next, we used a heterostructure model Ca3Ti2O7/(SrTiO${}_{3})_{4}$ to reveal
the effect of the interface formed with the substrate. The SrO layer at the
bottom of the SrTiO3 substrate was fixed during structural optimization to
simulate a thick substrate [47, 48]. The results of electrostatic potential
show that the out-of-plane electric field caused by the asymmetry of the
heterostructure model is negligible (see Fig. S9 [39]). In addition, the
introduction of dipole correction [49] does not change the distribution of
electrostatic potential and the energy barrier of ferroelectric switching. The
structural distortion of the Ca3Ti2O7 bilayer induces octahedral rotation and
tilt distortion in the substrate, which is mainly concentrated in the
interface SrTiO3 layer [see Fig. 6(b)]. The interface effect does not change
the octahedral rotation type and electronic properties of the Ca3Ti2O7
bilayer. However, it has a significant impact on ferroelectric switching. In
the heterostructure model, the energy barrier of ferroelectric switching by
reversing IR mode (especially OS switching) is significantly reduced, while
that by reversing tilt mode is only slightly changed [see Figs. 6(a) and
6(b)]. This is related to the cooperative effect of the octahedral rotation
distortion at the interface. The reversal of the IR mode in the bilayer also
leads to the reversal of the rotation in the interface SrTiO3 layer. The
presence of octahedral rotation distortion in the interface layer resulting in
asymmetry in the first half and the last half of the MS switching path of
reversing IR mode, which is responsible for the significant difference in the
energy of the two barrier phases. A similar interface effect is also observed
in the Ca3Sn2O7/(SrTiO${}_{3})_{4}$ heterostructure [see Fig. S8(b)] [39].

##  IV conclusion

In conclusion, we have systematically studied the lattice dynamics, structure,
ferroelectricity, strain and interface effect of a series of 2D perovskite
oxides. The results show that the soft modes and ground-state structures of
the perovskite monolayers and bilayers are significantly dependent on the
perovskite tolerance factor. Ferroelectricity is absent in these perovskite
monolayers while widely present in the perovskite bilayers with smaller
tolerance factors. Generally, the MS ferroelectric switching path of reversing
tilt mode has the lowest energy barrier. Epitaxial strain can significantly
tune the amplitude of octahedral rotation distortion. Compressive strain can
reduce the energy barrier of ferroelectric switching, and induce a polar to
non-polar phase transition by suppressing the tilt distortion. The interface
effect may significantly affect the ferroelectric switching of reversing IR
mode, and even lead to the transition of the lowest-energy ferroelectric
switching path.

###### Acknowledgements.

This work was supported by the National Natural Science Foundation of China
(Grant No. 11974418), the Fundamental Research Funds for the Central
Universities (Grant No. 2019QNA30), the Postgraduate Research & Practice
Innovation Program of Jiangsu Province (Grant No. KYCX21_2157), and the
Assistance Program for Future Outstanding Talents of China University of
Mining and Technology (Grant No. 2021WLJCRCZL170). Computer resources provided
by the High Performance Computing Center of Nanjing University are greatfully
acknowledged.

## References

  * Dawber  _et al._ [2005] M. Dawber, K. M. Rabe, and J. F. Scott, Physics of thin-film ferroelectric oxides, Rev. Mod. Phys. 77, 1083 (2005).
  * Scott [2007] J. F. Scott, Applications of modern ferroelectrics, Science 315, 954 (2007).
  * Fei  _et al._ [2016] R. Fei, W. Kang, and L. Yang, Ferroelectricity and phase transitions in monolayer group-IV monochalcogenides, Phys. Rev. Lett. 117, 097601 (2016).
  * Ding  _et al._ [2017] W. Ding, J. Zhu, Z. Wang, Y. Gao, D. Xiao, Y. Gu, Z. Zhang, and W. Zhu, Prediction of intrinsic two-dimensional ferroelectrics in in2se3 and other III2-VI3 van der waals materials, Nat. Commun. 8, 14956 (2017).
  * Osada and Sasaki [2019] M. Osada and T. Sasaki, The rise of 2d dielectrics/ferroelectrics, APL Materials 7, 120902 (2019).
  * Woo and Zheng [2007] C. Woo and Y. Zheng, Depolarization in modeling nano-scale ferroelectrics using the landau free energy functional, Applied Physics A: Materials Science & Processing 91, 59 (2007).
  * Junquera and Ghosez [2003] J. Junquera and P. Ghosez, Critical thickness for ferroelectricity in perovskite ultrathin films, Nature 422, 506 (2003).
  * Fong  _et al._ [2004] D. D. Fong, G. B. Stephenson, S. K. Streiffer, J. A. Eastman, O. Auciello, P. H. Fuoss, and C. Thompson, Ferroelectricity in ultrathin perovskite films, Science 304, 1650 (2004).
  * Kolpak and Rappe [2005] S. N. Kolpak and A. M. Rappe, Ferroelectricity in ultrathin perovskite films, Phys. Rev. B 72, 020101 (2005).
  * Gao  _et al._ [2017] P. Gao, Z. Zhang, M. Li, R. Ishikawa, B. Feng, H.-J. Liu, Y.-L. Huang, N. Shibata, X. Ma, S. Chen, J. Zhang, K. Liu, E.-G. Wang, D. Yu, L. Liao, Y.-H. Chu, and Y. Ikuhara, Possible absence of critical thickness and size effect in ultrathin perovskite ferroelectric films, Nat. Commun. 8, 15549 (2017).
  * Baker and Bowler [2020] J. S. Baker and D. R. Bowler, Polar morphologies from first principles: Pbtio3 films on srtio3 substrates and the $p(2\times\lambda)$ surface reconstruction, Adv. Theory Simul. 3, 2000154 (2020).
  * Chang  _et al._ [2016] K. Chang, J. Liu, H. Lin, N. Wang, K. Zhao, A. Zhang, F. Jin, Y. Zhong, X. Hu, W. Duan, Q. Zhang, L. Fu, Q.-K. Xue, X. Chen, and S.-H. Ji, Discovery of robust in-plane ferroelectricity in atomic-thick snte, Science 353, 274 (2016).
  * Liu  _et al._ [2016] F. Liu, L. You, K. L. Seyler, X. Li, P. Yu, J. Lin, X. Wang, J. Zhou, H. Wang, H. He, S. T. Pantelides, W. Zhou, P. Sharma, X. Xu, P. M. Ajayan, J. Wang, and Z. Liu, Room-temperature ferroelectricity in cuinp2s6 ultrathin flakes, Nat. Commun. 7, 12357 (2016).
  * Zhou  _et al._ [2017] Y. Zhou, D. Wu, Y. Zhu, Y. Cho, Q. He, X. Yang, K. Herrera, Z. Chu, Y. Han, M. C. Downer, H. Peng, and K. Lai, Out-of-plane piezoelectricity and ferroelectricity in layered $\alpha$-in2se3 nanoflakes, Nano Lett. 17, 5508 (2017).
  * Li and Wu [2017] L. Li and M. Wu, Binary compound bilayer and multilayer with vertical polarizations: Two-dimensional ferroelectrics, multiferroics, and nanogenerators, ACS Nano 11, 6382 (2017).
  * Xiao  _et al._ [2018] C. Xiao, F. Wang, S. A. Yang, Y. Lu, Y. Feng, and S. Zhang, Elemental ferroelectricity and antiferroelectricity in group-v monolayer, Adv. Funct. Mater. 28, 1707383 (2018).
  * Fei  _et al._ [2018] Z. Fei, W. Zhao, T. A. Palomaki, B. Sun, M. K. Miller, Z. Zhao, J. Yan, X. Xu, and D. H. Cobden, Ferroelectric switching of a two-dimensional metal, Nature 560, 336 (2018).
  * Ji  _et al._ [2019a] D. Ji, S. Cai, T. R. Paudel, H. Sun, C. Zhang, L. Han, Y. Wei, Y. Zang, M. Gu, Y. Zhang, W. Gao, H. Huyan, W. Guo, D. Wu, Z. Gu, E. Y. Tsymbal, P. Wang, Y. Nie, and X. Pan, Freestanding crystalline oxide perovskites down to the monolayer limit, Nature 570, 87 (2019a).
  * Hong  _et al._ [2017] S. S. Hong, J. H. Yu, D. Lu, A. F. Marshall, Y. Hikita, Y. Cui, and H. Y. Hwang, Two-dimensional limit of crystalline order in perovskite membrane films, Sci. Adv. 3, eaao5173 (2017).
  * Bersuker [2013] I. B. Bersuker, Pseudo-jahn-teller effect-a two-state paradigm in formation, deformation, and transformation of molecular systems and solids, Chem. Rev. 113, 1351 (2013).
  * Benedek and Fennie [2011] N. A. Benedek and C. J. Fennie, Hybrid improper ferroelectricity: A mechanism for controllable polarization-magnetization coupling, Phys. Rev. Lett. 106, 107204 (2011).
  * Benedek  _et al._ [2012] N. A. Benedek, A. T. Mulder, and C. J. Fennie, Polar octahedral rotations: A path to new multifunctional materials, J. Solid State Chem. 195, 11 (2012).
  * Bousquet  _et al._ [2008] E. Bousquet, M. Dawber, N. Stucki, C. Lichtensteiger, P. Hermet, S. Gariglio, J.-M. Triscone, and P. Ghosez, Improper ferroelectricity in perovskite oxide artificial superlattices, Nature 452, 732 (2008).
  * Akamatsu  _et al._ [2014] H. Akamatsu, K. Fujita, T. Kuge, A. S. Gupta, A. Togo, S. Lei, F. Xue, G. Stone, J. M. Rondinelli, L.-Q. Chen, I. Tanaka, V. Gopalan, and K. Tanaka, Inversion symmetry breaking by oxygen octahedral rotations in the ruddlesden-popper na _R_ tio4 family, Phys. Rev. Lett. 112, 187602 (2014).
  * Mulder  _et al._ [2013] A. T. Mulder, N. A. Benedek, J. M. Rondinelli, and C. J. Fennie, Turning $ab{\rm o}_{3}$ antiferroelectrics into ferroelectrics: Design rules for practical rotation-driven ferroelectricity in double perovskites and $a_{3}b_{2}{\rm o}_{7}$ ruddlesden-popper compounds, Adv. Funct. Mater. 23, 4810 (2013).
  * Oh  _et al._ [2015] Y. S. Oh, X. Luo, F.-T. Huang, Y. Wang, and S.-W. Cheong, Experimental demonstration of hybrid improper ferroelectricity and the presence of abundant charged walls in (ca,sr)3ti2o7 crystals, Nat. Mater. 14, 407 (2015).
  * Yoshida  _et al._ [2018a] S. Yoshida, K. Fujita, H. Akamatsu, O. Hernandez, A. S. Gupta, F. G. Brown, H. Padmanabhan, A. S. Gibbs, T. Kuge, R. Tsuji, S. Murai, J. M. Rondinelli, V. Gopalan, and K. Tanaka, Ferroelectric sr3zr2o7: Competition between hybrid improper ferroelectric and antiferroelectric mechanisms, Adv. Funct. Mater. 28, 1801856 (2018a).
  * Yoshida  _et al._ [2018b] S. Yoshida, H. Akamatsu, R. Tsuji, O. Hernandez, H. Padmanabhan, A. S. Gupta, A. S. Gibbs, K. Mibu, S. Murai, J. M. Rondinelli, V. Gopalan, K. Tanaka, and K. Fujita, Hybrid improper ferroelectricity in (sr,ca)3sn2o7 and beyond: Universal relationship between ferroelectric transition temperature and tolerance factor in n = 2 ruddlesden-popper phases, J. Am. Chem. Soc. 140, 15690 (2018b).
  * Lu  _et al._ [2017] J. Lu, W. Luo, J. Feng, and H. Xiang, Unusual ferroelectricity in two-dimensional perovskite oxide thin films, Nano Lett. 18, 595 (2017).
  * Zhang  _et al._ [2020] J. Zhang, X. Shen, Y. Wang, C. Ji, Y. Zhou, J. Wang, F. Huang, and X. Lu, Design of two-dimensional multiferroics with direct polarization-magnetization coupling, Phys. Rev. Lett. 125, 017601 (2020).
  * Zhou  _et al._ [2021] Y. Zhou, Z. Chen, Z. Wu, X. Shen, J. Wang, J. Zhang, and H. Sun, Hybrid improper ferroelectricity and magnetoelectric coupling in a two-dimensional perovskite oxide, Phys. Rev. B 103, 224409 (2021).
  * Bl$\rm\ddot{o}$chl [1994] P. E. Bl$\rm\ddot{o}$chl, Projector augmented-wave method, Phys. Rev. B 50, 17953 (1994).
  * Kresse and Furthmüller [1996] G. Kresse and J. Furthmüller, Efficient iterative schemes for ab initiototal-energy calculations using a plane-wave basis set, Phys. Rev. B 54, 11169 (1996).
  * Perdew  _et al._ [2008] J. P. Perdew, A. Ruzsinszky, G. I. Csonka, O. A. Vydrov, G. E. Scuseria, L. A. Constantin, X. Zhou, and K. Burke, Restoring the density-gradient expansion for exchange in solids and surfaces, Phys. Rev. Lett. 100, 136406 (2008).
  * Gonze and Lee [1997] X. Gonze and C. Lee, Dynamical matrices, born effective charges, dielectric permittivity tensors, and interatomic force constants from density-functional perturbation theory, Phys. Rev. B 55, 10355 (1997).
  * Togo and Tanaka [2015] A. Togo and I. Tanaka, First principles phonon calculations in materials science, Scr. Mater. 108, 1 (2015).
  * Sheppard  _et al._ [2012] D. Sheppard, P. Xiao, W. Chemelewski, D. D. Johnson, and G. Henkelman, A generalized solid-state nudged elastic band method, J. Chem. Phys. 136, 074103 (2012).
  * Campbell  _et al._ [2006] B. J. Campbell, H. T. Stokes, D. E. Tanner, and D. M. Hatch, ISODISPLACE: a web-based tool for exploring structural distortions, J. Appl. Crystallogr. 39, 607 (2006).
  * [39] See the Supplemental Material for more results about the phonon band structures, energy gain, energy of all structural phases, coupling of structural distortion modes, molecular dynamics simulation, variation in the amplitude of the distortion modes with ferroelectric switching coordinate and epitaxial strain, and comparison of ferroelectric switching between strain-free, strained bilayer and heterostructure model .
  * Cammarata and Rondinelli [2015] A. Cammarata and J. M. Rondinelli, Ferroelectricity from coupled cooperative jahn-teller distortions and octahedral rotations in ordered ruddlesden-popper manganates, Phys. Rev. B 92, 014102 (2015).
  * Ghosez  _et al._ [1999] P. Ghosez, E. Cockayne, U. V. Waghmare, and K. M. Rabe, Lattice dynamics of batio3, pbtio3, and pbzro3: A comparative first-principles study, Phys. Rev. B 60, 836 (1999).
  * Nowadnick and Fennie [2016] E. A. Nowadnick and C. J. Fennie, Domains and ferroelectric switching pathways in ca3ti2o7 from first principles, Phys. Rev. B 94, 104105 (2016).
  * Lu and Rondinelli [2016] X.-Z. Lu and J. M. Rondinelli, Epitaxial-strain-induced polar-to-nonpolar transitions in layered oxides, Nat. Mater. 15, 951 (2016).
  * May  _et al._ [2010] S. J. May, J.-W. Kim, J. M. Rondinelli, E. Karapetrova, N. A. Spaldin, A. Bhattacharya, and P. J. Ryan, Quantifying octahedral rotations in strained perovskite oxide films, Phys. Rev. B 82, 014110 (2010).
  * Rondinelli  _et al._ [2012] J. M. Rondinelli, S. J. May, and J. W. Freeland, Control of octahedral connectivity in perovskite oxide heterostructures: An emerging route to multifunctional materials discovery, MRS Bull. 37, 261 (2012).
  * Choquette  _et al._ [2016] A. K. Choquette, C. R. Smith, R. J. Sichel-Tissot, E. J. Moon, M. D. Scafetta, E. D. Gennaro, F. M. Granozio, E. Karapetrova, and S. J. May, Octahedral rotation patterns in strained eufeo3 and other pbnm perovskite films: Implications for hybrid improper ferroelectricity, Phys. Rev. B 94, 024105 (2016).
  * An  _et al._ [2017] M. An, Y. K. Weng, H. M. Zhang, J.-J. Zhang, Y. Zhang, and S. Dong, Appearance and disappearance of ferromagnetism in ultrathin lamno3 on srtio3 substrate: A viewpoint from first principles, Phys. Rev. B 96, 235112 (2017).
  * Ji  _et al._ [2019b] C. Ji, Y. Wang, B. Guo, X. Shen, Q. Luo, J. Wang, X. Meng, J. Zhang, X. Lu, and J. Zhu, Strain engineering of magnetic and orbital order in perovskite lumno3 epitaxial films, Phys. Rev. B 100, 174417 (2019b).
  * Bengtsson [1999] L. Bengtsson, Dipole correction for surface supercell calculations, Phys. Rev. B 59, 12301 (1999).


# Planar convex codes are decidable

Boris Bukh Department of Mathematical Sciences, Carnegie Mellon University,
Pittsburgh, PA 15213, USA. Supported in part by U.S. taxpayers through NSF
grant DMS-2154063 and NSF CAREER grant DMS-1555149. R. Amzi Jeffs Department
of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213,
USA. Supported by the National Science Foundation through Award No. 2103206.

(July 2022)

###### Abstract

We show that every convex code realizable by compact sets in the plane admits
a realization consisting of polygons, and analogously every open convex code
in the plane can be realized by interiors of polygons. We give factorial-type
bounds on the number of vertices needed to form such realizations.
Consequently we show that there is an algorithm to decide whether a convex
code admits a closed or open realization in the plane.

## Introduction

### Prelude.

A basic way to represent relationship between several sets is to use _Venn
diagrams_. In a Venn diagram, the sets are represented by planar regions, and
elements are represented by points in such a way that the containment relation
is preserved. For example, Figure 1(a) depicts the usual Venn diagram
representing three sets $A,B,C$ by discs, with eight regions containing points
of the eight sets ${A\cap B\cap C},\overline{A}\cap B\cap
C,\dotsc,\overline{A}\cap\overline{B}\cap\overline{C}$ respectively.

If certain intersections are empty, we may use Venn diagrams omitting them, as
in Figure 1(b).

$A$$B$$C$a) Eight regions are present$A$$B$$C$b) Region $A\cap B\cap C$ is
omitted Figure 1: Three-set Venn diagrams.

This paper is about Venn diagrams realizable by convex regions. These are also
known as _convex codes_ , which is the terminology that we adopt. Convex codes
have been studied extensively over the last decade, with most work following a
2013 paper of Curto, Itskov, Veliz-Cuba and Youngs [4]. The theory of convex
codes can be viewed as a strengthening of the theory of $d$-representable
complexes, which are the simplicial complexes that record nonempty
intersections of a collection of convex sets in $\mathbb{R}^{d}$. Convex codes
record not only the nonempty intersections, but also how other sets cover
these intersections.

It is well known that there is an algorithm to determine whether or not a
given simplicial complex is $d$-representable [11, Section 4.1], but the
analogous problem for convex codes has remained open. Chen, Frick and Shiu [2]
showed that recognizing codes that can be realized by “good covers” is
undecidable, and asked about recognizing convex codes realizable by bounded
open sets. Our main result is an affirmative answer to this question in the
case $d=2$ (Theorem 1 below). Though our focus is on convex sets in the plane,
we work in general $\mathbb{R}^{d}$ whenever possible.

### Convex codes.

Let $X_{1},\dotsc,X_{n}$ be $n$ bounded convex sets in $\mathbb{R}^{d}$. The
_intersection pattern_ of the tuple $\mathcal{X}=(X_{1},\dotsc,X_{n})$ at the
point $p\in\mathbb{R}^{d}$ is
$\operatorname{patt}_{\mathcal{X}}(p)\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\\{i\in[n]\mid p\in X_{i}\\}$. The _convex code_ of $\mathcal{X}$
is then defined as
$\operatorname{code}(\mathcal{X})\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\\{\operatorname{patt}_{\mathcal{X}}(p)\mid p\in\mathbb{R}^{d}\\}$.
If $\mathcal{C}=\operatorname{code}(\mathcal{X})$, we say that $\mathcal{C}$
is a convex code _realized_ by $\mathcal{X}$, and that $\mathcal{X}$ is a
$d$-realization of $\mathcal{C}$. Franke and Muthiah showed that every
$\mathcal{C}\subseteq 2^{[n]}$ containing $\emptyset$ as a codeword is
$d$-realizable for some $d$ [5, Theorem 1].

We shall say that a realization $\mathcal{X}=(X_{1},\dotsc,X_{n})$ of a convex
code $\mathcal{C}$ is _closed_ if every set $X_{i}$ is closed (which implies
that it is compact). We similarly define an _open_ realization. If we consider
only the realizations in $\mathbb{R}^{d}$ for a fixed $d\geq 2$, these are
different concepts: Some convex codes admit only open $d$-realizations, some
admit only closed $d$-realizations, and some admit neither; the first example
showing the difference between open and closed $d$-realizations is due to
Lienkaemper, Shiu and Woodstock [9], and [3, 7, 6] contain more recent
results.

### Our results.

The primary motivation for this work is to find a way to tell which convex
codes are $d$-realizable. To that end, it is natural to wonder whether every
convex code admits a not-too-complicated realization. We give a positive
answer for $d=2$, namely that every closed convex code in the plane can be
realized by polygons (some of which might degenerate into line segments or
points), and that the number of vertices among these polygons is bounded by a
computable function. We obtain the analogous result for open realizations in
the plane as well. As an immediate consequence, we conclude that there is an
algorithm for determining if a convex code has a closed or open
$2$-realization.

######  Theorem 1.

Let $\mathcal{C}\subseteq 2^{[n]}$ be a convex code.

  1. i)

If $\mathcal{C}$ admits a closed convex realization in $\mathbb{R}^{2}$, then
it admits a realization consisting of polygons with at most $6^{n}n!$ total
vertices among them, and

  2. ii)

If $\mathcal{C}$ admits an open convex realization in $\mathbb{R}^{2}$, then
it admits a realization consisting of interiors of polygons with at most
$4\cdot 6^{n}(n+1)!$ total vertices among them.

As a consequence, there is an algorithm to decide whether or not $\mathcal{C}$
admits a closed (respectively, open) convex realization in the plane.

Our proof consists of three steps. First, starting with an arbitrary
realization, we shrink its sets as much as possible. Second, we show that the
resulting inclusion-minimal realizations are polygonal. Third, we bound the
total number of vertices. The first step works for any $d$, but our methods
for the last two are specific to the plane. The situation for $d\geq 3$
remains unclear — we do not know if convex codes in higher dimensions admit
polytopal realizations, and we do not know if there exists a computable bound
on the number of vertices in inclusion-minimal polytopal realizations. In
particular, it is possible that there is no algorithm for deciding whether an
arbitrary convex code is $d$-realizable for fixed $d\geq 3$.

## Step 1: Existence of inclusion-minimal realizations

Let $\mathcal{X}=(X_{1},\ldots,X_{n})$ be a tuple of compact convex sets.
Recall that
$\operatorname{code}(\mathcal{X})\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\\{\operatorname{patt}_{\mathcal{X}}(p)\mid p\in\mathbb{R}^{d}\\}$.
We say that $P\subseteq\mathbb{R}^{d}$ is a _set of representatives_ for
$\mathcal{X}$ if
$\operatorname{code}(\mathcal{X})=\\{\operatorname{patt}_{\mathcal{X}}(p)\mid
p\in P\\}$. Obviously, every $\mathcal{X}$ admits a set of representatives of
size $\lvert\operatorname{code}(\mathcal{X})\rvert\leq 2^{n}$.

######  Lemma 2.

Let $\mathcal{X}=(X_{1},\ldots,X_{n})$ be a tuple of compact convex sets in
$\mathbb{R}^{d}$, and $P$ is a set of representatives for $\mathcal{X}$. Then
there exists a tuple $\mathcal{Y}=(Y_{1},\ldots,Y_{n})$ of compact convex sets
with the following properties:

  1. i)

$Y_{i}\subseteq X_{i}$ for all $i\in[n]$,

  2. ii)

$Y_{i}\cap P=X_{i}\cap P$ for all $i\in[n]$,

  3. iii)

$\operatorname{code}(\mathcal{Y})=\operatorname{code}(\mathcal{X})$, and

  4. iv)

The tuple $\mathcal{Y}$ is inclusion-minimal among all tuples satisfying (i),
(ii) and (iii).

###### Proof.

Let $\mathfrak{R}$ be the set consisting of tuples that satisfy conditions
(i), (ii) and (iii). Introduce a partial order on $\mathfrak{R}$ by declaring
$\mathcal{Y}\leq\mathcal{Y}^{\prime}$ if and only if $Y_{i}^{\prime}\subseteq
Y_{i}$ for all $i\in[n]$. The poset $\mathfrak{R}$ is nonempty as it contains
$\mathcal{X}$. The condition (iv) is equivalent to the tuple $\mathcal{Y}$
being a maximal element in this poset. We shall find it using Zorn’s lemma.

Given a chain $\mathfrak{C}$ of tuples in $\mathfrak{R}$, define a tuple
$\mathcal{Y}=(Y_{1},\ldots,Y_{n})$ by
$Y_{i}=\bigcap_{\mathcal{Y}^{\prime}\in\mathfrak{C}}Y_{i}^{\prime}$. Each
$Y_{i}$ is an intersection of compact convex sets, and so is itself compact
and convex. Moreover, each $Y_{i}$ satisfies (i) and (ii) since these
properties are preserved by intersections. It remains to argue that
$\mathcal{Y}$ satisfies condition (iii).

Since
$\operatorname{patt}_{\mathcal{Y}}(p)=\operatorname{patt}_{\mathcal{X}}(p)$
for every $p\in P$ and $P$ is a set of representatives for $\mathcal{X}$, it
follows that
$\operatorname{code}(\mathcal{X})\subseteq\operatorname{code}(\mathcal{Y})$.
Conversely, let $q$ be any point in $\mathbb{R}^{d}$. For every
$i\notin\operatorname{patt}_{\mathcal{Y}}(p)$, there exists some
$\mathcal{Y}^{(i)}\in\mathfrak{C}$ such that $q\notin Y^{(i)}_{i}$. Let
$\mathcal{Y}^{\prime}$ be the smallest of the tuples of the form
$\mathcal{Y}^{(i)}$. Then
$i\notin\operatorname{patt}_{\mathcal{Y}^{\prime}}(q)$ whenever
$i\notin\operatorname{patt}_{\mathcal{Y}}(q)$. Since $Y_{i}\subseteq
Y_{i}^{\prime}$, we also have
$i\in\operatorname{patt}_{\mathcal{Y}^{\prime}}(q)$ whenever
$i\in\operatorname{patt}_{\mathcal{Y}}(q)$. Therefore,
$\operatorname{patt}_{\mathcal{Y}}(q)=\operatorname{patt}_{\mathcal{Y}^{\prime}}(q)$.
Since $\mathcal{Y}^{\prime}\in\mathfrak{C}$, this implies that
$\operatorname{patt}_{\mathcal{Y}}(q)\in\operatorname{code}(\mathcal{X})$.
Since $q\in\mathbb{R}^{d}$ is arbitrary,
$\operatorname{code}(\mathcal{Y})\subseteq\operatorname{code}(\mathcal{X})$
and hence $\operatorname{code}(\mathcal{Y})=\operatorname{code}(\mathcal{X})$.
We conclude that every chain $\mathfrak{C}$ in $\mathfrak{R}$ has an upper
bound, so $\mathfrak{R}$ has a maximal element, and the result follows. ∎

## Step 2: Inclusion-minimal realizations in the plane are polygonal

######  Lemma 3.

Let $C\subseteq\mathbb{R}^{2}$ be a compact convex set with non-empty
interior, and let $p$ be a boundary point of $C$. Then there exists
$\varepsilon>0$ so that every circle $S$ of positive radius
$\delta<\varepsilon$ centered at $p$ intersects $C$ in a connected arc.

###### Proof.

Consider the set

$C_{p}\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}\\{v\in\mathbb{S}^{1}\mid
p+tv\in C\text{ for some }t>0\\}.$

The set $C_{p}$ consists of the unit vectors which point “into” $C$ from the
boundary point $p$. Since $C$ has non-empty interior, $C_{p}$ is a connected
arc (not necessarily closed or open) that contains more than one point. Up to
affine transformation, we may assume that $p=(0,0)$, and that $C_{p}$ is an
arc in the upper half of the unit circle. Since $C_{p}$ might not be closed,
it might not contains its endpoints. So, instead we select points $q_{1}$ and
$q_{2}$ in $C_{p}$ that are within angle $\pi/4$ of the left and right
endpoints of $C_{p}$, respectively. For convenience, we may also choose
$q_{1}$ and $q_{2}$ to have positive $y$-coordinates. Finally, by scaling $C$
up, we may assume that both $q_{1}$ and $q_{2}$ lie in $C$.

Let $S$ be a circle of radius $\varepsilon>0$ centered at $p$. The
$\varepsilon$ is chosen small enough to satisfy two conditions, which we call
disjointness and tangency.

Disjointness: The ball $\operatorname{conv}(S)$ is disjoint from the line
segment $q_{1}q_{2}$.

Consider the leftmost tangent from $q_{1}$ to $S$, and let $t_{1}=t_{1}(S)$ be
the tangency point. Define the point $t_{2}=t_{2}(S)$ symmetrically using the
tangent from $q_{2}$.

Tangency: The angles $\angle q_{1}pt_{1}$ and $\angle q_{2}pt_{2}$ are both
greater than $\pi/4$.

This situation is shown in Figure 2.

Figure 2: The small circle chosen in the proof of Lemma 3, and the relevant
tangent segments.

Note that any smaller circle centered at $p$ also satisfies disjointness and
tangency. We claim that any such circle intersects $C$ in a connected arc.
Without loss of generality, we prove this for $S$.

Let $q_{1}^{\prime}$ (respectively, $q_{2}^{\prime}$) be the point where the
line segment from $q_{1}$ (respectively, $q_{2}$) to $p$ crosses $S$. Note
that $S\cap C$ contains the arc between $q_{1}^{\prime}$ and $q_{2}^{\prime}$.
To see that $S\cap C$ is a connected arc, it will suffice to show that any
$q^{\prime}\in S\cap C$ is connected to $q_{1}^{\prime}$ or $q_{2}^{\prime}$
by an arc in $S\cap C$.

Let $q^{\prime}\in S\cap C$, and suppose that $q^{\prime}$ does not lie
between $q_{1}^{\prime}$ and $q_{2}^{\prime}$. By the choice of $q_{1}$ and
$q_{2}$, the point $q^{\prime}$ is at the angle at most $\pi/4$ away from
either $q_{1}^{\prime}$ or $q_{2}^{\prime}$. Consider the first case (the
other case being symmetric), i.e., $q^{\prime}$ is to the left of
$q_{1}^{\prime}$. Since the angle $\angle q_{1}pq^{\prime}$ is at most
$\pi/4$, and the angle $\angle q_{1}pt_{1}$ exceeds $\pi/4$, the point
$q^{\prime}$ lies in the cone bound by rays $\overrightarrow{pq_{1}}$ and
$\overrightarrow{pt_{1}}$. Since the line $q_{1}q^{\prime}$ intersects $S$, it
follows that $q^{\prime}$ in fact lies inside the triangle $\bigtriangleup
pq_{1}t_{1}$. From this it follows that the triangle $\bigtriangleup
pq_{1}q^{\prime}$ is contained in $\bigtriangleup pq_{1}t_{1}$, and so the
angle $\angle pq^{\prime}q_{1}$ is at least $\angle pt_{1}q_{1}=\pi/2$. From
this it follows that the line segment $q_{1}q^{\prime}$ intersects $S$ only in
$q^{\prime}$, and so its radial projection from $p$ onto $S$ is contained in
$S\cap C$. The projection is the desired arc from $q^{\prime}$ to
$q_{1}^{\prime}$ in $S\cap C$. ∎

a) Before$p$$B$$C$b) After$p$$B$$C$ Figure 3: Simplification of a convex set
$C$ in the neighborhood of a point $p$.

For a set $A\subseteq\mathbb{R}^{d}$ and a point $p\in\mathbb{R}^{d}$, the
_cone over $A$ with apex $p$_ is

$\operatorname{cone}_{p}(A)\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\\{\alpha p+(1-\alpha)x\mid 0\leq\alpha\leq 1\text{ and }x\in
A\\}\cup\\{p\\}.$

######  Definition 4.

Let $C\subseteq\mathbb{R}^{2}$ be a compact convex set, and let $p$ be a
boundary point of $C$. Let $B$ be a closed ball centered at $p$, and let
$\partial B$ be the boundary of $B$. The _simplification_ of $C$ relative to
$B$ is the set

$\operatorname{sim}_{B}(C)\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}(C\setminus B)\cup\operatorname{cone}_{p}(\partial B\cap C).$

######  Lemma 5.

Let $B,C$ and $p$ be as in Definition 4. If $\partial B\cap C$ is a connected
arc, then $\operatorname{sim}_{B}(C)$ is the convex hull of
$\\{p\\}\cup(C\setminus\operatorname{int}B)$.

###### Proof.

The definition of $\operatorname{sim}_{B}(C)$ implies that
$\operatorname{sim}_{B}(C)\subseteq\operatorname{conv}\bigl{(}\\{p\\}\cup(C\setminus\operatorname{int}B)\bigr{)}$.
To show the reverse inclusion it is enough to argue that
$\operatorname{sim}_{B}(C)$ is convex. To that end, let
$p_{1},p_{2}\in\operatorname{sim}_{B}(C)$ be arbitrary, and consider two
cases, according to how the line segment $p_{1}p_{2}$ is situated in relation
to $\operatorname{sim}_{B}(C)$. For brevity, denote the arc $\partial B\cap C$
by $A$.

Suppose that both $p_{1}$ and $p_{2}$ lie in $\operatorname{cone}_{p}(A)$: If
one of them is $p$, the line segment $p_{1}p_{2}$ is contained in
$\operatorname{sim}_{B}(C)$ by definition. Otherwise, neither is equal to $p$
and we may consider the points $p_{1}^{\prime}$ and $p_{2}^{\prime}$ obtained
by projecting $p_{1}$ and $p_{2}$ radially onto $\partial B$ from $p$. Since
$p$ lies on the boundary of $C$, the angular measure of the arc $A$ is at most
$\pi$. As both $p_{1}^{\prime}$ and $p_{2}^{\prime}$ lie in $A$, this implies
that the radial projection of the line segment $p_{1}p_{2}$ onto $\partial B$
is an arc in $A$ connecting $p_{1}^{\prime}$ to $p_{2}^{\prime}$. So, the line
segment $p_{1}p_{2}$ lies in $\operatorname{sim}_{B}(C)$.

Suppose one of $p_{1}$ and $p_{2}$ does not lie in
$\operatorname{cone}_{p}(A)$: The line segment $p_{1}p_{2}$ lies in $C$, and
so we need prove only that any portion of it that lies in $B$ also lies in
$\operatorname{cone}_{p}(A)$. Note that if $p_{1}p_{2}\cap B$ is nonempty,
then it is a line segment whose endpoints lie in $\operatorname{cone}_{p}(A)$.
In our analysis of the first case, we showed that such a line segment is
contained in $\operatorname{cone}_{p}(A)$. Hence $p_{1}p_{2}$ is contained in
$\operatorname{sim}_{B}(C)$ and the result follows. ∎

######  Proposition 6.

Let $\mathcal{X}=(X_{1},\ldots,X_{n})$ be a tuple of compact convex sets in
$\mathbb{R}^{2}$, and let $P$ be a finite system of representatives for
$\mathcal{X}$. If $\mathcal{Y}=(Y_{1},\ldots,Y_{n})$ is an inclusion-minimal
realization of $\operatorname{code}(\mathcal{X})$ as in Lemma 2, then each
$Y_{i}$ is a polygon.

###### Proof.

Recall that $x$ is an _extreme point_ of a convex set $C$ if $x$ is not
contained in $\operatorname{conv}(C\setminus\\{x\\})$. Every compact convex
set is the convex hull of its extreme points, and so it will suffice to show
that every $Y_{i}$ has finitely many extreme points. Suppose for contradiction
that some $Y_{i}$ has infinitely many extreme points. Each extreme point must
lie on the boundary of $Y_{i}$, and since the boundary is compact there must
exist a point $p$ on the boundary of $Y_{i}$ which is a limit point of the
extreme points of $Y_{i}$.

Choose a closed ball $B$ centered at $p$ whose radius is small enough as to
satisfy the following four conditions:

  * •

$B$ is disjoint from $\partial Y_{j}$ unless $p\in\partial Y_{j}$,

  * •

if $Y_{j}$ has a non-empty interior and $p\in\partial Y_{j}$ then $B$
satisfies the conclusion of Lemma 3, i.e., $\partial B\cap Y_{j}$ is a
connected arc spanning an angle of no more than $\pi$,

  * •

if $Y_{j}$ is a line segment containing $p$, the set $\partial B\cap Y_{j}$
contains at least one point,

  * •

$B$ is disjoint from $P\setminus\\{p\\}$.

Now let $\mathcal{Y}^{\prime}=(Y_{1}^{\prime},\ldots,Y_{n}^{\prime})$ where

$Y_{j}^{\prime}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\begin{cases}Y_{j}&\text{if $p\notin\partial Y_{j}$},\\\
\operatorname{sim}_{B}(Y_{j})&\text{if $p\in\partial Y_{j}$}.\end{cases}$

Note that if $Y_{j}$ is a line segment, then $\partial Y_{j}=Y_{j}$ and so
$Y_{j}^{\prime}=\operatorname{sim}_{B}(Y_{j})$. Clearly
$Y_{j}^{\prime}\subseteq Y_{j}$ for every $j\in[n]$. Moreover, the
simplification $Y_{i}^{\prime}=\operatorname{sim}_{B}(Y_{i})$ is a proper
subset of $Y_{i}$ as $p$ is no longer a limit point of the extreme points.

We claim that $\mathcal{Y}^{\prime}$ is a closed convex realization of
$\operatorname{code}(\mathcal{Y})$. Observe that each $Y_{j}^{\prime}$ is
compact and convex, for the sets $\operatorname{sim}_{B}(Y_{j})$ are convex
hulls of compact sets by Lemma 5. It remains to argue that
$\operatorname{code}(\mathcal{Y}^{\prime})=\operatorname{code}(\mathcal{Y})$.
For this, consider any point $q\in\mathbb{R}^{d}$. If $q\notin B$ or $q=p$,
then clearly
$\operatorname{patt}_{\mathcal{Y}^{\prime}}(q)=\operatorname{patt}_{\mathcal{Y}}(q)$.
Otherwise, consider the radial projection centered at $p$ onto $\partial B$.
Let $q^{\prime}\in\partial B$ be the projection of the point $q$. From the
definition of simplification, $q\in Y_{j}^{\prime}$ if and only if
$q^{\prime}\in Y_{j}$. Thus we have
$\operatorname{patt}_{\mathcal{Y}^{\prime}}(q)=\operatorname{patt}_{\mathcal{Y}}(q^{\prime})$,
and
$\operatorname{code}(\mathcal{Y}^{\prime})\subseteq\operatorname{code}(\mathcal{Y})$.
For the reverse containment, recall that $B$ avoids our system of
representatives for $\mathcal{Y}$, except possibly $p$. The intersection
pattern at $p$ is the same in $\mathcal{Y}^{\prime}$ as in $\mathcal{Y}$, so
every codeword of $\operatorname{code}(\mathcal{Y})$ appears in
$\operatorname{code}(\mathcal{Y}^{\prime})$. Thus
$\operatorname{code}(\mathcal{Y}^{\prime})=\operatorname{code}(\mathcal{Y})$.
However, $\mathcal{Y}^{\prime}$ satisfies (i), (ii) and (iii) of Lemma 2, and
so the fact that $Y_{i}^{\prime}$ is a proper subset of $Y_{i}$ contradicts
our choice of $\mathcal{Y}$ as an inclusion-minimal realization. Thus
$\mathcal{Y}$ must be polygonal, and the result follows. ∎

## Step 3: Bounding the number of vertices

Our main task in this section is to prove the first part of Theorem 1, which
says that every convex code admitting a closed $2$-realization admits a
polygonal realization in which the number of vertices is bounded by an
explicit function of the code size. Indeed, one can express the question of
whether a convex code $\mathcal{C}$ is $2$-realizable by polygons with at most
$m$ vertices as a sentence in the language of fields. As the theory of real
closed fields is decidable (originally shown by Tarski [12], see for example
[1] for a modern exposition), this will imply Theorem 1.

Let $\mathcal{X}=(X_{1},X_{2},\dotsc,X_{n})$ be a closed $2$-realization of a
convex code $\mathcal{C}$. Let $P$ be a set of representatives for
$\mathcal{X}$ of size $\lvert P\rvert\leq 2^{n}$. We may assume that
$\mathcal{X}$ is inclusion-minimal with respect to $P$, as in Lemma 2, which
by Proposition 6 implies that each $X_{i}$ is a closed polygon. We shall show
that, if $\mathcal{X}$ has too many vertices, then we may shrink $\mathcal{X}$
by pulling a vertex inward. As $\mathcal{X}$ is inclusion-minimal, a bound on
the number of vertices will follow.

### Locating good vertices.

The boundary of each $X_{i}$ is made of _vertices_ and _edges_ that join them.
We adopt the convention that the edges are open, i.e., _edges do not contain
their endpoints_. A point $p$ is _good_ with respect to $(X_{1},\dotsc,X_{n})$
if $p$ does not lie on an edge of any $X_{i}$. A point $p$ is _very good_ with
respect to $(X_{1},\dotsc,X_{n})$ if it is good and $p\notin
X_{1}\setminus\operatorname{vertices}(X_{1})$.

######  Lemma 7.

Suppose $X_{1},\dotsc,X_{n}$ are convex polygons in $\mathbb{R}^{2}$ and
$X_{1}$ has $K$ vertices. Then there is $j$ such that $X_{j}$ contains at
least $\frac{1}{3^{n-1}(n-1)!}K$ very good vertices with respect to the tuple
$(X_{1},\dotsc,X_{n})$.

###### Proof.

We argue by induction on $n$. The base case $n=1$ is trivial, so assume that
$n\geq 2$. If at least $\frac{1}{3^{n-1}(n-1)!}K$ vertices of $X_{1}$ are
good, then we are done with $j=1$. Otherwise, let $B$ be the set of all bad
vertices in $X_{1}$. Note that $\lvert
B\rvert\geq\bigl{(}1-\frac{1}{3^{n-1}(n-1)!}\bigr{)}K\geq\tfrac{2}{3}K$. For
each $i\neq 1$, let $B_{i}$ be the set of those points in $B$ that lie on some
edge of $X_{i}$. Since $B=\bigcup_{i\geq 2}B_{i}$, it follows from the
pigeonhole principle that one of $B_{2},\dotsc,B_{n}$ is large. Say, without
loss of generality, that $\lvert B_{2}\rvert\geq\tfrac{2}{3}K/(n-1)$.

Figure 4: Associating bad vertices of $X_{1}$ to vertices of $X_{2}^{\prime}$.

For each $v\in B_{2}$ choose a direction for which $v$ is an extremal point of
$X_{1}$. Let $u(v)$ be the vertex of
$X_{2}^{\prime}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\operatorname{conv}(X_{1}\cup X_{2})$ that is extremal for this
direction (if there are two such vertices, pick arbitrarily). Note that $u(v)$
is a vertex of $X_{2}$ that lies between two consecutive intersection points
of $\partial X_{1}$ with $\partial X_{2}$. So, the map $v\mapsto u(v)$ from
$B_{2}$ to $\operatorname{vertices}(X_{2}^{\prime})$ is at most two-to-one.
See Figure 4.

It follows that the polygon $X_{2}^{\prime}$ has at least $\lvert
B_{2}\rvert/2\geq K/3(n-1)$ vertices. By the induction hypothesis applied to
the $(n-1)$-tuple $(X_{2}^{\prime},X_{3},X_{4},\dotsc,X_{n})$ there is a
$j\in\\{2,3,\dotsc,n\\}$ and a set of $\frac{1}{3^{n-2}(n-2)!}\cdot K/3(n-1)$
very good vertices in $X_{j}$ (if $j>2$) or $X_{2}^{\prime}$ (if $j=2$) with
respect to this $(n-1)$-tuple. Since $\frac{1}{3^{n-2}(n-2)!}\cdot
K/3(n-1)=\frac{1}{3^{n-1}(n-1)!}K$, the proof is complete. ∎

######  Corollary 8.

Suppose $\mathcal{X}=(X_{1},\dotsc,X_{n})$ is an $n$-tuple of convex polygons
in the plane, and $P$ is a finite set of representatives for $\mathcal{X}$. If
one of $X_{1},\dotsc,X_{n}$ has more than $3^{n}(n-1)!\lvert P\rvert$
vertices, then there exist two distinct $v,v^{\prime}\in\mathbb{R}^{2}$ such
that

  * (i)

$v$ is a vertex of some polygon in $\mathcal{X}$, and

  * (ii)

Both $v$ and $v^{\prime}$ are good with respect to $\mathcal{X}$, and

  * (iii)

$v,v^{\prime}\notin P$, and

  * (iv)

$\operatorname{patt}_{\mathcal{X}}(v)=\operatorname{patt}_{\mathcal{X}}(v^{\prime})$.

###### Proof.

By the previous lemma, some $X_{j}$ contains more than $3\lvert P\rvert$ good
vertices with respect to $\mathcal{X}$. More than $2\lvert P\rvert$ among them
satisfy (iii). By the pigeonhole principle, a pair satisfies (iv) as well. ∎

### Pulling a vertex.

Let $\mathcal{X}$, $v$ and $v^{\prime}$ be as in Corollary 8. We will argue
that $\mathcal{X}$ is not inclusion-minimal. By permuting the polygons in
$\mathcal{X}$, we may assume that $v$ is a vertex of
$X_{1},X_{2},\dotsc,X_{m}$ and is not a vertex of $X_{m+1},\dotsc,X_{n}$, for
some $m\geq 1$. Let $B$ be a ball around $v$ small enough so that the only
polygon vertex inside $B$ is $v$. We shall shrink each of
$X_{1},X_{2},\dotsc,X_{m}$ by modifying inside $B$. Specifically, move the
vertex $v$ slightly toward $v^{\prime}$ along the line segment $vv^{\prime}$
to obtain a new vertex $\tilde{v}$. Then, for each $i\in[m]$, let $a_{i}$ and
$b_{i}$ be the intersection points between the boundaries of $X_{i}$ and $B$.
If $X_{i}$ is a line segment, then the points $a_{i}$ and $b_{i}$ are equal.
Let $\widetilde{X}_{i}$ be obtained from $X_{i}$ by replacing the line
segments $a_{i}v$ and $b_{i}v$ with $a_{i}\tilde{v}$ and $b_{i}\tilde{v}$
respectively.

$a_{i}$$b_{i}$$X_{i}$$v^{\prime}$$B$$v$a)
Before$a_{i}$$b_{i}$$\widetilde{X}_{i}$$v^{\prime}$$B$$\tilde{v}$b) After
Figure 5: Pulling the vertex $v$ toward $v^{\prime}$ in $X_{i}$.

Since
$\operatorname{patt}_{\mathcal{X}}(v)=\operatorname{patt}_{\mathcal{X}}(v^{\prime})$
and $v\in X_{1},\dotsc,X_{m}$, it follows that $v^{\prime}\in
X_{1},\dotsc,X_{m}$ as well. Thus, the sets
$\widetilde{X}_{1},\dotsc,\widetilde{X}_{m}$ are convex as long as $\tilde{v}$
is a sufficiently small perturbation of $v$. Now consider the tuple
$\widetilde{X}=(\widetilde{X}_{1},\dotsc,\widetilde{X}_{m},X_{m+1},\dotsc,X_{n})$.
Note that we may obtain $B\cap\widetilde{X}_{1},\dotsc,B\cap\widetilde{X}_{m}$
from $B\cap X_{1},\dotsc,B\cap X_{m}$ by a continuously deforming $B$ while
keeping its boundary fixed. Hence, the $m$-tuples $B\cap X_{1},\dotsc,B\cap
X_{m}$ and $B\cap\widetilde{X}_{1},\dotsc,B\cap\widetilde{X}_{m}$ realize the
same convex code. Furthermore, since the vertex $v$ is good, the ball $B$ can
be chosen so small that that it does not intersect the boundary of
$X_{m+1},X_{m+2},\dotsc,X_{n}$, and so
$\operatorname{code}(\mathcal{X})=\operatorname{code}(\mathcal{X}^{\prime})$.
As $P\cap B=\emptyset$ for sufficiently small $B$, we conclude that
$\mathcal{X}$ is not inclusion-minimal.

We immediately obtain the following corollary.

######  Corollary 9.

Let $\mathcal{Y}$ be an inclusion-minimal $2$-realization of a convex code on
$[n]$ with respect to a set of representatives $P$, as in Lemma 2. Then each
set in $\mathcal{Y}$ is a polygon with no more than $3^{n}(n-1)!|P|$ vertices.

As we may choose $|P|\leq 2^{n}$, we conclude that every convex code that
admits a closed convex realization in the plane admits a realization by
polygons with at most $6^{n}(n-1)!$ vertices each.

### Closed $2$-realizability is decidable.

Let $N=6^{n}(n-1)!$. Every polygon with at most $N$ vertices is an
intersection of $N$ closed halfspaces. Writing a polygon $X_{i}$ as
$\bigcap_{j=1}^{N}\\{a_{i,j}x+b_{i,j}y\leq c_{i,j}\\}$ with
$a_{i,j},b_{i,j},c_{i,j}\in\mathbb{R}$, we can write a formula asserting that
a point $(x,y)$ is in $X_{i}$,

$\Psi_{i}(\vec{a},\vec{b},\vec{c},x,y)\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\forall j\in[N]\,(a_{i,j}x+b_{i,j}y\leq c_{i,j}),$

where we abbreviated $\vec{a}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}(a_{i,j})_{i\in[n],j\in[N]}$, and similarly for $\vec{b}$ and
$\vec{c}$. We can then write a formula asserting that
$S\in\operatorname{code}(X_{1},\dotsc,X_{n})$,

$\Phi(S;\vec{a},\vec{b},\vec{c}\,)\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\exists x,y\,\forall i\in[n]\Big{(}i\in
S\,\Leftrightarrow\,\Psi_{i}(\vec{a},\vec{b},\vec{c},x,y)\Big{)}.$

We can also write a formula asserting that $X_{i}$ is bounded,

$\Gamma_{i}(\vec{a},\vec{b},\vec{c}\,)\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\exists
r\,\Bigl{(}x^{2}+y^{2}>r\implies\neg\Psi_{i}(\vec{a},\vec{b},\vec{c},x,y)\Bigr{)}.$

Then the assertion that a convex code $\mathcal{C}\subseteq 2^{[n]}$ admits a
closed $2$-realization can be written as

$\exists\vec{a},\vec{b},\vec{c}\bigwedge_{i\in[n]}\Gamma_{i}(\vec{a},\vec{b},\vec{c}\,)\wedge\bigwedge_{S\in\mathcal{C}}\Phi(S;\vec{a},\vec{b},\vec{c}\,)\wedge\bigwedge_{S\notin\mathcal{C}}\neg\Phi(S;\vec{a},\vec{b},\vec{c}\,).$

As mentioned above, the theory of real closed fields is decidable, and hence
so is the question of whether a convex code admits a closed $2$-realization.

######  Remark 10.

Kunin, Lienkaemper and Rosen [8] were the first to explain that, for any fixed
computable function of $n$ and $d$, there is an algorithm to decide whether a
convex code has a polytopal $d$-realization with the total number of vertices
bounded by this function (in fact they considered a bound on the number of
facets, but this is the same up to a slight modification of the computable
function in question). Seeking a combinatorial argument that $d$-realizability
is decidable, they reduced the problem of finding a $d$-realization with a
bounded number of vertices to the problem of determining whether certain
oriented matroids are representable. We have opted for the direct statements
above, since deciding representability of oriented matroids is complete with
respect to the theory of real closed fields, and hence the reduction to
oriented matroids does not improve the computational complexity of the
decision problem.

## Bonus: From closed to open realizations

In this section we will prove the second part of Theorem 1. We first show that
when we replace sets by their closures in an open realization, new codewords
can only arise inside convex regions with empty interior.

######  Lemma 11.

Let $\mathcal{U}=(U_{1},\ldots,U_{n})$ be a tuple of convex sets in
$\mathbb{R}^{d}$, and define $\mathcal{X}=(X_{1},\ldots,X_{n})$ where
$X_{i}\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}\operatorname{cl}U_{i}$.
If
$c\in\operatorname{code}(\mathcal{X})\setminus\operatorname{code}(\mathcal{U})$,
then $\bigcap_{i\in c}X_{i}$ has empty interior.

###### Proof.

Suppose for contradiction that there exists
$c\in\operatorname{code}(\mathcal{X})\setminus\operatorname{code}(\mathcal{U})$
so that $U\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\operatorname{int}\left(\bigcap_{i\in c}X_{i}\right)$ is nonempty.
Let $p\in U$, and let $q$ be a point with
$\operatorname{patt}_{\mathcal{X}}(q)=c$. Since $q\in\bigcap_{i\in c}X_{i}$,
the line segment $pq$ is contained in $U$ except possibly for the point $q$.
Since all $X_{i}$ are closed, $q$ lies a positive distance from $X_{i}$ for
all $i\notin c$. Hence we may choose $q^{\prime}\in U$ on the segment $pq$ so
that $\operatorname{patt}_{\mathcal{X}}(q^{\prime})=c$. Since $U_{i}$ is
convex, $\operatorname{int}X_{i}\subseteq U_{i}$. Hence,
$q^{\prime}\in\operatorname{int}X_{i}\subseteq U_{i}$ for all $i\in c$, and so
$\operatorname{patt}_{\mathcal{U}}(q^{\prime})=c$. This contradicts the
assumption that $c\notin\operatorname{code}(\mathcal{U})$. ∎

### Reduction from open to closed realizations.

Let $\mathcal{U}=(U_{1},\ldots,U_{n})$ be a tuple of bounded convex open sets
in $\mathbb{R}^{2}$. Let $\mathcal{X}=(X_{1},\ldots,X_{n})$ be the tuple of
compact convex sets in $\mathbb{R}^{2}$ with
$X_{i}\stackrel{{\scriptstyle\mbox{\tiny def}}}{{=}}\operatorname{cl}U_{i}$
for all $i\in[n]$. For every nonempty $\sigma\subseteq[n]$ for which
$\bigcap_{i\in\sigma}X_{i}$ is nonempty but has empty interior, let
$L_{\sigma}$ be a line containing the set $\bigcap_{i\in\sigma}X_{i}$. Fix a
set of representatives $P$ for $\mathcal{X}$ with the following properties:

  1. i)

for every $c\in\operatorname{code}(\mathcal{U})$, the set $P$ contains the
vertices of a triangle contained in $\bigcap_{i\in c}U_{i}$ whose interior
contains a point $p$ with $\operatorname{patt}_{\mathcal{U}}(p)=c$,

  2. ii)

for every pair $(L_{\sigma},X_{i})$ with $L_{\sigma}\cap U_{i}\neq\emptyset$,
the set $P$ contains the vertices of a quadrilateral contained in $X_{i}$
which has one of its diagonals equal to $L_{\sigma}\cap X_{i}$.

Notice that we may guarantee

$\displaystyle|P|$
$\displaystyle\leq\lvert\operatorname{code}(\mathcal{X})\rvert+3\lvert\operatorname{code}(\mathcal{U})\rvert+4n2^{n}$
$\displaystyle\leq 2^{n}+3\cdot 2^{n}+4n2^{n}=4(n+1)2^{n}.$

Now let $\mathcal{X}^{\prime}=(X_{1}^{\prime},\ldots,X_{n}^{\prime})$ be an
inclusion-minimal realization of $\operatorname{code}(\mathcal{X})$ with
respect to the set of representatives $P$, as in Lemma 2. By Corollary 9 the
number of vertices among all $X_{i}^{\prime}$ is at most $3^{n}(n-1)!|P|\leq
4(n+1)\cdot 6^{n}(n-1)!$. Define
$\mathcal{U}^{\prime}=(U_{1}^{\prime},\ldots,U_{n}^{\prime})$ to be the tuple
with $U_{i}^{\prime}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\operatorname{int}X_{i}^{\prime}$ for all $i\in[n]$. We claim that
$\operatorname{code}(\mathcal{U}^{\prime})=\operatorname{code}(\mathcal{U})$,
which will establish the second part of Theorem 1. The relationship between
the tuples $\mathcal{U},\mathcal{X},\mathcal{X}^{\prime}$ and
$\mathcal{U}^{\prime}$ is depicted on the right.

$\textstyle{\mathcal{X}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\operatorname{incl.min.}}$$\textstyle{\mathcal{X}^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\operatorname{int}}$$\textstyle{\mathcal{U}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\operatorname{cl}}$$\textstyle{\mathcal{U}^{\prime}}$

#### The inclusion
$\operatorname{code}(\mathcal{U}^{\prime})\subseteq\operatorname{code}(\mathcal{U})$:

Note that the condition (ii) implies that

$L_{\sigma}\cap U_{i}^{\prime}=L_{\sigma}\cap U_{i}\text{ for every }i\in[n].$
(1)

Indeed, let $a,b$ be the end points of the line segment $L_{\sigma}\cap
X_{i}$. Let $c,d$ be the other two vertices of the quadrilateral from the
condition (ii). Suppose first that $p$ is an interior point of the line
segment $L_{\sigma}\cap X_{i}$. Then
$p\in\operatorname{int}\operatorname{conv}\\{a,b,c,d\\}$. Since $a,b,c,d\in
X_{i}\cap P$, it follows that $a,b,c,d\in X_{i}^{\prime}\cap P$ and hence
$p\in\operatorname{int}\operatorname{conv}\\{a,b,c,d\\}\subseteq
U_{i}^{\prime}$. Suppose next that $p$ is either $a$ or $b$. In this case,
since $U_{i}$ is open it follows that $p\notin U_{i}$. Also, $p\in\partial
X_{i}^{\prime}$ and so $p\notin U_{i}^{\prime}$. So, neither $a$ nor $b$ is in
$U_{i}^{\prime}$ implying that the intersection of the line $L_{\sigma}$ with
$U_{i}^{\prime}$ is the open line segment $(a,b)$. Because $L_{\sigma}\cap
U_{i}=(a,b)$, this proves (1).

From (1) it follows that
$\operatorname{patt}_{\mathcal{U}^{\prime}}(p)=\operatorname{patt}_{\mathcal{U}}(p)$
if $p\in L_{\sigma}$. Let $L=\bigcup_{\sigma}L_{\sigma}$ be the union of all
$L_{\sigma}$’s. It remains to show that
$\operatorname{patt}_{\mathcal{U}^{\prime}}(p)\in\operatorname{code}(\mathcal{U})$
for $p\notin L$. So, fix a point $p\notin L$, and put
$c\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\operatorname{patt}_{\mathcal{X}^{\prime}}(p)$. Since any codewords
in $\operatorname{code}(\mathcal{X})\setminus\operatorname{code}(\mathcal{U})$
arise only inside $L$ by Lemma 11, it follows any codewords in
$\operatorname{code}(\mathcal{X}^{\prime})\setminus\operatorname{code}(\mathcal{U})$
also arise only inside $L$. As $p\notin L$, this implies that
$c\in\operatorname{code}(\mathcal{U})$. So by the choice of $P$ in the
condition (i) the set $\bigcap_{i\in c}X_{i}^{\prime}$ has nonempty interior.
Let $q$ be a point in the interior of $\bigcap_{i\in c}X_{i}^{\prime}$. For
sufficiently small $\varepsilon>0$, consider the point
$p_{\varepsilon}\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}p+\varepsilon(p-q)$. Since $q\in\operatorname{int}X_{i}^{\prime}$
for every $i\in c$, it follows that $p_{\varepsilon}\in X_{i}^{\prime}$ if and
only if $p_{\varepsilon}\in\operatorname{int}X_{i}^{\prime}$, for small enough
$\varepsilon$. As $\operatorname{int}X_{i}^{\prime}=U_{i}^{\prime}$, we
conclude that
$\operatorname{patt}_{\mathcal{U}^{\prime}}(p)=\operatorname{patt}_{\mathcal{X}^{\prime}}(p_{\varepsilon})$.
Furthermore, since $p\notin L$ and $\varepsilon>0$ is small, we also have
$p_{\varepsilon}\notin L$. Again using the fact that the codewords in
$\operatorname{code}(\mathcal{X}^{\prime})\setminus\operatorname{code}(\mathcal{U})$
arise only inside $L$, we have
$\operatorname{patt}_{\mathcal{U}^{\prime}}(p)=\operatorname{patt}_{\mathcal{X}^{\prime}}(p_{\varepsilon})\in\operatorname{code}(\mathcal{U})$,
as promised.

#### The inclusion
$\operatorname{code}(\mathcal{U})\subseteq\operatorname{code}(\mathcal{U}^{\prime})$:

Let $c\in\operatorname{code}(\mathcal{U})$. Consider the point $p$ and the
triangle $\bigtriangleup$ in $\bigcap_{i\in c}U_{i}$ from the condition (i).
Since $P$ contains the vertices of $\bigtriangleup$, the same is true of the
$X_{i}^{\prime}$ for $i\in c$. Because $p\in\operatorname{int}\bigtriangleup$
it follows that $p\in U_{i}^{\prime}$ for all $i\in c$. As
$U_{i}^{\prime}\subseteq U_{i}$ for all $i\in[n]$, we also have $p\notin
U_{i}^{\prime}$ for all $i\notin c$. Therefore,
$\operatorname{patt}_{\mathcal{U}^{\prime}}(p)=\operatorname{patt}_{\mathcal{U}}(p)$,
and so $c\in\operatorname{code}(\mathcal{U}^{\prime})$.

### Open $2$-realizability is decidable.

This is similar to the decidability of closed $2$-realizability. There are two
minor differences. First, the number of polygon vertices is bounded by
$4(n+\nobreak 1)\cdot 6^{n}(n-1)!$ instead of $6^{n}(n-1)!$. Second, the
formula $\Psi_{i}$ should use strict inequalities:

$\Psi_{i}(\vec{a},\vec{b},\vec{c},x,y)\stackrel{{\scriptstyle\mbox{\tiny
def}}}{{=}}\forall j\in[N]\,(a_{i,j}x+b_{i,j}y<c_{i,j}).$

The rest of the argument is the same.

## Epilogue: comments about the general case

In this paper we restricted our attention to realizations by open or closed
bounded sets in the plane. Extending our techniques to arbitrary convex sets
in the plane does not seem to pose serious challenges, but would make the
argument more technical. However, the situation in higher dimensions appears
more difficult, perhaps fundamentally so.

For example, there exist convex sets in $\mathbb{R}^{3}$ that are not
polyhedral at a neighborhood of a point, but which cannot be made locally
polyhedral using the simpification process in Definition 4 centered at the
point. Namely, consider the set $C$, which is the convex hull of

$\\{(x,y,z)\mid z=0,x^{2}+y^{2}=1\\}\cup\\{(x,y,z)\mid y=0,x^{2}+z^{2}=1\\}.$

The set $C$ is the convex hull of two circles which pass through the point
$p=(1,0,0)$ transversely (see Figure 6). If $B$ is a small ball centered at
$p$, then $\operatorname{cone}_{p}(\partial B\cap C)$ is not even a convex
set, no matter how small $B$ is. One could attempt to remedy this by replacing
$B$ with a neighborhood of $p$ that is shaped differently than a ball, but the
fact that we need a simplification process that works simultaneously for many
sets introduces further difficulties. Even if one does obtain polytopal
realizations in higher dimensions, a computable bound on the number of
vertices is not immediate, as our Lemma 7 does not have an obvious
generalization beyond the plane.

Figure 6: A convex set in $\mathbb{R}^{3}$ that is difficult to locally
simplify.

These difficulties suggest that recognizing $3$-realizable convex codes is
harder than recognizing $2$-realizable convex codes. The results of Kunin,
Lienkaemper and Rosen [8] suggest that recognizing $2$-realizable convex codes
is already at least NP-hard. In addition, Tancer [10, Section 6] showed that
recognizing $d$-representable complexes (for any fixed $d\geq 2$) is NP-hard.
It is entirely possible that recognizing $3$-realizable convex codes is in
fact an undecidable problem.

## References

  * [1] Saugata Basu, Richard Pollack, and Marie-Françoise Roy.  Algorithms in real algebraic geometry, volume 10 of Algorithms and Computation in Mathematics.  Springer-Verlag, Berlin, 2003.
  * [2] Aaron Chen, Florian Frick, and Anne Shiu.  Neural codes, decidability, and a new local obstruction to convexity.  SIAM Journal on Applied Algebra and Geometry, 3(1):44–66, 2019\.
  * [3] Joshua Cruz, Chad Giusti, Vladimir Itskov, and Bill Kronholm.  On open and closed convex codes.  Discrete & Computational Geometry, 61:247–270, 2016.
  * [4] Carina Curto, Vladimir Itskov, Alan Veliz-Cuba, and Nora Youngs.  The neural ring: an algebraic tool for analyzing the intrinsic structure of neural codes.  Bulletin of Mathematical Biology, 75(9):1571–1611, 2013.
  * [5] Megan K. Franke and Samuel Muthiah.  Every binary code can be realized by convex sets.  Advances in Applied Mathematics, 99:83–93, 2017.
  * [6] R. Amzi Jeffs.  Open, closed, and non-degenerate embedding dimensions of neural codes.  arXiv:2111.01010, 2021.
  * [7] R. Amzi Jeffs.  Embedding dimension phenomena in intersection complete codes.  Selecta Mathematica, 28, 2022.  arXiv:1909.13406.
  * [8] Alexander Kunin, Caitlin Lienkaemper, and Zvi Rosen.  Oriented matroids and combinatorial neural codes.  2020\.  arXiv:2002.03542.
  * [9] Caitlin Lienkaemper, Anne Shiu, and Zev Woodstock.  Obstructions to convexity in neural codes.  Advances in Applied Mathematics, 85:31–59, 2017.
  * [10] Martin Tancer.  $d$-collapsibility is NP-complete for $d\geq 4$.  Chic. J. Theoret. Comput. Sci., pages Article 3, 32, 2010.
  * [11] Martin Tancer.  Intersection patterns of convex sets via simplicial complexes: a survey.  In Thirty essays on geometric graph theory, pages 521–540. Springer, New York, 2013.  arXiv:1102.0417.
  * [12] Alfred Tarski.  A decision method for elementary algebra and geometry.  University of California Press, Berkeley-Los Angeles, Calif., 1951.  2nd ed.