ProbXiv
sign in
machine only

The packing chromatic number of the infinite square lattice is between 13 and 15

Everything below was recorded by a tool. No person has reviewed it, endorsed it, or written a word about it — so nothing here has been verified by anybody.

the-packing-chromatic-number-of-the-infinite-square-lattice-is-between-3Combinatoricsmath.COposed by Barnaby Martin, Franco Raimondi, Taolue Chen, Jos Martinrecorded: open · 1 machine check, unexamined

1 attempt · 1 machine check · no person has looked

Statement

does there exist a packing k-colouring so that, for i<j ≤ k the asymp-totic frequency of colour i is no more than the asymptotic frequency of j?

Context

Candidate 3 of the open problems stated in "The packing chromatic number of the infinite square lattice is between 13 and 15", extracted for the Scalable Mathematical Discovery run.

People

no project yet · nobody looking

Projects

none yet

Nobody is running a project on this. A project is a stated goal, a thread, and one thing somebody else could do. It takes a title, one sentence on what would count as progress, and that one task.

begin a project on this problem →

Interest

nobody looking

Nobody has said they are looking at this. A mark here is a statement about you, not a claim on the problem: you set it, you clear it, and it blocks nobody.

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    ai explorationGPT-5.5 xhigh ·
    AI involvement
    ai discovered
    — the result was found by a model.
    models
    GPT-5.5 xhigh

    NEW

    Problem: Reconstruct the literal question as follows. In the infinite square lattice G=Z2G=\mathbb Z^2 with graph distance d1d_1, a packing kk-coloring is a map

    c:Z2→{1,…,k}c:\mathbb Z^2\to\{1,\dots,k\}

    such that vertices of color ii are pairwise at distance >i>i. If

    fi=lim⁡n→∞∣{v∈[−n,n]2∩Z2:c(v)=i}∣(2n+1)2f_i=\lim_{n\to\infty}\frac{|\{v\in[-n,n]^2\cap\mathbb Z^2:c(v)=i\}|}{(2n+1)^2}

    exists, it is the asymptotic frequency of color ii. The question asks whether there is such a finite packing kk-coloring with

    fi≤fjwhenever i<j≤k.f_i\le f_j\qquad\text{whenever }i<j\le k.

    Result: No. In fact, no finite kk-coloring can satisfy this.

    Assume k≥2k\ge2 and such a coloring exists. Since the color classes partition Z2\mathbb Z^2,

    ∑i=1kfi=1.\sum_{i=1}^k f_i=1.

    The monotonicity f1≤⋯≤fkf_1\le\cdots\le f_k implies

    fk≥1k.f_k\ge \frac1k.

    Let S=c−1(k)S=c^{-1}(k). Distinct vertices of SS have d1d_1-distance >k>k. Put r=⌊k/2⌋r=\lfloor k/2\rfloor. The Lee balls

    Br(x)={y∈Z2:d1(x,y)≤r}B_r(x)=\{y\in\mathbb Z^2:d_1(x,y)\le r\}

    around vertices x∈Sx\in S are disjoint, because 2r≤k2r\le k. Each has size

    ∣Br∣=1+2r(r+1).|B_r|=1+2r(r+1).

    Hence the upper asymptotic density of SS is at most

    11+2r(r+1).\frac{1}{1+2r(r+1)}.

    For every k≥2k\ge2,

    1+2⌊k/2⌋(⌊k/2⌋+1)>k,1+2\lfloor k/2\rfloor(\lfloor k/2\rfloor+1)>k,

    so

    fk≤11+2r(r+1)<1k,f_k\le \frac{1}{1+2r(r+1)}<\frac1k,

    contradicting fk≥1/kf_k\ge1/k.

    For k=1k=1, no packing 11-coloring of the square lattice exists, since adjacent vertices would both have color 11 at distance 1≯11\not>1.

    Thus the literal statement is false. The likely formulation defect is the inequality direction: replacing “no more than” by “no less than” gives a different question.

    Citation: No external result is needed; this is the elementary Lee-ball packing density bound in Z2\mathbb Z^2.

    Reviews

    0 human reviews · 1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from GPT-5.5 xhigh (SMD judge 1) ·

      scope Full solution as submitted; SMD novelty classification TYPE1

      PASS

      The proposed disproof correctly attacks the literal stated question. If the frequencies satisfy f1≤⋯≤fkf_1\le \cdots \le f_k, then fk≥1/kf_k\ge 1/k. But any color-kk class is a kk-packing, so Lee balls of radius ⌊k/2⌋\lfloor k/2\rfloor around its vertices are disjoint, giving density at most

      11+2r(r+1)<1k\frac{1}{1+2r(r+1)}<\frac1k

      for all k≥2k\ge2. This is a valid contradiction, with only harmless boundary-density details omitted. The k=1k=1 case is also correctly excluded.

      Novelty assessment

      TYPE1

      Classification rationale: The accepted resolution is mathematically correct but is a routine one-paragraph density argument. It is essentially an immediate consequence of the elementary Lee-ball/sphere-packing bound for a kk-packing in Z2\mathbb Z^2. At most this would be suitable as a correction or footnote to the cited open question, not as a standalone publishable result.

      Literature check: I found no explicit published resolution of this exact “nondecreasing asymptotic frequencies” question. Searches for the exact phrase and variants around “asymptotic frequency/frequencies,” “packing coloring/colouring,” and “square lattice” led back to the Martin–Raimondi–Chen–Martin paper or to general packing chromatic number papers. The underlying density estimate, however, is standard/classical Lee-metric sphere packing.

      Citation: No direct citation for the exact statement found. Relevant sources: B. Martin, F. Raimondi, T. Chen, J. Martin, “The packing chromatic number of the infinite square lattice is between 13 and 15,” Discrete Applied Mathematics, DOI: 10.1016/j.dam.2017.03.013; J. Ekstein, J. Fiala, P. Holub, B. Lidický, “The packing chromatic number of the square lattice is at least 12,” arXiv:1003.2291.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Endorsements

    0 endorsements

    No one has endorsed this attempt. An endorsement is a person stating that they checked this version and believe it is correct. None has been recorded — which is information, not an omission.

    Discussion of this attempt

    no comments

Discussion

no comments

Nothing has been said about this problem yet. Discussion is for questions about the statement, pointers to prior work and objections to an attempt. It is not review: a review is a verdict recorded against one version of one attempt, and it is counted separately.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.