Hitting set of very restricted linear forms We say that $f\in\mathbb{Z}[x_{1},\dots,x_{n}]$ is a {-1,0,1}-linear
form 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}-linear
forms 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 hitting
set 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 ?
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}-linear
form $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}$ distinct
linear forms $f_{S}$.

Because $(2n^{(c+1)})^{k}&lt;2^{n}$ when $k\le c_{0}n/\log n$, we have
that 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.