{"id":"bd96399c-d041-46cb-94ba-8349a8cfded1","arxiv_id":"2506.11268","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Girth-8 regular bipartite graphs can be built with only O(sqrt(n)) check nodes, asymptotically optimal, using sequences free of three-term arithmetic progressions.","lead":"This paper derives lower bounds on the number of check nodes in regular bipartite graphs with girths 8 to 16, and presents two girth-8 graph constructions for LDPC codes. The second construction uses integer sequences without arithmetic progressions to achieve an asymptotically optimal number of check nodes, which could inform high-rate code design.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The semi-regular construction cannot have m=O(√n): any 3-AP-free sequence of length t has b_t=ω(t) by Roth's theorem, so m=4t+2b_t−3 is not O(t).","rationale":"The reader's weakest point was the unsupported girth-10–16 inequalities. That is a genuine gap, but the central claim — the semi-regular girth-8 construction with m=O(√n) — has a much more serious problem: the asymptotic statement is not merely unproved, it is inconsistent with known extremal bounds on 3-AP-free sets. The girth proof in Proposition 5 forces b to be 3-AP-free; any such sequence of length t has last element b_t=ω(t) by Roth's theorem, so m=4t+2b_t−3 is ω(t). Therefore the claimed match with Theorem 1 up to a constant fails. This is a falsifiable, mathematical error, not a missing case analysis. The lower bound in Theorem 1 and the greedy regular construction may survive, but the advertised highlight of the paper — a sublinear, asymptotically optimal girth-8 construction — does not. A revision could weaken the claim to m=n^{1/2+o(1)} and still present a sublinear construction, but the paper as written asserts m=O(√n) and 'asymptotically optimal', which is false. Because the strongest claim is contradicted by known results rather than simply underproved, I would move the verdict from CONDITIONAL to REJECT.","tokens_in":8927,"tokens_out":16434,"duration_ms":176145,"concrete_test":"Analytical test: Let B_t={b_1,...,b_t}. If the claimed m=O(t) held, then for some C>0 and all large t, b_t ≤ C t. But B_t is a 3-AP-free subset of [C t] of size t, so t ≤ r(C t). Roth's theorem gives r(C t)=o(C t), hence t=o(t) for large t, a contradiction. Therefore b_t/t is unbounded, and m=4t+2b_t−3=ω(t). This settles the issue without computation. As a supplementary check, compute the greedy 3-AP-free sequence up to t=2^14 and plot b_t/t; the ratio will grow, corroborating the analytic contradiction, but the Roth argument is decisive.","verdict_should_be":"REJECT","load_bearing_attack":"The load-bearing flaw is in Section IV. Proposition 5 proves girth 8 only if the sequence b is free of 3-term arithmetic progressions, i.e., {b_1,...,b_t} is 3-AP-free. Remark 5 then concludes m=4t+2b_t−3=O(t), so m=O(√n) with n=t^2, matching Theorem 1 up to a constant. This conclusion is false. Since the increasing sequence has t distinct positive integers, B_t = {b_1,...,b_t} is a 3-AP-free subset of [b_t] of size t. By Roth's theorem, the maximum such size in [M] is o(M). If b_t ≤ C t, then B_t would have density at least 1/C in [C t], contradicting r(C t)=o(C t). Hence b_t/t → ∞, and m/t = 4 + 2b_t/t − 3/t → ∞. Thus m is not O(t), and the construction does not achieve the claimed constant-factor-optimal m=O(√n). The mistake enters in Remark 5 when the Behrend lower bound r(M) ≥ M^{1−o(1)} is read as 'nearly linear'; the inverse of any sublinear function is superlinear, so the minimal M for t elements is t^{1+o(1)}, not O(t). The construction may still give girth 8 with m=n^{1/2+o(1)} check nodes, but that is a weaker, subpolynomially-worse result and does not match the O(√n) lower bound up to a constant.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the relation between the number of check nodes m and variable nodes n in regular bipartite graphs with prescribed girth. It derives a lower bound for girth 8 in Theorem 1, states order-wise bounds for girths 10, 12, 14, and 16, and presents two girth-8 constructions: a (w_c, w_r)-regular graph with minimum distance 2w_c, and a semi-regular graph built from a 3-arithmetic-progression-free integer sequence. The semi-regular construction is claimed to achieve m = O(√n) check nodes, matching the lower bound up to a constant.","tokens_in":9292,"tokens_out":18954,"duration_ms":189020,"significance":"The girth-8 lower bound in Theorem 1 is derived rigorously and is a useful addition to the literature. The regular construction with d_min = 2w_c is a solid, explicit construction. The semi-regular construction is a creative application of 3-AP-free sequences, but its central asymptotic claim is not supported: as discussed below, the construction actually yields m = n^{1/2+o(1)}, not m = O(√n). After correcting this claim, the construction remains a valid sublinear-redundancy construction, but the advertised order-optimality is lost.","major_comments":[{"comment":"The inference that M = O(t) from Theorem 4 is invalid. Theorem 4 is a lower bound on r(M); since {b_1, ..., b_t} is a 3-AP-free subset of [b_t] of size t, Roth's theorem gives r(b_t) = o(b_t), so b_t / t → ∞. Consequently m = 4t + 2b_t - 3 = ω(t), and with n = t^2 this means m = n^{1/2+o(1)}, not O(√n). The claim in Remark 5 and the abstract that the construction is asymptotically optimal is therefore unsupported and must be revised.","section":"Section IV, Remark 5"},{"comment":"The stated row range for Level 3 is inconsistent with the formula for r3j. For a_j = t and b_{i_j} = b_t, we get r3j = (√n - 1 + b_t) + t + (√n - 1 + b_t + t) = 4t + 2b_t - 2, which exceeds the declared last row 4t + 2b_t - 3 by one. The constant c2 should be √n - 2 + b_t for the construction to fit the declared m rows; without this correction, the matrix has a 1 outside its stated dimensions.","section":"Section IV, Definition 3"},{"comment":"The inequalities for girths 10, 12, 14, and 16 are stated without derivation, and the coefficients a_{i,j} in the polynomials P_G(m) are not specified. Because the order-wise bounds (7)-(10) rest on these inequalities, the authors should either provide the double-counting argument in the style of Theorem 1 or cite a reference for each inequality. As written, the reader cannot verify the claimed m = O(n^{2/3}) and m = O(n^{3/4}) results.","section":"Section II.B, Step 1"}],"minor_comments":[{"comment":"The WLOG reduction in the 6-cycle proof is not justified. The authors should explain why any 6-cycle can be relabeled so that the shared rows are r1p = r1q, r2q = r2ℓ, and r3p = r3ℓ; in particular, they should rule out the possibility that two of the three shared rows lie in the same level.","section":"Section IV, Proposition 5"},{"comment":"The proof of d_min = 2w_c is only worked out for w_c = 3; the general case is dismissed as 'straightforward using induction' without details. A sketch of the induction step would make the claim verifiable.","section":"Section III, Proposition 3"},{"comment":"There are several typographical issues: 'tanner graph' in Proposition 5 should be 'Tanner graph', 'qubic' in Section II.B should be 'cubic', and the girth notation G=8 appears with inconsistent spacing in a few places.","section":"Throughout"},{"comment":"The example in Fig. 2 does not state the resulting matrix dimensions or verify the row ranges from Definition 3; given the off-by-one issue in the row ranges, such a verification would be helpful.","section":"Section IV, Example 2"}],"recommendation":"major_revision","confidential_remarks":"The paper's headline contribution is the claimed order-optimal semi-regular construction. Since that claim is false, the revised paper will be considerably more modest. The lower bound and regular construction are correct and may justify publication after the asymptotic claims are corrected and the construction's row-range issue is fixed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline is that the main advertised result does not hold. Remark 5 reads Behrend's lower bound as \"nearly linear\" and concludes the maximum element b_t of a 3-AP-free sequence of length t is O(t). That is the wrong direction: r(M) = o(M), so a 3-AP-free subset of [b_t] of size t forces b_t/t → ∞. Hence m = 4t + 2b_t − 3 is not O(t), and with n = t^2 the construction gives m = n^{1/2+o(1)}, not O(√n). The abstract and Section IV claim this construction is asymptotically optimal matching the lower bound up to a constant; that is false.\n\nThe paper is not without merit. Theorem 1's girth-8 lower bound is clean and correctly derived by tree counting; it is tight for w_c=2 and a reasonable contribution. The regular construction in Section III is genuinely new: girth 8 with minimum distance 2^{w_c} is a real improvement over the usual linear bound. The proof is terse—worked out only for w_c=3, with the general case hand-waved as induction—but the core idea is plausible.\n\nThe soft spots are real but secondary. The bounds for girths 10–16 are asserted with unspecified coefficients a_{i,j} and no derivation of the listed inequalities, so the claimed m = O(n^{2/3}) and O(n^{3/4}) are not actually supported. Proposition 5's 6-cycle argument also skips some distinctness case analysis, though the main contradiction seems structurally sound.\n\nThe load-bearing flaw is the asymptotic claim in the semi-regular section. If the authors reframe the result as m = n^{1/2+o(1)}, the construction is still interesting and close to the lower bound, but it is not constant-factor optimal. I would send this to peer review: a good referee will catch the Roth error and force a correcting rewrite, and the remaining material is worth salvaging. I would not cite the current version, but I would read a revised one.","headline":"The paper's advertised constant-factor optimal semi-regular construction is wrong—Roth's theorem forces b_t/t to superlinear—but the girth-8 lower bound and the regular construction still deserve a serious revision.","tokens_in":9796,"tokens_out":3451,"would_cite":false,"duration_ms":40917,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C35","05C38"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes lower bounds on the number of check nodes in girth-constrained regular bipartite graphs and constructs a semi-regular family with girth 8 that has only $O(\\sqrt{n})$ check nodes, matching the bound up to a constant…","keywords":["regular bipartite graphs","girth","LDPC codes","check node count","three-term arithmetic progression","semi-regular graphs","high-rate codes","minimum distance"],"falsifier":"Construct the semi-regular $H_s$ for a fixed $t$ using a verified free-3-AP sequence and run a brute-force search over all 4- and 6-cycles in the Tanner graph; the presence of any such cycle falsifies Proposition 5's girth-8 claim.","tokens_in":8740,"feed_emoji":"📐","tokens_out":10007,"duration_ms":100010,"temperature":0.7,"pith_summary":"This paper asks how many check nodes a regular bipartite graph must have, for a given number of variable nodes and a given shortest cycle length (girth). It proves that for girth 8 the check count must grow at least like the square root of the variable count, and for girths 10, 12, 14, and 16 it must grow at least like $n^{2/3}$ or $n^{3/4}$, respectively. On the construction side, the paper gives two girth-8 families: a regular one whose minimum distance is $2^{w_c}$, and a semi-regular one built from integer sequences with no three-term arithmetic progression that achieves $m = O(\\sqrt{n})$ check nodes, matching the lower bound up to a constant factor. These constructions yield sparse parity-check matrices for high-rate codes, with the semi-regular family approaching rate 1 as the block length grows.","feed_headline":"Girth-8 graphs built with O(sqrt n) checks","feed_subtitle":"Using integers with no three in arithmetic progression, the construction hits the girth-8 lower bound.","key_machinery":"The load-bearing object for the semi-regular construction is the three-level parity-check matrix $H_s$: column $j$ receives its three 1s at row positions given by affine functions of a free-3-AP integer sequence $b$, namely $r_{1j}=a_j$, $r_{2j}=c_1+b_{i_j}+a_j$, and $r_{3j}=c_2+a_j+r_{2j}$. A 6-cycle in the Tanner graph would reduce to the equation $b_p+b_\\ell = 2b_q$, so the no-3-AP property of $b$ is exactly what rules out 6-cycles. For the bounds, the machinery is the standard rooted-tree count: with girth $2\\ell$, a height-$\\ell$ tree rooted at a check node contains distinct vertices, and double-counting the edges from the last layer yields polynomial inequalities in $m$ and $n$ that are solved, exactly for girth 8 and order-wise for girths 10 through 16.","core_discovery":"The central claim is that girth-8 bipartite graphs can be both regular in column weight and sublinear in check-node count: for $n = t^2$ variable nodes, the semi-regular Tanner graph $H_s$ has only $4t + 2b_t - 3$ check nodes, where $b_t$ is the $t$-th term of a free 3-AP sequence, and since $r(M)$ is nearly linear in $M$, this means $m = O(\\sqrt{n})$. The paper proves the girth is exactly 8 by showing that any candidate 6-cycle would force three sequence elements to satisfy $b_p + b_\\ell = 2b_q$, contradicting the absence of length-3 arithmetic progressions. It further establishes a matching lower bound for any girth-8 regular bipartite graph: with column weight $w_c$, variable count $n$, and check count $m$, one must have $m \\geq \\frac{-w_c(w_c-2) + w_c\\sqrt{(w_c-2)^2+4(w_c-1)n}}{2}$. Order-wise lower bounds $m = \\Omega(n^{2/3})$ for girths 10 and 12, and $m = \\Omega(n^{3/4})$ for girths 14 and 16, are also claimed.","pith_inferences":["A natural next step, not taken in the paper, is to generalize the semi-regular construction to column weights larger than 3; using higher-order AP-free sets may preserve girth 8 with $m = O(\\sqrt{n})$ while increasing the minimum distance.","The paper's bounds for girths 10 through 16 rest on a table of counting inequalities that is asserted without derivation; verifying or repairing those inequalities would either strengthen confidence in the $n^{2/3}$ and $n^{3/4}$ thresholds or reveal a gap.","The connection between 3-AP-free sets and Tanner graphs suggests a direct pipeline: any improvement in lower bounds for $r(M)$ immediately improves the constant in the $m = O(\\sqrt{n})$ construction, and near-optimal empirical sequences could be used to build finite-length high-rate codes.","If the $d_{\\min} = 2^{w_c}$ claim for the regular construction holds, it gives an explicit trade-off between girth 8 and exponentially growing minimum distance, which could translate into better trapping-set behavior for high-rate LDPC codes."],"forward_implications":["For girth 8 and column weight 2, the lower bound is tight and is met by the base matrix of fair-density parity-check codes, as noted in Remark 1.","Any regular bipartite graph with girth 10 or 12 needs $m = \\Omega(n^{2/3})$ check nodes, and with girth 14 or 16 needs $m = \\Omega(n^{3/4})$ check nodes, so increasing girth forces a polynomial increase in redundancy.","The semi-regular construction gives codes with rate $R = 1 - m/n \\to 1$ as the block length grows while maintaining girth 8, per Remark 5.","The regular construction produces girth-8 codes whose claimed minimum distance is $2^{w_c}$, growing exponentially in the column weight, compared to the linear lower bound for general girth-8 LDPC codes."],"supporting_citations":[{"why":"Supplies the existing bounds on 4- and 6-cycle-free bipartite graphs that the girth-8 lower bound refines.","marker":"[12]"},{"why":"Gives a prior bound on even-cycle-free graphs against which the order-wise results are compared.","marker":"[13]"},{"why":"Introduces fair-density parity-check codes, the high-rate motivation and the $w_c=2$ case where the girth-8 bound is tight.","marker":"[14]"},{"why":"Provides earlier constructions of graphs with prescribed girth and bi-degree, used as a complexity benchmark in Remark 3.","marker":"[16]"},{"why":"Contains the theorem that girth-8 Tanner graphs with column weight 3 have minimum distance at least 6, used in Proposition 5.","marker":"[17]"},{"why":"Behrend's lower bound on the size of 3-AP-free sets is the basis for the near-linear $r(M)$ used in Theorem 4.","marker":"[19]"},{"why":"Offers near-optimal finite 3-AP-free sequences used to instantiate the semi-regular construction.","marker":"[20]"},{"why":"Together with [19] establishes the growth of $r(M)$ quoted in Theorem 4.","marker":"[21]"}],"fun_headline_variants":["Girth-8 graphs with O(sqrt n) checks via 3-AP-free sets","3-AP-free integers give optimal girth-8 bipartite graphs","Sublinear checks for girth-8 regular bipartite graphs","Girth-8 graphs hit lower bound with O(sqrt n) checks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For girths 10 through 16, the claimed bounds depend on a table of counting inequalities that the paper lists but does not prove, and whose polynomial coefficients are left unspecified.","fun_headline_variants_meta":{"raw":{"variants":["Girth-8 graphs with O(sqrt n) checks via 3-AP-free sets","3-AP-free integers give optimal girth-8 bipartite graphs","Sublinear checks for girth-8 regular bipartite graphs","Girth-8 graphs hit lower bound with O(sqrt n) checks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001045,"raw_usage":{"total_tokens":4448,"prompt_tokens":1054,"completion_tokens":3394,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":670,"completion_tokens_details":{"reasoning_tokens":3311}},"tokens_in":670,"tokens_out":3394,"duration_ms":28544,"temperature":1.0,"reasoning_tokens":3311,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T04:13:14.214359+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct the semi-regular $H_s$ for a fixed $t$ using a verified free-3-AP sequence and run a brute-force search over all 4- and 6-cycles in the Tanner graph; the presence of any such cycle falsifies Proposition 5's girth-8 claim.","supporting_citations":[{"cited_title":"De Caen and L","cited_arxiv_id":null,"evidence_quote":"Supplies the existing bounds on 4- and 6-cycle-free bipartite graphs that the girth-8 lower bound refines."},{"cited_title":"Graphs without cycles of even length,","cited_arxiv_id":null,"evidence_quote":"Gives a prior bound on even-cycle-free graphs against which the order-wise results are compared."},{"cited_title":"Graphs of prescribed girth and bi-degree,","cited_arxiv_id":null,"evidence_quote":"Provides earlier constructions of graphs with prescribed girth and bi-degree, used as a complexity benchmark in Remark 3."},{"cited_title":"Progressive edge-growth tanner graphs,","cited_arxiv_id":null,"evidence_quote":"Contains the theorem that girth-8 Tanner graphs with column weight 3 have minimum distance at least 6, used in Proposition 5."},{"cited_title":"On sets of integers which contain no three terms in arithmetical progression,","cited_arxiv_id":null,"evidence_quote":"Behrend's lower bound on the size of 3-AP-free sets is the basis for the near-linear $r(M)$ used in Theorem 4."},{"cited_title":"Sequences containing no 3-term arithmetic progres- sions,","cited_arxiv_id":null,"evidence_quote":"Offers near-optimal finite 3-AP-free sequences used to instantiate the semi-regular construction."},{"cited_title":"Finding large 3-free sets i: The small n case,","cited_arxiv_id":null,"evidence_quote":"Together with [19] establishes the growth of $r(M)$ quoted in Theorem 4."}],"review_version":1}