Lower Bound of the Complexity of Functions over Finite Field of Order 4 in the Class of Polarized Polynomials
The representations, including polynomial, of functions over final fields have been actively investigated. The complexity of such representations is the main stream of research. Polynomial representations of Boolean functions have been studied well enough. The exact values of the complexity have bee...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Irkutsk State University
2016-06-01
|
| Series: | Известия Иркутского государственного университета: Серия "Математика" |
| Subjects: | |
| Online Access: | http://isu.ru/journal/downloadArticle?article=_81ead9fa86c04dc7aac69969376f9766&lang=rus |
| _version_ | 1819085449223733248 |
|---|---|
| author | A. Baliuk A.S. Zinchenko |
| author_facet | A. Baliuk A.S. Zinchenko |
| author_sort | A. Baliuk |
| collection | DOAJ |
| description | The representations, including polynomial, of functions over final fields have been actively investigated. The complexity of such representations is the main stream of research. Polynomial representations of Boolean functions have been studied well enough. The exact values of the complexity have been found for a lot of polynomial classes.
Recently, the interest to polynomial representations of functions over finite fields and over finite rings is being increased. There are a lot of difficulties in studying of the complexity of these representations. Only not equal upper and lower bounds has been obtained, even for sagnificantly simple classes of polynomials.
This paper is about polarized polynomials over finite field of order 4. Such a polynomial is a finite sum of products. Every polynomial represents an n-variable function over finite field. A complexity of a polynomial is a number of nonzero summands in it. Every function can be represented by several polynomials, which are belongs to the same class. A complexity of a function in a class of polynomials is the minimal complexity of polynomials in the class, which represent this function.
Previously, the constructive lower bounds in the class of polarized polynomials have been known only for the case of Boolean and three-valued functions. Also, the weaker, non-constructive lower bound has been known for the case of functions over arbitrary prime finite field.
In this paper the constructive lower bound has been obtained for functions over finite field of order 4 in the class of polarized polynomials. The lower bound is equivalent to previously known lower bound for Boolean and three-valued functions. |
| first_indexed | 2024-12-21T21:04:32Z |
| format | Article |
| id | doaj.art-daa1730a3fc34d5aa2f6ff597b97d915 |
| institution | Directory Open Access Journal |
| issn | 1997-7670 2541-8785 |
| language | English |
| last_indexed | 2024-12-21T21:04:32Z |
| publishDate | 2016-06-01 |
| publisher | Irkutsk State University |
| record_format | Article |
| series | Известия Иркутского государственного университета: Серия "Математика" |
| spelling | doaj.art-daa1730a3fc34d5aa2f6ff597b97d9152022-12-21T18:50:19ZengIrkutsk State UniversityИзвестия Иркутского государственного университета: Серия "Математика"1997-76702541-87852016-06-011611929Lower Bound of the Complexity of Functions over Finite Field of Order 4 in the Class of Polarized PolynomialsA. BaliukA.S. ZinchenkoThe representations, including polynomial, of functions over final fields have been actively investigated. The complexity of such representations is the main stream of research. Polynomial representations of Boolean functions have been studied well enough. The exact values of the complexity have been found for a lot of polynomial classes. Recently, the interest to polynomial representations of functions over finite fields and over finite rings is being increased. There are a lot of difficulties in studying of the complexity of these representations. Only not equal upper and lower bounds has been obtained, even for sagnificantly simple classes of polynomials. This paper is about polarized polynomials over finite field of order 4. Such a polynomial is a finite sum of products. Every polynomial represents an n-variable function over finite field. A complexity of a polynomial is a number of nonzero summands in it. Every function can be represented by several polynomials, which are belongs to the same class. A complexity of a function in a class of polynomials is the minimal complexity of polynomials in the class, which represent this function. Previously, the constructive lower bounds in the class of polarized polynomials have been known only for the case of Boolean and three-valued functions. Also, the weaker, non-constructive lower bound has been known for the case of functions over arbitrary prime finite field. In this paper the constructive lower bound has been obtained for functions over finite field of order 4 in the class of polarized polynomials. The lower bound is equivalent to previously known lower bound for Boolean and three-valued functions.http://isu.ru/journal/downloadArticle?article=_81ead9fa86c04dc7aac69969376f9766&lang=rusfinite fieldpolarized polynomialKroneker formcomplexitylower bounds |
| spellingShingle | A. Baliuk A.S. Zinchenko Lower Bound of the Complexity of Functions over Finite Field of Order 4 in the Class of Polarized Polynomials Известия Иркутского государственного университета: Серия "Математика" finite field polarized polynomial Kroneker form complexity lower bounds |
| title | Lower Bound of the Complexity of Functions over Finite Field of Order 4 in the Class of Polarized Polynomials |
| title_full | Lower Bound of the Complexity of Functions over Finite Field of Order 4 in the Class of Polarized Polynomials |
| title_fullStr | Lower Bound of the Complexity of Functions over Finite Field of Order 4 in the Class of Polarized Polynomials |
| title_full_unstemmed | Lower Bound of the Complexity of Functions over Finite Field of Order 4 in the Class of Polarized Polynomials |
| title_short | Lower Bound of the Complexity of Functions over Finite Field of Order 4 in the Class of Polarized Polynomials |
| title_sort | lower bound of the complexity of functions over finite field of order 4 in the class of polarized polynomials |
| topic | finite field polarized polynomial Kroneker form complexity lower bounds |
| url | http://isu.ru/journal/downloadArticle?article=_81ead9fa86c04dc7aac69969376f9766&lang=rus |
| work_keys_str_mv | AT abaliuk lowerboundofthecomplexityoffunctionsoverfinitefieldoforder4intheclassofpolarizedpolynomials AT aszinchenko lowerboundofthecomplexityoffunctionsoverfinitefieldoforder4intheclassofpolarizedpolynomials |