[seqfan] Re: deja vu
Joerg Arndt
arndt at jjj.de
Tue Dec 30 17:33:23 CET 2014
* 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?
> [...]
More information about the SeqFan
mailing list