{"id":"774247eb-6486-44ea-9bfb-1676585262cd","arxiv_id":"2411.13510","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves the optimal Daykin-Erdős bound on disjoint pairs, the Singer-Sudan conjecture, and optimal log-rank-style rectangle bounds for sparse and integer-valued matrices.","lead":"This mathematics paper settles the 40-year-old Daykin-Erdős problem: the exact exponential rate of disjoint pairs in large set families, with a matching construction. It also proves the Singer-Sudan conjecture on large fully-disjoint subfamilies and gives optimal all-zero submatrix bounds for sparse low-rank matrices.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the entropy proof of Theorem 1.2 survives scrutiny, though t and k should be integer-rounded.","rationale":"The reader's weakest assumption, Lemma 3.5, is indeed the linchpin of the entropy proof of Theorem 1.2, but on careful checking it is sound and its proof is correct. The same applies to the rest of the dependent-random-choice argument: each step is justified, and the constants are consistent after accounting for real-valued t and k, which can be rounded up at no cost. The reader's conditional verdict cites two additional issues: a numerically false inequality in the first combinatorial proof of Theorem 3.2, and an unjustified small-family case in Theorem 1.10. Both are genuine defects in the manuscript, but they are not load-bearing for the central claim, because Theorem 1.2 is independently proven by the entropy method and Theorem 1.10 is a separate result. Therefore I do not identify a concern that would change the verdict: the central claim stands, while the peripheral issues still merit editorial attention before publication.","tokens_in":32882,"tokens_out":36900,"duration_ms":341465,"concrete_test":"Rewrite the proof of Theorem 3.3 with integer parameters t = ⌈M/(θn)⌉ and k = ⌈log_2(1/θ)+c⌉, then verify the three inequalities used in the chain: (i) E|A0|^k ≥ ε^{tk}|A|^k, (ii) Cn/2^k ≤ θn, and (iii) √(θn log_2 n)·t ≥ 3 log_2 n. If all three hold with the rounded values, the entropy proof of Theorem 1.2 is complete; if any fails, a larger absolute constant in the O(·) of Theorem 3.3 may be needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I examined the strongest claim (Theorem 1.2) and the entropy route through Theorems 3.3 and Lemma 3.5, the premise flagged by the reader. Lemma 3.5 is correct: for each coordinate i, the inclusion probability 1-(1-p_i)^k is lower bounded by H(p_i)-C/2^k via Lemma 3.4, and summing with subadditivity of entropy gives E|U| ≥ log|F| - Cn/2^k. The proof of Lemma 3.4, while compressed, is valid: the only delicate case p∈[1/10, 1/2-5/k] uses H(p) ≤ 1-(2/ln 2)(1/2-p)^2 and the elementary bound (2/ln 2)(25/k^2) ≥ 0.9^k for k>40; the remaining cases are routine. The dependent-random-choice chain in Theorem 3.3 also checks out: Jensen gives E|A0|^k ≥ ε^{tk}|A|^k; the union bound over bad k-tuples gives E[X] ≤ |A|^k(2^s/|B|)^t, and the constants have been chosen so that this is absorbed by |A|^k ε^{tk} n^{-3}; finally, Lemma 3.5 forces a wide k-tuple with probability at least 1/n, yielding the contradiction. Thus the central claim does not rest on an insecure lemma. The numerical error in the first proof of Theorem 3.2 and the small-family gap in Theorem 1.10 are real but peripheral; neither affects the validity of Theorem 1.2, which is independently established by the entropy argument.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies extremal problems about disjoint pairs in set systems and zero/constant submatrices in low-rank matrices. Its main results are: an optimal bound for the Daykin-Erdős problem with the conjectured dependence on δ (Theorem 1.2); a bipartite strengthening with asymptotically sharp constants (Theorem 1.3); a Singer–Sudan type biclique theorem for disjointness graphs (Theorem 1.10); a tight lower bound for r-cover-free families (Lemma 1.11); a nonzero-intersection analogue (Theorem 1.5); an even/odd intersection bound (Theorem 1.6); new low-rank matrix results for sparse separated matrices (Theorem 1.12) and for integer matrices with bounded average (Theorem 1.13). The proofs combine dependent random choice, entropy, Fourier analysis, discrepancy, and additive combinatorics, and the paper also provides constructions showing optimality of several bounds.","tokens_in":33194,"tokens_out":31300,"duration_ms":371338,"significance":"If the proofs are correct, these are substantial contributions. Theorem 1.2 resolves the Daykin-Erdős problem with the optimal dependence on δ, matching Construction 1 up to the constant c. Theorem 1.10 proves the Singer–Sudan conjecture in a strong quantitative form, and Lemma 1.11 settles the Alon–Gilboa–Gueron problem up to a constant in the exponent. The matrix results generalize the best known log-rank bounds and are optimal in a natural parameter range. The entropy proof of Theorem 1.2 via Theorem 3.3 and Lemma 3.5 is sound; I checked the dependent-random-choice chain and the constants. The combinatorial proof of Theorem 3.2 is also essentially correct once the notation '104' is read as 10^4, matching the hypothesis of Theorem 3.2; with that reading the numerical inequalities are valid. The main weakness is in the appendix proof of Theorem 1.13, which has a missing verification of a key hypothesis.","major_comments":[{"comment":"In the key statement of the proof, Proposition A.5 is applied to the matrix M − ℓJ, but the hypothesis of Proposition A.5 that all entries lie in (−r^3, r^3) is not verified. Lemma 4.7(1) only shows that a submatrix has entries bounded by 400r^2 p(M), which can exceed r^3 when ℓ grows, and M − ℓJ can have negative entries of similarly large magnitude. This matters because the proof of Proposition A.5 uses the entry bound to assert q0 ≤ r^6 and hence f(p0) + g(q0) = O(√r + log r); without that bound the potential could be much larger and the claimed O(√r) iteration count does not follow. The theorem may still be true, and the gap may be repairable by a capping argument or by splitting off the regime where t is large, but as written the proof of Theorem 1.13 is incomplete.","section":"Appendix, proof of Theorem 1.13"}],"minor_comments":[{"comment":"The apparent numerical contradiction in the displayed inequality disappears when '104' is read as 10^4, as in the theorem statement; with that reading 32/100 + 192/10^4 < 1/2 and the analogous final bound 35/100 + 210/10^4 < 1 also hold. The text should use a clear superscript to avoid confusion.","section":"Section 3.1, proof of Theorem 3.2"},{"comment":"The proof of the first bullet of Claim 4.1 is omitted with a pointer to the authors' own paper [28]. Since this claim is used in the proof of Theorem 1.12, the manuscript should either include the short proof or state the precise claim from [28] being invoked.","section":"Section 4, Claim 4.1"},{"comment":"The theorem is stated for an m × n matrix but the conclusion says 'an all-zero submatrix of size at least n2^{-O(log r+√εr)}'. If m is much smaller than n this is false as stated; the proof actually gives a submatrix of size 2^{-O(...)}m × 2^{-O(...)}n. The statement should be corrected to use min(m,n) or to state both dimensions.","section":"Statement of Theorem 1.12"},{"comment":"The small-family case is written only for |B| ≤ 2^{2√{n log δ^{-1}}}; if instead |A| is small while |B| is large, the symmetric argument picking one element of A and its neighbourhood in B should be stated explicitly.","section":"Section 2, proof of Theorem 1.10"}],"recommendation":"major_revision","confidential_remarks":"The central results and the entropy route appear correct, and the paper is strong. The only substantive technical defect I found is the missing entry-bound verification in the appendix proof of Theorem 1.13, which is load-bearing for that theorem. I recommend major revision rather than rejection because the gap seems repairable and the rest of the paper is in good shape."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a major paper. It settles the Daykin–Erdős problem with the right δ-dependence, proves the Singer–Sudan conjecture in strong quantitative form, and gives optimal all-zero submatrix bounds for sparse low-rank matrices. I believe the main theorems are correct. The entropy route through Lemma 3.5 and Theorem 3.3 is sound; I checked the dependent random choice calculation and the constants work. The constructions are clean and match the upper bounds.\n\nThe paper does several things well beyond the headline results. Lemma 1.11 is a sharp answer to the Alon–Gilboa–Gueron question. Theorem 1.12 improves the log-rank bound to 2^{-O(√(εr))} and is optimal in the sparse regime. The Fourier/additive-combinatorics proof of Theorem 1.5 and the short proof of Theorem 1.6 are elegant. The writing is dense but the organization helps.\n\nNow the soft spots, in order of importance.\n\nFirst, the combinatorial proof of Theorem 1.2 in Section 3.1 contains a false numerical inequality. The text claims 32/100 + 192/104 < 1/2, which is false (the second term is larger than 1.8). This is exactly where the contradiction is supposed to come from. The entropy proof in Section 3.2 is independent and valid, so the theorem stands, but as written Section 3.1 is broken and should be corrected or removed. This is not a fatal flaw; it is a local error that does not infect the rest of the paper.\n\nSecond, the small-family case in Theorem 1.10 has a gap. The proof assumes δ ≥ 2^{-n} after handling small |B|, but the theorem allows smaller δ. For δ below 2^{-n}, the desired bound is weaker than 2^{-O(n)}, and taking a single disjoint pair (which exists when d(A,B)>0) gives 1, which is enough if the O-constant is chosen ≥ 2. So the statement is patchable with a short separate argument; it is not a counterexample.\n\nThird, Claim 4.1 is not proved; the first part is deferred to the authors' [28]. This is a minor citation debt. The claim is plausible and the second part is trivial, but for a self-contained paper it should be proved or stated as a known lemma.\n\nThe self-citations to [18], [23], [28] are not a problem: the central results are not circular, and the cited results are used as tools, not as the main conclusions.\n\nWho is this for? Researchers in extremal set theory, communication complexity, and coding theory. It deserves a serious referee. My recommendation: send it to review. The referee should ask the authors to fix the numerical inequality in Section 3.1, patch the small-δ edge case in Theorem 1.10, and either prove Claim 4.1 or state it explicitly as a lemma from [28]. None of these should block acceptance after revision.","headline":"This is a strong paper that settles the Daykin–Erdős problem with optimal dependence and proves the Singer–Sudan conjecture; the main proofs hold up, but Section 3.1 contains a false inequality and Theorem 1.10 has a fixable small-family gap.","tokens_in":33800,"tokens_out":5618,"would_cite":true,"duration_ms":49090,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D05","05D40","15A03","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves the optimal disjoint-pairs bound for large set families, resolving the 40-year-old problem, and extends the same covering and discrepancy machinery to dense disjointness graphs, nonzero intersections, and low-rank…","keywords":["Daykin–Erdős problem","disjoint pairs","set systems","low-rank matrices","log-rank conjecture","constant submatrix","cover-free families","entropy method"],"falsifier":"Exhibit a family $F\\subseteq 2^{[n]}$ of size $2^{(1/2+\\delta)n}$ whose disjoint-pair density is $2^{-o(\\delta/\\log(1/\\delta))}$, which would beat the theorem's upper bound for every constant $c$; alternatively, find a family for which the expected union of $k$ uniform random members is smaller than $\\alpha n - Cn/2^k$, which would refute the lemma that drives the proof.","tokens_in":32653,"feed_emoji":"🧩","tokens_out":11843,"duration_ms":114560,"temperature":0.7,"pith_summary":"This paper settles a 40-year-old extremal problem about set systems: how many disjoint pairs of sets can a family of large size contain? The authors prove that a family with $m = 2^{(1/2+\\delta)n}$ sets on an $n$-element ground set has at most $m^2 2^{-c\\delta/\\log(1/\\delta)}$ disjoint pairs, and that a construction proposed in 1985 reaches this bound up to the constant $c$. The same arguments prove a conjecture about extracting completely disjoint subfamilies from a dense disjointness graph, and give matching bounds on all-zero and constant submatrices of low-rank matrices, with direct consequences for the log-rank conjecture and for cover-free codes. The proofs run through a covering argument using 'bad' sets, an entropy lemma that controls the growth of random unions, and a discrepancy bound for low-rank matrices.","feed_headline":"Optimal bound settles 40-year-old disjoint-pairs problem","feed_subtitle":"Matches the conjectured construction and yields sharp low-rank matrix rectangle bounds","key_machinery":"Three mechanisms carry the proof. The first is the bad-set covering argument: a set $U$ is bad for a family $\\mathcal F$ if it covers fewer than $2^{-2n/k}|\\mathcal F|$ members; the union of $k$ independent random sets is bad with probability at most $2^{-n}$, while the expected common neighbourhood of $k$ random vertices in a $\\delta$-dense disjointness graph is at least $\\delta^k|\\mathcal B|$, so a typical union yields large cross-disjoint subfamilies. The second is the entropy covering lemma: for every $\\mathcal F$ of size $2^{\\alpha n}$, independent uniform draws $F_1,\\dots,F_k$ satisfy $\\mathbb E|\\bigcup_i F_i|\\ge \\alpha n - Cn/2^k$, proved by writing the expected union as $\\sum_i(1-(1-p_i)^k)$ and comparing each term with the binary entropy $H(p_i)$; this makes random unions provably large and creates the contradiction with a small common neighbourhood. The third is a discrepancy bound for low-rank matrices: representing $M$ through singular vectors scaled by singular values and applying Grothendieck's inequality gives a half-size submatrix $M'$ with $\\|M\\|_C \\ge c\\sqrt{mn}\\,\\|M'\\|_F^2/(\\sqrt r\\|M\\|_F)$, where $\\|\\cdot\\|_C$ is the cut norm; iterating this discrepancy while reducing the average entry produces large all-zero or constant submatrices.","core_discovery":"The central claim is that the density of disjoint pairs in a family is controlled by the exponent $\\delta$ through the ratio $\\delta/\\log(1/\\delta)$. For $F\\subseteq 2^{[n]}$ with $|F|=m\\ge 2^{(1/2+\\delta)n}$, the number of disjoint unordered pairs is at most $m^2 2^{-c\\delta/\\log(1/\\delta)}$, and the construction from [2] with a split ground set and low-intersection layers has size $2^{(1/2+\\delta)n}$ and contains $m^2 2^{-O(\\delta/\\log(1/\\delta))}$ disjoint pairs, so the upper bound is optimal up to the constant $c$. In the bipartite form, two families of size at least $c_d\\,2^{n/2} n^d$ have at most $(1+o(1))2^{-2d}|A||B|$ disjoint pairs. The same covering mechanism proves that families with a constant density of pairs having intersection exactly $\\lambda\\neq 0$ still have size at most $2^{(1/2+o(1))n}$, and that disjointness density $\\delta$ forces cross-disjoint subfamilies of product size $|A||B|2^{-O(\\sqrt{n\\log(1/\\delta)})}$. For matrices, the paper shows that an $m\\times n$ rank-$r$ matrix with entries $0$ or at least $1$ and average $\\varepsilon\\le 1/2$ contains an all-zero submatrix of size $n2^{-O(\\log r+\\sqrt{\\varepsilon r})}$, optimal when $\\varepsilon\\gg(\\log r)^2/r$, and that integer matrices with entries $0,\\dots,t$ contain constant submatrices of size $2^{-O(t\\sqrt r)}m\\times 2^{-O(t\\sqrt r)}n$.","pith_inferences":["The entropy covering lemma suggests a transferable principle: for any large family, $k$ uniform random draws cover essentially as many coordinates as $k$ draws from a subcube of dimension $\\log_2|\\mathcal F|$. If this principle extends to other forbidden intersection patterns, the $\\lambda\\neq0$ variant of the disjoint-pairs problem could be sharpened from constant-density to subconstant density.","Theorem 1.12 shows the additive $\\log r$ loss in the all-zero rectangle bound is only needed when the average entry is very small; reaching the conjectured $2^{-O(\\sqrt{\\varepsilon r})}$ for all $\\varepsilon$ would require a new argument near the boundary $\\varepsilon\\sim(\\log r)^2/r$, which the construction in the paper shows is the delicate regime.","The bad-set covering proof of Lemma 1.11 is distribution-free and yields a quantitative covering probability; the same union-bound-over-bad-sets trick should give supersaturation bounds for other union-closed properties, such as $k$-wise disjointness or prescribed intersection sizes, with the same $2^{-O(n/r)}$ shape.","The bipartite reduction in the proof of Theorem 1.3 indicates that sharp constants for other intersection constraints might follow from the same discrepancy and entropy template; Problem 6.2 of the paper, whether a large family of pairs with intersection $\\lambda$ contains a large subfamily with all intersections exactly $\\lambda$, is a natural first test."],"forward_implications":["The 1985 construction is optimal up to a constant factor, so the maximum disjoint-pair density for families of size $2^{(1/2+\\delta)n}$ is $2^{-\\Theta(\\delta/\\log(1/\\delta))}$.","The biclique conjecture of [26] holds in strong quantitative form: disjointness density $\\delta$ always yields cross-disjoint subfamilies of size at least $|A||B|2^{-O(\\sqrt{n\\log(1/\\delta)})}$.","For every distribution $\\mu$ on $2^{[n]}$, the probability that $A_0\\subseteq A_1\\cup\\cdots\\cup A_r$ for independent draws is at least $2^{-n/r-2}$, which is tight up to the constant and sharpens the known supersaturation bound for $r$-cover-free families.","The sparse low-rank matrix conjecture from [22] is confirmed for separated matrices: if the average entry of a rank-$r$ matrix is $\\varepsilon\\le1/2$, an all-zero submatrix of size $n2^{-O(\\log r+\\sqrt{\\varepsilon r})}$ exists, and this is optimal in the regime $\\varepsilon\\gg(\\log r)^2/r$.","Log-rank-type rectangle bounds extend beyond binary matrices: integer matrices with entries $0,\\dots,t$ and rank $r$ contain a constant submatrix of size $2^{-O(t\\sqrt r)}m\\times 2^{-O(t\\sqrt r)}n$."],"supporting_citations":[{"why":"Supplies the original bound for the disjoint-pairs problem and the construction that the paper shows is optimal.","marker":"[2]"},{"why":"Posed the biclique problem for dense disjointness graphs; Theorem 1.10 proves it and its lower-bound construction shows the conjecture is sharp.","marker":"[26]"},{"why":"Proposed Conjecture 1.8 on all-zero rectangles in sparse low-rank matrices; Theorem 1.12 confirms it for separated matrices and improves the prior log-rank rectangle bound.","marker":"[22]"},{"why":"Introduced the matrix discrepancy approach for binary matrices and the best known log-rank bound; Theorem 1.12 extends it to separated nonnegative matrices.","marker":"[28]"},{"why":"Proved the conditional additive-combinatorics result used in Theorem 1.5 to find large subfamilies with constant intersection modulo p.","marker":"[5]"},{"why":"Extended the partial approximate-duality result to all primes, which Theorem 1.5 needs for the prime p in the Fourier argument.","marker":"[7]"},{"why":"Gives the bound |A'||B'|≤2^r for families with constant intersection size, used in Theorem 1.5 and in Construction 3.","marker":"[25]"},{"why":"Provides the subadditivity of entropy used to prove the covering lemma that drives Theorems 1.2 and 1.3.","marker":"[4]"},{"why":"Grothendieck's inequality, used in Lemma 4.2 to lower-bound the cut norm of low-rank matrices.","marker":"[16]"},{"why":"Proves the polynomial Freiman-Ruzsa conjecture, making the result of [5] unconditional so that Theorem 1.5 can use it.","marker":"[14]"}],"fun_headline_variants":["Optimal disjoint-pair bound ends 40-year wait","Disjoint-pair density fixed sharp for sets and matrices","Sharp low-rank matrix zeros from set disjointness","Optimal bound for disjoint pairs and zero submatrices"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the entropy covering lemma: for every family $\\mathcal F$ of size $2^{\\alpha n}$, the union of $k$ independent uniform random sets from $\\mathcal F$ has expected size at least $\\alpha n - Cn/2^k$ with an absolute constant $C$; if that universal union-growth bound failed, the dependent-random-choice contradiction behind Theorems 1.2 and 1.3 would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Optimal disjoint-pair bound ends 40-year wait","Disjoint-pair density fixed sharp for sets and matrices","Sharp low-rank matrix zeros from set disjointness","Optimal bound for disjoint pairs and zero submatrices"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000364,"raw_usage":{"total_tokens":2184,"prompt_tokens":1391,"completion_tokens":793,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":1007,"completion_tokens_details":{"reasoning_tokens":728}},"tokens_in":1007,"tokens_out":793,"duration_ms":9018,"temperature":1.0,"reasoning_tokens":728,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:23:42.050798+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a family $F\\subseteq 2^{[n]}$ of size $2^{(1/2+\\delta)n}$ whose disjoint-pair density is $2^{-o(\\delta/\\log(1/\\delta))}$, which would beat the theorem's upper bound for every constant $c$; alternatively, find a family for which the expected union of $k$ uniform random members is smaller than $\\alpha n - Cn/2^k$, which would refute the lemma that drives the proof.","supporting_citations":[{"cited_title":"Alon and P","cited_arxiv_id":null,"evidence_quote":"Supplies the original bound for the disjoint-pairs problem and the construction that the paper shows is optimal."},{"cited_title":"Singer and M","cited_arxiv_id":null,"evidence_quote":"Posed the biclique problem for dense disjointness graphs; Theorem 1.10 proves it and its lower-bound construction shows the conjecture is sharp."},{"cited_title":"Sudakov and I","cited_arxiv_id":null,"evidence_quote":"Introduced the matrix discrepancy approach for binary matrices and the best known log-rank bound; Theorem 1.12 extends it to separated nonnegative matrices."},{"cited_title":"Ben-Sasson, S","cited_arxiv_id":null,"evidence_quote":"Proved the conditional additive-combinatorics result used in Theorem 1.5 to find large subfamilies with constant intersection modulo p."},{"cited_title":"Bhowmick, Z","cited_arxiv_id":null,"evidence_quote":"Extended the partial approximate-duality result to all primes, which Theorem 1.5 needs for the prime p in the Fourier argument."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the bound |A'||B'|≤2^r for families with constant intersection size, used in Theorem 1.5 and in Construction 3."},{"cited_title":"Alon and J","cited_arxiv_id":null,"evidence_quote":"Provides the subadditivity of entropy used to prove the covering lemma that drives Theorems 1.2 and 1.3."},{"cited_title":"Grothendieck","cited_arxiv_id":null,"evidence_quote":"Grothendieck's inequality, used in Lemma 4.2 to lower-bound the cut norm of low-rank matrices."}],"review_version":1}