{"id":"19cb75d3-701d-4fca-bb51-e3c9154fae46","arxiv_id":"2607.03041","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Finite subgraphs of the discrete Heisenberg group Cayley graph have O(r^4) growth but do not embed into any strong product of four linear-growth trees and a constant clique.","lead":"The paper disproves a 2022 conjecture: graphs of degree-4 polynomial growth need not embed into the strong product of four linear-growth trees and a constant clique. Finite subgraphs of the discrete Heisenberg group Cayley graph serve as counterexamples, via a quantitative collapse theorem for Lipschitz maps into L1.","discovery_kind":"new_application","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates the sole external dependency (CKN) and correctly judges the remainder of the argument to be elementary and self-contained. Because that dependency is a published theorem whose precise quantitative form is applied without modification, and because the subsequent discretisation, embedding into L1, and double-counting steps contain no algebraic or measure-theoretic slips that would invalidate the contradiction, there is no load-bearing concern that would move the verdict away from ACCEPT. The suggested concrete test simply re-checks the final arithmetic that produces the numerical contradiction; it is expected to succeed and thereby reconfirm the paper’s claim.","tokens_in":17138,"tokens_out":441,"duration_ms":5253,"concrete_test":"Independently recompute the lower bound |K'| ⩾ ε^{2} M^{4} in the last two paragraphs of §6 (using only the projection of R onto the first two coordinates and the fact that centre multiplications leave those coordinates unchanged) and verify that the resulting inequality still forces ε ⩾ 1/(49 C^{5/2}) for the chosen ε; if the inequality holds with the paper’s constants, the contradiction is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorems 1.2 and 7.2) rests on a transparent chain: CKN quantitative central collapse (Thm 3.1) is discretised via the extension/rounding lemmas of §4 into Lemma 4.3; the resulting collapsed central set K is then expanded by a short horizontal walk of length ~εM to produce a large set K' whose image under any putative product embedding into four linear-growth trees must be small (by the growth bound C r), yielding the counting contradiction of §6. Compactness (Lemma 7.1) is a standard diagonal-pattern argument that transfers the infinite obstruction to finite subgraphs. All constants are tracked explicitly and the only external black box is a published theorem whose statement is used verbatim. No internal gap, hidden assumption, or circularity appears in the combinatorial counting or the transfer.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper disproves Conjecture 1.1 of Campbell et al. for d=4: graphs of degree-d polynomial growth need not embed into the strong product of d linear-growth trees and a constant clique. The counterexamples are finite subgraphs of the Cayley graph Cay(H(Z),T) of the discrete Heisenberg group (growth O(r^4)). Theorem 1.2 shows that this infinite Cayley graph itself fails to embed into any such product of four linear-growth trees with K_C; a compactness argument (Lemma 7.1) then yields finite counterexamples (Theorem 7.2). The proof reduces an assumed product embedding to a Lipschitz map into L1, applies the Cheeger–Kleiner–Naor quantitative central-collapse theorem, discretises it (Lemma 4.3), and obtains a counting contradiction on a thickened central set (Section 6).","tokens_in":17323,"tokens_out":779,"duration_ms":5999,"significance":"The result settles a natural and explicitly stated conjecture in product-structure theory by exhibiting a clean geometric obstruction. The Heisenberg group was already proposed by Huang and McCarty as a candidate; the paper supplies a complete, self-contained argument that converts the analytic CKN theorem into a combinatorial non-embedding statement. All intermediate lemmas (extension, rounding, isometric tree embeddings into L1, compactness) are proved in full, constants are tracked explicitly, and the only external black box is a published theorem used verbatim. This is a high-quality negative result that clarifies the limits of tree-product structure for polynomial-growth graphs.","major_comments":[],"minor_comments":[{"comment":"In the definition of the Cayley graph (Definition 2.1) the third coordinate of the generators is written with a sign flip that is correct but slightly non-standard; a one-sentence remark that this is equivalent to the usual presentation would help readers coming from geometric group theory.","section":null},{"comment":"Lemma 2.2 claims f(r) ≤ 27 r^4; the elementary counting argument is correct, yet the constant 27 can be tightened without effort (e.g., (2r+1)^2 (2r^2+1) ≤ 8 r^4 + lower terms). A sharper constant is not needed for the main theorem but would make the growth statement cleaner.","section":null},{"comment":"In Corollary 3.2 the phrase “an absolute positive constant proportion” is left implicit; writing the proportion as \theta > 0 (depending only on the universal constants of CKN) would make the subsequent averaging steps easier to track.","section":null},{"comment":"Section 7 (compactness) is carefully written, but the “lazy walk” terminology and the pattern functions \rho_i^n could be illustrated with a short sentence or diagram for readers less familiar with inverse-limit constructions.","section":null},{"comment":"A few typographical points: “degree-d polynomial growth” is sometimes hyphenated inconsistently; the arXiv identifier in the header is future-dated (2607); and the AI-disclosure paragraph, while transparent, could be moved to an acknowledgement footnote.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is ready for acceptance essentially as is. The only external analytic input is the 2011 CKN theorem, which is independent of the combinatorial conjecture and is applied correctly. No novelty or citation concerns arise; the authors properly credit Huang–McCarty for the candidate examples. Fit for a top combinatorics journal is excellent."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper settles Conjecture 1.1 of Campbell–Distel–Gollin–Harvey–Hendrey–Hickingbotham–Mohar–Wood for d=4 in the negative. The counter-examples are finite subgraphs of the standard Cayley graph of the discrete Heisenberg group H(Z), which has growth O(r^4). Huang and McCarty had already flagged these graphs as candidates; the contribution is the first rigorous proof that they cannot embed into any strong product of four linear-growth trees plus a constant clique.\n\nWhat they do well is turn the Cheeger–Kleiner–Naor quantitative central-collapse theorem into a discrete counting obstruction. They extend a Lipschitz map from the word metric to L1, round back to the lattice while preserving central cosets, extract a large collapsed central set K of size M^{2}, thicken it by a short horizontal walk of length ~εM, and show that any putative product embedding would force the image of the thickened set to be smaller than its actual size. The constants are tracked explicitly (ε < 1/(49 C^{5/2}) produces the contradiction). Compactness via diagonal patterns on finite exhaustions then transfers the infinite obstruction to finite graphs. The argument is a transparent chain of reductions; every intermediate lemma is proved in full.\n\nThe only external black box is CKN 2011, used verbatim. That is not a soft spot: the theorem is independent, published for different reasons, and the paper never pretends otherwise. Minor technical points (the precise bi-Lipschitz constants between word and Carnot–Carathéodory metrics, the universal Lipschitz constant of the extension) are handled cleanly and do not affect the logic. No free parameters, no circularity, no hidden fitting.\n\nThis is for anyone working on product structure, polynomial-growth graphs, or the interface of geometric group theory with structural graph theory. It forces a revision of the expected form of product theorems once the degree exceeds 3. The math is solid, the citation pattern is appropriate, and the result is sharp enough that a serious editor should send it to referees without hesitation. I would engage with it and expect to cite the finite version (Theorem 7.2) when discussing the limits of tree products.","headline":"Clean, fully written disproof of the Campbell et al. tree-product conjecture for d=4 via Heisenberg Cayley graphs and CKN collapse; the chain holds.","tokens_in":17918,"tokens_out":563,"would_cite":true,"duration_ms":6039,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C75","05C12","20F65","46B85"],"pacs":[],"model":"grok-4.5","headline":"Finite pieces of the discrete Heisenberg group cannot sit inside any strong product of four linear-growth trees and a constant clique, disproving the tree-product conjecture for degree-4 growth.","keywords":["product structure","polynomial growth","Heisenberg group","tree product conjecture","central collapse","strong product","Cayley graph"],"falsifier":"Exhibit four trees of linear growth (or a finite approximation thereof) and a constant clique into which some large finite ball of the Heisenberg Cayley graph embeds isometrically as a strong-product subgraph; that single embedding would refute the claimed obstruction.","tokens_in":18046,"feed_emoji":"📐","tokens_out":661,"duration_ms":5597,"temperature":0.7,"pith_summary":"Product-structure theory asks whether graphs whose balls grow like a polynomial of degree d can always be drawn as subgraphs of a strong product of d linear-growth trees plus a bounded clique. The paper shows that the answer is already no when d equals 4. The counter-examples are finite subgraphs of a six-regular Cayley graph of the integer Heisenberg group; that infinite graph has growth at most 27 r to the fourth, yet no choice of four trees of linear growth and a fixed clique can contain a copy of it. The argument imports a deep analytic fact: every Lipschitz map from continuous Heisenberg space into L1 must collapse distances along a central line. After a careful discretisation, that collapse produces a combinatorial counting contradiction that rules out any such product embedding. A short compactness argument then transfers the obstruction from the infinite Cayley graph down to finite subgraphs, settling the conjecture in the negative for degree four.","feed_headline":"Heisenberg graphs kill the tree-product conjecture at d=4","feed_subtitle":"Finite pieces of a degree-4 Cayley graph refuse every strong product of four linear trees plus a clique","key_machinery":"Quantitative central collapse (Cheeger–Kleiner–Naor): every 1-Lipschitz map from a unit ball in the continuous Heisenberg group into L1 must shrink distances by a logarithmic factor along a positive-measure set of central segments; after discretisation and isometric L1 embeddings of trees this forces a volume contradiction inside any putative product embedding.","core_discovery":"There exists a Cayley graph of the discrete three-dimensional Heisenberg group whose growth function is at most 27 r^4 and which is not isomorphic to any subgraph of a strong product of four trees of linear growth and a constant-size clique; by compactness the same obstruction already appears among finite induced subgraphs, so the tree-product conjecture fails for d=4.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Heisenberg graphs kill tree-product conjecture for d=4","Cayley graphs of Heisenberg group refute d=4 tree products","Finite Heisenberg subgraphs disprove tree-product conjecture","Tree-product conjecture fails at d=4 via Heisenberg group","Degree-4 Heisenberg graphs escape four linear tree products"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The argument treats as given the analytic theorem that every Lipschitz map from continuous Heisenberg space into L1 collapses distances along a central line; if that collapse fails, the counting contradiction disappears.","fun_headline_variants_meta":{"raw":{"variants":["Heisenberg graphs kill tree-product conjecture for d=4","Cayley graphs of Heisenberg group refute d=4 tree products","Finite Heisenberg subgraphs disprove tree-product conjecture","Tree-product conjecture fails at d=4 via Heisenberg group","Degree-4 Heisenberg graphs escape four linear tree products"]},"model":"grok-4.5","effort":"low","cost_usd":0.006526,"raw_usage":{"total_tokens":1659,"prompt_tokens":761,"num_sources_used":0,"completion_tokens":85,"cost_in_usd_ticks":65260000,"prompt_tokens_details":{"text_tokens":761,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":813,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":761,"tokens_out":85,"duration_ms":6081,"temperature":1.0,"reasoning_tokens":813,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-12T05:15:46.560753+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit four trees of linear growth (or a finite approximation thereof) and a constant clique into which some large finite ball of the Heisenberg Cayley graph embeds isometrically as a strong-product subgraph; that single embedding would refute the claimed obstruction.","supporting_citations":[],"review_version":1}