Factorizable groups
Definition. A finite group $G$ is factorizable if for any positive integer numbers $a,b$ with $ab=|G|$ there are subsets $A,Bsubset G$ of cardinality $|A|=a$ and $|B|=b$ such that $AB=G$.
Problem 1. Is each finite group factorizable?
As I understood from these MO-posts (1, 2, 3), this problem is wide open and there is no intuition if it is true or not. So, we can ask a related
Problem 2. Which finite groups are factorizable?
The class of factorizable groups has a nice 3-space property that can be formulated in terms of bifactorizable subgroups.
A subgroup $H$ of a group $G$ is called bifactorizable if $H$ is factorizable and for any positive integer numbers $a,b$ with $ab=|G|$ there are sets $A,Bsubset G$ such that $AHB=G$, $|A|cdot |H|cdot |B|=|G|$, $|A|$ divides $a$ and $|B|$ divides $b$.
Theorem. A finite group $G$ is factorizable if $G$ contains a bifactorizable subgroup $H$.
Proof. Given positive integers $a,b$ with $ab=|G|$ use the bifactorizability of $H$ to find subsets $A_1,B_1subset G$ such that $AHB=G$, $|A_1|cdot |H|cdot |B_1|=|G|$, $|A_1|$ divides $a$, and $B_1$ divides $b$. The factorizability of $H$ yields two sets $A_2,B_2subset H$ of cardinality $|A_2|=a/|A_1|$ and $|B_2|=b/|B_1|$ such that $A_2B_2=H$. Then the sets $A=A_1A_2$ and $B=B_2B_1$ have cardinality $|A|le a$, $|B|le b$ and
$AB=A_1A_2B_2B_1=A_1HB_1=G$. It follows from $ab=|G|=|A|cdot|B|le ab$ that $|A|=a$ and $|B|=b$. $square$
It is easy to see that a subgroup $H$ of a group $G$ is bifactorizable if it is factorizable and has prime index in $G$. Moreover, as was observed by M.Farrokhi D.G. in his answer to this post, a subgroup $H$ of a group $G$ is bifactorizable if $H$ is factorizable and the index of $H$ in $G$ is a prime power $p^k$ such that $p^{2k-1}$ divides $|G|$.
A normal subgroup $H$ of a group $G$ is factorizable if both groups $H$ and $G/H$ are factorizable. This implies
Corollary. A finite group $G$ is factorizable if $G$ contains a bifactorizable subgroup $H$ with factorizable quotient $G/H$.
This corollary reduces Problems 1,2 to studying the factorizability of finite simple groups. According to the classification of finite simple groups, each finite simple group is either cyclic of prime order, or alternating, or belongs to 16 families of groups of Lie type or is one of 27 sporadic groups.
Among these families only the factorizability of finite cyclic groups is trivially true.
Problem 3. Is each alternating group $A_n$ factorizable?
It may happen that the argument of Ilya Bogdanov from his answer to this MO-problem can be helpful here. On the other hand, it can be shown that the subgroup $A_n$ is bifactorizable in $A_{n+1}$ if and only if $A_n$ is factorizable and $nne 3$ is a power of a prime. It follows from the answer to this MO-question that the subgroup $A_3$ is not bifactorizable in $A_4$.
Problem 4. Is any hope to prove that some infinite family of simple groups of Lie type consists of factorizable groups?
gr.group-theory finite-groups additive-combinatorics
|
show 2 more comments
Definition. A finite group $G$ is factorizable if for any positive integer numbers $a,b$ with $ab=|G|$ there are subsets $A,Bsubset G$ of cardinality $|A|=a$ and $|B|=b$ such that $AB=G$.
Problem 1. Is each finite group factorizable?
As I understood from these MO-posts (1, 2, 3), this problem is wide open and there is no intuition if it is true or not. So, we can ask a related
Problem 2. Which finite groups are factorizable?
The class of factorizable groups has a nice 3-space property that can be formulated in terms of bifactorizable subgroups.
A subgroup $H$ of a group $G$ is called bifactorizable if $H$ is factorizable and for any positive integer numbers $a,b$ with $ab=|G|$ there are sets $A,Bsubset G$ such that $AHB=G$, $|A|cdot |H|cdot |B|=|G|$, $|A|$ divides $a$ and $|B|$ divides $b$.
Theorem. A finite group $G$ is factorizable if $G$ contains a bifactorizable subgroup $H$.
Proof. Given positive integers $a,b$ with $ab=|G|$ use the bifactorizability of $H$ to find subsets $A_1,B_1subset G$ such that $AHB=G$, $|A_1|cdot |H|cdot |B_1|=|G|$, $|A_1|$ divides $a$, and $B_1$ divides $b$. The factorizability of $H$ yields two sets $A_2,B_2subset H$ of cardinality $|A_2|=a/|A_1|$ and $|B_2|=b/|B_1|$ such that $A_2B_2=H$. Then the sets $A=A_1A_2$ and $B=B_2B_1$ have cardinality $|A|le a$, $|B|le b$ and
$AB=A_1A_2B_2B_1=A_1HB_1=G$. It follows from $ab=|G|=|A|cdot|B|le ab$ that $|A|=a$ and $|B|=b$. $square$
It is easy to see that a subgroup $H$ of a group $G$ is bifactorizable if it is factorizable and has prime index in $G$. Moreover, as was observed by M.Farrokhi D.G. in his answer to this post, a subgroup $H$ of a group $G$ is bifactorizable if $H$ is factorizable and the index of $H$ in $G$ is a prime power $p^k$ such that $p^{2k-1}$ divides $|G|$.
A normal subgroup $H$ of a group $G$ is factorizable if both groups $H$ and $G/H$ are factorizable. This implies
Corollary. A finite group $G$ is factorizable if $G$ contains a bifactorizable subgroup $H$ with factorizable quotient $G/H$.
This corollary reduces Problems 1,2 to studying the factorizability of finite simple groups. According to the classification of finite simple groups, each finite simple group is either cyclic of prime order, or alternating, or belongs to 16 families of groups of Lie type or is one of 27 sporadic groups.
Among these families only the factorizability of finite cyclic groups is trivially true.
Problem 3. Is each alternating group $A_n$ factorizable?
It may happen that the argument of Ilya Bogdanov from his answer to this MO-problem can be helpful here. On the other hand, it can be shown that the subgroup $A_n$ is bifactorizable in $A_{n+1}$ if and only if $A_n$ is factorizable and $nne 3$ is a power of a prime. It follows from the answer to this MO-question that the subgroup $A_3$ is not bifactorizable in $A_4$.
Problem 4. Is any hope to prove that some infinite family of simple groups of Lie type consists of factorizable groups?
gr.group-theory finite-groups additive-combinatorics
Amazing to me that this seemingly basic problem in the theory of finite groups is apparently open.
– Sam Hopkins
Nov 26 at 16:01
@SamHopkins I am not expert in Group Theory. I admit that this problem has an answer, known to specialists, see the answer of M.Farrokhi D.G.
– Taras Banakh
Nov 26 at 16:12
I would guess that if the answer to the question is yes, then it might be possible to prove it, given that the problem has been reduced to the case of finite simple groups, about which a lot is known. But if the answer to the question is no, then it could be very hard to prove because you have so many subsets to consider!
– Derek Holt
Nov 26 at 19:21
@DerekHolt Exactly this reduction to the case of finite simple groups follows from Corollary. For a negative answer maybe it will be easier to construct a counterexample to this related question: mathoverflow.net/questions/316262/…
– Taras Banakh
Nov 26 at 19:33
1
You might be interested in googling the keyword "minimal logarithmic signature" for a related problem which has come under some scrutiny in cryptography and on which some progress has been made.
– Gro-Tsen
Nov 28 at 18:13
|
show 2 more comments
Definition. A finite group $G$ is factorizable if for any positive integer numbers $a,b$ with $ab=|G|$ there are subsets $A,Bsubset G$ of cardinality $|A|=a$ and $|B|=b$ such that $AB=G$.
Problem 1. Is each finite group factorizable?
As I understood from these MO-posts (1, 2, 3), this problem is wide open and there is no intuition if it is true or not. So, we can ask a related
Problem 2. Which finite groups are factorizable?
The class of factorizable groups has a nice 3-space property that can be formulated in terms of bifactorizable subgroups.
A subgroup $H$ of a group $G$ is called bifactorizable if $H$ is factorizable and for any positive integer numbers $a,b$ with $ab=|G|$ there are sets $A,Bsubset G$ such that $AHB=G$, $|A|cdot |H|cdot |B|=|G|$, $|A|$ divides $a$ and $|B|$ divides $b$.
Theorem. A finite group $G$ is factorizable if $G$ contains a bifactorizable subgroup $H$.
Proof. Given positive integers $a,b$ with $ab=|G|$ use the bifactorizability of $H$ to find subsets $A_1,B_1subset G$ such that $AHB=G$, $|A_1|cdot |H|cdot |B_1|=|G|$, $|A_1|$ divides $a$, and $B_1$ divides $b$. The factorizability of $H$ yields two sets $A_2,B_2subset H$ of cardinality $|A_2|=a/|A_1|$ and $|B_2|=b/|B_1|$ such that $A_2B_2=H$. Then the sets $A=A_1A_2$ and $B=B_2B_1$ have cardinality $|A|le a$, $|B|le b$ and
$AB=A_1A_2B_2B_1=A_1HB_1=G$. It follows from $ab=|G|=|A|cdot|B|le ab$ that $|A|=a$ and $|B|=b$. $square$
It is easy to see that a subgroup $H$ of a group $G$ is bifactorizable if it is factorizable and has prime index in $G$. Moreover, as was observed by M.Farrokhi D.G. in his answer to this post, a subgroup $H$ of a group $G$ is bifactorizable if $H$ is factorizable and the index of $H$ in $G$ is a prime power $p^k$ such that $p^{2k-1}$ divides $|G|$.
A normal subgroup $H$ of a group $G$ is factorizable if both groups $H$ and $G/H$ are factorizable. This implies
Corollary. A finite group $G$ is factorizable if $G$ contains a bifactorizable subgroup $H$ with factorizable quotient $G/H$.
This corollary reduces Problems 1,2 to studying the factorizability of finite simple groups. According to the classification of finite simple groups, each finite simple group is either cyclic of prime order, or alternating, or belongs to 16 families of groups of Lie type or is one of 27 sporadic groups.
Among these families only the factorizability of finite cyclic groups is trivially true.
Problem 3. Is each alternating group $A_n$ factorizable?
It may happen that the argument of Ilya Bogdanov from his answer to this MO-problem can be helpful here. On the other hand, it can be shown that the subgroup $A_n$ is bifactorizable in $A_{n+1}$ if and only if $A_n$ is factorizable and $nne 3$ is a power of a prime. It follows from the answer to this MO-question that the subgroup $A_3$ is not bifactorizable in $A_4$.
Problem 4. Is any hope to prove that some infinite family of simple groups of Lie type consists of factorizable groups?
gr.group-theory finite-groups additive-combinatorics
Definition. A finite group $G$ is factorizable if for any positive integer numbers $a,b$ with $ab=|G|$ there are subsets $A,Bsubset G$ of cardinality $|A|=a$ and $|B|=b$ such that $AB=G$.
Problem 1. Is each finite group factorizable?
As I understood from these MO-posts (1, 2, 3), this problem is wide open and there is no intuition if it is true or not. So, we can ask a related
Problem 2. Which finite groups are factorizable?
The class of factorizable groups has a nice 3-space property that can be formulated in terms of bifactorizable subgroups.
A subgroup $H$ of a group $G$ is called bifactorizable if $H$ is factorizable and for any positive integer numbers $a,b$ with $ab=|G|$ there are sets $A,Bsubset G$ such that $AHB=G$, $|A|cdot |H|cdot |B|=|G|$, $|A|$ divides $a$ and $|B|$ divides $b$.
Theorem. A finite group $G$ is factorizable if $G$ contains a bifactorizable subgroup $H$.
Proof. Given positive integers $a,b$ with $ab=|G|$ use the bifactorizability of $H$ to find subsets $A_1,B_1subset G$ such that $AHB=G$, $|A_1|cdot |H|cdot |B_1|=|G|$, $|A_1|$ divides $a$, and $B_1$ divides $b$. The factorizability of $H$ yields two sets $A_2,B_2subset H$ of cardinality $|A_2|=a/|A_1|$ and $|B_2|=b/|B_1|$ such that $A_2B_2=H$. Then the sets $A=A_1A_2$ and $B=B_2B_1$ have cardinality $|A|le a$, $|B|le b$ and
$AB=A_1A_2B_2B_1=A_1HB_1=G$. It follows from $ab=|G|=|A|cdot|B|le ab$ that $|A|=a$ and $|B|=b$. $square$
It is easy to see that a subgroup $H$ of a group $G$ is bifactorizable if it is factorizable and has prime index in $G$. Moreover, as was observed by M.Farrokhi D.G. in his answer to this post, a subgroup $H$ of a group $G$ is bifactorizable if $H$ is factorizable and the index of $H$ in $G$ is a prime power $p^k$ such that $p^{2k-1}$ divides $|G|$.
A normal subgroup $H$ of a group $G$ is factorizable if both groups $H$ and $G/H$ are factorizable. This implies
Corollary. A finite group $G$ is factorizable if $G$ contains a bifactorizable subgroup $H$ with factorizable quotient $G/H$.
This corollary reduces Problems 1,2 to studying the factorizability of finite simple groups. According to the classification of finite simple groups, each finite simple group is either cyclic of prime order, or alternating, or belongs to 16 families of groups of Lie type or is one of 27 sporadic groups.
Among these families only the factorizability of finite cyclic groups is trivially true.
Problem 3. Is each alternating group $A_n$ factorizable?
It may happen that the argument of Ilya Bogdanov from his answer to this MO-problem can be helpful here. On the other hand, it can be shown that the subgroup $A_n$ is bifactorizable in $A_{n+1}$ if and only if $A_n$ is factorizable and $nne 3$ is a power of a prime. It follows from the answer to this MO-question that the subgroup $A_3$ is not bifactorizable in $A_4$.
Problem 4. Is any hope to prove that some infinite family of simple groups of Lie type consists of factorizable groups?
gr.group-theory finite-groups additive-combinatorics
gr.group-theory finite-groups additive-combinatorics
edited Nov 30 at 15:18
asked Nov 26 at 13:23
Taras Banakh
15.6k13190
15.6k13190
Amazing to me that this seemingly basic problem in the theory of finite groups is apparently open.
– Sam Hopkins
Nov 26 at 16:01
@SamHopkins I am not expert in Group Theory. I admit that this problem has an answer, known to specialists, see the answer of M.Farrokhi D.G.
– Taras Banakh
Nov 26 at 16:12
I would guess that if the answer to the question is yes, then it might be possible to prove it, given that the problem has been reduced to the case of finite simple groups, about which a lot is known. But if the answer to the question is no, then it could be very hard to prove because you have so many subsets to consider!
– Derek Holt
Nov 26 at 19:21
@DerekHolt Exactly this reduction to the case of finite simple groups follows from Corollary. For a negative answer maybe it will be easier to construct a counterexample to this related question: mathoverflow.net/questions/316262/…
– Taras Banakh
Nov 26 at 19:33
1
You might be interested in googling the keyword "minimal logarithmic signature" for a related problem which has come under some scrutiny in cryptography and on which some progress has been made.
– Gro-Tsen
Nov 28 at 18:13
|
show 2 more comments
Amazing to me that this seemingly basic problem in the theory of finite groups is apparently open.
– Sam Hopkins
Nov 26 at 16:01
@SamHopkins I am not expert in Group Theory. I admit that this problem has an answer, known to specialists, see the answer of M.Farrokhi D.G.
– Taras Banakh
Nov 26 at 16:12
I would guess that if the answer to the question is yes, then it might be possible to prove it, given that the problem has been reduced to the case of finite simple groups, about which a lot is known. But if the answer to the question is no, then it could be very hard to prove because you have so many subsets to consider!
– Derek Holt
Nov 26 at 19:21
@DerekHolt Exactly this reduction to the case of finite simple groups follows from Corollary. For a negative answer maybe it will be easier to construct a counterexample to this related question: mathoverflow.net/questions/316262/…
– Taras Banakh
Nov 26 at 19:33
1
You might be interested in googling the keyword "minimal logarithmic signature" for a related problem which has come under some scrutiny in cryptography and on which some progress has been made.
– Gro-Tsen
Nov 28 at 18:13
Amazing to me that this seemingly basic problem in the theory of finite groups is apparently open.
– Sam Hopkins
Nov 26 at 16:01
Amazing to me that this seemingly basic problem in the theory of finite groups is apparently open.
– Sam Hopkins
Nov 26 at 16:01
@SamHopkins I am not expert in Group Theory. I admit that this problem has an answer, known to specialists, see the answer of M.Farrokhi D.G.
– Taras Banakh
Nov 26 at 16:12
@SamHopkins I am not expert in Group Theory. I admit that this problem has an answer, known to specialists, see the answer of M.Farrokhi D.G.
– Taras Banakh
Nov 26 at 16:12
I would guess that if the answer to the question is yes, then it might be possible to prove it, given that the problem has been reduced to the case of finite simple groups, about which a lot is known. But if the answer to the question is no, then it could be very hard to prove because you have so many subsets to consider!
– Derek Holt
Nov 26 at 19:21
I would guess that if the answer to the question is yes, then it might be possible to prove it, given that the problem has been reduced to the case of finite simple groups, about which a lot is known. But if the answer to the question is no, then it could be very hard to prove because you have so many subsets to consider!
– Derek Holt
Nov 26 at 19:21
@DerekHolt Exactly this reduction to the case of finite simple groups follows from Corollary. For a negative answer maybe it will be easier to construct a counterexample to this related question: mathoverflow.net/questions/316262/…
– Taras Banakh
Nov 26 at 19:33
@DerekHolt Exactly this reduction to the case of finite simple groups follows from Corollary. For a negative answer maybe it will be easier to construct a counterexample to this related question: mathoverflow.net/questions/316262/…
– Taras Banakh
Nov 26 at 19:33
1
1
You might be interested in googling the keyword "minimal logarithmic signature" for a related problem which has come under some scrutiny in cryptography and on which some progress has been made.
– Gro-Tsen
Nov 28 at 18:13
You might be interested in googling the keyword "minimal logarithmic signature" for a related problem which has come under some scrutiny in cryptography and on which some progress has been made.
– Gro-Tsen
Nov 28 at 18:13
|
show 2 more comments
2 Answers
2
active
oldest
votes
The problem both in case of numbers and groups are extensively studied in a more general setting. Here are the main references (books) I know:
Groups:
Products of Finite Groups (Adolfo Ballester-Bolinches, Ramon Esteban-Romero and Mohamed Asaad)(2010)
Factoring Groups into Subsets (Sandor Szabo and Arthur D. Sands)(2009)
Topics in Factorization of Abelian Groups (Sandor Szabo)(2004)
Products of Groups (Bernhard Amberg, Silvana Franciosi and Francesco de Giovanni)(1993)
Products of Conjugacy Classes in Groups (Zvi Arad and Marcel Herzog)(1985)
Also
The Maximal Factorizations of the Finite Simple Groups and Their Automorphism Groups (M. W. Liebeck, C. E. Praeger and J. Saxl)(1990)(86)(432)
Numbers:
Structural Additive Theory (David J. Grynkiewicz)(2013)
Combinatorial Number Theory and Additive Group Theory (Alfred Geroldinger and Imre Z. Ruzsa)(2009)
Additive Combinatorics (Terense Tao and Van Vu)(2006)
Additive Number Theory; The Classical Bases (Melvyn B. Nathanson)(1996)
Additive Number Theory: Inverse Problems and the Geometry of Sumsets (Melvyn B. Nathanson)(1996)
Foundations of a Structural Theory of Set Addition (Gregory A. Freiman)(1973)
Thank you fro the extensive references. But what about the above problems? What is the answer? Is each finite group factorizable or not?
– Taras Banakh
Nov 26 at 14:37
add a comment |
Definition. We say that a group $G$ of order $n$ is good if it satisfies any of the following equivalent conditions:
- For every divisor $d$ of $n$, there exists a nontrivial proper subgroup $H$ of $G$ such that either $d$ or $n/d$ divides $|H|$.
- For every divisor $d$ of $n$, there exists a nontrivial proper subgroup $H$ of $G$ such that $[G:H]$ divides either $d$ or $n/d$.
In the above definition, we can replace the subgroups with maximal subgroups. A set of (maximal) subgroups appearing in the definition of a good group is called a good set of (maximal) subgroups.
Theorem. Every good finite group with a good set of factorizable subgroups is factorizable.
Proof. Let $X$ be a good set of factorizable subgroups of $G$. If $|G|=ab$, then there exists a subgroup $Hin X$ such that $|H|$ is divisible by $a$ or $b$, say $a$. Let $|H|=aa'$ and $H=AA'$ be such that $|A|=a$ and $|A'|=a'$. Then $G=H(Hbackslash G)=A(A'(Hbackslash G))$ is a factorization of $G$ with $|A|=a$ and $|A'(Hbackslash G)|=b$. Therefore, $G$ is factorizable.
Corollary. Let $qneq2,4$ be a prime power. If $A_{q-1}$ is factorizable, then so is $A_q$.
Proof. The group $A_q$ has a maximal subgroup $A_{q-1}$ of index $q$, and that $q$ divides either $a$ or $b$ whenever $|A_q|=ab$. Hence, $A_q$ is good with the good set ${A_{q-1}}$ of factorizable subgroups so that $A_q$ is factorizable.
As a result, we obtain a new proof that $A_9$ is factorizable.
I think a large class of finite simple groups can be studied using the above theorem and the following criterion of François Brunault:
- If $|G|=ab$ and $G$ has a section of size $a$ or $b$, then $G=AB$ with $|A|=a$ and $|B|=b$.
I understand how Theorem implies Corollary for a prime q. But how do you derive it for prime powers? Why do you think that if a prime power $q$ divides $ab$, then it divides $a$ or $b$?
– Taras Banakh
Nov 26 at 17:04
And what is a "section" in the result of Francois Brunault, you mention?
– Taras Banakh
Nov 26 at 17:07
The definition of a "good" is not good as each group is good: just take $H=G$. Maybe "proper" should be added?
– Taras Banakh
Nov 26 at 17:14
1
Suppose $q=p^k$. The largest power of $p$ dividing $|A_q|$ is at least $2k-1$, so either $q$ divides $a$ or $b$. A section is simply a pair of subgroups $Hsubseteq K$ of $G$ and the size means $[K:H]$. The definition of good groups is fixed.
– M. Farrokhi D. G.
Nov 26 at 17:18
Are all arternating groups good?
– Taras Banakh
Nov 26 at 17:23
|
show 1 more comment
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "504"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f316233%2ffactorizable-groups%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
The problem both in case of numbers and groups are extensively studied in a more general setting. Here are the main references (books) I know:
Groups:
Products of Finite Groups (Adolfo Ballester-Bolinches, Ramon Esteban-Romero and Mohamed Asaad)(2010)
Factoring Groups into Subsets (Sandor Szabo and Arthur D. Sands)(2009)
Topics in Factorization of Abelian Groups (Sandor Szabo)(2004)
Products of Groups (Bernhard Amberg, Silvana Franciosi and Francesco de Giovanni)(1993)
Products of Conjugacy Classes in Groups (Zvi Arad and Marcel Herzog)(1985)
Also
The Maximal Factorizations of the Finite Simple Groups and Their Automorphism Groups (M. W. Liebeck, C. E. Praeger and J. Saxl)(1990)(86)(432)
Numbers:
Structural Additive Theory (David J. Grynkiewicz)(2013)
Combinatorial Number Theory and Additive Group Theory (Alfred Geroldinger and Imre Z. Ruzsa)(2009)
Additive Combinatorics (Terense Tao and Van Vu)(2006)
Additive Number Theory; The Classical Bases (Melvyn B. Nathanson)(1996)
Additive Number Theory: Inverse Problems and the Geometry of Sumsets (Melvyn B. Nathanson)(1996)
Foundations of a Structural Theory of Set Addition (Gregory A. Freiman)(1973)
Thank you fro the extensive references. But what about the above problems? What is the answer? Is each finite group factorizable or not?
– Taras Banakh
Nov 26 at 14:37
add a comment |
The problem both in case of numbers and groups are extensively studied in a more general setting. Here are the main references (books) I know:
Groups:
Products of Finite Groups (Adolfo Ballester-Bolinches, Ramon Esteban-Romero and Mohamed Asaad)(2010)
Factoring Groups into Subsets (Sandor Szabo and Arthur D. Sands)(2009)
Topics in Factorization of Abelian Groups (Sandor Szabo)(2004)
Products of Groups (Bernhard Amberg, Silvana Franciosi and Francesco de Giovanni)(1993)
Products of Conjugacy Classes in Groups (Zvi Arad and Marcel Herzog)(1985)
Also
The Maximal Factorizations of the Finite Simple Groups and Their Automorphism Groups (M. W. Liebeck, C. E. Praeger and J. Saxl)(1990)(86)(432)
Numbers:
Structural Additive Theory (David J. Grynkiewicz)(2013)
Combinatorial Number Theory and Additive Group Theory (Alfred Geroldinger and Imre Z. Ruzsa)(2009)
Additive Combinatorics (Terense Tao and Van Vu)(2006)
Additive Number Theory; The Classical Bases (Melvyn B. Nathanson)(1996)
Additive Number Theory: Inverse Problems and the Geometry of Sumsets (Melvyn B. Nathanson)(1996)
Foundations of a Structural Theory of Set Addition (Gregory A. Freiman)(1973)
Thank you fro the extensive references. But what about the above problems? What is the answer? Is each finite group factorizable or not?
– Taras Banakh
Nov 26 at 14:37
add a comment |
The problem both in case of numbers and groups are extensively studied in a more general setting. Here are the main references (books) I know:
Groups:
Products of Finite Groups (Adolfo Ballester-Bolinches, Ramon Esteban-Romero and Mohamed Asaad)(2010)
Factoring Groups into Subsets (Sandor Szabo and Arthur D. Sands)(2009)
Topics in Factorization of Abelian Groups (Sandor Szabo)(2004)
Products of Groups (Bernhard Amberg, Silvana Franciosi and Francesco de Giovanni)(1993)
Products of Conjugacy Classes in Groups (Zvi Arad and Marcel Herzog)(1985)
Also
The Maximal Factorizations of the Finite Simple Groups and Their Automorphism Groups (M. W. Liebeck, C. E. Praeger and J. Saxl)(1990)(86)(432)
Numbers:
Structural Additive Theory (David J. Grynkiewicz)(2013)
Combinatorial Number Theory and Additive Group Theory (Alfred Geroldinger and Imre Z. Ruzsa)(2009)
Additive Combinatorics (Terense Tao and Van Vu)(2006)
Additive Number Theory; The Classical Bases (Melvyn B. Nathanson)(1996)
Additive Number Theory: Inverse Problems and the Geometry of Sumsets (Melvyn B. Nathanson)(1996)
Foundations of a Structural Theory of Set Addition (Gregory A. Freiman)(1973)
The problem both in case of numbers and groups are extensively studied in a more general setting. Here are the main references (books) I know:
Groups:
Products of Finite Groups (Adolfo Ballester-Bolinches, Ramon Esteban-Romero and Mohamed Asaad)(2010)
Factoring Groups into Subsets (Sandor Szabo and Arthur D. Sands)(2009)
Topics in Factorization of Abelian Groups (Sandor Szabo)(2004)
Products of Groups (Bernhard Amberg, Silvana Franciosi and Francesco de Giovanni)(1993)
Products of Conjugacy Classes in Groups (Zvi Arad and Marcel Herzog)(1985)
Also
The Maximal Factorizations of the Finite Simple Groups and Their Automorphism Groups (M. W. Liebeck, C. E. Praeger and J. Saxl)(1990)(86)(432)
Numbers:
Structural Additive Theory (David J. Grynkiewicz)(2013)
Combinatorial Number Theory and Additive Group Theory (Alfred Geroldinger and Imre Z. Ruzsa)(2009)
Additive Combinatorics (Terense Tao and Van Vu)(2006)
Additive Number Theory; The Classical Bases (Melvyn B. Nathanson)(1996)
Additive Number Theory: Inverse Problems and the Geometry of Sumsets (Melvyn B. Nathanson)(1996)
Foundations of a Structural Theory of Set Addition (Gregory A. Freiman)(1973)
answered Nov 26 at 13:57
M. Farrokhi D. G.
1,284613
1,284613
Thank you fro the extensive references. But what about the above problems? What is the answer? Is each finite group factorizable or not?
– Taras Banakh
Nov 26 at 14:37
add a comment |
Thank you fro the extensive references. But what about the above problems? What is the answer? Is each finite group factorizable or not?
– Taras Banakh
Nov 26 at 14:37
Thank you fro the extensive references. But what about the above problems? What is the answer? Is each finite group factorizable or not?
– Taras Banakh
Nov 26 at 14:37
Thank you fro the extensive references. But what about the above problems? What is the answer? Is each finite group factorizable or not?
– Taras Banakh
Nov 26 at 14:37
add a comment |
Definition. We say that a group $G$ of order $n$ is good if it satisfies any of the following equivalent conditions:
- For every divisor $d$ of $n$, there exists a nontrivial proper subgroup $H$ of $G$ such that either $d$ or $n/d$ divides $|H|$.
- For every divisor $d$ of $n$, there exists a nontrivial proper subgroup $H$ of $G$ such that $[G:H]$ divides either $d$ or $n/d$.
In the above definition, we can replace the subgroups with maximal subgroups. A set of (maximal) subgroups appearing in the definition of a good group is called a good set of (maximal) subgroups.
Theorem. Every good finite group with a good set of factorizable subgroups is factorizable.
Proof. Let $X$ be a good set of factorizable subgroups of $G$. If $|G|=ab$, then there exists a subgroup $Hin X$ such that $|H|$ is divisible by $a$ or $b$, say $a$. Let $|H|=aa'$ and $H=AA'$ be such that $|A|=a$ and $|A'|=a'$. Then $G=H(Hbackslash G)=A(A'(Hbackslash G))$ is a factorization of $G$ with $|A|=a$ and $|A'(Hbackslash G)|=b$. Therefore, $G$ is factorizable.
Corollary. Let $qneq2,4$ be a prime power. If $A_{q-1}$ is factorizable, then so is $A_q$.
Proof. The group $A_q$ has a maximal subgroup $A_{q-1}$ of index $q$, and that $q$ divides either $a$ or $b$ whenever $|A_q|=ab$. Hence, $A_q$ is good with the good set ${A_{q-1}}$ of factorizable subgroups so that $A_q$ is factorizable.
As a result, we obtain a new proof that $A_9$ is factorizable.
I think a large class of finite simple groups can be studied using the above theorem and the following criterion of François Brunault:
- If $|G|=ab$ and $G$ has a section of size $a$ or $b$, then $G=AB$ with $|A|=a$ and $|B|=b$.
I understand how Theorem implies Corollary for a prime q. But how do you derive it for prime powers? Why do you think that if a prime power $q$ divides $ab$, then it divides $a$ or $b$?
– Taras Banakh
Nov 26 at 17:04
And what is a "section" in the result of Francois Brunault, you mention?
– Taras Banakh
Nov 26 at 17:07
The definition of a "good" is not good as each group is good: just take $H=G$. Maybe "proper" should be added?
– Taras Banakh
Nov 26 at 17:14
1
Suppose $q=p^k$. The largest power of $p$ dividing $|A_q|$ is at least $2k-1$, so either $q$ divides $a$ or $b$. A section is simply a pair of subgroups $Hsubseteq K$ of $G$ and the size means $[K:H]$. The definition of good groups is fixed.
– M. Farrokhi D. G.
Nov 26 at 17:18
Are all arternating groups good?
– Taras Banakh
Nov 26 at 17:23
|
show 1 more comment
Definition. We say that a group $G$ of order $n$ is good if it satisfies any of the following equivalent conditions:
- For every divisor $d$ of $n$, there exists a nontrivial proper subgroup $H$ of $G$ such that either $d$ or $n/d$ divides $|H|$.
- For every divisor $d$ of $n$, there exists a nontrivial proper subgroup $H$ of $G$ such that $[G:H]$ divides either $d$ or $n/d$.
In the above definition, we can replace the subgroups with maximal subgroups. A set of (maximal) subgroups appearing in the definition of a good group is called a good set of (maximal) subgroups.
Theorem. Every good finite group with a good set of factorizable subgroups is factorizable.
Proof. Let $X$ be a good set of factorizable subgroups of $G$. If $|G|=ab$, then there exists a subgroup $Hin X$ such that $|H|$ is divisible by $a$ or $b$, say $a$. Let $|H|=aa'$ and $H=AA'$ be such that $|A|=a$ and $|A'|=a'$. Then $G=H(Hbackslash G)=A(A'(Hbackslash G))$ is a factorization of $G$ with $|A|=a$ and $|A'(Hbackslash G)|=b$. Therefore, $G$ is factorizable.
Corollary. Let $qneq2,4$ be a prime power. If $A_{q-1}$ is factorizable, then so is $A_q$.
Proof. The group $A_q$ has a maximal subgroup $A_{q-1}$ of index $q$, and that $q$ divides either $a$ or $b$ whenever $|A_q|=ab$. Hence, $A_q$ is good with the good set ${A_{q-1}}$ of factorizable subgroups so that $A_q$ is factorizable.
As a result, we obtain a new proof that $A_9$ is factorizable.
I think a large class of finite simple groups can be studied using the above theorem and the following criterion of François Brunault:
- If $|G|=ab$ and $G$ has a section of size $a$ or $b$, then $G=AB$ with $|A|=a$ and $|B|=b$.
I understand how Theorem implies Corollary for a prime q. But how do you derive it for prime powers? Why do you think that if a prime power $q$ divides $ab$, then it divides $a$ or $b$?
– Taras Banakh
Nov 26 at 17:04
And what is a "section" in the result of Francois Brunault, you mention?
– Taras Banakh
Nov 26 at 17:07
The definition of a "good" is not good as each group is good: just take $H=G$. Maybe "proper" should be added?
– Taras Banakh
Nov 26 at 17:14
1
Suppose $q=p^k$. The largest power of $p$ dividing $|A_q|$ is at least $2k-1$, so either $q$ divides $a$ or $b$. A section is simply a pair of subgroups $Hsubseteq K$ of $G$ and the size means $[K:H]$. The definition of good groups is fixed.
– M. Farrokhi D. G.
Nov 26 at 17:18
Are all arternating groups good?
– Taras Banakh
Nov 26 at 17:23
|
show 1 more comment
Definition. We say that a group $G$ of order $n$ is good if it satisfies any of the following equivalent conditions:
- For every divisor $d$ of $n$, there exists a nontrivial proper subgroup $H$ of $G$ such that either $d$ or $n/d$ divides $|H|$.
- For every divisor $d$ of $n$, there exists a nontrivial proper subgroup $H$ of $G$ such that $[G:H]$ divides either $d$ or $n/d$.
In the above definition, we can replace the subgroups with maximal subgroups. A set of (maximal) subgroups appearing in the definition of a good group is called a good set of (maximal) subgroups.
Theorem. Every good finite group with a good set of factorizable subgroups is factorizable.
Proof. Let $X$ be a good set of factorizable subgroups of $G$. If $|G|=ab$, then there exists a subgroup $Hin X$ such that $|H|$ is divisible by $a$ or $b$, say $a$. Let $|H|=aa'$ and $H=AA'$ be such that $|A|=a$ and $|A'|=a'$. Then $G=H(Hbackslash G)=A(A'(Hbackslash G))$ is a factorization of $G$ with $|A|=a$ and $|A'(Hbackslash G)|=b$. Therefore, $G$ is factorizable.
Corollary. Let $qneq2,4$ be a prime power. If $A_{q-1}$ is factorizable, then so is $A_q$.
Proof. The group $A_q$ has a maximal subgroup $A_{q-1}$ of index $q$, and that $q$ divides either $a$ or $b$ whenever $|A_q|=ab$. Hence, $A_q$ is good with the good set ${A_{q-1}}$ of factorizable subgroups so that $A_q$ is factorizable.
As a result, we obtain a new proof that $A_9$ is factorizable.
I think a large class of finite simple groups can be studied using the above theorem and the following criterion of François Brunault:
- If $|G|=ab$ and $G$ has a section of size $a$ or $b$, then $G=AB$ with $|A|=a$ and $|B|=b$.
Definition. We say that a group $G$ of order $n$ is good if it satisfies any of the following equivalent conditions:
- For every divisor $d$ of $n$, there exists a nontrivial proper subgroup $H$ of $G$ such that either $d$ or $n/d$ divides $|H|$.
- For every divisor $d$ of $n$, there exists a nontrivial proper subgroup $H$ of $G$ such that $[G:H]$ divides either $d$ or $n/d$.
In the above definition, we can replace the subgroups with maximal subgroups. A set of (maximal) subgroups appearing in the definition of a good group is called a good set of (maximal) subgroups.
Theorem. Every good finite group with a good set of factorizable subgroups is factorizable.
Proof. Let $X$ be a good set of factorizable subgroups of $G$. If $|G|=ab$, then there exists a subgroup $Hin X$ such that $|H|$ is divisible by $a$ or $b$, say $a$. Let $|H|=aa'$ and $H=AA'$ be such that $|A|=a$ and $|A'|=a'$. Then $G=H(Hbackslash G)=A(A'(Hbackslash G))$ is a factorization of $G$ with $|A|=a$ and $|A'(Hbackslash G)|=b$. Therefore, $G$ is factorizable.
Corollary. Let $qneq2,4$ be a prime power. If $A_{q-1}$ is factorizable, then so is $A_q$.
Proof. The group $A_q$ has a maximal subgroup $A_{q-1}$ of index $q$, and that $q$ divides either $a$ or $b$ whenever $|A_q|=ab$. Hence, $A_q$ is good with the good set ${A_{q-1}}$ of factorizable subgroups so that $A_q$ is factorizable.
As a result, we obtain a new proof that $A_9$ is factorizable.
I think a large class of finite simple groups can be studied using the above theorem and the following criterion of François Brunault:
- If $|G|=ab$ and $G$ has a section of size $a$ or $b$, then $G=AB$ with $|A|=a$ and $|B|=b$.
edited Nov 26 at 19:13
answered Nov 26 at 16:58
M. Farrokhi D. G.
1,284613
1,284613
I understand how Theorem implies Corollary for a prime q. But how do you derive it for prime powers? Why do you think that if a prime power $q$ divides $ab$, then it divides $a$ or $b$?
– Taras Banakh
Nov 26 at 17:04
And what is a "section" in the result of Francois Brunault, you mention?
– Taras Banakh
Nov 26 at 17:07
The definition of a "good" is not good as each group is good: just take $H=G$. Maybe "proper" should be added?
– Taras Banakh
Nov 26 at 17:14
1
Suppose $q=p^k$. The largest power of $p$ dividing $|A_q|$ is at least $2k-1$, so either $q$ divides $a$ or $b$. A section is simply a pair of subgroups $Hsubseteq K$ of $G$ and the size means $[K:H]$. The definition of good groups is fixed.
– M. Farrokhi D. G.
Nov 26 at 17:18
Are all arternating groups good?
– Taras Banakh
Nov 26 at 17:23
|
show 1 more comment
I understand how Theorem implies Corollary for a prime q. But how do you derive it for prime powers? Why do you think that if a prime power $q$ divides $ab$, then it divides $a$ or $b$?
– Taras Banakh
Nov 26 at 17:04
And what is a "section" in the result of Francois Brunault, you mention?
– Taras Banakh
Nov 26 at 17:07
The definition of a "good" is not good as each group is good: just take $H=G$. Maybe "proper" should be added?
– Taras Banakh
Nov 26 at 17:14
1
Suppose $q=p^k$. The largest power of $p$ dividing $|A_q|$ is at least $2k-1$, so either $q$ divides $a$ or $b$. A section is simply a pair of subgroups $Hsubseteq K$ of $G$ and the size means $[K:H]$. The definition of good groups is fixed.
– M. Farrokhi D. G.
Nov 26 at 17:18
Are all arternating groups good?
– Taras Banakh
Nov 26 at 17:23
I understand how Theorem implies Corollary for a prime q. But how do you derive it for prime powers? Why do you think that if a prime power $q$ divides $ab$, then it divides $a$ or $b$?
– Taras Banakh
Nov 26 at 17:04
I understand how Theorem implies Corollary for a prime q. But how do you derive it for prime powers? Why do you think that if a prime power $q$ divides $ab$, then it divides $a$ or $b$?
– Taras Banakh
Nov 26 at 17:04
And what is a "section" in the result of Francois Brunault, you mention?
– Taras Banakh
Nov 26 at 17:07
And what is a "section" in the result of Francois Brunault, you mention?
– Taras Banakh
Nov 26 at 17:07
The definition of a "good" is not good as each group is good: just take $H=G$. Maybe "proper" should be added?
– Taras Banakh
Nov 26 at 17:14
The definition of a "good" is not good as each group is good: just take $H=G$. Maybe "proper" should be added?
– Taras Banakh
Nov 26 at 17:14
1
1
Suppose $q=p^k$. The largest power of $p$ dividing $|A_q|$ is at least $2k-1$, so either $q$ divides $a$ or $b$. A section is simply a pair of subgroups $Hsubseteq K$ of $G$ and the size means $[K:H]$. The definition of good groups is fixed.
– M. Farrokhi D. G.
Nov 26 at 17:18
Suppose $q=p^k$. The largest power of $p$ dividing $|A_q|$ is at least $2k-1$, so either $q$ divides $a$ or $b$. A section is simply a pair of subgroups $Hsubseteq K$ of $G$ and the size means $[K:H]$. The definition of good groups is fixed.
– M. Farrokhi D. G.
Nov 26 at 17:18
Are all arternating groups good?
– Taras Banakh
Nov 26 at 17:23
Are all arternating groups good?
– Taras Banakh
Nov 26 at 17:23
|
show 1 more comment
Thanks for contributing an answer to MathOverflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f316233%2ffactorizable-groups%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Amazing to me that this seemingly basic problem in the theory of finite groups is apparently open.
– Sam Hopkins
Nov 26 at 16:01
@SamHopkins I am not expert in Group Theory. I admit that this problem has an answer, known to specialists, see the answer of M.Farrokhi D.G.
– Taras Banakh
Nov 26 at 16:12
I would guess that if the answer to the question is yes, then it might be possible to prove it, given that the problem has been reduced to the case of finite simple groups, about which a lot is known. But if the answer to the question is no, then it could be very hard to prove because you have so many subsets to consider!
– Derek Holt
Nov 26 at 19:21
@DerekHolt Exactly this reduction to the case of finite simple groups follows from Corollary. For a negative answer maybe it will be easier to construct a counterexample to this related question: mathoverflow.net/questions/316262/…
– Taras Banakh
Nov 26 at 19:33
1
You might be interested in googling the keyword "minimal logarithmic signature" for a related problem which has come under some scrutiny in cryptography and on which some progress has been made.
– Gro-Tsen
Nov 28 at 18:13