Question: Are the given set of multivariate polynomials f_1, ..., f_k algebraically dependent? In other words, is there a non-zero polynomial g such that g(f_1, ..., f_k) = 0?
We will see that algebraic independence shares the matroid structure of linear independence. We show this connection with the help of partial derivatives of f_i (in particular, using the Jacobian matrix). From the Jacobian criteria, we can show that algebraic independence testing is in RP.
But the above Jacobian criteria is valid over fields of characteristic 0, like the complex numbers. In particular, it is not valid over finite fields. Thus the problem of algebraic independence testing over finite fields is wide open.
We will see that over finite fields, algebraic independence testing is in AM ∩ coAM.
Link to paper: https://arxiv.org/abs/1801.09275
