Additive bases of vector spaces over prime fields

Noga Alon, Nathan Linial, Roy MeshulamJ. Comb. Theory A 1991 · DOI

TL;DR

This paper investigates the concept of "additive bases" for vector spaces over finite fields. The authors prove that a relatively small number of linear bases, dependent only on the field's size, can guarantee that their union forms an additive basis for the entire vector space, regardless of the space's dimension. This has implications for understanding the structure of vector spaces and potentially for applications in areas like coding theory.

What Problem Does This Paper Address?

The paper tackles the question of how many "linear bases" of a vector space over a finite field are needed to guarantee that their union (allowing for repetitions) forms an "additive basis."

Let's break this down:

  • Vector Space over a Prime Field ($Z_p^n$): Imagine a 2D plane where points are represented by pairs of numbers $(x, y)$. If we're working over the prime field $Z_p$, the numbers are integers modulo $p$ (e.g., for $p=3$, numbers are 0, 1, 2). So, $Z_p^n$ is like an $n$-dimensional space where coordinates are taken modulo $p$.
  • Linear Basis: A set of vectors that can be used to uniquely represent any vector in the space as a linear combination. For example, in a 2D plane, $(1,0)$ and $(0,1)$ form a standard basis.
  • Additive Basis: A multiset of vectors such that any vector in the space can be represented as a sum of distinct vectors from the multiset. This is a weaker condition than a linear basis; it allows for repetitions in the sum, but not in the selection of vectors from the multiset. The paper uses a slightly different definition where the coefficients are 0 or 1, meaning each vector from the multiset is either used once or not at all in the sum.
  • The Problem: The authors define $f(p, n)$ as the minimum number of linear bases $B_1, \dots, B_t$ such that their union $\cup_{i=1}^t B_i$ (with repetitions allowed) forms an additive basis for $Z_p^n$. They are looking for bounds on $f(p, n)$, specifically whether it depends only on $p$ (the field size) and not on $n$ (the dimension).

The core question is: how many "building blocks" (linear bases) do we need to ensure we can construct any target vector (any element of $Z_p^n$) by summing up elements from these building blocks?

Methods

The paper presents two main approaches to proving their main theorem:

  1. Exponential Sums (Section 2): This method uses the theory of exponential sums, which are sums of complex exponentials of linear functions. The authors express the number of ways a vector $x$ can be represented as a linear combination of the union of bases as an exponential sum. By analyzing the properties of these sums, particularly their magnitude, they derive an upper bound for $f(p, n)$. This approach involves intricate algebraic manipulations and estimations of sums.
  2. Permanents and Vector Sums (Section 3): This section employs a more combinatorial and algebraic approach using the concept of "permanents" of matrices over finite fields.
  3. Permanents: Similar to determinants, but all terms in the sum are added (instead of alternating signs).
  4. Key Idea: They construct matrices whose columns are derived from the vectors in the linear bases. The permanent of such a matrix being non-zero implies certain properties about the linear combinations of its columns.
  5. Lemmas: The proof relies on several lemmas:
  6. A lemma about multilinear polynomials that are zero on all $\{0,1\}$ inputs.
  7. A crucial lemma connecting a non-zero permanent of a matrix to the ability to form any vector as a sum of a subset of its columns.
  8. A lemma that relates the permanent of a matrix formed by "starred" vectors (a transformation of original vectors) to the original bases.
  9. Strategy: The strategy is to show that if you have enough linear bases, you can always select a specific subset of vectors from these bases such that the matrix formed by their "starred" versions has a non-zero permanent. This, by the previous lemmas, guarantees an additive basis.

Datasets

Not discussed in the paper. The paper is theoretical and deals with abstract vector spaces and fields, not empirical data or specific datasets.

Key Insights and Ideas

  • Dimension Independence: The most significant insight is that the number of linear bases required, $f(p, n)$, can be bounded by a function of $p$ alone, specifically $c(p) \log n$. This means that for a fixed prime field $Z_p$, as the dimension $n$ of the vector space grows, the number of bases needed to guarantee an additive basis doesn't grow unboundedly; it grows only logarithmically with $n$.
  • The Power of Union: The paper demonstrates that even if individual linear bases are "small" or "special," their union (with repetitions) can be surprisingly powerful in spanning the entire vector space additively.
  • Two Distinct Proofs: The existence of two different proofs (using exponential sums and permanents) for the same main result lends strong support to its validity and highlights the versatility of mathematical tools in tackling such problems.
  • Connection to Permanents: The second proof reveals a deep connection between the algebraic structure of vector spaces and the combinatorial properties of permanents of matrices over finite fields.

Key Results

  • Theorem 1.1: The main result states that $f(p, n) \le c(p) \log n$ for some constant $c(p)$ depending only on $p$.
  • The exponential sum method yields $f(p, n) \le 1 + (p^2/2) \log(2pn)$.
  • The permanent-based method yields $f(p, n) < (p-1) \log n + p-2$.
  • Lower Bound: The paper establishes a lower bound of $f(p, n) \ge p-1$. For $p \ge 3$ and $n \ge 2$, this can be improved to $f(p, n) \ge p$.

Limitations and Future Work

  • Conjecture: The authors conjecture that $f(p, n)$ is bounded by a function of $p$ alone, suggesting that $f(p, n) \le p$. This is a stronger statement than what they proved.
  • Open Problems: The paper explicitly lists open problems, including:
  • Determining the exact value of $c(p)$ in the bound $f(p, n) \le c(p) \log n$.
  • Proving the conjecture $f(p, n) \le p$.
  • A conjecture about permanents (Conjecture 4.3) that would imply $f(p, n) \le p$.
  • Specific Cases: While the results are general, exploring specific values of $p$ and $n$ might reveal further insights.
  • Applications: The paper mentions motivation from "universal flows in graphs" and "group connectivity of graphs," suggesting that further research could explore direct applications of these additive basis results in graph theory and related areas.

Summary updated

BibTeX
@article{alon1991additive,
  author = {Noga Alon and Nathan Linial and Roy Meshulam},
  title = {{Additive bases of vector spaces over prime fields}},
  journal = {J. Comb. Theory A},
  year = {1991},
  doi = {10.1016/0097-3165(91)90045-i},
}

Loading related content...

Figure