\documentclass[12pt]{article}
\usepackage{e-jc}

\usepackage{amsthm,amsmath,amssymb}
\usepackage{tikz}
\usepackage{booktabs}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{caption}

\usetikzlibrary{matrix}
\usetikzlibrary{positioning}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\newcommand{\etal}{\textit{et al.}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\zero}{\hat{0}}
\renewcommand{\algorithmiccomment}[1]{\hfill\small\{#1\}\normalsize}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

% Tikz styles for edges
\tikzset{edge0/.style=dashed}                  % not visited yet
\tikzset{edgea/.style={red, ultra thick,->}}   % addition in red
\tikzset{edgeb/.style={very thick,->}}        % addition in black
\tikzset{edger/.style={very thick,<-}}        % addition in black, reverse direction
\tikzset{edges/.style={cyan,ultra thick,->}}   % subtraction
\tikzset{edgex/.style=ultra thick}             % done

% Tikz styles for elements
% Dot node
\tikzset{eld/.style={draw, circle, inner sep=0, minimum size=0.15cm}}
% Empty node
\tikzset{ele/.style={draw, circle, inner sep=0.05cm, minimum size=0.4cm}}
% Labeled node
\tikzset{ell/.style={draw, circle, inner sep=0.05cm, minimum size=0.5cm}}
% Highlighted labeled node
\tikzset{elh/.style={draw, circle, inner sep=0.05cm, minimum size=0.5cm, blue, ultra thick}}

% Slightly reduce column separation in tables
\setlength{\tabcolsep}{4.9pt}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Fast M\"obius inversion in semimodular lattices\\and ER-labelable posets}

% authors in alphabetical order

\author{Petteri Kaski and Jukka Kohonen\\
  \small Department of Computer Science\\[-0.8ex]
  \small Aalto University\\[-0.8ex]
  \small Espoo, Finland\\
  \small\tt \{petteri.kaski,jukka.kohonen\}@aalto.fi
  \and
  Thomas Westerb\"ack\\
  \small Department of Mathematics and Systems Analysis\\[-0.8ex]
  \small Aalto University\\[-0.8ex]
  \small Espoo, Finland\\
  \small\tt thomas.westerback@aalto.fi
  }

\date{\dateline{March 8, 2016}{XX}\\
\small Mathematics Subject Classifications: 06C10, 06A07, 68W40, 68R05}

% 06C10 Semimodular lattices
% 06A07 Combinatorics of partially ordered sets
% 68W40 Computer science: Analysis of algorithms
% 68R05 Computer science: Combinatorics

\begin{document}

\maketitle

\begin{abstract}
  We consider the problem of fast zeta and M\"obius transforms in
  finite posets, particularly in lattices.  It has previously been
  shown that for a certain family of lattices, zeta and M\"obius
  transforms can be computed in $O(e)$ elementary arithmetic
  operations, where $e$ denotes the size of the covering relation.  We
  show that this family is exactly that of geometric lattices.  We
  also extend the algorithms so that they work in $e$ operations for
  all semimodular lattices, including chains and divisor lattices.
  Finally, for both transforms, we provide a more general algorithm
  that works in $e$~operations for all ER-labelable posets.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
\label{sec:intro}

Fast methods for computing zeta and M\"obius transforms in finite
posets are important for many algorithms of combinatorial nature, such
as graph coloring \cite{bjorklund2007} and fast Fourier transforms on
inverse semigroups \cite{malandro2010}.  From an algebraic
perspective, these transforms are basis-changing isomorphisms
analogous to the fast Fourier transform \cite{bjorklund2015}.  From a
computational perspective, the zeta transform is related to
\emph{ensemble computation}, where one is required to compute several
different products of inputs, possibly sharing common subexpressions,
and the challenge is to minimize the number of elementary
multiplications perfomed (see Garey and Johnson~\cite{garey1979}).

Let $(P,\le)$ be a finite partially ordered set, or \emph{poset}, with
$|P|=v$ elements, and let $f : P \to A$ be a function to an abelian
group $A$.  The \emph{zeta transform} of $f$ is the function $g:
P \to A$ such that, for all $y \in P$,
\begin{equation*}
  g(y) = \sum_{x \le y} f(x).
\end{equation*}

For computational purposes, the function $f$ can be represented as a
$v$-element row vector $\vec{f} = (f(x))_{x \in P}$, and $g$
similarly.  The transformation $\vec{f} \mapsto \vec{g}$ is linear,
and defined by the $v \times v$ matrix~$\zeta$, where $\zeta_{xy} = 1$
if $x\le y$, and $0$ otherwise.  The obvious way to compute the zeta
transform is to perform the matrix-vector multiplication
$\vec{g}=\vec{f}\zeta$, incurring $O(v^2)$ elementary additions.
However, the special structure of the transformation gives hope of
performing it faster, in particular for posets of some specific form.
It should perhaps be emphasized that a method of \emph{computing} the
zeta transform need not involve any explicit construction of the
matrix~$\zeta$.

For a given poset, we represent the computation from~$f$ to its zeta
transform~$g$ as a \emph{straight-line program} (see B\"urgisser
\etal~\cite{burgisser1997}), a sequence of elementary pairwise
arithmetic operations (additions and subtractions) to be executed in
turn, without loops or conditional statements.  We seek to minimize
the length of the program, that is, the number of arithmetic
operations performed.

The zeta transform is always invertible, since $\zeta$ is an upper
triangular matrix with ones on the main diagonal, assuming the matrix
lists the elements of $P$ in a linear order that is an extension
of~$P$.  We also want to construct a short straight-line program for
the inverse transform $\mu = \zeta^{-1}$, called the \emph{M\"obius
  transform}.  The matrices $\zeta$ and $\mu$ are in fact
representations of the zeta and M\"obius functions of the poset.  We
refer to Stanley~\cite{stanley2011} for further discussion.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Measures of the complexity}

We relate the program length to certain parameters characterizing the
complexity of the poset: the number of elements or vertices ($v$), the
number of join-irreducible elements ($n$), and the number of edges in
the Hasse diagram of the poset ($e$).

In a lattice we always have $v-1 \le e \le vn$.\footnote{The first
  inequality holds because every non-maximal element has at least one
  upward edge.  The latter inequality follows by considering the
  upward edges of an arbitrary element $x$ and the spectrum map
  $\varphi$, as defined in Section~\ref{sec:preliminaries}.  If both
  $y \gtrdot x$ and $z \gtrdot x$, then $\varphi(y) \setminus
  \varphi(x)$ and $\varphi(z) \setminus \varphi(x)$ must be disjoint,
  otherwise $y$ and $z$ would have two incomparable lower bounds.
  Hence $x$ has at most $n$ upward edges, and the whole lattice has $e
  \le vn$.}  As~an example where $e$ is large, consider the lattice of
subsets of an $n$-element set.  This lattice has $v=2^n$ elements, of
which $n$ are join-irreducible (the singletons), and $e=2^{n-1}n =
\Theta(vn)$ edges.  Both zeta and M\"obius transforms can be computed
in $\Theta(e)=\Theta(vn)$ operations by Yates's
construction~\cite{yates1937}.  As~an example where $e$ is small,
consider the $v$-element chain, which has $n=e=v-1$, thus $vn =
\Theta(e^2)$.  In a chain both transforms are easily computed in $e$
operations.

The parameter $e$ also appears in a lower bound by
Kennes~\cite{kennes1992}: for any lattice, any sequence of additions
that computes the zeta transform has length at least~$e$.  Note that
this lower bound does not apply to posets in general; as a
counterexample, Bj\"orklund \etal~\cite[\S 6]{bjorklund2015} exhibit a
non-lattice bipartite poset whose zeta transform can be computed in
$O(\sqrt{e})$ additions, using a construction by
Valiant~\cite{valiant1986}.

For any lattice, Bj\"orklund \etal~\cite{bjorklund2015} construct both
programs with length $O(vn)$.  This upper bound is always valid but
possibly quite crude.  A tighter length bound $O(e)$ applies for
lattices fulfilling the condition that for any element~$x$ and any
join-irreducible element~$i$ that is not below $x$, the join $x \vee
i$ covers~$x$.  Examples of such lattices include the subset lattice,
the partition lattice, and the lattice of subspaces of a finite vector
space.  For some lattices, the resulting program length is highly
dependent upon the choice of certain details in the construction.  As
a simple example, with the $v$-element chain one choice leads to the
optimal $O(e)$ additions, while another choice leads to $\Theta(e^2)$
additions.  We seek here a better understanding of posets that admit
fast computation of the zeta and M\"obius transforms.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Our results}

First we show that the aforementioned condition by Bj\"orklund
\etal~\cite{bjorklund2015} is equivalent to the the lattice being
\emph{geometric} (semimodular and atomic).  Thus in any geometric
lattice both transforms can be done in $O(e)$ arithmetic operations.
This result also provides an alternative ``single-axiom''
characterization of geometric lattices.

Second, we show that atomicity is not needed: in any
\emph{semimodular} lattice, the construction can be done in a manner
that yields a program of length~$e$, matching Kennes's lower bound.
The optimal straight-line programs for chains now follow as a special
case, as well as for other semimodular lattices such as the lattice of
positive divisors of an integer.

Third, for further generality, we show that if a poset admits a
certain kind of \emph{edge labeling}, then the transforms can be done
in exactly $e$ arithmetic operations by following the edges in an
order implied by their labels.  The idea of such labelings goes back
to Stanley~\cite{stanley1972}, who studied edge labelings in the
context of counting chains in a lattice.  Edge labelings were further
studied and generalized in a series of papers by Bj\"orner and Wachs;
for bibliography we refer to Stanley~\cite[Chapter~3]{stanley2011} and
Bj\"orner and Wachs~\cite[Section~5]{bjorner1996}.  The class of
posets admitting zeta and M\"obius transforms in $e$~operations now
encompasses the family of \emph{ER-labelable} posets.  Semimodular
lattices are included as a special case, as well as lower semimodular
lattices (by duality) and supersolvable lattices.

The new results are summarized in Table~\ref{table:summary} in context
with previous results.  Note that the family of ER-labelable posets
subsumes all other families in the table (except for ``all
lattices'').

\begin{table}[tb]
  \centering
  \begin{tabular}{lll}
    \toprule
    Poset family & Program length & Reference \\
    \midrule
    all lattices            & $O(v^2)$     & matrix-vector multiplication \\
    subset lattices         & $O(vn)=O(e)$ & Yates~\cite{yates1937} \\
    distributive lattices (zeta only)   & $O(vn)$      & Parviainen and Koivisto \cite{parviainen2010} \\
    all lattices            & $O(vn)$      & Bj\"orklund \etal~\cite{bjorklund2015} \\
    lattices with a certain condition & $O(e)$       & Bj\"orklund \etal~\cite{bjorklund2015} \\
    geometric lattices      & $O(e)$       & new (\S2) \\
    semimodular lattices    & $O(e)$       & new (\S3) \\
    ER-labelable posets     & $O(e)$       & new (\S4) \\
    \bottomrule
  \end{tabular}
  \caption{Program lengths for the zeta and M\"obius
    transforms.}
  \label{table:summary}
\end{table}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Preliminaries}
\label{sec:preliminaries}

