e1e-mail<EMAIL_ADDRESS>
11institutetext: Graduate School of Engineering Science, Osaka University,
Toyonaka, Osaka 560-8531, Japan 22institutetext: Yukawa Institute for
Theoretical Physics, Kyoto University, Sakyo-ku, Kyoto 606-8502, Japan

In this study, we numerically investigated the mechanical responses and
trajectories of frictional granular particles under oscillatory shear in the
reversible phase where particle trajectories form closed loops below the
yielding point. When the friction coefficient is small, the storage modulus
exhibits softening, and the loss modulus remains finite in the quasi-static
limit. As the friction coefficient increases, the softening and residual loss
modulus are suppressed. The storage and loss moduli satisfy scaling laws if
they are plotted as functions of the areas of the loop trajectories divided by
the strain amplitude and diameter of grains, at least for small values of the
areas.

#  Shear modulus and reversible particle trajectories of frictional granular
materials under oscillatory shear

Michio Otsukie1,addr1  Hisao Hayakawaaddr2

(Received: date / Accepted: date)

††journal: Eur. Phys. J. E

##  1 Introduction

Dense disordered materials, such as granular materials, foams, emulsions, and
colloidal suspensions, behave like solids when the packing fraction $\phi$
exceeds the jamming point Hecke ; Behringer . Under a small shear strain, the
shear stress is proportional to shear strain, which is characterized by the
shear modulus depending on $\phi$ OHern02 ; Tighe11 ; Otsuki17 . However, as
the shear strain increases, the stress-strain relation becomes nonlinear
Coulais ; Otsuki14 .

The nonlinear stress-strain relation is believed to result from the yielding
transition associated with plastic deformations Nagamanasa ; Knowlton ;
Kawasaki16 ; Leishangthem ; Clark ; Boschan19 . However, recent studies have
shown that the mechanical response becomes nonlinear even when the system is
in the reversible phase in which particle trajectories form closed loops below
the yielding point Boschan ; Nakayama ; Kawasaki20 ; Bohy . Such a response is
called (reversible) softening, where the storage modulus under oscillatory
shear decreases as the strain amplitude increases. In a previous paper
Otsuki21 , we demonstrated that the loss modulus remains finite in the quasi-
static limit when reversible softening occurs. We have clarified that the
reversible softening and residual loss modulus originate from the loop
trajectories of particles Lundberg ; Schreck ; Keim13 ; Keim14 ; Regev13 ;
Regev15 ; Priezjev ; Lavrentovich ; Nagasawa ; Das .

Most previous numerical studies assumed frictionless particles, although
realistic disordered materials consist of frictional grains. The friction
causes drastic changes in rheology. For example, frictional particles exhibit
discontinuous shear thickening Otsuki11 ; Chialvo ; Brown ; Seto ; Fernandez ;
Heussinger ; Bandi ; Ciamarra ; Mari ; Grob ; Kawasaki14 ; Wyart14 ; Grob16 ;
Peters ; Fall ; Sarkar ; Singh ; Kawasaki18 ; Thomas  and shear jamming Bi11 ;
Zhang08 ; Zhang10 ; Wang18 ; Zhao ; Sarkar13 ; Sarkar16 ; Seto19 ; Pradipto ;
Otsuki20 , which hardly occurs in frictionless particles. Thus, it is natural
to expect that the friction between the grains affects the mechanical
responses and particle trajectories.

In this study, we numerically investigated the shear modulus of frictional
granular materials under oscillatory shear. In Sect. 2, we explain our model
and setup. In Sect. 3, we present our numerical results of a single-cycle
displacement and mean square displacement to distinguish the irreversible
phase from the reversible phase of particle trajectories. We show how particle
trajectories depend on the friction coefficient between the grains in Sect. 4.
In Sect. 5, we illustrate the existence of scaling laws of the storage and
loss moduli, at least, for small areas of reversible particles trajectories.
In Sect. 6, we conclude and discuss our results.

##  2 Model and setup

Let us consider two-dimensional frictional granular particles with identical
densities confined in a square box under oscillatory shear. Particle $i$ with
a diameter $d_{i}$ is driven by the SLLOD equation under the Lees–Edwards
boundary condition Evans :

$\displaystyle\frac{d}{dt}{\bm{r}}_{i}$ $\displaystyle=$
$\displaystyle\dot{\gamma}(t)y_{i}\bm{e}_{x}+\frac{\bm{p}_{i}}{m_{i}},$ (1)
$\displaystyle\frac{d}{dt}{\bm{p}}_{i}$ $\displaystyle=$
$\displaystyle-\dot{\gamma}(t)p_{i,y}\bm{e}_{x}+\bm{F}_{i},$ (2)

where ${\bm{r}}_{i}=(x_{i},y_{j})$ and
$\bm{p}_{i}=m_{i}(\dot{\bm{r}}_{i}-\dot{\gamma}(t)y_{i})\bm{e}_{x}$ are the
position and peculiar momentum of particle $i$ with mass $m_{i}$, shear rate
$\dot{\gamma}(t)$, and the unit vector $\bm{e}_{x}$ along the $x$-direction,
respectively. The force $\bm{F}_{i}$ is given by:

$\bm{F}_{i}=\sum_{j\neq
i}\left(\bm{F}_{ij}^{\rm(n)}+\bm{F}_{ij}^{\rm(t)}\right)\Theta(d_{ij}-r_{ij}),$
(3)

where $\bm{F}_{ij}^{\rm(n)}$ and $\bm{F}_{ij}^{\rm(t)}$ are the normal and
tangential forces between particles $i$ and $j$, $d_{ij}=(d_{i}+d_{j})/2$ is
the average diameter, and $r_{ij}=|\bm{r}_{ij}|$ is the distance between
particles $i$ and $j$, with
$\bm{r}_{ij}=\bm{r}_{i}-\bm{r}_{j}=(x_{ij},y_{ij})$. Here, $\Theta(x)$ is the
Heviside step function satisfying $\Theta(x)=1$ for $x>0$, and $\Theta(x)=0$
otherwise. To avoid crystallization, we constructed a dispersed system with an
equal number of grains of two diameters ($d_{0}$ and $d_{0}/1.4$).

Then, we adopt the following model for the normal force:

$\bm{F}_{ij}^{\rm(n)}=-\left(k^{\rm(n)}u^{\rm(n)}_{ij}+\eta^{\rm(n)}v^{\rm(n)}_{ij}\right)\bm{n}_{ij}$
(4)

with $k^{\rm(n)}$ as the normal elastic constant, $\eta^{\rm(n)}$ as the
normal viscous constant, and the normal unit vector is
$\bm{n}_{ij}=\bm{r}_{ij}/r_{ij}$. The normal relative displacement and
velocity are, given by the following, respectively:

$\displaystyle u^{\rm(n)}_{ij}=r_{ij}-d_{ij},$ (5)

and

$\displaystyle
v^{\rm(n)}_{ij}=\frac{d}{dt}u^{\rm(n)}_{ij}=\left(\frac{d}{dt}\bm{r}_{i}-\frac{d}{dt}\bm{r}_{j}\right)\cdot\frac{\bm{r}_{ij}}{r_{ij}}.$
(6)

We adopt the following model for the tangential force

$\bm{F}_{ij}^{\rm(t)}={\rm min}\left(|\tilde{F}_{ij}^{\rm(t)}|,\mu
F_{ij}^{\rm(n,el)}\right){\rm sgn}(\tilde{F}_{ij}^{\rm(t)})\bm{t}_{ij},$ (7)

where $\bm{t}_{ij}=(-y_{ij}/r_{ij},x_{ij}/r_{ij})$ is the tangential unit
vector, and $\mu$ is the friction coefficient. Here, ${\rm min}(a,b)$ selects
the smaller one between $a$ and $b$; ${\rm sgn}(x)=1$ for $x\geq 0$ and ${\rm
sgn}(x)=-1$ for $x<0$. Furthermore,
$F_{ij}^{\rm(n,el)}=-k^{\rm(n)}u^{\rm(n)}_{ij}$ is the elastic part of the
normal force. $\tilde{F}_{ij}^{\rm(t)}$ is given by

$\tilde{F}_{ij}^{\rm(t)}=-\left(k^{\rm(t)}u_{ij}^{\rm(t)}+\eta^{\rm(t)}v_{ij}^{\rm(t)}\right)$
(8)

with $k^{\rm(t)}$ as the tangential elastic constant and $\eta^{\rm(t)}$ as
the tangential viscous constant. The tangential velocity $v_{ij}^{\rm(t)}$ is
expressed as

$v_{ij}^{\rm(t)}=(\bm{v}_{i}-\bm{v}_{j})\cdot\bm{t}_{ij}-(d_{i}\omega_{i}+d_{j}\omega_{j})/2$
(9)

with $\omega_{i}$ as the angular velocity of particle $i$. The tangential
displacement $u_{ij}^{\rm(t)}$ satisfies
$\dot{u}_{ij}^{\rm(t)}=v_{ij}^{\rm(t)}$ for $|\tilde{F}_{ij}^{\rm(t)}|<\mu
F_{ij}^{\rm(n,el)}$, whereas $u_{ij}^{\rm(t)}$ remains unchanged for
$|\tilde{F}_{ij}^{\rm(t)}|\geq\mu F_{ij}^{\rm(n,el)}$. We note that
$u_{ij}^{\rm(t)}$ is set to zero if particles $i$ and $j$ are detached. The
time evolution of $\omega_{i}$ is given by

$I_{i}\frac{d}{dt}\omega_{i}=T_{i}$ (10)

with the moment of inertia $I_{i}=m_{i}d_{i}^{2}/8$, and torque
$T_{i}=-\sum_{j}\frac{d_{i}}{2}\bm{F}_{ij}^{\rm(t)}\cdot\bm{t}_{ij}$.

The particles were randomly placed with an initial packing fraction of
$\phi_{\rm I}=0.75$. The system was slowly compressed until the packing
fraction reached $\phi=0.870$, which was sufficiently above the jamming point.
In each step of the compression, the packing fraction is increased by
$\Delta\phi=1.0\times 10^{-4}$ with the affine transformation. Thereafter, the
particles were relaxed to a mechanical equilibrium state with the kinetic
temperature $T_{\rm K}=\sum_{i}p_{i}^{2}/(mN)<T_{\rm th}$. Here, we chose
$T_{\rm th}=1.0\times 10^{-8}k^{\rm(n)}d_{0}^{2}$.

After the compression, we apply the shear strain:

$\gamma(t)=\gamma_{0}\sin\omega t$ (11)

at constant volume with a strain amplitude $\gamma_{0}$ and angular frequency
$\omega$ for $N_{\rm c}$ cycles. The shear rate is given by

$\dot{\gamma}(t)=\gamma_{0}\omega\cos\omega t$ (12)

In the last cycle, we measured the storage and loss moduli, defined by Doi

$\displaystyle G^{\prime}$ $\displaystyle=$
$\displaystyle\frac{\omega}{\pi}\int_{0}^{2\pi/\omega}dt\ \sigma(t)\sin\omega
t/\gamma_{0},$ (13) $\displaystyle G^{\prime\prime}$ $\displaystyle=$
$\displaystyle\frac{\omega}{\pi}\int_{0}^{2\pi/\omega}dt\ \sigma(t)\cos\omega
t/\gamma_{0}$ (14)

