# Resonant and off-resonant magnetoacoustic waves in epitaxial Fe3Si/GaAs
hybrid structures

Marc Rovirola  Dept. of Condensed Matter Physics, University of Barcelona,
08028 Barcelona, Spain  Institut de Nanociència i Nanotecnologia (IN2UB),
University of Barcelona, 08028 Barcelona, Spain  M. Waqas Khaliq  Dept. of
Condensed Matter Physics, University of Barcelona, 08028 Barcelona, Spain
ALBA Synchrotron Light Source, 08290 Cerdanyola del Vallès, Spain  Blai Casals
Dept. of Condensed Matter Physics, University of Barcelona, 08028 Barcelona,
Spain  Institut de Nanociència i Nanotecnologia (IN2UB), University of
Barcelona, 08028 Barcelona, Spain  Michael Foerster  ALBA Synchrotron Light
Source, 08290 Cerdanyola del Vallès, Spain  Miguel Angel Niño  ALBA
Synchrotron Light Source, 08290 Cerdanyola del Vallès, Spain  Jens Herfort
Paul-Drude-Institut für Festkörperelektronik, Leibniz-Institut im
Forschungsverbund Berlin e.V., Hausvogteiplatz 5-7, 10117 Berlin, Germany
Joan Manel Hernàndez  Dept. of Condensed Matter Physics, University of
Barcelona, 08028 Barcelona, Spain  Institut de Nanociència i Nanotecnologia
(IN2UB), University of Barcelona, 08028 Barcelona, Spain  Ferran Macià
<EMAIL_ADDRESS>Dept. of Condensed Matter Physics, University of
Barcelona, 08028 Barcelona, Spain  Institut de Nanociència i Nanotecnologia
(IN2UB), University of Barcelona, 08028 Barcelona, Spain  Alberto Hernández-
Mínguez  Paul-Drude-Institut für Festkörperelektronik, Leibniz-Institut im
Forschungsverbund Berlin e.V., Hausvogteiplatz 5-7, 10117 Berlin, Germany

###### Abstract

Surface acoustic waves (SAWs) provide an efficient dynamical coupling between
strain and magnetization in micro/nano-metric devices. Using a hybrid device
composed of a piezoelectric, GaAs, and a ferromagnetic Heusler alloy thin
film, Fe3Si, we are able to quantify the amplitude of magnetoacoustic waves
generated with SAWs via magnetic imaging in an X-ray photoelectron microscope.
The cubic anisotropy of the sample together with a low damping coefficient
allows for the observation of resonant and non-resonant magnetoelastic
coupling. Additionally, via micromagnetic simulation, we verify the
experimental behavior and quantify the magnetoelastic shear strain component
in Fe3Si that appears to be very large ($b_{2}=14\times 10^{6}$ J/m3), much
larger than the one found in Nickel.

††preprint: APS/123-QED

##  I  Introduction

The use of charge carriers for information transport has proven to be
successful, but current technology is reaching its limitations and the growing
need for smaller, faster, and more efficient information processing units
calls for new data carriers. One of the solutions compatible with existing
technology and involving low-energy dissipation are spin waves— collective
excitation of magnetic order. However, generation, detection, and manipulation
of spin waves are still the focus of many studies due to the multiple
interactions that these magnetization modes have with other degrees of freedom
such as phonons or photons [1, 2].

The coupling between strain and magnetization—the magnetoelastic (ME)
effect—can be used to generate magnetization dynamics at the nanoscale with
low-power dissipation through surface acoustic waves (SAW) [3, 4, 5, 6, 7, 8,
9]. The interaction between SAW and magnetization dynamics has long been
studied [10, 11, 12, 13, 14, 15, 16, 17, 9, 18, 19] and there are clear
experiments showing the variation of magnetic states caused by SAW and,
reversibly, changes in SAW propagation are observed due to the action of
magnetization dynamics. SAW-induced magnetization waves including
magnetoacoustic switching might occur at magnetic resonances [12, 13, 14, 17,
4, 15] but there is no clear picture of what type of magnetoacoustic waves
might be generated, if any, when magnetic and acoustic systems are in a non-
resonance condition. Imaging techniques capable of quantifying both SAW and
magnetization dynamics are required to fully explore the interaction of hybrid
modes of magnetoacoustic waves generated by SAW.

The coherent transport of spin waves up to micrometers is a requirement for
processing units and for that reason finding materials with low damping
coefficients is critical. Materials such as nickel have a large ME effect,
which makes them ideal for generating strain-induced spin waves, but display a
large damping coefficient in the order of $10^{-3}$ [20] causing shorter
propagation distances and broad resonance peaks. On the contrary, Yttrium Iron
Garnet (YIG) has a damping coefficient in the order of $10^{-4}$ [20], but
high-quality growth is challenging and it is a weak magnetoelastic material.
Epitaxial Heusler alloys are promising alternatives due to their properties,
including low spin-wave damping, half-metallicity, and compatibility with CMOS
technology [21, 22, 23, 24, 25, 26, 27]. Specifically, Fe3Si films grown
epitaxially on GaAs have been reported having a damping coefficient as low as
$3\times 10^{-4}$ [28] and a large ME effect due to its large magnetoelastic
constant $b_{2}$ [29].

In this article, we study the acoustic excitation of spin waves in samples
consisting of a piezoelectric GaAs substrate with interdigital transducers
(IDTs) for the generation of SAW, and a ferromagnetic Fe3Si thin film on the
SAW acoustic path (see Fig. 1). The high structural quality of Fe3Si leads to
very narrow ferromagnetic resonance (FMR) peaks indicative of low Gilbert
damping ($\alpha\simeq 0.005$) and, therefore, to a large coherent length of
the spin wave. To quantify the spin waves, direct imaging through X-ray
microscopy of both SAW and magnetization waves is taken at different magnetic
fields, and we find that magnetoacoustic waves are generated in a wide range
of fields, showing that resonance is not an essential condition to generate
magnetoacoustic waves.

The article is organized as follows. Section II describes the sample
fabrication process and the experimental procedures. Section III is divided
into two parts: first, the experimental results, beginning with the
characterization of the sample via FMR and SAW transmission, and then the
analysis of direct imaging of both SAW and magnetic waves. Second,
micromagnetic simulations are shown to further verify and quantify the
magnetoelastic constants of the sample and support the idea that
magnetoacoustic waves can also exist at non-resonance conditions. Lastly,
Section IV presents the conclusions on the results.

##  II Experimental details

Figure 1:  (a) Schematic set-up of the hybrid device, where a cross-shaped
Heusler alloy film (Fe3Si) is deposited on top of a GaAs substrate with
interdigital transducers (IDTs) on both sides. The top left corner shows the
coordinates of the sample, where $x$ and $y$ are the easy axes, while $X$ and
$Y$ are the hard axes. IDT 1 is excited with an RF signal at 500 MHz to excite
SAW and the X-rays are sent perpendicular to the SAW propagation direction.
The top right corner shows the equilibrium magnetization and magnetic field
directions with angles $\varphi_{0}$ and $\varphi_{\mathrm{H}}$ respectively.
(b) Transmission coefficient between the two IDTs, $S_{21}$, as a function of
the RF frequency, applied to IDT 1. The arrow points to the highest
transmission and fundamental frequency of IDT 1 at 500 MHz. (c) Schematic
representation of the magnetization precession in the Fe3Si film with the SAW
propagating in the $X$ direction and the X-rays in the $Y$ direction. The
dashed lines that stretch in the $Y$ direction show the magnetic signal that
is captured by XMCD.

The studied sample is a 74-nm-thick Fe3Si film grown by molecular beam epitaxy
on a piezoelectric, GaAs (001)[21]. The fabrication of the magnetoacoustic
device begins by selective patterning of the Fe3Si film into cross-shaped
structures by electron beam lithography and plasma etching. Pairs of IDTs are
deposited on opposite sides of patterned Fe3Si film by electron beam
lithography, metal evaporation, and liftoff (see Fig. 1), thus allowing for
both the generation of SAWs that propagate along the Heusler film and the
measurement of transmitted SAW power ($S_{21}$) along the acoustic path.
Figure 1(b) displays $S_{21}$ spectrum measured with a vector network
analyzer. IDTs are designed to excite Rayleigh SAW [30, 31] with a frequency
of $f_{\text{SAW}}=500$ MHz and the corresponding wavelength
$\lambda_{\text{SAW}}=5.73$ $\mu$m propagating along $X\\!\parallel\\![110]$
direction of the GaAs substrate. They are characterized by longitudinal in-
plane and out-of-plane strains $\epsilon_{XX}$ and $\epsilon_{ZZ}$,
respectively, as well as shear strain $\epsilon_{XZ}$. Due to the large
structural quality of the Fe3Si film, the magnetization displays cubic in-
plane anisotropy, with easy and hard axes being the family of planes
$\expectationvalue{100}$ and $\expectationvalue{110}$, respectively.
Therefore, the SAW propagates along one of the hard axes of the Fe3Si film,
and magnetization in the absence of a magnetic field lies along any of the
four easy axes forming 45 degrees with respect to the SAW path.

To image the sample, we used an X-ray photoemission electron microscopy
(XPEEM) set-up from the CIRCE beamline at ALBA Synchrotron with a time and
spatial resolution below 80 ps and 100 nm, respectively. The SAW frequency is
synchronized to the repetition rate of the X-ray pulses, and the SAW and
magnetization images are taken simultaneously [32, 33, 3, 7]. The sample was
mounted on a holder containing an electromagnet that can generate an in-plane
magnetic field up to $20\text{ mT}$ in the SAW propagation direction. Sending
an RF signal of the appropriate frequency to IDT 1 generates SAW in the GaAs
that may excite spin waves in the Fe3Si with the same wavelength. When the
sample and the electron microscope are kept at a large potential difference,
electrons leaving the sample due to X-rays are accelerated to the electron
microscope, but the amount of electrons captured from each position depends on
the amplitude of the piezoelectric field accompanying the SAW [33]. Therefore,
we obtain contrast images sensitive to SAW wavefronts, as seen in the inset of
Fig. 1. No SAW can be detected in Fe3Si due to its metallic nature, which
shields the dynamic piezoelectric field. However, the effect of SAW on the
magnetization in the Fe3Si can be imaged using X-ray magnetic circular
dichroism (XMCD), which consists of subtracting two otherwise identical XPEEM
images using X-rays with opposite circular polarization [34].

