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.



Coefficients of linear dependency
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})$.


