Вот именно : формула для числа корней в общем виде совсем не очевидна , по крайней мере для меня . Любопытно было бы увидеть подробное доказательство .
Я думаю проще попытаться найти контрпример , посчитав число корней x^2=e для групп вида S(p^n) , где р - простое . И сравнить результат .
Я конечно не претендую на истину в последней инстанции , но мне кажется что ваше изложение данной темы несколько громоздко и потому непонятно для тех , кто не в теме .
Я думаю , что писать перестановки надо в виде произведения циклов : так нагляднее и на мой взгляд – понятнее , ( рядом пишу вашу запись ) . Итак :
1 ) s = ( 1 , 2, 3, 4 , 5 ) (6) = { 2,3,4,5,1,6 }
Так как для любой вообще перестановки p всегда существует натуральное число m , такое что : p^m=e ( или p^(m+1)=p ) , где e – тождественная перестановка ( это очевидно , так как степени конкретно взятой перестановки образуют подгруппу конечной группы – группы всех перестановок данного множества ) . В частности для цикла длинной m это и есть минимальная степень ( тоже очевидно ) . Итак – в нашем случае m=5 . Поэтому s^((m+1)/2) = s^3– корень данной перестановки и он единственный . То есть сразу и без вычисления , смотря на сам цикл , пишем ответ :
Видим два четных цикла длины два и значит будем иметь два варианта цикла длины четыре ( поменяв их местами ) , один вариант цикла длины два ( объединив единичные ) и оставляя единичные циклы неизменными . Всего четыре варианта . И тоже , можем сразу и без вычислений , лишь глядя на исходное представление перестановки , писать ответы :
Видим один цикл длины три и три цикла единичной длины . У нас всего три варианта объединить единичные циклы в цикл длиной два и один вариант – оставить единичные циклы . Всего четыре корня :
Видим один цикл длины 5 и два единичных цикла . А значит всего два корня – оставляем единичные циклы без изменений и объединяем их . Так как ( 5+1)/2 = 3 , то s^3 – корень квадратный . Итак :
Да , вы правы – формула верна . Я всегда был уверен , что она верна для простых полей . Сейчас освежил память , так как все это было очень-очень давно . И действительно – даже если в поле имеются не примитивные подполя , формула верна . Так что извиняюсь .
Только мне не понятно , зачем искать примитивные многочлены простым перебором . Можно сократить сильно поиски , используя например ( не залезая уж совсем в дебри алгебры ) круговые многочлены :
Пусть имеется поле GF(p^n) . Как известно , его мультипликативная группа состоит из q=p^n-1 элементов . Есть такая теорема : Произведение всех неприводимых многочленов степени m ( обозначается I(q,m,x) ) равно произведению круговых многочленов Qk(x) , где произведение берется по таким k- делителям числа q , для которых m – минимальная степень p , такая что : p^m=1(mod(k)) . Очевидно , что в этом произведении присутствует круговой многочлен Qq(x) и там , и только там присутствуют все примитивные элементы степени fi (q) , которых fi (q)/n . Пример :
Пример GF(2^5) x^31= Q1(x)* Q31(x) Q1(x)=x-1 Q31(x)=(x^31-1)/(x-1) I(2,5,x)= Q31(x) . То есть все неприводимые многочлены – примитивны . Так как многочлены 2 и 3 степени неприводимы над полем тогда и только тогда , когда у них нет корней в этом поле , то не трудно видеть , что такими многочленами являются x^2+x+1 , x^3+x+1 и x^3+x^2+1 . Исключая из произвольного многочлена 5 степени такие z : z^2=z+1 и z^3= z+1 и z^3=z^2+1 простым перебором , даже в ручную довольно быстро получаем все примитивные многочлены : 1+x^2+x^5 1+x+x^2+x^3+x^5 1+x^3+x^5 1+x+x^3+x^4+x^5 1+x^2+x^3+x^4+x^5 1+x+x^2+x^5+x^4
Пример GF(2^6) x^63-1= Q1(x)* Q3(x)* Q7(x)* Q9(x)* Q21(x)* Q63(x)
Q1(x)=x-1 Q3(x)=x^2+x+1 Q7(x)=x^6+x^5+x^4+x^3+x^2+x+1 Q9(x)=x^6+x^3+1 Q21(x)=x^12+x^11+x^9+x^8+x^6+x^4+x^3+x+1=( x^6+x^4+x^2+x+1)*(x^6+x^5+x^4+x^2+1) =P1(x)*P2(x) Q63(x)…. I(2,6,x)=Q9(x)Q21(x)Q63(x) . Как видим -Q7(x) не входит в это произведение ,а значит он разлагается . И действительно : Q7(x+1) = x^6+x^5+x^4+x^3+x^2=x^2(x^4+x^3+x^2+1) . То есть Q7(x)=(x^2+1)(x^4+x^3+1) Так как Q9(x) ,P2(x)- неприводимыe многочлены , то не приводимые и Q9 (x+1)= x^6+x^4+x^3+x+1 P2(x+1)= x^6+x^5+x^2+x+1 Так как только x^2+x+1, x^3 +x+1 и x^3+x^2+1 неприводимые многочлены степени не выше третей , то неприводимы и x^6+x+1 (x^2+x+1)*x^4+x+1=x^6+x^5+x^4+x+1= P3(x) P3(x+1)= x^6+x^5+1 Итак : f(x) = x^6+x^4+x^3+x+1 , x^6+x^5+x^2+x+1, x^6+x+1 , x^6+x^5+x^4+x+1 , x^6+x^5+1 – примитивные многочлены над GF(2) , а значит порождающие поле GF(2^6) . C ходу не получается найти лишь последний .
Согласен, что поиск примитивных многочленов над не простым полем, то есть над полем GF(p^n) , задача “так себе” – представляет из себя чисто теоретический интерес . Но суть не в этом. У вас, во-первых, не совсем корректное определение примитивного многочлена над простым полем ( в частности ) .
Дело в том , что у вас путаница с понятием примитивный элемент и примитивный многочлен над конечным полем. Поэтому я привел не простое поле в качестве намека . Например , вы пишите : “ … примитивный элемент может не определится …” Но дело в том , мультипликативная группа ненулевых элементов конечного поля GF(q) – циклична ( здесь q – не обязательно простое число ) , а ее образующий элемент называется примитивным элементом . Их , как известно , fi (q-1 ) , где ( у меня так обозначено ) fi – функция Эйлера . Подозреваю , вы путаете фактор -кольцо кольца целых чисел по главному идеалу ( или проще – кольцо классов вычетов ) , с фактор – кольцом кольца целых чисел по главному идеалу от простого числа , которое является полем – в нем обязательно будет примитивный элемент , так как это конечное поле . В любом поле , даже если его мультипликативная группа состоит из q элементов , где q – не простое число , всегда будет примитивный элемент и не всегда один . Точнее : Мультипликативная группа ненулевых элементов конечного поля GF(q) – циклична ( здесь q – не обязательно простое число ) , а ее образующий элемент называется примитивным элементом . Их , как известно , fi (q-1 ) , где ( у меня так обозначено ) fi – функция Эйлера . Поехали далее : Есть такая теорема – если многочлен степени n - f(x) принадлежит GF(q)(x) и является неприводимым , то любой корень этого многочлена принадлежит полю GF(q^n) .Более того , его полем разложения над полем GF(q) является GF( q^m ) и поля любых двух разных неприводимых многочленов одной и той -же степени изоморфны друг другу . Другими словами : Кольцо многочленов по модулю некоторого неприводимого в поле GF(q) многочлена p(x) степени m является полем GF(q^m). Здесь везде q – не обязательно простое. Далее , вы пишите : “…порождающий полином неприводим и примитивен …” Как видно из вышеописанного – это неверно . Достаточно неприводимости . Я приводить пример не буду , вы его сами привели взяв порождающий многочлен x^2+1 для поля GF( 3^2) – очевидно , что этот многочлен не примитивен. Так вот , одно из определений : порождающий многочлен , это такой неприводимый над полем многочлен , который имеет примитивный корень в расширенном поле , точнее – все его корни будут примитивными . Теперь переходим к полю GF(p^n ) . Так как его мультипликативная группа циклична , то она состоит из всех корней многочлена x^q-1=0 , где q= p^n -1 . Например : GF(2^2) имеем : x^3-1=(x-1)(x^2+x+1 ) . Как видим – единственный примитивный многочлен это x^2+x+1 GF(2^3) имеем : x^7-1=(x-1)(x^3+ x^2 +1 )(x^3+x+1) . Как видим – два примитивных многочлена это x^3+x^2+1 и x^3+x+1 GF(3^2) имеем : x^8-1=(x^4+1)( x^2 +1 )(x-1)(x+1)=(x^2+x+2)(x^2+2x+2)(x^2+1)(x-1)(x-2) . Как видим – два примитивных многочлена это x^2+2x+2 и x^2+x+2 И вообще , есть такая теорема – если n не делится на характеристику поля GF(q) , то многочлен x^n -1 разлагается в произведение так называемых циклических многочленов Qd(x) над его простым полем , где произведение берется по всем делителям числа n . Круговой многочлен Qd(x) = П ( x^(n/d)-1) ^ mu(d) , где произведение берется по всем делителям числа d числа n ( здесь mu – функция Мебиуса . В частности : Qp(x) ( p- простое ) = 1+ x+x^2+x^3+…x^(p-1) Qp^k(x) ( p -простое ) =(x^p^k-1)/(x^p^(k-1)-1)= 1+x^p^(k-1) +x^(2p^(k-1))+ x^(3p^(k-1))+… x^((p-1)p^(k-1)) Например : Q3(x)=1+x+x^2 – сразу получаем примитивный многочлен для GF(2) Q5(x)=1+x+x^2+x^3+x^4 Q15(x)=x^8+x^7+x^5+x^4+x^3+x+1 И так как Q5(x+1)=x^4+x^3+1 ( для GF(2) ) – неприводимый многочлен в этом поле , то он делит Q15(x)= ( x^4+x^3+1)( x^4+x+1) То есть получаем для GF(2^4) два примитивных многочлена x^4+x^3+1 и x^4+x+1 над полем GF(2)
Я писал : количество примитивных многочленов в поле GF( 9 ) ...
Вопрос лишь в том , что такое примитивный многочлен степени m над полем GF( q ) , где q = p^m ( m = 1 - частный случай ) . И их количество не определяется функцией Эйлера....
" Количество примитивных полиномов определяется функцией Эйлера " ..
Утверждение ложно . Например для поля F9 имеется 16 примитивных многочленов , а по вашей формуле получается 2...
Вывести можно лишь число нормированных неприводимых многочленов степени n , где участвует функция Мебиуса от делителей числа n , помноженная на степеня n по всем делителям и все это деленное на n .
И еще вопрос : как вы умудряетесь вводить математическую символику в комментарии - я пытался тупо скопировать из Maple , c соответствующим форматированием - хрень получается . Я что- то не знаю ?
И еще : в " методе через интеграл " не обязательно вводить ( и даже знать ) числа Бернули : сумма всех кожффициентов равна единице - этого достаточно .
Просто " бонус " : можно не вычислять коэффиициент при n , а взать табличный В ( к ) - дело вкуса ( и знаний... )
Во первых : рекуррентные формулы , приводимые ранее , требуют знания , а главное - использования всех предыдущих формул для сумм . В " моем " варианте - требуется лишь знание предыдущей суммы и интергал ( приметивнее не бывает...) . Спорить , по моему , невозможно - этот вариант явно проще .
Вычисление " в лоб " через числа Бернули - как вариант , если под рукой есть соответствующая таблица ( чисел Бернули ) , либо соответствующая программа...
В любом случае - рекуррентные формулы - это однозначно , более сложный путь .
А биноминальные коэффициенты посчитать можно даже в ручную и это проще чем суммировать все предыдущие суммы и кстати , тоже с использованием биноминальных коэффициентов .
Я думаю , тут вопрос восприятия : и биноминальные коэффициенты и числа Бернули , можно посчитать самостоятельно и даже вручную , а можно просто " взять " из " таблиц " .
Мой самый первый коммертарий как раз и говорил о том , что " интегральный " способ - наиболее простой и максимально примитивный из всех возможных , для достижения цели и что числа Бернули требуют те же рекуррентные соотношения ( либо разложения в ряд образующей функции ) .
Вы спросили : есть ли " прямая " формула . Я ответил - есть ...
Предыдущая , точнее - самая первая сумма - это сумма нулевых степеней , которая , очевидно равна n . Дальше - интегралом получаем последовательно формулы для любых степеней .
Если подставить в явной форме в формулу для интеграла : Pk(n)=Sum (a(k+1-m)*n^m , 1..k+1) можно получить формулы зависимости коэффициентов следующей суммы от коэффициентов предыдущей . Эту зависимость один из комментаторов показал , но не в общем виде - видимо для наглядности . Правда написал , что коэффициент при первой степени n , надо вычислять ( сумма всех коэффициентов полинома равна 1 ) .
Кстати - этот коэффициент можно не вычислять : это всегда число Бернулли B(k) ...
Уйти от рекуррентности формально можно и написать формулу полинома для любой суммы степеней к ...но через числа Бернули ( которые сами требуют либо рекурретности , либо разложения в ряд Тейлора соответствующей функции ) :
Смущает меня тот факт , что нигде и никогда не говорится о том , что вся эта " система " , так скажем , с обратной связью и самое главное - эта возникающая в зависимости от внешних условий , коммуникация , очень устойчива , не смотря на чудовищное разнообразие внешних условий . Одними алгоритмами , инструкциями и т.д. все многообразие внешних факторов , " запрограммировать " невозможно .
Кстати о рисунках : и просто молекулы , только под действием законов физики ( не имея никакой " коммуникации " ) , способны создавать фигуры ( рисунки ) фантастически совершенные с точки зрения математики ( например снежинки ) . Но изменились условия - ...и все....
Вот поэтому , я думаю , что такие сложные системы не могут не иметь механизмов коммуникации , а иначе как ( например ) та же самая " нашинкованная на лоскуты " планария " знает " что ей нужна одна голова , один хвост и т.д. И кто бы давал команды " запуск " , " стоп " и т.д. при отсутствии " коммуникации " ...
Зная механизмы этой коммуникации ( " язык " ) , по моему можно добиться головокружительных результатов . А самое интригующее : допустим мы один раз вмешались в этот механизм ( механизм именно коммуникаций !!! ) и получили нечто отличное от " идеала " . Вы уверены , что после того , как придет момент " делится " или " продолжать род" , мы не обнаружим опять не " идеал " ?! ( уже без нашего вмешательства ) ....
Возвращаясь к планариям : если мне не изменяет память , то " нашинковав " их на бешеную кучу частей , мы их не уничтожим - каждая часть восстановится в полноценную особь . Вот и спрашивается - каким это чудным образом " система " создает не только нужные " градиенты " , но и знает в каком месте , когда и как создать их ... Ведь очевидно - в " программах " ДНК И РНК это нет - это , выражаясь образно , лишь инструкция .
Может неудачный аналог , но : если вам придет например мебель с подробной инструкцией по сборке , сама она не соберется . Придется приложить усилия , в смысле интеллектуальные...
Извиняюсь , опечатался : хотел написать S(p*2^n) , где р - простое . То есть проверить формулу для групп S3 и S4 для числа корней x^2=e
Вот именно : формула для числа корней в общем виде совсем не очевидна , по крайней мере для меня . Любопытно было бы увидеть подробное доказательство .
Я думаю проще попытаться найти контрпример , посчитав число корней x^2=e для групп вида S(p^n) , где р - простое . И сравнить результат .
Вот именно : формула для числа корней в общем виде совсем не очевидна , по кра
Я конечно не претендую на истину в последней инстанции , но мне кажется что ваше изложение данной темы несколько громоздко и потому непонятно для тех , кто не в теме .
Я думаю , что писать перестановки надо в виде произведения циклов : так нагляднее и на мой взгляд – понятнее , ( рядом пишу вашу запись ) . Итак :
1 ) s = ( 1 , 2, 3, 4 , 5 ) (6) = { 2,3,4,5,1,6 }
Так как для любой вообще перестановки p всегда существует натуральное число m , такое что : p^m=e ( или p^(m+1)=p ) , где e – тождественная перестановка ( это очевидно , так как степени конкретно взятой перестановки образуют подгруппу конечной группы – группы всех перестановок данного множества ) . В частности для цикла длинной m это и есть минимальная степень ( тоже очевидно ) . Итак – в нашем случае m=5 . Поэтому s^((m+1)/2) = s^3– корень данной перестановки и он единственный . То есть сразу и без вычисления , смотря на сам цикл , пишем ответ :
P= ( 1 , 4 , 2 , 5 , 3 ) ( 6 ) ; p^2 = s
2 ) s = ( 1 , 2 ) ( 3 ,4 ) ( 5) ( 6) = { 2 , 1 ,4 , 3 , 5 , 6 }
Видим два четных цикла длины два и значит будем иметь два варианта цикла длины четыре ( поменяв их местами ) , один вариант цикла длины два ( объединив единичные ) и оставляя единичные циклы неизменными . Всего четыре варианта . И тоже , можем сразу и без вычислений , лишь глядя на исходное представление перестановки , писать ответы :
P1= ( 1 ,3 , 2 , 4 ) ( 5 ) (6) ; P2= ( 1 ,4 , 2 , 3 ) ( 5 ) (6) ; P3= ( 1 ,3 , 2 , 4 ) ( 5 ,6) ; P4= ( 1 ,4 , 2 , 3 ) ( 5 ,6)
Pk^2= s .
3) s = ( 1 , 2 , 3 ) ( 4 ) ( 5) ( 6) = { 2 , 3 ,1 , 4 , 5 , 6 }
Видим один цикл длины три и три цикла единичной длины . У нас всего три варианта объединить единичные циклы в цикл длиной два и один вариант – оставить единичные циклы . Всего четыре корня :
P1= ( 1 ,3 , 2 ) ( 4, 5 ) (6) ; P2= ( 1 ,3 , 2 ) ( 4, 6 ) (5); P3= ( 1 ,3 , 2 ) ( 5 ,6) (4) ; P1= ( 1 ,3 , 2 ) ( 4 ) ( 5 ) (6)
Pk^2= s .
4) s = ( 1 , 2 ) ( 3 , 4 ) ( 5 , 6 , 7 ) = { 2 , 1 , 4 , 3 , 6 , 7 , 5 }
Имеем два цикла длиной два и один цикл длиной три . То есть здесь будут всего два корня от перемены мест двух четных циклов :
( 1 , 2 ) ( 3 , 4 ) получим ( 1 , 3 , 2 , 4 ) и ( 3 , 4 ) ( 1 , 2 ) получим ( 3 , 1 , 4 , 2 ) = ( 1 , 4 , 2 , 3 ) . Итак , имеем :
P1= ( 5 ,7 , 6 ) ( 1, 3 , 2 , 4 ) ; P2= ( 5 ,7 , 6 ) ( 1, 4 , 2 , 3 ) ; Pk^2= s .
5 ) s = ( 1 , 2 , 3 , 4 , 5 ) ( 6 ) ( 7) = { 2 , 3 ,4 , 5 , 1 , 6 , 7 }
Видим один цикл длины 5 и два единичных цикла . А значит всего два корня – оставляем единичные циклы без изменений и объединяем их . Так как ( 5+1)/2 = 3 , то s^3 – корень квадратный . Итак :
P1= ( 1 ,4 , 2 , 5 , 3 ) ( 6 ) ( 7) ; P2= = ( 1 ,4 , 2 , 5 , 3 ) ( 6 , 7) ; Pk^2= s .
Ну и так далее . Все вычисляется вручную и очень быстро …
Да , вы правы – формула верна . Я всегда был уверен , что она верна для простых полей . Сейчас освежил память , так как все это было очень-очень давно . И действительно – даже если в поле имеются не примитивные подполя , формула верна . Так что извиняюсь .
Только мне не понятно , зачем искать примитивные многочлены простым перебором . Можно сократить сильно поиски , используя например ( не залезая уж совсем в дебри алгебры ) круговые многочлены :
Пусть имеется поле GF(p^n) . Как известно , его мультипликативная группа состоит из q=p^n-1 элементов . Есть такая теорема :
Произведение всех неприводимых многочленов степени m ( обозначается I(q,m,x) ) равно произведению круговых многочленов Qk(x) , где произведение берется по таким k- делителям числа q , для которых m – минимальная степень p , такая что : p^m=1(mod(k)) .
Очевидно , что в этом произведении присутствует круговой многочлен Qq(x) и там , и только там присутствуют все примитивные элементы степени fi (q) , которых fi (q)/n .
Пример :
Пример GF(2^5)
x^31= Q1(x)* Q31(x)
Q1(x)=x-1
Q31(x)=(x^31-1)/(x-1)
I(2,5,x)= Q31(x) . То есть все неприводимые многочлены – примитивны . Так как многочлены 2 и 3 степени неприводимы над полем тогда и только тогда , когда у них нет корней в этом поле , то не трудно видеть , что такими многочленами являются x^2+x+1 , x^3+x+1 и x^3+x^2+1 . Исключая из произвольного многочлена 5 степени такие z : z^2=z+1 и z^3= z+1 и z^3=z^2+1 простым перебором , даже в ручную довольно быстро получаем все примитивные многочлены :
1+x^2+x^5
1+x+x^2+x^3+x^5
1+x^3+x^5
1+x+x^3+x^4+x^5
1+x^2+x^3+x^4+x^5
1+x+x^2+x^5+x^4
Пример GF(2^6)
x^63-1= Q1(x)* Q3(x)* Q7(x)* Q9(x)* Q21(x)* Q63(x)
Q1(x)=x-1
Q3(x)=x^2+x+1
Q7(x)=x^6+x^5+x^4+x^3+x^2+x+1
Q9(x)=x^6+x^3+1
Q21(x)=x^12+x^11+x^9+x^8+x^6+x^4+x^3+x+1=( x^6+x^4+x^2+x+1)*(x^6+x^5+x^4+x^2+1) =P1(x)*P2(x)
Q63(x)….
I(2,6,x)=Q9(x)Q21(x)Q63(x) . Как видим -Q7(x) не входит в это произведение ,а значит он разлагается . И действительно : Q7(x+1) = x^6+x^5+x^4+x^3+x^2=x^2(x^4+x^3+x^2+1) . То есть Q7(x)=(x^2+1)(x^4+x^3+1)
Так как Q9(x) ,P2(x)- неприводимыe многочлены , то не приводимые и
Q9 (x+1)= x^6+x^4+x^3+x+1
P2(x+1)= x^6+x^5+x^2+x+1
Так как только x^2+x+1, x^3 +x+1 и x^3+x^2+1 неприводимые многочлены степени не выше третей , то неприводимы и
x^6+x+1
(x^2+x+1)*x^4+x+1=x^6+x^5+x^4+x+1= P3(x)
P3(x+1)= x^6+x^5+1
Итак : f(x) = x^6+x^4+x^3+x+1 , x^6+x^5+x^2+x+1, x^6+x+1 , x^6+x^5+x^4+x+1 , x^6+x^5+1 – примитивные многочлены над GF(2) , а значит порождающие поле GF(2^6) . C ходу не получается найти лишь последний .
Согласен, что поиск примитивных многочленов над не простым полем, то есть над полем GF(p^n) , задача “так себе” – представляет из себя чисто теоретический интерес . Но суть не в этом. У вас, во-первых, не совсем корректное определение примитивного многочлена над простым полем ( в частности ) .
Дело в том , что у вас путаница с понятием примитивный элемент и примитивный многочлен над конечным полем. Поэтому я привел не простое поле в качестве намека .
Например , вы пишите : “ … примитивный элемент может не определится …” Но дело в том , мультипликативная группа ненулевых элементов конечного поля GF(q) – циклична ( здесь q – не обязательно простое число ) , а ее образующий элемент называется примитивным элементом . Их , как известно , fi (q-1 ) , где ( у меня так обозначено ) fi – функция Эйлера . Подозреваю , вы путаете фактор -кольцо кольца целых чисел по главному идеалу ( или проще – кольцо классов вычетов ) , с фактор – кольцом кольца целых чисел по главному идеалу от простого числа , которое является полем – в нем обязательно будет примитивный элемент , так как это конечное поле . В любом поле , даже если его мультипликативная группа состоит из q элементов , где q – не простое число , всегда будет примитивный элемент и не всегда один . Точнее :
Мультипликативная группа ненулевых элементов конечного поля GF(q) – циклична ( здесь q – не обязательно простое число ) , а ее образующий элемент называется примитивным элементом . Их , как известно , fi (q-1 ) , где ( у меня так обозначено ) fi – функция Эйлера .
Поехали далее :
Есть такая теорема – если многочлен степени n - f(x) принадлежит GF(q)(x) и является неприводимым , то любой корень этого многочлена принадлежит полю GF(q^n) .Более того , его полем разложения над полем GF(q) является GF( q^m ) и поля любых двух разных неприводимых многочленов одной и той -же степени изоморфны друг другу .
Другими словами : Кольцо многочленов по модулю некоторого неприводимого в поле GF(q)
многочлена p(x) степени m является полем GF(q^m). Здесь везде q – не обязательно простое.
Далее , вы пишите : “…порождающий полином неприводим и примитивен …”
Как видно из вышеописанного – это неверно . Достаточно неприводимости . Я приводить пример не буду , вы его сами привели взяв порождающий многочлен x^2+1 для поля GF( 3^2) – очевидно , что этот многочлен не примитивен.
Так вот , одно из определений : порождающий многочлен , это такой неприводимый над полем многочлен , который имеет примитивный корень в расширенном поле , точнее – все его корни будут примитивными .
Теперь переходим к полю GF(p^n ) . Так как его мультипликативная группа циклична , то она состоит из всех корней многочлена x^q-1=0 , где q= p^n -1 .
Например :
GF(2^2) имеем : x^3-1=(x-1)(x^2+x+1 ) . Как видим – единственный примитивный многочлен это x^2+x+1 GF(2^3) имеем : x^7-1=(x-1)(x^3+ x^2 +1 )(x^3+x+1) . Как видим – два примитивных многочлена это x^3+x^2+1 и x^3+x+1 GF(3^2) имеем : x^8-1=(x^4+1)( x^2 +1 )(x-1)(x+1)=(x^2+x+2)(x^2+2x+2)(x^2+1)(x-1)(x-2) . Как видим – два примитивных многочлена это x^2+2x+2 и x^2+x+2
И вообще , есть такая теорема – если n не делится на характеристику поля GF(q) , то многочлен x^n -1 разлагается в произведение так называемых циклических многочленов Qd(x) над его простым полем , где произведение берется по всем делителям числа n .
Круговой многочлен Qd(x) = П ( x^(n/d)-1) ^ mu(d) , где произведение берется по всем делителям числа d числа n ( здесь mu – функция Мебиуса .
В частности :
Qp(x) ( p- простое ) = 1+ x+x^2+x^3+…x^(p-1)
Qp^k(x) ( p -простое )
=(x^p^k-1)/(x^p^(k-1)-1)= 1+x^p^(k-1) +x^(2p^(k-1))+ x^(3p^(k-1))+… x^((p-1)p^(k-1)) Например : Q3(x)=1+x+x^2 – сразу получаем примитивный многочлен для GF(2) Q5(x)=1+x+x^2+x^3+x^4 Q15(x)=x^8+x^7+x^5+x^4+x^3+x+1 И так как Q5(x+1)=x^4+x^3+1 ( для GF(2) ) – неприводимый многочлен в этом поле , то он делит Q15(x)= ( x^4+x^3+1)( x^4+x+1)
То есть получаем для GF(2^4) два примитивных многочлена x^4+x^3+1 и x^4+x+1 над полем GF(2)
Я писал : количество примитивных многочленов в поле GF( 9 ) ...
Вопрос лишь в том , что такое примитивный многочлен степени m над полем GF( q ) , где q = p^m ( m = 1 - частный случай ) . И их количество не определяется функцией Эйлера....
" Количество примитивных полиномов определяется функцией Эйлера " ..
Утверждение ложно . Например для поля F9 имеется 16 примитивных многочленов , а по вашей формуле получается 2...
Вывести можно лишь число нормированных неприводимых многочленов степени n , где участвует функция Мебиуса от делителей числа n , помноженная на степеня n по всем делителям и все это деленное на n .
А что насчет равновесия Нэша ?
....Про многочлены Бернули и связь интегрального исчисления с дискретным суммированием , про гармонические числа....
https://cyberleninka.ru/article/n/o-raspredelenii-prostyh-i-prostyh-chisel-bliznetsov-na-skaterti-ulama/viewer
Спасибо . Надо будет попробовать как -нибудь .
Я и не утверждал , что способ не рекуррентный . Я лишь говорил - он максимально простой , причем во всех смыслах !!!
Есть другое решение ? ! - Буду рад с ним ознакомиться ...
И еще вопрос : как вы умудряетесь вводить математическую символику в комментарии - я пытался тупо скопировать из Maple , c соответствующим форматированием - хрень получается . Я что- то не знаю ?
И еще : в " методе через интеграл " не обязательно вводить ( и даже знать ) числа Бернули : сумма всех кожффициентов равна единице - этого достаточно .
Просто " бонус " : можно не вычислять коэффиициент при n , а взать табличный В ( к ) - дело вкуса ( и знаний... )
Не согласен .
Во первых : рекуррентные формулы , приводимые ранее , требуют знания , а главное - использования всех предыдущих формул для сумм . В " моем " варианте - требуется лишь знание предыдущей суммы и интергал ( приметивнее не бывает...) . Спорить , по моему , невозможно - этот вариант явно проще .
Вычисление " в лоб " через числа Бернули - как вариант , если под рукой есть соответствующая таблица ( чисел Бернули ) , либо соответствующая программа...
В любом случае - рекуррентные формулы - это однозначно , более сложный путь .
А биноминальные коэффициенты посчитать можно даже в ручную и это проще чем суммировать все предыдущие суммы и кстати , тоже с использованием биноминальных коэффициентов .
Я думаю , тут вопрос восприятия : и биноминальные коэффициенты и числа Бернули , можно посчитать самостоятельно и даже вручную , а можно просто " взять " из " таблиц " .
Мой самый первый коммертарий как раз и говорил о том , что " интегральный " способ - наиболее простой и максимально примитивный из всех возможных , для достижения цели и что числа Бернули требуют те же рекуррентные соотношения ( либо разложения в ряд образующей функции ) .
Вы спросили : есть ли " прямая " формула . Я ответил - есть ...
Опечатался - пишу " на ходу " . Cуммирование идет от 0 до k....
Предыдущая , точнее - самая первая сумма - это сумма нулевых степеней , которая , очевидно равна n . Дальше - интегралом получаем последовательно формулы для любых степеней .
Если подставить в явной форме в формулу для интеграла : Pk(n)=Sum (a(k+1-m)*n^m , 1..k+1) можно получить формулы зависимости коэффициентов следующей суммы от коэффициентов предыдущей . Эту зависимость один из комментаторов показал , но не в общем виде - видимо для наглядности . Правда написал , что коэффициент при первой степени n , надо вычислять ( сумма всех коэффициентов полинома равна 1 ) .
Кстати - этот коэффициент можно не вычислять : это всегда число Бернулли B(k) ...
Уйти от рекуррентности формально можно и написать формулу полинома для любой суммы степеней к ...но через числа Бернули ( которые сами требуют либо рекурретности , либо разложения в ряд Тейлора соответствующей функции ) :
Pk(n)=(1/(k+1))*Sum ( B(m)*C(m,k+1)*n^(k+1-m) ,m=1...k+1 )
здесь C(m,k+1) - биноминальные коэффициенты
Смущает меня тот факт , что нигде и никогда не говорится о том , что вся эта " система " , так скажем , с обратной связью и самое главное - эта возникающая в зависимости от внешних условий , коммуникация , очень устойчива , не смотря на чудовищное разнообразие внешних условий . Одними алгоритмами , инструкциями и т.д. все многообразие внешних факторов , " запрограммировать " невозможно .
Кстати о рисунках : и просто молекулы , только под действием законов физики ( не имея никакой " коммуникации " ) , способны создавать фигуры ( рисунки ) фантастически совершенные с точки зрения математики ( например снежинки ) . Но изменились условия - ...и все....
Вот поэтому , я думаю , что такие сложные системы не могут не иметь механизмов коммуникации , а иначе как ( например ) та же самая " нашинкованная на лоскуты " планария " знает " что ей нужна одна голова , один хвост и т.д. И кто бы давал команды " запуск " , " стоп " и т.д. при отсутствии " коммуникации " ...
Зная механизмы этой коммуникации ( " язык " ) , по моему можно добиться головокружительных результатов . А самое интригующее : допустим мы один раз вмешались в этот механизм ( механизм именно коммуникаций !!! ) и получили нечто отличное от " идеала " . Вы уверены , что после того , как придет момент " делится " или " продолжать род" , мы не обнаружим опять не " идеал " ?! ( уже без нашего вмешательства ) ....
Ну а ссылку я обязательно посмотрю...
Понятно , что как всегда ничего не понятно .
Возвращаясь к планариям : если мне не изменяет память , то " нашинковав " их на бешеную кучу частей , мы их не уничтожим - каждая часть восстановится в полноценную особь . Вот и спрашивается - каким это чудным образом " система " создает не только нужные " градиенты " , но и знает в каком месте , когда и как создать их ... Ведь очевидно - в " программах " ДНК И РНК это нет - это , выражаясь образно , лишь инструкция .
Может неудачный аналог , но : если вам придет например мебель с подробной инструкцией по сборке , сама она не соберется . Придется приложить усилия , в смысле интеллектуальные...