##  III Results

###  III.1 Experimental results

The sample was initially characterized via FMR with a broadband coplanar
waveguide capable of producing microwave magnetic fields with frequencies up
to 20 GHz [35]. Figure 2 shows the resonance fields for the uniform precession
mode (spin wave with $\textbf{q}=0$) when an in-plane magnetic field is
applied in the [110] direction (hard axis). On top of the data, we plotted
solid and dashed lines calculated from a macrospin model at several magnetic
field alignments. The model accounts for the fourfold cubic crystalline
anisotropy, and the shape anisotropy, see Refs. [27, 36]. We notice here that
a curve corresponding to a magnetic field direction that slightly deviates
$\varphi_{\mathrm{H}}\simeq 2^{\circ}$ from [110] axis fits well the
experimental data. The curve corresponding to a perfectly aligned magnetic
field, $\varphi_{\mathrm{H}}=0^{\circ}$ (continuous black curve), clearly
shows the value of the anisotropy field, $\mu_{0}H_{k}=9$ mT, that corresponds
to the magnetic field required to align the magnetization along the hard axis
(i.e., the magnetic field required to suppress the effective magnetic field).
We also measured the linewidth broadening as a function of microwave frequency
and found a value for the Gilbert damping coefficient, $\alpha=0.005$ [37], an
order of magnitude smaller than Nickel [38].

We plotted in Fig. 2 an additional dashed line representing the frequency used
in the SAW experiment (500 MHz). The crossing points between the FMR curves
and the dashed line indicate the resonance fields at which there is a maximum
energy transfer between microwave magnetic fields (from the coplanar
waveguide) and the film’s magnetization. Small deviations in the applied
magnetic field direction result in an FMR curve shift and no intersection
points—or no resonance condition [39]. This effect is studied in detail later
on with micromagnetic modeling.

Figure 2: FMR for a magnetic field applied along the [110] crystalline
direction (hard axis) with the modeling curve plotted on top as continuous,
dashed, and dotted lines for different angles of the magnetic field,
$\varphi_{H}$. The horizontal dashed line corresponds to the SAW frequency and
the arrow points to the anisotropy field (9 mT) obtained with the model. The
green curve at 4.5 GHz displays the absorption peak in the form of a
Lorentzian derivative. The inset shows SAW attenuation at 500 MHz as a
function of the magnetic field strength for different field angles,
$\varphi_{\mathrm{H}}$ between SAW and H.

To further characterize our hybrid structures, we measured SAW attenuation as
a function of the applied magnetic field along the [110] direction (see the
inset of Fig. 2). The measurement of power transmission, $S_{21}$, between two
opposite IDTs serves to investigate the ME coupling between SAW and spin waves
in our Heusler thin film. Similar to the FMR measurements, there is a sharp
absorption peak with a linewidth of approximately $1\text{ mT}$ and a strong
angular dependence [36]. A deviation of $\varphi_{\mathrm{H}}=1.5^{\circ}$ of
the magnetic field direction with respect to the [110] axis results in no
measurable power loss (see Fig. 2 inset)

Next, we turn to the main experimental results consisting of resolving in
space and time the evolution of magnetoacoustic waves in the Heusler film.
First, we characterized the strength of a 500 MHz SAW by direct XPEEM images
of the GaAs substrate. The observed SAW wave fronts in the XPEEM image (see
the left-hand side of the inset in Fig. 1) are associated with the energy
shift of secondary electrons leaving the sample surface of GaAs due to the
piezoelectric field of the SAW. The energy shift can be indeed quantified via
local photo-electron kinetic energy scan—photoemission intensity as a function
of the electron kinetic energy—[33]. The difference between both spectra taken
at the wave edges (the difference between maxima and minima) corresponds to
the peak-to-peak value and was found to be $V_{pp}=0.1\text{ V}$. By
numerically solving the coupled elastic and electromagnetic equations for a
SAW propagating along the [110] axis of GaAs [40], we estimate that the
measured piezoelectric amplitude of $V_{0}\approx V_{pp}/2\approx 0.05$ V
corresponds to strain components with amplitudes
$\varepsilon_{\mathrm{XX}}=7\cdot 10^{-5}$, $\varepsilon_{\mathrm{ZZ}}=3\cdot
10^{-5}$ and $\varepsilon_{\mathrm{XZ}}=1\cdot 10^{-7}$ at the surface of the
sample. This is almost an order of magnitude smaller than the same quantity
measured in LiNbO3 piezoelectric structures under similar SAW excitations.

Figure 3: (a) XMCD image of the magnetic domains in Fe3Si and of the SAW in
the GaAs. The magnetization direction of each domain is represented by white
and black arrows. The difference between opposing magnetic states is
represented by $\Delta m_{Y}$. (b) XMCD image with SAW in the GaAs and spin
waves in Fe3Si.

To obtain XMCD images that are proportional to the Fe3Si magnetization
component along the X-ray incidence direction, we selected the X-ray energy
for the $L_{3}$ absorption edge of Fe [34]. In our experiment, the direction
of incidence of the X-ray is along the hard axes ($Y$ axis) perpendicular to
the SAW propagation direction (see Fig. 1 (c)). Figure 3(a) shows an XMCD
image revealing magnetic domains in all four easy axis directions with a
strong contrast that allows us to quantify the overall change in magnetization
in the X-ray direction.

SAWs create a dynamic strain in the Fe3Si film that induces a time-varying
magnetic anisotropy, which eventually creates magnetoacoustic waves. The
amplitude of these magnetoacoustic waves can be seen in the XMCD image, but
with a signal of 1-2 orders of magnitude smaller compared to the magnetic
domains observed in Fig. 3(a). Figure 3(b) displays an XMCD image under a
magnetic field of $\mu_{0}H\simeq$ 10 mT, showing magnetoacoustic waves in the
Fe3Si film (there are no magnetic domains for applied fields larger than 1
mT). A remaining SAW signal in the GaAs is still visible, both in Fig. 3(a)
and (b), due to tiny temperature drifts during integration time, which make
the two XPEEM images taken for XMCD slightly different and thus not fully
canceling out the SAW component.

To study the importance of magnetic resonance condition in the generation of
magnetoacoustic waves, we measured XMCD images as a function of the applied
magnetic field similar to what we did in the FMR and SAW transmission
characterization in Fig. 2. We took XMCD images at two different areas in the
sample, P1 and P2, as shown in Fig. 1. Location P1 includes GaAs substrate and
the Fe3Si film as seen in Fig. 3(b). By fitting the magnetoacoustic wave
profile to a sinusoidal function [41], we can retrieve the amplitude and
quantify it with respect to the overall $M_{s}$ value found from the magnetic-
domain image [42]. The normalized amplitude is showcased in Fig. 4 for the two
areas and shows that, contrary to FMR and SAW transmission measurements, there
are sizable magnetoacoustic waves on a large magnetic field range with a sharp
increase around 10 mT, which is exactly the magnetic resonance field for spin
waves with $\textbf{q}=\textbf{k}_{\mathrm{SAW}}$. Thus, magnetoacoustic waves
are created with SAW even when there is no measurable power loss in FMR or SAW
transmission—and are excited more efficiently at magnetic resonance. Our
quantification of the magnetoacoustic waves gives an estimate of 0.5-1.5
degree precession of amplitude for the magnetization vector around the
equilibrium.

Figure 4:  Spin wave amplitude obtained from the XMCD images as a function of
the in-plane magnetic field at two different positions of the sample as
indicated in Fig. 1 (a).

The results of both sample locations are similar and are plotted in Fig. 4.
Two parts can be identified: the first resembles a broad inverted parabola
with its vertex close to 9 mT, and the second is a peak of 1 mT width close to
10 mT. The first part corresponds to non-resonant magnetoacoustic excitation.
In the absence of an applied magnetic field, the effective field associated
with the cubic anisotropy keeps the magnetization along the in-plane easy axes
of the Fe3Si film (as seen in the XMCD image of Fig. 3(a)). As the in-plane
magnetic field increases, it generates a torque that partially counteracts the
anisotropy, until it reaches the anisotropy field of 9 mT. At this point, the
total effective field is zero, so that the magnetization can easily respond to
the effective magnetic anisotropy created by the SAW. Increasing further the
applied magnetic field creates again an effective magnetic field that locks
the magnetization so that oscillations around the equilibrium direction become
smaller. The second part of the curve corresponds to resonance or near-
resonance effects close to 10 mT where there is an increase in the amplitude
of the magnetoacoustic waves with a width of 1 mT, matching the width of the
power loss at magnetic resonance in both FMR and SAW transmission (see Fig.
2).

###  III.2 Micromagnetic simulation

We performed micromagnetic modeling using numerical simulations with MuMax3
[43] to estimate magnetoelastic constants, $b_{1}$ and $b_{2}$, that are
associated with the interaction strength between the strain of the SAW and the
magnetization of the Fe3Si. We must also check whether the microscopic model
predicts the magnetoacoustic excitations at both resonance and non-resonance
magnetic fields. The modeling accounts for all magnetic interactions,
including dipolar, cubic anisotropies, and exchange interactions together with
time and spatially oscillating strain fields that simulate a SAW. We used the
strain field amplitudes found in Sec. III.1 and the following values for the
ferromagnetic Fe3Si film found via FMR: $M_{s}=955\times 10^{3}$ A/m,
$A_{ex}=1\times 10^{-11}$ J/m, $\alpha=0.005$ and $K_{c1}=-4400$ J/m3, where
$M_{s}$ is the saturation value of magnetization, $A_{ex}$ is the exchange
stiffness and $K_{c1}$ is the first-order anisotropy constant. The value of
$A_{ex}$ was calculated using the exchange stiffness constant $D=240$ meV
$\r{A}^{2}$ [44] and the relation $A_{ex}=DM_{s}/2g\mu_{\mathrm{B}}$ where $g$
is the Landé factor and $\mu_{\mathrm{B}}$ is the Bohr magneton. The free
energy of the magnetoelastic interaction can be written as:

