Giovanni Gallo.

A solution to Kronecker's problem online

. (page 1 of 3)
Online LibraryGiovanni GalloA solution to Kronecker's problem → online text (page 1 of 3)
Font size
QR-code for this ebook

Robotics Research
Ifechnical Report


A Solution to Kronecker's Problem

Giovanni Gallo and Bhubaneswar Mishra

Technical Report No. 600

Robotics Report No. 262

March, 1992


VD ^

Pi C
fH C O

CouS.2§ .

a, o -H e

, o - 3 '-I

U O tH X2

l-H o o

C5 •-* to l-i

Mew York University

ititute of Mathematical Sciences

lomputer Science Division

Mercer Street New York, N.Y 1 00 1 2

A Solution to Kronecker's Problem

Giovanni Gallo and Bhubaneswar Mishra

Technical Report No. 600

Robotics Report No. 262

March, 1992

New York University

Dept. of Computer Science

Courant Institute of Mathematical Sciences

251 Mercer Street

New York, New York 10012

Work on this paper has been supported by NSF grant #CCR-90-02819, ONR grant
#N00014-89-J3042 and NYU Dean's Dissertation Fellowship

A Solution to
Kronecker's Problem

Giovanni Gallo
Bhubaneswar Mishra

Courant Institute, New York University

Section 1 Introduction

1. Introduction

"Kronecker believed God made the natural numbers and all the rest was man's work. We
only know of this opinion by hearsay evidence^ , however, and his paper Uber den Zahlbegriff
indicates to me that he thought God made a bit more: Buchstabenrechnung , or calculation with
letters^. In modern terms, Kronecker seems to envisage a cosmic computer which computes
not just with natural numbers, but with polynomials with natural number coefficients (in any
number of indeterminates). That's the God-given hardware. The man-made software then
creates negative numbers, fractions, algebraic irrationals, and goes on from there. Kronecker
believed that such a computer, in the hand of an able enough programmer, was adequate for all
the purposes of higher mathematics"^."

The preceding notion of constructive mathematics, as postulated by Kronecker, can be ex-
panded further and leads to some very interesting algorithmic problems. While it is quite
apparent that Kronecker regarded these algorithmic questions as at the heart of his formulation
of mathematics"*, it is unclear whether Kronecker had been able to resolve these questions in a
satisfactory manner. Edwards, in his essay on Kronecker's views^, has the following to say: "I
find no such algorithm in his works. My best guesses as to the explanation of this paradox is
that he had an algorithm which he had not yet reduced to a form ready to publish, or, perhaps,
that he had an algorithm in many cases but had not yet found one in the general case. Or, as
is entirely possible, it lies somewhere in his voluminous collected works waiting to be found."

The present notes make a fresh attempt at resolving the algorithmic questions raised by
Kronecker, while remaining faithful to the notion of constructivity espoused by Kronecker. Fur-
thermore, we attempt to stay close to the approaches and concepts that were known and available
to Kronecker. In order to avoid confusion, however, we shall use modern algebraic terminology.

To understand Kronecker's notion of constructivity, we need a detailed look at the latent
algorithmic questions: According to Kronecker, the semi-ring N[a;i, X2, . . ., a;„]^ is God-given —
-at least, a finite but significantly large fraction of it is God-given. The man-made cilgorithms
can then carry out all computations using the elements of N[a;i, x^, . . ., Xn], i.e., using only the
natural numbers and letters. Thus, even though we think of infinite sets, N, Z, Q, R and C, and
computations involving the elements of these sets, we must treat all calculations as occurring

"Supported by NSF Grant #CCR-90-02819 and ONR Grant #N00014-89-J3042, and NYU Dean's Dissertation

Authors' Address: Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street,
New York, NY-10012.

'H. Weber. Leopold Kronecker, Jahresber. D.M.-V., 2:19, (1892).

^Leopld Kronecker's Werke, (von K. Hensel), 3: Leipzig, Druck und Verlag von B.G. Teubner, (1895).
Harold M. Edwards. Kronecker's Views on the Foundations o{ Mathematics, "Proceedings of a Conference
held at Vassar College in June 1988," (D. Rowe and J. McCleary, eds.), Academic Press, (1990).

