The framework of algebraically natural proofs was independently introduced in the works of Forbes, Shpilka and Volk (2018), and Grochow, Kumar, Saks and Saraf (2017), to study the efficacy of commonly used techniques for proving lower bounds in algebraic complexity. We use the known connections between algebraic hardness and pseudorandomness to shed some more light on the question relating to this framework, as follows.

- The subclass of VP that contains polynomial families with bounded coefficients, has efficient equations. Over finite fields, this result holds without any restriction on coefficients. Further, both these results also extend to the class VNP as is.
- Over fields of characteristic zero, VNP does not have any efficient equations, if the Permanent is exponentially hard for algebraic circuits.
This gives the only known barrier to "natural" lower bound techniques (that follows from believable hardness assumptions), and also shows that the restriction on coefficients in the first category of results about VNP is necessary.

The first set of results follows essentially by algebraizing the well-known method of generating hardness from non-trivial hitting sets (e.g. Heintz and Schnorr 1980). The conditional hardness of equations for VNP uses the fact that pseudorandomness against a class can be extracted from a polynomial that is (sufficiently) hard for that class (Kabanets and Impagliazzo, 2004).

The work "If VNP is hard, then so are equations for it" has been combined with the previous version of this work (CKRST 2020). Further, this version generalizes the main results in the earlier version (CKRST 2020), and also includes more detailed definitions of algebraic natural proofs and other related concepts.

For every constant c > 0, we show that there is a family {P_{N,c}} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, that satisfies the following properties:
* For every family {f_n} of polynomials in VP, where f_n is an n variate polynomial of degree at most n^c with bounded integer coefficients and for N = \binom{n^c + n}{n}, P_{N,c} \emph{vanishes} on the coefficient vector of f_n.
* There exists a family {h_n} of polynomials where h_n is an n variate polynomial of degree at most n^c with bounded integer coefficients such that for N = \binom{n^c + n}{n}, P_{N,c} \emph{does not vanish} on the coefficient vector of h_n.

In other words, there are efficiently computable equations for polynomials in VP that have small integer coefficients.
In fact, we also prove an analogous statement for the seemingly larger class VNP. Thus, in this setting of polynomials with small integer coefficients, this provides evidence \emph{against} a natural proof like barrier for proving algebraic circuit lower bounds, a framework for which was proposed in the works of Forbes, Shpilka and Volk (2018), and Grochow, Kumar, Saks and Saraf (2017).

Our proofs are elementary and rely on the existence of (non-explicit) hitting sets for VP (and VNP) to show that there are efficiently constructible, low degree equations for these classes. Our proofs also extend to finite fields of small size.

Incorporating some comments on the previous version.
* We now use the phrase 'equations for a class' instead of 'defining equations'.
* Main theorem for VP now uses the result of Heintz and Schnorr (1980).

For every constant c > 0, we show that there is a family {P_{N,c}} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, and that satisfies the following properties:
* For every family {f_n} of polynomials in VP, where f_n is an n variate polynomial of degree at most n^c with bounded integer coefficients and for N = \binom{n^c + n}{n}, P_{N,c} -vanishes- on the coefficient vector of f_n.
* There exists a family {h_n} of polynomials where h_n is an n variate polynomial of degree at most n^c with bounded integer coefficients such that for N = \binom{n^c + n}{n}, P_{N,c} -does not vanish- on the coefficient vector of h_n.

In other words, there are efficiently computable defining equations for polynomials in VP that have small integer coefficients.
In fact, we also prove an analogous statement for the seemingly larger class VNP. Thus, in this setting of polynomials with small integer coefficients, this provides evidence -against- a natural proof like barrier for proving algebraic circuit lower bounds, a framework for which was proposed in the works of Forbes, Shpilka and Volk (2018), and Grochow, Kumar, Saks and Saraf (2017).

Our proofs are elementary and rely on the existence of (non-explicit) hitting sets for VP (and VNP) to show that there are efficiently constructible, low degree defining equations for these classes, and also extend to finite fields of small size.