Skip to main content
2 of 4
added 55 characters in body

Adding $n$-tuples over groups

Consider a finite group $\mathcal{G}$. Let $S_0$ be a $n$-tuple of elements of $\mathcal{G}$, and let $S_i$ be the cyclically shifted version of $S_0$ by $i$ indices to the right. So for example if $\mathcal{G}$ = $\text{GF}(2)$, $n = 3$, and $S_0 = (1,0,0)$, then $S_2 = (0,0,1)$.

Now let $\mathcal{S} = \{S_i : 0 \leq i \leq n-1\}$. One can add two $n$-tuples in $\mathcal{S}$ by adding the elements over the group $\mathcal{G}$. So in the above example, $S_0 + S_2 = (1,0,1)$.

The basic question is this: Pick any $g \in \mathcal{G}$. I want to choose a subset $\mathcal{H} \subseteq \mathcal{S}$ so that the number of times the element $g$ appears in the tuple $\sum_{h \in \mathcal{H}} h$ (let's call this the $g$-count) is maximum. I'm not really interested right now in the subset itself, but really in the maximum $g$-count.

Does anybody know what kind of results are known about this problem in general? Or what kind of techniques do you suspect are needed to tackle this problem? I'd also be interested if any special cases are known.