BRICS RS-04-6 Frandsen & Shparlinski: On Reducing a System of Equations to a Single Equation BRICS

Basic Research in Computer Science

On Reducing a System of Equations to a Single Equation

Gudmund Skovbjerg Frandsen Igor E. Shparlinski BRICS Report Series RS-04-6 ISSN 0909-0878 March 2004 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2004, Gudmund Skovbjerg Frandsen & Igor E.

Shparlinski. BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/04/6/

On Reducing a System of Equations to a Single Equation

Gudmund S. Frandsen BRICS, Department of Computer Science University of Aarhus DK-8200, Denmark

        Email: gudmund@daimi.au.dk

Igor E. Shparlinski Department of Computing Macquarie University NSW 2109, Australia

         Email: igor@ics.mq.edu.au

Abstract

For a system of polynomial equations over Q_{p} we present an efficient construction of a single polynomial of quite small degree whose zero set over Q_{p} coincides with the zero set over Q_{p} of the original system. We also show that the polynomial has some other attractive features such as low additive and straight-line complexity.

The proof is based on a link established here between the above problem and some recent number theoretic result about zeros of p-adic forms.

1 Introduction

Let us consider a system of n polynomial equations in m variables

f_{i}(x_{1}, …, x_{m}) = 0,  i = 1, …, n,  (1)

over a field IK,

f_{i}(X_{1}, …, X_{m}) ∈ IK[X_{1}, …, X_{m}], i = 1, …, n.

It is shown in [8, Lemma 13] that if IK is not algebraically closed then there exists a polynomial

f(X_{1}, …, X_{m}) ∈ IK[X_{1}, …, X_{m}]

such that the system (1) has a solution x_{1}, …, x_{m} ∈ IK if and only if the equation

f(x_{1}, …, x_{m}) = 0  (2)

has a solution x_{1}, …, x_{m} ∈ IK. Moreover if the total degree of polynomials f_{1}, …, f_{n} does not exceed d, then the total degree of the polynomial f does not exceed dn^{O(1)}. Thus we have a polynomial blow-up of the degree. This result has been applied to studying the complexity of some linear algebra problems [8].

Here we show that over Q_{p} the same can be achieved with polylogarithmic blow-up of the degree. Moreover, the same is true for the blowup of the additive and the straight-line complexity of the polynomials f_{1}, …, f_{n}. In fact, for our construction

Z_{IK}(f_{1}, …, f_{m}) = Z_{IK}(f)

where Z_{IK}(f_{1}, …, f_{m}) and Z_{IK}(f) are the zero sets (over IK) of the system of equations (1) and the equation (2).

The construction is based on a link established here between the above reduction problem and some recent results on p-adic forms of low degree and exponentially many variables having only trivial p-adic solutions [2, 3, 5, 6, 18].

This type of argument seems to be new in this area and we hope that this technique may be useful for a number of other applications in complexity theory and symbolic computation.

2 Notation and Auxiliary Results

For our applications we adapt a result from [6], although other results from [2, 3, 5, 18] can be used as well.

Lemma 1 (i) Let p be an odd prime. Given n polynomials

f_{0}, …, f_{n−1} ∈ Q_{p}[X_{1}, …, X_{m}]

and an integer t > log_{p} n, we define t polynomials

F_{j} = ∑_{i=0}^{n−1} f_{i}^{(p−1)(2t−j)} ∑_{k=0}^{n−1} f_{k}^{(p−1)(2t+j)} ∈ Q_{p}[X_{1}, …, X_{m}],

where j = 0, …, t − 1. Then

Z_{Q_{p}}(f_{0}, …, f_{n−1}) = Z_{Q_{p}}(F_{0}, …, F_{t−1}).

(ii) Let p = 2. Given n polynomials

f_{0}, …, f_{n−1} ∈ Q_{2}[X_{1}, …, X_{m}]

and an integer t > log_{8} n, we define t polynomials

