[seqfan] Re: deja vu

[Joerg Arndt]

* Allan Wechsler <acwacw at gmail.com> [Dec 29. 2014 08:39]:
> [...]

> 
> Perhaps something obvious is going on here; I don't understand the
> definition of A003474 yet.
> 

[the following peeled from my own book, please check]

The number of normal bases of GF(p^n) over GF(p) (for p prime)
  N(n, p) = p^n/n * prod( d_i , (1-1/p^{d_i})^({m_i}) )
if the polynomial  x^n - 1 (over GF(p)) factors (roughly, see below) as
  x^n - 1  =  \prod( i , f_i^{m_i} )

Example (from the Fxtbook p.906-907) for p=2:
  x^15 - 1 = (x^15+1) = (x+1) * (x^2+x+1) * (x^4+x+1) * (x^4+x^3+1) * (x^4+x^3+x^2+x+1)
We have one factor of deg 1, one of deg 2, and three of deg 4,
so (symbolically) we have
  15 = 1*1 + 1*2 + 3*4
(that's a partition of 15), and
  phi(15, 2) = 2^15/15 * (1 - 1/2^1)^1 * (1 - 1/2^2)^1 * (1 - 1/2^4)^3 = 675

For the computation one does not need to factor x^n - 1, because
we now the factors (cyclotomic polynomials).
This gives the formula shown in the Fxtbook right after the discussion above.

The generalized Euler function phi(m, p) is N(n,p) * n
Example:   A003473(n) = n * A027362(n)

Best regards,  jj

P.S.: am I the only one to find
  http://arxiv.org/abs/1405.0113
hard to understand?


> [...]