{"id":"16fb93c2-0575-4267-99db-748e757ad63a","arxiv_id":"1908.03523","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new construction shows I2(n,4) = Ω(n^{3/2-o(1)}), improving the previous lower bound Ω(n^{4/3+o(1)}) for 2-parent-identifying set systems of block size 4.","lead":"Mathematicians improved the best-known lower bound on the maximum size of a 2-parent-identifying set system with block size 4, from n^(4/3) to roughly n^(3/2). The construction uses sets of integers with no nontrivial solutions to certain linear equations, a technique from additive number theory.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.3 does not establish simultaneous avoidance of (2.5) for both coefficient pairs used in Theorem 3.1, and the paper's definition of 'nontrivial' is inconsistent with Lemma 2.2.","rationale":"The reader's verdict is CONDITIONAL, and this stress-test identifies the same load-bearing weakness: the set S guaranteed by Lemma 2.3 does not provably avoid all instances of equation (2.5) needed in Theorem 3.1. In fact, the issue is slightly more basic: the paper's definition of 'nontrivial solution' makes Lemma 2.2 impossible even for a single coefficient pair if read literally, so the intended meaning must be a Sidon-style pairwise-equality condition. Under that intended meaning, Lemma 2.3 is still insufficient because it intersects with only one S1, yet the case analysis invokes equation (3.23) with coefficients (2,5) and equation (3.25) with coefficients (1,1). Since the theorem's proof depends on these contradictions to verify IPPSb, the central construction is not fully established. The concern is concrete and localized; if a set avoiding both equations can be produced at the claimed density, the argument likely goes through. Hence the conditional verdict is appropriate, and no change to the reader's assessment is needed.","tokens_in":10010,"tokens_out":14341,"duration_ms":143043,"concrete_test":"Check the exact statement of Ruzsa's Theorem 7.3 in [14]: does the constructed S1 avoid (2.5) for one arbitrary fixed pair (a,b) only? If yes, try to extend the proof of Lemma 2.3 to the two required pairs by intersecting S0 with S1^{(2,5)} and S1^{(1,1)}. Estimating the size of (S0+u) ∩ S1^{(2,5)} ∩ S1^{(1,1)} by the same random-shift argument gives expected size roughly |S1^{(1,1)}| · (|S0|/m) · (|S1^{(2,5)}|/m) ≈ 2^{-O(log^{3/4}m)}, not √m/2^{O(log^{3/4}m)}, so the naive repair fails. This demonstrates that the current proof lacks the required simultaneous avoidance and that a genuinely new additive-combinatorial construction is needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central lower bound depends on the IPPSb case analysis in Theorem 3.1. In Case 2, equation (3.23) is 2x+5y = 2w+5z, which requires S to avoid equation (2.5) with (a,b) = (2,5). In Case 3, equation (3.25) is x+y = z+w, requiring S to avoid (2.5) with (a,b) = (1,1). Lemma 2.2 supplies a set S1 avoiding (2.5) for one fixed pair (a,b), and Lemma 2.3 constructs S as (S0+u) ∩ S1 with a single S1. That does not give simultaneous avoidance of the two distinct coefficient pairs used later. Moreover, the paper's Section 2 definition says a solution is nontrivial unless all variables are equal; under that definition no set of size at least 2 can avoid (2.5), even for one pair, since x=z, y=w with x≠y is a solution that is not all equal. So Lemma 2.2 must be relying on a different, weaker notion of nontriviality (typically allowing pairwise-equal solutions). With that weaker notion, the proof of Lemma 2.3 still only handles a single pair, while Theorem 3.1 needs at least (2,5) and (1,1). The contradiction in Cases 2 and 3 therefore rests on an unproved simultaneous-avoidance claim. This is load-bearing: without it, the lower bound construction is not shown to be a 2-IPPS.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the maximum size I2(n,4) of a 2-parent-identifying set system on an n-point ground set with blocks of size 4. The main result is the lower bound I2(n,4)=Ω(n^{3/2-o(1)}), improving the previous best lower bound Ω(n^{4/3+o(1)}). The construction chooses a set S⊆[m] that avoids certain linear equations (Lemmas 2.1–2.3) and forms blocks indexed by pairs (p,s) with p∈[m], s∈S, using four affine linear maps into the ground set [4]×[(q+6)m]. The proof then verifies the two conditions (IPPSa) and (IPPSb) of Lemma 1.4 through a case analysis on the intersection of two pairs of blocks. The paper also contains a discussion of the relation between parent-identifying set systems and parent-identifying codes.","tokens_in":10296,"tokens_out":14695,"duration_ms":135954,"significance":"If the construction were valid, the result would be a substantial improvement over the known lower bound for I2(n,4) and would demonstrate an interesting application of additive number theory to parent-identifying set systems. The paper also gives a useful comparison of IPP set systems with IPP codes. However, the central proof is not sound: the claimed set S whose existence is asserted in Lemma 2.3 is not established, and the case analysis in Theorem 3.1 relies on an impossible or unproved avoidance property. Because these issues are load-bearing, the main theorem is not proven in the manuscript as written.","major_comments":[{"comment":"The paper defines a solution to equation (2.1) to be nontrivial unless all variables are equal. Under this definition, Lemma 2.2 is false for equation (2.5): for any set S of size at least 2, choosing x=z and y=w with x≠y gives a solution to ax+by=az+bw that is not all-equal. The cited result of Ruzsa (and standard terminology in additive combinatorics) uses a weaker notion of triviality for (2.5), namely solutions with (x,y)=(z,w), and also (x,y)=(w,z) when a=b. Since Lemmas 2.2 and 2.3 are stated and used with the paper's all-equal definition, the existence of a set S in Lemma 2.3 with |S|≥2 and the claimed avoidance of (2.5) is impossible.","section":"Section 2, definition of nontrivial solution and Lemma 2.2"},{"comment":"Lemma 2.3 asserts that a single set S of size √m/2^{O(log^{3/4}m)} avoids equation (2.5) simultaneously with equations (2.2)–(2.4). The proof intersects S0+u with a single set S1 supplied by Lemma 2.2. However, Lemma 2.2 only provides S1 for one fixed coefficient pair (a,b). In Theorem 3.1, equation (2.5) is invoked with (a,b)=(2,5) in Case 2 (equation (3.23)) and with (a,b)=(1,1) in Case 3 (equation (3.25)), and the text claims the same for all other index configurations. The proof gives no reason why a single S1 can serve all these pairs, and the stated size bound for a set with such simultaneous avoidance does not follow from the cited lemmas.","section":"Section 2, Lemma 2.3"},{"comment":"The proof concludes x=y=z=w from equations (3.23) and (3.25) by invoking avoidance of (2.5). Even under the standard notion of trivial solutions to ax+by=az+bw, equation (3.23) permits solutions with x=w and y=z, and equation (3.25) permits solutions with x=z and y=w, neither of which forces all four variables to be equal. The manuscript does not show that these alternative solutions contradict the distinctness of A1,A2,B1,B2; it merely asserts that all variables are equal. This leaves the (IPPSb) verification incomplete and breaks the proof of Theorem 3.1.","section":"Section 3, Cases 2 and 3 (equations (3.23), (3.25))"}],"minor_comments":[{"comment":"The statement of Lemma 2.2 should specify that a and b are fixed positive integers given in advance; the phrase 'where a, b are positive integers' is ambiguous and could be read as quantifying over all pairs, which would make the lemma false.","section":"Section 2, Lemma 2.2"},{"comment":"Equation (3.15) is not literally equation (2.4); the reduction uses the variable permutation (x,y,z,w) ↦ (z,y,x,w). The text should state this explicitly, as otherwise the claim that (3.15) is avoided via (2.4) is not evident.","section":"Section 3, Case 1.1"},{"comment":"There are numerous minor typographical and formatting issues (for example, the exponent notation in (2.8) is hard to read, and some equation references are imprecise). A careful proofreading pass is needed in any revision.","section":"Throughout"},{"comment":"Reference [15] is an arXiv preprint; if a peer-reviewed version exists, it should be cited instead.","section":"References"}],"recommendation":"reject","confidential_remarks":"The central construction is not supported. The definitional inconsistency in Section 2 makes Lemma 2.2 false as stated, and the proof of Lemma 2.3 does not supply the simultaneous avoidance required by Theorem 3.1. These are load-bearing errors that would require a substantially new additive-combinatorics argument to repair, so I do not see them as local fixes within the scope of a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis paper improves the lower bound for I_2(n,4) from Ω(n^{4/3+o(1)}) to Ω(n^{3/2-o(1)}) using a clean additive-combinatorics construction. The idea is to adapt Alon–Fischer–Szegedy and Ruzsa sets to the stronger IPPSb condition, and the block construction in (3.2) is neat. The case analysis for IPPSa/IPPSb is long but mostly plausible, and the paper is honest about the remaining gap to the o(n^2) upper bound.\n\nThe soft spot is real, though. Section 2 defines a solution as nontrivial unless all variables are equal, but under that definition no set of size at least 2 can avoid (2.5), since x=z, y=w with x≠y is always a solution. The cited Ruzsa result must be using the standard weaker notion of nontriviality (coordinate-wise pair equality). More importantly, Lemma 2.3 takes a single S1 from Lemma 2.2 for one coefficient pair, while Cases 2 and 3 of Theorem 3.1 need simultaneous avoidance of two distinct equations: (3.23) with (a,b)=(2,5) and (3.25) with (a,b)=(1,1). Intersecting S0 with two Ruzsa sets, one per coefficient pair, should repair this while preserving the needed size, but as written the lemma does not deliver what the theorem uses. I did not find a similar gap in the case analysis; the conflict equations do map to the claimed avoidance lemmas.\n\nIf Lemma 2.3 is fixed, the main result stands. This deserves a serious referee: the construction is interesting, the exponent improvement is real, and the proof structure is sound. I would cite the result after a clean revision, but for now conditional acceptance is the right call.","headline":"A genuinely new and elegant construction for the I_2(n,4) lower bound, but Lemma 2.3 as written does not establish the simultaneous equation-avoidance the main proof needs.","tokens_in":10883,"tokens_out":4984,"would_cite":true,"duration_ms":46489,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B25","05D05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper constructs 2-parent-identifying set systems with block size 4 on n points that contain at least $n^{3/2-o(1)}$ blocks, improving the previous $\\Omega(n^{4/3+o(1)})$ lower bound.","keywords":["parent-identifying set systems","broadcast encryption","traitor tracing","block size 4","additive number theory","Ruzsa sets","linear equations","lower bounds"],"falsifier":"A concrete way to test the central claim is to search, for small values of $m$, whether the constructed family contains four distinct blocks $A_1,A_2,B_1,B_2$ with $|(A_1\\cup A_2)\\cap(B_1\\cup B_2)|\\ge4$. Such a violation would correspond to a nontrivial solution of one of equations (2.2)--(2.5) with parameters in the chosen set $S$; exhibiting that solution for a coefficient pair such as $(a,b)=(2,5)$ or $(1,1)$ would disprove the simultaneous avoidance asserted by Lemma 2.3.","tokens_in":9710,"feed_emoji":"🔐","tokens_out":5949,"duration_ms":61770,"temperature":0.7,"pith_summary":"The paper improves the known maximum size of a 2-parent-identifying set system with block size 4. It constructs, for every $\\varepsilon>0$ and all sufficiently large $n$, a system on $n$ points with at least $n^{3/2-\\varepsilon}$ blocks. The construction encodes each block as four points on a line-like progression, and the verification that a 4-point conflict cannot be traced to two different parent pairs is reduced to checking that a carefully chosen set of parameters avoids nontrivial solutions to several linear equations. This moves the lower bound for $I_2(n,4)$ from $\\Omega(n^{4/3+o(1)})$ to $\\Omega(n^{3/2-o(1)})$, still leaving a gap to the known upper bound $o(n^2)$.","feed_headline":"Four-key pirate-proof set systems now hit n-to-the-3/2","feed_subtitle":"A new construction beats the old n^{4/3} lower bound for 2-parent-identifying systems with block size 4.","key_machinery":"The central object is a set $S$ of integers with no nontrivial solution to a finite collection of homogeneous linear equations; such a set is produced by intersecting a set $S_0$ that avoids equations (2.2)--(2.4) with a set $S_1$ that avoids an equation of the form $ax+by=az+bw$, using a random translation to merge them. The resulting parameter set $S$ is what makes the four-point blocks pairwise almost disjoint and prevents ambiguous parent unions. The proof then reduces every possible configuration of a 4-subset lying in two unions of blocks to one of the forbidden equations, so the additive-number-theory avoidance condition is precisely what carries the parent-identifying property.","core_discovery":"Theorem 3.1 asserts that $I_2(n,4)=\\Omega(n^{3/2-o(1)})$. The proof gives an explicit construction: take $X=[4]\\times[(q+6)m]$ with $q=\\lceil2\\sqrt{\\log m}\\rceil$, and for every $p\\in[m]$ and $s\\in S$ define the block $\\{(1,p),(2,p+2s),(3,p+5s),(4,p+(q+5)s)\\}$. Here $S$ is a subset of $[m]$ of size at least $\\sqrt{m}/2^{O(\\log^{3/4}m)}$ with no nontrivial solution to the three fixed equations (2.2), (2.3), (2.4) or to any equation of the form $ax+by=az+bw$ from the case analysis. Because any violation of the parent-identifying property would force one of those equations to have a nontrivial solution, the constructed family is a 2-IPPS, and the size count gives the claimed bound.","pith_inferences":["The construction is modular in the number of forbidden equations: for larger block sizes the same style of argument would require avoiding more and more linear equations, and the $O(\\sqrt{m})$ ceiling on $S$ suggests that the $3/2$ exponent may be a natural limit for this type of Kautz-Singleton-like embedding.","Because the parameter set $S$ is built from additive-combinatorial objects, the proof suggests a general transfer between results on solution-free sets of integers and lower bounds for parent-identifying set systems with block size 4.","One testable extension would be to search computationally for small violations of the parent-identifying property in the constructed family; a concrete violation would indicate that the simultaneous avoidance required by Lemma 2.3 does not hold for all coefficient pairs used in the case analysis."],"forward_implications":["If the theorem is correct, the previous lower bound $\\Omega(n^{4/3+o(1)})$ is superseded, so broadcast-encryption schemes tolerating two colluders can support more users with four keys per user.","The known bounds become $\\Omega(n^{3/2-o(1)})\\le I_2(n,4)\\le o(n^2)$, and determining the true order of magnitude remains an open gap.","The same parametric construction cannot yield $\\Omega(n^{3/2+o(1)})$ because the size of $S$ is bounded above by $O(\\sqrt{m})$ by the Ruzsa upper bound on sets avoiding $ax+by=az+bw$.","For every $\\varepsilon>0$, sufficiently large $n$ admit a 2-IPPS$(n,4)$ with at least $n^{3/2-\\varepsilon}$ blocks."],"supporting_citations":[{"why":"Supplies the set $S_0$ and the three fixed equations (2.2)--(2.4) that the construction's parameter set must avoid.","marker":"[1]"},{"why":"Supplies a set $S_1$ avoiding $ax+by=az+bw$ for a fixed coefficient pair, as well as the $O(\\sqrt{m})$ upper bound that caps the size of $S$.","marker":"[14]"},{"why":"Gives the previous lower bound $I_2(n,4)=\\Omega(n^{4/3+o(1)})$ that the new construction improves.","marker":"[15]"},{"why":"Provides the characterization of 2-IPPS via conditions (IPPSa) and (IPPSb) used to certify the construction, along with earlier probabilistic lower bounds.","marker":"[9]"},{"why":"Introduces the combinatorial model of key-distribution schemes on which the notion of parent-identifying set systems is based.","marker":"[16]"},{"why":"Proposes parent-identifying set systems as a variant of codes with the identifiable parent property.","marker":"[5]"}],"fun_headline_variants":["Block-4 pirate-proof codes: exponent jumps from 4/3 to 3/2","Additive number theory boosts pirate-proof bound to 3/2","New bound for 2-parent-ID set systems: n^{3/2}","Pirate-proof set systems now reach n^{3/2} with block size 4"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire argument rests on the existence of a single large integer set $S$ that simultaneously avoids nontrivial solutions to the three fixed equations (2.2)--(2.4) and to every equation $ax+by=az+bw$ that appears in the case analysis of Theorem 3.1; if such a set cannot be produced for all required coefficient pairs, the verification of condition (IPPSb) collapses.","fun_headline_variants_meta":{"raw":{"variants":["Block-4 pirate-proof codes: exponent jumps from 4/3 to 3/2","Additive number theory boosts pirate-proof bound to 3/2","New bound for 2-parent-ID set systems: n^{3/2}","Pirate-proof set systems now reach n^{3/2} with block size 4"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001148,"raw_usage":{"total_tokens":4725,"prompt_tokens":874,"completion_tokens":3851,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":490,"completion_tokens_details":{"reasoning_tokens":3761}},"tokens_in":490,"tokens_out":3851,"duration_ms":27555,"temperature":1.0,"reasoning_tokens":3761,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:13:02.250062+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete way to test the central claim is to search, for small values of $m$, whether the constructed family contains four distinct blocks $A_1,A_2,B_1,B_2$ with $|(A_1\\cup A_2)\\cap(B_1\\cup B_2)|\\ge4$. Such a violation would correspond to a nontrivial solution of one of equations (2.2)--(2.5) with parameters in the chosen set $S$; exhibiting that solution for a coefficient pair such as $(a,b)=(2,5)$ or $(1,1)$ would disprove the simultaneous avoidance asserted by Lemma 2.3.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the set $S_0$ and the three fixed equations (2.2)--(2.4) that the construction's parameter set must avoid."},{"cited_title":"Z.: Solving a linear equation in a set of integer s I","cited_arxiv_id":null,"evidence_quote":"Supplies a set $S_1$ avoiding $ax+by=az+bw$ for a fixed coefficient pair, as well as the $O(\\sqrt{m})$ upper bound that caps the size of $S$."},{"cited_title":"Sparse Hypergraphs with Applications to Coding Theory","cited_arxiv_id":"1902.05903","evidence_quote":"Gives the previous lower bound $I_2(n,4)=\\Omega(n^{4/3+o(1)})$ that the new construction improves."},{"cited_title":"IEEE Trans","cited_arxiv_id":null,"evidence_quote":"Provides the characterization of 2-IPPS via conditions (IPPSa) and (IPPSb) used to certify the construction, along with earlier probabilistic lower bounds."},{"cited_title":"R., Wei R.: Combinatorial properties and con structions of traceability schemes and frameproof codes","cited_arxiv_id":null,"evidence_quote":"Introduces the combinatorial model of key-distribution schemes on which the notion of parent-identifying set systems is based."},{"cited_title":"J.: Upper bounds for parent-identifying set s ystems","cited_arxiv_id":null,"evidence_quote":"Proposes parent-identifying set systems as a variant of codes with the identifiable parent property."}],"review_version":1}