# 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

## 1 Answer

I'm afraid the answer to you question is negative, unless you place some restrictions on the parameters.

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
Thanks for your help so far! The suggested method did indeed go on to say that the linear independence 'followed from the theory of BCH codes', but since I didn't know anything about them I was simply hoping there might be a method which avoided that road which I would find more natural. Anyway, it's an interesting unique case if you are correct - much of the maths I am studying is 'for (parameter) large enough', so it may be that this single failing is just ignored here. –  Sosumi Mar 7 '12 at 22:36