pith. sign in

arxiv: 2303.00557 · v4 · submitted 2023-03-01 · 🧮 math.CO · cs.DM· cs.FL· math.DS

Finding codes on infinite grids automatically

Ville Salo , Ilkka T\"orm\"a This is my paper

Pith reviewed 2026-05-24 08:58 UTC · model grok-4.3

classification 🧮 math.CO cs.DMcs.FLmath.DS
keywords identifying codeshexagonal gridminimum densityautomata theoryminimum mean cycleperiodic constructionsupper boundscoding theory
0
0 comments X

The pith

Automata theory and cycle algorithms produce a new upper bound of 53/126 for identifying code density on the infinite hexagonal grid.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper models candidate identifying codes on the hexagonal grid as automata and applies a minimum mean weight cycle algorithm to locate periodic patterns of low density that still satisfy the unique-neighborhood condition. This search yields a concrete periodic construction whose density equals 53/126, improving on the previous best upper bound of 3/7. A sympathetic reader would care because the result demonstrates that an automated optimization procedure can systematically beat hand-crafted constructions for an infinite-lattice identification task. The method therefore supplies both a tighter concrete bound and a reusable computational technique for similar density-minimization questions.

Core claim

By representing periodic code configurations with automata and invoking Karp's minimum mean weight cycle algorithm to minimize density subject to the identifying-code constraint, the work obtains a periodic identifying code on the infinite hexagonal grid whose density is exactly 53/126. This value improves the prior record upper bound of 3/7. The construction is produced automatically rather than by manual design.

What carries the argument

Automata representations of periodic grid configurations, optimized by Karp's minimum mean weight cycle algorithm to find the lowest-density pattern obeying the identifying-code neighborhood condition.

If this is right

  • The minimum density of an identifying code on the infinite hexagonal grid is at most 53/126.
  • Periodic constructions found by automata and cycle algorithms can improve known upper bounds in grid coding problems.
  • The same automated search procedure applies directly to minimum-density questions on other regular infinite grids.
  • Verification of the new code reduces to a finite local check inside the period.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Running the same procedure on larger automata state spaces or different grid graphs could produce still lower densities.
  • The technique links classical coding-theory bounds to standard graph-algorithmic optimization, opening a route to other infinite-lattice problems.
  • If the bound is close to optimal, it constrains the possible range for the true minimum density on the hexagonal grid.

Load-bearing premise

The periodic pattern produced by the algorithm remains a valid identifying code, with every vertex uniquely identified by its neighborhood, when the pattern is repeated across the entire infinite grid.

What would settle it

An explicit enumeration of all vertices inside one or two periods of the reported pattern that locates two vertices possessing identical sets of code-neighbor positions.

Figures

Figures reproduced from arXiv: 2303.00557 by Ilkka T\"orm\"a, Ville Salo.

