On the degree of restrictions of $q$-valued logic functions to linear manifolds

V. G. Ryabov

Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 13-25

Résumé

In case of a finite field $\mathbb{F}_q$, the degree of restricting a $q$-valued logic function in $n$ variables to a $r$-dimensional linear manifold of the vector space $\mathbb{F}_q^n$ is defined as the degree of a polynomial in $r$ variables that represents this restriction. For manifolds of a fixed dimension, the probability of occurrence of restrictions with a degree not higher than the given one is estimated, and the asymptotics of the number of manifolds on which the restrictions are affine is obtained. It is shown that if $n \to \infty$, for almost all $q$-valued logic functions in $n$ variables, the value of the maximum dimension of a linear manifold on which the restriction is affine belongs to the segment $[\lfloor \log_q n+\log_q \log_q n \rfloor, \lceil \log_q n+\log_q \log_q n \rceil]$, while the analogous parameter for the case of fixing variables is in the range $[\lfloor \log_q n \rfloor, \lceil \log_q n \rceil]$.

Détail

Keywords: many-valued logic, Boolean function, restriction, linear manifold, degree.