We say that $f\in\mathbb{Z}[x_{1},\dots,x_{n}]$ is a {-1,0,1}-linearform if $f=\sum_{i\in S}x_{i}-\sum_{i\in T}x_{i}$ where $S,T\subseteq[n]$.A hitting set $H\subseteq\mathbb{Z}^{n}$ for {-1,0,1}-linearforms is such that, for any non-zero {-1,0,1}-coef linear form $f\in\mathbb{Z}[x_{1},\dots,x_{n}]$,there is $\alpha\in H$ where $f(\alpha)\neq0$.Observe that a singleton $\{(2^{1},\dots,2^{n})\}$ is already a hittingset for $\{-1,0,1\}$-linear forms. A hitting set is polynomially bounded if $H\subseteq\{-n^{c},\dots,n^{c}\}^{n}$for some fixed constant $c$.What is the smallest size of polynomially bounded hitting set for  {-1,0,1}-linear forms ?By Chinese remaindering and this singleton $\{(2^{1},\dots,2^{n})\}$,one can show a polynomially bounded hitting set of size $O(n/\log n)$.Can we do better ?
Hitting set of very restricted linear forms
cc.complexity theory;algebraic complexity;derandomization;property testing
There is a tight lower bound of size $\Omega(n/ \log n)$ by simple counting argument.Suppose there is a hitting set $H=\{\alpha_{1},\dots,\alpha_{k}\}$of size $k$. We will show that there is always {-1,0,1}-linearform $f$ such that $f(\alpha_{i})=0$ for all $i$ when $k\le c_{0}n/\log n$and $c_{0}$ is small enough.For each $S\subseteq[n]$, let $f_{S}=\sum_{i\in S}x_{i}$ and $f_{S}(H)=(f_{S}(\alpha_{1}),\dots,f_{S}(\alpha_{k}))$. Since $|f_{S}(\alpha_{i})|\le n^{c+1}$, there are at most $(2n^{(c+1)})^{k}$possible distinct values of $f_{S}(H)$. But there are $2^{n}$ distinctlinear forms $f_{S}$.Because $(2n^{(c+1)})^{k}<2^{n}$ when $k\le c_{0}n/\log n$, we havethat there are $S$ and $S'$ where $f_{S}(\alpha_{i})=f_{S'}(\alpha_{i})$for all $i$. So $(f_{S}-f_{S'})(\alpha_i)=0$ for all $i$, $f_{S}-f_{S'}$ is a {-1,0,1}-linear form.