Small Characteristic Sum-Check

The following proofs occured originally in "Power Sums over Finite Subspaces of a Field [BC99], but was included in the Aurora paper [BSCRSVW18] in which this sumcheck was introduced. The following details an efficient sumcheck over subspaces of $F_{q}^{k}$ : vector spaces over $F_{q}$ spanned by a set of vectors/elements ${v_{1}, \dots, v_{n}} \subseteq F_{q}^{k}$ . These techniques are efficient when $q$ is small, for instance, $q = 2$ .

Theorem

Let $H$ be an affine subspace of $F_{q^{k}}$ and let $i < ∣ H ∣ - 1$ , then:

$0 = x \in H \sum x^{i}$

In other words, summing any sufficiently small power of elements in an affine subspace of $F_{q}^{k}$ yields zero.

Definition

The generalized derivative of a polynomial $f (x)$ is defined as:

$Δ_{v} (f) = s \in F_{q} \sum f (X + s \cdot v)$

For $v_{1}, \dots, v_{n} \in F_{q^{k}}$ we inductively define the derivative in the direction $(v_{1}, \dots, v_{n}) \in F^{n}$ as:

$Δ_{(v_{1}, \dots, v_{n})} = Δ_{v_{1}} (Δ_{(v_{2}, \dots, v_{n})})$

Observe that the summation is over the finite field $s \in F_{q}$ , not the whole field $F_{q^{k}}$ , where as the "direction" $v \in F_{q^{k}}$ is from the whole field. In other words, the direction $v \in F_{q^{k}}$ is a vector (extension field element), and we consider all steps (scalar multiples) $s \in F_{q}$ in the direction of this vector. When there are multiple directions, we consider the sum over all the combinations:

$Δ_{v_{1}, v_{2}} (f) = s_{1} \in F_{2} \sum s_{2} \in F_{2} \sum f (X + s_{1} \cdot v_{1} + s_{2} \cdot v_{2})$

The relevance to the question at hand is clear: if $v_{1}, \dots, v_{n} \in F_{q^{k}}$ are a basis, then:

$Δ_{v_{1}, \dots, v_{n}} (δ) = s_{1}, \dots, s_{n} \in F_{q} \sum f (X + s_{1} \cdot v_{1} + \dots + s_{n} \cdot v_{n} + δ)$

Which is exactly the sum of $f (X)$ over all elements in the affine space $H = ⟨ v_{1}, \dots, v_{n} ⟩ + δ \subseteq F_{q^{k}}$ .

Next, we define a notion of "weight". The trick is going to be induction over this "metric": it measures the "size" of a polynomial and we will prove by induction that the statement holds up to a given "size", which happens to contain all polynomials of degree less than $∣ H ∣ - 1$ .

Definition

The $q$ -nary digit sum $ds_{q} (n)$ of a number $n \in N$ is the sum of the digits in its $q$ -nary representation. Let $n \in N$ and write it as:

$n = i = 0 \sum n_{i} \cdot q^{i}$

Where $n_{i} [0, q)$ . Then the $q$ -nary digit sum of $n$ is defined as: $ds_{q} (n) = i = 0 \sum n_{i}$

So, we the induction is going to be over the "size" of the exponents in the polynomial, where "size" is measured by the $q$ -nary digit sum of the degree of the polynomial. We introduce the notion of "weight" for a polynomial, which is simply the maximum $q$ -nary digit sum of its exponents of any (non-zero) monomial.

Definition

The weight $wt (f)$ of a polynomial $f (X)$ is the maximum $q$ -nary digit sum of its exponents of any (non-zero) monomial. Let:

$f (X) = i = 0 \sum d a_{i} \cdot X^{i}$

Where $a_{d} \neq = 0$ . Then:

$wt (f) = i max ds_{q} (i)$

Our first claim is that applying $Δ_{v} (f)$ reduces the "weight" of any polynomial:

$wt (Δ_{v} (f)) \leq max {wt (f) - (q - 1), 0}$

With the max simply being there, because the weight of the polynomial is always non-negative.

We also claim that if $wt (f) < q - 1$ , then $Δ_{v} (f) = 0$ .

Proof.

Let $f (X) = X^{d}$

$Δ_{v} (X^{d}) = s \in F_{q} \sum (X + s \cdot v)^{d} = s \in F_{q} \sum c = 0 \sum d (c d) X^{d} s^{d - c} v^{d - c} = d = 0 \sum d (c d) X^{d} v^{d - c} \cdot s \in F_{q} \sum s^{d - c} = c = 0 \sum d (d c) X^{c} v^{d - c} \cdot s \in F_{q} \sum s^{\sum_{i = 0}^{k} (d_{i} - c_{i}) q^{i}} = c = 0 \sum d (d c) X^{c} v^{d - c} \cdot s \in F_{q} \sum s^{\sum_{i = 0}^{k} (d_{i} - c_{i})} = c \leq_{q} d \sum (c d) X^{c} v^{d - c} \cdot s \in F_{q} \sum s^{ds (d) - ds (c)}$

The rewrites are as follows:

Expanding the definition of $Δ_{v} (f)$ .
Is the binomial expansion of some $(a + b)^{k}$ .
Rearranging sums.
A
Removes the $q^{i}$ in the exponents: since $s \in F_{q}$ , $s^{q^{i}} = s$ for all $i$ .
When $d >_{q} c$ then $(c d) = 0 mod q$ : $(c d) = \frac{d !}{c ! ( d - c )!}$

The theorem trivially extends to polynomials of degree less than $∣ H ∣ - 1$ : since the sum over the affine space of every monomial of degree less than $∣ H ∣ - 1$ is zero, then so must the sum of the sum of monomials: the sum of the polynomial over the affine space:

Keyboard shortcuts

Small Characteristic Sum-Check