### Leon Meier

unread,Oct 20, 2016, 8:48:55 AM10/20/16You do not have permission to delete messages in this group

Sign in to report message

Either email addresses are anonymous for this group or you need the view member email addresses permission to view the original message

to

Let Q be the set of rational numbers.

Let polynomial coefficients

f_{i,j} \in Q[x_1,...,x_n] (1\le i\le t, 1\le j\le s)

and

b_i \in Q[x_1,...,x_n] (1\le i\le t)

be given such that the equation system

f_{11}z_1 + ... + f_{1s}z_s = b_1

...

f_{t1}z_1 + ... + f_{ts}z_s = b_t

in variables z_j (1\le j\le s) has a solution over

Q[x_1,...,x_n].

Let q be the maximal degree of f_{i,j}

(1\le i\le t, 1\le j\le s).

Let B be the maximal degree of b_i (1\le i\le t).

What can we say about the minimal degree of such a solution? That is,

what is the possibly small upper small bound for

\min \{\max \{\deg z_j | 1\le j\le s\} | (z_j)_{j=1}^s is a solution of

the above system\}

as a function of s, n, q, and B?

Modern references, especially to step-by-step, Bourbaki-like proofs are

welcome. In other terms, I'm looking for a polished, undergrad-level

version of the proof from the appendix of E. W. Mayr, A. R. Meyer, "The

complexity of the word problem for commutative semigroups and

polynomial ideals", Academic Press, Inc., 1982.