$\displaystyle F_{\mathrm{me}}=$
$\displaystyle\,\,b_{1}\left[\varepsilon_{xx}m_{x}^{2}+\varepsilon_{yy}m_{y}^{2}+\varepsilon_{zz}m_{z}^{2}\right]$
$\displaystyle+2b_{2}\left[\varepsilon_{xy}m_{x}m_{y}+\varepsilon_{xz}m_{x}m_{z}+\varepsilon_{yz}m_{y}m_{z}\right],$
(1)

where $b_{1}$ and $b_{2}$ are magnetoelastic constants. The strain and
magnetization components are expressed in the coordinate system $(x,y,z)$ with
axes parallel to the $\expectationvalue{100}$ directions of the GaAs and
Fe3Si. The SAW strain components $\varepsilon_{XX}$, $\varepsilon_{ZZ}$ and
$\varepsilon_{XZ}$ are related to the strain components in the coordinate
system $(x,y,z)$ using the following formulas:

$\begin{array}[]{rl}\varepsilon_{xx}=\varepsilon_{XX}\cos^{2}\theta,&\varepsilon_{xy}=\varepsilon_{XX}\cos\theta\sin\theta,\\\
\varepsilon_{yy}=\varepsilon_{XX}\sin^{2}\theta,&\varepsilon_{xz}=\varepsilon_{XZ}\cos\theta,\\\
\varepsilon_{zz}=\varepsilon_{ZZ},&\varepsilon_{yz}=\varepsilon_{XZ}\sin\theta,\vspace{5mm}\end{array}$
(2)

where $\theta$ is the angle between the SAW propagation direction and the
coordinate system defined by the lower case letters $(x,y,z)$. The SAW strain
is modeled as a propagating wave that depends on the amplitude and propagation
direction as:

$e_{jk}=\varepsilon_{jk}\exp({i(\textbf{k}\textbf{r}-wt)})$ (3)

Figure 5: (a) Normalized magnetization components $m_{X}$ and $m_{Y}$ as a
function of the magnetic field strength for several degrees of misalignment
between the magnetic field and the SAW propagation direction. (b) Amplitude of
the normalized magnetic component $m_{Y}$ (spin wave amplitude) as a function
of the magnetic field for different angles $\varphi_{\mathrm{H}}$.

where $\varepsilon_{jk}$ is the amplitude, k and $w$ are the wave vector and
the angular frequency of the SAW, respectively. We varied the strength of the
applied magnetic field as well as the angle $\varphi_{\mathrm{H}}$ from
$0.5^{\circ}$ up to $3^{\circ}$. We also took the magnetoelastic constants
$b_{1}$ and $b_{2}$ as parameters.

The results of the simulation are summarized in Fig. 5, where the evolution of
both the equilibrium magnetization and the oscillation amplitudes are plotted
as a function of the applied magnetic field. Figure 5(a) shows the normalized
magnetization components $m_{X}$ and $m_{Y}$ and shows that, in the absence of
an applied magnetic field, the magnetization remains along the easy axis, with
each component having an amplitude of $m_{X}=m_{Y}=\cos(45^{\circ})$. As the
magnetic field increases, the magnetization rotates toward the magnetic field
(parallel to the $X$ axis) until it saturates at the anisotropy field (9 mT).
Figure 5(b) shows the amplitude of the oscillatory component
$m_{\text{osc}}$—equivalent to the component extracted from the waves in the
XMCD images—, at different angles of misalignment, $\varphi_{\mathrm{H}}$,
between SAW and applied magnetic field. The amplitude of the magnetization
oscillation has the same behavior as the one found from the XMCD experiment: a
broad peak centered at the anisotropy field $\mu_{0}H_{k}=9$ mT and a narrow 1
mT peak centered at magnetic resonance close to $\mu_{0}H=10$ mT. We notice
that as the angle of misalignment, $\varphi_{\mathrm{H}}$, increases, the
resonance peak disappears, and only the broad peak is left. The simulations
for a misalignment of $1-2^{\circ}$ match well with our data from the XMCD-
XPEEM experiment.

Finally, we investigated the dependence of the simulated curves on the values
of the magnetoelastic constants $b_{1}$ and $b_{2}$. We found that $b_{1}$ has
little effect on the amplitude of the magnetic oscillations unless $b_{2}$ is
small. Therefore, we fixed $b_{1}=5\times 10^{6}$ J/m3 and varied $b_{2}$ in
the range between 0 and $15\times 10^{6}$ J/m3. The best agreement between
simulations and experimental results are the ones shown in Fig. 5(b) and are
obtained for $b_{2}=14\times 10^{6}$ J/m3.

##  IV Conclusions

We have directly imaged and quantified magnetoacoustic waves in Fe3Si
generated with SAW. We observed that magnetoacoustic waves are generated
within a wide range of applied magnetic fields with a clear boost at magnetic
resonance. The boost at the resonance field matches the FMR and SAW-FMR
absorption peaks indicating energy transfer between the SAW and the magnetic
system. However, we clearly observed magnetoacoustic waves at non-resonance
fields—with little energy absorption. Thus, we conclude that resonance and
energy absorption techniques do not provide a full picture of existence of
magnetoacoustic waves in magnetic materials. XPEEM images allowed us to
quantify the SAW strain components, and the amplitude of the SAW-induced spin
waves was obtained from the corresponding XMCD images. Finally, through
micromagnetic simulations, we have determined the strength of the shear
magnetoelastic constant ($b_{2}=14\times 10^{6}$ J/m3) which is much larger
than the one found in Nickel ($b_{2(Ni)}=4.3\times 10^{6}$ J/m3 [45]).

###### Acknowledgements.

The authors would like to thank H.P. Schönherr and S. Meister for their
technical support in the preparation of the samples. MR, BC, JMH, MWQ and FM
acknowledge funding from MCIN/AEI/10.13039/501100011033 through grant number:
PID2020-113024GB-100. MF and MAN acknowledge funding from MCIN through grant
numbers: RTI2018-095303 and PID2021-122980OB-C5. MWK acknowledges also Marie
Skłodowska-Curie grant agreement No. 754397 (DOC-FAM) from EU Horizon 2020.

