Note that we do not have to construct the numerical values of the variables–their existence alone is what is needed to see whether this configuration is possible and to see whether the Diophantine equations are solvable. We also do not have to construct the transcendentals, their existence is enough, and that the linear combinations which we take are nonzero so that we can recover solutions of the original equations from solutions of the new equations. However we must construct the coefficients as polynomial combinations of the transcendentals in them, and all integers in them starting with 1. In the next two paragraphs we argue that for 2 different equations, or at two different terms for same equation, the partial steps in the computation will involve different transcendentals, and we can have no new incidence among them; for different partial computations of the same term in the same equation, there are only the natural incidences, not ones depending on values of the variables; the incidences involving variables will be only that the same variable has the same value in two different equations.
The addition construction can be arranged to construct in turn, using some parallelism, from
$(a,a),(b,b)$
,
$x=a,(a,0),x=y+a,y=b,(a+b,b),x=a+b,(a+b,a+b)$
. Thus it adds the following varying finite points in order to add
$a,b$
:
$(a,a),(b,b),(a,0),(a+b,b)$
, and the following finite lines:
$x=a,x=y+a,y=b,x=a+b$
. The multiplication construction can be arranged to construct in turn
$x=1,y=a,(1,a),y=ax,x=b,(b,ab),y=ab,(ab,ab)$
. Thus it adds the following finite points in order to multiply
$a,b$
:
$(a,a),(b,b),(0,0),(1,1),(1,0),(1,a),(b,ab),(ab,ab)$
and these lines:
$x=1,y=a,y=ax,x=b,y=ab$
. We can choose in these that
$a$
is a partial computation carried from before, and
$b$
is a coefficient or variable, or the integers -1,1 or 2. We do computations of terms in order, with the new variables in
${E}_{i}$
last; when each term is complete, add it to the previous partial sum.
Consider a term as some
$\left({\sum}_{r,s}{n}_{rs}{t}_{r}{t}_{s}\right){x}_{i}{x}_{j}$
where
${t}_{r},{t}_{s}$
are transcendentals (there may be only one, and
${x}_{i},{x}_{j}$
are variables (there may be one or none), and
${n}_{rs}$
are integers. Lowest powers of
$2$
are added first in computing binary integers. For subtraction, we multiply a coefficient, after computing it, by a fixed
$-1$
(a fixed diagram verifies its sum with 1 is 0). First the transcendentals
${t}_{i}$
are multiplied, and among those, first transcendentals from the
${E}_{i}$
, then the multiples by them of the powers of 2 in the binary expansions of
${n}_{rs}$
, then those are added, then once the entire polynomial coefficient is computed, it is multiplied times
${x}_{i},{x}_{j}$
, over which we have little control beyond knowing their two possible values.
The lines above are either vertical or horizontal or at a 45 degree angle with intercepts
$0,1,a,b,a+b,ab$
, or have the form
$y=ax$
. The points lie on pairs of these lines and their coordinates are all
$0,1,a,b,a+b,ab$
. This means for incidences, in addition to partial computations being equal we need only to look at ratios
$(a+b)/b$
when a sum is being computed, for incidences on some
$y={a}_{1}x$
and differences
$1-a,b-ab$
when a product is being computed, for incidences on some
$x=y+a$
; the second coordinate is always the more advanced in a product and the less advanced in a sum, in the partial computation. Every line or point involving an
$a$
involves a new transcendental or linear combination of transcendentals in a new term: these partial computations will not be the same as those for another equation or another term in the same equation, nor can they equal a variable. This is also true for
$a-1,ab-b$
. As things are arranged, also new transcendentals will not cancel from
$(a+b)/b$
and will not give the value of any variable; all the more this cannot happen when we are adding a previous collection of terms. Such
$a+b$
cannot occur in the stages of multiplying in the variables, and cancellation will not occur in adding in a completed term. In the process of multiplying out a particular term within itself there cannot be any unpredictable incidences involving the variables, since multiplying them is done last. This shows that all incidences are computable in polynomial time from a knowledge of the equations, without knowing the values of the variables.
Solvability of the new system means precisely realizability in terms of a system of points and lines over the field, hence Kapranov rank at most 3 of the corresponding
$(0,1)$
-matrix. Hence if there were a P algorithm for Kapranov rank 3, then there would be a P algorithm for solving a system of Boolean or Diophantine equations in terms of 0,1 which is an NP-complete problem.
If we have a non-algebraically closed but infinite field, then a polynomial number of trials of substitutions of field elements for transcendentals one by one will result in some case where each of the polynomially many intersections remain distinct.
Canny's result [
2]
implies the last statement with proposition 1, that is, he proved that solving a system of polynomial equations over an algebraically closed field is a problem lying within PSPACE. □