Породить все элементы конечной абел.группы попарными суммами

[Eldar]

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

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

[ИСН]

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

[Eldar]

Да, таким образом можно оценить, но это тривиальная оценка.
$\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$.

[ИСН]

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

[mihiv]

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

[Eldar]

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

[mihiv]

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$ Это близко к нижней оценке.