with the (symmetric contact) shear stress as

$\sigma=-\frac{1}{2L^{2}}\sum_{i}\sum_{j>i}(x_{ij}F_{ij,y}+y_{ij}F_{ij,x}).$
(15)

Here, we ignore the kinetic and asymmetric parts of the shear stress because
they are less than $1\%$ of $\sigma$.

The number of particles is $N=1000$, $k^{\rm(t)}=0.2k^{\rm(n)}$, and
$\eta^{\rm(n)}=\eta^{\rm(t)}=k^{\rm(n)}t_{0}$ with
$t_{0}=\sqrt{m/k^{\rm(n)}}$, where $m$ is the mass of a grain with diameter
$d_{0}$. This model corresponds to the restitution coefficient $e=0.043$. We
adopt the leapfrog algorithm with the time step $\Delta t=0.05t_{0}$. We chose
$\omega=1.0\times 10^{-4}t_{0}^{-1}$ as the quasi-static shear deformation
because $G^{\prime}$ and $G^{\prime\prime}$ do not depend on $\omega$ for
$\omega\leq 1.0\times 10^{-4}t_{0}^{-1}$.

##  3 Single-cycle particle displacement and mean square displacement

First, we introduce the single-cycle particle displacement as

$dr(n)=\left\langle\sum_{i=1}^{N}|\bm{r}_{i}(nT)-\bm{r}_{i}((n-1)T)|\right\rangle/N$
(16)

with the period $T=2\pi/\omega$ and the ensemble average
$\langle\cdot\rangle$. We plot $dr(n)$ against $n$ for various values of
$\gamma_{0}$ with $\mu=1.0$ in Fig. 1. For $\gamma_{0}=0.2$ and $0.1$, $dr(n)$
is finite and almost independent of $n$. The finite $dr(n)$ indicates that
plastic deformations exist during the cycles. For $\gamma_{0}=0.04$ and
$0.02$, a negligibly small $dr(n)$ can be regarded as the reversible motion of
particles.

Figure 1: Plots of the single-cycle displacement $dr(n)$ versus $n$ for
various values of $\gamma_{0}$ with $\mu=1.0$.

In Fig. 2, we plot the mean square displacements for various values of
$\gamma_{0}$ with $\mu=1.0$ and $n_{0}=100$, defined by

$|\Delta{\mathbf{r}}(n)|^{2}=\sum_{i}|\bm{r}_{i}((n+n_{0})T)-\bm{r}_{i}(n_{0}T)|^{2}/N.$
(17)

Here, the position $\bm{r}_{i}(n_{0}T)$ after $n_{0}$ cycles is the reference
state. For $\gamma_{0}=0.4,0.2,$ and $0.1$, $|\Delta{\mathbf{r}}(n)|^{2}$ is
proportional to $n$, whereas $|\Delta{\mathbf{r}}(n)|^{2}$ reaches a small
saturated value for $\gamma_{0}\leq 0.04$. These results are consistent with
the behavior shown in Fig. 1, where the system is irreversible for
$\gamma_{0}\geq 0.1$, and reversible for $\gamma_{0}\leq 0.04$.

Figure 2: Plots of the mean square displacement $|\Delta{\mathbf{r}}(n)|^{2}$
versus $n$ for various values of $\gamma_{0}$ with $\mu=1.0$. The solid line
represents $|\Delta{\mathbf{r}}(n)|^{2}\sim n$.

From Figs. 1 and 2, we define the reversible phase where the displacement
$dr(n)/\gamma_{0}$ in the last cycle is lower than $0.01d_{0}$, and the
diffusion coefficient $D$ is lower than $1.0\times 10^{-5}d_{0}^{2}/t_{0}$.
Here, we estimate $D$ from the mean square displacement
$|\Delta{\mathbf{r}}(n)|^{2}$ for $n_{\rm I}\leq n\leq n_{\rm F}$ as
$D=(|\Delta{\mathbf{r}}(n_{\rm F})|^{2}-|\Delta{\mathbf{r}}(n_{\rm
I})|^{2})/\left\\{4(n_{\rm F}-n_{\rm I})\right\\}$, where $n_{\rm I}=10$ and
$n_{\rm F}=100$. It should be noted that $|\Delta{\mathbf{r}}(n)|^{2}$ in the
reversible phase is subdiffusive, where $D$ decreases as $n_{\rm F}$
increases. We confirmed that the systems with $\mu=0.01,0.1,0.2,0.3,0.5,$ and
$1.0$ are in the reversible phase for $\gamma_{0}\leq 0.04$. 111We have also
checked that particles in the reversible phase exhibit almost the same
trajectories for ten cycles in all samples.

##  4 Particle trajectories in the reversible phase

In the reversible phase, non-affine particle trajectories should form closed
loops, where the non-affine trajectory for particle $i$ is defined as

$\tilde{\bm{r}}_{i}(t)={\bm{r}}_{i}(t)-\gamma(t)y_{i}(t)\bm{e}_{x}.$ (18)

We plot $\tilde{\bm{r}}_{i}(t)$ for the last two cycles for $\gamma=0.04$ and
$0.004$ with $\mu=0.1$ in Fig. 3. The particle returns to its original
position after each cycle, and the trajectory forms a loop; however,the
trajectories of two cycles for $\gamma_{0}=0.04$ deviate in some parts owing
to the inertia of the particles.

---
Figure 3:  Non-affine particle trajectories for $\gamma_{0}=0.04$ (a) and
$0.004$ (b) with $\mu=0.1$. The circles represent the trajectory in the last
cycle. The line represents the trajectory in the second to the last cycle.

In Figs. 4 and 5, the non-affine trajectories for $\mu=0.5$ and $1.0$ are
plotted. For $\mu=0.5$, the trajectory forms a loop with a finite area for
$\gamma_{0}=0.04$, as shown in Fig. 4(a), while the trajectory for
$\gamma_{0}=0.004$ in Fig. 4(b) becomes a line (or a loop with zero area).
Such a line trajectory is not observed in jammed frictionless particles
Lundberg ; Schreck ; Keim13 ; Keim14 ; Regev13 ; Regev15 ; Priezjev ;
Lavrentovich ; Nagasawa ; Das . For $\mu=1.0$, the trajectories for
$\gamma_{0}=0.04$ and $0.004$ formed lines, as shown in Fig. 5. For
$\gamma_{0}=0.04$, the line trajectory is bent (Fig. 5(a)), while it is almost
straight for $\gamma_{0}=0.004$ (Fig. 5(b)).

---
Figure 4:  Non-affine particle trajectories for $\gamma_{0}=0.04$ (a) and
$0.004$ (b) with $\mu=0.5$. The circles represent the trajectory in the last
cycle. The line represents the trajectory in the second to the last cycle.
---
Figure 5:  Non-affine particle trajectories for $\gamma_{0}=0.04$ (a) and
$0.004$ (b) with $\mu=1.0$. The circles represent the trajectory in the last
cycle. The line represents the trajectory in the second to the last cycle.

The geometry of the trajectory is characterized by

$A_{i}=\oint_{C}\tilde{x}_{i}d\tilde{y}_{i}=\int_{0}^{2\pi/\omega}\tilde{x}_{i}(t)\frac{d\tilde{y}_{i}(t)}{dt}dt,$
(19)

where $C$ represents the trajectory of a cycle. $|A_{i}|$ coincides with the
area covered by the trajectory of particle $i$, if there is no intersection
for the trajectory. We introduce the average area $A$ as

$A=\sum_{i}|A_{i}|/N.$ (20)

If the characteristic length of the trajectory is scaled by $\gamma_{0}d_{0}$,
as in frictionless particles Otsuki21 , $A$ is proportional to
$(\gamma_{0}d_{0})^{2}$. Therefore, we plot the normalized average area
$A/(\gamma_{0}d_{0})^{2}$ against $\gamma_{0}$ for various values of $\mu$ in
Fig. 6. When $\gamma_{0}$ is sufficiently small, $A/(\gamma_{0}d_{0})^{2}$ is
almost zero, corresponding to the line trajectories for $\mu\geq 0.1$.
Furthermore, $A/(\gamma_{0}d_{0})^{2}$ increases with the strain amplitude
$\gamma_{0}$ above a critical value, which is dependent on $\mu$.

Figure 6:  Plots of the normalized area $A/(\gamma_{0}d_{0})^{2}$ of loop
trajectories versus $\gamma_{0}$ for various values of $\mu$.

##  5 Storage and loss moduli

In Fig. 7, we plot the scaled storage modulus $G^{\prime}/G^{\prime}_{0}$ in
the reversible phase against the strain amplitude $\gamma_{0}$, where
$G^{\prime}_{0}$ is defined as the storage modulus
$G^{\prime}_{0}=\lim_{\gamma_{0}\to 0}G^{\prime}$ in the linear response
regime. Here, we estimate $G^{\prime}_{0}$ by $G^{\prime}$ at
$\gamma_{0}=1.0\times 10^{-4}$. As can be seen in Fig. 7,
$G^{\prime}/G^{\prime}_{0}$ decreases with $\gamma_{0}$ above the critical
strain amplitude, depending on $\mu$ for $\mu\geq 0.1$. The decay of
$G^{\prime}$ with $\gamma_{0}$ in the reversible phase is regarded as
reversible softening, which is also observed in frictionless particles
Otsuki21 . A similar decay of $G^{\prime}$ has been reported in an experiment
on photoelastic disks, but it is not clear whether it occurs in the reversible
phase Coulais . The critical strain amplitude for the decay of $G^{\prime}$
increases with $\mu$, and the softening decreases as $\mu$ increases. In Fig.
8, we plot $G^{\prime}_{0}$ as a function of $\mu$, where $G^{\prime}_{0}$
slowly decreases as $\mu$ increases.

Figure 7:  Plots of the normalized storage modulus $G^{\prime}/G^{\prime}_{0}$
versus $\gamma_{0}$ for various $\mu$ values.  Figure 8:  Plots of the storage
modulus $G^{\prime}_{0}$ in the linear response regime versus $\mu$.

Figure 9 shows the loss modulus $G^{\prime\prime}$ against $\gamma_{0}$ for
various $\mu$ values. $G^{\prime\prime}$ is approximately zero for small
$\gamma_{0}$, while $G^{\prime\prime}$ increases with $\gamma_{0}$ above a
threshold strain amplitude except for $\mu=0.01$.

Figure 9:  Plots of the loss modulus $G^{\prime\prime}$ versus $\gamma_{0}$
for various values of $\mu$.

In Ref. Otsuki21 , the reversible softening in frictionless systems can be
characterized by the loop trajectories of particles. Even in frictional
granular materials, the average area $A$ characterizing the loop trajectories
seems to be related to $G^{\prime}$. To check the validity of this conjecture,
we plotted $1-G^{\prime}/G^{\prime}_{0}$ against $A/(\gamma_{0}d_{0})^{2}$ in
Fig. 10 for $A/(\gamma_{0}d_{0})^{2}<0.6$. It is remarkable that
$1-G^{\prime}/G^{\prime}_{0}$ satisfies a scaling law in which
$1-G^{\prime}/G_{0}$ is a linear function of $A/(\gamma_{0}d_{0})^{2}$, and is
independent of $\mu$. Note that the data for $A/(\gamma_{0}d_{0})^{2}>0.6$
with $\mu=0.1$ and $0.01$ deviate from the linear behavior.

