The weak rank principle: lower bounds and applications
File(s)
Preprint version
Author(s)
Garlik, Michal
Gryaznov, Svyatoslav
Ren, Hanlin
Tzameret, Iddo
Type
Preprint
Abstract
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.
Date Issued
2026-03-23
Copyright Statement
© 2026 The Author(s).
Publication Status
Accepted