Dedicated to the memory of Vladimir N. Remeslennikov, Vitaly A. Roman’kov, and Gennady A. Noskov, mathematicians of Dostoevsky Omsk State University who made important contributions to the algorithmic theory of metabelian groups.
Introduction
The conjugacy problem is one of the classical algorithmic problems in group theory. For finitely generated metabelian groups, its decidability is well known, but the computational complexity of the problem is less understood. In this paper, we show that the conjugacy problem in finitely presented metabelian groups with a fixed number of generators can be solved in bounded-error quantum polynomial time. The algorithm is uniform in the defining relations of the group.
Our approach exploits the connection between metabelian groups and modules over commutative rings. If G G G A = G ′ A = G' A = G ′ A A A Z [ G / A ] \mathbb{Z}[G/A] Z [ G / A ] Z \mathbb{Z} Z
The main algebraic ingredient is a quantum polynomial-time algorithm for computing multiplicative relations among a fixed number of units in a finitely presented commutative Z \mathbb{Z} Z
Quantum polynomial-time algorithms in algebra
Since Shor’s quantum polynomial-time algorithms for integer factorization and discrete logarithms [21 ] , quantum computation has been studied extensively. Nevertheless, relatively few broad classes of computational problems in algebra and group theory are known to admit quantum polynomial-time algorithms. Many of the known results rely on reductions to integer factorization, discrete logarithms, or hidden subgroup problems.
In computational group theory, Watrous developed quantum polynomial-time algorithms for order computation, subgroup membership, and related problems in finite solvable black-box groups [25 ] . Cheung and Mosca gave a quantum polynomial-time algorithm for decomposing finite abelian groups [4 ] . Babai, Beals, and Seress obtained randomized polynomial-time algorithms for fundamental problems in finite matrix groups over fields of odd characteristic, using integer factorization and discrete logarithm oracles [3 ] . Together with Shor’s algorithms, these yield quantum polynomial-time algorithms for the corresponding problems.
In algebraic number theory, Hallgren developed quantum polynomial-time algorithms for Pell’s equation and the principal ideal problem in real quadratic fields [11 ] . Eisenträger, Hallgren, Kitaev, and Song extended quantum methods to computing unit groups of number fields of arbitrary degree, using a continuous hidden subgroup approach [7 ] .
Another notable example is the quantum polynomial-time algorithm of Aharonov, Jones, and Landau for additive approximation of the Jones polynomial at roots of unity [1 ] . For suitable roots of unity and approximation parameters, this problem is BQP-complete.
Main results and input conventions
For a tuple u = ( u 1 , … , u k ) u=(u_1,\ldots,u_k) u = ( u 1 , … , u k ) e ∈ Z k e\in\mathbb{Z}^k e ∈ Z k
u e = u 1 e 1 ⋯ u k e k . u^e=u_1^{e_1}\cdots u_k^{e_k}. u e = u 1 e 1 ⋯ u k e k . If A A A K K K K K K algebraicity lattice of u ∈ ( A × ) k u\in(A^\times)^k u ∈ ( A × ) k
Alg K ( u ) = { e ∈ Z k | u e is algebraic over K } . (1) \operatorname{Alg}_K(u)=\left\{e\in\mathbb{Z}^k\mathrel{}\middle|\mathrel{}u^e\text{ is algebraic over }K\right\}. \tag*{(1)} Alg K ( u ) = { e ∈ Z k u e is algebraic over K } . (1) For a commutative ring A A A relation lattice of u ∈ ( A × ) k u\in(A^\times)^k u ∈ ( A × ) k
Rel A ( u ) = { e ∈ Z k | u e = 1 } . (2) \operatorname{Rel}_A(u)=\left\{e\in\mathbb{Z}^k\mathrel{}\middle|\mathrel{}u^e=1\right\}. \tag*{(2)} Rel A ( u ) = { e ∈ Z k u e = 1 } . (2) Throughout the paper, polynomial running times refer to bit complexity, with integer coefficients and lattice coordinates encoded in binary. The numbers of variables and units are fixed, and the polynomial-time bounds may depend on these numbers. Polynomial degrees are measured numerically. We allow dense polynomial representations, as well as sparse representations whose numerical degrees are polynomially bounded in the input length. Our complexity bounds do not apply to unrestricted sparse representations with binary-encoded exponents.
Theorem 1.1 (Computing algebraicity lattices). Fix nonnegative integers m , k m,k m , k K = Q K=\mathbb{Q} K = Q F p \mathbb{F}_p F p
A = K [ X 1 , … , X m ] / ( f 1 , … , f r ) , A=K[X_1,\ldots,X_m]/(f_1,\ldots,f_r), A = K [ X 1 , … , X m ] / ( f 1 , … , f r ) , and let u = ( u 1 , … , u k ) ∈ ( A × ) k u=(u_1,\ldots,u_k)\in(A^\times)^k u = ( u 1 , … , u k ) ∈ ( A × ) k Alg K ( u ) \operatorname{Alg}_K(u) Alg K ( u )
Moreover, if D ≥ 2 D \ge2 D ≥ 2 Alg K ( u ) \operatorname{Alg}_{K}(u) Alg K ( u ) b 1 , … , b s b_1,\ldots,b_s b 1 , … , b s
∥ b i ∥ ∞ ≤ k ! D ( m + 1 ) k ( 1 ≤ i ≤ s ) . \lVert b_i\rVert_{\infty} \le k!D^{(m+1)k}\qquad(1\le i\le s). ∥ b i ∥ ∞ ≤ k ! D ( m + 1 ) k ( 1 ≤ i ≤ s ) . Theorem 1.2 (Computing relation lattices). Fix nonnegative integers m , k m,k m , k Let
A = Z [ X 1 , … , X m ] / ( f 1 , … , f r ) , A=\mathbb{Z}[X_1,\ldots,X_m]/(f_1,\ldots,f_r), A = Z [ X 1 , … , X m ] / ( f 1 , … , f r ) , and let u = ( u 1 , … , u k ) ∈ ( A × ) k u=(u_1,\ldots,u_k)\in(A^{\times})^k u = ( u 1 , … , u k ) ∈ ( A × ) k Rel A ( u ) \operatorname{Rel}_A(u) Rel A ( u )
Corollary 1.3 (Subgroup membership and exponent representations). Fix nonnegative integers m , k m,k m , k Let S S S u 1 , … , u k u_1,\ldots,u_k u 1 , … , u k Theorem 1.2 , and let h ∈ S × h\in S^{\times} h ∈ S × h h h h − 1 h^{-1} h − 1
h ∈ ⟨ u 1 , … , u k ⟩ . h\in\langle u_1,\ldots,u_k\rangle. h ∈ ⟨ u 1 , … , u k ⟩ . If so, the algorithm computes a vector e 0 ∈ Z k e_0\in\mathbb{Z}^k e 0 ∈ Z k
{ e ∈ Z k : e u = h } = e 0 + Rel S ( u 1 , … , u k ) . \{e\in\mathbb{Z}^k:e^u=h\}=e_0+\operatorname{Rel}_S(u_1,\ldots,u_k). { e ∈ Z k : e u = h } = e 0 + Rel S ( u 1 , … , u k ) . Theorem 1.4. Fix k ≥ 1 k\ge1 k ≥ 1 There is a bounded-error quantum polynomial-time algorithm that, given a finite presentation
G = ⟨ x 1 , … , x k ∣ r 1 , … , r m ⟩ M G=\langle x_1,\ldots,x_k\mid r_1,\ldots,r_m\rangle_M G = ⟨ x 1 , … , x k ∣ r 1 , … , r m ⟩ M of a metabelian group and two words x , y x,y x , y x x x y y y G G G
In Theorem 1.4 , the number k k k G G G k k k
The reductions and the new lattice argument are proved below. We use the standard polynomial algorithms for integer linear algebra and Hermite and Smith normal forms, the effective algebraic bounds specified in § 2 , Lenstra–Silverberg’s Theorem 1.11(i) for explicitly represented finite-dimensional commutative Q \mathbb{Q} Q [16 ] , and quantum factorization, order finding and the finite abelian hidden-subgroup algorithm [21 , 4 ] . These underlying algorithmic theorems are used with their stated input representations; their proofs are not reproduced here.
We use right conjugation g h = h − 1 g h g^h=h^{-1}gh g h = h − 1 g h [ g , h ] = g − 1 h − 1 g h [g,h]=g^{-1}h^{-1}gh [ g , h ] = g − 1 h − 1 g h
Related results
Noskov established decidability of the conjugacy problem in finitely generated metabelian groups [20 ] . The reduction of conjugacy to orbit problems in modules over integral group rings is part of this classical theory. We give an explicit formulation of this reduction and show that the required module presentations and subsequent cyclic-module computations can be constructed in polynomial time, uniformly over presentations with a fixed number of generators.
Stronger classical complexity bounds are known for several important classes of solvable groups. Matthews studied conjugacy in free metabelian groups using wreath products [17 ] . Vassileva established polynomial-time algorithms for conjugacy decision and search in free solvable groups [24 ] . Ushakov subsequently obtained a quasi-quartic-time Monte Carlo algorithm for conjugacy in free solvable groups, with a complexity bound uniform in the derived length, which need not be fixed [23 ] .
These results were extended to a broader family of groups by Gul, Sohrabi, and Ushakov [10 ] . They studied groups of the form F / N ( d ) F/N^{(d)} F / N ( d ) F F F N N N F F F F / N F/N F / N F / N ( d ) F/N^{(d)} F / N ( d ) d ≥ 2 d \ge2 d ≥ 2 d d d N = F N=F N = F
Miasnikov, Vassileva, and Weiß proved that conjugacy decision in fixed free solvable groups and fixed iterated wreath products of finitely generated abelian groups belongs to DLOGTIME-uniform T C 0 \mathrm{TC}^{0} TC 0 [18 Corollary 5.6] . Here the rank, derived length, and iterated wreath construction are fixed, and the inputs are ordinary words. Thus free metabelian groups admit stronger classical complexity bounds, while our result applies uniformly to arbitrary finitely presented metabelian groups with a fixed number of generators.
Nilpotent groups provide another point of comparison. Myasnikov and Weiß established uniform T C 0 \mathrm{TC}^{0} TC 0 [19 Theorem 13] . Their algorithms also produce conjugators. For binary-exponent inputs, the corresponding conjugacy computations are T C 0 \mathrm{TC}^{0} TC 0 T C 0 \mathrm{TC}^{0} TC 0
For certain split metabelian groups of finite Prüfer rank, Gryak, Kahrobaei, and Martínez-Pérez investigated the conjugacy search problem [9 ] . They obtained an exponential-time algorithm in the general setting, polynomial-time algorithms for a subfamily, and a reduction to discrete logarithms for another family. The exponential bound is an upper bound for their algorithm, not a complexity lower bound. These results illustrate the role of multiplicative arithmetic in conjugacy problems, although they concern more restricted classes of groups.
The algebraic component of our approach is closely related to algorithms for multiplicative relations. Ge developed polynomial-time algorithms for multiplicative relations among algebraic numbers [8 ] . Lenstra and Silverberg established algorithms for explicitly represented finite-dimensional commutative Q \mathbb{Q} Q [16 Theorem 1.11] . Their input consists of rational structure constants relative to a vector-space basis. We apply their result only after constructing an appropriate finite-dimensional subalgebra with an exact representation of polynomial size.
Kreuzer and Walsh developed algorithms for computing binomial parts of polynomial ideals and related exponent and unit lattices over fields, including affine algebras [14 ] . A unit lattice records exponents for which a product belongs to the coefficient field, whereas an exponent lattice records products equal to 1 1 1
In subsequent work, Kreuzer and Walsh also computed exponent lattices in arbitrary finitely generated Z \mathbb{Z} Z [15 Section 3] , although the later sections of their paper focus on algebras finite as Z \mathbb{Z} Z
The quantum ingredients are standard algorithms for integer factorization, order finding, and the finite abelian hidden-subgroup problem [21 , 4 ] . We apply them to finite rings with explicit canonical encodings. Our results establish quantum upper bounds; we do not claim classical lower bounds or that all quantum steps reduce to integer factorization.
Outline of the argument
The proof has two main parts. We first develop an algorithm for computing multiplicative relations among units in commutative affine Z \mathbb{Z} Z
For the algebraic part, let
S = Z [ X 1 , … , X m ] / I S = \mathbb{Z}[X_1,\ldots,X_m]/I S = Z [ X 1 , … , X m ] / I be a commutative affine Z \mathbb{Z} Z u 1 , … , u k ∈ S × u_1,\ldots,u_k \in S^\times u 1 , … , u k ∈ S × m m m k k k
Rel S ( u 1 , … , u k ) = { e ∈ Z k | u 1 e 1 ⋯ u k e k = 1 } . \operatorname{Rel}_S(u_1,\ldots,u_k)=\left\{e\in\mathbb{Z}^k \mathrel{}\middle|\mathrel{} u_1^{e_1}\cdots u_k^{e_k}=1\right\}. Rel S ( u 1 , … , u k ) = { e ∈ Z k u 1 e 1 ⋯ u k e k = 1 } . § 2 establishes the necessary algorithmic preliminaries. These include polynomial-time computations in modules over polynomial rings and group rings, effective degree bounds, algebraicity tests, and an arithmetic splitting for affine Z \mathbb{Z} Z
In § 3 , we consider an affine algebra over K = Q K=\mathbb{Q} K = Q F p \mathbb{F}_p F p
Alg K ( u 1 , … , u k ) = { e ∈ Z k | u e is algebraic over K } . \operatorname{Alg}_K(u_1,\ldots,u_k)=\left\{e\in\mathbb{Z}^k\mathrel{}\middle|\mathrel{}u^e\text{ is algebraic over }K\right\}. Alg K ( u 1 , … , u k ) = { e ∈ Z k u e is algebraic over K } . We prove that this lattice has a basis with polynomially bounded coordinates. Since the number of units is fixed, the lattice can be computed by enumerating polynomially many exponent vectors and testing algebraicity. Its basis vectors give units generating a finite-dimensional algebra over K K K
§ 4 treats affine algebras over Z / p a Z \mathbb{Z}/p^a\mathbb{Z} Z / p a Z p p p p a p^a p a
In § 5 , we combine the rational and prime-power cases. An effective arithmetic splitting gives an injective homomorphism
S ⟶ ( S ⊗ Q ) × S / c S S\longrightarrow(S\otimes\mathbb{Q})\times S/cS S ⟶ ( S ⊗ Q ) × S / c S for a computable positive integer c c c S S S Theorem 1.2 . § 6 derives the corresponding multiplicative subgroup-membership algorithm.
The group-theoretic reduction begins in § 7 . For a metabelian group G G G
A = G ′ , Q = G / A , R = Z Q . (3) A=G',\qquad Q=G/A,\qquad R=\mathbb{Z}Q. \tag*{(3)} A = G ′ , Q = G / A , R = Z Q . (3) Using the R R R A A A
f = e ⋅ q , q ∈ Q , f=e\cdot q,\qquad q\in Q, f = e ⋅ q , q ∈ Q , in an explicitly presented R R R
In Section 8, we reduce this orbit membership problem to multiplicative subgroup membership
h ∈ ⟨ u 1 , … , u k ⟩ h\in\langle u_1,\ldots,u_k\rangle h ∈ ⟨ u 1 , … , u k ⟩ in a commutative affine Z \mathbb{Z} Z k k k
Preliminaries: polynomial-time computations in polynomial rings and modules
This section collects the computational tools used in the subsequent reductions and algorithms. We establish polynomial-time bounds for linear algebra over polynomial rings in a fixed number of variables, module membership, and annihilator computations. We also develop the arithmetic splitting and elimination procedures needed for the exponent-lattice algorithm.
Fix s ≥ 0 s\ge0 s ≥ 0
P = Z [ Z 1 , … , Z s ] . P=\mathbb{Z}[Z_1,\ldots,Z_s]. P = Z [ Z 1 , … , Z s ] . Throughout this section, the number of variables s s s
Following [2 ] , the height of a polynomial f ∈ P f\in P f ∈ P
h ( f ) = max { log ∣ a ∣ ∣ a ≠ 0 is a coefficient of f } , h(f)=\max\{\log|a|\mid a\ne0\text{ is a coefficient of }f\}, h ( f ) = max { log ∣ a ∣ ∣ a = 0 is a coefficient of f } , with h ( 0 ) = 0 h(0)=0 h ( 0 ) = 0 f 1 , … , f k ∈ P f_1,\ldots,f_k\in P f 1 , … , f k ∈ P
h ( f 1 , … , f k ) = max 1 ≤ i ≤ k h ( f i ) . h(f_1,\ldots,f_k)=\max_{1\le i\le k}h(f_i). h ( f 1 , … , f k ) = 1 ≤ i ≤ k max h ( f i ) . Polynomial-time computations in P P P
In this subsection, we establish polynomial-time algorithms for solving linear systems and computing kernels over P P P [2 ] and standard integer linear algebra. We then apply them to submodule membership and annihilator computations in finitely presented P P P
Proposition 2.1. The following problems can be solved in deterministic polynomial time:
(a) deciding solvability of a linear system over P P P
(b) finding a solution of a linear system over P P P
(c) computing a finite generating set for the kernel of a matrix over P P P
Proof. Let F ∈ P m × r F\in P^{m\times r} F ∈ P m × r b ∈ P m b\in P^m b ∈ P m d ≥ 1 d\ge1 d ≥ 1 F F F b b b h h h
Suppose first that the system
is solvable over P P P [2 Theorem 6.5] , there is a constant C C C s s s
deg v i ≤ C ( 2 m d ) C ( h + 1 ) ( 1 ≤ i ≤ r ) . \deg v_i \leq C(2md)^C(h+1) \qquad(1 \leq i \leq r). deg v i ≤ C ( 2 m d ) C ( h + 1 ) ( 1 ≤ i ≤ r ) . Since s s s m m m d d d h + 1 h+1 h + 1
D = ⌈ C ( 2 m d ) C ( h + 1 ) ⌉ . D=\left\lceil C(2md)^C(h+1)\right\rceil. D = ⌈ C ( 2 m d ) C ( h + 1 ) ⌉ . Write the coordinates of v v v D D D s s s D D D Z 1 , … , Z s Z_1,\ldots,Z_s Z 1 , … , Z s
( D + s s ) = O ( D s ) , \binom{D+s}{s}=O(D^s), ( s D + s ) = O ( D s ) , and hence the total number of unknown coefficients is polynomial in the input size. Comparing coefficients in F v = b Fv=b F v = b
of polynomial size, whose coefficients have polynomial bit length. Using, for example, Smith or Hermite normal form, one can decide in polynomial time whether this system has an integral solution. When a solution exists, these algorithms also produce one whose coordinates have polynomial bit length. Substituting these coordinates into v v v F v = b Fv=b F v = b
It remains to prove (c). By [2 Corollary 5.4] , the P P P
ker P F = { v ∈ P r : F v = 0 } \ker_P F=\{v\in P^r:Fv=0\} ker P F = { v ∈ P r : F v = 0 } admits a generating set consisting of polynomial vectors of degree at most
( 2 m d ) 2 O ( s 2 ) . (2md)^{2^{O(s^2)}}. ( 2 m d ) 2 O ( s 2 ) . Since s s s D 0 D_0 D 0 m m m d d d
Write a polynomial vector v ∈ P r v\in P^r v ∈ P r D 0 D_0 D 0 s s s D 0 D_0 D 0
yields a homogeneous system of linear equations over Z \mathbb{Z} Z Z \mathbb{Z} Z v 1 , … , v ℓ ∈ ker P F v_1,\ldots,v_\ell\in\ker_P F v 1 , … , v ℓ ∈ ker P F Z \mathbb{Z} Z ker P F \ker_P F ker P F D 0 D_0 D 0
By the choice of D 0 D_0 D 0 P P P ker P F \ker_P F ker P F D 0 D_0 D 0 Z \mathbb{Z} Z v 1 , … , v ℓ v_1,\ldots,v_\ell v 1 , … , v ℓ
ker P F = P v 1 + ⋯ + P v ℓ . \ker_P F=Pv_1+\cdots+Pv_\ell. ker P F = P v 1 + ⋯ + P v ℓ . The computation and its output have polynomial bit complexity. □
Corollary 2.2. For finitely presented P P P
(a) deciding membership in a finitely generated submodule and, when membership holds, computing a representation in terms of its generators;
(b) computing a finite generating set for the annihilator of a given element.
Proof. Let M M M P P P
M = P q / im U , U ∈ P q × ℓ . M = P^q/\operatorname{im} U,\qquad U \in P^{q \times\ell}. M = P q / im U , U ∈ P q × ℓ . The columns of U U U M M M P q P^q P q V V V M M M b ∈ P q b \in P^q b ∈ P q c c c z z z P P P
V c + U z = b . Vc + Uz = b. V c + U z = b . This is a linear system over P P P Proposition 2.1 , its solvability can be decided in polynomial time and, when it is solvable, a solution c c c b b b
Now let a ∈ P q a \in P^q a ∈ P q a ˉ ∈ M \bar{a} \in M a ˉ ∈ M f ∈ P f \in P f ∈ P Ann P ( a ˉ ) \operatorname{Ann}_P(\bar{a}) Ann P ( a ˉ )
f a ∈ im U , fa \in\operatorname{im} U, f a ∈ im U , or equivalently, if there exists z z z
[ a − U ] ( f z ) = 0. \begin{bmatrix} a & -U \end{bmatrix}
\begin{pmatrix} f \\ z \end{pmatrix}
= 0. [ a − U ] ( f z ) = 0. By Proposition 2.1 , generators of the kernel of this matrix can be computed in polynomial time. Projecting these generators onto their first coordinates gives a generating set for Ann P ( a ˉ ) \operatorname{Ann}_P(\bar{a}) Ann P ( a ˉ )
Polynomial-time computations in Z Q \mathbb{Z}Q Z Q
Fix k ≥ 0 k \ge0 k ≥ 0 Q Q Q
Q = ⟨ x 1 , … , x k ∣ r 1 , … , r m ⟩ A b (4) Q = \langle x_1,\ldots,x_k \mid r_1,\ldots,r_m\rangle_{\mathrm{Ab}} \tag*{(4)} Q = ⟨ x 1 , … , x k ∣ r 1 , … , r m ⟩ Ab (4) in the variety of abelian groups, where r 1 , … , r m r_1,\ldots,r_m r 1 , … , r m x 1 , … , x k x_1,\ldots,x_k x 1 , … , x k
R = Z Q , P = Z [ X 1 , Y 1 , … , X k , Y k ] . R = \mathbb{Z}Q,\qquad P = \mathbb{Z}[X_1,Y_1,\ldots,X_k,Y_k]. R = Z Q , P = Z [ X 1 , Y 1 , … , X k , Y k ] . For a group word w w w x 1 , … , x k x_1,\ldots,x_k x 1 , … , x k σ x i ( w ) \sigma_{x_i}(w) σ x i ( w ) x i x_i x i w w w
mono ( w ) = ( ∏ 1 ≤ i ≤ k σ x i ( w ) > 0 X i σ x i ( w ) ) ( ∏ 1 ≤ i ≤ k σ x i ( w ) < 0 Y i − σ x i ( w ) ) . \operatorname{mono}(w) =
\left(\prod_{\substack{1 \le i \le k\\ \sigma_{x_i}(w)>0}} X_i^{\sigma_{x_i}(w)}\right)
\left(\prod_{\substack{1 \le i \le k\\ \sigma_{x_i}(w)<0}} Y_i^{-\sigma_{x_i}(w)}\right). mono ( w ) = 1 ≤ i ≤ k σ x i ( w ) > 0 ∏ X i σ x i ( w ) 1 ≤ i ≤ k σ x i ( w ) < 0 ∏ Y i − σ x i ( w ) . Since Q Q Q
R ≅ P / J , J = ⟨ X i Y i − 1 ( 1 ≤ i ≤ k ) , mono ( r j ) − 1 ( 1 ≤ j ≤ m ) ⟩ , (5) R \cong P/J,\qquad
J = \langle X_iY_i - 1\ (1 \le i \le k),\ \operatorname{mono}(r_j)-1\ (1 \le j \le m)\rangle, \tag*{(5)} R ≅ P / J , J = ⟨ X i Y i − 1 ( 1 ≤ i ≤ k ) , mono ( r j ) − 1 ( 1 ≤ j ≤ m )⟩ , (5) where X i X_i X i Y i Y_i Y i x i x_i x i x i − 1 x_i^{-1} x i − 1 σ x i ( r j ) \sigma_{x_i}(r_j) σ x i ( r j ) ∣ σ x i ( r j ) ∣ ≤ ∣ r j ∣ |\sigma_{x_i}(r_j)| \le|r_j| ∣ σ x i ( r j ) ∣ ≤ ∣ r j ∣ mono ( r j ) \operatorname{mono}(r_j) mono ( r j )
Corollary 2.3. For fixed k k k r 1 , … , r m r_1,\ldots,r_m r 1 , … , r m Q Q Q
(a) deciding solvability of a linear system over R R R
(b) computing a finite generating set for the kernel of a matrix over R R R
(c) deciding membership in a finitely generated submodule and, when membership holds, computing a representation in terms of its generators;
(d) computing a finite generating set for the annihilator of a given element.
Proof. A finitely presented R R R P P P g e i = 0 ge_i=0 g e i = 0 g g g J J J e i e_i e i R R R P P P R R R P P P J J J P P P R R R
Thus all four problems reduce to the algorithms of Proposition 2.1 and Corollary 2.2. Since P P P 2 k 2k 2 k Q Q Q
Corollary 2.4. For fixed k ≥ 0 k \ge0 k ≥ 0
I = ( f 1 , … , f ℓ ) I=(f_1,\ldots,f_\ell) I = ( f 1 , … , f ℓ ) of R R R h ∈ R h \in R h ∈ R h + I h+I h + I R / I R/I R / I Q Q Q
Proof. The element h + I h+I h + I R / I R/I R / I h ′ , c 1 , … , c ℓ ∈ R h',c_1,\ldots,c_\ell\in R h ′ , c 1 , … , c ℓ ∈ R
h h ′ + ∑ j = 1 ℓ f j c j = 1. hh' + \sum_{j=1}^{\ell} f_jc_j=1. h h ′ + j = 1 ∑ ℓ f j c j = 1. This is a linear system over R R R Q Q Q h ′ + I h'+I h ′ + I h + I h+I h + I R / I R/I R / I
Bounded-degree ideal computations
For a polynomial ring R R R Z \mathbb{Z} Z R ≤ d R_{\le d} R ≤ d d d d
For computations over Q \mathbb{Q} Q F p \mathbb{F}_p F p p p p p p p
We begin with an auxiliary lemma that reduces bounded-degree ideal computations to linear algebra over the coefficient field. It will be used both to compute rational contractions of ideals and to test algebraicity.
Lemma 2.5. Let K = Q K=\mathbb{Q} K = Q F p \mathbb{F}_p F p
R = K [ Z 1 , … , Z s ] , J = ( f 1 , … , f r ) ≤ R , R=K[Z_1,\ldots,Z_s], \qquad J=(f_1,\ldots,f_r)\le R, R = K [ Z 1 , … , Z s ] , J = ( f 1 , … , f r ) ≤ R , where s s s E ≥ 0 E\ge0 E ≥ 0 K K K
J ∩ R ≤ E . J\cap R_{\le E}. J ∩ R ≤ E . Over Q \mathbb{Q} Q
Proof. Let D ≥ 2 D\ge2 D ≥ 2 J J J d = max { D , E } d=\max\{D,E\} d = max { D , E } [2 Theorem 3.4] , every polynomial h ∈ J h\in J h ∈ J E E E
h = ∑ ν = 1 r a ν f ν , deg a ν ≤ ( 2 d ) 2 s . h=\sum_{\nu=1}^{r}a_{\nu}f_{\nu}, \qquad\deg a_{\nu}\le(2d)^{2^s}. h = ν = 1 ∑ r a ν f ν , deg a ν ≤ ( 2 d ) 2 s . Set H = ( 2 d ) 2 s + D H = (2d)^{2^s} + D H = ( 2 d ) 2 s + D s s s H H H d d d
Write h h h a ν a_\nu a ν E E E ( 2 d ) 2 s (2d)^{2^s} ( 2 d ) 2 s H H H
where u u u h h h a a a B B B h h h H H H C C C ( a 1 , … , a r ) ↦ ∑ ν a ν f ν (a_1,\ldots,a_r) \mapsto\sum_\nu a_\nu f_\nu ( a 1 , … , a r ) ↦ ∑ ν a ν f ν
By Gaussian elimination, compute a matrix L L L C C C
B u ∈ im C ⟺ L B u = 0. Bu \in\operatorname{im} C \quad\Longleftrightarrow\quad LBu = 0. B u ∈ im C ⟺ L B u = 0. Thus ker ( L B ) \ker(LB) ker ( L B )
J ∩ R ≤ E . J \cap R_{\leq E}. J ∩ R ≤ E . Since s s s Q \mathbb{Q} Q F p \mathbb{F}_p F p log p \log p log p
Arithmetic splitting
We now establish an effective separation of rational and modular information in a finitely generated Z \mathbb{Z} Z P / I P/I P / I P / I P/I P / I
Let I = ( f 1 , … , f r ) ≤ P I = (f_1,\ldots,f_r) \leq P I = ( f 1 , … , f r ) ≤ P
I Q = I Q [ Z 1 , … , Z s ] , J = I Q ∩ P . I_{\mathbb{Q}} = I\mathbb{Q}[Z_1,\ldots,Z_s], \qquad J = I_{\mathbb{Q}} \cap P. I Q = I Q [ Z 1 , … , Z s ] , J = I Q ∩ P . The rationalization of P / I P/I P / I
( P / I ) ⊗ Z Q ≅ Q [ Z 1 , … , Z s ] / I Q . (P/I) \otimes_{\mathbb{Z}} \mathbb{Q} \cong\mathbb{Q}[Z_1,\ldots,Z_s]/I_{\mathbb{Q}}. ( P / I ) ⊗ Z Q ≅ Q [ Z 1 , … , Z s ] / I Q . The kernel of the natural map
P / I ⟶ Q [ Z 1 , … , Z s ] / I Q P/I \longrightarrow\mathbb{Q}[Z_1,\ldots,Z_s]/I_{\mathbb{Q}} P / I ⟶ Q [ Z 1 , … , Z s ] / I Q is J / I J/I J / I J / I J/I J / I Z \mathbb{Z} Z P / I P/I P / I P / J P/J P / J J J J J / I J/I J / I
Lemma 2.6 (Rational contraction). There is a deterministic polynomial-time algorithm that computes generators of J J J
Proof. Let D ≥ 2 D \geq2 D ≥ 2 f 1 , … , f r f_1,\ldots,f_r f 1 , … , f r [2 Proposition 4.7] , there is an explicit degree bound
τ ≤ ( 2 D ) 2 O ( s 2 ) . \tau\leq(2D)^{2^{O(s^2)}}. τ ≤ ( 2 D ) 2 O ( s 2 ) . such that J J J τ \tau τ s s s τ \tau τ D D D
Consider the rational vector space
V = I Q ∩ Q [ Z 1 , … , Z s ] ≤ τ . V = I_{\mathbb{Q}} \cap\mathbb{Q}[Z_1,\ldots,Z_s]_{\leq\tau}. V = I Q ∩ Q [ Z 1 , … , Z s ] ≤ τ . By the proof of Lemma 2.5 , we can compute in polynomial time a rational matrix M M M V V V
Clearing the denominators in each row of M M M H H H
ker Q H = ker Q M = V . \ker_{\mathbb{Q}} H = \ker_{\mathbb{Q}} M = V. ker Q H = ker Q M = V . Under the corresponding identification P ≤ τ ≅ Z N P_{\leq\tau} \cong\mathbb{Z}^N P ≤ τ ≅ Z N
V ∩ P ≤ τ ≅ ker Z H . V \cap P_{\leq\tau} \cong\ker_{\mathbb{Z}} H. V ∩ P ≤ τ ≅ ker Z H . The matrix H H H [13 ] , compute a Z \mathbb{Z} Z
j 1 , … , j t j_1,\ldots,j_t j 1 , … , j t of this module. These polynomials generate J J J τ \tau τ J J J τ \tau τ V ∩ P ≤ τ V \cap P_{\leq\tau} V ∩ P ≤ τ
Lemma 2.7 (Torsion annihilator). There is a deterministic polynomial-time algorithm that computes c ∈ N c \in\mathbb{N} c ∈ N
c J ⊆ I . cJ \subseteq I. c J ⊆ I . Proof. By Lemma 2.6 , compute generators j 1 , … , j t j_1,\ldots,j_t j 1 , … , j t J J J J = 0 J = 0 J = 0 c = 1 c = 1 c = 1 j i j_i j i
j i = ∑ ν = 1 r a i ν f ν , a i ν ∈ Q [ Z 1 , … , Z s ] . j_i = \sum_{\nu=1}^{r} a_{i\nu}f_\nu,\qquad a_{i\nu} \in\mathbb{Q}[Z_1,\ldots,Z_s]. j i = ν = 1 ∑ r a i ν f ν , a i ν ∈ Q [ Z 1 , … , Z s ] . Hermann’s degree bound [2 Theorem 3.4] gives a polynomial bound on the degrees of the multipliers. Consequently, these representations can be found by solving polynomial-size rational linear systems. The resulting coefficients have polynomial bit length, and their total number is polynomially bounded. Let c > 0 c > 0 c > 0 c c c
c j i ∈ I ( 1 ≤ i ≤ t ) . cj_i \in I \qquad(1 \leq i \leq t). c j i ∈ I ( 1 ≤ i ≤ t ) . Since the j i j_i j i J J J c J ⊆ I cJ \subseteq I c J ⊆ I
Theorem 2.8 (Arithmetic splitting). There is a deterministic polynomial-time algorithm that computes c ∈ N c \in\mathbb{N} c ∈ N
P / I ⟶ ( P / I ) ⊗ Z Q × ( P / I ) / c ( P / I ) P/I \longrightarrow(P/I) \otimes_{\mathbb{Z}} \mathbb{Q} \times(P/I)/c(P/I) P / I ⟶ ( P / I ) ⊗ Z Q × ( P / I ) / c ( P / I ) is injective.
Proof. Put A = P / I A = P/I A = P / I T = J / I T = J/I T = J / I Z \mathbb{Z} Z c c c c J ⊆ I cJ \subseteq I c J ⊆ I
The kernel of the natural homomorphism
A ⟶ A ⊗ Z Q × A / c A A \longrightarrow A \otimes_{\mathbb{Z}} \mathbb{Q} \times A/cA A ⟶ A ⊗ Z Q × A / c A is T ∩ c A T \cap cA T ∩ c A z ∈ T ∩ c A z \in T \cap cA z ∈ T ∩ c A z = c y z = cy z = cy z z z n n n
0 = n z = n c y . 0 = nz = ncy. 0 = n z = n cy . Hence y ∈ T y \in T y ∈ T z = c y = 0 z = cy = 0 z = cy = 0
Algebraicity test
We next give an effective test for algebraicity in finitely generated algebras over Q \mathbb{Q} Q F p \mathbb{F}_p F p
Lemma 2.9. Let K = Q K = \mathbb{Q} K = Q F p \mathbb{F}_p F p
A = K [ Z 1 , … , Z s ] / I , A = K[Z_1,\ldots,Z_s]/I, A = K [ Z 1 , … , Z s ] / I , where s s s v ∈ A v \in A v ∈ A v v v K K K
Proof. Let v v v g ∈ K [ Z 1 , … , Z s ] g \in K[Z_1,\ldots,Z_s] g ∈ K [ Z 1 , … , Z s ] Y Y Y
J = I + ( Y − g ) ≤ K [ Z 1 , … , Z s , Y ] . J = I + (Y-g) \le K[Z_1,\ldots,Z_s,Y]. J = I + ( Y − g ) ≤ K [ Z 1 , … , Z s , Y ] . The evaluation homomorphism
ev v : K [ Z 1 , … , Z s , Y ] ⟶ A , \operatorname{ev}_v : K[Z_1,\ldots,Z_s,Y] \longrightarrow A, ev v : K [ Z 1 , … , Z s , Y ] ⟶ A , defined by
Z i ⟼ Z i + I , Y ⟼ v , Z_i \longmapsto Z_i + I,\qquad Y \longmapsto v, Z i ⟼ Z i + I , Y ⟼ v , has kernel J J J K [ Y ] K[Y] K [ Y ] J ∩ K [ Y ] J \cap K[Y] J ∩ K [ Y ]
v is algebraic over K ⟺ J ∩ K [ Y ] ≠ 0. v\text{ is algebraic over }K \quad\Longleftrightarrow\quad J \cap K[Y] \ne0. v is algebraic over K ⟺ J ∩ K [ Y ] = 0. Let D ≥ 2 D \ge2 D ≥ 2 J J J [6 Corollary 8.3] , applied with an elimination ordering, if J ∩ K [ Y ] ≠ 0 J \cap K[Y] \ne0 J ∩ K [ Y ] = 0
E = ⌊ 2 ( D 2 2 + D ) 2 s ⌋ . E = \left\lfloor2\left(\frac{D^2}{2}+D\right)^{2^s}\right\rfloor. E = ⌊ 2 ( 2 D 2 + D ) 2 s ⌋ . Since s s s E E E D D D
By Lemma 2.5 , applied to the polynomial ring K [ Z 1 , … , Z s , Y ] K[Z_1,\ldots,Z_s,Y] K [ Z 1 , … , Z s , Y ] s + 1 s+1 s + 1
V = J ∩ K [ Z 1 , … , Z s , Y ] ≤ E V = J \cap K[Z_1,\ldots,Z_s,Y]_{\le E} V = J ∩ K [ Z 1 , … , Z s , Y ] ≤ E in deterministic polynomial time. Represent the elements of V V V Z i Z_i Z i
V ∩ K [ Y ] = J ∩ K [ Y ] ≤ E . V \cap K[Y] = J \cap K[Y]_{\le E}. V ∩ K [ Y ] = J ∩ K [ Y ] ≤ E . By the choice of E E E v v v K K K h ( Y ) h(Y) h ( Y )
Since s s s Lemma 2.5 and standard bounds for rational linear algebra. Thus the algorithm runs in deterministic polynomial time. □
Relation lattices over fields
The goal of this section is to compute multiplicative relation lattices over Q \mathbb{Q} Q F p \mathbb{F}_p F p
Throughout this section, the number m m m k k k K K K
A = K [ X 1 , … , X m ] / I , I = ( f 1 , … , f r ) , A = K[X_1,\ldots,X_m]/I,\qquad I=(f_1,\ldots,f_r), A = K [ X 1 , … , X m ] / I , I = ( f 1 , … , f r ) , where K = Q K=\mathbb{Q} K = Q K = F p K=\mathbb{F}_p K = F p f 1 , … , f r f_1,\ldots,f_r f 1 , … , f r u 1 , … , u k ∈ A × u_1,\ldots,u_k\in A^\times u 1 , … , u k ∈ A × D ≥ 2 D\ge2 D ≥ 2 Q \mathbb{Q} Q F p \mathbb{F}_p F p O ( log p ) O(\log p) O ( log p )
Algebraicity lattices in affine algebras
Recall the algebraicity lattice Alg K ( u ) \operatorname{Alg}_K(u) Alg K ( u ) (1) . It is a saturated sublattice of Z k \mathbb{Z}^k Z k ( u e ) n (u^e)^n ( u e ) n K K K n ≠ 0 n\ne0 n = 0 u e u^e u e
V = D m + 1 , B 0 = k ! V k . V=D^{m+1},\qquad B_0=k!V^k. V = D m + 1 , B 0 = k ! V k . Proposition 3.1. The lattice Alg K ( u ) \operatorname{Alg}_K(u) Alg K ( u ) has a basis consisting of vectors b b b satisfying
∥ b ∥ ∞ ≤ B 0 . \lVert b\rVert_\infty\le B_0. ∥ b ∥ ∞ ≤ B 0 . Proof. Let p \mathfrak{p} p A A A A / p A/\mathfrak{p} A / p
X = Spec ( A / p ) X=\operatorname{Spec}(A/\mathfrak{p}) X = Spec ( A / p ) for the corresponding irreducible component of Spec ( A ) \operatorname{Spec}(A) Spec ( A ) A / p A/\mathfrak{p} A / p
K ( X ) = Frac ( A / p ) . K(X)=\operatorname{Frac}(A/\mathfrak{p}). K ( X ) = Frac ( A / p ) . Thus the images of the units u 1 , … , u k u_1,\ldots,u_k u 1 , … , u k A / p A/\mathfrak{p} A / p X X X
We pass to a normal projective model in order to record all zeros and poles of these rational functions, including those at infinity. Let
X ‾ ⊆ P K m \overline{X}\subseteq\mathbb{P}^m_K X ⊆ P K m be the projective closure of X X X
ν : Y ⟶ X ‾ \nu:Y\longrightarrow\overline{X} ν : Y ⟶ X be its normalization. Then Y Y Y ν \nu ν [22 Tag 0BXR] . In particular,
K ( Y ) ≅ K ( X ‾ ) ≅ K ( X ) , K(Y)\cong K(\overline{X})\cong K(X), K ( Y ) ≅ K ( X ) ≅ K ( X ) , so we may regard the u i u_i u i Y Y Y
Since X X X Spec ( A ) \operatorname{Spec}(A) Spec ( A ) I I I D D D [12 Theorem 1] gives
deg X ≤ D m . \deg X \le D^m. deg X ≤ D m . Here the degree of an affine variety is the degree of its projective closure under the standard embedding A K m ↪ P K m A^m_K \hookrightarrow\mathbb{P}^m_K A K m ↪ P K m
deg X ‾ = deg X ≤ D m . \deg\overline{X} = \deg X \le D^m. deg X = deg X ≤ D m . Suppose s = dim X ≥ 1 s = \dim X \ge1 s = dim X ≥ 1 F i ∈ K [ X 1 , … , X m ] F_i \in K[X_1,\ldots,X_m] F i ∈ K [ X 1 , … , X m ] u i u_i u i D D D F i h F_i^h F i h D D D X 0 ≠ 0 X_0 \ne0 X 0 = 0 F i F_i F i
F i h X 0 D . \frac{F_i^h}{X_0^D}. X 0 D F i h . Thus, after pulling back along ν : Y → X ‾ \nu:Y \to\overline{X} ν : Y → X Y Y Y
u i = ν ∗ ( F i h X 0 D ) = ν ∗ F i h ν ∗ X 0 D . u_i = \nu^*\left(\frac{F_i^h}{X_0^D}\right) = \frac{\nu^*F_i^h}{\nu^*X_0^D}. u i = ν ∗ ( X 0 D F i h ) = ν ∗ X 0 D ν ∗ F i h . Put
H = ν ∗ O X ‾ ( 1 ) . H = \nu^*\mathcal{O}_{\overline{X}}(1). H = ν ∗ O X ( 1 ) . Since ν \nu ν H H H ν ∗ F i h \nu^*F_i^h ν ∗ F i h ν ∗ X 0 D \nu^*X_0^D ν ∗ X 0 D H ⊗ D H^{\otimes D} H ⊗ D Y Y Y H H H
c 1 ( H ) s − 1 ⋅ div ( ν ∗ F i h ) = c 1 ( H ) s − 1 ⋅ div ( ν ∗ X 0 D ) = D deg X ‾ . c_1(H)^{s-1}\cdot\operatorname{div}(\nu^*F_i^h) = c_1(H)^{s-1}\cdot\operatorname{div}(\nu^*X_0^D) = D\deg\overline{X}. c 1 ( H ) s − 1 ⋅ div ( ν ∗ F i h ) = c 1 ( H ) s − 1 ⋅ div ( ν ∗ X 0 D ) = D deg X . Since ν \nu ν deg ( ν ) = 1 \deg(\nu)=1 deg ( ν ) = 1 [22 Tag 0BEX] gives deg H ( Y ) = deg O ( 1 ) ( X ‾ ) = deg X ‾ \deg_H(Y)=\deg_{\mathcal{O}(1)}(\overline{X})=\deg\overline{X} deg H ( Y ) = deg O ( 1 ) ( X ) = deg X H H H E E E Y Y Y H H H 1 1 1 div ( ν ∗ F i h ) \operatorname{div}(\nu^*F_i^h) div ( ν ∗ F i h ) H H H D deg X ‾ D\deg\overline{X} D deg X 1 1 1 D deg X ‾ D\deg\overline{X} D deg X div ( ν ∗ X 0 D ) \operatorname{div}(\nu^*X_0^D) div ( ν ∗ X 0 D )
ord E ( u i ) = ord E ( ν ∗ F i h ) − ord E ( ν ∗ X 0 D ) , \operatorname{ord}_E(u_i) = \operatorname{ord}_E(\nu^*F_i^h) - \operatorname{ord}_E(\nu^*X_0^D), ord E ( u i ) = ord E ( ν ∗ F i h ) − ord E ( ν ∗ X 0 D ) , with both terms on the right between 0 0 0 D deg X ‾ D\deg\overline{X} D deg X
∣ ord E ( u i ) ∣ ≤ D deg X ‾ ≤ D m + 1 = V . (6) \left|\operatorname{ord}_E(u_i)\right| \le D\deg\overline{X} \le D^{m+1} = V. \tag*{(6)} ∣ ord E ( u i ) ∣ ≤ D deg X ≤ D m + 1 = V . (6) For
u e = u 1 e 1 ⋯ u k e k , u^e = u_1^{e_1}\cdots u_k^{e_k}, u e = u 1 e 1 ⋯ u k e k , the additivity of ord E \operatorname{ord}_E ord E
ord E ( u e ) = ∑ i = 1 k e i ord E ( u i ) . \operatorname{ord}_E(u^e) = \sum_{i=1}^{k}e_i\operatorname{ord}_E(u_i). ord E ( u e ) = i = 1 ∑ k e i ord E ( u i ) . Thus the condition that u e u^e u e E E E e e e
For each positive-dimensional component X X X p \mathfrak{p} p A A A E E E
( ord E ( u 1 ) , … , ord E ( u k ) ) ∈ Z k . \left(\operatorname{ord}_E(u_1),\ldots,\operatorname{ord}_E(u_k)\right)\in\mathbb{Z}^k. ( ord E ( u 1 ) , … , ord E ( u k ) ) ∈ Z k . Only finitely many of these rows are nonzero, since each u i u_i u i M M M (6) , every entry of M M M V V V
Alg K ( u ) = ker Z ( M ) . \operatorname{Alg}_K(u)=\ker_{\mathbb{Z}}(M). Alg K ( u ) = ker Z ( M ) . Suppose first that e ∈ ker Z ( M ) e\in\ker_{\mathbb{Z}}(M) e ∈ ker Z ( M ) Y Y Y
u e = u 1 e 1 ⋯ u k e k u^e=u_1^{e_1}\cdots u_k^{e_k} u e = u 1 e 1 ⋯ u k e k has zero order along every prime divisor. Thus both u e u^e u e ( u e ) − 1 (u^e)^{-1} ( u e ) − 1 Y Y Y Y Y Y [22 Tag 0AVB] . Hence u e u^e u e Y Y Y Y Y Y K K K Γ ( Y , O Y ) \Gamma(Y,\mathcal{O}_Y) Γ ( Y , O Y ) K K K [22 Tag 0BUG] . Since Y Y Y Γ ( Y , O Y ) \Gamma(Y,\mathcal{O}_Y) Γ ( Y , O Y ) Γ ( Y , O Y ) \Gamma(Y,\mathcal{O}_Y) Γ ( Y , O Y ) K K K Γ ( Y , O Y ) \Gamma(Y,\mathcal{O}_Y) Γ ( Y , O Y ) K K K u e u^e u e Y Y Y K ( Y ) ≃ Frac ( A / p ) K(Y)\simeq\operatorname{Frac}(A/\mathfrak{p}) K ( Y ) ≃ Frac ( A / p ) K K K K K K
For each minimal prime p \mathfrak{p} p A A A f p ∈ K [ T ] f_{\mathfrak{p}}\in K[T] f p ∈ K [ T ] u e u^e u e A / p A/\mathfrak{p} A / p
f = ∏ p ∈ Min ( A ) f p , f=\prod_{\mathfrak{p}\in\operatorname{Min}(A)} f_{\mathfrak{p}}, f = p ∈ Min ( A ) ∏ f p , we have
f ( u e ) ∈ ⋂ p ∈ Min ( A ) p = 0 . f(u^e)\in\bigcap_{\mathfrak{p}\in\operatorname{Min}(A)}\mathfrak{p}=\sqrt{0}. f ( u e ) ∈ p ∈ Min ( A ) ⋂ p = 0 . Hence f ( u e ) f(u^e) f ( u e )
f ( u e ) N = 0 f(u^e)^N=0 f ( u e ) N = 0 for some N ≥ 1 N\ge1 N ≥ 1 f ( T ) N ∈ K [ T ] f(T)^N\in K[T] f ( T ) N ∈ K [ T ] u e u^e u e u e u^e u e K K K e ∈ Alg K ( u ) e\in\operatorname{Alg}_K(u) e ∈ Alg K ( u )
Conversely, suppose that e ∈ Alg K ( u ) e\in\operatorname{Alg}_K(u) e ∈ Alg K ( u ) g ∈ K [ T ] g\in K[T] g ∈ K [ T ] g ( u e ) = 0 g(u^e)=0 g ( u e ) = 0 A A A p \mathfrak{p} p A A A π : A → A / p \pi:A\to A/\mathfrak{p} π : A → A / p u e u^e u e A A A π ( u e ) \pi(u^e) π ( u e ) A / p A/\mathfrak{p} A / p π \pi π g ( u e ) = 0 g(u^e)=0 g ( u e ) = 0 g ( π ( u e ) ) = 0 g(\pi(u^e))=0 g ( π ( u e )) = 0 A / p A/\mathfrak{p} A / p K K K g ∈ K [ T ] g\in K[T] g ∈ K [ T ] u e u^e u e K ( Y ) ≃ Frac ( A / p ) K(Y)\simeq\operatorname{Frac}(A/\mathfrak{p}) K ( Y ) ≃ Frac ( A / p ) K K K ord E \operatorname{ord}_E ord E K K K K ( Y ) K(Y) K ( Y ) K K K
c 0 + c 1 a + ⋯ + c d a d = 0 , c 0 c d ≠ 0 , c_0+c_1a+\cdots+c_da^d=0,\qquad c_0c_d\ne0, c 0 + c 1 a + ⋯ + c d a d = 0 , c 0 c d = 0 , over K K K ord E ( a ) > 0 \operatorname{ord}_E(a)>0 ord E ( a ) > 0 ord E ( a ) < 0 \operatorname{ord}_E(a)<0 ord E ( a ) < 0
ord E ( u e ) = 0 \operatorname{ord}_E(u^e)=0 ord E ( u e ) = 0 for every such E E E e ∈ ker Z ( M ) e\in\ker_{\mathbb{Z}}(M) e ∈ ker Z ( M )
Alg K ( u ) = ker Z ( M ) . \operatorname{Alg}_K(u)=\ker_{\mathbb{Z}}(M). Alg K ( u ) = ker Z ( M ) . It remains to bound a basis of the integer kernel. Let ρ = rank M \rho= \operatorname{rank} M ρ = rank M ρ = 0 \rho= 0 ρ = 0 ker Z ( M ) = Z k \ker_{\mathbb{Z}}(M) = \mathbb{Z}^k ker Z ( M ) = Z k ρ = k \rho= k ρ = k ker Z ( M ) = 0 \ker_{\mathbb{Z}}(M) = 0 ker Z ( M ) = 0 0 < ρ < k 0 < \rho< k 0 < ρ < k ρ \rho ρ M M M M M M Q \mathbb{Q} Q Q \mathbb{Q} Q Z k \mathbb{Z}^k Z k ρ \rho ρ ρ × ρ \rho\times\rho ρ × ρ
where C ∈ Z ρ × ρ C \in\mathbb{Z}^{\rho\times\rho} C ∈ Z ρ × ρ
Δ = det C ≠ 0. \Delta= \det C \ne0. Δ = det C = 0. Since all entries have absolute value at most V V V
∣ Δ ∣ ≤ ρ ! V ρ . |\Delta| \le\rho!V^\rho. ∣Δ∣ ≤ ρ ! V ρ . Write a kernel vector as ( x , y ) (x,y) ( x , y ) x ∈ Z ρ x \in\mathbb{Z}^{\rho} x ∈ Z ρ y ∈ Z k − ρ y \in\mathbb{Z}^{k-\rho} y ∈ Z k − ρ
C x + T y = 0 , Cx + Ty = 0, C x + T y = 0 , and hence
x = − C − 1 T y = − adj ( C ) T y Δ . x = -C^{-1}Ty = -\frac{\operatorname{adj}(C)Ty}{\Delta}. x = − C − 1 T y = − Δ adj ( C ) T y . Thus projection onto the last k − ρ k-\rho k − ρ ker Z ( M ) \ker_{\mathbb{Z}}(M) ker Z ( M )
L_y = \left\{y \in\mathbb{Z}^{k-\rho} \mathrel{\left|} \operatorname{adj}(C)Ty \equiv0 \pmod{\Delta}\right.\right\}.
In particular,
Δ Z k − ρ ⊆ L y ⊆ Z k − ρ . \Delta\mathbb{Z}^{k-\rho} \subseteq L_y \subseteq\mathbb{Z}^{k-\rho}. Δ Z k − ρ ⊆ L y ⊆ Z k − ρ . Let H y = ( h i j ) H_y = (h_{ij}) H y = ( h ij ) L y L_y L y
h i i > 0 , h i j = 0 ( i < j ) , 0 ≤ h i j < h j j ( i > j ) ; h_{ii} > 0,\qquad h_{ij} = 0\ (i < j),\qquad0 \le h_{ij} < h_{jj}\ (i > j); h ii > 0 , h ij = 0 ( i < j ) , 0 ≤ h ij < h j j ( i > j ) ; see [5 ] , Algorithm 2.4.5. Since
Δ Z k − ρ ⊆ L y , \Delta\mathbb{Z}^{k-\rho} \subseteq L_y, Δ Z k − ρ ⊆ L y , we have Δ e j ∈ L y \Delta e_j \in L_y Δ e j ∈ L y j j j Δ e j \Delta e_j Δ e j H y H_y H y k − ρ k-\rho k − ρ j j j j + 1 , … , k − ρ j+1,\ldots,k-\rho j + 1 , … , k − ρ Δ \Delta Δ h j j h_{jj} h j j
h j j ∣ Δ . h_{jj} \mid\Delta. h j j ∣ Δ. Hence h j j ≤ ∣ Δ ∣ h_{jj} \le|\Delta| h j j ≤ ∣Δ∣ ∣ h i j ∣ < h j j ≤ ∣ Δ ∣ |h_{ij}| < h_{jj} \le|\Delta| ∣ h ij ∣ < h j j ≤ ∣Δ∣ y 1 , … , y k − ρ y_1,\ldots,y_{k-\rho} y 1 , … , y k − ρ H y H_y H y L y L_y L y
∥ y j ∥ ∞ ≤ ∣ Δ ∣ ≤ ρ ! V ρ . \lVert y_j\rVert_\infty\le|\Delta| \le\rho!V^\rho. ∥ y j ∥ ∞ ≤ ∣Δ∣ ≤ ρ ! V ρ . For each y j y_j y j
x j = − adj ( C ) T y j Δ . x_j = -\frac{\operatorname{adj}(C)Ty_j}{\Delta}. x j = − Δ adj ( C ) T y j . Since
∥ T y j ∥ ∞ ≤ ( k − ρ ) V ∣ Δ ∣ \lVert Ty_j\rVert_\infty\le(k-\rho)V|\Delta| ∥ T y j ∥ ∞ ≤ ( k − ρ ) V ∣Δ∣ and every entry of adj ( C ) \operatorname{adj}(C) adj ( C ) ( ρ − 1 ) × ( ρ − 1 ) (\rho-1) \times(\rho-1) ( ρ − 1 ) × ( ρ − 1 ) C C C
( ρ − 1 ) ! V ρ − 1 , (\rho-1)!V^{\rho-1}, ( ρ − 1 )! V ρ − 1 , each coordinate of adj ( C ) T y j \operatorname{adj}(C)^{T}y_j adj ( C ) T y j
ρ ( ρ − 1 ) ! V ρ − 1 ( k − ρ ) V ∣ Δ ∣ . \rho(\rho-1)!V^{\rho-1}(k-\rho)V|\Delta|. ρ ( ρ − 1 )! V ρ − 1 ( k − ρ ) V ∣Δ∣. Therefore
∥ x j ∥ ∞ ≤ ρ ! ( k − ρ ) V ρ . \lVert x_j\rVert_\infty\le\rho!(k-\rho)V^\rho. ∥ x j ∥ ∞ ≤ ρ ! ( k − ρ ) V ρ . Thus
∥ ( x j , y j ) ∥ ∞ ≤ ρ ! ( k − ρ ) V ρ ≤ k ! V k = B 0 . \lVert(x_j,y_j)\rVert_\infty\le\rho!(k-\rho)V^\rho\le k!V^k = B_0. ∥( x j , y j ) ∥ ∞ ≤ ρ ! ( k − ρ ) V ρ ≤ k ! V k = B 0 . since ρ ! ( k − ρ ) ≤ ρ ! ( k − ρ ) ! ≤ k ! \rho!(k-\rho)\le\rho!(k-\rho)!\le k! ρ ! ( k − ρ ) ≤ ρ ! ( k − ρ )! ≤ k ! V ρ ≤ V k V^\rho\le V^k V ρ ≤ V k V ≥ 1 V\ge1 V ≥ 1 k − ρ k-\rho k − ρ ker Z ( M ) \ker_{\mathbb{Z}}(M) ker Z ( M ) L y L_y L y ( x j , y j ) (x_j,y_j) ( x j , y j ) ker Z ( M ) = Alg K ( u ) \ker_{\mathbb{Z}}(M)=\operatorname{Alg}_K(u) ker Z ( M ) = Alg K ( u )
Proposition 3.2. A basis of Alg K ( u ) \operatorname{Alg}_K(u) Alg K ( u )
Proof. Enumerate all vectors
e ∈ [ − B 0 , B 0 ] k ∩ Z k . e\in[-B_0,B_0]^k\cap\mathbb{Z}^k. e ∈ [ − B 0 , B 0 ] k ∩ Z k . Since m m m k k k B 0 B_0 B 0 D D D
For each e = ( e 1 , … , e k ) e=(e_1,\ldots,e_k) e = ( e 1 , … , e k ) u i u_i u i u i − 1 u_i^{-1} u i − 1 g e ∈ K [ X 1 , … , X m ] g_e\in K[X_1,\ldots,X_m] g e ∈ K [ X 1 , … , X m ]
u e = u 1 e 1 ⋯ u k e k . u^e=u_1^{e_1}\cdots u_k^{e_k}. u e = u 1 e 1 ⋯ u k e k . Since at most k B 0 kB_0 k B 0
deg g e ≤ k B 0 D . \deg g_e\le kB_0D. deg g e ≤ k B 0 D . As m m m g e g_e g e Q \mathbb{Q} Q F p \mathbb{F}_p F p p p p g e g_e g e
Apply Lemma 2.9 to g e + I ∈ A g_e+I\in A g e + I ∈ A e ∈ Alg K ( u ) e\in\operatorname{Alg}_K(u) e ∈ Alg K ( u ) Proposition 3.1 , the accepted vectors contain a basis of Alg K ( u ) \operatorname{Alg}_K(u) Alg K ( u ) Alg K ( u ) \operatorname{Alg}_K(u) Alg K ( u ) Alg K ( u ) \operatorname{Alg}_K(u) Alg K ( u )
Proof of Theorem 1.1 . Proposition 3.1 gives the asserted bound on a basis of Alg K ( u ) \operatorname{Alg}_K(u) Alg K ( u ) Proposition 3.2 provides a deterministic polynomial-time algorithm for computing such a basis. □
Relation lattices in affine Q-algebras
We now compute multiplicative relation lattices in affine Q \mathbb{Q} Q
Proposition 3.3. For fixed m m m k k k Rel A ( u 1 , … , u k ) \operatorname{Rel}_A(u_1,\ldots,u_k) Rel A ( u 1 , … , u k ) u 1 , … , u k u_1,\ldots,u_k u 1 , … , u k
A = Q [ X 1 , … , X m ] / I , I = ( f 1 , … , f s ) , A=\mathbb{Q}[X_1,\ldots,X_m]/I,\qquad I=(f_1,\ldots,f_s), A = Q [ X 1 , … , X m ] / I , I = ( f 1 , … , f s ) , with the degree and coefficient encoding above.
Proof. The case A = 0 A=0 A = 0 A ≠ 0 A\ne0 A = 0 Proposition 3.2 to compute a basis b 1 , … , b r b_1,\ldots,b_r b 1 , … , b r Alg Q ( u ) \operatorname{Alg}_{\mathbb{Q}}(u) Alg Q ( u )
v j = u b j ( 1 ≤ j ≤ r ) . v_j=u^{b_j}\qquad(1\le j\le r). v j = u b j ( 1 ≤ j ≤ r ) . If r = 0 r=0 r = 0 Rel A ( u 1 , … , u k ) = 0 \operatorname{Rel}_A(u_1,\ldots,u_k)=0 Rel A ( u 1 , … , u k ) = 0 j j j v j v_j v j u i u_i u i u i − 1 u_i^{-1} u i − 1 Lemma 2.9 to compute a monic polynomial g j ( T ) ∈ Q [ T ] g_j(T)\in\mathbb{Q}[T] g j ( T ) ∈ Q [ T ] v j v_j v j
d j = deg g j . d_j=\deg g_j. d j = deg g j . The polynomial representatives of the v j v_j v j Lemma 2.9 gives polynomial bounds on the degrees and coefficient bit lengths of the g j g_j g j
The subalgebra
B = Q [ v 1 , … , v r ] ⊆ A B=\mathbb{Q}[v_1,\ldots,v_r]\subseteq A B = Q [ v 1 , … , v r ] ⊆ A is spanned over Q \mathbb{Q} Q
w α = v 1 α 1 ⋯ v r α r , 0 ≤ α j < d j ; w_\alpha=v_1^{\alpha_1}\cdots v_r^{\alpha_r},\qquad0\leq\alpha_j<d_j; w α = v 1 α 1 ⋯ v r α r , 0 ≤ α j < d j ; since the monic relation g j ( v j ) = 0 g_j(v_j)=0 g j ( v j ) = 0 v j n v_j^n v j n n ≥ d j n\geq d_j n ≥ d j Q \mathbb{Q} Q
M = ∏ j = 1 r d j M=\prod_{j=1}^{r}d_j M = j = 1 ∏ r d j monomials. Since r ≤ k r\leq k r ≤ k d j d_j d j M M M w α w_\alpha w α
We next compute the structure constants of B B B w α w_\alpha w α c α ∈ Q c_\alpha\in\mathbb{Q} c α ∈ Q
∑ α c α w α = 0 in A \sum_\alpha c_\alpha w_\alpha=0\qquad\text{in }A α ∑ c α w α = 0 in A is equivalent to an identity
∑ α c α W α = ∑ i = 1 s h i f i , \sum_\alpha c_\alpha W_\alpha=\sum_{i=1}^{s}h_i f_i, α ∑ c α W α = i = 1 ∑ s h i f i , where W α ∈ Q [ X 1 , … , X m ] W_\alpha\in\mathbb{Q}[X_1,\ldots,X_m] W α ∈ Q [ X 1 , … , X m ] w α w_\alpha w α h i ∈ Q [ X 1 , … , X m ] h_i\in\mathbb{Q}[X_1,\ldots,X_m] h i ∈ Q [ X 1 , … , X m ] E E E W α W_\alpha W α c α ∈ Q c_\alpha\in\mathbb{Q} c α ∈ Q
F = ∑ α c α W α F=\sum_\alpha c_\alpha W_\alpha F = α ∑ c α W α has degree at most E E E m m m [2 Theorem 3.4] gives a bound polynomial in E E E D D D c α c_\alpha c α F ∈ I F\in I F ∈ I h i h_i h i
F = ∑ i = 1 s h i f i . F=\sum_{i=1}^{s}h_i f_i. F = i = 1 ∑ s h i f i . As in the proof of Lemma 2.5 , we introduce the coefficients of the h i h_i h i Q \mathbb{Q} Q c α c_\alpha c α w α w_\alpha w α
B = { w α 1 , … , w α n } \mathcal{B}=\{w_{\alpha_1},\ldots,w_{\alpha_n}\} B = { w α 1 , … , w α n } of B B B
We next compute the multiplication table of B B B B \mathcal{B} B w α i , w α k w_{\alpha_i}, w_{\alpha_k} w α i , w α k v j v_j v j
g j ( v j ) = 0 , g_j(v_j)=0, g j ( v j ) = 0 , reduce all exponents of the v j v_j v j d j d_j d j Q \mathbb{Q} Q w α w_\alpha w α w α w_\alpha w α Q \mathbb{Q} Q B \mathcal{B} B B B B 1 1 1 v j v_j v j B \mathcal{B} B
Each v j v_j v j B B B v j v_j v j B B B v j v_j v j A A A B B B Q \mathbb{Q} Q v j − 1 ∈ B v_j^{-1}\in B v j − 1 ∈ B [16 Theorem 1.11(i)] , which computes in deterministic polynomial time generators for
Γ = ker ( Z r ⟶ B × , z ⟼ ∏ j = 1 r v j z j ) . \Gamma=\ker\left(\mathbb{Z}^r\longrightarrow B^\times,\quad z\longmapsto\prod_{j=1}^{r}v_j^{z_j}\right). Γ = ker ( Z r ⟶ B × , z ⟼ j = 1 ∏ r v j z j ) . The algorithm applies to arbitrary finite-dimensional commutative Q \mathbb{Q} Q B B B
Let U ∈ Z k × r U\in\mathbb{Z}^{k\times r} U ∈ Z k × r b 1 , … , b r b_1,\ldots,b_r b 1 , … , b r e ∈ Rel A ( u 1 , … , u k ) e\in\operatorname{Rel}_A(u_1,\ldots,u_k) e ∈ Rel A ( u 1 , … , u k ) Alg Q ( u ) \operatorname{Alg}_{\mathbb{Q}}(u) Alg Q ( u ) u e = 1 u^e=1 u e = 1 Q \mathbb{Q} Q z ∈ Z r z\in\mathbb{Z}^r z ∈ Z r
By the definition of the v j v_j v j
u U z = ∏ j = 1 r v j z j , u^{Uz}=\prod_{j=1}^{r}v_j^{z_j}, u U z = j = 1 ∏ r v j z j , and, since B ⊆ A B\subseteq A B ⊆ A
u U z = 1 in A ⟺ ∏ j = 1 r v j z j = 1 in B ⟺ z ∈ Γ . u^{Uz}=1\text{ in }A\quad\Longleftrightarrow\quad\prod_{j=1}^{r}v_j^{z_j}=1\text{ in }B\quad\Longleftrightarrow\quad z\in\Gamma. u U z = 1 in A ⟺ j = 1 ∏ r v j z j = 1 in B ⟺ z ∈ Γ. Therefore
Rel A ( u 1 , … , u k ) = U Γ . \operatorname{Rel}_A(u_1,\ldots,u_k)=U\Gamma. Rel A ( u 1 , … , u k ) = U Γ. Thus, multiplying the computed generators of Γ \Gamma Γ U U U Rel A ( u 1 , … , u k ) \operatorname{Rel}_A(u_1,\ldots,u_k) Rel A ( u 1 , … , u k )
Relation lattices over rings of prime-power characteristic
In this section we prove that a basis of the relation lattice Rel A ( u 1 , … , u k ) \operatorname{Rel}_A(u_1,\ldots,u_k) Rel A ( u 1 , … , u k ) u 1 , … , u k u_1,\ldots,u_k u 1 , … , u k
A = ( Z / p a Z ) [ X 1 , … , X m ] / I , I = ( f 1 , … , f s ) , A=(\mathbb{Z}/p^a\mathbb{Z})[X_1,\ldots,X_m]/I,\qquad I=(f_1,\ldots,f_s), A = ( Z / p a Z ) [ X 1 , … , X m ] / I , I = ( f 1 , … , f s ) , where p p p a ≥ 1 a\ge1 a ≥ 1 m m m k k k f 1 , … , f s f_1,\ldots,f_s f 1 , … , f s I I I u 1 , … , u k u_1,\ldots,u_k u 1 , … , u k p a p^a p a p a p^a p a ⌊ a log 2 p ⌋ + 1 \lfloor a\log_2 p\rfloor+1 ⌊ a log 2 p ⌋ + 1
We first show how to construct an exact presentation of a finite subring generated by elements satisfying monic polynomial relations.
Let 0 ≤ r ≤ k 0 \le r \le k 0 ≤ r ≤ k v 1 , … , v r ∈ A v_1,\ldots,v_r \in A v 1 , … , v r ∈ A j j j g j ( T ) ∈ ( Z / p a Z ) [ T ] g_j(T) \in(\mathbb{Z}/p^a\mathbb{Z})[T] g j ( T ) ∈ ( Z / p a Z ) [ T ] g j ( v j ) = 0 g_j(v_j)=0 g j ( v j ) = 0
B = ( Z / p a Z ) [ v 1 , … , v r ] ⊆ A . B=(\mathbb{Z}/p^a\mathbb{Z})[v_1,\ldots,v_r]\subseteq A. B = ( Z / p a Z ) [ v 1 , … , v r ] ⊆ A . Lemma 4.1 (An exact finite-subring presentation). The ring B B B B B B
Proof. Put d j = deg g j d_j=\deg g_j d j = deg g j Proposition 3.3 , the monic relations g j ( v j ) = 0 g_j(v_j)=0 g j ( v j ) = 0 B B B Z / p a Z \mathbb{Z}/p^a\mathbb{Z} Z / p a Z
w α = v 1 α 1 ⋯ v r α r , 0 ≤ α j < d j . w_\alpha=v_1^{\alpha_1}\cdots v_r^{\alpha_r},\qquad0\le\alpha_j<d_j. w α = v 1 α 1 ⋯ v r α r , 0 ≤ α j < d j . The number of these monomials is
M = ∏ j = 1 r d j . M=\prod_{j=1}^{r}d_j. M = j = 1 ∏ r d j . Since r ≤ k r\le k r ≤ k k k k d j d_j d j M M M w α w_\alpha w α
We next determine all additive relations among the spanning monomials. Unlike the rational case, these relations form an integer lattice rather than a vector space over Q \mathbb{Q} Q w 1 , … , w M w_1,\ldots,w_M w 1 , … , w M
\Omega=\left\{c\in\mathbb{Z}^{M}\mathrel{\left|}\sum_{i=1}^{M}c_iw_i=0\text{ in }A\right.\right\}.
Then
B a d d ≅ Z M / Ω . B_{\mathrm{add}}\cong\mathbb{Z}^{M}/\Omega. B add ≅ Z M /Ω. For each i i i W i ∈ Z [ X 1 , … , X m ] W_i\in\mathbb{Z}[X_1,\ldots,X_m] W i ∈ Z [ X 1 , … , X m ] w i w_i w i f 1 , … , f s f_1,\ldots,f_s f 1 , … , f s I I I
A ≅ Z [ X 1 , … , X m ] / ( f 1 , … , f s , p a ) . A\cong\mathbb{Z}[X_1,\ldots,X_m]/(f_1,\ldots,f_s,p^a). A ≅ Z [ X 1 , … , X m ] / ( f 1 , … , f s , p a ) . Every c ∈ Ω c\in\Omega c ∈ Ω p a Z M p^a\mathbb{Z}^{M} p a Z M c ( 0 ) ∈ Ω c^{(0)}\in\Omega c ( 0 ) ∈ Ω
0 ≤ c i ( 0 ) < p a . 0\le c_i^{(0)}<p^a. 0 ≤ c i ( 0 ) < p a . For such a vector, the polynomial
∑ i = 1 M c i ( 0 ) W i \sum_{i=1}^{M}c_i^{(0)}W_i i = 1 ∑ M c i ( 0 ) W i has polynomially bounded degree and coefficient bit length.
By Aschenbrenner’s integer ideal-membership bound [2 Theorem A] , there is a uniform bound E E E m m m
∑ i = 1 M c i ( 0 ) W i = ∑ ν = 1 s f ν h ν + p a h 0 , 0 ≤ c i ( 0 ) < p a , \sum_{i=1}^{M}c_i^{(0)}W_i=\sum_{\nu=1}^{s}f_\nu h_\nu+p^ah_0,\qquad0\le c_i^{(0)}<p^a, i = 1 ∑ M c i ( 0 ) W i = ν = 1 ∑ s f ν h ν + p a h 0 , 0 ≤ c i ( 0 ) < p a , that holds for some integer polynomials h ν h_\nu h ν deg h ν ≤ E \deg h_\nu\le E deg h ν ≤ E ν \nu ν
We now consider the equation
∑ i = 1 M c i W i = ∑ ν = 1 s f ν h ν + p a h 0 , (7) \sum_{i=1}^{M} c_i W_i = \sum_{\nu=1}^{s} f_\nu h_\nu+ p^a h_0, \tag*{(7)} i = 1 ∑ M c i W i = ν = 1 ∑ s f ν h ν + p a h 0 , (7) where the c i c_i c i h 0 , h 1 , … , h s h_0,h_1,\ldots,h_s h 0 , h 1 , … , h s E E E h ν h_\nu h ν
The projection of its integer solution lattice onto the c c c Ω \Omega Ω Ω \Omega Ω c ( 0 ) ∈ Ω c^{(0)} \in\Omega c ( 0 ) ∈ Ω 0 ≤ c i ( 0 ) < p a 0 \le c_i^{(0)} < p^a 0 ≤ c i ( 0 ) < p a p a e i p^a e_i p a e i h 0 = W i h_0 = W_i h 0 = W i h ν = 0 h_\nu= 0 h ν = 0 Ω \Omega Ω c ( 0 ) c^{(0)} c ( 0 ) p a Z M p^a\mathbb{Z}^M p a Z M Ω \Omega Ω
Standard polynomial-time integer linear algebra computes a basis of the integer solution lattice. Projecting this basis onto the c c c Ω \Omega Ω
Smith normal form, together with the corresponding unimodular transformation matrices, now gives an explicit decomposition
B a d d = Z M / Ω ≃ Z / n 1 Z ⊕ ⋯ ⊕ Z / n t Z . B_{\mathrm{add}} = \mathbb{Z}^M/\Omega\simeq\mathbb{Z}/n_1\mathbb{Z} \oplus\cdots\oplus\mathbb{Z}/n_t\mathbb{Z}. B add = Z M /Ω ≃ Z / n 1 Z ⊕ ⋯ ⊕ Z / n t Z . Since p a Z M ⊆ Ω p^a\mathbb{Z}^M \subseteq\Omega p a Z M ⊆ Ω n i n_i n i p a p^a p a 0 , … , n i − 1 0,\ldots,n_i-1 0 , … , n i − 1
We next compute the multiplication table of B B B w α , w β w_\alpha,w_\beta w α , w β v j v_j v j g j ( v j ) = 0 g_j(v_j)=0 g j ( v j ) = 0 Z / p a Z \mathbb{Z}/p^a\mathbb{Z} Z / p a Z
The resulting multiplication table has polynomial size, and ring operations in the canonical representation can be performed in deterministic polynomial time. □
Given a group G G G H ≤ G H \le G H ≤ G X X X f : G → X f:G \to X f : G → X H H H g 1 , g 2 ∈ G g_1,g_2 \in G g 1 , g 2 ∈ G f ( g 1 ) = f ( g 2 ) f(g_1)=f(g_2) f ( g 1 ) = f ( g 2 ) g 1 H = g 2 H g_1H=g_2H g 1 H = g 2 H f f f H H H H H H
Lemma 4.2 (Relations in a finite ring). There is a bounded-error quantum polynomial-time algorithm that computes a basis of Rel B ( v 1 , … , v r ) \operatorname{Rel}_B(v_1,\ldots,v_r) Rel B ( v 1 , … , v r )
Proof. By Lemma 4.1, the ring B B B v i v_i v i [21 ] to compute
o i = ord B × ( v i ) ≤ ∣ B ∣ , i = 1 , … , r . o_i = \operatorname{ord}_{B^\times}(v_i) \le|B|,\qquad i=1,\ldots,r. o i = ord B × ( v i ) ≤ ∣ B ∣ , i = 1 , … , r . Since ∣ B ∣ ≤ ( p a ) M |B| \le(p^a)^M ∣ B ∣ ≤ ( p a ) M o i o_i o i
Consider the composition of group homomorphisms
Z r → φ ⨁ i = 1 r Z / o i Z → ψ B × , \mathbb{Z}^r \xrightarrow{\varphi} \bigoplus_{i=1}^{r}\mathbb{Z}/o_i\mathbb{Z} \xrightarrow{\psi} B^\times, Z r φ i = 1 ⨁ r Z / o i Z ψ B × , where φ \varphi φ ψ ( e ) = v e \psi(e)=v^e ψ ( e ) = v e
Rel B ( v 1 , … , v r ) = ker ( ψ ∘ φ ) = φ − 1 ( ker ψ ) . \operatorname{Rel}_{B}(v_1,\ldots,v_r)=\ker(\psi\circ\varphi)=\varphi^{-1}(\ker\psi). Rel B ( v 1 , … , v r ) = ker ( ψ ∘ φ ) = φ − 1 ( ker ψ ) . The homomorphism ψ \psi ψ ker ψ \ker\psi ker ψ [4 ] therefore computes generators g 1 , … , g t g_1,\ldots,g_t g 1 , … , g t ker ψ \ker\psi ker ψ
Choose lifts g ~ 1 , … , g ~ t ∈ Z r \widetilde{g}_1,\ldots,\widetilde{g}_t\in\mathbb{Z}^r g 1 , … , g t ∈ Z r
Rel B ( v 1 , … , v r ) = ⟨ g ~ 1 , … , g ~ t , o 1 e 1 , … , o r e r ⟩ . \operatorname{Rel}_{B}(v_1,\ldots,v_r)=\langle\widetilde{g}_1,\ldots,\widetilde{g}_t,o_1e_1,\ldots,o_re_r\rangle. Rel B ( v 1 , … , v r ) = ⟨ g 1 , … , g t , o 1 e 1 , … , o r e r ⟩ . where e 1 , … , e r e_1,\ldots,e_r e 1 , … , e r Z r \mathbb{Z}^r Z r Rel B ( v 1 , … , v r ) \operatorname{Rel}_{B}(v_1,\ldots,v_r) Rel B ( v 1 , … , v r ) □ \square □
Proposition 4.3. Under the standing assumptions of this section, a basis of Rel A ( u 1 , … , u k ) \operatorname{Rel}_{A}(u_1,\ldots,u_k) Rel A ( u 1 , … , u k )
Proof. The case A = 0 A=0 A = 0 A ≠ 0 A\ne0 A = 0 A ‾ = A / p A \overline{A}=A/pA A = A / p A u ‾ i \overline{u}_i u i u i u_i u i A ‾ \overline{A} A Theorem 1.1 to compute a basis b 1 , … , b r b_1,\ldots,b_r b 1 , … , b r
L = Alg F p ( u ‾ 1 , … , u ‾ k ) . L=\operatorname{Alg}_{\mathbb{F}_p}(\overline{u}_1,\ldots,\overline{u}_k). L = Alg F p ( u 1 , … , u k ) . If r = 0 r=0 r = 0 Rel A ( u 1 , … , u k ) = 0 \operatorname{Rel}_{A}(u_1,\ldots,u_k)=0 Rel A ( u 1 , … , u k ) = 0
Put v j = u b j v_j=u^{b_j} v j = u b j j = 1 , … , r j=1,\ldots,r j = 1 , … , r Proposition 3.2 , the coordinates of the b j b_j b j u i u_i u i v j v_j v j Lemma 2.9 to each v ‾ j ∈ A ‾ \overline{v}_j\in\overline{A} v j ∈ A g j ( T ) ∈ F p [ T ] g_j(T)\in\mathbb{F}_p[T] g j ( T ) ∈ F p [ T ]
g j ( v ‾ j ) = 0. g_j(\overline{v}_j)=0. g j ( v j ) = 0. The degrees and coefficient bit lengths of these polynomials are polynomially bounded. Choose a monic coefficient lift g ~ j ( T ) ∈ ( Z / p a Z ) [ T ] \widetilde{g}_j(T)\in(\mathbb{Z}/p^a\mathbb{Z})[T] g j ( T ) ∈ ( Z / p a Z ) [ T ] g j ( T ) g_j(T) g j ( T ) g j ( v ‾ j ) = 0 g_j(\overline{v}_j)=0 g j ( v j ) = 0
g ~ j ( v j ) ∈ p A . \widetilde{g}_j(v_j)\in pA. g j ( v j ) ∈ p A . Consequently,
g ~ j ( v j ) a ∈ p a A = 0. \widetilde{g}_j(v_j)^a\in p^aA=0. g j ( v j ) a ∈ p a A = 0. Thus
G j ( T ) = g ~ j ( T ) a G_j(T)=\widetilde{g}_j(T)^a G j ( T ) = g j ( T ) a is a monic polynomial annihilating v j v_j v j deg G j = a deg g j \deg G_j=a\deg g_j deg G j = a deg g j a ≤ log 2 ( p a ) a\le\log_2(p^a) a ≤ log 2 ( p a ) G j G_j G j
By Lemma 4.1 , the subring
B = ( Z / p a Z ) [ v 1 , … , v r ] ⊆ A B=(\mathbb{Z}/p^a\mathbb{Z})[v_1,\ldots,v_r]\subseteq A B = ( Z / p a Z ) [ v 1 , … , v r ] ⊆ A has an exact finite presentation with unique polynomial-length encodings and polynomial-time ring operations.
Each v j v_j v j B B B v j v_j v j B B B v j v_j v j A A A B B B v j − 1 ∈ B v_j^{-1}\in B v j − 1 ∈ B
We may therefore apply Lemma 4.2 to compute a basis of
Γ = Rel B ( v 1 , … , v r ) \Gamma=\operatorname{Rel}_{B}(v_1,\ldots,v_r) Γ = Rel B ( v 1 , … , v r ) in bounded-error quantum polynomial time. Let U ∈ Z k × r U \in\mathbb{Z}^{k \times r} U ∈ Z k × r b 1 , … , b r b_1,\ldots,b_r b 1 , … , b r
Rel A ( u 1 , … , u k ) ⊆ Rel A ‾ ( u ‾ 1 , … , u ‾ k ) ⊆ L , \operatorname{Rel}_{A}(u_1,\ldots,u_k) \subseteq\operatorname{Rel}_{\overline{A}}(\overline{u}_1,\ldots,\overline{u}_k) \subseteq L, Rel A ( u 1 , … , u k ) ⊆ Rel A ( u 1 , … , u k ) ⊆ L , every relation e ∈ Rel A ( u 1 , … , u k ) e \in\operatorname{Rel}_{A}(u_1,\ldots,u_k) e ∈ Rel A ( u 1 , … , u k ) e = U z e=Uz e = U z z ∈ Z r z \in\mathbb{Z}^r z ∈ Z r v j v_j v j
u U z = ∏ j = 1 r v j z j , u^{Uz}=\prod_{j=1}^{r}v_j^{z_j}, u U z = j = 1 ∏ r v j z j , and, since B ⊆ A B \subseteq A B ⊆ A
u U z = 1 in A ⟺ ∏ j = 1 r v j z j = 1 in B ⟺ z ∈ Γ . u^{Uz}=1\text{ in }A \quad\Longleftrightarrow\quad\prod_{j=1}^{r}v_j^{z_j}=1\text{ in }B \quad\Longleftrightarrow\quad z\in\Gamma. u U z = 1 in A ⟺ j = 1 ∏ r v j z j = 1 in B ⟺ z ∈ Γ. Therefore
Rel A ( u 1 , … , u k ) = U Γ . (8) \operatorname{Rel}_{A}(u_1,\ldots,u_k)=U\Gamma. \tag*{(8)} Rel A ( u 1 , … , u k ) = U Γ. (8) Multiplying the computed basis vectors of Γ \Gamma Γ U U U Rel A ( u 1 , … , u k ) \operatorname{Rel}_{A}(u_1,\ldots,u_k) Rel A ( u 1 , … , u k )
Proof of Theorem 1.2
Let S = Z [ X 1 , … , X m ] / I S=\mathbb{Z}[X_1,\ldots,X_m]/I S = Z [ X 1 , … , X m ] / I S S S 1 ∈ I 1\in I 1 ∈ I Proposition 2.1 , this can be done in deterministic polynomial time. If S = 0 S=0 S = 0 u 1 e 1 ⋯ u k e k u_1^{e_1}\cdots u_k^{e_k} u 1 e 1 ⋯ u k e k 1 1 1 S S S e = ( e 1 , … , e k ) ∈ Z k e=(e_1,\ldots,e_k)\in\mathbb{Z}^k e = ( e 1 , … , e k ) ∈ Z k
Rel S ( u 1 , … , u k ) = Z k , \operatorname{Rel}_{S}(u_1,\ldots,u_k)=\mathbb{Z}^k, Rel S ( u 1 , … , u k ) = Z k , and we output the standard basis of Z k \mathbb{Z}^k Z k S ≠ 0 S\ne0 S = 0
Compute the integer c c c [21 ] . Write
c = ∏ ν = 1 t p ν a ν . c=\prod_{\nu=1}^{t}p_\nu^{a_\nu}. c = ν = 1 ∏ t p ν a ν . Since c c c t t t p ν a ν p_\nu^{a_\nu} p ν a ν
S ⟶ ( S ⊗ Q ) × S / c S S\longrightarrow(S\otimes\mathbb{Q})\times S/cS S ⟶ ( S ⊗ Q ) × S / c S is injective. Moreover, the Chinese remainder theorem gives
S / c S ≃ ∏ ν = 1 t S / p ν a ν S . S/cS\simeq\prod_{\nu=1}^{t}S/p_\nu^{a_\nu}S. S / c S ≃ ν = 1 ∏ t S / p ν a ν S . Consequently,
Rel S ( u 1 , … , u k ) = Rel S ⊗ Q ( u 1 , … , u k ) ∩ ⋂ ν = 1 t Rel S / p ν a ν S ( u 1 , … , u k ) . (9) \operatorname{Rel}_{S}(u_1,\ldots,u_k)=\operatorname{Rel}_{S\otimes\mathbb{Q}}(u_1,\ldots,u_k)\cap\bigcap_{\nu=1}^{t}\operatorname{Rel}_{S/p_\nu^{a_\nu}S}(u_1,\ldots,u_k). \tag*{(9)} Rel S ( u 1 , … , u k ) = Rel S ⊗ Q ( u 1 , … , u k ) ∩ ν = 1 ⋂ t Rel S / p ν a ν S ( u 1 , … , u k ) . (9) The relation lattice over S ⊗ Q S\otimes\mathbb{Q} S ⊗ Q Proposition 3.3 , and those over the prime-power quotients are computed by Proposition 4.3 . Zero-ring factors impose no restriction. If c = 1 c=1 c = 1
It remains to compute the intersection of the resulting integer lattices. Let B 1 , … , B ℓ B_1,\ldots,B_\ell B 1 , … , B ℓ B i B_i B i r i r_i r i x ∈ Z k x\in\mathbb{Z}^k x ∈ Z k
x = B i z i , z i ∈ Z r i , i = 1 , … , ℓ . x=B_i z_i,\qquad z_i\in\mathbb{Z}^{r_i},\qquad i=1,\ldots,\ell. x = B i z i , z i ∈ Z r i , i = 1 , … , ℓ . These equations form a homogeneous integer linear system whose solution lattice projects onto the required intersection.
Since each B i B_i B i x x x
The combined system has polynomially many rows and columns, and its coefficients have polynomially bounded bit lengths. Standard polynomial-time integer kernel algorithms therefore compute a basis of its solution lattice with polynomially bounded bit lengths. The same bounds hold for the projected basis.
All remaining classical computations take deterministic polynomial time. Amplifying the polynomially many quantum subroutines ensures that the overall probability of correctness is at least 2 / 3 2/3 2/3 RelS ( u 1 , … , u k ) \operatorname{RelS}(u_1,\ldots,u_k) RelS ( u 1 , … , u k ) □ \square □
Proof of Corollary 1.3
Apply Theorem 1.2 to the k + 1 k+1 k + 1 h , u 1 , … , u k h,u_1,\ldots,u_k h , u 1 , … , u k b 1 , … , b r b_1,\ldots,b_r b 1 , … , b r
Λ = RelS ( h , u 1 , … , u k ) ≤ Z k + 1 . \Lambda=\operatorname{RelS}(h,u_1,\ldots,u_k)\leq\mathbb{Z}^{k+1}. Λ = RelS ( h , u 1 , … , u k ) ≤ Z k + 1 . Write
b j = ( c j , v j ) , c j ∈ Z , v j ∈ Z k . b_j=(c_j,v_j),\qquad c_j\in\mathbb{Z},\quad v_j\in\mathbb{Z}^k. b j = ( c j , v j ) , c j ∈ Z , v j ∈ Z k . and put
g = gcd ( c 1 , … , c r ) , g=\gcd(c_1,\ldots,c_r), g = g cd( c 1 , … , c r ) , where g = 0 g=0 g = 0 r = 0 r=0 r = 0 c j c_j c j
The subgroup of first coordinates of elements of Λ \Lambda Λ g Z g\mathbb{Z} g Z
( − 1 , e ) ∈ Λ ⟺ h − 1 u e = 1 ⟺ u e = h , (-1,e)\in\Lambda\quad\Longleftrightarrow\quad h^{-1}u^e=1\quad\Longleftrightarrow\quad u^e=h, ( − 1 , e ) ∈ Λ ⟺ h − 1 u e = 1 ⟺ u e = h , we have
h ∈ ⟨ u 1 , … , u k ⟩ ⟺ − 1 ∈ g Z ⟺ g = 1. h\in\langle u_1,\ldots,u_k\rangle\quad\Longleftrightarrow\quad-1\in g\mathbb{Z}\quad\Longleftrightarrow\quad g=1. h ∈ ⟨ u 1 , … , u k ⟩ ⟺ − 1 ∈ g Z ⟺ g = 1. Suppose that g = 1 g=1 g = 1 λ 1 , … , λ r \lambda_1,\ldots,\lambda_r λ 1 , … , λ r
∑ j = 1 r λ j c j = − 1. \sum_{j=1}^{r}\lambda_jc_j=-1. j = 1 ∑ r λ j c j = − 1. Put
e 0 = ∑ j = 1 r λ j v j . e_0=\sum_{j=1}^{r}\lambda_jv_j. e 0 = j = 1 ∑ r λ j v j . Then ( − 1 , e 0 ) ∈ Λ (-1,e_0)\in\Lambda ( − 1 , e 0 ) ∈ Λ u e 0 = h u^{e_0}=h u e 0 = h e ∈ Z k e\in\mathbb{Z}^k e ∈ Z k
u e = h ⟺ u e − e 0 = 1 ⟺ e − e 0 ∈ RelS ( u 1 , … , u k ) . u^e=h\quad\Longleftrightarrow\quad u^{e-e_0}=1\quad\Longleftrightarrow\quad e-e_0\in\operatorname{RelS}(u_1,\ldots,u_k). u e = h ⟺ u e − e 0 = 1 ⟺ e − e 0 ∈ RelS ( u 1 , … , u k ) . Consequently,
{ e ∈ Z k : u e = h } = e 0 + RelS ( u 1 , … , u k ) . \{e\in\mathbb{Z}^k:u^e=h\}=e_0+\operatorname{RelS}(u_1,\ldots,u_k). { e ∈ Z k : u e = h } = e 0 + RelS ( u 1 , … , u k ) . All the additional computations use polynomial-time integer linear algebra. Since k + 1 k+1 k + 1 Theorem 1.2 also takes bounded-error quantum polynomial time. □ \square □
The conjugacy-to-orbit reduction
In this section, we reduce the conjugacy problem in a finitely generated metabelian group to an orbit problem in a finitely presented module over its integral group ring. We also show that this reduction can be carried out in polynomial time.
Let G G G k k k
A = G ′ , Q = G / A A = G', \qquad Q = G/A A = G ′ , Q = G / A be the derived subgroup and the abelianization of G G G φ : G → Q \varphi:G \to Q φ : G → Q G G G A A A Q Q Q
Conjugation by elements of G G G Q Q Q A A A A A A A A A A A A
R = Z Q . R = \mathbb{Z}Q. R = Z Q . We use right conjugation, a g = g − 1 a g a^g = g^{-1}ag a g = g − 1 a g A A A R R R
a ⋅ φ ( g ) = a g , [ a , g ] = a ⋅ ( φ ( g ) − 1 ) a \cdot\varphi(g) = a^g, \qquad[a,g] = a \cdot\left(\varphi(g)-1\right) a ⋅ φ ( g ) = a g , [ a , g ] = a ⋅ ( φ ( g ) − 1 ) for all a ∈ A a \in A a ∈ A g ∈ G g \in G g ∈ G
R-module coordinates in the derived subgroup
The derived subgroup A = G ′ A = G' A = G ′ R R R
a i j = [ x i , x j ] , 1 ≤ i < j ≤ k . a_{ij} = [x_i,x_j], \qquad1 \leq i < j \leq k. a ij = [ x i , x j ] , 1 ≤ i < j ≤ k . Thus every a ∈ A a \in A a ∈ A
a = ∑ 1 ≤ i < j ≤ k a i j f i j , f i j ∈ R . a = \sum_{1 \leq i < j \leq k} a_{ij} f_{ij}, \qquad f_{ij} \in R. a = 1 ≤ i < j ≤ k ∑ a ij f ij , f ij ∈ R . We call ( f i j ) i < j (f_{ij})_{i<j} ( f ij ) i < j R R R a a a a i j a_{ij} a ij R R R
Proposition 7.1. Fix k ≥ 1 k \geq1 k ≥ 1 There is a deterministic algorithm that, given a k k k G G G w = w ( x 1 , … , x k ) w = w(x_1,\ldots,x_k) w = w ( x 1 , … , x k ) G ′ G' G ′ R R R ( f i j ) i < j (f_{ij})_{i<j} ( f ij ) i < j w w w
The running time is polynomial in N + ∣ w ∣ N + |w| N + ∣ w ∣ N = m + ∑ i = 1 m ∣ r i ∣ N = m + \sum_{i=1}^{m} |r_i| N = m + ∑ i = 1 m ∣ r i ∣ k k k
Each coordinate f i j f_{ij} f ij N + ∣ w ∣ N + |w| N + ∣ w ∣ k k k
Proof. Let F = F ( x 1 , … , x k ) F = F(x_1,\ldots,x_k) F = F ( x 1 , … , x k ) α : F → Z k \alpha:F \to\mathbb{Z}^k α : F → Z k
v i = α ( r i ) ∈ Z k , 1 ≤ i ≤ m , v_i = \alpha(r_i) \in\mathbb{Z}^k, \qquad1 \leq i \leq m, v i = α ( r i ) ∈ Z k , 1 ≤ i ≤ m , and let V V V v 1 , … , v m v_1,\ldots,v_m v 1 , … , v m w w w G ′ G' G ′
α ( w ) ∈ ⟨ v 1 , … , v m ⟩ . \alpha(w) \in\langle v_1,\ldots,v_m\rangle. α ( w ) ∈ ⟨ v 1 , … , v m ⟩ . Thus the integer system
V c = − α ( w ) Vc = -\alpha(w) V c = − α ( w ) has a solution. The matrix V V V k k k N N N ∥ α ( w ) ∥ ∞ ≤ ∣ w ∣ \lVert\alpha(w)\rVert_{\infty} \le|w| ∥ α ( w ) ∥ ∞ ≤ ∣ w ∣ k k k c ∈ Z m c \in\mathbb{Z}^{m} c ∈ Z m
V c = − α ( w ) , ∑ i = 1 m ∣ c i ∣ ≤ ( N + ∣ w ∣ ) O ( k ) . Vc=-\alpha(w),\qquad\sum_{i=1}^{m}|c_i|\le(N+|w|)^{O(k)}. V c = − α ( w ) , i = 1 ∑ m ∣ c i ∣ ≤ ( N + ∣ w ∣ ) O ( k ) . Moreover, such a solution can be computed in deterministic polynomial time using integer linear algebra algorithms.
Set
u = r 1 c 1 ⋯ r m c m . u=r_1^{c_1}\cdots r_m^{c_m}. u = r 1 c 1 ⋯ r m c m . The word u u u G G G
∣ u ∣ ≤ ( N + ∣ w ∣ ) O ( k ) . |u|\le(N+|w|)^{O(k)}. ∣ u ∣ ≤ ( N + ∣ w ∣ ) O ( k ) . Moreover,
α ( w u ) = 0 , \alpha(wu)=0, α ( w u ) = 0 , so w u ∈ F ′ wu\in F' w u ∈ F ′ w w w w u wu w u G ′ G' G ′
L = ∣ w u ∣ ≤ ( N + ∣ w ∣ ) O ( k ) . L=|wu|\le(N+|w|)^{O(k)}. L = ∣ w u ∣ ≤ ( N + ∣ w ∣ ) O ( k ) . Collect the word w u wu w u
x 1 ± 1 , x 2 ± 1 , … , x k ± 1 . x_1^{\pm1},x_2^{\pm1},\ldots,x_k^{\pm1}. x 1 ± 1 , x 2 ± 1 , … , x k ± 1 . Whenever adjacent letters a = x j ± 1 a=x_j^{\pm1} a = x j ± 1 b = x i ± 1 b=x_i^{\pm1} b = x i ± 1 j > i j>i j > i
s a b v = s b a v ⋅ [ a , b ] v . sabv=sbav\cdot[a,b]^v. s ab v = s ba v ⋅ [ a , b ] v . Each interchange introduces a conjugate of a commutator of two generator letters. At most O ( L 2 ) O(L^2) O ( L 2 ) O ( L ) O(L) O ( L ) [ x j ± 1 , x i ± 1 ] [x_j^{\pm1},x_i^{\pm1}] [ x j ± 1 , x i ± 1 ] [ x i , x j ] ± 1 [x_i,x_j]^{\pm1} [ x i , x j ] ± 1 w u ∈ F ′ wu\in F' w u ∈ F ′
w u = ∏ ℓ = 1 T ( [ x i ℓ , x j ℓ ] ε ℓ ) h ℓ , wu=\prod_{\ell=1}^{T}\left([x_{i_\ell},x_{j_\ell}]^{\varepsilon_\ell}\right)^{h_\ell}, w u = ℓ = 1 ∏ T ( [ x i ℓ , x j ℓ ] ε ℓ ) h ℓ , where T = O ( L 2 ) T=O(L^2) T = O ( L 2 ) ε ℓ ∈ { 1 , − 1 } \varepsilon_\ell\in\{1,-1\} ε ℓ ∈ { 1 , − 1 } ∣ h ℓ ∣ = O ( L ) |h_\ell|=O(L) ∣ h ℓ ∣ = O ( L )
Passing to G G G G ′ G' G ′
w = ∑ ℓ = 1 T ε ℓ a i ℓ j ℓ φ ( h ℓ ) . w=\sum_{\ell=1}^{T}\varepsilon_\ell a_{i_\ell j_\ell}\varphi(h_\ell). w = ℓ = 1 ∑ T ε ℓ a i ℓ j ℓ φ ( h ℓ ) . Grouping terms corresponding to each pair i < j i<j i < j R R R
w = ∑ 1 ≤ i < j ≤ k a i j f i j , where f i j = ∑ ℓ : ( i ℓ , j ℓ ) = ( i , j ) ε ℓ φ ( h ℓ ) . w=\sum_{1\le i<j\le k}a_{ij}f_{ij},\qquad
\text{where }f_{ij}=\sum_{\ell:(i_\ell,j_\ell)=(i,j)}\varepsilon_\ell\varphi(h_\ell). w = 1 ≤ i < j ≤ k ∑ a ij f ij , where f ij = ℓ : ( i ℓ , j ℓ ) = ( i , j ) ∑ ε ℓ φ ( h ℓ ) . We represent these coordinates as Laurent polynomials in the images of x 1 , … , x k x_1,\ldots,x_k x 1 , … , x k Q Q Q Q Q Q f i j f_{ij} f ij O ( L 2 ) O(L^2) O ( L 2 ) x 1 , … , x k x_1,\ldots,x_k x 1 , … , x k O ( L ) O(L) O ( L ) O ( L 2 ) O(L^2) O ( L 2 ) L ≤ ( N + ∣ w ∣ ) O ( k ) L\le(N+|w|)^{O(k)} L ≤ ( N + ∣ w ∣ ) O ( k ) ( N + ∣ w ∣ ) O ( k ) (N+|w|)^{O(k)} ( N + ∣ w ∣ ) O ( k ) O ( k log ( N + ∣ w ∣ ) ) O(k\log(N+|w|)) O ( k log ( N + ∣ w ∣ )) N + ∣ w ∣ N + |w| N + ∣ w ∣ k k k
From conjugacy to orbit membership
Let x , y ∈ G x,y \in G x , y ∈ G Q Q Q φ \varphi φ
φ ( x ) = φ ( y ) = q ∈ Q . \varphi(x) = \varphi(y) = q \in Q. φ ( x ) = φ ( y ) = q ∈ Q . For every a ∈ A a \in A a ∈ A
[ a , x ] = a ⋅ ( q − 1 ) . [a,x] = a \cdot(q - 1). [ a , x ] = a ⋅ ( q − 1 ) . Hence, the subgroup
D = ( q − 1 ) A D = (q - 1)A D = ( q − 1 ) A consists precisely of the commutators [ a , x ] [a,x] [ a , x ] a ∈ A a \in A a ∈ A
Lemma 7.2. The following hold:
(a) D ⊴ G D \trianglelefteq G D ⊴ G
(b) x D xD x D A / D A/D A / D G / D G/D G / D
Proof. Since D D D R R R A A A G G G a ∈ A a \in A a ∈ A
[ a , x ] = a ⋅ ( q − 1 ) ∈ D . [a,x] = a \cdot(q - 1) \in D. [ a , x ] = a ⋅ ( q − 1 ) ∈ D . Hence x D xD x D A / D A/D A / D
Put
M = A / D , C = ⟨ M , x D ⟩ ≤ G / D . M = A/D,\qquad C = \langle M,xD\rangle\leq G/D. M = A / D , C = ⟨ M , x D ⟩ ≤ G / D . Lemma 7.3. The following hold:
(a) C C C G / D G/D G / D
(b) conjugation induces an R R R C C C
(c) y D ∈ C yD \in C y D ∈ C
Proof. By Lemma 7.2(b), the element x D xD x D M M M M M M C C C g ∈ G g \in G g ∈ G
x g = x [ x , g ] , x^{g} = x[x,g], x g = x [ x , g ] , where [ x , g ] ∈ A [x,g] \in A [ x , g ] ∈ A g D gD g D C C C C C C G / D G/D G / D
Since M ⊆ C M \subseteq C M ⊆ C C C C A A A C C C G G G C C C Q = G / A Q = G/A Q = G / A C C C R R R
Finally, since φ ( x ) = φ ( y ) \varphi(x) = \varphi(y) φ ( x ) = φ ( y ) x − 1 y ∈ A x^{-1}y \in A x − 1 y ∈ A
y D = ( x D ) ( x − 1 y D ) ∈ C , yD = (xD)(x^{-1}yD) \in C, y D = ( x D ) ( x − 1 y D ) ∈ C , proving (c).
The following proposition shows that conjugacy in G G G Q Q Q C C C
Proposition 7.4 (Noskov reduction). Let x , y ∈ G x,y \in G x , y ∈ G Q Q Q D D D C C C
x ∼ G y ⟺ y D = ( x D ) ⋅ s for some s ∈ Q . (10) x \sim_G y \quad\Longleftrightarrow\quad yD = (xD)\cdot s \quad\text{for some } s \in Q. \tag*{(10)} x ∼ G y ⟺ y D = ( x D ) ⋅ s for some s ∈ Q . (10) Proof. (⇒ \Rightarrow ⇒ x g = y x^g = y x g = y g ∈ G g \in G g ∈ G
y D = ( x D ) ⋅ φ ( g ) , yD = (xD) \cdot\varphi(g), y D = ( x D ) ⋅ φ ( g ) , proving the forward implication.
(⇐ \Leftarrow ⇐
y D = ( x D ) ⋅ s yD = (xD) \cdot s y D = ( x D ) ⋅ s for some s ∈ Q s \in Q s ∈ Q g ∈ G g \in G g ∈ G φ ( g ) = s \varphi(g) = s φ ( g ) = s x g D = y D x^gD = yD x g D = y D
for some d ∈ D d \in D d ∈ D
Since φ ( y ) = q \varphi(y) = q φ ( y ) = q A ⟶ A A \longrightarrow A A ⟶ A a ↦ [ y , a ] a \mapsto[y,a] a ↦ [ y , a ] ( 1 − q ) A = D (1-q)A = D ( 1 − q ) A = D a ∈ A a \in A a ∈ A [ y , a ] = d − 1 [y,a] = d^{-1} [ y , a ] = d − 1 A A A a a a d d d
x g a = ( x g ) a = ( y d ) a = y [ y , a ] d = y . x^{ga} = (x^g)^a = (yd)^a = y[y,a]d = y. x g a = ( x g ) a = ( y d ) a = y [ y , a ] d = y . Thus x x x y y y G G G
An explicit R R R A A A
We now show that a finite R R R A = G ′ A = G' A = G ′ G G G
Proposition 7.5. Fix k ≥ 1 k \ge1 k ≥ 1 There is a deterministic algorithm that, given a k k k G G G (1.3), constructs a finite R R R A = G ′ A = G' A = G ′ a i j = [ x i , x j ] a_{ij} = [x_i,x_j] a ij = [ x i , x j ]
N = m + ∑ i = 1 m ∣ r i ∣ , N = m + \sum_{i=1}^{m} |r_i|, N = m + i = 1 ∑ m ∣ r i ∣ , with degree depending only on k k k Z [ t 1 ± 1 , … , t k ± 1 ] \mathbb{Z}[t_1^{\pm1},\ldots,t_k^{\pm1}] Z [ t 1 ± 1 , … , t k ± 1 ] with polynomially bounded degrees, support sizes, and coefficient bit lengths.
Proof. Let F = F ( x 1 , … , x k ) F = F(x_1,\ldots,x_k) F = F ( x 1 , … , x k )
H = F / F ′ ′ , T = Z [ t 1 ± 1 , … , t k ± 1 ] . H = F/F'', \qquad T = \mathbb{Z}[t_1^{\pm1},\ldots,t_k^{\pm1}]. H = F / F ′′ , T = Z [ t 1 ± 1 , … , t k ± 1 ] . Then H H H k k k H ′ H' H ′ T T T H ′ H' H ′ a i j = [ x i , x j ] a_{ij} = [x_i,x_j] a ij = [ x i , x j ]
t i t j ( t ℓ − 1 ) a i j − t i t ℓ ( t j − 1 ) a i ℓ + t j t ℓ ( t i − 1 ) a j ℓ = 0 , 1 ≤ i < j < ℓ ≤ k . (11) t_i t_j(t_\ell- 1)a_{ij} - t_i t_\ell(t_j - 1)a_{i\ell} + t_j t_\ell(t_i - 1)a_{j\ell} = 0,\qquad1 \le i < j < \ell\le k. \tag*{(11)} t i t j ( t ℓ − 1 ) a ij − t i t ℓ ( t j − 1 ) a i ℓ + t j t ℓ ( t i − 1 ) a j ℓ = 0 , 1 ≤ i < j < ℓ ≤ k . (11) Indeed, after introducing the normalized generators
b i j = t i t j a i j , b_{ij} = t_i t_j a_{ij}, b ij = t i t j a ij , these become the Koszul relations
b i j ( t ℓ − 1 ) − b i ℓ ( t j − 1 ) + b j ℓ ( t i − 1 ) = 0. b_{ij}(t_\ell- 1) - b_{i\ell}(t_j - 1) + b_{j\ell}(t_i - 1) = 0. b ij ( t ℓ − 1 ) − b i ℓ ( t j − 1 ) + b j ℓ ( t i − 1 ) = 0. Their completeness follows from the Magnus embedding and the exactness of the Koszul complex associated with t 1 − 1 , … , t k − 1 t_1 - 1,\ldots,t_k - 1 t 1 − 1 , … , t k − 1
Let K K K r 1 , … , r m r_1,\ldots,r_m r 1 , … , r m H H H
G = H / K , A = G ′ ≅ H ′ / ( K ∩ H ′ ) . G = H/K,\qquad A = G' \cong H'/(K \cap H'). G = H / K , A = G ′ ≅ H ′ / ( K ∩ H ′ ) . Let α : H → Z k \alpha: H \to\mathbb{Z}^k α : H → Z k
v i = α ( r i ) , V = ( v 1 ⋯ v m ) ∈ Z k × m . v_i = \alpha(r_i),\qquad V = (v_1\ \cdots\ v_m) \in\mathbb{Z}^{k \times m}. v i = α ( r i ) , V = ( v 1 ⋯ v m ) ∈ Z k × m . Thus
Q ≅ Z k / im V , R = Z Q ≅ T / J , Q \cong\mathbb{Z}^{k}/\operatorname{im} V,\qquad R=\mathbb{Z}Q\cong T/J, Q ≅ Z k / im V , R = Z Q ≅ T / J , where
J = ( t v 1 − 1 , … , t v m − 1 ) , t v = t 1 v 1 ⋯ t k v k . J=(t^{v_1}-1,\ldots,t^{v_m}-1),\qquad t^v=t_1^{v_1}\cdots t_k^{v_k}. J = ( t v 1 − 1 , … , t v m − 1 ) , t v = t 1 v 1 ⋯ t k v k . We first determine generators of K ∩ H ′ K\cap H' K ∩ H ′ T T T
S 1 = { [ r i , x j ] ∣ 1 ≤ i ≤ m , 1 ≤ j ≤ k } . S_1=\{[r_i,x_j]\mid1\le i\le m,\ 1\le j\le k\}. S 1 = {[ r i , x j ] ∣ 1 ≤ i ≤ m , 1 ≤ j ≤ k } . Choose a Z \mathbb{Z} Z c ( 1 ) , … , c ( s ) c^{(1)},\ldots,c^{(s)} c ( 1 ) , … , c ( s ) ker Z V \ker_{\mathbb{Z}}V ker Z V
ρ ℓ = r 1 c 1 ( ℓ ) ⋯ r m c m ( ℓ ) , 1 ≤ ℓ ≤ s . \rho_\ell=r_1^{c^{(\ell)}_1}\cdots r_m^{c^{(\ell)}_m},\qquad1\le\ell\le s. ρ ℓ = r 1 c 1 ( ℓ ) ⋯ r m c m ( ℓ ) , 1 ≤ ℓ ≤ s . Since α ( ρ ℓ ) = V c ( ℓ ) = 0 \alpha(\rho_\ell)=Vc^{(\ell)}=0 α ( ρ ℓ ) = V c ( ℓ ) = 0 ρ ℓ \rho_\ell ρ ℓ K ∩ H ′ K\cap H' K ∩ H ′
S 2 = { ρ 1 , … , ρ s } . S_2=\{\rho_1,\ldots,\rho_s\}. S 2 = { ρ 1 , … , ρ s } . We claim that
K ∩ H ′ = ⟨ S 1 ∪ S 2 ⟩ T . (12) K\cap H'=\langle S_1\cup S_2\rangle_T. \tag*{(12)} K ∩ H ′ = ⟨ S 1 ∪ S 2 ⟩ T . (12) The normal closure of S 1 S_1 S 1 H H H [ K , H ] [K,H] [ K , H ] r i r_i r i x j x_j x j K K K [ K , H ] ⊆ H ′ [K,H]\subseteq H' [ K , H ] ⊆ H ′ H ′ H' H ′
[ K , H ] = ⟨ S 1 ⟩ T . [K,H]=\langle S_1\rangle_T. [ K , H ] = ⟨ S 1 ⟩ T . The quotient K / [ K , H ] K/[K,H] K / [ K , H ] r i r_i r i
β : Z m ⟶ K / [ K , H ] , c ⟼ r 1 c 1 ⋯ r m c m [ K , H ] \beta:\mathbb{Z}^m\longrightarrow K/[K,H],\qquad c\longmapsto r_1^{c_1}\cdots r_m^{c_m}[K,H] β : Z m ⟶ K / [ K , H ] , c ⟼ r 1 c 1 ⋯ r m c m [ K , H ] is surjective, and its composition with the map induced by α \alpha α V V V
For any z ∈ K ∩ H ′ z\in K\cap H' z ∈ K ∩ H ′ c ∈ Z m c\in\mathbb{Z}^m c ∈ Z m z [ K , H ] = β ( c ) z[K,H]=\beta(c) z [ K , H ] = β ( c ) V c = α ( z ) = 0 Vc=\alpha(z)=0 V c = α ( z ) = 0
c = ∑ ℓ = 1 s n ℓ c ( ℓ ) c=\sum_{\ell=1}^{s}n_\ell c^{(\ell)} c = ℓ = 1 ∑ s n ℓ c ( ℓ ) for some integers n ℓ n_\ell n ℓ
z [ K , H ] = ∏ ℓ = 1 s ρ ℓ n ℓ [ K , H ] . z[K,H]=\prod_{\ell=1}^{s}\rho_\ell^{n_\ell}[K,H]. z [ K , H ] = ℓ = 1 ∏ s ρ ℓ n ℓ [ K , H ] . Since [ K , H ] [K,H] [ K , H ] S 1 S_1 S 1 T T T (12) .
The conjugation action of H H H A A A Q = G / A Q=G/A Q = G / A J J J A A A
J H ′ ⊆ K ∩ H ′ . JH'\subseteq K\cap H'. J H ′ ⊆ K ∩ H ′ . By (12) , an R R R A A A (11) by adjoining the coordinate vectors of the elements of S 1 ∪ S 2 S_1\cup S_2 S 1 ∪ S 2 T T T R R R
We now establish the complexity bounds. The matrix V V V k k k N N N r = rank V ≤ k r=\operatorname{rank}V\le k r = rank V ≤ k r = 0 r=0 r = 0 ker Z V = Z m \ker_{\mathbb{Z}}V=\mathbb{Z}^m ker Z V = Z m r > 0 r>0 r > 0 r × r r\times r r × r V V V
D = r ! N r ≤ k ! N k . D=r!N^r\le k!N^k. D = r ! N r ≤ k ! N k . Choose r r r r r r r × r r\times r r × r B B B V V V ( B C ) (B\ C) ( B C ) V V V Q \mathbb{Q} Q
ker Z V = { ( u , w ) ∈ Z r ⊕ Z m − r ∣ B u + C w = 0 } . \ker_{\mathbb{Z}}V=\{(u,w)\in\mathbb{Z}^r\oplus\mathbb{Z}^{m-r}\mid Bu+Cw=0\}. ker Z V = {( u , w ) ∈ Z r ⊕ Z m − r ∣ B u + C w = 0 } . Put d = ∣ det B ∣ ≤ D d = |\det B| \le D d = ∣ det B ∣ ≤ D w w w
L = { w ∈ Z m − r ∣ adj ( B ) C w ≡ 0 ( m o d d ) } . L = \{w \in\mathbb{Z}^{m-r} \mid\operatorname{adj}(B)Cw \equiv0 \pmod{d}\}. L = { w ∈ Z m − r ∣ adj ( B ) C w ≡ 0 ( mod d )} . This lattice is the projection onto the first m − r m-r m − r
adj ( B ) C w − d z = 0 , ( w , z ) ∈ Z m − r ⊕ Z r . \operatorname{adj}(B)Cw - dz = 0, \qquad(w,z) \in\mathbb{Z}^{m-r} \oplus\mathbb{Z}^{r}. adj ( B ) C w − d z = 0 , ( w , z ) ∈ Z m − r ⊕ Z r . Since z z z w w w L L L L L L
Z m − r ⟶ ( Z / d Z ) r , \mathbb{Z}^{m-r} \longrightarrow(\mathbb{Z}/d\mathbb{Z})^{r}, Z m − r ⟶ ( Z / d Z ) r , so
[ Z m − r : L ] ≤ d r ≤ D k . [\mathbb{Z}^{m-r}:L] \le d^{r} \le D^{k}. [ Z m − r : L ] ≤ d r ≤ D k . A reduced Hermite normal form basis of L L L D k D^{k} D k w w w L L L
u = − B − 1 C w . u=-B^{-1}Cw. u = − B − 1 C w . The defining congruence of L L L u u u B − 1 C B^{-1}C B − 1 C r × r r \times r r × r V V V D D D
∥ ( u , w ) ∥ 1 ≤ ( m − r ) D k + r ( m − r ) D k + 1 ≤ N O ( k 2 ) . \|(u,w)\|_{1} \le(m-r)D^{k} + r(m-r)D^{k+1} \le N^{O(k^{2})}. ∥ ( u , w ) ∥ 1 ≤ ( m − r ) D k + r ( m − r ) D k + 1 ≤ N O ( k 2 ) . These vectors form a Z \mathbb{Z} Z c ( 1 ) , … , c ( s ) c^{(1)},\ldots,c^{(s)} c ( 1 ) , … , c ( s ) ker Z V \ker_{\mathbb{Z}} V ker Z V s = m − r ≤ m s=m-r \le m s = m − r ≤ m
∣ ρ ℓ ∣ ≤ ∑ i = 1 m ∣ c i ( ℓ ) ∣ ∣ r i ∣ ≤ N O ( k 2 ) . |\rho_{\ell}| \le\sum_{i=1}^{m} |c_{i}^{(\ell)}|\,|r_{i}| \le N^{O(k^{2})}. ∣ ρ ℓ ∣ ≤ i = 1 ∑ m ∣ c i ( ℓ ) ∣ ∣ r i ∣ ≤ N O ( k 2 ) . The words [ r i , x j ] [r_i,x_j] [ r i , x j ] O ( ∣ r i ∣ + 1 ) O(|r_i|+1) O ( ∣ r i ∣ + 1 ) ρ ℓ \rho_{\ell} ρ ℓ H ′ H' H ′ T T T Proposition 7.1 . Their degrees, support sizes, and coefficient bit lengths are polynomially bounded in N N N k k k
Finally, the presentation contains at most
( k 3 ) + m k + s ≤ ( k 3 ) + m k + m \binom{k}{3}+mk+s \le\binom{k}{3}+mk+m ( 3 k ) + mk + s ≤ ( 3 k ) + mk + m relations. Hence it has polynomial size and can be constructed in deterministic polynomial time, with degree depending only on k k k
An explicit R R R C C C
Noskov’s reduction is the structural step underlying his decidability theorem [20 ] . To obtain a polynomial-time reduction, we must construct an explicit R R R C C C
By Proposition 7.5 , a finite R R R
A = ⟨ a i j ( 1 ≤ i < j ≤ k ) ∣ R A ⟩ R A=\langle a_{ij}\ (1\le i<j\le k)\mid\mathcal{R}_{A}\rangle_{R} A = ⟨ a ij ( 1 ≤ i < j ≤ k ) ∣ R A ⟩ R can be constructed in polynomial time from the defining relations of G G G M = A / ( q − 1 ) A M=A/(q-1)A M = A / ( q − 1 ) A
( q − 1 ) a i j = 0 , 1 ≤ i < j ≤ k , (q-1)a_{ij}=0,\qquad1\le i<j\le k, ( q − 1 ) a ij = 0 , 1 ≤ i < j ≤ k , to R A \mathcal{R}_{A} R A R M \mathcal{R}_{M} R M 1 ≤ j ≤ k 1\le j\le k 1 ≤ j ≤ k
c j = [ x , x j ] D ∈ M . c_j=[x,x_j]D\in M. c j = [ x , x j ] D ∈ M . We represent each c j c_j c j R R R a i j a_{ij} a ij q q q o o o
c 0 = x o D ∈ M . c_0=x^oD\in M. c 0 = x o D ∈ M . Lemma 7.6. Fix k ≥ 1 k\ge1 k ≥ 1 k k k G G G x ∈ G x\in G x ∈ G R R R C C C
C = { ⟨ a i j ( i < j ) , e ∣ R M , ( q j − 1 ) e = c j ( 1 ≤ j ≤ k ) ⟩ R , if ∣ q ∣ = ∞ , ⟨ a i j ( i < j ) , e ∣ R M , ( q j − 1 ) e = c j ( 1 ≤ j ≤ k ) , o e = c 0 ⟩ R , if ∣ q ∣ = o < ∞ . C=\begin{cases}
\left\langle a_{ij}\ (i<j),e\mid\mathcal{R}_M,\ (q_j-1)e=c_j\ (1\le j\le k)\right\rangle_R, & \text{if } |q|=\infty,\\
\left\langle a_{ij}\ (i<j),e\mid\mathcal{R}_M,\ (q_j-1)e=c_j\ (1\le j\le k),\ oe=c_0\right\rangle_R, & \text{if } |q|=o<\infty.
\end{cases} C = { ⟨ a ij ( i < j ) , e ∣ R M , ( q j − 1 ) e = c j ( 1 ≤ j ≤ k ) ⟩ R , ⟨ a ij ( i < j ) , e ∣ R M , ( q j − 1 ) e = c j ( 1 ≤ j ≤ k ) , oe = c 0 ⟩ R , if ∣ q ∣ = ∞ , if ∣ q ∣ = o < ∞. Here e e e x D xD x D a i j a_{ij} a ij M M M
This presentation can be constructed in deterministic polynomial time in N + ∣ x ∣ N+|x| N + ∣ x ∣ N = m + ∑ i = 1 m ∣ r i ∣ N=m+\sum_{i=1}^{m}|r_i| N = m + ∑ i = 1 m ∣ r i ∣ k k k
Proof. Let C ~ \widetilde{C} C R R R C C C
a i j ↦ a i j D , e ↦ x D a_{ij}\mapsto a_{ij}D,\qquad e\mapsto xD a ij ↦ a ij D , e ↦ x D induce a surjective R R R
ψ : C ~ → C . \psi:\widetilde{C}\to C. ψ : C → C . The natural map M → C ~ M\to\widetilde{C} M → C ψ \psi ψ M ↪ C M\hookrightarrow C M ↪ C M M M C ~ \widetilde{C} C
Let ϵ : R → Z \epsilon:R\to\mathbb{Z} ϵ : R → Z ker ϵ \ker\epsilon ker ϵ q 1 − 1 , … , q k − 1 q_1-1,\ldots,q_k-1 q 1 − 1 , … , q k − 1
r e − ϵ ( r ) e ∈ M for every r ∈ R . re-\epsilon(r)e\in M\qquad\text{for every }r\in R. r e − ϵ ( r ) e ∈ M for every r ∈ R . Consequently, every element of C ~ \widetilde{C} C
z e + m , z ∈ Z , m ∈ M . ze+m,\qquad z\in\mathbb{Z},\quad m\in M. z e + m , z ∈ Z , m ∈ M . Suppose that z e + m ∈ ker ψ ze+m\in\ker\psi z e + m ∈ ker ψ Q = G / A Q=G/A Q = G / A q z = 1 q^z=1 q z = 1 q q q z = 0 z=0 z = 0 q q q o o o o ∣ z o\mid z o ∣ z o e = c 0 oe=c_0 oe = c 0 z e + m ze+m z e + m M M M ψ \psi ψ M M M z e + m = 0 ze+m=0 z e + m = 0 ψ \psi ψ
We now establish the complexity bound. By Proposition 7.5 , an R R R A A A M = A / ( q − 1 ) A M=A/(q-1)A M = A / ( q − 1 ) A
( q − 1 ) a i j = 0 , i < j . (q-1)a_{ij}=0,\qquad i<j. ( q − 1 ) a ij = 0 , i < j . Their coefficients have polynomial-size Laurent polynomial representatives. Recall that
Q ≅ Z k / im V . Q\cong\mathbb{Z}^k/\operatorname{im}V. Q ≅ Z k / im V . where V V V q q q o o o V V V N N N V V V k ! N k k!N^k k ! N k Q Q Q V V V V V V k ! N k k!N^k k ! N k
o ≤ k ! N k . o \le k!N^k. o ≤ k ! N k . Thus, for fixed k k k o o o N N N
By Proposition 7.1 , the coordinate vectors of
c j = [ x , x j ] D , 1 ≤ j ≤ k , c_j=[x,x_j]D,\qquad1\le j\le k, c j = [ x , x j ] D , 1 ≤ j ≤ k , can be computed in polynomial time.
If q q q o o o x o ∈ A x^o\in A x o ∈ A o o o x o x^o x o x o x^o x o M M M
Finally, the presentation of C C C M M M k + 1 k+1 k + 1 k k k
Polynomial-time reduction to a module orbit membership problem
The next proposition is the main result of this section.
Proposition 7.7. Fix k ≥ 1 k\ge1 k ≥ 1 k k k G G G x , y x,y x , y x x x y y y
a finite R R R C C C ( k 2 ) + 1 \binom{k}{2}+1 ( 2 k ) + 1
two elements e , f ∈ C e,f\in C e , f ∈ C R R R
such that
x ∼ G y ⟺ f = e ⋅ q for some q ∈ Q . x\sim_G y\qquad\Longleftrightarrow\qquad f=e\cdot q\quad\text{for some }q\in Q. x ∼ G y ⟺ f = e ⋅ q for some q ∈ Q . Proof. Compute the images of x x x y y y Q Q Q x x x y y y
q = φ ( x ) = φ ( y ) , D = ( q − 1 ) G ′ , M = G ′ / D , q=\varphi(x)=\varphi(y),\qquad D=(q-1)G',\qquad M=G'/D, q = φ ( x ) = φ ( y ) , D = ( q − 1 ) G ′ , M = G ′ / D , and
C = ⟨ M , x D ⟩ ≤ G / D . C=\langle M,xD\rangle\le G/D. C = ⟨ M , x D ⟩ ≤ G / D . By Lemma 7.3 (b), C C C R R R Proposition 7.4 , conjugacy of x x x y y y x D xD x D y D yD y D R R R C C C e e e x D xD x D x − 1 y ∈ A x^{-1}y\in A x − 1 y ∈ A Proposition 7.1 computes an R R R α \alpha α x − 1 y x^{-1}y x − 1 y α ˉ \bar{\alpha} α ˉ M M M
f = e + α ˉ f=e+\bar{\alpha} f = e + α ˉ represents y D yD y D Lemma 7.3 (c).
Thus
x ∼ G y ⟺ f = e ⋅ s for some s ∈ Q . x\sim_G y\qquad\Longleftrightarrow\qquad f=e\cdot s\quad\text{for some }s\in Q. x ∼ G y ⟺ f = e ⋅ s for some s ∈ Q . Since k k k R R R G G G k k k
Reduction of orbit membership to relation-lattice membership
In this section, we reduce the module orbit problem obtained in § 7 to subgroup membership in the unit group of a commutative affine Z \mathbb{Z} Z
Recall that Q = G / G ′ Q=G/G' Q = G / G ′ x 1 , … , x k x_1,\ldots,x_k x 1 , … , x k R = Z Q R=\mathbb{Z}Q R = Z Q (5) , the ring R R R
Z [ X 1 , Y 1 , … , X k , Y k ] . \mathbb{Z}[X_1,Y_1,\ldots,X_k,Y_k]. Z [ X 1 , Y 1 , … , X k , Y k ] . Since k k k 2 k 2k 2 k G G G
We first reduce the orbit-membership problem
f = e ⋅ q for some q ∈ Q , f=e\cdot q \qquad\text{for some }q\in Q, f = e ⋅ q for some q ∈ Q , where e , f e,f e , f R R R C C C
Every element q ∈ Q q\in Q q ∈ Q R = Z Q R=\mathbb{Z}Q R = Z Q q − 1 q^{-1} q − 1 S = R / I S=R/I S = R / I Q → S Q\to S Q → S S × S^\times S ×
Q ⟶ S × , q ⟼ q + I . Q\longrightarrow S^\times,\qquad q\longmapsto q+I. Q ⟶ S × , q ⟼ q + I . Proposition 8.1. Let C C C R = Z Q R=\mathbb{Z}Q R = Z Q e , f ∈ C e,f\in C e , f ∈ C
(a) If e = 0 e=0 e = 0
f ∈ e Q ⟺ f = 0. f\in eQ\qquad\Longleftrightarrow\qquad f=0. f ∈ e Q ⟺ f = 0. (b) Suppose that e ≠ 0 e\ne0 e = 0 f ∉ e R f\notin eR f ∈ / e R f ∉ e Q f\notin eQ f ∈ / e Q h ∈ R h\in R h ∈ R f = e h f=eh f = e h
I = Ann R ( e ) , S = R / I . I=\operatorname{Ann}_{R}(e),\qquad S=R/I. I = Ann R ( e ) , S = R / I . Then
f ∈ e Q ⟺ h + I ∈ im ( Q ⟶ S × ) . (13) f\in eQ\qquad\Longleftrightarrow\qquad h+I\in\operatorname{im}\left(Q\longrightarrow S^\times\right). \tag*{(13)} f ∈ e Q ⟺ h + I ∈ im ( Q ⟶ S × ) . (13) Proof. Part (a) is immediate, since the orbit of 0 0 0 0 0 0 e Q ⊆ e R eQ\subseteq eR e Q ⊆ e R f ∉ e R f\notin eR f ∈ / e R f ∉ e Q f\notin eQ f ∈ / e Q f = e h f=eh f = e h h ∈ R h\in R h ∈ R q ∈ Q q\in Q q ∈ Q
f = e q ⟺ e ( h − q ) = 0 ⟺ h + I = q + I . f=eq\qquad\Longleftrightarrow\qquad e(h-q)=0\qquad\Longleftrightarrow\qquad h+I=q+I. f = e q ⟺ e ( h − q ) = 0 ⟺ h + I = q + I . This proves (13) . □
Corollary 8.2. Fix k ≥ 1 k\ge1 k ≥ 1
a k k k Q Q Q (4) ;
a finite R R R C C C R = Z Q R=\mathbb{Z}Q R = Z Q
two elements e , f ∈ C e,f\in C e , f ∈ C R R R
performs the following computations:
(a) decides whether f ∈ e R f\in eR f ∈ e R h ∈ R h\in R h ∈ R f = e h f=eh f = e h
(b) computes generators of I = Ann R ( e ) I=\operatorname{Ann}_{R}(e) I = Ann R ( e )
:::`
(c) constructs a quotient-ring presentation of S = R / I S = R/I S = R / I
(d) if h h h h + I h + I h + I S S S
Proof. The test f ∈ e R f \in eR f ∈ e R e R eR e R C C C Corollary 2.3 (c). If f ∈ e R f \in eR f ∈ e R Corollary 2.3 (c) also computes h ∈ R h \in R h ∈ R
Generators g 1 , … , g ℓ g_1,\ldots,g_\ell g 1 , … , g ℓ I = Ann R ( e ) I = \operatorname{Ann}_R(e) I = Ann R ( e ) Corollary 2.3 (d). Using (5) , compute polynomial representatives g ~ i \widetilde{g}_i g i g i g_i g i Z [ X 1 , Y 1 , … , X k , Y k ] \mathbb{Z}[X_1,Y_1,\ldots,X_k,Y_k] Z [ X 1 , Y 1 , … , X k , Y k ]
S ≅ Z [ X 1 , Y 1 , … , X k , Y k ] ⟨ X i Y i − 1 ( 1 ≤ i ≤ k ) , mono ( r j ) − 1 ( 1 ≤ j ≤ m ) , g ~ 1 , … , g ~ ℓ ⟩ (14) S \cong\frac{\mathbb{Z}[X_1,Y_1,\ldots,X_k,Y_k]}{\langle X_iY_i - 1\ (1 \leq i \leq k),\ \operatorname{mono}(r_j) - 1\ (1 \leq j \leq m),\ \widetilde{g}_1,\ldots,\widetilde{g}_\ell\rangle} \tag*{(14)} S ≅ ⟨ X i Y i − 1 ( 1 ≤ i ≤ k ) , mono ( r j ) − 1 ( 1 ≤ j ≤ m ) , g 1 , … , g ℓ ⟩ Z [ X 1 , Y 1 , … , X k , Y k ] (14) This presentation of S = R / I S = R/I S = R / I Corollary 2.4 decides whether h + I h + I h + I S S S
Proposition 8.3 (Reduction to affine membership). Fix k ≥ 1 k \geq1 k ≥ 1
a k k k G G G Q = G / G ′ Q = G/G' Q = G / G ′ R = Z Q R = \mathbb{Z}Q R = Z Q
a finite R R R C C C
two elements e , f ∈ C e, f \in C e , f ∈ C R R R
either decides whether f ∈ e Q f \in eQ f ∈ e Q
a presentation (14) of a commutative affine Z \mathbb{Z} Z S S S
units h , u 1 , … , u k ∈ S × h, u_1,\ldots,u_k \in S^\times h , u 1 , … , u k ∈ S ×
such that
f ∈ e Q ⟺ h ∈ ⟨ u 1 , … , u k ⟩ . f \in eQ \quad\Longleftrightarrow\quad h \in\langle u_1,\ldots,u_k\rangle. f ∈ e Q ⟺ h ∈ ⟨ u 1 , … , u k ⟩ . All constructed presentations and polynomial representatives have polynomial size.
Proof. First decide whether e = 0 e = 0 e = 0 Corollary 2.3 (c). If e = 0 e = 0 e = 0 e Q = { 0 } eQ = \{0\} e Q = { 0 } f f f e Q eQ e Q f = 0 f = 0 f = 0
Suppose that e ≠ 0 e \ne0 e = 0 Corollary 8.2 , we can decide whether f ∈ e R f \in eR f ∈ e R f ∉ e R f \notin eR f ∈ / e R f ∉ e Q f \notin eQ f ∈ / e Q h 0 ∈ R h_0 \in R h 0 ∈ R f = e h 0 f = eh_0 f = e h 0 I = Ann R ( e ) I = \operatorname{Ann}_R(e) I = Ann R ( e ) S = R / I S = R/I S = R / I (14) .
By Corollary 2.4 , we can decide whether h 0 + I h_0 + I h 0 + I S S S h 0 + I h_0 + I h 0 + I Proposition 8.1 implies f ∉ e Q f \notin eQ f ∈ / e Q h = h 0 + I h = h_0 + I h = h 0 + I S S S u i = x i + I ∈ S × u_i = x_i + I \in S^\times u i = x i + I ∈ S × x 1 , … , x k x_1,\ldots,x_k x 1 , … , x k Q Q Q (14) of S S S u i u_i u i X i X_i X i X i Y i = 1 X_iY_i = 1 X i Y i = 1 S S S Y i Y_i Y i
By Proposition 8.1 ,
f ∈ e Q ⟺ h ∈ im ( Q → S × ) . f \in eQ \quad\Longleftrightarrow\quad h \in\operatorname{im}(Q \to S^\times). f ∈ e Q ⟺ h ∈ im ( Q → S × ) . Since Q Q Q x 1 , … , x k x_1,\ldots,x_k x 1 , … , x k S × S^\times S × ⟨ u 1 , … , u k ⟩ \langle u_1,\ldots,u_k\rangle ⟨ u 1 , … , u k ⟩
f = e ⋅ q for some q ∈ Q ⟺ h ∈ ⟨ u 1 , … , u k ⟩ . f = e \cdot q\ \text{ for some } q \in Q \quad\Longleftrightarrow\quad h \in\langle u_1,\ldots,u_k\rangle. f = e ⋅ q for some q ∈ Q ⟺ h ∈ ⟨ u 1 , … , u k ⟩ . All preliminary tests and constructions take deterministic polynomial time in the combined input size, with degree depending only on k k k □ \square □
Proof of Theorem 1.4
Fix k ≥ 1 k \ge1 k ≥ 1 k k k x , y x,y x , y
A = G ′ , Q = G / A , R = Z Q , A = G', \qquad Q = G/A, \qquad R = \mathbb{Z}Q, A = G ′ , Q = G / A , R = Z Q , and
N = m + ∑ i = 1 m ∣ r i ∣ , L = N + ∣ x ∣ + ∣ y ∣ . N = m + \sum_{i=1}^{m} |r_i|, \qquad L = N + |x| + |y|. N = m + i = 1 ∑ m ∣ r i ∣ , L = N + ∣ x ∣ + ∣ y ∣. By Proposition 7.5, an R R R A A A L L L k k k x x x y y y R R R C C C e , f ∈ C e,f \in C e , f ∈ C R R R
x ∼ G y ⟺ f = e ⋅ q for some q ∈ Q . x \sim_G y \quad\Longleftrightarrow\quad f = e \cdot q \quad\text{for some } q \in Q. x ∼ G y ⟺ f = e ⋅ q for some q ∈ Q . The presentation of C C C e , f e,f e , f L L L
By Proposition 8.3 and Corollary 8.2, we can either decide whether f ∈ e Q f \in eQ f ∈ e Q Z \mathbb{Z} Z S S S h , u 1 , … , u k ∈ S × h,u_1,\ldots,u_k \in S^\times h , u 1 , … , u k ∈ S ×
f ∈ e Q ⟺ h ∈ ⟨ u 1 , … , u k ⟩ . f \in eQ \quad\Longleftrightarrow\quad h \in\langle u_1,\ldots,u_k\rangle. f ∈ e Q ⟺ h ∈ ⟨ u 1 , … , u k ⟩ . The algebra S S S 2 k 2k 2 k L L L
Since k k k 2 k 2k 2 k k k k G G G
h ∈ ⟨ u 1 , … , u k ⟩ h \in\langle u_1,\ldots,u_k\rangle h ∈ ⟨ u 1 , … , u k ⟩ in bounded-error quantum polynomial time in L L L
Combining the deterministic polynomial-time reductions with this quantum membership algorithm gives a bounded-error quantum polynomial-time algorithm for deciding whether x x x y y y G G G k k k □ \square □
Department of Mathematical Sciences, Stevens Institute of Technology, Hoboken NJ 07030
Email address: amiasnik,aushakov@stevens.edu
