Finite obstructions, compatible lifts, and deformation

Proof of Lemma 10.1

Apply polynomial induction using constants, addition, and multiplication by a variable. Constants have zero remainder, and remainders add. For the multiplication step, suppose the assertion is known for \(P\) and write \(D_P(U)=\sum_j(\partial_jP)(a)U_j\). Multiplication of its expansion by \(a_i+cU_i\) gives constant term \(P(a)a_i\), linear term \(c(a_iD_P(U)+P(a)U_i)\), and remainder

The product rule identifies the linear term with the derivative of \(PX_i\). The displayed remainder vanishes at \(U=0\). This constructs the polynomial remainder before evaluation at \(u\), even over rings where division by \(c\) would be invalid.

Back to statement · Read statement and proof side by side · Permalink · Source line 47 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 10.2

Every point in the lower residue class has the form \(y=x+q^Lt\) with \(t\in{\mathbb Z}^d\). By Lemma 10.1 and \(2L\ge L+1\),

The integer \(q^L\) is nonzero. Cancelling it in the corresponding divisibility condition proves

Integer vectors reduce onto \(S_q^d\). The equation on the right is solvable exactly when \(\overline{r_x}\) belongs to \({\operatorname{im}} J_x\), since that image is closed under negation. This is precisely \(o_x=0\). Finiteness follows because \(\mathcal O_x\) is a quotient of the finite module \(S_q^e\).

Back to statement · Read statement and proof side by side · Permalink · Source line 84 · Claim record · Lean coverage · Code · Worked examples

Proof of Proposition 10.3

The affine identity \(F(x+q^Lt)=F(x)+q^LAt\) has no quadratic remainder. The proof of (10.3) therefore needs no inequality involving \(2L\). The residual and the finite quotient are obtained as above.

Back to statement · Read statement and proof side by side · Permalink · Source line 117 · Claim record · Lean coverage · Code · Worked examples

Proof of Proposition 10.4

Polynomial evaluation respects coordinatewise congruence. Apply this first to every formal partial derivative: \(x'\equiv x\pmod q\) gives \(J_{x'}=J_x\). Next apply (10.1) to \(F\) at scale \(q^L\). Subtract the two exact residual identities and cancel \(q^L\) to obtain the displayed relation modulo \(q\). Its additional term belongs to the common Jacobian image, so it vanishes in the quotient.

Back to statement · Read statement and proof side by side · Permalink · Source line 142 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 10.5

If \([u]=[v]\), write \(u-v=s+t\) with \(s\in\ker J\) and \(t\in\ker K\). Then \(w=u-s=v+t\) satisfies both required equalities. Conversely, a common \(w\) gives

Every class \([u]\) is the label of \(Ju\) and of \(Ku\), proving surjectivity. For attainable \(a=Ju\) and \(b=Kv\), the first equivalence says exactly that equal labels are equivalent to a simultaneous preimage. This proves (10.6). Finally, a finite target has finite image, and the associated surjective label map makes \(C(J,K)\) finite.

Back to statement · Read statement and proof side by side · Permalink · Source line 188 · Claim record · Lean coverage · Code · Worked examples

Proof of Corollary 10.6

For each system, (10.3) translates a valid next root into a linear correction equation. Once \(u\) corrects \(F\), another digit \(w\) corrects \(F\) precisely when \(Jw=Ju\). The analogous condition for \(G\) is \(Kw=Kv\). Theorem 10.5 now gives the criterion. Two valid corrections of one block differ by a vector in its Jacobian kernel, so they have equal labels. Finiteness follows from either finite residue target. An unconditional formulation quantifies over separately valid \(u,v\) with equal labels, thereby including their existence in the criterion rather than assuming it.

Back to statement · Read statement and proof side by side · Permalink · Source line 226 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 10.7

Equation (10.3) identifies exactly which points of the residue fiber satisfy the equations, proving the restricted equivalence. If \(u,t\in\mathcal T_x\), subtraction gives \(J_x(t-u)=0\). Conversely, adding any element of \(\ker J_x\) preserves the correction equation. The unique kernel vector carrying \(u\) to \(t\) is \(t-u\), so the action is free and transitive. Choosing one valid digit identifies the fiber with the kernel, without making that choice part of its translation action.

