Geodesic
On the number of functions of $k$-valued logic which are polynomials modulo composite $k$
Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 81-91.

Voir la notice de l'article provenant de la source Math-Net.Ru

A function of $k$-valued logic is called polynomial if it may be represented by a polynomial modulo $k$. For any composite number $k$ we propose a uniquely defined canonical form of polynomials for polynomial functions of $k$-valued logic depending on an arbitrary number of variables. This canonical form is used to find, for any composite $k$, a formula for the number of $n$-place polynomial functions of $k$-valued logic. As a corollary, for any composite $k$ we find the asymptotic behaviour of the logarithm of the number of $n$-place polynomial functions of $k$-valued logic.
Keywords: function of $k$-valued logic, polynomial, polynomial function, numeric functions, asymptotic behaviour. 
@article{DM_2016_28_2_a7,
     author = {S. N. Selezneva},
     title = {On the number of functions of $k$-valued logic which are polynomials modulo composite $k$},
     journal = {Diskretnaya Matematika},
     pages = {81--91},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2016_28_2_a7/}
}
TY  - JOUR
AU  - S. N. Selezneva
TI  - On the number of functions of $k$-valued logic which are polynomials modulo composite $k$
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 81
EP  - 91
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_2_a7/
LA  - ru
ID  - DM_2016_28_2_a7
ER  - 
%0 Journal Article
%A S. N. Selezneva
%T On the number of functions of $k$-valued logic which are polynomials modulo composite $k$
%J Diskretnaya Matematika
%D 2016
%P 81-91
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2016_28_2_a7/
%G ru
%F DM_2016_28_2_a7
S. N. Selezneva. On the number of functions of $k$-valued logic which are polynomials modulo composite $k$. Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 81-91. http://geodesic.mathdoc.fr/item/DM_2016_28_2_a7/

[1] Yablonskii S. V., “Funktsionalnye postroeniya v $k$-znachnoi logike”, Trudy Matem. in-ta im. V.A. Steklova AN SSSR, 51 (1958), 5–142

[2] Meschaninov D.G., “Metod postroeniya polinomov dlya funktsii $k$-znachnoi logiki”, Diskretnaya matematika 1995, 7:3, 48–60 ; Meshchaninov D. G., “A method for constructing polynomials of $k$-valued logic functions”, Discrete Math. Appl., 5:4 (1995), 333–346 | DOI | MR | Zbl

[3] Selezneva S. N., “Bystryi algoritm postroeniya dlya $k$-znachnykh funktsii polinomov po modulyu $k$ pri sostavnykh $k$”, Diskretnaya matematika, 23:3 (2011), 3–22 | DOI | Zbl

[4] Selezneva S. N., “Constructing polynomials for functions over residue rings modulo a composite number in linear time”, Lect. Notes Comput. Sci., 7353, 2012, 303–312 | MR

[5] Selezneva S.N., “Lineinaya otsenka skhemnoi slozhnosti raspoznavaniya polinomialnosti funktsii nad koltsom vychetov po sostavnomu modulyu”, Vestn. Mosk. un-ta. Ser. 15. Vychisl. matem. i kibernetika, 2013, no. 1, 27–31 | MR

[6] Niven I., Warren L. J., “A generalization of Fermat's theorem”, Proc. Amer. Math. Soc., 8, 1957, 306–313 | MR | Zbl

[7] Keller G., Olson F.R., “Counting polynomial ($\bmod\ p^n$)”, Duke Math. J., 35:4 (1968), 835–838 | DOI | MR | Zbl

[8] Aizenberg N.N., Semion I.V., Tsitkin A.I., “Moschnost klassa funktsii $k$-znachnoi logiki ot $n$ peremennykh, predstavimykh polinomami po modulyu $k$”, V kn. Mnogoustoichivye elementy i ikh primenenie, M.: Sov. radio, 1971, 79–83

[9] Singmaster D., “On polynomial functions ($\bmod\ m$)”, J. Number Theory, 6:5 (1974), 345–352 | DOI | MR | Zbl

[10] Aizenberg N.N., Semion I.V., “Nekotorye kriterii predstavimosti funktsii $k$-znachnoi logiki polinomami po modulyu $k$”, V kn. Mnogoustoichivye elementy i ikh primenenie, Sov. radio, M., 1971, 84–88 | MR