Four plane unit vectors generate a 3-colorable graph

Basic Information

• Paper ID: 2511.10813
• Title: Four plane unit vectors generate a 3-colorable graph
• Authors: Katherine Eng, Timothy Harris, Mike Krebs, Mason Meeks, Claudia Maria Schmidt
• Classification: math.CO (Combinatorics)
• Submission Date: November 13, 2025 to arXiv
• Paper Link: https://arxiv.org/abs/2511.10813

Abstract

This paper proves that for any four plane unit vectors $v_1, v_2, v_3, v_4$, the Cayley graph generated by $\{\pm v_1, \pm v_2, \pm v_3, \pm v_4\}$ is always 3-colorable. Furthermore, the authors prove this is a special case of a more general result: they determine the chromatic number of any abelian Cayley graph generated by four elements and their negatives, provided the rank of the relation group among these elements does not exceed 2.

Research Background and Motivation

1. Core Problem

This paper studies a variant of the classical plane chromatic number problem (Hadwiger-Nelson problem). The original problem asks: how many colors are needed to color each point in the plane $\mathbb{R}^2$ such that any two points at unit distance have different colors? Currently, it is known that $\chi(\mathbb{R}^2) \in \{5, 6, 7\}$.

2. Problem Significance

• Theoretical Importance: The plane chromatic number problem is a classical problem in combinatorial geometry, closely related to graph theory, geometry, and topology
• Practical Applications: Unit distance graphs have applications in wireless network frequency allocation, crystal structure analysis, and other fields
• Mathematical Depth: The problem involves intersections of Cayley graph theory, algebraic group theory, and graph coloring theory

3. Limitations of Existing Methods

• The complete plane chromatic number problem is extremely difficult and remains unsolved
• Research on chromatic numbers of finite unit distance graphs lacks systematic methodology
• There is no general theory for Cayley graph chromatic numbers with specific numbers of generators

4. Research Motivation

The authors propose a new research perspective: define $\chi_{\max}(n)$ as the maximum chromatic number of all Cayley graphs generated by $n$ plane unit vectors $\{\pm v_1, \ldots, \pm v_n\}$. This problem has more structure and is amenable to systematic study.

Core Contributions

1. Main Result (Corollary 1.1): Proves that $\chi_{\max}(1) = \chi_{\max}(2) = 2$ and $\chi_{\max}(3) = \chi_{\max}(4) = 3$
2. General Theorem (Theorem 1.2): Completely determines the chromatic number of standardized abelian Cayley graphs (SACG) with $4 \times 2$ Heuberger matrices, providing necessary and sufficient conditions for chromatic number 4
3. Theoretical Framework: Establishes systematic connections from plane unit vector problems to abelian Cayley graph chromatic numbers
4. Methodological Contribution: Extends previous results on small Heuberger matrices ($1 \times r$, $m \times 1$, $2 \times 2$, $3 \times 2$) to the $4 \times 2$ case
5. Technical Tools: Develops matrix normal forms including modified Hermite Normal Form and pre-modified Hermite Normal Form, along with associated analysis tools

Detailed Methods

Task Definition

Input:

• Four plane unit vectors $v_1, v_2, v_3, v_4 \in \mathbb{R}^2$, $\|v_i\| = 1$
• Or more generally: a $4 \times 2$ integer matrix $M$ (Heuberger matrix)

Output:

• The chromatic number $\chi(X)$ of Cayley graph $\text{Cay}(G, S)$, where $S = \{\pm v_1, \pm v_2, \pm v_3, \pm v_4\}$ and $G$ is the subgroup of $\mathbb{R}^2$ generated by $S$

Constraints:

• The graph has no loops
• The graph is nonbipartite
• The matrix has no zero rows

Core Theoretical Framework

1. Cayley Graphs and Heuberger Matrices

For an abelian group $G$ and symmetric generating set $S = \{\pm x_1, \ldots, \pm x_m\}$:

