{"id":"bdf8c34e-3384-4a38-9a80-7b99c9512efd","arxiv_id":"2509.04726","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Arithmetic width counts distinct linear-functional values on lattice points of a convex body; for rational polytopes it grows eventually quasilinearly under dilation, and its computation is claimed to be polynomial or single-exponential in fixed dimension.","lead":"This paper introduces 'arithmetic width', a new way to measure a convex shape by counting how many different values a linear function takes on the integer grid points inside it. The authors prove the value count behaves regularly as the shape grows, and propose algorithms to compute it.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5.4's test-set construction returns an empty T for full-dimensional rational polytopes with collinear lattice points, so Main Theorem 3(b) is unproved as written.","rationale":"The reader's weakest assumption identifies exactly the load-bearing failure: Lemma 5.4's test-set construction assumes N contains d−1 linearly independent vectors, which is false for full-dimensional rational polytopes whose lattice points are collinear or otherwise lie in a lower-dimensional affine subspace. My independent check of the dimension-3 example confirms the construction returns T=∅ despite aw(P)=1 being attained by an omitted direction. This invalidates the proof of Main Theorem 3(b), which is the paper's central algorithmic claim. I also note a related proof bug in Theorem 5.3: evaluating the substituted generating function at t=1 gives |P∩Z^d|, not the number of distinct values in AR_c(P), so the fixed-direction algorithm also needs correction. These are localized, repairable flaws in the algorithms section rather than defects in the structural results; Main Theorems 1, 2, and 4 have self-contained proofs and appear plausible. Since the reader's CONDITIONAL verdict already reflects the need for revision, my assessment does not move the verdict.","tokens_in":13821,"tokens_out":11361,"duration_ms":102060,"concrete_test":"Run the Lemma 5.4 enumeration on P=conv((0,0,0),(2,0,0),(1,1/3,1/3),(1,-1/3,1/3)). Verify P∩Z^3 = {(0,0,0),(1,0,0),(2,0,0)}, so N=(P−P)∩Z^3 has rank 1 and the subroutine returns T=∅. Then check that c=(0,1,0) gives aw_c(P)=1, so aw(P)=1. If the algorithm returns no candidate directions on an input with aw(P)=1, the sufficiency claim for the constructed T fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 5.4 is the sole basis for Main Theorem 3(b), and its construction of the test set T is not sufficient. It enumerates only directions orthogonal to a (d−1)-dimensional span of vectors in N=(P−P)∩Z^d. If the lattice points of P lie in a lower-dimensional affine subspace, N has rank r<d−1, no (d−1)-element independent subset exists, and T=∅, even though aw(P) is finite and attained. Concretely, take P=conv((0,0,0),(2,0,0),(1,1/3,1/3),(1,-1/3,1/3))⊂R^3. Because z=(λ_C+λ_D)/3, the only integer points in P are (0,0,0),(1,0,0),(2,0,0), so N has rank 1 and the algorithm produces T=∅. Yet c=(0,1,0) maps all three lattice points to 0, giving aw(P)=1. Thus the claimed singly-exponential algorithm fails on a valid full-dimensional rational polytope. This is a gap in a main theorem, not a stylistic issue; it is repairable by enumerating independent subsets of all sizes 1,...,d−1 and taking a primitive normal to each span, but the theorem and proof need revision.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper introduces the arithmetic width of a convex body K, defined as the minimum over nonzero integer directions c of the number of distinct values that c^T x attains on the lattice points K∩Z^d. The authors establish that for large dilates nK, the arithmetic range in a fixed direction is an almost arithmetic progression (Main Theorem 1); that for rational polytopes the arithmetic width in a fixed direction, and the minimized arithmetic width, are eventually quasilinear in the dilation parameter (Main Theorem 2); and that in fixed dimension, aw_c(P) is computable in polynomial time and aw(P) in single-exponential time (Main Theorem 3). They also show that optimal directions for lattice width and arithmetic width can differ, and that every finite set of integers occurs as an arithmetic range of a rational simplex (Main Theorem 4).","tokens_in":14040,"tokens_out":21685,"duration_ms":187610,"significance":"The notion of arithmetic width is a natural refinement of lattice width, and the structural results linking it to almost arithmetic progressions and eventual quasilinearity are genuinely interesting, connecting discrete geometry, integer programming, and additive combinatorics. The paper is self-contained and does not fit parameters to data; the algorithms are based on Barvinok's theory, which is appropriate. The claimed fixed-dimension algorithms are valuable if correct. However, the algorithmic theorem and the proof of the main structural theorem contain significant gaps that must be repaired before the results can be considered established.","major_comments":[{"comment":"The test set construction in Lemma 5.4 is incomplete and can output the empty set for valid inputs. The construction enumerates only linearly independent subsets of N=(P-P)∩Z^d of size d-1 and takes primitive integer normals to their span. If the lattice points of a full-dimensional rational polytope P lie in a lower-dimensional affine subspace, N has rank r<d-1, no such subset exists, and T=∅, yet aw(P) is finite and attained. For example, in R^3 take P=conv((0,0,0),(2,0,0),(1,1/3,1/3),(1,-1/3,1/3)). The only lattice points in P are (0,0,0),(1,0,0),(2,0,0), so N has rank 1; T is empty. But c=(0,1,0) maps all lattice points to 0, so aw_c(P)=1 and aw(P)=1. Thus Main Theorem 3(b) is unproved as stated. The repair is to enumerate independent subsets of all sizes 1,...,d-1 and take a primitive integer vector orthogonal to each span; the theorem and proof need revision.","section":"§5, Lemma 5.4"},{"comment":"The concluding step of the proof of Theorem 5.3 is incorrect: after computing the univariate generating function h(t) whose monomials correspond to AR_c(P), the proof states that 'evaluating h(t) at t=1 yields precisely the desired count.' In fact h(1) equals the number of lattice points |P∩Z^d|, not the number of distinct values |AR_c(P)|. The support size of a polynomial cannot be read off from its value at 1. Consequently the claimed polynomial-time algorithm for aw_c(P) in Main Theorem 3(a) is not established by the given proof. A different method to count the distinct exponents in the short rational representation of h(t) is needed; alternatively, one may use the Barvinok–Woods projection theorem (Lemma 5.2) and a support-size computation, but this is not supplied.","section":"§5, Theorem 5.3"},{"comment":"The reduction in the proof of Theorem 3.3 is invalid. After setting L=aff(K)∩Z^d and J=K∩L, the proof claims nJ∩Z^d = nK∩Z^d for all n. This is false: if K is a full-dimensional body whose lattice points are collinear, then J is just those finitely many lattice points, and nK∩Z^d contains lattice points that are not n times an original lattice point. For instance, with P as in the counterexample to Lemma 5.4, the point (3,1,1) lies in 3P∩Z^3 but (3,1,1)/3 is not in P∩Z^3, so 3J does not contain it. The argument 'x∈aff(L) so x∈J' confuses the real affine span of L with L itself. This gap undermines the proof of the almost-arithmetic-progression theorem (Main Theorem 1) and the step-size λ used in Main Theorem 2. The statements may be true, but a different reduction (for example, working with the lattice generated by differences of lattice points of all dilates) is required.","section":"§3, Theorem 3.3"}],"minor_comments":[{"comment":"'Barkinov' is a typo for 'Barvinok' in the proof of Lemma 5.4.","section":"§5, Lemma 5.4"},{"comment":"The sentence 'For rational polytopes, |N| can be computed in polynomial time... However, the number of lattice points in P, and thus N, can be exponentially large' should clarify that the cardinality is computable in polynomial time while listing the set may be exponential; as written it reads as a contradiction.","section":"§5, Lemma 5.4"},{"comment":"In the displayed formula for aw(nP), the step size λ should be indexed by the residue class i, since λ depends on the optimal direction c_i^*; the current notation suggests a single λ for all classes.","section":"§4, Theorem 4.8"},{"comment":"In the definition of an almost arithmetic progression, the sets A and A' are said to be subsets of [m,m+t]∩(λZ+m) and [M-t',M]∩(λZ+m), respectively, but they should represent the omitted values; the notation could be clarified.","section":"§3, Definition 3.1"},{"comment":"The phrase 'giving us our final claim' ends the proof of the maximal arithmetic width, but the sentence preceding it is missing a verb; please revise for clarity.","section":"§2, Proposition 2.1(d)"}],"recommendation":"major_revision","confidential_remarks":"The computational claims in Main Theorem 3 are the weakest part of the paper as written; the false evaluation step and the empty test set are concrete and easily demonstrated. The gap in Theorem 3.3 is more fundamental and will require a substantial rewriting of the proof of the structural theorem. I believe the underlying results are plausible and the paper is within scope for math.CO, but it should not be accepted until all three issues are resolved. The self-citation [28] in Remark 4.5 is used only as an alternative-proof remark and does not affect the main results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on arXiv:2509.04726. The paper's core idea is simple and good: count distinct values of c·x on lattice points instead of measuring the real width of the body. That gives a finer, integer-valued invariant that detects gaps lattice width misses. The structural half of the paper is in good shape. Main Theorem 1 (arithmetic ranges of large dilates form almost arithmetic progressions) and Main Theorem 2 (arithmetic width is eventually quasilinear, with optimal directions periodic) are new results with plausible proofs. The numerical semigroup material is a nice application, not a crutch. The writing is clear and the paper is self-contained.\n\nThe algorithmic half, Main Theorem 3, has two genuine gaps. First, the proof of Theorem 5.3 ends by evaluating the univariate generating function h(t) at t=1 and calling the result the number of distinct monomials. That's wrong. h(t) is a sum over lattice points, so h(1) counts lattice points, not distinct values of the linear functional. The support of h(t) is what you need, and the proof as written doesn't compute it. This is the final step of an algorithmic main theorem, not a typo.\n\nSecond, Lemma 5.4 constructs the test set T by enumerating linearly independent subsets of N=(P-P)∩Z^d of size d-1. If N has rank less than d-1, there are no such subsets, T is empty, and the algorithm still claims to compute aw(P). That happens for full-dimensional polytopes with all lattice points on a line. A concrete example: P=conv((0,0,0),(2,0,0),(1,1/3,1/3),(1,-1/3,1/3)) in R^3 has only (0,0,0),(1,0,0),(2,0,0) as lattice points, so N has rank 1, and the lemma produces T=∅. But aw(P)=1, attained by (0,1,0). This is a load-bearing gap in Main Theorem 3(b). The fix is straightforward—enumerate independent subsets of all sizes and take normals to their spans—but the theorem and proof need to be revised.\n\nThe structural results are worth publishing. The algorithmic claims are likely repairable, but as written Main Theorem 3 is not proven. I'd send this to peer review and let the authors fix the algorithm; I'd also want the referee to push on Lemma 4.1, which I found plausible but did not verify line by line. For a reader in polyhedral geometry or integer optimization, the paper is genuinely useful. I'd cite it for the structural results.","headline":"New invariant, solid structural theorems, but Main Theorem 3 has two repairable proof gaps that need fixing before the algorithmic claims are accepted.","tokens_in":14582,"tokens_out":10223,"would_cite":true,"duration_ms":92385,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["11H06","52B20","52C07"],"pacs":[],"model":"deepseek-v4-flash","headline":"A new invariant, arithmetic width, counts the distinct values a linear functional attains on the lattice points of a convex body, refining lattice width and enabling fixed-dimension computation.","keywords":["arithmetic width","lattice width","convex body","rational polytope","arithmetic progression","quasilinear growth","generating functions","numerical semigroup"],"falsifier":"For the simplex $P=\\operatorname{conv}((0,0,0),(2,0,0),(1,1/3,1/3),(1,-1/3,1/3))$ in $\\mathbb{R}^3$, the nonzero integer differences $(P-P)\\cap\\mathbb{Z}^3$ are all multiples of $(1,0,0)$, so the enumeration in Lemma 5.4 returns no test directions; yet $\\operatorname{aw}(P)=1$, attained by any direction perpendicular to the $x$-axis. Running the stated algorithm on this input would miss the optimum, showing that the constructed set is not a sufficient test set in the form presented.","tokens_in":13587,"feed_emoji":"📏","tokens_out":20279,"duration_ms":154637,"temperature":0.7,"pith_summary":"The paper introduces the arithmetic width of a convex body, defined for a fixed integer direction as the number of distinct values a linear functional takes on the lattice points inside the body. Unlike lattice width, which measures distances between parallel supporting hyperplanes, arithmetic width counts only the hyperplane levels that actually contain lattice points, so gaps in the lattice-point distribution are detected. The central claims are structural and algorithmic: for large dilates of any convex body the attained values form an arithmetic progression with only bounded omissions near the ends, and for rational polytopes the arithmetic width, whether in a fixed direction or minimized over all directions, grows eventually quasilinearly in the dilation parameter (linear on each residue class modulo the denominator) while the optimal directions repeat periodically. In fixed dimension, the arithmetic width in a given direction is computable in polynomial time, and the global arithmetic width is computable in single-exponential time, using short rational generating functions and a finite test set of directions.","feed_headline":"New width counts the lattice levels a body really touches","feed_subtitle":"For rational polytopes it grows quasilinearly under dilation and is computable in fixed dimension.","key_machinery":"The central object is the arithmetic width $\\operatorname{aw}_c(K)=|\\mathrm{AR}_c(K)|$, the number of distinct values of $c^{\\mathsf{T}}x$ on $K\\cap\\mathbb{Z}^d$. The structure theorem is carried by a convexity argument: once a dilation is large enough to contain a small ball, the fact that a primitive integer direction attains every integer value on the lattice guarantees that every intermediate lattice hyperplane contains a lattice point, so the arithmetic range is an arithmetic progression except near the extremes. The algorithmic machinery is the short rational generating function of the lattice points of a rational polytope, a polynomial-size expression in fixed dimension, together with substitution and projection theorems that turn it into a univariate generating function whose distinct monomials count the arithmetic width. For the global width, the finite test set $T$ is built from primitive integer vectors orthogonal to linearly independent differences of lattice points of $P$, since any minimizing direction must collapse two distinct lattice points.","core_discovery":"The core discovery is that the arithmetic range $\\mathrm{AR}_c(K)=\\{c^{\\mathsf{T}}x : x\\in K\\cap\\mathbb{Z}^d\\}$ of a convex body has a stabilized, almost arithmetic shape under dilation. For large $n$, the set $\\mathrm{AR}_c(nK)$ agrees with an arithmetic progression of some step $\\lambda$ except for a bounded number of missing values near the minimum and maximum, where $t,t',\\lambda$ depend only on $K$. For a rational polytope $P$ with denominator $D$, the arithmetic width in a fixed direction is eventually quasilinear in $n$, and the same holds for the minimized width $\\operatorname{aw}(nP)=\\min_c \\operatorname{aw}_c(nP)$; moreover the minimizing directions recur periodically with period $D$. On the algorithmic side, the arithmetic width in a fixed direction is computable in polynomial time in fixed dimension, and the global arithmetic width is computable in single-exponential time via a finite test set of directions obtained from differences of lattice points. Finally, the optimal directions for arithmetic and lattice width can be disjoint, and every finite set of integers arises as the arithmetic range of a rational simplex.","pith_inferences":["The almost-arithmetic-progression structure of arithmetic ranges parallels the eventual quasipolynomial behavior of lattice-point counting functions of rational polytopes and of graded algebra dimension sequences, so arithmetic width could serve as a discrete-geometric analog of those counting functions.","Because $\\operatorname{aw}(P)$ counts occupied hyperplane levels, it can serve as a sharper certificate of thinness in integer programming: a small arithmetic width in a near-optimal direction indicates that few integer objective values are available, complementing existing integrality-gap estimates.","A natural next step is to ask whether the finite test set can be constructed from the lattice span of $(P-P)\\cap\\mathbb{Z}^d$ rather than from the full difference set; answering this would settle the algorithm's scope for polytopes whose lattice points occupy a lower-dimensional subspace.","The realization theorem suggests a construction tool: one can design rational simplices whose lattice-point projections onto a line realize any prescribed finite pattern, which may be useful for building examples in projection and lifting problems."],"forward_implications":["For any rational polytope $P$ with denominator $D$, the arithmetic width $\\operatorname{aw}(nP)$ is eventually quasilinear in $n$, so the width of dilates is described by $D$ linear functions, one per residue class modulo $D$, and the optimal directions repeat with period $D$.","In fixed dimension, given any integer direction $c$, $\\operatorname{aw}_c(P)$ can be computed in polynomial time in the bit-sizes of $P$ and $c$, and $\\operatorname{aw}(P)$ can be computed in single-exponential time.","Arithmetic width is at most lattice width plus one and detects gaps that lattice width ignores; Example 2.2 shows the directions minimizing the two invariants can be disjoint, so arithmetic width is not just a relabeling of lattice width.","Because every finite set of integers is realizable as the arithmetic range of some rational simplex, no simple structural restriction other than finiteness governs which sets can be arithmetic ranges; in particular the realization result for numerical semigroup factorization lengths follows as a corollary."],"supporting_citations":[{"why":"Supplies the fixed-dimension short rational generating function theorem for lattice points in rational polytopes, the representational basis of both width algorithms.","marker":"[5]"},{"why":"Supplies the substitution and projection theorems for rational generating functions, used to compute the univariate function whose distinct monomials are the arithmetic width and to evaluate candidate directions.","marker":"[6]"},{"why":"Provides the periodicity theorem for sets of lengths in numerical semigroups that the paper recovers as a corollary of its quasilinear-width results, anchoring the connection to additive combinatorics.","marker":"[28]"}],"fun_headline_variants":["Arithmetic width: a finer lens on lattice point slices","Counting linear values exposes missing lattice levels","Large dilates yield near-arithmetic progressions of values","Quasilinear width growth with recurring optimal directions","Fixed-dimension algorithms for a sharper width measure"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The test-set construction assumes that the differences of lattice points of $P$ contain enough linearly independent vectors to determine every minimizing direction; a full-dimensional rational polytope whose lattice points all lie on a line makes the enumeration come up empty even though minimizing directions exist.","fun_headline_variants_meta":{"raw":{"variants":["Arithmetic width: a finer lens on lattice point slices","Counting linear values exposes missing lattice levels","Large dilates yield near-arithmetic progressions of values","Quasilinear width growth with recurring optimal directions","Fixed-dimension algorithms for a sharper width measure"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00027,"raw_usage":{"total_tokens":1597,"prompt_tokens":892,"completion_tokens":705,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":508,"completion_tokens_details":{"reasoning_tokens":631}},"tokens_in":508,"tokens_out":705,"duration_ms":6945,"temperature":1.0,"reasoning_tokens":631,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:29:23.568550+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For the simplex $P=\\operatorname{conv}((0,0,0),(2,0,0),(1,1/3,1/3),(1,-1/3,1/3))$ in $\\mathbb{R}^3$, the nonzero integer differences $(P-P)\\cap\\mathbb{Z}^3$ are all multiples of $(1,0,0)$, so the enumeration in Lemma 5.4 returns no test directions; yet $\\operatorname{aw}(P)=1$, attained by any direction perpendicular to the $x$-axis. Running the stated algorithm on this input would miss the optimum, showing that the constructed set is not a sufficient test set in the form presented.","supporting_citations":[{"cited_title":"Pommersheim","cited_arxiv_id":null,"evidence_quote":"Supplies the fixed-dimension short rational generating function theorem for lattice points in rational polytopes, the representational basis of both width algorithms."},{"cited_title":"Short rational generating functions for lattice point problems.J","cited_arxiv_id":null,"evidence_quote":"Supplies the substitution and projection theorems for rational generating functions, used to compute the univariate function whose distinct monomials are the arithmetic width and to evaluate candidate directions."},{"cited_title":"The structure theorem for sets of lengths for numerical semi- groups.J","cited_arxiv_id":null,"evidence_quote":"Provides the periodicity theorem for sets of lengths in numerical semigroups that the paper recovers as a corollary of its quasilinear-width results, anchoring the connection to additive combinatorics."}],"review_version":2}