6
$\begingroup$

What is the minimum size of the group containing a subset of elements $S = \{s_1,\dots,s_k\}$ satisfying the following property: There is no $i,t \in \{1,\dots,k\}$ such that $s_i^t = b_1\cdot b_2\cdot \dots \cdot b_t$ where $b_1,\dots,b_t \in S$ and not all $b_j$ are $s_i$.

There is a group of size $O(k^5)$ satisfying the property above. Can we improve this bound to $O(k)$ or $O(k^2)$?


Just an alternative formulation (from Włodzimierz Holsztyński):

Let $\ S\ $ be a subset of an arbitrary finite group $\ G.\ $ An arbitrary element $\ g\in S\ $ is called a geometric mean within $\ S$ $$ \Leftarrow:\Rightarrow\quad\exists_{n\leq |S|}\exists_{x_1\ldots x_n\in S}\ \left(g^n=\prod_{t=1}^n x_t\ \ \&\ \ \{x_1\ \ldots x_n\}\ne \{g\} \right) $$ This question is about the minimal possible $\ g(k)=|G|\ $ such that there is $\ S\subseteq G\ $ which has no geometric mean within $\ S,\ $ and $\ |S|=k.$

$\endgroup$
  • $\begingroup$ I found the original formulation more clear and I'm not sure that a post should be edited so thoroughly without its author's agreement, unless the question is really unclear (here I only found the reformulation unclear, no quantifier over $n$...). $\endgroup$ – YCor Oct 27 '16 at 4:33
  • $\begingroup$ It goes without saying that the original author is welcome to remove my version. $\endgroup$ – Włodzimierz Holsztyński Oct 27 '16 at 4:47
  • 1
    $\begingroup$ What's an example of size $O(k^5)$? Also, is the smallest size of an abelian group with these conditions known? $\endgroup$ – YCor Oct 27 '16 at 5:00
  • 2
    $\begingroup$ Consider a group with element set $\{(a,b) \mid 0 \leq a \leq 2k^2 - 1, 0 \leq b \leq 2k^3 - 1\}$ and group operation defined as $(a,b)\cdot (c,d) = (a+b \mod 2k^2,c+d\mod 2k^3)$. Set $S = \{(i,i^2) \mid i \in \{1,\dots,k\}\}$ satisfies the property above. $\endgroup$ – Vivek Madan Oct 27 '16 at 5:18
  • 1
    $\begingroup$ Slight modification needed I guess: $n$ needs to be bounded. Else, for all $s_i,s_j \in S$, there will exists a $n = lcm(order(s_i),order(s_j))$ such that $s_i^n = s_j^n$. $\endgroup$ – Vivek Madan Oct 27 '16 at 6:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.