Figure 1
Figure 1. Figure 1: Evolution of the known lower and upper bounds on the minimal density of an identifying [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A new locating-dominating code of density [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An identifying code with density 11/26 on the hexagonal grid, found using the SAT solver Gluecard [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: An identifying code with density 53/126 on the hexagonal grid found using automata theory and Karp’s algorithm [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The minimal set Fhex of forbidden patterns for identifying codes on Ehex. The circles denote non-codewords. More explicitly, first we observe that we can pick a finite set Fhex of sets, which define Xhex ⊂ {0, 1} Z 2 when for each T-translate F ′ of each F ∈ Fhex we forbid the all-zero pattern p ∈ {0} F . Such a family of sets is shown in [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗
read the original abstract

We apply automata theory and Karp's minimum mean weight cycle algorithm to minimum density problems in coding theory. Using this method, we find the new upper bound $53/126 \approx 0.4206$ for the minimum density of an identifying code on the infinite hexagonal grid, down from the previous record of $3/7 \approx 0.4286$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The paper applies automata theory and Karp's minimum mean weight cycle algorithm to minimum-density problems in coding theory. It reports a new upper bound of 53/126 ≈ 0.4206 on the minimum density of an identifying code in the infinite hexagonal grid, improving on the prior record of 3/7 ≈ 0.4286, obtained via a periodic construction found by the algorithm.

Significance. If the periodic construction is verified to be a valid identifying code, the result improves the known upper bound for identifying-code density on the hexagonal grid and demonstrates an automated algorithmic approach (automata plus Karp's algorithm) that can systematically search for low-density periodic codes on grids. The method's ability to reduce the search to a minimum-mean-cycle problem is a technical strength when the state space correctly encodes the identifying constraint.

major comments (1)
  1. [Abstract / algorithmic construction] The central claim that the output of the automata-plus-Karp procedure yields a valid identifying code of density 53/126 on the infinite grid is load-bearing, yet the manuscript provides no explicit verification (e.g., exhaustive check of neighborhood intersections for all vertex pairs within one or two periods, or a formal argument that the state representation captures distinctions across period boundaries).

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and for highlighting the need for explicit verification of the central construction. We address this point below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: The central claim that the output of the automata-plus-Karp procedure yields a valid identifying code of density 53/126 on the infinite grid is load-bearing, yet the manuscript provides no explicit verification (e.g., exhaustive check of neighborhood intersections for all vertex pairs within one or two periods, or a formal argument that the state representation captures distinctions across period boundaries).

    Authors: We agree that the manuscript would benefit from an explicit verification step or formal argument. The automata are designed so that each state encodes the local neighborhood information required to enforce the identifying-code property (every pair of vertices must be distinguished by their closed neighborhoods intersecting the code). Because the state transition graph is built over a finite window that tiles the plane, any cycle found by Karp's algorithm corresponds to a periodic labeling whose local constraints are satisfied everywhere, including across period boundaries. Nevertheless, to make this fully rigorous and address the referee's concern, we will add (i) a concise formal argument in Section 3 explaining why the chosen state representation suffices for global validity and (ii) a short computational appendix that exhaustively checks all relevant neighborhood intersections for the 53/126 construction over two periods. These additions will be included in the revised version. revision: yes

Circularity Check

0 steps flagged

No circularity; algorithmic search yields explicit construction

full rationale

The paper models identifying-code constraints via automata whose states and transitions encode the requirement that every pair of vertices has distinct closed-neighborhood intersections with the code set. Karp's minimum-mean-cycle algorithm is then run on the resulting graph to locate a cycle whose mean weight equals the density 53/126. The resulting periodic labeling is presented as an explicit witness for the upper bound; its validity follows directly from the automaton construction rather than from any self-referential definition, fitted parameter renamed as prediction, or load-bearing self-citation. The derivation is therefore self-contained and externally verifiable by inspecting the produced cycle.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no identifiable free parameters, axioms, or invented entities; the result is framed as a direct computational output.

pith-pipeline@v0.9.0 · 5578 in / 879 out tokens · 32481 ms · 2026-05-24T08:58:42.814462+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. On Iiro Honkala's contributions to identifying codes

    cs.DM 2024-02 unverdicted novelty 1.0

    The paper surveys Iiro Honkala's contributions to identifying codes across complexity, combinatorics, grids, graph parameters, structural properties, and optimal code counts.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages · cited by 1 Pith paper · 3 internal anchors

  1. [1]

    General bounds for identifying codes in some infinite reg- ular graphs

    Charon I, Honkala I, Hudry O, and Lobstein A. General bounds for identifying codes in some infinite reg- ular graphs. The electronic journal of combinatorics, 2001, 8(1):R39. doi:https://doi.org/10.37236/1583

    work page doi:10.37236/1583 2001

  2. [2]

    Identifying codes with sm all radius in some infinite regular graphs

    Charon I, Hudry O, and Lobstein A. Identifying codes with small radius in some infinite regular graphs. The electronic journal of combinatorics, 2002, 9(1):R11. doi:https://doi.org/10.37236/1628

    work page doi:10.37236/1628 2002

  3. [3]

    Bounds for codes identifying vertices in the hexagonal grid

    Cohen GD, Honkala I, Lobstein A, and Z ´emor G. Bounds for codes identifying vertices in the hexagonal grid. SIAM Journal on Discrete Mathematics, 2000, 13(4):492–504. doi:10.1137/S0895480199360990

    work page doi:10.1137/s0895480199360990 2000

  4. [4]

    A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid

    Cranston DW, and Yu G. A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid. arXiv preprint arXiv:1006.3779, 2010

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  5. [5]

    New bounds on the minimum density of an identifying code for the infinite hexagonal grid

    Cukierman A, and Yu G. New bounds on the minimum density of an identifying code for the infinite hexag- onal grid. Discrete Applied Mathematics, 2013, 161(18):2910–2924. doi:10.1016/j.dam.2013.06.002

    work page doi:10.1016/j.dam.2013.06.002 2013

  6. [6]

    Ergodic theory on compact spaces

    Denker M, Grillenberger Ch, and Sigmund K. Ergodic theory on compact spaces. Lecture Notes in Math- ematics, V ol. 527. Springer-Verlag, Berlin, 1976. ISBN: 978-3-540-07797-8, doi:10.1007/BFb0082364

    work page doi:10.1007/bfb0082364 1976

  7. [7]

    The still-Life density problem and its generalizations

    Elkies ND. The still-life density problem and its generalizations. In Voronoi’s Impact on Modern Science, Book I, volume 21 of Proceedings of the Institute of Mathematics of the National Academy of Sciences of Ukraine, pages 228–253. Institute of Mathematics of the National Academy of Sciences of Ukraine, 1998. doi:10.48550/arXiv.math/9905194

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.math/9905194 1998

  8. [8]

    Gibbs measures and phase transitions , volume 9 of De Gruyter Studies in Mathematics

    Georgii H-O. Gibbs measures and phase transitions , volume 9 of De Gruyter Studies in Mathematics . Walter de Gruyter, Berlin, New York, 2011. ISBN-10:9783110250299, 13:978-3110250299

    work page 2011

  9. [9]

    On the density of identifying codes in the square lattice

    Honkala I, and Lobstein A. On the density of identifying codes in the square lattice. Journal of Combina- torial Theory, Series B, 2002, 85(2):297–306. doi:10.1006/jctb.2001.2106

    work page doi:10.1006/jctb.2001.2106 2002

  10. [10]

    PySAT: A Python toolkit for prototyping with SAT ora- cles

    Ignatiev A, Morgado A, and Marques-Silva J. PySAT: A Python toolkit for prototyping with SAT ora- cles. In O. Beyersdorff and C. Wintersteiger, editors, Theory and Applications of Satisfiability Testing – SAT 2018, volume 10929 of Lecture Notes in Computer Science, pages 428–437. Springer, Cham, 2018. doi:10.1007/978-3-319-94144-8 26

    work page doi:10.1007/978-3-319-94144-8 2018

  11. [11]

    Fault-tolerant locating-dominating sets on the infinite king grid

    Jean D, and Seo S. Fault-tolerant locating-dominating sets on the infinite king grid. arXiv preprint arXiv:2201.09399, 2022

    work page arXiv 2022

  12. [12]

    New lower bound for 2-identifying code in the square grid

    Junnila V . New lower bound for 2-identifying code in the square grid. Discrete Applied Mathematics, 2013, 161(13):2042–2051. doi:10.1016/j.dam.2013.02.032

    work page doi:10.1016/j.dam.2013.02.032 2013

  13. [13]

    A characterization of the minimum cycle mean in a digraph

    Karp RM. A characterization of the minimum cycle mean in a digraph. Discrete Mathematics, 1978, 23(3):309–311

    work page 1978

  14. [14]

    On a new class of codes for identifying vertices in graphs

    Karpovsky GM, Chakrabarty K, and Levitin LB. On a new class of codes for identifying vertices in graphs. IEEE Transactions on Information Theory, 1998, 44(2):599–611. doi:10.1109/18.661507. V . Salo and I. T¨orm¨a / Finding Codes on Infinite Grids Automatically 349

    work page doi:10.1109/18.661507 1998

  15. [15]

    Morphisms from non-periodic Z2 subshifts I: constructing embeddings from homomorphisms

    Lightwood SJ. Morphisms from non-periodic Z2 subshifts I: constructing embeddings from homomorphisms. Ergodic Theory and Dynamical Systems , 2003, 23(2):587–609. doi:10.1017/S014338570200130X

    work page doi:10.1017/s014338570200130x 2003

  16. [16]

    An introduction to symbolic dynamics and coding

    Lind D, and Marcus B. An introduction to symbolic dynamics and coding . Cambridge University Press, Cambridge, 1995

    work page 1995

  17. [17]

    On identifying codes in lattices

    Obata K. On identifying codes in lattices. Preprint, December, 2003

    work page 2003

  18. [18]

    Optimal (r, ≤ 3)-locating–dominating codes in the infinite king grid

    Pelto M. Optimal (r, ≤ 3)-locating–dominating codes in the infinite king grid. Discrete Applied Mathe- matics, 2013, 161(16):2597–2603. doi::10.1016/j.dam.2013.04.027

    work page doi:10.1016/j.dam.2013.04.027 2013

  19. [19]

    On locating-dominating codes in the infinite king grid

    Pelto M. On locating-dominating codes in the infinite king grid. Ars Combinatoria, 2016, 124:353–363

    work page 2016

  20. [20]

    Theory of recursive functions and effective computability

    Rogers Jr H. Theory of recursive functions and effective computability . MIT press, 1987. ISBN-10: 0262680521, 13:978-0262680523

    work page 1987

  21. [21]

    Hex automaton, 2023

    Salo V , and T¨orm¨a I. Hex automaton, 2023. GitHub repository

    work page 2023

  22. [22]

    Dominating and reference sets in a graph

    Slater PJ. Dominating and reference sets in a graph. J. Math. Phys. Sci, 1988, 22(4):445–455

    work page 1988

  23. [23]

    Fault-tolerant locating-dominating sets

    Slater PJ. Fault-tolerant locating-dominating sets. Discrete Mathematics. Combinatorics, Graph Theory, and Computing. 2002, 249(1-3):179–189. doi:10.1016/S0012-365X(01)00244-8

    work page doi:10.1016/s0012-365x(01)00244-8 2002

  24. [24]

    Automated Discharging Arguments for Density Problems in Grids

    Stolee D. Automated discharging arguments for density problems in grids. ID: 15143804, arXiv preprint arXiv:1409.5922, 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  25. [25]

    An introduction to ergodic theory , volume 79 of Graduate Texts in Mathematics

    Walters P. An introduction to ergodic theory , volume 79 of Graduate Texts in Mathematics. Springer- Verlag, New York, 1982. ISBN: 3540905995, 9783540905998

    work page 1982