{"id":"fc18f23f-6aeb-41e4-95a4-b7a11168771b","arxiv_id":"2411.15137","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Any subset of {0,1,2}^n with density at least (log log log log n)^(-c) contains a combinatorial line of length 3.","lead":"This paper proves that any subset of the high-dimensional grid {0,1,2}^n of density at least (log log log log n)^(-c) must contain a combinatorial line, improving the 2012 Polymath bound. The proof introduces a new density-increment strategy that brings the density Hales-Jewett theorem into the range of reasonable bounds.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central bound hinges on unproven quantitative inverse theorems from companion papers: if the stated gamma >= exp(-epsilon^{-O_alpha(1)}) is weaker or Theorem 3 needs extra hypotheses, the (log log log log n)^{-c} threshold breaks.","rationale":"The reader's CONDITIONAL verdict identifies the same load-bearing assumption: the black-box inverse theorems. I agree. I checked the internal chain from Lemma 5.2 through Theorem 5 and found the Cauchy-Schwarz manipulations and density-increment arithmetic coherent; the connectedness assertions in Lemmas 5.8, 6.1, 6.2, and 6.3 are asserted tersely but appear to hold for the listed supports. The genuinely load-bearing uncertainty is external. The paper's own Section 1.2 says the relevant inverse theorem for pairwise-connected distributions from [BKLM24a] 'does not immediately imply any bounds for the DHJ[3] problem', and the proof works around this by using Theorems 2 and 3 as black boxes. Quantitatively, Theorem 6 loses dimension at a rate governed by gamma^{-4}; the four-iterated-log threshold depends on that rate being at most exp(epsilon^{-O(1)}) rather than a double exponential. Since the companion papers are not included and are not machine-checked, the central claim cannot be fully verified from this preprint alone. This does not amount to a discovered flaw; it is a precise condition whose failure would destroy the claimed bound. The recommended verdict stays CONDITIONAL, unchanged from the reader.","tokens_in":31779,"tokens_out":33192,"duration_ms":281902,"concrete_test":"Audit the companion papers: extract from [BKLM24a] and [BKLM24b] the exact quantitative statement proved for gamma as a function of alpha and epsilon (Theorems 2 and 3 as cited), and verify (a) it is at least exp(-epsilon^{-O_alpha(1)}), not merely exp(-exp(epsilon^{-O(1)})), and (b) Theorem 3's hypothesis is only connectedness of mu_123, not pairwise-connectedness. Then recompute the exponent in Theorem 6 with the audited bound; if gamma^{-4} becomes exp(exp(epsilon^{-O(1)})) rather than exp(epsilon^{-O(1)}), the final iteration budget fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The final density threshold is controlled by the dimension loss in Theorem 6, n' >= n^{1000^{-O(delta^{-1} tau^{-1} gamma^{-4})}}. For the iteration to survive, gamma must be at least exp(-epsilon^{-O_alpha(1)}) with epsilon of order alpha^3 delta^2; this is exactly the quantitative form imported from Theorems 2 and 3 of the companion papers [BKLM24a, BKLM24b], together with the density-increment lemma from [BKLM24a, Section 8]. The present paper quotes these as black boxes and does not prove them. If the true bound in either companion theorem were only exp(-exp(epsilon^{-O(1)})) (double-exponential), or if Theorem 3 required pairwise-connectedness rather than only connectedness of mu_123, then the applications in Lemmas 5.8, 6.1, 6.2, and 6.3 would fail or would force a much larger gamma^{-4}, and the claimed (log log log log n)^{-c} bound would not follow. Several 'it can be checked' connectedness assertions for the distributions in Tables 1-3 are also not expanded; each is load-bearing because Theorem 3 is invoked only when those supports are connected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that every subset of [3]^n of density at least C (log log log log n)^{-c} contains a combinatorial line of length 3, improving the previous bound Omega((log* n)^{-1/2}) of Polymath 2012. The proof adapts Shkredov's density-increment proof for corners to DHJ[3], using a notion of product pseudorandomness and quantitative inverse theorems for pairwise-connected and connected distributions imported from two companion papers by the same authors. The argument maintains a set S of relative density inside a disjoint product E1 ⊠ E2, and alternates between a density-increment step (Sections 5-6) and a uniformization step (Section 7) that restores product pseudorandomness at a polynomial cost in dimension, leading to the iterated-logarithm bound.","tokens_in":32029,"tokens_out":39811,"duration_ms":343601,"significance":"If the proof is correct, this is a substantial quantitative advance for DHJ[3], replacing a tower-type bound with a very slowly growing iterated-logarithmic density threshold. The conceptual contribution — importing quantitative inverse theorems for CSPs into the Shkredov/Polymath framework — is novel and likely to be influential. The paper is carefully structured and the final parameter arithmetic is internally consistent. However, the central claim depends on the exact quantitative form of two black-box inverse theorems from unpublished companion papers, and on several connectivity checks that are asserted rather than shown; these points must be resolved before the result can be considered established.","major_comments":[{"comment":"The proof of Theorem 1 relies on Theorems 2 and 3 and on the density-increment lemma from [BKLM24a, Section 8] as black boxes. These are same-author companion papers that are not proved or included here, and the references give no venue or preprint availability. The claimed bound (log log log log n)^{-c} depends exactly on the quantitative form gamma >= exp(-epsilon^{-O_alpha(1)}) (see §2.4 and the dimension loss in Theorem 6): if the true bounds were only double-exponential in epsilon^{-1}, or if Theorem 3 required a stronger connectivity hypothesis, the iteration would not close. The manuscript should either include complete proofs of these theorems in an appendix or rely on publicly available, refereed versions; as it stands, the main theorem is conditional on unverified external results.","section":"§3.2, §5-6"},{"comment":"The proof of Lemma 5.8 states that the projections of the support of (pi1(y), pi2(y), pi1(z), pi2(z)) to coordinates 234 and 123 are connected, and then says the result follows by expanding E1 and E2 and applying Theorem 3. This is not sufficient. Theorem 3 is asymmetric: to apply it to a function on a given coordinate, one needs the marginal on the other three coordinates to be connected. For the support S4 = {(0,0,0,0),(1,0,1,0),(0,2,0,2),(1,0,0,2)}, the projections to 134 and 124 are disconnected (the point (1,1,0) is isolated in 134, and (0,2,2) is isolated in 124). Hence Theorem 3 cannot directly control terms in the expansion where the non-constant factor is E1 - delta1 applied to pi1(z) or E2 - delta2 applied to pi2(y). An additional argument, for example a Cauchy-Schwarz reduction to correlations on the connected coordinates, is needed before this load-bearing lemma is justified.","section":"§5.2, Lemma 5.8"},{"comment":"The proof of Lemma 7.1 requires gamma to be substantially larger than m^{-1/72}: the displayed inequalities 'gamma - 101 m^{-1/72}' and the final bound E[mu(E1'')^2] >= mu(E1)^2 + 0.6 gamma^4 only give an index increment when gamma^2 >> m^{-1/72}. The lemma statement does not include any such hypothesis, and for gamma <= m^{-1/72} the proof's lower bounds are vacuous, so the claimed increment fails. In the final application the chosen gamma = exp(-exp(alpha_0^{-O(1)})) and the maintained dimension at least exp((log n)^{0.999}) do satisfy the needed condition, but this dependence should be stated explicitly in Lemma 7.1 or Theorem 6 rather than left implicit.","section":"§7, Lemma 7.1"}],"minor_comments":[{"comment":"The theorem is stated for all positive integers n, but the iterated logarithm is not defined for small n and the statement is false for n = 1 (a singleton has no combinatorial line of length 3). It should be stated for all sufficiently large n, or the iterated logarithm and the constants should be defined so that small n are handled separately.","section":"Abstract and Theorem 1"},{"comment":"The notation 'I ~ delta [n]' is used in Definition 3.1 but only 'I ~ 1-alpha [n]' is defined in Definition 1.2. Define the general notation explicitly to avoid ambiguity about whether delta denotes the probability of inclusion in the fixed set or the remaining set.","section":"§1.3 and §3.1"},{"comment":"The tables list supports but not the masses of the distributions mu1, mu2, mu3. Since Theorem 3 requires each atom to have probability at least alpha and the connectivity checks depend on the support, please state the exact masses or explain how they are derived from the construction in Theorem 4.","section":"Tables 1-3"},{"comment":"Several load-bearing connectivity assertions are only given as 'it can be checked' or 'can easily be seen' (in Lemmas 5.8, 6.1, 6.2, and 6.3). Given that the inverse theorems are applied only when these connectedness conditions hold, these checks should be written out explicitly or placed in an appendix.","section":"§5.2, §6.1, §6.2"},{"comment":"There are multiple typographical errors, including 'combiantorial' in the Introduction, the malformed density expression in the abstract, and stray spacing in equations. A careful proofreading pass is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"This is a potentially important paper, but the refereeing verdict is driven by three concerns: (1) the main theorem is conditional on quantitative inverse theorems from two companion papers by the same authors that are not proved or publicly available in refereed form; (2) the proof of Lemma 5.8 appears to have a real gap, because two of the four three-coordinate projections of the relevant 4-ary distribution are disconnected, so Theorem 3 cannot be applied directly to all expansion terms; (3) Lemma 7.1 needs an explicit lower bound on gamma relative to the dimension. These issues are load-bearing but may be fixable, so I recommend major revision rather than rejection. I see no circularity with DHJ[3]: the companion results concern pairwise-connected and connected distributions and do not themselves imply DHJ[3]."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe paper you asked about proves the first sub-tower density bound for DHJ[3]: density at least (log log log log n)^(-c) forces a length-3 combinatorial line, improving Polymath's (log* n)^(-1/2). This is real progress and not a routine tweak. The proof combines Shkredov's corners strategy with product pseudorandomness and inverse theorems for pairwise-connected CSPs. The architecture is new, and the paper explains the dictionary carefully.\n\nThe soft spot is exactly where the reader's report puts it: the central quantitative engine is two black-box inverse theorems from companion papers by the same authors (Theorems 2 and 3, plus a density-increment lemma from BKLM24a, Section 8). If those theorems have weaker quantitative bounds, or if Theorem 3's connectedness hypothesis fails for one of the supports in Tables 1-3, the (log log log log n)^(-c) threshold breaks. Several \"it can be checked\" connectedness claims are load-bearing and not expanded. I checked the tables and they look plausible, but this preprint alone does not let me verify the full chain.\n\nThat said, this is a normal way for a research program to develop, and the dependence is disclosed, not hidden. The invoked theorems concern pairwise-connected distributions; the DHJ[3] measure is explicitly not pairwise-connected, so the paper is not assuming its own conclusion. The novelty is precisely forcing DHJ[3] into that framework. I see no circularity.\n\nThe parameter section (2.4) is terse to the point of being cryptic: the relation between gamma, delta, and the final iterated log is sketched rather than proved, and the dimension loss in Theorem 6 momentarily reads as n times exp(-O(...)) instead of n^{exp(-O(...))}. A referee should ask for a clean accounting there.\n\nWho is this for? Anyone working on quantitative density Hales-Jewett or on CSP inverse theorems applied to additive combinatorics. It deserves a serious referee: the main theorem is important, the strategy is credible, and the dependence on companions is explicit. I would send it to review and would bring it to reading group to walk through Sections 5-6. I would cite it if I worked in this area.\n\nNet: conditional acceptance, with the condition being verification of the companion theorems and the connectedness checks. Not a desk reject.","headline":"First sub-tower bound for DHJ[3] via a genuinely new Shkredov-style framework; the main caveat is heavy dependence on same-author companion theorems.","tokens_in":32612,"tokens_out":3172,"would_cite":true,"duration_ms":30686,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D10","11B30"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that any subset of the ternary cube [3]^n with density at least (log log log log n)^{-c} contains a combinatorial line of length three, improving the previous (log* n)^{-1/2} bound.","keywords":["density Hales-Jewett theorem","combinatorial lines","DHJ(3)","density increment","product pseudorandomness","inverse theorems for CSPs","Shkredov corners method","Szemerédi-type bounds"],"falsifier":"Run a finite connectedness check on the auxiliary distributions in Tables 1-3: each projection onto any three coordinates is asserted to be connected, and the Cauchy-Schwarz chain invokes the four-ary inverse theorem through exactly those projections. A disconnected projection would break the proof; if all are connected, that link is sound. To decide Theorem 1 itself, one would need a counterexample to the imported inverse theorems at the stated quantitative scale, or an explicit line-free set in [3]^n with density above C(log log log log n)^{-c}, neither of which is known.","tokens_in":31561,"feed_emoji":"🎲","tokens_out":10095,"duration_ms":98591,"temperature":0.7,"pith_summary":"The paper aims to show how large a subset of the ternary cube [3]^n must be before it is forced to contain three points that form a combinatorial line of length three. It proves that density (log log log log n)^{-c} suffices, for a constant c, which is a much smaller required density than the previous sufficient bound $\\Omega$((log* n)^{-1/2}). Equivalently, the threshold has dropped from a tower of height depending on the density to a fixed four-fold iterated logarithm. This matters because the density Hales-Jewett theorem is a common source of quantitative bounds for Szemerédi-type and corners-type problems, and its known bounds have been notoriously weak. The authors reach the new bound by adapting Shkredov's density-increment strategy for corners and importing inverse theorems about product-like structure from two companion papers.","feed_headline":"Four nested logarithms force a combinatorial line","feed_subtitle":"Any subset of the ternary cube at density (log log log log n)^-c must contain a length-3 line, beating the old log-star bound.","key_machinery":"The load-bearing object is product pseudorandomness: a 1-bounded function is (n', gamma)-product pseudorandom if, after any random restriction leaving at least n' coordinates, the probability that the restriction correlates by gamma or more with a product of single-coordinate 1-bounded functions is less than gamma. Its partner is the disjoint product E1 ⊠ E2, the analogue of a rectangle in the corners proof, consisting of strings whose set of 1s lies in E1 and whose set of 2s lies in E2. The proof alternates between two operations: uniformization converts non-pseudorandom E1 and E2 into pseudorandom ones while preserving density, and a Cauchy-Schwarz box-norm argument converts a large triple correlation over the DHJ[3] distribution into a four-fold correlation that yields a density increment. The imported inverse theorems (Theorems 2 and 3) are the engine that makes both operations work: they certify that large correlation over a connected or pairwise-connected distribution implies product correlation after random restriction.","core_discovery":"On the paper's own terms, the discovery is Theorem 1: for every n and every A subset [3]^n with $3^{{-n}}$|A| >= C(log log log log n)^{-c}, there are x, y, z in A, not all equal, with each coordinate either constant or equal to (0,1,2). The proof proceeds by contradiction: assume A has no such line and run a density-increment scheme that maintains a set S of relative density $\\alpha$ inside a 'disjoint product' E1 ⊠ E2, where E1 encodes the positions of 1s and E2 the positions of 2s. Each no-line step either increases $\\alpha$ by $\\Omega$($alpha^{15}$) or passes to a smaller instance on which E1 and E2 are product-pseudorandom; the increment is forced by a large box-norm correlation obtained through repeated Cauchy-Schwarz manipulations. The paper's central structural claim is that product pseudorandomness, rather than Fourier pseudorandomness, is the right notion of pseudorandomness in this setting, and that the imported inverse theorems reduce the necessary analysis to checking connectedness of several small auxiliary distributions.","pith_inferences":["The four-fold iterated logarithm is not obviously the end of the line: the bottleneck is the gamma >= exp(-epsilon^{-O_alpha(1)}) dependence in the imported inverse theorems, so any future improvement in those constants should translate directly into a better DHJ[3] bound.","The disjoint-product and product-pseudorandomness dictionary may extend to other distributions whose support is not pairwise-connected, such as the corners distribution, potentially yielding comparable quantitative improvements for corners and multidimensional Szemerédi problems.","A low-cost internal check of the proof is to verify computationally that the small distributions in Tables 1-3 have all the connected projections the proof claims; this does not test the inverse theorems, but it isolates the finite combinatorial part of the argument and would catch a discrete mistake near the Cauchy-Schwarz chain."],"forward_implications":["As a direct consequence of Theorem 1, any subset of [3]^n with density at least C(log log log log n)^{-c} contains a combinatorial line of length three; equivalently, the density Hales-Jewett theorem for k=3 holds with a fixed finite tower of exponentials in 1/density.","The new bound subsumes and improves the previous Polymath bound, which required density Omega((log* n)^{-1/2}), so the paper reduces the required density for large n by a substantial margin.","The proof's density-increment scheme gives a quantitative structure theorem: a set avoiding lines forces successive relative densities at least alpha + Omega(alpha^15) on nested disjoint products, with dimension shrinking only by a controlled factor, until contradiction.","Consequently, to disprove Theorem 1 it would not be enough to find line-free sets at the known Behrend-style lower-bound scale exp(-(log n)^{1/2}); one would need a line-free set at the much larger four-fold-log density scale.","The method demonstrates that the non-pairwise-connected DHJ[3] distribution can be controlled by decomposing it into connected pieces and then invoking inverse theorems for pairwise-connected and connected CSP distributions."],"supporting_citations":[{"why":"Supplies the previous best bound and the combinatorial DHJ proof whose dictionary of equal-slices measure, insensitive sets, and subspace splitting the paper adapts.","marker":"[Pol12]"},{"why":"Shkredov's corners density-increment strategy is the high-level template the paper translates to the DHJ[3] setting.","marker":"[Shk06]"},{"why":"Provides the black-box 3-ary inverse theorem for pairwise-connected distributions, stated as Theorem 2, and the density-increment lemma from its Section 8 used in the uniformization step.","marker":"[BKLM24a]"},{"why":"Provides the black-box 4-ary inverse theorem for connected marginals, stated as Theorem 3, used to control products of the E1 and E2 indicator functions inside the Cauchy-Schwarz chain.","marker":"[BKLM24b]"},{"why":"Supplies the restricted 3-arithmetic-progression density-increment technology that underlies the product-function density increments in the uniformization step.","marker":"[BKM23a]"}],"fun_headline_variants":["Four logs beat log-star for combinatorial lines","Quadruple-log density forces a 3-line in [3]^n","From log-star to four logs: improved density bound","No line-free set at (log log log log n)^-c"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that two structural theorems from the companion papers are correct and quantitatively as strong as stated: any large statistical dependence surviving random restrictions must be a product of independent per-coordinate factors, at the exact strength needed for the four-log threshold.","fun_headline_variants_meta":{"raw":{"variants":["Four logs beat log-star for combinatorial lines","Quadruple-log density forces a 3-line in [3]^n","From log-star to four logs: improved density bound","No line-free set at (log log log log n)^-c"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001356,"raw_usage":{"total_tokens":5483,"prompt_tokens":906,"completion_tokens":4577,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":522,"completion_tokens_details":{"reasoning_tokens":4506}},"tokens_in":522,"tokens_out":4577,"duration_ms":37589,"temperature":1.0,"reasoning_tokens":4506,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:28:22.862679+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a finite connectedness check on the auxiliary distributions in Tables 1-3: each projection onto any three coordinates is asserted to be connected, and the Cauchy-Schwarz chain invokes the four-ary inverse theorem through exactly those projections. A disconnected projection would break the proof; if all are connected, that link is sound. To decide Theorem 1 itself, one would need a counterexample to the imported inverse theorems at the stated quantitative scale, or an explicit line-free set in [3]^n with density above C(log log log log n)^{-c}, neither of which is known.","supporting_citations":[],"review_version":1}