## References

  * Li  _et al._ [2020] Y. Li, W. Zhang, V. Tyberkevych, W.-K. Kwok, A. Hoffmann, and V. Novosad, Hybrid magnonics: Physics, circuits, and applications for coherent information processing, J. Appl. Phys. 128, 130902 (2020).
  * Inman  _et al._ [2022] J. Inman, Y. Xiong, R. Bidthanapally, S. Louis, V. Tyberkevych, H. Qu, J. Sklenar, V. Novosad, Y. Li, X. Zhang, and W. Zhang, Hybrid magnonics for short-wavelength spin waves facilitated by a magnetic heterostructure, Phys. Rev. Applied 17, 044034 (2022).
  * Foerster  _et al._ [2017] M. Foerster, F. Macià, N. Statuto, S. Finizio, A. Hernández-Mínguez, S. Lendínez, P. Santos, J. Fontcuberta, J. Hernàndez, M. Kläui, and L. Aballe, Direct imaging of delayed magneto-dynamic modes induced by surface acoustic waves, Nat. Commun. 8, 407 (2017).
  * Kuszewski  _et al._ [2018a] P. Kuszewski, J.-Y. Duquesne, L. Becerra, A. Lemaître, S. Vincent, S. Majrab, F. Margaillan, C. Gourdon, and L. Thevenard, Optical probing of rayleigh wave driven magnetoacoustic resonance, Phys. Rev. Applied 10, 034036 (2018a).
  * Foerster  _et al._ [2018] M. Foerster, L. Aballe, J. M. Hernàndez, and F. Macià, Subnanosecond magnetization dynamics driven by strain waves, MRS Bull. 43, 854 (2018).
  * Bertelli  _et al._ [2020] I. Bertelli, J. J. Carmiggelt, T. Yu, B. G. Simon, C. C. Pothoven, G. E. W. Bauer, Y. M. Blanter, J. Aarts, and T. van der Sar, Magnetic resonance imaging of spin-wave transport and interference in a magnetic insulator, Sci. Adv. 6, 10.1126/sciadv.abd3556 (2020).
  * Casals  _et al._ [2020] B. Casals, N. Statuto, M. Foerster, A. Hernández-Mínguez, R. Cichelero, P. Manshausen, A. Mandziak, L. Aballe, J. M. Hernàndez, and F. Macià, Generation and Imaging of Magnetoacoustic Waves over Millimeter Distances, Phys. Rev. Lett. 124, 137202 (2020).
  * Kraimia  _et al._ [2020] M. Kraimia, P. Kuszewski, J.-Y. Duquesne, A. Lemaître, F. Margaillan, C. Gourdon, and L. Thevenard, Time- and space-resolved nonlinear magnetoacoustic dynamics, Phys. Rev. B 101, 144425 (2020).
  * Labanowski  _et al._ [2018] D. Labanowski, V. P. Bhallamudi, Q. Guo, C. M. Purser, B. A. McCullian, P. C. Hammel, and S. Salahuddin, Voltage-driven, local, and efficient excitation of nitrogen-vacancy centers in diamond, Sci. Adv. 4 (2018).
  * Hernandez  _et al._ [2006] J. Hernandez, P. Santos, F. Macià, A. García-Santiago, and J. Tejada, Acoustomagnetic pulse experiments in LiNbO3/Mn12 hybrids, Appl. Phys. Lett. 88, 012503 (2006).
  * Davis  _et al._ [2010] S. Davis, A. Baruth, and S. Adenwalla, Magnetization dynamics triggered by surface acoustic waves, Appl. Phys. Lett. 97, 232507 (2010).
  * Weiler  _et al._ [2011] M. Weiler, L. Dreher, C. Heeg, H. Huebl, R. Gross, M. S. Brandt, and S. T. B. Goennenwein, Elastically driven ferromagnetic resonance in nickel thin films, Phys. Rev. Lett. 106, 117601 (2011).
  * Weiler  _et al._ [2012] M. Weiler, H. Huebl, F. S. Goerg, F. D. Czeschka, R. Gross, and S. T. B. Goennenwein, Spin pumping with coherent elastic waves, Phys. Rev. Lett. 108, 176601 (2012).
  * Gowtham  _et al._ [2015] P. G. Gowtham, T. Moriyama, D. C. Ralph, and R. A. Buhrman, Traveling surface spin-wave resonance spectroscopy using surface acoustic waves, J. Appl. Phys. 118, 233910 (2015).
  * Labanowski  _et al._ [2016] D. Labanowski, A. Jung, and S. Salahuddin, Power absorption in acoustically driven ferromagnetic resonance, Appl. Phys. Lett. 108, 022905 (2016).
  * Thevenard  _et al._ [2016] L. Thevenard, I. S. Camara, S. Majrab, M. Bernard, P. Rovillain, A. Lemaître, C. Gourdon, and J.-Y. Duquesne, Precessional magnetization switching by a surface acoustic wave, Phys. Rev. B 93, 134430 (2016).
  * Kuszewski  _et al._ [2018b] P. Kuszewski, I. S. Camara, N. Biarrotte, L. Becerra, J. von Bardeleben, W. S. Torres, A. Lemaître, C. Gourdon, J.-Y. Duquesne, and L. Thevenard, Resonant magneto-acoustic switching: influence of rayleigh wave frequency and wavevector, J. Phys. Condens. Matter 30, 244003 (2018b).
  * Foerster and Macià [2019] M. Foerster and F. Macià, Preface to special issue on magneto-elastic effects, J. Phys. Condens. Matter 31, 190301 (2019).
  * Puebla  _et al._ [2022] J. Puebla, Y. Hwang, S. Maekawa, and Y. Otani, Perspectives on spintronics with surface acoustic waves, Applied Physics Letters 120, 220502 (2022), https://doi.org/10.1063/5.0093654 .
  * Schmidt  _et al._ [2020] G. Schmidt, C. Hauser, P. Trempler, M. Paleschke, and E. T. Papaioannou, Ultra thin films of yttrium iron garnet with very low damping: A review, Phys. Status Solidi (b) 257, 1900644 (2020).
  * Herfort  _et al._ [2005] J. Herfort, H.-P. Schönherr, A. Kawaharazuka, M. Ramsteiner, and K. Ploog, Epitaxial growth of Fe3Si/GaAs(001) hybrid structures for spintronic application, J. Cryst. Growth 278, 666 (2005), 13th International Conference on Molecular Beam Epitaxy.
  * Ionescu  _et al._ [2005] A. Ionescu, C. A. F. Vaz, T. Trypiniotis, C. M. Gürtler, H. García-Miquel, J. A. C. Bland, M. E. Vickers, R. M. Dalgliesh, S. Langridge, Y. Bugoslavsky, Y. Miyoshi, L. F. Cohen, and K. R. A. Ziebeck, Structural, magnetic, electronic, and spin transport properties of epitaxial ${\mathrm{Fe}}_{3}\mathrm{Si}/\mathrm{GaAs}(001)$, Phys. Rev. B 71, 094401 (2005).
  * Herfort  _et al._ [2003] J. Herfort, H.-P. Schönherr, and K. H. Ploog, Epitaxial growth of Fe3Si/GaAs(001) hybrid structures, Appl. Phys. Lett. 83, 3912 (2003).
  * Bas  _et al._ [2020] D. Bas, P. Shah, A. Matyushov, M. Popov, V. Schell, R. Budhani, G. Srinivasan, E. Quandt, N. Sun, and M. Page, Acoustically Driven Ferromagnetic Resonance in Diverse Ferromagnetic Thin Films, IEEE Trans. Magn. PP, 1 (2020).
  * Gusenbauer  _et al._ [2011] C. Gusenbauer, T. Ashraf, J. Stangl, G. Hesser, T. Plach, A. Meingast, G. Kothleitner, and R. Koch, Interdiffusion in heusler film epitaxy on GaAs(001), Phys. Rev. B 83, 035319 (2011).
  * Thomas  _et al._ [2009] J. Thomas, J. Schumann, H. Vinzelberg, E. Arushanov, R. Engelhard, O. G. Schmidt, and T. Gemming, Epitaxial Fe3Si films on GaAs(100) substrates by means of electron beam evaporation, Nanotechnology 20, 235604 (2009).
  * Lenz  _et al._ [2005] K. Lenz, E. Kosubek, K. Baberschke, H. Wende, J. Herfort, H.-P. Schönherr, and K. H. Ploog, Magnetic properties of ${\mathrm{Fe}}_{3}\mathrm{Si}/\mathrm{Ga}\mathrm{As}(001)$ hybrid structures, Phys. Rev. B 72, 144411 (2005).
  * Lenz  _et al._ [2006] K. Lenz, E. Kosubek, K. Baberschke, J. Herfort, H.-P. Schönherr, and K. H. Ploog, Magnetic anisotropy and resonance linewidth of Fe3Si/GaAs(001), Phys. Status Solidi 3, 122 (2006).
  * Wegscheider  _et al._ [2011] M. Wegscheider, G. Käferböck, C. Gusenbauer, T. Ashraf, R. Koch, and W. Jantsch, Magnetic anisotropy of epitaxial Fe(1-x)Si(x) films on GaAs(001), Phys. Rev. B 84, 054461 (2011).
  * Auld [1973] B. A. Auld,  _Acoustic Fields and waves in solids_ , Vol. 2 (John Wiley and Sons, New York, 1973).
  * [31] M. F. Lewis, in  _Rayleigh-Wave Theory and Application_ (Springer Berlin Heidelberg) pp. 37–58.
  * Foerster  _et al._ [2016] M. Foerster, J. Prat, V. Massana, N. Gonzalez, A. Fontsere, B. Molas, O. Matilla, E. Pellegrin, and AballeL, Custom sample environment at the alba x-peem, Ultramicroscopy 171, 63 (2016).
  * Foerster  _et al._ [2019a] M. Foerster, N. Statuto, B. Casals, A. Hernández-Mínguez, S. Finizio, A. Mandziak, L. Aballe, J. M. Hernàndez Ferràs, and F. Macià, Quantification of propagating and standing surface acoustic waves by stroboscopic X-ray photoemission electron microscopy, J. Synch. Rad. 26, 184 (2019a).
  * Stohr and Siegmann [2006] J. Stohr and H. Siegmann,  _Magnetism: from Fundamentals to Nanoscale Dynamics_ , Vol. 152 (Springer Berlin Heidelberg, 2006).
  * Flovik  _et al._ [2015] V. Flovik, F. Macià, J. M. Hernàndez, R. Bručas, M. Hanson, and E. Wahlström, Tailoring the magnetodynamic properties of nanomagnets using magnetocrystalline and shape anisotropies, Phys. Rev. B 92, 104406 (2015).
  * Hernández-Mínguez  _et al._ [2020] A. Hernández-Mínguez, F. Macià, J. M. Hernàndez, J. Herfort, and P. V. Santos, Large nonreciprocal propagation of surface acoustic waves in epitaxial ferromagnetic/semiconductor hybrid structures, Phys. Rev. Applied 13, 044018 (2020).
  * sup [a] See Supplemental Material Note 1 at [URL will be inserted by publisher] for the results on the FMR experiment indicating the properties of the material. (a).
  * Walowski  _et al._ [2008] J. Walowski, M. D. Kaufmann, B. Lenk, C. Hamann, J. McCord, and M. Münzenberg, Intrinsic and non-local Gilbert damping in polycrystalline nickel studied by Ti : Sapphire laser fs spectroscopy, J. Phys. D: Appl. Phys. 41, 164016 (2008).
  * sup [b] See Supplemental Material Note 2 at [URL will be inserted by publisher] for the comparison between spin wave resonance and uniform mode resonance. (b).
  * Foerster  _et al._ [2019b] M. Foerster, N. Statuto, B. Casals, A. Hernández-Mínguez, S. Finizio, A. Mandziak, L. Aballe, J. M. Hernàndez Ferràs, and F. Macià, Quantification of propagating and standing surface acoustic waves by stroboscopic X-ray photoemission electron microscopy, J. Synchrotron Radiat. 26, 184 (2019b).
  * sup [c] See Supplemental Material Note 3 at [URL will be inserted by publisher] for examples of spin wave patterns and fittings of the XMCD images. (c).
  * sup [d] See Supplemental Material Note 4 at [URL will be inserted by publisher] for information on how the magnetization is quantified from the XMCD images. (d).
  * Vansteenkiste  _et al._ [2014] A. Vansteenkiste, J. Leliaert, M. Dvornik, M. Helsen, F. Garcia-Sanchez, and B. Van Waeyenberge, The design and verification of mumax3, AIP Advances 4, 107133 (2014).
  * Szymanski  _et al._ [1991] M. Szymanski, M. Jankowski, L. Dobrzynski, A. Wisniewski, and S. Bednarski, Spin dynamics of Fe3Si and Fe3-xMnx alloys, J. Phys. Condens. Matter 3, 4005 (1991).
  * Li  _et al._ [2017] X. Li, D. Labanowski, S. Salahuddin, and C. S. Lynch, Spin wave generation by surface acoustic waves, J. Appl. Phys. 122, 043904 (2017).


# A computation of the ninth Dedekind Number

Christian Jäkel
Technische Universität Dresden  01062  Dresden  Germany

christian.jaekel(at)tu-dresden.de

###### Abstract

In this article, we present an algorithm to compute the 9th Dedekind Number.
The key aspects are the use of matrix multiplication and symmetries in the
free distributive lattice, which are detected with techniques from Formal
Concept Analysis.

_Keywords_ dedekind numbers, free distributive lattice, formal concept
analysis, intervals.

##  1 Introduction

MI The _Dedekind numbers_ are a fast growing sequence of integers, named after
Richard Dedekind. Their determination is known as _Dedekind’s Problem_. Let
$\operatorname{d}(n)$ denote the $n$-th Dedekind number. A survey over past
achievements can be found in [11], which also contains the following table:

$n$ | $\operatorname{d}(n)$ | Source
---|---|---
$0$ |  $2$Mi |
$1$ |  $3$Mi |
$2$ |  $6$Mi | Dedekind, 1897 [4]
$3$ |  $20$Mi |
$4$ |  $168$Mi |
$5$ |  $7581$Mi | Church, 1940 [2]
$6$ |  $7828354$Mi | Ward, 1946 [9]
$7$ |  $2414682040998$Mi | Church, 1965 [3]
$8$ |  Mi$56130437228687557907788$Mi |  Mi Wiedemann, 1991 [10] Mi
Figure 1: Dedekind Numbers up to $n=8$. Integer sequence A000372.

