Mixing
Understanding Gauss's product formula as cited in Golomb's Shift Register Sequences
Clash Royale CLAN TAG#URR8PPP
up vote
6
down vote
favorite
In his book Shift Register Sequences, Solomon Golomb refers to "Gauss's product formula":
The basic device here is “Gauss's product formula†[39] which expresses the “product†of any two cosets as a sum of cosets. (This "product" is in terms of evaluation with 1's and 0's. It has nothing to do with multiplication in the factor group.)
I'm completely lost. What is he talking about? The cosets here in Golomb's example are cyclotomic cosets $bmod 2^N - 1$ for $N=5$, with
$$beginalign
C_0 &= 1,2,4,8,16 cr
C_1 &= 3,6,12,24,17 cr
C_2 &= 9,18,5,10,20 cr
C_3 &= 27,23,15,30,29 cr
C_4 &= 19,7,14,28,25 cr
C_5 &= 26,21,11,22,13
endalign$$
I understand what these cosets are (elements in the same coset are produced by multiplying by powers of 2, $bmod 2^N-1$), but how can you possibly "multiply" or "add" them, and write equations regarding $C_iC_j$?
abstract-algebra finite-fields
asked Jul 15 at 17:38
Jason S
1,90611617
add a comment |Â
up vote
6
down vote
favorite
In his book Shift Register Sequences, Solomon Golomb refers to "Gauss's product formula":
The basic device here is “Gauss's product formula†[39] which expresses the “product†of any two cosets as a sum of cosets. (This "product" is in terms of evaluation with 1's and 0's. It has nothing to do with multiplication in the factor group.)
I'm completely lost. What is he talking about? The cosets here in Golomb's example are cyclotomic cosets $bmod 2^N - 1$ for $N=5$, with
$$beginalign
C_0 &= 1,2,4,8,16 cr
C_1 &= 3,6,12,24,17 cr
C_2 &= 9,18,5,10,20 cr
C_3 &= 27,23,15,30,29 cr
C_4 &= 19,7,14,28,25 cr
C_5 &= 26,21,11,22,13
endalign$$
I understand what these cosets are (elements in the same coset are produced by multiplying by powers of 2, $bmod 2^N-1$), but how can you possibly "multiply" or "add" them, and write equations regarding $C_iC_j$?
abstract-algebra finite-fields
asked Jul 15 at 17:38
Jason S
1,90611617
add a comment |Â
up vote
6
down vote
favorite
up vote
6
down vote
favorite
In his book Shift Register Sequences, Solomon Golomb refers to "Gauss's product formula":
The basic device here is “Gauss's product formula†[39] which expresses the “product†of any two cosets as a sum of cosets. (This "product" is in terms of evaluation with 1's and 0's. It has nothing to do with multiplication in the factor group.)
I'm completely lost. What is he talking about? The cosets here in Golomb's example are cyclotomic cosets $bmod 2^N - 1$ for $N=5$, with
$$beginalign
C_0 &= 1,2,4,8,16 cr
C_1 &= 3,6,12,24,17 cr
C_2 &= 9,18,5,10,20 cr
C_3 &= 27,23,15,30,29 cr
C_4 &= 19,7,14,28,25 cr
C_5 &= 26,21,11,22,13
endalign$$
I understand what these cosets are (elements in the same coset are produced by multiplying by powers of 2, $bmod 2^N-1$), but how can you possibly "multiply" or "add" them, and write equations regarding $C_iC_j$?
abstract-algebra finite-fields
asked Jul 15 at 17:38
Jason S
1,90611617
In his book Shift Register Sequences, Solomon Golomb refers to "Gauss's product formula":
The basic device here is “Gauss's product formula†[39] which expresses the “product†of any two cosets as a sum of cosets. (This "product" is in terms of evaluation with 1's and 0's. It has nothing to do with multiplication in the factor group.)
I'm completely lost. What is he talking about? The cosets here in Golomb's example are cyclotomic cosets $bmod 2^N - 1$ for $N=5$, with
$$beginalign
C_0 &= 1,2,4,8,16 cr
C_1 &= 3,6,12,24,17 cr
C_2 &= 9,18,5,10,20 cr
C_3 &= 27,23,15,30,29 cr
C_4 &= 19,7,14,28,25 cr
C_5 &= 26,21,11,22,13
endalign$$
I understand what these cosets are (elements in the same coset are produced by multiplying by powers of 2, $bmod 2^N-1$), but how can you possibly "multiply" or "add" them, and write equations regarding $C_iC_j$?
abstract-algebra finite-fields
asked Jul 15 at 17:38
Jason S
1,90611617
asked Jul 15 at 17:38
Jason S
1,90611617
asked Jul 15 at 17:38
Jason S
1,90611617
asked Jul 15 at 17:38
Jason S
1,90611617
1,90611617
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
3
down vote
accepted
My guess is that Golomb wanted to avoid use of structures from abstract algebra. I would describe this product as follows. If you reach the end you may understand why Golomb wanted to use his simpler description! I do this anyway because this gives us many nice properties of the product (proving e.g. associativity may not be obvious otherwise).
All these arithmetic operations take place in the quotient ring of polynomials with coefficients in $BbbF_2$. When dealing with cyclotomic cosets modulo $m$ (an odd natural number) we use the ring
$$
R_m:=BbbF_2[x]/(x^m-1).
$$
You may have seen this ring used when studying cyclic codes of length $m$ also. Anyway, we view a cyclotomic coset modulo $m$ as an element of $R_m$.
If $C$ is such a cyclotomic coset, we can think of it as the polynomial $C(x)$ defined simply as
$$
C(x)=sum_iin Cx^i.
$$
So for example in $R_31$ we have
$$
C_0(x)=x+x^2+x^4+x^8+x^16
$$
and
$$
C_1(x)=x^3+x^6+x^12+x^24+x^17.
$$
When you multiply those polynomials in the ring $R_31$ you multiply them almost like usual polynomials. 1) You need to keep in mind that the arithmetic of the coefficients is done modulo two. 2) You also need to keep in mind that the arithmetic of exponents is done modulo $m$. So here for example
$$
x^16cdot x^17=x^16+17=x^33=x^31+2=x^2.
$$
Taking the quotient by $x^31-1$ does exactly that: equating $x^31$ with $1$, $x^32$ with $x$ et cetera.
On with the example. When we calculate the product $C_0(x)cdot C_1(x)$ we get first
$$
beginaligned
&left(x^16+x^8+x^4+x^2+xright) left(x^24+x^17+x^12+x^6+x^3right)\
=&x^40+x^33+x^32+2 x^28+x^26+2 x^25+x^22+x^21+x^20+2 x^19+x^18+x^16+2
x^14+x^13+x^11+x^10+x^8+2 x^7+x^5+x^4.
endaligned
$$
Reducing the exponents modulo $31$ gives
$$
2 x^28+x^26+2 x^25+x^22+x^21+x^20+2 x^19+x^18+x^16+2
x^14+x^13+x^11+x^10+x^9+x^8+2 x^7+x^5+x^4+x^2+x.
$$
As the finishing touch we then reduce the coefficients modulo two, and get the result:
$$
x^26+x^22+x^21+x^20+x^18+x^16+x^13+x^11+x^10+x^9+x^8+x^5+x^4+x^2+x.
$$
You see that this is the sum
$$C_0(x)+C_2(x)+C_5(x)$$
as promised.
I introduced a lot extra baggage. This does help if you do research with these things. I trust Golomb to have known his customers, and done what he viewed best pedagogically.
answered Jul 15 at 20:34
Jyrki Lahtonen
105k12161355
<strike>ok, so "sum" refers to the union of elements then?</strike> oh, never mind, it's representing them as polynomials. Got it. Thanks!
– Jason S
Jul 15 at 21:57
add a comment |Â
up vote
4
down vote
The first rule of mod $2$ is that $, x + x = 0 ,$ for all $,x.,$ Applying this to the given Golomb example:
$, C_ 0 C_ 1 = C_ 0 + C_ 4 + C_ 5 + C_ 4 + C_ 2 = C_0 + C_2 + C_5 + (C_4 + C_4) = C_0 + C_2 + C_5 pmod2.$
Your question about multiplying or adding cosets is answered explicitly by Golomb himself. He gave the rule for multiplying two cosets to get a sum of cosets. The addition is "formal" addition of cosets except he introduces the "mod $2$" rule. Thus every sum of cosets simplifies to a sum of distinct cosets. These concrete rules are ultimately derived from more abstract and general rules.
For example, in finite group theory, a multiplication operation is defined on conjugacy classes where the product of two conjugacy classes is the formal sum of conjugacy classes with positive integer multiplicity coefficients in case a conjugacy class appears more than once in the formal sum.
The general question of how we can perform operations called "addition" and "multiplication" on general objects is that we can give abstract rules about how these operations are performed and rules about how to determine equality between objects. This is the domain of "abstract algebra".
answered Jul 15 at 19:53
Somos
11.7k1933
But for addition, how do you know which members to add? Is $C_0 = 1+3, 2+6, 4+12, 8+24, 16+17$ ?
– Jason S
Jul 15 at 21:56
Do you understand Golomb's equation $(11)$?
– Somos
Jul 15 at 22:02
Not really. His example produces $4,7,13,25,18$ which belongs to $C_0, C_2, C_4, C_5$ and I don't get how he concludes this is $C_0 + C_2 + C_5$ (what happened to $C_4$?)
– Jason S
Jul 15 at 22:07
Did you read the part of Golomb's example just before equation $(12)$ and the first paragraph of my answer?
– Somos
Jul 15 at 22:14
OH -- the light finally went on, so because $C_4$ appears twice, it cancels itself out.
– Jason S
Jul 15 at 22:23
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
accepted
My guess is that Golomb wanted to avoid use of structures from abstract algebra. I would describe this product as follows. If you reach the end you may understand why Golomb wanted to use his simpler description! I do this anyway because this gives us many nice properties of the product (proving e.g. associativity may not be obvious otherwise).
All these arithmetic operations take place in the quotient ring of polynomials with coefficients in $BbbF_2$. When dealing with cyclotomic cosets modulo $m$ (an odd natural number) we use the ring
$$
R_m:=BbbF_2[x]/(x^m-1).
$$
You may have seen this ring used when studying cyclic codes of length $m$ also. Anyway, we view a cyclotomic coset modulo $m$ as an element of $R_m$.
If $C$ is such a cyclotomic coset, we can think of it as the polynomial $C(x)$ defined simply as
$$
C(x)=sum_iin Cx^i.
$$
So for example in $R_31$ we have
$$
C_0(x)=x+x^2+x^4+x^8+x^16
$$
and
$$
C_1(x)=x^3+x^6+x^12+x^24+x^17.
$$
When you multiply those polynomials in the ring $R_31$ you multiply them almost like usual polynomials. 1) You need to keep in mind that the arithmetic of the coefficients is done modulo two. 2) You also need to keep in mind that the arithmetic of exponents is done modulo $m$. So here for example
$$
x^16cdot x^17=x^16+17=x^33=x^31+2=x^2.
$$
Taking the quotient by $x^31-1$ does exactly that: equating $x^31$ with $1$, $x^32$ with $x$ et cetera.
On with the example. When we calculate the product $C_0(x)cdot C_1(x)$ we get first
$$
beginaligned
&left(x^16+x^8+x^4+x^2+xright) left(x^24+x^17+x^12+x^6+x^3right)\
=&x^40+x^33+x^32+2 x^28+x^26+2 x^25+x^22+x^21+x^20+2 x^19+x^18+x^16+2
x^14+x^13+x^11+x^10+x^8+2 x^7+x^5+x^4.
endaligned
$$
Reducing the exponents modulo $31$ gives
$$
2 x^28+x^26+2 x^25+x^22+x^21+x^20+2 x^19+x^18+x^16+2
x^14+x^13+x^11+x^10+x^9+x^8+2 x^7+x^5+x^4+x^2+x.
$$
As the finishing touch we then reduce the coefficients modulo two, and get the result:
$$
x^26+x^22+x^21+x^20+x^18+x^16+x^13+x^11+x^10+x^9+x^8+x^5+x^4+x^2+x.
$$
You see that this is the sum
$$C_0(x)+C_2(x)+C_5(x)$$
as promised.
I introduced a lot extra baggage. This does help if you do research with these things. I trust Golomb to have known his customers, and done what he viewed best pedagogically.
answered Jul 15 at 20:34
Jyrki Lahtonen
105k12161355
<strike>ok, so "sum" refers to the union of elements then?</strike> oh, never mind, it's representing them as polynomials. Got it. Thanks!
– Jason S
Jul 15 at 21:57
add a comment |Â
up vote
3
down vote
accepted
My guess is that Golomb wanted to avoid use of structures from abstract algebra. I would describe this product as follows. If you reach the end you may understand why Golomb wanted to use his simpler description! I do this anyway because this gives us many nice properties of the product (proving e.g. associativity may not be obvious otherwise).
All these arithmetic operations take place in the quotient ring of polynomials with coefficients in $BbbF_2$. When dealing with cyclotomic cosets modulo $m$ (an odd natural number) we use the ring
$$
R_m:=BbbF_2[x]/(x^m-1).
$$
You may have seen this ring used when studying cyclic codes of length $m$ also. Anyway, we view a cyclotomic coset modulo $m$ as an element of $R_m$.
If $C$ is such a cyclotomic coset, we can think of it as the polynomial $C(x)$ defined simply as
$$
C(x)=sum_iin Cx^i.
$$
So for example in $R_31$ we have
$$
C_0(x)=x+x^2+x^4+x^8+x^16
$$
and
$$
C_1(x)=x^3+x^6+x^12+x^24+x^17.
$$
When you multiply those polynomials in the ring $R_31$ you multiply them almost like usual polynomials. 1) You need to keep in mind that the arithmetic of the coefficients is done modulo two. 2) You also need to keep in mind that the arithmetic of exponents is done modulo $m$. So here for example
$$
x^16cdot x^17=x^16+17=x^33=x^31+2=x^2.
$$
Taking the quotient by $x^31-1$ does exactly that: equating $x^31$ with $1$, $x^32$ with $x$ et cetera.
On with the example. When we calculate the product $C_0(x)cdot C_1(x)$ we get first
$$
beginaligned
&left(x^16+x^8+x^4+x^2+xright) left(x^24+x^17+x^12+x^6+x^3right)\
=&x^40+x^33+x^32+2 x^28+x^26+2 x^25+x^22+x^21+x^20+2 x^19+x^18+x^16+2
x^14+x^13+x^11+x^10+x^8+2 x^7+x^5+x^4.
endaligned
$$
Reducing the exponents modulo $31$ gives
$$
2 x^28+x^26+2 x^25+x^22+x^21+x^20+2 x^19+x^18+x^16+2
x^14+x^13+x^11+x^10+x^9+x^8+2 x^7+x^5+x^4+x^2+x.
$$
As the finishing touch we then reduce the coefficients modulo two, and get the result:
$$
x^26+x^22+x^21+x^20+x^18+x^16+x^13+x^11+x^10+x^9+x^8+x^5+x^4+x^2+x.
$$
You see that this is the sum
$$C_0(x)+C_2(x)+C_5(x)$$
as promised.
I introduced a lot extra baggage. This does help if you do research with these things. I trust Golomb to have known his customers, and done what he viewed best pedagogically.
answered Jul 15 at 20:34
Jyrki Lahtonen
105k12161355
<strike>ok, so "sum" refers to the union of elements then?</strike> oh, never mind, it's representing them as polynomials. Got it. Thanks!
– Jason S
Jul 15 at 21:57
add a comment |Â
up vote
3
down vote
accepted
up vote
3
down vote
accepted
My guess is that Golomb wanted to avoid use of structures from abstract algebra. I would describe this product as follows. If you reach the end you may understand why Golomb wanted to use his simpler description! I do this anyway because this gives us many nice properties of the product (proving e.g. associativity may not be obvious otherwise).
All these arithmetic operations take place in the quotient ring of polynomials with coefficients in $BbbF_2$. When dealing with cyclotomic cosets modulo $m$ (an odd natural number) we use the ring
$$
R_m:=BbbF_2[x]/(x^m-1).
$$
You may have seen this ring used when studying cyclic codes of length $m$ also. Anyway, we view a cyclotomic coset modulo $m$ as an element of $R_m$.
If $C$ is such a cyclotomic coset, we can think of it as the polynomial $C(x)$ defined simply as
$$
C(x)=sum_iin Cx^i.
$$
So for example in $R_31$ we have
$$
C_0(x)=x+x^2+x^4+x^8+x^16
$$
and
$$
C_1(x)=x^3+x^6+x^12+x^24+x^17.
$$
When you multiply those polynomials in the ring $R_31$ you multiply them almost like usual polynomials. 1) You need to keep in mind that the arithmetic of the coefficients is done modulo two. 2) You also need to keep in mind that the arithmetic of exponents is done modulo $m$. So here for example
$$
x^16cdot x^17=x^16+17=x^33=x^31+2=x^2.
$$
Taking the quotient by $x^31-1$ does exactly that: equating $x^31$ with $1$, $x^32$ with $x$ et cetera.
On with the example. When we calculate the product $C_0(x)cdot C_1(x)$ we get first
$$
beginaligned
&left(x^16+x^8+x^4+x^2+xright) left(x^24+x^17+x^12+x^6+x^3right)\
=&x^40+x^33+x^32+2 x^28+x^26+2 x^25+x^22+x^21+x^20+2 x^19+x^18+x^16+2
x^14+x^13+x^11+x^10+x^8+2 x^7+x^5+x^4.
endaligned
$$
Reducing the exponents modulo $31$ gives
$$
2 x^28+x^26+2 x^25+x^22+x^21+x^20+2 x^19+x^18+x^16+2
x^14+x^13+x^11+x^10+x^9+x^8+2 x^7+x^5+x^4+x^2+x.
$$
As the finishing touch we then reduce the coefficients modulo two, and get the result:
$$
x^26+x^22+x^21+x^20+x^18+x^16+x^13+x^11+x^10+x^9+x^8+x^5+x^4+x^2+x.
$$
You see that this is the sum
$$C_0(x)+C_2(x)+C_5(x)$$
as promised.
I introduced a lot extra baggage. This does help if you do research with these things. I trust Golomb to have known his customers, and done what he viewed best pedagogically.
answered Jul 15 at 20:34
Jyrki Lahtonen
105k12161355
My guess is that Golomb wanted to avoid use of structures from abstract algebra. I would describe this product as follows. If you reach the end you may understand why Golomb wanted to use his simpler description! I do this anyway because this gives us many nice properties of the product (proving e.g. associativity may not be obvious otherwise).
All these arithmetic operations take place in the quotient ring of polynomials with coefficients in $BbbF_2$. When dealing with cyclotomic cosets modulo $m$ (an odd natural number) we use the ring
$$
R_m:=BbbF_2[x]/(x^m-1).
$$
You may have seen this ring used when studying cyclic codes of length $m$ also. Anyway, we view a cyclotomic coset modulo $m$ as an element of $R_m$.
If $C$ is such a cyclotomic coset, we can think of it as the polynomial $C(x)$ defined simply as
$$
C(x)=sum_iin Cx^i.
$$
So for example in $R_31$ we have
$$
C_0(x)=x+x^2+x^4+x^8+x^16
$$
and
$$
C_1(x)=x^3+x^6+x^12+x^24+x^17.
$$
When you multiply those polynomials in the ring $R_31$ you multiply them almost like usual polynomials. 1) You need to keep in mind that the arithmetic of the coefficients is done modulo two. 2) You also need to keep in mind that the arithmetic of exponents is done modulo $m$. So here for example
$$
x^16cdot x^17=x^16+17=x^33=x^31+2=x^2.
$$
Taking the quotient by $x^31-1$ does exactly that: equating $x^31$ with $1$, $x^32$ with $x$ et cetera.
On with the example. When we calculate the product $C_0(x)cdot C_1(x)$ we get first
$$
beginaligned
&left(x^16+x^8+x^4+x^2+xright) left(x^24+x^17+x^12+x^6+x^3right)\
=&x^40+x^33+x^32+2 x^28+x^26+2 x^25+x^22+x^21+x^20+2 x^19+x^18+x^16+2
x^14+x^13+x^11+x^10+x^8+2 x^7+x^5+x^4.
endaligned
$$
Reducing the exponents modulo $31$ gives
$$
2 x^28+x^26+2 x^25+x^22+x^21+x^20+2 x^19+x^18+x^16+2
x^14+x^13+x^11+x^10+x^9+x^8+2 x^7+x^5+x^4+x^2+x.
$$
As the finishing touch we then reduce the coefficients modulo two, and get the result:
$$
x^26+x^22+x^21+x^20+x^18+x^16+x^13+x^11+x^10+x^9+x^8+x^5+x^4+x^2+x.
$$
You see that this is the sum
$$C_0(x)+C_2(x)+C_5(x)$$
as promised.
I introduced a lot extra baggage. This does help if you do research with these things. I trust Golomb to have known his customers, and done what he viewed best pedagogically.
answered Jul 15 at 20:34
Jyrki Lahtonen
105k12161355
answered Jul 15 at 20:34
Jyrki Lahtonen
105k12161355
answered Jul 15 at 20:34
Jyrki Lahtonen
105k12161355
answered Jul 15 at 20:34
Jyrki Lahtonen
105k12161355
105k12161355
<strike>ok, so "sum" refers to the union of elements then?</strike> oh, never mind, it's representing them as polynomials. Got it. Thanks!
– Jason S
Jul 15 at 21:57
add a comment |Â
<strike>ok, so "sum" refers to the union of elements then?</strike> oh, never mind, it's representing them as polynomials. Got it. Thanks!
– Jason S
Jul 15 at 21:57
<strike>ok, so "sum" refers to the union of elements then?</strike> oh, never mind, it's representing them as polynomials. Got it. Thanks!
– Jason S
Jul 15 at 21:57
<strike>ok, so "sum" refers to the union of elements then?</strike> oh, never mind, it's representing them as polynomials. Got it. Thanks!
– Jason S
Jul 15 at 21:57
add a comment |Â
up vote
4
down vote
The first rule of mod $2$ is that $, x + x = 0 ,$ for all $,x.,$ Applying this to the given Golomb example:
$, C_ 0 C_ 1 = C_ 0 + C_ 4 + C_ 5 + C_ 4 + C_ 2 = C_0 + C_2 + C_5 + (C_4 + C_4) = C_0 + C_2 + C_5 pmod2.$
Your question about multiplying or adding cosets is answered explicitly by Golomb himself. He gave the rule for multiplying two cosets to get a sum of cosets. The addition is "formal" addition of cosets except he introduces the "mod $2$" rule. Thus every sum of cosets simplifies to a sum of distinct cosets. These concrete rules are ultimately derived from more abstract and general rules.
For example, in finite group theory, a multiplication operation is defined on conjugacy classes where the product of two conjugacy classes is the formal sum of conjugacy classes with positive integer multiplicity coefficients in case a conjugacy class appears more than once in the formal sum.
The general question of how we can perform operations called "addition" and "multiplication" on general objects is that we can give abstract rules about how these operations are performed and rules about how to determine equality between objects. This is the domain of "abstract algebra".
answered Jul 15 at 19:53
Somos
11.7k1933
But for addition, how do you know which members to add? Is $C_0 = 1+3, 2+6, 4+12, 8+24, 16+17$ ?
– Jason S
Jul 15 at 21:56
Do you understand Golomb's equation $(11)$?
– Somos
Jul 15 at 22:02
Not really. His example produces $4,7,13,25,18$ which belongs to $C_0, C_2, C_4, C_5$ and I don't get how he concludes this is $C_0 + C_2 + C_5$ (what happened to $C_4$?)
– Jason S
Jul 15 at 22:07
Did you read the part of Golomb's example just before equation $(12)$ and the first paragraph of my answer?
– Somos
Jul 15 at 22:14
OH -- the light finally went on, so because $C_4$ appears twice, it cancels itself out.
– Jason S
Jul 15 at 22:23
add a comment |Â
up vote
4
down vote
The first rule of mod $2$ is that $, x + x = 0 ,$ for all $,x.,$ Applying this to the given Golomb example:
$, C_ 0 C_ 1 = C_ 0 + C_ 4 + C_ 5 + C_ 4 + C_ 2 = C_0 + C_2 + C_5 + (C_4 + C_4) = C_0 + C_2 + C_5 pmod2.$
Your question about multiplying or adding cosets is answered explicitly by Golomb himself. He gave the rule for multiplying two cosets to get a sum of cosets. The addition is "formal" addition of cosets except he introduces the "mod $2$" rule. Thus every sum of cosets simplifies to a sum of distinct cosets. These concrete rules are ultimately derived from more abstract and general rules.
For example, in finite group theory, a multiplication operation is defined on conjugacy classes where the product of two conjugacy classes is the formal sum of conjugacy classes with positive integer multiplicity coefficients in case a conjugacy class appears more than once in the formal sum.
The general question of how we can perform operations called "addition" and "multiplication" on general objects is that we can give abstract rules about how these operations are performed and rules about how to determine equality between objects. This is the domain of "abstract algebra".
answered Jul 15 at 19:53
Somos
11.7k1933
But for addition, how do you know which members to add? Is $C_0 = 1+3, 2+6, 4+12, 8+24, 16+17$ ?
– Jason S
Jul 15 at 21:56
Do you understand Golomb's equation $(11)$?
– Somos
Jul 15 at 22:02
Not really. His example produces $4,7,13,25,18$ which belongs to $C_0, C_2, C_4, C_5$ and I don't get how he concludes this is $C_0 + C_2 + C_5$ (what happened to $C_4$?)
– Jason S
Jul 15 at 22:07
Did you read the part of Golomb's example just before equation $(12)$ and the first paragraph of my answer?
– Somos
Jul 15 at 22:14
OH -- the light finally went on, so because $C_4$ appears twice, it cancels itself out.
– Jason S
Jul 15 at 22:23
add a comment |Â
up vote
4
down vote
up vote
4
down vote
The first rule of mod $2$ is that $, x + x = 0 ,$ for all $,x.,$ Applying this to the given Golomb example:
$, C_ 0 C_ 1 = C_ 0 + C_ 4 + C_ 5 + C_ 4 + C_ 2 = C_0 + C_2 + C_5 + (C_4 + C_4) = C_0 + C_2 + C_5 pmod2.$
Your question about multiplying or adding cosets is answered explicitly by Golomb himself. He gave the rule for multiplying two cosets to get a sum of cosets. The addition is "formal" addition of cosets except he introduces the "mod $2$" rule. Thus every sum of cosets simplifies to a sum of distinct cosets. These concrete rules are ultimately derived from more abstract and general rules.
For example, in finite group theory, a multiplication operation is defined on conjugacy classes where the product of two conjugacy classes is the formal sum of conjugacy classes with positive integer multiplicity coefficients in case a conjugacy class appears more than once in the formal sum.
The general question of how we can perform operations called "addition" and "multiplication" on general objects is that we can give abstract rules about how these operations are performed and rules about how to determine equality between objects. This is the domain of "abstract algebra".
answered Jul 15 at 19:53
Somos
11.7k1933
The first rule of mod $2$ is that $, x + x = 0 ,$ for all $,x.,$ Applying this to the given Golomb example:
$, C_ 0 C_ 1 = C_ 0 + C_ 4 + C_ 5 + C_ 4 + C_ 2 = C_0 + C_2 + C_5 + (C_4 + C_4) = C_0 + C_2 + C_5 pmod2.$
Your question about multiplying or adding cosets is answered explicitly by Golomb himself. He gave the rule for multiplying two cosets to get a sum of cosets. The addition is "formal" addition of cosets except he introduces the "mod $2$" rule. Thus every sum of cosets simplifies to a sum of distinct cosets. These concrete rules are ultimately derived from more abstract and general rules.
For example, in finite group theory, a multiplication operation is defined on conjugacy classes where the product of two conjugacy classes is the formal sum of conjugacy classes with positive integer multiplicity coefficients in case a conjugacy class appears more than once in the formal sum.
The general question of how we can perform operations called "addition" and "multiplication" on general objects is that we can give abstract rules about how these operations are performed and rules about how to determine equality between objects. This is the domain of "abstract algebra".
answered Jul 15 at 19:53
Somos
11.7k1933
edited Jul 15 at 22:30
answered Jul 15 at 19:53
Somos
11.7k1933
answered Jul 15 at 19:53
Somos
11.7k1933
answered Jul 15 at 19:53
Somos
11.7k1933
11.7k1933
But for addition, how do you know which members to add? Is $C_0 = 1+3, 2+6, 4+12, 8+24, 16+17$ ?
– Jason S
Jul 15 at 21:56
Do you understand Golomb's equation $(11)$?
– Somos
Jul 15 at 22:02
Not really. His example produces $4,7,13,25,18$ which belongs to $C_0, C_2, C_4, C_5$ and I don't get how he concludes this is $C_0 + C_2 + C_5$ (what happened to $C_4$?)
– Jason S
Jul 15 at 22:07
Did you read the part of Golomb's example just before equation $(12)$ and the first paragraph of my answer?
– Somos
Jul 15 at 22:14
OH -- the light finally went on, so because $C_4$ appears twice, it cancels itself out.
– Jason S
Jul 15 at 22:23
add a comment |Â
But for addition, how do you know which members to add? Is $C_0 = 1+3, 2+6, 4+12, 8+24, 16+17$ ?
– Jason S
Jul 15 at 21:56
Do you understand Golomb's equation $(11)$?
– Somos
Jul 15 at 22:02
Not really. His example produces $4,7,13,25,18$ which belongs to $C_0, C_2, C_4, C_5$ and I don't get how he concludes this is $C_0 + C_2 + C_5$ (what happened to $C_4$?)
– Jason S
Jul 15 at 22:07
Did you read the part of Golomb's example just before equation $(12)$ and the first paragraph of my answer?
– Somos
Jul 15 at 22:14
OH -- the light finally went on, so because $C_4$ appears twice, it cancels itself out.
– Jason S
Jul 15 at 22:23
But for addition, how do you know which members to add? Is $C_0 = 1+3, 2+6, 4+12, 8+24, 16+17$ ?
– Jason S
Jul 15 at 21:56
But for addition, how do you know which members to add? Is $C_0 = 1+3, 2+6, 4+12, 8+24, 16+17$ ?
– Jason S
Jul 15 at 21:56
Do you understand Golomb's equation $(11)$?
– Somos
Jul 15 at 22:02
Do you understand Golomb's equation $(11)$?
– Somos
Jul 15 at 22:02
Not really. His example produces $4,7,13,25,18$ which belongs to $C_0, C_2, C_4, C_5$ and I don't get how he concludes this is $C_0 + C_2 + C_5$ (what happened to $C_4$?)
– Jason S
Jul 15 at 22:07
Not really. His example produces $4,7,13,25,18$ which belongs to $C_0, C_2, C_4, C_5$ and I don't get how he concludes this is $C_0 + C_2 + C_5$ (what happened to $C_4$?)
– Jason S
Jul 15 at 22:07
Did you read the part of Golomb's example just before equation $(12)$ and the first paragraph of my answer?
– Somos
Jul 15 at 22:14
Did you read the part of Golomb's example just before equation $(12)$ and the first paragraph of my answer?
– Somos
Jul 15 at 22:14
OH -- the light finally went on, so because $C_4$ appears twice, it cancels itself out.
– Jason S
Jul 15 at 22:23
OH -- the light finally went on, so because $C_4$ appears twice, it cancels itself out.
– Jason S
Jul 15 at 22:23
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2852717%2funderstanding-gausss-product-formula-as-cited-in-golombs-shift-register-sequen%23new-answer', 'question_page');
);
Post as a guest
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
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
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