Partitions and Compositions over Finite Fields

Amela Muratovic-Ribic, Qiang Wang

Abstract


In this paper we  find an exact formula for the number of partitions of an element  $z$ into $m$ parts over a finite field,  i.e. we find the number of nonzero solutions of the equation $x_1+x_2+\cdots +x_m=z$ over a finite field when the order of terms does not matter. This is equivalent to counting the number of $m$-multi-subsets whose sum is $z$.  When the order of the terms in a solution does matter, such a solution is called a composition of $z$. The number of compositions is useful in the study of zeta functions of toric hypersurfaces over finite fields.  We also give an application in the study of polynomials of prescribed ranges over finite fields.

Keywords


sumset; polynomials; finite fields; partitions; compositions

Full Text: PDF