Common systems of two equations over the binary field

• Daniel Král ^[1] ; Ander Lamaison ^[1] ; Péter Pál Pach ^[2]
  1. [1] Masaryk University

     Masaryk University

     Chequia

     
  2. [2] Budapest University of Technology and Economics

     Budapest University of Technology and Economics

     Hungría

     
• Localización: Discrete Mathematics Days 2022 / coord. por Luis Felipe Tabera Alonso , 2022, ISBN 978-84-19024-02-2, págs. 169-173
• Idioma: inglés
• Texto completo no disponible (Saber más ...)
• Resumen

  • A system of linear equations over a finite field Fq is said to be common if, among alltwo-colorings of Fnq, the uniform random coloring minimizes the number of monochromaticsolutions asymptotically. The notion of common systems of linear equations was introducedby Saad and Wolf, as an analogue to the well-studied notion of common graphs.Fox, Pham and Zhao characterized the common systems consisting of one equation. Westudy systems consisting of two equations over the binary field F2. We characterize, up to afinite number of cases, which systems with an odd number of variables are common. Ourcharacterization answers a question by Kamˇcev, Liebenau and Morrison in the affirmativeway whether there exist common systems of equations that are not translation invariant.