A q-Analog of Approximate Inclusion-Exclusion

Abstract

We consider the lattice of subspaces of ann-dimensional vector spaceVnqover a finite fieldGF(q) and represent a family of such subspaces by elements of a setX. Theq-analog of the principle of inclusion-exclusion expresses the size of the union of elements ofXrepresenting subspaces ofVnqin terms of the sizes of subsets ofXwhose intersection contains a given subspace ofVnq. We study the problem of approximating the size of this union when intersection sizes are known only for some subspaces ofVnq. In particular, we consider the case where intersection sizes are given for subsets ofXwhose intersection contains a subspace ofVnqof dimension at mostk. We extend methods of Linial and Nisan (1990,Combinatorica10, No. 4, pp. 349-365), drawn from approximation theory, to show that the quality of approximation changes in a significant way around [equation]: if [equation], then any approximation may err by a factor of [equation]

while if [equation] , the size of the union may be approximated to within a multiplicative factor of [equation]. Our result, the firstq-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. © 1998 Academic Press.