For prime \(p\), rank-nullity gives \(\dim\ker J_x=d-\rho_x\) and \(\dim({\mathbb F}_p^e/{\operatorname{im}} J_x)=e-\rho_x\). The cardinality of an \(n\)-dimensional \({\mathbb F}_p\)-space is \(p^n\). Combine these identities with the obstruction criterion and the residue equivalence.

Back to statement · Read statement and proof side by side · Permalink · Source line 303 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 10.8

At level \(N=L+n\), divide the residual by \(q^N\). Surjectivity supplies \(t\in S_q^d\) with \(J_{z_n}t=-\overline{F(z_n)/q^N}\). Choose an integer representative and apply (10.3) to obtain \(z_{n+1}\). The new point is congruent to \(z_n\) modulo \(q\). Evaluation of each formal partial derivative therefore gives \(J_{z_{n+1}}=J_{z_n}\).

Construct the sequence recursively, retaining the root condition and the fixed Jacobian at each step. Surjectivity at every later stage then follows from the single initial assumption. The cross-level congruence follows by induction, adding consecutive differences whose divisibilities all imply divisibility by \(q^{L+a}\).

Back to statement · Read statement and proof side by side · Permalink · Source line 345 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 10.9

Cross-level compatibility bounds the supremum distance between later terms by \(p^{-(L+n)}\). Completeness gives a limit, and closed norm bounds retain the congruence to every \(z_n\). View the coefficients of the original integer polynomials in \({\mathbb Z_p}\). Their evaluations satisfy both \(F_i(z_n)\to F_i(a)\), by continuity, and \(F_i(z_n)\to0\), by their growing divisibility. Uniqueness of limits gives exact vanishing.

Surjectivity gives \({\operatorname{rank}} J_x=e\le d\). Theorem 10.7 then gives \(p^{d-e}\) next residue roots and obstruction cardinality one at every stage.

For square uniqueness, let \(a,b\in B_L(x)\) be arbitrary exact roots. Their canonical integer truncations are genuine roots in the respective finite residue rings, since evaluation commutes with reduction. They agree at depth \(L\). If they agree at depth \(N\ge L\), both next residues belong to the same lift set, which has cardinality \(p^{d-d}=1\). Induction gives agreement at every depth. The residue maps separate \(p\)-adic integers, so \(a=b\). Existence was already supplied by the tower.

Back to statement · Read statement and proof side by side · Permalink · Source line 376 · Claim record · Lean coverage · Code · Worked examples

Proof of Proposition 10.11

Since \(p\mid c\), differentiation gives \(DG(x)\equiv DF(x)\pmod p\). Truncate \(a\) to an integer vector \(y\) at depth \(M\). Then \(F(y)\equiv0\pmod{p^M}\), hence also \(G(y)\equiv0\pmod{p^M}\). Congruence of \(y\) and \(x\) modulo \(p\) preserves the reduced Jacobian. The smooth root theorem gives \(b\equiv y\equiv a\pmod{p^M}\).

In the square case this constructed root lies in \(B_L(x)\) because \(M\ge L\). Square uniqueness for \(G\) identifies it with every competing root in that ball. The construction therefore gives the precision assertion for an arbitrary root there.

Back to statement · Read statement and proof side by side · Permalink · Source line 428 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 10.12

First consider a square integer polynomial map \(P\) whose reduced Jacobian at \(x\) is surjective. Its Jacobian is invertible over \({\mathbb F}_p\). A digit comparison using Taylor expansion shows that equal outputs modulo \(p^{N+1}\) force equal inputs modulo \(p^{N+1}\) whenever the inputs already agree modulo \(p^N\) and belong to \(B_1(x)\). Induction and integer truncation give, for arbitrary \(a,b\in B_1(x)\),

More generally, for a rectangular map with surjective reduced Jacobian,

One inclusion follows from polynomial congruence. For integer targets in the right-hand ball, subtract the target from the constant terms and use the smooth root theorem. For arbitrary \(p\)-adic targets, approximate by integer truncations. The input ball is compact, so its continuous image is closed. It contains all these approximants and hence their limit. This argument does not assume that independently chosen preimages form a compatible sequence.

For square \(P\), the resulting bijection between the two compact residue balls is continuous, and its target is Hausdorff. It is therefore a homeomorphism, with the same congruence preservation for its inverse.

