Today, 24 November 2004, I found the answer to the question why #E_{0} + #E_{1} = 2(q + 1). It is actually quite trivial. The reason is simply this:

The number of points on a given elliptic curve is equal to

#E = 2 + 2

where is the number of different non-zero x coordinates for which there is a solution (and thus exactly two solutions) to the elliptic curve equation E: x^{3} + ax^{2} + b = y^{2} + xy.

The first 2 takes the point at infinity and the point with x is zero (0, ) into account.

After dividing the elliptic curve equation by x^{2}, we see that there will be a solution for a non-zero value of x when x + a + b/x^{2} = (y/x)^{2} + y/x. And because of theorem 5, this only has a solution when Tr(x + a + b/x^{2}) = 0.

In other words, when the trace of a is changed from 0 into 1, then there will be solutions *for exactly the other non-zero values of x*!

Therefore, with #E_{0} = 2 + 2 and #E_{1} = 2 + 2 as defined in the chapter "Cracking parameter a of the elliptic curve", we can conclude that + equals the total number of possible non-zero values of the field: q - 1. And thus #E_{0} + #E_{1} = 4 + 2(q - 1) = 2(q + 1).

The following might be a very important result, since I never saw it anywhere in literature yet (please contact me if you know whether or not this is indeed new):

The order of an elliptic curve over is equal to (assuming Tr(a) = 0, otherwise it is 2(q + 1) minus this) 2 plus 2 times the number of values of x for which Tr(x) = Tr(b/x^{2}). Note that due to Frobenius .

If its new, then I hereby claim it ;).

It has been two years since I wrote something, but lets go again.

In order to find some relationship between b and #E we'll start with calculating #E_{0} for different values of m, setting a=0 and b=1. The choice for a is irrelevant as has been shown before. The choice for b=1 is made because it is the only value that will be independent of the field (using b=0 gives a singular curve) so that comparing them with different values of m makes sense.

Thus, given the curve E: y^{2} + xy = x^{3} + 1 over , #E was calculated by running over all non-zero values of x and then counting how many times Tr(x) = Tr(1/x). Multiplying this value with 2 and adding 2 then gives #E as shown above. The program used to do these calculations can be found in `testsuite/point/pointcount.cc`

.

The results are as follows.

m | #E |
---|---|

2 | 8 |

3 | 4 |

4 | 16 |

5 | 44 |

6 | 56 |

7 | 116 |

8 | 288 |

9 | 508 |

10 | 968 |

11 | 2116 |

12 | 4144 |

13 | 8012 |

14 | 16472 |

15 | 33044 |

16 | 65088 |

17 | 130972 |

18 | 263144 |

19 | 523492 |

20 | 1047376 |

21 | 2099948 |

22 | 4193912 |

23 | 8383412 |

24 | 16783200 |

25 | 33558844 |

26 | 67092488 |

27 | 134225284 |

28 | 268460656 |

29 | 536830604 |

30 | 1073731736 |

31 | 2147574356 |

I looked long and hard at those numbers and believe it or not, I came up with a structure.

First of all, you have to realize that each of those numbers where calculated as , so we might as well go back to that number.