For a general treatment on posets and lattices we refer to
Gr\"atzer~\cite{gratzer2011} and Stanley~\cite{stanley2011}.  In the
present work, a poset $P$ or a lattice $L$ is always finite.  The
covering relation is denoted by $\lessdot$, and the set of covering
pairs, or edges of the Hasse diagram, is $E = \{(x,y) : x \lessdot
y\}$.  An element $x \in P$ is \emph{join-irreducible} if it covers
exactly one element, and $I$ is the set of join-irreducible elements.
Poset size is characterized by three quantities: the number of
elements $v=|P|$; the number of join-irreducible elements $n=|I|$; and
the number of edges $e = |E|$.

% Note that Grätzer uses "atomistic" for atomic, and "atomic" for
% something else.

% This definition of semimodularity is found in Grätzer's Exercise 2.1.

Without loss of generality, we assume that the join-irreducible
elements of a lattice are denoted by integers $I=[n]$.  The
\emph{spectrum map} of an element $x \in L$ is $\varphi(x) = \{h \in I
: h \le x\}$, and for $i \le n$, the \emph{prefix spectrum map} is
$\varphi_i(x) = \{h \in [i] : h \le x\}$, with $\varphi_0(x) =
\varnothing$.

In a lattice the minimum element is $\zero$, and an element that
covers $\zero$ is an \emph{atom}.  A~lattice is \emph{atomic} if every
element is a join of atoms.  A~lattice is \emph{(upper) semimodular},
if for any two elements $x$ and $y$ such that $x$ covers $x \wedge y$,
the join $x \vee y$ in turn covers $y$.  The dual of a semimodular
lattice is \emph{lower semimodular}.  An~atomic semimodular lattice is
\emph{geometric}.  Examples of geometric lattices include subset
lattices and partition lattices.  Examples of non-atomic semimodular
lattices include the chain of three or more elements, and the divisor
lattice of an integer that is not a product of distinct primes (see
Stanley \cite[\S 3.3]{stanley2011}).

