OFFSET
2,4
COMMENTS
The number of Frobenius equivalence classes (FEC) of size n is given by A001037.
The trace of an FEC of size n is the sum of its elements.
The trace of (an element of) an FEC with a size d < n is either 0 or the sum of its elements; it is 0 when n/d is even; more generally, Tr(FEC) = Tr(representative) = n/d * sum of all elements in FEC.
The number of FEC with size n and trace 1 is given by sequence A000048.
The number of FEC with size n that is its own inverse (7 in the example below) is zero for odd n and A000048 (with n/2 as index) for even n.
The number of FEC with size n that are their own inverses and have trace 1 is zero if n is odd, is equal to (this sequence with index n/2)/2 if n/2 is odd and equal to (this sequence with index n/2 + A000048 with index n/4)/2 if n/2 is even.
LINKS
FORMULA
Let b(1) = 0, b(2) = 1, b(n) = 2^(n-1) - b(n-1) - 2 * b(n-2) - 3.
Let c(1) = 1, c(n) = 2^(n-1) - sum_{0<d<m,d|m}{c(d)}.
Let w(n) = b(n) - sum_{1<d<m,d even,d|m}{c(n/d)} - sum_{1<d<m,d odd,d|m}{w(n/d)}.
Then a(n) = 2 * w(n) / n.
EXAMPLE
Let g be a generator of the multiplicative group GF(2^6)^* with reduction polynomial t^6+t+1 = 0.
Pick g = t^3+1 (which generator is chosen doesn't matter for the sequence; but it matters for the table below).
Let n be an integer, 0 < n < 2^6 - 1. Let the smallest positive integer k such that (g^n)^(2^k) = g^n be k = 6, then the elements { g^n, (g^n)^2, (g^n)^(2^2), (g^n)^(2^3), (g^n)^(2^4), (g^n)^(2^5) } are all different and form an FEC with size 6.
These elements are equivalent, any may be chosen as representative.
The inverse of the FEC is an FEC with the inverse of those elements (all of which are in the same FEC of course).
The trace of each element is the same, of course and therefore we might as well speak about the inverse of the FEC and the trace of the FEC respectively.
In the table below, the FEC are denoted as {1,2,4,8,16,32} etc, only giving the exponents of g. All FEC with size 6 are given in both columns, the two columns give each others inverse.
The trace of the FEC is given after the FEC.
.......... x .......... Tr(x) ........ 1/x ........ Tr(1/x)
{ _1, _2, _4, _8, 16, 32} 0 { 31, 47, 55, 59, 61, 62} 1
{ _3, _6, 12, 24, 33, 48} 0 { 15, 30, 39, 51, 57, 60} 1
{ _5, 10, 17, 20, 34, 40} 1 { 23, 29, 43, 46, 53, 58} 1
{ _7, 14, 28, 35, 49, 56} 0 { _7, 14, 28, 35, 49, 56} 0
{ 11, 22, 25, 37, 44, 50} 1 { 13, 19, 26, 38, 41, 52} 0
{ 13, 19, 26, 38, 41, 52} 0 { 11, 22, 25, 37, 44, 50} 1
{ 15, 30, 39, 51, 57, 60} 1 { _3, _6, 12, 24, 33, 48} 0
{ 23, 29, 43, 46, 53, 58} 1 { _5, 10, 17, 20, 34, 40} 1
{ 31, 47, 55, 59, 61, 62} 1 { _1, _2, _4, _8, 16, 32} 0
This shows that there are 3 FEC (namely, 5, 7 and 23) whose trace is equal to the trace of its inverse and hence a(6) = 3.
CROSSREFS
KEYWORD
nonn
AUTHOR
Carlo Wood (carlo(AT)alinoe.com), Apr 22 2008, May 01 2008, May 05 2008
STATUS
approved