2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 
Сообщение13.01.2006, 11:43 
Аватара пользователя
Простых формул нет, но посчитать тем не менее можно.

Пусть 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 s}$.

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

 
 
 
 
Сообщение13.01.2006, 22:59 
Аватара пользователя
Etranger писал(а):
Правильно ли я понимаю, что выделенное слагаемое дает асимптотику по q?
А интересно, где можно найти доказательство?

Первое слагаемое - это число всех нормированных многочленов степени n+1. Вычитаемая сумма - это число нормированных приводимых многочленов степени n+1. Их разность дает число неприводимых нормированных многочленов.
Цитата:
И существует ли нерекуррентная формула? А что-нибудь хорошее про производящую функцию можно сказать?

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

 
 
 
 
Сообщение15.10.2008, 22:17 
Аватара пользователя
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.

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

 
 
 
 Re: Неприводимые многочлены
Сообщение13.10.2010, 22:09 
Аватара пользователя
Etranger в сообщении #7083 писал(а):
А что-нибудь хорошее про производящую функцию можно сказать?

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

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group