1
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ Cute problem! Care to give more details on the upper bound? $\endgroup$ – Michaël Cadilhac Nov 18 '14 at 17:36
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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