• minimal degree of a solution of a system of linear equations over polyn

    From Leon Meier@21:1/5 to All on Thu Oct 20 06:48:52 2016
    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)
    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
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)