Абелевы группы и перестановки

[lofar]

Руст, непонятно, как вы собираетесь подбирать $b_i$ для того чтобы $t$ было перестановкой. Если произвольно, то не все получится. Например, возьмем $b_i=3$, тогда нужно проверять разрешимость $a_i + \delta_{i-1}=c_i$ (*). Для $l=2$ пара уравнений $a_1 + \delta_2(a_2) = 0, a_2 + \delta_1(a_1) = 2^{k_2-1}$ решения не имеет.

[Руст]

Обозначим числа $\frac{b_i}{3}=d_i$.
$t(x)=s(x)+x$ перестановка тогда и только тогда, когда для любого $y=\sum_iy_ie_i$ существует единственное решение $t(x)=y$. Это приводит к системе уравнений ($x=\sum_ia_ie_i$):
$3a_i+3d_i\delta_{i-1}=y_i$ или $a_i=z_i-d_i\delta_{i-1}$.
Задав $\delta_l$ однозначно находим $a_1=z_1-d_1\delta_l$. Тут уже вычисляется $\delta_1$, соответственно находится $a_2$ и $\delta_2$ и в конце концов $a_l$ и $\delta_l$. Однако может не совпасть полученное значение с исходным. Меняем начальное значение на противоположное. Если и после этого не совпадение, то решений нет. Если совпадение при обоих вариантах исходного $\delta_l$ то два решения.

На самом деле достаточно подбирать $d_i$ для двух случаев, $l=2$ и $l=3$. Остальные случаи распадаются в прямую сумму таких и соответственно для них можно найти перестановку связанную с прямой суммой. Пусть $l=2$, тогда система эквивалентно:
$$a_1=z_1-d_1\delta_2, a_2=z_2-d_2\delta_1(z_1-d_1\delta_2)$ единственное решение имеется тогда и только тогда, когда $\delta_2(z_2-d_2\delta_1(z_1-d_1\delta_2))=\delta_2$ имеет единственное решение $\delta_2=0 \ or \ 1$ при любом $z_i$. При $z_1=z_2=0$ получаем необходимое условие $\delta_2(-d_2\delta_1(-d_1))=0.$ Оно удовлетворяется например при $d_1=1,d_2=-1$.
Рассмотрим этот случай для всех $z_i$, т.е. проверим единственность решения для $\delta_2$ у уравнения:

$$\delta_2(z_2+\delta_1(z_1-\delta_2))=\delta_2.$$