Figure 10:  Plots of $1-G^{\prime}/G^{\prime}_{0}$ versus
$A/(\gamma_{0}d_{0})^{2}$ for various $\gamma_{0}$ and $\mu$ values.

The loss modulus $G^{\prime\prime}$ is also expected to be characterized by
the loop trajectories of the particles even in the frictional system. The
connection between the loss modulus and loop trajectories is suggested in
suspension experiments Keim13 ; Keim14 . To clarify this connection, we
plotted $G^{\prime\prime}$ against $A/(\gamma_{0}d_{0})^{2}$ in Fig. 11 for
various $\mu$ with $A/(\gamma_{0}d_{0})^{2}\leq 0.6$. It is remarkable that
$G^{\prime\prime}$ satisfies a scaling law in which $G^{\prime\prime}$ is
proportional to $A/(\gamma_{0}d_{0})^{2}$, except for $\mu=0.1$ and $0.01$.

Figure 11:  Plots of the loss modulus $G^{\prime\prime}$ versus
$A/(\gamma_{0}d_{0})^{2}$ for various values of $\gamma_{0}$ and $\mu$.

##  6 Conclusion and discussion

We numerically studied the relationship between the trajectories of the
frictional granular materials and the shear modulus under oscillatory shear in
the reversible phase. The geometry of the particle trajectories depends on the
friction coefficient $\mu$, where the normalized area
$A/(\gamma_{0}d_{0})^{2}$ increases as $\gamma_{0}$ increases and $\mu$
decreases. The storage modulus $G^{\prime}$ exhibits reversible softening. The
loss modulus $G^{\prime\prime}$ remains finite for a large $\gamma_{0}$ and
small $\mu$. We found the existence of the scaling laws of $G^{\prime}$ and
$G^{\prime\prime}$, at least for not too large $A/(\gamma_{0}d_{0})^{2}$ and
not too small $\mu$.

In this study, we investigated the shear modulus of frictional granular
materials for $\phi=0.87$. In future studies, the findings on the shear
modulus and loop trajectories will have to be confirmed in the vicinity of the
jamming point.

In Ref. Otsuki21 , the reversible softening and residual loss modulus of
frictionless particles are theoretically related to the Fourier components of
the loop trajectories. We numerically connected $G^{\prime}$ and
$G^{\prime\prime}$ with the area of the loop trajectories, but the theoretical
basis has not been confirmed. Therefore, an extension of the theory in Ref.
Otsuki21  to frictional particles will be our future work.

###### Acknowledgements.

The authors thank K. Saitoh and D. Ishima for fruitful discussions. This work
was supported by JSPS KAKENHI Grant Numbers JP16H04025, JP19K03670, and
JP21H01006, and ISHIZUE 2020 of the Kyoto University Research Development
Program.

## References

  * (1) M. van Hecke, J. Phys.: Condens. Matter 22, 033101 (2009)
  * (2) R. P. Behringer and B. Chakraborty, Rep. Prog. Phys. 82 012601 (2019)
  * (3) C. S. O’Hern, S. A. Langer, A. J. Liu, and S. R. Nagel, Phys. Rev. Lett. 88, 075507 (2002).
  * (4) B. P. Tighe, Phys. Rev. Lett. 107, 158303 (2011).
  * (5) M. Otsuki and H. Hayakawa, Phys. Rev. E 95, 062902 (2017).
  * (6) C. Coulais, A. Seguin, and O. Dauchot, Phys. Rev. Lett. 113, 198001 (2014).
  * (7) M. Otsuki and H. Hayakawa, Phys. Rev. E 90, 042202 (2014).
  * (8) K. Hima Nagamanasa, S. Gokhale, A. K. Sood, and R. Ganapathy, Phys. Rev. E 89, 062308 (2014).
  * (9) E. D. Knowlton, D. J. Pine, and L. Cipelletti, Soft Matter 10, 6931 (2014).
  * (10) T. Kawasaki and L. Berthier, Phys. Rev. E 94, 022615 (2016).
  * (11) P. Leishangthem, A. D. S. Parmar, and S. Sastry, Nat. Commun. 8, 14653 (2017).
  * (12) A. H. Clark, J. D. Thompson, M. D. Shattuck, N. T. Ouellette, and C. S. O’Hern, Phys. Rev. E 97, 062901 (2018).
  * (13) J. Boschan, S. Luding, and B. P. Tighe, Granul. Matter 21, 58 (2019).
  * (14) J. Boschan, D. Vågberg, E. Somfai, and B. P. Tighe, Soft Matter 12, 5450 (2016).
  * (15) D. Nakayama, H. Yoshino, and F. Zamponi,J. Stat. Mech. 2016 104001 (2016).
  * (16) T. Kawasaki and K. Miyazaki, arXiv:2003.10716.
  * (17) S. Dagois-Bohy, E. Somfai, B. P. Tighe, and M. van Hecke, Soft Matter 13, 9036 (2017).
  * (18) M. Otsuki and H. Hayakawa, arXiv:2101.07473.
  * (19) M. Lundberg, K. Krishan, N. Xu, C. S. O’Hern, and M. Dennin, Phys. Rev. E 77, 041505 (2008).
  * (20) C. F. Schreck, R. S. Hoy, M. D. Shattuck, and C. S. O’Hern, Phys. Rev. E 88, 052205 (2013).
  * (21) N. C. Keim and P. E. Arratia, Soft Matter 9, 6222 (2013).
  * (22) N. C. Keim and P. E. Arratia, Phys. Rev. Lett. 112, 028302 (2014).
  * (23) I. Regev, T. Lookman, and C. Reichhardt Phys. Rev. E 88, 062401 (2013).
  * (24) I. Regev, J. Weber, C. Reichhardt, K. A. Dahmen, and T. Lookman, Nat. Commun. 6, 8805 (2015).
  * (25) N. V. Priezjev, Phys. Rev. E 93, 013001 (2016).
  * (26) M. O. Lavrentovich, A. J. Liu, and S. R. Nagel, Phys. Rev. E 96, 020101(R) (2017).
  * (27) K. Nagasawa, K. Miyazaki and T. Kawasaki, Soft Matter 15, 7557 (2019).
  * (28) P. Das, H. A. Vinutha, and S. Sastry, Proc. Natl. Acad. Sci. USA 117, 10203 (2020).
  * (29) M. Otsuki and H. Hayakawa, Phys. Rev. E 83, 051301 (2011).
  * (30) S. Chialvo, J. Sun, and S. Sundaresan, Phys. Rev. E 85, 021305 (2012).
  * (31) E. Brown and H. M. Jaeger, Phys. Rev. Lett. 103, 086001 (2009).
  * (32) R. Seto, R. Mari, J. F. Morris, and M. M. Denn, Phys. Rev. Lett. 111, 218301 (2013).
  * (33) N. Fernandez, R. Mani, D. Rinaldi, D. Kadau, M. Mosquet, H. Lombois-Burger, J. Cayer-Barrioz, H. J. Herrmann, N. D. Spencer, and L. Isa, Phys. Rev. Lett. 111, 108301 (2013).
  * (34) C. Heussinger, Phys. Rev. E 88, 050201 (2013).
  * (35) M. M. Bandi, M. K. Rivera, F. Krzakala and R.E. Ecke, Phys. Rev. E 87, 042205 (2013).
  * (36) M. P. Ciamarra, R. Pastore, M. Nicodemi, and A. Coniglio, Phys. Rev. E 84, 041308 (2011).
  * (37) R. Mari, R. Seto, J. F. Morris, and M. M. Denn, J. Rheol. 58, 1693 (2014).
  * (38) M. Grob, C. Heussinger, and A. Zippelius, Phys. Rev. E 89, 050201(R) (2014).
  * (39) T. Kawasaki, A. Ikeda, and L. Berthier, EPL 107, 28009 (2014).
  * (40) M. Wyart and M. E. Cates, Phys. Rev. Lett. 112, 098302 (2014).
  * (41) M. Grob, A. Zippelius, and C. Heussinger, Phys. Rev. E 93, 030901(R) (2016).
  * (42) I. R. Peters, S. Majumdar, and H. M. Jaeger, Nature 532, 214 (2016).
  * (43) A. Fall, F. Bertrand, D. Hautemayou, C. Mezière, P Moucheront, A. Lemaître, and G. Ovarlez, Phys. Rev. Lett. 114, 098301 (2015).
  * (44) S. Sarkar, E. Shatoff, K. Ramola, R. Mari, J. Morris, and B. Chakraborty, EPJ Web Conf. 140, 09045 (2017).
  * (45) A. Singh, R. Mari, M. M. Denn, and J. F. Morris, J. Rheol. 62, 457 (2018).
  * (46) T. Kawasaki and L. Berthier, Phys. Rev. E 98, 012609 (2018).
  * (47) J. E. Thomas, K. Ramola, A. Singh, R. Mari, J. F. Morris, and B. Chakraborty, Phys. Rev. Lett. 121, 128002 (2018).
  * (48) D. Bi, J. Zhang, B. Chakraborty and R. Behringer, Nature 480, 355 (2011).
  * (49) J. Zhang, T. Majmudar, and R. Behringer, Chaos 18, 041107 (2008).
  * (50) J. Zhang, T. S. Majmudar, A. Tordesillas, and R. P. Behringer, Granul. Matter 12, 159 (2010).
  * (51) D. Wang, J. Ren, J. A. Dijksman, H. Zheng, and R. P. Behringer, Phys. Rev. Lett. 120, 208004 (2018).
  * (52) Y. Zhao, J. Barés, H. Zheng, J. E. S. Socolar, and R. P. Behringer, Phys. Rev. Lett. 123, 158001 (2019).
  * (53) S. Sarkar, D. Bi, J. Zhang, R. P. Behringer and B. Chakraborty , Phys. Rev. Lett. 111, 068301 (2013).
  * (54) S. Sarkar, D. Bi, J. Zhang, J. Ren, R. P. Behringer and B. Chakraborty, Phys. Rev. E 93, 042901 (2016).
  * (55) R. Seto, A. Singh, B. Chakraborty, M. M. Denn, J. F. Morris, Granul. Matter 21, 82 (2019).
  * (56) Pradipto, H. Hayakawa, Soft Matter 16, 945 (2020).
  * (57) M. Otsuki and H. Hayakawa, Phys. Rev. E 101, 032905 (2020).
  * (58) D. J. Evans and G. P. Morriss, Statistical Mechanics of Nonequilibrium Liquids 2nd ed. (Cambridge University Press, Cambridge, MA, 2008).
  * (59) M. Doi and S. F. Edwards, The Theory of Polymer Dynamics (Oxford University Press, Oxford, 1986).


# Counting unate and balanced monotone Boolean functions

