Finite Field Restricted Isometry, Fourier Barriers, and Structural Limits of Linearly Robust PCP Systems

This paper analyzes the algebraic feasibility of linearly robust probabilistically checkable proof systems by studying the Finite Field Restricted Isometry Property (FF-RIP). Building on prior work identifying robust PCPs as the key missing ingredient for unconditional proof-complexity lower bounds, it develops a unified framework combining harmonic analysis, algebraic geometry, and random matrix methods. The paper proves that strong FF-RIP is equivalent to the existence of large Salem-type sets over finite fields and establishes sharp unconditional lower bounds showing that known constructions are essentially optimal. Dynamical and random-walk approaches are shown to fail due to structural metastability. These results demonstrate that the algebraic component of robust PCP constructions faces deep and intrinsic pseudorandomness barriers, rather than merely technical difficulties.