On the degree of restrictions of q-valued logic functions to linear manifolds | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 45. DOI: 10.17223/20710410/45/2

In case of a finite field Fq, the degree of restricting a q-valued logic function in n variables to a r-dimensional linear manifold of the vector space F_qⁿ 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 → ∞, 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 [ Llog_q n + + log_q log_q nJ, Llog_q n + log_q log_q nJ ], while the analogous parameter for the case of fixing variables is in the range [Llog_qnJ, Llog_qnJ].