{"id":"a510da30-4b98-4941-a613-53a9811cc9ff","arxiv_id":"2507.01138","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Random d-regular graphs have sum-sets of size n^{1-2/d} for every abelian group, proving a polynomial lower bound that is tight up to polylog factors.","lead":"Random d-regular graphs have sum-sets of size n^{1-2/d} over every abelian group, far larger than the logarithmic lower bound for worst-case expanders. The result is tight up to polylog factors and shows typical sparse graphs behave very differently from expanders.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 3.3's lattice-counting proof rests on a false 'integer volume' assertion; the step bound can likely be repaired, so the lower-bound proof is conditional on that repair.","rationale":"The paper's main new result is that random d-regular graphs have polynomial-size sum-sets over every abelian group, and the proof is a delicate union bound over groups and injections. The reduction in Claim 3.2 to quotient groups Z^k/Span(f_1,...,f_m) is clear, but the subsequent lattice-counting estimate in Claim 3.3 is the hinge: without a bound of the form k^{O(k D log D)} on the number of such quotients, the union bound over groups cannot be closed. The reader correctly isolated the false sentence 'the volume of any lattice is an integer' in Claim 3.3. My own reading confirms that the issue is not merely cosmetic: the 'reduces the volume by at least half' rule is also misapplied, since rank-increasing steps can increase the relevant volume. Nevertheless, the intended bound appears salvageable by a standard lattice-index argument, where each same-rank strict extension corresponds to an integer index of at least 2, and each rank increase is charged only O(k log D) overall. Because the fix is local and the rest of the proof is detailed and coherent, the appropriate posture remains conditional: accept only after Claim 3.3 is repaired or replaced with a correct derivation of the same counting bound. The concrete test above is the minimal check that would settle whether the flaw is harmless or fatal.","tokens_in":18473,"tokens_out":15314,"duration_ms":151813,"concrete_test":"Re-derive the step bound in Claim 3.3 using the three facts: (i) every nonzero lattice generated by integer vectors has r-volume at least 1; (ii) a proper same-rank sublattice has integer index at least 2; (iii) adjoining a vector of L1-norm less than 3D to increase rank multiplies the r-volume by at most 3D. If this yields t ≤ k(2+log D), Claim 3.3's bound, and hence the union bound in Section 3.2, stands. If the resulting exponent is instead k^2 log D, the proof of Theorem 3.1 fails in its present form and needs a different counting argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central lower bound (Theorem 3.1) depends on Claim 3.3's bound |F| ≤ k^{C k D log D}, which feeds the union bound over all abelian groups and injections. The proof of Claim 3.3 asserts that 'the volume of any lattice is an integer' and that adding any generator that changes the lattice 'reduces the volume by at least half.' Both statements are false as written. A rank-r lattice in Z^k generated by integer vectors has r-volume sqrt(det(Gram)), which need not be an integer, e.g., the rank-1 lattice spanned by (1,1) has length sqrt(2). Moreover, adding a vector that raises the rank from r to r+1 can multiply the volume by a factor as large as 3D, not divide it. What is true is: (i) the r-volume is at least 1, (ii) a proper same-rank extension divides the volume by an integer index at least 2, and (iii) a rank-increasing step multiplies the volume by at most 3D. These facts give at most k + log((3D)^k) + k log(3D) = O(k log D) steps, so the stated bound is plausibly correct. But the proof as printed does not supply this argument, and the entire lower bound is pinned to this counting estimate. The claim should be explicitly re-proved with the corrected volume/index accounting.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies, for a graph G and an abelian group H, the minimum size S_H(G) of the set of edge sums A(u)+A(v) over all injections A: V(G) -> H, and the worst-case-over-groups quantity S(G). The main result (Theorem 1.1) states that for a random d-regular graph G_{n,d}, with high probability S(G_n) = Omega(n^{1-2/d}) for every abelian group when 3 <= d <= ln n / ln ln n, and that this is tight up to a polylogarithmic factor; it also determines the asymptotics for larger d, including the near-full regime S(G_n) = n(1-o(1)) for d = omega(ln^2 n). Theorem 1.2 provides a universal Cayley sum-graph with O(n^{1-2/d} d^2 (ln n)^{2+4/d}) edges that contains every n-vertex graph of maximum degree d, and an elementary upper bound S(G) <= n - ceil(n/(2d)) + 1 for all graphs. The lower-bound proof reduces an arbitrary abelian group and injection to a canonical quotient Z^k/Span(f_1,...,f_m) with bounded L1-norm generators (Claim 3.2), then bounds the number of such lattices (Claim 3.3) and combines this with expansion and counting arguments for random regular graphs.","tokens_in":18699,"tokens_out":18358,"duration_ms":197359,"significance":"If the results are correct, they resolve a natural question left open by Alon--Angel--Benjamini--Lubetzky on sum-sets of sparse graphs: random d-regular graphs have polynomially large sum-sets for all abelian groups, in sharp contrast with the logarithmic worst-case for expanders, and the bounds are tight up to polylog factors. The paper also provides an explicit universal Cayley sum-graph construction and a clean second-order term for large d. The proofs are detailed and the main theorems are quantitative and falsifiable; the paper ships explicit constructions (Cayley expanders and universal graphs) and relies on standard external theorems for random regular graph counts, edge-disjoint placement, and the Hajnal--Szemerédi theorem, rather than on any fitted parameters. The central claims are likely correct, but one load-bearing lattice-counting argument in Claim 3.3 contains a flawed sentence that must be repaired before the lower bound can be considered fully justified.","major_comments":[{"comment":"The proof of Claim 3.3 relies on the sentence: 'It remains to recall that the volume of any lattice is an integer and that adding any element that changes the lattice reduces the volume by at least half.' Both assertions are false for the lattices considered here, which are rank-r sublattices of Z^k with r possibly less than k: the r-volume is sqrt(det(Gram)) and need not be an integer (e.g., the lattice spanned by (1,1) in Z^2 has volume sqrt(2)), and adding a vector that increases the rank can multiply the volume by a factor up to 3D rather than divide it. Because the bound |F| <= k^{C k D log D} feeds directly into the union bound over canonical groups in the proof of Theorem 3.1, this is a load-bearing gap. The claim is plausibly correct and can be repaired: a proper same-rank extension divides the volume by an integer index at least 2, a rank-increasing step increases the rank by 1 and can be charged against the initial bound Vol(L_r) <= (3D)^r, and every such lattice has volume at least 1; these facts yield the step bound t <= k(2+log D). Please replace the flawed sentence with this corrected volume/index accounting or with an equivalent citation.","section":"Section 3.1, Claim 3.3"}],"minor_comments":[{"comment":"In the displayed chain after the union bound, the factor n!/2^n is not the number of n-cycles on [n]; the correct count is (n-1)!/2. The subsequent sufficient condition (5) uses n^n as an upper bound, so the argument survives if the equality is replaced by an inequality with n^n or by the exact count.","section":"Section 3.2"},{"comment":"In the proof of Claim 3.5, the text says 'the number of (d-2)-regular graphs on [n] equals gd(n)' but the displayed asymptotic formula is for g_{d-2}(n); the subscript should be corrected.","section":"Section 3.2, Claim 3.5"},{"comment":"There is a typo in the phrase 'Nethertheless' in the lattice background subsection; it should read 'Nevertheless'.","section":"Section 2.2"},{"comment":"The proof-strategy paragraph repeats the flawed Claim 3.3 assertion ('at every step, we get a lattice with an integer volume, and every step reduces the volume by at least half'); it should be updated in tandem with the corrected Claim 3.3 argument.","section":"Section 1, Proof strategy"}],"recommendation":"major_revision","confidential_remarks":"This is a strong paper and the central theorems are likely correct. The main issue is the flawed lattice-volume sentence in Claim 3.3; since the repair is short and uses only standard facts about sublattice indices and volumes, I do not view it as grounds for rejection. I would ask the authors to provide the corrected argument explicitly rather than simply citing around it. The cycle-count typo in Section 3.2 should also be fixed, though it does not affect the validity of the bound because the proof already uses the coarser n^n upper bound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline is simple: this is a strong paper with one load-bearing but fixable gap. The result answers a natural question from Alon–Angel–Benjamini–Lubetzky: random d-regular graphs have sum-sets of size n^{1-2/d} for every abelian group, up to polylog factors, in sharp contrast to the logarithmic worst case for expanders. The proof strategy is genuinely new — reduce the infinite family of abelian groups to quotient groups Z^k/F with generators of bounded L1-norm, then union-bound over a small set of lattices. The matching upper bound via a universal Cayley sum-graph, and the handling of the large-d regime, are also real contributions. The paper is well-written and honest about its reliance on external machinery (random regular graph diameter, enumeration, Hajnal–Szemerédi, Sauer–Spencer, Alon–Capalbo), and the citation pattern is fine.\n\nThe soft spot is Claim 3.3. The proof asserts that the volume of any lattice is an integer and that adding a vector which changes the lattice reduces the volume by at least half. Both statements are false as written: a rank-1 lattice in Z^2 spanned by (1,1) has volume sqrt(2), and adding a vector that raises the rank can multiply the volume by up to 3D. The bound is still salvageable — same-rank proper extensions have integer index at least 2, so they only happen O(k log D) times; rank-increasing steps occur at most k times and multiply the volume by at most 3D. That yields the same O(k log D) count, but the argument in the paper does not make this distinction. Since the union bound over groups is pinned to this counting estimate, the lower-bound proof is conditional on this repair. It is a genuine gap, not a typo, though clearly not a fatal one.\n\nWho is this for? Anyone working on extremal combinatorics, additive combinatorics, or random graphs. The technique of reducing all abelian groups to a small lattice family will likely propagate. The paper deserves a serious referee; I would send it out and require the authors to re-prove Claim 3.3 with the correct volume/index accounting before acceptance.","headline":"The main result is real — random d-regular graphs have sum-sets of size n^{1-2/d} for every abelian group — but the proof of Claim 3.3 contains a false lattice-volume assertion that needs a repair before the lower bound is fully rigorous.","tokens_in":19278,"tokens_out":4839,"would_cite":true,"duration_ms":59917,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","05C25","05C35","11H06"],"pacs":[],"model":"deepseek-v4-flash","headline":"Random d-regular graphs have edge-sum sets of size at least n^{1-2/d} over every abelian group.","keywords":["sum-sets","random regular graphs","abelian groups","Cayley sum-graphs","lattices","universal graphs","expander graphs","bounded degree graphs"],"falsifier":"For k=2 and D=1, the vector (1,1) spans a rank-1 lattice of volume $\\sqrt$(2), violating the paper's assertion that lattice volumes are integers; checking Claim 3.3 computationally for small k and D by counting distinct spans of vectors with L1 norm at most 3D and comparing with $k^{{C k D log D}}$ would settle whether the counting bound holds as stated.","tokens_in":18241,"feed_emoji":"🔢","tokens_out":6276,"duration_ms":68712,"temperature":0.7,"pith_summary":"The paper asks how few distinct values can appear as sums A(u)+A(v) along the edges of an n-vertex graph, where A injects the vertices into an abelian group. The authors prove that a random d-regular graph is extremely incompressible in this sense: with high probability, every injection into every abelian group produces at least c $n^{{1-2/d}}$ distinct edge sums, for constant d ≥ 3. This lower bound is tight up to a polylogarithmic factor, and it implies that for every ε > 0 there is a regular graph with O(n) edges whose edge-sum set has size at least $n^{{1-ε}}$ over all abelian groups. The result shows that the earlier logarithmic bound for expanders is far from what typical regular graphs achieve.","feed_headline":"Random regular graphs force edge-sum sets of size n^(1-2/d)","feed_subtitle":"A sparse graph with O(n) edges can encode at least n^(1-ε) distinct edge sums over any abelian group.","key_machinery":"The lower-bound proof reduces an arbitrary injection A : V(G) → H to a canonical quotient group Z^k / Span(f_1, ..., f_m), where k is the number of distinct edge sums and each generator f_t has L1 norm at most 3D for a graph of diameter D. Claim 3.3 bounds the number of distinct lattices generated by such vectors by $k^{{C k D log D}}$, which makes a union bound over all groups possible. The matching upper bound is produced by an explicit Cayley sum-graph, built as a modification of a sparse universal graph construction, that contains every n-vertex graph of maximum degree d and whose generating set has size O($n^{{1-2/d}}$ $d^{2}$ (ln n)^{2+4/d}).","core_discovery":"The central claim is Theorem 1.1: for a uniformly random d-regular graph G_n on n vertices, the quantity S(G_n), defined as the minimum, over all abelian groups, of the number of distinct edge sums under an injective vertex labeling, satisfies c $n^{{1-2/d}}$ ≤ S(G_n) ≤ $n^{{1-2/d}}$ $ln^{4}$ n with high probability, for every 3 ≤ d ≤ ln n / ln ln n and a universal constant c > 0. In particular, for every ε > 0 there exists a regular graph with O(n) edges whose sum-set has size at least $n^{{1-ε}}$ over every abelian group. The paper also proves a matching upper bound for arbitrary graphs of maximum degree d, and it determines the near-extremal behavior for large d: when d ≫ $ln^{2}$ n, S(G_n) = n(1-o(1)), and more precisely n(1 - C $ln^{2}$ n / d) ≤ S(G_n) ≤ n(1 - c/d).","pith_inferences":["The gap in Claim 3.3's volume-counting argument appears repairable by replacing the false assertion that every lattice volume is an integer with the fact that a proper inclusion of equal-rank lattices has integer index at least 2; the stated polynomial bounds would then survive unchanged.","The reduction to quotient groups Z^k / Span(f_1, ..., f_m) is a general tool that could apply to other edge-labeling problems where one must rule out all abelian groups at once.","The proof suggests that, among bounded-degree graphs, sum-set size may be governed primarily by n^{1-2/d} and by diameter rather than by expansion alone; comparing Ramanujan graphs with random regular graphs of the same degree would test this directly.","A computational check of Claim 3.3 for small k and D, counting distinct spans of integer vectors with L1 norm at most 3D, would give a concrete sanity check for the union-bound step."],"forward_implications":["For every ε > 0, there is a regular graph with O(n) edges whose edge-sum set has size at least n^{1-ε} over every abelian group.","Random d-regular graphs are essentially extremal: among all n-vertex graphs with maximum degree d, they attain the largest possible sum-set up to a polylogarithmic factor, for 3 ≤ d ≤ ln n / ln ln n.","For d ≫ ln^2 n, a random d-regular graph has sum-set n(1-o(1)), so almost every possible edge sum can be forced to occur.","The lower bound c n^{1-2/d} is matched by the universal upper bound n^{1-2/d}(log n)^4 in the stated range, so no graph with maximum degree d can do much better.","The logarithmic barrier for expanders is not the right order for typical regular graphs; random regular graphs exhibit polynomial-sized sum-sets."],"supporting_citations":[{"why":"Establishes the original sum-set problem for expanders and proves the logarithmic lower bound that this paper supersedes.","marker":"[1]"},{"why":"Provides the sparse universal graph construction that the paper modifies to obtain a universal Cayley sum-graph.","marker":"[2]"},{"why":"Supplies the explicit Cayley expander used as the initial expander Z in the universal graph construction.","marker":"[3]"},{"why":"Used together with [26] to prove the second part of Theorem 1.2 via edge-disjoint placement of graphs.","marker":"[12]"},{"why":"Supplies the edge-disjoint placement theorem used to prove the linear upper bound for arbitrary abelian groups.","marker":"[26]"},{"why":"Give the asymptotic count of d-regular graphs and the edge-avoidance probabilities used throughout the lower-bound proof.","marker":"[22, 23]"},{"why":"Supply the diameter and Hamiltonicity bounds for random regular graphs that set D = O(log n / log d) in the reduction.","marker":"[8, 18, 25]"},{"why":"Provide the sandwiching coupling used to extend the lower bound to d > sqrt n.","marker":"[14, 15]"}],"fun_headline_variants":["Random d-regular graphs force Ω(n^{1-2/d}) distinct edge sums","Edge sums on random regular graphs: lower bound n^{1-2/d} for any group","Sparse graphs with O(n) edges yield n^{1-ε} edge sums over any abelian group","For random d-regular graphs, edge-sum sets are at least n^{1-2/d}"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower-bound proof's lattice-counting step assumes that every enlargement of a lattice cuts its volume by at least half, because volumes are asserted to be integers; for lower-dimensional lattices this is false, so the counting step as written has a gap.","fun_headline_variants_meta":{"raw":{"variants":["Random d-regular graphs force Ω(n^{1-2/d}) distinct edge sums","Edge sums on random regular graphs: lower bound n^{1-2/d} for any group","Sparse graphs with O(n) edges yield n^{1-ε} edge sums over any abelian group","For random d-regular graphs, edge-sum sets are at least n^{1-2/d}"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000411,"raw_usage":{"total_tokens":2243,"prompt_tokens":1171,"completion_tokens":1072,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":787,"completion_tokens_details":{"reasoning_tokens":972}},"tokens_in":787,"tokens_out":1072,"duration_ms":11879,"temperature":1.0,"reasoning_tokens":972,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T20:59:39.189323+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For k=2 and D=1, the vector (1,1) spans a rank-1 lattice of volume $\\sqrt$(2), violating the paper's assertion that lattice volumes are integers; checking Claim 3.3 computationally for small k and D by counting distinct spans of vectors with L1 norm at most 3D and comparing with $k^{{C k D log D}}$ would settle whether the counting bound holds as stated.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the original sum-set problem for expanders and proves the logarithmic lower bound that this paper supersedes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the sparse universal graph construction that the paper modifies to obtain a universal Cayley sum-graph."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the explicit Cayley expander used as the initial expander Z in the universal graph construction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Used together with [26] to prove the second part of Theorem 1.2 via edge-disjoint placement of graphs."},{"cited_title":"Sauer, J","cited_arxiv_id":null,"evidence_quote":"Supplies the edge-disjoint placement theorem used to prove the linear upper bound for arbitrary abelian groups."}],"review_version":1}