
> 
> Given a prime $p$ and an integer $n\ge p$, what is the smallest possible degree of a polynomial $Q\in\mathbb F\_p[x\_1,\dotsc, x\_n]$ such that $Q$ vanishes on every vector $x\in\{0,1\}^n$ of weight $w(x)=p$, but $Q(0)\ne 0$? (Here the *weight* of a vector is the number of its nonzero coordinates.)
> 
> 
> 


I am also interested in variations of this question: what is the smallest possible degree if $Q$ vanishes on every zero-one vector of weight *at least* $p$? Of weight *divisible* by $p$?


The range of interest is $n=p^c$ with $c>2$, particularly large values of $c$.



Polynomials vanishing on prescribed layers
For both modified questions, the answer is $n+1-p$. Since every polynomial that vanishes on vectors of weight $\geq p$ vanishes on vectors of nonzero weight divisible by $p$, other than $0$, it suffices to prove the upper bound for polynomials vanishing on vectors of weight $\geq p$ and the lower bound for vectors of nonzero weight divisible by $p$.


For the upper bound, it suffices to take $$Q =\prod\_{i=1}^{n+1-p} (1-x\_i)$$ since any set of at least $p$ of $x\_1,\dots, x\_n$ contains at least $1$ of the $x\_1,\dots, x\_{n+1-p}$.


For the lower bound, it suffices to observe that $Q ( 1- (x\_1+ \dots + x\_n)^{p-1})$ vanishes on all vectors of nonzero weight but is nonzero at $\{0,\dots ,0\} $. Thus, when we remove all squares of variables, it is a nonzero scalar multiple of $$\prod\_{i=1}^{n} (1-x\_i)$$ and thus has degree $n$ (or use the combinatorial nullstellensatz), so has degree $\geq n$, so $Q$ has degree $\geq n +1-p$.




---


For the original question where $Q$ vanishes on vectors of weight $p$, the answer is $p$ if $n \geq 2p-1$.


For the upper bound, it suffices to take $$Q =1 - \sum\_{ \substack{ S \subseteq \{1,\dots n\}\\ |S| = p }} \prod\_{i\in S} x\_i = 1- e\_p (x\_1,\dots, x\_n) $$ where $e\_p$ are the elementary symmetric polynomials.


For the lower bound, it suffices to handle the case $n=2p-1$, as restricting a polynomial $Q$ to the first $n$ variables by setting the remaining variables to zero preserves this possibility. But for $n=2p-1$, a vector has weight $p$ if and only if it has weight a nonzero multiple of $p$, and so the lower bound in this case follows from the lower bound for the modified problem, since $n+1-p=p$.