Aniruddha Biswas and Palash Sarkar
Indian Statistical Institute
203, B.T.Road, Kolkata
India 700108.
Email: {anib_r<EMAIL_ADDRESS>
###### Abstract

We show that the problem of counting the number of $n$-variable unate
functions reduces to the problem of counting the number of $n$-variable
monotone functions. Using recently obtained results on $n$-variable monotone
functions, we obtain counts of $n$-variable unate functions up to $n=9$. We
use an enumeration strategy to obtain the number of $n$-variable balanced
monotone functions up to $n=7$. We show that the problem of counting the
number of $n$-variable balanced unate functions reduces to the problem of
counting the number of $n$-variable balanced monotone functions, and
consequently, we obtain the number of $n$-variable balanced unate functions up
to $n=7$. Using enumeration, we obtain the numbers of equivalence classes of
$n$-variable balanced monotone functions, unate functions and balanced unate
functions up to $n=6$. Further, for each of the considered sub-class of
$n$-variable monotone and unate functions, we also obtain the corresponding
numbers of $n$-variable non-degenerate functions.
Keywords: Boolean function, unate function, monotone function, Dedekind
number, non-degenerate function, balanced functions, equivalence classes of
functions.
MSC: 05A99.

##  1 Introduction

For a positive integer $n$, an $n$-variable Boolean function $f$ is a map
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$. A Boolean function $f$ is said to be
monotone increasing (resp. decreasing) in the $i$-th variable if

$f(x_{1},\ldots,x_{i-1},0,x_{i+1},\ldots,x_{n})\leq
f(x_{1},\ldots,x_{i-1},1,x_{i+1},\ldots,x_{n})$ $(\mbox{resp.
}f(x_{1},\ldots,x_{i-1},0,x_{i+1},\ldots,x_{n})\geq
f(x_{1},\ldots,x_{i-1},1,x_{i+1},\ldots,x_{n}))$

for all possible $x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{n}\in\\{0,1\\}$. The
function $f$ is said to be locally monotone or unate, if for each
$i\in\\{1,\ldots,n\\}$, it is either monotone increasing or monotone
decreasing in the $i$-th variable. The function $f$ is said to be monotone
increasing (or, simply monotone) if for each $i\in\\{1,\ldots,n\\}$, it is
monotone increasing in the $i$-th variable.

Unate functions have been studied in the literature from various viewpoints
such as switching theory [14, 18, 28, 17, 5, 23], combinatorial aspects [28,
8, 10], and complexity theoretic aspects [2, 31, 19, 10]. Monotone functions
have been studied much more extensively than unate functions and have many
applications so much so that it is difficult to mention only a few
representative works.

A Boolean function is degenerate on some variable if its output does not
depend on the variable, and it is said to be non-degenerate if it is not
degenerate on any variable. A Boolean function is said to be balanced if it
takes the values 0 and 1 equal number of times. Two Boolean functions on the
same number of variables are said to be equivalent if one can be obtained from
the other by a permutation of variables. The notion of equivalence partitions
the set of Boolean functions into equivalence classes.

The number of $n$-variable monotone Boolean functions is called the $n$-th
Dedekind number $D(n)$ after Dedekind who posed the problem in 1897. Till
date, the $n$-th Dedekind numbers has been obtained only up to $n=9$ (see [26,
7, 6, 29, 4, 30, 9, 12, 11]). A closed form summation formula for $D(n)$ was
given in [13], though it was pointed out in [15] that using the formula to
compute $D(n)$ has the same complexity as direct enumeration of all
$n$-variable monotone Boolean functions. Dedekind numbers form the entry
A000372 of [26]. The number of $n$-variable non-degenerate Boolean functions
can be obtained as the inverse binomial transform of the Dedekind numbers and
are hence also known up to $n=9$. These numbers form the entry A006126 of
[26]. The numbers of $n$-variable inequivalent monotone Boolean functions are
known up to $n=9$ (see [27, 21, 22]) and form the entry A003182 of [26].

The focus of the present work is on counting unate and monotone Boolean
functions under various restrictions. For $n\leq 5$, it is possible to
enumerate all $n$-variable Boolean functions. Consequently, the problem of
counting various sub-classes of $n$-variable Boolean functions becomes a
reasonably simple problem. Non-triviality of counting Boolean functions arises
for $n\geq 6$.

We show that the problem of counting unate functions reduces to the problem of
counting monotone functions. Since the numbers of $n$-variable monotone
functions are known up to $n=9$, these values immediately provide the numbers
of $n$-variable unate functions up to $n=9$. The problem of counting balanced
monotone functions has not been considered in the literature. We use an
enumeration strategy to count the number of balanced monotone functions up to
$n=7$. We show that the problem of counting balanced unate functions reduces
to the problem of counting balanced monotone functions. Consequently, we
obtain the numbers of $n$-variable balanced unate functions up to $n=7$. We
further extend these results to obtain the numbers of non-degenerate balanced
monotone functions, non-degenerate unate functions, and non-degenerate
balanced unate functions.

We describe a simple filtering technique for counting the number of
equivalence classes of $n$-variable functions possessing a given property.
Using this technique, we compute the number of equivalence classes of
$n$-variable balanced monotone functions. Unlike the situation for counting
functions, the problem of counting the number of equivalence classes of unate
functions does not reduce to the problem of counting the number of equivalence
classes of monotone functions. So to count equivalence classes of unate
functions, we used a method to generate all $n$-variable unate functions and
applied our filtering technique to obtain the number of equivalence classes of
$n$-variable unate functions. This allowed us to obtain the numbers of
equivalence classes of $n$-variable unate and balanced unate functions up to
$n=6$. We further extend these results to obtain the numbers of equivalence
classes of $n$-variable non-degenerate monotone functions up to $n=9$.
Moreover, we obtain the numbers of equivalence classes of $n$-variable
balanced monotone functions, non-degenerate balanced monotone functions, non-
degenerate unate functions and non-degenerate balanced unate functions up to
$n=6$.

To summarise, the new results that we obtain for monotone and unate functions
are the following.

Monotone:

  1. 1.

Numbers of $n$-variable balanced monotone functions and $n$-variable non-
degenerate balanced monotone functions up to $n=7$.

  2. 2.

Numbers of equivalence classes of $n$-variable non-degenerate monotone
functions up to $n=9$.

  3. 3.

Numbers of equivalence classes of $n$-variable balanced monotone functions,
and $n$-variable non-degenerate balanced monotone functions up to $n=6$.

Unate:

  1. 1.

Numbers of $n$-variable unate functions and $n$-variable non-degenerate unate
functions up to $n=9$.

  2. 2.

Numbers of $n$-variable balanced unate functions and $n$-variable non-
degenerate balanced unate functions up to $n=7$.

  3. 3.

Numbers of equivalence classes of $n$-variable unate functions, $n$-variable
non-degenerate unate functions, $n$-variable balanced unate functions, and
$n$-variable non-degenerate balanced unate functions up to $n=6$.

#### Related counts:

The number of NPN-equivalence classes111Two Boolean functions are said to be
NPN equivalent, if one can be obtained from the other by some combination of
the following operations: a permutation of the variables, negation of a subset
of the variables, and negation of the output. Two functions are NPN
inequivalent if they are not NPN equivalent. of unate Boolean functions has
been studied (see [3] and $A003183$ in [26]). A proper subclass of unate
functions is the class of unate cascade functions which have been studied in
[25, 16, 20]. Entry $A005612$ in [26] provides counts of unate cascade
functions.

#### Outline of the paper:

In Section 2 we describe the preliminaries and prove the mathematical results
required to obtain the various counts. In Section 3 we address the problem of
counting various sub-classes of monotone and unate functions and in Section 4
we take up the problem of counting equivalence classes of monotone and unate
functions possessing a combination of several basic properties. Finally,
Section 5 provides the concluding remarks.

##  2 Mathematical Results

We fix some terminology and notation. The cardinality of a finite set $S$ will
be denoted as $\\#S$. For $x,y\in\\{0,1\\}$, $xy$ and $x\oplus y$ denote the
AND and XOR operations respectively, and $\overline{x}$ denotes the complement
(or negation) of $x$.

Elements of $\\{0,1\\}^{n}$, $n\geq 2$, are $n$-bit strings (or vectors) and
will be denoted using bold font. Given $n\geq 2$ and $1\leq i\leq n$, by
$\mathbf{e}_{i}$ we will denote the $n$-bit string whose $i$-th bit is 1 and
is 0 elsewhere.

Let $f$ be an $n$-variable Boolean function. The weight ${\sf wt}(f)$ of $f$
is the size of its support, i.e. ${\sf
wt}(f)=\\#\\{\mathbf{x}:f(\mathbf{x})=1\\}$. An $n$-variable Boolean function
$f$ can be uniquely represented by a binary string of length $2^{n}$ in the
following manner: for $0\leq i<2^{n}$, the $i$-th bit of the string is the
value of $f$ on the $n$-bit binary representation of $i$. We will use the same
notation $f$ to denote the string representation of $f$. So $f_{0}\cdots
f_{2^{n}-1}$ is the bit string of length $2^{n}$ which represents $f$.

By $\overline{f}$, we will denote the negation of $f$, i.e.
$\overline{f}(\mathbf{x})=1$ if and only if $f(\mathbf{x})=0$. Let $f^{r}$ be
a Boolean function defined as
$f^{r}(x_{1},\ldots,x_{n})=f(\overline{x}_{1},\ldots,\overline{x}_{n})$. The
bit string representation of $f^{r}$ is the reverse of the bit string
representation of $f$.

Let $g$ and $h$ be two $n$-variable Boolean functions having string
representations $g_{0}\cdots g_{2^{n}-1}$ and $h_{0}\cdots h_{2^{n}-1}$. We
write $g\leq h$ if $g_{i}\leq h_{i}$ for $i=0,\ldots,2^{n}-1$. From $g$ and
$h$, it is possible to construct an $(n+1)$-variable function $f$ whose string
representation is obtained by concatenating the string representations of $g$
and $h$. We denote this construction as $f=g||h$. For
$(x_{1},\ldots,x_{n+1})\in\\{0,1\\}^{n+1}$, we have

$\displaystyle f(x_{1},\ldots,x_{n+1})$ $\displaystyle=$
$\displaystyle\overline{x}_{1}g(x_{2},\ldots,x_{n+1})\oplus
x_{1}h(x_{2},\ldots,x_{n+1}).$ (1)

An $n$-variable Boolean function $f$ is said to be non-degenerate on the
$i$-th variable, $1\leq i\leq n$, if there is an $\bm{\alpha}\in\\{0,1\\}^{n}$
such that $f(\bm{\alpha})\neq f(\bm{\alpha}\oplus\mathbf{e}_{i})$. The
function $f$ is said to be non-degenerate, if it is non-degenerate on all the
$n$ variables.

By a property $\mathcal{P}$ of Boolean functions, we will mean a subset of the
set of all Boolean functions. For example, $\mathcal{P}$ could be the property
of being balanced, being monotone, being unate, or a combination of these
properties, where a combination of properties is given by the intersection of
the corresponding subsets of Boolean functions. For $n\geq 0$, let ${\sf
P}_{n}$ denote the number of $n$-variable Boolean functions possessing the
property $\mathcal{P}$, and let ${\sf nd}\mbox{-}{\sf P}_{n}$ denote the
number of $n$-variable non-degenerate Boolean functions possessing the
property $\mathcal{P}$. Since an $n$-variable function can be non-degenerate
on $i$ variables for some $i\in\\{0,\ldots,n\\}$ and the $i$ variables can be
chosen from the $n$ variables in ${n\choose i}$ ways, we obtain the following
result which shows that the sequence $\\{{\sf P}_{n}\\}_{n\geq 0}$ is given by
the binomial transform of the sequence $\\{{\sf nd}\mbox{-}{\sf
P}_{n}\\}_{n\geq 0}$.

######  Proposition 1.

For any property $\mathcal{P}$ of Boolean functions,

$\displaystyle{\sf P}_{n}$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{n}{n\choose i}{\sf nd}\mbox{-}{\sf P}_{i}.$ (2)

Consequently,

$\displaystyle{\sf nd}\mbox{-}{\sf P}_{n}$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{n}(-1)^{n-i}{n\choose i}{\sf P}_{i}.$ (3)

######  Remark 1.

We assume that for $n=0$, there are two $n$-variable, non-degenerate, monotone
(and hence unate), and unbalanced Boolean functions whose string
representations are 0 and 1.

For $n\geq 0$, let ${\sf A}_{n}=2^{2^{n}}$ be the number of all $n$-variable
Boolean functions, and let ${\sf B}_{n}={2^{n}\choose 2^{n-1}}$ be the number
of $n$-variable balanced Boolean functions. Let ${\sf nd}\mbox{-}{\sf A}_{n}$
be the number of all non-degenerate $n$-variable Boolean functions, and ${\sf
nd}\mbox{-}{\sf B}_{n}$ be the number of all non-degenerate $n$-variable
balanced Boolean functions. Using Proposition 1, we obtain

$\displaystyle{\sf nd}\mbox{-}{\sf A}_{n}=\sum_{i=0}^{n}(-1)^{n-i}{n\choose
i}\cdot 2^{2^{i}}$ and $\displaystyle{\sf nd}\mbox{-}{\sf
B}_{n}=\sum_{i=0}^{n}(-1)^{n-i}{n\choose i}\cdot{2^{i}\choose 2^{i-1}}.$ (4)

For $n\geq 0$, by ${\sf M}_{n},{\sf BM}_{n},{\sf U}_{n}$ and ${\sf BU}_{n}$,
we will denote the numbers of $n$-variable monotone, balanced-monotone, unate,
and balanced-unate functions respectively, and by ${\sf nd}\mbox{-}{\sf
M}_{n},{\sf nd}\mbox{-}{\sf BM}_{n},{\sf nd}\mbox{-}{\sf U}_{n}$ and ${\sf
nd}\mbox{-}{\sf BU}_{n}$ we will denote the corresponding numbers of non-
degenerate functions. The relations between the number of $n$-variable
functions possessing one of these properties and the number of non-degenerate
$n$-variable functions possessing the corresponding property are obtained from
Proposition 1.

The following result relates the numbers of monotone and unate Boolean
functions.

######  Proposition 2.

For $n\geq 0$, the following holds.

$\displaystyle{\sf nd}\mbox{-}{\sf U}_{n}$ $\displaystyle=$ $\displaystyle
2^{n}\cdot{\sf nd}\mbox{-}{\sf M}_{n},$ (5) $\displaystyle{\sf nd}\mbox{-}{\sf
BU}_{n}$ $\displaystyle=$ $\displaystyle 2^{n}\cdot{\sf nd}\mbox{-}{\sf
BM}_{n},$ (6) $\displaystyle{\sf U}_{n}$ $\displaystyle\leq$ $\displaystyle
2^{n}\cdot{\sf M}_{n},$ (7) $\displaystyle{\sf BU}_{n}$ $\displaystyle\leq$
$\displaystyle 2^{n}\cdot{\sf BM}_{n},.$ (8)

###### Proof.

First we consider (5) and (6). We prove (5), the proof of (6) being similar.

Let $f$ be an $n$-variable monotone Boolean function. Then it is easy to see
that for any $\bm{\alpha}\in\\{0,1\\}^{n}$, the $n$-variable function
$f_{\bm{\alpha}}$ is unate, where $f_{\bm{\alpha}}$ is defined as
$f_{\bm{\alpha}}(\mathbf{x})=f(\mathbf{x}\oplus\bm{\alpha})$ for all
$\mathbf{x}\in\\{0,1\\}^{n}$. The proof of (5) follows from the following
claim.

Claim: If $f$ is monotone, then the $2^{n}$ possible functions
$f_{\bm{\alpha}}$ corresponding to the $2^{n}$ possible $\bm{\alpha}$’s are
distinct if and only if $f$ is non-degenerate.

Proof of the claim: Suppose $f$ is degenerate on the $i$-th variable. Then $f$
and $f_{\mathbf{e}_{i}}$ are equal. This proves one side of the claim. So
suppose that $f$ is non-degenerate. We have to show that for
$\bm{\alpha}\neq\bm{\beta}$, $f_{\bm{\alpha}}$ and $f_{\bm{\beta}}$ are
distinct functions. Let if possible $f_{\bm{\alpha}}$ and $f_{\bm{\beta}}$ be
equal. Note that since $f$ is non-degenerate, both $f_{\bm{\alpha}}$ and
$f_{\bm{\beta}}$ are also non-degenerate. Since
$\bm{\alpha}=(\alpha_{1},\ldots,\alpha_{n})$ and
$\bm{\beta}=(\beta_{1},\ldots,\beta_{n})$ are distinct, there is a $j$ in
$\\{1,\ldots,n\\}$ such that $\alpha_{j}\neq\beta_{j}$. Suppose without loss
of generality that $\alpha_{j}=0$ and $\beta_{j}=1$. Since $f$ is monotone, it
is monotone increasing in all variables and hence in the $j$-th variable.
Further, since $\alpha_{j}=0$, $f_{\bm{\alpha}}$ is monotone increasing in the
$j$-th variable and since $\beta_{j}=1$, $f_{\bm{\beta}}$ is monotone
decreasing in the $j$-th variable. From $f_{\bm{\alpha}}$ is monotone
increasing in the $j$-th variable we have that for all
$\mathbf{y}=(y_{1},\ldots,y_{n})\in\\{0,1\\}^{n}$ with $y_{j}=0$,
$f_{\bm{\alpha}}(\mathbf{y})\leq
f_{\bm{\alpha}}(\mathbf{y}\oplus\mathbf{e}_{j})$. Further, since
$f_{\bm{\alpha}}$ is non-degenerate, and hence non-degenerate on the $j$-th
variable, equality cannot hold everywhere, i.e. there is a
$\mathbf{z}=(z_{1},\ldots,z_{n})\in\\{0,1\\}^{n}$ with $z_{j}=0$, such that
$f_{\bm{\alpha}}(\mathbf{z})=0$ and
$f_{\bm{\alpha}}(\mathbf{z}\oplus\mathbf{e}_{j})=1$. Since $f_{\bm{\alpha}}$
and $f_{\bm{\beta}}$ are assumed to be equal, it follows that
$f_{\bm{\beta}}(\mathbf{z})=0$ and
$f_{\bm{\beta}}(\mathbf{z}\oplus\mathbf{e}_{j})=1$, which contradicts the fact
that $f_{\bm{\beta}}$ is monotone decreasing in the $j$-th variable. This
proves the claim.

Next we consider (7) and (8). We provide the proof of (7), the proof of (8)
being similar. The relation given by (7) can be obtained from (5) and
Proposition 1 using the following calculation.

$\displaystyle{\sf U}_{n}$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{n}{n\choose i}{\sf nd}\mbox{-}{\sf
U}_{i}=\sum_{i=0}^{n}\left({n\choose i}\cdot 2^{i}\cdot{\sf nd}\mbox{-}{\sf
M}_{i}\right)\leq 2^{n}\cdot\sum_{i=0}^{n}{n\choose i}{\sf nd}\mbox{-}{\sf
M}_{i}=2^{n}\cdot{\sf M}_{n}.$

We record two known facts about monotone functions.

######  Proposition 3.

[1] Let $g$ and $h$ be $n$-variable Boolean functions and $f=g||h$. Then $f$
is a monotone function if and only if $g$ and $h$ are both monotone functions
and $g\leq h$.

######  Proposition 4.

$\left(\mbox{A003183
of~{}\cite[cite]{[\@@bibref{}{ListINtSequence}{}{}]}}\right)$ If $f$ is a
monotone function then $\overline{f^{r}}$ is also a monotone function.

Next we present some results on unate and monotone functions which will be
useful in our enumeration strategy. The first result is the analogue of
Proposition 3 for unate functions.

######  Proposition 5.

Let $g$ and $h$ be $n$-variable functions and $f=g||h$. Then $f$ is a unate
function if and only if $g$ and $h$ are both unate functions satisfying the
following two conditions.

  1. 1.

For each variable, $g$ and $h$ are either both monotone increasing, or both
monotone decreasing.

  2. 2.

Either $g\leq h$ or $h\leq g$.

###### Proof.

First consider the proof of the “if” part. Suppose $g$ and $h$ are unate
functions satisfying the stated condition. We have to show that for each
variable, $f$ is either monotone increasing, or monotone decreasing. Consider
the variable $x_{1}$. If $g\leq h$, then from (1), $f$ is monotone increasing
on $x_{1}$, while if $g\geq h$, then again from (1), $f$ is monotone
decreasing on $x_{1}$. Now consider any variable $x_{i}$, with $i\geq 2$. If
$g$ and $h$ are both monotone increasing on $x_{i}$, then $f$ is also monotone
increasing on $x_{i}$, while if $g$ and $h$ are both monotone decreasing on
$x_{i}$, then $f$ is also monotone decreasing on $x_{i}$. Since for each
variable, $f$ is either monotone increasing, or monotone decreasing, it
follows that $f$ is a unate function.

For the converse, suppose that $f$ is a unate functions. Then for each
variable $x_{i}$, $i\geq 1$, $f$ is either monotone increasing or monotone
decreasing. From (1), it follows that for each variable $x_{i}$, $i\geq 2$,
$g$ and $h$ are either both monotone increasing, or both monotone decreasing.
So in particular, $g$ and $h$ are unate. If $f$ is monotone increasing for
$x_{1}$, then $g\leq h$ and if $f$ is monotone decreasing for $x_{1}$, then
$g\geq h$.

######  Proposition 6.

If $f$ is a unate function then $\overline{f}$ is also a unate function.

###### Proof.

The proof is by induction on the number of variables $n$. The base case is
$n=1$ and is trivial. Suppose the result holds for some $n\geq 1$. Suppose
that $f$ is an $(n+1)$-variable unate function. Then $f$ can be written as
$f=g||h$, where $g$ and $h$ are $n$-variable unate functions satisfying the
conditions in Proposition 5. Then $\overline{f}=\overline{g}||\overline{h}$.
By induction hypothesis, $\overline{g}$ and $\overline{h}$ are $n$-variable
unate functions and the conditions in Proposition 5 hold for $\overline{g}$
and $\overline{h}$. So $\overline{f}$ is a unate function.

For $0\leq w\leq 2^{n}$, let ${\sf M}_{n,w}$ (resp. ${\sf U}_{n,w}$) be the
number of $n$-variable monotone (resp. unate) Boolean functions of weight $w$.

######  Proposition 7.

For any $n\geq 1$ and weight $w\in\\{0,\ldots,2^{n}\\}$, ${\sf M}_{n,w}={\sf
M}_{n,2^{n}-w}$.

###### Proof.

Proposition 4 sets up a one-one correspondence between $n$-variable monotone
functions having weight $w$ and $n$-variable monotone functions having weight
$2^{n}-w$. This shows that ${\sf M}_{n,w}={\sf M}_{n,2^{n}-w}$.

######  Proposition 8.

For any $n\geq 1$ and weight $w\in\\{0,\ldots,2^{n}\\}$, ${\sf U}_{n,w}={\sf
U}_{n,2^{n}-w}$.

###### Proof.

Proposition 6 sets up a one-one correspondence between $n$-variable unate
functions having weight $w$ and $n$-variable unate functions having weight
$2^{n}-w$. This shows that ${\sf U}_{n,w}={\sf U}_{n,2^{n}-w}$.

###  2.1 Equivalence

Two Boolean functions are equivalent if they have the same number of variables
and one can be obtained from the other by a permutation of variables. Let
$\mathcal{P}$ be a property of Boolean functions. The set $\mathcal{P}$ is
partitioned into equivalence classes by the notion of equivalence. For $n\geq
0$, let $[P]_{n}$ denote the number of equivalence classes of $n$-variable
functions possessing the property $\mathcal{P}$. Also, let ${\sf
nd}\mbox{-}[P]_{n}$ denote the number of equivalence classes of non-degenerate
$n$-variable functions possessing the property $\mathcal{P}$.

######  Remark 2.

We assume that for $n=0$, there are two equivalence classes of $n$-variable,
non-degenerate, monotone (and hence unate), and unbalanced Boolean functions
given by $[0]$ and $[1]$.

We have the following analogue of Proposition 1.

######  Proposition 9.

Let $\mathcal{P}$ be a property of Boolean functions which is closed under
permutation of variables (i.e. if $f$ is in $\mathcal{P}$ and $g$ is obtained
from $f$ by applying a permutation to the variables, then $g$ is also in
$\mathcal{P}$). Then

$\displaystyle[P]_{n}$ $\displaystyle=$ $\displaystyle\sum_{i=0}^{n}{\sf
nd}\mbox{-}[P]_{i}.$ (9)

Consequently,

$\displaystyle{\sf nd}\mbox{-}[P]_{n}$ $\displaystyle=$
$\displaystyle[P]_{n}-[P]_{n-1}.$ (10)

For $n\geq 0$, let $[A]_{n}$ denote the number of equivalence classes of
$n$-variable Boolean functions and $[B]_{n}$ denote the number of equivalence
classes of $n$-variable balanced Boolean functions. The values of $[A]_{n}$
and $[B]_{n}$ can be obtained using Polya’s theory (see for example [24]). Let
${\sf nd}\mbox{-}[A]_{n}$ denote the number of equivalence classes of
$n$-variable non-degenerate Boolean functions and ${\sf nd}\mbox{-}[B]_{n}$
denote the number of equivalence classes of $n$-variable non-degenerate
balanced Boolean functions. Using Proposition 9,

$\displaystyle{\sf nd}\mbox{-}[A]_{n}=[A]_{n}-[A]_{n-1}$ and
$\displaystyle{\sf nd}\mbox{-}[B]_{n}=[B]_{n}-[B]_{n-1}.$ (11)

For $n\geq 0$, by $[M]_{n}$, $[BM]_{n}$, $[U]_{n}$ and $[BU]_{n}$ we will
denote the numbers of equivalence classes of $n$-variable monotone, balanced-
monotone, unate, and balanced-unate functions respectively and by ${\sf
nd}\mbox{-}[M]_{n}$, ${\sf nd}\mbox{-}[BM]_{n}$, ${\sf nd}\mbox{-}[U]_{n}$ and
${\sf nd}\mbox{-}[BU]_{n}$ we will denote the corresponding numbers of
equivalence classes of non-degenerate functions. The following result is the
analogue of Proposition 2.

######  Proposition 10.

For $n\geq 0$, the following holds.

$\displaystyle{\sf nd}\mbox{-}[U]_{n}$ $\displaystyle\leq$ $\displaystyle
2^{n}\cdot{\sf nd}\mbox{-}[M]_{n},$ (12) $\displaystyle{\sf
nd}\mbox{-}[BU]_{n}$ $\displaystyle\leq$ $\displaystyle 2^{n}\cdot{\sf
nd}\mbox{-}[BM]_{n},$ (13) $\displaystyle\mbox{$[U]$}_{n}$ $\displaystyle\leq$
$\displaystyle 2^{n}\cdot[M]_{n},$ (14) $\displaystyle\mbox{$[BU]$}_{n}$
$\displaystyle\leq$ $\displaystyle 2^{n}\cdot[BM]_{n},$ (15)

The relations given by (14) and (15) are analogues of (7) and (8)
respectively. However, unlike (5) and (6), we do not have equalities in (12)
and (13). The reason is that two distinct input translations of a non-
degenerate monotone function can lead to two unate functions which are
equivalent. An example is the following. Suppose $f(X_{1},X_{2})=X_{1}X_{2}$,
i.e. $f$ is the AND function. Let $g(X_{1},X_{2})=f(1\oplus
X_{1},X_{2})=(1\oplus X_{1})X_{2}$ and $h(X_{1},X_{2})=f(X_{1},1\oplus
X_{2})=X_{1}(1\oplus X_{2})$. Then $g(X_{1},X_{2})=h(X_{2},X_{1})$, i.e. $g$
and $h$ are distinct, but equivalent unate functions obtained by distinct
input translations from the monotone function $f$.

##  3 Counting Functions

In this section, we consider the problem of counting various sub-classes of
monotone and unate Boolean functions.

###  3.1 Monotone Functions

Note that ${\sf M}_{n}$ is the $n$-th Dedekind number. For $0\leq n\leq 9$,
the values of ${\sf M}_{n}$ are known [26], with the value of ${\sf M}_{9}$
being obtained recently and independently by two groups of researchers [11,
12]. The values of ${\sf M}_{n}$ form entry A000372 of [26]. The numbers of
non-degenerate $n$-variable monotone functions, ${\sf nd}\mbox{-}{\sf M}_{n}$,
form entry A006126 of [26].

We used enumeration to obtain the number ${\sf BM}_{n}$ of $n$-variable
balanced monotone functions. For $n\leq 6$, we enumerated all monotone
functions and counted only the balanced functions. Our strategy for
enumerating monotone functions is based on Proposition 3. The approach is the
following. First generate all $1$-variable monotone functions and store these.
For $n\geq 2$, to generate all $n$-variable monotone functions, we consider
each pair $(g,h)$ of $(n-1)$-variable monotone functions and check whether the
pair satisfies the condition of Proposition 3. If it does, then $f=g||h$ is
stored. To generate all $n$-variable monotone functions, this approach
requires considering $({\sf M}_{n-1})^{2}$ pairs. The enumeration and
filtering out unbalanced functions allows us to obtain the values of ${\sf
BM}_{n}$, for $n=1,\ldots,6$.

######  Remark 3.

To obtain a faster method, one may consider generating only non-degenerate
functions using Proposition 3. This, however, does not work. It is indeed true
that if $g$ and $h$ are distinct non-degenerate functions, $f=g||h$ is also
non-degenerate. On the other hand, it is possible that one of $g$ or $h$ is
degenerate, but $f$ is non-degenerate. For example, take $g$ to be the
2-variable constant function whose string representation is $0000$, and $h$ to
be the 2-variable AND function whose string representation is given by $0001$.
Then the string representation of the 3-variable function $f=g||h$ is
$00000001$ which is the AND of the three variables and hence non-degenerate.
So the set of all non-degenerate $n$-variable monotone functions cannot be
obtained by concatenating only non-degenerate $(n-1)$-variable monotone
functions.

To obtain ${\sf BM}_{7}$ we used a faster method. After enumerating all
6-variable monotone functions, we divided these functions into groups where
all functions in the same group have the same weight. Our modified strategy is
to take two $n$-variable monotone functions $g$ and $h$, where $g$ has weight
$w$ and $h$ has weight $2^{n}-w$ and check whether $g\leq h$. If the check
passes, then we generate the $(n+1)$-variable balanced monotone function
$f=g||h$. Recall that for $0\leq w\leq 2^{n}$, there are ${\sf M}_{n,w}$
$n$-variable monotone functions having weight $w$. The number of pairs needed
to be considered by the modified method is

$\sum_{w=0}^{2^{n}}{\sf M}_{n,w}{\sf
M}_{n,2^{n}-w}=\sum_{w=0}^{2^{n}}\left({\sf M}_{n,w}\right)^{2},$

where the equality follows from Proposition 7. Substituting $n=6$ and using
the values of ${\sf M}_{6,w}$ obtained through enumeration, we find that the
modified strategy for generating 7-variable balanced monotone functions
requires considering $\sum_{w=0}^{64}\left({\sf M}_{6,w}\right)^{2}\approx
2^{40}$ pairs, while the previous strategy would have required considering
$({\sf M}_{6})^{2}\approx 2^{45}$ pairs.

######  Remark 4.

Note that the above procedure to generate balanced monotone functions can be
applied only once. It uses the set of all $n$-variable monotone functions to
generate the set of all $(n+1)$-variable balanced monotone functions. Since
this does not provide all $(n+1)$-variable monotone functions, it cannot be
applied to generate the set of all $(n+2)$-variable balanced monotone
functions.

Having obtained ${\sf BM}_{n}$, for $n=1,\ldots,7$, we use Proposition 1 to
obtain the values of ${\sf nd}\mbox{-}{\sf BM}_{n}$, i.e. the number of
$n$-variable non-degenerate balanced monotone functions. The obtained values
of ${\sf BM}_{n}$ and ${\sf nd}\mbox{-}{\sf BM}_{n}$ are given in Table 1.

$n$ | ${\sf BM}_{n}$ | ${\sf nd}\mbox{-}{\sf BM}_{n}$
---|---|---
0 | 0 | 0
1 | 1 | 1
2 | 2 | 0
3 | 4 | 1
4 | 24 | 16
5 | 621 | 526
6 | 492288 | 488866
7 | 81203064840 | 81199631130
Table 1: Numbers of $n$-variable balanced monotone and non-degenerate balanced
monotone functions for $0\leq n\leq 7$.

###  3.2 Unate Functions

The problem of counting unate functions reduces to the problem of counting
monotone functions in the following manner. Suppose we wish to obtain the
number ${\sf U}_{n}$ of $n$-variable unate functions. Using Proposition 1,
this reduces to the problem of obtaining ${\sf nd}\mbox{-}{\sf U}_{i}$, for
$0\leq i\leq n$. From (5), this reduces to the problem of obtaining ${\sf
nd}\mbox{-}{\sf M}_{i}$ for $0\leq i\leq n$. Using another application of
Proposition 1 reduces the problem of obtaining ${\sf nd}\mbox{-}{\sf M}_{i}$
to that of obtaining ${\sf M}_{j}$ for $0\leq j\leq i$. So to obtain ${\sf
U}_{n}$, it is sufficient to know ${\sf M}_{i}$ for $0\leq i\leq n$. Since the
values of ${\sf M}_{i}$ are known for $0\leq i\leq 9$, we can obtain the
values of ${\sf U}_{n}$ for $0\leq n\leq 9$. From these values, using
Proposition 1, we obtain the values of ${\sf nd}\mbox{-}{\sf U}_{n}$ for
$0\leq n\leq 9$. The values of ${\sf U}_{n}$ and ${\sf nd}\mbox{-}{\sf U}_{n}$
are shown in Table 2.

$n$ | ${\sf U}_{n}$ | ${\sf nd}\mbox{-}{\sf U}_{n}$
---|---|---
0 | 2 | 2
1 | 4 | 2
2 | 14 | 8
3 | 104 | 72
4 | 2170 | 1824
5 | 230540 | 220608
6 | 499596550 | 498243968
7 | 309075799150640 | 309072306743552
8 | 14369391928071394429416818 | 14369391925598802012151296
9 | 146629927766168786368451678290041110762316052 | 146629927766168786239127150948525247729660416
Table 2: Numbers of $n$-variable unate and non-degenerate unate functions for
$0\leq n\leq 9$.

In a similar manner, using Proposition 1 and (6), the problem of counting
balanced unate functions can be reduced to the problem of counting balanced
monotone functions. Since we have obtained the values of ${\sf BM}_{i}$ for
$0\leq i\leq 7$, we obtain the values of ${\sf BU}_{n}$ for $0\leq n\leq 7$.
Using Proposition 1, this gives us the values of ${\sf nd}\mbox{-}{\sf
BU}_{n}$ for $0\leq n\leq 7$. The values of ${\sf BU}_{n}$ and ${\sf
nd}\mbox{-}{\sf BU}_{n}$ are shown in Table 3.

$n$ | ${\sf BU}_{n}$ | ${\sf nd}\mbox{-}{\sf BU}_{n}$
---|---|---
0 | 0 | 0
1 | 2 | 2
2 | 4 | 0
3 | 14 | 8
4 | 296 | 256
5 | 18202 | 16832
6 | 31392428 | 31287424
7 | 10393772159334 | 10393552784640
Table 3: Numbers of $n$-variable balanced unate and non-degenerate balanced
unate functions for $0\leq n\leq 7$.

##  4 Counting Equivalence Classes of Functions

In this section, we present the results on numbers of equivalence classes of
various subsets of monotone and unate functions.

###  4.1 Filtering Procedure

The basic problem of enumerating equivalence classes is the following. Let
$\mathcal{S}$ be a subset of the set of all $n$-variable Boolean functions.
Given $\mathcal{S}$, we wish to generate a set
$\mathcal{T}\subseteq\mathcal{S}$ of functions such that no two functions in
$\mathcal{T}$ are equivalent, and each function in $\mathcal{S}$ is equivalent
to some function in $\mathcal{T}$. The technique for such filtering is the
following.

Given a permutation $\pi$ of $\\{1,\ldots,n\\}$, we define a permutation
$\pi^{\star}$ of $\\{0,\ldots,2^{n}-1\\}$ as follows. For
$i\in\\{0,\ldots,2^{n}-1\\}$, let $(i_{1},\ldots,i_{n})$ be the $n$-bit binary
representation of $i$. Then $\pi^{\star}(i)=j$, where the $n$-bit binary
representation of $j$ is $(i_{\pi(1)},\ldots,i_{\pi(n)})$. Given an
$n$-variable function $f$, let $f^{\pi}$ denote the function such that for all
$(x_{1},\ldots,x_{n})\in\\{0,1\\}^{n}$,
$f^{\pi}(x_{1},\ldots,x_{n})=f(x_{\pi(1)},\ldots,x_{\pi(n)})$. Suppose
$f_{0}\cdots f_{2^{n}-1}$ is the bit string representation of $f$. Then the
bit string representation of $f^{\pi}$ is $f_{\pi^{\star}(0)}\cdots
f_{\pi^{\star}(2^{n}-1)}$.

Note that for each permutation $\pi$, the permutation $\pi^{\star}$ can be
pre-computed and stored as an array say $P[0,\ldots,2^{n}-1]$. Suppose the bit
string representation of $f$ is stored as an array $A[0,\ldots,2^{n}-1]$. Then
the bit string representation of $f^{\pi}$ is obtained as the array
$B[0,\ldots,2^{n}-1]$, where $B[i]=A[P[i]]$, for $i=0,\ldots,2^{n}-1$. So
obtaining $f^{\pi}$ becomes simply a matter of array reindexing.

Consider the set of functions $\mathcal{S}$ to be filtered is given as a list
of string representations of the functions. We incrementally generate
$\mathcal{T}$ as follows. The first function in $\mathcal{S}$ is moved to
$\mathcal{T}$. We iterate over the other functions in $\mathcal{S}$. For a
function $f$ in $\mathcal{S}$, we generate $f^{\pi}$ for all permutations
$\pi$ of $\\{1,\ldots,n\\}$ using the technique described above. For each such
$f^{\pi}$, we check whether it is present in $\mathcal{T}$. If none of the
$f^{\pi}$’s are present in $\mathcal{T}$, then we append $f$ to $\mathcal{T}$.
At the end of the procedure, $\mathcal{T}$ is the desired set of functions.

The check for the presence of $f^{\pi}$ in $\mathcal{T}$ involves a search in
$\mathcal{T}$. This is done using binary search. To apply binary search on a
list, it is required that the list be sorted. To ensure this, we initially
ensure that $\mathcal{S}$ is sorted (either by generating it in a sorted
manner, or by sorting it after generation). This ensures that at any point of
time, $\mathcal{T}$ is also a sorted list, so that binary search can be
applied.

###  4.2 Monotone

For $n\geq 0$, the numbers $[M]_{n}$ of equivalence classes of $n$-variable
monotone functions form entry A003182 of [26]. Using Proposition 9, it is
possible to find the numbers ${\sf nd}\mbox{-}[M]_{n}$ of equivalence classes
of $n$-variable monotone functions. These values are shown in Table 4.

$n$ | ${\sf nd}\mbox{-}[M]_{n}$
---|---
0 | 2
1 | 1
2 | 2
3 | 5
4 | 20
5 | 180
6 | 16143
7 | 489996795
8 | 1392195548399980210
9 | 789204635842035039135545297410259322
Table 4: Numbers of equivalence classes of $n$-variable non-degenerate
monotone functions for $0\leq n\leq 9$.

For $0\leq n\leq 6$, the numbers $[BM]_{n}$ of equivalence classes of
$n$-variable balanced monotone functions are obtained by applying the
filtering procedure described in Section 4.1 to the strategy for generating
balanced monotone functions described in Section 3.1. Next applying
Proposition 9, we obtained the numbers ${\sf nd}\mbox{-}[BM]_{n}$ of
equivalence classes of $n$-variable non-degenerate balanced monotone
functions. The values of $[BM]_{n}$ and ${\sf nd}\mbox{-}[BM]_{n}$ are shown
in Table 5.

We briefly consider the computation required to obtain $[BM]_{7}$. From Table
1, ${\sf BM}_{7}\allowbreak=\allowbreak
81203064840\allowbreak\approx\allowbreak 2^{36.24}$. For each 7-variable
balanced monotone function $f$, it is required to consider $7!=5040\approx
2^{12.29}$ functions $f^{\pi}$ for the $7!$ permutations $\pi$ of
$\\{1,\ldots,7\\}$. So a total of about $2^{48.53}$ functions would have to be
considered. For each of these functions a binary search is required on the
partially generated set of functions $\mathcal{T}$ and requires performing
about $\log_{2}\\#\mathcal{T}$ comparisons. So the total number of comparisons
required is somewhat above $2^{50}$. This amount of computation is not
presently feasible on the computing resources available to us.

$n$ | $[BM]_{n}$ | ${\sf nd}\mbox{-}[BM]_{n}$
---|---|---
0 | 0 | 0
1 | 1 | 1
2 | 1 | 0
3 | 2 | 1
4 | 4 | 2
5 | 16 | 12
6 | 951 | 935
Table 5: Numbers of equivalence classes of $n$-variable balanced monotone and
non-degenerate balanced monotone functions for $0\leq n\leq 6$.

###  4.3 Unate

In the case of counting functions, the problems of counting unate and balanced
unate functions reduce to the problems of counting monotone and balanced
monotone functions respectively. In the case of counting equivalence classes
of functions, such reduction is no longer possible (using the results that we
could prove). The reason is that unlike (5) which expresses the number of non-
degenerate unate functions in terms of the number of non-degenerate monotone
function, the relation (12) only provides an upper bound on the number of
equivalence classes of non-degenerate unate functions in terms of the number
of equivalence classes of non-degenerate monotone functions.

In view of the above, for counting equivalence classes of unate functions, we
resorted to the technique of enumerating unate functions and then using the
technique described in Section 4.1 to obtain the number of equivalence
classes.

The technique of generating all unate functions is based on Proposition 5.
Along with the string representation of a unate function, we also need to
record whether the function is increasing or decreasing in each of its
variables. This is recorded as the signature of the function. The special
cases of the two constant functions cause some complications in the definition
of the signature.

For an $n$-variable unate function $f$, we define its signature, denoted ${\sf
sig}(f)$, to be an element of
$\\{0,1\\}^{n}\cup\\{\mathfrak{z},\mathfrak{o}\\}$ in the following manner. If
$f$ is the constant function $1$, then ${\sf sig}(f)=\mathfrak{o}$, if $f$ is
the constant function $0$, then ${\sf sig}(f)=\mathfrak{z}$; otherwise ${\sf
sig}(f)$ is an $n$-bit string $\alpha$, where for $i=1,\ldots,n$,
$\alpha_{i}=1$ if $f$ is monotone increasing in the variable $x_{i}$, and
$\alpha_{i}=0$ if $f$ is monotone decreasing in the variable $x_{i}$. The
signature ${\sf sig}(f)$ encodes whether $f$ is monotone increasing or
monotone decreasing on each variable. The function $f$ is both monotone
increasing and monotone decreasing in all the variables if and only if it is a
constant function. The signatures of the constant functions are defined
appropriately.

For enumeration, the bit string representation of the functions are used. A
unate function and its signature are stored as a pair. Consider the following
recursive algorithm to generate all $n$-variable unate functions and their
signatures for $n\geq 1$. At the base step, i.e. for $n=1$, store the four
pairs of 1-variable unate functions and their signatures as
$(00,\mathfrak{z})$, $(01,1)$, $(10,0)$ and $(11,\mathfrak{o})$. Suppose that
for some $n\geq 1$, we have already generated all $n$-variable unate functions
and their signatures. The generation of all $(n+1)$-variable unate functions
and their signatures are done as follows. For any two function-signature pairs
$(g,{\sf sig}(g))$ and $(h,{\sf sig}(h))$, where $g$ and $h$ are $n$-variable
unate functions (which are not necessarily distinct), perform the following
checks:

  1. 1.

Whether at least one of ${\sf sig}(g)$ or ${\sf sig}(h)$ is equal to either
$\mathfrak{z}$ or $\mathfrak{o}$ (i.e. whether at least one of $g$ or $h$ is a
constant function).

  2. 2.

${\sf sig}(g)={\sf sig}(h)=\alpha$, and either $g\leq h$ or $h\leq g$ holds.

If either of the checks pass, then generate $f=g||h$, and determine ${\sf
sig}(f)$ as follows.

$\displaystyle{\sf sig}(f)$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}\mathfrak{z}&\mbox{if }{\sf
sig}(g)={\sf sig}(h)=\mathfrak{z},\\\ \mathfrak{o}&\mbox{if }{\sf sig}(g)={\sf
sig}(h)=\mathfrak{o},\\\ 1^{n+1}&\mbox{if }{\sf sig}(g)=\mathfrak{z},\ {\sf
sig}(h)=\mathfrak{o},\\\ 0^{n+1}&\mbox{if }{\sf sig}(g)=\mathfrak{o},\ {\sf
sig}(h)=\mathfrak{z},\\\ 1||\alpha&\mbox{if }{\sf sig}(g)=\mathfrak{z},\ {\sf
sig}(h)=\alpha\in\\{0,1\\}^{n},\\\ 0||\alpha&\mbox{if }{\sf
sig}(g)=\mathfrak{o},\ {\sf sig}(h)=\alpha\in\\{0,1\\}^{n}\\\
1||\alpha&\mbox{if }{\sf sig}(g)=\alpha\in\\{0,1\\}^{n},\ {\sf
sig}(h)=\mathfrak{o},\\\ 0||\alpha&\mbox{if }{\sf
sig}(g)=\alpha\in\\{0,1\\}^{n},\ {\sf sig}(h)=\mathfrak{z},\\\
1||\alpha&\mbox{if }g\leq h,\ {\sf sig}(g)={\sf
sig}(h)=\alpha\in\\{0,1\\}^{n},\\\ 0||\alpha&\mbox{if }g\geq h,\ {\sf
sig}(g)={\sf sig}(h)=\alpha\in\\{0,1\\}^{n}.\end{array}\right.$ (26)