Theorem 1.3 of Bj\"orklund \etal~\cite{bjorklund2015} shows that both
zeta and M\"obius transforms can be done in $O(e)$ arithmetic
operations in any finite lattice $L$ fulfilling the following
condition:
\begin{equation}
  x \vee i \gtrdot x \qquad \text{for all $x \in L$, $i \in I$, $x \not\ge i$}.
  \label{eq:x}
\end{equation}
The following theorem provides an alternative characterization.

\begin{theorem} 
  A finite lattice fulfills condition \eqref{eq:x} if and only if it
  is geometric.
  \label{thm:geom}
\end{theorem}
\begin{proof}
  For the ``if'' direction, let $L$ be a finite geometric lattice,
  $x\in L$, and $i\in I$ such that $x \not\ge i$.  Since $L$ is atomic,
  $i$ is an atom, and $i \gtrdot \zero = x \wedge i$.  Now by
  semimodularity $x \vee i \gtrdot x$.

  For the ``only if'' direction, let $L$ be a finite lattice where
  \eqref{eq:x} holds.  For any join-irreducible $i$, choosing
  $x=\zero$ shows that $i \gtrdot \zero$, thus $L$ is atomic.

  Let $x$ and $y$ be elements such that $y \gtrdot x \wedge y = m$.
  Choose a join-irreducible element $i$ such that $i \le y$ but $i
  \not\le x$.  Now $y=m \vee i$, so $x \vee y = x \vee m \vee i = x
  \vee i$, which covers $x$ by condition \eqref{eq:x}.  Thus $L$ is
  semimodular.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Fast M\"obius inversion in semimodular lattices}

We shall next show that atomicity is unnecessary for fast zeta and
M\"obius transforms: semimodularity by itself suffices to ensure
programs of length~$e$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Fast zeta transform}

We recall the fast zeta transform algorithm of Bj\"ork\-lund
\etal~\cite[\S 3.2]{bjorklund2015}.  While the original algorithm is
described by embedding the lattice $L$ into a set family
$\mathcal{L}$, for the sake of transparency we describe the algorithm
directly in terms of lattice operations.

\begin{algorithm}[H]
  \caption{Fast zeta transform}
  \begin{algorithmic}[1]
    \REQUIRE Lattice $L$ with join-irreducibles $I=[n]$
    \ENSURE Straight-line program that, given $f$, computes its zeta transform $g$
    \FORALL{$x \in L$}
    \PRINT ``$g(x) \leftarrow f(x)$'' \COMMENT{Initialization}
    \ENDFOR
    \FOR{$i = 1, 2, \ldots, n$}
    \FORALL{$x \in L$ such that $x \not\ge i$}
    \STATE $y \leftarrow x \vee i$
    \IF {$\varphi_{i-1}(x) = \varphi_{i-1}(y)$}
    \PRINT ``$g(y) \leftarrow g(y) + g(x)$'' \COMMENT{Addition}
    \ENDIF
    \ENDFOR
    \ENDFOR
  \end{algorithmic}
  \label{alg:fastzeta}
\end{algorithm}

Algorithm~\ref{alg:fastzeta} takes as input a representation of the
lattice structure, and outputs a sequence of additions to be
performed.  Theorem~1.1 of Bj\"orklund \etal~\cite{bjorklund2015}
shows that the resulting straight-line program indeed computes the
zeta transform for any lattice, regardless of how $I$~is ordered.  The
outer loop beginning on line~4 is executed $n$ times, and the inner
loop at most $|L|=v$ times, so at most $O(vn)$ additions are used; but
the precise number may be much smaller, depending on lattice structure
and the ordering of~$I$.  Consider a chain of $v$ elements, with
$n=e=v-1$.  Bottom-up traversal incurs $e$~additions, which is the
optimal number; each addition proceeds along an edge of the chain.  In
contrast, top-down traversal is suboptimal and incurs $\Theta(e^2)$
additions \cite{bjorklund2015}, many of which involve two distant
elements that do not share an edge.

The observation that bottom-up traversal leads to fewer additions can
be generalized to all semimodular lattices.  The following theorem
provides the optimal arrangement, whereby each addition corresponds to
an edge of the lattice.

\begin{theorem} 
  In a semimodular lattice with $e$ edges, the join-irreducible
  elements can be ordered so that Algorithm~\ref{alg:fastzeta}
  generates exactly $e$ additions.
  \label{thm:semizeta}
\end{theorem}
\begin{proof}
  Order the join-irreducible elements by increasing rank, breaking
  ties arbitrarily.  Consider the situation when the condition on
  line~7 succeeds.

  Since $i$ is join-irreducible, there is a unique element $k$ such
  that $k \lessdot i$.  Since $k$ has a rank strictly smaller than
  $i$, it follows that $\varphi_{i-1}(k) = \varphi(k)$.  Now, because
  $k \le i \le x \vee i = y$, we have
  \[
  \varphi(k) = \varphi_{i-1}(k) \subseteq \varphi_{i-1}(y) = \varphi_{i-1}(x)
  \subseteq \varphi(x),
  \]
  where the equality $\varphi_{i-1}(y) = \varphi_{i-1}(x)$ is true due
  to the condition on line~7.
  
  Since $\varphi(k) \subseteq \varphi(x)$, it follows that $k \le x$.
  Thus since $i \not\le x$ we must have $x \wedge i = k$, implying $i
  \gtrdot k = x \wedge i$, and then $x \vee i \gtrdot x$ by
  semimodularity.

  We have seen that whenever an addition is generated on line~8, it
  involves elements $x$ and $y$ such that $x \lessdot y$, so we can
  associate the addition with an edge of the Hasse diagram.  No two
  additions are associated with the same edge, so the number of
  additions is at most~$e$.  Conversely, each edge is visited by the
  algorithm, since if $x \lessdot y$, then $\varphi(x) \ne
  \varphi(y)$, and the edge is visited with the smallest $i$ such that
  $\varphi_i(x) \ne \varphi_i(y)$.  Hence the algorithm perfoms
  exactly $e$ additions.
\end{proof}

Figure~\ref{fig:fastzeta} illustrates how the zeta transform proceeds
in a semimodular lattice that has 9~edges.  Nine additions are
performed in four phases, corresponding to the four join-irreducible
elements of the lattice.

