Complexity of function systems over a finite field in the class of polarized polynomial forms

Abstract

The Shannon complexity of a function system over a q-element finite field which contains m functions of n variables in the class of polarized polynomial forms is exactly evaluated: L_q^PPF (n,m) = qⁿ for all n ≥ 1, m ≥ 2, and all possible odd q. It has previously been known that L₂^PPF (n,m) = 2ⁿ and L₃^PPF (n,m) = 3ⁿ for all n ≥ 1 and m ≥ 2.