Задачи по многочленам (Винберг)

[caxap]

Спасибо за проверку.

Ales в сообщении #412659 писал(а):

Формулу Виета Вы использовали для нахождения свободного члена.

И без Виета ясно, что в $(x-1)(x-2)\cdots(x-(n-1))$ свободный член $(n-1)!$.

Ales в сообщении #412659 писал(а):

Кстати, Вы получили заодно, что остальные симметрические многочлены - нули

Круто.

5.4. В кольце $\mathbb Z[i]$ (гауссовы числа) разложить на простые множители числа $2,3,5$ и подумать, в чём принципиальная разница между этими случаями.

$2=(1-i)(1+i)$. $N(1\pm i)=2$ простое, значит $2\pm i$ гауссовы простые.
$5=(2-i)(2+i)$. $N(2\pm i)=3$ простое, значит $2\pm i$ гауссовы простые.
$3$ простое, т. к. $N(3)=9$ можно представить только как $3\cdot 3$ и нет таких целых чисел $a,b$, что $a^2+b^2=3$. Правильно?

Вопрос про принципиальную разницу я не очень понял. Разница есть: три простое, а два и пять нет. Наверное, что-то более глубокое спрашивалось...

[Ales]

caxap в сообщении #412682 писал(а):

$5=(2-i)(2+i)$. $N(2\pm i)=3$ простое, значит $2\pm i$ гауссовы простые.

Должно быть: $N(2\pm i)=5$

-- Пн фев 14, 2011 00:03:13 --

caxap в сообщении #412682 писал(а):

Вопрос про принципиальную разницу я не очень понял.

Вопрос о представлении чисел в виде суммы двух квадратов (или о разложении на сопряженные множители в кольце гауссовых чисел) был впервые изучен П. Ферма.
Все простые числа вида 4n+1 представимы в виде суммы двух квадратов, например 5.
Простые числа вида 4n-1 не представимы в виде суммы двух квадратов, например 3.

Двойка является квадратом в кольце $\mathbb Z[i]$, с точностью до умножения на "единицу" кольца - то есть на $i$. В этом наверное и состоит "принципиальное отличие".

[caxap]

Ales в сообщении #412720 писал(а):

Должно быть: $N(2\pm i)=5$

Да, извините, я описАлся.

Ales в сообщении #412720 писал(а):

Двойка является квадратом в кольце $\mathbb Z[i]$

Это как?

[caxap]

5.5.а Перечислить все неприводимые многочлены степени $\le 4$ над полем $\mathbb Z_2$.

В голову приходит только перебор:

00010 -- $x$
00011 -- $x+1$
00100 -- $x^2=xx$
00101 -- $x^2+1=(x+1)^2$
00110 -- $x^2+x=x(x+1)$
00111 -- $x^2+x+1$
01000 -- $x^3=xxx$
01001 -- $x^3+1=(x+1)(x^2+x+1)$
01010 -- $x^3+x=x(x^2+x)$
01011 -- $x^3+x+1$
01100 -- $x^3+x^2=x^2(x+1)$
01101 -- $x^3+x^2+1$
01110 -- $x^3+x^2+x=x(x^2+x+1)$
01111 -- $x^3+x^2+x+1=(x+1)(x^2+1)$
10000 -- $x^4=xxxx$
... уфф, надоело.

Вопроса три:
1) $0$ и $1$ можно назвать неприводимыми многочленами?
2) Как проверить, что многочлен неприводим? Выше я считал неприводимым все многочлены, которые мне не удалось разложить...
3) Можно ли обойтись без перебора?

[ewert]

caxap в сообщении #412936 писал(а):

... уфф, надоело.

Хм. Многочлены первой степени неприводимы по определению (а к многочленам нулевой степени это понятие вроде бы и неприменимо). Неприводимые многочлены второй и третьей степеней -- это просто не имеющие корней. Т.е. заканчивающиеся на единицу и имеющие нечётное количество ненулевых слагаемых. Для четвёртой степени из этого списка следует исключить многочлены, раскладывающиеся на два неприводимых квадратных, а таких и всего-то один.

[caxap]

ewert в сообщении #412945 писал(а):

Для четвёртой степени из этого списка следует исключить

Что значит "из этого списка исключить"? Если вы имеете в виду приписать ко всем неприводимым многочленам меньшей степени член $x^4$ и из них исключить $(x^2+x+1)^2$, то не получается. Напр. $x^3+x+1$ неприводим (?), но $x^4+x^3+x+1=(x+1)^2(x^2+x+1)$.

Я правильно понял, чтобы проверить на неприводимость, надо показать, что многочлен не имеет корней? Но в случае $\deg\ge 3$ это не так легко.

Ладно, может после этой наступит просветление:

5.2.б. Доказать, что в $\mathbb Z_2[x]$ существует ровно 6 неприводимых многочленов степени 5.

Тут опять перебор? Ещё есть идея (тоже переборная) написать все возможные произведения неприводимых многочленов меньшей степени, дающие многочлен 5-й степени. Все многочлены, которые таким образом не получились, неприводимы. Не знаю, что легче.

[ewert]

caxap в сообщении #412955 писал(а):

Тут опять перебор?

