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

Improve this question
$\endgroup$
7
  • $\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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 6:26

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.