The Weak Rank Principle: Lower Bounds and Applications

Given two symbolic matrices X and Y of dimensions m × n and n × m, respectively, the rank principle states that when m = n+1 and A is a scalar matrix of rank n+1, the equation XY = A is unsatisfiable. When m is arbitrarily larger than n and A has rank exceeding n, we obtain the weak rank principle. We study this principle as an algebraic generalisation of the weak pigeonhole principle (WPHP), asserting that m pigeons cannot be injected into n holes, extending its counting argument to an algebraic setting. As a strengthening of WPHP, it admits proof complexity lower bounds in settings where none are known for WPHP, yet we show that these still yield applications analogous to those of WPHP. In particular, using new generalised types of random restrictions, which may be interesting by themselves, this allows us to resolve a number of open problems in proof complexity, including the construction of proof complexity generators for Polynomial Calculus Resolution over the two-element field (PCRF2), new generators for Sherali–Adams (SA), and hardness results for circuit lower bound statements against PCRF2, as detailed below. Generators for PCRF2. We prove exponential size lower bounds for several encodings—both algebraic and CNF—of the weak rank principle in PCR over F2, where no such bounds are known for the WPHP in the regime with arbitrarily many pigeons. In particular, we obtain 2Ω(n) size lower bounds for both algebraic and standard CNF encodings, including the bamboo-tree encoding, which is the most useful and corresponds to a circuit encoding, as considered by Alekhnovich, Ben-Sasson, Razborov, and Wigderson (SIAM J. Comput., 2004) and Razborov (Ann. Math., 2015). Our bounds hold for every matrix A in XY = A, implying that the rank principle forms a proof complexity generator with nearly quadratic stretch. Using a standard iteration technique we amplify the stretch to 2nΩ(1), meaning we obtain a function generator. This resolves an open problem posed by Alekhnovich et al. (SIAM J. Comput., 2004) and Razborov (Ann. Math., 2015) concerning the construction of proof complexity generators with good stretch for PCRF2. Generators for SA. Since in SA even the strong pigeonhole principle is easy, we develop a new size lower-bound technique showing that the weak rank principle, encoded as a bamboo-tree CNF, serves as a proof complexity generator for SA. Our method introduces a new relaxed notion of degree and a new corresponding pseudoexpectation tailored specifically to the rank principle (and incompatible with the pigeonhole principle). Circuit lower bound formulas. We show that PCRF2 does not admit short proofs of lower-bound statements against Boolean circuits, nor against weak models of algebraic circuits such as non-commutative algebraic branching programs. This settles an open problem raised by Razborov (Ann. Math., 2015) concerning the provability of such lower bounds in PCRF2. Rank principle as an axiom. Finally, we demonstrate the centrality of the weak rank principle by showing that it is necessary for proving NC2 circuit lower bounds and sufficient for proving AC0[p] lower bounds.