• Relations: Integer vectors $(a_1, \ldots, a_m)^t$ satisfying $a_1x_1 + \cdots + a_mx_m = 0$
• Relation Group: $H \subseteq \mathbb{Z}^m$ is the subgroup formed by all relations
• Heuberger Matrix: An $m \times r$ integer matrix $M$ whose columns generate $H$

2. Standardized Abelian Cayley Graphs (SACG)

Given an $m \times r$ integer matrix $M$:

• Let $H$ be the subgroup of $\mathbb{Z}^m$ generated by the columns of $M$
• Let $G = \mathbb{Z}^m / H$, $S = \{H \pm e_1, \ldots, H \pm e_m\}$
• Denote $M^{\text{SACG}} = \text{Cay}(G, S)$

Key Property: Every connected finite-degree abelian Cayley graph is isomorphic to some SACG

Main Theorem (Theorem 1.2)

Let $M$ be a $4 \times 2$ integer matrix and $X = M^{\text{SACG}}$. If $X$ is nonbipartite, has no loops, and $M$ has no zero rows, then:

$\chi(X) = 4 \Leftrightarrow \exists \text{ signed permutation matrix } P \text{ and unimodular matrix } U \text{ such that } PMU = \begin{pmatrix} 1 & a \\ 1 & b \\ 1 & c \\ 0 & 1 \end{pmatrix}$

where $a, b, c \in \mathbb{Z}$ and $3 \mid a + b + c$. Otherwise $\chi(X) = 3$.

Proof Strategy

Stage 1: From Unit Vectors to Matrices (Section 3)

For four plane unit vectors, construct Heuberger matrix $M$ and analyze by column count $r$:

Case $r = 1$: By Tomato Cage Theorem, $\chi(X) \leq 3$

Case $r = 2$: This is the core case

• If there is a zero row: reducible to the 3-vector case, using $\chi_{\max}(2) = 2$
• If no zero row and nonbipartite: apply Theorem 1.2
• If the special form of Theorem 1.2 holds, prove that necessarily $v_1 + v_2 + v_3 = 0$ (equilateral triangle configuration)
• Then $v_4$ must be a unit vector in the lattice, i.e., $v_4 \in \{\pm v_1, \pm v_2, \pm v_3\}$
• Use triangular lattice coloring formula: $\alpha v_1 + \beta v_2 + \gamma v_3 \mapsto \alpha + \beta + \gamma \pmod{3}$

Case $r = 3, 4$: Graph is finite or reducible

Stage 2: Proof of Theorem 1.2 (Sections 4-6)

Tool 1: Modified Hermite Normal Form

For $3 \times 2$ matrices, define standard form satisfying:

• $y_{11} > 0$, $y_{12} = 0$
• $y_{11} \equiv 0 \pmod{3}$ or $y_{22} \equiv y_{32} \pmod{3}$
• Other technical conditions

Theorem 4.6 provides complete chromatic number classification under this standard form (6 exceptional cases with chromatic number 4)

Tool 2: Pre-modified Hermite Normal Form

For $4 \times 2$ matrices, define three "buckets":

• Case 1: Merge rows 1, 2 to obtain modified Hermite Normal Form
• Case 2: Merge rows 2, 3 to obtain modified Hermite Normal Form
• Case 3: Merge rows 3, 4 to obtain modified Hermite Normal Form

Tool 3: Key Lemmas

• 4×2 three-divisible row lemma (Lemma 5.1): If some row is divisible by 3, then $\chi(Y) \leq 3$
• Tri-Triangle Lemma (Lemma 4.9): Chromatic number determination for specific matrix forms
• Graph homomorphisms: Row merging operations produce homomorphisms $M^{\text{SACG}} \xrightarrow{\circledcirc} M'^{\text{SACG}}$

Proof Flow:

