Upper bound for the length of functions over a finite field in the class of pseudopolynomials

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 f over this field in the class of ESPPs is the minimum length o...

Full description

Saved in:
Bibliographic Details
Published in:Computational mathematics and mathematical physics 2017-05, Vol.57 (5), p.898-903
Main Author: Selezneva, S. N.
Format: Article
Language:English
Subjects:
Computational Mathematics and Numerical Analysis
Mathematical analysis
Mathematics
Mathematics and Statistics
Polynomials
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 f 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 2 ).
ISSN:0965-5425
1555-6662
DOI:10.1134/S0965542517050116