We have a polynomial $f(x_1,x_2,x_3,x_4)\in\mathbb Z[x_1,x_2,x_3,x_4]$ where the only monomials are either from set $$\{x_1,x_1x_2,x_2,x_3,x_3x_4,x_4\}$$ and we seek solutions $(x_1,x_2,x_3,x_4)\in\mathbb Z^4$ with $|x_1|<X_1$, $|x_2|<X_2$, $|x_3|<X_3$ and $|x_4|<X_4$. We see that $x_1,x_2$ and $x_3,x_4$ variables do not mix.

It seems the set of $x_1,x_2$ variables and set of $x_3,x_4$ variables each both individually and collectively satisfy the generalized lower triangle bound on page $16$ http://www.cits.rub.de/imperia/md/content/may/paper/jochemszmay.pdf with $\lambda_1=\lambda_2=\lambda_3=\lambda_4=2$ and $D=1$.

enter image description here

Assume we have the additional condition that for a given $(x_1,x_2)\in\mathbb Z^2$ with $|x_1|<X_1$ and $|x_2|<X_2$ we have that there is an unique $(x_3,x_4)\in\mathbb Z^2$ with $f(x_1,x_2,x_3,x_4)=0$, $|x_3|<X_3$ and $|x_4|<X_4$ vice versa for a given $(x_3,x_4)\in\mathbb Z^2$ with $|x_3|<X_3$ and $|x_4|<X_4$ we have that there is an unique $(x_1,x_2)\in\mathbb Z^2$ with $f(x_1,x_2,x_3,x_4)=0$, $|x_1|<X_1$ and $|x_2|<X_2$. $W$ is highest absolute value of coefficient of $f(x_1X_1,x_2X_2,x_3X_3,x_4X_4)$.

  1. In this situation can the bound of $X_1^{\lambda_1}X_2^{\lambda_2}X_3^{\lambda_3}X_4^{\lambda_4}\leq W^\frac1D$ be improved to $$\max(X_1^{\lambda_1}X_2^{\lambda_2},X_3^{\lambda_3}X_4^{\lambda_4})\leq W^\frac1D$$ or may be at least $$\max(X_1^{\lambda_1}X_2^{\lambda_2},X_3^{\lambda_3/2}X_4^{\lambda_4/2})\leq W^\frac2{3D}$$ ($\lambda_3/2$ and $\lambda_4/2$ is based on guess that variables are disjoint and have separate control and $x_3,x_4$ do not satisfy generalized triangle bound with $\lambda_3=\lambda_4=1$ and assuming $x_1,x_2$ variables were not present in given polynomial will give $W^{\frac2{3D}}$ bound)?

  2. If not what is the best we can do at least for the case $X_1=X_2=X_3=X_4$?

Cross-posted: https://crypto.stackexchange.com/questions/64296/is-there-a-variation-of-coppersmiths-method-that-applies-to-disjoint-variable-s


Your Answer

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

Browse other questions tagged or ask your own question.