1. Reduce the $4 \times 2$ matrix to one of three Cases
2. For each Case, merge two rows to obtain $3 \times 2$ matrix $M_Z$
3. If $\chi(Y) \geq 4$, then by homomorphism properties $\chi(Z) \geq 4$
4. Apply Theorem 4.6; $M_Z$ must be one of 6 exceptional cases
5. Through case analysis, prove only the special form in Theorem 1.2 can yield $\chi(Y) = 4$

Technical Innovations

1. Matrix Normal Form Theory: Creatively transforms graph coloring problems into matrix normal form problems
2. Hierarchical Reduction Strategy: $4 \times 2 \to 3 \times 2 \to$ known results, using graph homomorphisms to preserve chromatic number upper bounds
3. Modular Arithmetic Constraints: Cleverly exploits modulo 3 congruence relations to eliminate many cases
4. Binary Quadratic Form Theory: Uses quadratic form reduction theory to solve Diophantine equations in complex subcases
5. Geometric Intuition: Translates algebraic conditions into geometric configurations (e.g., equilateral triangle lattice points)

Experimental Setup

Note: This is a pure theoretical mathematics paper with no traditional experiments. All results are mathematical proofs.

Verification Methods

• Theoretical Proofs: Through rigorous mathematical reasoning
• Case Verification: Exhaustive case analysis for specific matrix forms
• Citation of Prior Work: Relies on three master's theses 4, 6, 7 to complete proofs of certain subcases

Proof Coverage

• Case 1 (merge rows 1, 2): Completely proved by 4
• Case 2 (merge rows 2, 3): Partially proved by 7, this paper supplements remaining cases
• Case 3 (merge rows 3, 4): Partially proved by 6, this paper supplements remaining cases

Detailed Case Analysis (Section 6)

The authors demonstrate the complete proof of Case 3 + exceptional case (v):

Matrix form: $M_Y = \begin{pmatrix} 1 & 0 \\ 0 & -1 \\ y_{31} & y_{32} \\ y_{41} & 2-y_{32} \end{pmatrix} \xrightarrow{\circledcirc} M_Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \\ \pm 3k & 2 \end{pmatrix}$

Proof steps include:

1. Modulo 3 analysis to determine variable congruence classes
2. Construct new homomorphism to matrix $M_U$
3. Reduce $M_U$ to modified Hermite Normal Form
4. Identify subcases with chromatic number 4
5. Construct second homomorphism $M_V$ for cross-verification
6. Solve resulting Diophantine equation systems

Experimental Results

Main Results

Theorem Verification: Corollary 1.1 completely establishes:

• $\chi_{\max}(1) = 2$: Doubly infinite path graph
• $\chi_{\max}(2) = 2$: Infinite grid or path graph
• $\chi_{\max}(3) = 3$: Triangular lattice (lower bound) + derivation from Theorem 1.2 (upper bound)
• $\chi_{\max}(4) = 3$: Same as above

Key Observations:

• $\chi_{\max}(n)$ for $n \geq 5$ remains unknown
• $\chi_{\max}(7) \geq 4$: Moser's spindle provides example of 4-chromatic graph
• By de Bruijn-Erdős theorem (assuming axiom of choice), for sufficiently large $n$, $\chi(\mathbb{R}^2) = \chi_{\max}(n)$

Theoretical Findings

1. Critical Dimension Phenomenon: From 3 to 4 vectors, chromatic number does not increase, showing a saturation effect
2. Algebraic-Geometric Correspondence: The necessary and sufficient condition for chromatic number 4 corresponds to specific algebraic form ($3 \mid a+b+c$), geometrically corresponding to triangular lattice configuration
3. Role of Rank: The constraint that relation group rank $\leq 2$ is critical; higher rank cases show significantly increased complexity
4. Symmetry Preservation: Signed permutations and unimodular transformations preserve graph chromatic number (isomorphism class)

Case Analysis

Example: Equilateral Triangle Configuration

When $v_1 = (1, 0)$, $v_2 = (-1/2, \sqrt{3}/2)$, $v_3 = (-1/2, -\sqrt{3}/2)$:

