# 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 ?

• Cute problem! Care to give more details on the upper bound? Nov 18, 2014 at 17:36

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}<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.