We consider the lattice of subspaces of an n-dimensional vector space Vnq over a finite field GF(q) and represent a family of such subspaces by elements of a set X. The q-analog of the principle of inclusion-exclusion expresses the size of the union of elements of X representing subspaces of Vnq in terms of the sizes of subsets of X whose intersection contains a given subspace of Vnq . We study the problem of approximating the size of this union when intersection sizes are known only for some subspaces of Vnq . In particular, we consider the case where intersection sizes are given for subsets of X whose intersection contains a subspace of Vnq of dimension at most k. We extend methods of Linial and Nisan (1990, Combinatorica 10, No. 4, pp. 349-365), drawn from approximation theory, to show that the quality of approximation changes in a significant way around : if , then any approximation may err by a factor of ; while if , the size of the union may be approximated to within a multiplicative factor of . Our result, the first q-analog of a computational property of the lattice of subsets of a finite set, answers in the affirmative a question posed by Linial and Nisan. Copyright 1998 Academic Press.
Document Type: Research Article
Department of Computer Science, University of Cyprus, Nicosia, CY-1678, Cyprus