1 Introduction
A super-Vandermonde set (short: an sV-set) in GF(q), \(q=p^h\), p a prime, is a set T of size \(1<t<q\) such thatfor \(0< k< t\). It follows from the non-singularity of the Vandermonde matrices \((y^k)_{yk}\), \(y\in T\) and \(k\in [0,t)\) resp. \(k\in (0,t]\) that \(0\not \in T\) and that \(\pi _t(T)\ne 0\) (in particular \(p\!\not \!|\,\,t\)). The Newton identities relating the power sums \(\pi _k(T)\) and the elementary symmetric polynomials \(\sigma _k(T)\) imply that in the polynomialthe only possible nonzero coefficients are the constant term \((-1)^t\sigma _t\) and the coefficient of \(Z^{t-k}\): \((-1)^k\sigma _k\) with \(k=0\mod p\). The Newton-identities are given by:and we see that indeed \(\sigma _k=0\) if k is not divisible by p (and less than t).
$$\begin{aligned} \pi _k(T):=\sum _{y\in T} y^k=0~, \end{aligned}$$
$$\begin{aligned} f(Z):=\prod _{y\in T}(Z-y)=\sum (-1)^k\sigma _k(T)Z^{t-k}~, \end{aligned}$$
$$\begin{aligned} k\sigma _k = \sum _{m=1}^k (-1)^{m-1}\pi _m\sigma _{k-m}~, \end{aligned}$$
In terms of the inverses of the elements in T, we get that being sV is equivalent towith g a p-th power.
$$\begin{aligned} \phi (Y):=\prod _{y\in T} (Y-y^{-1})=Y^t+g(Y)~, \end{aligned}$$
Advertisement
The underlying notion of Vandermonde set was introduced by Gács and Weiner in [1]. They appear at several places in the investigation of special point sets in finite projective planes. More about this, as well as many examples, can be found in Chapter 1 of the thesis of Takáts [2], or in her paper [3] with Péter Sziklai, which also classifies small and large sV-sets. Here small means \(t<p\), and small sV-sets are cosets of multiplicative subgroups of \({GF(q)}^*\): in this case the polynomial g is constant, sowhere \(t\,|\,q-1\) and c is a t-th power, so that T is a coset of the group of t-th roots of unity.
$$\begin{aligned} \phi (Y)=\prod _{y\in T} (Y-y^{-1})=Y^t-c~, \end{aligned}$$
By large we mean \(t>q/p\) and again we get cosets of multiplicative subgroups, corresponding to the case that \(g=-c\) is constant. The proof in this case is much more involved, but in the final section we will give a simpler proof.
2 Super-Vandermonde sets of size \(p+1\)
If T is an sV-set of size \(p+1\), then the polynomial \(\prod _{y\in T} (Z-y)\) is of the form \(f(Z)=Z^{p+1}+aZ+b\), so our problem is to classify the polynomials of this form that are fully reducible over GF(q). Notice that two different polynomials of this form have a gcd of degree at most one, so that two elements of GF(q) are contained in at most one sV-set of size \(p+1\). We will see in fact that two elements are contained in an sV-set of this size precisely when they have the same GF(p)-norm. We will prove in the next theorem that they can all be obtained from 2-dimensional GF(p)-vector subspaces of GF(q).
Theorem 2.1
Let T be an sV-set in GF(q), \(q=p^h\), p prime, of size \(p+1\). Then there exists \(\alpha \in {GF(q)}^*\) such thatwhere \(\{ x_1,\dots ,x_{p+1}\}\) represent the 1-dimensional subspaces of a 2-dimensional GF(p)-vector subspace of GF(q).
$$\begin{aligned} T=\{\alpha x_1^{p-1},\dots ,\alpha x_{p+1}^{p-1}\}, \end{aligned}$$
(1)
Advertisement
Conversely, every 2-dimensional GF(p)-vector subspace of GF(q) defines a family of \(q-1\) sV-sets of type (1). In particular, the elements of an sV-set of size \(p+1\) have the same norm over GF(p).
Proof
We first observe that if \(T=\{y_1,\dots ,y_t\}\) is an sV-set, then for each \(\gamma \in {GF(q)}^*\), the set \(\gamma T=\{\gamma y_1,\dots ,\gamma y_t\}\) is an sV-set as well (and of the same size of course). We first show that 2-dimensional subspaces give rise to sV-sets. Let U be a 2-dimensional GF(p)-vector subspace of GF(q), then U is the set of zeros of a polynomial of the formfor some \(a,b\in {GF(q)}\). If \(x_1\) and \(x_2\) are two nonzero roots of (2) which are not proportional over GF(p), then \(x_1^{p-1}\) and \(x_2^{p-1}\) are two different roots of the polynomial \(Z^{p+1}+aZ+b\), which turns out to be fully reducible over GF(q). It follows that for each \(\alpha \in {GF(q)}^*\)
is an sV-set of size \(p+1\).
$$\begin{aligned} X^{p^2}+aX^p+bX, \end{aligned}$$
(2)
$$\begin{aligned} \alpha T=\{\alpha x^{p-1}:\ x \hbox { is a nonzero root of (2)} \} \end{aligned}$$
On the other hand let \(T=\{y_1,\dots ,y_{p+1}\}\) be an sV-set of size \(p+1\) and letbe the associated polynomial. Then, there exist \(y_i,y_j\in T\), with the same GF(p)-norm \(\delta \). Let \(\alpha \) be an element of \({GF(q)}^*\) with norm \(N(\alpha )=\delta \) and set \(z_k:=y_k/\alpha \), for \(k\in \{1,\dots ,p+1\}\). Thenis an sV-set of size \(p+1\) with \(N(z_i)=N(z_j)=1\) and its associated polynomial isDenoting by \(x_i\) and \(x_j\) the elements of \({GF(q)}^*\) such that \(z_i=x_i^{p-1}\) and \(z_j=x_j^{p-1}\), then \(x_i\) and \(x_j\) are independent over GF(p) and so \(U:=\langle x_i,x_j\rangle \) is a 2-dimensional GF(p)-vector subspace of GF(q), whose elements are the zeros of the polynomialIt follows that the elements of \(\frac{1}{\alpha }T\) are of the form \(x^{p-1}\). This completes the proof. \(\square \)
$$\begin{aligned} f(Z)=Z^{p+1}+aZ+b \end{aligned}$$
(3)
$$\begin{aligned} \frac{1}{\alpha }T:=\{z_1,\dots ,z_{p+1}\}, \end{aligned}$$
$$\begin{aligned} Z^{p+1}+\frac{a}{\alpha ^p}Z+\frac{b}{\alpha ^{p+1}}. \end{aligned}$$
$$\begin{aligned} X^{p^2}+\frac{a}{\alpha ^p}X^p+\frac{b}{\alpha ^{p+1}}X. \end{aligned}$$
3 Super-Vandermonde sets of size \(q/p-1\)
Consider the polynomial \({\hbox {Tr}_{q\longrightarrow p}}(aZ)=aZ+a^pZ^p+\cdots +a^{p^{h-1}}Z^{p^{h-1}}\), the trace from GF(q) to GF(p). It is clearly fully reducible over GF(q), and we see that the nonzero roots form an sV-set of size \(q/p-1\). The aim of this section is to prove the converse:
Proposition 3.1
Let T be an sV-set in GF(q), of size \(q/p-1\), (\(q=p^h\)) thenfor some \(a\in {GF(q)}^*\).
$$\begin{aligned} \prod _{y\in T} (Z-y)=(a_{h-1}Z)^{-1}{\hbox {Tr}_{q\longrightarrow p}}(aZ) \end{aligned}$$
Proof
Consider as before the polynomialwhere g is a p-th power. Let \(T_a\) be the sV-set corresponding to the hyperplane \(\hbox {Tr}(aZ)=0\) withThe greatest common divisor of \(\phi \) and \(\phi _a\) divides \((g(Y)-g_a(Y))^{1/p}\) of degree at most \(q/p^2-1\). So we find that T has at most \(q/p^2-1\) points in every hyperplane, unless it coincides with it. Since the average size of the intersection of T with a hyperplane equalswe see that for some a, T coincides with \(T_a\). \(\square \)
$$\begin{aligned} \phi (Y)=\prod _{y\in T} (Y-y^{-1})=Y^{q/p-1}+g(Y)~, \end{aligned}$$
$$\begin{aligned} \phi _a(Y):=\prod _{y\in T_a} (Y-y^{-1}) = Y^{q/p-1}+g_a(Y). \end{aligned}$$
$$\begin{aligned} \frac{q/p-1}{q-1}\cdot \left( \frac{q}{p}-1\right) >\frac{q}{p^2}-1~, \end{aligned}$$
4 Large super-Vandermonde sets
Proposition 4.1
Let T be an sV-set in GF(q), \(q=p^h\) of size \(t>q/p\), thenfor some t-th power \(c\in {GF(q)}^*\), so T is coset of a multiplicative subgroup.
$$\begin{aligned} \prod _{y\in T} (Y-y^{-1})=Y^t-c \end{aligned}$$
Proof
As before \(\phi (Y)=\prod _{y\in T} (Y-y^{-1})=Y^t+g(Y)\), where g is a p-th power. Since this polynomial is fully reducible we may write:where also the polynomials \(h_i\) are p-th powers. We now equate left and right the terms of degree d mod p, \(d=0,p-1,\dots ,1\), writing \(e=t-q/p\) and \(E=q/p\):
We look at the divisibility by Y. From the last equation we see that \(h_1\) is not divisible by Y, in particular \(h_1\ne 0\), then we see from the other equation involving \(h_1\) that \(h_{1+e}\) is divisible by \(Y^{E}\), next \(h_{1+2e}\) by \(Y^{2E}\), (where of course we take indices mod p) and so on until finally \(h_{1+(p-1)e}=h_{p-e+1}\) is divisible by \(Y^{(p-1)E}=Y^{q-q/p}\). If \(h_{p-e+1}\) is nonzero then the total degree of the left hand side will be at least \(t+1+q-q/p>q\), a contradiction, so \(h_{p-e+1}=0\) and now the last equation tells us that g is constant. \(\square \)
$$\begin{aligned} (Y^t+g)(h_0+Yh_1+\cdots +Y^{p-1}h_{p-1})=Y^q-Y,~~~~q=p^h, \end{aligned}$$
Acknowledgments
This research was supported by the Italian national research project Geometrie di Galois e Strutture di Incidenza (COFIN 2012), by the Dipartimento di Matematica e Fisica of the Seconda Università degli Studi di Napoli and by GNSAGA of the Italian Istituto Nazionale di Alta Matematica.
Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.