Learning algorithms versus automatability of Frege systems

We connect learning algorithms and algorithms automating proof search in propositional proof systems: for every sufficiently strong, well-behaved propositional proof system [Formula: see text], we prove that the following statements are equivalent, (1) Provable learning. [Formula: see text] proves efficiently that p-size circuits are learnable by subexponential-size circuits over the uniform distribution with membership queries. (2) Provable automatability. [Formula: see text] proves efficiently that [Formula: see text] is automatable by non-uniform circuits on propositional formulas expressing p-size circuit lower bounds. Here, [Formula: see text] is sufficiently strong and well-behaved if I.–III. hold: I. [Formula: see text] p-simulates Jeřábek’s system [Formula: see text] (which strengthens the Extended Frege system [Formula: see text] by a surjective weak pigeonhole principle); II. [Formula: see text] satisfies some basic properties of standard proof systems which p-simulate [Formula: see text]; III. [Formula: see text] proves efficiently for some Boolean function [Formula: see text] that [Formula: see text] is hard on average for circuits of subexponential size. For example, if III. holds for [Formula: see text], then Items 1 and 2 are equivalent for [Formula: see text]. We use the following modified notion of automatability in Item 2, the automating circuits output a [Formula: see text]-proof of a given formula (expressing a p-size circuit lower bound for a function [Formula: see text]) in non-uniform p-time in the length of a shortest [Formula: see text]-proof of a closely related but different formula (expressing an average-case subexponential-size circuit lower bound for the same function [Formula: see text]). If there is a function [Formula: see text] which is hard on average for circuits of size [Formula: see text], for each sufficiently big [Formula: see text], then there is an explicit propositional proof system [Formula: see text] satisfying properties I.-III., i.e. the equivalence of Items 1 and 2 holds for [Formula: see text].