Genericity conditions

With the same notation and assumption as in Section~#444#1239> we are now discussing the genericity conditions; we therefore begin with

a Noether position #math203#{Z₁,…, Z_r},
a lifting point #math204##tex2html_wrap_inline4955# : = (p₁,…, p_δ),
a primitive element #math205#U : = λ_δ+1Z_δ+1 + ^... + λ_rZ_r of #math206#K[Z_δ+1,…, Z_r]/#tex2html_wrap_inline4960#.

for #math207##tex2html_wrap_inline4964#.

The computation we sketched in Section~#444#1252> and discussed in the next Sections returns a lifting fiber of #math208##tex2html_wrap_inline4968# for the lifting point #math209#(p₁,…, p_δ-1) and the primitive element #math210#λ_δZ_δ + λ_δ+1Z_δ+1 + ^... + λ_rZ_r provided the following conditions hold:

#math211#{Z₁,…, Z_r} is in Noether position for #math212##tex2html_wrap_inline4975#;
#math213##tex2html_wrap_inline4977# : = (p₁,…, p_δ-1) is a lifting point for #math214##tex2html_wrap_inline4981#;
#math215#λ_δ is a Liouville point for #tex2html_wrap_inline4986#;
#math216#λ_δZ_δ + λ_δ+1Z_δ+1 + ^... + λ_rZ_r is a primitive element for #math217##tex2html_wrap_inline4991#;
#math218##tex2html_wrap_inline4993# : = (p₁,…, p_δ-1) is a cleaning point for #tex2html_wrap_inline4997#.

We need moreover three further assumptions:

#math219#{Z₀,…, Z_r} is in Noether position for each homogeneous ideal #math220#^h#tex2html_wrap_inline5002#⊂K[Z₀,…, Z_r];
#math221#p_δ is lucky for the truncated computation;
U and #math222#λ_δ are lucky for the resultant computation of Remark~#R441#1288>.

In fact

consider, as an example, the 1-dimensional prime ideal #tex2html_wrap_inline5007#p generated by #math223#f (Z₁, Z₂) : = Z₁² - Z₂∈K[Z₁, Z₂]. While the variables are in Noether position, any specialization of Z₁ returns a single point, notwithstanding #math224#deg(f )= 2.
On the otherside, this does not happen for a really generic frame of coordinates: if we perform a generic change of coordinates obtaining
#math225#
f (Y₁, Y₂) : = d₁₁²Y₁² + d₁₁d₁₂Y₁Y₂ + d₁₂²Y₂² - d₂₁Y₁ + d₂₂Y₂
each evaluation of Y₁ returns two points.
More in general we need to avoid a degeneration in which
#math226#
deg(f (p₁,…, p_δ, Z_δ+1,…, Z_r) ;SPMlt; deg(f );
this cannot occur if #math227#{Z₀, Z₁,…, Z_r} is in Noether position for the homogeneous ideal #math228#^h#tex2html_wrap_inline5018#;
gcd and resultant computation of polynomials have good complexity if performed over L[T] where L is a field, but this implies the ability of performing zero-testing and inverting, which is out of the present model.
The computation, e.g., of the resultant
#math229#
A(Z_δ) : = #tex2html_wrap_indisplay5023#(Q, f (Z_δ, V_δ+1,…, V_r)
which satisfies
#math230#deg(A)≤η : = deg(
#tex2html_wrap_inline5027#))deg(f ) costs
#math231#
#tex2html_wrap_indisplay5029#(η) : = #tex2html_wrap_indisplay5030#O(ηlog²(η)loglog(η))
arithmetical operations in
#math232#K(Z_δ) if it is performed in this <#1306#>field<#1306#> where we don't have a good complexity model for zero-testing and inverting; the result of this computation gives a polynomial
#math233#A(Z_δ)∈K[Z_δ] of degree η.
Let us now fix a value p∈K and, remarking that #math234#K(Z_δ)⊂K[[Z_δ]], consider the <#1307#>ring<#1307#>
#math235#
R : = K[[Z_δ]]/(Z_δ - p)^η+1≅#tex2html_wrap_indisplay5037#{1,…, Z_δ^η}
where we can perform both

zero-testing: an element #math236#g = #tex2html_wrap_inline5039#c_iZ_δ^t∈R is zero iff c_i = 0 for each i iff g(p) = 0,

inverting : the inverse in R of the invertible polynomial g, #math237#g(p)≠ 0, is the polynomial #math238#s(Z_δ), deg(s)≤η which satisfies
#math239#
s(Z_δ)g(Z_δ) + t(Z_δ)(Z_δ - p)^η+1 = gcd(g(Z_δ),(Z_δ - p)^η+1 = 1
for a suitable #math240#t(Z_δ), deg(t) ;SPMlt; deg(g).

Thus any element
#math241#
g(Z_δ) : = d (Z_δ)/r(Z_δ)∈K(Z_δ), d (Z_δ), r(Z_δ)∈K[Z_δ]
can be canonically represented by an element #math242##tex2html_wrap_inline5051#∈#tex2html_wrap_inline5052#{1,…, Z_δ^η} such that #math243##tex2html_wrap_inline5054#(Z_δ)r(Z_δ)≡d (Z_δ) mod(Z_δ-p)^η+1.
Thus the same algorithm which, if performed on #math244#K(Z_δ), resturns #math245#A(Z_δ) with complexity #math246##tex2html_wrap_inline5058#(η) can be performed also on R with the same complexity #math247##tex2html_wrap_inline5061#(η) returning some polynomial #math248#B(Z_δ) : = #tex2html_wrap_inline5063#c_iZ_δ^t∈K[Z_δ] of degree bounded by η.
Can we assume that such polynomial #math249#B(Z_δ) is the <#1324#>true<#1324#> resultant #math250#A(Z_δ), i.e. that #math251#B(Z_δ) = #tex2html_wrap_inline5068#(Z_δ) = A(Z_δ)? The answer is obvious: the solution is correct iff in each step of the computation, the algorithm in R gives the same answer as the algorithm in #math252#K(Z_δ), <#1326#>id est<#1326#>

when zero-testing #math253#g(Z_δ)∈K(Z_δ), #math254#g = 0#tex2html_wrap_inline5073##tex2html_wrap_inline5074#(p) = 0,

when computing the inverse #math255#h(Z_δ) : = g^-1(Z_δ) of #math256#g(Z_δ)∈K(Z_δ), the polynomial #math257#s(Z_δ) such that #math258#s(Z_δ)#tex2html_wrap_inline5079#(Z_δ)≡1 mod(Z_δ-p)^η+1 satisfies #math259#s = #tex2html_wrap_inline5081#.

This behavieur depends on the choice of p∈K; there are some values p in which some wrong answer is returned failing this approach; but almost all choices are ;SPMquot;lucky;SPMquot; thus allowing to produce the correct answer #math260#B(Z_δ) = #tex2html_wrap_inline5085#(Z_δ) = A(Z_δ) with the good #math261##tex2html_wrap_inline5087#(η) complexity while computing in the ring R instead than in the field #math262#K(Z_δ).
In a similar way a better complexity is obtained if the computation (see Remark~#R441#1337>) of the resultant #math263#A(Z)∈K[Z] of the polynomials #math264##tex2html_wrap_inline5092#(Z, T) and #math265#f (λ_δ^-1(Z - T),#tex2html_wrap_inline5094#(Z, T),…,#tex2html_wrap_inline5095#(Z, T)) in K[Z][T] can be performed with the ring arithmetics of K[Z] instead of the field arithmetics of K(Z). Such ability depends on a lucky choice of the Liouville point #math266#λ_δ and of the primitive U.