2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 
Сообщение20.03.2011, 18:49 
Заслуженный участник
Аватара пользователя


28/09/05
286
Руст, непонятно, как вы собираетесь подбирать $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}$ решения не имеет.

 Профиль  
                  
 
 Re: Абелевы группы и перестановки
Сообщение20.03.2011, 22:07 
Заслуженный участник


09/02/06
4365
Москва
Обозначим числа $\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$, что дасть полное решение.

 Профиль  
                  
 
 
Сообщение21.03.2011, 00:24 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Абелевы группы и перестановки
Сообщение21.03.2011, 09:09 
Заслуженный участник


09/02/06
4365
Москва
Да, я не правильно обобщал пример профессора Снейп.
Рассмотрю сейчас только случай $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$ проверяется аналогично.

 Профиль  
                  
 
 
Сообщение27.03.2011, 06:41 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Шота я опять нихрена не понимаю.

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

 Профиль  
                  
 
 
Сообщение27.03.2011, 08:53 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Я в своих попытках решения дошёл примерно вот до чего...

Пусть $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$ в квадрат, получается похожее выражение... сумма по перестановкам, ненулевая, значит одно из слагаемых ненулевое. Но, увы, знаки в половине слагаемых не такие :-(

 Профиль  
                  
 
 Re: Абелевы группы и перестановки
Сообщение27.03.2011, 09:54 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение27.03.2011, 10:00 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Не понимаю, что за проценты...

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

 Профиль  
                  
 
 Re: Абелевы группы и перестановки
Сообщение27.03.2011, 11:45 
Заслуженный участник


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

Поэтому, попробую дать ответ последний раз:
Любую абелеву группу конечного порядка можно разложить в прямую сумму:
$$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$ так же перестановка.

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

 Профиль  
                  
 
 
Сообщение27.03.2011, 11:56 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Что означает запись $y \% 2^k$? Я не знаю этого обозначения :oops:

 Профиль  
                  
 
 
Сообщение27.03.2011, 13:03 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Рискну предположить, что $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 писал(а):
Профессор Снейп, вы своими едкими замечаниями в мой адрес добились того, что в дальнейшем я не буду участвовать в задачах и дисскуссиях открытых Вами.

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

 Профиль  
                  
 
 Re: Абелевы группы и перестановки
Сообщение27.03.2011, 15:00 
Заслуженный участник


09/02/06
4365
Москва
Вы правы, я опять поторопился. Хотя обещал больше не участвовать в постах, открытых вами, закончу обсуждение этой начатой задачи.
С самого начало было ясно (раньше я именно так пытался решить), что отображение надо определить через умножение на 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$.
Если опять не ошибаюсь это однозначно разрешает х при любом у. Тем самым решается проблема.

 Профиль  
                  
 
 
Сообщение27.03.2011, 15:21 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Руст в сообщении #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 --

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

 Профиль  
                  
 
 Re: Абелевы группы и перестановки
Сообщение27.03.2011, 16:38 
Заслуженный участник


09/02/06
4365
Москва
Да, это не гомоморфизм, просто отображение. Мне и нужно просто отображение.

 Профиль  
                  
 
 
Сообщение27.03.2011, 19:20 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Поразмыслив, начинаю думать, что нечто во всём этом есть. Но до конца пока, увы, в правильности предложенного решения не уверен :oops:

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

Итак, $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)$ не обязано выполняться :cry:

-- Вс мар 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$ и т. п...

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 51 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group