* Werke.

^Kronecker's Views on the Foundations of Mathematics.
Here, N denotes the set of natural numbers: {0, 1, 2, . . .} and N[ii , Z2, .... Xn] denot> ~ i Ik set of multivariate
polynomials with coefficients from N and in variables i], X2, ..., x„. Both N and N[j i. t2, . . ., in] are semi-
rings — rings except that subtraction may not always be possible.

A Solution to Kronecker's Problem

with a finite subset of N and finitely many letters xi, X2, . . ., a:„— as if, the computations over
Z, Q, R, etc. get compiled into the low-level programs involving N[a;i, X2, . . ., x^] and then

A concept basic to the Kronecker's programme is the idea of equivalence of two elements,
A and A' of N[a;i, X2, . . ., a;„] modulo a finite collection {Mi,M2,...,M„} C N[ii,X2, . . .,a;„].

Definition 1.1 Given .4, A', Mi, M2, . . ., M^ G N[a;i,X2, . . ., a;„], we say that >1 ~ yl' mod (Mi,
M2, . . ., Mu) if for some i,, V'l, ^"2, ■ ■ ■, i^u & N[a;i, X2, . . ., a;„],

A + ^,Mi = A' + J2^i^i- n

t=l i=l

If we apply the above definition to the special case of N[a:] and Mi = 1 + a; we see that any
polynomial in N[x] is equivcilent to one of the form a + bx {a, b £ N), since

x^ + 1(1 + 1) = l + x(l + x) and
x^ ~ 1 mod (1 + x).

Furthermore, it is easily seen that the following are equivalent:

a + bx ~ c + dxmod(l + x)

a + d + b{l + x) ~ c + 6 + (f(l + x) mod (1 -l-x)

a + d ~ c + 6mod(l + x)

a + d = c -\- b.

Thus, the semi-ring of equivalence classes N[x]/(1 + x) is isomorphic to the ring of integers Z.
Thus, after a preprocessing which amounts to equivalence modulo 1 + x we can feel free to use any
finite collection of integers as well as the natural numbers. Thus as we perform computations
in Z, we only need to remember that "—6" is really "6x" and after each operation, we do a
straightforward normalization to bring the representation into the form "a + 6x." Thus each
ring operation over Z corresponds to some constant number of (perhaps, five) operations in N.
For all practical purposes, God could have got us started with Z!!

In a similar way, by considering N[x, t/i, . . ., yn]/(l + x, oi + bixyi, . . ., Cn + b^xyn), we can
create any finite collection of rational numbers'^ as well. In general then, by using an arbitrary
set of modulii we can perform arithmetic in any algebraic number field or even algebraic function
field. In particular, the field of rational functions on an algebraic curve can be handled in this

^Quoting Edwards: "Our impulse is to go on to construct the field of rational numbers, but Kronecker does not,
and, in fact, one cannot. One can throw in another indeterminate t [in addition to e] and another relation 1 + 10e<
(that is, two indeterminates e, t and two relations 1 + e and 1 + 10e X2 > • ■ ■ > a;„. Let the
ordering on the variables induce the lexicographic ordering on the power products. Thus

-ai -012 . . . a„ ^ 01 02 . . . 0n

if the first non-zero entry of the n-tuple

(ai, a2, ..., a„) -(/?!, /32, ..., /3„)

is positive. Note that the lexicographic ordering is a well-ordering"'''.

Now consider an ideal M C Z[ii, X2, . . ., x„] generated by a finite set M = {Mi, A/2,
. . ., M„} C Z[ii, X2, . . ., x„]. Let A e Zfxi, 12, • • •, a:„] be a multivariate polynomial with
integer coefficients, whose terms are ordered according to the lexicographic ordering, with the
biggest term occurring first. Following the usual terminology, we will denote the leading power
product (or head term), leading coefficient (or head coefficient) and leading monomial (or head
monomial) of A by Hterm(i4), Hcoef(yl) and Hmono(^), respectively. Thus,

Hmono(^) = Hcoef(yl) • Hterm(A), where Hcoef(^) e Z.

der Universitat, Heidelberg, Germany, (1987).

^°It is possible to carry out the subsequent arguments mutatis mutandis with other term or admissible orderings.
However, in order to keep our exposition simple, we have chosen to confine our discussions to the lexicograpluc

Section 2 Our Approach

We also write, A = }lmoao(A) + Tail(>l).

