Fast zeta transforms for lattices with few irreducibles

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, Pekka Parviainen

Research output: Contribution to journalArticleAcademicpeer-review

15 Citations (Scopus)


We investigate fast algorithms for changing between the standard basis and an orthogonal basis of idempotents for Möbius algebras of finite lattices. We show that every lattice with v elements, n of which are nonzero and join-irreducible (or, by a dual result, nonzero and meet-irreducible), has arithmetic circuits of size O(vn) for computing the zeta transform and its inverse, thus enabling fast multiplication in the Möbius algebra. Furthermore, the circuit construction in fact gives optimal (up to constants) monotone circuits for several lattices of combinatorial and algebraic relevance, such as the lattice of subsets of a finite set, the lattice of set partitions of a finite set, the lattice of vector subspaces of a finite vector space, and the lattice of positive divisors of a positive integer.

Original languageEnglish
Article number4
Number of pages19
JournalACM Transactions on Algorithms
Issue number1
Publication statusPublished - 1 Dec 2015


  • Arithmetic circuit
  • Fast multiplication
  • Lattice
  • Möbius inversion
  • Möbius transform
  • Semigroup algebra
  • Zeta transform


Dive into the research topics of 'Fast zeta transforms for lattices with few irreducibles'. Together they form a unique fingerprint.

Cite this