Неприводимые многочлены

[Etranger]

Не знает ли кто-нибудь, как можно посчитать число многочленов степени n от k
переменных над конечным полем из q элементов?
Хотя бы при числе переменных k = 2 или 3 (для k=1 ответ довольно простой)

[maxal]

Простых формул нет, но посчитать тем не менее можно.

Пусть q и k фиксированы. Зафиксируем также deglex порядок на мономах.
Положим f(n) равным числу неприводимых многочленов степени n со старшим коэффициентом 1.
Предположим, что у нас уже вычислены f(1),...,f(n), тогда для f(n+1) справедлива формула

$$f(n+1)=q^{C(n,k+1)}\frac{q^{C(n+1,k)}-1}{q-1} - \sum_{i_1+2i_2+\dots+n i_n=n+1} C(i_1,f(1)) C(i_2,f(2))\dots C(i_n,f(n)),$$

где $C(s,t)$ - число композиций s в сумму t неотрицательных слагаемых (оно же число сочетаний с повторениями из t по s), его можно выразить через биномиальный коэффициент: $C(s,t)={s+t-1\choose t-1}$.

[Etranger]

Правильно ли я понимаю, что выделенное слагаемое дает асимптотику по q?
А интересно, где можно найти доказательство?
И существует ли нерекуррентная формула? А что-нибудь хорошее про производящую функцию можно сказать?

[maxal]

Etranger писал(а):

Правильно ли я понимаю, что выделенное слагаемое дает асимптотику по q?
А интересно, где можно найти доказательство?

Первое слагаемое - это число всех нормированных многочленов степени n+1. Вычитаемая сумма - это число нормированных приводимых многочленов степени n+1. Их разность дает число неприводимых нормированных многочленов.

Цитата:

И существует ли нерекуррентная формула? А что-нибудь хорошее про производящую функцию можно сказать?

Мне сие неизвестно.

[maxal]

maxal в сообщении #7034 писал(а):

Пусть q и k фиксированы. Зафиксируем также deglex порядок на мономах.
Положим f(n) равным числу неприводимых многочленов степени n со старшим коэффициентом 1.
Предположим, что у нас уже вычислены f(1),...,f(n), тогда для f(n+1) справедлива формула

$$f(n+1)=q^{C(n,k+1)}\frac{q^{C(n+1,k)}-1}{q-1} - \sum_{i_1+2i_2+\dots+n i_n=n+1} C(i_1,f(1)) C(i_2,f(2))\dots C(i_n,f(n)),$$

где $C(s,t)$ - число композиций s в сумму t неотрицательных слагаемых (оно же число сочетаний с повторениями из t по s), его можно выразить через биномиальный коэффициент: $C(s,t)={s+t-1\choose t-1}$.

Хехе. Эта формула недавно составила фактически всю содержательную часть статьи:

Arnaud Bodin, Number of irreducible polynomials in several variables over finite fields, Amer. Math. Monthly, 115 (2008), 653-660.

Публикацию, можно сказать, из-под носа увели
Ну да ладно, я бы все равно такую тривиальщину публиковать не стал.

[maxal]

Etranger в сообщении #7083 писал(а):

А что-нибудь хорошее про производящую функцию можно сказать?

Вот статья на эту тему от того же автора:
Arnaud Bodin, Generating series for irreducible polynomials over finite fields