Several interpretations of $\operatorname{d}(n)$ exist. For example, the value
$\operatorname{d}(n)$ is equal to the number of antichains of the powerset
lattice $\mathbbm{2}^{n}:=(2^{\\{0,\dots,n-1\\}},\subseteq)$, or the number of
monotone Boolean functions on $n$ variables, or the number of elements of the
free distributive lattice with $n$ generators.

Therefore, the next section explains how the free distributive lattice can be
numerically represented. After that, Section 3 treats (anti) isomorphic
lattice intervals, a tool that is utilized for the computation. Section 4 and
5 deal with theoretical, and Section 6 with practical aspects of our algorithm
to compute the ninth Dedekind number.

##  2 The Free Distributive Lattice

Let $\mathbb{D}_{n}=(\operatorname{D}(n),\leq)$ denote the free distributive
lattice with $n$ generators. The following theorem can be found in [5]:

###### Theorem 2.1

There is a one to one correspondence between elements of $\mathbb{D}_{n}$ and
monotone mappings from $\mathbbm{2}^{k}$ into $\mathbb{D}_{n-k}$.

###### Corollary 1

There is a one to one correspondence of elements from $\mathbb{D}_{n+1}$ and
pairs $(x,y)$ of elements $x,y$ from $\mathbb{D}_{n}$, such that $x\leq y$.

###### Proof

_Let $x$ and $y$ be elements of $\mathbb{D}_{n}$. We have $\emptyset$ and
$\\{0\\}$ as elements of $\mathbbm{2}$. Mapping $\emptyset$ to $x$ allows to
monotonously map $\\{0\\}$ to every $y$ for which $x\leq y$ holds. ∎_

Corollary 1 provides a method to generate elements of $\mathbb{D}_{n}$
recursively. Even more, this leads to a numerical representation of
$\operatorname{D}(n)$ which facilitates the efficient implementation of
algorithms to compute $\operatorname{d}(n)$. For that, let the two elements of
$\mathbb{D}_{0}$ be represented by the binary numbers $0$ and $1$. The
underlying order is $0\leq 1$ applied bitwise. In the next step, we form valid
pairs w.r.t. Corollary 1 and concatenate them to $2$-bit numbers, which are
$00$, $01$ and $11$. This process can be iterated further.

###### Example 1

This example illustrates the generation of $\operatorname{D}(3)$, starting
from $\operatorname{D}(0)$.

$0$

$1$

$\rightarrow$

$00$

$01$

$11$

$\rightarrow$

$0000$

$0001$

$0011$

$0101$

$0111$

$1111$

$\rightarrow$

$0000.0000$ $0001.0011$ $0101.0101$

$0000.0001$ $0001.0101$ $0101.0111$

$0000.0011$ $0001.0111$ $0101.1111$

$0000.0101$ $0001.1111$ $0111.0111$

$0000.0111$ $0011.0011$ $0111.1111$

$0000.1111$ $0011.0111$ $1111.1111$

$0001.0001$ $0011.1111$

Figure 2 shows how these numbers form the free distributive lattice, by taking
"bitwise or" as join- and "bitwise and" as meet operation. Instead of binary
numbers, we use the more convenient decimal interpretation as integer values.
From a programming point of view, this representation is memory efficient and
the bitwise operations are very fast.

$\;0$$\;1$$\;0$$\;1$$\;3$

$\;0$$\;1$$\;5$$\;3$$\;7$$\;15$

$\;0$$\;1$$\,5$$\,17$$\,3$$\,19$$\,21$$\,7$$\,23$$\,85$$\,51$$\,15$$\,55$$\,87$$\,31$$\,95$$\,119$$\,63$$\,127$$\,255$

Figure 2: The free distributive lattice with $0,1,2$ and $3$ generators.

##  3 Lattices, Definitions and Notation

Throughout this section, we consider a finite lattice
$\mathbbm{L}=(L,\vee,\wedge,\bot,\top)=(L,\leq)$ with _bottom_ $\bot$ and
_top_ $\top$. An _isomorphism_ between lattices is a bijective map that
preserves join and meet operations, and consequently order as well. Dually, an
_anti isomorphism_ $\varphi$ is a bijective map which reverses order, and
hence join and meet too.

$x\leq y\Leftrightarrow\varphi(y)\leq\varphi(x)\;\;\;\;\;\;\;\;x\vee
y\Leftrightarrow\varphi(x)\wedge\varphi(y)\;\;\;\;\;\;\;\;x\wedge
y\Leftrightarrow\varphi(x)\vee\varphi(y).$

###### Definition 1

For $a,b\in L$ with $a\leq b$, we define the _interval_ $[a,b]:=\\{x\mid x\in
L,\;a\leq x\leq b\\}$. An interval $I$ is _isomorphic_ to interval $J$,
denoted by $I\cong J$, if an isomorphism exists, that maps $I$ onto $J$.
Similarly, _anti isomorphic_ intervals $I\operatorname{\cong_{a}}J$ are
defined through the existence of a respective anti isomorphism. Two intervals
$I$ and $J$ are _equivalent_ , denoted by $I\equiv J$, if they are isomorphic
or anti isomorphic. Furthermore, $\operatorname{Int}(\mathbbm{L})$ denotes the
set of all intervals of $\mathbbm{L}$ and $\\#I$ the cardinality of $I$.

###### Proposition 1

The equivalence of intervals is an equivalence relation on
$\operatorname{Int}(\mathbbm{L})$. Consequently, the set of all intervals
$\operatorname{Int}(\mathbbm{L})$ can be factorized by $\equiv$.

###### Proof

_Reflexivity is induced by $\cong$ and the fact that every interval is
isomorphic to itself. Furthermore, symmetry is given due to the symmetry of
$\cong$ and $\cong_{a}$. To deduce transitivity, we consider three cases:_

$I\cong J\wedge J\cong K\Rightarrow I\cong
K,\;\;\;\;I\operatorname{\cong_{a}}J\wedge
J\operatorname{\cong_{a}}K\Rightarrow I\cong K\;\;\;\;I\cong J\wedge
J\operatorname{\cong_{a}}K\Rightarrow I\operatorname{\cong_{a}}K.$

_∎_

For $[I]\in\operatorname{Int}(\mathbbm{L})/_{\equiv}$ and we denote the
equivalence class $[I]$’s cardinality by $\\#[I]$. Lastly, for every $x\in I$,
we introduce two operators that decode the interval length w.r.t. the top and
bottom of $I$:

$\bot_{\operatorname{I}}(x):=\\#[\bot_{\operatorname{I}},x]\;\text{and}\;\top_{\operatorname{I}}(x):=\\#[x,\top_{\operatorname{I}}],$

where $\bot_{\operatorname{I}}$ denotes the bottom and
$\top_{\operatorname{I}}$ the top element of $I$. Since $I$ can be deduced
from the outer context (the domain containing the operators’ argument), we
will omit subscript $\operatorname{I}$ in the rest of this paper.

###### Example 2

These are the equivalence classes of
$\operatorname{Int}(\mathbbm{D}_{2})/_{\equiv}$ (compare Fig. 2).

$\displaystyle\\{[0,0],[1,1],[3,3],[5,5],[7,7],[15,15]\\},\\{[0,1],[1,3],[1,5],[3,7],[5,7],[7,15]\\},$
$\displaystyle\\{[0,3],[0,5],[3,15],[5,15]\\},\\{[1,7]\\},\\{[0,7],[1,15]\\},\\{[0,15]\\}.$

##  4 Enumeration of $\mathbb{D}_{n+1}$, $\mathbb{D}_{n+2}$ and
$\mathbb{D}_{n+3}$

In this section, we apply Theorem 2.1 to derive values of
$\operatorname{d}(n+1),\operatorname{d}(n+2),\operatorname{d}(n+3)$, by
respectively counting all monotonous maps from
$\mathbbm{2}^{1},\mathbbm{2}^{2}$ and $\mathbbm{2}^{3}$ to $\mathbb{D}_{n}$.
This is a warmup for the next section and provides an overview over formulas
to compute some Dedekind numbers.

###### Theorem 4.1

The following formulas compute $\mathbb{D}_{n+1}$ by means of
$\mathbb{D}_{n}$:

$\operatorname{d}(n+1)=\sum_{a\in\operatorname{D}(n)}\top(a)=\sum_{I\in\operatorname{Int}(\mathbb{D}_{n})}1=\\#\operatorname{Int}(\mathbb{D}_{n})=\sum_{[I]\in\operatorname{Int}(\mathbbm{D}_{n})/_{\equiv}}\\#[I].$

###### Proof

_If $\mathbbm{2}$’s bottom is mapped to $a\in\operatorname{D}(n)$, every
$b\in[a,\top]$ is a valid image for the top element. This implies that every
$a,b\in\operatorname{D}(n)$, such that
$[a,b]\in\operatorname{Int}(\mathbb{D}_{n})$, is a valid choice too (see
Figure 3, left image). Instead of summing up all intervals, we can restrict
the summation to equivalent ones. _∎

The first equation from Theorem 4.2 was presented in [1].

###### Theorem 4.2

The following formulas enumerate $\mathbb{D}_{n+2}$ by means of
$\mathbb{D}_{n}$:

