On the asymptotics of the logarithm of the number of threshold functions of $K$-valued logic

A. A. Irmatov ; Ž. D. Kovijanić

Diskretnaya Matematika, Tome 10 (1998) no. 3, pp. 35-56

Résumé

For the number $P(K,n)$ of threshold $n$-ary functions of $K$-valued logic, we obtain the lower bound $$ P(K,n+1)\geq \frac{1}{2}\binom{K^{n}}{\lfloor n-4- 2n/\log_K n\rfloor} P(K,\lfloor 2n/\log_K n+4\rfloor). $$ The key argument in our investigation is the generalization of a result obtained by Odlyzko on the subspaces spanned by $p$ randomly chosen $(\pm1)$-vectors. Namely, we prove that, as $n\to\infty$, for any $$ p\leq n-(3+\log_{2Q}36)n/\log_{2Q}{n} $$ if $K=2Q$, respectively, for any $$ p\leq n-(3+\log_{2Q+1}36)n/\log_{2Q+1}{n} $$ if $K=2Q+1$, the probability that the linear span of $p$ randomly chosen vectors $$ v_{1},v_{2},\ldots,v_{p}\in (E_K')^n=\{\pm 1, \pm 3,\ldots ,\pm(2Q-1)\}^n, $$ respectively, from $E_K^n=\{0,\pm 1,\ldots,\pm Q\}^n$, contains at least one vector from $$ (E_K')^n \setminus \bigcup_{i=1}^p \langle v_i\rangle, $$ respectively, from $$ E_K^n \setminus \bigcup_{i=1}^p \langle v_i\rangle, $$ equals, for even $K=2Q$, $Q\ne 1$, $$ 4\binom p3\biggl(\frac{2}{3}+ \frac{1}{12Q^2}\biggr)^n + O\biggl(p^{3}\biggl(\frac{2}{3}+\frac{Q-3}{12Q^3}\biggr)^{n}\biggr), $$ and for $Q=1$, $$ 4\binom p3\biggl(\frac{3}{4}\biggr)^n+ O\biggl(p^4 \biggl(\frac{5}{8}\biggr)^n\biggr), $$ and, respectively, for odd $K=2Q+1$, $Q\ne 1$, $$ 2\binom p2\biggl(\frac{3}{4}+\frac{1}{4(2Q+1)^2}\biggr)^n+ O\biggl(p^2 \biggl(\frac{3}{4}-\frac{7}{4(2Q+1)^2}\biggr)^n\biggr), $$ and for $Q=1$, $$ 2\binom p2\biggl(\frac{7}{9}\biggr)^n+ O\biggl(p^3 \biggl(\frac{17}{27}\biggr)^n\biggr). $$ The research of the first author was supported by the Ministry of Science of the Russian Federation, project ‘Prospective Information Technologies’ No0201{.}05{.}028.