Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

minimal degree of a solution of a system of linear equations over polynomials

33 views
Skip to first unread message

Leon Meier

unread,
Oct 20, 2016, 8:48:55 AM10/20/16
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.
0 new messages