Upper bound for the length of functions over a finite field in the class of pseudopolynomialsстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 12 июля 2017 г.
Аннотация:An exclusive-OR sum of pseudoproducts (ESPP), or a pseudopolynomial over a finite field
is a sum of products of linear functions. The length of an ESPP is defined as the number of its pairwise distinct summands. The length of a function over this field in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function L_k^{ESPP}(n) on the set of functions over a finite field of k elements in the class of ESPPs is considered; it is defined as the maximum length of a function of n variables over this field in the class of ESPPs. It is proved that L_k^{ESPP}(n) = O(k^n/n).