6
$\begingroup$

Let $G$ be a finite group. We say a subset $A$ of $G$, $|A|=m$, is $(m,i)$-good, $m\geq 1$ and $0\leq i\leq m$, if there exist $g_A\in G$ such that we have $|gA\cap A|=m-i$.

I need some groups such that, for fixed $m$ and $i$, preferably $i$ is much smaller than $m$, the number of $(m, i)$-good subsets is large.

Is this property well known in group theory? Or, is it related to some well-known properties of groups for special values $m$ and $i$?

$\textbf{The motivation for this question:}$ These type of subsets are used to define some special type of participants in secret sharing schemes on groups. Participants are the members of group and subsets with this property can take some special values of share to construct the key.

I do not know how can I upload a large file here. You can download the text file from this address. If it is helpful, I can do this computation for each order of groups.

$\textbf{Addendum 1}:$ http://s8.picofile.com/file/8341377742/Order_8.txt.html

$\textbf{Addendum 2}:$ http://s9.picofile.com/file/8341380550/Order_9.txt.html

$\textbf{Addendum 3}:$ http://s9.picofile.com/file/8341379792/Order_12.txt.html

$\textbf{New question (10/2018)}:$ Is it true that if the $(m,i)$-good numbers of two groups $G$ and $H$ are equal, then $G$ is isomorphic to $H$?

Thanks for helpful answers, references, and comments.

$\endgroup$
11
  • $\begingroup$ I assume that $m$ is the cardinality of $A$? $\endgroup$ Oct 29, 2018 at 14:06
  • 1
    $\begingroup$ Maybe you should provide a little more context, so that one can grasp an idea what you want, as the question is very open-ended so far. For instance, are you happy with cyclic groups of prime order? $\endgroup$
    – YCor
    Oct 29, 2018 at 14:50
  • $\begingroup$ @YCor: actually for a given number $n$, I am interested in the group of order $n$ which has the possible maximum number of such subsets. $\endgroup$
    – Shahrooz
    Oct 29, 2018 at 17:23
  • $\begingroup$ @Stefan Kohl: the group is finite. $\endgroup$
    – Shahrooz
    Oct 29, 2018 at 17:24
  • $\begingroup$ OK, but I was asking for context, that is, what you already checked... what values are easy to achieve, what values you'd like to achieve, etc. $\endgroup$
    – YCor
    Oct 29, 2018 at 17:30

1 Answer 1

2
$\begingroup$

Any $m$-set is an $(m,0)$-set with $g$ the identity. It is easier to count the number of pairs $(g,S)$ where $S$ is $(m,i)-$good for that particular $g.$ If $g$ has order $2$ and $|G|=n=2t$ then, using that $g$, there are $\binom{t}k$ sets that are $(2k,0)$ and $\binom{t}k\binom{t-k}i2^i$ which are $(2k+i,i). $ An elementary abelian $2$ group has all non-identity elements of order $2$. Of course the same set could be $(m,i)$ for more than one $g$ but that might not be that big a consideration.

It doesn't really matter if the group is abelian. For $g$ of order $j,$ the exact counts using that $g$, are sums of terms each the product of a multinomial coefficient and some powers of constants which are counts for a cyclic group of order $j$.

For $C_s$ and a given generator $g$ consider the $2^s-1$ non-empty subsets and let $c_{m',i'}$ be the number that are $(m',i')-$good for that $g.$

Then if $G$ is a group of order $n=st$ and $g$ is an element of order $s$ then from the $t$ right cosets of $<g>$ $n_{(m',i')}$ of each type. The result will be $(m,i)-$ good (for that $g$) for $m=\sum n_{(m',i')}m'$ and $i=\sum n_{(m',i')}i'.$ Sum over all the possibilities to get the total count of $(m,i)$ sets for that $g$. The number of ways to do this is a multinomial coefficient.

To count $(m,i)-$good sets with a distinguished $g$ do the above for every combination giving the desired $(m,i)$

In theory, do the above for each element of $G$ then somehow account for sets with multiple possible $g$.

$\endgroup$
5
  • $\begingroup$ Thanks for your answer. Do you have any idea for odd case? Actually, I did some computation where I will add them here soon. $\endgroup$
    – Shahrooz
    Oct 30, 2018 at 20:58
  • $\begingroup$ @ShahroozJanbaz do you mean like order $3$ instead of $2?$ $\endgroup$ Oct 31, 2018 at 13:28
  • $\begingroup$ I mean the order of the group $G$ is odd. Also, for the case where $|G|=16$, the group $C_2\times C_2 \times C_2 \times C_2$ has $12000$ $(8,2)$-good sets, which is the maximum possible among all groups. By your estimation in this case, we obtain much less number of such sets. $\endgroup$
    – Shahrooz
    Oct 31, 2018 at 13:43
  • $\begingroup$ And for $(9,2)$-good sets, the group $Q_{16}$ has the maximum possible such sets which is equal to $2688$ $\endgroup$
    – Shahrooz
    Oct 31, 2018 at 13:53
  • $\begingroup$ @ShahroozJanbaz My claim was that each of the $15$ order $2$ elements is the $g$ for exactly $\binom{8}{3}\binom522^2=2240$ different $(8,2)-$good sets. So that is an upper bound of $33600.$ Some might be good for $6$ or more distinct $g$. $\endgroup$ Oct 31, 2018 at 19:32

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.