Store $(f,{\sf sig}(f))$. Proposition 5 assures us that this recursive
procedure generates all $(n+1)$-variable unate functions and their signatures.

To generate all $(n+1)$-variable unate functions, the above method requires
considering all pairs of $n$-variable unate functions, i.e. a total of
$\left(U(n)\right)^{2}$ options. Applying the fitering strategy of Section 4.1
we obtain the value of $[U]_{n}$. Next using Proposition 9 we obtain the value
of ${\sf nd}\mbox{-}[U]_{n}$. We could perform this computation for $n\leq 6$.
The obtained values of $[U]_{n}$ and ${\sf nd}\mbox{-}[U]_{n}$ are shown in
Table 6. To generate all 7-variable unate functions using this option requires
considering $\left(U(6)\right)^{2}\approx 2^{57.8}$ pairs of functions. This
is not feasible on the computing facility available to us.

$n$ | $[U]_{n}$ | ${\sf nd}\mbox{-}[U]_{n}$
---|---|---
0 | 2 | 2
1 | 4 | 2
2 | 10 | 6
3 | 34 | 24
4 | 200 | 166
5 | 3466 | 3266
6 | 829774 | 826308
Table 6: Numbers of equivalence classes of $n$-variable unate and non-
degenerate unate functions for $0\leq n\leq 6$.

