Pith. sign in

REVIEW 3 major objections 4 minor 16 references

On $2$-parent-identifying set systems of block size $4$

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 1908.03523 v3 pith:JBQMC3Z2 submitted 2019-08-09 math.CO

Yujie Gu , Shohei Satake This is my paper · ORCID
classification math.CO MSC 94B2505D05
keywords parent-identifyingsetsystemsbroadcastencryptiontraitortracingblocksize4additivenumbertheoryRuzsasetslinearequationslowerbounds
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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)$.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Section 2, definition of nontrivial solution and Lemma 2.2] 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.
  2. [Section 2, Lemma 2.3] 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.
  3. [Section 3, Cases 2 and 3 (equations (3.23), (3.25))] 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.
minor comments (4)
  1. [Section 2, Lemma 2.2] 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.
  2. [Section 3, Case 1.1] 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.
  3. [Throughout] 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.
  4. [References] Reference [15] is an arXiv preprint; if a peer-reviewed version exists, it should be cited instead.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the lower-bound construction is built from independent external lemmas, with no fitted parameter renamed as a prediction.

full rationale

Theorem 3.1 constructs blocks explicitly from a set S whose existence is taken from Alon-Fischer-Szegedy (Lemma 2.1) and Ruzsa (Lemma 2.2), combined in Lemma 2.3; the claimed lower bound then follows directly from |S| and n = 4(q+6)m with no equation of the proof being reused as its own conclusion. The previous lower bound I2(n,4)=Omega(n^{4/3+o(1)}) is cited only as historical context, not as an ingredient, and the self-cited result Lemma 1.4 is a parameter-free characterization of 2-IPPS with assumptions that do not include the target lower bound. No parameter is fitted to a subset of data and then 'predicted'; no uniqueness theorem by the authors is invoked to force the choice; the ansatz-smuggling pattern is absent. The known correctness gap concerning whether Lemma 2.3 establishes simultaneous avoidance of (2.5) for the coefficient pairs (2,5) and (1,1) used in Cases 2 and 3 of Theorem 3.1 is a matter of proof validity, not circularity, because it does not consist in the target claim being assumed or defined into existence.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The construction rests on external additive number theory lemmas and a known characterization of 2-IPPS. The main unproven item is the assertion that one set S avoids all needed instances of equation (2.5). No free parameters are fitted and no new entities are introduced.

assumptions (5)
  • standard math Lemma 2.1 (Alon-Fischer-Szegedy): existence of S0 ⊆ [m] of size m/2^{O(log^{3/4}m)} avoiding equations (2.2)-(2.4).
    External theorem cited from [1]; accepted as a black box.
  • standard math Lemma 2.2 (Ruzsa): existence of S1 ⊆ [m] of size √m/2^{O(log^{1/2}m)} avoiding ax+by=az+bw for a fixed positive integer pair (a,b).
    External theorem cited from [14]; the proof later needs avoidance for several distinct pairs, which is not covered by this single-set statement.
  • domain assumption Lemma 1.4 ([9]): a set system is a 2-IPPS iff it satisfies (IPPSa) and (IPPSb).
    Known characterization of 2-parent-identifying set systems, stated by the authors and used to verify the construction.
  • standard math Translation invariance of homogeneous linear equations.
    Used in Lemma 2.3 to intersect a shifted S0 with S1 while preserving the avoidance properties.
  • ad hoc to paper Unproven assertion: a single set S of size √m/2^{O(log^{3/4}m)} avoids every equation of the form ax+by=az+bw that arises in the case analysis of Theorem 3.1.
    Lemma 2.3 asserts this by intersecting S0 with a single S1, but Lemma 2.2 only avoids one fixed equation; the case analysis uses several distinct pairs (e.g., (2,5), (3,2), (q+3,3), (1,1)). This is the load-bearing gap.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On $2$-parent-identifying set systems of block size $4$." pith.science (2026). https://pith.science/paper/JBQMC3Z2

@misc{pith2026190803523,
  author       = {Pith},
  title        = {Pith review of: On $2$-parent-identifying set systems of block size $4$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JBQMC3Z2}},
  note         = {Machine review of arXiv:1908.03523}
}
abstract

