Задача про набор элементов группы

[Руст]

Рассмотрите в начале группы попроще. Любая коммутативная группа раскладывается в прямую сумму групп типа $Z/nZ$, где $n$ степень простого числа. Тут умножение соответствует сложению по модулю $n$. Легко показать, что $m=1+[log_2(n)]$ элементов всегда дадут 1. Аналогично для прямых сумм. В некоммутативном случае количество возможных значений произведения зависит ещё и от порядка умножения. Поэтому вышеуказанная верхняя граница остается в силе. Точное значение для разных групп в особенности для некоммутативных трудно подсчитать.

[Профессор Снэйп]

Руст в сообщении #301835 писал(а):

Рассмотрите в начале группы попроще. Любая коммутативная группа раскладывается в прямую сумму групп типа $Z/nZ$, где $n$ степень простого числа. Тут умножение соответствует сложению по модулю $n$. Легко показать, что $m=1+[log_2(n)]$ элементов всегда дадут 1.

Не понял. $m(\mathbb{Z}_n)=n$, это, вроде, очевидно.

[Руст]

Цитата:

Не понял. $m(\mathbb{Z}_n)=n$, это, вроде, очевидно.

Рассмотрите $Z_3=\{e,a,a^2\}$. Любая двухэлементная фракция или содержит $e$, тем самым партия или содержит $\{a,a^2 \}$ произведение которых $e$, тем самым является партией. Т.е. $m(Z_3)=2$, так как имеется одноэлементные фракции не являющиеся партией. Аналогично рассматриваются остальные $Z_n$.

[Хорхе]

Тут все решают разные задачи, вот и ответы разные.

[mihiv]

Может быть задачу лучше сформулировать так:для любой группы $G$ порядка n,найти минимальное m,такое,что из любого набора $(a_1\dots a_m)$ различных элементов $G$ можно выбрать поднабор различных элементов $(a_{i_1}\dots a_{i_k})$,такой что $a_{i_1}\dots a_{i_k}=e.$
Руст,видимо,имеет в виду такую формулировку.

[VoloCh]

Не хотите ль вернуться к школьной задаче про таблицу с $\pm1$?

[Руст]

mihiv в сообщении #302014 писал(а):

Может быть задачу лучше сформулировать так:для любой группы $G$ порядка n,найти минимальное m,такое,что из любого набора $(a_1\dots a_m)$ различных элементов $G$ можно выбрать поднабор различных элементов $(a_{i_1}\dots a_{i_k})$,такой что $a_{i_1}\dots a_{i_k}=e.$
Руст,видимо,имеет в виду такую формулировку.

Да. А какую ещё интерпретацию можно придумать относительно исходного условия?

[Профессор Снэйп]

mihiv в сообщении #302014 писал(а):

Может быть задачу лучше сформулировать так:для любой группы $G$ порядка n,найти минимальное m,такое,что из любого набора $(a_1\dots a_m)$ различных элементов $G$ можно выбрать поднабор различных элементов $(a_{i_1}\dots a_{i_k})$,такой что $a_{i_1}\dots a_{i_k}=e.$
Руст,видимо,имеет в виду такую формулировку.

Вроде автор задачи специально оговорил, что элементы в наборе могут повторяться. Почему тогда вы берёте различные?

С различными, кстати, задача проще.

-- Чт мар 25, 2010 10:03:45 --

Руст в сообщении #302057 писал(а):

А какую ещё интерпретацию можно придумать относительно исходного условия?

Хорхе уже написал точную формулировку.

Хорхе в сообщении #301439 писал(а):

Я так понял условие: найти минимальное $m$, что для любой группы G порядка n из любого набора $(a_1,\dots,a_m)$ элементов $G$ можно выбрать поднабор $(a_{i_1},\dots,a_{i_k})$ ($i_j\neq i_l,j\neq l$), что $a_{i_1}\dots a_{i_k} = e$.

[mihiv]

Для больших n число неизоморфных групп порядка n велико и точно неизвестно,поэтому имеет смысл искать такое m(n),которое годится сразу для всех групп порядка n,т.е. $m(n)=max\limits _Gm(G)$,но тогда,если допускать выборки с одинаковыми элементами,то $m(n)=n$,потому что среди групп порядка n всегда есть $\mathbb{Z}_n.$
Поэтому,чтобы сделать задачу более интересной нужно по-моему ограничиться выборками с различными элементами,или,может быть, искать m(n) только для неабелевых групп.

[Руст]

Профессор Снэйп в сообщении #302092 писал(а):

mihiv в сообщении #302014 писал(а):

Может быть задачу лучше сформулировать так:для любой группы $G$ порядка n,найти минимальное m,такое,что из любого набора $(a_1\dots a_m)$ различных элементов $G$ можно выбрать поднабор различных элементов $(a_{i_1}\dots a_{i_k})$,такой что $a_{i_1}\dots a_{i_k}=e.$
Руст,видимо,имеет в виду такую формулировку.

Вроде автор задачи специально оговорил, что элементы в наборе могут повторяться. Почему тогда вы берёте различные?

С различными, кстати, задача проще.

-- Чт мар 25, 2010 10:03:45 --

Руст в сообщении #302057 писал(а):

А какую ещё интерпретацию можно придумать относительно исходного условия?

Хорхе уже написал точную формулировку.

Хорхе в сообщении #301439 писал(а):

Я так понял условие: найти минимальное $m$, что для любой группы G порядка n из любого набора $(a_1,\dots,a_m)$ элементов $G$ можно выбрать поднабор $(a_{i_1},\dots,a_{i_k})$ ($i_j\neq i_l,j\neq l$), что $a_{i_1}\dots a_{i_k} = e$.

[mihiv]

Руст в сообщении #301835 писал(а):

Легко показать, что $m=1+[log_2(n)]$ элементов всегда дадут 1.

Рассмотрим циклическую группу порядка $n$.Возьмем $m_0=[\sqrt {2n}]-1$ элементов группы:$a,a^2,\cdots ,a^{m_0}.$Здесь $a$ образующая группы.
Составляя из этих элементов всевозможные произведения будем получать элементы вида:$a^k$,где $k\leqslant \frac {m_0(m_0+1)}2<n.$И $a^k\not =e.$Поэтому должно быть $m>m_0>[\log _2n]+1$ для достаточно больших $n.$