Adding $n$-tuples over groups

Question

Consider a finite abelian 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.

Edit: In view of the answer below, I'd like to mention that a special case that I'm interested in is when $\mathcal{G} = \mathbb{F}_4$, with the group operation being addition in $\mathbb{F}_4$.

Answer 1

It might help to know more about which cases interest you.

Here is an NP complete problem:

given a set of integers which add to $2N$ , decide if there is a subset which adds to $N.$

This translates into deciding for your question if the $g=N$-count for a certain vector over $\mathbb{Z}_{2N}$ is positive or $0.$

Over $G=\mathbb{Z}_2$ the only cases are $g=0$ and $g=1.$ The length $n$ all $0$ vector arises from taking $\mathcal{S}=\emptyset.$ Adding all the vectors in $\mathcal{S}$ gives a constant vector. All $1$'s if $S_0$ has an odd number of $1$'s and all $0$ otherwise. Just to make it more interesting one might require that $\sum_{h \in \mathcal{H}} h$ is not a constant vector.

The triple $(1,1,0)$ gives only even weight words so the length $24$ tuple $(1,1,0,1,1,0,\cdots$ only gives $4$ distinct sums $\sum_{h \in \mathcal{H}} h$ and the non-zero ones all have $16$ $1$'s.

Over $\mathbb{Z}_2$ the possible tuples $\sum_{h \in \mathcal{H}} h$ constitute a linear subspace of $\mathbb{Z_2}^n.$ This is a cylic binary code and the question of the weight enumerator polynomial is well studied. There is a binary Golay code where the tuples have length $24$ and each one which isn't constant has $8,12$ or $16.$ This is no better numerically than the relatively trivial construction above, but more impressive.

Over $\mathbb{Z}_p$ for a larger $p$ we would get a linear code by taking sums $\sum_{h \in \mathcal{H}} c_h h$ with coefficients $c_h \in \mathbb{Z}_p.$ but sticking to $\sum_{h \in \mathcal{H}} h$ gives a subset of this code. There is a ternary Golay code over $\mathbb{Z}_3$ with $n=12$ where no one of $0,1,2$ can show up more than $6$ times in a non-constant tuple.

In summary:

• Whatever $S_0$ is, there is at least one $g'$ so that the $g'$-count is can be $n$. This is the sum of the entries of $S_0.$
• Then the highest $g$ count is also the highest $g'-g$ count, use complementary sets $H$ and $\mathcal{S}-H.$
• $g=0$ can always be obtained $n$ times by the empty sum.
• We may assume that the entries of $S_0$ generate the entire group, since otherwise we can just use a smaller group.
• It is worth looking at the theory of cyclic linear codes.
• To see how small the number could be, consider well known codes.

In the particular case of $\mathbb{Z}_4$ this suggests:

• Treat separately the nine cases of $g=0$, $g=2$ and $g=1,3$ and and $g'=0$,$g'=2$, $g'=1,3.$
• Check Preperata, Kerdock and other interesting $\mathbb{Z}_4$ codes.