• Satisfies $v_1 + v_2 + v_3 = 0$
• Generates triangular lattice $G$
• Coloring scheme: $\alpha v_1 + \beta v_2 + \gamma v_3 \mapsto \alpha + \beta + \gamma \pmod{3}$
• This provides tight lower bound for $\chi_{\max}(3) = 3$

Example: Moser's Spindle

• Graph defined by 7 unit vectors
• Known to be 4-chromatic
• Proves $\chi_{\max}(7) \geq 4$

Related Work

1. Plane Chromatic Number Problem

• Hadwiger-Nelson Problem (1950s): $\chi(\mathbb{R}^2) \in \{5, 6, 7\}$
• de Bruijn-Erdős Theorem 3: Connects finite and infinite graph chromatic numbers
• Soifer's Monograph 9: Provides rich historical background

2. Cayley Graph Chromatic Numbers

• Cervantes & Krebs 1, 2: Established matrix methods, handled $1 \times r$, $m \times 1$, $2 \times 2$, $3 \times 2$ cases
• Tomato Cage Theorem 1: Chromatic number formula for single-column matrices

3. Master's Thesis Series

• Harris 4: Complete proof of Case 1
• Ortiz 7: Partial proof of Case 2
• Meeks 6: Partial proof of Case 3

4. Algebraic Number Theory Tools

• Jarvis 5: Binary quadratic form reduction theory, used for solving Diophantine equations

Advantages of This Work

• Systematicity: First complete answer for $n \leq 4$
• Generality: Addresses not only unit vector problems but provides general theory for abelian Cayley graphs
• Methodology: Establishes extensible matrix method framework

Conclusions and Discussion

Main Conclusions

1. Core Theorem: Any Cayley graph generated by four plane unit vectors is 3-colorable
2. Exact Characterization: Completely determines chromatic numbers of SACGs with $4 \times 2$ Heuberger matrices, providing necessary and sufficient conditions for chromatic number 4
3. Computational Results: $\chi_{\max}(n) = 2$ for $n \in \{1, 2\}$; $\chi_{\max}(n) = 3$ for $n \in \{3, 4\}$
4. Method Contribution: Matrix normal form method provides tools for studying higher-dimensional cases

Limitations

1. Unresolved Cases: $\chi_{\max}(n)$ for $n \geq 5$ remains unknown
2. Proof Complexity: Proof involves extensive case analysis, partially dependent on detailed work in three master's theses
3. Computational Difficulty: Construction from unit vectors to Heuberger matrix may not be unique, requiring selection of appropriate representation
4. Axiom of Choice Dependence: Connection to plane chromatic number requires assuming the axiom of choice (AC)
5. Missing Direct Proof: Authors acknowledge possible more direct proofs of Corollary 1.1

Future Directions

1. Extension to More Vectors:
   • Determine $\chi_{\max}(5)$, $\chi_{\max}(6)$, $\chi_{\max}(7)$, etc.
   • Develop techniques for handling larger $m \times r$ matrices
2. Proof Simplification:
   • Seek more direct geometric proofs
   • Reduce number of case analyses
3. Algorithmic Implementation:
   • Develop algorithms to automatically determine chromatic number of given matrices
   • Computer-assisted verification
4. Generalization to Higher Dimensions:
   • Unit distance graph problems in $\mathbb{R}^d$
   • Non-abelian Cayley graphs
5. Application Exploration:
   • Frequency allocation in wireless networks
   • Symmetry problems in crystallography

In-Depth Evaluation

Strengths

1. Theoretical Depth

• Completeness: First complete solution for $n \leq 4$ cases
• Generality: Bridges concrete geometric problems to abstract algebraic structures
• Precision: Provides necessary and sufficient conditions for chromatic number 4, not merely bounds

2. Method Innovation

• Matrix Method: Transforms graph coloring into matrix normal form problem, providing systematic analysis tools
• Hierarchical Reduction: Uses graph homomorphisms and row merging to reduce complex problems to known results
• Integrated Techniques: Combines tools from graph theory, linear algebra, and number theory (binary quadratic forms)

