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 ?

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

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.