Let $f_1,\ldots,f_n\in \mathbb{Q}[X_1,\ldots,X_n]$ be a system of $n$ polynomials in $n$ indeterminant, which only has finitely many solutions. Supose that the each of the variables $X_i$ appears at most with degree $d_i$ in the polynomials. What can be said about the complexity of finding the solutions in this case?
4
-
$\begingroup$ It will also depend (rather badly, I guess) on the coefficients. $\endgroup$– Felipe VolochCommented Sep 21, 2020 at 18:42
-
$\begingroup$ What do you mean by "finding" here? What are your inputs and outputs? Inputs seem like they should be easy - the coefficients of the $f_i$ - and I have one idea for outputs, but it isn't "nice" (specifically, it gives a set of single-variable polynomials $P_i$ such that if $(x_1, \dots)$ is a common zero of $(f_1, \dots)$, then $x_i$ is a solution of $P_i$; this gives "too many" answers because it "solves" each coordinate separately, meaning it doesn't eliminate "crossover" between two solutions). $\endgroup$– user44191Commented Sep 21, 2020 at 18:51
-
$\begingroup$ @FelipeVoloch At least for my solution, the complexity shouldn't depend on coefficients - if we let the coefficients of the $f_i$ be indeterminate, then the coefficients of the $P_i$ can still be determined in terms of the $f$ coefficients. They're polynomials, even. There may be cases where the complexity drops from that, but there is an algorithm that works in the generic case. $\endgroup$– user44191Commented Sep 21, 2020 at 19:01
-
$\begingroup$ We can assume the degree is $1$ in each variable: in each $f$, replace $X_1^1$ by $X_{1,1}$, replace $X_1^2$ by $X_{1,1} X_{1,2}$, replace $X_1^3$ by $X_{1,1} X_{1,2} X_{1,3}$, etc. and then add the polynomials $X_{1,1} - X_{1,2}$, $X_{1,2} - X_{1,3}$, etc. See the discussion at mathoverflow.net/questions/338050/…, and note that any algorithm solving this question would come close to solving the noted open question of Hilbert's tenth problem over the rationals. $\endgroup$– user44143Commented Sep 28, 2020 at 2:27
Add a comment
|