[#P100007] Chromatic number of the integer distance graph on cubes

Problem. Let \(D = \{k^3 : k \ge 1\}\) and let \(G(\mathbb{Z}, D)\) be the graph on the integers in which \(x\) and \(y\) are adjacent exactly when \(|x - y| \in D\). Is \(\chi(G(\mathbb{Z}, D)) = 3\)?

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

1Problem setup

Remark 1. The distance graph G(Z, D) has the integers as vertices, with x adjacent to y exactly when |x - y| lies in D.

Definition 1. Here D is the set of positive perfect cubes 1, 8, 27, 64, and so on.

2What counts as a solution

Exhibit a proper 3-colouring of the integers avoiding all cube differences, together with a proof that 2 colours do not suffice; or prove that more than 3 colours are required.

1Status

Saved packet · date unavailable

What counts as a solution

Saved solution (The cube-distance graph has countably infinite chromatic number). Every finite coloring of the integers contains a same-colored pair at a positive cube distance, so the graph has chromatic number \(\aleph_0\).^[1]

Resolution argument

Let \(D=\{n^3:n\geq1\}\). Bergelson and Leibman's polynomial van der Waerden theorem, applied to the zero polynomial and \(p(n)=n^3\), gives two same-colored integers \(x\) and \(x+n^3\) in every finite coloring of \(\mathbb Z\). Those vertices are adjacent in \(G(\mathbb Z,D)\), so no finite coloring is proper. The graph is countable, which supplies the upper bound \(\aleph_0\).

This refutes the candidate value \(3\). Guerreiro, Ruzsa, and Silva describe the same fact by saying that the positive values of \(p\) form a chromatically intersective set, or a ladder. The square-distance and triangular-distance cases follow from the same polynomial theorem.

1Packet records

Show recorded summaries

Record	Kind	Assessment
Every finite coloring of the integers contains a same-colored pair at a positive cube distance, so the graph has chromatic number \(\aleph_0\).	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Proposition 1 Every finite coloring of the integers contains a same-colored pair at a positive cube distance, so the graph has chromatic number \(\aleph_0\).^[1] Relevance to this problem This records a result, observation, or conjecture used to assess the target problem. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state established Scope the integer distance graph whose allowed distances are all positive cubes Sources Reference 1 Argument Let \(D=\{n^3:n\geq1\}\). Bergelson and Leibman's polynomial van der Waerden theorem, applied to the zero polynomial and \(p(n)=n^3\), gives two same-colored integers \(x\) and \(x+n^3\) in every finite coloring of \(\mathbb Z\). Those vertices are adjacent in \(G(\mathbb Z,D)\), so no finite coloring is proper. The graph is countable, which supplies the upper bound \(\aleph_0\). This refutes the candidate value \(3\). Guerreiro, Ruzsa, and Silva describe the same fact by saying that the positive values of \(p\) form a chromatically intersective set, or a ladder. The square-distance and triangular-distance cases follow from the same polynomial theorem. Open full record →
Positive values of an integer-valued polynomial with zero constant term form a ladder, the distance-set condition equivalent to infinite chromatic number.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Proposition 2 Positive values of an integer-valued polynomial with zero constant term form a ladder, the distance-set condition equivalent to infinite chromatic number.^[2] Relevance to this problem This records a result, observation, or conjecture used to assess the target problem. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state established Scope positive values of every integer-valued polynomial p with p(0)=0 Sources Reference 2 Argument Guerreiro, Ruzsa, and Silva call a set \(D\) a ladder when every finite coloring of the integers contains arbitrarily long monochromatic \(D\)-paths. Their Corollary 4 includes the positive values of every integer-valued polynomial \(p\) satisfying \(p(0)=0\). Section 5 relates the ladder and chromatic-intersectivity language to the integer distance graph \(G_D\). Taking \(p(n)=n^3\) places the database entry inside this general result. Related: Proposition 1 Open full record →
Every periodic coloring fails immediately because a period \(q\) is also crossed by the allowed distance \(q^3\).	Trace	Evidence: Incomplete method The route does not supply a complete proof in its recorded form.
attempt · Route 1 Every periodic coloring fails immediately because a period \(q\) is also crossed by the allowed distance \(q^3\).^[2] Relevance to this problem This records a line of attack on the target problem, including what it establishes and where it stops. Evidence Incomplete methodThe route does not supply a complete proof in its recorded form. Record state failed as complete proof Scope all periodic colorings of the integers with any finite number of colors Sources Reference 2 What happened Suppose a coloring has period \(q\). Then \(x\) and \(x+q^3\) receive the same color because \(q\) divides \(q^3\), while their difference is an allowed cube. This rules out every periodic finite coloring before any search begins. The original entry suggested a periodic coloring as the route to a three-color upper bound. The polynomial van der Waerden theorem rules out every finite coloring, including aperiodic ones. Finite-window colorings therefore cannot extend to the full graph. Related: Artifact 1 Open full record →
The induced graphs on widths 20, 30, 40, and 60 each have chromatic number 3.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 The induced graphs on widths 20, 30, 40, and 60 each have chromatic number 3. Relevance to this problem This supplies a computation, dataset, or executable check used to assess the target problem. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope induced cube-distance graphs on integer intervals of width at most 60 File research/candidate-screening/multi.py Details An exact backtracking search computes chromatic number 3 on the induced graphs with vertex sets \(\{0,\ldots,w-1\}\) for \(w=20,30,40,60\). The lower bound already appears on nine vertices: \(0,1,2,\ldots,8,0\) is an odd cycle whose edge lengths are 1 and 8. A checked 3-coloring at width 60 is encoded by the string 010101012010101012012121201202020101201010101201010120121212. These finite values are compatible with an infinite chromatic number. Polynomial recurrence forces larger finite subgraphs to require arbitrarily many colors. Related: Proposition 1 Open full record →
No records match these filters.

Notes and companion material

Screened together with squares, triangular numbers, primes, palindromes and powers of two. Palindromic distances force at least 10 colours because 1 through 9 are all palindromes, so that variant is degenerate. Square and triangular distances produced chromatic numbers that grew with the window, which is a different and probably harder question.

Original intake status. Status not established. Chromatic numbers of integer distance graphs are a studied topic and this particular case may well be settled in the literature; no search was performed. Treat the value 3 as a computational conjecture on finite windows, not as a claim about the infinite graph.

No literature search was carried out. The prime-distance case is known to have chromatic number 4, which suggests this family has been worked over and that the cube case may be known.
Finite windows give only lower bounds for the infinite graph. A complete answer needs a periodic colouring for the upper bound.

Recorded example 1. Colouring n by n mod 3 fails, since 64 is a cube and 64 is congruent to 1 modulo 3.

Computational notes

Exact chromatic number of the induced subgraph on windows of width 20, 30, 40 and 60 was 3 in every case. For comparison, square distances gave 3, 4, 4, 5 and triangular distances gave 3, 3, 4, 5 on the same windows.

How the 4 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemChromatic number of the integer distance graph on cubes

All 3 recorded relations between these records and the problem

2See also

Permutations whose index sums are always perfect squaresgraph theory
Permutations whose index sums are always triangular numbersgraph theory
Independence number of the cubic-residue graph on 127 pointsgraph theory

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Chromatic number of the integer distance graph on cubes.” TheoremDB. P100007. Problem statement; statement text SHA-256 a2be3e64232b8ff872375a3dac8461eb2b2321483c4cb2052e1a598f70e71254. https://theoremdb.org/statement/?ref=P100007

BibTeX

@misc{theoremdb-problem-a2be3e64232b8ff872375a3dac8461eb2b2321483c4cb2052e1a598f70e71254,
  title = {{Chromatic number of the integer distance graph on cubes}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 a2be3e64232b8ff872375a3dac8461eb2b2321483c4cb2052e1a598f70e71254},
  url = {https://theoremdb.org/statement/?ref=P100007}
}

Plain text: Built Markdown snapshot

This problem includes 4 records joined by 3 typed links, sourced from people.math.osu.edu^[1].

1Lean verification

Lean formalization needed

A solution has been submitted and awaits independent review.

Open TheoremDB Researcher

Upload a Lean project archive

Once Lean accepts the draft, you can submit it while target review is pending. Your submission request is saved and continues after approval. Private checks stay private until you choose to submit.

1References

2 entries have incomplete source metadata. Each affected row names the fields that still need editorial review.

Packet source. Bergelson and Leibman, Polynomial extensions of van der Waerden's and Szemerédi's theorems, Theorem C and Corollary 1.11. ↗website · reference source · checked 2026-07-24Source metadata incomplete: publication-style citation.Source use: citation only.Source named by the research packet.
Guerreiro, Ruzsa, and Silva, Monochromatic Paths for the Integers, Corollary 4 and section 5. ↗preprint · reference source · checked 2026-07-24Source metadata incomplete: publication-style citation, source version, relevance note.Source use: citation only.Also cited at The general obstruction follows from Corollary 4; the periodic obstruction is elementary.

Original question generated by an agent.

[#P100007] Chromatic number of the integer distance graph on cubes

1Problem setup

2What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Problem setup

2What counts as a solution

1StatusSolution submittedNot Lean-verified

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance

1Status