Sharp Rank Transitions and Supercritical Kernel Structure in Sparse Cayley Incidence Matrices

Abstract

Fix k ≥ 3 and let p → ∞ through odd primes. We sample m = ⌊Cp⌋ distinct rows uniformly from the additive Cayley host on kp part-labeled vertices and form their binary incidence matrix. Although local peeling gives a scalar prediction, the additive constraint leaves global row dependencies to be controlled. We determine the limiting normalized rank curve. The exact full-row-rank threshold agrees, after density rescaling, with the classical random k-XORSAT satisfiability threshold; full row rank holds with probability tending to one uniformly on fixed strict subcritical margins. At each fixed supercritical density, the terminal 2-core right kernel is, with high probability, exactly the direct sum of the part-constant gauge and flippable-cycle spaces. The cycle count has an explicit Poisson limit, governing core right nullity minus k − 1 and full left nullity minus the realized core excess and k − 1. The proofs combine rank interpolation, certificate estimates, and physical-overlap counting.