# Spanning set for $\mathbb{Z}_2^{1+b(a+1)}$

Given finite field $GF(2^b)$ with elements $v_1,\ldots,v_{2^b}$, and integer $a$ such that $2^{b} \geq 2(a+1)!$, I am trying to locate a proof that the set of column vectors $e_i = (1,v_i,v_i^3,\ldots,v_i^{2a+1})^{\operatorname{T}}$, $1 \leq i \leq 2^b$, form a spanning set for additive group $\mathbb{Z}_2^{1+b(a+1)}$ (where each $v_i$ is itself a column vector, so $e_i$ is a vector of length $1+b(a+1)$).

Firstly, is this statement actually true? I'm aware a series of vectors don't really 'span' a group in the sense of a basis, but I mean that each element of $\mathbb{Z}_2^{1+b(a+1)}$ is a linear combination of the $e_i$.

Secondly, if indeed it is true (I believe/hope it is!), is there a particularly nice and elementary or concise way to prove it? Thanks for your help!

-
Are there any limitations on the size of the parameter $a$? There are only $2^b$ vectors $e_i$, so they cannot span the whole group, when $2^b<1+b(a+1)$. – Jyrki Lahtonen Mar 7 '12 at 21:43
Ah yes I missed a condition sorry! I was thinking something didn't look right. The condition is written as $2^{b} \geq 2(a+1)!$, which I presume means to say the 2 is outside the factorial; I have added this to the original statement. Does this suffice now? – Sosumi Mar 7 '12 at 21:52
Doesn't look like that is enough. The counterexample in my answer has $a=2$, $b=4$. – Jyrki Lahtonen Mar 7 '12 at 22:00

One problem (there may be others) is related to the norm maps. As the smallest example consider the case $b=4$. The (relative) norm map $N(x)=x^5$ from $GF(16)$ to itself only takes values in the subfield $GF(4)$. Therefore the component $v_i^5$ will have only four possible values, and these four values form a proper additive subgroup. Thus those components will never span all of $GF(16)$. The problem can be described by stating that all the vectors $(1,x,x^3,x^5)$ with $x$ ranging over $GF(16)$ belong to the subgroup $GF(2)\oplus GF(16)\oplus GF(16)\oplus GF(4)$. Therefore they cannot span anything bigger.
Similar cases occur for suitable values of $a$ whenever the field $GF(2^b)$ has proper subfields, i.e. unless $b$ is a prime. I need to sleep on it to determine, whether the extra condition $2^b\ge 2(a+1)!$ rules out all but finitely many of these norm map problems.
I see. My ultimate intention here was to show that, given the $d=2^b$ elements $v_i$ of $GF(2^k)$ represented as length-$b$ column vectors, the Cayley graph with vertices $\mathbb{Z}_2^{1+b(a+1)}$ and spanning set $S = \{e_1,\ldots,e_d\} \subseteq \mathbb{Z}_2^{1+b(a+1)}$ was connected when $d \geq 2(a+1)!$. Is this statement also false, or have I somehow made an error in translating one proposition to the other? – Sosumi Mar 7 '12 at 22:11
A suggested argument said that we simply need to confirm that the matrix with columns $e_i$ has rank 1+b(a+1); since this is the number of rows, we just need to check that no nontrivial linear combination of the rows is the zero vector, which is apparently feasible - I couldn't see how that was obvious though, and was hoping for a nicer method... – Sosumi Mar 7 '12 at 22:23
@Sosumi, IIRC doesn't it happen that the cosets of the spanned subgroup form the connectivity components of the Cayley graph? I'm a bit rusty with the Cayley graphs :-) Anyway, I think that the case $b=4,a=2$ is the only case, where the norm map destroys your conjecture. It may well happen that your conjecture holds in all the other cases (with the condition $d\ge 2(a+1)!$ in place). The dimension formula for binary BCH-codes probably takes care of this. But it is past my bedtime, and I need to think about this a bit more. Hopefully somebody else can help you while I'm counting sheep. – Jyrki Lahtonen Mar 7 '12 at 22:24