2.1 Head Reduction and £-Bases

Definition 2.2 (Head Reduction by M,) If Hinono(Af,) divides Hmono(/l) and


Hmono(i4) „.,,,, ^ „ ... .^
^ '^-Tail(M,) + Tail(A),


then we say that A/,- reduces A to A' and we denote this by the expression A — '-* A'. D
Note that if A-^A' then

We should also note that

Hterni(yl) > Hterm(«.M,), and Hterm(4) > Hterm(/l').

lex lex

We also write A — >■ A' if A — '■* A' for some M, € M. Finally, we write A — > A' if


and A' cannot be reduced any further by M. Note that the A' obtained by the above process
depends on the choice of the M,'s at each step of the reduction. It is thus possible that A ^ A',

A ^ A" and A' 7^ A".

Following simple observations are now in order:

1. The length of the sequence of reductions is necessarily finite, since the lexicographic or-
dering on the head monomials is a well-ordering.

2. We call an irreducible A' obtained from >1 by a sequence of reductions, as above, a normal
form of A with respect to M, and is not necessarily unique. We denote the set of normal
forms of A by

NFm(^) = {A':A-^^'}^0.

3. It is also evident that A — > A' implies that A - A' £ M, and

A = 0iMi + OiAh + ■■■ + O^M, + A',
where Hterm(A) > Hterm(^,A/,), for all i, and Hterm(A) > Hterm(A').

lex le«

A Solution to Kronecker's Problem

4. In particular, A^O (i.e. G NFm(^)) implies that A e M.

Definition 2.3 (Property (E)) A set of generators M = {Mi, M2, ■ ■ ., Mu} of the ideal M
has property {E) if

AeM O A^O.
In this case, we say that M is an E -basis of the ideal A1. D

Note that the property (E) is equivalent to the following seemingly stronger condition:

AeM ^ NFm(A) = {0}.

If, in fact, our claim were not true then there would he an A £ M\ {0}, and a choice of reduction
sequence such that A — >■ A' / 0. But a,s A' = A - (A - A') G M, A', itself would be reducible
by some M, G M.

Thus the property (E) provides an effective procedure to solve ideal membership problem.
Assume that the set of generators {Mi, . . ., M^} satisfies the property {E); reduce A with respect

to some choice of reduction sequence: A — > A', if A' = then AeM; otherwise, A ^ M.

Property {E) is equivalent to property (^1) which says that for every A ^ in M, there is
an Mi such that Hmono(M,) divides Hmono(>l). It is trivial to see that {E) implies (£^1); to see
the converse, it suffices to observe that {E\) implies that every non-zero A £ M. is reducible.

2.2 Head Monomial Ideal, G-Basis and the Property (SYZ)

Before we present an algorithm to compute an £-basis of an ideal in Z[a;i, X2, . . ., Xn\., we relate
it to some of the well known concepts, introduced in the context of the computation of a Grobner
bases. We begin with a few definitions:

Definition 2.4 (Head Monomial Ideal) Given a subset 5 C Z[ii, X2, . . ., Xn\ we call the
ideal generated by all the head monomials of elements in S the head monomial ideal of S and
denote it Head(5). D

Note that 5 is not required to be a finite set. The idea of a Grobner basis is expressed
these terms by what we shall call property (G).


Definition 2.5 (Property (G)) A set of generators M = {Mi, M2, . . ., M^} of the ideal M

1 3

Online LibraryGiovanni GalloA solution to Kronecker's problem → online text (page 1 of 3)