F_{j} = ∑_{i=0}^{n−1} f_{i}^{2(4t−j)} ∑_{k=0}^{n−1} f_{k}^{2(4t+j)} ∈ Q_{2}[X_{1}, …, X_{m}],

where j = 0, …, t − 1. Then

Z_{Q_{2}}(f_{0}, …, f_{n−1}) = Z_{Q_{2}}(F_{0}, …, F_{t−1}).

Proof. Let be be an odd prime. Clearly

Z_{Q_{p}}(f_{0}, …, f_{n−1}) ⫅ Z_{Q_{p}}(F_{0}, …, F_{t−1}).

It is now enough to show that for t > log_{p} n the following system of homogeneous equations

∑_{i=0}^{n−1} x_{i}^{(p−1)(2t−j)} ∑_{k=0}^{n−1} x_{k}^{(p−1)(2t+j)} = 0, j = 0, …, t − 1,

does not have a nontrivial solution over Q_{p}. Indeed, let (x_{1}, …, x_{n}) be such a nontrivial solution. We can also assume that all x_{1}, …, x_{n} are nonzero p-adic integers, not all divisible by p. We remark that the above system of equations leads to t equations of the form

∑_{i=0}^{n−1} x_{i}^{(p−1)j_{ν}} = 0, ν = 1, …, t,

with some integers t < j_{1} < … < j_{t} < 3t. By Basic Odd Lemma of [6, Section 2] we see that this system does not have nonzero modulo p solutions which contradicts our assumption on x_{1}, …, x_{n}, which finishes the proof in the case p ≥ 3.

For p = 2 the proof is completely analogous except that we use Basic Even Lemma of [6, Section 2]. ⊓ ⊔

We also need a more trivial construction of higher degree:

Lemma 2 Let p be a prime. Given n polynomials

f_{0}, …, f_{n−1} ∈ Q_{p}[X_{1}, …, X_{m}]

and an integer k > log_{p} n, we define a polynomial F ∈ Q_{p}[X_{1}, …, X_{m}] by

F = ∑_{i=0}^{n−1} f_{i}^{(p−1)p^{k−1}}

Then Z_{Q_{p}}(f_{0}, …, f_{n−1}) = Z_{Q_{p}}(F).

Proof. We observe that if p |/ y then y^{(p−1)p^{k−1}} ≡ 1 (mod p^{k}), and if p | y then y^{(p−1)p^{k−1}} ≡ 0 (mod p^{k}). Hence for the polynomial

Φ(Y_{1}, …, Y_{p^{k}−1}) = ∑_{i=1}^{p^{k}−1} Y_{i}^{(p−1)p^{k−1}} ∈ Q_{p}[Y_{1}, …, Y_{p^{k}−1}]

we have

Z_{Q_{p}} (Φ) = {(0, …, 0)}

and the result follows, when using that p^{k} − 1 ≥ n. ⊓ ⊔ Now we recall several notions from algebraic complexity theory. For a polynomial f(X_{1}, …, X_{m}) ∈ IK[X_{1}, …, X_{m}] we define its ad-

ditive complexity A(f) as the least number of signs + and − which are necessary to represent f as an algebraic formula over IK (thus we do not count × and /).

We also define its straight-line complexity L(f) as the length of the shortest straight-line arithmetic program which computes the values of f at any point (x_{1}, …, x_{m}) ∈ IK^{m}. That is the length L of the shortest chain of the relations u_{i} = x_{i}, i = 1, …, m, and either u_{i} = u_{j_{i}} ∘ u_{k_{i}} or u_{i} = c_{i} where c_{i} ∈ IK is a constant, i = m + 1, …, L, with u_{L} = f(x_{1}, …, x_{m}) for all (x_{1}, …, x_{m}) ∈ IK^{m}, where ∘ stands for one of the arithmetic operations and 1 ≤ j_{i}, k_{i} ≤ i − 1.

For example, for the polynomial

