2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Неприводимые многочлены
Сообщение13.01.2006, 01:16 


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

 Профиль  
                  
 
 
Сообщение13.01.2006, 11:43 
Модератор
Аватара пользователя


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

Пусть 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 


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

 Профиль  
                  
 
 
Сообщение13.01.2006, 22:59 
Модератор
Аватара пользователя


11/01/06
5660
Etranger писал(а):
Правильно ли я понимаю, что выделенное слагаемое дает асимптотику по q?
А интересно, где можно найти доказательство?

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

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

 Профиль  
                  
 
 
Сообщение15.10.2008, 22:17 
Модератор
Аватара пользователя


11/01/06
5660
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 
Модератор
Аватара пользователя


11/01/06
5660
Etranger в сообщении #7083 писал(а):
А что-нибудь хорошее про производящую функцию можно сказать?

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 6 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group