\begin{figure}[p]
  \begin{tikzpicture}
    \matrix(a)[matrix of math nodes, column sep=0cm, row sep=0.5cm]{
      && \node[ell](6){6}; \\
      \node[ell](3){3}; && \node[ell](5){5}; && \node[ell](4){4}; \\
      & \node[elh](1){1}; && \node[ell](2){2}; \\
      && \node[ell](0){0}; \\};
    \draw[edgea] (0)--(1);
    \draw[edgea] (2)--(5);
    \draw[edgea] (4)--(6);
    \draw[edge0] (0)--(2);
    \draw[edge0] (1)--(5);
    \draw[edge0] (3)--(6);
    \draw[edge0] (1)--(3);
    \draw[edge0] (5)--(6);
    \draw[edge0] (2)--(4);
  \end{tikzpicture}
  \hfill
  \begin{tikzpicture}
    \matrix(a)[matrix of math nodes, column sep=0cm, row sep=0.5cm]{
      && \node[ell](6){6}; \\
      \node[ell](3){3}; && \node[ell](5){5}; && \node[ell](4){4}; \\
      & \node[ell](1){1}; && \node[elh](2){2}; \\
      && \node[ell](0){0}; \\};
    \draw[edgex] (0)--(1);
    \draw[edgex] (2)--(5);
    \draw[edgex] (4)--(6);
    \draw[edgea] (0)--(2);
    \draw[edgea] (1)--(5);
    \draw[edgea] (3)--(6);
    \draw[edge0] (1)--(3);
    \draw[edge0] (5)--(6);
    \draw[edge0] (2)--(4);
  \end{tikzpicture}
  \hfill
  \begin{tikzpicture}
    \matrix(a)[matrix of math nodes, column sep=0cm, row sep=0.5cm]{
      && \node[ell](6){6}; \\
      \node[elh](3){3}; && \node[ell](5){5}; && \node[ell](4){4}; \\
      & \node[ell](1){1}; && \node[ell](2){2}; \\
      && \node[ell](0){0}; \\};
    \draw[edgex] (0)--(1);
    \draw[edgex] (2)--(5);
    \draw[edgex] (4)--(6);
    \draw[edgex] (0)--(2);
    \draw[edgex] (1)--(5);
    \draw[edgex] (3)--(6);
    \draw[edgea] (1)--(3);
    \draw[edgea] (5)--(6);
    \draw[edge0] (2)--(4);
  \end{tikzpicture}
  \hfill
  \begin{tikzpicture}
    \matrix(a)[matrix of math nodes, column sep=0cm, row sep=0.5cm]{
      && \node[ell](6){6}; \\
      \node[ell](3){3}; && \node[ell](5){5}; && \node[elh](4){4}; \\
      & \node[ell](1){1}; && \node[ell](2){2}; \\
      && \node[ell](0){0}; \\};
    \draw[edgex] (0)--(1);
    \draw[edgex] (2)--(5);
    \draw[edgex] (4)--(6);
    \draw[edgex] (0)--(2);
    \draw[edgex] (1)--(5);
    \draw[edgex] (3)--(6);
    \draw[edgex] (1)--(3);
    \draw[edgex] (5)--(6);
    \draw[edgea] (2)--(4);
  \end{tikzpicture}
  \\[0.25cm]
  \begin{minipage}{0.55\textwidth}
    \captionsetup{width=\linewidth}
    \caption{Fast zeta transform in a semimodular lattice.  In each
      phase the join-irreducible element $i$ being considered is
      highlighted in blue.  Red arrows indicate addition along edges.
      Thick black edges have been visited already, and dashed edges
      are yet unvisited.}
    \label{fig:fastzeta}
  \end{minipage}
  \hfill
  \begin{tabular}{ll}
    \toprule
    \multicolumn{2}{l}{Straight-line program} \\
    \midrule
    Phase 1 & $g(1) \leftarrow g(1) + g(0)$ \\
    & $g(5) \leftarrow g(5) + g(2)$ \\
    & $g(6) \leftarrow g(6) + g(4)$ \\
    \midrule
    Phase 2 & $g(2) \leftarrow g(2) + g(0)$ \\
    & $g(5) \leftarrow g(5) + g(1)$ \\
    & $g(6) \leftarrow g(6) + g(3)$ \\
    \midrule
    Phase 3 & $g(3) \leftarrow g(3) + g(1)$ \\
    & $g(6) \leftarrow g(6) + g(5)$ \\
    \midrule
    Phase 4 & $g(4) \leftarrow g(4) + g(2)$ \\
    \bottomrule
  \end{tabular}
  %
  \\[1cm]
  %
  \begin{tikzpicture}
    \matrix(a)[matrix of math nodes, column sep=0cm, row sep=0.5cm]{
      && \node[ell](6){6}; \\
      \node[ell](3){3}; && \node[ell](5){5}; && \node[elh](4){4}; \\
      & \node[ell](1){1}; && \node[ell](2){2}; \\
      && \node[ell](0){0}; \\};
    \draw[edge0] (0)--(1);
    \draw[edge0] (2)--(5);
    \draw[edge0] (4)--(6);
    \draw[edge0] (0)--(2);
    \draw[edge0] (1)--(5);
    \draw[edge0] (3)--(6);
    \draw[edge0] (1)--(3);
    \draw[edge0] (5)--(6);
    \draw[edges] (2)--(4);
  \end{tikzpicture}
  \hfill
  \begin{tikzpicture}
    \matrix(a)[matrix of math nodes, column sep=0cm, row sep=0.5cm]{
      && \node[ell](6){6}; \\
      \node[elh](3){3}; && \node[ell](5){5}; && \node[ell](4){4}; \\
      & \node[ell](1){1}; && \node[ell](2){2}; \\
      && \node[ell](0){0}; \\};
    \draw[edge0] (0)--(1);
    \draw[edge0] (2)--(5);
    \draw[edge0] (4)--(6);
    \draw[edge0] (0)--(2);
    \draw[edge0] (1)--(5);
    \draw[edge0] (3)--(6);
    \draw[edges] (1)--(3);
    \draw[edges] (5)--(6);
    \draw[edgex] (2)--(4);
  \end{tikzpicture}
  \hfill
  \begin{tikzpicture}
    \matrix(a)[matrix of math nodes, column sep=0cm, row sep=0.5cm]{
      && \node[ell](6){6}; \\
      \node[ell](3){3}; && \node[ell](5){5}; && \node[ell](4){4}; \\
      & \node[ell](1){1}; && \node[elh](2){2}; \\
      && \node[ell](0){0}; \\};
    \draw[edge0] (0)--(1);
    \draw[edge0] (2)--(5);
    \draw[edge0] (4)--(6);
    \draw[edges] (0)--(2);
    \draw[edges] (1)--(5);
    \draw[edges] (3)--(6);
    \draw[edgex] (1)--(3);
    \draw[edgex] (5)--(6);
    \draw[edgex] (2)--(4);
  \end{tikzpicture}
  \hfill
  \begin{tikzpicture}
    \matrix(a)[matrix of math nodes, column sep=0cm, row sep=0.5cm]{
      && \node[ell](6){6}; \\
      \node[ell](3){3}; && \node[ell](5){5}; && \node[ell](4){4}; \\
      & \node[elh](1){1}; && \node[ell](2){2}; \\
      && \node[ell](0){0}; \\};
    \draw[edges] (0)--(1);
    \draw[edges] (2)--(5);
    \draw[edges] (4)--(6);
    \draw[edgex] (0)--(2);
    \draw[edgex] (1)--(5);
    \draw[edgex] (3)--(6);
    \draw[edgex] (1)--(3);
    \draw[edgex] (5)--(6);
    \draw[edgex] (2)--(4);
  \end{tikzpicture}
  \\[0.5cm]
  \begin{minipage}{0.55\textwidth}
    \captionsetup{width=\linewidth}
    \caption{Fast M\"obius transform in a semimodular lattice.  In
      each phase the join-irreducible element $i$ being considered is
      highlighted in blue.  Cyan arrows indicate subtraction along
      edges.  Thick black edges have been visited already, and dashed
      edges are yet unvisited.}
    \label{fig:fastmobius}
  \end{minipage}
  \hfill
  \begin{tabular}{ll}
    \toprule
    \multicolumn{2}{l}{Straight-line program} \\
    \midrule
    Phase 4 & $f(4) \leftarrow f(4) - f(2)$ \\
    \midrule
    Phase 3 & $f(6) \leftarrow f(6) - f(5)$ \\
    & $f(3) \leftarrow f(3) - f(1)$ \\
    \midrule
    Phase 2 & $f(6) \leftarrow f(6) - f(3)$ \\
    & $f(5) \leftarrow f(5) - f(1)$ \\
    & $f(2) \leftarrow f(2) - f(0)$ \\
    \midrule
    Phase 1 & $f(6) \leftarrow f(6) - f(4)$ \\
    & $f(5) \leftarrow f(5) - f(2)$ \\
    & $f(1) \leftarrow f(1) - f(0)$ \\
    \bottomrule
  \end{tabular}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Fast M\"obius transform}