f(x_{1}, x_{2}, x_{3}) = (((2x_{1} + x_{2})^{k} + 3x_{1}^{k^{2}+1}x_{3}^{k^{3}})^{2k+1} + 1)
× ((x_{1} + 3x_{2}x_{3})^{k} − 2) + 1.

we have

A(f) = 6, L(f) = O(log k).

These two notions play a central role in many parts of complexity theory [7, 10, 17, 19, 21, 22, 23, 24]. In particular, polynomials of low additive complexity admit a short encoding but exhibit quite complicated behaviour.

Also, for a polynomial f(X_{1}, …, X_{m}) ∈ IK[X_{1}, …, X_{m}] we define its sparsity S(f) as the number of non-zero coefficients in the representation of f of the form

f(X_{1}, …, X_{m}) = ∑_{i_{1},...,i_{m}} a_{i_{1}...i_{m}}X_{1}^{i_{1}} … X_{m}^{i_{m}}.

That is S(f) is the number of distinct monomials in such a representation.

Obviously A(f) ≤ S(f) but as the above example shows S(f) cannot be estimated in terms of A(f).

There is a constantly growing interest to various features of sparse polynomials over various algebraic domains, see [4, 9, 11, 12, 13, 14, 15, 16, 20, 25, 27, 28, 29] and references therein.

One can easily verify the following statement.

Lemma 3 For given n polynomials

f_{0}, …, f_{n−1} ∈ Q_{p}[X_{1}, …, X_{m}],

we put

F = ∑_{i=0}^{n−1} f_{i}^{D_{1}} ∑_{k=0}^{n−1} f_{k}^{D_{2}},

where D_{1}, D_{2} are non-negative integers with D_{1} + D_{2} = O(log n). Let

d = max_{1≤i≤n} deg f_{i},  a = max_{1≤i≤n} A(f_{i}),
l = max_{1≤i≤n} L(f_{i}),  s = max_{1≤i≤n} S(f_{i}).

Then

deg F = O(d log n),  A(F) = O(an),
L(F) = O(ln + n log log n),  S(F) = s^{O(log n)},

provided s ≥ 2.

In connection with the iterated use of Lemma 1 we need the following notation. Let log^{(i)} n denote i iterations of the function x ↦ ⌈log_{3}(x+1)⌉ taken on n, and let log^{∗} n denote the minimal i for which log^{(i)} n ≤ 1. Finally, we denote

λ(n) = ∏_{i=1}^{log^{∗} n} log^{(i)} n.

Throughout this paper p is assumed to be fixed; thus implicit constants in ‘O’-symbols may depend on p.

3 Main Results

Theorem 4 Let polynomials

f_{i}(X_{1}, …, X_{m}) ∈ Q_{p}[X_{1}, …, X_{m}],

where i = 1, …, n, be of total degree at most d, of additive complexity at most a, of straight-line complexity at most l and of sparsity at most s ≥ 2.

Then there exists a polynomial

G(X_{1}, …, X_{m}) ∈ Q_{p}[X_{1}, …, X_{m}]

∘ of total degree deg G = dλ(n)2^{O(log^{∗} n)};

∘ of additive complexity A(G) = anλ(n)2^{O(log^{∗} n)};

∘ of straight-line complexity L(G) = O(ln + n log n);

∘ of sparsity S(G) = s^{λ(n)2^{O(log^{∗} n)}};

and such that Z_{Q_{p}}(f_{1}, …, f_{m}) = Z_{Q_{p}}(G).

Proof. Let t be the minimal integer such that t > log_{3} n and use the construction of Lemma 1 to find polynomials F_{1}, …, F_{t} such that Z_{Q_{p}}(f_{1}, …, f_{m}) = Z_{Q_{p}}(F_{1}, …, F_{t}). While t > 1 the construction of Lemma 1 is repeated and after a total of log^{∗} n iterations the result is a single polynomial G such that Z_{Q_{p}}(f_{1}, …, f_{m}) = Z_{Q_{p}}(G).