Тут ровно так же. Корней быть не должно -- значит, многочлен должен заканчиваться на единицу и при этом иметь или пять слагаемых (таких четыре штуки), либо три (таких тоже четыре). Из этого набора надо исключить многочлены, раскладывающиеся на неприводимые многочлены второй и третьей степени, а их два: $(x^2+x+1)(x^3+x^2+1)$ и $(x^2+x+1)(x^3+x+1)$. Итого шесть штук.

[caxap]

ewert в сообщении #412945 писал(а):

Т.е. заканчивающиеся на единицу и имеющие нечётное количество ненулевых слагаемых.

ewert в сообщении #412959 писал(а):

Корней быть не должно -- значит, многочлен должен заканчиваться на единицу и при этом иметь или пять слагаемых (таких четыре штуки), либо три (таких тоже четыре).

Мм... А это из каких соображений, я что-то не догоню (Ну единица понятно, иначе можно $x$ вынести за скобки, а про чётность не понял.)

[ewert]

caxap в сообщении #412971 писал(а):

а про чётность не понял.)

Ну как. Единичка является корнем тогда и только тогда, когда при её подстановке в многочлен окажется чётное количество складываемых единичек.

Ладно, в качестве продолжения: количество неприводимых многочленов шестой степени -- это, по той же логике

$1+C_5^3+C_5^1-1\cdot1\cdot1-1\cdot3-(2+1)$

(если не сбился со счёта).
Седьмой -- тоже не очень трудно, а дальше уже хуже.

[caxap]

Понял. Спасибо за разъяснения.

[caxap]

7.1. Доказать, что размерность пространство однородных многочленов степени $d$ от $n$ переменных равна

$$\frac{n(n+1)\cdots (n+d-1)}{d!}$$

Базис пространства многочленов составляют векторы $x_1^{k_1}\cdots x_n^{k_n}$. Базис однородных многочленов степени $d$ образует те векторы, в которых $k_1+\cdots+k_n=d$, $k_i\in\mathbb Z_{\ge 0}$. Нам нужно посчитать количество таких возможностей. Это число и правда согласуются с формулой из задачи, но вывести её не получается. Пробовал так: у нас есть $d$ предметов, расположенных в ряд, и нам нужно расставить $n$ перегородок между ними. Но так получается $\binom{d+1}n$, что неправильно.

[Ales]

caxap в сообщении #412908 писал(а):

Ales в сообщении #412720 писал(а):
Двойка является квадратом в кольце $\mathbb Z[i]$

Это как?

$2=-i(1+i)(1+i)$

-- Пн фев 14, 2011 23:42:31 --

caxap в сообщении #413042 писал(а):

Пробовал так: у нас есть $d$ предметов, расположенных в ряд, и нам нужно расставить $n$ перегородок между ними. Но так получается $\binom{d+1}n$, что неправильно.

Дело в том, что могут быть нулевые степени.
Увеличьте все степени на $1$, а $d$ - на $n$.

Я не придумываю ответы, а как-то вспоминаю.

[VAL]

ewert в сообщении #412945 писал(а):

caxap в сообщении #412936 писал(а):

... уфф, надоело.

Хм. Многочлены первой степени неприводимы по определению (а к многочленам нулевой степени это понятие вроде бы и неприменимо).

Можно я усилю?
Не просто "вроде бы неприменимо", категорически неприменимо (что-то я сегодня очень категоричен )

Неприводимый многочлен - прямой аналог простого числа. А считать многочлены нулевой степени неприводимыми - это все равно что считать единицу простым числом. Впрочем, многие так и считают...

Но считают неправильно!
Разложение многочленов на множители ведется с точностью до ассоциированности, то есть до обратимых множителей. А это и есть многочлены нулевой степени. То есть то, чем при разложении пренебрегают.

-- 15 фев 2011, 00:28 --

caxap в сообщении #412955 писал(а):

Я правильно понял, чтобы проверить на неприводимость, надо показать, что многочлен не имеет корней? Но в случае $\deg\ge 3$ это не так легко.

Для многочленов степени выше третьей это только "не так легко". Это просто неверно. То есть, отсутствие корней, условие, конечно, необходимое, но явно недостаточное.
Не так давно я уже отвечал здесь же на похожий вопрос. Вот самоцитата:

Цитата:

Почитайте книжку Лидл, Нидеррайтер "Конечные поля"или мои лекции во по этой ссылочке (лучше скачать полный экземпляр лекций по второй ссылке). Там все подробно написано. С доказательствами и даже с примерами.

[caxap]

VAL
Спасибо за информацию. (Только сейчас понял, почему 1 не считают простым числом.) Лекции почитаю.

Ales в сообщении #413100 писал(а):

Увеличьте все степени на $1$, а $d$ - на $n$.

Спасибо за подсказку, но всё равно не выходит. Пусть количество переменных $n$, а получить нужно степень $d$. Заменим задачу эквивалентной: степень каждой переменной $\ge 1$, а получить нужно $n+d$ степень. Расположим $n+d$ камешков в ряд. Нам нужно разбить их на $n$ частей. Для этого нужно разместить в $n+d-1$ местах между ними $n-1$ перегородки. То есть $\binom{n+d-1}{n-1}$ случаев, но это не сходится с ответом; если выражать ответ в виде бин. коэффициента, то должно быть $\binom{n+d-1}{d}$.

[ewert]

Это одно и то же.