m | (#E - 2)/2 |
---|---|

2 | 3 |

3 | 1 |

4 | 7 |

5 | 21 |

6 | 27 |

7 | 57 |

8 | 143 |

9 | 253 |

10 | 483 |

11 | 1057 |

12 | 2071 |

13 | 4005 |

14 | 8235 |

15 | 16521 |

16 | 32543 |

17 | 65485 |

18 | 131571 |

19 | 261745 |

20 | 523687 |

21 | 1049973 |

22 | 2096955 |

23 | 4191705 |

24 | 8391599 |

25 | 16779421 |

26 | 33546243 |

27 | 67112641 |

28 | 134230327 |

29 | 268415301 |

30 | 536865867 |

31 | 1073787177 |

Then it occured to me that if you subtract one from that number, m divides the result if m is prime. This being the case for m=2, 3, 5, 7, 11, 13, 17, 19, 23, 29 and 31 can hardly be a coincidence, so I subtracted 1 from the number and calculated the division.

m | (#E - 2)/2 - 1 | ((#E - 2)/2 - 1)/m |
---|---|---|

2 | 2 | 1 |

3 | 0 | 0 |

4 | 6 | |

5 | 20 | 4 |

6 | 26 | |

7 | 56 | 8 |

8 | 142 | |

9 | 252 | |

10 | 482 | |

11 | 1056 | 96 |

12 | 2070 | |

13 | 4004 | 308 |

14 | 8234 | |

15 | 16520 | |

16 | 32542 | |

17 | 65484 | 3852 |

18 | 131570 | |

19 | 261744 | 13776 |

20 | 523686 | |

21 | 1049972 | |

22 | 2096954 | |

23 | 4191704 | 182248 |

24 | 8391598 | |

25 | 16779420 | |

26 | 33546242 | |

27 | 67112640 | |

28 | 134230326 | |

29 | 268415300 | 9255700 |

30 | 536865866 | |

31 | 1073787176 | 34638296 |

This isn't as odd as it might seem, it is our friend Frobenius again! The value gives rise to the '1' count; after all we have b=1 and thus Tr(x) = Tr(1/x) for x=1! And if some and satisfies Tr(x) = Tr(1/x), then the Frobenius map that sends gives a different value of x that satisfies the formula as well. Since Frobenius repeats after m times when m is prime, those values of x come in groups of size m.

This discovery therefore immediately clarifies how to continue. When m is not prime, some values of x will not repeat after applying Frobenius m times, but after a factor of m times. For example, if m = 12 then some values of x will repeat after applying Frobenius 2, 3, 4, or 6 times, because each of those values divides 12.

We can therefore write (#E - 2)/2 - 1 as a weighted sum over the divisors of m as follows,

where w(m, d) is a function of the divisor and of the field (not of E since a=0 and b=1 are fixed and the whole elliptic curve is virtually out of the picture here). As the field is entirely determined by m, w(m, d) is a function of d and m. The actual value of w(m, d) is then the number of different elements x of the field that satisfy Tr(x) = Tr(1/x) and for which the smallest positive integer n such that x^{2n} = x is n = m/d. Put in a formula,

These values can be brute force calculated. Note that when m is prime then ((#E - 2)/2 - 1)/m = w(m, 1), so we replace the last column in the previous table with w(m, 1). New columns are added for each of the divisors of m. The program used to calculate this can be found in `testsuite/point/bspace.cc`

.

m | (#E - 2)/2 - 1 | w(m, 1) | w(m, 2) | w(m, 3) | w(m, 4) | w(m, 5) | w(m, 6) | w(m, 7) | w(m, 8) | w(m, 9) | w(m, 10) | w(m, 11) | w(m, 12) | w(m, 13) | w(m, 14) | w(m, 15) |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

2 | 2 | 1 | ||||||||||||||

3 | 0 | 0 | ||||||||||||||

4 | 6 | 1 | 1 | |||||||||||||

5 | 20 | 4 | ||||||||||||||

6 | 26 | 3 | 2 | 1 | ||||||||||||

7 | 56 | 8 | ||||||||||||||

8 | 142 | 16 | 3 | 1 | ||||||||||||

9 | 252 | 28 | 0 | |||||||||||||

10 | 482 | 45 | 6 | 1 | ||||||||||||

11 | 1056 | 96 | ||||||||||||||

12 | 2070 | 167 | 9 | 1 | 2 | 1 | ||||||||||

13 | 4004 | 308 | ||||||||||||||

14 | 8234 | 579 | 18 | 1 | ||||||||||||

15 | 16520 | 1100 | 4 | 0 | ||||||||||||

16 | 32542 | 2018 | 30 | 3 | 1 | |||||||||||

17 | 65484 | 3852 | ||||||||||||||

18 | 131570 | 7280 | 56 | 3 | 2 | 1 | ||||||||||

19 | 261744 | 13776 | ||||||||||||||

20 | 523686 | 26133 | 99 | 6 | 1 | 1 | ||||||||||

21 | 1049972 | 49996 | 8 | 0 | ||||||||||||

22 | 2096954 | 95223 | 186 | 1 | ||||||||||||

23 | 4191704 | 182248 | ||||||||||||||

24 | 8391598 | 349474 | 335 | 16 | 9 | 3 | 2 | 1 | ||||||||

25 | 16779420 | 671176 | 4 | |||||||||||||

26 | 33546242 | 1289925 | 630 | 1 | ||||||||||||

27 | 67112640 | 2485644 | 28 | 0 | ||||||||||||

28 | 134230326 | 4793355 | 1161 | 18 | 1 | 1 | ||||||||||

29 | 268415300 | 9255700 | ||||||||||||||

30 | 536865866 | 17894421 | 2182 | 45 | 3 | 6 | 2 | 1 | ||||||||

31 | 1073787176 | 34638296 |

And what a beautiful structure it is! This shows clearly that only w(m, 1) and w(m, 2) are significant. The value of w(m, d) with d > 2 can be directly expressed in one of the former:

After several weeks of writing down little numbers of papers, I can tell you that got very excited when I finally found the next step: A way to calculate w(m, 2)!

where

For example, in the table we see that w(26, 2) = 630. This number can be expressed in m as foc(13)/13 = (2^{13} - foc(1))/13 = (8192 - 2)/13 = 630.

The name foc stands for Frobenius Order Count, as it turns out that foc(m) is the number of elements of the field for which the smallest positive integer n such that x^{2n} = x is n = m.

foc(1) therefore represents the two elements of the base field { 0, 1 } whose square is equal to itself and thus never contribute to the count of elements. While if m is prime, then every other element does contribute, hence that for prime m we have 2^{m} - 2. If m is not prime then elements with a Frobenius multiplicity between 1 and m have to be taken into account, by subtracting them, as well.

In order to really understand the table (and the meaning of w(m,d)), lets look at each of the different contributions in turn. We'll start with the diagonal series of 1's on the right-side of the table. These 1's each have a count of 2 (m/d = 2): there are two different values of x that contribute to each of them. The reason for their existance is that, for some fields, there exists an element x such that applying Frobenius two times returns to itself (x^{4} = x). If such an element exists, then apparently all of them satisfy the equation Tr(x) = Tr(1/x), which can only be accounted for when x^{2} = 1/x (recall that Tr(x) = Tr(x^{2}) due to Frobenius). "Normally" an element of is expected to return to itself after applying Frobenius two times. Lets recall that fact by working it out.

F_{22}, t^{2}+t+1=0 | |||||||
---|---|---|---|---|---|---|---|

x | 1/x | x^{2} | x^{2}+x+1 | ||||

0 | 0 | 0 | |||||

t^{0} | = | 1 | t^{0} | = | 1 | 1 | 1 |

t^{1} | = | t | t^{2} | = | t + 1 | t + 1 | 0 |

t^{2} | = | t + 1 | t^{1} | = | t | t | 0 |

Where the Frobenius multiplicity of t and t+1 is 2 because squaring t gives t+1 and squaring that once more gives t again.

The elements 0 and 1 have both already been taken into account by subtracting 2 from #E (for x = 0 and the point at infinity) and subtracting 1 from (#E - 2) / 2 respectively, so we don't see any count for them back in the table with w(m, d) (table 4). I won't show x = 0 in the table below and x = 1 will be dropped further on, too.

Looking at table 4 again, the table with w(m,d), we see that this 1 occurs for every even value of m. The reason for that is that each of those fields has as subfield, and have therefore two elements that satisfy x^{2} + x + 1 = 0. More in general, a field will have a subfield if and only if n|m. As an example lets have a detailed look at the smallest field that has as subfield, . Lets use g as generator of the field rather than t in order not to get confused by the previously used t for the reduction polynomial of .

F_{24}, t^{4}+t+1=0, g=t | |||||||
---|---|---|---|---|---|---|---|

x | 1/x | x^{2} | x^{2}+x+1 | ||||

g^{0} | = | 1 | g^{0} | = | 1 | 1 | 1 |

g^{1} | = | g | g^{14} | = | g^{3} + 1 | g^{2} | g^{2} + g + 1 |

g^{2} | = | g^{2} | g^{13} | = | g^{3} + g^{2} + 1 | g + 1 | g^{2} + g |

g^{3} | = | g^{3} | g^{12} | = | g^{3} + g^{2} + g + 1 | g^{3} + g^{2} | g^{2} + 1 |

g^{4} | = | g+1 | g^{11} | = | g^{3} + g^{2} + g | g^{2} + 1 | g^{2} + g + 1 |

g^{5} | = | g^{2} + g | g^{10} | = | g^{2} + g + 1 | g^{2} + g + 1 | 0 |

g^{6} | = | g^{3} + g^{2} | g^{9} | = | g^{3} + g | g^{3} + g^{2} + g + 1 | g |

g^{7} | = | g^{3} + g + 1 | g^{8} | = | g^{2} + 1 | g^{3} + 1 | g + 1 |

g^{8} | = | g^{2} + 1 | g^{7} | = | g^{3} + g + 1 | g | g^{2} + g |

g^{9} | = | g^{3} + g | g^{6} | = | g^{3} + g^{2} | g^{3} | g + 1 |

g^{10} | = | g^{2} + g + 1 | g^{5} | = | g^{2} + g | g^{2} + g | 0 |

g^{11} | = | g^{3} + g^{2} + g | g^{4} | = | g+1 | g^{3} + g + 1 | g^{2} |

g^{12} | = | g^{3} + g^{2} + g + 1 | g^{3} | = | g^{3} | g^{3} + g | g^{2} |

g^{13} | = | g^{3} + g^{2} + 1 | g^{2} | = | g^{2} | g^{3} + g^{2} + g | g |

g^{14} | = | g^{3} + 1 | g^{1} | = | g | g^{3} + g^{2} + 1 | g^{2} + 1 |

Here I used the same color for elements in the same Frobenius equivalence class. For example, g^{6} and g^{9} are in the same Frobenius equivalence class because ((g^{6})^{2})^{2} = s^{24} = g^{9} (recall that g^{2m} = g and thus g^{15} = 1).

Note that the two values (g^{5} and g^{10}) together with g^{0} form a group under multiplication isomorphic with , and together with 0 they form a group under addition, so that this latter set is a subfield isomorphic with . For our investigation only the multiplication is important, so lets look at the group .

Z_{3} | |
---|---|

n | 2n |

0 | 0 |

1 | 2 |

2 | 1 |

As mentioned before, a field will only contain a subfield of the form if n|m (so that (p^{n} - 1) divides (p^{m} - 1), giving a subgroup under multiplication with size (p^{m} - 1) / (p^{n} - 1) = p^{m/n} + 1). Therefore, every field with even m has a subgroup under multiplication isomorphic with that gives rise to the same number of solutions as does its subfield . This is what caused the diagonal of 1's in the table for w(m, m/2).

Now lets have a look at the next diagonal, the alternating 2's and 0's, in particular the 2's thereof. These are the contributions w(m, m/3) and in particular when m is even. The smallest subfield that we can investigate that has this structure is with m = 6 and thus d = m/3 = 2. The following table was generated with `testsuite/point/bspacetables2.cc`

.

F_{26}, t^{6}+t+1=0 | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|

x = g^{n} | GCD(n, 63) | 1/x | Tr(x) | Tr(1/x) | d | x^{2}+x+1 | x^{3}+x+1 | ||||

g^{1} | = | t | 1 | g^{62} | = | t^{5}+1 | 0 | 1 | 1 | t^{2}+t+1 | t^{3}+t+1 |

g^{2} | = | t^{2} | 1 | g^{61} | = | t^{5}+t^{4}+1 | 0 | 1 | 1 | t^{4}+t^{2}+1 | t^{2}+t |

g^{3} | = | t^{3} | 3 | g^{60} | = | t^{5}+t^{4}+t^{3}+1 | 0 | 1 | 1 | t^{3}+t | t^{4}+1 |

g^{4} | = | t^{4} | 1 | g^{59} | = | t^{5}+t^{4}+t^{3}+t^{2}+1 | 0 | 1 | 1 | t^{4}+t^{3}+t^{2}+1 | t^{4}+t^{2} |

g^{5} | = | t^{5} | 1 | g^{58} | = | t^{5}+t^{4}+t^{3}+t^{2}+t+1 | 1 | 1 | 1 | t^{4}+1 | t^{3}+1 |

g^{6} | = | t+1 | 3 | g^{57} | = | t^{5}+t^{4}+t^{3}+t^{2}+t | 0 | 1 | 1 | t^{2}+t+1 | t^{3}+t^{2}+1 |

g^{7} | = | t^{2}+t | 7 | g^{56} | = | t^{4}+t^{3}+t^{2}+t+1 | 0 | 0 | 1 | t^{4}+t+1 | t^{5}+t^{4}+t^{3}+t^{2} |

g^{8} | = | t^{3}+t^{2} | 1 | g^{55} | = | t^{5}+t^{3}+t^{2}+t | 0 | 1 | 1 | t^{4}+t^{3}+t^{2}+t | t^{4}+t^{3}+t^{2} |

g^{9} | = | t^{4}+t^{3} | 9 | g^{54} | = | t^{4}+t^{2}+t+1 | 0 | 0 | 2 | t^{4}+t^{2}+t | t^{4}+t^{2}+t+1 |

g^{10} | = | t^{5}+t^{4} | 1 | g^{53} | = | t^{5}+t^{3}+t | 1 | 1 | 1 | t^{3}+t^{2}+1 | t |

g^{11} | = | t^{5}+t+1 | 1 | g^{52} | = | t^{4}+t^{2}+1 | 1 | 0 | 1 | t^{4}+t^{2}+t+1 | t^{5}+t^{4} |

g^{12} | = | t^{2}+1 | 3 | g^{51} | = | t^{5}+t^{3}+t+1 | 0 | 1 | 1 | t^{4}+t^{2}+1 | t^{4}+t |

g^{13} | = | t^{3}+t | 1 | g^{50} | = | t^{5}+t^{4}+t^{2} | 0 | 1 | 1 | t^{3}+t^{2} | t^{5}+t^{4}+t^{3}+t^{2}+1 |

g^{14} | = | t^{4}+t^{2} | 7 | g^{49} | = | t^{4}+t^{3}+t | 0 | 0 | 1 | t^{3}+1 | t^{5}+t^{3}+t^{2}+t+1 |

g^{15} | = | t^{5}+t^{3} | 3 | g^{48} | = | t^{3}+t^{2}+1 | 1 | 0 | 1 | t^{4}+t^{3}+t | t^{5}+t^{4} |

g^{16} | = | t^{4}+t+1 | 1 | g^{47} | = | t^{5}+t^{2}+t+1 | 0 | 1 | 1 | t^{4}+t^{3}+t+1 | t^{4}+t^{3}+t^{2}+t+1 |

g^{17} | = | t^{5}+t^{2}+t | 1 | g^{46} | = | t^{5}+t^{4}+t | 1 | 1 | 1 | t+1 | t^{3}+t^{2} |

g^{18} | = | t^{3}+t^{2}+t+1 | 9 | g^{45} | = | t^{4}+t^{3}+1 | 0 | 0 | 2 | t^{4}+t^{3} | t^{4}+t^{3}+1 |

g^{19} | = | t^{4}+t^{3}+t^{2}+t | 1 | g^{44} | = | t^{5}+t^{3}+t^{2}+1 | 0 | 1 | 1 | t^{2} | t^{5}+1 |

g^{20} | = | t^{5}+t^{4}+t^{3}+t^{2} | 1 | g^{43} | = | t^{5}+t^{4}+t^{2}+t+1 | 1 | 1 | 1 | t^{4}+t | t^{2} |

g^{21} | = | t^{5}+t^{4}+t^{3}+t+1 | 21 | g^{42} | = | t^{5}+t^{4}+t^{3}+t | 1 | 1 | 3 | 0 | t^{5}+t^{4}+t^{3}+t+1 |

g^{22} | = | t^{5}+t^{4}+t^{2}+1 | 1 | g^{41} | = | t^{4}+t^{3}+t^{2}+1 | 1 | 0 | 1 | t^{4}+t^{3}+1 | t^{5}+t^{4}+t^{3}+t^{2} |

g^{23} | = | t^{5}+t^{3}+1 | 1 | g^{40} | = | t^{5}+t^{3}+t^{2}+t+1 | 1 | 1 | 1 | t^{4}+t^{3}+t | t^{5}+t^{3}+t+1 |

g^{24} | = | t^{4}+1 | 3 | g^{39} | = | t^{5}+t^{4}+t^{2}+t | 0 | 1 | 1 | t^{4}+t^{3}+t^{2}+1 | t^{3} |

g^{25} | = | t^{5}+t | 1 | g^{38} | = | t^{4}+t^{3}+t+1 | 1 | 0 | 1 | t^{4}+t^{2}+t+1 | t^{5}+t^{2}+t |

g^{26} | = | t^{2}+t+1 | 1 | g^{37} | = | t^{5}+t^{3}+t^{2} | 0 | 1 | 1 | t^{4}+t+1 | t^{5}+t^{3}+t^{2}+t |

g^{27} | = | t^{3}+t^{2}+t | 9 | g^{36} | = | t^{4}+t^{2}+t | 0 | 0 | 2 | t^{4}+t^{3} | 0 |

g^{28} | = | t^{4}+t^{3}+t^{2} | 7 | g^{35} | = | t^{3}+t+1 | 0 | 0 | 1 | t | t^{5}+t^{2}+t |

g^{29} | = | t^{5}+t^{4}+t^{3} | 1 | g^{34} | = | t^{5}+t^{2} | 1 | 1 | 1 | t^{2}+t | t^{5}+t^{3} |

g^{30} | = | t^{5}+t^{4}+t+1 | 3 | g^{33} | = | t^{4}+t | 1 | 0 | 1 | t^{3}+t+1 | t^{5}+t^{4}+t^{3}+t^{2} |

g^{31} | = | t^{5}+t^{2}+1 | 1 | g^{32} | = | t^{3}+1 | 1 | 0 | 1 | t^{2}+1 | t^{4}+t^{2}+t+1 |

g^{32} | = | t^{3}+1 | 1 | g^{31} | = | t^{5}+t^{2}+1 | 0 | 1 | 1 | t^{3}+t | t^{4}+t^{3}+t |

g^{33} | = | t^{4}+t | 3 | g^{30} | = | t^{5}+t^{4}+t+1 | 0 | 1 | 1 | t^{4}+t^{3}+t+1 | t^{2}+1 |

g^{34} | = | t^{5}+t^{2} | 1 | g^{29} | = | t^{5}+t^{4}+t^{3} | 1 | 1 | 1 | t^{2}+1 | t^{4}+t+1 |

g^{35} | = | t^{3}+t+1 | 7 | g^{28} | = | t^{4}+t^{3}+t^{2} | 0 | 0 | 1 | t^{3}+t^{2} | t^{5}+t^{4} |

g^{36} | = | t^{4}+t^{2}+t | 9 | g^{27} | = | t^{3}+t^{2}+t | 0 | 0 | 2 | t^{3}+t^{2}+t+1 | t^{3}+t^{2}+t |

g^{37} | = | t^{5}+t^{3}+t^{2} | 1 | g^{26} | = | t^{2}+t+1 | 1 | 0 | 1 | t^{3}+t^{2}+t | t^{5} |

g^{38} | = | t^{4}+t^{3}+t+1 | 1 | g^{25} | = | t^{5}+t | 0 | 1 | 1 | t^{4} | t^{5}+t^{4}+1 |

g^{39} | = | t^{5}+t^{4}+t^{2}+t | 3 | g^{24} | = | t^{4}+1 | 1 | 0 | 1 | t^{4}+t^{3}+t^{2}+t+1 | t^{5} |

g^{40} | = | t^{5}+t^{3}+t^{2}+t+1 | 1 | g^{23} | = | t^{5}+t^{3}+1 | 1 | 1 | 1 | t^{3} | t^{4} |

g^{41} | = | t^{4}+t^{3}+t^{2}+1 | 1 | g^{22} | = | t^{5}+t^{4}+t^{2}+1 | 0 | 1 | 1 | t | t^{5}+t^{2}+1 |

g^{42} | = | t^{5}+t^{4}+t^{3}+t | 21 | g^{21} | = | t^{5}+t^{4}+t^{3}+t+1 | 1 | 1 | 3 | 0 | t^{5}+t^{4}+t^{3}+t |

g^{43} | = | t^{5}+t^{4}+t^{2}+t+1 | 1 | g^{20} | = | t^{5}+t^{4}+t^{3}+t^{2} | 1 | 1 | 1 | t^{4}+t^{3}+t^{2}+t+1 | t^{5}+t^{4}+t^{3}+t^{2}+t |

g^{44} | = | t^{5}+t^{3}+t^{2}+1 | 1 | g^{19} | = | t^{4}+t^{3}+t^{2}+t | 1 | 0 | 1 | t^{3}+t^{2}+t | t^{5}+t^{3}+t^{2}+t+1 |

g^{45} | = | t^{4}+t^{3}+1 | 9 | g^{18} | = | t^{3}+t^{2}+t+1 | 0 | 0 | 2 | t^{4}+t^{2}+t | 0 |

g^{46} | = | t^{5}+t^{4}+t | 1 | g^{17} | = | t^{5}+t^{2}+t | 1 | 1 | 1 | t^{3}+t+1 | t^{5}+t^{4}+t^{2}+t |

g^{47} | = | t^{5}+t^{2}+t+1 | 1 | g^{16} | = | t^{4}+t+1 | 1 | 0 | 1 | t+1 | t^{3}+t^{2}+t |

g^{48} | = | t^{3}+t^{2}+1 | 3 | g^{15} | = | t^{5}+t^{3} | 0 | 1 | 1 | t^{4}+t^{3}+t^{2}+t | t+1 |

g^{49} | = | t^{4}+t^{3}+t | 7 | g^{14} | = | t^{4}+t^{2} | 0 | 0 | 1 | t^{4} | t^{5} |

g^{50} | = | t^{5}+t^{4}+t^{2} | 1 | g^{13} | = | t^{3}+t | 1 | 0 | 1 | t^{4}+t^{3}+1 | t^{5}+t^{2} |

g^{51} | = | t^{5}+t^{3}+t+1 | 3 | g^{12} | = | t^{2}+1 | 1 | 0 | 1 | t^{4}+t^{3}+t^{2} | t^{5}+t^{2} |

g^{52} | = | t^{4}+t^{2}+1 | 1 | g^{11} | = | t^{5}+t+1 | 0 | 1 | 1 | t^{3}+1 | t^{5}+t^{2}+t+1 |

g^{53} | = | t^{5}+t^{3}+t | 1 | g^{10} | = | t^{5}+t^{4} | 1 | 1 | 1 | t^{4}+t^{3}+t^{2} | t^{5}+t^{4}+t^{3}+1 |

g^{54} | = | t^{4}+t^{2}+t+1 | 9 | g^{9} | = | t^{4}+t^{3} | 0 | 0 | 2 | t^{3}+t^{2}+t+1 | 0 |

g^{55} | = | t^{5}+t^{3}+t^{2}+t | 1 | g^{8} | = | t^{3}+t^{2} | 1 | 0 | 1 | t^{3} | t^{4}+t^{3}+1 |

g^{56} | = | t^{4}+t^{3}+t^{2}+t+1 | 7 | g^{7} | = | t^{2}+t | 0 | 0 | 1 | t^{2} | t^{5}+t^{2} |

g^{57} | = | t^{5}+t^{4}+t^{3}+t^{2}+t | 3 | g^{6} | = | t+1 | 1 | 0 | 1 | t^{4}+t^{2} | t^{5}+t^{2}+t |

g^{58} | = | t^{5}+t^{4}+t^{3}+t^{2}+t+1 | 1 | g^{5} | = | t^{5} | 1 | 1 | 1 | t^{4}+t^{2} | t^{5}+t^{4}+t+1 |

g^{59} | = | t^{5}+t^{4}+t^{3}+t^{2}+1 | 1 | g^{4} | = | t^{4} | 1 | 0 | 1 | t^{4}+t | t^{4}+t^{2}+t+1 |

g^{60} | = | t^{5}+t^{4}+t^{3}+1 | 3 | g^{3} | = | t^{3} | 1 | 0 | 1 | t^{2}+t | t^{5}+t^{3}+t^{2}+t+1 |

g^{61} | = | t^{5}+t^{4}+1 | 1 | g^{2} | = | t^{2} | 1 | 0 | 1 | t^{3}+t^{2}+1 | t^{3}+t^{2}+t |

g^{62} | = | t^{5}+1 | 1 | g^{1} | = | t | 1 | 0 | 1 | t^{4}+1 | t^{4}+t^{3}+1 |

Here we see again the two elements that give rise to the w(6,3) as g^{21} and g^{42}. Together with 1 they form the multiplicative subgroup GF(2^{2})^{*} as can be seen from the fact that x^{2}+x+1 in the second column from the right is zero. Likewise, the third column contains zeroes for the roots of x^{3}+x+1: g^{27}, g^{45} and g^{54} which are thus, elements of the multiplicative group GF(2^{3})^{*}. The remaining elements of that group, besides the multiplicative unity, are g^{9}, g^{18} and g^{36}. At this point I have no idea if it's a coincidence that those are precisely the inverse of first three (this could be because there simply are no other elements with GCD(n, 63) of 9). Note that GF(2^{3})^{*} is isomorphic with :

Z_{7} | |
---|---|

n | 6n |

0 | 0 |

1 | 6 |

2 | 5 |

3 | 4 |

4 | 3 |

5 | 2 |

6 | 1 |

In this case we have two different colors (two Frobenius equivalence classes) and thus w(6, 2) = 2.

Looking at F_{26} again, we only see one other (besides { g^{21}, g^{42} }}) Frobenius equivalence class that automatically adds to the count of solutions in the form of the elements { t^{7}, t^{14}, t^{28}, t^{35}, t^{49}, t^{56} }, because their inverses are in the same Frobenius equivalence class. These elements added one to the value of w(6,1) because there are six of them (d = 1).

What exactly is the structure that gives rise to these six elements? As you can see, they are not part of a subfield of ( and ): neither of the two right-most columns is zero for these elements.

The magic lies in the fact that each element can be paired up with another element from the same Frobenius equivalence class, such that if x is in this class then so is 1/x. The factor 7 is an arbitrary residue factor so lets start with deviding that away. Much in the same way as we did get before, now we get . The elements we have are the set which is a direct result of the fact that we repeatedly applied Frobenius: each time the exponents of t are doubled.

The puzzle that we have to solve therefore is this: Let G = Z/nZ, S={2^{i}}, when will be even and for each x in S there will be a y in S such that x+y = 0 (mod n)?

I had two mathematicians look at that, and after two hours of trying and discussion, they came up with the following. If there exists a k such that 2^{k} + 1 = 0 (mod n), then let k be the least positive such, then S = { 2^{0}, 2^{1}, ..., 2^{(2k-1)}} since 2^{2k} = 1 (mod n), thus is even, and = 2k2^{i} + 2^{k+i} = 2^{i} + (-1) 2^{i} = 0 (mod n), i.e. all elements are paired up. Let 2^{i} = x in S then there exists a y in S such that x + y = 0 (mod n) thus 2^{i} + 2^{k} 2^{i} = 0 (mod n), thus 2^{k} 2^{i} = (-1) 2^{i} (mod n), which shows that this is the only possibility.

The restriction on the factor (n) is therefore that there has to exist a k such that 2^{k} + 1 = 0 (mod n).

And indeed, 9 = 2^{3} + 1, where the exponent k = 3 gives rise to 2k = 6 elements in the Frobenius equivalence class of w(m, m/6). Moreover, 3 = 2^{1} + 1, where the exponent k = 1 gives rise to 2k = 2 elements in the Frobenius equivalence class of w(m, m/2). This does not happen for every m however, but only for those m where 2^{m} - 1 has a factor n such that there exists a positive k such that 2^{k} + 1 = 0 (mod n).

Lets start using m/d rather than d, because it is m/d that is constant along of the diagonals in table 4. For the same reason, show (2^{m} - 1) / gcd(2^{m} - 1, n) instead of gcd(2^{m} - 1, n).

The same structures return for larger m if it is a multiple of 6. Consider these tables for m = 6, 12, 18, 24:

F_{26}, t^{6}+t+1=0 | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|

x = g^{n} | 63/GCD(n, 63) | 1/x | Tr(x) | Tr(1/x) | m/d | x^{2}+x+1 | x^{3}+x+1 | ||||

g^{9} | = | t^{4}+t^{3} | 7 | g^{54} | = | t^{4}+t^{2}+t+1 | 0 | 0 | 3 | t^{4}+t^{2}+t | t^{4}+t^{2}+t+1 |

g^{18} | = | t^{3}+t^{2}+t+1 | 7 | g^{45} | = | t^{4}+t^{3}+1 | 0 | 0 | 3 | t^{4}+t^{3} | t^{4}+t^{3}+1 |

g^{21} | = | t^{5}+t^{4}+t^{3}+t+1 | 3 | g^{42} | = | t^{5}+t^{4}+t^{3}+t | 1 | 1 | 2 | 0 | t^{5}+t^{4}+t^{3}+t+1 |

g^{27} | = | t^{3}+t^{2}+t | 7 | g^{36} | = | t^{4}+t^{2}+t | 0 | 0 | 3 | t^{4}+t^{3} | 0 |

g^{36} | = | t^{4}+t^{2}+t | 7 | g^{27} | = | t^{3}+t^{2}+t | 0 | 0 | 3 | t^{3}+t^{2}+t+1 | t^{3}+t^{2}+t |

g^{42} | = | t^{5}+t^{4}+t^{3}+t | 3 | g^{21} | = | t^{5}+t^{4}+t^{3}+t+1 | 1 | 1 | 2 | 0 | t^{5}+t^{4}+t^{3}+t |

g^{45} | = | t^{4}+t^{3}+1 | 7 | g^{18} | = | t^{3}+t^{2}+t+1 | 0 | 0 | 3 | t^{4}+t^{2}+t | 0 |

g^{54} | = | t^{4}+t^{2}+t+1 | 7 | g^{9} | = | t^{4}+t^{3} | 0 | 0 | 3 | t^{3}+t^{2}+t+1 | 0 |

F_{212}, t^{12}+t^{3}+1=0 | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|

x = g^{n} | 4095/GCD(n, 4095) | 1/x | Tr(x) | Tr(1/x) | m/d | x^{2}+x+1 | x^{3}+x+1 | ||||

g^{585} | = | t^{10}+t^{7}+t^{5}+t+1 | 7 | g^{3510} | = | t^{11}+t^{8}+t^{7}+t | 0 | 0 | 3 | t^{11}+t^{8}+t^{7}+t+1 | t^{11}+t^{8}+t^{7}+t |

g^{1170} | = | t^{11}+t^{10}+t^{8}+t^{5}+1 | 7 | g^{2925} | = | t^{10}+t^{7}+t^{5}+t | 0 | 0 | 3 | t^{10}+t^{7}+t^{5}+t+1 | t^{10}+t^{7}+t^{5}+t |

g^{1365} | = | t^{6}+t^{3} | 3 | g^{2730} | = | t^{6}+t^{3}+1 | 0 | 0 | 2 | 0 | t^{6}+t^{3} |

g^{1755} | = | t^{11}+t^{10}+t^{8}+t^{5} | 7 | g^{2340} | = | t^{11}+t^{8}+t^{7}+t+1 | 0 | 0 | 3 | t^{10}+t^{7}+t^{5}+t+1 | 0 |

g^{2340} | = | t^{11}+t^{8}+t^{7}+t+1 | 7 | g^{1755} | = | t^{11}+t^{10}+t^{8}+t^{5} | 0 | 0 | 3 | t^{11}+t^{10}+t^{8}+t^{5}+1 | t^{11}+t^{10}+t^{8}+t^{5} |

g^{2730} | = | t^{6}+t^{3}+1 | 3 | g^{1365} | = | t^{6}+t^{3} | 0 | 0 | 2 | 0 | t^{6}+t^{3}+1 |

g^{2925} | = | t^{10}+t^{7}+t^{5}+t | 7 | g^{1170} | = | t^{11}+t^{10}+t^{8}+t^{5}+1 | 0 | 0 | 3 | t^{11}+t^{8}+t^{7}+t+1 | 0 |

g^{3510} | = | t^{11}+t^{8}+t^{7}+t | 7 | g^{585} | = | t^{10}+t^{7}+t^{5}+t+1 | 0 | 0 | 3 | t^{11}+t^{10}+t^{8}+t^{5}+1 | 0 |

F_{218}, t^{18}+t^{3}+1=0 | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|

x = g^{n} | 262143/GCD(n, 262143) | 1/x | Tr(x) | Tr(1/x) | m/d | x^{2}+x+1 | x^{3}+x+1 | ||||

g^{37449} | = | t^{12}+t^{6}+t^{3}+1 | 7 | g^{224694} | = | t^{12}+t^{9} | 0 | 0 | 3 | t^{9}+t^{6}+t^{3}+1 | 0 |

g^{74898} | = | t^{12}+t^{9}+1 | 7 | g^{187245} | = | t^{9}+t^{6}+t^{3}+1 | 0 | 0 | 3 | t^{12}+t^{6}+t^{3} | 0 |

g^{87381} | = | t^{15}+t^{12}+t^{9}+t^{3}+1 | 3 | g^{174762} | = | t^{15}+t^{12}+t^{9}+t^{3} | 1 | 1 | 2 | 0 | t^{15}+t^{12}+t^{9}+t^{3}+1 |

g^{112347} | = | t^{12}+t^{6}+t^{3} | 7 | g^{149796} | = | t^{9}+t^{6}+t^{3} | 0 | 0 | 3 | t^{9}+t^{6}+t^{3}+1 | t^{9}+t^{6}+t^{3} |

g^{149796} | = | t^{9}+t^{6}+t^{3} | 7 | g^{112347} | = | t^{12}+t^{6}+t^{3} | 0 | 0 | 3 | t^{12}+t^{9} | 0 |

g^{174762} | = | t^{15}+t^{12}+t^{9}+t^{3} | 3 | g^{87381} | = | t^{15}+t^{12}+t^{9}+t^{3}+1 | 1 | 1 | 2 | 0 | t^{15}+t^{12}+t^{9}+t^{3} |

g^{187245} | = | t^{9}+t^{6}+t^{3}+1 | 7 | g^{74898} | = | t^{12}+t^{9}+1 | 0 | 0 | 3 | t^{12}+t^{9} | t^{12}+t^{9}+1 |

g^{224694} | = | t^{12}+t^{9} | 7 | g^{37449} | = | t^{12}+t^{6}+t^{3}+1 | 0 | 0 | 3 | t^{12}+t^{6}+t^{3} | t^{12}+t^{6}+t^{3}+1 |

F_{224}, t^{24}+t^{4}+t^{3}+t+1=0 | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|

x = g^{n} | 16777215/GCD(n, 16777215) | 1/x | Tr(x) | Tr(1/x) | m/d | x^{2}+x+1 | x^{3}+x+1 | ||||

g^{2396745} | = | t^{15}+t^{14}+t^{13}+t^{9}+t^{7}+t^{5}+t^{3}+t^{2}+1 | 7 | g^{14380470} | = | t^{18}+t^{15}+t^{13}+t^{8}+t^{7}+t^{6}+t^{5} | 0 | 0 | 3 | t^{18}+t^{15}+t^{13}+t^{8}+t^{7}+t^{6}+t^{5}+1 | t^{18}+t^{15}+t^{13}+t^{8}+t^{7}+t^{6}+t^{5} |

g^{4793490} | = | t^{18}+t^{14}+t^{9}+t^{8}+t^{6}+t^{3}+t^{2}+1 | 7 | g^{11983725} | = | t^{15}+t^{14}+t^{13}+t^{9}+t^{7}+t^{5}+t^{3}+t^{2} | 0 | 0 | 3 | t^{15}+t^{14}+t^{13}+t^{9}+t^{7}+t^{5}+t^{3}+t^{2}+1 | t^{15}+t^{14}+t^{13}+t^{9}+t^{7}+t^{5}+t^{3}+t^{2} |

g^{5592405} | = | t^{12}+t^{6}+t^{3}+t^{2}+t | 3 | g^{11184810} | = | t^{12}+t^{6}+t^{3}+t^{2}+t+1 | 0 | 0 | 2 | 0 | t^{12}+t^{6}+t^{3}+t^{2}+t |

g^{7190235} | = | t^{18}+t^{14}+t^{9}+t^{8}+t^{6}+t^{3}+t^{2} | 7 | g^{9586980} | = | t^{18}+t^{15}+t^{13}+t^{8}+t^{7}+t^{6}+t^{5}+1 | 0 | 0 | 3 | t^{15}+t^{14}+t^{13}+t^{9}+t^{7}+t^{5}+t^{3}+t^{2}+1 | 0 |

g^{9586980} | = | t^{18}+t^{15}+t^{13}+t^{8}+t^{7}+t^{6}+t^{5}+1 | 7 | g^{7190235} | = | t^{18}+t^{14}+t^{9}+t^{8}+t^{6}+t^{3}+t^{2} | 0 | 0 | 3 | t^{18}+t^{14}+t^{9}+t^{8}+t^{6}+t^{3}+t^{2}+1 | t^{18}+t^{14}+t^{9}+t^{8}+t^{6}+t^{3}+t^{2} |

g^{11184810} | = | t^{12}+t^{6}+t^{3}+t^{2}+t+1 | 3 | g^{5592405} | = | t^{12}+t^{6}+t^{3}+t^{2}+t | 0 | 0 | 2 | 0 | t^{12}+t^{6}+t^{3}+t^{2}+t+1 |

g^{11983725} | = | t^{15}+t^{14}+t^{13}+t^{9}+t^{7}+t^{5}+t^{3}+t^{2} | 7 | g^{4793490} | = | t^{18}+t^{14}+t^{9}+t^{8}+t^{6}+t^{3}+t^{2}+1 | 0 | 0 | 3 | t^{18}+t^{15}+t^{13}+t^{8}+t^{7}+t^{6}+t^{5}+1 | 0 |

g^{14380470} | = | t^{18}+t^{15}+t^{13}+t^{8}+t^{7}+t^{6}+t^{5} | 7 | g^{2396745} | = | t^{15}+t^{14}+t^{13}+t^{9}+t^{7}+t^{5}+t^{3}+t^{2}+1 | 0 | 0 | 3 | t^{18}+t^{14}+t^{9}+t^{8}+t^{6}+t^{3}+t^{2}+1 | 0 |

showing all the elements that contribute to w(m, m/2) and w(m, m/3), namely one Frobenius equivalence class for m/2, and two Frobenius equivalence classes for m/3. If m is an odd multiple of 3, the same two Frobenius equivalence classes still exist, but they are not a solution of the Elliptic Curve (Tr(x) Tr(1/x)):

F_{23}, t^{3}+t+1=0 | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|

x = g^{n} | 7/GCD(n, 7) | 1/x | Tr(x) | Tr(1/x) | m/d | x^{2}+x+1 | x^{3}+x+1 | ||||

g^{1} | = | t | 7 | g^{6} | = | t^{2}+1 | 0 | 1 | 3 | t^{2}+t+1 | 0 |

g^{2} | = | t^{2} | 7 | g^{5} | = | t^{2}+t+1 | 0 | 1 | 3 | t+1 | 0 |

g^{3} | = | t+1 | 7 | g^{4} | = | t^{2}+t | 1 | 0 | 3 | t^{2}+t+1 | t^{2}+t |

g^{4} | = | t^{2}+t | 7 | g^{3} | = | t+1 | 0 | 1 | 3 | t^{2}+1 | 0 |

g^{5} | = | t^{2}+t+1 | 7 | g^{2} | = | t^{2} | 1 | 0 | 3 | t^{2}+1 | t^{2} |

g^{6} | = | t^{2}+1 | 7 | g^{1} | = | t | 1 | 0 | 3 | t+1 | t |

F_{29}, t^{9}+t+1=0 | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|

x = g^{n} | 511/GCD(n, 511) | 1/x | Tr(x) | Tr(1/x) | m/d | x^{2}+x+1 | x^{3}+x+1 | ||||

g^{73} | = | t^{8}+t^{7}+t^{6}+t^{4}+t+1 | 7 | g^{438} | = | t^{8}+t^{5}+t^{3}+t^{2}+t | 1 | 0 | 3 | t^{8}+t^{5}+t^{3}+t^{2}+t+1 | t^{8}+t^{5}+t^{3}+t^{2}+t |

g^{146} | = | t^{7}+t^{6}+t^{5}+t^{4}+t^{3}+t^{2}+1 | 7 | g^{365} | = | t^{8}+t^{7}+t^{6}+t^{4}+t | 1 | 0 | 3 | t^{8}+t^{7}+t^{6}+t^{4}+t+1 | t^{8}+t^{7}+t^{6}+t^{4}+t |

g^{219} | = | t^{7}+t^{6}+t^{5}+t^{4}+t^{3}+t^{2} | 7 | g^{292} | = | t^{8}+t^{5}+t^{3}+t^{2}+t+1 | 0 | 1 | 3 | t^{8}+t^{7}+t^{6}+t^{4}+t+1 | 0 |

g^{292} | = | t^{8}+t^{5}+t^{3}+t^{2}+t+1 | 7 | g^{219} | = | t^{7}+t^{6}+t^{5}+t^{4}+t^{3}+t^{2} | 1 | 0 | 3 | t^{7}+t^{6}+t^{5}+t^{4}+t^{3}+t^{2}+1 | t^{7}+t^{6}+t^{5}+t^{4}+t^{3}+t^{2} |

g^{365} | = | t^{8}+t^{7}+t^{6}+t^{4}+t | 7 | g^{146} | = | t^{7}+t^{6}+t^{5}+t^{4}+t^{3}+t^{2}+1 | 0 | 1 | 3 | t^{8}+t^{5}+t^{3}+t^{2}+t+1 | 0 |

g^{438} | = | t^{8}+t^{5}+t^{3}+t^{2}+t | 7 | g^{73} | = | t^{8}+t^{7}+t^{6}+t^{4}+t+1 | 0 | 1 | 3 | t^{7}+t^{6}+t^{5}+t^{4}+t^{3}+t^{2}+1 | 0 |

F_{215}, t^{15}+t+1=0 | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|

x = g^{n} | 32767/GCD(n, 32767) | 1/x | Tr(x) | Tr(1/x) | m/d | x^{2}+x+1 | x^{3}+x+1 | ||||

g^{4681} | = | t^{12}+t^{10}+t^{9}+t^{5}+t^{4}+t | 7 | g^{28086} | = | t^{9}+t^{8}+t^{6}+t^{5}+t^{4}+t^{3}+t^{2}+1 | 0 | 1 | 3 | t^{12}+t^{10}+t^{8}+t^{6}+t^{3}+t^{2}+t+1 | 0 |

g^{9362} | = | t^{9}+t^{8}+t^{6}+t^{5}+t^{4}+t^{3}+t^{2} | 7 | g^{23405} | = | t^{12}+t^{10}+t^{8}+t^{6}+t^{3}+t^{2}+t+1 | 0 | 1 | 3 | t^{12}+t^{10}+t^{9}+t^{5}+t^{4}+t+1 | 0 |

g^{14043} | = | t^{12}+t^{10}+t^{9}+t^{5}+t^{4}+t+1 | 7 | g^{18724} | = | t^{12}+t^{10}+t^{8}+t^{6}+t^{3}+t^{2}+t | 1 | 0 | 3 | t^{12}+t^{10}+t^{8}+t^{6}+t^{3}+t^{2}+t+1 | t^{12}+t^{10}+t^{8}+t^{6}+t^{3}+t^{2}+t |

g^{18724} | = | t^{12}+t^{10}+t^{8}+t^{6}+t^{3}+t^{2}+t | 7 | g^{14043} | = | t^{12}+t^{10}+t^{9}+t^{5}+t^{4}+t+1 | 0 | 1 | 3 | t^{9}+t^{8}+t^{6}+t^{5}+t^{4}+t^{3}+t^{2}+1 | 0 |

g^{23405} | = | t^{12}+t^{10}+t^{8}+t^{6}+t^{3}+t^{2}+t+1 | 7 | g^{9362} | = | t^{9}+t^{8}+t^{6}+t^{5}+t^{4}+t^{3}+t^{2} | 1 | 0 | 3 | t^{9}+t^{8}+t^{6}+t^{5}+t^{4}+t^{3}+t^{2}+1 | t^{9}+t^{8}+t^{6}+t^{5}+t^{4}+t^{3}+t^{2} |

g^{28086} | = | t^{9}+t^{8}+t^{6}+t^{5}+t^{4}+t^{3}+t^{2}+1 | 7 | g^{4681} | = | t^{12}+t^{10}+t^{9}+t^{5}+t^{4}+t | 1 | 0 | 3 | t^{12}+t^{10}+t^{9}+t^{5}+t^{4}+t+1 | t^{12}+t^{10}+t^{9}+t^{5}+t^{4}+t |

The following is a discussion of the data on this page.

It is not a coincidence that every time this shows alternating a table where every entry is a solution of the elliptic curve. For those tables where m / (m/d) is even, in other words, showing the elements that contribute to even d. We saw already before that those values, the values of w(m, 2), can be easily calculated.

Recall that,

In this case we have x = g^{n} such that (g^{n})^{2m/d} = g^{n} (= (g^{n})^{20}), and thus,

where the last equation holds because d is even. Likewise Tr(1/x) = 0 and thus all values are a solution of the Elliptic curve.

Instead we need to concentrate on the other values, the odd values of d, and because the structures are 100% equivalent, it is also not needed to look at large m, the smallest with d = 1 will do, because the rest is trivially deducable.

Those elements are:

F_{23}, t^{3}+t+1=0 | |||||||||
---|---|---|---|---|---|---|---|---|---|

x = g^{n} | 7/GCD(n, 7) | 1/x | Tr(x) | Tr(1/x) | m/d | ||||

g^{1} | = | t | 7 | g^{6} | = | t^{2}+1 | 0 | 1 | 3 |

g^{2} | = | t^{2} | 7 | g^{5} | = | t^{2}+t+1 | 0 | 1 | 3 |

g^{3} | = | t+1 | 7 | g^{4} | = | t^{2}+t | 1 | 0 | 3 |

g^{4} | = | t^{2}+t | 7 | g^{3} | = | t+1 | 0 | 1 | 3 |

g^{5} | = | t^{2}+t+1 | 7 | g^{2} | = | t^{2} | 1 | 0 | 3 |

g^{6} | = | t^{2}+1 | 7 | g^{1} | = | t | 1 | 0 | 3 |

F_{24}, t^{4}+t+1=0 | |||||||||
---|---|---|---|---|---|---|---|---|---|

x = g^{n} | 15/GCD(n, 15) | 1/x | Tr(x) | Tr(1/x) | m/d | ||||

g^{1} | = | t | 15 | g^{14} | = | t^{3}+1 | 0 | 1 | 4 |

g^{2} | = | t^{2} | 15 | g^{13} | = | t^{3}+t^{2}+1 | 0 | 1 | 4 |

g^{3} | = | t^{3} | 5 | g^{12} | = | t^{3}+t^{2}+t+1 | 1 | 1 | 4 |

g^{4} | = | t+1 | 15 | g^{11} | = | t^{3}+t^{2}+t | 0 | 1 | 4 |

g^{6} | = | t^{3}+t^{2} | 5 | g^{9} | = | t^{3}+t | 1 | 1 | 4 |

g^{7} | = | t^{3}+t+1 | 15 | g^{8} | = | t^{2}+1 | 1 | 0 | 4 |

g^{8} | = | t^{2}+1 | 15 | g^{7} | = | t^{3}+t+1 | 0 | 1 | 4 |

g^{9} | = | t^{3}+t | 5 | g^{6} | = | t^{3}+t^{2} | 1 | 1 | 4 |

g^{11} | = | t^{3}+t^{2}+t | 15 | g^{4} | = | t+1 | 1 | 0 | 4 |

g^{12} | = | t^{3}+t^{2}+t+1 | 5 | g^{3} | = | t^{3} | 1 | 1 | 4 |

g^{13} | = | t^{3}+t^{2}+1 | 15 | g^{2} | = | t^{2} | 1 | 0 | 4 |

g^{14} | = | t^{3}+1 | 15 | g^{1} | = | t | 1 | 0 | 4 |

F_{25}, t^{5}+t^{2}+1=0 | |||||||||
---|---|---|---|---|---|---|---|---|---|

x = g^{n} | 31/GCD(n, 31) | 1/x | Tr(x) | Tr(1/x) | m/d | ||||

g^{1} | = | t | 31 | g^{30} | = | t^{4}+t | 0 | 0 | 5 |

g^{2} | = | t^{2} | 31 | g^{29} | = | t^{3}+1 | 0 | 0 | 5 |

g^{3} | = | t^{3} | 31 | g^{28} | = | t^{4}+t^{2}+t | 1 | 0 | 5 |

g^{4} | = | t^{4} | 31 | g^{27} | = | t^{3}+t+1 | 0 | 0 | 5 |

g^{5} | = | t^{2}+1 | 31 | g^{26} | = | t^{4}+t^{2}+t+1 | 1 | 1 | 5 |

g^{6} | = | t^{3}+t | 31 | g^{25} | = | t^{4}+t^{3}+1 | 1 | 0 | 5 |

g^{7} | = | t^{4}+t^{2} | 31 | g^{24} | = | t^{4}+t^{3}+t^{2}+t | 0 | 1 | 5 |

g^{8} | = | t^{3}+t^{2}+1 | 31 | g^{23} | = | t^{3}+t^{2}+t+1 | 0 | 0 | 5 |

g^{9} | = | t^{4}+t^{3}+t | 31 | g^{22} | = | t^{4}+t^{2}+1 | 1 | 1 | 5 |

g^{10} | = | t^{4}+1 | 31 | g^{21} | = | t^{4}+t^{3} | 1 | 1 | 5 |

g^{11} | = | t^{2}+t+1 | 31 | g^{20} | = | t^{3}+t^{2} | 1 | 1 | 5 |

g^{12} | = | t^{3}+t^{2}+t | 31 | g^{19} | = | t^{2}+t | 1 | 0 | 5 |

g^{13} | = | t^{4}+t^{3}+t^{2} | 31 | g^{18} | = | t+1 | 1 | 1 | 5 |

g^{14} | = | t^{4}+t^{3}+t^{2}+1 | 31 | g^{17} | = | t^{4}+t+1 | 0 | 1 | 5 |

g^{15} | = | t^{4}+t^{3}+t^{2}+t+1 | 31 | g^{16} | = | t^{4}+t^{3}+t+1 | 0 | 0 | 5 |

g^{16} | = | t^{4}+t^{3}+t+1 | 31 | g^{15} | = | t^{4}+t^{3}+t^{2}+t+1 | 0 | 0 | 5 |

g^{17} | = | t^{4}+t+1 | 31 | g^{14} | = | t^{4}+t^{3}+t^{2}+1 | 1 | 0 | 5 |

g^{18} | = | t+1 | 31 | g^{13} | = | t^{4}+t^{3}+t^{2} | 1 | 1 | 5 |

g^{19} | = | t^{2}+t | 31 | g^{12} | = | t^{3}+t^{2}+t | 0 | 1 | 5 |

g^{20} | = | t^{3}+t^{2} | 31 | g^{11} | = | t^{2}+t+1 | 1 | 1 | 5 |

g^{21} | = | t^{4}+t^{3} | 31 | g^{10} | = | t^{4}+1 | 1 | 1 | 5 |

g^{22} | = | t^{4}+t^{2}+1 | 31 | g^{9} | = | t^{4}+t^{3}+t | 1 | 1 | 5 |

g^{23} | = | t^{3}+t^{2}+t+1 | 31 | g^{8} | = | t^{3}+t^{2}+1 | 0 | 0 | 5 |

g^{24} | = | t^{4}+t^{3}+t^{2}+t | 31 | g^{7} | = | t^{4}+t^{2} | 1 | 0 | 5 |

g^{25} | = | t^{4}+t^{3}+1 | 31 | g^{6} | = | t^{3}+t | 0 | 1 | 5 |

g^{26} | = | t^{4}+t^{2}+t+1 | 31 | g^{5} | = | t^{2}+1 | 1 | 1 | 5 |

g^{27} | = | t^{3}+t+1 | 31 | g^{4} | = | t^{4} | 0 | 0 | 5 |

g^{28} | = | t^{4}+t^{2}+t | 31 | g^{3} | = | t^{3} | 0 | 1 | 5 |

g^{29} | = | t^{3}+1 | 31 | g^{2} | = | t^{2} | 0 | 0 | 5 |

g^{30} | = | t^{4}+t | 31 | g^{1} | = | t | 0 | 0 | 5 |

F_{26}, t^{6}+t+1=0 | |||||||||
---|---|---|---|---|---|---|---|---|---|

x = g^{n} | 63/GCD(n, 63) | 1/x | Tr(x) | Tr(1/x) | m/d | ||||

g^{1} | = | t | 63 | g^{62} | = | t^{5}+1 | 0 | 1 | 6 |

g^{2} | = | t^{2} | 63 | g^{61} | = | t^{5}+t^{4}+1 | 0 | 1 | 6 |

g^{3} | = | t^{3} | 21 | g^{60} | = | t^{5}+t^{4}+t^{3}+1 | 0 | 1 | 6 |

g^{4} | = | t^{4} | 63 | g^{59} | = | t^{5}+t^{4}+t^{3}+t^{2}+1 | 0 | 1 | 6 |

g^{5} | = | t^{5} | 63 | g^{58} | = | t^{5}+t^{4}+t^{3}+t^{2}+t+1 | 1 | 1 | 6 |

g^{6} | = | t+1 | 21 | g^{57} | = | t^{5}+t^{4}+t^{3}+t^{2}+t | 0 | 1 | 6 |

g^{7} | = | t^{2}+t | 9 | g^{56} | = | t^{4}+t^{3}+t^{2}+t+1 | 0 | 0 | 6 |

g^{8} | = | t^{3}+t^{2} | 63 | g^{55} | = | t^{5}+t^{3}+t^{2}+t | 0 | 1 | 6 |

g^{10} | = | t^{5}+t^{4} | 63 | g^{53} | = | t^{5}+t^{3}+t | 1 | 1 | 6 |

g^{11} | = | t^{5}+t+1 | 63 | g^{52} | = | t^{4}+t^{2}+1 | 1 | 0 | 6 |

g^{12} | = | t^{2}+1 | 21 | g^{51} | = | t^{5}+t^{3}+t+1 | 0 | 1 | 6 |

g^{13} | = | t^{3}+t | 63 | g^{50} | = | t^{5}+t^{4}+t^{2} | 0 | 1 | 6 |

g^{14} | = | t^{4}+t^{2} | 9 | g^{49} | = | t^{4}+t^{3}+t | 0 | 0 | 6 |

g^{15} | = | t^{5}+t^{3} | 21 | g^{48} | = | t^{3}+t^{2}+1 | 1 | 0 | 6 |

g^{16} | = | t^{4}+t+1 | 63 | g^{47} | = | t^{5}+t^{2}+t+1 | 0 | 1 | 6 |

g^{17} | = | t^{5}+t^{2}+t | 63 | g^{46} | = | t^{5}+t^{4}+t | 1 | 1 | 6 |

g^{19} | = | t^{4}+t^{3}+t^{2}+t | 63 | g^{44} | = | t^{5}+t^{3}+t^{2}+1 | 0 | 1 | 6 |

g^{20} | = | t^{5}+t^{4}+t^{3}+t^{2} | 63 | g^{43} | = | t^{5}+t^{4}+t^{2}+t+1 | 1 | 1 | 6 |

g^{22} | = | t^{5}+t^{4}+t^{2}+1 | 63 | g^{41} | = | t^{4}+t^{3}+t^{2}+1 | 1 | 0 | 6 |

g^{23} | = | t^{5}+t^{3}+1 | 63 | g^{40} | = | t^{5}+t^{3}+t^{2}+t+1 | 1 | 1 | 6 |

g^{24} | = | t^{4}+1 | 21 | g^{39} | = | t^{5}+t^{4}+t^{2}+t | 0 | 1 | 6 |

g^{25} | = | t^{5}+t | 63 | g^{38} | = | t^{4}+t^{3}+t+1 | 1 | 0 | 6 |

g^{26} | = | t^{2}+t+1 | 63 | g^{37} | = | t^{5}+t^{3}+t^{2} | 0 | 1 | 6 |

g^{28} | = | t^{4}+t^{3}+t^{2} | 9 | g^{35} | = | t^{3}+t+1 | 0 | 0 | 6 |

g^{29} | = | t^{5}+t^{4}+t^{3} | 63 | g^{34} | = | t^{5}+t^{2} | 1 | 1 | 6 |

g^{30} | = | t^{5}+t^{4}+t+1 | 21 | g^{33} | = | t^{4}+t | 1 | 0 | 6 |

g^{31} | = | t^{5}+t^{2}+1 | 63 | g^{32} | = | t^{3}+1 | 1 | 0 | 6 |

g^{32} | = | t^{3}+1 | 63 | g^{31} | = | t^{5}+t^{2}+1 | 0 | 1 | 6 |

g^{33} | = | t^{4}+t | 21 | g^{30} | = | t^{5}+t^{4}+t+1 | 0 | 1 | 6 |

g^{34} | = | t^{5}+t^{2} | 63 | g^{29} | = | t^{5}+t^{4}+t^{3} | 1 | 1 | 6 |

g^{35} | = | t^{3}+t+1 | 9 | g^{28} | = | t^{4}+t^{3}+t^{2} | 0 | 0 | 6 |

g^{37} | = | t^{5}+t^{3}+t^{2} | 63 | g^{26} | = | t^{2}+t+1 | 1 | 0 | 6 |

g^{38} | = | t^{4}+t^{3}+t+1 | 63 | g^{25} | = | t^{5}+t | 0 | 1 | 6 |

g^{39} | = | t^{5}+t^{4}+t^{2}+t | 21 | g^{24} | = | t^{4}+1 | 1 | 0 | 6 |

g^{40} | = | t^{5}+t^{3}+t^{2}+t+1 | 63 | g^{23} | = | t^{5}+t^{3}+1 | 1 | 1 | 6 |

g^{41} | = | t^{4}+t^{3}+t^{2}+1 | 63 | g^{22} | = | t^{5}+t^{4}+t^{2}+1 | 0 | 1 | 6 |

g^{43} | = | t^{5}+t^{4}+t^{2}+t+1 | 63 | g^{20} | = | t^{5}+t^{4}+t^{3}+t^{2} | 1 | 1 | 6 |

g^{44} | = | t^{5}+t^{3}+t^{2}+1 | 63 | g^{19} | = | t^{4}+t^{3}+t^{2}+t | 1 | 0 | 6 |

g^{46} | = | t^{5}+t^{4}+t | 63 | g^{17} | = | t^{5}+t^{2}+t | 1 | 1 | 6 |

g^{47} | = | t^{5}+t^{2}+t+1 | 63 | g^{16} | = | t^{4}+t+1 | 1 | 0 | 6 |

g^{48} | = | t^{3}+t^{2}+1 | 21 | g^{15} | = | t^{5}+t^{3} | 0 | 1 | 6 |

g^{49} | = | t^{4}+t^{3}+t | 9 | g^{14} | = | t^{4}+t^{2} | 0 | 0 | 6 |

g^{50} | = | t^{5}+t^{4}+t^{2} | 63 | g^{13} | = | t^{3}+t | 1 | 0 | 6 |

g^{51} | = | t^{5}+t^{3}+t+1 | 21 | g^{12} | = | t^{2}+1 | 1 | 0 | 6 |

g^{52} | = | t^{4}+t^{2}+1 | 63 | g^{11} | = | t^{5}+t+1 | 0 | 1 | 6 |

g^{53} | = | t^{5}+t^{3}+t | 63 | g^{10} | = | t^{5}+t^{4} | 1 | 1 | 6 |

g^{55} | = | t^{5}+t^{3}+t^{2}+t | 63 | g^{8} | = | t^{3}+t^{2} | 1 | 0 | 6 |

g^{56} | = | t^{4}+t^{3}+t^{2}+t+1 | 9 | g^{7} | = | t^{2}+t | 0 | 0 | 6 |

g^{57} | = | t^{5}+t^{4}+t^{3}+t^{2}+t | 21 | g^{6} | = | t+1 | 1 | 0 | 6 |

g^{58} | = | t^{5}+t^{4}+t^{3}+t^{2}+t+1 | 63 | g^{5} | = | t^{5} | 1 | 1 | 6 |

g^{59} | = | t^{5}+t^{4}+t^{3}+t^{2}+1 | 63 | g^{4} | = | t^{4} | 1 | 0 | 6 |

g^{60} | = | t^{5}+t^{4}+t^{3}+1 | 21 | g^{3} | = | t^{3} | 1 | 0 | 6 |

g^{61} | = | t^{5}+t^{4}+1 | 63 | g^{2} | = | t^{2} | 1 | 0 | 6 |

g^{62} | = | t^{5}+1 | 63 | g^{1} | = | t | 1 | 0 | 6 |

The tables are still larger than needed: all of the elements in a Frobenius equivalence class are equivalent. Instead of showing m elements with the same color, we might as well put them all in one entry.

In the tables below, a { 1, 2, 4 } means the elements g, g^{2} and g^{4}.

F_{23}, t^{3}+t+1=0, g=t^{2} | |||
---|---|---|---|

x | Tr(x) | x^{-1} | Tr(x^{-1}) |

{ 1, 2, 4} | 0 | { 3, 5, 6} | 1 |

F_{24}, t^{4}+t+1=0, g=t | |||
---|---|---|---|

x | Tr(x) | x^{-1} | Tr(x^{-1}) |

{ 1, 2, 4, 8} | 0 | { 7, 11, 13, 14} | 1 |

{ 3, 6, 9, 12} | 1 | { 3, 6, 9, 12} | 1 |

F_{25}, t^{5}+t^{2}+1=0, g=t^{2} | |||
---|---|---|---|

x | Tr(x) | x^{-1} | Tr(x^{-1}) |

{ 1, 2, 4, 8, 16} | 0 | { 15, 23, 27, 29, 30} | 0 |

{ 3, 6, 12, 17, 24} | 1 | { 7, 14, 19, 25, 28} | 0 |

{ 5, 9, 10, 18, 20} | 1 | { 11, 13, 21, 22, 26} | 1 |

F_{26}, t^{6}+t+1=0, g=t^{3}+1 | |||
---|---|---|---|

x | Tr(x) | x^{-1} | Tr(x^{-1}) |

{ 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 |

F_{27}, t^{7}+t+1=0, g=t^{2} | |||
---|---|---|---|

x | Tr(x) | x^{-1} | Tr(x^{-1}) |

{ 1, 2, 4, 8, 16, 32, 64} | 0 | { 63, 95, 111, 119, 123, 125, 126} | 1 |

{ 3, 6, 12, 24, 48, 65, 96} | 0 | { 31, 62, 79, 103, 115, 121, 124} | 1 |

{ 5, 10, 20, 33, 40, 66, 80} | 0 | { 47, 61, 87, 94, 107, 117, 122} | 1 |

{ 7, 14, 28, 56, 67, 97, 112} | 1 | { 15, 30, 60, 71, 99, 113, 120} | 0 |

{ 9, 17, 18, 34, 36, 68, 72} | 0 | { 55, 59, 91, 93, 109, 110, 118} | 0 |

{ 11, 22, 44, 49, 69, 88, 98} | 0 | { 29, 39, 58, 78, 83, 105, 116} | 0 |

{ 13, 26, 35, 52, 70, 81, 104} | 1 | { 23, 46, 57, 75, 92, 101, 114} | 0 |

{ 19, 25, 38, 50, 73, 76, 100} | 1 | { 27, 51, 54, 77, 89, 102, 108} | 1 |

{ 21, 37, 41, 42, 74, 82, 84} | 1 | { 43, 45, 53, 85, 86, 90, 106} | 1 |

F_{28}, t^{8}+t^{4}+t^{3}+t+1=0, g=t^{2}+1 | |||
---|---|---|---|

x | Tr(x) | x^{-1} | Tr(x^{-1}) |

{ 1, 2, 4, 8, 16, 32, 64, 128} | 0 | {127, 191, 223, 239, 247, 251, 253, 254} | 0 |

{ 3, 6, 12, 24, 48, 96, 129, 192} | 0 | { 63, 126, 159, 207, 231, 243, 249, 252} | 1 |

{ 5, 10, 20, 40, 65, 80, 130, 160} | 1 | { 95, 125, 175, 190, 215, 235, 245, 250} | 1 |

{ 7, 14, 28, 56, 112, 131, 193, 224} | 0 | { 31, 62, 124, 143, 199, 227, 241, 248} | 0 |

{ 9, 18, 33, 36, 66, 72, 132, 144} | 1 | {111, 123, 183, 189, 219, 222, 237, 246} | 0 |

{ 11, 22, 44, 88, 97, 133, 176, 194} | 1 | { 61, 79, 122, 158, 167, 211, 233, 244} | 1 |

{ 13, 26, 52, 67, 104, 134, 161, 208} | 0 | { 47, 94, 121, 151, 188, 203, 229, 242} | 1 |

{ 15, 30, 60, 120, 135, 195, 225, 240} | 1 | { 15, 30, 60, 120, 135, 195, 225, 240} | 1 |

{ 19, 38, 49, 76, 98, 137, 152, 196} | 0 | { 59, 103, 118, 157, 179, 206, 217, 236} | 0 |

{ 21, 42, 69, 81, 84, 138, 162, 168} | 1 | { 87, 93, 117, 171, 174, 186, 213, 234} | 1 |

{ 23, 46, 92, 113, 139, 184, 197, 226} | 0 | { 29, 58, 71, 116, 142, 163, 209, 232} | 1 |

{ 25, 35, 50, 70, 100, 140, 145, 200} | 0 | { 55, 110, 115, 155, 185, 205, 220, 230} | 1 |

{ 27, 54, 99, 108, 141, 177, 198, 216} | 0 | { 39, 57, 78, 114, 147, 156, 201, 228} | 1 |

{ 37, 41, 73, 74, 82, 146, 148, 164} | 0 | { 91, 107, 109, 173, 181, 182, 214, 218} | 1 |

{ 43, 86, 89, 101, 149, 172, 178, 202} | 1 | { 53, 77, 83, 106, 154, 166, 169, 212} | 1 |

{ 45, 75, 90, 105, 150, 165, 180, 210} | 0 | { 45, 75, 90, 105, 150, 165, 180, 210} | 0 |

Lets answer the question: how many 1's are in each table?

Proposition 1: If **m** is odd prime then there is no Frobenius equivalence class that is it's own inverse.

Proof:

Let g be a generator of GF(2^{m})^{*}. Let g^{n} be representative of it's Frobenius equivalence class. If the inverse of g^{n} is an element of the same Frobenius equivalence class then there exists a positive k such that (g^{n})^{(2k)} = g^{(n 2k)} = g^{-n}, and thus n 2^{k} = -n [mod 2^{m} - 1], and thus n (2^{k} + 1) = 0 [mod 2^{m} - 1]. That implies that (2^{k} + 1) devides (2^{m} - 1), but for m odd prime this has no solutions because 2^{m} - 1 has the form cm + 1, where c is an integer, and m does not devide 2^{k}.

Moreover, every element is part of a Frobenius equivalence class with size m and therefore every element is shown precisely once. The total number of elements in the table is q - 2, where the 2 takes the elements 0 and 1 into account that are not shown. Exactly half of all field elements (q/2) have trace 1. The trace of 0 is always 0 and the trace of 1 is 0 for odd m. Therefore, if m is an odd prime, the number of elements in the table for which the trace is 1 is equal to q/2 - 1, where the 1 takes the trace of element 1 into account, and if m is 2 then the number of elements in the table for which the trace is 1 is equal to q/2 = 2 (namely t and t + 1).

The number of 1's in the tables shown is 1/m times that, because we only show Frobenius equivalence classes with m elements at a time. Therefore, the number of 1's in the table with m = 2 is 1, and for m odd prime it is (q/2 - 1)/m.

If m is not prime then it's a bit harder.

Proposition 2: There are no elements in the tables whose inverse is in the same Frobenius equivalence class if m is odd.

Proof:

Let g be a generator of GF(2^{m})^{*}. Let g^{n} be representative of a Frobenius equivalence class given in the table, then the smallest integer i > 0 such that (g^{n})^{(2i)} = g^{n} is i = m. If the inverse of g^{n} is an element of the same Frobenius equivalence class then there exists a positive k such that (g^{n})^{(2k)} = g^{-n}. From that follows that squaring k times again, we get g^{n} back: (g^{n})^{(22k)} = ((g^{n})^{(2k)})^{(2k)} = (g^{-n})^{(2k)} = g^{-(-n)} = g^{n}. From that follows that 2k = m, because there is no value smaller than m for which this equality holds. Therefore, if m is odd, there are no elements with a Frobenius equivalence class size of m whose inverse is in the same Frobenius equivalence class.

Let ect1(m) be the number of elements in Frobenius equivalence classes size m and trace 1. Then the ect1(m) can be calculated by taking the total number of elements with trace 1 and subtracting the number of elements with trace 1 that are in a Frobenius equivalence class with less than m elements. Those elements are precisely the m/d w(m, d) elements with a proper divisor d of m. As seen before, the elements represented by even d have all trace 0, thus we only need to subtract the number of elements with a trace of 1 in the Frobenius equivalence class groups formed by the m/d w(m, d) elements with odd d.

Proposition 3: The total number of elements with trace 1 in Frobenius equivalence classes with size m/d is independent of the chosen generator and is, for odd d, equal to the total number of elements with trace 1 in the Frobenius equivalence classes of w(m/d, 1), which is defined as ect1(m/d).

Proof:

Both, the definition of Frobenius equivalence class as well as trace are independent of the chosen basis. Consider a normal basis { b, b^{2}, b^{4}, b^{8}, ..., b^{2m-1} }, then squaring means rotation of the binary vector that represents the element and therefore, if we need to square no less than m times before we get the original element back, one of the elements of the Frobenius equivalence class is a binary Lyndon word (which is the minimal element in the lexicographical ordering of all its rotations. The minimality implies that a Lyndon word is aperiodic, so differs from any of its non-trivial rotations). Note that there is a 1-on-1 correspondence between binary Lyndon words of size n and Frobenius equivalence classes of size n. Let the number of binary Lyndon words of size n with trace 1 be blwt1(n), it could be represented, for example, by the Lyndon word (abcde...) with n bits, then, because of the 1-on-1 correspondence blwt1(n) = ect1(n) / n.

Note that the trace of an element is equal to the sum of the trace of all it's basis elements. Since the trace of an element of a normal basis is 1, as was explained before, we see that the trace of an arbitrary element is the sum of the bits of its binary vector representation (modulo 2), or equivalently the sum of the bits of the binary Lyndon word corresponding to it's Frobenius equivalence class.

An element from a Frobenius equivalence class with size m/d will repeat after squaring m/d times. Therefore, an element from a Frobenius equivalence class with size m/d can be represented with the binary vector (relative to a normal basis): (abcde...)(abcde...)(abcde...)... repeated d times. Note that the trace is 0 if d is even. For odd d this clearly shows that the number of elements with trace 1 of such form are equal to the number of elements with trace 1 in (abcde...).

See also this link that lists sequence A000048 as the number of binary Lyndon words with trace 1 as function of it's size.

As a result, we can write ect1(m) as follows,

ect1(2) | = | q/2 | = | 2 | = | 2 1 | ||

ect1(3) | = | q/2 - 1 | = | 3 | = | 3 1 | ||

ect1(4) | = | q/2 | = | 8 | = | 4 2 | ||

ect1(5) | = | q/2 - 1 | = | 15 | = | 5 3 | ||

ect1(6) | = | q/2 | - | ect1(6/3) | = | 30 | = | 6 5 |

ect1(7) | = | q/2 - 1 | = | 63 | = | 7 9 | ||

ect1(8) | = | q/2 | = | 128 | = | 8 16 | ||

ect1(9) | = | q/2 - 1 | - | ect1(9/3) | = | 252 | = | 9 28 |

ect1(10) | = | q/2 | - | ect1(10/5) | = | 510 | = | 10 51 |

ect1(11) | = | q/2 - 1 | = | 1023 | = | 11 93 | ||

ect1(12) | = | q/2 | - | ect1(12/3) | = | 2040 | = | 12 170 |

ect1(13) | = | q/2 - 1 | = | 4095 | = | 13 315 | ||

ect1(14) | = | q/2 | - | ect1(14/7) | = | 8190 | = | 14 585 |

ect1(15) | = | q/2 - 1 | - | ect1(15/3) - ect1(15/5) | = | 16365 | = | 15 1091 |

ect1(16) | = | q/2 | = | 32768 | = | 16 2048 | ||

ect1(17) | = | q/2 - 1 | = | 65535 | = | 17 65535 | ||

ect1(18) | = | q/2 | - | ect1(18/3) - ect1(18/9) | = | 131040 | = | 18 7280 |

ect1(19) | = | q/2 - 1 | = | 262143 | = | 19 13797 | ||

ect1(20) | = | q/2 | - | ect1(20/5) | = | 524280 | = | 20 26214 |

ect1(21) | = | q/2 - 1 | - | ect1(21/3) - ect1(21/7) | = | 1048509 | = | 21 49929 |

ect1(22) | = | q/2 | - | ect1(22/11) | = | 2097150 | = | 22 95325 |

ect1(23) | = | q/2 - 1 | = | 4194303 | = | 23 182361 | ||

ect1(24) | = | q/2 | - | ect1(24/3) | = | 8388480 | = | 24 349520 |

ect1(25) | = | q/2 - 1 | - | ect1(25/5) | = | 16777200 | = | 25 671088 |

ect1(26) | = | q/2 | - | ect1(26/13) | = | 33554430 | = | 26 1290555 |

ect1(27) | = | q/2 - 1 | - | ect1(27/3) - ect1(27/9) | = | 67108608 | = | 27 2485504 |

If we define ect1(1) = 1, then this can be written as:

This still doesn't give us the number of 1's in the tables: some elements are given twice, namely those whose inverse is in the same Frobenius equivalence class. As we saw before, this number is zero for odd m.

Before we continue, let us first have a closer look at field extensions. As was shown before, all fields have p^{n} elements, where p is a prime and n the degree of the field. So, if some larger field L is an extension of a smaller field K (meaning that K is a subfield of L) then both necessarily need to have the same characteristic p. Let the larger field have p^{m} elements, and the smaller field p^{n} elements, then n must devide m.

This is easy to understand by realizing that L is in fact K[s]/u(s)K[s], where s is the root of some irreducible polynomial u(s) over K of degree m/n. For example, let K have 2^{6} elements, thus it is isomorphic with F_{64}, or more specifically K = F_{2}[t]/(t^{6}+t+1)F_{2}[t], where t^{6}+t+1 is irreducible over F_{2}. [ Often this is written more concise as K = F_{2}[t]/<t^{6}+t+1>, compare the longer notation with Z/nZ. More in general, R/I (pronounce: R *over* I); where R is a ring and I is called an Ideal of R. An Ideal has the property that if i I then ri I for any r R. ] Now extent this field by adding an indeterminate s and then making it algebraically closed again: L = K[s]/u(s)K[s], where u(s) is irreducible over K. For example, let u(s) = s^{2} + (t^{5} + t^{2})s + 1, which is irreducible over K. We can see both fields as a vector space over some basis. In the case of K we can choose the familiar basis { 1, t, t^{2}, t^{3}, t^{4}, t^{5} }, and represent every element as a binary vector consisting of the coefficients relative to this basis. Likewise, we can choose the basis { 1, s } for L, and write each element of L as a two dimensional vector with elements from K as coefficients. The total number of elements in L is therefore ^{2} = 64^{2} = 4096 = 2^{12}. But wait-a-minute! Aren't all fields with a given number of elements isomorphic? How can this = L be isomorphic with the field that we've been working with all along: F_{2}[x]/<x^{12}+x^{3}+1>? And how does the mapping work that links elements of L to K in that case?

Ok, this mapping is a linear map: it preserves the algebraic relationships between elements. It is a so called homomorphism that assigns 1-on-1 (injective) an element in L to every element in K: , with the properties (a + b) = (a) + (b), (ab) = (a) (b) and (1) = 1 for every a and b in K. [ Note that field homomorphisms are always injective, because its kernel (that what maps to 0) is a proper ideal (it doesn't contain 1, since (1_{K}) = 1_{L}), which must therefore be zero because the only Ideal of a field F is (0) or the whole field itself: let I be a non-zero ideal of F. If a is a non-zero element of I then a^{-1}a = 1 is element of I and thus I = F. Moreover, if (a) = (b) then (a-b) = 0 which, because the ideal is (0), implies that a - b = 0, and thus is injective.] Let every element in L be represented by a 2-dimensional vector (k_{1}, k_{2}) where k_{1} and k_{2} are elements of (a field isomorphic with) K and the element is actually k_{1} + k_{2} s. In this case it is trivial which elements in L correspond to those in K. Let k K, then (k) corresponds to the vector space spanned by the vector (1, 0).

Finding this correspondence between K = F_{2}[t]/<t^{6}+t+1> and L = F_{2}[x]/<x^{12}+x^{3}+1> requires a little bit more work. First, we have to find an element in L (which we can very well call t) that satisfies the equation t^{6}+t+1 = 0. If g is a generator of the multiplicative group L^{*} (L without it's zero), then it turns out that t = g^{65}, where 65 comes from . The other roots of / = 4095 / 63 = 65t^{6}+t+1 = 0 can be found by applying Frobenius repeatedly to g^{65}, each of which could have been used for t as well, of course. Since t is a generator of K, g^65 can subsequently be used to find all elements in L that form the subgroup isomorphic with K in L.

Finally, to really see the link, lets express s in x too! Lets use g = x^{9} + x^{8} + x^{7} + x^{4} + x^{2} + x as generator of L (as found by the function `generator(void)`

in `point/bspacetables3.cc`

). t = g^{65} = x^{11} + x^{10} + x^{8} + x^{7} + x + 1. Furthermore we have u(s) = s^{2} + (t^{5} + t^{2})s + 1 = 0 s^{2} + (x^{10} + x^{7} + x^{6} + x^{3} + x)s + 1 = 0 s = x^{11} + x^{9} + x^{8} + x^{7} + x^{6} + x^{5} + 1 or s = x^{11} + x^{10} + x^{9} + x^{8} + x^{5} + x^{3} + x + 1. And indeed, using one of those s, k_{1} + k_{2}s, where k_{1} and k_{2} run from 0 to x^{5} + x^{4} + x^{3} + x^{2} + x + 1 generates exactly all elements in L from 0 to x^{11} + x^{10} + x^{9} + x^{8} + x^{7} + x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1! So, K[s]/<s^{2}+(t^{5}+t^{2})s+1> and F_{2}[x]/<x^{12}+x^{3}+1> are the same thing after all!

Proposition 4: The elements of a Frobenius equivalence class size m over F_{2m} are not in a proper subfield of the field.

Proof:

Let L = F_{2m} be an extension of the proper subfield K = F_{2n}. This means that n < m and n|m. Let x L be such that the smallest integer k such that x^{2k} = x is for k = m, in other words x is in an Frobenius equivalence class size m over F_{2m}. If x K then the minimal polynomial of x has a degree d <= n < m, and the roots of that polynomial can be found by applying Frobenius d times. In other words, x^{2d} = x and we have a contradiction.

Now we're ready to prove the following proposition.

Proposition 5: The number of Frobenius equivalence classes size m that are their own inverse and where m is even, is blwt1(m/2).

Proof:

blwt1(m/2) is the number of Lyndon words with length m/2 and trace 1. This sequence is well-known, and for example given by A000048. Thus, blwt1(1) = 1, and we can experimentally verify that the proposition holds for m = 2, therefore, for the remainder of the proof, with m = 2n, assume n > 1.

We already saw that a Lyndon word length m has a one-on-one correspondence to the number of Frobenius equivalence classes of size m. Therefore, the proposition is equivalent with: The number of Frobenius equivalence classes size 2n over F_{22n} that are their own inverse is equal to the number of Frobenius equivalence classes size n over F_{2n}, with n > 0 (although we only need to prove it for n > 1).

In terms of elements, since the number of elements in a Frobenius equivalence class is equal to its size, we still have to prove: For n > 1, the number of elements in F_{22n} that are not in a proper subfield of F_{22n} and that have an inverse that is also not in a proper subfield of F_{22n}, is equal to twice the number of elements in F_{2n} that are not in a proper subfield of F_{2n} and have trace 1.

Let x F_{2n} and y F_{22n}. Consider the equation y^{2} + xy + 1 = 0. This being a quadratic equation with coeficients from F_{2n}, there are three possibilities: 1) The equation has one solution, 2) The equation has no solution over F_{2n}, 3) The equation has two solutions over F_{2n}. Case 1) is not interesting because this only happens when x = 0 (namely, the two solutions are y and y + x) and 0 cannot be represented by a Lyndon word for n > 1. Two solutions over F_{22n} always exist: y and 1/y, after all y 0 and (1/y)^{2} + x/y + 1 = (1 + xy + y^{2})/y^{2} = 0. In order for y not to be in a proper subgroup of F_{22n}, the equation may not have solutions over F_{2n} (otherwise y would be in the proper subgroup F_{2n}). Moreover, x may not be in a proper subgroup J of K = F_{2n} (so that [K:J] > 1), because if it were then y would be in a subgroup S such that [S:F_{2}] = [S:J][J:F_{2}] = 2[J:F_{2}] < [L:F_{2}] = [L:K][K:J][J:F_{2}] = 2[K:J][J:F_{2}] and therefore in a proper subgroup of L. Therefore, since both are roots of the same irreducible polynomial (case 2), they are in the same Frobenius equivalence class (namely, y^{2k} = 1/y, as we saw before, with k = n = m/2). Knowing that y + 1/y = x, and since 1/y = y^{2n}, we can write y + y^{2n} = x, and thus see that there will only be solutions over F_{2n} if Tr(x) = 0. We demand case 2, no solutions, and thus Tr(x) = 1. As such we see that the pair of solutions (y, 1/y) over F_{22n} are not in a proper subgroup of F_{22n} if and only if x is not in a proper subgroup of F_{2n} and Tr(x) = 1. Finally we should probably prove that for different x, the solutions y are different, but I consider that trivial, as well as that every y is the solution of the quadratic for some value of x, but that follows trivially from the fact that L is a field extension of K.

The program `testsuite/point/bspacetables3.cc`

was used to count the number of Frobenius equivalence classes with size m, either any, with trace 1, being it's own inverse or both. Also the number of generators and normal basis were counted with and without trace 1, and a combination thereof. Finally the number of Frobenius equivalence classes with a trace equal to the trace of it's inverse (solutions accounted for by w(m, 1)) were counted, as well as those with extra demands like trace 1, generator, normal base and combinations thereof.

Detailed results can be found on the page Brute force counting data for b = 1. A summary follows below.

Code | Description | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|

A | Number of Frobenius equivalence classes (foc(m) / m = A001037): | 1 | 2 | 3 | 6 | 9 | 18 | 30 | 56 | 99 | 186 | 335 | 630 | 1161 | 2182 | 4080 | 7710 | 14532 | 27594 | 52377 | 99858 | 190557 | 364722 | 698870 | 1342176 | 2580795 | 4971008 | 9586395 | 18512790 | 35790267 | 69273666 |

B | Number of Frobenius equivalence classes with trace 1 (blwt1(m) = A000048 (see also proposition 3)): | 1 | 1 | 2 | 3 | 5 | 9 | 16 | 28 | 51 | 93 | 170 | 315 | 585 | 1091 | 2048 | 3855 | 7280 | 13797 | 26214 | 49929 | 95325 | 182361 | 349520 | 671088 | 1290555 | 2485504 | 4793490 | 9256395 | 17895679 | 34636833 |

C | Number of Frobenius equivalence classes that are their own inverse (blwt1(m/2) (propositions 2 and 5)): | 1 | 0 | 1 | 0 | 1 | 0 | 2 | 0 | 3 | 0 | 5 | 0 | 9 | 0 | 16 | 0 | 28 | 0 | 51 | 0 | 93 | 0 | 170 | 0 | 315 | 0 | 585 | 0 | 1091 | 0 |

D | Number of Frobenius equivalence classes that are their own inverse with trace 1 (depends on w(m/2, 1)*): | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 2 | 0 | 2 | 0 | 4 | 0 | 9 | 0 | 14 | 0 | 24 | 0 | 48 | 0 | 86 | 0 | 154 | 0 | 294 | 0 | 550 | 0 |

E | Number of generators (euler_phi(2^{m} - 1) / m = A011260): | 1 | 2 | 2 | 6 | 6 | 18 | 16 | 48 | 60 | 176 | 144 | 630 | 756 | 1800 | 2048 | 7710 | 7776 | 27594 | 24000 | 84672 | 120032 | 356960 | 276480 | 1296000 | 1719900 | 4202496 | 4741632 | 18407808 | 17820000 | 69273666 |

F | Number of generators with trace 1 (no formula): | 1 | 1 | 1 | 3 | 4 | 9 | 7 | 25 | 31 | 87 | 72 | 315 | 381 | 901 | 1017 | 3855 | 3890 | 13797 | 12000 | 42344 | 60043 | 178431 | 138224 | 648031 | 860059 | 2101353 | 2370715 | 9203747 | 8908940 | 34636833 |

G | Number of normal basis (num_normal(m) = A027362): | 1 | 1 | 2 | 3 | 4 | 7 | 16 | 21 | 48 | 93 | 128 | 315 | 448 | 675 | 2048 | 3825 | 5376 | 13797 | 24576 | 27783 | 95232 | 182183 | 262144 | 629145 | 1290240 | 1835001 | 3670016 | 9256395 | 11059200 | 28629151 |

H | Number of normal basis that exist of generators (no formula, A107222): | 1 | 1 | 1 | 3 | 3 | 7 | 7 | 19 | 29 | 87 | 52 | 315 | 291 | 562 | 1017 | 3825 | 2870 | 13797 | 11255 | 23579 | 59986 | 178259 | 103680 | 607522 | 859849 | 1551227 | 1815045 | 9203747 | 5505966 | 28629151 |

I | Number of solutions, w(m, 1) (this is what we want to know) (A137503): | 1 | 0 | 1 | 4 | 3 | 8 | 16 | 28 | 45 | 96 | 167 | 308 | 579 | 1100 | 2018 | 3852 | 7280 | 13776 | 26133 | 49996 | 95223 | 182248 | 349474 | 671176 | 1289925 | 2485644 | 4793355 | 9255700 | 17894421 | 34638296 |

J | Number of solutions with trace 1 (no formula): | 1 | 0 | 1 | 2 | 2 | 4 | 9 | 14 | 24 | 48 | 86 | 154 | 294 | 550 | 1017 | 1926 | 3654 | 6888 | 13092 | 24998 | 47658 | 91124 | 174822 | 335588 | 645120 | 1242822 | 2396970 | 4627850 | 8947756 | 17319148 |

K | Number of solutions that are generators (no formula): | 1 | 0 | 0 | 4 | 2 | 8 | 10 | 26 | 26 | 94 | 76 | 308 | 378 | 902 | 1014 | 3852 | 3908 | 13776 | 11944 | 42460 | 60014 | 178414 | 138360 | 648042 | 859642 | 2101290 | 2370858 | 9202954 | 8910288 | 34638296 |

L | Number of solutions that are generators with trace 1 (no formula): | 1 | 0 | 0 | 2 | 2 | 4 | 4 | 14 | 14 | 46 | 38 | 154 | 192 | 452 | 500 | 1926 | 1956 | 6888 | 5972 | 21238 | 30034 | 89158 | 69164 | 324052 | 429930 | 1050750 | 1185328 | 4601320 | 4454084 | 17319148 |

M | Number of solutions that are normal basis (no formula): | 1 | 0 | 1 | 2 | 2 | 4 | 9 | 12 | 22 | 48 | 62 | 154 | 224 | 332 | 1017 | 1912 | 2712 | 6888 | 12286 | 13912 | 47610 | 91028 | 131094 | 314584 | 644966 | 917600 | 1835144 | 4627850 | 5529896 | 14314976 |

N | Number of solutions that are normal basis and generators (no formula): | 1 | 0 | 0 | 2 | 2 | 4 | 4 | 12 | 13 | 46 | 25 | 154 | 145 | 277 | 500 | 1912 | 1459 | 6888 | 5603 | 11876 | 30005 | 89062 | 51888 | 303761 | 429829 | 775566 | 907684 | 4601320 | 2753361 | 14314976 |

***** Conjecture: the number of Frobenius equivalence classes that are their own inverse with trace 1 is zero if m is odd (proposition 2), equal to w(m/2, 1)/2 if m/2 is odd, or equal to (w(m/2, 1) + et1c(m/4)/(m/4))/2 is m/2 is even.

Ok, anti-climax ... I found how to generate w(m,1), as is now also shown Neil Sloane's integer sequence database as entry A137503.

The following program generates directly the #E (table 1):

#include <iostream> #include <iomanip>

// The number of elements x that have an inverse 1/x (which is every x except 0) that satisfy Tr(x) = Tr(1/x). unsigned long s(int m) { static unsigned long cache[64]; if (cache[m]) return cache[m];

if (m == 1) return 1; if (m == 2) return 3; unsigned long result = (1UL << m) - 1; result -= 1 + s(m - 1) + 2 * s(m - 2);

cache[m] = result; return result; }

int main() { for (int m = 1; m < 64; ++m) std::cout << std::setw(2) << m << ": " << std::setw(14) << (2 * s(m) + 2) << '\n'; }

m | #E |
---|---|

1 | 4 |

2 | 8 |

3 | 4 |

4 | 16 |

5 | 44 |

6 | 56 |

7 | 116 |

8 | 288 |

9 | 508 |

10 | 968 |

11 | 2116 |

12 | 4144 |

13 | 8012 |

14 | 16472 |

15 | 33044 |

16 | 65088 |

17 | 130972 |

18 | 263144 |

19 | 523492 |

20 | 1047376 |

21 | 2099948 |

22 | 4193912 |

23 | 8383412 |

24 | 16783200 |

25 | 33558844 |

26 | 67092488 |

27 | 134225284 |

28 | 268460656 |

29 | 536830604 |

30 | 1073731736 |

31 | 2147574356 |

32 | 4294896768 |

33 | 8589823708 |

34 | 17180121128 |

35 | 34359708196 |

36 | 68719003024 |

37 | 137439487532 |

38 | 274878320312 |

39 | 549754332404 |

40 | 1099512282528 |

41 | 2199025563772 |

42 | 4398042893384 |

43 | 8796092023492 |

44 | 17592194278576 |

45 | 35184365852108 |

46 | 70368733946072 |

47 | 140737511060372 |

48 | 281474974468800 |

49 | 562949910253084 |

50 | 1125899954494568 |

51 | 2251799852369764 |

52 | 4503599493382096 |

53 | 9007199311360364 |

54 | 18014398720839416 |

55 | 36028796694367796 |

56 | 72057593939809248 |

57 | 144115188823166908 |

58 | 288230375600638088 |

59 | 576460751359875076 |

60 | 1152921506652542704 |

61 | 2305843009055095052 |

62 | 4611686014494595352 |

63 | 9223372041104766164 |

Of course, much more analysis will follow...

<To Be Continued>