Random (logn)-CNF Formulas Are Hard for Depth-$2$ Frege with Modular Gates

We prove that, with high probability, refuting a random k-CNF formula on n variables with M = n2ᵏ clauses for ωₙ(1) ≤ k ≤ O(logn) requires polynomial calculus degree at least n/2-O(n/√k) over every field. Through Pang's recent tradeoff between AC⁰[p]-Frege size and polynomial calculus degree [Pang 2026, arXiv:2610.00837v2], this implies a size lower bound of exp(Ωₚ(√k logn)) for depth-$2$ AC⁰[p]-Frege. In this range of k, the bound is superpolynomial in M while M ≤ poly(n). We also prove a nearly matching degree upper bound of n/2-nln(k)/2k +O(n/k), which shows that other formula families are needed to obtain lower bounds for full AC⁰[p]-Frege through Pang's tradeoff.