Базис малого веса для полиномиального модуля

[spk]

Здравствуйте!
Передо мной стоит вот такая задача. Исходные данные:

1. пусть $\{f_i(x) \in \mathbb{F}_{2^l}[x]/\langle x^m - 1 \rangle\}$ - множество порождающих элементов для некоторого $\mathbb{F}_2[x]$-подмодуля $\mathcal{C}$ алгебры $\mathbb{F}_{2^l}[x]/\langle x^m - 1 \rangle$; например, при $l=3, m=5$ рассматриваемый подмодуль порождается с помощью $\{1 + \alpha \cdot x + x^2, \alpha^2 + (1 + \alpha)x^4\}$, где $\alpha$ - примитивный элемент поля $\mathbb{F}_{2^l}$.
2. весом $w: \mathbb{F}_{2^l}[x]/\langle x^m - 1 \rangle\ \to \mathbb{Z}_{\ge 0}$ называется количество мономов в многочлене - представителе класса смежности; например, $w((1+ \alpha \cdot x + x^2) + \langle x^m-1 \rangle)=3$.

Требуется найти такое порождающее множество для порождающих подмодуля $\mathcal{C}$, чтобы сумма весов его элементов была бы минимальной.

Другими словами, необходимо найти более "разреженное" представление для модуля $\mathcal{C}$. Очень хотелось бы иметь алгебраическую процедуру решения этой задачи. Но я, честно говоря, пока не знаю, как к нему подойти. Поиск в Интернет мне ничего не дал. Буду рад любым мыслям и предложениям. Возможно, кто-нибудь уже сталкивался с такой же проблемой.

Спасибо!

[Leox]

Для начала, решите ету задачу для указаного примера - $\{1 + \alpha \cdot x + x^2, \alpha^2 + (1 + \alpha)x^4\}$.

[Xaositect]

Leox в сообщении #335417 писал(а):

для указаного примера

Для указанного примера суммарный вес равен 5 :)

Я что-то не могу придумать примера, у которого вес меньше, чем у $\{1,\alpha,\dots,\alpha^{l-1}\}$. Впрочем, доказать его минимальность сходу тоже не получается.

-- Сб июн 26, 2010 20:11:01 --

Хотя что это я. Вы тут неправильные порождающие множества пишете.

$\mathbb{F}_{2^l}/\langle{x^m - 1}\rangle$ же является алгеброй над полем $\mathbb{F}_2$ размерности $lm$. Любое порождающее множество $F = \{f_1,\dots,f_k\}$ из $k$ элементов для $\mathbb{F}_{2^l}/\langle{x^m - 1}\rangle$ сразу же дает порождающее множество $\{f x^j|f\in F, 0\leq j < m\}$ для него как л.п. над $\mathbb{F}_2$ из не более, чем $km$ элементов.
Значит, любое порождающее множество содержит не менее $l$ элементов, а из них минимальный вес будет иметь $\{1,\alpha,\dots,\alpha^{l-1}\}$.

Или я что-то упустил?

[Leox]

Xaositect в сообщении #335420 писал(а):

Leox в сообщении #335417 писал(а):

для указаного примера

Для указанного примера суммарный вес равен 5 :)

Нет. Возможно существует другая порождающая система етого модуля для которой суммарный вес меньше пяти. Поетому я и спрашивал о том как он решает етот пример. Насколько я понимаю ему нужно перебрать все возможные порождающие системы модуля $C$ и найти среди них систему минимального суммарного веса.

-- Сб июн 26, 2010 19:51:33 --

Xaositect в сообщении #335420 писал(а):

Значит, любое порождающее множество содержит не более $l$ элементов, а из них минимальный вес будет иметь $\{1,\alpha,\dots,\alpha^{l-1}\}$.

Или я что-то упустил?

Мне кажется вы просто оценили снизу возможный суммарный вес. Топикстартер же спрашивал другое - предложить алгоритм, который для заданного $\mathbb{F}_2[x]$-модуля $C$ находит такую систему порождающих елементов, для которой суммарный вес был-бы минимальным. Но, уже задача нахождения всех порождающих систем модуля есть непростой задачей.

