{"id":"2ee05cd6-0f35-4c0c-bcd9-15f9bf8b331c","arxiv_id":"2411.13248","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A new maximal-independent-set formulation for periodic unit-distance-free sets in the plane is tested and shown, in the parameter range tried, not to beat Croft's 1967 density lower bound of 0.22936.","lead":"This paper recasts the hunt for the densest planar set with no two points exactly one unit apart as a computer search for independent sets on flat-torus graphs. It finds that, across a broad range of lattice parameters, this search never beats the 1967 lower bound, and the best patterns look like Croft's classic construction.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper's negative conclusion that the method cannot improve Croft is not supported by the data: the reported independent-set sizes come from heuristic solvers on finite grids, so they bound the true graph maximum only from below.","rationale":"The most central assertion is not the framework itself, which is sound under its hypotheses, but the claim that the framework fails to improve the known lower bound. The experiments cannot establish this because the solvers are heuristic and the grid sizes are finite. Found independent sets are lower bounds; to conclude 'cannot improve' one needs either an exact maximum for each graph or an upper bound on the MIS density. The data show an upward trend in density with n, so the 0.2246 at n=400 may not be the limit. This is load-bearing because it directly concerns the headline result. The reader's parameter-regime concern is related but, in my reading, secondary. Any periodic set with a small primitive cell can also be viewed on a sublattice/supercell with larger side lengths and heights, so the perfect-periodicity condition l1 >= 2, l2 sin alpha >= 2 is not in principle exclusive of Croft-like configurations. What remains true is that the paper's finite grid sampling and single refinement path could miss parameter regions; this is another reason the negative claim is provisional. The minor flaw in Lemma 2's 'shortest lattice vector >= min{l1,l2}' statement does not enter the main argument once the height condition is used correctly. Overall, the paper's theoretical contribution stands, but its central negative conclusion should be presented as heuristic evidence, not as a definitive impossibility result.","tokens_in":1283,"tokens_out":958,"duration_ms":206040,"concrete_test":"Take the graph G_{400,400} for the reported best torus (l1=l2=3.331, alpha=pi/3) and compute a certified upper bound on the maximum independent set size, for example by running an exact branch-and-bound MIS solver with an optimality certificate, or by exploiting the graph's translation-invariance to solve the LP/fractional relaxation around one vertex. If the certified upper bound is at most 36,697, then no independent set on this grid reaches density above Croft's 0.22936 (since 36,698/160,000 > 0.22936), supporting the negative claim at this resolution. If the upper bound is at least 36,698, the heuristic value 35,936 is inconclusive and the paper's conclusion is not established; one would then need to find a certified independent set of size at least 36,698 to demonstrate an actual improvement.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The theoretical core (Theorem 1 via Lemmas 3-4) is valid: a certified independent set M in the constructed torus graph gives a legitimate lower bound m1(R^2) >= |M|/(nm), provided the torus is perfectly periodic and 2r<1. The load-bearing gap is the inference drawn from the experiments. In Section 5.4 and the Conclusion the paper states that 'the maximum independent set problem on a periodic grid... cannot improve' Croft's 0.22936. But every numerical maximum in Table 2 and Figs. 4-8 is obtained by heuristic solvers with 100-second time limits, and the paper explicitly acknowledges that none of these methods guarantees optimality. Hence each reported value is only a lower bound on the true maximum independent set size of the corresponding graph. A larger independent set could exist and could push the density above 0.22936. Indeed the KaMIS densities increase with grid size (0.2193 at n=100, 0.2212 at n=200, 0.2218 at n=300, 0.2246 at n=400), so the gap to Croft is not shown to be stable. Additionally, the dataset search used n=m=100 and refined only around one local maximum (l*=3.331, alpha=60 degrees); no optimality certificates are supplied. Consequently, the paper's 'does not improve' conclusion is an overstatement: the experiments show only that these particular heuristic runs did not find a better set.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a computational framework for lower-bounding the maximal density m_1(R^2) of planar sets avoiding unit distances. It reformulates the problem on a flat torus T_{l1,l2,α} as a maximum independent set (MIS) problem on a finite graph G_{n,m} whose vertices are grid points and whose edges connect pairs whose torus distance lies in [1−2r,1+2r], where r is the circumradius of the triangulation cells. Under a sufficient 'perfectly periodic' condition on the torus (Lemma 2), Theorem 1 states that any independent set M of G_{n,m} yields a valid lower bound m_1(R^2) ≥ |M|/(nm). The paper runs several heuristic MIS solvers (KaMIS, DGL-TreeSearch, Intel-TreeSearch, LwD) on datasets of such graphs, finds a local optimum near (l1,l2,α)=(3.331,3.331,60°), and reports best densities of about 0.2246 for grids up to 400×400, below Croft's 0.22936. It concludes that, within the tested range, the approach does not improve the known lower bound, and it compares the solvers' performance.","tokens_in":16688,"tokens_out":9007,"duration_ms":86345,"significance":"If the theoretical framework is made fully rigorous and the negative conclusion were properly qualified, the paper would be a useful contribution: it gives a novel, general way to translate the Moser problem into a finite combinatorial optimization problem, it supplies open-source code and reproducible experiments, and it provides a systematic comparison of MIS solvers on a new family of geometric graphs. The observation that the found near-optimal sets resemble Croft's construction is also interesting. However, the paper's central negative claim currently overstates what the heuristic experiments can establish, and two proof errors in the theoretical core need correction before the framework can be relied upon.","major_comments":[{"comment":"The proof of Lemma 2 contains an incorrect inequality: it states that for any nonzero integer pair (m,n), |m v1 + n v2| ≥ min{l1,l2}, which is false. For example, with l1 = l2 = 2 and α = 30°, the vector v1 − v2 has length 4 sin(15°) < 2, so the claimed lower bound fails. The statement of the lemma is nevertheless salvageable under its hypotheses: when n ≠ 0, the vertical component is |n| l2 sin α ≥ 2, and when n = 0, the length is |m| l1 ≥ 2. The proof must be rewritten using this argument rather than the false minimum-basis-vector bound. Since Lemma 2 is what justifies the 'perfectly periodic' condition used throughout the experimental parameter selection, this is a load-bearing proof error, though it is readily repairable.","section":"Lemma 2 (proof)"},{"comment":"In the proof of Lemma 3, the sentence 'by the construction of G, there are no two points p ∈ Fi, q ∈ Fj such that ρ(p,q) < 1' is incorrect: the graph construction rule only guarantees that ρ(p,q) ≠ 1 for such pairs, not that all distances are non-sub-unit. Consequently, the following line 'Consequently, ρ(P0,Q0) < 1' does not follow. The intended argument works if one instead uses ρ(P0,Q0) ≠ 1 directly and then applies the perfect-periodicity condition. Because Lemma 3 is the core of Theorem 1, this logical gap must be fixed before the theorem's proof is valid.","section":"Lemma 3 (proof)"},{"comment":"The paper's main conclusion that the MIS approach 'cannot improve' Croft's bound 0.22936 is not supported by the evidence presented. As the paper itself notes in Section 5.2, none of the solvers guarantees optimality, so every reported |M| is only a lower bound on the true maximum independent set size of the corresponding graph. The experiments therefore show that certain heuristic runs did not find a better set; they do not demonstrate that no such set exists, even within the tested parameter range. Moreover, the best densities increase with grid size (0.2193 at n=100, 0.2212 at n=200, 0.2218 at n=300, 0.2246 at n=400 for KaMIS), so the gap to Croft is not shown to be stable under refinement. The paper should either provide optimality certificates (for example, for small n) or explicitly rephrase the conclusion as 'no improvement was found by these heuristics' and state that the question remains open for finer grids and larger instances.","section":"Section 5.4 and Conclusion (negative claim)"},{"comment":"The experimental search is restricted to tori satisfying the sufficient perfect-periodicity conditions l1 ≥ 2 and l2 sin α ≥ 2 (or the symmetric condition). Croft's own construction uses a hexagonal lattice of side length about 1.965, whose height is about 1.70, so it falls outside the tested regime. The abstract's phrase 'for a sufficiently wide range of parameters' is therefore potentially misleading: the most historically relevant parameter region is excluded. The paper should state this restriction explicitly in the abstract and in the conclusion, and it should not be implied that the tested range represents all plausible periodic constructions.","section":"Abstract and Section 5.3 (parameter restriction)"}],"minor_comments":[{"comment":"The caption contains a typo: 'flat tours datasets' should read 'flat tori datasets'.","section":"Table 2 caption"},{"comment":"The paper uses the term 'maximal independent set' when it means 'maximum independent set' (the largest cardinality independent set). In graph theory, 'maximal' means inclusion-wise maximal, which is a different notion. Please correct the terminology throughout, including the title.","section":"Throughout"},{"comment":"The claim that the Voronoi cells of the grid points under the torus metric are equal hexagons with circumradius r is asserted without proof. This relies on the described triangulation being the Delaunay triangulation of the lattice. Since Theorem 1 depends on the hexagon decomposition and the equality of all cell areas, a short proof or a reference for this standard lattice fact should be provided.","section":"Section 4"},{"comment":"The numeric labels in the figures should be checked for consistency. In particular, Figure 5 reports n = 250 with |M| = 13962 and density 0.2233, while the text says DGL-TreeSearch had difficulty scaling beyond 250² vertices; please verify these values against the repository data.","section":"Figures 4-8"},{"comment":"The proof of Lemma 1 treats only the case t1,t2 ≥ 0 in detail and states that other sign cases are 'analogous'. This is acceptable, but a short explanation of the definition of the vector w in the mixed-sign cases would improve readability.","section":"Lemma 1 proof"}],"recommendation":"major_revision","confidential_remarks":"The paper's main value is as a reproducible computational framework and a systematic solver comparison; the theoretical core, once the two proof errors are fixed, appears valid. The key editorial risk is that the abstract and conclusion state a negative mathematical claim ('cannot improve') that is not justified by heuristic lower-bound experiments. I recommend the editor ask for a careful revision that (i) corrects the proofs of Lemmas 2 and 3, (ii) softens the conclusion to reflect that the experiments are heuristic and restricted to a parameter regime that excludes Croft's own lattice, and (iii) adds either optimality certificates for small instances or a clear statement that the method's potential for improving m_1(R^2) remains open. If the authors can provide such certifications for at least some parameter values, the paper would be much stronger."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"New here is the reduction: for any perfectly periodic flat torus satisfying the height conditions and a discretization with hexagon diameter <1, an independent set in the associated graph gives a valid lower bound on m1(R2) (Theorem 1). That is real and reusable. The paper also ships code and a careful solver comparison. The best found density, 0.2246 at n=400, is below Croft's 0.22936, and the found sets do approximate Croft's tortoise. That is an honest, reproducible negative data point.\n\nThe theoretical core mostly holds. Lemma 1 gives a finite algorithm for the torus metric; Lemma 5's regularity argument is correct. The proof of Lemma 2, however, uses a wrong bound: it claims that for (m,n) not both zero, |m v1 + n v2| >= min{l1,l2}, which is false when v1-v2 is shorter than either basis vector. The lemma is still true under l1 >= 2 and l2 sin alpha >= 2, but the proof should argue via the height l2 sin alpha, not min{l1,l2}. Minor and fixable.\n\nThe soft spots are in the experimental inference. Section 5.4 says that within the tested range, the MIS problem on these grids 'cannot improve' the Croft bound. That is too strong. Every reported |M| comes from KaMIS, DGL-TreeSearch, Intel-TreeSearch, or LwD with a 100-second limit, and the paper states these solvers do not guarantee optimality. So each value is only a lower bound on the graph's true independence number. A larger independent set may exist that would push the density above 0.22936. The trend is not plateaued: KaMIS gives 0.2193 at n=100 and 0.2246 at n=400, still rising with grid size. The paper's own conclusion, a sentence later, hedges by saying other parameter values are not covered, but the 'cannot improve' line overstates what the evidence shows.\n\nSecond, the search is restricted to tori with the parallelogram height at least 2. Croft's construction has height about 1.70, so the most natural competitor sits outside the tested region. That makes the negative result provisional rather than definitive.\n\nThird, the paper mentions that the edge set was computed with a simplified algorithm and that this does not lead to a noticeable improvement, but gives no data for that claim. It is a small reproducibility gap.\n\nWho is this for? People working on the chromatic number of the plane or on distance-avoiding densities will find the reformulation useful, and the code is a reasonable starting point. The mathematical core is sound, but the negative claim needs to be reworded as 'our heuristic searches did not beat Croft in this parameter range.' That is a legitimate result, just not the stronger impossibility. I would send it to a journal with a referee.","headline":"A sound new reformulation of periodic 1-avoiding density as MIS on flat-torus graphs, with an honest negative data point, but the stronger claim that this approach cannot improve Croft is not supported because all reported maxima come from heuristic solvers.","tokens_in":17233,"tokens_out":4142,"would_cite":false,"duration_ms":41237,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["52C10","05C69"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper reduces the lower-bound problem for planar unit-distance-free sets to maximum independent sets on flat-torus graphs; over a wide tested range the best bound is 0.2246, below the standing 0.22936.","keywords":["Distance-avoiding sets","independent set search","planar colorings","combinatorial optimization","discrete optimization","flat torus","periodic sets","unit distances"],"falsifier":"Run the same graph construction on the hexagonal torus of side about 1.965 and height about 1.70 that underlies the 1967 bound, with a grid fine enough that $2r<1$, and check directly whether an independent set lifts to a unit-distance-free periodic set with ratio above $0.22936$; finding such a set would show the paper's negative conclusion is limited to its tested parameter range. Alternatively, a single grid up to $400\\times400$ on the identified local-maximum torus returning $|M|/(nm) > 0.22936$ would refute the saturation claim.","tokens_in":16147,"feed_emoji":"📐","tokens_out":14251,"duration_ms":124387,"temperature":0.7,"pith_summary":"This paper tries to lower-bound the maximal density $m_1(\\mathbb{R}^2)$ of measurable planar sets that contain no pair of points at distance exactly 1. Its contribution is a finite reduction: on a flat torus $T_{l_1,l_2,\\alpha}$ that is perfectly periodic (both lattice heights at least 2), partitioning the torus into equal hexagons of circumradius $r<1/2$ and drawing an edge between two grid points when their torus distance lies in $[1-2r,1+2r]$ turns the geometric problem into a maximum independent set (MIS) problem. Any independent set $M$ in this graph gives a rigorous lower bound $m_1(\\mathbb{R}^2) \\ge |M|/(nm)$. Running several MIS solvers over a wide grid of parameters, with graphs up to $400\\times400$ vertices, the best ratio found is $0.2246$, below the known lower bound $0.22936$ from 1967. The found sets visually match that classical construction, so the paper concludes that within this tested range the approach reproduces but does not improve the record.","feed_headline":"Unit-distance search tops out below the 1967 density bound","feed_subtitle":"Reformulating periodic sets as independent-set graphs yields 0.2246 — not better than the standing 0.22936.","key_machinery":"The load-bearing object is the graph $G_{n,m}$ built on a perfectly periodic flat torus $T_{l_1,l_2,\\alpha}$, where a flat torus is the parallelogram spanned by two non-collinear vectors with opposite sides identified. Perfect periodicity here means the sufficient condition $l_1\\ge 2$ and $l_2\\sin\\alpha\\ge 2$ (or the symmetric inequalities), which guarantees that a set avoiding unit distances on the torus lifts to a periodic set avoiding unit distances in the plane. The torus is triangulated by an $n\\times m$ grid; each grid point is the center of an equal hexagonal Voronoi cell, and the triangulation's circumradius $r$ must satisfy $2r<1$ so every cell has diameter below 1. Two vertices are adjacent when their torus distance lies in $[1-2r,1+2r]$, the only interval in which points of their cells can be exactly one unit apart. An independent set $M$ selects whole hexagons with no unit distance between any two, and Theorem 1 converts the ratio $|M|/(nm)$ into a rigorous lower bound on $m_1(\\mathbb{R}^2)$. The paper also proves the graph is shift-invariant and regular, so all edges can be generated from one vertex's neighborhood, which is what makes grids up to 90,000 vertices computationally feasible.","core_discovery":"The central claim, stated as Theorem 1, is that for a flat torus $T_{l_1,l_2,\\alpha}$ satisfying the perfect-periodicity conditions $l_1\\ge 2$ and $l_2\\sin\\alpha\\ge 2$ (or the symmetric pair), and for any grid sizes $n,m$ whose triangulation circumradius $r$ obeys $2r<1$, every independent set $M$ in the constructed graph $G_{n,m}$ gives a valid lower bound $m_1(\\mathbb{R}^2)\\ge |M|/(nm)$. The paper searches this family of tori over a broad parameter grid, locates a local maximum near side lengths $3.331,3.331$ with angle $60^\\circ$, and runs four independent-set solvers on graphs up to $400\\times400$ vertices. The best ratio obtained is $0.2246$, below the known $0.22936$ bound from 1967, and the independent sets resemble the classical tortoise-shaped construction. The paper therefore concludes that, within the range of parameters it tested, the MIS approach does not improve the known lower bound of $m_1(\\mathbb{R}^2)$.","pith_inferences":["A natural next step is to relax the perfect-periodicity height condition and test tori with $l_2\\sin\\alpha < 2$, checking the lifted set directly; the 1967 construction's lattice sits in this excluded regime, so a better bound could still hide there.","If the extremal sets really are tortoise-like, then beating $m_1(\\mathbb{R}^2)$ may require breaking periodicity or abandoning equal hexagonal cells; the MIS formulation as presented cannot see such configurations.","The shift-invariance that lets $G_{n,m}$ be built from one vertex's neighborhood is specific to these geometric graphs, and it could make the family a useful stress test for independent-set solvers independent of the unit-distance problem."],"forward_implications":["Every independent set found through the construction yields a rigorous, checkable lower bound $m_1(\\mathbb{R}^2) \\ge |M|/(nm)$ for any perfectly periodic torus satisfying the conditions, so the method is a proof engine rather than a heuristic estimate.","Within the tested parameter range, the best bound increases with grid size but stays below $0.22936$; the largest graphs (up to 90,000 vertices) give $0.2246$.","The optimal independent sets on the local-maximum torus are discrete approximations of the 1967 tortoise shape, indicating that the MIS approach saturates at the known construction within this family.","Since the construction is valid for any independent set, better bounds in this formulation would come from larger grids or stronger MIS solvers; the paper's comparison indicates that exact branch-and-bound solving currently outperforms the neural and reinforcement-learning solvers on these geometric graphs.","The same graph construction applies to other periodic-set density problems with a forbidden distance, provided the perfect-periodicity and cell-diameter conditions hold."],"supporting_citations":[{"why":"Supplies the standing lower bound 0.22936 and the tortoise-shaped periodic construction that the found independent sets approximate.","marker":"[7]"},{"why":"Provides the integrated open-source benchmark suite that runs the four independent-set solvers on the flat-torus graphs.","marker":"[5]"},{"why":"The guided tree-search solver whose results on the datasets are one of the four compared methods.","marker":"[19]"},{"why":"The reinforcement-learning solver compared in the experiments; its weaker large-graph performance is part of the evidence.","marker":"[1]"},{"why":"The branch-and-bound solver that performs best and produces the 400x400 independent set giving the 0.2246 bound.","marker":"[16]"}],"fun_headline_variants":["MIS reformulation fails to beat known density bound","Unit-distance density floor still 0.22936 after search","Graph approach finds 0.2246, below 1967 record","No improvement: periodic set density bound stands","MIS method falls short of 0.22936 lower bound"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the search only covers tori satisfying the sufficient perfect-periodicity condition $l_1\\ge2$ and $l_2\\sin\\alpha\\ge2$ (or its symmetric counterpart); if denser periodic constructions live on smaller tori outside this window, the observed failure to reach $0.22936$ would not prove anything about the method outside that range.","fun_headline_variants_meta":{"raw":{"variants":["MIS reformulation fails to beat known density bound","Unit-distance density floor still 0.22936 after search","Graph approach finds 0.2246, below 1967 record","No improvement: periodic set density bound stands","MIS method falls short of 0.22936 lower bound"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000209,"raw_usage":{"total_tokens":1405,"prompt_tokens":940,"completion_tokens":465,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":556,"completion_tokens_details":{"reasoning_tokens":382}},"tokens_in":556,"tokens_out":465,"duration_ms":5528,"temperature":1.0,"reasoning_tokens":382,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:40:51.474500+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same graph construction on the hexagonal torus of side about 1.965 and height about 1.70 that underlies the 1967 bound, with a grid fine enough that $2r<1$, and check directly whether an independent set lifts to a unit-distance-free periodic set with ratio above $0.22936$; finding such a set would show the paper's negative conclusion is limited to its tested parameter range. Alternatively, a single grid up to $400\\times400$ on the identified local-maximum torus returning $|M|/(nm) > 0.22936$ would refute the saturation claim.","supporting_citations":[{"cited_title":"Eureka30, 22–26 (1967)","cited_arxiv_id":null,"evidence_quote":"Supplies the standing lower bound 0.22936 and the tortoise-shaped periodic construction that the found independent sets approximate."},{"cited_title":"In: Proceedings of the International Conference on Learning Representations (ICLR) (2022)","cited_arxiv_id":null,"evidence_quote":"Provides the integrated open-source benchmark suite that runs the four independent-set solvers on the flat-torus graphs."},{"cited_title":"In: Advances in Neural Information Pro- cessing Systems (NeurIPS) (2018)","cited_arxiv_id":null,"evidence_quote":"The guided tree-search solver whose results on the datasets are one of the four compared methods."},{"cited_title":"In: Proceedings of the 37th International Conference on Machine Learning (ICML) (2020)","cited_arxiv_id":null,"evidence_quote":"The reinforcement-learning solver compared in the experiments; its weaker large-graph performance is part of the evidence."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The branch-and-bound solver that performs best and produces the 400x400 independent set giving the 0.2246 bound."}],"review_version":1}