Now suppose a chosen set of \(e\) columns of \(DF(x)\bmod p\) is independent, and put those coordinates first. Apply the square result to the augmented polynomial map

Its reduced Jacobian has upper blocks \((D_YF,D_TF)\) and lower blocks \((0,I_k)\), so it is invertible. For \(t\in T\), the target \((0,t)\) belongs to \(\Psi(x)+p^L{\mathbb Z_p}^{e+k}\) because \(F(x)\equiv0\pmod{p^L}\). The inverse of \(\Psi\) at that target gives the unique root with parameters \(t\). The inverse congruence property gives one direction of (10.8); projection onto the parameter coordinates gives the other.

Finally, surjectivity of the original rectangular Jacobian guarantees a basis among its columns. Extend the corresponding injection of coordinate indices to a permutation \(\sigma\). Renaming the variables by \(\sigma^{-1}\) transports polynomial evaluation and every formal partial derivative. The fixed-coordinate construction therefore applies to the original system after undoing the permutation.

Back to statement · Read statement and proof side by side · Permalink · Source line 471 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 10.13

A candidate for the next lift has the form \(x+q^L(\widetilde u,\widetilde v)\), with solved digit \(u\in S_q^m\). Its Taylor correction equation is

Solvability is exactly vanishing of the displayed cokernel class. Restrict the residue-digit equivalence to the prescribed parameter coordinates. This identifies the lift fiber with the solved-digit fiber. Translation by \(\ker J_x\) is free and transitive on any nonempty such fiber. The prime-field count follows from rank-nullity as before.

Back to statement · Read statement and proof side by side · Permalink · Source line 565 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 10.14

At level \(N=L+n\), write the supplied parameter increment exactly as \(t_{n+1}-t_n=q^Nw\) with \(w\in{\mathbb Z}^k\). Surjectivity of the solved block gives a digit \(u\) satisfying \(J_{z_n}u=-\overline{F(z_n)/q^N}-K_{z_n}\overline w\). Choose an integer representative \(\widetilde u\) and set \(z_{n+1}=z_n+q^N(\widetilde u,w)\). Its parameter coordinates equal the supplied target exactly. Taylor expansion proves the next root condition, while congruence modulo \(q\) preserves the full reduced Jacobian. Construct the sequence recursively, preserving the exact parameter coordinates and the fixed solved Jacobian. The earlier cross-level argument proves all the stated integer congruences.

Back to statement · Read statement and proof side by side · Permalink · Source line 606 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 10.15

Set the first integer parameter approximation equal to the prescribed \(t_0\). For \(n\ge1\), use canonical representatives of \(\tau\bmod p^{L+n}\). The initial congruence and truncation precision give

Subtracting consecutive relations gives compatibility in \({\mathbb Z_p}\). Faithfulness of integer divisibility under \({\mathbb Z}\hookrightarrow{\mathbb Z_p}\) gives compatibility in \({\mathbb Z}\), and the same norm bounds give \(t_n\to\tau\). Theorem 10.14 and completion now produce \(b\) with exact polynomial vanishing and all retained precisions. Each free coordinate has both the corresponding coordinate of \(b\) and that of \(\tau\) as its limit, proving exact parameter equality.

The solved Jacobian remains surjective, so every shifted obstruction \([\overline r+K_{z_n}v]\) vanishes. Formula (10.10) therefore gives \(p^{m-e}\) choices for every parameter digit at every stage. When \(m=e\), the fixed-coordinate chart in the proof of Theorem 10.12 contains every root in the initial ball with the specified parameters. Its uniqueness proves the endpoint assertion. This is uniqueness of the actual endpoint, not of the integer representatives used to approach it.

Back to statement · Read statement and proof side by side · Permalink · Source line 641 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 10.16

Let \(A=p^sJ^{-1}\in M_d(R)\). Inclusion into \({\mathbb Q_p}\) and its injectivity give the two integral identities

These identities are also an equivalent integral certificate for the first two hypotheses of (10.11). In particular, \(A\) is injective: \(Aw=0\) implies \(p^sw=JAw=0\), hence \(w=0\).

Precondition the polynomial system by \(A\) and set \(c=p^{s+1}\). Its derivative at \(a\) is \(AJ=p^sI_d\). Lemma 10.1 gives a polynomial vector \(Q\) with \(Q(0)=0\) and

