1
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ Is $\mathcal {G} $ abelian? $\endgroup$ Feb 28, 2020 at 6:03
  • $\begingroup$ @JeremyRickard Yes, in the case I'm interested in $\mathcal{G}$ is abelian. $\endgroup$ Feb 28, 2020 at 6:49
  • 2
    $\begingroup$ You should probably add that to the question, then. If $\mathcal{G} $ is not abelian, then it's not clear what $\sum_{h\in\mathcal{H}}h $ means. $\endgroup$ Feb 28, 2020 at 8:27
  • 1
    $\begingroup$ @JeremyRickard edited the question. Thanks! $\endgroup$ Feb 28, 2020 at 16:44

1 Answer 1

1
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ 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$. I have added a comment to the question, in case it helps. $\endgroup$ Feb 29, 2020 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.