$\operatorname{d}(n+2)=\sum_{a,b\in\operatorname{D}(n)}\bot(a\wedge
b)\cdot\top(a\vee
b)=\sum_{I\in\operatorname{Int}(\mathbb{D}_{n})}(\\#I)^{2}=\sum_{[I]\in\operatorname{Int}(\mathbbm{D}_{n})/_{\equiv}}(\\#I)^{2}\cdot\\#[I].$

###### Proof

_If $a,b\in\operatorname{D}(n)$ are chosen as in Figure 3’s center, every
element in $[a\vee b,\top]$ and each in $[\bot,a\wedge b]$ are possibilities
for top and bottom respectively. On the other hand, Figure 3’s right image
shows that bottom and top can be mapped to every interval $[a,b]$, which
implies the second last equation. Since isomorphic and anti isomorphic
intervals have equal cardinality, the last equality holds. _∎

The next theorem shows how to express the computation of
$\operatorname{d}(n+2)$ with matrix calculus. For that we use the trace
operator $\operatorname{Tr}$ of square matrices, that is defined as the sum of
all diagonal elements.

###### Theorem 4.3

We define two matrices $\alpha(a,b):=\bot(a\wedge b)$ and
$\beta(a,b):=\top(a\vee b)$, with $a,b\in\operatorname{D}(n)$. It holds that:

$\operatorname{d}(n+2)=\operatorname{Tr}(\alpha\cdot\beta).$

###### Proof

_Let $\gamma=\alpha\cdot\beta$ be the matrix product. We use the first formula
from Theorem 4.2 and insert the matrix expressions. Note that $\alpha$ and
$\beta$ are symmetric._

$\operatorname{d}(n+2)=\sum_{a\in\operatorname{D}(n)}\sum_{b\in\operatorname{D}(n)}\alpha(a,b)\cdot\beta(b,a)=\sum_{a\in\operatorname{D}(n)}\gamma(a,a)=\operatorname{Tr}(\gamma).$

∎

$a$$b$

$a\wedge b$$b$$a$$a\vee b$

$a$$b$

Figure 3: Figures for the proof of Theorem 4.1 and 4.2.

The next theorem’s first formula is similar to the one stated in [7].

###### Theorem 4.4

Let $X$ denote the set of all intervals $\\{[\bot,y]\mid
y\in\operatorname{D}(n)\\}$. The following formulas enumerate
$\mathbb{D}_{n+3}$ by means of $\mathbb{D}_{n}$:

$\displaystyle\operatorname{d}(n+3)$
$\displaystyle=\sum_{y\in\operatorname{D}(n)}\sum_{a,b,c\in[\bot,y]}\bot(a\wedge
b\wedge c)\cdot\top(a\vee b)\cdot\top(a\vee c)\cdot\top(b\vee c)$
$\displaystyle=\sum_{[I]\in X/_{\cong}}\\#[I]\cdot\sum_{a,b,c\in
I}\bot(a\wedge b\wedge c)\cdot\top(a\vee b)\cdot\top(a\vee c)\cdot\top(b\vee
c)$ $\displaystyle=\sum_{I\in\operatorname{Int}(\mathbb{D}_{n})}\sum_{a,b,c\in
I}\top(a\vee b)\cdot\top(a\vee c)\cdot\top(b\vee c)$
$\displaystyle=\sum_{[I]\in\operatorname{Int}(\mathbbm{D}_{n})/_{\equiv}}\\#[I]\cdot\sum_{a,b,c\in
I}\top(a\vee b)\cdot\top(a\vee c)\cdot\top(b\vee c)$
$\displaystyle=\sum_{[I]\in\operatorname{Int}(\mathbbm{D}_{n})/_{\equiv}}\\#[I]\cdot\sum_{a,b\in
I}(\sum_{c\in[a,\top_{\operatorname{I}}]}\bot(b\wedge c))^{2}.$

###### Proof

_Choosing $y$ and then $a,b,c\in[\bot,y]$ as in Figure 4’s left image, the
first formula can be deduced. By factoring out isomorphic elements from $X$,
we derive the second equation. It is important to notice that after choosing
$a,b,c\in[\bot,y]$, there is still one degree of freedom for the bottom
element. If we map bottom and top to an interval $[x,y]$’s boundaries, we
remove this degree of freedom and get the third equation. Obviously,
isomorphic intervals can then be factored out. Equation number four follows
from the fact that anti isomorphic intervals can be factored out as well. To
see why this holds, we dualize the third identity111This implies $a,b,c$ have
to be placed one ”level” above than depicted in Figure 4.:_

$\operatorname{d}(n+3)=\sum_{[I]\in\operatorname{Int}(\mathbb{D}_{n})}\sum_{a,b,c\in
I}\bot(a\wedge b)\cdot\bot(a\wedge c)\cdot\bot(b\wedge c).$

_Since an anti isomorphism reverses order and thereby join and meet
operations, for $I\operatorname{\cong_{a}}J$ it holds that:_

$\sum_{a,b,c\in I}\bot(a\wedge b)\cdot\bot(a\wedge c)\cdot\bot(b\wedge
c)=\sum_{a,b,c\in J}\top(a\vee b)\cdot\top(a\vee c)\cdot\top(b\vee c).$

_To conclude the last equation, we utilize that
$\mathbbm{2}^{3}\cong\mathbbm{2}^{2}\times\mathbbm{2}$. The goal is to apply
vertical symmetry from $\mathbbm{2}^{3}$ (see Figure 4, right image). If an
interval $I$ is chosen, every $a,b\in I=[x,y]$ can be independently placed as
depicted. After computing $\sum_{c\in[a,y]}\\#[x,b\wedge c]$, the result can
be squared due to symmetry induced by $\mathbbm{2}^{2}$. _∎

$a\wedge b\wedge c=x$$c$$b$$a$$b\vee c$$a\vee c$$a\vee b$$y$

$x$$a$$b\wedge c$$b$$c$$y$

Figure 4: Figures for the proof of Theorem 4.4.

Like in Theorem 4.3, we express the computation of $\operatorname{d}(n+3)$ via
matrix calculus.

###### Theorem 4.5

We define the matrix $\alpha(a,b):=\top(a\vee b)$, with $a,b\in
I\in\operatorname{Int}(\mathbbm{D}_{n})$. It holds that:

$\operatorname{d}(n+3)=\sum_{[I]\in\operatorname{Int}(\mathbbm{D}_{n})/_{\equiv}}\\#[I]\cdot\operatorname{Tr}(\alpha^{3}).$

###### Proof

_We use Theorem 4.2’s fourth formula and insert the matrix definition._

$\operatorname{d}(n+3)=\sum_{[I]\in\operatorname{Int}(\mathbbm{D}_{n})/_{\equiv}}\\#[I]\cdot\sum_{a\in
I}\sum_{b\in I}\alpha(a,b)\sum_{c\in I}\alpha(b,c)\alpha(c,a).$

_The innermost sum expresses $\alpha^{2}$, the sum over $b$ leads to
$\alpha^{3}$ and the sum over $a$ gives the trace operator. _∎

Our implementation of Theorem 4.5 with GPU support, run on a Nvidia A100 GPU,
computes $\operatorname{d}(8)$ in $17.56$ seconds. However, this algorithm can
not compute $\operatorname{d}(9)$, since the involved matrices would have a
maximal dimension of $7828354\times 7828354$.

##  5 Enumeration of $\mathbb{D}_{n+4}$

In this section, we apply Theorem 2.1 to derive values of
$\operatorname{d}(n+4)$, by counting all monotonous maps from
$\mathbbm{2}^{4}$ to $\mathbb{D}_{n}$.

###### Theorem 5.1

The following formulas enumerate $\mathbb{D}_{n+4}$ by means of
$\mathbb{D}_{n}$:

$\operatorname{d}(n+4)=\sum_{I\in\operatorname{Int}(\mathbb{D}_{n})}X=\sum_{[I]\in\operatorname{Int}(\mathbbm{D}_{n})/_{\equiv}}\\#[I]\cdot
X,\;\text{with:}$ $\displaystyle X$ $\displaystyle=\sum_{a,b,c,d\in
I}\sum_{\begin{subarray}{c}e\in[a\vee b,\top]\\\ f\in[a\vee c,\top]\\\
g\in[a\vee d,\top]\\\ h\in[b\vee c,\top]\\\ i\in[b\vee d,\top]\\\ j\in[c\vee
d,\top]\end{subarray}}\top(e\vee f\vee h)\cdot\top(e\vee g\vee
i)\cdot\top(f\vee g\vee j)\cdot\top(h\vee i\vee j)$
$\displaystyle=\sum_{a,b,c,d\in I}\sum_{\begin{subarray}{c}e\in[a\vee b\vee
c,\top]\\\ f\in[a\vee b\vee d,\top]\\\ g\in[a\vee c\vee d,\top]\\\ h\in[b\vee
c\vee d,\top]\end{subarray}}(\;\\#[a\vee b,e\wedge f]\cdot\\#[a\vee c,e\wedge
g]\cdot\\#[a\vee d,f\wedge g]$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\cdot\\#[b\vee
c,e\wedge h]\cdot\\#[b\vee d,f\wedge h]\cdot\\#[c\vee d,g\wedge h]\;)$
$\displaystyle=\sum_{a,b,c,d,e,f\in I}(\bot(a\wedge c\wedge
d)\cdot\bot(b\wedge c\wedge e)\cdot\bot(b\wedge d\wedge f)\cdot\bot(a\wedge
e\wedge f)$
$\displaystyle\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\cdot\top(b\vee c\vee
d)\cdot\top(a\vee c\vee e)\cdot\top(a\vee d\vee f)\cdot\top(b\vee e\vee f)).$

###### Proof

_For all three formulas, bottom and top of $\mathbbm{2}^{4}$ are mapped to the
bounds of every possible interval $[x,y]$. But as in Theorem 4.4’s proof, we
can argue that it is sufficient to consider equivalent intervals.
In the first equation, values $a,b,c,d$ are chosen as depicted by the red
labels of Figure 5. We then iterate over all six ranges given by the $2$-joins
and the interval top. This leaves four degrees of freedom which range form the
respective $3$-joins up to the top element.
The second equation uses the same choice for $a,b,c,d$. In the following step,
we iterate over all four ranges given by the $3$-joins and the top element via
$e,f,g,h$. This results in six degrees of freedom that range from the
$2$-joins of $a,b,c,d$ up to the respective $2$-meet of $e,f,g,h$.
Lastly, we can place $a,b,c,d,e,f$ as depicted by the blue labels of Figure 5.
Consequently, there are eight degrees of freedom that range from every
$3$-join to the interval top, and from the interval bottom to every $3$-meet.
_∎

$x$$b$$b\wedge c\wedge e$$c$$b\wedge d\wedge f$$b$$a$$a\wedge c\wedge
d$$c$$d$$b\vee c\vee d$$d$$a\wedge e\wedge f$$f$$e$$b\vee e\vee f$$a$$a\vee
c\vee e$$a\vee d\vee f$$y$

