{"id":"95f1cad7-883c-4300-a425-d8eda89c9557","arxiv_id":"2501.11855","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A new combinatorial structure, non-half-sum disjoint packing, yields coded caching schemes with F=K linear subpacketization and transmission load R=product of block counts, improving on several earlier linear-subpacketization designs.","lead":"This paper introduces a new combinatorial object, non-half-sum disjoint packing, and uses it to build coded caching schemes whose file subpacketization grows only linearly with the number of users. The resulting schemes can achieve lower transmission load than previously known linear-subpacketization schemes, and the new object connects to classic structures like cyclic difference packings, non-three-term arithmetic progressions, and perfect hash families.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Appendix C's equation (25) gives the block index range as a ∈ [q]^n, but Construction 2 and Lemma 3 require a ∈ [(q−1)/2]^n; with q=5, n=2 the wrong range makes half-sums reappear, so the proof of Theorem 3 is internally inconsistent as written.","rationale":"The paper's central mathematical construction, Theorem 1 and Lemma 3, is essentially sound: the dominance inequality x_{i+1} > 2∑_{j≤i} a_j x_j follows from the definition of the f(i) and a_j ≤ m_j, and Theorem 1's PDA verification is correct. The reader's verdict of CONDITIONAL is therefore appropriate. The most load-bearing weakness is not the construction itself but an internal inconsistency in the proof of Theorem 3's optimal solution: equation (25) in Appendix C extends the block index to [q]^n instead of [(q−1)/2]^n. Taken literally, this breaks the dominance condition and makes the non-half-sum property fail, as the q=5, n=2 counterexample shows. The same equation underpins Remark 2 and parts of Section VI, so it matters for the claimed optimality and for the NTAP/PHF applications. The error is likely a typo, since the surrounding text and Theorem 3 use m_i = (q−1)/2, and the q=3 case has b=1 rather than 3^n. Because the fix is straightforward and the main theorem remains valid, the verdict stays CONDITIONAL: the manuscript should correct equation (25) and re-verify the claims that depend on it. The reader's weakest_assumption pointed to the same region, the dominance/uniqueness proof, but identified it as merely abbreviated; the actual defect is a concrete wrong index range in a displayed equation, so agreement is partial. I also note the comparison sections omit the MR scheme [29] from Table I and contain a false 'more users' statement, but those issues are secondary to the proof inconsistency and do not affect the construction's correctness.","tokens_in":28777,"tokens_out":15450,"duration_ms":149753,"concrete_test":"Write a short script that, for q=5, n=2, constructs D_a in two ways: (i) with a∈[2]^2 (m_i=(q−1)/2) and (ii) with a∈[5]^2 as in equation (25). For each, check (a) disjointness of blocks and (b) that no half-sum of two distinct elements within any block lies in any block. Variant (ii) should fail via D_{(1,1)}: half-sum of 6 and 4 is 5, and 5 = −5+10 ∈ D_{(5,2)}; variant (i) should pass. This distinguishes a harmless typo from a substantive invalidation of Lemma 3's parameter range.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Construction 2 defines D_a for a ∈ A = [m_1]×···×[m_n], and Lemma 3's dominance inequality x_{i+1} > 2∑_{j≤i} a_j x_j holds only for a_j ≤ m_j. In Theorem 3, m_i = (q−1)/2, so valid blocks have a_i ≤ (q−1)/2. However, Appendix C's equation (25) states that when q = v^{1/n} is an odd integer, D_a = {Σ α_i a_i q^{i−1} | α_i ∈ {±1}} for all a ∈ [q]^n. This range is too large: for q=5, n=2, block D_{(1,1)} contains ±1±5 = {6,4,−4,−6}, and the half-sum (6+4)/2 = 5 equals −5+10, an element of D_{(5,2)} under the [q]^n range, violating Definition 2. It also contradicts b = m^n: with [q]^n there would be q^n blocks, not m^n. The q=3 case in Lemma 6 gives b=1, which is m^n with m=1, not q^n=3^n, so (25) is internally inconsistent. The main theorem is salvageable by replacing [q]^n with [(q−1)/2]^n, but as written the proof of Theorem 3 and Remark 2 relies on a false formula.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a new combinatorial object, the non-half-sum disjoint packing (NHSDP), and shows that a (v,g,b) NHSDP yields a (v,v,v-bg,bv) placement-delivery array via Construction 1, hence a coded caching scheme with linear subpacketization F=v, memory ratio M/N=1-bg/v, gain g, and load R=b (Theorem 1). It then constructs explicit NHSDPs in Construction 2 by embedding blocks as signed sums of dominating coordinate weights; Lemma 3 proves that this yields a (v,2^n,prod m_i) NHSDP whenever v is odd and v >= 2*phi(m_1,...,m_n)+1. This gives schemes with K=v, F=v, gain 2^n, load prod m_i (Theorem 2), and the optimization in Theorem 3 selects m_i = floor((v^{1/n}-1)/2), producing load close to floor((v^{1/n}-1)/2)^n. The paper compares these schemes with several existing linear-, polynomial-, and exponential-subpacketization schemes and connects NHSDP to cyclic difference packings, non-three-term arithmetic progressions, and perfect hash families.","tokens_in":29089,"tokens_out":6959,"duration_ms":64775,"significance":"If the results are correct after revision, the NHSDP framework is a valuable unifying condition for linear-subpacketization coded caching: it integrates placement and delivery into a single condition, and the explicit Construction 2 family achieves load roughly (v^{1/n}/2)^n while keeping F=K, which is competitive with or better than several prior schemes in the linear-subpacketization regime. The connections to NTAP and PHF also give new explicit objects, including an NTAP lower bound that beats the previous bound for small n and PHFs with more columns than the quadrics construction. The main proofs are self-contained and the key PDA verification in Theorem 1 is sound. The paper's abstract claim of lower load than all existing linear-subpacketization schemes is not yet supported because the MR scheme [29] is omitted from the comparisons, and the proof of Theorem 3 contains a false formula in Eq. (25); these issues are local and fixable, so the underlying framework remains promising.","major_comments":[{"comment":"Equation (25) states that when q=v^{1/n} is an odd integer, the blocks are D_a = {sum_i alpha_i a_i q^{i-1} | alpha_i in {-1,1}} for all a in [q]^n. This is inconsistent with Construction 2 and Lemma 3, where the block indices are restricted to A=[m_1] x ... x [m_n] and in Theorem 3 m_i=(q-1)/2. For q=5, n=2, the block D_{(1,1)} under (25) contains 4 and 6, whose half-sum 5 equals -5+10 and hence appears in D_{(5,2)} under the [q]^n range, violating Definition 2. It also contradicts the block count b=m^n: with [q]^n there would be q^n blocks, not ((q-1)/2)^n. Since the proof of Theorem 3 and Remark 2 rely on this formula, the proof as written is internally inconsistent. Replace [q]^n with [((q-1)/2)]^n, i.e., use (9) directly with m_i=(q-1)/2; the claimed family is then consistent with Lemma 3.","section":"Appendix C, Eq. (25); Remark 2"},{"comment":"The headline claim that the proposed scheme achieves a lower load than existing schemes with linear subpacketization is not fully supported, because the theoretical and numerical comparisons omit the MR scheme [29], which is listed in Table I and has linear subpacketization F=K. The phrase in Section V-A that only [16], [20], [24], [26], [27] have special parameters does not justify excluding [29]. To substantiate claim (i), the authors should compare with [29] (and ideally with [30]) for the same K and comparable memory ratios, or explicitly restrict the claim to the schemes actually compared.","section":"Section V-A and Abstract claim (i)"}],"minor_comments":[{"comment":"There is a typo: \"cachign\" should be \"caching\".","section":"Remark 2"},{"comment":"The lemma statement begins \"Gvien a ... PDA\", which should be \"Given a ... PDA\".","section":"Lemma 4"},{"comment":"In the proof of Theorem 1, \"This contracts the condition of NHSDP\" should read \"This contradicts the condition of NHSDP\".","section":"Appendix A"},{"comment":"The set is written as \"D = {alpha_1 + 3 alpha_2 + ... + 3^{n-1} alpha_n | alpha_i in {-1,1}}\"; please make explicit that this is the single block D_{(1,...,1)} in Z_{3^n} and that the half-sum condition is verified over that ring.","section":"Lemma 6"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the journal's scope and the core NHSDP-to-PDA reduction (Theorem 1) and the Construction 2 family (Lemma 3) appear correct. The main obstacles are an internally inconsistent formula in the proof of Theorem 3 and an incomplete comparison for the abstract's strongest claim; both are repairable without changing the framework. I would be willing to review a revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper. The main construction is real: the NHSDP-to-PDA route (Theorem 1, Appendix A) is correct, and the coordinate-weight NHSDP of Lemma 3/Construction 2 gives a genuinely new family with K=F, gain 2^n, and load the product of m_i, valid for odd v at least 2*phi+1. The b=1 special case recovering NTAP sets, and the PHF connections, are a nice bonus. The core math holds up.\n\nSecond, the paper is sloppier than its results. Appendix C's equation (25) writes D_a = {sum alpha_i a_i q^{i-1} | alpha_i in {±1}} for all a in [q]^n when q is odd. That range is wrong: Construction 2 and Lemma 3 require a_i <= m_i = (q-1)/2. With the [q]^n range you get blocks that violate disjointness and half-sum exclusion, and q=5, n=2 gives a concrete counterexample. As written, the proof of Theorem 3 contains a false formula. The theorem itself survives because the actual construction with m_i=(q-1)/2 satisfies v = q^n = 2*phi+1, so Lemma 3 applies; only the appendix's restatement is wrong. Still, it needs to be fixed.\n\nThe performance claims are also overstated. The abstract says lower load than existing linear-subpacketization schemes, but the comparisons skip the MR scheme [29], which is in Table I and is not dominated by the argument given. The numerical section also makes a wrong statement about user counts versus the AST scheme in Table II (e.g., 52 vs 49, 1332 vs 1331; the 'more users' claim only holds in some rows). These are fixable, but they matter for a paper whose headline is 'lower load than all existing schemes.'\n\nMinor typos appear throughout ('cachign', 'Gvien'), but nothing that obscures the method. The self-citations are normal for this research line and the proofs in Appendices A and B are genuinely informative.\n\nBottom line: the combinatorial idea is solid, the construction is new, and the paper deserves to be in the literature. But the sweeping comparison claim in the abstract and the erroneous [q]^n in Appendix C need a revision before it is citable as-is. Send it to review; a good referee will catch the same issues and the authors can clean it up.","headline":"A genuinely new combinatorial framework with a correct core construction, but the paper overclaims its comparisons and includes a wrong formula in an appendix.","tokens_in":29633,"tokens_out":3615,"would_cite":true,"duration_ms":33703,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","05B30"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper introduces non-half-sum disjoint packing, a combinatorial condition that unifies placement and delivery, and uses it to build coded caching schemes with subpacketization equal to the number of users and lower transmission load…","keywords":["coded caching","linear subpacketization","placement delivery array","transmission load","non-half-sum disjoint packing","cyclic difference packing","non-three-term arithmetic progression","perfect hash family"],"falsifier":"For Construction 2 with $m_1=m_2=m_3=2$, take the odd value $v=123$, below $2\\phi+1=125$: the element $-62$ generated by block $a=(2,2,2)$ equals $61$ modulo $123$, and $61$ is generated by block $a=(1,2,2)$, so block disjointness fails. Checking all odd $v\\ge125$ for the same parameters would confirm the claimed validity region.","tokens_in":1915,"feed_emoji":"📡","tokens_out":3007,"duration_ms":85657,"temperature":0.7,"pith_summary":"Fixing the number of users $K$ and the cache-to-file ratio, coded caching's two practical bottlenecks are the transmission load $R$ and the subpacketization $F$, the number of pieces each file is cut into. Most low-load schemes force $F$ to grow exponentially with $K$; the few known schemes with $F$ linear in $K$ pay for it with large $R$. This paper claims a middle path: a new combinatorial object, the non-half-sum disjoint packing (NHSDP), turns a $v\\times v$ Latin square into a placement-delivery array with $K=F=v$, gain equal to the block size, and load equal to the number of blocks. The authors construct NHSDPs explicitly and report that the resulting schemes beat all existing linear-subpacketization schemes in load, beat some polynomial-subpacketization schemes, and approach exponential-subpacketization performance. If correct, the paper establishes a single design principle that simultaneously handles placement and delivery and yields practical schemes with linear subpacketization.","feed_headline":"One packing structure makes coded caching linear and low-load","feed_subtitle":"A single condition encodes placement and delivery, beating existing linear schemes in transmission cost","key_machinery":"Non-half-sum disjoint packing (NHSDP): for odd $v$, a collection $\\mathcal{D}$ of $b$ disjoint $g$-subsets of $\\mathbb{Z}_v$ such that the half-sum $(x+y)/2$ of any two distinct elements of any block never appears in any block. It carries the argument because it integrates placement and delivery: the blocks determine where a Latin-square array is filled with integers, and the half-sum condition determines where the stars must sit, so a single definition supplies both the cache layout and the guarantee that every transmitted XOR reaches its intended users.","core_discovery":"The paper's central claim is Theorem 1: from any $(v,g,b)$ NHSDP, Construction 1 produces a $(v,v,v-bg,bv)$ placement-delivery array, hence a $(K=v,M,N)$ coded caching scheme with $K=F=v$, memory ratio $M/N=1-bg/v$, coded caching gain $g$, and transmission load $R=b$. The construction places the difference $k-f$ of a Latin-square entry into one of $b$ disjoint $g$-subsets of $\\mathbb{Z}_v$; the NHSDP's second condition, that no half-sum of two elements of a block lies in any block, is exactly what forces the XOR deliveries to be decodable. With the explicit family of Construction 2, built from coordinate weights $x_i$ satisfying $x_{i+1}>2\\sum_{j\\le i}f(j)$, the paper obtains $v\\ge2\\phi(m_1,\\ldots,m_n)+1$, gain $2^n$, load $\\prod_i m_i$, and subpacketization $v$, with the balanced choice $m_i=\\lfloor(v^{1/n}-1)/2\\rfloor$ giving load $\\lfloor(v^{1/n}-1)/2\\rfloor^n$. The authors argue numerically and theoretically that these schemes beat the known linear-subpacketization schemes in load and are competitive with schemes using much larger subpacketization.","pith_inferences":["The NHSDP condition is not tied to the specific Latin square $f+k$; the same half-sum argument would work for any Cayley table of an abelian group of odd order, so other group tables might yield NHSDP families with different parameters.","The explicit NTAP sets obtained at $q=3$ suggest a constructive route to better bounds on the maximum NTAP size for intermediate $v$, not just powers of 3, by interpolating the coordinate-weight construction.","Solving the integer program in Problem 1 exactly rather than through the symmetric relaxation could produce schemes with lower memory ratio at fixed gain, since the paper's closed form is only shown optimal when $q$ is an odd integer.","A natural testable extension is to allow block sizes other than $2^n$, for example by using higher-dimensional coefficient sets or mixed radices, which the paper lists as future work."],"forward_implications":["For every choice of $n$ and $m_1,\\ldots,m_n$ with $v\\ge2\\phi+1$, the constructed scheme has $K=F=v$, gain $2^n$, and load $\\prod_i m_i$, so the designer can trade memory and load across many operating points.","At the balanced point $m_i=\\lfloor(q-1)/2\\rfloor$ with $q=v^{1/n}$, the scheme matches the memory ratio of the MN scheme while reducing subpacketization by a factor exponential in $K$, at a modest load increase.","Compared with the WCWL, ZCW, AST, and XXGL linear-subpacketization schemes, the proposed scheme achieves smaller or equal subpacketization and lower load in the parameter ranges the paper tabulates.","The conjugate PDA of the balanced construction gives a high-memory regime with memory ratio $1-(2/q)^n$ and load $\\lfloor(q-1)/2\\rfloor^{-n}$, extending the same design to memory ratios near 1.","When $q=3$, the construction yields an NTAP set of size $2^n$ in $\\mathbb{Z}_{3^n}$, improving the known generic lower bound on maximal NTAP size for $n\\le52$."],"supporting_citations":[{"why":"defines placement-delivery arrays and proves that any PDA yields an $F$-division coded caching scheme, the target object of Construction 1.","marker":"[9]"},{"why":"introduces the MN coded caching scheme whose exponential subpacketization motivates the linear regime and whose load is the main comparison baseline.","marker":"[2]"},{"why":"provides the WCWL linear-subpacketization scheme with consecutive cyclic placement that the proposed scheme is compared against and beats in load.","marker":"[14]"},{"why":"gives the WCLC framework that contains several earlier PDA constructions; its subpacketization and load are used as comparison points.","marker":"[19]"},{"why":"gives the ZCW linear-subpacketization scheme appearing in the numerical comparison tables.","marker":"[16]"},{"why":"gives the AST lifting construction with linear subpacketization used as a numerical benchmark.","marker":"[20]"},{"why":"gives the XXGL rainbow-framework scheme with linear subpacketization and memory ratio near 1, used for theoretical load comparison.","marker":"[28]"},{"why":"defines cyclic difference packings, shown to be special NHSDPs and used to generate a one-load scheme for projective-plane parameters.","marker":"[31]"},{"why":"supplies the best known lower bound on NTAP size that the new NTAP sets improve for $n\\le52$.","marker":"[36]"},{"why":"provides the quadrics and Hermitian perfect hash families whose column counts the new PHFs are compared against.","marker":"[37]"}],"fun_headline_variants":["NHSDP yields linear subpacketization with lower load","New packing structure improves linear coded caching","Non-half-sum packing: key to efficient coded caching","Coded caching gets a new combinatorial structure for lower load","Linear subpacketization achieved via non-half-sum disjoint packing"],"cache_read_input_tokens":31744,"weakest_assumption_plain":"The construction's correctness rests on the coordinate weights in Construction 2 growing fast enough that no two block representations coincide in $\\mathbb{Z}_v$ and no half-sum of a block reappears in any block; this requires $v$ odd and $v\\ge2\\phi+1$, and it collapses if $v$ is chosen smaller so that wrap-around identifies two distinct integers.","fun_headline_variants_meta":{"raw":{"variants":["NHSDP yields linear subpacketization with lower load","New packing structure improves linear coded caching","Non-half-sum packing: key to efficient coded caching","Coded caching gets a new combinatorial structure for lower load","Linear subpacketization achieved via non-half-sum disjoint packing"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000851,"raw_usage":{"total_tokens":3809,"prompt_tokens":1160,"completion_tokens":2649,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":776,"completion_tokens_details":{"reasoning_tokens":2571}},"tokens_in":776,"tokens_out":2649,"duration_ms":20786,"temperature":1.0,"reasoning_tokens":2571,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:50:13.434929+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For Construction 2 with $m_1=m_2=m_3=2$, take the odd value $v=123$, below $2\\phi+1=125$: the element $-62$ generated by block $a=(2,2,2)$ equals $61$ modulo $123$, and $61$ is generated by block $a=(1,2,2)$, so block disjointness fails. Checking all odd $v\\ge125$ for the same parameters would confirm the claimed validity region.","supporting_citations":[{"cited_title":"On the placement delivery array design for centralized coded caching scheme,","cited_arxiv_id":null,"evidence_quote":"defines placement-delivery arrays and proves that any PDA yields an $F$-division coded caching scheme, the target object of Construction 1."},{"cited_title":"Multi-access coded caching with optimal rate and linear subpacketization under pda and consecutive cyclic placement,","cited_arxiv_id":null,"evidence_quote":"provides the WCWL linear-subpacketization scheme with consecutive cyclic placement that the proposed scheme is compared against and beats in load."},{"cited_title":"Design of placement delivery arrays for coded caching with small subpacketizations and flexible memory sizes,","cited_arxiv_id":null,"evidence_quote":"gives the WCLC framework that contains several earlier PDA constructions; its subpacketization and load are used as comparison points."},{"cited_title":"Coded caching schemes with linear subpacketizations,","cited_arxiv_id":null,"evidence_quote":"gives the ZCW linear-subpacketization scheme appearing in the numerical comparison tables."},{"cited_title":"Lifting constructions of pdas for coded caching with linear subpacketization,","cited_arxiv_id":null,"evidence_quote":"gives the AST lifting construction with linear subpacketization used as a numerical benchmark."},{"cited_title":"A rainbow framework for coded caching and its applications,","cited_arxiv_id":null,"evidence_quote":"gives the XXGL rainbow-framework scheme with linear subpacketization and memory ratio near 1, used for theoretical load comparison."},{"cited_title":"Some combinatorial constructions for optical orthogonal codes,","cited_arxiv_id":null,"evidence_quote":"defines cyclic difference packings, shown to be special NHSDPs and used to generate a one-load scheme for projective-plane parameters."},{"cited_title":"Perfect hash families of strength three with three rows from varieties on finite projective geometries,","cited_arxiv_id":null,"evidence_quote":"provides the quadrics and Hermitian perfect hash families whose column counts the new PHFs are compared against."}],"review_version":1}