7
$\begingroup$

Let $L_1, \ldots, L_m \in \mathbb{Z}[x_1, \ldots, x_n]$ be polynomials of the form $L_i = l_{i1} \cdot l_{i2} \ldots \cdot l_{ik}$, where every $l_{ij}$ is an integer linear form.

Assume that magnitudes of all coefficients of all $l_{ij}$ are bounded by some integer $H$. (So, every $l_{ij}$ has form $A_1 \cdot x_1 +\ldots + A_n \cdot x_n$, where every $A_i$ is an integer such that $|A_i| \le H$.)

Suppose that polynomials $L_1, \ldots, L_m$ are linearly dependent over $\mathbb{Z}$, i.e. there exists $B_1, \ldots, B_m \in \mathbb{Z}$ (not all equal to zero) such that $B_1\cdot L_1 + \ldots + B_m\cdot L_m \equiv 0$.

Is it true that these coefficients $B_1, \ldots, B_m$ can be chosen in such a way so that every $|B_i| \le H^{\text{poly}(n,m,k)}$ for some polynomial $\text{poly}(n,m,k)$?

This question is motivated by studing depth-$3$ arithmetic circuits.

$\endgroup$
10
$\begingroup$

Yes. The coefficients of the $L_j$ are $O(k! H^k)$ (the $k!$ is a bound for how many different products can contribute to the same term, a multinomial coefficient with $k$ on top). The $B_i$ are given as the kernel of a matrix whose entries are the coefficients of $L_j$. That kernel can be computed by Cramer's rule, giving $m \times m$ determinants, so the $B$'s are $O((m!) (k!)^m H^{mk}) = O(H^{m k} e^{m k \log k + m \log m})$.

| cite | improve this answer | |
$\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.