To obtain the set of $n$-variable balanced unate functions, after generating
the set of all $n$-variable unate functions, we remove the ones that are
unbalanced. Then to the resulting set, we apply the technique of Section 4.1
to obtain the number $[BU]_{n}$ of equivalence classes of $n$-variable
balanced unate functions. Subsequently, we apply Proposition 9 to obtain the
number ${\sf nd}\mbox{-}[BU]_{n}$ of equivalence classes of $n$-variable non-
degenerate balanced unate functions. The values of $[BU]_{n}$ and ${\sf
nd}\mbox{-}[BU]_{n}$ are shown in Table 7

$n$ | $[BU]_{n}$ | ${\sf nd}\mbox{-}[BU]_{n}$
---|---|---
0 | 0 | 0
1 | 2 | 2
2 | 2 | 0
3 | 6 | 4
4 | 24 | 18
5 | 254 | 230
6 | 50172 | 49918
Table 7: Numbers of equivalence classes of $n$-variable balanced unate and
non-degenerate balanced unate functions for $0\leq n\leq 6$.

##  5 Concluding Remarks

We have obtained the numbers of $n$-variable unate and monotone functions
possessing a combination of some basic properties. Also, we have obtained the
numbers of equivalence classes of $n$-variable unate and monotone functions
also possessing a combination of those same properties. Our work raises a
number of questions that may be pursued in the future. One such question is
whether the techniques for counting monotone functions from the recent works
[12, 11] can be applied to the problem of counting balanced monotone
functions. Another similar question is whether the techniques for counting the
number of equivalence classes of monotone functions from [21, 22] can be
applied to the problem of counting the number of equivalence classes of
balanced monotone functions. A third question is whether the techniques for
counting the number of equivalence classes of monotone functions from [21, 22]
can be applied to the problem of counting the number of equivalence classes of
unate functions. Positive answers to these questions will allow extending the
results that we could obtain up to $n=6$ or $n=7$ to $n=9$.

