Disclaimer: Throughout, fix a field $K$ with $\text{char}(K) = p >0$, and we assume that all the computations related to Gröbner bases are done with a fixed elimination ordering.
I am currently working on a problem involving Gröbner basis computations and as the title explains:
I'm looking for upper bounds for both the degree and the number of polynomials in the reduced Gröbner basis of an ideal $J = \langle f_1 \dots, f_d\rangle \triangleleft K[x_1, \dots, x_m]$ in terms of the (Krull) dimension of $I$, the maximum total degree of the polynomials $f_i$ $(1\leq i \leq d)$ and $m$. Moreover, I'm also looking for the same kind of upper bounds for the radical of an ideal.
After an extensive search in various online archives and journals I barely managed to find any information related to such kind of bounds.
To give a bit of context and background, some time ago I was working in a situation where I started with an ideal $J = \langle f_1 \dots, f_d\rangle \triangleleft F[x_1, \dots, x_r, y_1, \dots, y_s]$ where $\text{char}(F)=0$ and then I needed to look at the ideal $\sqrt{H}$, where $H = J \cap F[x_1, \dots, x_r]$; one of my tasks was to bound above both the degree and the number of polynomials in the reduced Gröbner basis of $\sqrt{H}$. In particular, I looked at the case where $F = \mathbb Q$ and I was able to find various results which enabled me to obtain the answers I needed. The way I approached this was as follows:
- Using the results of Mayr & Ritscher I could bound the maximum total degree of polynomials in the reduced Gröbner basis of $J$ and after some easy observations I bounded the maximum total degree of polynomials in the reduced Gröbner basis of $H$.
- From Laplagne's algorithm, together with the results from Krick & Logar, Giusti and Dube (which state that the number of polynomials in the reduced Gröbner basis of an ideal of an ideal in $n$ variables over $\mathbb Q$, generated by $s$ polynomials of maximum degree $d$ is of order $s^{O(1)}d^{2^{O(n)}}$) and combining these with the bounds obtained in part 1 I managed to give an upper bound for the degree and the number of polynomials in the reduced Gröbner basis of $\sqrt{H}$.
Of course, these bounds were double exponential in the number of variables as it generally happens with Gröbner basis computations; my task was not to find sharp bounds, but just to give concrete bounds.
I'm working now on the same task but for the case of a field of positive characteristic, and the issue is that for this case it seems as if the theory for finding and/or sharpening bounds for these quantities is not that well developed. There are some papers discussing, for example, the computation of the radical of an ideal over a field of positive characteristic, like Matsumoto's paper and Kemper's paper, but there is no mention whatsoever about the kind of bounds I'm looking for; on the other hand Mayr & Ritscher's bounds for reduced Gröbner basis would work for an infinite filed of positive characteristic, but not over finite fields. With this in mind, my main questions about this overall situation are the following:
- Are there any concrete bounds for the degree and number of polynomials in the reduced Gröbner basis of ideals of rings over fields of positive characteristic?
- Are there any concrete bounds for the degree and number of polynomials in the reduced Gröbner basis of the radical of ideals of rings over fields of positive characteristic?
- Is it possible to give such bounds by analyzing the complexity of the used algorithms in (say) Matsumoto's paper and Kemper's paper as is done by Lagplagne in his paper?
Any idea is much appreciated.