Figure 5: Figure of $\mathbbm{2}^{4}$ seen as
$\mathbbm{2}^{2}\times\mathbbm{2}^{2}$.

Theorem 5.1’s last formula can be expressed via matrix calculus.

###### Theorem 5.2

For $I\in\operatorname{Int}(\mathbbm{D}_{n})$ and $a,b,c,d\in I$, we define
matrices $\alpha$ and $\beta$:

$\alpha_{ab}(c,d):=\bot(a\wedge c\wedge d)\cdot\top(b\vee c\vee
d)\;\text{and}\;\beta_{ab}(c,d):=\bot(b\wedge c\wedge d)\cdot\top(a\vee c\vee
d).$

Let $\gamma_{ab}$ be the matrix product of $\alpha_{ab}$ and $\beta_{ab}$. It
holds that:

$\operatorname{d}(n+4)=\sum_{[I]\in\operatorname{Int}(\mathbbm{D}_{n})/_{\equiv}}\\#[I]\cdot\sum_{a,b\in
I}\operatorname{Tr}(\gamma^{2}_{ab}).$

###### Proof

_Inserting the matrix expressions into the formula from Theorem 5.1, we get
for $d(n+4):$_

$\sum_{[I]\in\operatorname{Int}(\mathbbm{D}_{n})/_{\equiv}}\\#[I]\cdot\sum_{a,b\in
I}\sum_{c,d\in I}\sum_{e,f\in I}\alpha(c,d)\beta(c,e)\alpha(e,f)\beta(d,f).$

Mi _Since $\alpha$ and $\beta$ are symmetric, we can identify two matrix
multiplications:_

$\gamma(d,e)=\sum_{c\in
I}\alpha(d,c)\beta(c,e)\;\text{and}\;\gamma(e,d)=\sum_{f\in
I}\alpha(e,f)\beta(f,d).$

Mi _All indices are from the same range (the interval $I$), which means that
the matrices above are equal. Proceeding from this matrix point of view, we
compute the diagonal of the product from $\gamma$ with itself and sum it up
$\sum_{d\in I}\sum_{e\in I}\gamma(d,e)\gamma(e,d)$._∎

Looking at Figure 5, we see that $a$ and $b$ are independent from each other.
Together with the formula from Theorem 5.1, this implies rotation symmetry
between $a$ and $b$. It is enough to consider pairs such that $a\leq b$.
Values for $a$ that are strictly smaller than $b$ are weighted with factor two
and for $a=b$ the weight is one. This reduces computations by almost one half.
Still, further reductions are possible. Therefor, for every
$I\in\operatorname{Int}(\mathbbm{D}_{n})$, let $\varphi:I\rightarrow I$ be an
(anti) isomorphism. We introduce a relation on $I\times I$. That is
$(a,b)\sim(\tilde{a},\tilde{b}):\Longleftrightarrow$

$\exists\varphi:I\rightarrow
I,\;\varphi(a)=\varphi(\tilde{a})\;\text{and}\;\varphi(b)=\varphi(\tilde{b}).$

Let $I\times I\mid_{\leq}$ denote all pairs $(a,b)$, such that $a\leq b$.
Furthermore the weight operator $\omega:I\times
I\mid_{\leq}\,\rightarrow\\{1,2\\}$ equals $2$ for $a\neq b$ and $1$
otherwise.

###### Theorem 5.3

For $I\in\operatorname{Int}(\mathbbm{D}_{n})$ and $a,b,c,d\in I$, we define
matrices $\alpha$ and $\beta$:

$\alpha_{ab}(c,d):=\bot(a\wedge c\wedge d)\cdot\top(b\vee c\vee
d)\;\text{and}\;\beta_{ab}(c,d):=\bot(b\wedge c\wedge d)\cdot\top(a\vee c\vee
d).$

Let $\gamma_{ab}$ be the matrix product of $\alpha_{ab}$ and $\beta_{ab}$. It
holds that:

$\operatorname{d}(n+4)=\sum_{[I]\in\operatorname{Int}(\mathbbm{D}_{n})/_{\equiv}}\\#[I]\cdot\sum_{[(a,b)]\in(I\times
I\mid_{\leq})/_{\sim}}\omega(a,b)\cdot\\#[(a,b)]\cdot\operatorname{Tr}(\gamma^{2}_{ab}).$

###### Proof

_The relation $\sim$ is an equivalence relation and all pairs within one
equivalence class result in an equal summand for the enumeration formula. We
illustrate this at the simpler example $\sum_{z\in I}\bot(a\wedge
z)\cdot\top(a\vee z)$. Under an isomorphism $\varphi$, with
$\varphi(a)=\tilde{a}$ (also note that top and bottom are preserved), we get:_

$\sum_{\varphi(z)\in I}\bot(\varphi(a\wedge z))\cdot\top(\varphi(a\vee
z))=\sum_{\varphi(z)\in
I}\bot(\tilde{a}\wedge\varphi(z))\cdot\top(\tilde{a}\vee\varphi(z))=\sum_{\tilde{z}\in
I}\bot(\tilde{a}\wedge\tilde{z})\cdot\top(\tilde{a}\vee\tilde{z}).$

_Since $\varphi$ is bijective and preserves join, meet and order, both sums
(with and without applying $\varphi$) are equal. An anti isomorphism would
inverse order, but this is offset by the symmetry w.r.t. top and bottom. These
arguments can be extended to the actual formula from Theorem 5.1.∎_

Our implementation of Theorem 5.3 with GPU support, as described in the
following section, can compute $\operatorname{d}(8)$ in about $3$ seconds.

##  6 Algorithm To Compute The Ninth Dedekind Number

We list all steps necessary to compute $\operatorname{d}(n+4)$ via Theorem 5.3
and address them individually.

  1. 1.

Generate $\mathbbm{D}_{n}$ as described at the end of Section 1.

  2. 2.

Compute the equivalence classes
$\operatorname{Int}(\mathbbm{D}_{n})/_{\equiv}$ and save one representative
for each class together with the class’s cardinality.

  3. 3.

For every equivalence class representative $I$ of
$\operatorname{Int}(\mathbbm{D}_{n})/_{\equiv}$, compute equivalence classes
of $(I\times I\mid_{\leq})/_{\sim}$. Again save one representative for each
class together with the respective cardinality.

  4. 4.

Run the computation according to Theorem 5.3:

Data: $\operatorname{Int}(\mathbbm{D_{n}})/_{\equiv}$ and
$\forall[I]\,\in\operatorname{Int}(\mathbbm{D_{n}})/_{\equiv}:\;(I\times
I\mid_{\leq})/_{\sim}$

Result: $\operatorname{d}(n+4)$

for  _$[I]\in\operatorname{Int}(\mathbbm{D_{n}})/_{\equiv}$_ do

for  _$[(a,b)]\in(I\times I\mid_{\leq})/_{\sim}$_ do

\- generate the matrices $\alpha_{ab}$ and $\beta_{ab}$;

\- compute the matrix product $\gamma_{ab}=\alpha_{ab}\cdot\beta_{ab}$;

\- compute the trace of $\gamma^{2}_{ab}$;

\- multiply the trace with $\omega(a,b)$ and $\\#[(a,b)]$;

end for

\- sum up each value from above;

\- multiply the sum with $\\#[I]$;

end for

###  6.1 Step 1

The generation of $\mathbbm{D}_{n}$ is straight forward and needs no special
explanation. Elements of $\mathbbm{D}_{4}$ can be represented by $16$-bit,
$\mathbbm{D}_{5}$ by $32$-bit and $\mathbbm{D}_{6}$ by $64$-bit unsigned
integers. To store all elements of $\mathbbm{D}_{6}$ takes about $63$ MB. Even
the elements of $\mathbbm{D}_{7}$ can be generated within a few hours, but to
store them would require about $38.63$ TB of memory, which makes
$\mathbbm{D}_{7}$ not suitable as a basis to calculate $\mathbbm{D}_{9}$.

###  6.2 Step 2

It is a simple task to generate all intervals
$\operatorname{Int}(\mathbbm{D}_{n})$. In the following, we describe how to
determine equivalence classes w.r.t. $\equiv$, like depicted in Example 2. For
that we use _Formal Concept Analysis_ (see [6]), which treats the relationship
between complete lattices and binary relations. We present some aspects of
this theory that we will utilize to achieve our goals.

MIGiven a complete lattice $\mathbb{L}=(L,\leq)$, a _join irreducible_ (_meet
irreducible_) element of $\mathbb{L}$ can not be expressed as a proper join
(meet) of other elements form $\mathbb{L}$ that are strictly below (above).
Let $J(\mathbb{L})$ denote all join irreducibles and $M(\mathbb{L})$ all meet
irreducibles. It holds that $\mathbb{L}$ can be represented by the binary
relation $\mathbb{R}:=(J(\mathbb{L}),M(\mathbb{L}),R)$ with
$R:=\leq\mid_{J(\mathbb{L})\times M(\mathbb{L})}$, that is referred to as a
_formal context_. Every element, as well as various properties and parameters
of $\mathbb{L}$ can be reconstructed from the formal context. For instance,
every $x\in L$ can be represented by the set $J(x)$ (all join irreducibles
equal to or below $x$) or $M(x)$ (all meet irreducibles equal to or above
$x$). Since the transition form $\mathbb{L}$ to $\mathbb{R}$ constitutes an up
to logarithmic size reduction, it is often beneficial to use $\mathbb{R}$ for
computations.

MIIt is shown in [6] that an interval
$[x,y]\in\operatorname{Int}(\mathbbm{L})$, can be described by a subrelation
of $R$ namely $(J(y),M(x),R\cap(J(y)\times M(x)))$. Furthermore, a lattice
isomorphism $\varphi:\mathbb{L}_{1}\rightarrow\mathbb{L}_{2}$ exists if and
only if a _context isomorphism_
$(\alpha,\beta):\mathbb{R}_{1}\rightarrow\mathbb{R}_{2}$ exists. The latter
one is defined as a pair of bijective maps
$\alpha:J(\mathbb{R}_{1})\rightarrow J(\mathbb{R}_{2})$ and
$\beta:M(\mathbb{R}_{1})\rightarrow M(\mathbb{R}_{2})$, such that $(j,m)\in
R_{1}\Longleftrightarrow(\alpha(j),\beta(m))\in R_{2}$. A lattice anti
isomorphism corresponds to a context isomorphism from $\mathbb{R}_{1}$ to the
_dual context_
$\mathbb{R}^{d}_{2}:=(M(\mathbb{R}_{2}),J(\mathbb{R}_{2}),R_{2}^{d})$, with
$R^{d}_{2}:=\geq\cap(M(\mathbb{R}_{2})\times J(\mathbb{R}_{2}))$.

