<p>There is a tight lower bound of size $\Omega(n/ \log n)$ by simple counting argument.</p>

<p>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.</p>

<p>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}))$. </p>

<p>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}$.</p>

<p>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$. </p>

<p>So $(f_{S}-f_{S'})(\alpha_i)=0$ for all $i$, $f_{S}-f_{S'}$ is a {-1,0,1}-linear form.</p>

CC BY-SA 3.0
2014-11-18T16:35:20.807Z
2014-11-18T16:35:20.807Z
Thatchaphol
<p>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$.</p>

<p>Observe that a singleton $\{(2^{1},\dots,2^{n})\}$ is already a hitting
set for $\{-1,0,1\}$-linear forms. </p>

<p>A hitting set is polynomially bounded if $H\subseteq\{-n^{c},\dots,n^{c}\}^{n}$
for some fixed constant $c$.</p>

<blockquote>
  <p>What is the smallest size of polynomially bounded hitting set for
  {-1,0,1}-linear forms ?</p>
</blockquote>

<p>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 ?</p>

CC BY-SA 3.0
2014-11-18T17:36:51.370Z
Cute problem!  Care to give more details on the upper bound?
Michaël Cadilhac
<cc.complexity-theory><algebraic-complexity><derandomization><property-testing>
Hitting set of very restricted linear forms
Thatchaphol
# Hitting set of very restricted linear forms

(Asked by: username_0 on 2014-11-17)

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 ?

**Tags:** cc.complexity-theory, algebraic-complexity, derandomization, property-testing

> **Comments:**
> **username_1**: Cute problem!  Care to give more details on the upper bound?  

---

## 1 answers

### Answer by username_0 on 2014-11-18. Score: 3 | Accepted answer

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.


---

