Timeline for Large product-1-free sets in finite groups
Current License: CC BY-SA 4.0
37 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 22, 2021 at 7:20 | history | edited | Taras Banakh | CC BY-SA 4.0 |
Added 7th remark.
|
| Jul 21, 2021 at 19:33 | history | edited | Taras Banakh | CC BY-SA 4.0 |
Added a link to the book of Erdos and Graham.
|
| Jul 21, 2021 at 18:33 | history | edited | Taras Banakh | CC BY-SA 4.0 |
added 254 characters in body
|
| Jul 21, 2021 at 18:21 | history | edited | Taras Banakh | CC BY-SA 4.0 |
deleted 203 characters in body
|
| Jul 21, 2021 at 18:10 | history | edited | Taras Banakh | CC BY-SA 4.0 |
Aded the result of Balandraud.
|
| Jul 21, 2021 at 17:56 | history | edited | Taras Banakh | CC BY-SA 4.0 |
Added known results on upper bounds
|
| Jul 20, 2021 at 15:51 | history | edited | Taras Banakh | CC BY-SA 4.0 |
edited body
|
| Jul 12, 2021 at 2:06 | history | edited | Taras Banakh | CC BY-SA 4.0 |
corrected 47 to 48.
|
| Jul 10, 2021 at 8:48 | vote | accept | Taras Banakh | ||
| Jul 8, 2021 at 8:25 | history | edited | Taras Banakh | CC BY-SA 4.0 |
edited body
|
| Jul 8, 2021 at 8:07 | answer | added | Taras Banakh | timeline score: 2 | |
| Jul 7, 2021 at 12:36 | answer | added | Nick Gill | timeline score: 4 | |
| Jul 7, 2021 at 8:17 | comment | added | Nick Gill | If one removed the "distinct elements" part of the condition, then the Product Theorem (to which @YCor alludes) would imply, I think, that for $G$ non-abelian simple we have $f_1(G)< \exp(C\sqrt{\log|G|})$ for some absolute $C$. The value of $C$ for, say, ${\rm PSL}_2(p)$ can be deduced from work of Kowalski. This is a bit stronger than your proposed upper bound but of course the condition is a bit stronger too. Anyway, thought it was worth mentioning. | |
| Jul 6, 2021 at 20:33 | history | edited | Taras Banakh | CC BY-SA 4.0 |
Added a Remark.
|
| Jul 6, 2021 at 20:30 | comment | added | Taras Banakh | @NickGill In fact, there is a small problem with the proof of the lower bound $2^{f_1(G)}\ge |G|$ for Abelian groups by the greedy algorithm. Indeed, we should choose the next $x$, not equal to the inverses of all possible products of elements of a constructed set, but this $x$ should be also outside of the set. So, the greedy algorithm yields a weaker lower bound: $f_1(G)+2^{f_1(G)}\ge |G|$. For non-commutative groups this algorithm yields the lower bound $f_1(G)+e\cdot f_1(G)!\ge |G|$. | |
| Jul 6, 2021 at 19:00 | comment | added | Taras Banakh | @YCor To some my surprise, my GAP-program computed (rather quickly) $f_1(A5)=6$ with many witnesses, in particular: [ (3,4,5), (2,3)(4,5), (2,3,5), (2,5)(3,4), (1,2,3), (1,4,5) ]. But $6=\lfloor \log_2(|A5|)\rfloor$, so this is not a counterexample to the lower bound $f_1(G)\ge\lfloor\log_2(|G|)\rfloor$. | |
| Jul 6, 2021 at 18:00 | history | edited | Taras Banakh | CC BY-SA 4.0 |
Removed the table to a partial answer.
|
| Jul 6, 2021 at 17:58 | answer | added | Taras Banakh | timeline score: 0 | |
| Jul 6, 2021 at 13:28 | history | edited | Taras Banakh | CC BY-SA 4.0 |
added 527 characters in body
|
| Jul 6, 2021 at 9:59 | comment | added | Nick Gill | ok, I thought you would know this already but anyway... | |
| Jul 6, 2021 at 9:55 | comment | added | Taras Banakh | @NickGill Yes, of course! The problem is to prove the same lower bound (which is actually very low) for non-abelian groups. By a greedy argument it is possible to prove something like $f_1(G)>log_2(|G|)/log_2(log_2(|G|))$. | |
| Jul 6, 2021 at 9:51 | comment | added | Nick Gill | The lower bound holds when $G$ is abelian just by a greedy algorithm: Given a product 1-free-set of size $k-1$, the set of all products is size at most $2^{k-1}$ and you add another element that is not equal to the inverse of any of these products. You can do this so long as $|G|>2^{k-1}$. You'll end up with a set of size $k$ where $2^k\geq |G|$. | |
| Jul 6, 2021 at 8:55 | history | edited | Taras Banakh | CC BY-SA 4.0 |
added 30 characters in body
|
| Jul 6, 2021 at 8:23 | history | edited | Taras Banakh | CC BY-SA 4.0 |
added 80 characters in body
|
| Jul 6, 2021 at 6:22 | history | edited | Taras Banakh | CC BY-SA 4.0 |
added 462 characters in body
|
| Jul 6, 2021 at 5:20 | history | edited | Taras Banakh | CC BY-SA 4.0 |
added 5 characters in body
|
| Jul 6, 2021 at 4:55 | history | edited | Taras Banakh | CC BY-SA 4.0 |
added 102 characters in body
|
| Jul 5, 2021 at 22:42 | history | edited | Taras Banakh | CC BY-SA 4.0 |
added 1882 characters in body
|
| Jul 5, 2021 at 22:12 | history | edited | Taras Banakh | CC BY-SA 4.0 |
added 14 characters in body
|
| Jul 5, 2021 at 21:42 | history | edited | Taras Banakh | CC BY-SA 4.0 |
added 64 characters in body
|
| Jul 5, 2021 at 21:34 | comment | added | Taras Banakh | @YCor This lower bound does not hold for Boolean groups: in this case $f_1(G)=log_2(|G|)$ is the dimension of $G$ as a linear space over the 2-element field. The difference between $log_2(|G|)$ and $\lfloor\sqrt{|G|}\rfloor$ is not visible for small Boolean groups. | |
| Jul 5, 2021 at 21:27 | history | edited | Taras Banakh | CC BY-SA 4.0 |
added 10 characters in body
|
| Jul 5, 2021 at 21:15 | comment | added | Taras Banakh | @YCor No. I just compute $f_1(SmallGroup(n,k))$ in increasing order. Now the computer struggles with groups of cardinality 32, more precisely with the SmallGroup(32,45)=C4 x C2^3. This group has large automorphism group, so my algorithm (which optimizes the search) runs slowly for such groups. Certainly my algorithm will not be able to calclulate $f_1(Alt_5)$. So, something less computational should be invented. | |
| Jul 5, 2021 at 21:11 | comment | added | YCor | I may be wrong, but I think known expansion results for finite simple groups imply that for all but finitely many nonabelian finite simple groups $G$ and $A\subset G$ with $|A|\ge \sqrt{|G|}-1$ we have $AAA=G$. This suggests that very few such $G$ satisfy the proposed inequality. | |
| Jul 5, 2021 at 21:02 | comment | added | YCor | Have you computed $f_1(\mathrm{Alt}_5)$? | |
| Jul 5, 2021 at 20:57 | history | edited | YCor | CC BY-SA 4.0 |
edited tags, formatting
|
| Jul 5, 2021 at 20:54 | history | asked | Taras Banakh | CC BY-SA 4.0 |