Mixing
Roots of unity (group theory)
$begingroup$
Let $p$ be a prime and $T$ the set of ALL $n$-th roots of unity $zeta_n pmod p$: $T=[1, zeta_n, zeta_n^2, zeta_n^3...zeta_n^{n-1}]$ ($n$ is odd). Find the smallest (non-empty) subset (in length) $S ⊂ T$ such that the sum of all elements in $S$ is $0pmod p$. I suspect that the quickest way to accomplish this is the LLL Algorithm and hope that the coefficients of $zeta_n^k$ are either $0$ or $1$ but I'm not sure.
elementary-number-theory summation
asked Jan 18 at 5:31
J. LinneJ. Linne
883415
$endgroup$
|
show 3 more comments
$begingroup$
Let $p$ be a prime and $T$ the set of ALL $n$-th roots of unity $zeta_n pmod p$: $T=[1, zeta_n, zeta_n^2, zeta_n^3...zeta_n^{n-1}]$ ($n$ is odd). Find the smallest (non-empty) subset (in length) $S ⊂ T$ such that the sum of all elements in $S$ is $0pmod p$. I suspect that the quickest way to accomplish this is the LLL Algorithm and hope that the coefficients of $zeta_n^k$ are either $0$ or $1$ but I'm not sure.
elementary-number-theory summation
asked Jan 18 at 5:31
J. LinneJ. Linne
883415
$endgroup$
3
$begingroup$
I find it difficult to believe that anything as hifalutin as LLL could be the right way to go. But is $n$ supposed to be prime to $p$? And where are these roots of unity? Are you looking only within $Bbb F_p=Bbb Z/pBbb Z$? Or are you starting with roots of unity as algebraic numbers, which you then want to look at in characteristic $p$ somehow?
$endgroup$
– Lubin
Jan 18 at 6:30
$begingroup$
The smallest subset such that the sum is $0$ is always $S=varnothing$. If $q$ is the smallest prime dividing $n$, then the powers of $zeta_n^{n/q}$ yield a set of size $q$. But to say more, it would help to clarify where these roots of unity are from.
$endgroup$
– Servaes
Jan 18 at 10:30
$begingroup$
@Lubin yes, working in $mathbb Z/pmathbb Z$. With $p=1pmod n$, the elements in $S$ are the $n$-th roots of unity $pmod p$. Then find a non-empty subset of $S$ whos sum is $0$.
$endgroup$
– J. Linne
Jan 19 at 2:55
$begingroup$
Then have you looked at the case $n=9$, $p=37$? Or at the case $n=105$, $p=211$? Now that I understand your setup, the problem looks not at all deep to me.
$endgroup$
– Lubin
Jan 19 at 22:59
2
$begingroup$
By length of $S$ do you mean just its cardinality, or the difference from the first included exponent to the last? Anyway, this is a bit like a modular knapsack problem, probably why you thought of LLL.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 4:53
|
show 3 more comments
$begingroup$
Let $p$ be a prime and $T$ the set of ALL $n$-th roots of unity $zeta_n pmod p$: $T=[1, zeta_n, zeta_n^2, zeta_n^3...zeta_n^{n-1}]$ ($n$ is odd). Find the smallest (non-empty) subset (in length) $S ⊂ T$ such that the sum of all elements in $S$ is $0pmod p$. I suspect that the quickest way to accomplish this is the LLL Algorithm and hope that the coefficients of $zeta_n^k$ are either $0$ or $1$ but I'm not sure.
elementary-number-theory summation
asked Jan 18 at 5:31
J. LinneJ. Linne
883415
$endgroup$
Let $p$ be a prime and $T$ the set of ALL $n$-th roots of unity $zeta_n pmod p$: $T=[1, zeta_n, zeta_n^2, zeta_n^3...zeta_n^{n-1}]$ ($n$ is odd). Find the smallest (non-empty) subset (in length) $S ⊂ T$ such that the sum of all elements in $S$ is $0pmod p$. I suspect that the quickest way to accomplish this is the LLL Algorithm and hope that the coefficients of $zeta_n^k$ are either $0$ or $1$ but I'm not sure.
elementary-number-theory summation
elementary-number-theory summation
asked Jan 18 at 5:31
J. LinneJ. Linne
883415
asked Jan 18 at 5:31
J. LinneJ. Linne
883415
edited Jan 19 at 2:54
J. Linne
asked Jan 18 at 5:31
J. LinneJ. Linne
883415
asked Jan 18 at 5:31
J. LinneJ. Linne
883415
asked Jan 18 at 5:31
J. LinneJ. Linne
883415
883415
3
$begingroup$
I find it difficult to believe that anything as hifalutin as LLL could be the right way to go. But is $n$ supposed to be prime to $p$? And where are these roots of unity? Are you looking only within $Bbb F_p=Bbb Z/pBbb Z$? Or are you starting with roots of unity as algebraic numbers, which you then want to look at in characteristic $p$ somehow?
$endgroup$
– Lubin
Jan 18 at 6:30
$begingroup$
The smallest subset such that the sum is $0$ is always $S=varnothing$. If $q$ is the smallest prime dividing $n$, then the powers of $zeta_n^{n/q}$ yield a set of size $q$. But to say more, it would help to clarify where these roots of unity are from.
$endgroup$
– Servaes
Jan 18 at 10:30
$begingroup$
@Lubin yes, working in $mathbb Z/pmathbb Z$. With $p=1pmod n$, the elements in $S$ are the $n$-th roots of unity $pmod p$. Then find a non-empty subset of $S$ whos sum is $0$.
$endgroup$
– J. Linne
Jan 19 at 2:55
$begingroup$
Then have you looked at the case $n=9$, $p=37$? Or at the case $n=105$, $p=211$? Now that I understand your setup, the problem looks not at all deep to me.
$endgroup$
– Lubin
Jan 19 at 22:59
2
$begingroup$
By length of $S$ do you mean just its cardinality, or the difference from the first included exponent to the last? Anyway, this is a bit like a modular knapsack problem, probably why you thought of LLL.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 4:53
|
show 3 more comments
3
$begingroup$
I find it difficult to believe that anything as hifalutin as LLL could be the right way to go. But is $n$ supposed to be prime to $p$? And where are these roots of unity? Are you looking only within $Bbb F_p=Bbb Z/pBbb Z$? Or are you starting with roots of unity as algebraic numbers, which you then want to look at in characteristic $p$ somehow?
$endgroup$
– Lubin
Jan 18 at 6:30
$begingroup$
The smallest subset such that the sum is $0$ is always $S=varnothing$. If $q$ is the smallest prime dividing $n$, then the powers of $zeta_n^{n/q}$ yield a set of size $q$. But to say more, it would help to clarify where these roots of unity are from.
$endgroup$
– Servaes
Jan 18 at 10:30
$begingroup$
@Lubin yes, working in $mathbb Z/pmathbb Z$. With $p=1pmod n$, the elements in $S$ are the $n$-th roots of unity $pmod p$. Then find a non-empty subset of $S$ whos sum is $0$.
$endgroup$
– J. Linne
Jan 19 at 2:55
$begingroup$
Then have you looked at the case $n=9$, $p=37$? Or at the case $n=105$, $p=211$? Now that I understand your setup, the problem looks not at all deep to me.
$endgroup$
– Lubin
Jan 19 at 22:59
2
$begingroup$
By length of $S$ do you mean just its cardinality, or the difference from the first included exponent to the last? Anyway, this is a bit like a modular knapsack problem, probably why you thought of LLL.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 4:53
3
3
$begingroup$
I find it difficult to believe that anything as hifalutin as LLL could be the right way to go. But is $n$ supposed to be prime to $p$? And where are these roots of unity? Are you looking only within $Bbb F_p=Bbb Z/pBbb Z$? Or are you starting with roots of unity as algebraic numbers, which you then want to look at in characteristic $p$ somehow?
$endgroup$
– Lubin
Jan 18 at 6:30
$begingroup$
I find it difficult to believe that anything as hifalutin as LLL could be the right way to go. But is $n$ supposed to be prime to $p$? And where are these roots of unity? Are you looking only within $Bbb F_p=Bbb Z/pBbb Z$? Or are you starting with roots of unity as algebraic numbers, which you then want to look at in characteristic $p$ somehow?
$endgroup$
– Lubin
Jan 18 at 6:30
$begingroup$
The smallest subset such that the sum is $0$ is always $S=varnothing$. If $q$ is the smallest prime dividing $n$, then the powers of $zeta_n^{n/q}$ yield a set of size $q$. But to say more, it would help to clarify where these roots of unity are from.
$endgroup$
– Servaes
Jan 18 at 10:30
$begingroup$
The smallest subset such that the sum is $0$ is always $S=varnothing$. If $q$ is the smallest prime dividing $n$, then the powers of $zeta_n^{n/q}$ yield a set of size $q$. But to say more, it would help to clarify where these roots of unity are from.
$endgroup$
– Servaes
Jan 18 at 10:30
$begingroup$
@Lubin yes, working in $mathbb Z/pmathbb Z$. With $p=1pmod n$, the elements in $S$ are the $n$-th roots of unity $pmod p$. Then find a non-empty subset of $S$ whos sum is $0$.
$endgroup$
– J. Linne
Jan 19 at 2:55
$begingroup$
@Lubin yes, working in $mathbb Z/pmathbb Z$. With $p=1pmod n$, the elements in $S$ are the $n$-th roots of unity $pmod p$. Then find a non-empty subset of $S$ whos sum is $0$.
$endgroup$
– J. Linne
Jan 19 at 2:55
$begingroup$
Then have you looked at the case $n=9$, $p=37$? Or at the case $n=105$, $p=211$? Now that I understand your setup, the problem looks not at all deep to me.
$endgroup$
– Lubin
Jan 19 at 22:59
$begingroup$
Then have you looked at the case $n=9$, $p=37$? Or at the case $n=105$, $p=211$? Now that I understand your setup, the problem looks not at all deep to me.
$endgroup$
– Lubin
Jan 19 at 22:59
2
2
$begingroup$
By length of $S$ do you mean just its cardinality, or the difference from the first included exponent to the last? Anyway, this is a bit like a modular knapsack problem, probably why you thought of LLL.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 4:53
$begingroup$
By length of $S$ do you mean just its cardinality, or the difference from the first included exponent to the last? Anyway, this is a bit like a modular knapsack problem, probably why you thought of LLL.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 4:53
|
show 3 more comments
1 Answer
1
active
oldest
votes
$begingroup$
I have a contribution, but not an answer; let’s see whether I can explain why I think this is not a hard problem.
You have your number $n$ and a larger prime $p$, satisfying $n|(p-1)$. Let’s denote the field of integers modulo $p$ by $k$. We know that the set of nonzero elements, $k^times$, is not only a group, but a cyclic group, and has a generator $g$, one of a (usually) large number of such. Now, if we call $(p-1)/n=d$, then $g^d$ generates a subgroup of order $(p-1)/d=n$, in other words, $g^d$ can be taken to be your $zeta_n$.
From here on, everything seems to take place in the subgroup $langle g^drangle=Tsubset k^times$ of order $n$. In the same way as above, if $m|n$, then the $m$-th roots of $1$ in $k^times$ form a (cyclic) subgroup of $T$ of order $m$, and if $xi$ is a generator of this group, then ${1,xi,cdotsxi^{m-1}}$ form one of your sets $S$, since their sum is $(xi^m-1)/(xi-1)=0$. In particular, if $m$ is prime, you have a set of your type $S$ of cardinality $m$. I’d like to state with assurance that if you let $m$ be the smallest prime dividing $n$, then this set satisfies your minimality demand. But I’m unsure.
Certainly if $3$ is the smallest prime dividing $n$, then the group of cube roots of $1$ in $k$ is contained in $T$ and is minimal, since there is no $S$-set with only two elements, because $n$ is assumed even. So, of the two examples you offered in your comment, the first is easy: there’s an $S$ with $3$ elements, and no smaller nonempty such set. The second example catches me exactly where I’m on shakiest ground, since $307$ is prime. If my guess is correct, the only $S$-set here is $T$ itself.
EDIT — Amendment:
Your single example of elements of $Bbb F_{53}$, $1+24+28equiv0pmod{53}$, where all three summands are $13$-th roots of unity, shows that I was certainly wrong in stating that this is not a hard problem. Further, I may have said it only in comments, but I was wrong to state that the containing field $Bbb F_p$ was immaterial to the problem.
Perhaps I was looking through the wrong end of the telescope. If one looks even at the simplest case of your problem, to find three elements summing to zero in the (unique) subgroup of order $n$ in $Bbb F_p^times$ where necessarily $n|(p-1)$, then you can attack it in the following way, which makes my arguments seem particularly overoptimistic:
Once you normalize so that one of the elements of your triple is $1$, there’s a one-parameter family of triples adding to zero in $Bbb F_p$, namely ${1,a,-a-1}$. There is absolutely no reason why all three couldn’t lie in some proper subgroup of $Bbb F_p^times$, even with your restriction that this subgroup should be of odd order.
Unfortunately, I have no idea and no tools in my kit that could help you with this problem.
answered Jan 20 at 19:16
LubinLubin
44.7k44586
$endgroup$
$begingroup$
Hmmm... the set $T$ itself is always a trivial solution. I was more curious of nontrivial solutions $S⫋T$. That is, $S$ is a subset not equal to $T$ but a solution to the original problem. I just go along with the fact that there are exactly $2^n$ proper subsets of $T$.
$endgroup$
– J. Linne
Jan 21 at 20:10
$begingroup$
If $p<2^n$, then there should be at least one other subset $S$ (besides $T$) such that summing all the elements of $S$ is $0$. Therefore, we assume $p<2^n$ and one other non-trivial solution exists.
$endgroup$
– J. Linne
Jan 21 at 20:12
$begingroup$
In my examples with $n=105,163,$ and $307$, $p<2^n$, so there are more solutions than just $T$. It could be a problem related to the subset sum problem in finite fields.
$endgroup$
– J. Linne
Jan 21 at 20:15
$begingroup$
So sorry, of course I was being sloppy to say anything suggesting that the minimal set was unique. In the case $n=105$, for instance, the size of a minimal set will be $3$. I took as model the group of all cube roots of unity, call it $S_0$. Then if $zeta$ is any $10-5$-th root of unity, any $zeta S_0$ will also have three elements and have sum zero, so will satisfy your criteria.
$endgroup$
– Lubin
Jan 22 at 0:48
1
$begingroup$
Mersenne Primes $2^n-1$ seem to be a good example of this. For instance, $n=17$ and $p=2^13-1=8191$, $T=[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]$ and the only subset $S$ of $T$ such that all elements in $S$ sum to $0$ $pmod p$ is $T$ itself (good so far). Then I find if $p=53$ and $T=[1, 10, 13, 15, 16, 24, 28, 36, 42, 44, 46, 47, 49]$. Then $S=[1, 24, 28]$ is a proper subset of $T$ (that is not $T$ itself) with sum $0 pmod p$.
$endgroup$
– J. Linne
Jan 22 at 6:15
|
show 5 more comments
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: "69"
};
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%2fmath.stackexchange.com%2fquestions%2f3077874%2froots-of-unity-group-theory%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I have a contribution, but not an answer; let’s see whether I can explain why I think this is not a hard problem.
You have your number $n$ and a larger prime $p$, satisfying $n|(p-1)$. Let’s denote the field of integers modulo $p$ by $k$. We know that the set of nonzero elements, $k^times$, is not only a group, but a cyclic group, and has a generator $g$, one of a (usually) large number of such. Now, if we call $(p-1)/n=d$, then $g^d$ generates a subgroup of order $(p-1)/d=n$, in other words, $g^d$ can be taken to be your $zeta_n$.
From here on, everything seems to take place in the subgroup $langle g^drangle=Tsubset k^times$ of order $n$. In the same way as above, if $m|n$, then the $m$-th roots of $1$ in $k^times$ form a (cyclic) subgroup of $T$ of order $m$, and if $xi$ is a generator of this group, then ${1,xi,cdotsxi^{m-1}}$ form one of your sets $S$, since their sum is $(xi^m-1)/(xi-1)=0$. In particular, if $m$ is prime, you have a set of your type $S$ of cardinality $m$. I’d like to state with assurance that if you let $m$ be the smallest prime dividing $n$, then this set satisfies your minimality demand. But I’m unsure.
Certainly if $3$ is the smallest prime dividing $n$, then the group of cube roots of $1$ in $k$ is contained in $T$ and is minimal, since there is no $S$-set with only two elements, because $n$ is assumed even. So, of the two examples you offered in your comment, the first is easy: there’s an $S$ with $3$ elements, and no smaller nonempty such set. The second example catches me exactly where I’m on shakiest ground, since $307$ is prime. If my guess is correct, the only $S$-set here is $T$ itself.
EDIT — Amendment:
Your single example of elements of $Bbb F_{53}$, $1+24+28equiv0pmod{53}$, where all three summands are $13$-th roots of unity, shows that I was certainly wrong in stating that this is not a hard problem. Further, I may have said it only in comments, but I was wrong to state that the containing field $Bbb F_p$ was immaterial to the problem.
Perhaps I was looking through the wrong end of the telescope. If one looks even at the simplest case of your problem, to find three elements summing to zero in the (unique) subgroup of order $n$ in $Bbb F_p^times$ where necessarily $n|(p-1)$, then you can attack it in the following way, which makes my arguments seem particularly overoptimistic:
Once you normalize so that one of the elements of your triple is $1$, there’s a one-parameter family of triples adding to zero in $Bbb F_p$, namely ${1,a,-a-1}$. There is absolutely no reason why all three couldn’t lie in some proper subgroup of $Bbb F_p^times$, even with your restriction that this subgroup should be of odd order.
Unfortunately, I have no idea and no tools in my kit that could help you with this problem.
answered Jan 20 at 19:16
LubinLubin
44.7k44586
$endgroup$
$begingroup$
Hmmm... the set $T$ itself is always a trivial solution. I was more curious of nontrivial solutions $S⫋T$. That is, $S$ is a subset not equal to $T$ but a solution to the original problem. I just go along with the fact that there are exactly $2^n$ proper subsets of $T$.
$endgroup$
– J. Linne
Jan 21 at 20:10
$begingroup$
If $p<2^n$, then there should be at least one other subset $S$ (besides $T$) such that summing all the elements of $S$ is $0$. Therefore, we assume $p<2^n$ and one other non-trivial solution exists.
$endgroup$
– J. Linne
Jan 21 at 20:12
$begingroup$
In my examples with $n=105,163,$ and $307$, $p<2^n$, so there are more solutions than just $T$. It could be a problem related to the subset sum problem in finite fields.
$endgroup$
– J. Linne
Jan 21 at 20:15
$begingroup$
So sorry, of course I was being sloppy to say anything suggesting that the minimal set was unique. In the case $n=105$, for instance, the size of a minimal set will be $3$. I took as model the group of all cube roots of unity, call it $S_0$. Then if $zeta$ is any $10-5$-th root of unity, any $zeta S_0$ will also have three elements and have sum zero, so will satisfy your criteria.
$endgroup$
– Lubin
Jan 22 at 0:48
1
$begingroup$
Mersenne Primes $2^n-1$ seem to be a good example of this. For instance, $n=17$ and $p=2^13-1=8191$, $T=[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]$ and the only subset $S$ of $T$ such that all elements in $S$ sum to $0$ $pmod p$ is $T$ itself (good so far). Then I find if $p=53$ and $T=[1, 10, 13, 15, 16, 24, 28, 36, 42, 44, 46, 47, 49]$. Then $S=[1, 24, 28]$ is a proper subset of $T$ (that is not $T$ itself) with sum $0 pmod p$.
$endgroup$
– J. Linne
Jan 22 at 6:15
|
show 5 more comments
$begingroup$
I have a contribution, but not an answer; let’s see whether I can explain why I think this is not a hard problem.
You have your number $n$ and a larger prime $p$, satisfying $n|(p-1)$. Let’s denote the field of integers modulo $p$ by $k$. We know that the set of nonzero elements, $k^times$, is not only a group, but a cyclic group, and has a generator $g$, one of a (usually) large number of such. Now, if we call $(p-1)/n=d$, then $g^d$ generates a subgroup of order $(p-1)/d=n$, in other words, $g^d$ can be taken to be your $zeta_n$.
From here on, everything seems to take place in the subgroup $langle g^drangle=Tsubset k^times$ of order $n$. In the same way as above, if $m|n$, then the $m$-th roots of $1$ in $k^times$ form a (cyclic) subgroup of $T$ of order $m$, and if $xi$ is a generator of this group, then ${1,xi,cdotsxi^{m-1}}$ form one of your sets $S$, since their sum is $(xi^m-1)/(xi-1)=0$. In particular, if $m$ is prime, you have a set of your type $S$ of cardinality $m$. I’d like to state with assurance that if you let $m$ be the smallest prime dividing $n$, then this set satisfies your minimality demand. But I’m unsure.
Certainly if $3$ is the smallest prime dividing $n$, then the group of cube roots of $1$ in $k$ is contained in $T$ and is minimal, since there is no $S$-set with only two elements, because $n$ is assumed even. So, of the two examples you offered in your comment, the first is easy: there’s an $S$ with $3$ elements, and no smaller nonempty such set. The second example catches me exactly where I’m on shakiest ground, since $307$ is prime. If my guess is correct, the only $S$-set here is $T$ itself.
EDIT — Amendment:
Your single example of elements of $Bbb F_{53}$, $1+24+28equiv0pmod{53}$, where all three summands are $13$-th roots of unity, shows that I was certainly wrong in stating that this is not a hard problem. Further, I may have said it only in comments, but I was wrong to state that the containing field $Bbb F_p$ was immaterial to the problem.
Perhaps I was looking through the wrong end of the telescope. If one looks even at the simplest case of your problem, to find three elements summing to zero in the (unique) subgroup of order $n$ in $Bbb F_p^times$ where necessarily $n|(p-1)$, then you can attack it in the following way, which makes my arguments seem particularly overoptimistic:
Once you normalize so that one of the elements of your triple is $1$, there’s a one-parameter family of triples adding to zero in $Bbb F_p$, namely ${1,a,-a-1}$. There is absolutely no reason why all three couldn’t lie in some proper subgroup of $Bbb F_p^times$, even with your restriction that this subgroup should be of odd order.
Unfortunately, I have no idea and no tools in my kit that could help you with this problem.
answered Jan 20 at 19:16
LubinLubin
44.7k44586
$endgroup$
$begingroup$
Hmmm... the set $T$ itself is always a trivial solution. I was more curious of nontrivial solutions $S⫋T$. That is, $S$ is a subset not equal to $T$ but a solution to the original problem. I just go along with the fact that there are exactly $2^n$ proper subsets of $T$.
$endgroup$
– J. Linne
Jan 21 at 20:10
$begingroup$
If $p<2^n$, then there should be at least one other subset $S$ (besides $T$) such that summing all the elements of $S$ is $0$. Therefore, we assume $p<2^n$ and one other non-trivial solution exists.
$endgroup$
– J. Linne
Jan 21 at 20:12
$begingroup$
In my examples with $n=105,163,$ and $307$, $p<2^n$, so there are more solutions than just $T$. It could be a problem related to the subset sum problem in finite fields.
$endgroup$
– J. Linne
Jan 21 at 20:15
$begingroup$
So sorry, of course I was being sloppy to say anything suggesting that the minimal set was unique. In the case $n=105$, for instance, the size of a minimal set will be $3$. I took as model the group of all cube roots of unity, call it $S_0$. Then if $zeta$ is any $10-5$-th root of unity, any $zeta S_0$ will also have three elements and have sum zero, so will satisfy your criteria.
$endgroup$
– Lubin
Jan 22 at 0:48
1
$begingroup$
Mersenne Primes $2^n-1$ seem to be a good example of this. For instance, $n=17$ and $p=2^13-1=8191$, $T=[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]$ and the only subset $S$ of $T$ such that all elements in $S$ sum to $0$ $pmod p$ is $T$ itself (good so far). Then I find if $p=53$ and $T=[1, 10, 13, 15, 16, 24, 28, 36, 42, 44, 46, 47, 49]$. Then $S=[1, 24, 28]$ is a proper subset of $T$ (that is not $T$ itself) with sum $0 pmod p$.
$endgroup$
– J. Linne
Jan 22 at 6:15
|
show 5 more comments
$begingroup$
I have a contribution, but not an answer; let’s see whether I can explain why I think this is not a hard problem.
You have your number $n$ and a larger prime $p$, satisfying $n|(p-1)$. Let’s denote the field of integers modulo $p$ by $k$. We know that the set of nonzero elements, $k^times$, is not only a group, but a cyclic group, and has a generator $g$, one of a (usually) large number of such. Now, if we call $(p-1)/n=d$, then $g^d$ generates a subgroup of order $(p-1)/d=n$, in other words, $g^d$ can be taken to be your $zeta_n$.
From here on, everything seems to take place in the subgroup $langle g^drangle=Tsubset k^times$ of order $n$. In the same way as above, if $m|n$, then the $m$-th roots of $1$ in $k^times$ form a (cyclic) subgroup of $T$ of order $m$, and if $xi$ is a generator of this group, then ${1,xi,cdotsxi^{m-1}}$ form one of your sets $S$, since their sum is $(xi^m-1)/(xi-1)=0$. In particular, if $m$ is prime, you have a set of your type $S$ of cardinality $m$. I’d like to state with assurance that if you let $m$ be the smallest prime dividing $n$, then this set satisfies your minimality demand. But I’m unsure.
Certainly if $3$ is the smallest prime dividing $n$, then the group of cube roots of $1$ in $k$ is contained in $T$ and is minimal, since there is no $S$-set with only two elements, because $n$ is assumed even. So, of the two examples you offered in your comment, the first is easy: there’s an $S$ with $3$ elements, and no smaller nonempty such set. The second example catches me exactly where I’m on shakiest ground, since $307$ is prime. If my guess is correct, the only $S$-set here is $T$ itself.
EDIT — Amendment:
Your single example of elements of $Bbb F_{53}$, $1+24+28equiv0pmod{53}$, where all three summands are $13$-th roots of unity, shows that I was certainly wrong in stating that this is not a hard problem. Further, I may have said it only in comments, but I was wrong to state that the containing field $Bbb F_p$ was immaterial to the problem.
Perhaps I was looking through the wrong end of the telescope. If one looks even at the simplest case of your problem, to find three elements summing to zero in the (unique) subgroup of order $n$ in $Bbb F_p^times$ where necessarily $n|(p-1)$, then you can attack it in the following way, which makes my arguments seem particularly overoptimistic:
Once you normalize so that one of the elements of your triple is $1$, there’s a one-parameter family of triples adding to zero in $Bbb F_p$, namely ${1,a,-a-1}$. There is absolutely no reason why all three couldn’t lie in some proper subgroup of $Bbb F_p^times$, even with your restriction that this subgroup should be of odd order.
Unfortunately, I have no idea and no tools in my kit that could help you with this problem.
answered Jan 20 at 19:16
LubinLubin
44.7k44586
$endgroup$
I have a contribution, but not an answer; let’s see whether I can explain why I think this is not a hard problem.
You have your number $n$ and a larger prime $p$, satisfying $n|(p-1)$. Let’s denote the field of integers modulo $p$ by $k$. We know that the set of nonzero elements, $k^times$, is not only a group, but a cyclic group, and has a generator $g$, one of a (usually) large number of such. Now, if we call $(p-1)/n=d$, then $g^d$ generates a subgroup of order $(p-1)/d=n$, in other words, $g^d$ can be taken to be your $zeta_n$.
From here on, everything seems to take place in the subgroup $langle g^drangle=Tsubset k^times$ of order $n$. In the same way as above, if $m|n$, then the $m$-th roots of $1$ in $k^times$ form a (cyclic) subgroup of $T$ of order $m$, and if $xi$ is a generator of this group, then ${1,xi,cdotsxi^{m-1}}$ form one of your sets $S$, since their sum is $(xi^m-1)/(xi-1)=0$. In particular, if $m$ is prime, you have a set of your type $S$ of cardinality $m$. I’d like to state with assurance that if you let $m$ be the smallest prime dividing $n$, then this set satisfies your minimality demand. But I’m unsure.
Certainly if $3$ is the smallest prime dividing $n$, then the group of cube roots of $1$ in $k$ is contained in $T$ and is minimal, since there is no $S$-set with only two elements, because $n$ is assumed even. So, of the two examples you offered in your comment, the first is easy: there’s an $S$ with $3$ elements, and no smaller nonempty such set. The second example catches me exactly where I’m on shakiest ground, since $307$ is prime. If my guess is correct, the only $S$-set here is $T$ itself.
EDIT — Amendment:
Your single example of elements of $Bbb F_{53}$, $1+24+28equiv0pmod{53}$, where all three summands are $13$-th roots of unity, shows that I was certainly wrong in stating that this is not a hard problem. Further, I may have said it only in comments, but I was wrong to state that the containing field $Bbb F_p$ was immaterial to the problem.
Perhaps I was looking through the wrong end of the telescope. If one looks even at the simplest case of your problem, to find three elements summing to zero in the (unique) subgroup of order $n$ in $Bbb F_p^times$ where necessarily $n|(p-1)$, then you can attack it in the following way, which makes my arguments seem particularly overoptimistic:
Once you normalize so that one of the elements of your triple is $1$, there’s a one-parameter family of triples adding to zero in $Bbb F_p$, namely ${1,a,-a-1}$. There is absolutely no reason why all three couldn’t lie in some proper subgroup of $Bbb F_p^times$, even with your restriction that this subgroup should be of odd order.
Unfortunately, I have no idea and no tools in my kit that could help you with this problem.
answered Jan 20 at 19:16
LubinLubin
44.7k44586
edited Jan 23 at 4:22
answered Jan 20 at 19:16
LubinLubin
44.7k44586
answered Jan 20 at 19:16
LubinLubin
44.7k44586
answered Jan 20 at 19:16
LubinLubin
44.7k44586
44.7k44586
$begingroup$
Hmmm... the set $T$ itself is always a trivial solution. I was more curious of nontrivial solutions $S⫋T$. That is, $S$ is a subset not equal to $T$ but a solution to the original problem. I just go along with the fact that there are exactly $2^n$ proper subsets of $T$.
$endgroup$
– J. Linne
Jan 21 at 20:10
$begingroup$
If $p<2^n$, then there should be at least one other subset $S$ (besides $T$) such that summing all the elements of $S$ is $0$. Therefore, we assume $p<2^n$ and one other non-trivial solution exists.
$endgroup$
– J. Linne
Jan 21 at 20:12
$begingroup$
In my examples with $n=105,163,$ and $307$, $p<2^n$, so there are more solutions than just $T$. It could be a problem related to the subset sum problem in finite fields.
$endgroup$
– J. Linne
Jan 21 at 20:15
$begingroup$
So sorry, of course I was being sloppy to say anything suggesting that the minimal set was unique. In the case $n=105$, for instance, the size of a minimal set will be $3$. I took as model the group of all cube roots of unity, call it $S_0$. Then if $zeta$ is any $10-5$-th root of unity, any $zeta S_0$ will also have three elements and have sum zero, so will satisfy your criteria.
$endgroup$
– Lubin
Jan 22 at 0:48
1
$begingroup$
Mersenne Primes $2^n-1$ seem to be a good example of this. For instance, $n=17$ and $p=2^13-1=8191$, $T=[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]$ and the only subset $S$ of $T$ such that all elements in $S$ sum to $0$ $pmod p$ is $T$ itself (good so far). Then I find if $p=53$ and $T=[1, 10, 13, 15, 16, 24, 28, 36, 42, 44, 46, 47, 49]$. Then $S=[1, 24, 28]$ is a proper subset of $T$ (that is not $T$ itself) with sum $0 pmod p$.
$endgroup$
– J. Linne
Jan 22 at 6:15
|
show 5 more comments
$begingroup$
Hmmm... the set $T$ itself is always a trivial solution. I was more curious of nontrivial solutions $S⫋T$. That is, $S$ is a subset not equal to $T$ but a solution to the original problem. I just go along with the fact that there are exactly $2^n$ proper subsets of $T$.
$endgroup$
– J. Linne
Jan 21 at 20:10
$begingroup$
If $p<2^n$, then there should be at least one other subset $S$ (besides $T$) such that summing all the elements of $S$ is $0$. Therefore, we assume $p<2^n$ and one other non-trivial solution exists.
$endgroup$
– J. Linne
Jan 21 at 20:12
$begingroup$
In my examples with $n=105,163,$ and $307$, $p<2^n$, so there are more solutions than just $T$. It could be a problem related to the subset sum problem in finite fields.
$endgroup$
– J. Linne
Jan 21 at 20:15
$begingroup$
So sorry, of course I was being sloppy to say anything suggesting that the minimal set was unique. In the case $n=105$, for instance, the size of a minimal set will be $3$. I took as model the group of all cube roots of unity, call it $S_0$. Then if $zeta$ is any $10-5$-th root of unity, any $zeta S_0$ will also have three elements and have sum zero, so will satisfy your criteria.
$endgroup$
– Lubin
Jan 22 at 0:48
1
$begingroup$
Mersenne Primes $2^n-1$ seem to be a good example of this. For instance, $n=17$ and $p=2^13-1=8191$, $T=[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]$ and the only subset $S$ of $T$ such that all elements in $S$ sum to $0$ $pmod p$ is $T$ itself (good so far). Then I find if $p=53$ and $T=[1, 10, 13, 15, 16, 24, 28, 36, 42, 44, 46, 47, 49]$. Then $S=[1, 24, 28]$ is a proper subset of $T$ (that is not $T$ itself) with sum $0 pmod p$.
$endgroup$
– J. Linne
Jan 22 at 6:15
$begingroup$
Hmmm... the set $T$ itself is always a trivial solution. I was more curious of nontrivial solutions $S⫋T$. That is, $S$ is a subset not equal to $T$ but a solution to the original problem. I just go along with the fact that there are exactly $2^n$ proper subsets of $T$.
$endgroup$
– J. Linne
Jan 21 at 20:10
$begingroup$
Hmmm... the set $T$ itself is always a trivial solution. I was more curious of nontrivial solutions $S⫋T$. That is, $S$ is a subset not equal to $T$ but a solution to the original problem. I just go along with the fact that there are exactly $2^n$ proper subsets of $T$.
$endgroup$
– J. Linne
Jan 21 at 20:10
$begingroup$
If $p<2^n$, then there should be at least one other subset $S$ (besides $T$) such that summing all the elements of $S$ is $0$. Therefore, we assume $p<2^n$ and one other non-trivial solution exists.
$endgroup$
– J. Linne
Jan 21 at 20:12
$begingroup$
If $p<2^n$, then there should be at least one other subset $S$ (besides $T$) such that summing all the elements of $S$ is $0$. Therefore, we assume $p<2^n$ and one other non-trivial solution exists.
$endgroup$
– J. Linne
Jan 21 at 20:12
$begingroup$
In my examples with $n=105,163,$ and $307$, $p<2^n$, so there are more solutions than just $T$. It could be a problem related to the subset sum problem in finite fields.
$endgroup$
– J. Linne
Jan 21 at 20:15
$begingroup$
In my examples with $n=105,163,$ and $307$, $p<2^n$, so there are more solutions than just $T$. It could be a problem related to the subset sum problem in finite fields.
$endgroup$
– J. Linne
Jan 21 at 20:15
$begingroup$
So sorry, of course I was being sloppy to say anything suggesting that the minimal set was unique. In the case $n=105$, for instance, the size of a minimal set will be $3$. I took as model the group of all cube roots of unity, call it $S_0$. Then if $zeta$ is any $10-5$-th root of unity, any $zeta S_0$ will also have three elements and have sum zero, so will satisfy your criteria.
$endgroup$
– Lubin
Jan 22 at 0:48
$begingroup$
So sorry, of course I was being sloppy to say anything suggesting that the minimal set was unique. In the case $n=105$, for instance, the size of a minimal set will be $3$. I took as model the group of all cube roots of unity, call it $S_0$. Then if $zeta$ is any $10-5$-th root of unity, any $zeta S_0$ will also have three elements and have sum zero, so will satisfy your criteria.
$endgroup$
– Lubin
Jan 22 at 0:48
1
1
$begingroup$
Mersenne Primes $2^n-1$ seem to be a good example of this. For instance, $n=17$ and $p=2^13-1=8191$, $T=[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]$ and the only subset $S$ of $T$ such that all elements in $S$ sum to $0$ $pmod p$ is $T$ itself (good so far). Then I find if $p=53$ and $T=[1, 10, 13, 15, 16, 24, 28, 36, 42, 44, 46, 47, 49]$. Then $S=[1, 24, 28]$ is a proper subset of $T$ (that is not $T$ itself) with sum $0 pmod p$.
$endgroup$
– J. Linne
Jan 22 at 6:15
$begingroup$
Mersenne Primes $2^n-1$ seem to be a good example of this. For instance, $n=17$ and $p=2^13-1=8191$, $T=[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096]$ and the only subset $S$ of $T$ such that all elements in $S$ sum to $0$ $pmod p$ is $T$ itself (good so far). Then I find if $p=53$ and $T=[1, 10, 13, 15, 16, 24, 28, 36, 42, 44, 46, 47, 49]$. Then $S=[1, 24, 28]$ is a proper subset of $T$ (that is not $T$ itself) with sum $0 pmod p$.
$endgroup$
– J. Linne
Jan 22 at 6:15
|
show 5 more comments
Thanks for contributing an answer to Mathematics Stack Exchange!
- 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.
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%2fmath.stackexchange.com%2fquestions%2f3077874%2froots-of-unity-group-theory%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
3
$begingroup$
I find it difficult to believe that anything as hifalutin as LLL could be the right way to go. But is $n$ supposed to be prime to $p$? And where are these roots of unity? Are you looking only within $Bbb F_p=Bbb Z/pBbb Z$? Or are you starting with roots of unity as algebraic numbers, which you then want to look at in characteristic $p$ somehow?
$endgroup$
– Lubin
Jan 18 at 6:30
$begingroup$
The smallest subset such that the sum is $0$ is always $S=varnothing$. If $q$ is the smallest prime dividing $n$, then the powers of $zeta_n^{n/q}$ yield a set of size $q$. But to say more, it would help to clarify where these roots of unity are from.
$endgroup$
– Servaes
Jan 18 at 10:30
$begingroup$
@Lubin yes, working in $mathbb Z/pmathbb Z$. With $p=1pmod n$, the elements in $S$ are the $n$-th roots of unity $pmod p$. Then find a non-empty subset of $S$ whos sum is $0$.
$endgroup$
– J. Linne
Jan 19 at 2:55
$begingroup$
Then have you looked at the case $n=9$, $p=37$? Or at the case $n=105$, $p=211$? Now that I understand your setup, the problem looks not at all deep to me.
$endgroup$
– Lubin
Jan 19 at 22:59
2
$begingroup$
By length of $S$ do you mean just its cardinality, or the difference from the first included exponent to the last? Anyway, this is a bit like a modular knapsack problem, probably why you thought of LLL.
$endgroup$
– Jyrki Lahtonen
Jan 23 at 4:53