# Degree bounds and coefficient size in elimination theory?

Suppose we have polynomials is of form $$h_1(x_1,\dots,x_{dn})-c_1\in\mathbb Z[x_1,\dots,x_{dn}]$$ $$\vdots$$ $$h_{nd}(x_1,\dots,x_{dn})-c_{nd}\in\mathbb Z[x_1,\dots,x_{dn}]$$ where $$h_1(x_1,\dots,x_{dn}),\dots,h_n(x_1,\dots,x_{dn})\in\mathbb Z[x_1,\dots,x_{nd}]$$ are homogeneous polynoials of degree $$d$$ with each $$x_i$$ degree $$1$$ (that is only monomials of form $$x_{i_1},\dots,x_{i_d}$$) on the conditions that

1. each coefficient except $$c_1,\dots,c_{nd}$$ is random in $$[-B,B]\setminus\{0\}$$

2. with $$c_1,\dots,c_{nd}$$ being of absolute value at most $$B^{1+\frac1{2^d-1}}$$

3. in each monomial $$x_{i_1},\dots,x_{i_d}$$ we have $$i_j\in\{(j-1)n+1,\dots,jn\}$$.

Then if you use elimination theory we can successively eliminate variables and reduce to an univariate polynomial.

Let the absolute value of the maximum coefficient size $$B'$$ of final univariate polynomial in reduced form (no common gcd of coefficients) and the let the degree be $$d'$$.

Then can $$B'^{\frac1{d'}+\epsilon}>B^{\frac1{d(2^d-1)}}$$ hold with probability $$1-o(1)$$ at arbitrarily small $$\epsilon>0$$ as $$B$$ increases and $$d$$ is fixed?

• Editing a question with high frequency indicates that the questioner hasn't thought enough about his/her question before asking. (And my experience is to better stay away from questions that are not well-thought.) – tj_ Jan 11 at 23:42