For each application of Lemma 1, the degree of the constructed polynomial grows by a factor O(log n). When the construction is repeated log^{∗} n times the constant factor hidden in the O-notation may grow to a factor 2^{O(log^{∗} n)}. Bearing this in mind, the stated bounds on the degree and the sparsity follows from Lemma 3.

The bound on the additive complexity similarly follows from repeated applications of Lemma 3.

For the straight line complexity, one must in addition compute the intermediate results only once in order to obtain the stated bound O(ln+ n log n) ⊓ ⊔

It is an open question, whether our result is nearly optimal. Over the field of real numbers, one may encode an arbitrary number of polynomials into a single polynomial while only doubling the degree when using the form x_{1}^{2} +x_{2}^{2} +⋯+x_{n}^{2}. It is known, see [26], that any form in n variables having only trivial zeros over Q_{p} must have degree at least Ω(log log n). The construction of Theorem 4 implicitly uses such a form of degree λ(n)2^{O(log^{∗} n)}. An improved result may, however, not be based on such forms, in which case no lower bound is known.

There seems to be a trade-off between additive complexity and degree in the result of Theorem 4 in that a modified construction leads to a better additive complexity with the cost of a slightly higher degree (and sparsity):

Theorem 5 Under the same assumptions as in Theorem 4 there exists a polynomial

H(X_{1}, …, X_{m}) ∈ Q_{p}[X_{1}, …, X_{m}]

∘ of total degree deg H = O(d log^{2} n);

∘ of additive complexity A(H) = O(an log n);

∘ of straight-line complexity L(H) = O(ln + n log n);

∘ of sparsity S(H) = s^{O(log^{2} n)};

and such that Z_{Q_{p}}(f_{1}, …, f_{m}) = Z_{Q_{p}}(H).

Proof. Let integer t be the minimal such that t > log_{3} n and use the construction of Lemma 1 to find polynomials F_{1}, …, F_{t}. Apply the construction of Lemma 2 on these t polynomials (with integer k chosen minimal such that k > log_{2} t) to get the single polynomial H with the same zero set as the original n polynomials.

The complexity bounds for H are proved similarly to those for G in theorem 4. ⊓ ⊔

Finally we show how to reduce studying zero sets of p-adic polynomials of low additive complexity to studying zero sets of sparse polynomials which admit a number of algorithmic approaches [4, 9, 11, 12, 13, 14, 15, 16, 19, 25, 28, 29].

Theorem 6 For any polynomial

F (X_{1}, …, X_{m}) ∈ Q_{p}[X_{1}, …, X_{m}]

of additive complexity at most A(F) there exists a polynomial

f(X_{1}, …, X_{m+n}) ∈ Q_{p}[X_{1}, …, X_{m+n}]

of sparsity

S(f) ≤ A(F)^{λ(log n)2^{O(log^{∗} n)}}

and such that

Z_{Q_{p}}(F) = π_{m}Z_{Q_{p}}(f).

where π_{m} : Q_{p}^{m+n} → Q_{p}^{m} is the projection map along the first m coordinates.

Proof. It is easy to show by induction, see also [10, 21, 22], that the equation

F (x_{1}, …, x_{m}) = 0

can be written down as an equivalent system of n+1 ≤ A(F)+1 equations in m + n variables of the following shape

x_{i} = α_{i} ∏_{j∈J_{i}} x_{j}^{e_{ij}} + β_{i} ∏_{k∈K_{i}} x_{k}^{h_{ik}},

i = m + 1, …, m + n,

∏_{j∈J_{m+n+1}} x_{j} = 0,

where J_{i}, K_{i} ⊆ {1, …, i − 1}, α_{i}, β_{i} ∈ IK, with some integer non-negative exponents e_{ij}, h_{ik}. Applying Theorem 4 (with s = 3) and using that

3^{λ(n)} = (n + 1)^{λ(log n)} ≤ (A(F) + 1)^{λ(log n)}

