# Subsets $E$ of $\mathbb{F}_{p^k}$ with vanishing polynomial subset sums

The following question arose in some discussions recently as a misunderstanding of another problem.

Question: Which subsets $$E\subset \mathbb{F}_{p^k}$$ satisfy the property that $$\sum\limits_{x\in E}Q(x)=0$$ for all $$Q(x)$$ polynomials in $$\mathbb{F_{p}}[x]$$ of degree less or equal to $$t$$?

Zero here is the additive identity in the field $$\mathbb{F}_{p^k}$$.

A sub problem of the above which should be manageable is the following question:

Question: Does the collection of sets $$E$$, each of size $$p$$ and containing the origin which satisfy the above condition for $$t \leq p-2$$ consist precisely of the $$\frac{p^{k}−1}{p−1}$$ lines (containing $$0$$) in $$\mathbb{F}_{p^k}$$?

(Note the condition $$t\leq p-2$$ is needed by Fermat's little theorem, $$0^{p-1}+1^{p-1}+...+(p-1)^{p-1}=1+1+...+1=p-1\neq 0$$.)

This has been computationally verified for $$\mathbb{F}_{5^3}$$ below.

A simple example to clarify the first problem follows: the condition in the question can be reformulated as a collection of statements, namely $$\sum\limits_{x\in E} x^{m}=0\ \text{for all } m\leq t,$$ due to the fact that the first statement by restriction implies all of the second statements. Further, given $$Q(x)=a_{0}+a_{1}x+\dots+a_{t}x^t$$, the equalities in the second statement can be added to give that $$\sum\limits_{x\in E} Q(x)=0$$.

The first condition $$\sum\limits_{x\in E} 1=0$$ shows exactly that $$N=|E|$$ is a multiple of $$p$$.

The case $$t=1$$ also is not difficult. Here one gets a linear condition on the elements of $$E$$. The interesting question is what these sets look like, especially when $$k$$ and $$t$$ are not too small.

There are some natural invariants of such sets $$E$$ like multiplication of elements in $$E$$ by a constant multiple (where constant here means constant in $$\mathbb{F}_{p}$$). For $$y\in\mathbb{F}_{p}$$ a constant, $$E+y=\{x+y\ |\ x\in E\}$$ is also a vanishing set if $$E$$ is. Both of these follow from the fact that the set of polynomials of degree bounded by $$t$$ are invariant under the corresponding operations.

Consider the vanishing condition for quadratics with $$p=5$$ and $$k=3$$. For example, let $$\mathbb{F}_{5^3}$$ be represented by the quotient of $$\mathbb{F}_{5}[x]$$ by $$g(x)=x^3+x+1$$ (which is irreducible in $$\mathbb{F}_{5}[x]$$). Letting the coefficients of each element in $$\tilde{E}$$ be given by the formula $$p_{j}(x)=a_{j}x^2+b_{j}x+c_{j}$$ ($$\tilde{E}$$ here is just the representatives of $$E$$ in reduced form in the quotient of $$\mathbb{F}_{5}[x]$$ by $$g(x)=x^3+x+1$$), then the condition $$\sum\limits_{p(x)\in \tilde{E}} p(x)^2=0$$ can be checked to be equivalent to three equalities : $$\begin{eqnarray*} \sum\limits_{j=1}^{N} 4a_{j}^2+2a_{j}c_{j}+b_{j}^2 \equiv_{5} 0 \\ \sum\limits_{j=1}^{N} 3a_{j}b_{j}+4a_{j}^2+2b_{j}c_{j} \equiv_{5} 0 \\ \sum\limits_{j=1}^{N} c_{j}^2+3a_{j}b_{j}\equiv_{5} 0 \end{eqnarray*}$$

which follows from reducing the quartic polynomial resulting from squaring a general polynomial of degree two in $$\mathbb{F}_{5}[x]$$ by $$g$$.

Update: Following the same procedure for cubics ($$t=3$$) and $$p=5$$, $$k=3$$ gives exactly $$31$$ $$5$$-element subsets containing the origin which are all lines, that is they are all of the form $$\langle (a,b,c) \rangle=\{s(a,b,c) |\ s\in\mathbb{F}_{p}\}$$. One natural generalization of this observation, is the possibility that such lines are exactly the vanishing sets of size $$p$$ containing the origin for polynomials of degree $$t\geq k$$ for $$\mathbb{F}_{p^k}$$ (see second question above).

• "... $N=Е$ is multiple of $p$." -- was it meant $p^{k}$ instead of $p$? – Paata Ivanishvili Nov 30 '18 at 17:46
• @PaataIvanishvili No, it was not. The multiplicative identity $1$ in the field $\mathbb{F}_{p^k}$ has additive order $p$. So if the sum is zero then $|E|$ must be a multiple of $p$. The problem is stated for subsets $E$ of the field $\mathbb{F}_{p^k}$ rather than the cyclic group $\mathbb{F}_{p^k}$ (original title was edited to clarify). – Josiah Park Nov 30 '18 at 17:49
• Somewhat related: the Prouhet–Tarry–Escott problem – Greg Martin Nov 30 '18 at 22:27
• All $651$ examples of five element sets containing the origin for the last example problem (where the sets additionally satisfy that the linear poly sums vanish as well) were found by naive exhaustive search and are posted here: pastebin.com/5zuRvf2w. – Josiah Park Dec 2 '18 at 20:45
• The paper here treats sums of quadratic residues vanishing: arxiv.org/pdf/1702.03028.pdf. – Josiah Park Dec 16 '18 at 1:56

Let $$E$$ be a subset of any field. Then $$\sum_{x \in E} x^m=0$$ for all $$m \leq t$$ if and only if $$\sum_m \sum_{x \in E} u^{-m-1} x^m = \sum_{x \in E} \frac{1} {u-x} = \sum_{x \in E} \frac{d}{du} \log (u-x) = \frac{d}{du} \log \left(\prod_{x \in E} (u-x)\right)$$ has degree $$\leq -t -2$$ in $$u$$.

Now, $$\frac{d}{du} \log \left(\prod_{x \in E} (u-x)\right)= \frac{ \frac{d}{du} \prod_{x \in E} (u-x)}{ \prod_{x \in E} (u-x)}$$

so this happens if and only if $$\deg \frac{d}{du} \prod_{x \in E} (u-x) \leq |E|-t-2 .$$

In other words, this happens if and only if the only terms of $$\prod_{x \in E} (u-x)$$ occurring with degree greater than $$|E|-t-1$$ are those whose degree is a multiple of $$p$$ ($$p$$ the characteristic of the base field), as these are the only terms with vanishing derivative.

For instance, in the case when $$|E|=p$$, $$t=p-2$$, and $$E$$ is guaranteed to contain $$0$$, we see that this polynomial can only have nonvanishing coefficients of $$u^p, u,$$ and $$1$$, and the $$1$$ must vanish because $$|E|$$ contains $$0$$, so it must be of the form $$u^p- au = 0$$, which is easily seen to define a line through the origin.

In general, a polynomial of this special form will correspond to a set $$E$$ if and only if it has all distinct roots and these roots lie in the base field.

• Expressing the sum as a product by introducing the auxiliary variable $u$ works well. The expectation is that hyperplanes should arise for large enough $t$ when the number of points is larger than $p$, and the argument seems to be well adapted for that case too. – Josiah Park Dec 20 '18 at 0:34