## Acknowledgement

We are grateful to an anonymous reviewer of the PhD thesis of the first author
for suggesting that the number of $n$-variable non-degenerate unate functions
is equal to $2^{n}$ times the number of $n$-variable non-degenerate monotone
functions.

## References

  * [1] Valentin Bakoev.  Generating and identification of monotone Boolean functions.  In Mathematics and Education in Mathematics, Sofia, pages 226–232, 2003.
  * [2] József Balogh, Dingding Dong, Bernard Lidickỳ, Nitya Mani, and Yufei Zhao.  Nearly all $k$-SAT functions are unate.  https://arxiv.org/pdf/2209.04894.pdf, 2022.
  * [3] Charles R. Baugh.  Generation of representative functions of the NPN equivalence classes of unate Boolean functions.  IEEE Transactions on Computers, 21(12), 1972.
  * [4] Joel Berman and Peter Köhler.  Cardinalities of finite distributive lattices.  Mitt. Math. Sem. Giessen, 121:103–124, 1976.
  * [5] Rodolfo Betancourt.  Derivation of minimum test sets for unate logical circuits.  IEEE Transactions on Computers, 100(11):1264–1269, 1971.
  * [6] Randolph Church.  Nunmerical analysis of certain free distributive structures.  Duke Mathematical Journal, 6(3):732 – 734, 1940.
  * [7] Richard Dedekind.  Über zerlegungen von zahlen durch ihre grössten gemeinsamen teiler.  Gesammelte Werke, 2:103 – 148, 1897.
  * [8] Aaron Feigelson and Lisa Hellerstein.  The forbidden projections of unate functions.  Discrete Applied Mathematics, 77(3):221–236, 1997.
  * [9] Robert Fidytek, Andrzej W. Mostowski, Rafal Somla, and Andrzej Szepietowski.  Algorithms counting monotone Boolean functions.  Inf. Process. Lett., 79(5):203–209, 2001.
  * [10] Yutaka Hata, Masaharu Yuhara, Fujio Miyawaki, and Kazuharu Yamato.  On the complexity of enumerations for multiple-valued Kleenean functions and unate functions.  In 1991 Proceedings of the Twenty-First International Symposium on Multiple-Valued Logic, pages 55–56. IEEE Computer Society, 1991.
  * [11] Lennart Van Hirtum, Patrick De Causmaecker, Jens Goemaere, Tobias Kenter, Heinrich Riebler, Michael Lass, and Christian Plessl.  A computation of $D(9)$ using FPGA supercomputing.  https://arxiv.org/abs/2304.03039, 2023.
  * [12] Christian Jäkel.  A computation of the ninth Dedekind number.  https://arxiv.org/abs/2304.00895, 2023.
  * [13] Andrzej Kisielewicz.  A solution of Dedekind’s problem on the number of isotone Boolean functions.  Journal fur die Reine und Angewandte Mathematik, 1988(386):139 – 144, 1988.
  * [14] Zvi Kohavi.  Switching and finite automata theory.  McGraw-Hill (New York, NY [ua]), 1970.
  * [15] Aleksej D. Korshunov.  Monotone Boolean functions.  Russian Mathematical Surveys, 58(5):929 – 1001, 2003.
  * [16] Karuna K Maitra.  Cascaded switching networks of two-input flexible cells.  IRE Transactions on Electronic Computers, (2):136–143, 1962.
  * [17] William S. Matheson.  Recognition of monotonic and unate cascade realizable functions using an informational model of switching circuits.  IEEE Transactions on Computers, 100(10):1214–1219, 1971.
  * [18] Robert McNaughton.  Unate truth functions.  IRE Transactions on Electronic Computers, EC-10(1):1–6, 1961.
  * [19] Hiroki Morizumi.  Sensitivity, block sensitivity, and certificate complexity of unate functions and read-once functions.  In IFIP International Conference on Theoretical Computer Science, pages 104–110. Springer, 2014.
  * [20] Amar Mukhopadhyay.  Unate cellular logic.  IEEE Transactions on Computers, 100(2):114–121, 1969.
  * [21] Bartłomiej Pawelski.  On the number of inequivalent monotone Boolean functions of 8 variables.  https://arxiv.org/abs/2108.13997, 2021.
  * [22] Bartłomiej Pawelski.  On the number of inequivalent monotone Boolean functions of 9 variables.  https://arxiv.org/abs/2305.06346, 2023.
  * [23] Vijay Pitchumani and Satish S. Soman.  Functional test generation based on unate function theory.  IEEE transactions on computers, 37(6):756–760, 1988.
  * [24] Fred Roberts and Barry Tesman.  Applied Combinatorics, 2nd edition.  Chapman and Hall/CRC, 2009.
  * [25] Tsutomu Sasao and Kozo Kinoshita.  On the number of fanout-free functions and unate cascade functions.  IEEE Transactions on Computers, 28(1):66–72, 1979.
  * [26] Neil J.A. Sloane.  The online encyclopedia of integer sequences.  https://oeis.org/, 1964.
  * [27] Tamon Stephen and Timothy Yusun.  Counting inequivalent monotone Boolean functions.  Discrete Applied Mathematics, 167:15–24, 2014.
  * [28] André Thayse and Jean P. Deschamps.  Logic properties of unate and of symmetric discrete functions.  In Proceedings of the sixth international symposium on Multiple-valued logic, pages 79–87, 1976.
  * [29] Morgan Ward.  Note on the order of free distributive lattices.  Bull. Amer. Math. Soc., 52:423, 1946.
  * [30] Doug Wiedemann.  A computation of the eighth Dedekind number.  Order, 8(1):5 – 6, 1991.
  * [31] Uri Zwick.  A $4n$ lower bound on the combinational complexity of certain symmetric Boolean functions over the basis of unate dyadic boolean functions.  SIAM Journal on Computing, 20(3):499–505, 1991.