we obtain the desired statement. ⊓ ⊔

We remark that an analogue of Lemma 1 is known for finite algebraic extensions of Q_{p} as well [1], thus our results can be transferred to such fields, too.

4 Acknowledgments

This work was essentially done during a visit by I. S. to the University of Aarhus, whose hospitality is gratefully acknowledged. This visit as well as the work of the first author was supported by BRICS, Basic Research in Computer Science (www.brics.dk), Centre of the Danish National Research Foundation.

References

[1] Y. Alemu, ‘On zeros of forms over local fields’, Acta Arithm., 45 (1985), 163–171.

[2] G. I. Arkhipov and A. A. Karatsuba, ‘On a problem in the theory of congruences’, Uspechi Mat. Nauk, 37 (1981), 161–162 (in Russian).

[3] G. I. Arkhipov and A. A. Karatsuba, ‘On the local representation of zero by a form’, Izv. Akad Nauk USSR, 19 (1982), 231–240 (in Russian).

[4] M. Ben-Or and M. Tiwari, ‘A deterministic algorithm for sparse multivariate polynomial interpolation’, Proc. 20th ACM Symp. on Theor. Comp. Sci., 1988, 301–309.

[5] J. Browkin, ‘On systems of congruences’, Bull. of the Polish Acad. Sci., 31 (1983), 219–226.

[6] J. Brownawell, ‘On p-adic zeros of forms’, J. Number Theory, 18 (1984), 342–349.

[7] P. Bürgisser, M. Clausen and M. A. Shokrollahi, Algebraic complexity theory, Springer-Verlag, Berlin, 1996.

[8] J. F. Buss, G. S. Frandsen and J. O. Shallit, ‘The computational complexity of some problems of linear algebra’, J. Comp. and Syst. Sci., 58 (1999), 572–596.

[9] M. Clausen, A. Dress, J. Grabmeier and M. Karpinski, ‘On zero testing and interpolation of k-sparse multivariate polynomials over finite field’, Theor. Comp. Sci., 84 (1991), 151–164.

[10] D. Grigoriev, ‘Lower bounds in the algebraic computational complexity’, Zapiski Nauchn. Semin. Leningr. Otdel. Matem. Inst. Acad. Sci. USSR, 118 (1982), 25–82 (in Russian).

[11] D. Grigoriev and M. Karpinski, ‘Algorithms for sparse rational interpolation’, Proc. Intern. Symp. on Symbolic and Algebraic Comp., 1991, 7–13.

[12] D. Grigoriev and M. Karpinski, ‘A zero-test and an interpolation algorithm for the shifted sparse polynomials’, Lect. Notes in Comp. Sci., 673 (1993), 162–169.

[13] D. Grigoriev, M. Karpinski and M. Singer, ‘Fast parallel algorithm for sparse multivariate polynomials over finite fields’, SIAM J. Comput., 19 (1990), 1059–1063.

[14] D. Grigoriev, M. Karpinski and M. Singer, ‘Computational complexity of sparse rational interpolation’, SIAM J. Comput., 23 (1994), 1–11.

[15] M. Karpinski, A. van der Poorten and I. E. Shparlinski, ‘Zero testing of p-adic and modular polynomials’, Theor. Comput. Sci., 233 (2000), 309–317.

[16] M. Karpinski and I. E. Shparlinski, ‘On some approximation problems concerning sparse polynomials over finite fields’, Theor. Comp. Sci., 157 (1996), 259–266.

[17] A. G. Khovanski, Fewnomials, Amer. Math. Soc., Providence, 1991.

[18] D. J. Lewis and H. L. Montgomery, ‘On zeros of p-adic forms’, Michigan Math. J., 30 (1983), 83–87.

[19] L. Lipshitz, ‘P -adic zeros of polynomials’, J. Reine Angew. Math., 390 (1988), 208–214.

