2024/04/25 by Dingding Dong, Anqi Li, Dong, Dingding +3
Computer Science · #Combinatorics (math.CO) #FOS: Mathematics #Matrix Theory and Algorithms #Number Theory (math.NT)
paper · pdf · doi:10.48550/arxiv.2404.17005
openalex publication_date 2024/04/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A system of linear equations L is common over \mathbbFp if, as n→∞, any 2-coloring of \mathbbFpn gives asymptotically at least as many monochromatic solutions to L as a random 2-coloring. The notion of common linear systems is analogous to that of common graphs, i.e., graphs whose monochromatic density in 2-edge-coloring of cliques is asymptotically minimized by the random coloring. Saad and Wolf initiated a systematic study on identifying common linear systems, built upon the earlier work of Cameron-Cilleruelo-Serra. When L is a single equation, Fox-Pham-Zhao gave a complete characterization of common linear equations. When L consists of two equations, Kamčev-Liebenau-Morrison showed that irredundant 2× 4 linear systems are always uncommon. In this work, (1) we determine commonness of all 2× 5 linear systems up to a small number of cases, and (2) we show that all 2× k linear systems with k even and girth (minimum number of nonzero coefficients of a nonzero equation spanned by the system) k-1 are uncommon, answering a question of Kamčev-Liebenau-Morrison.