Geodesic
On the degree of restrictions of $q$-valued logic functions to linear manifolds
Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 13-25
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{PDM_2019_3_a2,
     author = {V. G. Ryabov},
     title = {On the degree of restrictions of $q$-valued logic functions to linear manifolds},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {13--25},
     year = {2019},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2019_3_a2/}
}
TY  - JOUR
AU  - V. G. Ryabov
TI  - On the degree of restrictions of $q$-valued logic functions to linear manifolds
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2019
SP  - 13
EP  - 25
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/PDM_2019_3_a2/
LA  - ru
ID  - PDM_2019_3_a2
ER  - 
%0 Journal Article
%A V. G. Ryabov
%T On the degree of restrictions of $q$-valued logic functions to linear manifolds
%J Prikladnaâ diskretnaâ matematika
%D 2019
%P 13-25
%N 3
%U http://geodesic.mathdoc.fr/item/PDM_2019_3_a2/
%G ru
%F PDM_2019_3_a2
V. G. Ryabov. On the degree of restrictions of $q$-valued logic functions to linear manifolds. Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 13-25. http://geodesic.mathdoc.fr/item/PDM_2019_3_a2/

[1] D'edonne Zh., Linear Algebra and Elementary Geometry, Nauka, M., 1972, 336 pp. (in Russian)

[2] Glukhov M. M., Shishkov A. B., Mathematical Logic. Discrete Functions. Theory of Algorithms, Lan Publ., St. Petersburg, 2012, 416 pp. (in Russian)

[3] Glukhov M. M., Elizarov V. P., Nechaev A. A., Algebra, v. II, Gelios ARV Publ., M., 2003, 416 pp. (in Russian)

[4] Feller V., An Introduction to Probability Theory and its Applications, v. 1, Mir Publ., M., 1984, 528 pp. (in Russian) | MR

[5] Sachkov V. N., Combinatorial Methods in Discrete Mathematics, Nauka, M., 1977, 320 pp. (in Russian)

[6] Zhuravlev Yu. I., “Set-theoretical methods in the algebra of logic”, Problemy Kibernetiki, 8, 1962, 5–44 (in Russian)

[7] Logachev O. A., “On values of affinity level for almost all Boolean functions”, Prikladnaya Diskretnaya Matematika, 2010, no. 3(9), 17–21 (in Russian)

[8] Buryakov M. L., “Asymptotic bounds for the affinity level for almost all Boolean functions”, Discrete Math. Appl., 20:3 (2008), 73–79 (in Russian) | DOI | MR | Zbl

[9] Cheremushkin A. V., “Estimating the level of affinity of a quadratic form”, Discrete Math. Appl., 29:1 (2017), 114–125 (in Russian) | DOI | MR | Zbl