ABSTRACT
Given a list of n real numbers, one wants to decide whether every number in the list occurs at least k times. It will be shown that \Omega(n log n) is a sharp lower bound for the depth of an algebraic decision or computation tree solving this problem for a fixed k. For linear decision trees the coefficient can be taken to be arbitrarily close to 1 (using ternary logarithm). This is done by using the Björner-Lovász-Yao method, which turns the problem into one of estimating the Möbius function for a certain partition lattice. The method will work also for the more general T-multiplicity problem when T is additive and cofinite. A formula for the exponential generating function for the Möbius function of a partition poset with restricted block sizes in general will also be given.