Next we shall show the corresponding result for the M\"obius
transform, which computes $f$ from~$g$.  Again we start with the
algorithm by Bj\"orklund \etal~\cite[\S 3.6]{bjorklund2015} expressed
in terms of lattice operations.

\begin{algorithm}[H]
  \caption{Fast M\"obius transform}
  \begin{algorithmic}[1]
    \REQUIRE Lattice $L$ with join-irreducibles $I=[n]$
    \ENSURE Straight-line program that, given $g$, computes its M\"obius transform $f$
    \FORALL{$x \in L$}
    \PRINT ``$f(x) \leftarrow g(x)$'' \COMMENT{Initialization}
    \ENDFOR
    \FOR{$i = n, n-1, \ldots, 1$}
    \FORALL{$x \in L$ such that $x \not\ge i$}
    \STATE $y \leftarrow x \vee i$
    \IF {$\varphi_{i-1}(x) = \varphi_{i-1}(y)$}
    \PRINT ``$f(y) \leftarrow f(y) - f(x)$'' \COMMENT{Subtraction}
    \ENDIF
    \ENDFOR
    \ENDFOR
  \end{algorithmic}
  \label{alg:fastmobius}
\end{algorithm}

Algorithm~\ref{alg:fastmobius} is similar to the zeta transform
algorithm, with a few crucial changes.  The join-irreducible elements
are visited in reverse order, the roles of $f$~and~$g$ are inversed,
and subtraction replaces the addition on line~8.  Since the conditions
on lines 5--7 are the same as before, the next theorem follows.

\begin{theorem} 
  In a semimodular lattice with $e$ edges, the join-irreducible
  elements can be ordered so that Algorithm~\ref{alg:fastmobius}
  generates exactly $e$ subtractions.
  \label{thm:semimobius}
\end{theorem}
\begin{proof}
  Order and name the join-irreducible elements as $1,2,\ldots,n$ by
  increasing rank, breaking ties arbitrarily.  When the condition on
  line~7 succeeds, it holds that $x \lessdot y$, by the same reasoning
  as in Theorem~\ref{thm:semizeta}.  Thus the subtraction on line~8
  can be associated with that edge, and total the number of
  subtractions performed equals the number of edges.
\end{proof}

Figure~\ref{fig:fastmobius} illustrates how the M\"obius transform
proceeds on a semimodular lattice.  Note that join-irreducible
elements are considered in the reverse order $4,3,2,1$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Fast M\"obius inversion in posets labelable with unique rising chains}
\label{sec:ulabel}

Our next addition algorithm (Algorithm~\ref{alg:addalong}) is
constructed to proceed along the edges of a poset.  By this we mean
that the straight-line program consists of $e$~lines of the form
\begin{equation*}
  g(y) \leftarrow g(y) + g(x),
\end{equation*}
one for each edge $(x,y)$, where $x \lessdot y$.  The edges are
visited in an order specified by an \emph{edge labeling} $\lambda: E
\to \Z$.  The algorithm requires the labels to be distinct so that the
order is unambiguous.  The inverse transform is obtained by reversing
the order of operations and replacing additions with subtractions
(Algorithm~\ref{alg:subalong}).

\begin{algorithm}[H]
  \caption{Add along edges}
  \begin{algorithmic}[1]
    \REQUIRE Poset $P$ with injective edge labeling $\lambda: E \to \Z$
    \ENSURE Straight-line program
    \FORALL{$x \in P$}
    \PRINT ``$g(x) \leftarrow f(x)$'' \COMMENT{Initialization}
    \ENDFOR
    \FORALL{$(x,y) \in E$ in increasing order of $\lambda$}
    \PRINT ``$g(y) \leftarrow g(y) + g(x)$''  \COMMENT{Addition}
    \ENDFOR
  \end{algorithmic}
  \label{alg:addalong}
\end{algorithm}

\begin{algorithm}[H]
  \caption{Subtract along edges}
  \begin{algorithmic}[1]
    \REQUIRE Poset $P$ with injective edge labeling $\lambda: E \to \Z$
    \ENSURE Straight-line program
    \FORALL{$x \in P$}
    \PRINT ``$f(x) \leftarrow g(x)$'' \COMMENT{Initialization}
    \ENDFOR
    \FORALL{$(x,y) \in E$ in decreasing order of $\lambda$}
    \PRINT ``$f(y) \leftarrow f(y) - f(x)$''  \COMMENT{Subtraction}
    \ENDFOR
  \end{algorithmic}
  \label{alg:subalong}
\end{algorithm}

Both Algorithms~\ref{alg:addalong} and~\ref{alg:subalong} generate
exactly $e$ operations by design, in contrast to
Algorithms~\ref{alg:fastzeta} and~\ref{alg:fastmobius}, which do so
for semimodular lattices but not in general.  We will next formulate a
sufficient condition to ensure that Algorithm~\ref{alg:addalong}
computes the zeta transform (and that consequently
Algorithm~\ref{alg:subalong} computes the M\"obius transform).

Consider two comparable elements $x \le y$ and an unrefinable chain
$C$ from $x$ to $y$,
\begin{equation*}
  x = x_0 \lessdot x_1 \lessdot \cdots \lessdot x_m = y.
\end{equation*}
With a labeling $\lambda: E \to \Z$, we say that $C$ is \emph{rising}
if its labels are strictly increasing,
\begin{equation*}
  \lambda(x_0,x_1) < \lambda(x_1,x_2) < \cdots < \lambda(x_{m-1},x_m).
\end{equation*}
An edge labeling $\lambda: E \to \Z$ is an \emph{ER-labeling} (edge
rising labeling) if, for each pair of elements $x \le y$, there is a
unique rising chain from $x$ to~$y$.\footnote{The name ``ER-labeling''
  is due to Bj\"orner and Wachs~\cite[Definition~5.2]{bjorner1996}.
  Strictly speaking their definition applies to a \emph{chain-edge
    labeling} induced by an edge labeling.  We use here a simpler
  definition as edge labelings are sufficient to our present
  purposes.}

If $\lambda$ is an injective ER-labeling and $C$ is a rising chain
from $x$ to $y$, then Algorithm~\ref{alg:addalong} performs additions
along $C$ in the chain order.  Thus the input term $f(x)$ propagates
along $C$ to the output $g(y)$.  Conversely, if $C$ is not rising,
then some of the additions in the chain are performed out of the chain
order, and $f(x)$ does \emph{not} propagate to $g(y)$ along $C$.
Figure~\ref{fig:erzeta} illustrates this in a poset equipped with an
ER-labeling.  Hence we have following sufficient condition.

\begin{figure}[tb]
  \begin{minipage}{0.32\textwidth}
    \centering
    \begin{tikzpicture}[baseline=(current bounding box.center)]
      \matrix(a)[matrix of nodes, column sep=0.5cm, row sep=0.6cm]{
        & \node[ell](s){$s$}; \\
        \node[ell](r){$r$}; && \node[ell](u){$u$}; \\
        \node[ell](q){$q$}; && \node[ell](t){$t$}; \\
        & \node[ell](p){$p$}; \\};
      \draw[edgeb] (p)--(q) node[midway,below left] {1};
      \draw[edgeb] (q)--(r) node[midway,left] {2};
      \draw[edgeb] (r)--(s) node[midway,above left] {3};
      \draw[edgeb] (p)--(t) node[midway,below right] {5};
      \draw[edgeb] (t)--(u) node[midway,right] {4};
      \draw[edgeb] (u)--(s) node[midway,above right] {6};
      \draw[edgeb] (q)--(u) node[midway,above left] {7};
    \end{tikzpicture}
  \end{minipage}
  \hfill
  \begin{minipage}{0.32\textwidth}
    \centering
    \begin{tikzpicture}[baseline=(current bounding box.center)]
      \matrix(a)[matrix of nodes, column sep=0.5cm, row sep=0.6cm]{
        & \node[ell](s){$s$}; \\
        \node[ell](r){$r$}; && \node[ell](u){$u$}; \\
        \node[ell](q){$q$}; && \node[ell](t){$t$}; \\
        & \node[ell](p){$p$}; \\};
      \draw[edgeb] (p)--(q) node[midway,below left] {1};
      \draw[edgeb] (q)--(r) node[midway,left] {2};
      \draw[edgeb] (r)--(s) node[midway,above left] {3};
      \draw[edgeb] (t)--(u) node[midway,right] {4};
      \draw[edgeb] (u)--(s) node[midway,above right] {6};
    \end{tikzpicture}
  \end{minipage}
  \hfill
  \begin{minipage}{0.32\textwidth}
    \centering
    \begin{tikzpicture}[baseline=(current bounding box.center)]
      \matrix(a)[matrix of nodes, column sep=0.5cm, row sep=0.6cm]{
        & \node[ell](s){$s$}; \\
        \node[ell](r){$r$}; && \node[ell](u){$u$}; \\
        \node[ell](q){$q$}; && \node[ell](t){$t$}; \\
        & \node[ell](p){$p$}; \\};
      \draw[edgeb] (p)--(q) node[midway,below left] {1};
      \draw[edgeb] (t)--(u) node[midway,right] {4};
      \draw[edgeb] (q)--(u) node[midway,above left] {7};
    \end{tikzpicture}
  \end{minipage}
  \caption{\textbf{Left:} A poset with an injective ER-labeling.
    \textbf{Center:} The rising chains that propagate input terms to
    $g(s)$.  Note that the input term from each element below~$s$
    appears exactly once in the result.  For example, $f(q)$
    propagates to $g(s)$ along the rising chain $q \lessdot r \lessdot
    s$, but not along the non-rising chain $q \lessdot u \lessdot s$.
    \textbf{Right:} The rising chains that propagate input terms to
    $g(u)$.}
  \label{fig:erzeta}
\end{figure}

\begin{proposition}
  If $\lambda$ is an ER-labeling, then the straight-line programs from
  Algorithms~\ref{alg:addalong} and~\ref{alg:subalong} compute the
  zeta and M\"obius transforms, respectively.
  \label{prop:erzeta}
\end{proposition}
\begin{proof}
  For each pair $x \le y$, the straight-line program from
  Algorithm~\ref{alg:addalong} propagates $f(x)$ up to $g(y)$ exactly
  once, along the unique rising chain from $x$ to $y$.  Thus for each
  element $y \in P$, the output $g(y)$ equals $\sum_{x \le y} f(x)$ as
  required.  Hence the result is the zeta transform.

  The program from Algorithm~\ref{alg:subalong} consists of subtractions
  that undo the additions in reverse order, hence it performs the
  M\"obius transform.
\end{proof}

A poset that admits an ER-labeling is \emph{ER-labelable}.  An
ER-labeling is not necessarily injective as required by
Algorithms~\ref{alg:addalong} and~\ref{alg:subalong}, but an injective
ER-labeling can be produced as follows.

\begin{proposition}
  If a poset has an ER-labeling, then it also has an injective
  ER-labeling.
  \label{prop:injective}
\end{proposition}
\begin{proof}
  Let $P$ be a poset with an ER-labeling $\lambda$.  Order the edges
  by $\lambda$; among edges that have the same label, order by their
  first elements in descending order (with respect to the poset
  order~$\le$).  Break any remaining ties arbitrarily.  With the edges
  thus ordered, define an injective labeling $\lambda'$ by assigning
  labels $1,2,\ldots,e$ in order.

  Consider now an unrefinable chain $C$.  If $C$ is not rising under
  $\lambda$, then it contains three elements $s \lessdot t \lessdot u$
  such that either $\lambda(s,t) > \lambda(t,u)$, or $\lambda(s,t) =
  \lambda(t,u)$.  In both cases, by construction, we have
  $\lambda'(s,t) > \lambda'(t,u)$, so $C$ is not rising under
  $\lambda'$.

  Conversely, if $C$ is rising under $\lambda$, then with any three
  consecutive elements $s \lessdot t \lessdot u$ in $C$, we have
  $\lambda(s,t) < \lambda(t,u)$.  Then by construction $\lambda'(s,t)
  < \lambda'(t,u)$.  Hence $C$ is rising under $\lambda'$.

  Since $\lambda$ and $\lambda'$ have the same rising chains,
  $\lambda'$ is also an ER-labeling.
\end{proof}

By combining Propositions~\ref{prop:erzeta} and~\ref{prop:injective} we
obtain our main result for ER-labelable posets.

\begin{theorem}
  In an ER-labelable poset that has $e$~edges, the zeta transform can be
  computed in $e$~additions, and the M\"obius transform in
  $e$~subtractions.
  \label{thm:erzeta}
\end{theorem}

ER-labelable posets are a generalization of \emph{R-labelable} posets:
an R-labelable poset is a graded ER-labelable poset.  Thus
Theorem~\ref{thm:erzeta} provides fast zeta and M\"obius transforms
for all R-labelable posets, which include supersolvable lattices and
semimodular lattices (see Stanley~\cite[\S 3.14]{stanley2011}).  For a
semimodular lattice an ER-labeling is obtained by naming the
join-irreducible elements as $1,2,\ldots,n$ in an order compatible
with the lattice (for example, ordering by rank), and defining
\[
\lambda(s,t) = \min \{i : s \vee i = t\}.
\]

Lower semimodular lattices are ER-labelable as well.  More generally,
duality preserves ER-labelability: if $\lambda$ is an ER-labeling for
poset~$P$, then $\lambda^*(s,t) = -\lambda(t,s)$ is an ER-labeling
for~$P^*$.  This is illustrated in Figure~\ref{fig:dual}.  If we take
this induced ER-labeling, convert it to an injective one, and run
Algorithm~\ref{alg:addalong}, we obtain the zeta transform for the
lower semimodular lattice shown on the right in $9$ additions.  In
comparison, Algorithm~\ref{alg:fastzeta} can use up to $11$ additions
(depending on how $I$ is ordered).

\begin{figure}[H]
  \begin{minipage}{0.49\textwidth}
    \centering
    \begin{tikzpicture}
      \matrix(a)[matrix of math nodes, column sep=0.35cm, row sep=0.8cm]{
        && \node[ele](6){}; \\
        \node[ele](3){}; && \node[ele](5){}; && \node[ele](4){}; \\
        & \node[ele](1){}; && \node[ele](2){}; \\
        && \node[ele](0){}; \\};
      \draw[edgeb] (0)--(1) node[midway,left] {1};
      \draw[edgeb] (2)--(5) node[midway,left] {1};
      \draw[edgeb] (4)--(6) node[midway,left=1mm] {1};
      \draw[edgeb] (0)--(2) node[midway,left] {2};
      \draw[edgeb] (1)--(5) node[midway,left] {2};
      \draw[edgeb] (3)--(6) node[midway,left=1mm] {2};
      \draw[edgeb] (1)--(3) node[midway,left] {3};
      \draw[edgeb] (5)--(6) node[midway,left] {3};
      \draw[edgeb] (2)--(4) node[midway,left] {4};
    \end{tikzpicture}
  \end{minipage}
  \hfill
  \begin{minipage}{0.49\textwidth}
    \centering
    \begin{tikzpicture}
      \matrix(a)[matrix of math nodes, column sep=0.35cm, row sep=0.8cm]{
        && \node[ele](0){}; \\
        & \node[ele](1){}; && \node[ele](2){}; \\
        \node[ele](3){}; && \node[ele](5){}; && \node[ele](4){}; \\
        && \node[ele](6){}; \\};
      \draw[edger] (0)--(1) node[midway,left] {$-1$};
      \draw[edger] (2)--(5) node[midway,left] {$-1$};
      \draw[edger] (4)--(6) node[midway,left=0.5mm] {$-1$};
      \draw[edger] (0)--(2) node[midway,left] {$-2$};
      \draw[edger] (1)--(5) node[midway,left] {$-2$};
      \draw[edger] (3)--(6) node[midway,left=1mm] {$-2$};
      \draw[edger] (1)--(3) node[midway,left] {$-3$};
      \draw[edger] (5)--(6) node[midway,left] {$-3$};
      \draw[edger] (2)--(4) node[midway,left] {$-4$};
    \end{tikzpicture}
  \end{minipage}
  \caption{An upper semimodular lattice with an ER-labeling (left), and
    its dual with the induced ER-labeling (right).}
  \label{fig:dual}    
\end{figure}

An ER-labelable poset need not be graded.  As an example, the pentagon
lattice (Figure~\ref{fig:pentahexa}, left) is not graded but has an
ER-labeling, facilitating both transforms in $5$~operations.  The
hexagon lattice (Figure~\ref{fig:pentahexa}, right) cannot be
ER-labeled.  This would require rising chains from $p$ to~$r$ and from
$q$ to~$s$, implying that the chain $p \lessdot q \lessdot r \lessdot
s$ is rising; but similarly $p \lessdot t \lessdot u \lessdot s$ would
be rising, so there would be two rising chains from $p$ to~$s$.

\begin{figure}[H]
  \begin{minipage}{0.49\textwidth}
    \centering
    \begin{tikzpicture}[baseline=(current bounding box.center)]
      \matrix[matrix of nodes, column sep=0.5cm, row sep=0.6cm]{
        & \node[ell](1){$s$}; \\
        \node[ell](b){$r$}; \\
        \node[ell](a){$q$}; && \node[ell](c){$t$}; \\
        & \node[ell](0){$p$}; \\};
      \draw[edgeb] (b)--(1) node[midway,above left] {3};
      \draw[edgeb] (a)--(b) node[midway,left] {2};
      \draw[edgeb] (0)--(a) node[midway,below left] {1};
      \draw[edgeb] (c)--(1) node[midway,above right] {4};
      \draw[edgeb] (0)--(c) node[midway,below right] {5};
    \end{tikzpicture}
  \end{minipage}
  \hfill
  \begin{minipage}{0.49\textwidth}
    \centering
    \begin{tikzpicture}[baseline=(current bounding box.center)]
      \matrix(a)[matrix of nodes, column sep=0.5cm, row sep=0.6cm]{
        & \node[ell](top){$s$}; \\
        \node[ell](4){$r$}; && \node[ell](5){$u$}; \\
        \node[ell](1){$q$}; && \node[ell](2){$t$}; \\
        & \node[ell](bottom){$p$}; \\};
      \draw[edgeb] (bottom)--(1);
      \draw[edgeb] (1)--(4);
      \draw[edgeb] (4)--(top);
      \draw[edgeb] (bottom)--(2);
      \draw[edgeb] (2)--(5);
      \draw[edgeb] (5)--(top);
    \end{tikzpicture}
  \end{minipage}
  \caption{The pentagon is ER-labelable (left), but the hexagon is not
    (right).}
  \label{fig:pentahexa}
\end{figure}

In the hexagon it is also impossible to compute the zeta transform in
$e$ pairwise operations (additions or subtractions); at the minimum,
$7 = e+1$ operations are required.  This can be seen by observing that
at least four operations are required to compute the four outputs at
$q, r, t,$ and $u$, and then enumerating the possibilities of
computing the remaining output $g(s)$.

Proposition~\ref{prop:erzeta} can in fact be reversed, giving a method
of recognizing whether a given edge labeling is an ER-labeling.  If an
edge labeling is not injective, it can first be converted into an
injective one by Proposition~\ref{prop:injective}.  Care must be taken
to specify how the additions are performed.  Consider, for example,
addition in a Boolean algebra: there might well be two or more rising
chains from $x$ to $y$, but since $f(x)+f(x)=f(x)$, the result might
still be the zeta transform of the input.  A simple solution is to
perform the additions in a free abelian group with all input values
distinct.

\begin{proposition}
  Let $\lambda$ be an injective edge labeling in poset $P$, and let
  $f(x)=x$ in the free abelian group whose basis is $P$.  If
  Algorithm~\ref{alg:addalong} computes the zeta transform, then
  $\lambda$ is an ER-labeling.
\end{proposition}
\begin{proof}
  Let $g$ be the result from running Algorithm~\ref{alg:addalong}.
  Consider any two comparable elements $a \le b$ in $P$.  Since $g$ is
  the zeta transform of $f$, in particular $g(b)$ contains the term
  $f(a)=a$ exactly once.  This implies that there is exactly one
  rising chain from $a$ to~$b$, otherwise $g(b)$ would contain $a$
  either zero times or more than once.
\end{proof}

The converse of Theorem~\ref{thm:erzeta} does not hold for posets in
general.  There are posets that are not ER-labelable, but admit the
zeta transform in $e$ operations or less (for example the bipartite
poset mentioned in the introduction, augmented with a hexagon on top).
However, for lattices this seems to be an open question: if a lattice
admits the zeta transform in $e$ operations, is it necessarily
ER-labelable?

Another open question concerns whether there are any posets where the
zeta transform requires more than $2e$ operations.  The hardest known
instance, in terms of~$e$, seems to be a lattice constructed from
$k$~parallel chains of $k$~elements, adjoined with a common bottom and
a common top, with a total of $e=k(k+1)$ edges.  If only addition is
available, then Theorem~1 of J\"arvisalo \etal~\cite{jarvisalo2012}
implies that computing the zeta transform for this lattice requires
$2e-O(\sqrt{e})$ additions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
The research that led to these results has received funding from the
European Research Council under the European Union's Seventh Framework
Programme (FP/2007-2013) / ERC Grant Agreement 338077 ``Theory and
Practice of Advanced Search and Enumeration.''

We thank Marcus Greferath for the conjecture that became
Theorem~\ref{thm:geom}, and Matti Karppa and the anonymous referee for
invaluable comments.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bibliographystyle{plain}
%\bibliography{refs}
\begin{thebibliography}{10}

\bibitem{bjorklund2007}
Andreas Bj\"{o}rklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto.
\newblock Fourier meets {M\"o}bius: Fast subset convolution.
\newblock In {\em Proc. 39th Annual ACM Symposium on Theory of Computing},
  STOC'07, pages 67--74, 2007.

\bibitem{bjorklund2015}
Andreas Bj\"orklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper
  Nederlof, and Pekka Parviainen.
\newblock Fast zeta transforms for lattices with few irreducibles.
\newblock {\em ACM Transactions on Algorithms}, 12:4:1--19, 2015.

\bibitem{bjorner1996}
Anders Bj\"orner and Michelle~L. Wachs.
\newblock Shellable nonpure complexes and posets. {I}.
\newblock {\em Transactions of the American Mathematical Society},
  348:1299--1327, 1996.

\bibitem{burgisser1997}
Peter B{\"u}rgisser, Michael Clausen, and M.~Amin Shokrollahi.
\newblock {\em Algebraic Complexity Theory}.
\newblock Springer, 1997.

\bibitem{garey1979}
Michael~R. Garey and David~S. Johnson.
\newblock {\em Computers and Intractability: A Guide to the Theory of
  NP-completeness}.
\newblock W. H. Freeman, 1979.

\bibitem{gratzer2011}
George Gr{\"a}tzer.
\newblock {\em Lattice Theory: Foundation}.
\newblock Birkh{\"a}user, 2011.

\bibitem{jarvisalo2012}
Matti J\"{a}rvisalo, Petteri Kaski, Mikko Koivisto, and Janne~H. Korhonen.
\newblock Finding efficient circuits for ensemble computation.
\newblock In {\em Proc. 15th International Conference on Theory and
  Applications of Satisfiability Testing}, SAT'12, pages 369--382, 2012.

\bibitem{kennes1992}
Robert Kennes.
\newblock Computational aspects of the {M}{\"o}bius transformation of graphs.
\newblock {\em {IEEE} Transactions on Systems, Man, and Cybernetics},
  22:201--223, 1992.

\bibitem{malandro2010}
Martin~E. Malandro.
\newblock Fast {F}ourier transforms for finite inverse semigroups.
\newblock {\em Journal of Algebra}, 324:282--312, 2010.

\bibitem{parviainen2010}
Pekka Parviainen and Mikko Koivisto.
\newblock Bayesian structure discovery in {B}ayesian networks with less space.
\newblock In {\em Proc. 13th International Conference on Artificial
  Intelligence and Statistics}, AISTATS'10, pages 589--596, 2010.

\bibitem{stanley1972}
Richard~P. Stanley.
\newblock Supersolvable lattices.
\newblock {\em Algebra Universalis}, 2:197--217, 1972.

\bibitem{stanley2011}
Richard~P. Stanley.
\newblock {\em Enumerative Combinatorics: Volume 1}.
\newblock Cambridge University Press, second edition, 2011.

\bibitem{valiant1986}
Leslie~G. Valiant.
\newblock Negation is powerless for {B}oolean slice functions.
\newblock {\em {SIAM} Journal on Computing}, 15:531--535, 1986.

\bibitem{yates1937}
Frank Yates.
\newblock {\em The Design and Analysis of Factorial Experiments}.
\newblock Imperial Bureau of Soil Science, 1937.

\end{thebibliography}

\end{document}