Since \(A\) is integral, \((AF)(a)\in p^rR^d\). The strict integer inequality \(r>2s\) permits \(k=r-(2s+1)\ge0\) and a vector \(C\in p^kR^d\) such that \((AF)(a)=p^{2s+1}C\). The normalized root equation is therefore

Integral polynomial evaluation is \(1\)-Lipschitz for the supremum \(p\)-adic metric: a common divisibility of input differences is preserved under addition and multiplication by integral elements. Consequently the right side of (10.13) has contraction constant \(|p|_p<1\) on the complete space \(R^d\). It has a unique fixed point \(u\).

To obtain the sharper displacement, begin with \(u\in R^d\). If \(u\in p^nR^d\), then \(Q(0)=0\) and polynomial congruence give \(Q(u)\in p^nR^d\). For \(n<k\), both \(C\) and \(pQ(u)\) are divisible by \(p^{n+1}\). Equation (10.13) therefore improves the divisibility of \(u\) by one digit. Induction gives \(u\in p^kR^d\). Thus \(b=a+p^{s+1}u\) satisfies (10.12), because \(s+1+k=r-s\). Its normalized preconditioned value vanishes, and injectivity of \(A\) gives \(F(b)=0\).

Every competing root \(z\in a+p^{s+1}R^d\) can be written \(z=a+p^{s+1}w\). Its root equation implies the same fixed-point equation after cancellation of the nonzero scalar \(p^{2s+1}\). Contraction uniqueness gives \(w=u\), proving uniqueness on the entire stated ball.

Back to statement · Read statement and proof side by side · Permalink · Source line 698 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 10.18

Retain the original certificate \(A=p^sJ^{-1}\) and put \(c=p^{s+1}\). Taylor expansion and a polynomial difference identity yield polynomial vectors \(Q_F,Q_H\), both zero at the origin, such that

Consequently

where

All exponents are nonnegative. The same contraction and divisibility argument as in Theorem 10.16 gives the root, the displacement \(p^{M-s}\), and full-ball uniqueness. This constructs the root without introducing an inverse hypothesis for \(DG(a)\).

For the error estimate, let \(\delta=b-a\) and \(D=M-s\). Taylor's theorem for the preconditioned polynomial gives

Polynomial congruence gives \(E_H=(AH)(b)-(AH)(a)\in p^DR^d\). The equations \(F(a)=0\) and \(G(b)=0\) imply

because \(M+D\ge2D\). Cancel \(p^s\) in the integral domain \(R\) to obtain

This integral vector is \(\varepsilon\). After inclusion into \({\mathbb Q_p}\), \(p^{M-s}A=p^MJ^{-1}\) gives (10.14).

Back to statement · Read statement and proof side by side · Permalink · Source line 774 · Claim record · Lean coverage · Code · Worked examples

Proof of Theorem 10.19

Use the augmented polynomial systems

Then \(\mathcal F(a)=0\), and its derivative is

For \(A=p^sJ^{-1}\in M_e(R)\) and \(c=p^s\), define

The identities \(AJ=JA=cI_e\) give \(CB=BC=cI_{e+k}\). In the second product, the upper right block is \(-JAK+cK=0\); in the first, it is \(AK-AK=0\). Thus augmentation preserves the original inverse bound \(s\).

Theorem 10.18 gives a unique root \(b\) of \(\mathcal F+p^M\mathcal H\) in \(a+p^{s+1}R^{e+k}\), with displacement depth \(M-s\). Its last equations say exactly \(b_T=t_0+p^Mv=\tau\). Its first equations are \(G(b)=0\). The integral first-order expression uses

Projection onto the solved coordinates gives

The same inclusion identity as before converts this to (10.15).

Finally, if \(z\in y_0+p^{s+1}R^e\) is any competing solved root with parameters \(\tau\), then \((z,\tau)\) belongs to the full augmented ball. Indeed, \(M>2s\) implies \(M\ge s+1\). Full-point uniqueness therefore gives \((z,\tau)=b\). This comparison proves uniqueness on exactly the solved ball stated in the theorem.

Back to statement · Read statement and proof side by side · Permalink · Source line 846 · Claim record · Lean coverage · Code · Worked examples