3. Clear Structure

• Modular Proofs: Decomposes proofs into independent lemmas and theorems
• Detailed Case Studies: Section 6 provides complete case analysis sample
• Literature Integration: Effectively integrates results from three master's theses

4. Geometric Intuition

• Successfully translates algebraic conditions into geometric configurations (equilateral triangles)
• Provides concrete coloring scheme constructions

Weaknesses

1. Proof Complexity

• Case Explosion: Requires handling numerous subcases, lengthy proofs
• External Dependencies: Complete proof scattered across multiple references
• High Technical Barrier: Requires reader familiarity with multiple mathematical branches

2. Computational Efficiency

• No efficient algorithm provided for computing chromatic number of given vector sets
• Matrix reduction process may involve substantial computation

3. Readability

• Numerous symbols and definitions; difficult for beginners to follow
• Key proofs (Section 6) show only one case; other cases left to reader

4. Application Limitations

• Primarily theoretical results; practical application scenarios unclear
• Unresolved cases for $n \geq 5$ limit practical utility

5. Missing Directness

• Authors acknowledge possible more direct proof paths
• Transition from plane geometry to abstract algebra may obscure problem essence

Impact

1. Field Contributions

• Classical Problem Progress: Substantial progress on Hadwiger-Nelson problem variant
• Methodological Contribution: Matrix method potentially applicable to other Cayley graph problems
• Theoretical Completeness: Fills theoretical gap for small generator counts

2. Practical Value

• Theoretical Tools: Provides foundation for studying more complex cases
• Potential Applications: Possible applications in network design, coding theory
• Educational Value: Demonstrates cross-disciplinary research methodology

3. Reproducibility

• Theoretical Proofs: Mathematical proofs are in principle fully verifiable
• Detailed Documentation: Referenced master's theses provide detailed proofs
• Open Problems: Clearly identifies unresolved directions

4. Follow-up Research

• Establishes foundation for research on $n = 5, 6, 7, \ldots$
• May inspire research on non-abelian cases
• Matrix method potentially generalizable to other graph classes

Applicable Scenarios

1. Theoretical Research

• Coloring problems in combinatorial geometry
• Cayley graph theory
• Algebraic graph theory

2. Computational Mathematics

• Graph coloring algorithm design
• Implementation in symbolic computation systems

3. Application Fields

• Wireless Communications: Frequency allocation problems (unit distance constraints)
• Crystallography: Symmetry and coloring problems
• Coding Theory: Distance graph coding

4. Education

• Advanced topics in graduate courses
• Case study demonstrating cross-disciplinary approaches

References

Key References

1 Cervantes & Krebs (2023): Chromatic numbers of Cayley graphs of abelian groups: A matrix method

• Establishes foundational matrix method framework

2 Cervantes & Krebs (2023): Chromatic numbers of Cayley graphs of abelian groups: Cases of small dimension and rank

• Handles $3 \times 2$ and smaller matrix cases

3 de Bruijn & Erdős (1951): A colour problem for infinite graphs

• Classical theorem connecting finite and infinite graph chromatic numbers

4 Harris (2024): Master's Thesis

• Complete proof of Case 1

5 Jarvis (2014): Algebraic number theory

• Provides binary quadratic form theory tools

6 Meeks (2025): Master's Thesis

• Partial proof of Case 3

7 Ortiz (2025): Master's Thesis

• Partial proof of Case 2

9 Soifer (2024): The new mathematical coloring book

• Comprehensive reference on plane chromatic number problem

Summary

This paper makes important progress on coloring theory of plane unit distance graphs, completely solving the four-vector case through innovative matrix methods. Although proof techniques are complex, the established theoretical framework provides solid foundation for future research. The main achievement is transforming geometric problems into algebraic problems and providing precise chromatic number determination criteria. This is an excellent mathematics paper with strong technical content and deep theory, making important contributions to both combinatorial geometry and algebraic graph theory.