RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2019 Number 45, Pages 13–25 (Mi pdm667)

This article is cited in 5 papers

Theoretical Backgrounds of Applied Discrete Mathematics

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

V. G. Ryabov

NP “GST”, Moscow, Russia

Abstract: 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]$.

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

UDC: 519.1,519.7

DOI: 10.17223/20710410/45/2



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025