Если $\delta_1=\delta_2=0$, то $z_1<2^{k_1-1},z_2<2^{k_2-1}$
Если $\delta_1=1,\delta_2=0$, то $z_1\ge 2^{k_1-1},z_2=2^{k_2}-1 \ or \ z_2<2^{k_2-1}-1$.
Если $\delta_1=0,\delta_2=1$, то $1\le z_1\le 2^{k_1-1}, z_2\ge 2^{k_2-1}$.
Если $\delta_1=\delta_2=1$, то $1\le z_1\le 2^{k_1-1}, 2^{k_2-1}-1\le z_2<2^{k_2}-1.$`
Как видно, охвачены все случаи $z_1,z_2$ и всегда решение существует и единственное. Таким образом, случай $l=2$, а стало быть все четные $l$ разобраны.
Думаю не так сложно найти набор и для $l=3$, что дасть полное решение.

[lofar]

Ваше соотношение неразрешимо при $z_1=0$, $z_2=2^{k_2}-1$.

[Руст]

Да, я не правильно обобщал пример профессора Снейп.
Рассмотрю сейчас только случай $l=2$ и группу $Z_{2^k}+Z_{2^{k+d}}$.
Тогда отображение $s:(x,y)\to ([y*2^{-d}],-x+2^dy)$ осуществляет соответствующую перестановку.
При $d=0$ это очевидно. При $d=1$ соответствует примеру профессора Снейп (поэтому взял - перед х, хотя от этого кажется не зависит, можно взять любой нечетный множитель перед х). Случай $d>1$ проверяется аналогично.

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

Шота я опять нихрена не понимаю.

Квадратные скобки --- это что, целая часть? Если да, то при $k < d$ элементы $(0,0)$ и $(0,2^k)$ оба переводятся в $(0,0)$.

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

Я в своих попытках решения дошёл примерно вот до чего...

Пусть $A^{\#}$ --- множество гомоморфизмов группы $A$ в мультипликативную группу комплексных чисел. Можно показать, что $A^{\#} \cong A$. Более того, все эти гомоморфизмы образуют базис в $\mathbb{C}^A$. Если выписать вектора этого базиса в ряд, то определитель полученной матрицы $(u_{a,b})$ будет равен $n^{n/2}$, где $n = |A|$.

И нам необходимо (и достаточно) показать, что для некоторой перестановки $s$ определитель

$$ \sum_{\tau \in S_n} \mathrm{sgn}(\tau) \prod_{a \in A} u_{a, \tau(a)} u_{s(a), \tau(a)} $$

не равен нулю.

И вот там если возвести матрицу $U$ в квадрат, получается похожее выражение... сумма по перестановкам, ненулевая, значит одно из слагаемых ненулевое. Но, увы, знаки в половине слагаемых не такие

[Руст]

При перенесении $y$ в поле $x$ мы теряем $y\%2^d$, соответственно во второй части должен был быть именно это $-x+y\%2^d$ а не умножение на $2^d$.

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

Не понимаю, что за проценты...

Руст, не мучайте нас уже! Вы уже пятый раз что-то правите, правите... Либо напишите аккуратное решение, либо признайте, что у Вас его пока нет!

[Руст]

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

Поэтому, попробую дать ответ последний раз:
Любую абелеву группу конечного порядка можно разложить в прямую сумму:

$$A=G+\sum_{i=1}^m Z_{2^{k_i}}, k_1\le k_2\le ...\le k_m.$$

Группа $G$ нечетного порядка. Случаи $m=0,1$ уже доказаны ранее. Достаточно доказать существование перестановки $s$ для группы $A$ в случае $G=\{0\}, m\ge 2,$ такой, что $t(x)=x+s(x)$ так же перестановка. Запишем элемент $x$ в некотором базисе и представим как набор координат $x=(x_1,...,x_m)$, координата $x_i$ определяется по модули $2^{k_i}$.
Достаточно это построить для групп с $m=2,3$. Остальные можно разложить на такие компоненты и перестановки определить покомпонентно.
При $m=2$ для удобства будем обозначать $k_1-k,k_2=k+d, x_1=x, x_2=y$.
Определим $s(x,y)=(y\%2^k,2^dx+[y/2^k])=(z,t)$. Легко вычисляется обратная перестановка $x=[t/2^d], y=z+2^kl, l=t\%2^d$.
Поэтому надо показать, что $t$ так же перестановка. Пусть $t(x,y)=(x+y\%2^k,2^dx+[y/2^k]+y)=(z,t)$. Соответственно надо показать однозначную разрешимость системы уравнений:
$x+y\%2^k=z$
$2^dx+y+[y/2^k]=t$
при любых $z\mod 2^k, t\mod 2^{k+d}.$
Обозначим $y=2^ky_1+y_2, y_1<2^d, y_2<2^k$.
Выражая $x$ из первого уравнения получаем:
$(2^d-1)y_2=2^dz-t-y_1(2^k+1)$.
Пусть $a=\frac{2^k+1}{2^d-1}$ вычисленное по модулю $2^{k+d}$ (это единственное и вычисляемое число). Тогда уравнение сводится к $y_2=2^dz-t-y_1a$. Представим число $2^d-t=2^kz_1+z_2, z_1<2^d, z_2<2^k$ (единственное представление) и $a=2^ka_1+a_2$.
Тогда взяв по модулю $2^k$ определяем $y_2=z_2-y_1*a_2\mod 2^k$ через $y_1$ и поделив на $2^k$ и взяв целую часть
$z_1-y_1a_1+[\frac{z_2-y_1a_2}{2^k}]=0$, откуда однозначно определяется $y_1$ по модулю $2^d$. Что и доказывает существование и единственность решения, т.е. $t$ так же перестановка.

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

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

Что означает запись $y \% 2^k$? Я не знаю этого обозначения

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

Рискну предположить, что $y \% 2^k$ означает остаток от деления $y$ на $2^k$. Но, если так, давайте возьмём $k = 1$, $d = 2$ и посмотрим, что у нас получается.

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

Определим $s(x,y)=(y\%2^k,2^dx+[y/2^k])=(z,t)$.

Поехали!

$$ \begin{array}{c|c|c} a & s(a) & a + s(a) \\ \hline \\ (0,0) & (0,0) & (0,0) \\ (0,1) & (1,0) & (1,1) \\ (0,2) & (0,1) & (0,3) \\ (0,3) & (1,1) & (1,4) \\ (0,4) & (0,2) & (0,6) \\ (0,5) & (1,2) & (1,7) \\ (0,6) & (0,3) & (0,1) \\ (0,7) & (1,3) & (1,2) \\ (1,0) & (0,4) & (1,4) \\ (1,1) & (1,4) & (0,5) \\ (1,2) & (0,5) & (1,7) \\ (1,3) & (1,5) & (0,0) \\ (1,4) & (0,6) & (1,2) \\ (1,5) & (1,6) & (0,3) \\ (1,6) & (0,7) & (1,5) \\ (1,7) & (1,7) & (0,6) \end{array} $$

Что-то непохоже отображение $a \mapsto a + s(a)$ на перестановку

-- Вс мар 27, 2011 16:10:11 --

Либо я про процентики неправильно понял, либо... тут мысль останавливается.

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

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

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

[Руст]

Вы правы, я опять поторопился. Хотя обещал больше не участвовать в постах, открытых вами, закончу обсуждение этой начатой задачи.
С самого начало было ясно (раньше я именно так пытался решить), что отображение надо определить через умножение на 2. При этом, чтобы $t$ так же была перестановкой, лучше взять со знаком минус т.е. $s(x)=-2x+a(x)$, где $a(x)$ нечетный элемемент (возможно равная нулю для нулевого х), причем он служит для различия $s(x+i))$ различающихся на идемпотенту ($i+i=0$). Когда имеется больше одного ненулевого идемпотента, то можно добиться того, что $s(x),t(x)$ были перестановками за счет перестановки идемпотент.
для каждого $x=(x_0,x_1,...,x_m)$ в группе $A=G+\sum_{i=1}^mZ_{2^{k_i}} , i=1,...m$ определим гомоморфизм в группу идемпотентов по формуле $i(x)=(0,2^{k_1-1}[2^{1-k_1}x_1],...,2^{k_m-1}[2^{1-k_m}x_m]).$ Определим так же отображение четности $x\%2=(0,x_1\%2,...,x_m\%2)$ и отображение $A\to B: b(x)=(0,[2^{1-k_1}x_1],...,[2^{1-k_m}x_m])$. Остается определить отображение $s_0$ из группы идемпотентов в множество элементов $B=(0,y_1,...,y_m), y_i=0 \ or \ 1$, так чтобы $s(x)=-2x+s_0(i(x)), t(x)=-x+s_0(i(x))$ были перестановками. На вид проходит $s_0=\pi(b(x))$, где $\pi$ циклическая перестановка. Очевидно, что $s(x)$ перестановка. Для этого $s(x)$ делим на -2, это можно сделать с точностью до идемпотентов, который определяется через $s(x)\%2$. Проверим, что $t(x)$ так же перестановка. Обозначая $t(x)=y$ разрешаем это уравнение относительно х:
$[-\frac x2]=[\frac y2]$,
$-x\%2+\pi(b(x))=y\%2$.
Если опять не ошибаюсь это однозначно разрешает х при любом у. Тем самым решается проблема.

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

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

определим гомоморфизм в группу идемпотентов по формуле $i(x)=(0,2^{k_1-1}[2^{1-k_1}x_1],...,2^{k_m-1}[2^{1-k_m}x_m]).$

Непохоже на гомоморфизм. Если взять $x = (0, 2^{k_1-2}, 0, \ldots, 0)$, то по Вашей формуле получается $i(x) = 0$ и $i(x+x) = (0, 2^{k_1-1}, 0, \ldots, 0) \neq i(x) + i(x)$.

-- Вс мар 27, 2011 18:25:32 --

Вы в этом месте действительно гомоморфизм хотите, или просто отображение, такое, как нарисовали?

[Руст]

Да, это не гомоморфизм, просто отображение. Мне и нужно просто отображение.

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

Поразмыслив, начинаю думать, что нечто во всём этом есть. Но до конца пока, увы, в правильности предложенного решения не уверен

Перескажу предложенное решение на свой манер...

Итак, $A$ у нас абелева группа, не содержащая элементов нечётного порядка и содержащая более одного элемента порядка $2$. В $A$ есть "идемпотентная подгруппа" $I = \{ i \in A : 2i = 0 \}$, не изоморфная $\mathbb{Z}_2$. Фиксируем отображение $i$ из $A$ в $I$, которое инъективно на каждом смежном классе $a + I$, где $a \in A$.

Далее, у нас есть эндоморфизм $\varphi(x) = 2x$ группы $A$ в себя, ядро которого равно $I$. Имеем $A/I \cong \varphi(A)$, откуда $|A| = |I| \cdot |\varphi(A)|$. Следовательно, факторгруппа $A/\varphi(A)$ содержит столько же элементов, сколько их содержится во множестве $I$. Кроме того, каждый элемент фактора $A/\varphi(A)$, будучи умноженным на $2$, даёт ноль, из чего сразу следует $A/\varphi(A) \cong I$. Зафиксируем гомоморфизм $\psi : A \to I$ с ядром $\varphi(A)$. Зафиксируем также множество $B \subseteq A$, содержащее ровно по одному представителю каждого смежного класса $a + \varphi(A)$. Отображение $\psi$ инъективно на $B$. Пусть $\alpha$ --- биекция $I$ на $B$, для которой $\psi \circ \alpha = \mathrm{id}_I$ и $\beta(a) = \alpha(i(a))$.

Теперь полагаем $s(a) = -2a + \beta(a)$ и $t(a) = -a + \beta(a)$.

Отображение $s$ --- перестановка. Действительно, если $-2a_1 + \beta(a_1) = s(a_1) = s(a_2) = -2a_2 + \beta(a_2)$, то $\psi(s(a_1)) = \psi(\beta(a_1)) = \psi(\alpha(i(a_1))) = i(a_1)$, $\psi(s(a_2)) = \psi(\beta(a_2)) = \psi(\alpha(i(a_2))) = i(a_2)$, $i(a_1) = i(a_2)$, $\beta(a_1) = \alpha(i(a_1)) = \alpha(i(a_2)) = \beta(a_2)$, $2a_1 = 2a_2$, $2(a_1-a_2) = 0$, $a_1 - a_2 \in I$ и $a_1 = a_2$.

Это то, что делал Руст, и до этого момента вроде всё понятно. А вот дальше... Утверждается, по сути, что можно выбрать отображение $i$ так, чтобы $t$ тоже оказалось перестановкой (или, что равносильно, домножить $\beta$ на некоторую перестановку множества $B$). А вот так ли оно это?.. Тут ведь в общем случае даже непонятно, как располагаются относительно друг друга подгруппы $I$ и $\varphi(A)$. В общем случае даже включение $I \subseteq \varphi(A)$ не обязано выполняться

-- Вс мар 27, 2011 22:27:49 --

У Руста, по крайней мере, у самого нет уверенности в том, что "циклическая перестановка" $\pi$ даст нужный результат. Надо будет на свежую голову попробовать подобрать $\pi$ для простых случаев $\mathbb{Z}_2 \oplus \mathbb{Z}_8$, $\mathbb{Z}_2 \oplus \mathbb{Z}_4 \oplus \mathbb{Z}_8$ и т. п...