$j$$\vdots$$m$$\vdots$ $J(\mathbb{L})$ $M(\mathbb{L})$$R$

Figure 6: A formal context interpreted as bipartite graph.

MIThe identification of (anti) isomorphic formal contexts can be translated to
an isomorphism problem of colored bipartite graphs. That is because every
formal context represents a bipartite graph (see Figure 6). If we want to
determine context isomorphisms only, each of the two vertex sets gets a
different color label assigned to, and we compute graph isomorphisms that
respect them. Since we want to determine anit isomorphisms too, we have to
allow for a complete switch of the vertex sets, but still no mapping from one
set into the other. This can be achieved by adding two additional equally
colored vertices, and connecting them with every vertex of the bipartite set
that they represent.

To practically determine isomorphic graphs, we use the software "nauty" (see
[8]), that can compute a canonical string representation of a given colored
graph. This translates the graph isomorphism problem into a string comparison,
since two graphs are isomorphic if and only if their canonical string
representations are equal.

Data: $\operatorname{Int}(\mathbbm{D_{n}})$

Result: $\operatorname{Int}(\mathbbm{D_{n}}/_{\equiv}$

for  _$[x,y]\in\operatorname{Int}(\mathbbm{D_{n}})$_ do

\- compute a formal context that represents $[x,y]$;

\- transform the context to a colored bipartite graph as depicted in Figure 6;

\- use "nauty" to compute a canonical string;

\- count occurrences of each string;

end for

Algorithm 1 The steps to calculate
$\operatorname{Int}(\mathbbm{D_{n}})/_{\equiv}$.

For $\mathbbm{D}_{2}$ we compute 6, for $\mathbbm{D}_{3}$ 18, for
$\mathbbm{D}_{4}$ 134 and for $\mathbbm{D}_{5}$ 9919 equivalence classes. Due
to nauty’s efficiency, the last computation can be performed within just a
couple of seconds on a $2.4$ GHz desktop PC. Note that according to Theorem
4.1 there are $7828354$ intervals of $\mathbbm{D}_{5}$. Hence we reduce them
to just $0.00127\%$, which has a huge runtime impact on the computation of
$\operatorname{d}(5+4)$.

###  6.3 Step 3

Considering an interval $I\in\operatorname{Int}(\mathbbm{D_{n}})$, we can
generate all pairs $(a,b)\in I\times I\mid_{\leq}$. In order to determine the
existence of an (anti) isomorphism $\varphi:I\rightarrow I$, with
$\varphi(a)=\tilde{a}$ and $\varphi(b)=\tilde{b}$, for given pairs $(a,b)$ and
$(\tilde{a},\tilde{b})$, we use a refined version of the approach from Step 2,
which is illustrated in Figure 7.

Firstly, the bipartite graph that decodes the (anti) isomorphism problem on
$I$ (as in Step 2) has to be generated. Next we impose further restrictions,
by adjoining 4 additional vertices that are connected to all join and meet
irreducibles w.r.t. $a$ and $b$ respectively. The red vertices in Figure 7
connect the vertices related to $a$ and $b$ separately. This configuration
assures that, if we compute equivalence classes w.r.t. nauty’s canonical
string representation, an (anti) isomorphism on $I$ respects the pair $(a,b)$,
and can additionally swap $a$ and $b$. Example 3 shows the equivalence classes
of $([0,15]\times[0,15])\mid_{\leq}$.

$j$$\vdots$$m$$\vdots$ $J(\mathbb{L})$
$M(\mathbb{L})$$R$$m(a)$$j(a)$$m(b)$$j(b)$

Figure 7: The graph that decodes the (anti) isomorphism problem w.r.t. $\sim$.

###### Example 3

Equivalence classes of $([0,15]\times[0,15])\mid_{\leq}$ w.r.t. $\sim$.

$\displaystyle\\{(0,0),(15,15)\\},\\{(1,1),(7,7)\\},\\{(3,3),(5,5)\\},\\{(0,1),(7,15)\\},\\{(3,5)\\},\\{(0,3),$
$\displaystyle(0,5),(3,15),(5,15)\\},\\{(1,3),(1,5),(3,7),(5,7)\\},\\{(1,7)\\},\\{(0,7),(1,15)\\},\\{(0,15)\\}.$

If we perform the computation for every
$[I]\in\operatorname{Int}(\mathbbm{D_{n}})/_{\equiv}$, we treat a certain
amount of pairs $(a,b)$ and reduce them to equivalence classes. We get the
reductions $\mathbbm{D}_{2}:\,56\rightarrow 33$,
$\mathbbm{D}_{3}:\,1127\rightarrow 446$, $\mathbbm{D}_{4}:\,274409\rightarrow
80741$ and $\mathbbm{D}_{5}:\,8646896880\rightarrow 4257682565$. The
computation for $\mathbbm{D}_{5}$ took about one hour on an AWS "c6i.32xlarge"
cluster with 128 cores. One could think that it is not worth the effort, since
the reduction for $\mathbbm{D}_{5}$ is only slightly more than a factor two.
But it can be observed that large intervals usually have a higher reduction
rate. That is because they leave "more room" for symmetry than small
intervals. For instance the largest interval of $\mathbbm{D}_{5}$ is
$[0,4294967295]$. For this interval we have a reduction $57471561\rightarrow
140736$. This reduction has a big runtime impact, since the involved matrices
have dimension $7581\times 7581$.

###  6.4 Step 4

For a given $I\in\operatorname{Int}(\mathbbm{D_{n}})$, we precompute all
values of $\bot(\cdot)$ and $\top(\cdot)$ on a CPU host and transfer them to a
GPU device. There the matrices $\alpha$ and $\beta$ are generated and
multiplied. A batch of matrices is processed in parallel via CUDA’s
"cublasDgemmStridedBatched" kernel. Since a shift from integer values to
double precision occurs, we have to assure that all values are not bigger than
$2^{53}$ to rule out a loss of precision. Actually, we use the smaller bound
$2^{51}$, since this is beneficial for another estimation.

An upper bound for the entries of $\alpha$ and $\beta$ is given by
$\max_{\alpha}=\bot(a)\cdot\top(b)$ and $\max_{\beta}=\bot(b)\cdot\top(a)$.
This leads to $\max_{\gamma}=\max_{\alpha}\cdot\max_{\beta}\cdot\\#I$. We
compute $\max_{\gamma}$ for all pairs $(a,b)$ w.r.t. $\mathbbm{D}_{5}$. In
$118084$ cases this estimation exceeds $2^{51}$. For these we perform the
exact matrix multiplication with $64$-bit integer precision using the C++
Eigen library, and confirm that $\max_{\gamma}$ is smaller than $2^{51}$.

After multiplying the matrices, a handwritten CUDA kernel computes the trace
of $\gamma^{2}$. For that $128$-bit unsigned integer values are used. Since
the largest entry in $\gamma$ is smaller than $2^{51}$ and $7581\leq 2^{13}$,
we can estimate a maximal value for the trace of $\gamma^{2}$ via
$(2^{51}\cdot 2^{51}\cdot 2^{13})\cdot 2^{13}=2^{128}$. This assures us that
$128$-bit unsigned integer precision is enough to compute the trace. Finally,
the summation of all trace values and multiplication with the equivalence
classes’ carnality is done via $1024$-bit unsigned integers on the host
system.

##  7 Conclusion

We gave an overview about formulas to compute Dedekind numbers in Section 4
and 5. Some of these formulas can by interpreted in terms of matrix
multiplication, which allows for fast "number crunching" on a GPU device. In
Section 6, the steps of an algorithm to compute the ninth Dedekind number are
described. For that, Formal Concept Analysis is used to detect symmetries on
lattice intervals. These symmetries could be efficiently computed with the
graph isomorphism software nauty.

The only thing left to say is that we run the algorithm on Nvidia A100 GPUs.
$5311$ GPU hours and $4257682565$ matrix multiplications later, we got the
following value for the ninth Dedekind number:

$286386577668298411128469151667598498812366.$

## References

  * [1] Berman, J., Köhler, P.: Cardinalities of finite distributive lattices. Mitt. Math. Sem. Giessen pp. 103–124 (1976)
  * [2] Church, R.: Numerical analysis of certain free distributive structures. Duke Mathematical Journal pp. 6(3):732–734 (1940)
  * [3] Church, R.: Enumeration by rank of the free distributive lattice with 7 generators. Notices of the American Mathematical Society p. (11):724 (1965)
  * [4] Dedekind, R.: Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler. Gesammelte Werke. Band 2 p. 732–734 (1897)
  * [5] Fidytek, R., Mostowski, A.W., Somla, R., Szepietowski, A.: Algorithms counting monotone boolean functions. Information Processing Letters 79(5), 203 – 209 (2001). https://doi.org/https://doi.org/10.1016/S0020-0190(00)00230-1, http://www.sciencedirect.com/science/article/pii/S0020019000002301
  * [6] Ganter, B., Wille, R.: Formal Concept Analysis: Mathematical Foundations. Springer-Verlag New York, Inc. (1997)
  * [7] Hoedt, P.J.: Parallelizing with mpi in java to find the ninth dedekind number (Jan 2015), http://oeis.org/A000372
  * [8] McKay, B.D., Piperno, A.: Practical graph isomorphism, II. CoRR abs/1301.1493 (2013), http://arxiv.org/abs/1301.1493
  * [9] Ward, M.: Note on the order of free distributive lattices. Bulletin of the American Mathematical Society p. (52):423 (1946)
  * [10] Wiedemann, D.: A computation of the eighth dedekind number. Order 8(1), 5–6 (Mar 1991). https://doi.org/10.1007/BF00385808, https://doi.org/10.1007/BF00385808
  * [11] Yusun, T.J.: Dedekind numbers and related sequences (2008)