|
Известия Иркутского государственного университета. Серия «Математика», 2014, том 10, страницы 3–12
(Mi iigum205)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
О верхней оценке сложности задания квазиполиномами функций над конечными полями
А. С. Балюк Иркутский государственный университет
Аннотация:
Представления функций над конечными полями, в том числе полиномиальные,
в настоящее время активно исследуются.
Одним из основных направлений этих исследований является сложность
таких представлений.
В данной работе исследуется сложность задания функций квазиполиномами
над конечными полями.
Квазиполином можно рассматривать как полином многих переменных,
в котором вхождения $x_i^0, \dots, x_i^{k-1}$ одной из переменных
заменены на функции из некоторого
множества $\{g_0(x_i), \dots, g_{k-1}(x_i)\}$ линейно независимых
одноместных функций.
Под сложностью полинома над конечным полем обычно понимают количество
слагаемых в нем, число вхождений переменных или степень.
В случае квазиполиномов напрямую можно оценивать количество слагаемых,
число вхождений переменных и степень требуют обобщения.
В статье в качестве сложности квазиполинома исследуется количество
слагаемых в нем.
Для случая квазиполиномов по модулю простого $k$ ранее была известна верхняя
оценка такой сложности, а именно, сложность задания квазиполиномами
$n$-местной функции над конечным полем простого порядка $k$ не превосходит
величины $\frac{k}{k+1}k^n$.
В работе получена верхняя оценка сложности представления квазиполиномами
функций над произвольным конечным полем порядка $q$,
которая при $q \geqslant 3$ усиливает ранее известную верхнюю оценку,
полученную для случая квазиполиномов по модулю простого числа.
А именно, если $q = k^n$, где $k$ — простое, а $n \geqslant 1$,
для любой $n$-местной функции над конечным полем порядка $q$
сложность её задания квазиполиномами ограничена
сверху величиной $ \frac{q-1}{q-q^{1-q}}q^n$.
Ключевые слова:
конечное поле, полином, квазиполином, сложность.
Образец цитирования:
А. С. Балюк, “О верхней оценке сложности задания квазиполиномами функций над конечными полями”, Известия Иркутского государственного университета. Серия Математика, 10 (2014), 3–12
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/iigum205 https://www.mathnet.ru/rus/iigum/v10/p3
|
Статистика просмотров: |
Страница аннотации: | 135 | PDF полного текста: | 37 | Список литературы: | 22 |
|