How many essentially different generating sets of cardinality $d +1$ are there in a vector space $V$ of dim $d$ over a field of prime cardinality $p$?

Let $p$ be a prime number and let $V$ be a finite dimensional vector space over the field with $p$ elements. Let $d$ denote its dimension. For the purpose of this question let us say two subsets $A,A'$ of $V$ are equivalent if there exists an automorphism $f$ of $V$ such that $f(A)=A'$.

This notion of "equivalent" gives an equivalence relation on the set of subsets of $V$.

Question: What is the number of equivalence classes of generating subsets of $V$ of cardinality $d+1$?

To be precise, maybe I should say: "the number of equivalence classes that contains some generating subset of cardinality $d+1$." Yet, note that if a class contains one generating subsets of cardinality $d+1$ then all sets in this class are generating subsets of cardinality $d+1$, so ultimately different interpretations should yield the same problem.

I would be interested both in exact results as well as in estimates and/or pointers to relevant literature.

Context: I often need to study properties of generating subsets in finite dimensional vector space over the field with $p$ elements (think of coding theory if this at first glance seems like a strange thing to study). Usually, the properties I care about are invariant under automorphisms. Thus, in my investigations I can assume "without loss" that the set contains a specific fixed basis. Sometimes I wonder how many cases I would need to distinguish, if I would want to go one step further, and fix one element in addition to the basis.

Since so far I was always either in the case "it is easy to figure out in my current vector space" or "too many to be useful" I never investigated this seriously. Yet, I thought about it a bit and it did not seem obvious either, but maybe I just do not look at it from the right angle.

Example and further comments: Let $B= \{e_1,\dots, e_d\}$ be a basis. For $g \in V \setminus B$ the set $A_g = B \cup \{g\}$ is generating of cardinality $d+1$. It is not hard to see that each of the equivalence classes we want to count contains some set of the form $A_g$. Thus their number is bounded by $|V \setminus B|$.

But $A_g$ and $A_h$ can very well be equivalent for distinct $g,h$.

One phenomenon are permutations. If $g=\sum_{i=1}^d a_ie_i$ and $h = \sum_{i=1}^d a_{\sigma(i)}e_i$ for some permutation $\sigma \in \mathfrak{S}_d$ then $A_g$ and $A_h$ are equivalent.

But this is not all. For example, let $e_0 = \sum_{i=1}^d e_i$. Then $e_1 =e_0 - \sum_{i=2}^d e_i$, and one thus sees that for $f_0 =e_1 - \sum_{i=2}^d e_i$, one has $A_{e_0}$ and $A_{f_0}$ are equivalent.

Solution 1:

The following observations are simple but they are too long for a coment and I allowed myself to stress them as an answer hoping that the proposed reduction may direct a way to an answer of Question.

Let $\Bbb F$ be the field with $p$ elements and $A=\{a_1,\dots, a_{d+1}\}$ be a generating subset of $V=\Bbb F^d$ of cardinality $d+1$. Then the set $A$ is linearly dependent, that is there exists a non-zero annulating vector $x=(x_1,\dots, x_{d+1})\in \Bbb F^{d+1}$, that is $\sum x_ia_i=0$. Since the set $A$ contains a basis, the vector $x$ is defined uniquely up to a multipliction by a non-zero scalar of $\Bbb F$. Moreover, if $f$ is an arbitrary automorphism of $V $ then $\sum x_if(a_i)=0$, so $f$ preserves the annulating vector of a generating set (up to a permutation of its coordinates).

Conversely, let $x\in \Bbb F^{d+1}$ be a non-zero vector. Without loss of generality, after a multipliction by a non-zero scalar and a permutation of coordinates, we may suppose that $x_{d+1}=1$. Given a basis $a_1,\dots, a_d$ in $V$ if we put $a_{d+1}=-\sum x_ia_i$, then we obtain a generaring set $A=\{a_1,\dots, a_{d+1}\}$ with the annualting vector $x$.

Thus the number of equivalence classes of generating subsets of $V$ of cardinality $d+1$ equals the number of equivalence classes of non-zero vectors of $\Bbb F^{d+1}$ with respect to a multipliction by a non-zero scalar and a permutation of coordinates.

This allows us to calculate the required number for small $p$. If $p=2$ then the vector equivalence class is uniquely determined by the number $n_0$ of its zero coordinates, which is from $0$ to $d$. That is in this case the answer is $d+1$. If $p=3$ then the vector equivalence class is uniquely determined by the number $n_0\le d$ of its zero coordinates and the size $\lceil(d+1-n_0)/2\rceil\le n_1\le d+1-n_0$ of the non-smaller group of its non-zero coordinates. That is in this case the answer is $\sum_{n_0=0}^d \lfloor (d+3-n_0)/2\rfloor$. This experssion equals $(d^2+6d+4)/4$ if $d$, is even and equals $(d^2+6d+5)/4$, if $d$ is odd.