[20] R. Lipton and N. Vishnoi, ‘Deterministic identity testing for multivariate polynomials’, Proc. 14th ACM-SIAM Symp. on Discr. Algorithms, ACM, 2003, 756–760.

[21] J.-J. Risler, ‘Khovansky’s theorem and complexity theory’, Rocky Mountain J. Math., 14 (1984), 851–853.

[22] J.-J. Risler, ‘Additive complexity of real polynomials’, SIAM J. Comp., 14 (1985), 178–183.

[23] J. M. Rojas, ‘Additive complexity and p-adic roots of polynomials’, Lect. Notes in Comp. Sci., Springer-Verlag, Berlin, 2369 (2002), 506–516.

[24] J. M. Rojas, ‘Arithmetic multivariate Descartes’ rule’, Amer. J. Math., 126 (2004) 1–30.

[25] R. M. Roth and G. M. Benedek, ‘Interpolation and approximation of sparse multivariate polynomials over GF (2)’, SIAM J. Comp. 20 (1991), 291–314.

[26] W. M. Schmidt, ‘The solubility of certain p-adic equations’, J. Number Theory, 19 (1984), 63–80.

[27] I. E. Shparlinski, ‘Sparse polynomial approximation in finite fields’, Proc. 33rd ACM Symp. on Theory of Comput., ACM, 2001, 209–215.

[28] K. Werther, ‘The complexity of sparse polynomials interpolation over finite fields’, Appl. Algebra in Engin., Commun. and Comp., 5(1994), 91–103.

[29] R. Zippel, Effective polynomial computation, Kluwer Acad. Publ., Dordrecht, 1993.

Recent BRICS Report Series Publications

RS-04-6 Gudmund Skovbjerg Frandsen and Igor E. Shparlinski. On Reducing a System of Equations to a Single Equation. March 2004. 11 pp. To appear in Schicho and Singer, editors, ACM SIGSAM International Symposium on Symbolic and Algebraic Computation, ISSAC ’04 Proceedings, 2004.

RS-04-5 Biernacki Dariusz and Danvy Olivier. From Interpreter to Logic Engine by Defunctionalization. March 2004. 20 pp. To appear in Bruynooghe, editor, International Symposium on Logic Based Program Development and Transformation, LOPSTR ’03 Proceedings, Revised Selected Papers, LNCS, 2003. This report supersedes the earlier BRICS report RS-03-25.

RS-04-4 Patricia Bouyer, Franck Cassez, Emmanuel Fleury, and Kim G. Larsen. Optimal Strategies in Priced Timed Game Automata. February 2004. 32 pp.

RS-04-3 Mads Sig Ager, Olivier Danvy, and Jan Midtgaard. A Functional Correspondence between Call-by-Need Evaluators and Lazy Abstract Machines. February 2004. 17 pp. This report supersedes the earlier BRICS report RS-03-24. Extended version of an article to appear in Information Processing Letters.

RS-04-2 Gerth Stølting Brodal, Rolf Fagerberg, Ulrich Meyer, and Norbert Zeh. Cache-Oblivious Data Structures and Algorithms for Undirected Breadth-First Search and Shortest Paths. February 2004. 19 pp.

RS-04-1 Luca Aceto, Willem Jan Fokkink, Anna Ingólfsdóttir, and Bas Luttik. Split-2 Bisimilarity has a Finite Axiomatization over CCS with Hennessy’s Merge. January 2004. 16 pp.

RS-03-53 Kyung-Goo Doh and Peter D. Mosses. Composing Programming Languages by Combining Action-Semantics Modules. December 2003. 39 pp. Appears in Science of Computer Programming, 47(1):2–36, 2003.

RS-03-52 Peter D. Mosses. Pragmatics of Modular SOS. December 2003. 22 pp. Invited paper, published in Kirchner and Ringeissen, editors, Algebraic Methodology and Software Technology: 9th International Conference, AMAST ’02 Proceedings, LNCS 2422, 2002, pages 21–40.