# Coefficients of linear dependency

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.

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