2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
01/01/18 20:50 UTC: Перешли на HTTPS в тестовом режиме. О проблемах пишите в ЛС cepesh.



Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Породить все элементы конечной абел.группы попарными суммами
Сообщение24.02.2015, 10:10 


28/12/10
23
Какое минимальное число элементов конечой абелевой группы нужно взять, чтобы попарными суммами (именно суммами двух элементов из множества, которое мы набираем) породить все элементы поля?

Или может кто подскажет где и что можно почитать по этому поводу.

 Профиль  
                  
 
 Re: Породить все элементы конечной абел.группы попарными суммами
Сообщение24.02.2015, 14:51 
Заслуженный участник
Аватара пользователя


18/05/06
13176
с Территории
Допустим, Вы взяли $n$ элементов; сколько из них можно собрать разных попарных сумм?

 Профиль  
                  
 
 Re: Породить все элементы конечной абел.группы попарными суммами
Сообщение25.02.2015, 12:24 


28/12/10
23
Да, таким образом можно оценить, но это тривиальная оценка.
$\binom{n}{2} + 1$ различных сумм там будет. $+1$ потому, что мы можем сложить 2 одинаковых с целью получения нуля.
Для конкретики, тут рассматривается группа двоичных векторов и сложением является обычный XOR (поэтому складывая два одинаковых мы получаем 0-вектор). И по теореме о том, что всякая коммутативная конечная группа может быть представлена как прямая сумма p-групп, эта группа, пусть она обозначается $\mathbb{Z}_2^n$, (тут $n$ другое, не то что в начале сообщения) представляется в виде прямой суммы $n$ групп $\mathbb{Z}_2$.
На языке групп вопрос звучит следующим образом:

Есть конечная абелева группа $<\mathbb{Z}_2^n,+>$ Выбирается подмножество $M\subseteq\mathbb{Z}_2^n$, такое что $\mathbb{Z}_2^n = M + M$, где + это теперь теоретикомножественное сложение, а сложение элементов берётся из группы ($A+B = \{a+b: a\in A, b\in B\}$). Вопрос: какова оценка снизу на мощность множества $M$.

 Профиль  
                  
 
 Re: Породить все элементы конечной абел.группы попарными суммами
Сообщение25.02.2015, 12:51 
Заслуженный участник
Аватара пользователя


18/05/06
13176
с Территории
Ну, знаете... Понятия $\mathbb{Z}_2^n$ и "конечная абелева группа" соотносятся примерно как "Хосе Доротео Аранго Арамбула" и "какой-то человек". В общем случае тривиальная оценка неулучшаема, потому что кое-когда является точной. А в конкретно Вашем - не знаю, думать надо.

 Профиль  
                  
 
 Re: Породить все элементы конечной абел.группы попарными суммами
Сообщение25.02.2015, 22:04 
Заслуженный участник


03/01/09
1182
москва
Для группы $\mathbb Z^n_2$ достаточно взять $2^{\frac n2+1}$ элементов(для четного $n$). С другой стороны простая оценка снизу дает $|M|>2^{\frac {n+1}2}-1$.

 Профиль  
                  
 
 Re: Породить все элементы конечной абел.группы попарными суммами
Сообщение26.02.2015, 13:42 


28/12/10
23
Я бы сказал что простая оценка снизу ($\binom{k}{2}+1\geq 2^n$) даёт $k=|M| > 2^{\frac{n+1}{2}}$, т.е. без $ - 1$.
Исходя из каких предположений получено, что для группы $\mathbb{Z}_2^n$ достаточно взять $2^\frac{n}{2}+1$?

 Профиль  
                  
 
 Re: Породить все элементы конечной абел.группы попарными суммами
Сообщение26.02.2015, 17:42 
Заслуженный участник


03/01/09
1182
москва
Eldar в сообщении #982840 писал(а):
Исходя из каких предположений получено, что для группы $\mathbb{Z}_2^n$ достаточно взять $2^\frac{n}{2}+1$?

Покажем это на примере $n=4$. Каждый элемент группы можно представить в виде суммы элементов вида: $(a,b,0,0)$ и $(0,0,c,d)$. Но всего имеется $2^{\frac n2}$ элементов каждого из этих двух видов, так что всего получим $2\cdot 2^{\frac n2}$ элементов, кроме того, элемент $(0,0,0,0)$ в выбранное множество элементов включать не нужно, поэтому из полученного числа элементов вычитаем 2. Окончательно $|M|=2^{\frac n2+1}-2$ для четного $n$. Аналогично получим $|M|=2^{\frac {n-1}2}+2^{\frac {n+1}2}-2$ для нечетного $n$ Это близко к нижней оценке.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

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



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

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


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

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