[spk]

Спасибо за интерес!

Leox, Вы правы: мне необходимо найти минимальную по весу порождающую систему модуля, который задан какой-то системой порождающих.

Xaositect, система $\{1, \alpha, \ldots, \alpha^{l-1}\}$ ведь будет порождающей для всего кольца $\mathbb{F}_{2^l}[x]/\langle x^m-1 \rangle$, а я рассматриваю только его подалгебру - $\mathbb{F}_2[x]$-модуль $\mathcal{C}$.
Алгебры $\mathbb{F}_{2^l}[x]/\langle x^m-1 \rangle$ и $\mathbb{F}_2^{m \cdot l}$ сами по себе не изоморфны, а изоморфны будут именно $\mathbb{F}_2^{m \cdot l}$ и $\mathbb{F}_2[x]$-модуль алгебры $\mathbb{F}_{2^l}[x]/\langle x^m-1 \rangle$, порожденный $\{1,\alpha,\ldots,\alpha^{l-1}\}$. А так, действительно, можно искать вектор из $\mathbb{F}_2^{m \cdot l}$ минимального веса. Но проблема в том, что у меня определенный модуль, заданный системой порождающих.

Leox, я пытался решить (правда, не успешно) хоть какой-нибудь пример следующим образом (какое-то полуэвристическое подобие желаемой алгебраической процедуры):
ищу такую матрицу $B$ над $\mathbb{F}_2[x]$ с единичным определителем, чтобы $B \cdot A$ при обычном умножении матрицы на матрицу бы имело побольше нулей (вот тут как раз и проблемы - пока не смог ни найти такой матрицы, ни приблизиться даже к необходимым условиям на нее). Соответственно искомый мною базис и будет $B \cdot A$, где $A$ - это вектор, состоящий из многочленов - элементов порождающего множества модуля.

Это, конечно, всё вилами по воде писано, и задача вроде бы абсолютно переборная, но вдруг кто-нибудь с ней уже сталкивался и как-нибудь решал.

Спасибо!

[Xaositect]

spk в сообщении #335571 писал(а):

Xaositect, система $\{1, \alpha, \ldots, \alpha^{l-1}\}$ ведь будет порождающей для всего кольца $\mathbb{F}_{2^l}[x]/\langle x^m-1 \rangle$, а я рассматриваю только его подалгебру - $\mathbb{F}_2[x]$-модуль $\mathcal{C}$.

Извиняюсь, совсем просмотрел.

Подумаю еще, может быть, напишу что-нибудь.

[Leox]

spk в сообщении #335571 писал(а):

Спасибо за интерес!
Это, конечно, всё вилами по воде писано, и задача вроде бы абсолютно переборная, но вдруг кто-нибудь с ней уже сталкивался и как-нибудь решал.

Задача о нахождении всех базисов даже линейного постранства над конечным полем не так проста, а у вас же не линейное пространство а модуль. Вот я и спрашиваю, повторно - вы можете найти, для указаного примера, хотя бы один другой базис модуля, отличный от предложенного? Такого рода вычисления в полиномиальных алгебрах выполняются например при помощи базисов Гребнера. Попробуйте все таки начать с нахождения базисов модуля.

[spk]

Спасибо всем!
Задачу приближённо решил следующим образом:

1. нашёл изоморфизм с подалгебрами некоторой структуры, для которой нахождение редуцированного базиса Грёбнера просто и приятно.
2. на основе общего вида резуцированного базиса Грёбнера нашёл верхнюю оценку на вес.
3. минимизировал её: найденный в пункте 1 изоморфизм сохраняет вес.

Вообщем методом "выход за пределы квадрата" построил некий приближенный алгоритм. Что, наверное, достаточно неплохо.

[Leox]

теперь напишите статью и отошлите в какой нибудь западный журнал.. Базисы Гребнера ето сейчас очень модно и всякие новые нестандарные приложения всячески приветствуются и являются публикабельными