Parent-identifying set system is a kind of combinatorial structures with applications to broadcast encryption. In this paper we investigate the maximum number of blocks $I_2(n,4)$ in a $2$-parent-identifying set system with ground set size $n$ and block size $4$. The previous best known lower bound states that $I_2(n,4)=\Omega(n^{4/3+o(1)})$. We improve this lower bound by showing that $I_2(n,4)= \Omega(n^{3/2-o(1)})$ using techniques in additive number theory.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [4]

    IE EE Trans

    Chor B., Fiat A., Naor M., Pinkas B.: Tracing traitors. IE EE Trans. Inf. Theory, vol. 46, no. 3, pp. 893–910, May 2000

    work page 2000

  2. [1]

    Alon N., Fischer E., Szegedy M.: Parent-identifying cod es. J. Combinat. Theory A, vol. 95, no. 2, pp. 349–359, 2001

    work page 2001

  3. [2]

    IEEE Trans

    Boneh D., Shaw J.: Collusion-secure fingerprinting for d igital data. IEEE Trans. Inf. Theory, vol. 44, no. 5, pp. 1897–1905, 1998

    work page 1905

  4. [3]

    In Advances in Crytology (Lecture Notes in Computer Science), vol

    Chor B., Fiat A., Naor M.: Tracing traitors. In Advances in Crytology (Lecture Notes in Computer Science), vol. 839. Berlin, Germany: Springer- Verlag, 1994, pp. 480–491

    work page 1994

  5. [5]

    J.: Upper bounds for parent-identifying set s ystems

    Collins M. J.: Upper bounds for parent-identifying set s ystems. Des. Codes Cryptogr., vol. 51, no. 2, pp. 167–173, 2009

    work page 2009

  6. [6]

    E.: Generalization of IPP codes and IPP set sys tems

    Egorova E. E.: Generalization of IPP codes and IPP set sys tems. Probl. Inf. Transm., Vol. 55, No. 3, pp. 241–253, 2019

    work page 2019

  7. [7]

    Erd˝ os P., Frankl P., Furedi Z.: Families of finite sets in which no set is covered by the union of two others. J. Combinat. Theory A, Vol.33, No. 2, pp. 158–166, 1982

    work page 1982

  8. [8]

    In Coding Theory and Applications (Lecture Notes in Computer Science), vol

    Egorova E., Kabatiansky G.: Analysis of two tracing trai tor schemes via coding theory. In Coding Theory and Applications (Lecture Notes in Computer Science), vol. 10495, pp. 84–92, 2017

    work page 2017

Show all 16 references
  1. [9]

    IEEE Trans

    Gu Y., Cheng M., Kabatiansky G., Miao Y.: Probabilistic e xistence results for parent- identifying schemes. IEEE Trans. Inf. Theory, vol. 65, pp. 6 160–6170, 2019

    2019

  2. [10]

    IEEE Tra ns

    Gu Y., Miao Y.: Bounds on traceability schemes. IEEE Tra ns. Inf. Theory, vol. 64, no. 5, pp. 3450–3460, 2018

    2018

  3. [11]

    Hollmann H. D. L., van Lint J. H., Linnartz J.-P., Tolhui zen L. M. G. M.: On codes with the identifiable parent property. J. Combinat. Theory A , vol. 82, pp. 121–133, 1998

    1998

  4. [12]

    A.: Traceability codes and their genera lizations

    Kabatiansky G. A.: Traceability codes and their genera lizations. Probl. Inf. Transm., Vol. 55, No. 3, pp. 283–294, 2019

    2019

  5. [13]

    H., Singleton R

    Kautz W. H., Singleton R. R. : Nonrandom binary superimp osed codes. IEEE Trans. Inform. Theory, vol. 10, no. 4, pp. 363–377, 1964

    1964

  6. [14]

    Z.: Solving a linear equation in a set of integer s I

    Ruzsa I. Z.: Solving a linear equation in a set of integer s I. Acta Arith., vol. 65, 259–282, 1993

    1993

  7. [15]

    Available: https://arxiv.org/abs/1902.05903

    Shangguan C., Tamo I.: Universally sparse hypergraphs with applications to coding theory. Available: https://arxiv.org/abs/1902.05903

    1902 arXiv

  8. [16]

    R., Wei R.: Combinatorial properties and con structions of traceability schemes and frameproof codes

    Stinson D. R., Wei R.: Combinatorial properties and con structions of traceability schemes and frameproof codes. SIAM J. Discrete Math., vol. 1 1, pp. 41–53, 1998. Department of Electrical Engineering–Systems, Tel A viv Un iversity, Tel A viv 6997801, Israel E-mail address : g...

    1998

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.